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