BDE Allocator Model

Mike Verschell edited this page Aug 19, 2015 · 12 revisions

This document provides information about the BDE allocator model, the rationale for its use, the available concrete allocators, and relevant code examples.

History of Allocators

STL Allocators were introduced to provide containers an abstraction for the different pointer types on the Intel architecture (such as near and far pointers). That use was rendered obsolete after the C++ standard (section 20.1.5 of the 1998 standard) specified the requirements on an allocator type. The standard specification that all standard containers be parameterized on an allocator type made them independent of the underlying memory model.

Allocator objects provide users greater control over the memory usage of individual objects. By changing the allocation strategy users can control the memory source (for example: stack, heap, shared memory, etc.) e.g., memory for short-lived temporary objects can be supplied from fast, fixed size memory allocations on the stack. Additionally, allocator objects can be used to avoid fragmentation in long-running processes and to improve locality of reference among objects by colocating them.

Although standard allocators provide users great control on how containers can allocate memory, the C++03 allocator specification introduced two distinct problems:

  1. The allocator used to supply memory to a container and its underlying objects is not the same. This issue was resolved with the introduction of the scoped_allocator_adaptor template in the C++11 standard (section 20.12).

  2. Two containers instantiated with different allocator types refer to distinct types making interoperability between them difficult. A proposal for the use of Polymorphic allocators that would solve this issue is provided here.

bslma::Allocator protocol

BDE provides allocators and container implementations that solve the issues mentioned above. BDE provides an allocator protocol and concrete allocator implementations that can be passed as constructor arguments (not as template parameters) to all objects that allocate memory. The type of an object is unaffected by the passed-in allocator and the user has full control over the scope of an allocator instance. As the model specifies a protocol, it is easier to create concrete implementations and use them. The allocator model requires all elements (data members) of a container (object) to use the same allocator as the container (object). Also, the allocator is not transferred on copy construction.

bslma::Allocator is a protocol for memory allocation mechanisms. The interface of this class includes two virtual methods allocate and deallocate whose signatures are:

    virtual void *allocate(size_type size) = 0;
        // Return a newly allocated block of memory of (at least) the specified
        // positive 'size' (in bytes).  If 'size' is 0, a null pointer is
        // returned with no other effect.  If this allocator cannot return the
        // requested number of bytes, then it will throw a 'std::bad_alloc'
        // exception in an exception-enabled build, or else will abort the
        // program in a non-exception build.  The behavior is undefined unless
        // '0 <= size'.  Note that the alignment of the address returned
        // conforms to the platform requirement for any object of the specified
        // 'size'.

    virtual void deallocate(void *address) = 0;
        // Return the memory block at the specified 'address' back to this
        // allocator.  If 'address' is 0, this function has no effect.  The
        // behavior is undefined unless 'address' was allocated using this
        // allocator object and has not already been deallocated.

The bslma_allocator component also provides overloaded global operator new that allows convenient construction of objects using a bslma::Allocator object. Although an overloaded global operator delete is supplied in bslma_allocator, it is solely for the compiler to invoke in the event an exception is thrown during a failed construction, and users should call the deleteObject method instead to destroy an object and deallocate its memory. A code snippet showing the syntax of these methods is provided below:

    template <typename TYPE>
    void someFunction(bslma::Allocator *basicAllocator)
    {
        TYPE *object = new (*basicAllocator) TYPE(...);

        // Process 'object'

        basicAllocator->deleteObject(object);
    }

A larger example of how to use this syntax is here.

Each BDE class that allocates memory requires an allocator at construction. This allocator argument provides clients fine-grained control over the memory usage of individual objects by substituting the default allocator with an object-specific alternative. Clients can write their own, customized allocator classes, and use those customized allocators with the BDE classes.

Allocator Instances

The BDE allocator model provides two static (global) allocator instances of which a user should be mindful:

  • Default allocator: This is the allocator that is used by default by all BDE objects. Users can access the default allocator by calling the defaultAllocator method in bslma::Default.

  • Global allocator: This is the allocator that should be used for constructing objects with static linkage. Users can access the global allocator by calling the globalAllocator method in bslma::Default.

The ability to set the default or the global allocator is intended primarily for testing correct allocator propagation in composite types. Although code other than test drivers can set the default allocator by calling the setDefaultAllocator method in bslma::Default, doing so is strongly discouraged as changing the default allocator can lead to unintended effects in multi-threaded applications. If an application must set the default alloactor it must do so in the very beginning of main and library code should never set these allocators. Once set, these allocators should remain in effect throughout the lifetime of an application. The bslma::NewDeleteAllocator is the used for the default and global allocators unless they are explicitly modified.

Refer to the bslma_default component for further information on the default and global allocators.

BSL-Provided bslma::Allocator Derived Classes

Three derived allocators are provided in the bslma package:

  • MallocFreeAllocator: This class uses the global functions std::malloc and std::free for allocations and deallocations. Refer to the bslma_mallocfreeallocator component for more information.

  • NewDeleteAllocator: This class uses global operators new and delete for allocations and deallocations, and is used for both the default and global allocators by default. Refer to the bslma_newdeleteallocator component for more information.

  • TestAllocator: This class provides an instrumented memory allocator that uses global functions std::malloc and std::free for allocations and deallocations, respectively. Instances of this class allow users to track memory usage and test the allocation behavior of objects. Refer to the bslma_testallocator component for more information.

'bdlma::ManagedAllocator' protocol

The bdlma::ManagedAllocator, introduces a new allocator protocol, that derives from and extends the bslma::Allocator protocol by adding a method to release all allocated memory at once. Derived implementations of this protocol can be used for allocating temporary memory and can be made efficient by skipping the deallocation of individual memory blocks.

The signature of the 'release' method is:

    virtual void release() = 0;
        // Release all memory currently allocated through this allocator.

Refer to the bdlma_managedallocator component for more information.

BDL-Provided bdlma::ManagedAllocator Derived Classes

The bdlma package provides three derived bdlma::ManagedAllocator allocators:

  • BufferedSequentialAllocator: This class provides a fast allocator that dispenses heterogeneous blocks of memory (of varying, user-specified sizes) from an external buffer whose address and size (in bytes) are supplied at construction. Refer to the bdlma_bufferedsequentialallocator component for more information.

  • MultipoolAllocator: This class maintains a configurable number of 'bdlma::Pool' objects, each dispensing maximally-aligned memory blocks of a unique size. Refer to the bdlma_multipoolallocator component for more information.

  • SequentialAllocator: This class provides a fast allocator that dispenses heterogeneous blocks of memory (of varying, user-specified sizes) from a sequence of dynamically-allocated buffers. Refer to the bdlma_sequentialallocator component for more information.

Using BDE Allocators

Creating a Type that Uses bslma::Allocator

If objects of a class allocate memory (or contain data members that do) then having all constructors of that class accept the address of a bslma::Allocator object as an argument allows its clients to control how those objects allocate memory. An example of this is provided by showing the creators of a Customer class that stores the first and last names of a customer as bsl::string objects and the various account numbers of that customer using a bsl::vector:

    Customer(bslma::Allocator *basicAllocator = 0);
    Customer(const bslstl::StringRef&  firstName,
             const bslstl::StringRef&  lastName,
             const bsl::vector<int>&   accounts,
             int                       id,
             bslma::Allocator         *basicAllocator = 0);
    Customer(const Customer& original, bslma::Allocator *basicAllocator = 0);

The constructor implementations of Customer would simply forward the basicAllocator argument to its data members:

    Customer::Customer(bslma::Allocator *basicAllocator)
    : d_firstName(basicAllocator)
    , d_lastName(basicAllocator)
    , d_accounts(basicAllocator)
    , d_id(0)
    {
    }
    
    Customer::Customer(const bslstl::StringRef&  firstName,
                       const bslstl::StringRef&  lastName,
                       const bsl::vector<int>&   accounts,
                       int                       id,
                       bslma::Allocator         *basicAllocator)
    : d_firstName(firstName.begin(), firstName.end(), basicAllocator)
    , d_lastName(lastName.begin(), lastName.end(), basicAllocator)
    , d_accounts(accounts, basicAllocator)
    , d_id(id)
    {
        BSLS_ASSERT_SAFE(!firstName.isEmpty());
        BSLS_ASSERT_SAFE(!lastName.isEmpty());
    }
    
    Customer::Customer(const Customer&   original,
                       bslma::Allocator *basicAllocator)
    : d_firstName(original.d_firstName, basicAllocator)
    , d_lastName(original.d_lastName, basicAllocator)
    , d_accounts(original.d_accounts, basicAllocator)
    , d_id(original.d_id)
    {
    }

All BSL containers, including bsl::string and bsl::vector, accept a bslma::Allocator constructor argument.

Since the Customer class contains members that allocate memory, it can associate the UsesBslmaAllocator trait defined in the bslma package to programmatically inform templated code that it uses an allocator as follows:

    // TRAITS
    namespace BloombergLP {
    namespace bslma {
    
    template <> struct UsesBslmaAllocator<Customer> : bsl::true_type {};
    
    }
    }

The complete Customer class interface and implementation is provided here.

Implementing Templates That May Be Supplied Allocating Types

When writing templatized code that may be parameterized on types that allocate memory it is often necessary to decide whether to pass through the user-supplied allocator to individual objects. Such code (and containers) can use the UsesBslmaAllocator trait defined in the bslma package to decide whether to pass the allocator to an object's constructor. An example of using this trait is provided below:

    using namespace BloombergLP;
    
    template <typename TYPE>
    void appendDefaultElement(bsl::vector<TYPE> *array, bslma::Allocator *basicAllocator, bsl::false_type)
    {
        TYPE newElement;
        array->push_back(newElement);
    }

    template <typename TYPE>
    void appendDefaultElement(bsl::vector<TYPE> *array, bslma::Allocator *basicAllocator, bsl::true_type)
    {
        TYPE newElement(basicAllocator);
        array->push_back(newElement);
    }

    template <typename TYPE>
    void appendDefaultElement(bsl::vector<TYPE> *array, bslma::Allocator *basicAllocator)
    {
        appendDefaultElement(array, basicAllocator, bslma::UsesBslmaAllocator<TYPE>());
    }

For further details refer to the bslma_usesbslmaallocator component. A complete example that uses the UsesBslmaAllocator trait is provided here.

Implementing a Customized Allocator

Since bslma::Allocator is a protocol, users can create their own concrete implementations for object-specific situations. A complete example of a concrete implementation that allocates memory from a user-supplied buffer and reverts to an allocator specified at construction if that buffer is exhausted is provided here.

Using Allocating Types with Containers

Often objects that allocate memory are stored within standard containers. To allow users to control the allocation behavior of the container and its sub-elements, BSL containers pass the user-specified allocator through to individual elements if those elements allocate memory.

Allocating memory from a user-supplied buffer

bdlma::BufferedSequentialAllocator allows users to supply a buffer used for allocating memory.

Functions often create short-lived containers that allocate memory from the heap. This is expensive and unnecessary since the memory is short-lived. The simple code snippet below shows how to create a bdlma::BufferedSequentialAllocator to that uses memory from the stack:

    const int BUFFER_SIZE = 1024;
    char      buffer[BUFFER_SIZE];

    bdlma::BufferedSequentialAllocator allocator(buffer, BUFFER_SIZE);
    bsl::vector<int>                   dataVector(&allocator);

    dataVector.resize(50);

Testing Types That Allocate Memory

The bslma::TestAllocator provides an instrumented allocator that can be used to track various aspects of the memory allocated from it. The bslma_testallocator component also provides macros that can be used to ensure the exception-safety of classes.

Other Useful Components

The bslma package provides a range of components that can act as guards and proctors to manage previously allocated memory and objects. Refer to the bslma package for further information on these components.

Miscellaneous

Alignment

Alignment of an address in memory refers to the relative position of that address with respect to specific (hardware-imposed) boundaries within the memory space. An address can be said to be on a one-byte boundary, a two-byte boundary, a four-byte boundary, or an eight-byte boundary depending on whatever 1, 2, 4, or 8 is the largest integer that evenly divides the numerical value of that address. Refer to the bsls_alignment component for further details on the memory alignment strategies supported.

Normally, programmers needn't worry about alignment for dynamically allocated memory. The runtime system's operator new is required by the C++ standard to return memory blocks beginning at maximally-aligned addresses. All the BSL allocators similarly return memory that is maximally-aligned, and allocators that return addresses that are "naturally aligned" (and therefore would be more efficient) are planned for subsequent releases.

Note that "alignment", as used by BDE components, does not deal with page boundaries or other larger memory structures, although those considerations may be important elsewhere.

Swap

When implementing the swap method, classes whose objects store allocators should not exchange their respective allocators. An invocation of the swap method is completed in constant time only if the allocators of the objects being swapped compare equal.

Returning objects that allocate memory by-value

If an object that allocates memory is returned by-value then care must be taken to ensure that the allocator passed to that value outlives that object itself. With the return value optimization, returning by-value could result in objects referring to destroyed allocator instances. When returning objects that allocate by-value it is generally a good idea to use the default allocator.

Thread-Safety

All bslma allocators (except the [bslma::TestAllocator] (http://github.com/bloomberg/bde/blob/master/groups/bsl/bslma/bslma_testallocator.h#L299)) are fully thread-safe.

Questions, Comments, and Feedback

If you have questions, comments, suggestions for improvement or any other inquiries regarding BSL or this wiki, feel free to open an issue in the issue tracker.


Creative Commons License  BSL Wiki by Bloomberg Finance L.P. is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.