sys/src/9/port/debugalloc.c

   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                 if(!waserror()){
 444                         tsleep(&up->sleep, return0, 0, 100);
 445                         poperror();
 446                 }
 447         }
 448         memset(v, 0, size);
 449         return v;
 450 }
 451
 452 void*
 453 mallocz(ulong size, int clr)
 454 {
 455         void *v;
 456
 457         v = poolalloc(mainmem, size);
 458 remember(getcallerpc(&size), v);
 459         if(clr && v != nil)
 460                 memset(v, 0, size);
 461         return v;
 462 }
 463
 464 void
 465 free(void *v)
 466 {
 467         Bhdr *b;
 468
 469         if(v != nil) {
 470 forget(v);
 471                 D2B(b, v);
 472                 poolfree(mainmem, v);
 473         }
 474 }
 475
 476 void*
 477 realloc(void *v, ulong size)
 478 {
 479         Bhdr *b;
 480         void *nv;
 481         int osize;
 482
 483         if(v == nil)
 484                 return malloc(size);
 485
 486         D2B(b, v);
 487
 488         osize = b->size - BHDRSIZE;
 489         if(osize >= size)
 490                 return v;
 491
 492         nv = poolalloc(mainmem, size);
 493 remember(getcallerpc(&v), nv);
 494         if(nv != nil) {
 495                 memmove(nv, v, osize);
 496                 free(v);
 497         }
 498         return nv;
 499 }
 500
 501 int
 502 msize(void *v)
 503 {
 504         Bhdr *b;
 505
 506         D2B(b, v);
 507         return b->size - BHDRSIZE;
 508 }
 509
 510 void*
 511 calloc(ulong n, ulong szelem)
 512 {
 513         return malloc(n*szelem);
 514 }
 515
 516 /*
 517 void
 518 pooldump(Bhdr *b, int d, int c)
 519 {
 520         Bhdr *t;
 521
 522         if(b == nil)
 523                 return;
 524
 525         print("%.8lux %.8lux %.8lux %c %4d %d (f %.8lux p %.8lux)\n",
 526                 b, b->left, b->right, c, d, b->size, b->fwd, b->prev);
 527         d++;
 528         for(t = b->fwd; t != b; t = t->fwd)
 529                 print("\t%.8lux %.8lux %.8lux\n", t, t->prev, t->fwd);
 530         pooldump(b->left, d, 'l');
 531         pooldump(b->right, d, 'r');
 532 }
 533
 534
 535 void
 536 poolshow(void)
 537 {
 538         int i;
 539
 540         for(i = 0; i < table.n; i++) {
 541                 print("Arena: %s root=%.8lux\n", table.pool[i].name, table.pool[i].root);
 542                 pooldump(table.pool[i].root, 0, 'R');
 543         }
 544 }
 545 */
 546
 547 void
 548 poolsummary(void)
 549 {
 550         int i;
 551
 552         for(i = 0; i < table.n; i++)
 553                 print("Arena: %s cursize=%lud; maxsize=%lud\n",
 554                         table.pool[i].name,
 555                         table.pool[i].cursize,
 556                         table.pool[i].maxsize);
 557 }
 558
 559 /*
 560 void
 561 pooldump(Pool *p)
 562 {
 563         Bhdr *b, *base, *limit, *ptr;
 564
 565         b = p->chain;
 566         if(b == nil)
 567                 return;
 568         base = b;
 569         ptr = b;
 570         limit = B2LIMIT(b);
 571
 572         while(base != nil) {
 573                 print("\tbase #%.8lux ptr #%.8lux", base, ptr);
 574                 if(ptr->magic == MAGIC_A)
 575                         print("\tA%.5d\n", ptr->size);
 576                 else if(ptr->magic == MAGIC_E)
 577                         print("\tE\tL#%.8lux\tS#%.8lux\n", ptr->clink, ptr->csize);
 578                 else
 579                         print("\tF%.5d\tL#%.8lux\tR#%.8lux\tF#%.8lux\tP#%.8lux\tT#%.8lux\n",
 580                                 ptr->size, ptr->left, ptr->right, ptr->fwd, ptr->prev, ptr->parent);
 581                 ptr = B2NB(ptr);
 582                 if(ptr >= limit) {
 583                         print("link to #%.8lux\n", base->clink);
 584                         base = base->clink;
 585                         if(base == nil)
 586                                 break;
 587                         ptr = base;
 588                         limit = B2LIMIT(base);
 589                 }
 590         }
 591         return;
 592 }
 593 */
 594
 595 void
 596 poolsetcompact(Pool *p, void (*move)(void*, void*))
 597 {
 598         p->move = move;
 599 }
 600
 601 void
 602 poolsetparam(char *name, ulong maxsize, int quanta, int chunk)
 603 {
 604         Pool *p;
 605         int i;
 606
 607         for(i=0; i<table.n; i++){
 608                 p = &table.pool[i];
 609                 if(strcmp(name, p->name) == 0){
 610                         if(maxsize)
 611                                 p->maxsize = maxsize;
 612                         if(quanta)
 613                                 p->quanta = quanta;
 614                         if(chunk)
 615                                 p->chunk = chunk;
 616                         return;
 617                 }
 618         }
 619 }
 620
 621 int
 622 poolcompact(Pool *pool)
 623 {
 624         Bhdr *base, *limit, *ptr, *end, *next;
 625         int compacted, recov, nb;
 626
 627         if(pool->move == nil || pool->lastfree == pool->nfree)
 628                 return 0;
 629
 630         pool->lastfree = pool->nfree;
 631
 632         base = pool->chain;
 633         ptr = B2NB(base);       /* First Block in arena has clink */
 634         limit = B2LIMIT(base);
 635         compacted = 0;
 636
 637         pool->root = nil;
 638         end = ptr;
 639         recov = 0;
 640         while(base != nil) {
 641                 next = B2NB(ptr);
 642                 if(ptr->magic == MAGIC_A) {
 643                         if(ptr != end) {
 644                                 memmove(end, ptr, ptr->size);
 645                                 pool->move(B2D(ptr), B2D(end));
 646                                 recov = (uchar*)ptr - (uchar*)end;
 647                                 compacted = 1;
 648                         }
 649                         end = B2NB(end);
 650                 }
 651                 if(next >= limit) {
 652                         nb = (uchar*)limit - (uchar*)end;
 653                         //print("recovered %d bytes\n", recov);
 654                         //print("%d bytes at end\n", nb);
 655                         USED(recov);
 656                         if(nb > 0){
 657                                 if(nb < pool->quanta+1)
 658                                         panic("poolcompact: leftover too small");
 659                                 end->size = nb;
 660                                 pooladd(pool, end);
 661                         }
 662                         base = base->clink;
 663                         if(base == nil)
 664                                 break;
 665                         ptr = B2NB(base);
 666                         end = ptr;      /* could do better by copying between chains */
 667                         limit = B2LIMIT(base);
 668                         recov = 0;
 669                 } else
 670                         ptr = next;
 671         }
 672
 673         return compacted;
 674 }
 675
 676 int
 677 recur(Bhdr *t)
 678 {
 679         if(t == 0)
 680                 return 1;
 681         if((uintptr)t < KZERO || (uintptr)t - KZERO > 0x10000000)
 682                 return 0;
 683         return recur(t->right) && recur(t->left);
 684 }