BSD 4_4 release

[unix-history] / usr / src / lib / libc / stdlib / malloc.c

diff --git a/usr/src/lib/libc/stdlib/malloc.c b/usr/src/lib/libc/stdlib/malloc.c
index f0037a6..ea8f092 100644 (file)
--- a/usr/src/lib/libc/stdlib/malloc.c
+++ b/usr/src/lib/libc/stdlib/malloc.c
@@ -1,6 +1,39 @@
-#ifndef lint
-static char sccsid[] = "@(#)malloc.c   4.5 (Berkeley) %G%";
-#endif
+/*
+ * Copyright (c) 1983, 1993
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *     This product includes software developed by the University of
+ *     California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)malloc.c   8.1 (Berkeley) 6/4/93";
+#endif /* LIBC_SCCS and not lint */

 
 /*
  * malloc.c (Caltech) 2/21/82
 
 /*
  * malloc.c (Caltech) 2/21/82


@@ -9,35 +42,38 @@ static char sccsid[] = "@(#)malloc.c 4.5 (Berkeley) %G%";
  * This is a very fast storage allocator.  It allocates blocks of a small 
  * number of different sizes, and keeps free lists of each size.  Blocks that
  * don't exactly fit are passed up to the next larger size.  In this 
  * This is a very fast storage allocator.  It allocates blocks of a small 
  * number of different sizes, and keeps free lists of each size.  Blocks that
  * don't exactly fit are passed up to the next larger size.  In this 

- * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
- * This is designed for use in a program that uses vast quantities of memory,
- * but bombs when it runs out. 
+ * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
+ * This is designed for use in a virtual memory environment.

  */
 
 #include <sys/types.h>
  */
 
 #include <sys/types.h>

+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>

 
 #define        NULL 0
 
 
 #define        NULL 0
 

+static void morecore();
+static int findbucket();
+

 /*
  * The overhead on a block is at least 4 bytes.  When free, this space
  * contains a pointer to the next free block, and the bottom two bits must
  * be zero.  When in use, the first byte is set to MAGIC, and the second
  * byte is the size index.  The remaining bytes are for alignment.
 /*
  * The overhead on a block is at least 4 bytes.  When free, this space
  * contains a pointer to the next free block, and the bottom two bits must
  * be zero.  When in use, the first byte is set to MAGIC, and the second
  * byte is the size index.  The remaining bytes are for alignment.

- * If range checking is enabled and the size of the block fits
- * in two bytes, then the top two bytes hold the size of the requested block
- * plus the range checking words, and the header word MINUS ONE.
+ * If range checking is enabled then a second word holds the size of the
+ * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
+ * The order of elements is critical: ov_magic must overlay the low order
+ * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.

  */
 union  overhead {
        union   overhead *ov_next;      /* when free */
        struct {
  */
 union  overhead {
        union   overhead *ov_next;      /* when free */
        struct {

-#ifndef RCHECK
-               u_char  ovu_magic;      /* magic number */
-               u_char  ovu_index;      /* bucket # */
-#else
-               u_int   ovu_size;       /* actual block size */

                u_char  ovu_magic;      /* magic number */
                u_char  ovu_index;      /* bucket # */
                u_char  ovu_magic;      /* magic number */
                u_char  ovu_index;      /* bucket # */

+#ifdef RCHECK

                u_short ovu_rmagic;     /* range magic number */
                u_short ovu_rmagic;     /* range magic number */

+               u_int   ovu_size;       /* actual block size */

 #endif
        } ovu;
 #define        ov_magic        ovu.ovu_magic
 #endif
        } ovu;
 #define        ov_magic        ovu.ovu_magic


@@ -76,27 +112,28 @@ static     u_int nmalloc[NBUCKETS];
 #include <stdio.h>
 #endif
 
 #include <stdio.h>
 #endif
 

-#ifdef DEBUG
+#if defined(DEBUG) || defined(RCHECK)

 #define        ASSERT(p)   if (!(p)) botch("p")
 #define        ASSERT(p)   if (!(p)) botch("p")

+#include <stdio.h>

 static
 botch(s)
        char *s;
 {
 static
 botch(s)
        char *s;
 {

-
-       printf("assertion botched: %s\n", s);
+       fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
+       (void) fflush(stderr);          /* just in case user buffered it */

        abort();
 }
 #else
 #define        ASSERT(p)
 #endif
 
        abort();
 }
 #else
 #define        ASSERT(p)
 #endif
 

-char *
+void *

 malloc(nbytes)
 malloc(nbytes)

-       unsigned nbytes;
+       size_t nbytes;

 {
        register union overhead *op;
 {
        register union overhead *op;

-       register int bucket;
-       register unsigned amt, n;
+       register int bucket, n;
+       register unsigned amt;

 
        /*
         * First time malloc is called, setup page size and
 
        /*
         * First time malloc is called, setup page size and


@@ -140,6 +177,8 @@ malloc(nbytes)
        }
        while (nbytes > amt + n) {
                amt <<= 1;
        }
        while (nbytes > amt + n) {
                amt <<= 1;

+               if (amt == 0)
+                       return (NULL);

                bucket++;
        }
        /*
                bucket++;
        }
        /*


@@ -163,9 +202,9 @@ malloc(nbytes)
         * Record allocated size of block and
         * bound space with magic numbers.
         */
         * Record allocated size of block and
         * bound space with magic numbers.
         */

-       op->ov_size = nbytes;
+       op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);

        op->ov_rmagic = RMAGIC;
        op->ov_rmagic = RMAGIC;

-       *(u_short *)((caddr_t)(op + 1) + nbytes) = RMAGIC;
+       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;

 #endif
        return ((char *)(op + 1));
 }
 #endif
        return ((char *)(op + 1));
 }


@@ -173,16 +212,26 @@ malloc(nbytes)
 /*
  * Allocate more memory to the indicated bucket.
  */
 /*
  * Allocate more memory to the indicated bucket.
  */

-static
+static void

 morecore(bucket)
        int bucket;
 {
        register union overhead *op;
        register int sz;                /* size of desired block */
 morecore(bucket)
        int bucket;
 {
        register union overhead *op;
        register int sz;                /* size of desired block */

-       register int amt;               /* amount to allocate */
-       register int nblks;             /* how many blocks we get */
+       int amt;                        /* amount to allocate */
+       int nblks;                      /* how many blocks we get */

 
 

+       /*
+        * sbrk_size <= 0 only for big, FLUFFY, requests (about
+        * 2^30 bytes on a VAX, I think) or for a negative arg.
+        */

        sz = 1 << (bucket + 3);
        sz = 1 << (bucket + 3);

+#ifdef DEBUG
+       ASSERT(sz > 0);
+#else
+       if (sz <= 0)
+               return;
+#endif

        if (sz < pagesz) {
                amt = pagesz;
                nblks = amt / sz;
        if (sz < pagesz) {
                amt = pagesz;
                nblks = amt / sz;


@@ -205,8 +254,9 @@ morecore(bucket)
        }
 }
 
        }
 }
 

+void

 free(cp)
 free(cp)

-       char *cp;
+       void *cp;

 {   
        register int size;
        register union overhead *op;
 {   
        register int size;
        register union overhead *op;


@@ -226,7 +276,7 @@ free(cp)
 #endif
        size = op->ov_index;
        ASSERT(size < NBUCKETS);
 #endif
        size = op->ov_index;
        ASSERT(size < NBUCKETS);

-       op->ov_next = nextf[size];
+       op->ov_next = nextf[size];      /* also clobbers ov_magic */

        nextf[size] = op;
 #ifdef MSTATS
        nmalloc[size]--;
        nextf[size] = op;
 #ifdef MSTATS
        nmalloc[size]--;


@@ -240,18 +290,19 @@ free(cp)
  * back.  We have to search all the free lists for the block in order
  * to determine its bucket: 1st we make one pass thru the lists
  * checking only the first block in each; if that fails we search
  * back.  We have to search all the free lists for the block in order
  * to determine its bucket: 1st we make one pass thru the lists
  * checking only the first block in each; if that fails we search

- * ``realloc_srchlen'' blocks in each list for a match (the variable
+ * ``__realloc_srchlen'' blocks in each list for a match (the variable

  * is extern so the caller can modify it).  If that fails we just copy
  * however many bytes was given to realloc() and hope it's not huge.
  */
  * is extern so the caller can modify it).  If that fails we just copy
  * however many bytes was given to realloc() and hope it's not huge.
  */

-int realloc_srchlen = 4;       /* 4 should be plenty, -1 =>'s whole list */
+int __realloc_srchlen = 4;     /* 4 should be plenty, -1 =>'s whole list */

 
 

-char *
+void *

 realloc(cp, nbytes)
 realloc(cp, nbytes)

-       char *cp; 
-       unsigned nbytes;
+       void *cp; 
+       size_t nbytes;

 {   
 {   

-       register u_int onb, i;
+       register u_int onb;
+       register int i;

        union overhead *op;
        char *res;
        int was_alloced = 0;
        union overhead *op;
        char *res;
        int was_alloced = 0;


@@ -269,18 +320,17 @@ realloc(cp, nbytes)
                 * Search for the old block of memory on the
                 * free list.  First, check the most common
                 * case (last element free'd), then (this failing)
                 * Search for the old block of memory on the
                 * free list.  First, check the most common
                 * case (last element free'd), then (this failing)

-                * the last ``realloc_srchlen'' items free'd.
+                * the last ``__realloc_srchlen'' items free'd.

                 * If all lookups fail, then assume the size of
                 * the memory block being realloc'd is the
                 * If all lookups fail, then assume the size of
                 * the memory block being realloc'd is the

-                * smallest possible.
+                * largest possible (so that all "nbytes" of new
+                * memory are copied into).  Note that this could cause
+                * a memory fault if the old area was tiny, and the moon
+                * is gibbous.  However, that is very unlikely.

                 */
                if ((i = findbucket(op, 1)) < 0 &&
                 */
                if ((i = findbucket(op, 1)) < 0 &&

-                   (i = findbucket(op, realloc_srchlen)) < 0)
-#ifndef RCHECK
-                       i = 0;
-#else
-                       i = 1;  /* smallest possible w/ RCHECK */
-#endif
+                   (i = findbucket(op, __realloc_srchlen)) < 0)
+                       i = NBUCKETS;

        }
        onb = 1 << (i + 3);
        if (onb < pagesz)
        }
        onb = 1 << (i + 3);
        if (onb < pagesz)


@@ -298,7 +348,7 @@ realloc(cp, nbytes)
                }
                if (nbytes <= onb && nbytes > i) {
 #ifdef RCHECK
                }
                if (nbytes <= onb && nbytes > i) {
 #ifdef RCHECK

-                       op->ov_size = nbytes;
+                       op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);

                        *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
 #endif
                        return(cp);
                        *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
 #endif
                        return(cp);


@@ -307,7 +357,7 @@ realloc(cp, nbytes)
        }
        if ((res = malloc(nbytes)) == NULL)
                return (NULL);
        }
        if ((res = malloc(nbytes)) == NULL)
                return (NULL);

-       if (cp != res)                  /* common optimization */
+       if (cp != res)          /* common optimization if "compacting" */

                bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
        return (res);
 }
                bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
        return (res);
 }