x2p/malloc.c

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