]>
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.
39 #include "nest/bird.h"
40 #include "nest/route.h"
41 #include "lib/string.h"
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
52 fib_ht_alloc(struct fib
*f
)
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
)
59 f
->entries_max
= f
->hash_size HASH_HI_MARK
;
60 if (f
->hash_order
< HASH_LO_MIN
+ HASH_LO_STEP
)
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
*));
70 fib_ht_free(struct fib_node
**h
)
75 static inline unsigned
76 fib_hash(struct fib
*f
, ip_addr
*a
)
78 return ipa_hash(*a
) >> f
->hash_shift
;
82 fib_dummy_init(struct fib_node
*dummy UNUSED
)
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
94 * @init: pointer a function to be called to initialize a newly created node
96 * This function initializes a newly allocated FIB and prepares it for use.
99 fib_init(struct fib
*f
, pool
*p
, unsigned node_size
, unsigned hash_order
, fib_init_func init
)
102 hash_order
= HASH_DEF_ORDER
;
104 f
->fib_slab
= sl_new(p
, node_size
);
105 f
->hash_order
= hash_order
;
107 bzero(f
->hash_table
, f
->hash_size
* sizeof(struct fib_node
*));
110 f
->init
= init
? : fib_dummy_init
;
114 fib_rehash(struct fib
*f
, int step
)
116 unsigned old
, new, oldn
, newn
, ni
, nh
;
117 struct fib_node
**n
, *e
, *x
, **t
, **m
, **h
;
122 m
= h
= f
->hash_table
;
123 DBG("Re-hashing FIB from order %d to %d\n", old
, new);
126 t
= n
= f
->hash_table
;
136 nh
= fib_hash(f
, &e
->prefix
);
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
162 * Search for a FIB node corresponding to the given prefix, return
163 * a pointer to it or %NULL if no such node exists.
166 fib_find(struct fib
*f
, ip_addr
*a
, int len
)
168 struct fib_node
*e
= f
->hash_table
[fib_hash(f
, a
)];
170 while (e
&& (e
->pxlen
!= len
|| !ipa_equal(*a
, e
->prefix
)))
177 fib_histogram(struct fib *f)
179 log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
184 for (i = 0; i < f->hash_size; i++)
187 for (e = f->hash_table[i]; e != NULL; e = e->next)
190 log(L_WARN "Histogram line %d: %d", i, j);
193 log(L_WARN "Histogram dump end");
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
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.
207 fib_get(struct fib
*f
, ip_addr
*a
, int len
)
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
;
214 while (e
&& (e
->pxlen
!= len
|| !ipa_equal(*a
, e
->prefix
)))
219 if (len
< 0 || len
> BITS_PER_IP_ADDRESS
|| !ip_is_prefix(*a
,len
))
220 bug("fib_get() called for invalid address");
223 while ((g
= *ee
) && g
->uid
< uid
)
225 while ((g
= *ee
) && g
->uid
== uid
)
231 if ((uid
>> 16) != h
)
232 log(L_ERR
"FIB hash table chains are too long");
234 // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
236 e
= sl_alloc(f
->fib_slab
);
244 if (f
->entries
++ > f
->entries_max
)
245 fib_rehash(f
, HASH_HI_STEP
);
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
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
261 fib_route(struct fib
*f
, ip_addr a
, int len
)
268 a0
= ipa_and(a
, ipa_mkmask(len
));
269 t
= fib_find(f
, &a0
, len
);
278 fib_merge_readers(struct fib_iterator
*i
, struct fib_node
*to
)
282 struct fib_iterator
*j
= to
->readers
;
287 i
->prev
= (struct fib_iterator
*) to
;
303 else /* No more nodes */
312 * fib_delete - delete a FIB node
313 * @f: FIB to delete from
314 * @E: entry to delete
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.
321 fib_delete(struct fib
*f
, void *E
)
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
;
335 struct fib_node
*l
= e
->next
;
339 if (h
>= f
->hash_size
)
342 l
= f
->hash_table
[h
];
344 fib_merge_readers(it
, l
);
346 sl_free(f
->fib_slab
, e
);
347 if (f
->entries
-- < f
->entries_min
)
348 fib_rehash(f
, -HASH_LO_STEP
);
353 bug("fib_delete() called for invalid node");
357 * fib_free - delete a FIB
358 * @f: FIB to be deleted
360 * This function deletes a FIB -- it frees all memory associated
361 * with it and all its entries.
364 fib_free(struct fib
*f
)
366 fib_ht_free(f
->hash_table
);
371 fit_init(struct fib_iterator
*i
, struct fib
*f
)
377 for(h
=0; h
<f
->hash_size
; h
++)
378 if (n
= f
->hash_table
[h
])
380 i
->prev
= (struct fib_iterator
*) n
;
381 if (i
->next
= n
->readers
)
387 /* The fib is empty, nothing to do */
388 i
->prev
= i
->next
= NULL
;
393 fit_get(struct fib
*f
, struct fib_iterator
*i
)
396 struct fib_iterator
*j
, *k
;
400 /* We are at the end */
406 /* No node info available, we are a victim of merging. Try harder. */
408 while (j
->efef
== 0xff)
410 n
= (struct fib_node
*) j
;
416 i
->hash
= fib_hash(f
, &n
->prefix
);
421 fit_put(struct fib_iterator
*i
, struct fib_node
*n
)
423 struct fib_iterator
*j
;
430 i
->prev
= (struct fib_iterator
*) n
;
434 fit_put_next(struct fib
*f
, struct fib_iterator
*i
, struct fib_node
*n
, uint hpos
)
439 while (++hpos
< f
->hash_size
)
440 if (n
= f
->hash_table
[hpos
])
443 /* We are at the end */
444 i
->prev
= i
->next
= NULL
;
455 * fib_check - audit a FIB
456 * @f: FIB to be checked
458 * This debugging function audits a FIB by checking its internal consistency.
459 * Use when you suspect somebody of corrupting innocent data structures.
462 fib_check(struct fib
*f
)
464 uint i
, ec
, lo
, nulls
;
467 for(i
=0; i
<f
->hash_size
; i
++)
471 for(n
=f
->hash_table
[i
]; n
; n
=n
->next
)
473 struct fib_iterator
*j
, *j0
;
474 uint h0
= ipa_hash(n
->prefix
);
476 bug("fib_check: discord in hash chains");
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
;
482 for(j
=n
->readers
; j
; j
=j
->next
)
485 bug("fib_check: iterator->prev mismatch");
490 bug("fib_check: iterator nullified");
491 else if (j
->node
!= n
)
492 bug("fib_check: iterator->node mismatch");
497 if (ec
!= f
->entries
)
498 bug("fib_check: invalid entry count (%d != %d)", ec
, f
->entries
);
505 #include "lib/resource.h"
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
++)
517 struct fib_iterator
*j
;
518 for(n
=f
.hash_table
[i
]; n
; n
=n
->next
)
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
);
530 void init(struct fib_node
*n
)
537 struct fib_iterator i
, j
;
541 log_init_debug(NULL
);
543 fib_init(&f
, &root_pool
, sizeof(struct fib_node
), 4, init
);
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);
565 FIB_ITERATE_START(&f
, &i
, z
)
569 FIB_ITERATE_PUT(&i
, z
);
574 debug("got %p\n", z
);
586 fit_put(&i
, n
->next
);
589 a
= ipa_from_u32(0xffffffff); n
= fib_get(&f
, &a
, 32);