# 2.11BSD#431 - /usr/src/bin/csh/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
    NULL              X
    WORD              X
    clearbusy         X
    setbusy           X
    testbusy          X

##### unions's

    store             X

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

#### Defined functions

allock defined in line 178; used 2 times

- in line 80, 136

botch defined in line 8; used 1 times

- in line 7

free defined in line 130; used 8 times

- in line 160, 200, 216-219(2)
- in /usr/src/bin/csh/sh.file.c line 338-339(2)
- in /usr/src/bin/csh/sh.h line 391
- in /usr/src/bin/csh/sh.misc.c line 42

malloc defined in line 64; used 3 times

- in line 162
- in /usr/src/bin/csh/sh.h line 394, 402

realloc defined in line 149; never used
showall defined in line 196; used 3 times

- in /usr/src/bin/csh/sh.init.c line 77, 92
- in /usr/src/bin/csh/sh.misc.c line 89

#### Defined variables

allocp defined in line 59; used 14 times

- in line 76-81(4), 118-124(6), 137-140(2), 185-189(2)

allocs defined in line 58; used 14 times

- in line 72-79(8), 95-96(2), 115, 135, 184, 204

alloct defined in line 60; used 19 times

- in line 75-79(2), 85, 94-96(3), 110-119(8), 135-140(2), 188, 204, 219

allocx defined in line 61; used 2 times

- in line 121, 173

sccsid defined in line 2; never used

#### Defined union's

store defined in line 53; used 32 times

- in line 53-61(10), 68(2), 102-106(4), 133(4), 151-155(6), 162(2), 181(2), 199(2)

#### Defined macros

ALIGN defined in line 43; used 1 times

- in line 54

ASSERT defined in line 15; used 12 times

- in line 79-85(3), 94-96(2), 110, 119, 135-140(4), 188

BLOCK defined in line 46; used 3 times

- in line 101(3)

BUSY defined in line 47; used 3 times

- in line 49-51(3)

GRANULE defined in line 22; used 1 times

- in line 103

INT defined in line 42; used 4 times

- in line 49-51(3), 107

NALIGN defined in line 44; used 1 times

- in line 54

NULL defined in line 48; used 4 times

- in line 97, 104-108(2), 163

WORD defined in line 45; used 9 times

- in line 78(3), 101-106(4), 167(2)

clearbusy defined in line 51; used 8 times

- in line 92, 135-139(2), 184(2), 204-205(2), 219

setbusy defined in line 50; used 5 times

- in line 73-74(2), 113-115(2), 124

testbusy defined in line 49; used 5 times

- in line 83-84(2), 138, 159, 207

Last modified: 1991-08-31 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1383 |