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