[PATCH 1/3] dlmalloc: use jemalloc-inspired size classes

[Eric Wong <e@80x24.org>]

For allocations too small for direct mmap and too large for
fastbins, use jemalloc-inspired size classes to reduce
fragmentation.  This means mid-sized allocations pay a 0-20%
overhead to improve the likelyhood of having a good fit
(and not "best fit") over repeated allocations and frees.
---
 mwrap_core.h | 39 +++++++++++++++++++++++++++++++++++----
 1 file changed, 35 insertions(+), 4 deletions(-)

diff --git a/mwrap_core.h b/mwrap_core.h
index 7ccf6ad..78c14e3 100644
--- a/mwrap_core.h
+++ b/mwrap_core.h
@@ -661,11 +661,39 @@ void *pvalloc(size_t size)
 	return memalign_result(err, p);
 }
 
+static inline size_t size_class_pad(size_t bytes)
+{
+	if (bytes <= MAX_SMALL_REQUEST)
+		return bytes;
+
+	size_t mm_thresh = mparams.mmap_threshold;
+
+	if (bytes >= mm_thresh)
+		return bytes;
+
+	/*
+	 * Use jemalloc-inspired size classes for mid-size allocations to
+	 * minimize fragmentation.  This means we pay a 0-20% overhead on
+	 * the initial allocations to improve the likelyhood of reuse.
+	 */
+	size_t max = sizeof(void *) << 5;
+	size_t nxt;
+	do {
+		if (bytes <= max) {
+			size_t sc_bytes = size_align(bytes, max >> 3);
+			return sc_bytes <= mm_thresh ? sc_bytes : bytes;
+		}
+		nxt = max << 1;
+	} while (nxt > max && nxt < mm_thresh && (max = nxt));
+
+	return bytes;
+}
+
 void *malloc(size_t size)
 {
-	size_t asize;
+	size_t asize = size_class_pad(size);
 
-	if (__builtin_add_overflow(size, sizeof(struct alloc_hdr), &asize))
+	if (__builtin_add_overflow(asize, sizeof(struct alloc_hdr), &asize))
 		goto enomem;
 
 	void *p = real_malloc(asize);
@@ -686,7 +714,9 @@ void *calloc(size_t nmemb, size_t size)
 
 	if (__builtin_mul_overflow(size, nmemb, &size))
 		goto enomem;
-	if (__builtin_add_overflow(size, sizeof(struct alloc_hdr), &asize))
+
+	asize = size_class_pad(size);
+	if (__builtin_add_overflow(asize, sizeof(struct alloc_hdr), &asize))
 		goto enomem;
 	void *p = real_malloc(asize);
 	if (p) {
@@ -708,7 +738,8 @@ void *realloc(void *ptr, size_t size)
 		free(ptr);
 		return 0;
 	}
-	if (__builtin_add_overflow(size, sizeof(struct alloc_hdr), &asize))
+	asize = size_class_pad(size);
+	if (__builtin_add_overflow(asize, sizeof(struct alloc_hdr), &asize))
 		goto enomem;
 	void *p = real_malloc(asize);
 	if (p) {