bdlma_concurrentpool.h

Go to the documentation of this file.

/// @file bdlma_concurrentpool.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bdlma_concurrentpool.h                                             -*-C++-*-
#ifndef INCLUDED_BDLMA_CONCURRENTPOOL
#define INCLUDED_BDLMA_CONCURRENTPOOL
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bdlma_concurrentpool bdlma_concurrentpool
/// @brief  Provide thread-safe allocation of memory blocks of uniform size.
/// @addtogroup bdl
/// @{
/// @addtogroup bdlma
/// @{
/// @addtogroup bdlma_concurrentpool
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bdlma_concurrentpool-purpose"> Purpose</a>
/// * <a href="#bdlma_concurrentpool-classes"> Classes </a>
/// * <a href="#bdlma_concurrentpool-description"> Description </a>
///   * <a href="#bdlma_concurrentpool-configuration-at-construction"> Configuration at Construction </a>
///   * <a href="#bdlma_concurrentpool-overloaded-global-operator-new"> Overloaded Global Operator new </a>
///   * <a href="#bdlma_concurrentpool-usage"> Usage </a>
///     * <a href="#bdlma_concurrentpool-example-1-basic-usage"> Example 1: Basic Usage </a>
///
/// # Purpose {#bdlma_concurrentpool-purpose}
/// Provide thread-safe allocation of memory blocks of uniform size.
///
/// # Classes {#bdlma_concurrentpool-classes}
///
/// -   bdlma::ConcurrentPool: thread-safe memory manager that allocates blocks
///
/// @see  bdlma_pool
///
/// # Description {#bdlma_concurrentpool-description}
/// This component implements a memory pool,
/// `bdlma::ConcurrentPool`, that allocates and manages memory blocks of some
/// uniform size specified at construction.  A `bdlma::ConcurrentPool` object
/// maintains an internal linked list of free memory blocks, and dispenses one
/// block for each `allocate` method invocation.  When a memory block is
/// deallocated, it is returned to the free list for potential reuse.
///
/// Whenever the linked list of free memory blocks is depleted, the
/// `bdlma::ConcurrentPool` replenishes the list by first allocating a large,
/// contiguous "chunk" of memory, then splitting the chunk into multiple memory
/// blocks.  A chunk and its constituent memory blocks can be depicted visually:
/// @code
///    +-----+--- memory blocks of uniform size
///    |     |
///  ----- ----- ------------
/// |     |     |     ...    |
///  =====^=====^============
///
///  \___________ __________/
///              V
///          a "chunk"
/// @endcode
/// Note that the size of the allocated chunk is determined by both the growth
/// strategy and maximum blocks per chunk, either of which can be optionally
/// specified at construction (see the "Configuration at Construction" section).
///
/// ## Configuration at Construction {#bdlma_concurrentpool-configuration-at-construction}
///
///
/// When creating a `bdlma::ConcurrentPool`, clients must specify the specific
/// block size managed and dispensed by the pool.  Furthermore, clients can
/// optionally configure:
///
/// 1. GROWTH STRATEGY -- geometrically growing chunk size starting from 1 (in
///    terms of the number of memory blocks per chunk), or fixed chunk size.  If
///    the growth strategy is not specified, geometric growth is used.
/// 2. MAX BLOCKS PER CHUNK -- the maximum number of memory blocks within a
///    chunk.  If the maximum blocks per chunk is not specified, an
///    implementation-defined default value is used.
/// 3. BASIC ALLOCATOR -- the allocator used to supply memory to replenish the
///    internal pool.  If not specified, the currently installed default
///    allocator (see @ref bslma_default ) is used.
///
/// For example, if geometric growth is used and the maximum blocks per chunk is
/// specified as 30, the chunk size grows geometrically, starting from 1, until
/// the specified maximum blocks per chunk, as follows:
/// @code
/// 1, 2, 4, 8, 16, 30, 30, 30 ...
/// @endcode
/// If constant growth is used, the chunk size is always the specified maximum
/// blocks per chunk (or an implementation-defined value if the maximum blocks
/// per chunk is not specified), for example:
/// @code
/// 30, 30, 30 ...
/// @endcode
/// A default-constructed pool has an initial chunk size of 1 (i.e., the number
/// of memory blocks of a given size allocated at once to replenish a pool's
/// memory), and the pool's chunk size grows geometrically until it reaches an
/// implementation-defined maximum, at which it is capped.  Finally, unless
/// otherwise specified, all memory comes from the allocator that was the
/// currently installed default allocator at the time the
/// `bdlma::ConcurrentPool` was created.
///
/// ## Overloaded Global Operator new {#bdlma_concurrentpool-overloaded-global-operator-new}
///
///
/// This component overloads the global `operator new` to allow convenient
/// syntax for the construction of objects using a `bdlma::ConcurrentPool`.  The
/// `new` operator supplied in this component takes a `bdlma::ConcurrentPool`
/// argument indicating the source of the memory.  Consider the following use of
/// standard placement `new` syntax (supplied by `bsl_new.h`) along with a
/// `bdlma::ConcurrentPool` to allocate an object of type `T`.  Note that the
/// size of `T` must be the same or smaller than the `blockSize` with which the
/// pool is constructed:
/// @code
/// void f(bdlma::ConcurrentPool *pool)
/// {
///     assert(pool->blockSize() >= sizeof(T));
///
///     T *t = new (pool->allocate()) T(...);
///
///     // ...
/// }
/// @endcode
/// This usage style is not exception-safe.  If the constructor of `T` throws an
/// exception, `pool->deallocate` is never called.
///
/// Supplying an overloaded global `operator new`:
/// @code
/// ::operator new(bsl::size_t size, bdlma::ConcurrentPool& pool);
/// @endcode
/// allows for the following cleaner usage, which does not require the size
/// calculation and guarantees that `pool->deallocate` *is* called in case of an
/// exception:
/// @code
/// void f(bdlma::ConcurrentPool *pool)
/// {
///     assert(pool->blockSize() >= sizeof(T));
///
///     T *t = new (*pool) T(...);
///
///     // ...
/// @endcode
/// Also note that the analogous version of operator `delete` should *not* be
/// called directly.  Instead, this component provides a static template member
/// function `deleteObject`, parameterized on `TYPE`:
/// @code
///     pool->deleteObject(t);
/// }
/// @endcode
/// The above `deleteObject` call is equivalent to performing the following:
/// @code
/// t->~TYPE();
/// pool->deallocate(t);
/// @endcode
/// An overloaded operator `delete` is supplied solely to allow the compiler to
/// arrange for it to be called in case of an exception.
///
/// ## Usage {#bdlma_concurrentpool-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Basic Usage {#bdlma_concurrentpool-example-1-basic-usage}
///
///
/// A `bdlma::ConcurrentPool` can be used by node-based containers (such as
/// lists, trees, and hash tables that hold multiple elements of uniform size)
/// for efficient memory allocation of new elements.  The following container
/// class, `my_PooledArray`, stores templatized values "out-of-place" as nodes
/// in a `vector` of pointers.  Since the size of each node is fixed and known
/// *a priori*, the class uses a `bdlma::ConcurrentPool` to allocate memory for
/// the nodes to improve memory allocation efficiency:
/// @code
/// // my_poolarray.h
///
/// template <class T>
/// class my_PooledArray {
///     // This class implements a container that stores 'double' values
///     // out-of-place.
///
///     // DATA
///     bsl::vector<T *>      d_array_p;  // array of pooled elements
///     bdlma::ConcurrentPool d_pool;     // memory manager for array elements
///
///   private:
///     // Not implemented:
///     my_PooledArray(const my_PooledArray&);
///
///   public:
///     // CREATORS
///     explicit my_PooledArray(bslma::Allocator *basicAllocator = 0);
///         // Create a pooled array that stores the parameterized values
///         // "out-of-place".  Optionally specify a 'basicAllocator' used to
///         // supply memory.  If 'basicAllocator' is 0, the currently
///         // installed default allocator is used.
///
///     ~my_PooledArray();
///         // Destroy this array and all elements held by it.
///
///     // MANIPULATORS
///     void append(const T &value);
///         // Append the specified 'value' to this array.
///
///     void removeAll();
///         // Remove all elements from this array.
///
///     // ACCESSORS
///     int length() const;
///         // Return the number of elements in this array.
///
///     const T& operator[](int index) const;
///         // Return a reference to the non-modifiable value at the specified
///         // 'index' in this array.  The behavior is undefined unless
///         // '0 <= index < length()'.
/// };
/// @endcode
/// In the `removeAll` method, all elements are deallocated by invoking the
/// pool's `release` method.  This technique implies significant performance
/// gain when the array contains many elements:
/// @code
/// // MANIPULATORS
/// template <class T>
/// inline
/// void my_PooledArray<T>::removeAll()
/// {
///     d_array_p.clear();
///     d_pool.release();
/// }
///
/// // ACCESSORS
/// template <class T>
/// inline
/// int my_PooledArray<T>::length() const
/// {
///     return static_cast<int>(d_array_p.size());
/// }
///
/// template <class T>
/// inline
/// const T& my_PooledArray<T>::operator[](int index) const
/// {
///     assert(0 <= index);
///     assert(index < length());
///
///     return *d_array_p[index];
/// }
/// @endcode
/// Note that the growth strategy and maximum chunk size of the pool is left as
/// the default value:
/// @code
/// // my_poolarray.cpp
///
/// // CREATORS
/// template <class T>
/// my_PooledArray<T>::my_PooledArray(bslma::Allocator *basicAllocator)
/// : d_array_p(basicAllocator)
/// , d_pool(sizeof(T), basicAllocator)
/// {
/// }
/// @endcode
/// Since all memory is managed by `d_pool`, we do not have to explicitly invoke
/// `deleteObject` to reclaim outstanding memory.  The destructor of the pool
/// will automatically deallocate all array elements:
/// @code
/// template <class T>
/// my_PooledArray<T>::~my_PooledArray()
/// {
///     // Elements are automatically deallocated when 'd_pool' is destroyed.
/// }
/// @endcode
/// Note that the overloaded "placement" `new` is used to allocate new nodes:
/// @code
/// template <class T>
/// void my_PooledArray<T>::append(const T& value)
/// {
///     T *tmp = new (d_pool) T(value);
///     d_array_p.push_back(tmp);
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bdl
 * @{
 */
/** @addtogroup bdlma
 * @{
 */
/** @addtogroup bdlma_concurrentpool
 * @{
 */
 
#include <bdlscm_version.h>
 
#include <bslmt_mutex.h>
 
#include <bdlma_infrequentdeleteblocklist.h>
 
#include <bslma_allocator.h>
#include <bslma_deleterhelper.h>
 
#include <bsls_alignmentutil.h>
#include <bsls_assert.h>
#include <bsls_atomic.h>
#include <bsls_atomicoperations.h>
#include <bsls_blockgrowth.h>
#include <bsls_platform.h>
#include <bsls_types.h>
 
#include <bsl_cstddef.h>
 
 
namespace bdlma {
 
                           // ====================
                           // class ConcurrentPool
                           // ====================
 
/// This class implements a memory pool that allocates and manages memory
/// blocks of some uniform size specified at construction.  This memory pool
/// maintains an internal linked list of free memory blocks, and dispenses
/// one block for each `allocate` method invocation.  When a memory block is
/// deallocated, it is returned to the free list for potential reuse.
///
/// This class guarantees thread safety while allocating or releasing
/// memory.
///
/// See @ref bdlma_concurrentpool 
class ConcurrentPool {
 
    // PRIVATE TYPES
 
    /// This `struct` implements a link data structure that stores the
    /// address of the next link, and is used to implement the internal linked list of free memory blocks.  
    /// 
    /// \note Note that   this type is
    /// replicated in `bdlma_concurrentpool.cpp` to provide access to a
    /// compatible type from static methods defined in `bdema_pool.cpp`.
    ///
    /// See @ref bdlma_concurrentpool 
    struct Link {
 
        union {
            bsls::AtomicOperations::AtomicTypes::Int d_refCount;
            bsls::AlignmentUtil::MaxAlignedType      d_dummy;
        };
        Link  *volatile d_next_p;   // pointer to next link
    };
 
    // DATA
    bsls::Types::size_type d_blockSize;  // size of each allocated memory block
                                         // returned to client
 
    bsls::Types::size_type d_internalBlockSize;
                                         // actual size of each block
                                         // maintained on free list (contains
                                         // overhead for 'Link')
 
    int                    d_chunkSize;  // current chunk size (in
                                         // blocks-per-chunk)
 
    int                    d_maxBlocksPerChunk;
                                         // maximum chunk size (in
                                         // blocks-per-chunk)
 
    bsls::BlockGrowth::Strategy d_growthStrategy;
                                         // growth strategy of the chunk size
 
    bsls::AtomicPointer<Link> d_freeList;
                                         // linked list of free memory blocks
 
    bdlma::InfrequentDeleteBlockList d_blockList;
                                         // memory manager for allocated memory
 
    bslmt::Mutex      d_mutex;           // protects access to the block list
 
    // PRIVATE MANIPULATORS
 
    /// Dynamically allocate a new chunk using the pool's underlying growth
    /// strategy, and use the chunk to replenish the free memory list of this pool.  
    /// 
    /// \pre The behavior is undefined   unless the calling thread has
    /// a lock on `d_mutex`.
    void replenish();
 
  private:
    // NOT IMPLEMENTED
    ConcurrentPool(const ConcurrentPool&);
    ConcurrentPool& operator=(const ConcurrentPool&);
 
  public:
    // CREATORS
 
    /// Create a memory pool that returns blocks of contiguous memory of the
    /// specified `blockSize` (in bytes) for each `allocate` method
    /// invocation.  Optionally specify a `growthStrategy` used to control
    /// the growth of internal memory chunks (from which memory blocks are
    /// dispensed).  If `growthStrategy` is not specified, geometric growth
    /// is used.  Optionally specify `maxBlocksPerChunk` as the maximum
    /// chunk size.  If geometric growth is used, the chunk size grows
    /// starting at `blockSize`, doubling in size until the size is exactly
    /// `blockSize * maxBlocksPerChunk`.  If constant growth is used, the
    /// chunk size is always `maxBlocksPerChunk`.  If `maxBlocksPerChunk` is
    /// not specified, an implementation-defined value is used.  Optionally
    /// specify a `basicAllocator` used to supply memory.  If
    /// `basicAllocator` is 0, the currently installed default allocator is used.  
    /// 
    /// \pre The behavior is undefined   unless `1 <= blockSize` and
    /// `1 <= maxBlocksPerChunk`.
    explicit ConcurrentPool(bsls::Types::size_type  blockSize,
                            bslma::Allocator       *basicAllocator = 0);
    ConcurrentPool(bsls::Types::size_type       blockSize,
                   bsls::BlockGrowth::Strategy  growthStrategy,
                   bslma::Allocator            *basicAllocator = 0);
    ConcurrentPool(bsls::Types::size_type       blockSize,
                   bsls::BlockGrowth::Strategy  growthStrategy,
                   int                          maxBlocksPerChunk,
                   bslma::Allocator            *basicAllocator = 0);
 
    /// Destroy this pool, releasing all associated memory back to the
    /// underlying allocator.
    ~ConcurrentPool();
 
    // MANIPULATORS
 
    /// Return the address of a contiguous block of memory having the fixed
    /// block size specified at construction.
    void *allocate();
 
    /// Relinquish the memory block at the specified `address` back to this pool object for reuse.  
    /// 
    /// \pre The behavior is undefined   unless `address`
    /// is non-zero, was allocated by this pool, and has not already been
    /// deallocated.
    void deallocate(void *address);
 
    /// Destroy the specified `object` based on its dynamic type and then
    /// use this pool to deallocate its memory footprint.  This method has no effect if `object` is 0.  
    /// 
    /// \pre The behavior is undefined   unless
    /// `object`, when cast appropriately to `void *`, was allocated using
    /// this pool and has not already been deallocated.  
    /// 
    /// \note Note that   `dynamic_cast<void *>(object)` is applied if `TYPE` is polymorphic,
    /// and `static_cast<void *>(object)` is applied otherwise.
    template <class TYPE>
    void deleteObject(const TYPE *object);
 
    /// Destroy the specified `object` and then use this pool to deallocate
    /// its memory footprint.  This method has no effect if `object` is 0. 
    /// 
    /// \pre The behavior is undefined   unless `object` is **not** a secondary base
    /// class pointer (i.e., the address is (numerically) the same as when
    /// it was originally dispensed by this pool), was allocated using this
    /// pool, and has not already been deallocated.
    template <class TYPE>
    void deleteObjectRaw(const TYPE *object);
 
    /// Relinquish all memory currently allocated via this pool object.
    void release();
 
    /// Reserve memory from this pool to satisfy memory requests for at
    /// least the specified `numBlocks` before the pool replenishes.  
    /// 
    /// \pre The behavior is undefined   unless `0 <= numBlocks`.
    void reserveCapacity(int numBlocks);
 
    // ACCESSORS
 
    /// Return the size (in bytes) of the memory blocks allocated from this pool object.  
    /// 
    /// \note Note that   all blocks dispensed by this pool have the
    /// same size.
    bsls::Types::size_type blockSize() const;
 
                                  // Aspects
 
    /// Return the allocator used by this object to allocate memory.  
    /// 
    /// \note Note that   this allocator can not be used to deallocate memory
    /// allocated through this pool.
    bslma::Allocator *allocator() const;
};
 
}  // close package namespace
 
 
// Note that the 'new' and 'delete' operators are declared outside the
// 'BloombergLP' namespace so that they do not hide the standard placement
// 'new' and 'delete' operators (i.e.,
// 'void *operator new(bsl::size_t, void *)' and
// 'void operator delete(void *)').
//
// Also note that only the scalar versions of operators 'new' and 'delete' are
// provided, because overloading 'new' (and 'delete') with their array versions
// would cause dangerous ambiguity.  Consider what would have happened had we
// overloaded the array version of 'operator new':
//..
//  void *operator new[](bsl::size_t size, BloombergLP::bdlma::Pool& pool);
//..
// A user of 'bdlma::Pool' may expect to be able to use array 'operator new' as
// follows:
//..
//   new (*pool) my_Type[...];
//..
// The problem is that this expression returns an array that cannot be safely
// deallocated.  On the one hand, there is no syntax in C++ to invoke an
// overloaded 'operator delete'; on the other hand, the pointer returned by
// 'operator new' cannot be passed to the 'deallocate' method directly because
// the pointer is different from the one returned by the 'allocate' method.
// The compiler offsets the value of this pointer by a header, which is used to
// maintain the number of objects in the array (so that 'operator delete' can
// destroy the right number of objects).
 
// FREE OPERATORS
 
/// Return a block of memory of the specified `size` (in bytes) allocated from the specified `pool`.  
/// 
/// \pre The behavior is undefined   unless `size` is
/// the same or smaller than the `blockSize` with which `pool` was constructed.  
/// 
/// \note Note that   an object may allocate additional memory
void *operator new(bsl::size_t size, BloombergLP::bdlma::ConcurrentPool& pool);
 
    // internally, requiring the allocator to be passed in as a constructor
    // argument:
    //..
    //  my_Type *newMyType(bdlma::ConcurrentPool *pool,
    //                     bslma::Allocator      *basicAllocator)
    //  {
    //      return new (*pool) my_Type(..., basicAllocator);
    //  }
    //..
    // Also note that the analogous version of 'operator delete' should not be
    // called directly.  Instead, this component provides a static template
    // member function, 'deleteObject', parameterized by 'TYPE':
    //..
    //  void deleteMyType(my_Type *t, bdlma::ConcurrentPool *pool)
    //  {
    //      pool->deleteObject(t);
    //  }
    //..
    // 'deleteObject' performs the following:
    //..
    //  t->~my_Type();
    //  pool->deallocate(t);
    //..
 
/// Use the specified `pool` to deallocate the memory at the specified `address`.  
/// 
/// \pre The behavior is undefined   unless `address` was allocated
/// using `pool` and has not already been deallocated.  This operator is
/// supplied solely to allow the compiler to arrange for it to be called in
/// case of an exception.  Client code should not call it; use
/// `bdlma::ConcurrentPool::deleteObject()` instead.
inline
void operator delete(void *address, BloombergLP::bdlma::ConcurrentPool& pool);
 
// ============================================================================
//                             INLINE DEFINITIONS
// ============================================================================
 
 
namespace bdlma {
 
                           // --------------------
                           // class ConcurrentPool
                           // --------------------
 
// MANIPULATORS
template<class TYPE>
inline
void ConcurrentPool::deleteObject(const TYPE *object)
{
    bslma::DeleterHelper::deleteObject(object, this);
}
 
template<class TYPE>
inline
void ConcurrentPool::deleteObjectRaw(const TYPE *object)
{
    bslma::DeleterHelper::deleteObjectRaw(object, this);
}
 
inline
void ConcurrentPool::release()
{
    d_mutex.lock();
    d_freeList = (Link*)0;
    d_blockList.release();
    d_mutex.unlock();
}
 
// ACCESSORS
inline
bsls::Types::size_type ConcurrentPool::blockSize() const
{
    return d_blockSize;
}
 
// Aspects
 
inline
bslma::Allocator *ConcurrentPool::allocator() const
{
    return d_blockList.allocator();
}
 
}  // close package namespace
 
 
// FREE OPERATORS
inline
void *operator new(bsl::size_t size, BloombergLP::bdlma::ConcurrentPool& pool)
{
#if defined(BSLS_ASSERT_SAFE_IS_USED)
    // gcc-4.8.1 introduced a new warning for unused typedefs, so this typedef
    // should only be present in SAFE mode builds (where it is used).
 
    typedef BloombergLP::bsls::AlignmentUtil Util;
 
    BSLS_ASSERT_SAFE(size <= pool.blockSize()
                  && Util::calculateAlignmentFromSize(size)
                       <= Util::calculateAlignmentFromSize(pool.blockSize()));
#endif
 
    static_cast<void>(size);  // suppress "unused parameter" warnings
    return pool.allocate();
}
 
inline
void operator delete(void *address, BloombergLP::bdlma::ConcurrentPool& pool)
{
    pool.deallocate(address);
}
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2016 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */