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