aboutsummaryrefslogtreecommitdiff
path: root/mempool/src
diff options
context:
space:
mode:
Diffstat (limited to 'mempool/src')
-rw-r--r--mempool/src/mempool.c78
1 files changed, 40 insertions, 38 deletions
diff --git a/mempool/src/mempool.c b/mempool/src/mempool.c
index 059db93..fdb5f8c 100644
--- a/mempool/src/mempool.c
+++ b/mempool/src/mempool.c
@@ -3,22 +3,39 @@
3#include <stdlib.h> 3#include <stdlib.h>
4#include <string.h> 4#include <string.h>
5 5
6#define NO_BLOCK ((size_t)-1)
7
6static inline size_t min(size_t a, size_t b) { return a < b ? a : b; } 8static inline size_t min(size_t a, size_t b) { return a < b ? a : b; }
7 9
10/// Initialize the free list.
11/// All of the blocks in the pool are assumed free.
12static void init_free_list(mempool* pool) {
13 assert(pool);
14 for (size_t i = 0; i < pool->num_blocks - 1; ++i) {
15 pool->block_info[i].next = i + 1;
16 }
17 pool->block_info[pool->num_blocks - 1].next = NO_BLOCK;
18}
19
8bool mempool_make_( 20bool mempool_make_(
9 mempool* pool, BlockInfo* block_info, void* blocks, size_t num_blocks, 21 mempool* pool, BlockInfo* block_info, void* blocks, size_t num_blocks,
10 size_t block_size_bytes) { 22 size_t block_size_bytes) {
11 assert(pool); 23 assert(pool);
12 assert((block_info && blocks) || (!block_info && !blocks)); 24 assert((block_info && blocks) || (!block_info && !blocks));
13 assert(num_blocks >= 1); 25 assert(num_blocks >= 1);
26
14 pool->block_size_bytes = block_size_bytes; 27 pool->block_size_bytes = block_size_bytes;
15 pool->num_blocks = num_blocks; 28 pool->num_blocks = num_blocks;
16 pool->next_free_block = 0; 29 pool->head = 0;
17 pool->full = false; 30
31 // Initialize blocks and block info.
18 if (!block_info) { 32 if (!block_info) {
19 block_info = calloc(num_blocks, sizeof(BlockInfo)); 33 block_info = calloc(num_blocks, sizeof(BlockInfo));
20 blocks = calloc(num_blocks, block_size_bytes); 34 blocks = calloc(num_blocks, block_size_bytes);
21 pool->dynamic = true; 35 pool->dynamic = true;
36 if ((block_info == 0) || (blocks == 0)) {
37 return false;
38 }
22 } else { 39 } else {
23 memset(blocks, 0, num_blocks * block_size_bytes); 40 memset(blocks, 0, num_blocks * block_size_bytes);
24 memset(block_info, 0, num_blocks * sizeof(BlockInfo)); 41 memset(block_info, 0, num_blocks * sizeof(BlockInfo));
@@ -26,7 +43,10 @@ bool mempool_make_(
26 } 43 }
27 pool->block_info = block_info; 44 pool->block_info = block_info;
28 pool->blocks = blocks; 45 pool->blocks = blocks;
29 return (block_info != 0) && (blocks != 0); 46
47 init_free_list(pool);
48
49 return true;
30} 50}
31 51
32void mempool_del_(mempool* pool) { 52void mempool_del_(mempool* pool) {
@@ -45,37 +65,24 @@ void mempool_del_(mempool* pool) {
45 65
46void mempool_clear_(mempool* pool) { 66void mempool_clear_(mempool* pool) {
47 assert(pool); 67 assert(pool);
48 pool->next_free_block = 0; 68 pool->head = 0;
49 pool->full = false;
50 memset(pool->blocks, 0, pool->num_blocks * pool->block_size_bytes); 69 memset(pool->blocks, 0, pool->num_blocks * pool->block_size_bytes);
51 memset(pool->block_info, 0, pool->num_blocks * sizeof(BlockInfo)); 70 memset(pool->block_info, 0, pool->num_blocks * sizeof(BlockInfo));
71 init_free_list(pool);
52} 72}
53 73
54void* mempool_alloc_(mempool* pool) { 74void* mempool_alloc_(mempool* pool) {
55 assert(pool); 75 assert(pool);
56 76
57 if (pool->full) { 77 if (pool->head == NO_BLOCK) {
58 return 0; 78 return 0;
59 } 79 }
60 80
61 // Allocate the block. 81 // Allocate the block.
62 void* block = &pool->blocks[pool->next_free_block * pool->block_size_bytes]; 82 BlockInfo* head = &pool->block_info[pool->head];
63 pool->block_info[pool->next_free_block].used = true; 83 void* block = &pool->blocks[pool->head * pool->block_size_bytes];
64 84 head->used = true;
65 // Search for the next free block. If it does not exist, flag the pool 85 pool->head = head->next;
66 // full.
67 //
68 // The search starts near the current free block, where we might be more
69 // likely to find free blocks. The search starts with i=1 since we only
70 // need to test the other N-1 blocks in the pool.
71 pool->full = true;
72 for (size_t i = 1; i < pool->num_blocks; i++) {
73 pool->next_free_block = (pool->next_free_block + 1) % pool->num_blocks;
74 if (!pool->block_info[pool->next_free_block].used) {
75 pool->full = false;
76 break;
77 }
78 }
79 86
80 return block; 87 return block;
81} 88}
@@ -84,27 +91,22 @@ void mempool_free_(mempool* pool, void** block_ptr) {
84 assert(pool); 91 assert(pool);
85 assert(block_ptr); 92 assert(block_ptr);
86 93
87 // Zero out the block so that we don't get stray values the next time it is
88 // allocated.
89 memset(*block_ptr, 0, pool->block_size_bytes);
90
91 const size_t block_index = 94 const size_t block_index =
92 ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes; 95 ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes;
93 assert(block_index < pool->num_blocks); 96 assert(block_index < pool->num_blocks);
97 BlockInfo* info = &pool->block_info[block_index];
94 98
95 // Disallow double-frees. 99 // Disallow double-frees.
96 assert(pool->block_info[block_index].used); 100 assert(info->used);
97 101
98 pool->block_info[block_index].used = false; 102 // Zero out the block so that we don't get stray values the next time it is
99 if (pool->full) { 103 // allocated.
100 pool->next_free_block = block_index; 104 memset(*block_ptr, 0, pool->block_size_bytes);
101 pool->full = false; 105
102 } else { 106 // Free the block and add it to the head of the free list.
103 // Prefer to allocate blocks towards the start of the pool. This way, blocks 107 info->used = false;
104 // should cluster around this area and the pool should offer better memory 108 info->next = pool->head;
105 // locality for used blocks. 109 pool->head = block_index;
106 pool->next_free_block = min(pool->next_free_block, block_index);
107 }
108 110
109 *block_ptr = 0; 111 *block_ptr = 0;
110} 112}