# 2.11BSD#431 - /usr/src/new/PORT/perl.1.0.0/malloc.c

##### Functions

    free              X
    malloc            X
    mstats            X
    realloc           X

##### Variables

    realloc_srchlen   X

##### Macros

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

##### unions's

    overhead          X

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

#### Defined functions

botch defined in line 84; used 1 times

- in line 83

findbucket defined in line 291; used 2 times

- in line 268-269(2)

free defined in line 197; used 2 times

- in line 282
- in /usr/src/new/PORT/perl.1.0.0/util.c line 83

malloc defined in line 96; used 4 times

- in line 251, 277
- in /usr/src/new/PORT/perl.1.0.0/util.c line 32-34(2)

morecore defined in line 149; used 1 times

- in line 121

mstats defined in line 318; never used
realloc defined in line 239; used 2 times

- in /usr/src/new/PORT/perl.1.0.0/util.c line 56-58(2)

#### Defined variables

nextf defined in line 70; used 10 times

- in line 120-127(4), 158, 189, 219-220(2), 301, 328

nmalloc defined in line 78; used 4 times

- in line 131, 222, 335-336(2)

realloc_srchlen defined in line 237; used 1 times

- in line 269

sccsid defined in line 10; never used

#### Defined union's

overhead defined in line 40; used 40 times

- in line 41(2), 70(2), 100(2), 110(2), 122(2), 153(2), 165(2), 173(2), 182(2), 192-193(4), 201-205(6), 245(2), 252(4), 293-296(4), 322(2)

#### Defined macros

ASSERT defined in line 93; used 4 times

- in line 207, 213-217(3)

MAGIC defined in line 56; used 4 times

- in line 128, 207-209(2), 253

NBUCKETS defined in line 69; used 6 times

- in line 70, 78, 217, 299, 327, 334

NULL defined in line 29; used 7 times

- in line 120-123(3), 203, 250, 277-278(2)

RCHECK defined in line 14; used 4 times

- in line 45, 58, 133, 212

RMAGIC defined in line 57; used 4 times

- in line 140-141(2), 213-215(2)

RSLOP defined in line 61; used 5 times

- in line 110, 141, 215, 272-275(2)

ov_index defined in line 51; used 5 times

- in line 129, 214-218(3), 255

ov_magic defined in line 50; used 4 times

- in line 128, 207-209(2), 253

ov_rmagic defined in line 53; used 2 times

- in line 140, 213

ov_size defined in line 52; used 2 times

- in line 139, 215

Last modified: 1988-01-31 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1189 |