malloc.c

   1 /* $Header: malloc.c,v 2.0 88/06/05 00:09:16 root Exp $
   2  *
   3  * $Log:        malloc.c,v $
   4  * Revision 2.0  88/06/05  00:09:16  root
   5  * Baseline version 2.0.
   6  *
   7  */
   8
   9 #ifndef lint
  10 static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
  11 #endif
  12
  13 #define RCHECK
  14 /*
  15  * malloc.c (Caltech) 2/21/82
  16  * Chris Kingsley, kingsley@cit-20.
  17  *
  18  * This is a very fast storage allocator.  It allocates blocks of a small
  19  * number of different sizes, and keeps free lists of each size.  Blocks that
  20  * don't exactly fit are passed up to the next larger size.  In this
  21  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  22  * This is designed for use in a program that uses vast quantities of memory,
  23  * but bombs when it runs out.
  24  */
  25
  26 #include "EXTERN.h"
  27 #include "perl.h"
  28
  29 /* I don't much care whether these are defined in sys/types.h--LAW */
  30
  31 #define u_char unsigned char
  32 #define u_int unsigned int
  33 #define u_short unsigned short
  34
  35 /*
  36  * The overhead on a block is at least 4 bytes.  When free, this space
  37  * contains a pointer to the next free block, and the bottom two bits must
  38  * be zero.  When in use, the first byte is set to MAGIC, and the second
  39  * byte is the size index.  The remaining bytes are for alignment.
  40  * If range checking is enabled and the size of the block fits
  41  * in two bytes, then the top two bytes hold the size of the requested block
  42  * plus the range checking words, and the header word MINUS ONE.
  43  */
  44 union   overhead {
  45         union   overhead *ov_next;      /* when free */
  46         struct {
  47                 u_char  ovu_magic;      /* magic number */
  48                 u_char  ovu_index;      /* bucket # */
  49 #ifdef RCHECK
  50                 u_short ovu_size;       /* actual block size */
  51                 u_int   ovu_rmagic;     /* range magic number */
  52 #endif
  53         } ovu;
  54 #define ov_magic        ovu.ovu_magic
  55 #define ov_index        ovu.ovu_index
  56 #define ov_size         ovu.ovu_size
  57 #define ov_rmagic       ovu.ovu_rmagic
  58 };
  59
  60 #define MAGIC           0xff            /* magic # on accounting info */
  61 #define OLDMAGIC        0x7f            /* same after a free() */
  62 #define RMAGIC          0x55555555      /* magic # on range info */
  63 #ifdef RCHECK
  64 #define RSLOP           sizeof (u_int)
  65 #else
  66 #define RSLOP           0
  67 #endif
  68
  69 /*
  70  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  71  * smallest allocatable block is 8 bytes.  The overhead information
  72  * precedes the data area returned to the user.
  73  */
  74 #define NBUCKETS 30
  75 static  union overhead *nextf[NBUCKETS];
  76 extern  char *sbrk();
  77
  78 #ifdef MSTATS
  79 /*
  80  * nmalloc[i] is the difference between the number of mallocs and frees
  81  * for a given block size.
  82  */
  83 static  u_int nmalloc[NBUCKETS];
  84 #include <stdio.h>
  85 #endif
  86
  87 #ifdef debug
  88 #define ASSERT(p)   if (!(p)) botch("p"); else
  89 static
  90 botch(s)
  91         char *s;
  92 {
  93
  94         printf("assertion botched: %s\n", s);
  95         abort();
  96 }
  97 #else
  98 #define ASSERT(p)
  99 #endif
 100
 101 char *
 102 malloc(nbytes)
 103         register unsigned nbytes;
 104 {
 105         register union overhead *p;
 106         register int bucket = 0;
 107         register unsigned shiftr;
 108
 109         /*
 110          * Convert amount of memory requested into
 111          * closest block size stored in hash buckets
 112          * which satisfies request.  Account for
 113          * space used per block for accounting.
 114          */
 115         nbytes += sizeof (union overhead) + RSLOP;
 116         nbytes = (nbytes + 3) &~ 3;
 117         shiftr = (nbytes - 1) >> 2;
 118         /* apart from this loop, this is O(1) */
 119         while (shiftr >>= 1)
 120                 bucket++;
 121         /*
 122          * If nothing in hash bucket right now,
 123          * request more memory from the system.
 124          */
 125         if (nextf[bucket] == NULL)
 126                 morecore(bucket);
 127         if ((p = (union overhead *)nextf[bucket]) == NULL)
 128                 return (NULL);
 129         /* remove from linked list */
 130         if (*((int*)p) > 0x10000000)
 131             fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
 132         nextf[bucket] = nextf[bucket]->ov_next;
 133         p->ov_magic = MAGIC;
 134         p->ov_index= bucket;
 135 #ifdef MSTATS
 136         nmalloc[bucket]++;
 137 #endif
 138 #ifdef RCHECK
 139         /*
 140          * Record allocated size of block and
 141          * bound space with magic numbers.
 142          */
 143         if (nbytes <= 0x10000)
 144                 p->ov_size = nbytes - 1;
 145         p->ov_rmagic = RMAGIC;
 146         *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
 147 #endif
 148         return ((char *)(p + 1));
 149 }
 150
 151 /*
 152  * Allocate more memory to the indicated bucket.
 153  */
 154 static
 155 morecore(bucket)
 156         register bucket;
 157 {
 158         register union overhead *op;
 159         register int rnu;       /* 2^rnu bytes will be requested */
 160         register int nblks;     /* become nblks blocks of the desired size */
 161         register int siz;
 162
 163         if (nextf[bucket])
 164                 return;
 165         /*
 166          * Insure memory is allocated
 167          * on a page boundary.  Should
 168          * make getpageize call?
 169          */
 170         op = (union overhead *)sbrk(0);
 171         if ((int)op & 0x3ff)
 172                 sbrk(1024 - ((int)op & 0x3ff));
 173         /* take 2k unless the block is bigger than that */
 174         rnu = (bucket <= 8) ? 11 : bucket + 3;
 175         nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
 176         if (rnu < bucket)
 177                 rnu = bucket;
 178         op = (union overhead *)sbrk(1 << rnu);
 179         /* no more room! */
 180         if ((int)op == -1)
 181                 return;
 182         /*
 183          * Round up to minimum allocation size boundary
 184          * and deduct from block count to reflect.
 185          */
 186         if ((int)op & 7) {
 187                 op = (union overhead *)(((int)op + 8) &~ 7);
 188                 nblks--;
 189         }
 190         /*
 191          * Add new memory allocated to that on
 192          * free list for this hash bucket.
 193          */
 194         nextf[bucket] = op;
 195         siz = 1 << (bucket + 3);
 196         while (--nblks > 0) {
 197                 op->ov_next = (union overhead *)((caddr_t)op + siz);
 198                 op = (union overhead *)((caddr_t)op + siz);
 199         }
 200 }
 201
 202 free(cp)
 203         char *cp;
 204 {
 205         register int size;
 206         register union overhead *op;
 207
 208         if (cp == NULL)
 209                 return;
 210         op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 211 #ifdef debug
 212         ASSERT(op->ov_magic == MAGIC);          /* make sure it was in use */
 213 #else
 214         if (op->ov_magic != MAGIC) {
 215                 fprintf(stderr,"%s free() ignored\n",
 216                     op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
 217                 return;                         /* sanity */
 218         }
 219         op->ov_magic = OLDMAGIC;
 220 #endif
 221 #ifdef RCHECK
 222         ASSERT(op->ov_rmagic == RMAGIC);
 223         if (op->ov_index <= 13)
 224                 ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
 225 #endif
 226         ASSERT(op->ov_index < NBUCKETS);
 227         size = op->ov_index;
 228         op->ov_next = nextf[size];
 229         nextf[size] = op;
 230 #ifdef MSTATS
 231         nmalloc[size]--;
 232 #endif
 233 }
 234
 235 /*
 236  * When a program attempts "storage compaction" as mentioned in the
 237  * old malloc man page, it realloc's an already freed block.  Usually
 238  * this is the last block it freed; occasionally it might be farther
 239  * back.  We have to search all the free lists for the block in order
 240  * to determine its bucket: 1st we make one pass thru the lists
 241  * checking only the first block in each; if that fails we search
 242  * ``reall_srchlen'' blocks in each list for a match (the variable
 243  * is extern so the caller can modify it).  If that fails we just copy
 244  * however many bytes was given to realloc() and hope it's not huge.
 245  */
 246 int reall_srchlen = 4;  /* 4 should be plenty, -1 =>'s whole list */
 247
 248 char *
 249 realloc(cp, nbytes)
 250         char *cp;
 251         unsigned nbytes;
 252 {
 253         register u_int onb;
 254         union overhead *op;
 255         char *res;
 256         register int i;
 257         int was_alloced = 0;
 258
 259         if (cp == NULL)
 260                 return (malloc(nbytes));
 261         op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
 262         if (op->ov_magic == MAGIC) {
 263                 was_alloced++;
 264                 i = op->ov_index;
 265         } else {
 266                 /*
 267                  * Already free, doing "compaction".
 268                  *
 269                  * Search for the old block of memory on the
 270                  * free list.  First, check the most common
 271                  * case (last element free'd), then (this failing)
 272                  * the last ``reall_srchlen'' items free'd.
 273                  * If all lookups fail, then assume the size of
 274                  * the memory block being realloc'd is the
 275                  * smallest possible.
 276                  */
 277                 if ((i = findbucket(op, 1)) < 0 &&
 278                     (i = findbucket(op, reall_srchlen)) < 0)
 279                         i = 0;
 280         }
 281         onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
 282         /* avoid the copy if same size block */
 283         if (was_alloced &&
 284             nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
 285                 return(cp);
 286         if ((res = malloc(nbytes)) == NULL)
 287                 return (NULL);
 288         if (cp != res)                  /* common optimization */
 289                 bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
 290         if (was_alloced)
 291                 free(cp);
 292         return (res);
 293 }
 294
 295 /*
 296  * Search ``srchlen'' elements of each free list for a block whose
 297  * header starts at ``freep''.  If srchlen is -1 search the whole list.
 298  * Return bucket number, or -1 if not found.
 299  */
 300 static
 301 findbucket(freep, srchlen)
 302         union overhead *freep;
 303         int srchlen;
 304 {
 305         register union overhead *p;
 306         register int i, j;
 307
 308         for (i = 0; i < NBUCKETS; i++) {
 309                 j = 0;
 310                 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
 311                         if (p == freep)
 312                                 return (i);
 313                         j++;
 314                 }
 315         }
 316         return (-1);
 317 }
 318
 319 #ifdef MSTATS
 320 /*
 321  * mstats - print out statistics about malloc
 322  *
 323  * Prints two lines of numbers, one showing the length of the free list
 324  * for each size category, the second showing the number of mallocs -
 325  * frees for each size category.
 326  */
 327 mstats(s)
 328         char *s;
 329 {
 330         register int i, j;
 331         register union overhead *p;
 332         int totfree = 0,
 333         totused = 0;
 334
 335         fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
 336         for (i = 0; i < NBUCKETS; i++) {
 337                 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
 338                         ;
 339                 fprintf(stderr, " %d", j);
 340                 totfree += j * (1 << (i + 3));
 341         }
 342         fprintf(stderr, "\nused:\t");
 343         for (i = 0; i < NBUCKETS; i++) {
 344                 fprintf(stderr, " %d", nmalloc[i]);
 345                 totused += nmalloc[i] * (1 << (i + 3));
 346         }
 347         fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
 348             totused, totfree);
 349 }
 350 #endif