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

##### Functions

    free              X
    malloc            X
    morecore          X
    realloc           X
    showall           X

##### Variables

    realloc_srchlen   X

##### Macros

    ASSERT            X
    MAGIC             X
    NBUCKETS          X
    NULL              X
    RMAGIC            X
    RSLOP             X
    ov_index          X
    ov_magic          X
    ov_rmagic         X
    ov_size           X

##### unions's

    overhead          X

       1: /*
       2:  * Copyright (c) 1983 Regents of the University of California.
       3:  * All rights reserved.  The Berkeley software License Agreement
       4:  * specifies the terms and conditions for redistribution.
       5:  */
       6:
       7: #if !defined(lint) && defined(DOSCCS)
       8: /* From "@(#)malloc.c	5.5 (Berkeley) 2/25/86"; */
       9: static char *sccsid = "@(#)alloc.c	5.3 (Berkeley) 3/29/86";
      10: #endif
      11:
      12: /*
      13:  * malloc.c (Caltech) 2/21/82
      14:  * Chris Kingsley, kingsley@cit-20.
      15:  *
      16:  * This is a very fast storage allocator.  It allocates blocks of a small
      17:  * number of different sizes, and keeps free lists of each size.  Blocks that
      18:  * don't exactly fit are passed up to the next larger size.  In this
      19:  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
      20:  * This is designed for use in a virtual memory environment.
      21:  */
      22:
      23: #include <sys/types.h>
      24:
      25: #define NULL 0
      26:
      27: /*
      28:  * The overhead on a block is at least 4 bytes.  When free, this space
      29:  * contains a pointer to the next free block, and the bottom two bits must
      30:  * be zero.  When in use, the first byte is set to MAGIC, and the second
      31:  * byte is the size index.  The remaining bytes are for alignment.
      32:  * If range checking is enabled then a second word holds the size of the
      33:  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
      34:  * The order of elements is critical: ov_magic must overlay the low order
      35:  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
      36:  */
      37: union   overhead {
      38:     union   overhead *ov_next;  /* when free */
      39:     struct {
      40:         u_char  ovu_magic;  /* magic number */
      41:         u_char  ovu_index;  /* bucket # */
      42: #ifdef RCHECK
      43:         u_short ovu_rmagic; /* range magic number */
      44:         u_int   ovu_size;   /* actual block size */
      45: #endif
      46:     } ovu;
      47: #define ov_magic    ovu.ovu_magic
      48: #define ov_index    ovu.ovu_index
      49: #define ov_rmagic   ovu.ovu_rmagic
      50: #define ov_size     ovu.ovu_size
      51: };
      52:
      53: #define MAGIC       0xef        /* magic # on accounting info */
      54: #define RMAGIC      0x5555      /* magic # on range info */
      55:
      56: #ifdef RCHECK
      57: #define RSLOP       sizeof (u_short)
      58: #else
      59: #define RSLOP       0
      60: #endif
      61:
      62: /*
      63:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
      64:  * smallest allocatable block is 8 bytes.  The overhead information
      65:  * precedes the data area returned to the user.
      66:  */
      67: #define NBUCKETS 30
      68: static  union overhead *nextf[NBUCKETS];
      69: extern  char *sbrk();
      70:
      71: static  int pagesz;         /* page size */
      72: static  int pagebucket;         /* page size bucket */
      73:
      74: /*
      75:  * nmalloc[i] is the difference between the number of mallocs and frees
      76:  * for a given block size.
      77:  */
      78: static  u_int nmalloc[NBUCKETS];
      79:
      80: #if defined(DEBUG) || defined(RCHECK)
      81: #define ASSERT(p)   if (!(p)) botch("p")
      82: static
      83: botch(s)
      84:     char *s;
      85: {
      86:     printf("\r\nassertion botched: %s\r\n", s);
      87:     abort();
      88: }
      89: #else
      90: #define ASSERT(p)
      91: #endif
      92:
      93: char *
      94: malloc(nbytes)
      95:     unsigned nbytes;
      96: {
      97:     register union overhead *op;
      98:     register int bucket;
      99:     register unsigned amt, n;
     100:
     101:     /*
     102: 	 * First time malloc is called, setup page size and
     103: 	 * align break pointer so all data will be page aligned.
     104: 	 */
     105:     if (pagesz == 0) {
     106:         pagesz = n = getpagesize();
     107:         op = (union overhead *)sbrk(0);
     108:         n = n - sizeof (*op) - ((int)op & (n - 1));
     109:         if (n < 0)
     110:             n += pagesz;
     111:         if (n) {
     112:             if (sbrk(n) == (char *)-1)
     113:                 return (NULL);
     114:         }
     115:         bucket = 0;
     116:         amt = 8;
     117:         while (pagesz > amt) {
     118:             amt <<= 1;
     119:             bucket++;
     120:         }
     121:         pagebucket = bucket;
     122:     }
     123:     /*
     124: 	 * Convert amount of memory requested into closest block size
     125: 	 * stored in hash buckets which satisfies request.
     126: 	 * Account for space used per block for accounting.
     127: 	 */
     128:     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
     129: #ifndef RCHECK
     130:         amt = 8;    /* size of first bucket */
     131:         bucket = 0;
     132: #else
     133:         amt = 16;   /* size of first bucket */
     134:         bucket = 1;
     135: #endif
     136:         n = -(sizeof (*op) + RSLOP);
     137:     } else {
     138:         amt = pagesz;
     139:         bucket = pagebucket;
     140:     }
     141:     while (nbytes > amt + n) {
     142:         amt <<= 1;
     143:         if (amt == 0)
     144:             return (NULL);
     145:         bucket++;
     146:     }
     147:     /*
     148: 	 * If nothing in hash bucket right now,
     149: 	 * request more memory from the system.
     150: 	 */
     151:     if ((op = nextf[bucket]) == NULL) {
     152:         morecore(bucket);
     153:         if ((op = nextf[bucket]) == NULL)
     154:             return (NULL);
     155:     }
     156:     /* remove from linked list */
     157:     nextf[bucket] = op->ov_next;
     158:     op->ov_magic = MAGIC;
     159:     op->ov_index = bucket;
     160:     nmalloc[bucket]++;
     161: #ifdef RCHECK
     162:     /*
     163: 	 * Record allocated size of block and
     164: 	 * bound space with magic numbers.
     165: 	 */
     166:     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
     167:     op->ov_rmagic = RMAGIC;
     168:     *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
     169: #endif
     170:     return ((char *)(op + 1));
     171: }
     172:
     173: /*
     174:  * Allocate more memory to the indicated bucket.
     175:  */
     176: morecore(bucket)
     177:     int bucket;
     178: {
     179:     register union overhead *op;
     180:     register int sz;        /* size of desired block */
     181:     int amt;            /* amount to allocate */
     182:     int nblks;          /* how many blocks we get */
     183:
     184:     /*
     185: 	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
     186: 	 * 2^30 bytes on a VAX, I think) or for a negative arg.
     187: 	 */
     188:     sz = 1 << (bucket + 3);
     189: #ifdef DEBUG
     190:     ASSERT(sz > 0);
     191: #else
     192:     if (sz <= 0)
     193:         return;
     194: #endif
     195:     if (sz < pagesz) {
     196:         amt = pagesz;
     197:         nblks = amt / sz;
     198:     } else {
     199:         amt = sz + pagesz;
     200:         nblks = 1;
     201:     }
     202:     op = (union overhead *)sbrk(amt);
     203:     /* no more room! */
     204:     if ((int)op == -1)
     205:         return;
     206:     /*
     207: 	 * Add new memory allocated to that on
     208: 	 * free list for this hash bucket.
     209: 	 */
     210:     nextf[bucket] = op;
     211:     while (--nblks > 0) {
     212:         op->ov_next = (union overhead *)((caddr_t)op + sz);
     213:         op = (union overhead *)((caddr_t)op + sz);
     214:     }
     215: }
     216:
     217: free(cp)
     218:     char *cp;
     219: {
     220:     register int size;
     221:     register union overhead *op;
     222:
     223:     if (cp == NULL)
     224:         return;
     225:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
     226:     /*
     227: 	 * The following botch is because csh tries to free a free block
     228: 	 * when processing the =~ or !~ operators. -- layer@ucbmonet
     229: 	*/
     230: #ifdef CSHbotch /* was DEBUG */
     231:     ASSERT(op->ov_magic == MAGIC);      /* make sure it was in use */
     232: #else
     233:     if (op->ov_magic != MAGIC)
     234:         return;             /* sanity */
     235: #endif
     236: #ifdef RCHECK
     237:     ASSERT(op->ov_rmagic == RMAGIC);
     238:     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
     239: #endif
     240:     size = op->ov_index;
     241:     ASSERT(size < NBUCKETS);
     242:     op->ov_next = nextf[size];  /* also clobbers ov_magic */
     243:     nextf[size] = op;
     244:     nmalloc[size]--;
     245: }
     246:
     247: /*
     248:  * When a program attempts "storage compaction" as mentioned in the
     249:  * old malloc man page, it realloc's an already freed block.  Usually
     250:  * this is the last block it freed; occasionally it might be farther
     251:  * back.  We have to search all the free lists for the block in order
     252:  * to determine its bucket: 1st we make one pass thru the lists
     253:  * checking only the first block in each; if that fails we search
     254:  * ``realloc_srchlen'' blocks in each list for a match (the variable
     255:  * is extern so the caller can modify it).  If that fails we just copy
     256:  * however many bytes was given to realloc() and hope it's not huge.
     257:  */
     258: int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
     259:
     260: char *
     261: realloc(cp, nbytes)
     262:     char *cp;
     263:     unsigned nbytes;
     264: {
     265:     register u_int onb, i;
     266:     union overhead *op;
     267:     char *res;
     268:     int was_alloced = 0;
     269:
     270:     if (cp == NULL)
     271:         return (malloc(nbytes));
     272:     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
     273:     if (op->ov_magic == MAGIC) {
     274:         was_alloced++;
     275:         i = op->ov_index;
     276:     } else {
     277:         /*
     278: 		 * Already free, doing "compaction".
     279: 		 *
     280: 		 * Search for the old block of memory on the
     281: 		 * free list.  First, check the most common
     282: 		 * case (last element free'd), then (this failing)
     283: 		 * the last ``realloc_srchlen'' items free'd.
     284: 		 * If all lookups fail, then assume the size of
     285: 		 * the memory block being realloc'd is the
     286: 		 * largest possible (so that all "nbytes" of new
     287: 		 * memory are copied into).  Note that this could cause
     288: 		 * a memory fault if the old area was tiny, and the moon
     289: 		 * is gibbous.  However, that is very unlikely.
     290: 		 */
     291:         if ((i = findbucket(op, 1)) < 0 &&
     292:             (i = findbucket(op, realloc_srchlen)) < 0)
     293:             i = NBUCKETS;
     294:     }
     295:     onb = 1 << (i + 3);
     296:     if (onb < pagesz)
     297:         onb -= sizeof (*op) + RSLOP;
     298:     else
     299:         onb += pagesz - sizeof (*op) - RSLOP;
     300:     /* avoid the copy if same size block */
     301:     if (was_alloced) {
     302:         if (i) {
     303:             i = 1 << (i + 2);
     304:             if (i < pagesz)
     305:                 i -= sizeof (*op) + RSLOP;
     306:             else
     307:                 i += pagesz - sizeof (*op) - RSLOP;
     308:         }
     309:         if (nbytes <= onb && nbytes > i) {
     310: #ifdef RCHECK
     311:             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
     312:             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
     313: #endif
     314:             return(cp);
     315:         } else
     316:             free(cp);
     317:     }
     318:     if ((res = malloc(nbytes)) == NULL)
     319:         return (NULL);
     320:     if (cp != res)      /* common optimization if "compacting" */
     321:         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
     322:     return (res);
     323: }
     324:
     325: /*
     326:  * Search ``srchlen'' elements of each free list for a block whose
     327:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
     328:  * Return bucket number, or -1 if not found.
     329:  */
     330: static
     331: findbucket(freep, srchlen)
     332:     union overhead *freep;
     333:     int srchlen;
     334: {
     335:     register union overhead *p;
     336:     register int i, j;
     337:
     338:     for (i = 0; i < NBUCKETS; i++) {
     339:         j = 0;
     340:         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
     341:             if (p == freep)
     342:                 return (i);
     343:             j++;
     344:         }
     345:     }
     346:     return (-1);
     347: }
     348:
     349: /*
     350:  * mstats - print out statistics about malloc
     351:  *
     352:  * Prints two lines of numbers, one showing the length of the free list
     353:  * for each size category, the second showing the number of mallocs -
     354:  * frees for each size category.
     355:  */
     356: showall(s)
     357: char **s;
     358: {
     359:     register int i, j;
     360:     register union overhead *p;
     361:     int totfree = 0,
     362:     totused = 0;
     363:
     364:     if (s[1])
     365:         printf("Memory allocation statistics %s\nfree:", s[1]);
     366:     for (i = 0; i < NBUCKETS; i++) {
     367:         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
     368:             ;
     369:         if (s[1])
     370:             printf(" %d", j);
     371:         totfree += j * (1 << (i + 3));
     372:     }
     373:     if (s[1])
     374:         printf("\nused:");
     375:     for (i = 0; i < NBUCKETS; i++) {
     376:         if (s[1])
     377:             printf(" %d", nmalloc[i]);
     378:         totused += nmalloc[i] * (1 << (i + 3));
     379:     }
     380:     if (s[1])
     381:         printf("\n");
     382:     printf("Total in use: %d, total free: %d\n", totused, totfree);
     383: }

#### Defined functions

botch defined in line 82; used 1 times

- in line 81

findbucket defined in line 330; used 2 times

- in line 291-292(2)

free defined in line 217; used 1 times

- in line 316

malloc defined in line 93; used 2 times

- in line 271, 318

morecore defined in line 176; used 1 times

- in line 152

realloc defined in line 260; never used
showall defined in line 356; never used

#### Defined variables

nextf defined in line 68; used 8 times

- in line 151-157(3), 210, 242-243(2), 340, 367

nmalloc defined in line 78; used 4 times

- in line 160, 244, 377-378(2)

pagebucket defined in line 72; used 2 times

- in line 121, 139

pagesz defined in line 71; used 13 times

- in line 105-110(3), 117, 128, 138, 195-199(3), 296-307(4)

realloc_srchlen defined in line 258; used 1 times

- in line 292

sccsid defined in line 9; never used

#### Defined union's

overhead defined in line 37; used 34 times

- in line 38(2), 68(2), 97(2), 107(2), 179(2), 202(2), 212-213(4), 221-225(6), 266(2), 272(4), 332-335(4), 360(2)

#### Defined macros

ASSERT defined in line 90; used 5 times

- in line 190, 231, 237-241(3)

MAGIC defined in line 53; used 4 times

- in line 158, 231-233(2), 273

NBUCKETS defined in line 67; used 7 times

- in line 68, 78, 241, 293, 338, 366, 375

NULL defined in line 25; used 9 times

- in line 113, 144, 151-154(3), 223, 270, 318-319(2)

RMAGIC defined in line 54; used 5 times

- in line 167-168(2), 237-238(2), 312

RSLOP defined in line 59; used 10 times

- in line 128, 136, 166(2), 297-299(2), 305-311(4)

ov_index defined in line 48; used 3 times

- in line 159, 240, 275

ov_magic defined in line 47; used 4 times

- in line 158, 231-233(2), 273

ov_rmagic defined in line 49; used 2 times

- in line 167, 237

ov_size defined in line 50; used 5 times

- in line 166-168(2), 238, 311-312(2)

Last modified: 1991-08-31 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1464 |