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
|
#define _BSD_SOURCE
#include <stdlib.h>
#include <sys/mman.h>
#include "meta.h"
struct mapinfo {
void *base;
size_t len;
};
static struct mapinfo nontrivial_free(struct meta *, int);
static struct mapinfo free_group(struct meta *g)
{
struct mapinfo mi = { 0 };
int sc = g->sizeclass;
if (sc < 48) {
ctx.usage_by_class[sc] -= g->last_idx+1;
}
if (g->maplen) {
step_seq();
record_seq(sc);
mi.base = g->mem;
mi.len = g->maplen*4096UL;
} else {
void *p = g->mem;
struct meta *m = get_meta(p);
int idx = get_slot_index(p);
g->mem->meta = 0;
// not checking size/reserved here; it's intentionally invalid
mi = nontrivial_free(m, idx);
}
free_meta(g);
return mi;
}
static int okay_to_free(struct meta *g)
{
int sc = g->sizeclass;
if (!g->freeable) return 0;
// always free individual mmaps not suitable for reuse
if (sc >= 48 || get_stride(g) < UNIT*size_classes[sc])
return 1;
// always free groups allocated inside another group's slot
// since recreating them should not be expensive and they
// might be blocking freeing of a much larger group.
if (!g->maplen) return 1;
// if there is another non-full group, free this one to
// consolidate future allocations, reduce fragmentation.
if (g->next != g) return 1;
// free any group in a size class that's not bouncing
if (!is_bouncing(sc)) return 1;
size_t cnt = g->last_idx+1;
size_t usage = ctx.usage_by_class[sc];
// if usage is high enough that a larger count should be
// used, free the low-count group so a new one will be made.
if (9*cnt <= usage && cnt < 20)
return 1;
// otherwise, keep the last group in a bouncing class.
return 0;
}
static struct mapinfo nontrivial_free(struct meta *g, int i)
{
uint32_t self = 1u<<i;
int sc = g->sizeclass;
uint32_t mask = g->freed_mask | g->avail_mask;
if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
// any multi-slot group is necessarily on an active list
// here, but single-slot groups might or might not be.
if (g->next) {
assert(sc < 48);
int activate_new = (ctx.active[sc]==g);
dequeue(&ctx.active[sc], g);
if (activate_new && ctx.active[sc])
activate_group(ctx.active[sc]);
}
return free_group(g);
} else if (!mask) {
assert(sc < 48);
// might still be active if there were no allocations
// after last available slot was taken.
if (ctx.active[sc] != g) {
queue(&ctx.active[sc], g);
}
}
a_or(&g->freed_mask, self);
return (struct mapinfo){ 0 };
}
void free(void *p)
{
if (!p) return;
struct meta *g = get_meta(p);
int idx = get_slot_index(p);
size_t stride = get_stride(g);
unsigned char *start = g->mem->storage + stride*idx;
unsigned char *end = start + stride - IB;
get_nominal_size(p, end);
uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;
((unsigned char *)p)[-3] = 255;
// invalidate offset to group header, and cycle offset of
// used region within slot if current offset is zero.
*(uint16_t *)((char *)p-2) = 0;
// release any whole pages contained in the slot to be freed
// unless it's a single-slot group that will be unmapped.
if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) {
unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1));
size_t len = (end-base) & -PGSZ;
if (len && USE_MADV_FREE) {
int e = errno;
madvise(base, len, MADV_FREE);
errno = e;
}
}
// atomic free without locking if this is neither first or last slot
for (;;) {
uint32_t freed = g->freed_mask;
uint32_t avail = g->avail_mask;
uint32_t mask = freed | avail;
assert(!(mask&self));
if (!freed || mask+self==all) break;
if (!MT)
g->freed_mask = freed+self;
else if (a_cas(&g->freed_mask, freed, freed+self)!=freed)
continue;
return;
}
wrlock();
struct mapinfo mi = nontrivial_free(g, idx);
unlock();
if (mi.len) {
int e = errno;
munmap(mi.base, mi.len);
errno = e;
}
}
|
