# 2.11BSD#431 - /usr/src/usr.bin/patch/malloc.c

##### Functions

    bcopy             X
    free              X
    freespace         X
    malloc            X
    malloc_init       X
    malloc_stats      X
    mc_size           X
    realloc           X

##### Macros

    ASSERT            X
    CHAIN             X
    EXTRA             X
    ISALLOC           X
    ISFREE            X
    MAGIC1            X
    MAGIC4            X

##### struct's

    mhead             X
    mstats_value      X

       1: /*
       2:  * @(#)nmalloc.c 1 (Caltech) 2/21/82
       3:  *
       4:  *	U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
       5:  *
       6:  *	Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
       7:  *
       8:  * This is a very fast storage allocator.  It allocates blocks of a small
       9:  * number of different sizes, and keeps free lists of each size.  Blocks
      10:  * that don't exactly fit are passed up to the next larger size.  In this
      11:  * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
      12:  * This is designed for use in a program that uses vast quantities of
      13:  * memory, but bombs when it runs out.  To make it a little better, it
      14:  * warns the user when he starts to get near the end.
      15:  *
      16:  * June 84, ACT: modified rcheck code to check the range given to malloc,
      17:  * rather than the range determined by the 2-power used.
      18:  *
      19:  * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
      20:  * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
      21:  * You should call malloc_init to reinitialize after loading dumped Emacs.
      22:  * Call malloc_stats to get info on memory stats if MSTATS turned on.
      23:  * realloc knows how to return same block given, just changing its size,
      24:  * if the power of 2 is correct.
      25:  */
      26:
      27: /*
      28:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
      29:  * smallest allocatable block is 8 bytes.  The overhead information will
      30:  * go in the first int of the block, and the returned pointer will point
      31:  * to the second.
      32:  *
      33: #ifdef MSTATS
      34:  * nmalloc[i] is the difference between the number of mallocs and frees
      35:  * for a given block size.
      36: #endif /* MSTATS */
      37:  */
      38:
      39: #define ISALLOC ((char) 0xf7)   /* magic byte that implies allocation */
      40: #define ISFREE ((char) 0x54)    /* magic byte that implies free block */
      41:                 /* this is for error checking only */
      42:
      43: extern char etext;
      44:
      45: /* end of the program; can be changed by calling init_malloc */
      46: static char *endofpure = &etext;
      47:
      48: #ifdef MSTATS
      49: static int nmalloc[30];
      50: static int nmal, nfre;
      51: #endif /* MSTATS */
      52:
      53: /* If range checking is not turned on, all we have is a flag indicating
      54:    whether memory is allocated, an index in nextf[], and a size field; to
      55:    realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
      56:    on whether the former can hold the exact size (given the value of
      57:    'index').  If range checking is on, we always need to know how much space
      58:    is allocated, so the 'size' field is never used. */
      59:
      60: struct mhead {
      61:     char     mh_alloc;  /* ISALLOC or ISFREE */
      62:     char     mh_index;  /* index in nextf[] */
      63: /* Remainder are valid only when block is allocated */
      64:     unsigned short mh_size; /* size, if < 0x10000 */
      65: #ifdef rcheck
      66:     unsigned mh_nbytes; /* number of bytes allocated */
      67:     int      mh_magic4; /* should be == MAGIC4 */
      68: #endif /* rcheck */
      69:     };
      70:
      71: /* Access free-list pointer of a block.
      72:   It is stored at block + 4.
      73:   This is not a field in the mhead structure
      74:   because we want sizeof (struct mhead)
      75:   to describe the overhead for when the block is in use,
      76:   and we do not want the free-list pointer to count in that.  */
      77:
      78: #define CHAIN(a) \
      79:   (*(struct mhead **) (sizeof (char *) + (char *) (a)))
      80:
      81: #ifdef rcheck
      82:
      83: /* To implement range checking, we write magic values in at the beginning and
      84:    end of each allocated block, and make sure they are undisturbed whenever a
      85:    free or a realloc occurs. */
      86: /* Written in each of the 4 bytes following the block's real space */
      87: #define MAGIC1 0x55
      88: /* Written in the 4 bytes before the block's real space */
      89: #define MAGIC4 0x55555555
      90: #define ASSERT(p) if (!(p)) botch("p"); else
      91: static
      92: botch(s)
      93:     char *s;
      94: {
      95:
      96:     printf("assertion botched: %s\n", s);
      97:     abort();
      98: }
      99: #define EXTRA  4        /* 4 bytes extra for MAGIC1s */
     100: #else
     101: #define ASSERT(p)
     102: #define EXTRA  0
     103: #endif /* rcheck */
     104:
     105: /* nextf[i] is free list of blocks of size 2**(i + 3)  */
     106:
     107: static struct mhead *nextf[30];
     108:
     109: #ifdef  M_WARN
     110: /* Number of bytes of writable memory we can expect to be able to get */
     111: static int  lim_data;
     112: /* Level number of warnings already issued.
     113:   0 -- no warnings issued.
     114:   1 -- 75% warning already issued.
     115:   2 -- 85% warning already issued.
     116: */
     117: static int  warnlevel;
     118: #endif /* M_WARN */
     119:
     120: /* nonzero once initial bunch of free blocks made */
     121: static int gotpool;
     122:
     123: /* Cause reinitialization based on job parameters;
     124:   also declare where the end of pure storage is. */
     125: malloc_init (end)
     126:     char *end; {
     127:     endofpure = end;
     128: #ifdef  M_WARN
     129:     lim_data = 0;
     130:     warnlevel = 0;
     131: #endif /* M_WARN */
     132:     }
     133:
     134: static
     135: morecore (nu)           /* ask system for more memory */
     136:     register int nu; {      /* size index to get more of  */
     137:     char   *sbrk ();
     138:     register char  *cp;
     139:     register int    nblks;
     140:     register int    siz;
     141:
     142: #ifdef  M_WARN
     143: #ifndef BSD42
     144: #ifdef USG
     145:     extern long ulimit ();
     146:     if (lim_data == 0)      /* find out how much we can get */
     147:         lim_data = ulimit (3, 0) - TEXT_START;
     148: #else   /*HMS: was endif */
     149:     if (lim_data == 0)      /* find out how much we can get */
     150:         lim_data = vlimit (LIM_DATA, -1);
     151: #endif /* USG */	/HMS:* was not here */
     152: #else
     153:     if (lim_data == 0) {
     154:         struct rlimit   XXrlimit;
     155:
     156:         getrlimit (RLIMIT_DATA, &XXrlimit);
     157:         lim_data = XXrlimit.rlim_cur;}  /* soft limit */
     158: #endif /* BSD42 */
     159: #endif /* M_WARN */
     160:
     161:     /* On initial startup, get two blocks of each size up to 1k bytes */
     162:     if (!gotpool)
     163:         getpool (), getpool (), gotpool = 1;
     164:
     165:     /* Find current end of memory and issue warning if getting near max */
     166:
     167:     cp = sbrk (0);
     168:     siz = cp - endofpure;
     169: #ifdef  M_WARN
     170:     switch (warnlevel) {
     171:         case 0:
     172:         if (siz > (lim_data / 4) * 3) {
     173:             warnlevel++;
     174:             malloc_warning ("Warning: past 75% of memory limit");}
     175:         break;
     176:         case 1:
     177:         if (siz > (lim_data / 20) * 17) {
     178:             warnlevel++;
     179:             malloc_warning ("Warning: past 85% of memory limit");}
     180:         break;
     181:         case 2:
     182:         if (siz > (lim_data / 20) * 19) {
     183:             warnlevel++;
     184:             malloc_warning ("Warning: past 95% of memory limit");}
     185:         break;}
     186: #endif /* M_WARN */
     187:
     188:     if ((int) cp & 0x3ff)   /* land on 1K boundaries */
     189:         sbrk (1024 - ((int) cp & 0x3ff));
     190:
     191:     /* Take at least 2k, and figure out how many blocks of the desired size we're about to get */
     192:     nblks = 1;
     193:     if ((siz = nu) < 8)
     194:         nblks = 1 << ((siz = 8) - nu);
     195:
     196:     if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
     197:         return;         /* no more room! */
     198:     if ((int) cp & 7) {     /* shouldn't happen, but just in case */
     199:         cp = (char *) (((int) cp + 8) & ~7);
     200:         nblks--;}
     201:
     202:     /* save new header and link the nblks blocks together */
     203:     nextf[nu] = (struct mhead *) cp;
     204:     siz = 1 << (nu + 3);
     205:     while (1) {
     206:         ((struct mhead *) cp) -> mh_alloc = ISFREE;
     207:         ((struct mhead *) cp) -> mh_index = nu;
     208:         if (--nblks <= 0) break;
     209:         CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
     210:         cp += siz;}
     211: /*	CHAIN ((struct mhead *) cp) = 0;	/* since sbrk() returns cleared core, this is already set */
     212:     }
     213:
     214: static
     215: getpool () {
     216:     register int nu;
     217:     register char *cp = sbrk (0);
     218:
     219:     if ((int) cp & 0x3ff)   /* land on 1K boundaries */
     220:         sbrk (1024 - ((int) cp & 0x3ff));
     221:
     222:     /* Get 2k of storage */
     223:
     224:     cp = sbrk (04000);
     225:     if (cp == (char *) -1)
     226:         return;
     227:
     228:     /* Divide it into an initial 8-word block
     229: 	plus one block of size 2**nu for nu = 3 ... 10.  */
     230:
     231:     CHAIN (cp) = nextf[0];
     232:     nextf[0] = (struct mhead *) cp;
     233:     ((struct mhead *) cp) -> mh_alloc = ISFREE;
     234:     ((struct mhead *) cp) -> mh_index = 0;
     235:     cp += 8;
     236:
     237:     for (nu = 0; nu < 7; nu++) {
     238:         CHAIN (cp) = nextf[nu];
     239:         nextf[nu] = (struct mhead *) cp;
     240:         ((struct mhead *) cp) -> mh_alloc = ISFREE;
     241:         ((struct mhead *) cp) -> mh_index = nu;
     242:         cp += 8 << nu;}}
     243:
     244: char *
     245: malloc (n)      /* get a block */
     246:     unsigned n; {
     247:     register struct  mhead *p;
     248:     register unsigned int  nbytes;
     249:     register int    nunits = 0;
     250:
     251:     /* Figure out how many bytes are required, rounding up to the nearest
     252: 	multiple of 4, then figure out which nextf[] area to use */
     253:     nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
     254:         {
     255:         register unsigned int   shiftr = (nbytes - 1) >> 2;
     256:
     257:         while (shiftr >>= 1)
     258:             nunits++;
     259:         }
     260:
     261:     /* If there are no blocks of the appropriate size, go get some */
     262:     /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
     263:     if (nextf[nunits] == 0)
     264:         morecore (nunits);
     265:
     266:     /* Get one block off the list, and set the new list head */
     267:     if ((p = nextf[nunits]) == 0)
     268:         return 0;
     269:     nextf[nunits] = CHAIN (p);
     270:
     271:     /* Check for free block clobbered */
     272:     /* If not for this check, we would gobble a clobbered free chain ptr */
     273:     /* and bomb out on the NEXT allocate of this size block */
     274:     if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
     275: #ifdef rcheck
     276:         botch ("block on free list clobbered");
     277: #else
     278:         abort ();
     279: #endif /* rcheck */
     280:
     281:     /* Fill in the info, and if range checking, set up the magic numbers */
     282:     p -> mh_alloc = ISALLOC;
     283: #ifdef rcheck
     284:     p -> mh_nbytes = n;
     285:     p -> mh_magic4 = MAGIC4;
     286:         {
     287:         register char  *m = (char *) (p + 1) + n;
     288:
     289:         *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
     290:         }
     291: #else
     292:     p -> mh_size = n;
     293: #endif /* rcheck */
     294: #ifdef MSTATS
     295:     nmalloc[nunits]++;
     296:     nmal++;
     297: #endif /* MSTATS */
     298:     return (char *) (p + 1);}
     299:
     300: free (mem)
     301:     char *mem; {
     302:     register struct mhead *p;
     303:         {
     304:         register char *ap = mem;
     305:
     306:         ASSERT (ap != 0);
     307:         p = (struct mhead *) ap - 1;
     308:         ASSERT (p -> mh_alloc == ISALLOC);
     309: #ifdef rcheck
     310:         ASSERT (p -> mh_magic4 == MAGIC4);
     311:         ap += p -> mh_nbytes;
     312:         ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
     313:         ASSERT (*ap++ == MAGIC1); ASSERT (*ap   == MAGIC1);
     314: #endif /* rcheck */
     315:         }
     316:         {
     317:         register int nunits = p -> mh_index;
     318:
     319:         ASSERT (nunits <= 29);
     320:         p -> mh_alloc = ISFREE;
     321:         CHAIN (p) = nextf[nunits];
     322:         nextf[nunits] = p;
     323: #ifdef MSTATS
     324:         nmalloc[nunits]--;
     325:         nfre++;
     326: #endif /* MSTATS */
     327:         }
     328:     }
     329:
     330: char *
     331: realloc (mem, n)
     332:     char *mem;
     333:     register unsigned n; {
     334:     register struct mhead *p;
     335:     register unsigned int tocopy;
     336:     register int nbytes;
     337:     register int nunits;
     338:
     339:     if ((p = (struct mhead *) mem) == 0)
     340:         return malloc (n);
     341:     p--;
     342:     nunits = p -> mh_index;
     343:     ASSERT (p -> mh_alloc == ISALLOC);
     344: #ifdef rcheck
     345:     ASSERT (p -> mh_magic4 == MAGIC4);
     346:         {
     347:         register char *m = mem + (tocopy = p -> mh_nbytes);
     348:         ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
     349:         ASSERT (*m++ == MAGIC1); ASSERT (*m   == MAGIC1);
     350:         }
     351: #else
     352:     if (p -> mh_index >= 13)
     353:         tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
     354:     else
     355:         tocopy = p -> mh_size;
     356: #endif /* rcheck */
     357:
     358:     /* See if desired size rounds to same power of 2 as actual size. */
     359:     nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
     360:
     361:     /* If ok, use the same block, just marking its size as changed.  */
     362:     if (nbytes > (4 << nunits) && nbytes <= (8 << nunits)) {
     363: #ifdef rcheck
     364:         register char *m = mem + tocopy;
     365:         *m++ = 0;  *m++ = 0;  *m++ = 0;  *m++ = 0;
     366:         p-> mh_nbytes = n;
     367:         m = mem + n;
     368:         *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;
     369: #else
     370:         p -> mh_size = n;
     371: #endif /* rcheck */
     372:         return mem;}
     373:
     374:     if (n < tocopy)
     375:         tocopy = n;
     376:         {
     377:         register char *new;
     378:         void bcopy();   /*HMS: here? */
     379:
     380:         if ((new = malloc (n)) == 0)
     381:             return 0;
     382:         bcopy (mem, new, tocopy);
     383:         free (mem);
     384:         return new;
     385:         }
     386:     }
     387:
     388: #ifdef MSTATS
     389: /* Return statistics describing allocation of blocks of size 2**n. */
     390:
     391: struct mstats_value {
     392:     int blocksize;
     393:     int nfree;
     394:     int nused;
     395:     };
     396:
     397: struct mstats_value
     398: malloc_stats (size)
     399:     int size; {
     400:     struct mstats_value v;
     401:     register int i;
     402:     register struct mhead *p;
     403:
     404:     v.nfree = 0;
     405:
     406:     if (size < 0 || size >= 30) {
     407:         v.blocksize = 0;
     408:         v.nused = 0;
     409:         return v;}
     410:
     411:     v.blocksize = 1 << (size + 3);
     412:     v.nused = nmalloc[size];
     413:
     414:     for (p = nextf[size]; p; p = CHAIN (p))
     415:         v.nfree++;
     416:
     417:     return v;}
     418: #endif
     419:
     420: /* how much space is available? */
     421:
     422: unsigned freespace() {
     423:     register int i, j;
     424:     register struct mhead *p;
     425:     register unsigned space = 0;
     426:     int local;  /* address only is used */
     427:
     428:     space = (char *)&local - sbrk(0);   /* stack space */
     429:
     430:     for (i = 0; i < 30; i++) {
     431:         for (j = 0, p = nextf[i]; p; p = CHAIN (p), j++) ;
     432:         space += j * (1 << (i + 3));}
     433:
     434:     return(space);}
     435:
     436: /* How big is this cell? */
     437:
     438: unsigned mc_size(cp)
     439:     char *cp;{
     440:     register struct mhead *p;
     441:
     442:     if ((p = (struct mhead *) cp) == 0) {
     443:         /*HMS? */
     444:         }
     445:     p--;
     446: #ifdef rcheck
     447:     return p -> mh_nbytes;
     448: #else
     449:     return (1 << (p -> mh_index + 3)) - sizeof *p;
     450: /**/
     451: /*	if (p -> mh_index >= 13)
     452: /*	    return (1 << (p -> mh_index + 3)) - sizeof *p;
     453: /*	else
     454: /*	    return p -> mh_size;
     455: /**/
     456: #endif /* rcheck */
     457:     }
     458:
     459: /*HMS: Really should use memcpy, if available... */
     460:
     461: void bcopy(source, dest, len)
     462:     register char *source, *dest;
     463:     register len; {
     464:     register i;
     465:
     466:     for (i = 0; i < len; i++)
     467:         *dest++ = *source++;}

#### Defined functions

bcopy defined in line 461; used 2 times

- in line 378-382(2)

botch defined in line 91; used 2 times

- in line 90, 276

free defined in line 300; used 29 times

- in line 383
- in /usr/src/usr.bin/patch/inp.c line 45-48(2), 56-57(2), 149, 171
- in /usr/src/usr.bin/patch/patch.c line 336-341(2), 350
- in /usr/src/usr.bin/patch/pch.c line 181, 276, 336, 360-370(6), 423, 675, 902-909(3), 969-974(3)
- in /usr/src/usr.bin/patch/util.c line 357, 363

freespace defined in line 422; never used
getpool defined in line 214; used 2 times

- in line 163(2)

malloc defined in line 244; used 11 times

- in line 340, 380
- in /usr/src/usr.bin/patch/common.h line 147
- in /usr/src/usr.bin/patch/inp.c line 139, 168, 255-256(2)
- in /usr/src/usr.bin/patch/pch.c line 107-112(3)
- in /usr/src/usr.bin/patch/util.c line 133

malloc_init defined in line 125; never used
malloc_stats defined in line 397; never used
mc_size defined in line 438; never used
morecore defined in line 134; used 1 times

- in line 264

realloc defined in line 330; used 4 times

- in /usr/src/usr.bin/patch/common.h line 148
- in /usr/src/usr.bin/patch/pch.c line 128-130(3)

#### Defined variables

endofpure defined in line 46; used 2 times

- in line 127, 168

gotpool defined in line 121; used 2 times

- in line 162-163(2)

lim_data defined in line 111; used 10 times

- in line 129, 146-157(6), 172-182(3)

nextf defined in line 107; used 12 times

- in line 203, 231-232(2), 238-239(2), 263-269(3), 321-322(2), 414, 431

nfre defined in line 50; used 1 times

- in line 325

nmal defined in line 50; used 1 times

- in line 296

nmalloc defined in line 49; used 3 times

- in line 295, 324, 412

warnlevel defined in line 117; used 5 times

- in line 130, 170-183(4)

#### Defined struct's

mhead defined in line 60; used 42 times

- in line 107(2), 203-209(10), 232-241(12), 247(2), 302-307(4), 334-339(4), 402(2), 424(2), 440-442(4)

mstats_value defined in line 391; used 4 times

- in line 397-400(4)

#### Defined macros

ASSERT defined in line 101; used 14 times

- in line 306-313(7), 319, 343-349(6)

CHAIN defined in line 78; used 7 times

- in line 209, 231, 238, 269, 321, 414, 431

EXTRA defined in line 102; used 2 times

- in line 253, 359

ISALLOC defined in line 39; used 3 times

- in line 282, 308, 343

ISFREE defined in line 40; used 5 times

- in line 206, 233, 240, 274, 320

MAGIC1 defined in line 87; used 16 times

- in line 289(4), 312-313(4), 348-349(4), 368(4)

MAGIC4 defined in line 89; used 3 times

- in line 285, 310, 345

Last modified: 1988-06-23 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1691 |