Integrate latest malloc(3) from FreeBSD

1 files changed, 124 insertions, 264 deletions

diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
index 1606ea6602e..94db62c5852 100644
--- a/lib/libc/stdlib/malloc.c
+++ b/lib/libc/stdlib/malloc.c
@@ -8,7 +8,7 @@
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
-static char rcsid[] = "$OpenBSD: malloc.c,v 1.19 1996/11/24 00:41:30 niklas Exp $";
+static char rcsid[] = "$OpenBSD: malloc.c,v 1.20 1997/01/05 22:12:48 tholo Exp $";
 #endif /* LIBC_SCCS and not lint */
 
 /*
@@ -18,17 +18,17 @@ static char rcsid[] = "$OpenBSD: malloc.c,v 1.19 1996/11/24 00:41:30 niklas Exp
  * any good unless you fiddle with the internals of malloc or want
  * to catch random pointer corruption as early as possible.
  */
-#undef EXTRA_SANITY
+#ifndef MALLOC_EXTRA_SANITY
+#undef MALLOC_EXTRA_SANITY
+#endif
 
 /*
  * Defining MALLOC_STATS will enable you to call malloc_dump() and set
  * the [dD] options in the MALLOC_OPTIONS environment variable.
  * It has no run-time performance hit, but does pull in stdio...
  */
+#ifndef MALLOC_STATS
 #undef MALLOC_STATS
-
-#if defined(EXTRA_SANITY) && !defined(MALLOC_STATS)
-# define MALLOC_STATS	/* required for EXTRA_SANITY */
 #endif
 
 /*
@@ -51,16 +51,24 @@ static char rcsid[] = "$OpenBSD: malloc.c,v 1.19 1996/11/24 00:41:30 niklas Exp
 #include <sys/mman.h>
 
 /*
- * If these weren't defined here, they would be calculated on the fly,
- * at a considerable cost in performance.
+ * The basic parameters you can tweak.
+ *
+ * malloc_pageshift	pagesize = 1 << malloc_pageshift
+ *			It's probably best if this is the native
+ *			page size, but it shouldn't have to be.
+ *
+ * malloc_minsize	minimum size of an allocation in bytes.
+ *			If this is too small it's too much work
+ *			to manage them.  This is also the smallest
+ *			unit of alignment used for the storage
+ *			returned by malloc/realloc.
+ *
  */
 #ifdef __OpenBSD__
 #   if defined(__alpha__) || defined(__m68k__) || defined(__mips__) || \
        defined(__i386__) || defined(__m88k__) || defined(__ns32k__) || \
        defined(__vax__)
-#	define	malloc_pagesize		(NBPG)
 #	define	malloc_pageshift	(PGSHIFT)
-#	define	malloc_maxsize		(malloc_pagesize >> 1)
 #	define	malloc_minsize		16U
 #   endif /* __i386__ */
 #endif /* __OpenBSD__ */
@@ -76,7 +84,7 @@ struct pginfo {
     u_short		shift;	/* How far to shift for this size chunks */
     u_short		free;	/* How many free chunks */
     u_short		total;	/* How many chunk */
-    u_long		bits[1]; /* Which chunks are free */
+    u_int		bits[1]; /* Which chunks are free */
 };
 
 /*
@@ -92,10 +100,10 @@ struct pgfree {
 };
 
 /*
- * How many bits per u_long in the bitmap.
+ * How many bits per u_int in the bitmap.
  * Change only if not 8 bits/byte
  */
-#define	MALLOC_BITS	(8*sizeof(u_long))
+#define	MALLOC_BITS	(8*sizeof(u_int))
 
 /*
  * Magic values to put in the page_directory
@@ -106,67 +114,29 @@ struct pgfree {
 #define MALLOC_FOLLOW	((struct pginfo*) 3)
 #define MALLOC_MAGIC	((struct pginfo*) 4)
 
-/*
- * The i386 architecture has some very convenient instructions.
- * We might as well use them.  There are C-language backups, but
- * they are considerably slower.
- */
-#if defined(__i386__) && defined(__GNUC__)
-#define ffs _ffs
-static __inline int
-_ffs(input)
-	unsigned input;
-{
-	int result;
-	__asm("bsfl %1, %0" : "=r" (result) : "r" (input));
-	return result+1;
-}
-
-#define fls _fls
-static __inline int
-_fls(input)
-	unsigned input;
-{
-	int result;
-	__asm("bsrl %1, %0" : "=r" (result) : "r" (input));
-	return result+1;
-}
+#ifndef malloc_pageshift
+#define malloc_pageshift		12U
+#endif
 
-#define set_bit _set_bit
-static __inline void
-_set_bit(pi, bit)
-	struct pginfo *pi;
-	int bit;
-{
-	__asm("btsl %0, (%1)" :
-	: "r" (bit & (MALLOC_BITS-1)), "r" (pi->bits+(bit/MALLOC_BITS)));
-}
+#ifndef malloc_minsize
+#define malloc_minsize			16U
+#endif
 
-#define clr_bit _clr_bit
-static __inline void
-_clr_bit(pi, bit)
-	struct pginfo *pi;
-	int bit;
-{
-	__asm("btcl %0, (%1)" :
-	: "r" (bit & (MALLOC_BITS-1)), "r" (pi->bits+(bit/MALLOC_BITS)));
-}
+#ifndef malloc_pageshift
+#error	"malloc_pageshift undefined"
+#endif
 
-#endif /* __i386__ && __GNUC__ */
+#if !defined(malloc_pagesize)
+#define malloc_pagesize			(1U<<malloc_pageshift)
+#endif
 
-/*
- * Set to one when malloc_init has been called
- */
-static	unsigned	initialized;
+#if ((1<<malloc_pageshift) != malloc_pagesize)
+#error	"(1<<malloc_pageshift) != malloc_pagesize"
+#endif
 
-/*
- * The size of a page.
- * Must be a integral multiplum of the granularity of mmap(2).
- * Your toes will curl if it isn't a power of two
- */
-#ifndef malloc_pagesize
-static	unsigned        malloc_pagesize;
-#endif /* malloc_pagesize */
+#ifndef malloc_maxsize
+#define malloc_maxsize			((malloc_pagesize)>>1)
+#endif
 
 /* A mask for the offset inside a page.  */
 #define malloc_pagemask	((malloc_pagesize)-1)
@@ -174,45 +144,26 @@ static	unsigned        malloc_pagesize;
 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo)
 
-/* malloc_pagesize == 1 << malloc_pageshift */
-#ifndef malloc_pageshift
-static	unsigned	malloc_pageshift;
-#endif /* malloc_pageshift */
+/* Set when initialization has been done */
+static unsigned malloc_started;	
 
-/*
- * The smallest allocation we bother about.
- * Must be power of two
- */
-#ifndef malloc_minsize
-static	unsigned  malloc_minsize;
-#endif /* malloc_minsize */
-
-/*
- * The largest chunk we care about.
- * Must be smaller than pagesize
- * Must be power of two
- */
-#ifndef malloc_maxsize
-static	unsigned  malloc_maxsize;
-#endif /* malloc_maxsize */
-
-/* The minimum size (in pages) of the free page cache.  */
-static	unsigned  malloc_cache = 16;
+/* Number of free pages we cache */
+static unsigned malloc_cache = 16;
 
 /* The offset from pagenumber to index into the page directory */
-static	u_long  malloc_origo;
+static u_long malloc_origo;
 
 /* The last index in the page directory we care about */
-static	u_long  last_index;
+static u_long last_index;
 
 /* Pointer to page directory. Allocated "as if with" malloc */
-static	struct	pginfo **page_dir;
+static struct	pginfo **page_dir;
 
 /* How many slots in the page directory */
-static	unsigned	malloc_ninfo;
+static unsigned	malloc_ninfo;
 
 /* Free pages line up here */
-static struct pgfree	free_list;
+static struct pgfree free_list;
 
 /* Abort(), user doesn't handle problems.  */
 static int malloc_abort;
@@ -223,7 +174,7 @@ static int suicide;
 #ifdef MALLOC_STATS
 /* dump statistics */
 static int malloc_stats;
-#endif /* MALLOC_STATS */
+#endif
 
 /* always realloc ?  */
 static int malloc_realloc;
@@ -245,6 +196,8 @@ static int malloc_utrace;
 
 struct ut { void *p; size_t s; void *r; };
 
+void utrace __P((struct ut *, int));
+
 #define UTRACE(a, b, c) \
 	if (malloc_utrace) \
 		{struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
@@ -261,6 +214,9 @@ static struct pgfree *px;
 /* compile-time options */
 char *malloc_options;
 
+/* Name of the current public function */
+static char *malloc_func;
+
 /*
  * Necessary function declarations
  */
@@ -328,16 +284,17 @@ malloc_dump(fd)
 }
 #endif /* MALLOC_STATS */
 
-static char *malloc_func;
+extern char *__progname;
 
 static void
 wrterror(p)
     char *p;
 {
-    char *q = "Malloc error: ";
+    char *q = " error: ";
     suicide = 1;
-    write(2, q, strlen(q));
+    write(2, __progname, strlen(__progname));
     write(2, malloc_func, strlen(malloc_func));
+    write(2, q, strlen(q));
     write(2, p, strlen(p));
 #ifdef MALLOC_STATS
     if (malloc_stats)
@@ -350,15 +307,16 @@ static void
 wrtwarning(p)
     char *p;
 {
-    char *q = "Malloc warning: ";
+    char *q = " warning: ";
     if (malloc_abort)
 	wrterror(p);
-    write(2, q, strlen(q));
+    write(2, __progname, strlen(__progname));
     write(2, malloc_func, strlen(malloc_func));
+    write(2, q, strlen(q));
     write(2, p, strlen(p));
 }
 
-#ifdef EXTRA_SANITY
+#ifdef MALLOC_STATS
 static void
 malloc_exit()
 {
@@ -370,7 +328,7 @@ malloc_exit()
     } else
 	write(2, q, strlen(q));
 }
-#endif /* EXTRA_SANITY */
+#endif /* MALLOC_STATS */
 
 
 /*
@@ -402,83 +360,6 @@ map_pages(pages)
 }
 
 /*
- * Set a bit in the bitmap
- */
-#ifndef set_bit
-static __inline void
-set_bit(pi, bit)
-    struct pginfo *pi;
-    int bit;
-{
-    pi->bits[bit/MALLOC_BITS] |= 1UL<<(bit%MALLOC_BITS);
-}
-#endif /* set_bit */
-
-/*
- * Clear a bit in the bitmap
- */
-#ifndef clr_bit
-static __inline void
-clr_bit(pi, bit)
-    struct pginfo *pi;
-    int bit;
-{
-    pi->bits[bit/MALLOC_BITS] &= ~(1UL<<(bit%MALLOC_BITS));
-}
-#endif /* clr_bit */
-
-#ifndef tst_bit
-/*
- * Test a bit in the bitmap
- */
-static __inline int
-tst_bit(pi, bit)
-    struct pginfo *pi;
-    int bit;
-{
-    return pi->bits[bit/MALLOC_BITS] & (1UL<<(bit%MALLOC_BITS));
-}
-#endif /* tst_bit */
-
-/*
- * Find last bit
- */
-#ifndef fls
-static __inline int
-fls(size)
-    size_t size;
-{
-    int i = 1;
-    while (size >>= 1)
-	i++;
-    return i;
-}
-#endif /* fls */
-
-#if LONG_BIT == WORD_BIT
-#define ffs_ul ffs
-#else
-static __inline int
-ffs_ul(u_long ul)
-{
-    u_int n;
-    int i;
-    int k;
-
-    for (i = 0; i < sizeof (u_long) / sizeof (u_int); i++) {
-	n = ul & UINT_MAX;
-	k = ffs (n);
-	if (k)
-	    break;
-	ul >>= (sizeof (u_int) * 8);
-    }
-    if (k)
-	k += i * sizeof (u_int) * 8;
-    return k;
-}
-#endif
-
-/*
  * Extend page directory
  */
 static int
@@ -556,11 +437,9 @@ malloc_init ()
 	    p = b;
 	} else if (i == 1 && issetugid() == 0) {
 	    p = getenv("MALLOC_OPTIONS");
-	} else if (i == 2) {
+	} else {
 	    p = malloc_options;
 	}
-	else
-	    p = NULL;
 	for (; p && *p; p++) {
 	    switch (*p) {
 		case '>': malloc_cache   <<= 1; break;
@@ -604,53 +483,10 @@ malloc_init ()
     if (malloc_zero)
 	malloc_junk=1;
 
-#ifdef EXTRA_SANITY
+#ifdef MALLOC_STATS
     if (malloc_stats)
 	atexit(malloc_exit);
-#endif /* EXTRA_SANITY */
-
-#ifndef malloc_pagesize
-    /* determine our pagesize */
-    malloc_pagesize = getpagesize();
-#endif /* malloc_pagesize */
-
-#ifndef malloc_maxsize
-    malloc_maxsize = malloc_pagesize >> 1;
-#endif /* malloc_maxsize */
-
-#ifndef malloc_pageshift
-    {
-    int i;
-    /* determine how much we shift by to get there */
-    for (i = malloc_pagesize; i > 1; i >>= 1)
-	malloc_pageshift++;
-    }
-#endif /* malloc_pageshift */
-
-#ifndef malloc_minsize
-    {
-    int i;
-    /*
-     * find the smallest size allocation we will bother about.
-     * this is determined as the smallest allocation that can hold
-     * it's own pginfo;
-     */
-    i = 2;
-    for(;;) {
-	int j;
-
-	/* Figure out the size of the bits */
-	j = malloc_pagesize/i;
-	j /= 8;
-	if (j < sizeof(u_long))
-		j = sizeof (u_long);
-	if (sizeof(struct pginfo) + j - sizeof (u_long) <= i)
-		break;
-	i += i;
-    }
-    malloc_minsize = i;
-    }
-#endif /* malloc_minsize */
+#endif /* MALLOC_STATS */
 
     /* Allocate one page for the page directory */
     page_dir = (struct pginfo **) mmap(0, malloc_pagesize, PROT_READ|PROT_WRITE,
@@ -668,7 +504,14 @@ malloc_init ()
     malloc_ninfo = malloc_pagesize / sizeof *page_dir;
 
     /* Been here, done that */
-    initialized++;
+    malloc_started++;
+
+    /* Recalculate the cache size in bytes, and make sure it's nonzero */
+
+    if (!malloc_cache)
+	malloc_cache++;
+
+    malloc_cache <<= malloc_pageshift;
 
     /*
      * This is a nice hack from Kaleb Keithly (kaleb@x.org).
@@ -676,16 +519,12 @@ malloc_init ()
      */
     px = (struct pgfree *) imalloc (sizeof *px);
 
-    if (!malloc_cache)
-	malloc_cache++;
-
-    malloc_cache <<= malloc_pageshift;
 }
 
 /*
  * Allocate a number of complete pages
  */
-void *
+static void *
 malloc_pages(size)
     size_t size;
 {
@@ -771,7 +610,7 @@ malloc_pages(size)
  * Allocate a page of fragments
  */
 
-static __inline int
+static __inline__ int
 malloc_make_chunks(bits)
     int bits;
 {
@@ -794,8 +633,10 @@ malloc_make_chunks(bits)
 	bp = (struct  pginfo *)pp;
     } else {
 	bp = (struct  pginfo *)imalloc(l);
-	if (!bp)
+	if (!bp) {
+	    ifree(pp);
 	    return 0;
+	}
     }
 
     bp->size = (1UL<<bits);
@@ -803,12 +644,7 @@ malloc_make_chunks(bits)
     bp->total = bp->free = malloc_pagesize >> bits;
     bp->page = pp;
 
-    page_dir[ptr2index(pp)] = bp;
-
-    bp->next = page_dir[bits];
-    page_dir[bits] = bp;
-
-    /* set all valid bits in the bits */
+    /* set all valid bits in the bitmap */
     k = bp->total;
     i = 0;
 
@@ -817,18 +653,27 @@ malloc_make_chunks(bits)
 	bp->bits[i / MALLOC_BITS] = (u_long)~0;
 
     for(; i < k; i++)
-	set_bit(bp, i);
+        bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
 
     if (bp == bp->page) {
 	/* Mark the ones we stole for ourselves */
 	for(i=0;l > 0;i++) {
-	    clr_bit(bp, i);
+	    bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS));
 	    bp->free--;
 	    bp->total--;
 	    l -= (1 << bits);
 	}
     }
 
+    /* MALLOC_LOCK */
+
+    page_dir[ptr2index(pp)] = bp;
+
+    bp->next = page_dir[bits];
+    page_dir[bits] = bp;
+
+    /* MALLOC_UNLOCK */
+
     return 1;
 }
 
@@ -839,17 +684,21 @@ static void *
 malloc_bytes(size)
     size_t size;
 {
-    int j;
+    int i,j;
+    u_int u;
     struct  pginfo *bp;
     int k;
-    u_long *lp;
+    u_int *lp;
 
     /* Don't bother with anything less than this */
     if (size < malloc_minsize)
 	size = malloc_minsize;
 
     /* Find the right bucket */
-    j = fls((size)-1);
+    j = 1;
+    i = size-1;
+    while (i >>= 1)
+	j++;
 
     /* If it's empty, make a page more of that size chunks */
     if (!page_dir[j] && !malloc_make_chunks(j))
@@ -862,8 +711,13 @@ malloc_bytes(size)
 	;
 
     /* Find that bit, and tweak it */
-    k = ffs_ul(*lp) - 1;
-    *lp ^= 1UL<<k;
+    u = 1;
+    k = 0;
+    while (!(*lp & u)) {
+	u += u;
+	k++;
+    }
+    *lp ^= u;
 
     /* If there are no more free, remove from free-list */
     if (!--bp->free) {
@@ -878,7 +732,7 @@ malloc_bytes(size)
     if (malloc_junk)
 	memset((char *)bp->page + k, SOME_JUNK, bp->size);
 
-    return (void *)((char *)bp->page + k);
+    return (u_char *)bp->page + k;
 }
 
 /*
@@ -893,7 +747,7 @@ imalloc(size)
     int     status;
 #endif
 
-    if (!initialized)
+    if (!malloc_started)
 	malloc_init();
 
     if (suicide)
@@ -907,7 +761,7 @@ imalloc(size)
     if (malloc_abort && !result)
 	wrterror("allocation failed.\n");
 
-    if (malloc_zero)
+    if (malloc_zero && result)
 	memset(result, 0, size);
 
     return result;
@@ -932,7 +786,7 @@ irealloc(ptr, size)
     if (suicide)
 	return 0;
 
-    if (!initialized) {
+    if (!malloc_started) {
 	wrtwarning("malloc() has never been called.\n");
 	return 0;
     }
@@ -981,7 +835,7 @@ irealloc(ptr, size)
 	i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
 
 	/* Verify that it isn't a free chunk already */
-	if (tst_bit(*mp, i)) {
+        if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
 	    wrtwarning("chunk is already free.\n");
 	    return 0;
 	}
@@ -1017,7 +871,7 @@ irealloc(ptr, size)
  * Free a sequence of pages
  */
 
-static __inline void
+static __inline__ void
 free_pages(ptr, index, info)
     void *ptr;
     int index;
@@ -1050,6 +904,9 @@ free_pages(ptr, index, info)
 
     l = i << malloc_pageshift;
 
+    if (malloc_junk)
+	memset(ptr, SOME_JUNK, l);
+
 #ifdef __FreeBSD__
     if (malloc_hint)
 	madvise(ptr, l, MADV_FREE);
@@ -1150,7 +1007,7 @@ free_pages(ptr, index, info)
  */
 
 /* ARGSUSED */
-static __inline void
+static __inline__ void
 free_bytes(ptr, index, info)
     void *ptr;
     int index;
@@ -1168,12 +1025,15 @@ free_bytes(ptr, index, info)
 	return;
     }
 
-    if (tst_bit(info, i)) {
+    if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
 	wrtwarning("chunk is already free.\n");
 	return;
     }
 
-    set_bit(info, i);
+    if (malloc_junk)
+	memset(ptr, SOME_JUNK, info->size);
+
+    info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
     info->free++;
 
     mp = page_dir + info->shift;
@@ -1226,7 +1086,7 @@ ifree(ptr)
     if (!ptr)
 	return;
 
-    if (!initialized) {
+    if (!malloc_started) {
 	wrtwarning("malloc() has never been called.\n");
 	return;
     }
@@ -1265,7 +1125,7 @@ ifree(ptr)
 #include "pthread_private.h"
 static int malloc_lock;
 #define THREAD_LOCK() _thread_kern_sig_block(&malloc_lock);
-#define THREAD_UNLOCK() _thread_kern_sig_unblock(&malloc_lock);
+#define THREAD_UNLOCK() _thread_kern_sig_unblock(malloc_lock);
 #else
 #define THREAD_LOCK() 
 #define THREAD_UNLOCK()
@@ -1278,7 +1138,7 @@ malloc(size_t size)
 {
     register void *r;
 
-    malloc_func = "malloc():";
+    malloc_func = " in malloc():";
     THREAD_LOCK();
     if (malloc_active++) {
 	wrtwarning("recursive call.\n");
@@ -1295,7 +1155,7 @@ malloc(size_t size)
 void
 free(void *ptr)
 {
-    malloc_func = "free():";
+    malloc_func = " in free():";
     THREAD_LOCK();
     if (malloc_active++) {
 	wrtwarning("recursive call.\n");
@@ -1314,7 +1174,7 @@ realloc(void *ptr, size_t size)
 {
     register void *r;
 
-    malloc_func = "realloc():";
+    malloc_func = " in realloc():";
     THREAD_LOCK();
     if (malloc_active++) {
 	wrtwarning("recursive call.\n");