subtle usage of reinterpret cast in Pool allocator implementation

Question

I am currently implementing my own pool allocator to store n chunks of the same size in one big block of memory. I am linking all the chunks together using a *next pointer stored in the struct chunk like this

struct Chunk{
    Chunk* next;
};

so I would expect to make a linked list like this given that i have a variable num_chunks which stores the number of chunks in the block

Chunk* allocate_block(size_t chunk_size){
        alloc_pointer = (Chunk*) malloc(chunk_size * num_chunks);
        Chunk* chunk = alloc_pointer;
        for (int i = 0; i < num_chunks; ++i){
            /*
                I need to solve the problem of how to
                link all these chunks together.
                So I know that I have to work using the next pointer.
                This next pointer must point to an address chunk_size
                away from the current pointer and so on so forth.
                So basically:
                    chunk -> next = alloc_pointer + chunk_size
                    and chunk is going to be this chunk -> next on the
                    successive call.
            */
            chunk -> next = chunk + chunk_size;
            chunk = chunk -> next;}

        chunk -> next = nullptr;
        return chunk;    
    }

However looking at a blog post I have this implementation which makes sense but still do not understand why mine should be wrong

/**
 * 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;
}

I don’t really understand why I should convert the type of chunk to char and then add that to the size of the chunk. Thanks in advance

The result of `chunk + chunk_size` and `reinterpret_cast(chunk) + chunkSize` is very different, as debugging will show you — UnholySheep, Dec 04 '21 at 17:16
If you rewrote `chunk + chunk_size` as `reinterpret_cast(chunk) + chunk_size * sizeof(Chunk)` you'd immediately see that it will result in a different address than `reinterpret_cast(chunk) + chunkSize` — UnholySheep, Dec 04 '21 at 17:20

Shane Bishop · Accepted Answer · 2021-12-04T22:33:09.663

When you add to pointers, pointer arithmetic is used. With pointer arithmetic, the memory address result depends on the size of the pointer being added to.

Let's break down this expression:

reinterpret_cast<Chunk *>(reinterpret_cast<char *>(chunk) + chunkSize);

The first part of this expression to be evaluated is

reinterpret_cast<char *>(chunk)

This will take the chunk pointer and tell the compiler to treat it as a char* rather than as Chunk*. This means that when pointer arithmetic is performed on the pointer, it will be in terms of 1 byte offsets (since a char has a size of 1 byte), instead of in offsets of sizeof(Chunk) bytes.

Next, chunkSize is added to this pointer. Because we are doing pointer arithmetic on a char* pointer, we will take the memory address of chunk, and add chunkSize*sizeof(char) = chunkSize*1 to that memory address.

That covers everything inside the outer set of brackets.

The problem now is that the result of our pointer arithmetic is still understood by the compiler to be a char* pointer, but we really want it to be a Chunk*. To fix this, we cast back to Chunk*. This effectively undoes the temporary cast to char*.

You can find more info on pointer arithmetic in the answers to this question.

don't you have to also consider alignment when implementing something like a memory pool for a type? — Sergey Kolesnik, Dec 05 '21 at 01:26

subtle usage of reinterpret cast in Pool allocator implementation

1 Answers1