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, 57 insertions, 0 deletions

diff --git a/src/malloc/mallocng/aligned_alloc.c b/src/malloc/mallocng/aligned_alloc.c
new file mode 100644
index 00000000..34116896
--- /dev/null
+++ b/src/malloc/mallocng/aligned_alloc.c
@@ -0,0 +1,57 @@
+#include <stdlib.h>
+#include <errno.h>
+#include "meta.h"
+
+void *aligned_alloc(size_t align, size_t len)
+{
+	if ((align & -align) != align) {
+		errno = EINVAL;
+		return 0;
+	}
+
+	if (len > SIZE_MAX - align || align >= (1ULL<<31)*UNIT) {
+		errno = ENOMEM;
+		return 0;
+	}
+
+	if (DISABLE_ALIGNED_ALLOC) {
+		errno = ENOMEM;
+		return 0;
+	}
+
+	if (align <= UNIT) align = UNIT;
+
+	unsigned char *p = malloc(len + align - UNIT);
+	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 = g->mem->storage + stride*(idx+1) - IB;
+	size_t adj = -(uintptr_t)p & (align-1);
+
+	if (!adj) {
+		set_size(p, end, len);
+		return p;
+	}
+	p += adj;
+	uint32_t offset = (size_t)(p-g->mem->storage)/UNIT;
+	if (offset <= 0xffff) {
+		*(uint16_t *)(p-2) = offset;
+		p[-4] = 0;
+	} else {
+		// use a 32-bit offset if 16-bit doesn't fit. for this,
+		// 16-bit field must be zero, [-4] byte nonzero.
+		*(uint16_t *)(p-2) = 0;
+		*(uint32_t *)(p-8) = offset;
+		p[-4] = 1;
+	}
+	p[-3] = idx;
+	set_size(p, end, len);
+	// store offset to aligned enframing. this facilitates cycling
+	// offset and also iteration of heap for debugging/measurement.
+	// for extreme overalignment it won't fit but these are classless
+	// allocations anyway.
+	*(uint16_t *)(start - 2) = (size_t)(p-start)/UNIT;
+	start[-3] = 7<<5;
+	return p;
+}