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
*/
@larkwiot

This comment has been minimized.

Copy link

@larkwiot larkwiot commented Mar 11, 2020

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

@DmitrySoshnikov

This comment has been minimized.

Copy link
Owner Author

@DmitrySoshnikov DmitrySoshnikov commented Mar 11, 2020

@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.

@DBJDBJ

This comment has been minimized.

Copy link

@DBJDBJ DBJDBJ commented Apr 15, 2020

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.

@DmitrySoshnikov

This comment has been minimized.

Copy link
Owner Author

@DmitrySoshnikov DmitrySoshnikov commented Apr 15, 2020

@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.

@DBJDBJ

This comment has been minimized.

Copy link

@DBJDBJ DBJDBJ commented Apr 16, 2020

@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.

@DmitrySoshnikov

This comment has been minimized.

Copy link
Owner Author

@DmitrySoshnikov DmitrySoshnikov commented Apr 17, 2020

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

@DBJDBJ

This comment has been minimized.

Copy link

@DBJDBJ DBJDBJ commented Apr 17, 2020

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.

@DmitrySoshnikov

This comment has been minimized.

Copy link
Owner Author

@DmitrySoshnikov DmitrySoshnikov commented Apr 17, 2020

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

@DBJDBJ

This comment has been minimized.

Copy link

@DBJDBJ DBJDBJ commented Apr 17, 2020

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.

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.