ds-writing-a-pool-allocator.cpp

/**
 * Pool-allocator.
 *
 * Details: http://dmitrysoshnikov.com/compilers/writing-a-pool-allocator/
 *
 * Allocates a larger block using `malloc`.
 *
 * Splits the large block into smaller chunks
 * of equal size.
 *
 * Uses bump-allocated per chunk.
 *
 * by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
 * MIT Style License, 2019
 */

#include <iostream>

using std::cout;
using std::endl;

/**
 * A chunk within a larger block.
 */
struct Chunk {
  /**
   * When a chunk is free, the `next` contains the
   * address of the next chunk in a list.
   *
   * When it's allocated, this space is used by
   * the user.
   */
  Chunk *next;
};

/**
 * The allocator class.
 *
 * Features:
 *
 *   - Parametrized by number of chunks per block
 *   - Keeps track of the allocation pointer
 *   - Bump-allocates chunks
 *   - Requests a new larger block when needed
 *
 */
class PoolAllocator {
 public:
  PoolAllocator(size_t chunksPerBlock) : mChunksPerBlock(chunksPerBlock) {}

  void *allocate(size_t size);
  void deallocate(void *ptr, size_t size);

 private:
  /**
   * Number of chunks per larger block.
   */
  size_t mChunksPerBlock;

  /**
   * Allocation pointer.
   */
  Chunk *mAlloc = nullptr;

  /**
   * Allocates a larger block (pool) for chunks.
   */
  Chunk *allocateBlock(size_t chunkSize);
};

// -----------------------------------------------------------

/**
 * Allocates a new block from OS.
 *
 * Returns a Chunk pointer set to the beginning of the block.
 */
Chunk *PoolAllocator::allocateBlock(size_t chunkSize) {
  cout << "\nAllocating block (" << mChunksPerBlock << " chunks):\n\n";

  size_t blockSize = mChunksPerBlock * chunkSize;

  // The first chunk of the new block.
  Chunk *blockBegin = reinterpret_cast<Chunk *>(malloc(blockSize));

  // Once the block is allocated, we need to chain all
  // the chunks in this block:

  Chunk *chunk = blockBegin;

  for (int i = 0; i < mChunksPerBlock - 1; ++i) {
    chunk->next =
        reinterpret_cast<Chunk *>(reinterpret_cast<char *>(chunk) + chunkSize);
    chunk = chunk->next;
  }

  chunk->next = nullptr;

  return blockBegin;
}

/**
 * Returns the first free chunk in the block.
 *
 * If there are no chunks left in the block,
 * allocates a new block.
 */
void *PoolAllocator::allocate(size_t size) {

  // No chunks left in the current block, or no any block
  // exists yet. Allocate a new one, passing the chunk size:

  if (mAlloc == nullptr) {
    mAlloc = allocateBlock(size);
  }

  // The return value is the current position of
  // the allocation pointer:

  Chunk *freeChunk = mAlloc;

  // Advance (bump) the allocation pointer to the next chunk.
  //
  // When no chunks left, the `mAlloc` will be set to `nullptr`, and
  // this will cause allocation of a new block on the next request:

  mAlloc = mAlloc->next;

  return freeChunk;
}

/**
 * Puts the chunk into the front of the chunks list.
 */
void PoolAllocator::deallocate(void *chunk, size_t size) {

  // The freed chunk's next pointer points to the
  // current allocation pointer:

  reinterpret_cast<Chunk *>(chunk)->next = mAlloc;

  // And the allocation pointer is moved backwards, and
  // is set to the returned (now free) chunk:

  mAlloc = reinterpret_cast<Chunk *>(chunk);
}

// -----------------------------------------------------------

/**
 * The `Object` structure uses custom allocator,
 * overloading `new`, and `delete` operators.
 */
struct Object {

  // Object data, 16 bytes:

  uint64_t data[2];

  // Declare out custom allocator for
  // the `Object` structure:

  static PoolAllocator allocator;

  static void *operator new(size_t size) {
    return allocator.allocate(size);
  }

  static void operator delete(void *ptr, size_t size) {
    return allocator.deallocate(ptr, size);
  }
};

// Instantiate our allocator, using 8 chunks per block:

PoolAllocator Object::allocator{8};

int main(int argc, char const *argv[]) {

  // Allocate 10 pointers to our `Object` instances:

  constexpr int arraySize = 10;

  Object *objects[arraySize];

  // Two `uint64_t`, 16 bytes.
  cout << "size(Object) = " << sizeof(Object) << endl << endl;

  // Allocate 10 objects. This causes allocating two larger,
  // blocks since we store only 8 chunks per block:

  cout << "About to allocate " << arraySize << " objects" << endl;

  for (int i = 0; i < arraySize; ++i) {
    objects[i] = new Object();
    cout << "new [" << i << "] = " << objects[i] << endl;
  }

  cout << endl;

  // Deallocate all the objects:

  for (int i = arraySize - 1; i >= 0; --i) {
    cout << "delete [" << i << "] = " << objects[i] << endl;
    delete objects[i];
  }

  cout << endl;

  // New object reuses previous block:

  objects[0] = new Object();
  cout << "new [0] = " << objects[0] << endl << endl;
}

/*

size(Object) = 16

Allocating block (8 chunks):

new [0] = 0x7ff85e4029e0
new [1] = 0x7ff85e4029f0
new [2] = 0x7ff85e402a00
new [3] = 0x7ff85e402a10
new [4] = 0x7ff85e402a20
new [5] = 0x7ff85e402a30
new [6] = 0x7ff85e402a40
new [7] = 0x7ff85e402a50

Allocating block (8 chunks):

new [8] = 0x7ff85e402a60
new [9] = 0x7ff85e402a70

delete [0] = 0x7ff85e4029e0
delete [1] = 0x7ff85e4029f0
delete [2] = 0x7ff85e402a00
delete [3] = 0x7ff85e402a10
delete [4] = 0x7ff85e402a20
delete [5] = 0x7ff85e402a30
delete [6] = 0x7ff85e402a40
delete [7] = 0x7ff85e402a50
delete [8] = 0x7ff85e402a60
delete [9] = 0x7ff85e402a70

new [0] = 0x7ff85e402a70

*/

Why is the size parameter of PoolAllocator::deallocate never used?

@larkwiot, yes, it's mainly to be consistent with the operator delete(void *ptr, size_t size) signature, which works with different sizes. However, since the pool allocator uses the same chunk size, this parameter is not used, and can be removed.

The basic, the simplest, the most feasible. There is no better pool allocator concept that justifies big efforts required, for developing that better concept. One question if I may.

Chunk* allocateBlock(size_t chunkSize);

I assume you want to check if chunkSize is bigger than sizeof Chunk ? Also you would want to check that chunks are always of the same size? One solution might be chunk size as template parameter, or as constructor argument.

@DBJDBJ, thanks, and yes, as you correctly mention -- making the chunk size as a parametrized constant (via template or a constructor arg) is a good alternative solution. In the current implementation though, the size is guaranteed be the same since the size of the Object structure is passed, which is known at compile time.

I assume you want to check if chunkSize is bigger than sizeof Chunk

Don't think this is needed though, since the Chunk structure itself, when a chunk is not allocated, is only one pointer size (8 or 4 bytes, depending on the machine). When a chunk is allocated, it takes the requested space.

@DmitrySoshnikov

I have made a repo where I am comparing yours and 3 other well-known memory allocation lib. In case you would like to take a peek please do let me know.

@DBJDBJ, absolutely, always glad to see different alternative solutions to a problem.

It is not an alternative it is a comparison ... my version of your allocator is basically the same

https://github.com/dbj-data/comparing_allocation_libs

Next "thing" to do is efficient array allocation using Shoshnikov allocator.

@DBJDBJ, nice work, thanks! I'll take a deeper look at this repo.

Finished fiddling with it, literally a minute ago. Thanks for the star.
Array allocation is currently naive and with an obvious bug inside. To tired right now so not in use currently.

@DmitrySoshnikov, hi, wouldn't there be a problem chaining those chunks if the chuck size is smaller than the pointer size?

  for (int i = 0; i < mChunksPerBlock - 1; ++i) {
    chunk->next = reinterpret_cast<Chunk *>(reinterpret_cast<char *>(chunk) + chunkSize);
    chunk = chunk->next;
  }

@JunLin820119 - thanks, that's a good point. And in this case you would need to keep an extra field, for data and still for chaining the blocks, as any allocator does.

@DmitrySoshnikov, got it, thanks for replying and everything. This PoolAllocator solves one of my big problem.
Btw, I added an extra member "std::vector<void> v_block_address"*, to record the starting address of each allocated blocks, so that I can free all the memories allocated during runtime.

void* PoolAllocator::allocate(size_t buffer_size)
...
if (mAlloc == nullptr)
{
    mAlloc = allocateBlock(buffer_size);   

    v_block_address.push_back(mAlloc);
}
...

@JunLin820119 , yes, that's a good optimization since you can directly remove the blocks.