# 2.11BSD#431 - /usr/src/new/PORT/perl.1.0.10/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
    u_char            X
    u_int             X
    u_short           X

##### unions's

    overhead          X

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

#### Defined functions

botch defined in line 96; used 1 times

- in line 95

findbucket defined in line 303; used 2 times

- in line 280-281(2)

free defined in line 209; used 2 times

- in line 294
- in /usr/src/new/PORT/perl.1.0.10/util.c line 86

malloc defined in line 108; used 4 times

- in line 263, 289
- in /usr/src/new/PORT/perl.1.0.10/util.c line 35-37(2)

morecore defined in line 161; used 1 times

- in line 133

mstats defined in line 330; never used
realloc defined in line 251; used 2 times

- in /usr/src/new/PORT/perl.1.0.10/util.c line 59-61(2)

#### Defined variables

nextf defined in line 82; used 10 times

- in line 132-139(4), 170, 201, 231-232(2), 313, 340

nmalloc defined in line 90; used 4 times

- in line 143, 234, 347-348(2)

realloc_srchlen defined in line 249; used 1 times

- in line 281

sccsid defined in line 13; never used

#### Defined union's

overhead defined in line 52; used 40 times

- in line 53(2), 82(2), 112(2), 122(2), 134(2), 165(2), 177(2), 185(2), 194(2), 204-205(4), 213-217(6), 257(2), 264(4), 305-308(4), 334(2)

#### Defined macros

ASSERT defined in line 105; used 4 times

- in line 219, 225-229(3)

MAGIC defined in line 68; used 4 times

- in line 140, 219-221(2), 265

NBUCKETS defined in line 81; used 6 times

- in line 82, 90, 229, 311, 339, 346

NULL defined in line 41; used 7 times

- in line 132-135(3), 215, 262, 289-290(2)

RCHECK defined in line 17; used 4 times

- in line 57, 70, 145, 224

RMAGIC defined in line 69; used 4 times

- in line 152-153(2), 225-227(2)

RSLOP defined in line 73; used 5 times

- in line 122, 153, 227, 284-287(2)

ov_index defined in line 63; used 5 times

- in line 141, 226-230(3), 267

ov_magic defined in line 62; used 4 times

- in line 140, 219-221(2), 265

ov_rmagic defined in line 65; used 2 times

- in line 152, 225

ov_size defined in line 64; used 2 times

- in line 151, 227

u_char defined in line 37; never used
u_int defined in line 38; never used
u_short defined in line 39; never used

Last modified: 1988-02-03 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1836 |