include/hamt/hamt_pool.h

filter: Statementstmt 100% 35 / 35 Branchbran 79.1% 19 / 24 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 91.5% 54 / 59 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_node.h ↑ Summary include/hamt/hamt_entry.h »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (c = 0; c < HAMT_POOL_CLASSES; c++) { 580 29 609
78 10251 ▶ while (pl->head[c]) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (c = 0; c < HAMT_POOL_CLASSES; c++) n += pl->n[c]; 400100 20005 420105
91 20005 return n;
92 }
93  
94 #endif
« include/hamt/hamt_node.h ↑ Summary include/hamt/hamt_entry.h »