memory pool 的高效实现（代码）
mpool.h
|
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 |
#ifndef __febird_c_mpool_h__ #define __febird_c_mpool_h__ #ifdef __cplusplus extern "C" { #endif //------------------------------------------------------------------------------------------ typedef void* (*chunk_alloc_ft)(struct chunk_allocator* self, size_t size); typedef void* (*chunk_realloc_ft)(struct chunk_allocator* self, void* block, size_t olc_size, size_t new_size); typedef void (*chunk_free_ft)(struct chunk_allocator* self, void* block, size_t size); struct chunk_allocator { void* (*chunk_alloc)(struct chunk_allocator* self, size_t size); void* (*chunk_realloc)(struct chunk_allocator* self, void* block, size_t olc_size, size_t new_size); void (*chunk_free)(struct chunk_allocator* self, void* block, size_t size); }; struct fixed_mpool { struct chunk_allocator* ca; struct mpool_chunk* pChunks; struct mpool_cell* head; size_t iNextChunk; size_t nChunks; size_t cell_size; size_t chunk_size; size_t used_cells; // size_t free_cells; }; // 是否允许 mpool 分配超出 max_cell_size 的内存块 //#define FEBIRD_MPOOL_ALLOW_BIG_BLOCK #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK struct big_block_header { struct big_block_header *next, *prev; }; #endif struct mpool { //------------------------------------------------------------------------------------------ /// export a chunk_allocator interface void* (*chunk_alloc)(struct chunk_allocator* self, size_t size); void* (*chunk_realloc)(struct chunk_allocator* self, void* block, size_t olc_size, size_t new_size); void (*chunk_free)(struct chunk_allocator* self, void* block, size_t size); //------------------------------------------------------------------------------------------ /// chunk_allocator for this mpool self struct chunk_allocator* ca; struct fixed_mpool* fixed; size_t max_cell_size; size_t chunk_size; #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK size_t big_blocks; // size > max_cell_size, use malloc, this is rare case struct big_block_header big_list; #endif }; void fixed_mpool_init(struct fixed_mpool* mpf); void fixed_mpool_destroy(struct fixed_mpool* mpf); void* fixed_mpool_alloc(struct fixed_mpool* mpf); void fixed_mpool_free(struct fixed_mpool* mpf, void* ptr); void mpool_init(struct mpool* mp); void mpool_destroy(struct mpool* mp); void* mpool_alloc(struct mpool* mp, size_t size); void mpool_free(struct mpool* mp, void* ptr, size_t size); size_t mpool_used_cells(const struct mpool* mp); size_t mpool_used_bytes(const struct mpool* mp); #ifdef __cplusplus } #endif #endif // __febird_c_mpool_h__ |
mpool.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 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 |
#include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "mpool.h" /* must be power of 2 and greater than sizeof(void*) */ #define MPOOL_MIN_CELL 8 #define MPOOL_MIN_CHUNK 256 struct mpool_cell { struct mpool_cell* next; }; struct mpool_chunk { struct mpool_cell* cell; // cell array size_t size; // size in bytes; }; /**********************************************************************************/ /** * chunk_allocator use malloc/free */ static void* chunk_malloc_alloc(struct chunk_allocator* , size_t size) { return malloc(size); } static void chunk_malloc_free(struct chunk_allocator* , void* block, size_t size) { return free(block); } static void* chunk_malloc_realloc(struct chunk_allocator* , void* block, size_t old_size, size_t new_size) { return realloc(block, new_size); } /**********************************************************************************/ void* default_chunk_realloc(struct chunk_allocator* ca, void* ptr, size_t old_size, size_t new_size) { void* q = ca->chunk_alloc(ca, new_size); assert(old_size > 0); assert(new_size > 0); if (NULL == q) return NULL; memcpy(q, ptr, old_size < new_size ? old_size : new_size); ca->chunk_free(ca, ptr, old_size); return q; } static void mpool_chunk_init(struct mpool_cell* cell, size_t cell_count, size_t cell_size) { size_t i; struct mpool_cell* p = cell; assert(cell_size % MPOOL_MIN_CELL == 0); for (i = 0; i < cell_count-1; ++i) p = p->next = (struct mpool_cell*)((char*)p + cell_size); p->next = NULL; } /**********************************************************************************/ static struct chunk_allocator fal = { &chunk_malloc_alloc, &chunk_malloc_realloc, &chunk_malloc_free }; /**********************************************************************************/ /** * require initialized fields: * cell_size * chunk_size * ca [0 OR initialized] */ void fixed_mpool_init(struct fixed_mpool* mpf) { struct chunk_allocator* al; if (NULL == mpf->ca) al = mpf->ca = &fal; else { al = mpf->ca; assert(NULL != al->chunk_alloc); assert(NULL != al->chunk_free); if (NULL == al->chunk_realloc) al->chunk_realloc = &default_chunk_realloc; } assert(mpf->chunk_size > 0); assert(mpf->cell_size > 0); assert(mpf->cell_size < mpf->chunk_size); mpf->cell_size = (mpf->cell_size + MPOOL_MIN_CELL - 1) / MPOOL_MIN_CELL * MPOOL_MIN_CELL; mpf->chunk_size = (mpf->chunk_size + MPOOL_MIN_CHUNK - 1) / MPOOL_MIN_CHUNK * MPOOL_MIN_CHUNK; mpf->head = NULL; if (mpf->nChunks < MPOOL_MIN_CHUNK/sizeof(struct mpool_chunk)) mpf->nChunks = MPOOL_MIN_CHUNK/sizeof(struct mpool_chunk); mpf->iNextChunk = 0; mpf->pChunks = (struct mpool_chunk*) al->chunk_alloc(al, sizeof(struct mpool_chunk) * mpf->nChunks); if (NULL == mpf->pChunks) { fprintf(stderr , "fatal: febird.fixed_mpool_init failed, chunk[size=%zd, count=%zd]/n" , mpf->chunk_size, mpf->nChunks); abort(); } mpf->used_cells = 0; } void fixed_mpool_destroy(struct fixed_mpool* mpf) { struct chunk_allocator* ca = mpf->ca; long i; for (i = mpf->iNextChunk - 1; i >= 0; --i) ca->chunk_free(ca, mpf->pChunks[i].cell, mpf->pChunks[i].size); ca->chunk_free(ca, mpf->pChunks, sizeof(struct mpool_chunk) * mpf->nChunks); } // 0 success, -1 fail int fixed_mpool_add_chunk(struct fixed_mpool* mpf) { struct mpool_cell* cell; assert(mpf->pChunks != NULL); if (mpf->iNextChunk == mpf->nChunks) { size_t old_size = sizeof(struct mpool_chunk) * mpf->nChunks; size_t new_size = 2 * old_size; // allocate new chunk array struct mpool_chunk* c = (struct mpool_chunk*) mpf->ca->chunk_realloc(mpf->ca, mpf->pChunks, old_size, new_size); if (NULL == c) return -1; mpf->pChunks = c; mpf->nChunks *= 2; // chunk array expanded 2 mpf->chunk_size *= 2; // chunk_size expanded 2 also } // allocate a new cell array cell = (struct mpool_cell*)mpf->ca->chunk_alloc(mpf->ca, mpf->chunk_size); if (NULL == cell) return -1; mpf->pChunks[mpf->iNextChunk].cell = cell; mpf->pChunks[mpf->iNextChunk].size = mpf->chunk_size; mpf->iNextChunk++; mpool_chunk_init(cell, mpf->chunk_size / mpf->cell_size, mpf->cell_size); mpf->head = cell; return 0; } void* fixed_mpool_alloc(struct fixed_mpool* mpf) { struct mpool_cell* cell; if (NULL == mpf->head) { // in most case it will not run this path if (fixed_mpool_add_chunk(mpf) != 0) return NULL; } cell = mpf->head; mpf->used_cells++; mpf->head = mpf->head->next; return cell; } void fixed_mpool_free(struct fixed_mpool* mpf, void* ptr) { struct mpool_cell* cell = (struct mpool_cell*)ptr; cell->next = mpf->head; mpf->used_cells--; mpf->head = cell; } /**********************************************************************************/ /** * require initialized fields: * max_cell_size * chunk_size * ca [0 OR initialized] */ void mpool_init(struct mpool* mp) { int i, nFixed; struct chunk_allocator* al; assert(mp->max_cell_size < mp->chunk_size); if (NULL == mp->chunk_alloc) al = mp->ca = &fal; else { al = mp->ca; assert(NULL != al->chunk_alloc); assert(NULL != al->chunk_free); if (NULL == al->chunk_realloc) al->chunk_realloc = &default_chunk_realloc; } mp->chunk_alloc = (chunk_alloc_ft)&mpool_alloc; mp->chunk_free = (chunk_free_ft)&mpool_free; mp->chunk_realloc = (chunk_realloc_ft)&default_chunk_realloc; mp->max_cell_size = (mp->max_cell_size + MPOOL_MIN_CELL - 1) / MPOOL_MIN_CELL * MPOOL_MIN_CELL; mp->chunk_size = (mp->chunk_size + MPOOL_MIN_CHUNK - 1) / MPOOL_MIN_CHUNK * MPOOL_MIN_CHUNK; nFixed = mp->max_cell_size / MPOOL_MIN_CELL; mp->fixed = (struct fixed_mpool*)al->chunk_alloc(al, sizeof(struct fixed_mpool) * nFixed); if (NULL == mp->fixed) { fprintf(stderr, "fatal: febird.mpool_init[max_cell_size=%zd, chunk_size=%zd]/n" , mp->max_cell_size, mp->chunk_size); abort(); } for (i = 0; i < nFixed; ++i) { mp->fixed[i].cell_size = (i + 1) * MPOOL_MIN_CELL; mp->fixed[i].chunk_size = mp->chunk_size; mp->fixed[i].nChunks = 16; mp->fixed[i].ca = mp->ca; fixed_mpool_init(&mp->fixed[i]); } #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK mp->big_blocks = 0; mp->big_list.prev = mp->big_list.next = &mp->big_list; #endif } void mpool_destroy(struct mpool* mp) { size_t i, nFixed; #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK struct big_block_header *p; for (i = 0, p = mp->big_list.next; p != &mp->big_list; ++i) { struct big_block_header *q; if (i > mp->big_blocks) { fprintf(stderr, "fatal: febird.mpool_destroy/n"); abort(); } q = p->next; free(p); p = q; } assert(i == mp->big_blocks); #endif nFixed = mp->max_cell_size / MPOOL_MIN_CELL; for (i = 0; i < nFixed; ++i) { fixed_mpool_destroy(&mp->fixed[i]); } mp->ca->chunk_free(mp->ca, mp->fixed, sizeof(struct fixed_mpool) * nFixed); } void* mpool_alloc(struct mpool* mp, size_t size) { size_t idx; struct fixed_mpool* mpf; struct mpool_cell* cell; #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK if (size > mp->max_cell_size) { // this is rare case struct big_block_header *p, *h; p = (struct big_block_header*)malloc(sizeof(struct big_block_header) + size); if (p) { h = &mp->big_list; p->prev = h; p->next = h->next; h->next->prev = p; h->next = p; mp->big_blocks++; return (p + 1); } else return NULL; } #else assert(size <= mp->max_cell_size); #endif assert(size > 0); idx = (size - 1) / MPOOL_MIN_CELL; mpf = &mp->fixed[idx]; // same as fixed_mpool_alloc.... if (NULL == mpf->head) { // in most case it will not run this path if (fixed_mpool_add_chunk(mpf) != 0) return NULL; } cell = mpf->head; mpf->used_cells++; mpf->head = mpf->head->next; return cell; } void mpool_free(struct mpool* mp, void* ptr, size_t size) { size_t idx; struct fixed_mpool* mpf; struct mpool_cell* cell; #ifdef FEBIRD_MPOOL_ALLOW_BIG_BLOCK if (size > mp->max_cell_size) { // this is rare case struct big_block_header* bbh = (struct big_block_header*)ptr - 1; bbh->prev->next = bbh->next; bbh->next->prev = bbh->prev; free(bbh); mp->big_blocks--; return; } #else assert(size <= mp->max_cell_size); #endif assert(size > 0); idx = (size - 1) / MPOOL_MIN_CELL; mpf = &mp->fixed[idx]; // same as fixed_mpool_free... cell = (struct mpool_cell*)ptr; cell->next = mpf->head; mpf->used_cells--; mpf->head = cell; } size_t mpool_used_cells(const struct mpool* mp) { size_t i, n = mp->max_cell_size / MPOOL_MIN_CELL; size_t used = 0; for (i = 0; i < n; ++i) used += mp->fixed[i].used_cells; return used; } size_t mpool_used_bytes(const struct mpool* mp) { size_t i, n = mp->max_cell_size / MPOOL_MIN_CELL; size_t used = 0; for (i = 0; i < n; ++i) used += mp->fixed[i].cell_size * mp->fixed[i].used_cells; return used; } |
memory pool 的高效实现
memory pool
malloc可以分配任意大小的内存，因此，在malloc内部，保存了一些簿记信息（至少有一个包含内存块尺寸的信息）。调用free时，可以正确释放。
为了减少这些簿记开销，可以使用memory pool。
根据使用情境，可以分为两种：
1. 只分配固定大小的内存块，速度最快（normal path约10条机器指令）。
2. 可分配不同大小的内存块，速度稍慢，但比malloc快得多，也无簿记开销。
以下将分别说明
mpool
mpool可分配不同尺寸的内存。大多数时刻，都在内部分配。
销毁mpool时，会自动释放在mpool中未释放的内存。
mpool内部有一个包含多个不同尺寸fixed_mpool的array，根据请求分配的内存大小，直接索引到相应的fixed_mpool来分配一个单元（cell）。
通过定义宏FEBIRD_MPOOL_ALLOW_BIG_BLOCK，就允许大于max_cell_size的内存分配。在这种情况下，使用标准的malloc分配内存，分配出去的内存有额外簿记（用双向链表串起来），以便在销毁mpool时自动释放。
fixed_mpool
尺寸固定的内存池，一旦创建，该内存池只能分配固定尺寸的内存单元（cell）。这在很多情况下都适用，例如链表结点、树节点、图结点、自定义的结构、等等。
用于stl的map/set/list再适合不过了——但是不能用于vector/deque等需要分配可变尺寸的容器。
fixed_mpool内部的多个chunk使用数组，类似std::vector，iNextChunk相当于vector.size，nChunks相当于vector.capacity，每次空间不够时扩张一倍。使用数组，而不是链表，有以下好处：
1. 有助于对齐——如果chunk_allocator是对齐（对齐>=32时）分配的，而chunk使用链表组织，就会在chunk开始处预留一个chunk头部，这会导致不对齐。
2. 如果cell_size也刚好较大且整除chunk_size，使用链表就会浪费将近一个cell（cell_size – chunk_header_size）。
3. 如果不把连接信息保存在chunk header，就需要另外分配chunk结点，而分配chunk结点又需要其它内存分配函数。
空闲表使用单链表，因此，理论上每个cell最小必须能容纳一个指针，32位系统式4字节，64位系统式8字节，实现中使用8字节作为最小值。
世界上应用最广泛的虚拟机是啥？
别说是JavaVM！
正确答案：x86vm
x86本身是一个硬件vm，它的指令系统是一个vm指令系统，通过翻译层后，才交给下面的risk内核。
malloc/free 的开销，如何去掉这种开销？
一般的malloc实现，对一块已分配的内存，都有两个机器字的簿记，甚至更多。如果不需要排错，理论上讲，只需要一个字长的额外开销，用来记录这块内存的尺寸（放在intptr[-1]处是个好主意）。
为什么需要这个开销呢？因为free传入的只是个指针，它不知道要释放多大的内存，因此free内部必须通过某种方式来获得这块内存的尺寸。
可以想象，如果用 malloc/free 来作为一个关联数组（map）的分配器，要浪费不少内存。不过好在实际数据的尺寸往往比额外消耗要大很多，相比起来，浪费的比例不算很大，况且现在内存还很便宜。
其实，打造一个高效的分配器并不难，难的是它的适用范围（多线程？cell尺寸，chunk尺寸，对齐，排错…），如果可以忍受这些缺陷，或者说是限制，还是比较值得的。下一步就是它的灵活性——让它可以更加容易集成进其它系统。
对于C标准库，如果能增加一个/一族这样的分配器，还是很有价值的。从理论上讲，只要free时多传一个size参数，就可以完全去掉额外的开销。这样两个函数就可以做到：
|
1 2 |
void* salloc(size_t size); void sfree(void* ptr, size_t size); |
这样做还有一个额外的好处，就是可以更好地对齐，假定程序需要按32字节对齐，malloc/free 就至少需要32字节做簿记，如果再加上内存越界检测，就需要64字节。salloc/sfree则只需要将分配的内存对齐到32字节边界即可。
但是这对程序的正确性要求很高，malloc/free中，内存越界检测可以很容易实现，而salloc/sfree就完全做不到（除非增加额外簿记）。一个好主意是可以在debug版中加入这些差错功能，而在release版中去掉。
更好（确切地讲应该是更灵活）的方案是，实现一个
|
1 2 3 4 5 6 7 8 9 |
struct mpool{ // ..... }; // return success or fail int mpool_init(struct mpool* pool); void mpool_destroy(struct mpool* pool); void* mpalloc(struct mpool* pool, size_t size); void mpfree(struct mpool* pool, void* ptr, size_t size); |
而让 salloc/sfree简单地作为 mpool 的包装。
gcc的std::allocator基本上是按这样的方式实现的，只不过，它的size参数，大多数时刻是自动传递的（知道具体的class/struct，也就知道它的尺寸）。实现方式上，使用 size_aligned/align 作为索引去访问特定尺寸的mempool，一个 mempool 是多个链表串起来的大chunk，每个chunk内部是链表穿起来的cell。这也许是最好的实现方式了，除了节省的额外空间开销，时间开销上，如果不考虑加锁，一次alloc平均可以在10时钟周期内完成，dealloc用的时间更短。相比之下malloc/free耗的时间也要多得多。