Annotation of embedaddon/bird/nest/rt-fib.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD -- Forwarding Information Base -- Data Structures
! 3: *
! 4: * (c) 1998--2000 Martin Mares <mj@ucw.cz>
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: /**
! 10: * DOC: Forwarding Information Base
! 11: *
! 12: * FIB is a data structure designed for storage of routes indexed by their
! 13: * network prefixes. It supports insertion, deletion, searching by prefix,
! 14: * `routing' (in CIDR sense, that is searching for a longest prefix matching
! 15: * a given IP address) and (which makes the structure very tricky to implement)
! 16: * asynchronous reading, that is enumerating the contents of a FIB while other
! 17: * modules add, modify or remove entries.
! 18: *
! 19: * Internally, each FIB is represented as a collection of nodes of type &fib_node
! 20: * indexed using a sophisticated hashing mechanism.
! 21: * We use two-stage hashing where we calculate a 16-bit primary hash key independent
! 22: * on hash table size and then we just divide the primary keys modulo table size
! 23: * to get a real hash key used for determining the bucket containing the node.
! 24: * The lists of nodes in each bucket are sorted according to the primary hash
! 25: * key, hence if we keep the total number of buckets to be a power of two,
! 26: * re-hashing of the structure keeps the relative order of the nodes.
! 27: *
! 28: * To get the asynchronous reading consistent over node deletions, we need to
! 29: * keep a list of readers for each node. When a node gets deleted, its readers
! 30: * are automatically moved to the next node in the table.
! 31: *
! 32: * Basic FIB operations are performed by functions defined by this module,
! 33: * enumerating of FIB contents is accomplished by using the FIB_WALK() macro
! 34: * or FIB_ITERATE_START() if you want to do it asynchronously.
! 35: */
! 36:
! 37: #undef LOCAL_DEBUG
! 38:
! 39: #include "nest/bird.h"
! 40: #include "nest/route.h"
! 41: #include "lib/string.h"
! 42:
! 43: #define HASH_DEF_ORDER 10
! 44: #define HASH_HI_MARK *4
! 45: #define HASH_HI_STEP 2
! 46: #define HASH_HI_MAX 16 /* Must be at most 16 */
! 47: #define HASH_LO_MARK /5
! 48: #define HASH_LO_STEP 2
! 49: #define HASH_LO_MIN 10
! 50:
! 51: static void
! 52: fib_ht_alloc(struct fib *f)
! 53: {
! 54: f->hash_size = 1 << f->hash_order;
! 55: f->hash_shift = 16 - f->hash_order;
! 56: if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
! 57: f->entries_max = ~0;
! 58: else
! 59: f->entries_max = f->hash_size HASH_HI_MARK;
! 60: if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
! 61: f->entries_min = 0;
! 62: else
! 63: f->entries_min = f->hash_size HASH_LO_MARK;
! 64: DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
! 65: f->hash_order, f->hash_size, f->entries_min, f->entries_max);
! 66: f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
! 67: }
! 68:
! 69: static inline void
! 70: fib_ht_free(struct fib_node **h)
! 71: {
! 72: mb_free(h);
! 73: }
! 74:
! 75: static inline unsigned
! 76: fib_hash(struct fib *f, ip_addr *a)
! 77: {
! 78: return ipa_hash(*a) >> f->hash_shift;
! 79: }
! 80:
! 81: static void
! 82: fib_dummy_init(struct fib_node *dummy UNUSED)
! 83: {
! 84: }
! 85:
! 86: /**
! 87: * fib_init - initialize a new FIB
! 88: * @f: the FIB to be initialized (the structure itself being allocated by the caller)
! 89: * @p: pool to allocate the nodes in
! 90: * @node_size: node size to be used (each node consists of a standard header &fib_node
! 91: * followed by user data)
! 92: * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
! 93: * (recommended)
! 94: * @init: pointer a function to be called to initialize a newly created node
! 95: *
! 96: * This function initializes a newly allocated FIB and prepares it for use.
! 97: */
! 98: void
! 99: fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, fib_init_func init)
! 100: {
! 101: if (!hash_order)
! 102: hash_order = HASH_DEF_ORDER;
! 103: f->fib_pool = p;
! 104: f->fib_slab = sl_new(p, node_size);
! 105: f->hash_order = hash_order;
! 106: fib_ht_alloc(f);
! 107: bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
! 108: f->entries = 0;
! 109: f->entries_min = 0;
! 110: f->init = init ? : fib_dummy_init;
! 111: }
! 112:
! 113: static void
! 114: fib_rehash(struct fib *f, int step)
! 115: {
! 116: unsigned old, new, oldn, newn, ni, nh;
! 117: struct fib_node **n, *e, *x, **t, **m, **h;
! 118:
! 119: old = f->hash_order;
! 120: oldn = f->hash_size;
! 121: new = old + step;
! 122: m = h = f->hash_table;
! 123: DBG("Re-hashing FIB from order %d to %d\n", old, new);
! 124: f->hash_order = new;
! 125: fib_ht_alloc(f);
! 126: t = n = f->hash_table;
! 127: newn = f->hash_size;
! 128: ni = 0;
! 129:
! 130: while (oldn--)
! 131: {
! 132: x = *h++;
! 133: while (e = x)
! 134: {
! 135: x = e->next;
! 136: nh = fib_hash(f, &e->prefix);
! 137: while (nh > ni)
! 138: {
! 139: *t = NULL;
! 140: ni++;
! 141: t = ++n;
! 142: }
! 143: *t = e;
! 144: t = &e->next;
! 145: }
! 146: }
! 147: while (ni < newn)
! 148: {
! 149: *t = NULL;
! 150: ni++;
! 151: t = ++n;
! 152: }
! 153: fib_ht_free(m);
! 154: }
! 155:
! 156: /**
! 157: * fib_find - search for FIB node by prefix
! 158: * @f: FIB to search in
! 159: * @a: pointer to IP address of the prefix
! 160: * @len: prefix length
! 161: *
! 162: * Search for a FIB node corresponding to the given prefix, return
! 163: * a pointer to it or %NULL if no such node exists.
! 164: */
! 165: void *
! 166: fib_find(struct fib *f, ip_addr *a, int len)
! 167: {
! 168: struct fib_node *e = f->hash_table[fib_hash(f, a)];
! 169:
! 170: while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
! 171: e = e->next;
! 172: return e;
! 173: }
! 174:
! 175: /*
! 176: int
! 177: fib_histogram(struct fib *f)
! 178: {
! 179: log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
! 180:
! 181: int i, j;
! 182: struct fib_node *e;
! 183:
! 184: for (i = 0; i < f->hash_size; i++)
! 185: {
! 186: j = 0;
! 187: for (e = f->hash_table[i]; e != NULL; e = e->next)
! 188: j++;
! 189: if (j > 0)
! 190: log(L_WARN "Histogram line %d: %d", i, j);
! 191: }
! 192:
! 193: log(L_WARN "Histogram dump end");
! 194: }
! 195: */
! 196:
! 197: /**
! 198: * fib_get - find or create a FIB node
! 199: * @f: FIB to work with
! 200: * @a: pointer to IP address of the prefix
! 201: * @len: prefix length
! 202: *
! 203: * Search for a FIB node corresponding to the given prefix and
! 204: * return a pointer to it. If no such node exists, create it.
! 205: */
! 206: void *
! 207: fib_get(struct fib *f, ip_addr *a, int len)
! 208: {
! 209: uint h = ipa_hash(*a);
! 210: struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
! 211: struct fib_node *g, *e = *ee;
! 212: u32 uid = h << 16;
! 213:
! 214: while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
! 215: e = e->next;
! 216: if (e)
! 217: return e;
! 218: #ifdef DEBUGGING
! 219: if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
! 220: bug("fib_get() called for invalid address");
! 221: #endif
! 222:
! 223: while ((g = *ee) && g->uid < uid)
! 224: ee = &g->next;
! 225: while ((g = *ee) && g->uid == uid)
! 226: {
! 227: ee = &g->next;
! 228: uid++;
! 229: }
! 230:
! 231: if ((uid >> 16) != h)
! 232: log(L_ERR "FIB hash table chains are too long");
! 233:
! 234: // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
! 235:
! 236: e = sl_alloc(f->fib_slab);
! 237: e->prefix = *a;
! 238: e->pxlen = len;
! 239: e->next = *ee;
! 240: e->uid = uid;
! 241: *ee = e;
! 242: e->readers = NULL;
! 243: f->init(e);
! 244: if (f->entries++ > f->entries_max)
! 245: fib_rehash(f, HASH_HI_STEP);
! 246:
! 247: return e;
! 248: }
! 249:
! 250: /**
! 251: * fib_route - CIDR routing lookup
! 252: * @f: FIB to search in
! 253: * @a: pointer to IP address of the prefix
! 254: * @len: prefix length
! 255: *
! 256: * Search for a FIB node with longest prefix matching the given
! 257: * network, that is a node which a CIDR router would use for routing
! 258: * that network.
! 259: */
! 260: void *
! 261: fib_route(struct fib *f, ip_addr a, int len)
! 262: {
! 263: ip_addr a0;
! 264: void *t;
! 265:
! 266: while (len >= 0)
! 267: {
! 268: a0 = ipa_and(a, ipa_mkmask(len));
! 269: t = fib_find(f, &a0, len);
! 270: if (t)
! 271: return t;
! 272: len--;
! 273: }
! 274: return NULL;
! 275: }
! 276:
! 277: static inline void
! 278: fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
! 279: {
! 280: if (to)
! 281: {
! 282: struct fib_iterator *j = to->readers;
! 283: if (!j)
! 284: {
! 285: /* Fast path */
! 286: to->readers = i;
! 287: i->prev = (struct fib_iterator *) to;
! 288: }
! 289: else
! 290: {
! 291: /* Really merging */
! 292: while (j->next)
! 293: j = j->next;
! 294: j->next = i;
! 295: i->prev = j;
! 296: }
! 297: while (i && i->node)
! 298: {
! 299: i->node = NULL;
! 300: i = i->next;
! 301: }
! 302: }
! 303: else /* No more nodes */
! 304: while (i)
! 305: {
! 306: i->prev = NULL;
! 307: i = i->next;
! 308: }
! 309: }
! 310:
! 311: /**
! 312: * fib_delete - delete a FIB node
! 313: * @f: FIB to delete from
! 314: * @E: entry to delete
! 315: *
! 316: * This function removes the given entry from the FIB,
! 317: * taking care of all the asynchronous readers by shifting
! 318: * them to the next node in the canonical reading order.
! 319: */
! 320: void
! 321: fib_delete(struct fib *f, void *E)
! 322: {
! 323: struct fib_node *e = E;
! 324: uint h = fib_hash(f, &e->prefix);
! 325: struct fib_node **ee = f->hash_table + h;
! 326: struct fib_iterator *it;
! 327:
! 328: while (*ee)
! 329: {
! 330: if (*ee == e)
! 331: {
! 332: *ee = e->next;
! 333: if (it = e->readers)
! 334: {
! 335: struct fib_node *l = e->next;
! 336: while (!l)
! 337: {
! 338: h++;
! 339: if (h >= f->hash_size)
! 340: break;
! 341: else
! 342: l = f->hash_table[h];
! 343: }
! 344: fib_merge_readers(it, l);
! 345: }
! 346: sl_free(f->fib_slab, e);
! 347: if (f->entries-- < f->entries_min)
! 348: fib_rehash(f, -HASH_LO_STEP);
! 349: return;
! 350: }
! 351: ee = &((*ee)->next);
! 352: }
! 353: bug("fib_delete() called for invalid node");
! 354: }
! 355:
! 356: /**
! 357: * fib_free - delete a FIB
! 358: * @f: FIB to be deleted
! 359: *
! 360: * This function deletes a FIB -- it frees all memory associated
! 361: * with it and all its entries.
! 362: */
! 363: void
! 364: fib_free(struct fib *f)
! 365: {
! 366: fib_ht_free(f->hash_table);
! 367: rfree(f->fib_slab);
! 368: }
! 369:
! 370: void
! 371: fit_init(struct fib_iterator *i, struct fib *f)
! 372: {
! 373: unsigned h;
! 374: struct fib_node *n;
! 375:
! 376: i->efef = 0xff;
! 377: for(h=0; h<f->hash_size; h++)
! 378: if (n = f->hash_table[h])
! 379: {
! 380: i->prev = (struct fib_iterator *) n;
! 381: if (i->next = n->readers)
! 382: i->next->prev = i;
! 383: n->readers = i;
! 384: i->node = n;
! 385: return;
! 386: }
! 387: /* The fib is empty, nothing to do */
! 388: i->prev = i->next = NULL;
! 389: i->node = NULL;
! 390: }
! 391:
! 392: struct fib_node *
! 393: fit_get(struct fib *f, struct fib_iterator *i)
! 394: {
! 395: struct fib_node *n;
! 396: struct fib_iterator *j, *k;
! 397:
! 398: if (!i->prev)
! 399: {
! 400: /* We are at the end */
! 401: i->hash = ~0 - 1;
! 402: return NULL;
! 403: }
! 404: if (!(n = i->node))
! 405: {
! 406: /* No node info available, we are a victim of merging. Try harder. */
! 407: j = i;
! 408: while (j->efef == 0xff)
! 409: j = j->prev;
! 410: n = (struct fib_node *) j;
! 411: }
! 412: j = i->prev;
! 413: if (k = i->next)
! 414: k->prev = j;
! 415: j->next = k;
! 416: i->hash = fib_hash(f, &n->prefix);
! 417: return n;
! 418: }
! 419:
! 420: void
! 421: fit_put(struct fib_iterator *i, struct fib_node *n)
! 422: {
! 423: struct fib_iterator *j;
! 424:
! 425: i->node = n;
! 426: if (j = n->readers)
! 427: j->prev = i;
! 428: i->next = j;
! 429: n->readers = i;
! 430: i->prev = (struct fib_iterator *) n;
! 431: }
! 432:
! 433: void
! 434: fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos)
! 435: {
! 436: if (n = n->next)
! 437: goto found;
! 438:
! 439: while (++hpos < f->hash_size)
! 440: if (n = f->hash_table[hpos])
! 441: goto found;
! 442:
! 443: /* We are at the end */
! 444: i->prev = i->next = NULL;
! 445: i->node = NULL;
! 446: return;
! 447:
! 448: found:
! 449: fit_put(i, n);
! 450: }
! 451:
! 452: #ifdef DEBUGGING
! 453:
! 454: /**
! 455: * fib_check - audit a FIB
! 456: * @f: FIB to be checked
! 457: *
! 458: * This debugging function audits a FIB by checking its internal consistency.
! 459: * Use when you suspect somebody of corrupting innocent data structures.
! 460: */
! 461: void
! 462: fib_check(struct fib *f)
! 463: {
! 464: uint i, ec, lo, nulls;
! 465:
! 466: ec = 0;
! 467: for(i=0; i<f->hash_size; i++)
! 468: {
! 469: struct fib_node *n;
! 470: lo = 0;
! 471: for(n=f->hash_table[i]; n; n=n->next)
! 472: {
! 473: struct fib_iterator *j, *j0;
! 474: uint h0 = ipa_hash(n->prefix);
! 475: if (h0 < lo)
! 476: bug("fib_check: discord in hash chains");
! 477: lo = h0;
! 478: if ((h0 >> f->hash_shift) != i)
! 479: bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
! 480: j0 = (struct fib_iterator *) n;
! 481: nulls = 0;
! 482: for(j=n->readers; j; j=j->next)
! 483: {
! 484: if (j->prev != j0)
! 485: bug("fib_check: iterator->prev mismatch");
! 486: j0 = j;
! 487: if (!j->node)
! 488: nulls++;
! 489: else if (nulls)
! 490: bug("fib_check: iterator nullified");
! 491: else if (j->node != n)
! 492: bug("fib_check: iterator->node mismatch");
! 493: }
! 494: ec++;
! 495: }
! 496: }
! 497: if (ec != f->entries)
! 498: bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
! 499: }
! 500:
! 501: #endif
! 502:
! 503: #ifdef TEST
! 504:
! 505: #include "lib/resource.h"
! 506:
! 507: struct fib f;
! 508:
! 509: void dump(char *m)
! 510: {
! 511: uint i;
! 512:
! 513: debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
! 514: for(i=0; i<f.hash_size; i++)
! 515: {
! 516: struct fib_node *n;
! 517: struct fib_iterator *j;
! 518: for(n=f.hash_table[i]; n; n=n->next)
! 519: {
! 520: debug("%04x %04x %p %I/%2d", i, ipa_hash(n->prefix), n, n->prefix, n->pxlen);
! 521: for(j=n->readers; j; j=j->next)
! 522: debug(" %p[%p]", j, j->node);
! 523: debug("\n");
! 524: }
! 525: }
! 526: fib_check(&f);
! 527: debug("-----\n");
! 528: }
! 529:
! 530: void init(struct fib_node *n)
! 531: {
! 532: }
! 533:
! 534: int main(void)
! 535: {
! 536: struct fib_node *n;
! 537: struct fib_iterator i, j;
! 538: ip_addr a;
! 539: int c;
! 540:
! 541: log_init_debug(NULL);
! 542: resource_init();
! 543: fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
! 544: dump("init");
! 545:
! 546: a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
! 547: a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
! 548: a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
! 549: a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
! 550: a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
! 551: a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
! 552: dump("fill");
! 553:
! 554: fit_init(&i, &f);
! 555: dump("iter init");
! 556:
! 557: fib_rehash(&f, 1);
! 558: dump("rehash up");
! 559:
! 560: fib_rehash(&f, -1);
! 561: dump("rehash down");
! 562:
! 563: next:
! 564: c = 0;
! 565: FIB_ITERATE_START(&f, &i, z)
! 566: {
! 567: if (c)
! 568: {
! 569: FIB_ITERATE_PUT(&i, z);
! 570: dump("iter");
! 571: goto next;
! 572: }
! 573: c = 1;
! 574: debug("got %p\n", z);
! 575: }
! 576: FIB_ITERATE_END(z);
! 577: dump("iter end");
! 578:
! 579: fit_init(&i, &f);
! 580: fit_init(&j, &f);
! 581: dump("iter init 2");
! 582:
! 583: n = fit_get(&f, &i);
! 584: dump("iter step 2");
! 585:
! 586: fit_put(&i, n->next);
! 587: dump("iter step 3");
! 588:
! 589: a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
! 590: fib_delete(&f, n);
! 591: dump("iter step 3");
! 592:
! 593: return 0;
! 594: }
! 595:
! 596: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rt-fib.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 / nest