From c42849b106551f5d9c723e3924b6f93db88fca84 Mon Sep 17 00:00:00 2001 From: tedu Date: Mon, 12 May 2014 19:02:20 +0000 Subject: [PATCH] change to having four freelists per size, to reduce another source of deterministic behavior. four selected because it's more than three, less than five. i.e., no particular reason. --- lib/libc/stdlib/malloc.c | 36 ++++++++++++++++++++---------------- 1 file changed, 20 insertions(+), 16 deletions(-) diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c index 361294eb511..c0542fc9c86 100644 --- a/lib/libc/stdlib/malloc.c +++ b/lib/libc/stdlib/malloc.c @@ -1,4 +1,4 @@ -/* $OpenBSD: malloc.c,v 1.162 2014/05/10 18:14:55 otto Exp $ */ +/* $OpenBSD: malloc.c,v 1.163 2014/05/12 19:02:20 tedu Exp $ */ /* * Copyright (c) 2008, 2010, 2011 Otto Moerbeek * Copyright (c) 2012 Matthew Dempsky @@ -64,6 +64,7 @@ #define MALLOC_DELAYED_CHUNK_MASK 15 #define MALLOC_INITIAL_REGIONS 512 #define MALLOC_DEFAULT_CACHE 64 +#define MALLOC_CHUNK_LISTS 4 /* * When the P option is active, we move allocations between half a page @@ -110,7 +111,7 @@ struct dir_info { /* 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]; + struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS]; size_t free_regions_size; /* free pages cached */ /* free pages cache */ struct region_info free_regions[MALLOC_MAXCACHE]; @@ -621,7 +622,8 @@ omalloc_init(struct dir_info **dp) } for (i = 0; i <= MALLOC_MAXSHIFT; i++) { LIST_INIT(&d->chunk_info_list[i]); - LIST_INIT(&d->chunk_dir[i]); + for (j = 0; j < MALLOC_CHUNK_LISTS; j++) + LIST_INIT(&d->chunk_dir[i][j]); } malloc_used += regioninfo_size; d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d; @@ -816,7 +818,7 @@ delete(struct dir_info *d, struct region_info *ri) * Allocate a page of chunks */ static struct chunk_info * -omalloc_make_chunks(struct dir_info *d, int bits) +omalloc_make_chunks(struct dir_info *d, int bits, int listnum) { struct chunk_info *bp; void *pp; @@ -867,7 +869,7 @@ omalloc_make_chunks(struct dir_info *d, int bits) for (; i < k; i++) bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS); - LIST_INSERT_HEAD(&d->chunk_dir[bits], bp, entries); + LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries); bits++; if ((uintptr_t)pp & bits) @@ -884,7 +886,7 @@ omalloc_make_chunks(struct dir_info *d, int bits) static void * malloc_bytes(struct dir_info *d, size_t size, void *f) { - int i, j; + int i, j, listnum; size_t k; u_short u, *lp; struct chunk_info *bp; @@ -907,13 +909,13 @@ malloc_bytes(struct dir_info *d, size_t size, void *f) j++; } + listnum = getrbyte() % MALLOC_CHUNK_LISTS; /* If it's empty, make a page more of that size chunks */ - if (LIST_EMPTY(&d->chunk_dir[j])) { - bp = omalloc_make_chunks(d, j); + if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) { + bp = omalloc_make_chunks(d, j, listnum); if (bp == NULL) return NULL; - } else - bp = LIST_FIRST(&d->chunk_dir[j]); + } if (bp->canary != d->canary1) wrterror("chunk info corrupted", NULL); @@ -973,7 +975,7 @@ free_bytes(struct dir_info *d, struct region_info *r, void *ptr) { struct chunk_head *mp; struct chunk_info *info; - int i; + int i, listnum; info = (struct chunk_info *)r->size; if (info->canary != d->canary1) @@ -994,16 +996,18 @@ free_bytes(struct dir_info *d, struct region_info *r, void *ptr) info->bits[i / MALLOC_BITS] |= 1U << (i % MALLOC_BITS); info->free++; - if (info->size != 0) - mp = d->chunk_dir + info->shift; - else - mp = d->chunk_dir; - if (info->free == 1) { /* Page became non-full */ + listnum = getrbyte() % MALLOC_CHUNK_LISTS; + if (info->size != 0) + mp = &d->chunk_dir[info->shift][listnum]; + else + mp = &d->chunk_dir[0][listnum]; + LIST_INSERT_HEAD(mp, info, entries); return; } + if (info->free != info->total) return; -- 2.20.1