From c9c2a8bced2637f49891a0cc87ce149229a8c70e Mon Sep 17 00:00:00 2001 From: otto Date: Tue, 9 Mar 2021 07:39:28 +0000 Subject: [PATCH] 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@ --- lib/libc/stdlib/malloc.c | 270 +++++++++++++++++---------------------- 1 file 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 * Copyright (c) 2012 Matthew Dempsky @@ -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++) -- 2.20.1