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

##### Functions

    botch             X
    free              X
    malloc            X
    prbusy            X

##### Variables

    allocp            X
    allocs            X
    alloct            X
    allocx            X

##### Macros

    ASSERT            X
    BLOCK             X
    BUSY              X
    NULL              X
    WORD              X
    clearbusy         X
    setbusy           X
    testbusy          X

##### struct's

    store             X

       1: #define ASSERT(p) if(!(p))botch("p");else
       2: botch(s)
       3: char *s;
       4: {
       5:     printf("assertion botched: %s\n",s);
       6:     abort();
       7: }
       8: /*	C storage allocator
       9:  *	circular first-fit strategy
      10:  *	works with noncontiguous, but monotonically linked, arena
      11:  *	each block is preceded by a ptr to the (pointer of)
      12:  *	the next following block
      13:  *	blocks are exact number of words long; BUSY
      14:  *	bit in ptr is 1 for busy, 0 for idle
      15:  *	gaps in arena are merely noted as busy blocks
      16:  *	last block of arena (pointed to by alloct) is empty and
      17:  *	has a pointer to first
      18:  *	idle blocks are coalesced during space search
      19: */
      20: /*	all these defines must be powers of 2 */
      21: #define WORD sizeof(struct store)
      22: #define BLOCK 1024
      23: #define BUSY 1
      24: #define NULL 0
      25: #define testbusy(p) ((int)(p)&BUSY)
      26: #define setbusy(p) ((int)(p)+BUSY)
      27: #define clearbusy(p) ((int)(p)&~BUSY)
      28:
      29: struct store { struct store *ptr; };
      30:
      31: struct store allocs[] = {   /*initial arena*/
      32:     setbusy(&allocs[1].ptr),
      33:     setbusy(&allocs[0].ptr)
      34: };
      35: struct store *allocp = &allocs[1];  /*search ptr*/
      36: struct store *alloct = &allocs[1];  /*arena top*/
      37: struct store *allocx;       /*for benefit of realloc*/
      38: struct store *sbrk();
      39:
      40: struct store *
      41: malloc(nbytes)
      42: unsigned nbytes;
      43: {
      44:     register struct store *p, *q;
      45:     register nw;
      46:     static temp;    /*coroutines assume no auto*/
      47:
      48:     nw = (nbytes+2*WORD-1)/WORD;
      49:     ASSERT(allocp>allocs && allocp<=alloct);
      50:     for(p=allocp; ; ) {
      51:         for(temp=0; ; ) {
      52:             if(!testbusy(p->ptr)) {
      53:                 while(!testbusy((q=p->ptr)->ptr)) {
      54:                     ASSERT(q>p&&q<alloct);
      55:                     p->ptr = q->ptr;
      56:                 }
      57:                 if(q>=p+nw && p+nw>=p)
      58:                     goto found;
      59:             }
      60:             q = p;
      61:             p = clearbusy(p->ptr);
      62:             if(p>q)
      63:                 ASSERT(p<=alloct);
      64:             else if(q!=alloct || p!=allocs) {
      65:                 write(2,"corrupt arena\n",14);
      66:                 exit(0175);
      67:             } else if(++temp>1)
      68:                 break;
      69:         }
      70:         temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
      71:         q = sbrk(0);
      72:         if(q+temp < q)
      73:             return(NULL);
      74:         q = sbrk(temp*WORD);
      75:         if((int)q == -1)
      76:             return(NULL);
      77:         ASSERT(q>alloct);
      78:         alloct->ptr = q;
      79:         if(q!=alloct+1)
      80:             alloct->ptr = setbusy(alloct->ptr);
      81:         alloct = q->ptr = q+temp-1;
      82:         alloct->ptr = setbusy(allocs);
      83:     }
      84: found:
      85:     allocp = p + nw;
      86:     ASSERT(allocp<=alloct);
      87:     if(q>allocp) {
      88:         allocx = allocp->ptr;
      89:         allocp->ptr = p->ptr;
      90:     }
      91:     p->ptr = setbusy(allocp);
      92:     return(p+1);
      93: }
      94: /*	freeing strategy tuned for LIFO allocation
      95: */
      96: free(p)
      97: register struct store *p;
      98: {
      99:     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
     100:     allocp = --p;
     101:     ASSERT(testbusy(p->ptr));
     102:     p->ptr = clearbusy(p->ptr);
     103:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
     104: }
     105: struct { unsigned tag:4, vtype:4;};
     106:
     107:
     108: prbusy()
     109: {
     110:     register struct store *p, *q;
     111:
     112:     ASSERT(allocp>allocs && allocp<=alloct);
     113:     for(p=allocs; ; ) {
     114:             if(testbusy(p->ptr))
     115:                 {
     116:                 printf("busy 0%o, tag %d, type %d, length %d\n",
     117:                     p, p[1].tag, p[1].vtype,
     118:                     clearbusy(p->ptr) - (int) p - 2 );
     119:                 }
     120:             q = p;
     121:             p = clearbusy(p->ptr);
     122:             if(p>q)
     123:                 ASSERT(p<=alloct);
     124:             else if(q!=alloct || p!=allocs)
     125:                 {
     126:                 write(2,"corrupt arena\n",14);
     127:                 exit(0175);
     128:                 }
     129:             else return;
     130:     }
     131: }

#### Defined functions

botch defined in line 2; used 1 times

- in line 1

free defined in line 96; used 52 times

- in /usr/src/usr.bin/f77/data.c line 310
- in /usr/src/usr.bin/f77/equiv.c line 229, 245
- in /usr/src/usr.bin/f77/exec.c line 188
- in /usr/src/usr.bin/f77/expr.c line 292, 335, 424, 511, 761, 787, 842, 926, 1383, 1416, 1430, 1439, 1449, 2140, 2172
- in /usr/src/usr.bin/f77/init.c line 189-191(2), 199
- in /usr/src/usr.bin/f77/intr.c line 419, 442, 469
- in /usr/src/usr.bin/f77/io.c line 453
- in /usr/src/usr.bin/f77/lex.c line 147-151(2), 168
- in /usr/src/usr.bin/f77/misc.c line 486, 500
- in /usr/src/usr.bin/f77/proc.c line 612
- in /usr/src/usr.bin/f77/putdmr.c line 200, 220, 229, 306, 368, 435, 450, 473, 576, 739, 765-767(3), 855, 872, 934, 1054, 1143, 1161-1162(2)

malloc defined in line 40; never used
prbusy defined in line 108; never used

#### Defined variables

allocp defined in line 35; used 13 times

- in line 49-50(3), 85-91(6), 100-103(2), 112(2)

allocs defined in line 31; used 11 times

- in line 32-36(4), 49, 64, 82, 99, 112-113(2), 124

alloct defined in line 36; used 17 times

- in line 49-54(2), 63-64(2), 77-86(8), 99-103(2), 112, 123-124(2)

allocx defined in line 37; used 1 times

- in line 88

#### Defined struct's

store defined in line 29; used 20 times

- in line 29-44(16), 97(2), 110(2)

#### Defined macros

ASSERT defined in line 1; used 10 times

- in line 49-54(2), 63, 77, 86, 99-103(3), 112, 123

BLOCK defined in line 22; used 2 times

- in line 70(2)

BUSY defined in line 23; used 3 times

- in line 25-27(3)

NULL defined in line 24; used 2 times

- in line 73-76(2)

WORD defined in line 21; used 5 times

- in line 48(2), 70-74(3)

clearbusy defined in line 27; used 5 times

- in line 61, 99-102(2), 118-121(2)

setbusy defined in line 26; used 5 times

- in line 32-33(2), 80-82(2), 91

testbusy defined in line 25; used 4 times

- in line 52-53(2), 101, 114

Last modified: 1987-02-17 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 594 |