Annotation of embedaddon/bird/lib/slab.c, revision 1.1.1.1

1.1       misho       1: /*
                      2:  *     BIRD Resource Manager -- A SLAB-like Memory Allocator
                      3:  *
                      4:  *     Heavily inspired by the original SLAB paper by Jeff Bonwick.
                      5:  *
                      6:  *     (c) 1998--2000 Martin Mares <mj@ucw.cz>
                      7:  *
                      8:  *     Can be freely distributed and used under the terms of the GNU GPL.
                      9:  */
                     10: 
                     11: /**
                     12:  * DOC: Slabs
                     13:  *
                     14:  * Slabs are collections of memory blocks of a fixed size.
                     15:  * They support very fast allocation and freeing of such blocks, prevent memory
                     16:  * fragmentation and optimize L2 cache usage. Slabs have been invented by Jeff Bonwick
                     17:  * and published in USENIX proceedings as `The Slab Allocator: An Object-Caching Kernel
                     18:  * Memory Allocator'. Our implementation follows this article except that we don't use
                     19:  * constructors and destructors.
                     20:  *
                     21:  * When the |DEBUGGING| switch is turned on, we automatically fill all
                     22:  * newly allocated and freed blocks with a special pattern to make detection
                     23:  * of use of uninitialized or already freed memory easier.
                     24:  *
                     25:  * Example: Nodes of a FIB are allocated from a per-FIB Slab.
                     26:  */
                     27: 
                     28: #include <stdlib.h>
                     29: #include <stdint.h>
                     30: 
                     31: #include "nest/bird.h"
                     32: #include "lib/resource.h"
                     33: #include "lib/string.h"
                     34: 
                     35: #undef FAKE_SLAB       /* Turn on if you want to debug memory allocations */
                     36: 
                     37: #ifdef DEBUGGING
                     38: #define POISON         /* Poison all regions after they are freed */
                     39: #endif
                     40: 
                     41: static void slab_free(resource *r);
                     42: static void slab_dump(resource *r);
                     43: static resource *slab_lookup(resource *r, unsigned long addr);
                     44: static size_t slab_memsize(resource *r);
                     45: 
                     46: #ifdef FAKE_SLAB
                     47: 
                     48: /*
                     49:  *  Fake version used for debugging.
                     50:  */
                     51: 
                     52: struct slab {
                     53:   resource r;
                     54:   uint size;
                     55:   list objs;
                     56: };
                     57: 
                     58: static struct resclass sl_class = {
                     59:   "FakeSlab",
                     60:   sizeof(struct slab),
                     61:   slab_free,
                     62:   slab_dump,
                     63:   NULL,
                     64:   slab_memsize
                     65: };
                     66: 
                     67: struct sl_obj {
                     68:   node n;
                     69:   uintptr_t data_align[0];
                     70:   byte data[0];
                     71: };
                     72: 
                     73: slab *
                     74: sl_new(pool *p, uint size)
                     75: {
                     76:   slab *s = ralloc(p, &sl_class);
                     77:   s->size = size;
                     78:   init_list(&s->objs);
                     79:   return s;
                     80: }
                     81: 
                     82: void *
                     83: sl_alloc(slab *s)
                     84: {
                     85:   struct sl_obj *o = xmalloc(sizeof(struct sl_obj) + s->size);
                     86: 
                     87:   add_tail(&s->objs, &o->n);
                     88:   return o->data;
                     89: }
                     90: 
                     91: void
                     92: sl_free(slab *s, void *oo)
                     93: {
                     94:   struct sl_obj *o = SKIP_BACK(struct sl_obj, data, oo);
                     95: 
                     96:   rem_node(&o->n);
                     97:   xfree(o);
                     98: }
                     99: 
                    100: static void
                    101: slab_free(resource *r)
                    102: {
                    103:   slab *s = (slab *) r;
                    104:   struct sl_obj *o, *p;
                    105: 
                    106:   for(o = HEAD(s->objs); p = (struct sl_obj *) o->n.next; o = p)
                    107:     xfree(o);
                    108: }
                    109: 
                    110: static void
                    111: slab_dump(resource *r)
                    112: {
                    113:   slab *s = (slab *) r;
                    114:   int cnt = 0;
                    115:   struct sl_obj *o;
                    116: 
                    117:   WALK_LIST(o, s->objs)
                    118:     cnt++;
                    119:   debug("(%d objects per %d bytes)\n", cnt, s->size);
                    120: }
                    121: 
                    122: static size_t
                    123: slab_memsize(resource *r)
                    124: {
                    125:   slab *s = (slab *) r;
                    126:   size_t cnt = 0;
                    127:   struct sl_obj *o;
                    128: 
                    129:   WALK_LIST(o, s->objs)
                    130:     cnt++;
                    131: 
                    132:   return ALLOC_OVERHEAD + sizeof(struct slab) + cnt * (ALLOC_OVERHEAD + s->size);
                    133: }
                    134: 
                    135: 
                    136: #else
                    137: 
                    138: /*
                    139:  *  Real efficient version.
                    140:  */
                    141: 
                    142: #define SLAB_SIZE 4096
                    143: #define MAX_EMPTY_HEADS 1
                    144: 
                    145: struct slab {
                    146:   resource r;
                    147:   uint obj_size, head_size, objs_per_slab, num_empty_heads, data_size;
                    148:   list empty_heads, partial_heads, full_heads;
                    149: };
                    150: 
                    151: static struct resclass sl_class = {
                    152:   "Slab",
                    153:   sizeof(struct slab),
                    154:   slab_free,
                    155:   slab_dump,
                    156:   slab_lookup,
                    157:   slab_memsize
                    158: };
                    159: 
                    160: struct sl_head {
                    161:   node n;
                    162:   struct sl_obj *first_free;
                    163:   int num_full;
                    164: };
                    165: 
                    166: struct sl_obj {
                    167:   struct sl_head *slab;
                    168:   union {
                    169:     struct sl_obj *next;
                    170:     byte data[0];
                    171:   } u;
                    172: };
                    173: 
                    174: struct sl_alignment {                  /* Magic structure for testing of alignment */
                    175:   byte data;
                    176:   int x[0];
                    177: };
                    178: 
                    179: /**
                    180:  * sl_new - create a new Slab
                    181:  * @p: resource pool
                    182:  * @size: block size
                    183:  *
                    184:  * This function creates a new Slab resource from which
                    185:  * objects of size @size can be allocated.
                    186:  */
                    187: slab *
                    188: sl_new(pool *p, uint size)
                    189: {
                    190:   slab *s = ralloc(p, &sl_class);
                    191:   uint align = sizeof(struct sl_alignment);
                    192:   if (align < sizeof(int))
                    193:     align = sizeof(int);
                    194:   s->data_size = size;
                    195:   size += OFFSETOF(struct sl_obj, u.data);
                    196:   if (size < sizeof(struct sl_obj))
                    197:     size = sizeof(struct sl_obj);
                    198:   size = (size + align - 1) / align * align;
                    199:   s->obj_size = size;
                    200:   s->head_size = (sizeof(struct sl_head) + align - 1) / align * align;
                    201:   s->objs_per_slab = (SLAB_SIZE - s->head_size) / size;
                    202:   if (!s->objs_per_slab)
                    203:     bug("Slab: object too large");
                    204:   s->num_empty_heads = 0;
                    205:   init_list(&s->empty_heads);
                    206:   init_list(&s->partial_heads);
                    207:   init_list(&s->full_heads);
                    208:   return s;
                    209: }
                    210: 
                    211: static struct sl_head *
                    212: sl_new_head(slab *s)
                    213: {
                    214:   struct sl_head *h = xmalloc(SLAB_SIZE);
                    215:   struct sl_obj *o = (struct sl_obj *)((byte *)h+s->head_size);
                    216:   struct sl_obj *no;
                    217:   uint n = s->objs_per_slab;
                    218: 
                    219:   h->first_free = o;
                    220:   h->num_full = 0;
                    221:   while (n--)
                    222:     {
                    223:       o->slab = h;
                    224:       no = (struct sl_obj *)((char *) o+s->obj_size);
                    225:       o->u.next = n ? no : NULL;
                    226:       o = no;
                    227:     }
                    228:   return h;
                    229: }
                    230: 
                    231: /**
                    232:  * sl_alloc - allocate an object from Slab
                    233:  * @s: slab
                    234:  *
                    235:  * sl_alloc() allocates space for a single object from the
                    236:  * Slab and returns a pointer to the object.
                    237:  */
                    238: void *
                    239: sl_alloc(slab *s)
                    240: {
                    241:   struct sl_head *h;
                    242:   struct sl_obj *o;
                    243: 
                    244: redo:
                    245:   h = HEAD(s->partial_heads);
                    246:   if (!h->n.next)
                    247:     goto no_partial;
                    248: okay:
                    249:   o = h->first_free;
                    250:   if (!o)
                    251:     goto full_partial;
                    252:   h->first_free = o->u.next;
                    253:   h->num_full++;
                    254: #ifdef POISON
                    255:   memset(o->u.data, 0xcd, s->data_size);
                    256: #endif
                    257:   return o->u.data;
                    258: 
                    259: full_partial:
                    260:   rem_node(&h->n);
                    261:   add_tail(&s->full_heads, &h->n);
                    262:   goto redo;
                    263: 
                    264: no_partial:
                    265:   h = HEAD(s->empty_heads);
                    266:   if (h->n.next)
                    267:     {
                    268:       rem_node(&h->n);
                    269:       add_head(&s->partial_heads, &h->n);
                    270:       s->num_empty_heads--;
                    271:       goto okay;
                    272:     }
                    273:   h = sl_new_head(s);
                    274:   add_head(&s->partial_heads, &h->n);
                    275:   goto okay;
                    276: }
                    277: 
                    278: /**
                    279:  * sl_free - return a free object back to a Slab
                    280:  * @s: slab
                    281:  * @oo: object returned by sl_alloc()
                    282:  *
                    283:  * This function frees memory associated with the object @oo
                    284:  * and returns it back to the Slab @s.
                    285:  */
                    286: void
                    287: sl_free(slab *s, void *oo)
                    288: {
                    289:   struct sl_obj *o = SKIP_BACK(struct sl_obj, u.data, oo);
                    290:   struct sl_head *h = o->slab;
                    291: 
                    292: #ifdef POISON
                    293:   memset(oo, 0xdb, s->data_size);
                    294: #endif
                    295:   o->u.next = h->first_free;
                    296:   h->first_free = o;
                    297:   if (!--h->num_full)
                    298:     {
                    299:       rem_node(&h->n);
                    300:       if (s->num_empty_heads >= MAX_EMPTY_HEADS)
                    301:        xfree(h);
                    302:       else
                    303:        {
                    304:          add_head(&s->empty_heads, &h->n);
                    305:          s->num_empty_heads++;
                    306:        }
                    307:     }
                    308:   else if (!o->u.next)
                    309:     {
                    310:       rem_node(&h->n);
                    311:       add_head(&s->partial_heads, &h->n);
                    312:     }
                    313: }
                    314: 
                    315: static void
                    316: slab_free(resource *r)
                    317: {
                    318:   slab *s = (slab *) r;
                    319:   struct sl_head *h, *g;
                    320: 
                    321:   WALK_LIST_DELSAFE(h, g, s->empty_heads)
                    322:     xfree(h);
                    323:   WALK_LIST_DELSAFE(h, g, s->partial_heads)
                    324:     xfree(h);
                    325:   WALK_LIST_DELSAFE(h, g, s->full_heads)
                    326:     xfree(h);
                    327: }
                    328: 
                    329: static void
                    330: slab_dump(resource *r)
                    331: {
                    332:   slab *s = (slab *) r;
                    333:   int ec=0, pc=0, fc=0;
                    334:   struct sl_head *h;
                    335: 
                    336:   WALK_LIST(h, s->empty_heads)
                    337:     ec++;
                    338:   WALK_LIST(h, s->partial_heads)
                    339:     pc++;
                    340:   WALK_LIST(h, s->full_heads)
                    341:     fc++;
                    342:   debug("(%de+%dp+%df blocks per %d objs per %d bytes)\n", ec, pc, fc, s->objs_per_slab, s->obj_size);
                    343: }
                    344: 
                    345: static size_t
                    346: slab_memsize(resource *r)
                    347: {
                    348:   slab *s = (slab *) r;
                    349:   size_t heads = 0;
                    350:   struct sl_head *h;
                    351: 
                    352:   WALK_LIST(h, s->empty_heads)
                    353:     heads++;
                    354:   WALK_LIST(h, s->partial_heads)
                    355:     heads++;
                    356:   WALK_LIST(h, s->full_heads)
                    357:     heads++;
                    358: 
                    359:   return ALLOC_OVERHEAD + sizeof(struct slab) + heads * (ALLOC_OVERHEAD + SLAB_SIZE);
                    360: }
                    361: 
                    362: static resource *
                    363: slab_lookup(resource *r, unsigned long a)
                    364: {
                    365:   slab *s = (slab *) r;
                    366:   struct sl_head *h;
                    367: 
                    368:   WALK_LIST(h, s->partial_heads)
                    369:     if ((unsigned long) h < a && (unsigned long) h + SLAB_SIZE < a)
                    370:       return r;
                    371:   WALK_LIST(h, s->full_heads)
                    372:     if ((unsigned long) h < a && (unsigned long) h + SLAB_SIZE < a)
                    373:       return r;
                    374:   return NULL;
                    375: }
                    376: 
                    377: #endif

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>