Fixed-Size Memory Pool Allocator — Detailed Explanation

This document explains how your allocator in allocator.cpp works, why each part exists, and what tradeoffs it has.

---

1) What problem this allocator solves

General-purpose allocators (new, malloc) are flexible, but they can be slower and may fragment memory over time.

A fixed-size pool allocator is optimized for cases where:

• Many objects have the same size
• Allocation/free happens frequently
• Predictable speed is important

Core idea

Reserve one big memory block once, split it into equal chunks, and reuse chunks.

• pool_alloc() gives one free chunk
• pool_free() returns a chunk back

Both operations are O(1).

---

2) Data structure used in your code

In allocator.cpp, the allocator state is:

• memory: start address of the full pool
• free_head: head of free-list
• chunk_size: real chunk size used internally
• chunk_count: total number of chunks
• free_count: how many are currently free

The free-list is intrusive: each free chunk stores a pointer to the next free chunk in its own first bytes.

So no external array (free_list[]) is needed.

---

3) Why alignment is needed (kAlignment)

You have:

• constexpr size_t kAlignment = alignof(std::max_align_t);

What this means

std::max_align_t is a type whose alignment is at least as strict as any scalar type on the platform. So alignof(std::max_align_t) gives a safe "maximum normal alignment".

Why used here

If chunk starts are not aligned correctly, writing certain types into them can cause:

• Undefined behavior
• Crashes on strict architectures
• Slow unaligned accesses

Using this alignment ensures chunk starts are broadly safe for common objects.

---

4) What align_up() does

Function in allocator.cpp:

• size_t align_up(size_t value, size_t alignment)

Purpose

Rounds value up to the next multiple of alignment.

Mathematically:

aligned = ceil(value / alignment) * alignment

Your bitwise implementation does the same efficiently (for power-of-two alignment, which this is).

Example

If requested_chunk_size = 30 and alignment = 16, then align_up(30, 16) = 32.

---

5) pool_init() step-by-step

pool_init(PoolAllocator* allocator, size_t requested_chunk_size, size_t chunk_count)

Steps

1. Validate inputs (not null, sizes not zero)
2. Compute actual_chunk_size
   • At least sizeof(void*) (needed because free chunks store next-pointer)
   • Aligned to kAlignment
3. Allocate one large block:
   • actual_chunk_size * chunk_count
4. Save allocator metadata
5. Build intrusive free-list:
   • chunk 0 points to chunk 1
   • chunk 1 points to chunk 2
   • ...
   • last chunk points to nullptr
6. Set free_head to first chunk

After this, all chunks are free.

---

6) pool_alloc() step-by-step

pool_alloc(PoolAllocator* allocator)

Steps

1. If allocator invalid or no free chunk (free_head == nullptr), return nullptr
2. Save current free_head as result chunk
3. Move free_head to next chunk (*reinterpret_cast<void**>(chunk))
4. Decrement free_count
5. Return chunk

This is a classic stack pop on singly linked list.

---

7) pool_free() step-by-step

pool_free(PoolAllocator* allocator, void* ptr)

Steps

1. Reject null args
2. Validate that ptr belongs to this pool and is chunk-aligned using pointer_belongs_to_pool()
3. Write old free_head into ptr (as next pointer)
4. Set free_head = ptr
5. Increment free_count

This is a stack push.

---

8) How pointer validation works

pointer_belongs_to_pool() checks:

1. Allocator and pointer are non-null
2. ptr in range [base, end)
3. (ptr - base) % chunk_size == 0 (exact chunk boundary)

This avoids freeing random pointers not produced by this pool.

---

9) pool_deinit()

pool_deinit(PoolAllocator* allocator):

• Frees memory
• Resets all fields to safe defaults

After this, allocator can't be used unless re-initialized.

---

10) Complexity and memory cost

Time complexity

• pool_init: $O(n)$ (build free-list)
• pool_alloc: $O(1)$
• pool_free: $O(1)$
• pool_deinit: $O(1)$

Extra memory overhead

• No side array
• Only allocator metadata + one pointer stored inside each free chunk

---

11) Important caveats

1. No double-free detection currently
   • Freeing same pointer twice can corrupt free-list
2. Not thread-safe
   • Needs lock or lock-free design for multithreading
3. Fixed-size only
   • Each allocation is exactly one chunk
4. Object lifetime
   • In C++, if storing non-trivial objects, manage constructors/destructors properly (placement new / explicit destructor)

---

12) Suggested improvements (optional)

• Add debug mode bitmap to detect double-free
• Add pool_owns(ptr) public helper
• Add stats (peak_used, alloc/free counters)
• Add typed wrapper template, e.g. Pool<T>
• Add thread-safe variant (std::mutex)

---

13) Mental model summary

Think of free chunks as a linked stack:

• alloc = pop top
• free = push top

Because all chunks are equal size and preallocated, operations stay fast and predictable.