cds/memory/vyukov_queue_pool.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
  32 #define CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
  33
  34 #include <cds/details/allocator.h>
  35 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
  36
  37 namespace cds { namespace memory {
  38
  39     /// \p vyukov_queue_pool traits
  40     /** @ingroup cds_memory_pool
  41     */
  42     struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
  43     {
  44         /// Allocator type
  45         typedef CDS_DEFAULT_ALLOCATOR allocator;
  46     };
  47
  48     /// Free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
  49     /** @ingroup cds_memory_pool
  50         Template parameters:
  51         - \p T - the type of object maintaining by free-list
  52         - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
  53             \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
  54
  55         \b Internals
  56
  57         This free-list is very simple.
  58         At construction time, the free-list allocates the array of N items
  59         and stores them into queue, where N is the queue capacity.
  60         When allocating the free-list tries to pop an object from
  61         internal queue i.e. from preallocated pool. If success the popped object is returned.
  62         Otherwise a new one is allocated. When deallocating, the free-list checks whether
  63         the object is from preallocated pool. If so, the object is pushed into queue, otherwise
  64         it is deallocated by using the allocator provided.
  65         The pool can manage more than \p N items but only \p N items is contained in the free-list.
  66
  67         \b Usage
  68
  69         \p %vyukov_queue_pool should be used together with \ref pool_allocator.
  70         You should declare an static object of type \p %vyukov_queue_pool, provide
  71         an accessor to that object and use \p pool_allocator as an allocator:
  72         \code
  73         #include <cds/memory/vyukov_queue_pool.h>
  74         #include <cds/memory/pool_allocator.h>
  75
  76         // Pool of Foo object of size 1024.
  77         struct pool_traits: public cds::memory::vyukov_queue_pool_traits
  78         {
  79             typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
  80         };
  81         typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
  82         static pool_type thePool;
  83
  84         struct pool_accessor {
  85             typedef typename pool_type::value_type  value_type;
  86
  87             pool_type& operator()() const
  88             {
  89                 return thePool;
  90             }
  91         };
  92
  93         // Declare pool allocator
  94         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
  95
  96         // Use pool_allocator
  97         // Allocate an object
  98         Foo * p = pool_allocator().allocate( 1 );
  99
 100         // construct object
 101         new(p) Foo;
 102
 103         //...
 104
 105         // Destruct object
 106         p->~Foo();
 107
 108         // Deallocate object
 109         pool_allocator().deallocate( p , 1 );
 110         \endcode
 111     */
 112     template <typename T, typename Traits = vyukov_queue_pool_traits >
 113     class vyukov_queue_pool
 114     {
 115     public:
 116         typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type  ;   ///< Queue type
 117
 118     public:
 119         typedef T  value_type ; ///< Value type
 120         typedef Traits traits;  ///< Traits type
 121         typedef typename traits::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
 122         typedef typename traits::back_off back_off; ///< back-off strategy
 123
 124     protected:
 125         //@cond
 126         typedef cds::details::Allocator< value_type, allocator_type >   cxx_allocator;
 127
 128         queue_type      m_Queue;
 129         value_type *    m_pFirst;
 130         value_type *    m_pLast;
 131         //@endcond
 132
 133     protected:
 134         //@cond
 135         void preallocate_pool()
 136         {
 137             m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
 138             m_pLast = m_pFirst + m_Queue.capacity();
 139
 140             for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
 141                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
 142             }
 143         }
 144
 145         bool from_pool( value_type * p ) const
 146         {
 147             return m_pFirst <= p && p < m_pLast;
 148         }
 149         //@endcond
 150
 151     public:
 152         /// Preallocates the pool of object
 153         /**
 154             \p nCapacity argument is the queue capacity. It should be passed
 155             if the queue is based on dynamically-allocated buffer.
 156             See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
 157         */
 158         vyukov_queue_pool( size_t nCapacity = 0 )
 159             : m_Queue( nCapacity )
 160         {
 161             preallocate_pool();
 162         }
 163
 164         /// Deallocates the pool.
 165         ~vyukov_queue_pool()
 166         {
 167             m_Queue.clear();
 168             cxx_allocator().Delete( m_pFirst, m_Queue.capacity());
 169         }
 170
 171         /// Allocates an object from pool
 172         /**
 173             The pool supports allocation only single object (\p n = 1).
 174             If \p n > 1 the behaviour is undefined.
 175
 176             If the queue is not empty, the popped value is returned.
 177             Otherwise, a new value allocated.
 178         */
 179         value_type * allocate( size_t n )
 180         {
 181             assert( n == 1 );
 182             CDS_UNUSED(n);
 183
 184             value_type * p = m_Queue.pop();
 185             if ( p ) {
 186                 assert( from_pool(p) );
 187                 return p;
 188             }
 189             // The pool is empty - allocate new from the heap
 190             return cxx_allocator().New();
 191         }
 192
 193         /// Deallocated the object \p p
 194         /**
 195             The pool supports allocation only single object (\p n = 1).
 196             If \p n > 1 the behaviour is undefined.
 197
 198             If \p p is from preallocated pool, it pushes into the queue.
 199             Otherwise, \p p is deallocated by allocator provided.
 200         */
 201         void deallocate( value_type * p, size_t n )
 202         {
 203             assert( n == 1 );
 204             CDS_UNUSED(n);
 205
 206             if ( p ) {
 207                 if ( from_pool(p) ) {
 208                     // The queue can notify about false fullness state
 209                     // so we push in loop
 210                     back_off bkoff;
 211                     while ( !m_Queue.push( *p ))
 212                         bkoff();
 213                 }
 214                 else
 215                     cxx_allocator().Delete( p );
 216             }
 217         }
 218     };
 219
 220
 221     /// Lazy free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
 222     /** @ingroup cds_memory_pool
 223         Template parameters:
 224         - \p T - the type of object maintaining by free-list
 225         - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
 226             \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
 227
 228         \b Internals
 229
 230         This free-list is very simple.
 231         At construction time the pool is empty.
 232         When allocating the free-list tries to pop an object from
 233         internal queue. If success the popped object is returned.
 234         Otherwise a new one is allocated.
 235         When deallocating, the free-list tries to push the object into the pool.
 236         If internal queue is full, the object is deallocated by using the allocator provided.
 237         The pool can manage more than \p N items but only \p N items is placed in the free-list.
 238
 239         \b Usage
 240
 241         \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
 242         You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
 243         an accessor functor to this object and use \p pool_allocator as an allocator:
 244         \code
 245         #include <cds/memory/vyukov_queue_pool.h>
 246         #include <cds/memory/pool_allocator.h>
 247
 248         // Pool of Foo object of size 1024.
 249         typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
 250         static pool_type thePool( 1024 );
 251
 252         struct pool_accessor {
 253             typedef typename pool_type::value_type  value_type;
 254
 255             pool_type& operator()() const
 256             {
 257                 return thePool;
 258             }
 259         };
 260
 261         // Declare pool allocator
 262         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
 263
 264         // Use pool_allocator
 265         // Allocate an object
 266         Foo * p = pool_allocator().allocate( 1 );
 267
 268         // construct object
 269         new(p) Foo;
 270
 271         //...
 272
 273         // Destruct object
 274         p->~Foo();
 275
 276         // Deallocate object
 277         pool_allocator().deallocate( p , 1 );
 278         \endcode
 279
 280     */
 281     template <typename T, typename Traits = vyukov_queue_pool_traits>
 282     class lazy_vyukov_queue_pool
 283     {
 284     public:
 285         typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type  ;   ///< Queue type
 286
 287     public:
 288         typedef T  value_type ; ///< Value type
 289         typedef Traits traits;  ///< Pool traits
 290         typedef typename traits::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
 291
 292     protected:
 293         //@cond
 294         typedef cds::details::Allocator< value_type, allocator_type >   cxx_allocator;
 295
 296         queue_type      m_Queue;
 297         //@endcond
 298
 299     public:
 300         /// Constructs empty pool
 301         lazy_vyukov_queue_pool( size_t nCapacity = 0 )
 302             : m_Queue( nCapacity )
 303         {}
 304
 305         /// Deallocates all objects from the pool
 306         ~lazy_vyukov_queue_pool()
 307         {
 308             cxx_allocator a;
 309             while ( !m_Queue.empty() )
 310                 a.Delete( m_Queue.pop());
 311         }
 312
 313         /// Allocates an object from pool
 314         /**
 315             The pool supports allocation only single object (\p n = 1).
 316             If \p n > 1 the behaviour is undefined.
 317
 318             If the queue is not empty, the popped value is returned.
 319             Otherwise, a new value allocated.
 320         */
 321         value_type * allocate( size_t n )
 322         {
 323             assert( n == 1 );
 324             CDS_UNUSED(n);
 325
 326             value_type * p = m_Queue.pop();
 327             if ( p )
 328                 return p;
 329
 330             return cxx_allocator().New();
 331         }
 332
 333         /// Deallocates the object \p p
 334         /**
 335             The pool supports allocation only single object (\p n = 1).
 336             If \p n > 1 the behaviour is undefined.
 337
 338             If the queue is not full, \p p is pushed into the queue.
 339             Otherwise, \p p is deallocated by allocator provided.
 340         */
 341         void deallocate( value_type * p, size_t n )
 342         {
 343             assert( n == 1 );
 344             CDS_UNUSED(n);
 345
 346             if ( p ) {
 347                 // Here we ignore false fullness state of the queue
 348                 if ( !m_Queue.push( *p ))
 349                     cxx_allocator().Delete( p );
 350             }
 351         }
 352
 353     };
 354
 355     /// Bounded free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
 356     /** @ingroup cds_memory_pool
 357         Template parameters:
 358         - \p T - the type of object maintaining by free-list
 359         - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
 360             \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
 361
 362         \b Internals
 363
 364         At construction time, the free-list allocates the array of N items
 365         and stores them into the queue, where N is the queue capacity.
 366         When allocating the free-list tries to pop an object from
 367         internal queue i.e. from preallocated pool. If success the popped object is returned.
 368         Otherwise a \p std::bad_alloc exception is raised.
 369         So, the pool can contain up to \p N items.
 370         When deallocating, the object is pushed into the queue.
 371         In debug mode \p deallocate() member function asserts
 372         that the pointer is from preallocated pool.
 373
 374         \b Usage
 375
 376         \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
 377         You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
 378         an accessor functor to this object and use \p pool_allocator as an allocator:
 379         \code
 380         #include <cds/memory/vyukov_queue_pool.h>
 381         #include <cds/memory/pool_allocator.h>
 382
 383         // Pool of Foo object of size 1024.
 384         struct pool_traits: public cds::memory::vyukov_queue_pool_traits
 385         {
 386             typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
 387         };
 388         typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
 389         static pool_type thePool;
 390
 391         struct pool_accessor {
 392             typedef typename pool_type::value_type  value_type;
 393
 394             pool_type& operator()() const
 395             {
 396                 return thePool;
 397             }
 398         };
 399
 400         // Declare pool allocator
 401         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
 402
 403         // Use pool_allocator
 404         // Allocate an object
 405         Foo * p = pool_allocator().allocate( 1 );
 406
 407         // construct object
 408         new(p) Foo;
 409
 410         //...
 411
 412         // Destruct object
 413         p->~Foo();
 414
 415         // Deallocate object
 416         pool_allocator().deallocate( p , 1 );
 417         \endcode
 418     */
 419     template <typename T, typename Traits = vyukov_queue_pool_traits >
 420     class bounded_vyukov_queue_pool
 421     {
 422         //@cond
 423         struct internal_traits : public Traits {
 424             typedef cds::atomicity::item_counter item_counter;
 425         };
 426         //@endcond
 427     public:
 428         typedef cds::intrusive::VyukovMPMCCycleQueue< T, internal_traits > queue_type  ;   ///< Queue type
 429
 430     public:
 431         typedef T  value_type;  ///< Value type
 432         typedef Traits traits;  ///< Pool traits
 433         typedef typename traits::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
 434         typedef typename traits::back_off back_off; ///< back-off strategy
 435
 436     protected:
 437         //@cond
 438         typedef cds::details::Allocator< value_type, allocator_type >   cxx_allocator;
 439
 440         queue_type      m_Queue;
 441         value_type *    m_pFirst;
 442         value_type *    m_pLast;
 443         //@endcond
 444
 445     protected:
 446         //@cond
 447         void preallocate_pool()
 448         {
 449             size_t const nCount = m_Queue.capacity();
 450             m_pFirst = cxx_allocator().NewArray( nCount );
 451             m_pLast = m_pFirst + nCount;
 452
 453             for ( value_type * p = m_pFirst; p < m_pLast; ++p )
 454                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
 455         }
 456
 457         bool from_pool( value_type * p ) const
 458         {
 459             return m_pFirst <= p && p < m_pLast;
 460         }
 461         //@endcond
 462
 463     public:
 464         /// Preallocates the pool of object
 465         /**
 466             \p nCapacity argument is the queue capacity. It should be passed
 467             if the queue is based on dynamically-allocated buffer.
 468             See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
 469         */
 470         bounded_vyukov_queue_pool( size_t nCapacity = 0 )
 471             : m_Queue( nCapacity )
 472         {
 473             preallocate_pool();
 474         }
 475
 476         /// Deallocates the pool.
 477         ~bounded_vyukov_queue_pool()
 478         {
 479             m_Queue.clear();
 480             cxx_allocator().Delete( m_pFirst, m_Queue.capacity() );
 481         }
 482
 483         /// Allocates an object from pool
 484         /**
 485             The pool supports allocation only single object (\p n = 1).
 486             If \p n > 1 the behaviour is undefined.
 487
 488             If the queue is not empty, the popped value is returned.
 489             Otherwise, a \p std::bad_alloc exception is raised.
 490         */
 491         value_type * allocate( size_t n )
 492         {
 493             assert( n == 1 );
 494             CDS_UNUSED( n );
 495
 496             value_type * p = m_Queue.pop();
 497
 498             if ( !p ) {
 499                 back_off bkoff;
 500                 while ( m_Queue.size() ) {
 501                     p = m_Queue.pop();
 502                     if ( p )
 503                         goto ok;
 504                     bkoff();
 505                 }
 506
 507                 // The pool is empty
 508                 throw std::bad_alloc();
 509             }
 510
 511         ok:
 512             assert( from_pool(p) );
 513             return p;
 514         }
 515
 516         /// Deallocates the object \p p
 517         /**
 518             The pool supports allocation only single object (\p n = 1).
 519             If \p n > 1 the behaviour is undefined.
 520
 521             \p p should be from preallocated pool.
 522         */
 523         void deallocate( value_type * p, size_t n )
 524         {
 525             assert( n == 1 );
 526             CDS_UNUSED( n );
 527
 528             if ( p ) {
 529                 assert( from_pool( p ));
 530                 back_off bkoff;
 531                 // The queue can notify it is full but that is false fullness state
 532                 // So, we push in loop
 533                 while ( !m_Queue.push(*p) )
 534                     bkoff();
 535             }
 536         }
 537     };
 538
 539
 540 }}  // namespace cds::memory
 541
 542
 543 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H