malloc.c

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