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