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