Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* 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
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.