malloc.c

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