malloc.c

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