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.

1 files changed, 20 insertions, 16 deletions

diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
index 361294eb51..c0542fc9c8 100644
--- a/src/lib/libc/stdlib/malloc.c
+++ b/src/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 <otto@drijf.net>
  * Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org>
@@ -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;