malloc.c

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