1 #include "u.h"
2 #include "../port/lib.h"
3 #include "mem.h"
4 #include "pool.h"
5 #include "dat.h"
6 #include "fns.h"
7 #include "error.h"
8
9 #define left u.s.bhl
10 #define right u.s.bhr
11 #define fwd u.s.bhf
12 #define prev u.s.bhv
13 #define parent u.s.bhp
14
15 typedef struct Bhdr Bhdr;
16
17 struct Bhdr {
18 ulong magic;
19 ulong size;
20 };
21 enum {
22 NOT_MAGIC = 0xdeadfa11,
23 };
24
25 struct Pool
26 {
27 char* name;
28 ulong maxsize;
29 int quanta;
30 int chunk;
31 ulong cursize;
32 ulong arenasize;
33 ulong hw;
34 Lock l;
35 Bhdr* root;
36 Bhdr* chain;
37 int nalloc;
38 int nfree;
39 int nbrk;
40 int lastfree;
41 void (*move)(void*, void*);
42 };
43
44 struct
45 {
46 int n;
47 Pool pool[MAXPOOL];
48 Lock l;
49 } table = {
50 2,
51 {
52 { "Main", 4*1024*1024, 31, 128*1024 },
53 { "Image", 16*1024*1024, 31, 2*1024*1024 },
54 }
55 };
56
57 Pool* mainmem = &table.pool[0];
58 Pool* imagmem = &table.pool[1];
59
60 int poolcompact(Pool*);
61
62 Bhdr*
poolchain(Pool * p)63 poolchain(Pool *p)
64 {
65 return p->chain;
66 }
67
68 void
pooldel(Pool * p,Bhdr * t)69 pooldel(Pool *p, Bhdr *t)
70 {
71 Bhdr *s, *f, *rp, *q;
72
73 if(t->parent == nil && p->root != t) {
74 t->prev->fwd = t->fwd;
75 t->fwd->prev = t->prev;
76 return;
77 }
78
79 if(t->fwd != t) {
80 f = t->fwd;
81 s = t->parent;
82 f->parent = s;
83 if(s == nil)
84 p->root = f;
85 else {
86 if(s->left == t)
87 s->left = f;
88 else
89 s->right = f;
90 }
91
92 rp = t->left;
93 f->left = rp;
94 if(rp != nil)
95 rp->parent = f;
96 rp = t->right;
97 f->right = rp;
98 if(rp != nil)
99 rp->parent = f;
100
101 t->prev->fwd = t->fwd;
102 t->fwd->prev = t->prev;
103 return;
104 }
105
106 if(t->left == nil)
107 rp = t->right;
108 else {
109 if(t->right == nil)
110 rp = t->left;
111 else {
112 f = t;
113 rp = t->right;
114 s = rp->left;
115 while(s != nil) {
116 f = rp;
117 rp = s;
118 s = rp->left;
119 }
120 if(f != t) {
121 s = rp->right;
122 f->left = s;
123 if(s != nil)
124 s->parent = f;
125 s = t->right;
126 rp->right = s;
127 if(s != nil)
128 s->parent = rp;
129 }
130 s = t->left;
131 rp->left = s;
132 s->parent = rp;
133 }
134 }
135 q = t->parent;
136 if(q == nil)
137 p->root = rp;
138 else {
139 if(t == q->left)
140 q->left = rp;
141 else
142 q->right = rp;
143 }
144 if(rp != nil)
145 rp->parent = q;
146 }
147
148 void
pooladd(Pool * p,Bhdr * q)149 pooladd(Pool *p, Bhdr *q)
150 {
151 int size;
152 Bhdr *tp, *t;
153
154 q->magic = MAGIC_F;
155
156 q->left = nil;
157 q->right = nil;
158 q->parent = nil;
159 q->fwd = q;
160 q->prev = q;
161
162 t = p->root;
163 if(t == nil) {
164 p->root = q;
165 return;
166 }
167
168 size = q->size;
169
170 tp = nil;
171 while(t != nil) {
172 if(size == t->size) {
173 q->fwd = t->fwd;
174 q->fwd->prev = q;
175 q->prev = t;
176 t->fwd = q;
177 return;
178 }
179 tp = t;
180 if(size < t->size)
181 t = t->left;
182 else
183 t = t->right;
184 }
185
186 q->parent = tp;
187 if(size < tp->size)
188 tp->left = q;
189 else
190 tp->right = q;
191 }
192
193 void*
poolalloc(Pool * p,int size)194 poolalloc(Pool *p, int size)
195 {
196 Bhdr *q, *t;
197 int alloc, ldr, ns, frag;
198
199 if(size < 0 || size >= 1024*1024*1024) /* for sanity and to avoid overflow */
200 return nil;
201 size = (size + BHDRSIZE + p->quanta) & ~(p->quanta);
202
203 ilock(&p->l);
204 p->nalloc++;
205
206 t = p->root;
207 q = nil;
208 while(t) {
209 if(t->size == size) {
210 pooldel(p, t);
211 t->magic = MAGIC_A;
212 p->cursize += t->size;
213 if(p->cursize > p->hw)
214 p->hw = p->cursize;
215 iunlock(&p->l);
216 return B2D(t);
217 }
218 if(size < t->size) {
219 q = t;
220 t = t->left;
221 }
222 else
223 t = t->right;
224 }
225 if(q != nil) {
226 pooldel(p, q);
227 q->magic = MAGIC_A;
228 frag = q->size - size;
229 if(frag < (size>>2)) {
230 p->cursize += q->size;
231 if(p->cursize > p->hw)
232 p->hw = p->cursize;
233 iunlock(&p->l);
234 return B2D(q);
235 }
236 /* Split */
237 ns = q->size - size;
238 q->size = size;
239 B2T(q)->hdr = q;
240 t = B2NB(q);
241 t->size = ns;
242 B2T(t)->hdr = t;
243 pooladd(p, t);
244 p->cursize += q->size;
245 if(p->cursize > p->hw)
246 p->hw = p->cursize;
247 iunlock(&p->l);
248 return B2D(q);
249 }
250
251 ns = p->chunk;
252 if(size > ns)
253 ns = size;
254 ldr = p->quanta+1;
255
256 alloc = ns+ldr+sizeof(t->magic);
257 p->arenasize += alloc;
258 if(p->arenasize > p->maxsize) {
259 p->arenasize -= alloc;
260
261 if(poolcompact(p)) {
262 iunlock(&p->l);
263 return poolalloc(p, size);
264 }
265
266 iunlock(&p->l);
267 print("%s arena too large: size %d cursize %lud arenasize %lud maxsize %lud\n",
268 p->name, size, p->cursize, p->arenasize, p->maxsize);
269 return nil;
270 }
271
272 p->nbrk++;
273 t = xalloc(alloc);
274 if(t == nil) {
275 iunlock(&p->l);
276 return nil;
277 }
278
279 t->magic = MAGIC_E; /* Make a leader */
280 t->size = ldr;
281 t->csize = ns+ldr;
282 t->clink = p->chain;
283 p->chain = t;
284 B2T(t)->hdr = t;
285 t = B2NB(t);
286
287 t->magic = MAGIC_A; /* Make the block we are going to return */
288 t->size = size;
289 B2T(t)->hdr = t;
290 q = t;
291
292 ns -= size; /* Free the rest */
293 if(ns > 0) {
294 q = B2NB(t);
295 q->size = ns;
296 B2T(q)->hdr = q;
297 pooladd(p, q);
298 }
299 B2NB(q)->magic = MAGIC_E; /* Mark the end of the chunk */
300
301 p->cursize += t->size;
302 if(p->cursize > p->hw)
303 p->hw = p->cursize;
304 iunlock(&p->l);
305 return B2D(t);
306 }
307
308 void
poolfree(Pool * p,void * v)309 poolfree(Pool *p, void *v)
310 {
311 Bhdr *b, *c;
312
313 D2B(b, v);
314
315 ilock(&p->l);
316 p->nfree++;
317 p->cursize -= b->size;
318
319 c = B2NB(b);
320 if(c->magic == MAGIC_F) { /* Join forward */
321 pooldel(p, c);
322 c->magic = 0;
323 b->size += c->size;
324 B2T(b)->hdr = b;
325 }
326
327 c = B2PT(b)->hdr;
328 if(c->magic == MAGIC_F) { /* Join backward */
329 pooldel(p, c);
330 b->magic = 0;
331 c->size += b->size;
332 b = c;
333 B2T(b)->hdr = b;
334 }
335
336 pooladd(p, b);
337 iunlock(&p->l);
338 }
339
340 int
poolread(char * va,int count,ulong offset)341 poolread(char *va, int count, ulong offset)
342 {
343 Pool *p;
344 int n, i, signed_off;
345
346 n = 0;
347 signed_off = offset;
348 for(i = 0; i < table.n; i++) {
349 p = &table.pool[i];
350 n += snprint(va+n, count-n, "%11lud %11lud %11lud %11d %11d %11d %s\n",
351 p->cursize,
352 p->maxsize,
353 p->hw,
354 p->nalloc,
355 p->nfree,
356 p->nbrk,
357 p->name);
358
359 if(signed_off > 0) {
360 signed_off -= n;
361 if(signed_off < 0) {
362 memmove(va, va+n+signed_off, -signed_off);
363 n = -signed_off;
364 }
365 else
366 n = 0;
367 }
368
369 }
370 return n;
371 }
372
373 Lock pcxlock;
374 struct {
375 ulong n;
376 ulong pc;
377 } pcx[1024];
378
379 static void
remember(ulong pc,void * v)380 remember(ulong pc, void *v)
381 {
382 Bhdr *b;
383 int i;
384
385 if(v == nil)
386 return;
387
388 D2B(b, v);
389 if((b->size>>5) != 2)
390 return;
391
392 ilock(&pcxlock);
393 B2T(b)->pad = 0;
394 for(i = 0; i < 1024; i++)
395 if(pcx[i].pc == pc || pcx[i].pc == 0){
396 pcx[i].pc = pc;
397 pcx[i].n++;
398 B2T(b)->pad = i;
399 break;
400 }
401 iunlock(&pcxlock);
402 }
403
404 static void
forget(void * v)405 forget(void *v)
406 {
407 Bhdr *b;
408
409 if(v == nil)
410 return;
411
412 D2B(b, v);
413 if((b->size>>5) != 2)
414 return;
415
416 ilock(&pcxlock);
417 pcx[B2T(b)->pad].n--;
418 iunlock(&pcxlock);
419 }
420
421 void*
malloc(ulong size)422 malloc(ulong size)
423 {
424 void *v;
425
426 v = poolalloc(mainmem, size);
427 remember(getcallerpc(&size), v);
428 if(v != nil)
429 memset(v, 0, size);
430 return v;
431 }
432
433 void*
smalloc(ulong size)434 smalloc(ulong size)
435 {
436 void *v;
437
438 for(;;) {
439 v = poolalloc(mainmem, size);
440 remember(getcallerpc(&size), v);
441 if(v != nil)
442 break;
443 tsleep(&up->sleep, return0, 0, 100);
444 }
445 memset(v, 0, size);
446 return v;
447 }
448
449 void*
mallocz(ulong size,int clr)450 mallocz(ulong size, int clr)
451 {
452 void *v;
453
454 v = poolalloc(mainmem, size);
455 remember(getcallerpc(&size), v);
456 if(clr && v != nil)
457 memset(v, 0, size);
458 return v;
459 }
460
461 void
free(void * v)462 free(void *v)
463 {
464 Bhdr *b;
465
466 if(v != nil) {
467 forget(v);
468 D2B(b, v);
469 poolfree(mainmem, v);
470 }
471 }
472
473 void*
realloc(void * v,ulong size)474 realloc(void *v, ulong size)
475 {
476 Bhdr *b;
477 void *nv;
478 int osize;
479
480 if(v == nil)
481 return malloc(size);
482
483 D2B(b, v);
484
485 osize = b->size - BHDRSIZE;
486 if(osize >= size)
487 return v;
488
489 nv = poolalloc(mainmem, size);
490 remember(getcallerpc(&v), nv);
491 if(nv != nil) {
492 memmove(nv, v, osize);
493 free(v);
494 }
495 return nv;
496 }
497
498 int
msize(void * v)499 msize(void *v)
500 {
501 Bhdr *b;
502
503 D2B(b, v);
504 return b->size - BHDRSIZE;
505 }
506
507 void*
calloc(ulong n,ulong szelem)508 calloc(ulong n, ulong szelem)
509 {
510 return malloc(n*szelem);
511 }
512
513 /*
514 void
515 pooldump(Bhdr *b, int d, int c)
516 {
517 Bhdr *t;
518
519 if(b == nil)
520 return;
521
522 print("%.8lux %.8lux %.8lux %c %4d %d (f %.8lux p %.8lux)\n",
523 b, b->left, b->right, c, d, b->size, b->fwd, b->prev);
524 d++;
525 for(t = b->fwd; t != b; t = t->fwd)
526 print("\t%.8lux %.8lux %.8lux\n", t, t->prev, t->fwd);
527 pooldump(b->left, d, 'l');
528 pooldump(b->right, d, 'r');
529 }
530
531
532 void
533 poolshow(void)
534 {
535 int i;
536
537 for(i = 0; i < table.n; i++) {
538 print("Arena: %s root=%.8lux\n", table.pool[i].name, table.pool[i].root);
539 pooldump(table.pool[i].root, 0, 'R');
540 }
541 }
542 */
543
544 void
poolsummary(void)545 poolsummary(void)
546 {
547 int i;
548
549 for(i = 0; i < table.n; i++)
550 print("Arena: %s cursize=%lud; maxsize=%lud\n",
551 table.pool[i].name,
552 table.pool[i].cursize,
553 table.pool[i].maxsize);
554 }
555
556 /*
557 void
558 pooldump(Pool *p)
559 {
560 Bhdr *b, *base, *limit, *ptr;
561
562 b = p->chain;
563 if(b == nil)
564 return;
565 base = b;
566 ptr = b;
567 limit = B2LIMIT(b);
568
569 while(base != nil) {
570 print("\tbase #%.8lux ptr #%.8lux", base, ptr);
571 if(ptr->magic == MAGIC_A)
572 print("\tA%.5d\n", ptr->size);
573 else if(ptr->magic == MAGIC_E)
574 print("\tE\tL#%.8lux\tS#%.8lux\n", ptr->clink, ptr->csize);
575 else
576 print("\tF%.5d\tL#%.8lux\tR#%.8lux\tF#%.8lux\tP#%.8lux\tT#%.8lux\n",
577 ptr->size, ptr->left, ptr->right, ptr->fwd, ptr->prev, ptr->parent);
578 ptr = B2NB(ptr);
579 if(ptr >= limit) {
580 print("link to #%.8lux\n", base->clink);
581 base = base->clink;
582 if(base == nil)
583 break;
584 ptr = base;
585 limit = B2LIMIT(base);
586 }
587 }
588 return;
589 }
590 */
591
592 void
poolsetcompact(Pool * p,void (* move)(void *,void *))593 poolsetcompact(Pool *p, void (*move)(void*, void*))
594 {
595 p->move = move;
596 }
597
598 void
poolsetparam(char * name,ulong maxsize,int quanta,int chunk)599 poolsetparam(char *name, ulong maxsize, int quanta, int chunk)
600 {
601 Pool *p;
602 int i;
603
604 for(i=0; i<table.n; i++){
605 p = &table.pool[i];
606 if(strcmp(name, p->name) == 0){
607 if(maxsize)
608 p->maxsize = maxsize;
609 if(quanta)
610 p->quanta = quanta;
611 if(chunk)
612 p->chunk = chunk;
613 return;
614 }
615 }
616 }
617
618 int
poolcompact(Pool * pool)619 poolcompact(Pool *pool)
620 {
621 Bhdr *base, *limit, *ptr, *end, *next;
622 int compacted, recov, nb;
623
624 if(pool->move == nil || pool->lastfree == pool->nfree)
625 return 0;
626
627 pool->lastfree = pool->nfree;
628
629 base = pool->chain;
630 ptr = B2NB(base); /* First Block in arena has clink */
631 limit = B2LIMIT(base);
632 compacted = 0;
633
634 pool->root = nil;
635 end = ptr;
636 recov = 0;
637 while(base != nil) {
638 next = B2NB(ptr);
639 if(ptr->magic == MAGIC_A) {
640 if(ptr != end) {
641 memmove(end, ptr, ptr->size);
642 pool->move(B2D(ptr), B2D(end));
643 recov = (uchar*)ptr - (uchar*)end;
644 compacted = 1;
645 }
646 end = B2NB(end);
647 }
648 if(next >= limit) {
649 nb = (uchar*)limit - (uchar*)end;
650 //print("recovered %d bytes\n", recov);
651 //print("%d bytes at end\n", nb);
652 USED(recov);
653 if(nb > 0){
654 if(nb < pool->quanta+1)
655 panic("poolcompact: leftover too small\n");
656 end->size = nb;
657 pooladd(pool, end);
658 }
659 base = base->clink;
660 if(base == nil)
661 break;
662 ptr = B2NB(base);
663 end = ptr; /* could do better by copying between chains */
664 limit = B2LIMIT(base);
665 recov = 0;
666 } else
667 ptr = next;
668 }
669
670 return compacted;
671 }
672
673 int
recur(Bhdr * t)674 recur(Bhdr *t)
675 {
676 if(t == 0)
677 return 1;
678 if((uintptr)t < KZERO || (uintptr)t - KZERO > 0x10000000)
679 return 0;
680 return recur(t->right) && recur(t->left);
681 }
682