Memory pool (fixed-size block allocator) in Embedded C - Step-by-Step Execution

Concept Flow - Memory pool (fixed-size block allocator)

Initialize pool with fixed blocks

↓

Request allocation?

No→Exit

Yes↓

Check free blocks available

↓

Return NULL

↓

User uses block

↓

User frees block

↓

Return block to pool

↓

Repeat

This flow shows how a fixed-size memory pool allocates and frees blocks step-by-step.

Execution Sample

Embedded C

typedef struct Block {
  struct Block* next;
} Block;

Block* pool = NULL;

void init_pool(Block* blocks, int count) {
  for (int i = 0; i < count - 1; i++) {
    blocks[i].next = &blocks[i+1];
  }
  blocks[count-1].next = NULL;
  pool = &blocks[0];
}

Block* allocate() {
  if (!pool) return NULL;
  Block* block = pool;
  pool = pool->next;
  return block;
}

void free_block(Block* block) {
  block->next = pool;
  pool = block;
}

This code initializes a pool of fixed blocks, allocates a block by removing it from the pool, and frees a block by returning it to the pool.

Execution Table

Step	Action	Pool State (addresses)	Allocated Block	Output
1	Initialize pool with 3 blocks	&blocks[0] -> &blocks[1] -> &blocks[2] -> NULL	NULL	Pool ready
2	allocate() called	&blocks[1] -> &blocks[2] -> NULL	&blocks[0]	Block allocated: &blocks[0]
3	allocate() called	&blocks[2] -> NULL	&blocks[1]	Block allocated: &blocks[1]
4	allocate() called	NULL	&blocks[2]	Block allocated: &blocks[2]
5	allocate() called	NULL	NULL	No blocks left, return NULL
6	free_block(&blocks[1]) called	&blocks[1] -> NULL	NULL	Block &blocks[1] returned to pool
7	allocate() called	NULL	&blocks[1]	Block allocated: &blocks[1]
8	free_block(&blocks[0]) called	&blocks[0] -> NULL	NULL	Block &blocks[0] returned to pool
9	free_block(&blocks[2]) called	&blocks[2] -> &blocks[0] -> NULL	NULL	Block &blocks[2] returned to pool
10	allocate() called	&blocks[0] -> NULL	&blocks[2]	Block allocated: &blocks[2]
11	allocate() called	NULL	&blocks[0]	Block allocated: &blocks[0]
12	allocate() called	NULL	NULL	No blocks left, return NULL

💡 Allocation stops when pool is empty (NULL), free returns blocks to pool.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12
pool	NULL	&blocks[0]	&blocks[1]	&blocks[2]	NULL	NULL	&blocks[1]	NULL	&blocks[0]	&blocks[2]	&blocks[0]	NULL	NULL
allocated_block	NULL	NULL	&blocks[0]	&blocks[1]	&blocks[2]	NULL	NULL	&blocks[1]	NULL	NULL	&blocks[2]	&blocks[0]	NULL

Key Moments - 3 Insights

Why does allocate() return NULL at step 5 and 12?

Because the pool pointer is NULL, meaning no free blocks are left to allocate, as shown in execution_table rows 5 and 12.

How does free_block() add a block back to the pool?

It sets the freed block's next pointer to the current pool head, then updates pool to point to this block, shown in steps 6, 8, and 9.

Why does the pool state change after each allocate() and free_block()?

Because allocate() removes the first block from the pool, and free_block() adds a block back at the front, updating the linked list head each time.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which block is allocated?

A &blocks[1]

B &blocks[2]

C &blocks[0]

D NULL

💡 Hint

Check the 'Allocated Block' column at step 4 in the execution_table.

At which step does the pool become empty (NULL) after allocation?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look at the 'Pool State' column in execution_table rows 4 and 5.

If free_block(&blocks[1]) was not called at step 6, what would happen at step 7?

A allocate() would return &blocks[1]

B allocate() would return &blocks[0]

C allocate() would return NULL

D allocate() would crash

💡 Hint

Refer to variable_tracker for pool state after step 5 and before step 7.

Concept Snapshot

Memory pool manages fixed-size blocks.
Initialize pool as linked list of free blocks.
allocate() removes and returns first free block.
free_block() adds block back to front of pool.
Returns NULL if no blocks free.
Simple, fast fixed-size memory management.

Full Transcript

This visual execution shows how a fixed-size memory pool works in embedded C. We start by initializing a pool of blocks linked together. When allocate() is called, it removes the first block from the pool and returns it. If no blocks are left, allocate() returns NULL. When free_block() is called, it returns a block to the pool by adding it back to the front of the linked list. The execution table tracks each step, showing pool state and allocated blocks. Variable tracker shows how the pool pointer and allocated block change over time. Key moments clarify why allocate returns NULL when empty and how free_block updates the pool. The quiz tests understanding of allocation steps and pool emptiness. This method is a simple, efficient way to manage fixed-size memory blocks in embedded systems.

Practice

1.

What is the main advantage of using a memory pool with fixed-size blocks in embedded systems?

easy

A. Unlimited memory usage

B. Automatic garbage collection

C. Faster and predictable memory allocation

D. Dynamic resizing of blocks

Solution

1. Step 1: Understand memory pool purpose

   A memory pool divides memory into fixed-size blocks to allocate memory quickly without fragmentation.

2. Step 2: Identify advantage in embedded systems

   Embedded systems need fast and predictable memory allocation, which memory pools provide.

3. Final Answer:

   Faster and predictable memory allocation -> Option C

4. Quick Check:

   Memory pool advantage = Faster and predictable memory allocation [OK]

Hint: Memory pools speed up allocation by fixed block sizes [OK]

Common Mistakes:

• Confusing memory pools with dynamic resizing
• Thinking memory pools provide garbage collection
• Assuming memory pools allow unlimited memory

2.

Which of the following is the correct way to declare a fixed-size memory pool array for 10 blocks of 32 bytes each in C?

?

easy

A. char pool[10][32];

B. char pool[32][10];

C. char *pool[10];

D. char pool[10*32];

Solution

1. Step 1: Understand array dimensions

   We want 10 blocks, each block is 32 bytes, so array should be 10 rows and 32 columns.

2. Step 2: Match declaration syntax

   char pool[10][32]; declares 10 blocks of 32 bytes each correctly.

3. Final Answer:

   char pool[10][32]; -> Option A

4. Quick Check:

   Array size = 10 blocks x 32 bytes [OK]

Hint: Rows = blocks, columns = block size in bytes [OK]

Common Mistakes:

• Swapping dimensions (32 and 10)
• Using pointer array instead of fixed blocks
• Declaring a single large array without blocks

3.

Given this simplified memory pool allocator code snippet, what will be the output?

char pool[3][16];
int free_blocks = 3;

char* allocate() {
    if (free_blocks > 0) {
        return pool[--free_blocks];
    }
    return NULL;
}

int main() {
    char* p1 = allocate();
    char* p2 = allocate();
    char* p3 = allocate();
    char* p4 = allocate();
    printf("%p %p %p %p\n", p1, p2, p3, p4);
    return 0;
}

medium

A. Three valid pointers and one NULL pointer

B. All pointers are NULL

C. All pointers point to the same block

D. Compilation error due to missing headers

Solution

1. Step 1: Trace allocation calls

   Initially free_blocks=3. Each allocate() call decrements free_blocks and returns pool[free_blocks]. So p1=pool[2], p2=pool[1], p3=pool[0], p4=NULL because free_blocks=0.

2. Step 2: Understand output

   First three pointers are valid addresses, last pointer is NULL.

3. Final Answer:

   Three valid pointers and one NULL pointer -> Option A

4. Quick Check:

   3 blocks allocated, 4th returns NULL [OK]

Hint: Allocation decreases free_blocks; NULL when none left [OK]

Common Mistakes:

• Assuming pointers are all NULL
• Thinking pointers point to same block
• Forgetting to decrement free_blocks

4.

Identify the bug in this memory pool free function and select the correct fix.

void free_block(char* block) {
    if (free_blocks < MAX_BLOCKS) {
        pool[free_blocks++] = block;
    }
}

medium

A. No bug; function works correctly

B. Incrementing free_blocks before storing pointer causes overwrite

C. Should check if block is NULL before freeing

D. Store pointer in pool array is wrong; should mark block as free differently

Solution

1. Step 1: Analyze free_block logic

   The pool array holds actual memory blocks, not pointers. Storing a pointer in pool overwrites data.

2. Step 2: Correct way to free block

   Freeing should mark the block as available in a separate structure or use a free list, not overwrite pool data.

3. Final Answer:

   Store pointer in pool array is wrong; should mark block as free differently -> Option D

4. Quick Check:

   Freeing must not overwrite pool memory [OK]

Hint: Freeing must not overwrite pool data blocks [OK]

Common Mistakes:

• Overwriting pool memory with pointers
• Not checking block validity
• Assuming pool holds pointers, not blocks

5.

You want to implement a memory pool that supports 5 blocks of 64 bytes each. You also want to track which blocks are free using a bitmap (an integer where each bit represents a block's status: 0 = free, 1 = used). Which of the following code snippets correctly initializes the bitmap and allocates a block?

?

hard

A. int bitmap = 0xFF; // all used
char pool[5][64];
char* allocate() {
for (int i = 0; i < 5; i++) {
if ((bitmap & (1 << i)) == 0) {
bitmap &= ~(1 << i);
return pool[i];
}
}
return NULL;
}

B. int bitmap = 0; // all free
char pool[5][64];
char* allocate() {
for (int i = 0; i < 5; i++) {
if ((bitmap & (1 << i)) == 0) {
bitmap |= (1 << i);
return pool[i];
}
}
return NULL;
}

C. int bitmap = 0; // all used
char pool[5][64];
char* allocate() {
for (int i = 0; i < 5; i++) {
if ((bitmap & (1 << i)) != 0) {
bitmap |= (1 << i);
return pool[i];
}
}
return NULL;
}

D. int bitmap = 0xFF; // all free
char pool[5][64];
char* allocate() {
for (int i = 0; i < 5; i++) {
if ((bitmap & (1 << i)) != 0) {
bitmap &= ~(1 << i);
return pool[i];
}
}
return NULL;
}

Solution

1. Step 1: Understand bitmap meaning

   Bitmap bit 0 means free, 1 means used. So initializing bitmap=0 means all blocks free.

2. Step 2: Check allocation logic

   Allocation finds first free bit (0), sets it to 1 (used), and returns that block.

3. Final Answer:

   Bitmap initialized to 0; allocate sets bit to 1 on allocation -> Option B

4. Quick Check:

   0 = free, set bit to 1 when used [OK]

Hint: 0 bits free, set bit to 1 when allocated [OK]

Common Mistakes:

• Initializing bitmap with all bits set (all used)
• Checking wrong bit condition for free blocks
• Setting bits incorrectly on allocation