144 lines
3.7 KiB
C
144 lines
3.7 KiB
C
#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) madvise(base, len, MADV_FREE);
|
|
}
|
|
|
|
// 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) munmap(mi.base, mi.len);
|
|
}
|