| 1 |
|
| #ifndef HAMT_POOL_H |
| 2 |
|
| #define HAMT_POOL_H |
| 3 |
|
| |
| 4 |
|
| /* Freed blocks kept by size, so the next allocation of that size is a pop |
| 5 |
|
| * and not a trip to the C library. An update frees about as many small |
| 6 |
|
| * blocks as it allocates, of the same few sizes, which is the case this is |
| 7 |
|
| * for. |
| 8 |
|
| * |
| 9 |
|
| * Sizes are rounded up to a multiple of sixteen bytes and each multiple has |
| 10 |
|
| * a list, linked through the first word of every free block. A list holds a |
| 11 |
|
| * fixed number of blocks at most, so a large structure being freed goes back |
| 12 |
|
| * to the C library and is not pinned here. A block too large for any list is |
| 13 |
|
| * allocated and freed directly. |
| 14 |
|
| * |
| 15 |
|
| * A pool is used by one thread. Nothing here locks. |
| 16 |
|
| * |
| 17 |
|
| * The caller must free a block with the size it allocated it with: that is |
| 18 |
|
| * how the block finds its list. */ |
| 19 |
|
| |
| 20 |
|
| #ifndef HAMT_POOL_RAW_ALLOC |
| 21 |
|
| # define HAMT_POOL_RAW_ALLOC(bytes) malloc(bytes) |
| 22 |
|
| # define HAMT_POOL_RAW_FREE(p, bytes) free(p) |
| 23 |
|
| #endif |
| 24 |
|
| |
| 25 |
|
| #define HAMT_POOL_GRAIN 16 |
| 26 |
|
| #define HAMT_POOL_CLASSES 20 /* lists for 16, 32, ... 304 bytes */ |
| 27 |
|
| #ifndef HAMT_POOL_KEEP |
| 28 |
|
| # define HAMT_POOL_KEEP 128 /* blocks a list holds at most */ |
| 29 |
|
| #endif |
| 30 |
|
| |
| 31 |
|
| typedef struct hamt_pool { |
| 32 |
|
| int open; |
| 33 |
|
| uint32_t n[HAMT_POOL_CLASSES]; |
| 34 |
|
| void *head[HAMT_POOL_CLASSES]; |
| 35 |
|
| } hamt_pool; |
| 36 |
|
| |
| 37 |
|
| #define HAMT_POOL_CLASS(bytes) (((size_t)(bytes) + HAMT_POOL_GRAIN - 1) / HAMT_POOL_GRAIN) |
| 38 |
|
| |
| 39 |
29 |
| static void hamt_pool_open(hamt_pool *pl) { |
| 40 |
29 |
| memset(pl, 0, sizeof(*pl)); |
| 41 |
29 |
| pl->open = 1; |
| 42 |
29 |
| } |
| 43 |
|
| |
| 44 |
|
| /* `pl` may be NULL, for a caller that has no pool to use: the block is then |
| 45 |
|
| * allocated as a pooled one would be, so it may be freed into any pool. */ |
| 46 |
3191957 |
| static void *hamt_pool_alloc(hamt_pool *pl, size_t bytes) { |
| 47 |
3191957 |
| size_t c = HAMT_POOL_CLASS(bytes); |
| 48 |
|
| |
| 49 |
3191957 |
▶ | if (c == 0 || c >= HAMT_POOL_CLASSES) return HAMT_POOL_RAW_ALLOC(bytes); |
Branch: 2 branches
| Branch | True | False | Total |
| if (c == 0 || c >= HAMT_POOL_CLASSES) return HAMT_POOL_RAW_ALLOC(bytes); |
3191957 |
0 |
3191957 |
| if (c == 0 || c >= HAMT_POOL_CLASSES) return HAMT_POOL_RAW_ALLOC(bytes); |
8390 |
3183567 |
3191957 |
|
| 50 |
3183567 |
▶ | if (pl && pl->head[c]) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (pl && pl->head[c]) { |
3183567 |
0 |
3183567 |
| if (pl && pl->head[c]) { |
1651354 |
1532213 |
3183567 |
|
| 51 |
1651354 |
| void *p = pl->head[c]; |
| 52 |
1651354 |
| memcpy(&pl->head[c], p, sizeof(void *)); |
| 53 |
1651354 |
| pl->n[c]--; |
| 54 |
1651354 |
| return p; |
| 55 |
|
| } |
| 56 |
1532213 |
| return HAMT_POOL_RAW_ALLOC(c * HAMT_POOL_GRAIN); |
| 57 |
|
| } |
| 58 |
|
| |
| 59 |
3191957 |
| static void hamt_pool_free(hamt_pool *pl, void *p, size_t bytes) { |
| 60 |
3191957 |
| size_t c = HAMT_POOL_CLASS(bytes); |
| 61 |
|
| |
| 62 |
3191957 |
▶ | if (c == 0 || c >= HAMT_POOL_CLASSES) { HAMT_POOL_RAW_FREE(p, bytes); return; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (c == 0 || c >= HAMT_POOL_CLASSES) { HAMT_POOL_RAW_FREE(p, bytes); return; } |
3191957 |
0 |
3191957 |
| if (c == 0 || c >= HAMT_POOL_CLASSES) { HAMT_POOL_RAW_FREE(p, bytes); return; } |
8390 |
3183567 |
3191957 |
|
| 63 |
3183567 |
▶ | if (pl && pl->open && pl->n[c] < HAMT_POOL_KEEP) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (pl && pl->open && pl->n[c] < HAMT_POOL_KEEP) { |
3183567 |
0 |
3183567 |
| if (pl && pl->open && pl->n[c] < HAMT_POOL_KEEP) { |
3183567 |
0 |
3183567 |
| if (pl && pl->open && pl->n[c] < HAMT_POOL_KEEP) { |
1661025 |
1522542 |
3183567 |
|
| 64 |
1661025 |
| memcpy(p, &pl->head[c], sizeof(void *)); |
| 65 |
1661025 |
| pl->head[c] = p; |
| 66 |
1661025 |
| pl->n[c]++; |
| 67 |
1661025 |
| return; |
| 68 |
|
| } |
| 69 |
1522542 |
| HAMT_POOL_RAW_FREE(p, c * HAMT_POOL_GRAIN); |
| 70 |
|
| } |
| 71 |
|
| |
| 72 |
|
| /* Give everything back and keep nothing from here on. Blocks handed out |
| 73 |
|
| * before this are still freed through hamt_pool_free. */ |
| 74 |
29 |
| static void hamt_pool_close(hamt_pool *pl) { |
| 75 |
|
| size_t c; |
| 76 |
29 |
| pl->open = 0; |
| 77 |
609 |
▶ | for (c = 0; c < HAMT_POOL_CLASSES; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < HAMT_POOL_CLASSES; c++) { |
580 |
29 |
609 |
|
| 78 |
10251 |
▶ | while (pl->head[c]) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (pl->head[c]) { |
9671 |
580 |
10251 |
|
| 79 |
9671 |
| void *p = pl->head[c]; |
| 80 |
9671 |
| memcpy(&pl->head[c], p, sizeof(void *)); |
| 81 |
9671 |
| HAMT_POOL_RAW_FREE(p, c * HAMT_POOL_GRAIN); |
| 82 |
|
| } |
| 83 |
580 |
| pl->n[c] = 0; |
| 84 |
|
| } |
| 85 |
29 |
| } |
| 86 |
|
| |
| 87 |
|
| /* Blocks waiting in the lists. */ |
| 88 |
20005 |
| static size_t hamt_pool_held(const hamt_pool *pl) { |
| 89 |
20005 |
| size_t c, n = 0; |
| 90 |
420105 |
▶ | for (c = 0; c < HAMT_POOL_CLASSES; c++) n += pl->n[c]; |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < HAMT_POOL_CLASSES; c++) n += pl->n[c]; |
400100 |
20005 |
420105 |
|
| 91 |
20005 |
| return n; |
| 92 |
|
| } |
| 93 |
|
| |
| 94 |
|
| #endif |