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* 63 poolchain(Pool *p) 64 { 65 return p->chain; 66 } 67 68 void 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 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* 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 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 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 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 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* 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* 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* 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 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* 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 499 msize(void *v) 500 { 501 Bhdr *b; 502 503 D2B(b, v); 504 return b->size - BHDRSIZE; 505 } 506 507 void* 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 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 593 poolsetcompact(Pool *p, void (*move)(void*, void*)) 594 { 595 p->move = move; 596 } 597 598 void 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 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 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