import mallocng

the files added come from the mallocng development repo, commit
2ed58817cca5bc055974e5a0e43c280d106e696b. they comprise a new malloc
implementation, developed over the past 9 months, to replace the old
allocator (since dubbed "oldmalloc") with one that retains low code
size and minimal baseline memory overhead while avoiding fundamental
flaws in oldmalloc and making significant enhancements. these include
highly controlled fragmentation, fine-grained ability to return memory
to the system when freed, and strong hardening against dynamic memory
usage errors by the caller.

internally, mallocng derives most of these properties from tightly
structuring memory, creating space for allocations as uniform-sized
slots within individually mmapped (and individually freeable)
allocation groups. smaller-than-pagesize groups are created within
slots of larger ones. minimal group size is very small, and larger
sizes (in geometric progression) only come into play when usage is
high.

all data necessary for maintaining consistency of the allocator state
is tracked in out-of-band metadata, reachable via a validated path
from minimal in-band metadata. all pointers passed (to free, etc.) are
validated before any stores to memory take place. early reuse of freed
slots is avoided via approximate LRU order of freed slots. further
hardening against use-after-free and double-free, even in the case
where the freed slot has been reused, is made by cycling the offset
within the slot at which the allocation is placed; this is possible
whenever the slot size is larger than the requested allocation.

1 files changed, 288 insertions, 0 deletions

diff --git a/src/malloc/mallocng/meta.h b/src/malloc/mallocng/meta.h
new file mode 100644
index 00000000..61ec53f9
--- /dev/null
+++ b/src/malloc/mallocng/meta.h
@@ -0,0 +1,288 @@
+#ifndef MALLOC_META_H
+#define MALLOC_META_H
+
+#include <stdint.h>
+#include <errno.h>
+#include <limits.h>
+#include "glue.h"
+
+__attribute__((__visibility__("hidden")))
+extern const uint16_t size_classes[];
+
+#define MMAP_THRESHOLD 131052
+
+#define UNIT 16
+#define IB 4
+
+struct group {
+	struct meta *meta;
+	unsigned char active_idx:5;
+	char pad[UNIT - sizeof(struct meta *) - 1];
+	unsigned char storage[];
+};
+
+struct meta {
+	struct meta *prev, *next;
+	struct group *mem;
+	volatile int avail_mask, freed_mask;
+	uintptr_t last_idx:5;
+	uintptr_t freeable:1;
+	uintptr_t sizeclass:6;
+	uintptr_t maplen:8*sizeof(uintptr_t)-12;
+};
+
+struct meta_area {
+	uint64_t check;
+	struct meta_area *next;
+	int nslots;
+	struct meta slots[];
+};
+
+struct malloc_context {
+	uint64_t secret;
+#ifndef PAGESIZE
+	size_t pagesize;
+#endif
+	int init_done;
+	unsigned mmap_counter;
+	struct meta *free_meta_head;
+	struct meta *avail_meta;
+	size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;
+	struct meta_area *meta_area_head, *meta_area_tail;
+	unsigned char *avail_meta_areas;
+	struct meta *active[48];
+	size_t usage_by_class[48];
+	uint8_t unmap_seq[32], bounces[32];
+	uint8_t seq;
+	uintptr_t brk;
+};
+
+__attribute__((__visibility__("hidden")))
+extern struct malloc_context ctx;
+
+#ifdef PAGESIZE
+#define PGSZ PAGESIZE
+#else
+#define PGSZ ctx.pagesize
+#endif
+
+__attribute__((__visibility__("hidden")))
+struct meta *alloc_meta(void);
+
+__attribute__((__visibility__("hidden")))
+int is_allzero(void *);
+
+static inline void queue(struct meta **phead, struct meta *m)
+{
+	assert(!m->next);
+	assert(!m->prev);
+	if (*phead) {
+		struct meta *head = *phead;
+		m->next = head;
+		m->prev = head->prev;
+		m->next->prev = m->prev->next = m;
+	} else {
+		m->prev = m->next = m;
+		*phead = m;
+	}
+}
+
+static inline void dequeue(struct meta **phead, struct meta *m)
+{
+	if (m->next != m) {
+		m->prev->next = m->next;
+		m->next->prev = m->prev;
+		if (*phead == m) *phead = m->next;
+	} else {
+		*phead = 0;
+	}
+	m->prev = m->next = 0;
+}
+
+static inline struct meta *dequeue_head(struct meta **phead)
+{
+	struct meta *m = *phead;
+	if (m) dequeue(phead, m);
+	return m;
+}
+
+static inline void free_meta(struct meta *m)
+{
+	*m = (struct meta){0};
+	queue(&ctx.free_meta_head, m);
+}
+
+static inline uint32_t activate_group(struct meta *m)
+{
+	assert(!m->avail_mask);
+	uint32_t mask, act = (2u<<m->mem->active_idx)-1;
+	do mask = m->freed_mask;
+	while (a_cas(&m->freed_mask, mask, mask&~act)!=mask);
+	return m->avail_mask = mask & act;
+}
+
+static inline int get_slot_index(const unsigned char *p)
+{
+	return p[-3] & 31;
+}
+
+static inline struct meta *get_meta(const unsigned char *p)
+{
+	assert(!((uintptr_t)p & 15));
+	int offset = *(const uint16_t *)(p - 2);
+	int index = get_slot_index(p);
+	if (p[-4]) {
+		assert(!offset);
+		offset = *(uint32_t *)(p - 8);
+		assert(offset > 0xffff);
+	}
+	const struct group *base = (const void *)(p - UNIT*offset - UNIT);
+	const struct meta *meta = base->meta;
+	assert(meta->mem == base);
+	assert(index <= meta->last_idx);
+	assert(!(meta->avail_mask & (1u<<index)));
+	assert(!(meta->freed_mask & (1u<<index)));
+	const struct meta_area *area = (void *)((uintptr_t)meta & -4096);
+	assert(area->check == ctx.secret);
+	if (meta->sizeclass < 48) {
+		assert(offset >= size_classes[meta->sizeclass]*index);
+		assert(offset < size_classes[meta->sizeclass]*(index+1));
+	} else {
+		assert(meta->sizeclass == 63);
+	}
+	if (meta->maplen) {
+		assert(offset <= meta->maplen*4096UL/UNIT - 1);
+	}
+	return (struct meta *)meta;
+}
+
+static inline size_t get_nominal_size(const unsigned char *p, const unsigned char *end)
+{
+	size_t reserved = p[-3] >> 5;
+	if (reserved >= 5) {
+		assert(reserved == 5);
+		reserved = *(const uint32_t *)(end-4);
+		assert(reserved >= 5);
+		assert(!end[-5]);
+	}
+	assert(reserved <= end-p);
+	assert(!*(end-reserved));
+	// also check the slot's overflow byte
+	assert(!*end);
+	return end-reserved-p;
+}
+
+static inline size_t get_stride(const struct meta *g)
+{
+	if (!g->last_idx && g->maplen) {
+		return g->maplen*4096UL - UNIT;
+	} else {
+		return UNIT*size_classes[g->sizeclass];
+	}
+}
+
+static inline void set_size(unsigned char *p, unsigned char *end, size_t n)
+{
+	int reserved = end-p-n;
+	if (reserved) end[-reserved] = 0;
+	if (reserved >= 5) {
+		*(uint32_t *)(end-4) = reserved;
+		end[-5] = 0;
+		reserved = 5;
+	}
+	p[-3] = (p[-3]&31) + (reserved<<5);
+}
+
+static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
+{
+	size_t stride = get_stride(g);
+	size_t slack = (stride-IB-n)/UNIT;
+	unsigned char *p = g->mem->storage + stride*idx;
+	unsigned char *end = p+stride-IB;
+	// cycle offset within slot to increase interval to address
+	// reuse, facilitate trapping double-free.
+	int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
+	assert(!p[-4]);
+	if (off > slack) {
+		size_t m = slack;
+		m |= m>>1; m |= m>>2; m |= m>>4;
+		off &= m;
+		if (off > slack) off -= slack+1;
+		assert(off <= slack);
+	}
+	if (off) {
+		// store offset in unused header at offset zero
+		// if enframing at non-zero offset.
+		*(uint16_t *)(p-2) = off;
+		p[-3] = 7<<5;
+		p += UNIT*off;
+		// for nonzero offset there is no permanent check
+		// byte, so make one.
+		p[-4] = 0;
+	}
+	*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
+	p[-3] = idx;
+	set_size(p, end, n);
+	return p;
+}
+
+static inline int size_to_class(size_t n)
+{
+	n = (n+IB-1)>>4;
+	if (n<10) return n;
+	n++;
+	int i = (28-a_clz_32(n))*4 + 8;
+	if (n>size_classes[i+1]) i+=2;
+	if (n>size_classes[i]) i++;
+	return i;
+}
+
+static inline int size_overflows(size_t n)
+{
+	if (n >= SIZE_MAX/2 - 4096) {
+		errno = ENOMEM;
+		return 1;
+	}
+	return 0;
+}
+
+static inline void step_seq(void)
+{
+	if (ctx.seq==255) {
+		for (int i=0; i<32; i++) ctx.unmap_seq[i] = 0;
+		ctx.seq = 1;
+	} else {
+		ctx.seq++;
+	}
+}
+
+static inline void record_seq(int sc)
+{
+	if (sc-7U < 32) ctx.unmap_seq[sc-7] = ctx.seq;
+}
+
+static inline void account_bounce(int sc)
+{
+	if (sc-7U < 32) {
+		int seq = ctx.unmap_seq[sc-7];
+		if (seq && ctx.seq-seq < 10) {
+			if (ctx.bounces[sc-7]+1 < 100)
+				ctx.bounces[sc-7]++;
+			else
+				ctx.bounces[sc-7] = 150;
+		}
+	}
+}
+
+static inline void decay_bounces(int sc)
+{
+	if (sc-7U < 32 && ctx.bounces[sc-7])
+		ctx.bounces[sc-7]--;
+}
+
+static inline int is_bouncing(int sc)
+{
+	return (sc-7U < 32 && ctx.bounces[sc-7] >= 100);
+}
+
+#endif