Annotation of embedaddon/bird/lib/slab.c, revision 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to slab.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib