]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-fib.c
2 * BIRD -- Forwarding Information Base -- Data Structures
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
10 * DOC: Forwarding Information Base
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.
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.
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.
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.
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).
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.
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.
57 #include "nest/bird.h"
58 #include "nest/route.h"
59 #include "lib/string.h"
61 #define HASH_DEF_ORDER 10
62 #define HASH_HI_MARK *4
63 #define HASH_HI_STEP 2
64 #define HASH_HI_MAX 24
65 #define HASH_LO_MARK /5
66 #define HASH_LO_STEP 2
67 #define HASH_LO_MIN 10
71 fib_ht_alloc(struct fib
*f
)
73 f
->hash_size
= 1 << f
->hash_order
;
74 f
->hash_shift
= 32 - f
->hash_order
;
75 if (f
->hash_order
> HASH_HI_MAX
- HASH_HI_STEP
)
78 f
->entries_max
= f
->hash_size HASH_HI_MARK
;
79 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
82 f
->entries_min
= f
->hash_size HASH_LO_MARK
;
83 DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
84 f
->hash_order
, f
->hash_size
, f
->entries_min
, f
->entries_max
);
85 f
->hash_table
= mb_alloc(f
->fib_pool
, f
->hash_size
* sizeof(struct fib_node
*));
89 fib_ht_free(struct fib_node
**h
)
95 static inline u32
fib_hash(struct fib
*f
, const net_addr
*a
);
98 * fib_init - initialize a new FIB
99 * @f: the FIB to be initialized (the structure itself being allocated by the caller)
100 * @p: pool to allocate the nodes in
101 * @node_size: node size to be used (each node consists of a standard header &fib_node
102 * followed by user data)
103 * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
105 * @init: pointer a function to be called to initialize a newly created node
107 * This function initializes a newly allocated FIB and prepares it for use.
110 fib_init(struct fib
*f
, pool
*p
, uint addr_type
, uint node_size
, uint node_offset
, uint hash_order
, fib_init_fn init
)
112 uint addr_length
= net_addr_length
[addr_type
];
115 hash_order
= HASH_DEF_ORDER
;
117 f
->fib_slab
= addr_length
? sl_new(p
, node_size
+ addr_length
) : NULL
;
118 f
->addr_type
= addr_type
;
119 f
->node_size
= node_size
;
120 f
->node_offset
= node_offset
;
121 f
->hash_order
= hash_order
;
123 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct fib_node
*));
130 fib_rehash(struct fib
*f
, int step
)
132 unsigned old
, new, oldn
, newn
, ni
, nh
;
133 struct fib_node
**n
, *e
, *x
, **t
, **m
, **h
;
138 m
= h
= f
->hash_table
;
139 DBG("Re-hashing FIB from order %d to %d\n", old
, new);
142 t
= n
= f
->hash_table
;
152 nh
= fib_hash(f
, e
->addr
);
172 #define CAST(t) (const net_addr_##t *)
173 #define CAST2(t) (net_addr_##t *)
175 #define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift)
177 #define FIB_FIND(f,a,t) \
179 struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)]; \
180 while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a)) \
182 fib_node_to_user(f, e); \
185 #define FIB_INSERT(f,a,e,t) \
187 u32 h = net_hash_##t(CAST(t) a); \
188 struct fib_node **ee = f->hash_table + (h >> f->hash_shift); \
189 struct fib_node *g; \
191 while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h)) \
194 net_copy_##t(CAST2(t) e->addr, CAST(t) a); \
201 fib_hash(struct fib
*f
, const net_addr
*a
)
203 /* Same as FIB_HASH() */
204 return net_hash(a
) >> f
->hash_shift
;
208 fib_get_chain(struct fib
*f
, const net_addr
*a
)
210 ASSERT(f
->addr_type
== a
->type
);
212 struct fib_node
*e
= f
->hash_table
[fib_hash(f
, a
)];
217 * fib_find - search for FIB node by prefix
218 * @f: FIB to search in
219 * @n: network address
221 * Search for a FIB node corresponding to the given prefix, return
222 * a pointer to it or %NULL if no such node exists.
225 fib_find(struct fib
*f
, const net_addr
*a
)
227 ASSERT(f
->addr_type
== a
->type
);
229 switch (f
->addr_type
)
231 case NET_IP4
: return FIB_FIND(f
, a
, ip4
);
232 case NET_IP6
: return FIB_FIND(f
, a
, ip6
);
233 case NET_VPN4
: return FIB_FIND(f
, a
, vpn4
);
234 case NET_VPN6
: return FIB_FIND(f
, a
, vpn6
);
235 case NET_ROA4
: return FIB_FIND(f
, a
, roa4
);
236 case NET_ROA6
: return FIB_FIND(f
, a
, roa6
);
237 case NET_FLOW4
: return FIB_FIND(f
, a
, flow4
);
238 case NET_FLOW6
: return FIB_FIND(f
, a
, flow6
);
239 case NET_IP6_SADR
: return FIB_FIND(f
, a
, ip6_sadr
);
240 case NET_MPLS
: return FIB_FIND(f
, a
, mpls
);
241 default: bug("invalid type");
246 fib_insert(struct fib
*f
, const net_addr
*a
, struct fib_node
*e
)
248 ASSERT(f
->addr_type
== a
->type
);
250 switch (f
->addr_type
)
252 case NET_IP4
: FIB_INSERT(f
, a
, e
, ip4
); return;
253 case NET_IP6
: FIB_INSERT(f
, a
, e
, ip6
); return;
254 case NET_VPN4
: FIB_INSERT(f
, a
, e
, vpn4
); return;
255 case NET_VPN6
: FIB_INSERT(f
, a
, e
, vpn6
); return;
256 case NET_ROA4
: FIB_INSERT(f
, a
, e
, roa4
); return;
257 case NET_ROA6
: FIB_INSERT(f
, a
, e
, roa6
); return;
258 case NET_FLOW4
: FIB_INSERT(f
, a
, e
, flow4
); return;
259 case NET_FLOW6
: FIB_INSERT(f
, a
, e
, flow6
); return;
260 case NET_IP6_SADR
: FIB_INSERT(f
, a
, e
, ip6_sadr
); return;
261 case NET_MPLS
: FIB_INSERT(f
, a
, e
, mpls
); return;
262 default: bug("invalid type");
268 * fib_get - find or create a FIB node
269 * @f: FIB to work with
270 * @n: network address
272 * Search for a FIB node corresponding to the given prefix and
273 * return a pointer to it. If no such node exists, create it.
276 fib_get(struct fib
*f
, const net_addr
*a
)
278 void *b
= fib_find(f
, a
);
283 b
= sl_alloc(f
->fib_slab
);
285 b
= mb_alloc(f
->fib_pool
, f
->node_size
+ a
->length
);
287 struct fib_node
*e
= fib_user_to_node(f
, b
);
292 memset(b
, 0, f
->node_offset
);
296 if (f
->entries
++ > f
->entries_max
)
297 fib_rehash(f
, HASH_HI_STEP
);
303 fib_route_ip4(struct fib
*f
, net_addr_ip4
*n
)
307 while (!(r
= fib_find(f
, (net_addr
*) n
)) && (n
->pxlen
> 0))
310 ip4_clrbit(&n
->prefix
, n
->pxlen
);
317 fib_route_ip6(struct fib
*f
, net_addr_ip6
*n
)
321 while (!(r
= fib_find(f
, (net_addr
*) n
)) && (n
->pxlen
> 0))
324 ip6_clrbit(&n
->prefix
, n
->pxlen
);
331 * fib_route - CIDR routing lookup
332 * @f: FIB to search in
333 * @n: network address
335 * Search for a FIB node with longest prefix matching the given
336 * network, that is a node which a CIDR router would use for routing
340 fib_route(struct fib
*f
, const net_addr
*n
)
342 ASSERT(f
->addr_type
== n
->type
);
344 net_addr
*n0
= alloca(n
->length
);
353 return fib_route_ip4(f
, (net_addr_ip4
*) n0
);
359 return fib_route_ip6(f
, (net_addr_ip6
*) n0
);
368 fib_merge_readers(struct fib_iterator
*i
, struct fib_node
*to
)
372 struct fib_iterator
*j
= to
->readers
;
377 i
->prev
= (struct fib_iterator
*) to
;
393 else /* No more nodes */
402 * fib_delete - delete a FIB node
403 * @f: FIB to delete from
404 * @E: entry to delete
406 * This function removes the given entry from the FIB,
407 * taking care of all the asynchronous readers by shifting
408 * them to the next node in the canonical reading order.
411 fib_delete(struct fib
*f
, void *E
)
413 struct fib_node
*e
= fib_user_to_node(f
, E
);
414 uint h
= fib_hash(f
, e
->addr
);
415 struct fib_node
**ee
= f
->hash_table
+ h
;
416 struct fib_iterator
*it
;
425 struct fib_node
*l
= e
->next
;
429 if (h
>= f
->hash_size
)
432 l
= f
->hash_table
[h
];
434 fib_merge_readers(it
, l
);
438 sl_free(f
->fib_slab
, E
);
442 if (f
->entries
-- < f
->entries_min
)
443 fib_rehash(f
, -HASH_LO_STEP
);
448 bug("fib_delete() called for invalid node");
452 * fib_free - delete a FIB
453 * @f: FIB to be deleted
455 * This function deletes a FIB -- it frees all memory associated
456 * with it and all its entries.
459 fib_free(struct fib
*f
)
461 fib_ht_free(f
->hash_table
);
466 fit_init(struct fib_iterator
*i
, struct fib
*f
)
472 for(h
=0; h
<f
->hash_size
; h
++)
473 if (n
= f
->hash_table
[h
])
475 i
->prev
= (struct fib_iterator
*) n
;
476 if (i
->next
= n
->readers
)
482 /* The fib is empty, nothing to do */
483 i
->prev
= i
->next
= NULL
;
488 fit_get(struct fib
*f
, struct fib_iterator
*i
)
491 struct fib_iterator
*j
, *k
;
495 /* We are at the end */
501 /* No node info available, we are a victim of merging. Try harder. */
503 while (j
->efef
== 0xff)
505 n
= (struct fib_node
*) j
;
511 i
->hash
= fib_hash(f
, n
->addr
);
516 fit_put(struct fib_iterator
*i
, struct fib_node
*n
)
518 struct fib_iterator
*j
;
525 i
->prev
= (struct fib_iterator
*) n
;
529 fit_put_next(struct fib
*f
, struct fib_iterator
*i
, struct fib_node
*n
, uint hpos
)
534 while (++hpos
< f
->hash_size
)
535 if (n
= f
->hash_table
[hpos
])
538 /* We are at the end */
539 i
->prev
= i
->next
= NULL
;
550 * fib_check - audit a FIB
551 * @f: FIB to be checked
553 * This debugging function audits a FIB by checking its internal consistency.
554 * Use when you suspect somebody of corrupting innocent data structures.
557 fib_check(struct fib
*f
)
562 for(i
=0; i
<f
->hash_size
; i
++)
565 for(n
=f
->hash_table
[i
]; n
; n
=n
->next
)
567 struct fib_iterator
*j
, *j0
;
568 uint h0
= fib_hash(f
, n
->addr
);
570 bug("fib_check: mishashed %x->%x (order %d)", h0
, i
, f
->hash_order
);
571 j0
= (struct fib_iterator
*) n
;
573 for(j
=n
->readers
; j
; j
=j
->next
)
576 bug("fib_check: iterator->prev mismatch");
581 bug("fib_check: iterator nullified");
582 else if (j
->node
!= n
)
583 bug("fib_check: iterator->node mismatch");
588 if (ec
!= f
->entries
)
589 bug("fib_check: invalid entry count (%d != %d)", ec
, f
->entries
);
595 fib_histogram(struct fib *f)
597 log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
602 for (i = 0; i < f->hash_size; i++)
605 for (e = f->hash_table[i]; e != NULL; e = e->next)
608 log(L_WARN "Histogram line %d: %d", i, j);
611 log(L_WARN "Histogram dump end");
619 #include "lib/resource.h"
627 debug("%s ... order=%d, size=%d, entries=%d\n", m
, f
.hash_order
, f
.hash_size
, f
.hash_size
);
628 for(i
=0; i
<f
.hash_size
; i
++)
631 struct fib_iterator
*j
;
632 for(n
=f
.hash_table
[i
]; n
; n
=n
->next
)
634 debug("%04x %08x %p %N", i
, ipa_hash(n
->prefix
), n
, n
->addr
);
635 for(j
=n
->readers
; j
; j
=j
->next
)
636 debug(" %p[%p]", j
, j
->node
);
644 void init(struct fib_node
*n
)
651 struct fib_iterator i
, j
;
655 log_init_debug(NULL
);
657 fib_init(&f
, &root_pool
, sizeof(struct fib_node
), 4, init
);
660 a
= ipa_from_u32(0x01020304); n
= fib_get(&f
, &a
, 32);
661 a
= ipa_from_u32(0x02030405); n
= fib_get(&f
, &a
, 32);
662 a
= ipa_from_u32(0x03040506); n
= fib_get(&f
, &a
, 32);
663 a
= ipa_from_u32(0x00000000); n
= fib_get(&f
, &a
, 32);
664 a
= ipa_from_u32(0x00000c01); n
= fib_get(&f
, &a
, 32);
665 a
= ipa_from_u32(0xffffffff); n
= fib_get(&f
, &a
, 32);
679 FIB_ITERATE_START(&f
, &i
, z
)
683 FIB_ITERATE_PUT(&i
, z
);
688 debug("got %p\n", z
);
700 fit_put(&i
, n
->next
);
703 a
= ipa_from_u32(0xffffffff); n
= fib_get(&f
, &a
, 32);