cds/memory/vyukov_queue_pool.h

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