]>
Commit | Line | Data |
---|---|---|
62aa008a MM |
1 | /* |
2 | * BIRD -- Forwarding Information Base -- Data Structures | |
3 | * | |
6998bb9e | 4 | * (c) 1998--2000 Martin Mares <mj@ucw.cz> |
62aa008a MM |
5 | * |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
ce4aca09 MM |
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. | |
58f7d004 | 24 | * The lists of nodes in each bucket are sorted according to the primary hash |
ce4aca09 MM |
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. | |
7b2c5f3d MV |
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. | |
ce4aca09 MM |
53 | */ |
54 | ||
6b9fa320 | 55 | #undef LOCAL_DEBUG |
62aa008a | 56 | |
62aa008a MM |
57 | #include "nest/bird.h" |
58 | #include "nest/route.h" | |
221135d6 | 59 | #include "lib/string.h" |
62aa008a | 60 | |
3ab001b9 MM |
61 | #define HASH_DEF_ORDER 10 |
62 | #define HASH_HI_MARK *4 | |
63 | #define HASH_HI_STEP 2 | |
d73c4ac8 | 64 | #define HASH_HI_MAX 24 |
3ab001b9 MM |
65 | #define HASH_LO_MARK /5 |
66 | #define HASH_LO_STEP 2 | |
67 | #define HASH_LO_MIN 10 | |
62aa008a | 68 | |
fe9f1a6d | 69 | |
62aa008a MM |
70 | static void |
71 | fib_ht_alloc(struct fib *f) | |
72 | { | |
3ab001b9 | 73 | f->hash_size = 1 << f->hash_order; |
23c212e7 | 74 | f->hash_shift = 32 - f->hash_order; |
3ab001b9 MM |
75 | if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP) |
76 | f->entries_max = ~0; | |
77 | else | |
78 | f->entries_max = f->hash_size HASH_HI_MARK; | |
79 | if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP) | |
62aa008a | 80 | f->entries_min = 0; |
3ab001b9 MM |
81 | else |
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); | |
62aa008a | 85 | f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *)); |
62aa008a MM |
86 | } |
87 | ||
88 | static inline void | |
89 | fib_ht_free(struct fib_node **h) | |
90 | { | |
91 | mb_free(h); | |
92 | } | |
93 | ||
62aa008a | 94 | |
345e50d5 | 95 | static inline u32 fib_hash(struct fib *f, const net_addr *a); |
ce45fc12 | 96 | |
ce4aca09 MM |
97 | /** |
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 | |
104 | * (recommended) | |
105 | * @init: pointer a function to be called to initialize a newly created node | |
106 | * | |
107 | * This function initializes a newly allocated FIB and prepares it for use. | |
108 | */ | |
62aa008a | 109 | void |
fe9f1a6d | 110 | fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init) |
62aa008a | 111 | { |
fe9f1a6d OZ |
112 | uint addr_length = net_addr_length[addr_type]; |
113 | ||
3ab001b9 MM |
114 | if (!hash_order) |
115 | hash_order = HASH_DEF_ORDER; | |
62aa008a | 116 | f->fib_pool = p; |
fe9f1a6d OZ |
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; | |
3ab001b9 | 121 | f->hash_order = hash_order; |
62aa008a | 122 | fib_ht_alloc(f); |
3ab001b9 | 123 | bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *)); |
62aa008a MM |
124 | f->entries = 0; |
125 | f->entries_min = 0; | |
fe9f1a6d | 126 | f->init = init; |
62aa008a MM |
127 | } |
128 | ||
129 | static void | |
3ab001b9 | 130 | fib_rehash(struct fib *f, int step) |
62aa008a | 131 | { |
3ab001b9 | 132 | unsigned old, new, oldn, newn, ni, nh; |
62aa008a MM |
133 | struct fib_node **n, *e, *x, **t, **m, **h; |
134 | ||
3ab001b9 MM |
135 | old = f->hash_order; |
136 | oldn = f->hash_size; | |
137 | new = old + step; | |
62aa008a | 138 | m = h = f->hash_table; |
3ab001b9 MM |
139 | DBG("Re-hashing FIB from order %d to %d\n", old, new); |
140 | f->hash_order = new; | |
62aa008a | 141 | fib_ht_alloc(f); |
3ab001b9 MM |
142 | t = n = f->hash_table; |
143 | newn = f->hash_size; | |
144 | ni = 0; | |
145 | ||
6998bb9e | 146 | while (oldn--) |
62aa008a MM |
147 | { |
148 | x = *h++; | |
149 | while (e = x) | |
150 | { | |
151 | x = e->next; | |
fe9f1a6d | 152 | nh = fib_hash(f, e->addr); |
3ab001b9 MM |
153 | while (nh > ni) |
154 | { | |
155 | *t = NULL; | |
156 | ni++; | |
157 | t = ++n; | |
158 | } | |
62aa008a | 159 | *t = e; |
3ab001b9 | 160 | t = &e->next; |
62aa008a MM |
161 | } |
162 | } | |
3ab001b9 MM |
163 | while (ni < newn) |
164 | { | |
165 | *t = NULL; | |
166 | ni++; | |
167 | t = ++n; | |
168 | } | |
62aa008a MM |
169 | fib_ht_free(m); |
170 | } | |
171 | ||
0f7d5b1a OZ |
172 | #define CAST(t) (const net_addr_##t *) |
173 | #define CAST2(t) (net_addr_##t *) | |
fe9f1a6d OZ |
174 | |
175 | #define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift) | |
176 | ||
177 | #define FIB_FIND(f,a,t) \ | |
178 | ({ \ | |
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)) \ | |
181 | e = e->next; \ | |
600998fc | 182 | fib_node_to_user(f, e); \ |
fe9f1a6d OZ |
183 | }) |
184 | ||
185 | #define FIB_INSERT(f,a,e,t) \ | |
186 | ({ \ | |
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; \ | |
190 | \ | |
191 | while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h)) \ | |
192 | ee = &g->next; \ | |
193 | \ | |
0f7d5b1a | 194 | net_copy_##t(CAST2(t) e->addr, CAST(t) a); \ |
fe9f1a6d OZ |
195 | e->next = *ee; \ |
196 | *ee = e; \ | |
197 | }) | |
198 | ||
199 | ||
345e50d5 | 200 | static inline u32 |
0f7d5b1a | 201 | fib_hash(struct fib *f, const net_addr *a) |
fe9f1a6d | 202 | { |
345e50d5 OZ |
203 | /* Same as FIB_HASH() */ |
204 | return net_hash(a) >> f->hash_shift; | |
fe9f1a6d OZ |
205 | } |
206 | ||
0264ccf6 PT |
207 | void * |
208 | fib_get_chain(struct fib *f, const net_addr *a) | |
209 | { | |
210 | ASSERT(f->addr_type == a->type); | |
211 | ||
212 | struct fib_node *e = f->hash_table[fib_hash(f, a)]; | |
213 | return e; | |
214 | } | |
215 | ||
0f7d5b1a OZ |
216 | /** |
217 | * fib_find - search for FIB node by prefix | |
218 | * @f: FIB to search in | |
219 | * @n: network address | |
220 | * | |
221 | * Search for a FIB node corresponding to the given prefix, return | |
222 | * a pointer to it or %NULL if no such node exists. | |
223 | */ | |
fe9f1a6d | 224 | void * |
0f7d5b1a | 225 | fib_find(struct fib *f, const net_addr *a) |
fe9f1a6d OZ |
226 | { |
227 | ASSERT(f->addr_type == a->type); | |
228 | ||
229 | switch (f->addr_type) | |
230 | { | |
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); | |
de9b87f5 PT |
235 | case NET_ROA4: return FIB_FIND(f, a, roa4); |
236 | case NET_ROA6: return FIB_FIND(f, a, roa6); | |
77234bbb OZ |
237 | case NET_FLOW4: return FIB_FIND(f, a, flow4); |
238 | case NET_FLOW6: return FIB_FIND(f, a, flow6); | |
be17805c | 239 | case NET_IP6_SADR: return FIB_FIND(f, a, ip6_sadr); |
66acbc8d | 240 | case NET_MPLS: return FIB_FIND(f, a, mpls); |
fe9f1a6d OZ |
241 | default: bug("invalid type"); |
242 | } | |
243 | } | |
244 | ||
245 | static void | |
0f7d5b1a | 246 | fib_insert(struct fib *f, const net_addr *a, struct fib_node *e) |
fe9f1a6d | 247 | { |
3f358161 MM |
248 | ASSERT(f->addr_type == a->type); |
249 | ||
fe9f1a6d OZ |
250 | switch (f->addr_type) |
251 | { | |
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; | |
de9b87f5 PT |
256 | case NET_ROA4: FIB_INSERT(f, a, e, roa4); return; |
257 | case NET_ROA6: FIB_INSERT(f, a, e, roa6); return; | |
77234bbb OZ |
258 | case NET_FLOW4: FIB_INSERT(f, a, e, flow4); return; |
259 | case NET_FLOW6: FIB_INSERT(f, a, e, flow6); return; | |
be17805c | 260 | case NET_IP6_SADR: FIB_INSERT(f, a, e, ip6_sadr); return; |
66acbc8d | 261 | case NET_MPLS: FIB_INSERT(f, a, e, mpls); return; |
fe9f1a6d OZ |
262 | default: bug("invalid type"); |
263 | } | |
264 | } | |
265 | ||
266 | ||
ce4aca09 MM |
267 | /** |
268 | * fib_get - find or create a FIB node | |
269 | * @f: FIB to work with | |
0f7d5b1a | 270 | * @n: network address |
ce4aca09 MM |
271 | * |
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. | |
274 | */ | |
62aa008a | 275 | void * |
0f7d5b1a | 276 | fib_get(struct fib *f, const net_addr *a) |
62aa008a | 277 | { |
23c212e7 | 278 | void *b = fib_find(f, a); |
fe9f1a6d OZ |
279 | if (b) |
280 | return b; | |
d82fc18d | 281 | |
fe9f1a6d OZ |
282 | if (f->fib_slab) |
283 | b = sl_alloc(f->fib_slab); | |
284 | else | |
285 | b = mb_alloc(f->fib_pool, f->node_size + a->length); | |
d82fc18d | 286 | |
23c212e7 | 287 | struct fib_node *e = fib_user_to_node(f, b); |
fe9f1a6d OZ |
288 | e->readers = NULL; |
289 | e->flags = 0; | |
fe9f1a6d | 290 | fib_insert(f, a, e); |
d82fc18d | 291 | |
fe9f1a6d OZ |
292 | memset(b, 0, f->node_offset); |
293 | if (f->init) | |
294 | f->init(b); | |
d82fc18d | 295 | |
62aa008a | 296 | if (f->entries++ > f->entries_max) |
3ab001b9 | 297 | fib_rehash(f, HASH_HI_STEP); |
d82fc18d | 298 | |
fe9f1a6d | 299 | return b; |
62aa008a MM |
300 | } |
301 | ||
04632fd7 OZ |
302 | static inline void * |
303 | fib_route_ip4(struct fib *f, net_addr_ip4 *n) | |
0f7d5b1a | 304 | { |
04632fd7 | 305 | void *r; |
0f7d5b1a | 306 | |
04632fd7 | 307 | while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
0f7d5b1a OZ |
308 | { |
309 | n->pxlen--; | |
310 | ip4_clrbit(&n->prefix, n->pxlen); | |
311 | } | |
312 | ||
04632fd7 | 313 | return r; |
0f7d5b1a OZ |
314 | } |
315 | ||
04632fd7 OZ |
316 | static inline void * |
317 | fib_route_ip6(struct fib *f, net_addr_ip6 *n) | |
0f7d5b1a | 318 | { |
04632fd7 | 319 | void *r; |
0f7d5b1a | 320 | |
04632fd7 | 321 | while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
0f7d5b1a OZ |
322 | { |
323 | n->pxlen--; | |
324 | ip6_clrbit(&n->prefix, n->pxlen); | |
325 | } | |
326 | ||
04632fd7 | 327 | return r; |
0f7d5b1a OZ |
328 | } |
329 | ||
ce4aca09 MM |
330 | /** |
331 | * fib_route - CIDR routing lookup | |
332 | * @f: FIB to search in | |
0f7d5b1a | 333 | * @n: network address |
ce4aca09 MM |
334 | * |
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 | |
337 | * that network. | |
338 | */ | |
56d6c530 | 339 | void * |
0f7d5b1a | 340 | fib_route(struct fib *f, const net_addr *n) |
56d6c530 | 341 | { |
0f7d5b1a | 342 | ASSERT(f->addr_type == n->type); |
56d6c530 | 343 | |
04632fd7 OZ |
344 | net_addr *n0 = alloca(n->length); |
345 | net_copy(n0, n); | |
346 | ||
0f7d5b1a OZ |
347 | switch (n->type) |
348 | { | |
349 | case NET_IP4: | |
350 | case NET_VPN4: | |
de9b87f5 | 351 | case NET_ROA4: |
77234bbb | 352 | case NET_FLOW4: |
04632fd7 | 353 | return fib_route_ip4(f, (net_addr_ip4 *) n0); |
0f7d5b1a OZ |
354 | |
355 | case NET_IP6: | |
356 | case NET_VPN6: | |
de9b87f5 | 357 | case NET_ROA6: |
77234bbb | 358 | case NET_FLOW6: |
04632fd7 | 359 | return fib_route_ip6(f, (net_addr_ip6 *) n0); |
0f7d5b1a OZ |
360 | |
361 | default: | |
362 | return NULL; | |
363 | } | |
56d6c530 MM |
364 | } |
365 | ||
04632fd7 | 366 | |
3ab001b9 MM |
367 | static inline void |
368 | fib_merge_readers(struct fib_iterator *i, struct fib_node *to) | |
369 | { | |
370 | if (to) | |
371 | { | |
372 | struct fib_iterator *j = to->readers; | |
373 | if (!j) | |
374 | { | |
375 | /* Fast path */ | |
376 | to->readers = i; | |
377 | i->prev = (struct fib_iterator *) to; | |
3ab001b9 | 378 | } |
8abbde02 MM |
379 | else |
380 | { | |
381 | /* Really merging */ | |
382 | while (j->next) | |
383 | j = j->next; | |
384 | j->next = i; | |
385 | i->prev = j; | |
386 | } | |
387 | while (i && i->node) | |
388 | { | |
389 | i->node = NULL; | |
390 | i = i->next; | |
391 | } | |
3ab001b9 MM |
392 | } |
393 | else /* No more nodes */ | |
394 | while (i) | |
395 | { | |
396 | i->prev = NULL; | |
397 | i = i->next; | |
398 | } | |
399 | } | |
400 | ||
ce4aca09 MM |
401 | /** |
402 | * fib_delete - delete a FIB node | |
403 | * @f: FIB to delete from | |
404 | * @E: entry to delete | |
405 | * | |
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. | |
409 | */ | |
62aa008a MM |
410 | void |
411 | fib_delete(struct fib *f, void *E) | |
412 | { | |
fe9f1a6d OZ |
413 | struct fib_node *e = fib_user_to_node(f, E); |
414 | uint h = fib_hash(f, e->addr); | |
3ab001b9 MM |
415 | struct fib_node **ee = f->hash_table + h; |
416 | struct fib_iterator *it; | |
62aa008a MM |
417 | |
418 | while (*ee) | |
419 | { | |
420 | if (*ee == e) | |
421 | { | |
422 | *ee = e->next; | |
3ab001b9 MM |
423 | if (it = e->readers) |
424 | { | |
425 | struct fib_node *l = e->next; | |
426 | while (!l) | |
427 | { | |
428 | h++; | |
429 | if (h >= f->hash_size) | |
430 | break; | |
431 | else | |
432 | l = f->hash_table[h]; | |
433 | } | |
434 | fib_merge_readers(it, l); | |
435 | } | |
04632fd7 OZ |
436 | |
437 | if (f->fib_slab) | |
438 | sl_free(f->fib_slab, E); | |
439 | else | |
440 | mb_free(E); | |
441 | ||
62aa008a | 442 | if (f->entries-- < f->entries_min) |
3ab001b9 | 443 | fib_rehash(f, -HASH_LO_STEP); |
62aa008a MM |
444 | return; |
445 | } | |
446 | ee = &((*ee)->next); | |
447 | } | |
08c69a77 | 448 | bug("fib_delete() called for invalid node"); |
62aa008a MM |
449 | } |
450 | ||
ce4aca09 MM |
451 | /** |
452 | * fib_free - delete a FIB | |
453 | * @f: FIB to be deleted | |
454 | * | |
455 | * This function deletes a FIB -- it frees all memory associated | |
456 | * with it and all its entries. | |
457 | */ | |
62aa008a MM |
458 | void |
459 | fib_free(struct fib *f) | |
460 | { | |
461 | fib_ht_free(f->hash_table); | |
462 | rfree(f->fib_slab); | |
463 | } | |
3ab001b9 MM |
464 | |
465 | void | |
466 | fit_init(struct fib_iterator *i, struct fib *f) | |
467 | { | |
468 | unsigned h; | |
469 | struct fib_node *n; | |
470 | ||
471 | i->efef = 0xff; | |
472 | for(h=0; h<f->hash_size; h++) | |
473 | if (n = f->hash_table[h]) | |
474 | { | |
475 | i->prev = (struct fib_iterator *) n; | |
476 | if (i->next = n->readers) | |
477 | i->next->prev = i; | |
478 | n->readers = i; | |
479 | i->node = n; | |
480 | return; | |
481 | } | |
482 | /* The fib is empty, nothing to do */ | |
483 | i->prev = i->next = NULL; | |
484 | i->node = NULL; | |
485 | } | |
486 | ||
487 | struct fib_node * | |
488 | fit_get(struct fib *f, struct fib_iterator *i) | |
489 | { | |
490 | struct fib_node *n; | |
491 | struct fib_iterator *j, *k; | |
492 | ||
493 | if (!i->prev) | |
494 | { | |
495 | /* We are at the end */ | |
8abbde02 | 496 | i->hash = ~0 - 1; |
3ab001b9 MM |
497 | return NULL; |
498 | } | |
499 | if (!(n = i->node)) | |
500 | { | |
501 | /* No node info available, we are a victim of merging. Try harder. */ | |
502 | j = i; | |
503 | while (j->efef == 0xff) | |
504 | j = j->prev; | |
505 | n = (struct fib_node *) j; | |
506 | } | |
507 | j = i->prev; | |
508 | if (k = i->next) | |
509 | k->prev = j; | |
510 | j->next = k; | |
fe9f1a6d | 511 | i->hash = fib_hash(f, n->addr); |
3ab001b9 MM |
512 | return n; |
513 | } | |
514 | ||
515 | void | |
516 | fit_put(struct fib_iterator *i, struct fib_node *n) | |
517 | { | |
518 | struct fib_iterator *j; | |
519 | ||
520 | i->node = n; | |
521 | if (j = n->readers) | |
522 | j->prev = i; | |
523 | i->next = j; | |
524 | n->readers = i; | |
525 | i->prev = (struct fib_iterator *) n; | |
526 | } | |
527 | ||
8465dccb OZ |
528 | void |
529 | fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos) | |
530 | { | |
531 | if (n = n->next) | |
532 | goto found; | |
533 | ||
534 | while (++hpos < f->hash_size) | |
535 | if (n = f->hash_table[hpos]) | |
536 | goto found; | |
537 | ||
538 | /* We are at the end */ | |
539 | i->prev = i->next = NULL; | |
540 | i->node = NULL; | |
541 | return; | |
542 | ||
543 | found: | |
544 | fit_put(i, n); | |
545 | } | |
546 | ||
3ab001b9 MM |
547 | #ifdef DEBUGGING |
548 | ||
ce4aca09 MM |
549 | /** |
550 | * fib_check - audit a FIB | |
551 | * @f: FIB to be checked | |
552 | * | |
553 | * This debugging function audits a FIB by checking its internal consistency. | |
58f7d004 | 554 | * Use when you suspect somebody of corrupting innocent data structures. |
ce4aca09 | 555 | */ |
3ab001b9 MM |
556 | void |
557 | fib_check(struct fib *f) | |
558 | { | |
e87a95d9 | 559 | uint i, ec, nulls; |
3ab001b9 MM |
560 | |
561 | ec = 0; | |
562 | for(i=0; i<f->hash_size; i++) | |
563 | { | |
564 | struct fib_node *n; | |
3ab001b9 MM |
565 | for(n=f->hash_table[i]; n; n=n->next) |
566 | { | |
567 | struct fib_iterator *j, *j0; | |
e87a95d9 OZ |
568 | uint h0 = fib_hash(f, n->addr); |
569 | if (h0 != i) | |
08c69a77 | 570 | bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order); |
3ab001b9 MM |
571 | j0 = (struct fib_iterator *) n; |
572 | nulls = 0; | |
573 | for(j=n->readers; j; j=j->next) | |
574 | { | |
575 | if (j->prev != j0) | |
08c69a77 | 576 | bug("fib_check: iterator->prev mismatch"); |
3ab001b9 MM |
577 | j0 = j; |
578 | if (!j->node) | |
579 | nulls++; | |
580 | else if (nulls) | |
08c69a77 | 581 | bug("fib_check: iterator nullified"); |
3ab001b9 | 582 | else if (j->node != n) |
08c69a77 | 583 | bug("fib_check: iterator->node mismatch"); |
3ab001b9 MM |
584 | } |
585 | ec++; | |
586 | } | |
587 | } | |
588 | if (ec != f->entries) | |
08c69a77 | 589 | bug("fib_check: invalid entry count (%d != %d)", ec, f->entries); |
23c212e7 | 590 | return; |
3ab001b9 MM |
591 | } |
592 | ||
fe9f1a6d OZ |
593 | /* |
594 | int | |
595 | fib_histogram(struct fib *f) | |
596 | { | |
597 | log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries); | |
598 | ||
599 | int i, j; | |
600 | struct fib_node *e; | |
601 | ||
602 | for (i = 0; i < f->hash_size; i++) | |
603 | { | |
604 | j = 0; | |
605 | for (e = f->hash_table[i]; e != NULL; e = e->next) | |
606 | j++; | |
607 | if (j > 0) | |
a82f692e | 608 | log(L_WARN "Histogram line %d: %d", i, j); |
fe9f1a6d OZ |
609 | } |
610 | ||
611 | log(L_WARN "Histogram dump end"); | |
612 | } | |
613 | */ | |
614 | ||
3ab001b9 MM |
615 | #endif |
616 | ||
617 | #ifdef TEST | |
618 | ||
619 | #include "lib/resource.h" | |
620 | ||
621 | struct fib f; | |
622 | ||
623 | void dump(char *m) | |
624 | { | |
ae80a2de | 625 | uint i; |
3ab001b9 MM |
626 | |
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++) | |
629 | { | |
630 | struct fib_node *n; | |
631 | struct fib_iterator *j; | |
632 | for(n=f.hash_table[i]; n; n=n->next) | |
633 | { | |
fe9f1a6d | 634 | debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr); |
3ab001b9 MM |
635 | for(j=n->readers; j; j=j->next) |
636 | debug(" %p[%p]", j, j->node); | |
637 | debug("\n"); | |
638 | } | |
639 | } | |
640 | fib_check(&f); | |
641 | debug("-----\n"); | |
642 | } | |
643 | ||
644 | void init(struct fib_node *n) | |
645 | { | |
646 | } | |
647 | ||
648 | int main(void) | |
649 | { | |
650 | struct fib_node *n; | |
651 | struct fib_iterator i, j; | |
652 | ip_addr a; | |
653 | int c; | |
654 | ||
655 | log_init_debug(NULL); | |
656 | resource_init(); | |
657 | fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); | |
658 | dump("init"); | |
659 | ||
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); | |
666 | dump("fill"); | |
667 | ||
668 | fit_init(&i, &f); | |
669 | dump("iter init"); | |
670 | ||
671 | fib_rehash(&f, 1); | |
672 | dump("rehash up"); | |
673 | ||
674 | fib_rehash(&f, -1); | |
675 | dump("rehash down"); | |
676 | ||
677 | next: | |
678 | c = 0; | |
679 | FIB_ITERATE_START(&f, &i, z) | |
680 | { | |
681 | if (c) | |
682 | { | |
683 | FIB_ITERATE_PUT(&i, z); | |
684 | dump("iter"); | |
685 | goto next; | |
686 | } | |
687 | c = 1; | |
688 | debug("got %p\n", z); | |
689 | } | |
6264aad1 | 690 | FIB_ITERATE_END(z); |
3ab001b9 MM |
691 | dump("iter end"); |
692 | ||
693 | fit_init(&i, &f); | |
694 | fit_init(&j, &f); | |
695 | dump("iter init 2"); | |
696 | ||
697 | n = fit_get(&f, &i); | |
698 | dump("iter step 2"); | |
699 | ||
700 | fit_put(&i, n->next); | |
701 | dump("iter step 3"); | |
702 | ||
703 | a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); | |
704 | fib_delete(&f, n); | |
705 | dump("iter step 3"); | |
706 | ||
707 | return 0; | |
708 | } | |
709 | ||
710 | #endif |