Operating SystemsOS Project Ideas

Operating System Project Ideas

LevelAdvanced

Duration120 mins

TopicOS Project Ideas

3 / 5

Memory Allocator

Building Your Own Memory Allocator

Every malloc() call you've ever made invokes one of the most critical pieces of systems software—the memory allocator. A well-designed allocator can make programs run 10x faster; a poorly designed one causes fragmentation, cache misses, and memory exhaustion.

Building your own allocator is a masterclass in systems programming: you'll manage raw memory, implement data structures without using malloc itself, handle alignment requirements, and optimize for real-world allocation patterns.

What You Will Learn

By the end of this page, you will understand heap management, implement first-fit/best-fit/next-fit strategies, handle coalescing and splitting, manage metadata, and understand the tradeoffs production allocators make.

Allocator Fundamentals

An allocator manages a heap—a contiguous region of memory obtained from the OS. It must:

Track free space — Know which regions are available
Satisfy allocation requests — Find and return appropriately sized blocks
Handle deallocations — Mark returned memory as free
Manage fragmentation — Coalesce adjacent free blocks
Maintain alignment — Return properly aligned addresses

Memory is obtained from the OS via:

sbrk() — Extends the data segment (traditional Unix)
mmap() — Maps anonymous memory pages (modern approach)

The allocator subdivides these large regions into smaller blocks for application use.

Allocator Design Goals
Goal	Description	Tradeoff
Throughput	Allocations per second	vs. memory efficiency
Utilization	Percentage of heap actually used	vs. speed
Locality	Related allocations near each other	vs. fragmentation
Low fragmentation	Minimize wasted space	vs. allocation speed

Block Structure and Metadata

Each block needs metadata to track its size and status. The challenge: this metadata consumes space and must be managed without using malloc!

Common approaches:

Header only — Store size and status before each block
Header + footer — Enable bidirectional coalescing
Boundary tags — Size at both ends for O(1) coalescing

allocator.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#ifndef ALLOCATOR_H
#define ALLOCATOR_H
 
#include <stddef.h>
#include <stdint.h>
 
// Alignment requirement (typically 8 or 16 bytes)
#define ALIGNMENT 16
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
 
// Minimum block size (header + minimum payload)
#define MIN_BLOCK_SIZE (sizeof(BlockHeader) + ALIGNMENT)
 
/**
 * Block header - stored at the start of each block.
 * The size field uses the low bit as an "allocated" flag.
 */
typedef struct BlockHeader {
    size_t size_and_flags;      // Size + allocated bit
    struct BlockHeader *next;    // Next free block (only used when free)
    struct BlockHeader *prev;    // Previous free block (only used when free)
} BlockHeader;
 
// Extract size from header (mask off low bits)
#define GET_SIZE(header) ((header)->size_and_flags & ~0xF)
 
// Check if block is allocated
#define IS_ALLOCATED(header) ((header)->size_and_flags & 0x1)
 
// Set size and allocated flag
#define SET_SIZE_ALLOC(header, size, alloc) \
    ((header)->size_and_flags = ((size) & ~0xF) | ((alloc) & 0x1))
 
// Get footer from header (at end of block)
#define GET_FOOTER(header) \
    ((size_t *)((char *)(header) + GET_SIZE(header) - sizeof(size_t)))
 
// Get next block in memory
#define NEXT_BLOCK(header) \
    ((BlockHeader *)((char *)(header) + GET_SIZE(header)))
 
// Get previous block in memory (using footer)
#define PREV_BLOCK(header) \
    ((BlockHeader *)((char *)(header) - \
        (*(((size_t *)(header)) - 1) & ~0xF)))
 
// Convert header pointer to payload pointer
#define HEADER_TO_PAYLOAD(header) \
    ((void *)((char *)(header) + sizeof(BlockHeader)))
 
// Convert payload pointer to header pointer
#define PAYLOAD_TO_HEADER(payload) \
    ((BlockHeader *)((char *)(payload) - sizeof(BlockHeader)))
 
#endif

Alignment Is Critical

malloc() must return addresses aligned to the platform's requirement (typically 8 or 16 bytes). Misaligned access causes crashes on some architectures and performance penalties on others. Always round up block sizes to alignment boundaries.

Free List Management Strategies

The free list tracks available blocks. Different organizations optimize for different goals:

Implicit free list — Walk through all blocks, checking status

Simple but O(n) where n = total blocks

Explicit free list — Linked list of only free blocks

O(n) where n = free blocks only (much faster)

Segregated free lists — Multiple lists by size class

O(1) average case for common sizes

allocator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <unistd.h>
#include <string.h>
#include "allocator.h"
 
// Global free list head
static BlockHeader *free_list_head = NULL;
 
// Heap boundaries
static void *heap_start = NULL;
static void *heap_end = NULL;
 
/**
 * Initialize the allocator with initial heap.
 */
void allocator_init(void) {
    // Request initial heap from OS
    heap_start = sbrk(0);
    void *request = sbrk(4096);  // 4KB initial heap
    if (request == (void *)-1) {
        return;  // sbrk failed
    }
    heap_end = sbrk(0);
 
    // Create initial free block spanning entire heap
    free_list_head = (BlockHeader *)heap_start;
    size_t heap_size = (char *)heap_end - (char *)heap_start;
    SET_SIZE_ALLOC(free_list_head, heap_size, 0);
    free_list_head->next = NULL;
    free_list_head->prev = NULL;
 
    // Set footer
    *GET_FOOTER(free_list_head) = heap_size;
}
 
/**
 * Add block to free list (LIFO insertion).
 */
void add_to_free_list(BlockHeader *block) {
    block->next = free_list_head;
    block->prev = NULL;
    if (free_list_head != NULL) {
        free_list_head->prev = block;
    }
    free_list_head = block;
}
 
/**
 * Remove block from free list.
 */
void remove_from_free_list(BlockHeader *block) {
    if (block->prev != NULL) {
        block->prev->next = block->next;
    } else {
        free_list_head = block->next;
    }
    if (block->next != NULL) {
        block->next->prev = block->prev;
    }
}
 
/**
 * First-fit: Find first block large enough.
 * Simple, fast, but causes fragmentation at heap start.
 */
BlockHeader *find_first_fit(size_t size) {
    BlockHeader *current = free_list_head;
    while (current != NULL) {
        if (GET_SIZE(current) >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // No suitable block found
}
 
/**
 * Best-fit: Find smallest block that fits.
 * Better utilization, but slower O(n) scan.
 */
BlockHeader *find_best_fit(size_t size) {
    BlockHeader *current = free_list_head;
    BlockHeader *best = NULL;
 
    while (current != NULL) {
        size_t block_size = GET_SIZE(current);
        if (block_size >= size) {
            if (best == NULL || block_size < GET_SIZE(best)) {
                best = current;
                if (block_size == size) {
                    break;  // Perfect fit
                }
            }
        }
        current = current->next;
    }
    return best;
}

Search Strategy Comparison
Strategy	Time	Fragmentation	Use Case
First-fit	O(n) average	Moderate	General purpose
Next-fit	O(n) average	Better spread	Sequential allocs
Best-fit	O(n) always	Low internal	Memory-constrained
Worst-fit	O(n) always	High	Rarely used
Segregated	O(1) average	Low	Production allocators

Implementing malloc and free

Now we implement the core allocation functions. Key operations:

malloc(size):

Calculate total block size (header + payload + alignment)
Search free list for suitable block
If found, potentially split block
Mark as allocated and return payload pointer

free(ptr):

Get block header from payload pointer
Mark as free
Coalesce with adjacent free blocks
Add to free list

malloc_free.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/**
 * Split a block if remainder is large enough.
 * Returns the block to allocate (may be original or split).
 */
void split_block(BlockHeader *block, size_t needed_size) {
    size_t current_size = GET_SIZE(block);
    size_t remainder = current_size - needed_size;
 
    // Only split if remainder can hold minimum block
    if (remainder >= MIN_BLOCK_SIZE) {
        // Shrink current block
        SET_SIZE_ALLOC(block, needed_size, 1);
        *GET_FOOTER(block) = needed_size | 1;
 
        // Create new free block from remainder
        BlockHeader *new_block = NEXT_BLOCK(block);
        SET_SIZE_ALLOC(new_block, remainder, 0);
        *GET_FOOTER(new_block) = remainder;
 
        // Add new block to free list
        add_to_free_list(new_block);
    } else {
        // Use entire block (internal fragmentation)
        SET_SIZE_ALLOC(block, current_size, 1);
        *GET_FOOTER(block) = current_size | 1;
    }
}
 
/**
 * Extend heap when no suitable block exists.
 */
BlockHeader *extend_heap(size_t size) {
    // Round up to page boundary for efficiency
    size_t extend_size = ALIGN(size);
    if (extend_size < 4096) extend_size = 4096;
 
    void *request = sbrk(extend_size);
    if (request == (void *)-1) {
        return NULL;  // Out of memory
    }
    heap_end = sbrk(0);
 
    // Create new free block
    BlockHeader *new_block = (BlockHeader *)request;
    SET_SIZE_ALLOC(new_block, extend_size, 0);
    *GET_FOOTER(new_block) = extend_size;
 
    return new_block;
}
 
/**
 * malloc - Allocate memory of given size.
 */
void *my_malloc(size_t size) {
    if (size == 0) return NULL;
 
    // Initialize on first call
    if (heap_start == NULL) {
        allocator_init();
    }
 
    // Calculate required block size
    size_t block_size = ALIGN(size + sizeof(BlockHeader) + sizeof(size_t));
    if (block_size < MIN_BLOCK_SIZE) {
        block_size = MIN_BLOCK_SIZE;
    }
 
    // Find suitable free block
    BlockHeader *block = find_first_fit(block_size);
 
    // Extend heap if necessary
    if (block == NULL) {
        block = extend_heap(block_size);
        if (block == NULL) {
            return NULL;  // Out of memory
        }
    } else {
        remove_from_free_list(block);
    }
 
    // Split block if too large
    split_block(block, block_size);
 
    return HEADER_TO_PAYLOAD(block);
}
 
/**
 * Coalesce with adjacent free blocks.
 */
BlockHeader *coalesce(BlockHeader *block) {
    size_t size = GET_SIZE(block);
    BlockHeader *next = NEXT_BLOCK(block);
    BlockHeader *prev = NULL;
 
    // Check if previous block exists and is free
    int prev_alloc = 1;  // Assume allocated
    if ((void *)block > heap_start) {
        size_t *prev_footer = (size_t *)block - 1;
        prev_alloc = (*prev_footer) & 1;
        if (!prev_alloc) {
            prev = PREV_BLOCK(block);
        }
    }
 
    // Check if next block is free
    int next_alloc = 1;
    if ((void *)next < heap_end) {
        next_alloc = IS_ALLOCATED(next);
    }
 
    if (prev_alloc && next_alloc) {
        // No coalescing possible
        return block;
    } else if (prev_alloc && !next_alloc) {
        // Coalesce with next block
        remove_from_free_list(next);
        size += GET_SIZE(next);
        SET_SIZE_ALLOC(block, size, 0);
        *GET_FOOTER(block) = size;
    } else if (!prev_alloc && next_alloc) {
        // Coalesce with previous block
        remove_from_free_list(prev);
        size += GET_SIZE(prev);
        SET_SIZE_ALLOC(prev, size, 0);
        *GET_FOOTER(prev) = size;
        block = prev;
    } else {
        // Coalesce with both
        remove_from_free_list(prev);
        remove_from_free_list(next);
        size += GET_SIZE(prev) + GET_SIZE(next);
        SET_SIZE_ALLOC(prev, size, 0);
        *GET_FOOTER(prev) = size;
        block = prev;
    }
 
    return block;
}
 
/**
 * free - Return memory to the allocator.
 */
void my_free(void *ptr) {
    if (ptr == NULL) return;
 
    BlockHeader *block = PAYLOAD_TO_HEADER(ptr);
 
    // Mark as free
    size_t size = GET_SIZE(block);
    SET_SIZE_ALLOC(block, size, 0);
    *GET_FOOTER(block) = size;
 
    // Coalesce adjacent free blocks
    block = coalesce(block);
 
    // Add to free list
    add_to_free_list(block);
}

Summary: Memory Allocator Project

Key Takeaways

•Metadata overhead matters — Every block needs tracking information
•Coalescing prevents fragmentation — Merge adjacent free blocks immediately
•Alignment is non-negotiable — Hardware requires it, performance demands it
•Search strategy affects performance — Choose based on allocation patterns
•Splitting and coalescing are inverses — Balance utilization vs. overhead
•Production allocators are sophisticated — jemalloc, tcmalloc use thread caches and size classes

Extension Ideas

Extend with: realloc() implementation, segregated free lists, thread-safe locking, memory debugging (detect double-free, use-after-free), and performance benchmarking against system malloc.

3 / 5

Loading learning content...

Operating SystemsOS Project Ideas

Operating System Project Ideas

LevelAdvanced

Duration120 mins

TopicOS Project Ideas

3 / 5

Memory Allocator

Building Your Own Memory Allocator

What You Will Learn

Allocator Fundamentals

An allocator manages a heap—a contiguous region of memory obtained from the OS. It must:

Track free space — Know which regions are available
Satisfy allocation requests — Find and return appropriately sized blocks
Handle deallocations — Mark returned memory as free
Manage fragmentation — Coalesce adjacent free blocks
Maintain alignment — Return properly aligned addresses

Memory is obtained from the OS via:

sbrk() — Extends the data segment (traditional Unix)
mmap() — Maps anonymous memory pages (modern approach)

The allocator subdivides these large regions into smaller blocks for application use.

Allocator Design Goals
Goal	Description	Tradeoff
Throughput	Allocations per second	vs. memory efficiency
Utilization	Percentage of heap actually used	vs. speed
Locality	Related allocations near each other	vs. fragmentation
Low fragmentation	Minimize wasted space	vs. allocation speed

Block Structure and Metadata

Each block needs metadata to track its size and status. The challenge: this metadata consumes space and must be managed without using malloc!

Common approaches:

Header only — Store size and status before each block
Header + footer — Enable bidirectional coalescing
Boundary tags — Size at both ends for O(1) coalescing

allocator.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#ifndef ALLOCATOR_H
#define ALLOCATOR_H
 
#include <stddef.h>
#include <stdint.h>
 
// Alignment requirement (typically 8 or 16 bytes)
#define ALIGNMENT 16
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
 
// Minimum block size (header + minimum payload)
#define MIN_BLOCK_SIZE (sizeof(BlockHeader) + ALIGNMENT)
 
/**
 * Block header - stored at the start of each block.
 * The size field uses the low bit as an "allocated" flag.
 */
typedef struct BlockHeader {
    size_t size_and_flags;      // Size + allocated bit
    struct BlockHeader *next;    // Next free block (only used when free)
    struct BlockHeader *prev;    // Previous free block (only used when free)
} BlockHeader;
 
// Extract size from header (mask off low bits)
#define GET_SIZE(header) ((header)->size_and_flags & ~0xF)
 
// Check if block is allocated
#define IS_ALLOCATED(header) ((header)->size_and_flags & 0x1)
 
// Set size and allocated flag
#define SET_SIZE_ALLOC(header, size, alloc) \
    ((header)->size_and_flags = ((size) & ~0xF) | ((alloc) & 0x1))
 
// Get footer from header (at end of block)
#define GET_FOOTER(header) \
    ((size_t *)((char *)(header) + GET_SIZE(header) - sizeof(size_t)))
 
// Get next block in memory
#define NEXT_BLOCK(header) \
    ((BlockHeader *)((char *)(header) + GET_SIZE(header)))
 
// Get previous block in memory (using footer)
#define PREV_BLOCK(header) \
    ((BlockHeader *)((char *)(header) - \
        (*(((size_t *)(header)) - 1) & ~0xF)))
 
// Convert header pointer to payload pointer
#define HEADER_TO_PAYLOAD(header) \
    ((void *)((char *)(header) + sizeof(BlockHeader)))
 
// Convert payload pointer to header pointer
#define PAYLOAD_TO_HEADER(payload) \
    ((BlockHeader *)((char *)(payload) - sizeof(BlockHeader)))
 
#endif

Alignment Is Critical

Free List Management Strategies

The free list tracks available blocks. Different organizations optimize for different goals:

Implicit free list — Walk through all blocks, checking status

Simple but O(n) where n = total blocks

Explicit free list — Linked list of only free blocks

O(n) where n = free blocks only (much faster)

Segregated free lists — Multiple lists by size class

O(1) average case for common sizes

allocator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <unistd.h>
#include <string.h>
#include "allocator.h"
 
// Global free list head
static BlockHeader *free_list_head = NULL;
 
// Heap boundaries
static void *heap_start = NULL;
static void *heap_end = NULL;
 
/**
 * Initialize the allocator with initial heap.
 */
void allocator_init(void) {
    // Request initial heap from OS
    heap_start = sbrk(0);
    void *request = sbrk(4096);  // 4KB initial heap
    if (request == (void *)-1) {
        return;  // sbrk failed
    }
    heap_end = sbrk(0);
 
    // Create initial free block spanning entire heap
    free_list_head = (BlockHeader *)heap_start;
    size_t heap_size = (char *)heap_end - (char *)heap_start;
    SET_SIZE_ALLOC(free_list_head, heap_size, 0);
    free_list_head->next = NULL;
    free_list_head->prev = NULL;
 
    // Set footer
    *GET_FOOTER(free_list_head) = heap_size;
}
 
/**
 * Add block to free list (LIFO insertion).
 */
void add_to_free_list(BlockHeader *block) {
    block->next = free_list_head;
    block->prev = NULL;
    if (free_list_head != NULL) {
        free_list_head->prev = block;
    }
    free_list_head = block;
}
 
/**
 * Remove block from free list.
 */
void remove_from_free_list(BlockHeader *block) {
    if (block->prev != NULL) {
        block->prev->next = block->next;
    } else {
        free_list_head = block->next;
    }
    if (block->next != NULL) {
        block->next->prev = block->prev;
    }
}
 
/**
 * First-fit: Find first block large enough.
 * Simple, fast, but causes fragmentation at heap start.
 */
BlockHeader *find_first_fit(size_t size) {
    BlockHeader *current = free_list_head;
    while (current != NULL) {
        if (GET_SIZE(current) >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // No suitable block found
}
 
/**
 * Best-fit: Find smallest block that fits.
 * Better utilization, but slower O(n) scan.
 */
BlockHeader *find_best_fit(size_t size) {
    BlockHeader *current = free_list_head;
    BlockHeader *best = NULL;
 
    while (current != NULL) {
        size_t block_size = GET_SIZE(current);
        if (block_size >= size) {
            if (best == NULL || block_size < GET_SIZE(best)) {
                best = current;
                if (block_size == size) {
                    break;  // Perfect fit
                }
            }
        }
        current = current->next;
    }
    return best;
}

Search Strategy Comparison
Strategy	Time	Fragmentation	Use Case
First-fit	O(n) average	Moderate	General purpose
Next-fit	O(n) average	Better spread	Sequential allocs
Best-fit	O(n) always	Low internal	Memory-constrained
Worst-fit	O(n) always	High	Rarely used
Segregated	O(1) average	Low	Production allocators

Implementing malloc and free

Now we implement the core allocation functions. Key operations:

malloc(size):

Calculate total block size (header + payload + alignment)
Search free list for suitable block
If found, potentially split block
Mark as allocated and return payload pointer

free(ptr):

Get block header from payload pointer
Mark as free
Coalesce with adjacent free blocks
Add to free list

malloc_free.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/**
 * Split a block if remainder is large enough.
 * Returns the block to allocate (may be original or split).
 */
void split_block(BlockHeader *block, size_t needed_size) {
    size_t current_size = GET_SIZE(block);
    size_t remainder = current_size - needed_size;
 
    // Only split if remainder can hold minimum block
    if (remainder >= MIN_BLOCK_SIZE) {
        // Shrink current block
        SET_SIZE_ALLOC(block, needed_size, 1);
        *GET_FOOTER(block) = needed_size | 1;
 
        // Create new free block from remainder
        BlockHeader *new_block = NEXT_BLOCK(block);
        SET_SIZE_ALLOC(new_block, remainder, 0);
        *GET_FOOTER(new_block) = remainder;
 
        // Add new block to free list
        add_to_free_list(new_block);
    } else {
        // Use entire block (internal fragmentation)
        SET_SIZE_ALLOC(block, current_size, 1);
        *GET_FOOTER(block) = current_size | 1;
    }
}
 
/**
 * Extend heap when no suitable block exists.
 */
BlockHeader *extend_heap(size_t size) {
    // Round up to page boundary for efficiency
    size_t extend_size = ALIGN(size);
    if (extend_size < 4096) extend_size = 4096;
 
    void *request = sbrk(extend_size);
    if (request == (void *)-1) {
        return NULL;  // Out of memory
    }
    heap_end = sbrk(0);
 
    // Create new free block
    BlockHeader *new_block = (BlockHeader *)request;
    SET_SIZE_ALLOC(new_block, extend_size, 0);
    *GET_FOOTER(new_block) = extend_size;
 
    return new_block;
}
 
/**
 * malloc - Allocate memory of given size.
 */
void *my_malloc(size_t size) {
    if (size == 0) return NULL;
 
    // Initialize on first call
    if (heap_start == NULL) {
        allocator_init();
    }
 
    // Calculate required block size
    size_t block_size = ALIGN(size + sizeof(BlockHeader) + sizeof(size_t));
    if (block_size < MIN_BLOCK_SIZE) {
        block_size = MIN_BLOCK_SIZE;
    }
 
    // Find suitable free block
    BlockHeader *block = find_first_fit(block_size);
 
    // Extend heap if necessary
    if (block == NULL) {
        block = extend_heap(block_size);
        if (block == NULL) {
            return NULL;  // Out of memory
        }
    } else {
        remove_from_free_list(block);
    }
 
    // Split block if too large
    split_block(block, block_size);
 
    return HEADER_TO_PAYLOAD(block);
}
 
/**
 * Coalesce with adjacent free blocks.
 */
BlockHeader *coalesce(BlockHeader *block) {
    size_t size = GET_SIZE(block);
    BlockHeader *next = NEXT_BLOCK(block);
    BlockHeader *prev = NULL;
 
    // Check if previous block exists and is free
    int prev_alloc = 1;  // Assume allocated
    if ((void *)block > heap_start) {
        size_t *prev_footer = (size_t *)block - 1;
        prev_alloc = (*prev_footer) & 1;
        if (!prev_alloc) {
            prev = PREV_BLOCK(block);
        }
    }
 
    // Check if next block is free
    int next_alloc = 1;
    if ((void *)next < heap_end) {
        next_alloc = IS_ALLOCATED(next);
    }
 
    if (prev_alloc && next_alloc) {
        // No coalescing possible
        return block;
    } else if (prev_alloc && !next_alloc) {
        // Coalesce with next block
        remove_from_free_list(next);
        size += GET_SIZE(next);
        SET_SIZE_ALLOC(block, size, 0);
        *GET_FOOTER(block) = size;
    } else if (!prev_alloc && next_alloc) {
        // Coalesce with previous block
        remove_from_free_list(prev);
        size += GET_SIZE(prev);
        SET_SIZE_ALLOC(prev, size, 0);
        *GET_FOOTER(prev) = size;
        block = prev;
    } else {
        // Coalesce with both
        remove_from_free_list(prev);
        remove_from_free_list(next);
        size += GET_SIZE(prev) + GET_SIZE(next);
        SET_SIZE_ALLOC(prev, size, 0);
        *GET_FOOTER(prev) = size;
        block = prev;
    }
 
    return block;
}
 
/**
 * free - Return memory to the allocator.
 */
void my_free(void *ptr) {
    if (ptr == NULL) return;
 
    BlockHeader *block = PAYLOAD_TO_HEADER(ptr);
 
    // Mark as free
    size_t size = GET_SIZE(block);
    SET_SIZE_ALLOC(block, size, 0);
    *GET_FOOTER(block) = size;
 
    // Coalesce adjacent free blocks
    block = coalesce(block);
 
    // Add to free list
    add_to_free_list(block);
}

Summary: Memory Allocator Project

Key Takeaways

•Metadata overhead matters — Every block needs tracking information
•Coalescing prevents fragmentation — Merge adjacent free blocks immediately
•Alignment is non-negotiable — Hardware requires it, performance demands it
•Search strategy affects performance — Choose based on allocation patterns
•Splitting and coalescing are inverses — Balance utilization vs. overhead
•Production allocators are sophisticated — jemalloc, tcmalloc use thread caches and size classes

Extension Ideas

Extend with: realloc() implementation, segregated free lists, thread-safe locking, memory debugging (detect double-free, use-after-free), and performance benchmarking against system malloc.

3 / 5