1 files changed, 143 insertions, 0 deletions
diff --git a/src/malloc/mallocng/free.c b/src/malloc/mallocng/free.c
new file mode 100644
index 00000000..40745f97
--- /dev/null
+++ b/src/malloc/mallocng/free.c
@@ -0,0 +1,143 @@
+#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);
+}