More efficient scanning for free chunks while not losing any randomization;

thanks to all testers.

1 files changed, 25 insertions, 21 deletions

diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
index 8d7d3ae18a..010cb7fafc 100644
--- a/src/lib/libc/stdlib/malloc.c
+++ b/src/lib/libc/stdlib/malloc.c
@@ -1,4 +1,4 @@
-/*      $OpenBSD: malloc.c,v 1.127 2010/12/16 18:47:01 dhill Exp $      */
+/*      $OpenBSD: malloc.c,v 1.128 2011/04/30 14:56:20 otto Exp $       */
 /*
  * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
  *
@@ -138,7 +138,7 @@ struct dir_info {
  *
  * How many bits per u_long in the bitmap
  */
-#define MALLOC_BITS             (NBBY * sizeof(u_long))
+#define MALLOC_BITS             (NBBY * sizeof(u_short))
 struct chunk_info {
         LIST_ENTRY(chunk_info) entries;
         void *page;                     /* pointer to the page */
@@ -148,7 +148,7 @@ struct chunk_info {
         u_short free;                   /* how many free chunks */
         u_short total;                  /* how many chunk */
                                         /* which chunks are free */
-        u_long bits[(MALLOC_PAGESIZE / MALLOC_MINSIZE) / MALLOC_BITS];
+        u_short bits[(MALLOC_PAGESIZE / MALLOC_MINSIZE) / MALLOC_BITS];
 };
 
 struct malloc_readonly {
@@ -958,10 +958,10 @@ omalloc_make_chunks(struct dir_info *d, int bits)
 
         /* Do a bunch at a time */
         for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
-                bp->bits[i / MALLOC_BITS] = ~0UL;
+                bp->bits[i / MALLOC_BITS] = (u_short)~0U;
 
         for (; i < k; i++)
-                bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
+                bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS);
 
         LIST_INSERT_HEAD(&d->chunk_dir[bits], bp, entries);
 
@@ -982,7 +982,7 @@ malloc_bytes(struct dir_info *d, size_t size)
 {
         int             i, j;
         size_t          k;
-        u_long          u, *lp;
+        u_short         u, *lp;
         struct chunk_info *bp;
 
         if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
@@ -1026,22 +1026,26 @@ malloc_bytes(struct dir_info *d, size_t size)
         }
 
         /* advance a random # of positions */
-        i = getrnibble() % bp->free;
-        while (i > 0) {
-                u += u;
-                k++;
-                if (k >= MALLOC_BITS) {
-                        lp++;
-                        u = 1;
-                        k = 0;
-                }
-                if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
-                        wrterror("chunk overflow", NULL);
-                        errno = EFAULT;
-                        return (NULL);
+        if (bp->free > 1) {
+                i = getrnibble() % bp->free;
+                while (i > 0) {
+                        u += u;
+                        k++;
+                        if (k >= MALLOC_BITS) {
+                                while (!*++lp)
+                                        /* EMPTY */;
+                                u = 1;
+                                k = 0;
+                                if (lp - bp->bits > (bp->total - 1) /
+                                    MALLOC_BITS) {
+                                        wrterror("chunk overflow", NULL);
+                                        errno = EFAULT;
+                                        return (NULL);
+                                }
+                        }
+                        if (*lp & u)
+                                i--;
                 }
-                if (*lp & u)
-                        i--;
         }
 
         *lp ^= u;