The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/port/debugalloc.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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(((ulong)t) < 0x80000000)
  679                 return 0;
  680         if(((ulong)t) > 0x90000000)
  681                 return 0;
  682         return recur(t->right) && recur(t->left);
  683 }

Cache object: 02bce4cce0590f168b795399d5472050


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.