2.11BSD#431 - /usr/src/bin/tcsh/tc.alloc.c

   1: /*
   2:  * tc.alloc.c (Caltech) 2/21/82
   3:  * Chris Kingsley, kingsley@cit-20.
   4:  *
   5:  * This is a very fast storage allocator.  It allocates blocks of a small
   6:  * number of different sizes, and keeps free lists of each size.  Blocks that
   7:  * don't exactly fit are passed up to the next larger size.  In this
   8:  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
   9:  * This is designed for use in a program that uses vast quantities of memory,
  10:  * but bombs when it runs out.
  11:  */
  12: /*-
  13:  * Copyright (c) 1980, 1991 The Regents of the University of California.
  14:  * All rights reserved.
  15:  *
  16:  * Redistribution and use in source and binary forms, with or without
  17:  * modification, are permitted provided that the following conditions
  18:  * are met:
  19:  * 1. Redistributions of source code must retain the above copyright
  20:  *    notice, this list of conditions and the following disclaimer.
  21:  * 2. Redistributions in binary form must reproduce the above copyright
  22:  *    notice, this list of conditions and the following disclaimer in the
  23:  *    documentation and/or other materials provided with the distribution.
  24:  * 3. All advertising materials mentioning features or use of this software
  25:  *    must display the following acknowledgement:
  26:  *	This product includes software developed by the University of
  27:  *	California, Berkeley and its contributors.
  28:  * 4. Neither the name of the University nor the names of its contributors
  29:  *    may be used to endorse or promote products derived from this software
  30:  *    without specific prior written permission.
  31:  *
  32:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  33:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  34:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  35:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  36:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  37:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  38:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  39:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  40:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  41:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  42:  * SUCH DAMAGE.
  43:  */
  44: #include "config.h"
  45: #if !defined(lint) && !defined(pdp11)
  46: static char *rcsid()
  47:     { return "$Id: tc.alloc.c,v 3.0.1 1996/04/04 21:49:28 sms Exp $"; }
  48: #endif
  49: 
  50: 
  51: #include "sh.h"
  52: 
  53: char   *memtop = NULL;      /* PWP: top of current memory */
  54: char   *membot = NULL;      /* PWP: bottom of allocatable memory */
  55: 
  56: #ifndef SYSMALLOC
  57: 
  58: #define RCHECK
  59: #define DEBUG
  60: 
  61: 
  62: #ifndef NULL
  63: #define NULL 0
  64: #endif
  65: 
  66: typedef unsigned char U_char;   /* we don't really have signed chars */
  67: #ifdef  pdp11
  68: typedef u_long U_int;
  69: #else
  70: typedef unsigned int U_int;
  71: #endif
  72: typedef unsigned short U_short;
  73: 
  74: 
  75: /*
  76:  * The overhead on a block is at least 4 bytes.  When free, this space
  77:  * contains a pointer to the next free block, and the bottom two bits must
  78:  * be zero.  When in use, the first byte is set to MAGIC, and the second
  79:  * byte is the size index.  The remaining bytes are for alignment.
  80:  * If range checking is enabled and the size of the block fits
  81:  * in two bytes, then the top two bytes hold the size of the requested block
  82:  * plus the range checking words, and the header word MINUS ONE.
  83:  */
  84: 
  85: 
  86: #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP)
  87: 
  88: union overhead {
  89:     union overhead *ov_next;    /* when free */
  90:     struct {
  91:     U_char  ovu_magic;  /* magic number */
  92:     U_char  ovu_index;  /* bucket # */
  93: #ifdef RCHECK
  94:     U_short ovu_size;   /* actual block size */
  95:     U_int   ovu_rmagic; /* range magic number */
  96: #endif
  97:     }       ovu;
  98: #define ov_magic    ovu.ovu_magic
  99: #define ov_index    ovu.ovu_index
 100: #define ov_size     ovu.ovu_size
 101: #define ov_rmagic   ovu.ovu_rmagic
 102: };
 103: 
 104: #define MAGIC       0xfd    /* magic # on accounting info */
 105: #define RMAGIC      0x55555555  /* magic # on range info */
 106: #ifdef RCHECK
 107: #define RSLOP       sizeof (U_int)
 108: #else
 109: #define RSLOP       0
 110: #endif
 111: 
 112: 
 113: #ifdef SUNOS4
 114: /*
 115:  * SunOS localtime() overwrites the 9th byte on an 8 byte malloc()....
 116:  * So we align to 16 bytes...
 117:  */
 118: #define ROUNDUP 15
 119: #else
 120: #define ROUNDUP 7
 121: #endif
 122: 
 123: /*
 124:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
 125:  * smallest allocatable block is 8 bytes.  The overhead information
 126:  * precedes the data area returned to the user.
 127:  */
 128: #define NBUCKETS 30
 129: static union overhead *nextf[NBUCKETS];
 130: 
 131: #ifdef notdef
 132: extern char *sbrk();
 133: 
 134: #endif
 135: 
 136: /*
 137:  * nmalloc[i] is the difference between the number of mallocs and frees
 138:  * for a given block size.
 139:  */
 140: static U_int nmalloc[NBUCKETS];
 141: 
 142: static  int findbucket  __P((union overhead *, int));
 143: static  void    morecore    __P((int));
 144: 
 145: 
 146: #ifdef DEBUG
 147: #define CHECK(a, str, p) \
 148:     if (a) { \
 149:     xprintf(str, p);    \
 150:     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
 151:     abort(); \
 152:     }   \
 153:     else
 154: #else
 155: #define CHECK(a, str, p) \
 156:     if (a) { \
 157:     xprintf(str, p);    \
 158:     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
 159:     return; \
 160:     }   \
 161:     else
 162: #endif
 163: 
 164: memalign_t
 165: malloc(nbytes)
 166:     register size_t nbytes;
 167: {
 168: #ifndef lint
 169:     register union overhead *p;
 170:     register int bucket = 0;
 171:     register unsigned shiftr;
 172: 
 173:     /*
 174:      * Convert amount of memory requested into closest block size stored in
 175:      * hash buckets which satisfies request.  Account for space used per block
 176:      * for accounting.
 177:      */
 178:     nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP);
 179:     shiftr = (nbytes - 1) >> 2;
 180: 
 181:     /* apart from this loop, this is O(1) */
 182:     while (shiftr >>= 1)
 183:     bucket++;
 184:     /*
 185:      * If nothing in hash bucket right now, request more memory from the
 186:      * system.
 187:      */
 188:     if (nextf[bucket] == NULL)
 189:     morecore(bucket);
 190:     if ((p = (union overhead *) nextf[bucket]) == NULL) {
 191:     child++;
 192: #ifndef DEBUG
 193:     stderror(ERR_NOMEM);
 194: #else
 195:     showall();
 196:     xprintf("nbytes=%d: Out of memory\n", nbytes);
 197:     abort();
 198: #endif
 199:     /* fool lint */
 200:     return ((memalign_t) 0);
 201:     }
 202:     /* remove from linked list */
 203:     nextf[bucket] = nextf[bucket]->ov_next;
 204:     p->ov_magic = MAGIC;
 205:     p->ov_index = bucket;
 206:     nmalloc[bucket]++;
 207: #ifdef RCHECK
 208:     /*
 209:      * Record allocated size of block and bound space with magic numbers.
 210:      */
 211:     if (nbytes <= 0x10000)
 212:     p->ov_size = nbytes - 1;
 213:     p->ov_rmagic = RMAGIC;
 214:     *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC;
 215: #endif
 216:     return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead))));
 217: #else
 218:     if (nbytes)
 219:     return ((memalign_t) 0);
 220:     else
 221:     return ((memalign_t) 0);
 222: #endif				/* !lint */
 223: }
 224: 
 225: #ifndef lint
 226: /*
 227:  * Allocate more memory to the indicated bucket.
 228:  */
 229: static void
 230: morecore(bucket)
 231:     register bucket;
 232: {
 233:     register union overhead *op;
 234:     register int rnu;       /* 2^rnu bytes will be requested */
 235:     register int nblks;     /* become nblks blocks of the desired size */
 236:     register int siz;
 237: 
 238:     if (nextf[bucket])
 239:     return;
 240:     /*
 241:      * Insure memory is allocated on a page boundary.  Should make getpageize
 242:      * call?
 243:      */
 244:     op = (union overhead *) sbrk(0);
 245:     memtop = (char *) op;
 246:     if (membot == NULL)
 247:     membot = memtop;
 248:     if ((int) op & 0x3ff) {
 249:     memtop = (char *) sbrk(1024 - ((int) op & 0x3ff));
 250:     memtop += 1024 - ((int) op & 0x3ff);
 251:     }
 252: 
 253:     /* take 2k unless the block is bigger than that */
 254:     rnu = (bucket <= 8) ? 11 : bucket + 3;
 255:     nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
 256:     if (rnu < bucket)
 257:     rnu = bucket;
 258:     memtop = (char *) sbrk(1 << rnu);   /* PWP */
 259:     op = (union overhead *) memtop;
 260:     memtop += 1 << rnu;
 261:     /* no more room! */
 262:     if ((int) op == -1)
 263:     return;
 264:     /*
 265:      * Round up to minimum allocation size boundary and deduct from block count
 266:      * to reflect.
 267:      */
 268:     if (((U_int) op) & ROUNDUP) {
 269:     op = (union overhead *) (((U_int) op + (ROUNDUP + 1)) & ~ROUNDUP);
 270:     nblks--;
 271:     }
 272:     /*
 273:      * Add new memory allocated to that on free list for this hash bucket.
 274:      */
 275:     nextf[bucket] = op;
 276:     siz = 1 << (bucket + 3);
 277:     while (--nblks > 0) {
 278:     op->ov_next = (union overhead *) (((caddr_t) op) + siz);
 279:     op = (union overhead *) (((caddr_t) op) + siz);
 280:     }
 281: }
 282: 
 283: #endif
 284: 
 285: void
 286: free(cp)
 287:     ptr_t   cp;
 288: {
 289: #ifndef lint
 290:     register int size;
 291:     register union overhead *op;
 292: 
 293:     if (cp == NULL)
 294:     return;
 295:     CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp);
 296:     CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp);
 297:     CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp);
 298:     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
 299:     CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp);
 300: 
 301: #ifdef RCHECK
 302:     if (op->ov_index <= 13)
 303:     CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC,
 304:           "free(%lx) bad range check.", cp);
 305: #endif
 306:     CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp);
 307:     size = op->ov_index;
 308:     op->ov_next = nextf[size];
 309:     nextf[size] = op;
 310: 
 311:     nmalloc[size]--;
 312: 
 313: #else
 314:     if (cp == NULL)
 315:     return;
 316: #endif
 317: }
 318: 
 319: memalign_t
 320: calloc(i, j)
 321:     size_t  i, j;
 322: {
 323: #ifndef lint
 324:     register char *cp, *scp;
 325: 
 326:     i *= j;
 327:     scp = cp = (char *) xmalloc((size_t) i);
 328:     if (i != 0)
 329:     do
 330:         *cp++ = 0;
 331:     while (--i);
 332: 
 333:     return (scp);
 334: #else
 335:     if (i && j)
 336:     return ((memalign_t) 0);
 337:     else
 338:     return ((memalign_t) 0);
 339: #endif
 340: }
 341: 
 342: #ifndef lint
 343: /* PWP: a bcopy that does overlapping extents correctly */
 344: static void
 345: mybcopy(from, to, len)
 346:     char   *from, *to;
 347:     register unsigned len;
 348: {
 349:     register char *sp, *dp;
 350: 
 351:     if (from == to)
 352:     return;
 353:     if (from < to) {
 354:     /* len is unsigned, len > 0 is equivalent to len != 0 */
 355:     for (sp = &from[len - 1], dp = &to[len - 1]; len != 0; len--, sp--, dp--)
 356:         *dp = *sp;
 357:     }
 358:     else {
 359:     /* len is unsigned, len > 0 is equivalent to len != 0 */
 360:     for (sp = from, dp = to; len != 0; len--, sp++, dp++)
 361:         *dp = *sp;
 362:     }
 363: }
 364: 
 365: #endif
 366: 
 367: /*
 368:  * When a program attempts "storage compaction" as mentioned in the
 369:  * old malloc man page, it realloc's an already freed block.  Usually
 370:  * this is the last block it freed; occasionally it might be farther
 371:  * back.  We have to search all the free lists for the block in order
 372:  * to determine its bucket: 1st we make one pass thru the lists
 373:  * checking only the first block in each; if that fails we search
 374:  * ``realloc_srchlen'' blocks in each list for a match (the variable
 375:  * is extern so the caller can modify it).  If that fails we just copy
 376:  * however many bytes was given to realloc() and hope it's not huge.
 377:  */
 378: #ifndef lint
 379: int     realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
 380: 
 381: #endif				/* lint */
 382: 
 383: memalign_t
 384: realloc(cp, nbytes)
 385:     ptr_t   cp;
 386:     size_t  nbytes;
 387: {
 388: #ifndef lint
 389:     register U_int onb;
 390:     union overhead *op;
 391:     char   *res;
 392:     register int i;
 393:     int     was_alloced = 0;
 394: 
 395:     if (cp == NULL)
 396:     return (malloc(nbytes));
 397:     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
 398:     if (op->ov_magic == MAGIC) {
 399:     was_alloced++;
 400:     i = op->ov_index;
 401:     }
 402:     else
 403:     /*
 404: 	 * Already free, doing "compaction".
 405: 	 *
 406: 	 * Search for the old block of memory on the free list.  First, check the
 407: 	 * most common case (last element free'd), then (this failing) the last
 408: 	 * ``realloc_srchlen'' items free'd. If all lookups fail, then assume
 409: 	 * the size of the memory block being realloc'd is the smallest
 410: 	 * possible.
 411: 	 */
 412:     if ((i = findbucket(op, 1)) < 0 &&
 413:         (i = findbucket(op, realloc_srchlen)) < 0)
 414:     i = 0;
 415: 
 416:     onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP);
 417: 
 418:     /* avoid the copy if same size block */
 419:     if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2))))
 420:     return ((memalign_t) cp);
 421:     if ((res = malloc(nbytes)) == NULL)
 422:     return (NULL);
 423:     if (cp != res)      /* common optimization */
 424:     mybcopy(cp, res, nbytes);
 425:     if (was_alloced)
 426:     free(cp);
 427:     return (res);
 428: #else
 429:     if (cp && nbytes)
 430:     return ((memalign_t) 0);
 431:     else
 432:     return ((memalign_t) 0);
 433: #endif				/* !lint */
 434: }
 435: 
 436: 
 437: 
 438: #ifndef lint
 439: /*
 440:  * Search ``srchlen'' elements of each free list for a block whose
 441:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
 442:  * Return bucket number, or -1 if not found.
 443:  */
 444: static int
 445: findbucket(freep, srchlen)
 446:     union overhead *freep;
 447:     int     srchlen;
 448: {
 449:     register union overhead *p;
 450:     register int i, j;
 451: 
 452:     for (i = 0; i < NBUCKETS; i++) {
 453:     j = 0;
 454:     for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
 455:         if (p == freep)
 456:         return (i);
 457:         j++;
 458:     }
 459:     }
 460:     return (-1);
 461: }
 462: 
 463: #endif
 464: 
 465: 
 466: #else               /* SYSMALLOC */
 467: 
 468: /**
 469:  ** ``Protected versions'' of malloc, realloc, calloc, and free
 470:  **
 471:  ** On many systems:
 472:  **
 473:  ** 1. malloc(0) is bad
 474:  ** 2. free(0) is bad
 475:  ** 3. realloc(0, n) is bad
 476:  ** 4. realloc(n, 0) is bad
 477:  **
 478:  ** Also we call our error routine if we run out of memory.
 479:  **/
 480: memalign_t
 481: Malloc(n)
 482:     size_t  n;
 483: {
 484:     ptr_t   ptr;
 485: 
 486:     n = n ? n : 1;
 487: 
 488:     if ((ptr = malloc(n)) == (ptr_t) 0) {
 489:     child++;
 490:     stderror(ERR_NOMEM);
 491:     }
 492:     return ((memalign_t) ptr);
 493: }
 494: 
 495: memalign_t
 496: Realloc(p, n)
 497:     ptr_t   p;
 498:     register size_t  n;
 499: {
 500:     ptr_t   ptr;
 501: 
 502:     n = n ? n : 1;
 503:     if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) {
 504:     child++;
 505:     stderror(ERR_NOMEM);
 506:     }
 507:     return ((memalign_t) ptr);
 508: }
 509: 
 510: memalign_t
 511: Calloc(s, n)
 512:     register size_t  s, n;
 513: {
 514:     register char   *sptr;
 515:     ptr_t   ptr;
 516: 
 517:     n *= s;
 518:     n = n ? n : 1;
 519:     if ((ptr = malloc(n)) == (ptr_t) 0) {
 520:     child++;
 521:     stderror(ERR_NOMEM);
 522:     }
 523: 
 524:     sptr = (char *) ptr;
 525:     if (n != 0)
 526:     do
 527:         *sptr++ = 0;
 528:     while (--n);
 529: 
 530:     return ((memalign_t) ptr);
 531: }
 532: 
 533: void
 534: Free(p)
 535:     ptr_t   p;
 536: {
 537:     if (p) {
 538:     free(p);
 539:     /*
 540:  	 * jpn: free() doesn't NULL pointers on all systems
 541: 	 * but tcsh seems to expect it: see sh.c where comment that
 542: 	 * xfree doesn't care if called twice on same pointers,
 543: 	 * and fact that Free here tests pointer before freeing it.
 544:  	 */
 545:     p = NULL;
 546:     }
 547: }
 548: 
 549: #endif				/* SYSMALLOC */
 550: 
 551: #ifndef pdp11
 552: /*
 553:  * mstats - print out statistics about malloc
 554:  *
 555:  * Prints two lines of numbers, one showing the length of the free list
 556:  * for each size category, the second showing the number of mallocs -
 557:  * frees for each size category.
 558:  */
 559: void
 560: showall()
 561: {
 562: #ifndef SYSMALLOC
 563:     register int i, j;
 564:     register union overhead *p;
 565:     int     totfree = 0, totused = 0;
 566: 
 567:     xprintf("tcsh current memory allocation:\nfree:\t");
 568:     for (i = 0; i < NBUCKETS; i++) {
 569:     for (j = 0, p = nextf[i]; p; p = p->ov_next, j++);
 570:     xprintf(" %4d", j);
 571:     totfree += j * (1 << (i + 3));
 572:     }
 573:     xprintf("\nused:\t");
 574:     for (i = 0; i < NBUCKETS; i++) {
 575:     xprintf(" %4d", nmalloc[i]);
 576:     totused += nmalloc[i] * (1 << (i + 3));
 577:     }
 578:     xprintf("\n\tTotal in use: %d, total free: %d\n",
 579:         totused, totfree);
 580:     xprintf("\tAllocated memory from 0x%lx to 0x%lx.  Real top at 0x%lx\n",
 581:         membot, memtop, (char *) sbrk(0));
 582: #else
 583:     xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n",
 584:         (long)membot, (long)(memtop = (char *) sbrk(0)),(long)(memtop - membot));
 585: #endif				/* SYSMALLOC */
 586: }
 587: #endif /* pdp11 */

Defined functions

Defined variables

Defined union's

Defined typedef's

Defined macros