1 #include <u.h>
2 #include <libc.h>
3 #include <ip.h>
4 #include <auth.h>
5 #include "ppp.h"
6
7 enum
8 {
9 PAD = 128,
10 NLIST = (1<<5),
11 BPOW = 10,
12 };
13
14 typedef struct Barena Barena;
15 struct Barena
16 {
17 QLock;
18 Block* list[NLIST];
19 };
20 static Barena area;
21
22 #define ADEBUG if(0)
23
24
25 /*
26 * allocation tracing
27 */
28 enum
29 {
30 Npc= 64,
31 };
32 typedef struct Arefent Arefent;
33 struct Arefent
34 {
35 uint pc;
36 uint n;
37 };
38 typedef struct Aref Aref;
39 struct Aref
40 {
41 Arefent tab[Npc];
42 QLock;
43 };
44 Aref arefblock;
45
46 static ulong callerpc(void*);
47 static void aref(Aref*, ulong);
48 static void aunref(Aref*, ulong);
49
50 Block*
allocb(int len)51 allocb(int len)
52 {
53 int sz;
54 Block *bp, **l;
55
56 len += PAD;
57 sz = (len>>BPOW)&(NLIST-1);
58
59 qlock(&area);
60 l = &area.list[sz];
61 for(bp = *l; bp; bp = bp->flist) {
62 if(bp->bsz >= len) {
63 *l = bp->flist;
64 qunlock(&area);
65
66 bp->next = nil;
67 bp->list = nil;
68 bp->flist = nil;
69 bp->base = (uchar*)bp+sizeof(Block);
70 bp->rptr = bp->base+PAD;
71 bp->wptr = bp->rptr;
72 bp->lim = bp->base+bp->bsz;
73 bp->flow = nil;
74 bp->flags= 0;
75 ADEBUG {
76 bp->pc = callerpc(&len);
77 aref(&arefblock, bp->pc);
78 }
79 return bp;
80 }
81 l = &bp->flist;
82 }
83
84 qunlock(&area);
85
86 bp = mallocz(sizeof(Block)+len, 1);
87
88 bp->bsz = len;
89 bp->base = (uchar*)bp+sizeof(Block);
90 bp->rptr = bp->base+PAD;
91 bp->wptr = bp->rptr;
92 bp->lim = bp->base+len;
93 ADEBUG {
94 bp->pc = callerpc(&len);
95 aref(&arefblock, bp->pc);
96 }
97 return bp;
98 }
99
100 void
freeb(Block * bp)101 freeb(Block *bp)
102 {
103 int sz;
104 Block **l, *next;
105
106 qlock(&area);
107 while(bp) {
108 sz = (bp->bsz>>BPOW)&(NLIST-1);
109
110 l = &area.list[sz];
111 bp->flist = *l;
112 *l = bp;
113
114 next = bp->next;
115
116 /* to catch use after free */
117 bp->rptr = (uchar*)0xdeadbabe;
118 bp->wptr = (uchar*)0xdeadbabe;
119 bp->next = (Block*)0xdeadbabe;
120 bp->list = (Block*)0xdeadbabe;
121
122 ADEBUG aunref(&arefblock, bp->pc);
123
124 bp = next;
125 }
126 qunlock(&area);
127 }
128
129 /*
130 * concatenate a list of blocks into a single one and make sure
131 * the result is at least min uchars
132 */
133 Block*
concat(Block * bp)134 concat(Block *bp)
135 {
136 int len;
137 Block *nb, *f;
138
139 nb = allocb(blen(bp));
140 for(f = bp; f; f = f->next) {
141 len = BLEN(f);
142 memmove(nb->wptr, f->rptr, len);
143 nb->wptr += len;
144 }
145 freeb(bp);
146 return nb;
147 }
148
149 int
blen(Block * bp)150 blen(Block *bp)
151 {
152 int len;
153
154 len = 0;
155 while(bp) {
156 len += BLEN(bp);
157 bp = bp->next;
158 }
159 return len;
160 }
161
162 Block *
pullup(Block * bp,int n)163 pullup(Block *bp, int n)
164 {
165 int i;
166 Block *nbp;
167
168 /*
169 * this should almost always be true, the rest it
170 * just for to avoid every caller checking.
171 */
172 if(BLEN(bp) >= n)
173 return bp;
174
175 /*
176 * if not enough room in the first block,
177 * add another to the front of the list.
178 */
179 if(bp->lim - bp->rptr < n){
180 nbp = allocb(n);
181 nbp->next = bp;
182 bp = nbp;
183 }
184
185 /*
186 * copy uchars from the trailing blocks into the first
187 */
188 n -= BLEN(bp);
189 while(nbp = bp->next){
190 i = BLEN(nbp);
191 if(i >= n) {
192 memmove(bp->wptr, nbp->rptr, n);
193 bp->wptr += n;
194 nbp->rptr += n;
195 return bp;
196 }
197 else {
198 memmove(bp->wptr, nbp->rptr, i);
199 bp->wptr += i;
200 bp->next = nbp->next;
201 nbp->next = nil;
202 freeb(nbp);
203 n -= i;
204 }
205 }
206 freeb(bp);
207 return nil;
208 }
209
210 /*
211 * Pad a block to the front with n uchars. This is used to add protocol
212 * headers to the front of blocks.
213 */
214 Block*
padb(Block * bp,int n)215 padb(Block *bp, int n)
216 {
217 Block *nbp;
218
219 if(bp->rptr-bp->base >= n) {
220 bp->rptr -= n;
221 return bp;
222 }
223 else {
224 /* fprint(2, "padb: required %d PAD %d\n", n, PAD) = malloc(sizeof(*required %d PAD %d\n", n, PAD))); */
225 nbp = allocb(n);
226 nbp->wptr = nbp->lim;
227 nbp->rptr = nbp->wptr - n;
228 nbp->next = bp;
229 return nbp;
230 }
231 }
232
233 Block *
btrim(Block * bp,int offset,int len)234 btrim(Block *bp, int offset, int len)
235 {
236 ulong l;
237 Block *nb, *startb;
238
239 if(blen(bp) < offset+len) {
240 freeb(bp);
241 return nil;
242 }
243
244 while((l = BLEN(bp)) < offset) {
245 offset -= l;
246 nb = bp->next;
247 bp->next = nil;
248 freeb(bp);
249 bp = nb;
250 }
251
252 startb = bp;
253 bp->rptr += offset;
254
255 while((l = BLEN(bp)) < len) {
256 len -= l;
257 bp = bp->next;
258 }
259
260 bp->wptr -= (BLEN(bp) - len);
261 bp->flags |= S_DELIM;
262
263 if(bp->next) {
264 freeb(bp->next);
265 bp->next = nil;
266 }
267
268 return startb;
269 }
270
271 Block*
copyb(Block * bp,int count)272 copyb(Block *bp, int count)
273 {
274 int l;
275 Block *nb, *head, **p;
276
277 p = &head;
278 head = nil;
279 while(bp != nil && count != 0) {
280 l = BLEN(bp);
281 if(count < l)
282 l = count;
283 nb = allocb(l);
284 memmove(nb->wptr, bp->rptr, l);
285 nb->wptr += l;
286 count -= l;
287 nb->flags = bp->flags;
288 *p = nb;
289 p = &nb->next;
290 bp = bp->next;
291 }
292 if(count) {
293 nb = allocb(count);
294 memset(nb->wptr, 0, count);
295 nb->wptr += count;
296 nb->flags |= S_DELIM;
297 *p = nb;
298 }
299 if(blen(head) == 0)
300 fprint(2, "copyb: zero length\n");
301
302 return head;
303 }
304
305 int
pullb(Block ** bph,int count)306 pullb(Block **bph, int count)
307 {
308 Block *bp;
309 int n, uchars;
310
311 uchars = 0;
312 if(bph == nil)
313 return 0;
314
315 while(*bph != nil && count != 0) {
316 bp = *bph;
317 n = BLEN(bp);
318 if(count < n)
319 n = count;
320 uchars += n;
321 count -= n;
322 bp->rptr += n;
323 if(BLEN(bp) == 0) {
324 *bph = bp->next;
325 bp->next = nil;
326 freeb(bp);
327 }
328 }
329 return uchars;
330 }
331
332 /*
333 * handy routines for keeping track of allocations
334 */
335 static ulong
callerpc(void * a)336 callerpc(void *a)
337 {
338 return ((ulong*)a)[-1];
339 }
340 static void
aref(Aref * ap,ulong pc)341 aref(Aref *ap, ulong pc)
342 {
343 Arefent *a, *e;
344
345 e = &ap->tab[Npc-1];
346 qlock(ap);
347 for(a = ap->tab; a < e; a++)
348 if(a->pc == pc || a->pc == 0)
349 break;
350 a->pc = pc;
351 a->n++;
352 qunlock(ap);
353 }
354 static void
aunref(Aref * ap,ulong pc)355 aunref(Aref *ap, ulong pc)
356 {
357 Arefent *a, *e;
358
359 e = &ap->tab[Npc-1];
360 qlock(ap);
361 for(a = ap->tab; a < e; a++)
362 if(a->pc == pc || a->pc == 0)
363 break;
364 a->n--;
365 qunlock(ap);
366 }
367