Change the implementation of the malloc cache to keep lists of

regions of a given size.  In snaps for a while, committing since
no issues were reported and a wider audience is good.  ok deraadt@

1 files changed, 118 insertions, 152 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index 46b07ff77d0..9a4aacc3f95 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: malloc.c,v 1.268 2021/02/25 15:20:18 otto Exp $	*/
+/*	$OpenBSD: malloc.c,v 1.269 2021/03/09 07:39:28 otto Exp $	*/
 /*
  * Copyright (c) 2008, 2010, 2011, 2016 Otto Moerbeek <otto@drijf.net>
  * Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org>
@@ -113,29 +113,33 @@ struct region_info {
 
 LIST_HEAD(chunk_head, chunk_info);
 
+#define MAX_CACHEABLE_SIZE	32
+struct cache {
+	void *pages[MALLOC_MAXCACHE];
+	ushort length;
+	ushort max;
+};
+
 struct dir_info {
 	u_int32_t canary1;
 	int active;			/* status of malloc */
 	struct region_info *r;		/* region slots */
 	size_t regions_total;		/* number of region slots */
 	size_t regions_free;		/* number of free slots */
-	size_t free_regions_size;	/* free pages cached */
 	size_t rbytesused;		/* random bytes used */
 	char *func;			/* current function */
-	u_int malloc_cache;		/* # of free pages we cache */
 	int malloc_junk;		/* junk fill? */
 	int mmap_flag;			/* extra flag for mmap */
-	u_int rotor;
 	int mutex;
 					/* lists of free chunk info structs */
 	struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
 					/* lists of chunks with free slots */
 	struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS];
-					/* free pages cache */
-	struct region_info free_regions[MALLOC_MAXCACHE];
 					/* delayed free chunk slots */
 	void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1];
 	u_char rbytes[32];		/* random bytes */
+					/* free pages cache */
+	struct cache cache[MAX_CACHEABLE_SIZE];
 #ifdef MALLOC_STATS
 	size_t inserts;
 	size_t insert_collisions;
@@ -166,6 +170,8 @@ struct dir_info {
 #define DIR_INFO_RSZ	((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \
 			~MALLOC_PAGEMASK)
 
+static void unmap(struct dir_info *d, void *p, size_t sz, size_t clear);
+
 /*
  * This structure describes a page worth of chunks.
  *
@@ -196,7 +202,7 @@ struct malloc_readonly {
 	int	malloc_xmalloc;		/* xmalloc behaviour? */
 	u_int	chunk_canaries;		/* use canaries after chunks? */
 	int	internal_funcs;		/* use better recallocarray/freezero? */
-	u_int	def_malloc_cache;	/* free pages we cache */
+	u_int	def_maxcache;		/* free pages we cache */
 	size_t	malloc_guard;		/* use guard pages after allocations? */
 #ifdef MALLOC_STATS
 	int	malloc_stats;		/* dump statistics at end */
@@ -335,12 +341,12 @@ omalloc_parseopt(char opt)
 			mopts.malloc_mutexes = 2;
 		break;
 	case '>':
-		mopts.def_malloc_cache <<= 1;
-		if (mopts.def_malloc_cache > MALLOC_MAXCACHE)
-			mopts.def_malloc_cache = MALLOC_MAXCACHE;
+		mopts.def_maxcache <<= 1;
+		if (mopts.def_maxcache > MALLOC_MAXCACHE)
+			mopts.def_maxcache = MALLOC_MAXCACHE;
 		break;
 	case '<':
-		mopts.def_malloc_cache >>= 1;
+		mopts.def_maxcache >>= 1;
 		break;
 	case 'c':
 		mopts.chunk_canaries = 0;
@@ -416,7 +422,7 @@ omalloc_init(void)
 	 */
 	mopts.malloc_mutexes = 8;
 	mopts.def_malloc_junk = 1;
-	mopts.def_malloc_cache = MALLOC_DEFAULT_CACHE;
+	mopts.def_maxcache = MALLOC_DEFAULT_CACHE;
 
 	for (i = 0; i < 3; i++) {
 		switch (i) {
@@ -445,12 +451,12 @@ omalloc_init(void)
 			case 'S':
 				for (q = "CFGJ"; *q != '\0'; q++)
 					omalloc_parseopt(*q);
-				mopts.def_malloc_cache = 0;
+				mopts.def_maxcache = 0;
 				break;
 			case 's':
 				for (q = "cfgj"; *q != '\0'; q++)
 					omalloc_parseopt(*q);
-				mopts.def_malloc_cache = MALLOC_DEFAULT_CACHE;
+				mopts.def_maxcache = MALLOC_DEFAULT_CACHE;
 				break;
 			default:
 				omalloc_parseopt(*p);
@@ -512,7 +518,6 @@ omalloc_poolinit(struct dir_info **dp, int mmap_flag)
 	STATS_ADD(d->malloc_used, regioninfo_size + 3 * MALLOC_PAGESIZE);
 	d->mmap_flag = mmap_flag;
 	d->malloc_junk = mopts.def_malloc_junk;
-	d->malloc_cache = mopts.def_malloc_cache;
 	d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
 	d->canary2 = ~d->canary1;
 
@@ -525,16 +530,17 @@ omalloc_grow(struct dir_info *d)
 	size_t newtotal;
 	size_t newsize;
 	size_t mask;
-	size_t i;
+	size_t i, oldpsz;
 	struct region_info *p;
 
 	if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2)
 		return 1;
 
 	newtotal = d->regions_total * 2;
-	newsize = newtotal * sizeof(struct region_info);
+	newsize = PAGEROUND(newtotal * sizeof(struct region_info));
 	mask = newtotal - 1;
 
+	/* Don't use cache here, we don't want user uaf touch this */
 	p = MMAP(newsize, d->mmap_flag);
 	if (p == MAP_FAILED)
 		return 1;
@@ -554,13 +560,11 @@ omalloc_grow(struct dir_info *d)
 			p[index] = d->r[i];
 		}
 	}
-	/* avoid pages containing meta info to end up in cache */
-	if (munmap(d->r, d->regions_total * sizeof(struct region_info)))
-		wrterror(d, "munmap %p", (void *)d->r);
-	else
-		STATS_SUB(d->malloc_used,
-		    d->regions_total * sizeof(struct region_info));
-	d->regions_free = d->regions_free + d->regions_total;
+
+	oldpsz = PAGEROUND(d->regions_total * sizeof(struct region_info));
+	/* clear to avoid meta info ending up in the cache */
+	unmap(d, d->r, oldpsz, oldpsz);
+	d->regions_free += d->regions_total;
 	d->regions_total = newtotal;
 	d->r = p;
 	return 0;
@@ -700,9 +704,7 @@ validate_junk(struct dir_info *pool, void *p, size_t sz)
 
 
 /*
- * Cache maintenance. We keep at most malloc_cache pages cached.
- * If the cache is becoming full, unmap pages in the cache for real,
- * and then add the region to the cache
+ * Cache maintenance. 
  * Opposed to the regular region data structure, the sizes in the
  * cache are in MALLOC_PAGESIZE units.
  */
@@ -710,139 +712,100 @@ static void
 unmap(struct dir_info *d, void *p, size_t sz, size_t clear)
 {
 	size_t psz = sz >> MALLOC_PAGESHIFT;
-	size_t rsz;
-	struct region_info *r;
-	u_int i, offset, mask;
+	void *r;
+	u_short i;
+	struct cache *cache;
 
-	if (sz != PAGEROUND(sz))
+	if (sz != PAGEROUND(sz) || psz == 0)
 		wrterror(d, "munmap round");
 
-	rsz = d->malloc_cache - d->free_regions_size;
-
-	/*
-	 * normally the cache holds recently freed regions, but if the region
-	 * to unmap is larger than the cache size or we're clearing and the
-	 * cache is full, just munmap
-	 */
-	if (psz > d->malloc_cache || (clear > 0 && rsz == 0)) {
-		i = munmap(p, sz);
-		if (i)
+	if (psz > MAX_CACHEABLE_SIZE || d->cache[psz - 1].max == 0) {
+		if (munmap(p, sz))
 			wrterror(d, "munmap %p", p);
 		STATS_SUB(d->malloc_used, sz);
 		return;
 	}
-	offset = getrbyte(d);
-	mask = d->malloc_cache - 1;
-	if (psz > rsz) {
-		size_t tounmap = psz - rsz;
-		for (i = 0; ; i++) {
-			r = &d->free_regions[(i + offset) & mask];
-			if (r->p != NULL) {
-				rsz = r->size << MALLOC_PAGESHIFT;
-				if (!mopts.malloc_freeunmap)
-					validate_junk(d, r->p, rsz);
-				if (munmap(r->p, rsz))
-					wrterror(d, "munmap %p", r->p);
-				r->p = NULL;
-				if (tounmap > r->size)
-					tounmap -= r->size;
-				else
-					tounmap = 0;
-				d->free_regions_size -= r->size;
-				STATS_SUB(d->malloc_used, rsz);
-				if (tounmap == 0) {
-					offset = i;
-					break;
-				}
-			}
-		}
-	}
-	for (i = 0; ; i++) {
-		r = &d->free_regions[(i + offset) & mask];
-		if (r->p == NULL) {
-			if (clear > 0)
-				memset(p, 0, clear);
-			if (mopts.malloc_freeunmap)
-				mprotect(p, sz, PROT_NONE);
-			else
-				junk_free(d->malloc_junk, p,
-				    psz << MALLOC_PAGESHIFT);
-			r->p = p;
-			r->size = psz;
-			d->free_regions_size += psz;
-			break;
-		}
-	}
-	if (d->free_regions_size > d->malloc_cache)
-		wrterror(d, "malloc cache overflow");
+	cache = &d->cache[psz - 1];
+	if (cache->length == cache->max) {
+		/* use a random slot */
+		i = getrbyte(d) % cache->max;
+		r = cache->pages[i];
+		if (!mopts.malloc_freeunmap)
+			validate_junk(d, r, sz);
+		if (munmap(r, sz))
+			wrterror(d, "munmap %p", r);
+		STATS_SUB(d->malloc_used, sz);
+		cache->length--;
+	} else
+		i = cache->length;
+
+	/* fill slot */
+	if (clear > 0)
+		memset(p, 0, clear);
+	if (mopts.malloc_freeunmap)
+		mprotect(p, sz, PROT_NONE);
+	else
+		junk_free(d->malloc_junk, p, sz);
+	cache->pages[i] = p;
+	cache->length++;
 }
 
 static void *
 map(struct dir_info *d, size_t sz, int zero_fill)
 {
-	size_t psz = sz >> MALLOC_PAGESHIFT;
-	struct region_info *r, *big = NULL;
-	u_int i;
+	size_t i, psz = sz >> MALLOC_PAGESHIFT;
 	void *p;
+	struct cache *cache;
 
 	if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
 	    d->canary1 != ~d->canary2)
 		wrterror(d, "internal struct corrupt");
-	if (sz != PAGEROUND(sz))
+	if (sz != PAGEROUND(sz) || psz == 0)
 		wrterror(d, "map round");
 
-	if (psz > d->free_regions_size) {
-		_MALLOC_LEAVE(d);
-		p = MMAP(sz, d->mmap_flag);
-		_MALLOC_ENTER(d);
-		if (p != MAP_FAILED)
-			STATS_ADD(d->malloc_used, sz);
-		/* zero fill not needed */
-		return p;
-	}
-	for (i = 0; i < d->malloc_cache; i++) {
-		r = &d->free_regions[(i + d->rotor) & (d->malloc_cache - 1)];
-		if (r->p != NULL) {
-			if (r->size == psz) {
-				p = r->p;
-				if (!mopts.malloc_freeunmap)
-					validate_junk(d, p,
-					    psz << MALLOC_PAGESHIFT);
-				r->p = NULL;
-				d->free_regions_size -= psz;
+	
+	if (psz <= MAX_CACHEABLE_SIZE && d->cache[psz - 1].max > 0) {
+		cache = &d->cache[psz - 1];
+		if (cache->length > 0) {
+			if (cache->length == 1)
+				p = cache->pages[--cache->length];
+			else {
+				i = getrbyte(d) % cache->length;
+				p = cache->pages[i];
+				cache->pages[i] = cache->pages[--cache->length];
+			}
+			if (!mopts.malloc_freeunmap)
+				validate_junk(d, p, sz);
+			if (mopts.malloc_freeunmap)
+				mprotect(p, sz, PROT_READ | PROT_WRITE);
+			if (zero_fill)
+				memset(p, 0, sz);
+			else if (mopts.malloc_freeunmap)
+				junk_free(d->malloc_junk, p, sz);
+			return p;
+		}
+		if (psz <= 1) {
+			_MALLOC_LEAVE(d);
+			p = MMAP(cache->max * sz, d->mmap_flag);
+			_MALLOC_ENTER(d);
+			if (p != MAP_FAILED) {
+				STATS_ADD(d->malloc_used, cache->max * sz);
+				cache->length = cache->max - 1;
+				for (i = 0; i < cache->max - 1; i++) {
+					void *q = (char*)p + i * sz;
+					cache->pages[i] = q;
+					if (!mopts.malloc_freeunmap)
+						junk_free(d->malloc_junk, q, sz);
+				}
 				if (mopts.malloc_freeunmap)
-					mprotect(p, sz, PROT_READ | PROT_WRITE);
-				if (zero_fill)
-					memset(p, 0, sz);
-				else if (mopts.malloc_freeunmap)
-					junk_free(d->malloc_junk, p, sz);
-				d->rotor += i + 1;
+					mprotect(p, (cache->max - 1) * sz, PROT_NONE);
+				p = (char*)p + (cache->max - 1) * sz;
+				/* zero fill not needed */
 				return p;
-			} else if (r->size > psz)
-				big = r;
+			}
 		}
+
 	}
-	if (big != NULL) {
-		r = big;
-		p = r->p;
-		if (!mopts.malloc_freeunmap)
-			validate_junk(d, p, r->size << MALLOC_PAGESHIFT);
-		r->p = (char *)r->p + (psz << MALLOC_PAGESHIFT);
-		r->size -= psz;
-		d->free_regions_size -= psz;
-		if (mopts.malloc_freeunmap)
-			mprotect(p, sz, PROT_READ | PROT_WRITE);
-		else
-			junk_free(d->malloc_junk, r->p,
-			    r->size << MALLOC_PAGESHIFT);
-		if (zero_fill)
-			memset(p, 0, sz);
-		else if (mopts.malloc_freeunmap)
-			junk_free(d->malloc_junk, p, sz);
-		return p;
-	}
-	if (d->free_regions_size > d->malloc_cache)
-		wrterror(d, "malloc cache");
 	_MALLOC_LEAVE(d);
 	p = MMAP(sz, d->mmap_flag);
 	_MALLOC_ENTER(d);
@@ -896,6 +859,7 @@ alloc_chunk_info(struct dir_info *d, int bits)
 			size += count * sizeof(u_short);
 		size = _ALIGN(size);
 
+		/* Don't use cache here, we don't want user uaf touch this */
 		q = MMAP(MALLOC_PAGESIZE, d->mmap_flag);
 		if (q == MAP_FAILED)
 			return NULL;
@@ -1239,7 +1203,7 @@ malloc_recurse(struct dir_info *d)
 void
 _malloc_init(int from_rthreads)
 {
-	u_int i, nmutexes;
+	u_int i, j, nmutexes;
 	struct dir_info *d;
 
 	_MALLOC_LOCK(1);
@@ -1260,11 +1224,13 @@ _malloc_init(int from_rthreads)
 		if (i == 0) {
 			omalloc_poolinit(&d, MAP_CONCEAL);
 			d->malloc_junk = 2;
-			d->malloc_cache = 0;
+			for (j = 0; j < MAX_CACHEABLE_SIZE; j++)
+				d->cache[j].max = 0;
 		} else {
 			omalloc_poolinit(&d, 0);
 			d->malloc_junk = mopts.def_malloc_junk;
-			d->malloc_cache = mopts.def_malloc_cache;
+			for (j = 0; j < MAX_CACHEABLE_SIZE; j++)
+				d->cache[j].max = mopts.def_maxcache >> (j / 8);
 		}
 		d->mutex = i;
 		mopts.malloc_pool[i] = d;
@@ -1591,7 +1557,7 @@ orealloc(struct dir_info **argpool, void *p, size_t newsz, void *f)
 		size_t rnewsz = PAGEROUND(gnewsz);
 
 		if (rnewsz < roldsz && rnewsz > roldsz / 2 &&
-		    roldsz - rnewsz < pool->malloc_cache * MALLOC_PAGESIZE &&
+		    roldsz - rnewsz < mopts.def_maxcache * MALLOC_PAGESIZE &&
 		    !mopts.malloc_guard) {
 
 			ret = p;
@@ -2227,16 +2193,17 @@ dump_free_chunk_info(int fd, struct dir_info *d)
 static void
 dump_free_page_info(int fd, struct dir_info *d)
 {
-	int i;
+	struct cache *cache;
+	size_t i, total = 0;
 
-	dprintf(fd, "Free pages cached: %zu\n", d->free_regions_size);
-	for (i = 0; i < d->malloc_cache; i++) {
-		if (d->free_regions[i].p != NULL) {
-			dprintf(fd, "%2d) ", i);
-			dprintf(fd, "free at %p: %zu\n",
-			    d->free_regions[i].p, d->free_regions[i].size);
-		}
+	dprintf(fd, "Cached:\n");
+	for (i = 0; i < MAX_CACHEABLE_SIZE; i++) {
+		cache = &d->cache[i];
+		if (cache->length != 0)
+			dprintf(fd, "%zu(%u): %u = %zu\n", i + 1, cache->max, cache->length, cache->length * (i + 1));
+		total += cache->length * (i + 1);
 	}
+	dprintf(fd, "Free pages cached: %zu\n", total);
 }
 
 static void
@@ -2247,8 +2214,7 @@ malloc_dump1(int fd, int poolno, struct dir_info *d)
 	dprintf(fd, "Malloc dir of %s pool %d at %p\n", __progname, poolno, d);
 	if (d == NULL)
 		return;
-	dprintf(fd, "J=%d cache=%u Fl=%x\n",
-	    d->malloc_junk, d->malloc_cache, d->mmap_flag);
+	dprintf(fd, "J=%d Fl=%x\n", d->malloc_junk, d->mmap_flag);
 	dprintf(fd, "Region slots free %zu/%zu\n",
 		d->regions_free, d->regions_total);
 	dprintf(fd, "Finds %zu/%zu\n", d->finds, d->find_collisions);
@@ -2340,7 +2306,7 @@ malloc_exit(void)
 		    mopts.internal_funcs, mopts.malloc_freecheck,
 		    mopts.malloc_freeunmap, mopts.def_malloc_junk,
 		    mopts.malloc_realloc, mopts.malloc_xmalloc,
-		    mopts.chunk_canaries, mopts.def_malloc_cache,
+		    mopts.chunk_canaries, mopts.def_maxcache,
 		    mopts.malloc_guard);
 
 		for (i = 0; i < mopts.malloc_mutexes; i++)