1 /* 2 3 * Copyright (c) 1984, 1985, 1986 AT&T 4 * All Rights Reserved 5 6 * THIS IS UNPUBLISHED PROPRIETARY SOURCE 7 * CODE OF AT&T. 8 * The copyright notice above does not 9 * evidence any actual or intended 10 * publication of such source code. 11 12 */ 13 /* @(#)blok.c 1.1 */ 14 /* 15 * UNIX shell 16 * 17 * S. R. Bourne 18 * Rewritten by David Korn 19 * AT&T Bell Laboratories 20 * 21 */ 22 23 #include "defs.h" 24 #include "stak.h" 25 #include "brkincr.h" 26 27 28 /* 29 * storage allocator 30 * (circular first fit strategy) 31 */ 32 33 #define BUSY 01 34 #define busy(x) (Rcheat((x)->word)&BUSY) 35 36 void addblok(); 37 void free(); 38 char *malloc(); 39 void setbrk(); 40 #ifdef DBUG 41 void chkmem(); 42 extern void p_str(); 43 extern void p_num(); 44 extern void p_flush(); 45 #endif /* DBUG */ 46 47 48 /* 49 * equivalent to malloc(3) except that a data area stack is 50 * maintained on top of the heap 51 */ 52 53 char *malloc(nbytes) 54 unsigned nbytes; 55 { 56 register unsigned rbytes = round(nbytes+BYTESPERWORD,BYTESPERWORD); 57 while(1) 58 { 59 register BLKPTR p = blokp; 60 register BLKPTR q; 61 register int c=0; 62 do 63 { 64 if(!busy(p)) 65 { 66 while(!busy(q = p->word)) 67 p->word = q->word; 68 if(ADR(q)-ADR(p) >= rbytes) 69 { 70 blokp = BLK(ADR(p)+rbytes); 71 if(q > blokp) 72 blokp->word = p->word; 73 p->word=BLK(Rcheat(blokp)|BUSY); 74 return(ADR(p+1)); 75 } 76 } 77 q = p; p = BLK(Rcheat(p->word)&~BUSY); 78 } 79 while(p>q || (c++)==0); 80 addblok(rbytes); 81 } 82 } 83 84 /* 85 * add more space to the heap and move the stack to the top of the heap 86 */ 87 88 void addblok(reqd) 89 register unsigned int reqd; 90 { 91 if(stakbot == 0) 92 { 93 setbrk(3*BRKINCR); 94 bloktop = BLK(brkbegin); 95 } 96 if(stakbas!=staktop) 97 { 98 register STKPTR rndstak; 99 register BLKPTR blokstak; 100 pushstak(0); 101 rndstak=(STKPTR) round(staktop,BYTESPERWORD); 102 blokstak=BLK(stakbas)-1; 103 blokstak->word=stakbsy; stakbsy=blokstak; 104 bloktop->word=BLK(Rcheat(rndstak)|BUSY); 105 bloktop=BLK(rndstak); 106 } 107 reqd += BRKINCR; 108 reqd &= ~(BRKINCR-1); 109 blokp=bloktop; 110 bloktop=bloktop->word=BLK(Rcheat(bloktop)+reqd); 111 reqd = 0; 112 while((char*)bloktop+BRKINCR > brkend+reqd) 113 reqd += BRKINCR; 114 if(reqd) 115 setbrk((int)reqd); 116 bloktop->word=BLK(Rcheat(brkbegin)|BUSY); 117 { 118 register STKPTR stakadr=STK(bloktop+2); 119 register STKPTR sp = stakadr; 120 if(reqd = (staktop-stakbot)) 121 { 122 while(reqd-- > 0) 123 *sp++ = *stakbot++; 124 sp--; 125 } 126 staktop = sp; 127 stakbas=stakbot=stakadr; 128 } 129 } 130 131 /* 132 * mark the block free if address is in the heap 133 */ 134 135 void free(ap) 136 register char *ap; 137 { 138 register BLKPTR p; 139 if(ap>brkbegin && ap<(char*)bloktop) 140 { 141 p = (BLKPTR)(ap-sizeof(p->word)); 142 p->word = (BLKPTR)(Rcheat(p->word)&~BUSY); 143 } 144 } 145 146 147 void setbrk(incr) 148 { 149 register char *a=(char *)(sbrk(incr)); 150 if((int)a == -1) 151 error(nospace); 152 a = (char*)round(a,BYTESPERWORD); 153 if(brkbegin==0) 154 brkbegin = a; 155 brkend=a+incr-8; 156 #ifndef INT16 157 if(brkend > brkbegin + BRKMAX) 158 { 159 error(nospace); 160 } 161 #endif /* INT16 */ 162 } 163 164 #ifdef DBUG 165 void chkmem() 166 { 167 register BLKPTR p = (BLKPTR)brkbegin; 168 register BLKPTR q; 169 register int us=0, un=0; 170 171 while(1) 172 { 173 q = (BLKPTR) (Rcheat(p->word)&~BUSY); 174 175 if(q<BLK(brkbegin) || q>bloktop) 176 abort(3); 177 if(p==bloktop) 178 break; 179 if(busy(p)) 180 us += q-p; 181 else 182 un += q-p; 183 if(p>=q) 184 { 185 p_flush(); 186 abort(4); 187 } 188 p=q; 189 } 190 un *= sizeof(*q); 191 us *= sizeof(*q); 192 p_str("free/used/missing",':'); 193 p_num(un,' '); 194 p_num(us,' '); 195 p_num((char*)bloktop - (char*)brkbegin - (un+us),NL); 196 } 197 198 /* 199 * returns 1 if <ap> is on heap and is free 200 * returns 2 if <ap> is on heap and not beginning of a block 201 * otherwise returns 0 202 */ 203 204 int chkfree(ap) 205 register char *ap; 206 { 207 register BLKPTR p; 208 if(ap>brkbegin && ap<(char*)bloktop) 209 { 210 p = (BLKPTR)(ap-sizeof(p->word)); 211 if(p->word<BLK(brkbegin) || p->word>bloktop) 212 return(2); 213 return(!busy(p)); 214 } 215 return(0); 216 } 217 #endif /* DBUG */ 218