malloc.c

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