malloc.c

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