master
1#define _BSD_SOURCE
2#include <stdlib.h>
3#include <sys/mman.h>
4
5#include "meta.h"
6
7struct mapinfo {
8 void *base;
9 size_t len;
10};
11
12static struct mapinfo nontrivial_free(struct meta *, int);
13
14static struct mapinfo free_group(struct meta *g)
15{
16 struct mapinfo mi = { 0 };
17 int sc = g->sizeclass;
18 if (sc < 48) {
19 ctx.usage_by_class[sc] -= g->last_idx+1;
20 }
21 if (g->maplen) {
22 step_seq();
23 record_seq(sc);
24 mi.base = g->mem;
25 mi.len = g->maplen*4096UL;
26 } else {
27 void *p = g->mem;
28 struct meta *m = get_meta(p);
29 int idx = get_slot_index(p);
30 g->mem->meta = 0;
31 // not checking size/reserved here; it's intentionally invalid
32 mi = nontrivial_free(m, idx);
33 }
34 free_meta(g);
35 return mi;
36}
37
38static int okay_to_free(struct meta *g)
39{
40 int sc = g->sizeclass;
41
42 if (!g->freeable) return 0;
43
44 // always free individual mmaps not suitable for reuse
45 if (sc >= 48 || get_stride(g) < UNIT*size_classes[sc])
46 return 1;
47
48 // always free groups allocated inside another group's slot
49 // since recreating them should not be expensive and they
50 // might be blocking freeing of a much larger group.
51 if (!g->maplen) return 1;
52
53 // if there is another non-full group, free this one to
54 // consolidate future allocations, reduce fragmentation.
55 if (g->next != g) return 1;
56
57 // free any group in a size class that's not bouncing
58 if (!is_bouncing(sc)) return 1;
59
60 size_t cnt = g->last_idx+1;
61 size_t usage = ctx.usage_by_class[sc];
62
63 // if usage is high enough that a larger count should be
64 // used, free the low-count group so a new one will be made.
65 if (9*cnt <= usage && cnt < 20)
66 return 1;
67
68 // otherwise, keep the last group in a bouncing class.
69 return 0;
70}
71
72static struct mapinfo nontrivial_free(struct meta *g, int i)
73{
74 uint32_t self = 1u<<i;
75 int sc = g->sizeclass;
76 uint32_t mask = g->freed_mask | g->avail_mask;
77
78 if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
79 // any multi-slot group is necessarily on an active list
80 // here, but single-slot groups might or might not be.
81 if (g->next) {
82 assert(sc < 48);
83 int activate_new = (ctx.active[sc]==g);
84 dequeue(&ctx.active[sc], g);
85 if (activate_new && ctx.active[sc])
86 activate_group(ctx.active[sc]);
87 }
88 return free_group(g);
89 } else if (!mask) {
90 assert(sc < 48);
91 // might still be active if there were no allocations
92 // after last available slot was taken.
93 if (ctx.active[sc] != g) {
94 queue(&ctx.active[sc], g);
95 }
96 }
97 a_or(&g->freed_mask, self);
98 return (struct mapinfo){ 0 };
99}
100
101void free(void *p)
102{
103 if (!p) return;
104
105 struct meta *g = get_meta(p);
106 int idx = get_slot_index(p);
107 size_t stride = get_stride(g);
108 unsigned char *start = g->mem->storage + stride*idx;
109 unsigned char *end = start + stride - IB;
110 get_nominal_size(p, end);
111 uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;
112 ((unsigned char *)p)[-3] = 255;
113 // invalidate offset to group header, and cycle offset of
114 // used region within slot if current offset is zero.
115 *(uint16_t *)((char *)p-2) = 0;
116
117 // release any whole pages contained in the slot to be freed
118 // unless it's a single-slot group that will be unmapped.
119 if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) {
120 unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1));
121 size_t len = (end-base) & -PGSZ;
122 if (len && USE_MADV_FREE) {
123 int e = errno;
124 madvise(base, len, MADV_FREE);
125 errno = e;
126 }
127 }
128
129 // atomic free without locking if this is neither first or last slot
130 for (;;) {
131 uint32_t freed = g->freed_mask;
132 uint32_t avail = g->avail_mask;
133 uint32_t mask = freed | avail;
134 assert(!(mask&self));
135 if (!freed || mask+self==all) break;
136 if (!MT)
137 g->freed_mask = freed+self;
138 else if (a_cas(&g->freed_mask, freed, freed+self)!=freed)
139 continue;
140 return;
141 }
142
143 wrlock();
144 struct mapinfo mi = nontrivial_free(g, idx);
145 unlock();
146 if (mi.len) {
147 int e = errno;
148 munmap(mi.base, mi.len);
149 errno = e;
150 }
151}