# 2.11BSD#431 - /usr/src/bin/tcsh/alloc11.c

##### Functions

    allock            X
    botch             X
    free              X
    malloc            X
    realloc           X
    showall           X

##### Macros

    ALIGN             X
    ASSERT            X
    BLOCK             X
    BUSY              X
    GRANULE           X
    INT               X
    NALIGN            X
    WORD              X
    clearbusy         X
    debug             X
    setbusy           X
    testbusy          X

##### unions's

    store             X

       1: #if !defined(lint) && !defined(NOSCCS)
       2: static  char *sccsid = "@(#)alloc.c 4.1.1 1996/4/4";
       3: #endif
       4:
       5: #include "config.h"
       6: #include <unistd.h>
       7: #include <sys/types.h>
       8: #include <sys/uio.h>
       9:
      10: #define debug
      11: #ifdef debug
      12: #define ASSERT(p) if(!(p))botch("p");else
      13:
      14: /*
      15:  * Can't use 'printf' below because that can call malloc().  If the malloc
      16:  * arena is corrupt the result is a recursive loop which underflows the stack
      17:  * and obfuscates the initial problem.
      18: */
      19: botch(s)
      20: char *s;
      21: {
      22:     struct  iovec   iov[3];
      23:     register struct iovec *v = iov;
      24:     char    *ab = "assertion botched: ";
      25:
      26:     v->iov_base = ab;
      27:     v->iov_len = strlen(ab);
      28:     v++;
      29:     v->iov_base = s;
      30:     v->iov_len = strlen(s);
      31:     v++;
      32:     v->iov_base = "\n";
      33:     v->iov_len = 1;
      34:
      35:     writev(STDOUT_FILENO, iov, 3);
      36:     abort();
      37: }
      38: #else
      39: #define ASSERT(p)
      40: #endif
      41:
      42: /*	avoid break bug */
      43: #ifdef pdp11
      44: #define GRANULE 64
      45: #else
      46: #define GRANULE 0
      47: #endif
      48: /*	C storage allocator
      49:  *	circular first-fit strategy
      50:  *	works with noncontiguous, but monotonically linked, arena
      51:  *	each block is preceded by a ptr to the (pointer of)
      52:  *	the next following block
      53:  *	blocks are exact number of words long
      54:  *	aligned to the data type requirements of ALIGN
      55:  *	pointers to blocks must have BUSY bit 0
      56:  *	bit in ptr is 1 for busy, 0 for idle
      57:  *	gaps in arena are merely noted as busy blocks
      58:  *	last block of arena (pointed to by alloct) is empty and
      59:  *	has a pointer to first
      60:  *	idle blocks are coalesced during space search
      61:  *
      62:  *	a different implementation may need to redefine
      63:  *	ALIGN, NALIGN, BLOCK, BUSY, INT
      64:  *	where INT is integer type to which a pointer can be cast
      65: */
      66: #define INT int
      67: #define ALIGN int
      68: #define NALIGN 1
      69: #define WORD sizeof(union store)
      70: #define BLOCK 1024  /* a multiple of WORD*/
      71: #define BUSY 1
      72:
      73: #define testbusy(p) ((INT)(p)&BUSY)
      74: #define setbusy(p) (union store *)((INT)(p)|BUSY)
      75: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
      76:
      77: union store { union store *ptr;
      78:           ALIGN dummy[NALIGN];
      79:           int calloc;   /*calloc clears an array of integers*/
      80: };
      81:
      82: static  union store allocs[2];  /*initial arena*/
      83: static  union store *allocp;    /*search ptr*/
      84: static  union store *alloct;    /*arena top*/
      85: static  union store *allocx;    /*for benefit of realloc*/
      86: char    *sbrk();
      87:
      88: char *
      89: malloc(nbytes)
      90: unsigned nbytes;
      91: {
      92:     register union store *p, *q;
      93:     register nw;
      94:     static temp;    /*coroutines assume no auto*/
      95:
      96:     if(allocs[0].ptr==0) {  /*first time*/
      97:         allocs[0].ptr = setbusy(&allocs[1]);
      98:         allocs[1].ptr = setbusy(&allocs[0]);
      99:         alloct = &allocs[1];
     100:         allocp = &allocs[0];
     101:     }
     102:     nw = (nbytes+WORD+WORD-1)/WORD;
     103:     ASSERT(allocp>=allocs && allocp<=alloct);
     104:     ASSERT(allock());
     105:     for(p=allocp; ; ) {
     106:         for(temp=0; ; ) {
     107:             if(!testbusy(p->ptr)) {
     108:                 while(!testbusy((q=p->ptr)->ptr)) {
     109:                     ASSERT(q>p&&q<alloct);
     110:                     p->ptr = q->ptr;
     111:                 }
     112:                 if(q>=p+nw && p+nw>=p)
     113:                     goto found;
     114:             }
     115:             q = p;
     116:             p = clearbusy(p->ptr);
     117:             if(p>q)
     118:                 ASSERT(p<=alloct);
     119:             else if(q!=alloct || p!=allocs) {
     120:                 ASSERT(q==alloct&&p==allocs);
     121:                 return(NULL);
     122:             } else if(++temp>1)
     123:                 break;
     124:         }
     125:         temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
     126:         q = (union store *)sbrk(0);
     127:         if(q+temp+GRANULE < q) {
     128:             return(NULL);
     129:         }
     130:         q = (union store *)sbrk(temp*WORD);
     131:         if((INT)q == -1) {
     132:             return(NULL);
     133:         }
     134:         ASSERT(q>alloct);
     135:         alloct->ptr = q;
     136:         if(q!=alloct+1)
     137:             alloct->ptr = setbusy(alloct->ptr);
     138:         alloct = q->ptr = q+temp-1;
     139:         alloct->ptr = setbusy(allocs);
     140:     }
     141: found:
     142:     allocp = p + nw;
     143:     ASSERT(allocp<=alloct);
     144:     if(q>allocp) {
     145:         allocx = allocp->ptr;
     146:         allocp->ptr = p->ptr;
     147:     }
     148:     p->ptr = setbusy(allocp);
     149:     return((char *)(p+1));
     150: }
     151:
     152: /*	freeing strategy tuned for LIFO allocation
     153: */
     154: free(ap)
     155: register char *ap;
     156: {
     157:     register union store *p = (union store *)ap;
     158:
     159:     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
     160:     ASSERT(allock());
     161:     allocp = --p;
     162:     ASSERT(testbusy(p->ptr));
     163:     p->ptr = clearbusy(p->ptr);
     164:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
     165: }
     166:
     167: /*	realloc(p, nbytes) reallocates a block obtained from malloc()
     168:  *	and freed since last call of malloc()
     169:  *	to have new size nbytes, and old content
     170:  *	returns new location, or 0 on failure
     171: */
     172:
     173: char *
     174: realloc(p, nbytes)
     175: register union store *p;
     176: unsigned nbytes;
     177: {
     178:     register union store *q;
     179:     union store *s, *t;
     180:     register unsigned nw;
     181:     unsigned onw;
     182:
     183:     if(testbusy(p[-1].ptr))
     184:         free((char *)p);
     185:     onw = p[-1].ptr - p;
     186:     q = (union store *)malloc(nbytes);
     187:     if(q==NULL || q==p)
     188:         return((char *)q);
     189:     s = p;
     190:     t = q;
     191:     nw = (nbytes+WORD-1)/WORD;
     192:     if(nw<onw)
     193:         onw = nw;
     194:     while(onw--!=0)
     195:         *t++ = *s++;
     196:     if(q<p && q+nw>=p)
     197:         (q+(q+nw-p))->ptr = allocx;
     198:     return((char *)q);
     199: }
     200:
     201: #ifdef debug
     202: allock()
     203: {
     204: #ifdef longdebug
     205:     register union store *p;
     206:     int x;
     207:     x = 0;
     208:     for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
     209:         if(p==allocp)
     210:             x++;
     211:     }
     212:     ASSERT(p==alloct);
     213:     return(x==1|p==allocp);
     214: #else
     215:     return(1);
     216: #endif
     217: }
     218: #endif
     219:
     220: showall(s)
     221:     char **s;
     222: {
     223:     register union store *p, *q;
     224:     int used = 0, free = 0, i;
     225:
     226:     if (s[1])
     227:         printf("Memory allocation statistics %s\n", s[1]);
     228:     for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
     229:         q = clearbusy(p->ptr);
     230:         i = ((unsigned) q - (unsigned) p);
     231:         if (testbusy(p->ptr)) {
     232:             if (s[1]) {
     233:                 printf("	addr %06o, len %5d BUSY\n",
     234:                     p, i);
     235:                 printf("	content is: %s\n", p+1);
     236:             }
     237:             used += i;
     238:         } else {
     239:             if (s[1])
     240:                 printf("	addr %06o, len %5d FREE\n",
     241:                     p, i);
     242:             free += i;
     243:         }
     244:     }
     245:     printf("%u used, %u free, %u end\n", used, free, clearbusy(alloct));
     246: }

#### Defined functions

allock defined in line 202; used 2 times

- in line 104, 160

botch defined in line 19; used 1 times

- in line 12

free defined in line 154; used 5 times

- in line 184, 224, 242-245(2)
- in /usr/src/bin/tcsh/sh.types.h line 141

malloc defined in line 88; used 1 times

- in line 186

realloc defined in line 173; never used
showall defined in line 220; never used

#### Defined variables

allocp defined in line 83; used 14 times

- in line 100-105(4), 142-148(6), 161-164(2), 209-213(2)

allocs defined in line 82; used 14 times

- in line 96-103(8), 119-120(2), 139, 159, 208, 228

alloct defined in line 84; used 19 times

- in line 99-103(2), 109, 118-120(3), 134-143(8), 159-164(2), 212, 228, 245

allocx defined in line 85; used 2 times

- in line 145, 197

sccsid defined in line 2; never used

#### Defined union's

store defined in line 77; used 32 times

- in line 77-85(10), 92(2), 126-130(4), 157(4), 175-179(6), 186(2), 205(2), 223(2)

#### Defined macros

ALIGN defined in line 67; used 1 times

- in line 78

ASSERT defined in line 39; used 12 times

- in line 103-109(3), 118-120(2), 134, 143, 159-164(4), 212

BLOCK defined in line 70; used 3 times

- in line 125(3)

BUSY defined in line 71; used 3 times

- in line 73-75(3)

GRANULE defined in line 46; used 1 times

- in line 127

INT defined in line 66; used 4 times

- in line 73-75(3), 131

NALIGN defined in line 68; used 1 times

- in line 78

WORD defined in line 69; used 9 times

- in line 102(3), 125-130(4), 191(2)

clearbusy defined in line 75; used 8 times

- in line 116, 159-163(2), 208(2), 228-229(2), 245

debug defined in line 10; used 2 times

- in line 11, 201

setbusy defined in line 74; used 5 times

- in line 97-98(2), 137-139(2), 148

testbusy defined in line 73; used 5 times

- in line 107-108(2), 162, 183, 231

Last modified: 1996-04-05 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 829 |