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
malloc(nbytes)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
addblok(reqd)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
free(ap)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
setbrk(incr)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
chkmem()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
chkfree(ap)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