malloc.c

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