malloc.c

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