]>
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 | |
a8d0f251 MM |
61 | /* |
62 | * The FIB rehash values are maintaining FIB count between N/5 and 2N. What | |
63 | * does it mean? | |
64 | * | |
65 | * +------------+--------+---------+-----------+----------+-----------+ | |
66 | * | Table size | Memory | Min cnt | net + rte | Max cnt | net + rte | | |
67 | * +------------+--------+---------+-----------+----------+-----------+ | |
68 | * | 1k | 8k | 0 | 0 | 2k | 192 k | | |
69 | * | 2k | 16k | 409 | 38.3k | 4k | 384 k | | |
70 | * | 4k | 32k | 819 | 76.8k | 8k | 768 k | | |
71 | * | 8k | 64k | 1.6k | 153.6k | 16k | 1.5M | | |
72 | * | 16k | 128k | 3.2k | 307.1k | 32k | 3 M | | |
73 | * | 32k | 256k | 6.4k | 614.3k | 64k | 6 M | | |
74 | * | 64k | 512k | 12.8k | 1.2M | 128k | 12 M | | |
75 | * | 128k | 1024k | 25.6k | 2.4M | 256k | 24 M | | |
76 | * | 256k | 2M | 51.2k | 4.8M | 512k | 48 M | | |
77 | * | 512k | 4M | 102.4k | 9.6M | 1M | 96 M | | |
78 | * | 1M | 8M | 204.8k | 19.2M | 2M | 192 M | | |
79 | * | 2M | 16M | 409.6k | 38.4M | 4M | 384 M | | |
80 | * | 4M | 32M | 819.2k | 76.8M | 8M | 768 M | | |
81 | * | 8M | 64M | 1.6M | 153.6M | infinity | infinity | | |
82 | * +------------+--------+---------+-----------+----------+-----------+ | |
83 | * | |
84 | * Table size shows how many slots are in FIB table. | |
85 | * Memory shows how much memory is eaten by FIB table. | |
86 | * Min cnt minimal number of nets in table of given size | |
87 | * Max cnt maximal number of nets in table of given size | |
88 | * net + rte memory eaten by 1 net and one route in it for min cnt and max cnt | |
89 | * | |
90 | * Example: If we have 750,000 network entries in a table: | |
91 | * * the table size may be 512k if we have never had more | |
92 | * * the table size may be 1M or 2M if we at least happened to have more | |
93 | * * 256k is too small, 8M is too big | |
94 | * | |
95 | * When growing, rehash is done on demand so we do it on every power of 2. | |
96 | * When shrinking, rehash is done on delete which is done (in global tables) | |
97 | * in a scheduled event. Rehashing down 2 steps. | |
98 | * | |
99 | */ | |
100 | ||
101 | ||
3ab001b9 | 102 | #define HASH_DEF_ORDER 10 |
a8d0f251 MM |
103 | #define HASH_HI_MARK * 2 |
104 | #define HASH_HI_STEP 1 | |
d73c4ac8 | 105 | #define HASH_HI_MAX 24 |
a8d0f251 | 106 | #define HASH_LO_MARK / 5 |
3ab001b9 MM |
107 | #define HASH_LO_STEP 2 |
108 | #define HASH_LO_MIN 10 | |
62aa008a | 109 | |
fe9f1a6d | 110 | |
62aa008a MM |
111 | static void |
112 | fib_ht_alloc(struct fib *f) | |
113 | { | |
3ab001b9 | 114 | f->hash_size = 1 << f->hash_order; |
23c212e7 | 115 | f->hash_shift = 32 - f->hash_order; |
3ab001b9 MM |
116 | if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP) |
117 | f->entries_max = ~0; | |
118 | else | |
119 | f->entries_max = f->hash_size HASH_HI_MARK; | |
120 | if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP) | |
62aa008a | 121 | f->entries_min = 0; |
3ab001b9 MM |
122 | else |
123 | f->entries_min = f->hash_size HASH_LO_MARK; | |
124 | DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n", | |
125 | f->hash_order, f->hash_size, f->entries_min, f->entries_max); | |
62aa008a | 126 | f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *)); |
62aa008a MM |
127 | } |
128 | ||
129 | static inline void | |
130 | fib_ht_free(struct fib_node **h) | |
131 | { | |
132 | mb_free(h); | |
133 | } | |
134 | ||
62aa008a | 135 | |
345e50d5 | 136 | static inline u32 fib_hash(struct fib *f, const net_addr *a); |
ce45fc12 | 137 | |
ce4aca09 MM |
138 | /** |
139 | * fib_init - initialize a new FIB | |
140 | * @f: the FIB to be initialized (the structure itself being allocated by the caller) | |
141 | * @p: pool to allocate the nodes in | |
142 | * @node_size: node size to be used (each node consists of a standard header &fib_node | |
143 | * followed by user data) | |
144 | * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order | |
145 | * (recommended) | |
146 | * @init: pointer a function to be called to initialize a newly created node | |
147 | * | |
148 | * This function initializes a newly allocated FIB and prepares it for use. | |
149 | */ | |
62aa008a | 150 | void |
fe9f1a6d | 151 | fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init) |
62aa008a | 152 | { |
fe9f1a6d OZ |
153 | uint addr_length = net_addr_length[addr_type]; |
154 | ||
3ab001b9 MM |
155 | if (!hash_order) |
156 | hash_order = HASH_DEF_ORDER; | |
62aa008a | 157 | f->fib_pool = p; |
fe9f1a6d OZ |
158 | f->fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL; |
159 | f->addr_type = addr_type; | |
160 | f->node_size = node_size; | |
161 | f->node_offset = node_offset; | |
3ab001b9 | 162 | f->hash_order = hash_order; |
62aa008a | 163 | fib_ht_alloc(f); |
3ab001b9 | 164 | bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *)); |
62aa008a MM |
165 | f->entries = 0; |
166 | f->entries_min = 0; | |
fe9f1a6d | 167 | f->init = init; |
62aa008a MM |
168 | } |
169 | ||
170 | static void | |
3ab001b9 | 171 | fib_rehash(struct fib *f, int step) |
62aa008a | 172 | { |
3ab001b9 | 173 | unsigned old, new, oldn, newn, ni, nh; |
62aa008a MM |
174 | struct fib_node **n, *e, *x, **t, **m, **h; |
175 | ||
3ab001b9 MM |
176 | old = f->hash_order; |
177 | oldn = f->hash_size; | |
178 | new = old + step; | |
62aa008a | 179 | m = h = f->hash_table; |
3ab001b9 MM |
180 | DBG("Re-hashing FIB from order %d to %d\n", old, new); |
181 | f->hash_order = new; | |
62aa008a | 182 | fib_ht_alloc(f); |
3ab001b9 MM |
183 | t = n = f->hash_table; |
184 | newn = f->hash_size; | |
185 | ni = 0; | |
186 | ||
6998bb9e | 187 | while (oldn--) |
62aa008a MM |
188 | { |
189 | x = *h++; | |
190 | while (e = x) | |
191 | { | |
192 | x = e->next; | |
fe9f1a6d | 193 | nh = fib_hash(f, e->addr); |
3ab001b9 MM |
194 | while (nh > ni) |
195 | { | |
196 | *t = NULL; | |
197 | ni++; | |
198 | t = ++n; | |
199 | } | |
62aa008a | 200 | *t = e; |
3ab001b9 | 201 | t = &e->next; |
62aa008a MM |
202 | } |
203 | } | |
3ab001b9 MM |
204 | while (ni < newn) |
205 | { | |
206 | *t = NULL; | |
207 | ni++; | |
208 | t = ++n; | |
209 | } | |
62aa008a MM |
210 | fib_ht_free(m); |
211 | } | |
212 | ||
0f7d5b1a OZ |
213 | #define CAST(t) (const net_addr_##t *) |
214 | #define CAST2(t) (net_addr_##t *) | |
fe9f1a6d OZ |
215 | |
216 | #define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift) | |
217 | ||
218 | #define FIB_FIND(f,a,t) \ | |
219 | ({ \ | |
220 | struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)]; \ | |
221 | while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a)) \ | |
222 | e = e->next; \ | |
600998fc | 223 | fib_node_to_user(f, e); \ |
fe9f1a6d OZ |
224 | }) |
225 | ||
226 | #define FIB_INSERT(f,a,e,t) \ | |
227 | ({ \ | |
228 | u32 h = net_hash_##t(CAST(t) a); \ | |
229 | struct fib_node **ee = f->hash_table + (h >> f->hash_shift); \ | |
230 | struct fib_node *g; \ | |
231 | \ | |
232 | while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h)) \ | |
233 | ee = &g->next; \ | |
234 | \ | |
0f7d5b1a | 235 | net_copy_##t(CAST2(t) e->addr, CAST(t) a); \ |
fe9f1a6d OZ |
236 | e->next = *ee; \ |
237 | *ee = e; \ | |
238 | }) | |
239 | ||
240 | ||
345e50d5 | 241 | static inline u32 |
0f7d5b1a | 242 | fib_hash(struct fib *f, const net_addr *a) |
fe9f1a6d | 243 | { |
345e50d5 OZ |
244 | /* Same as FIB_HASH() */ |
245 | return net_hash(a) >> f->hash_shift; | |
fe9f1a6d OZ |
246 | } |
247 | ||
0264ccf6 PT |
248 | void * |
249 | fib_get_chain(struct fib *f, const net_addr *a) | |
250 | { | |
251 | ASSERT(f->addr_type == a->type); | |
252 | ||
253 | struct fib_node *e = f->hash_table[fib_hash(f, a)]; | |
254 | return e; | |
255 | } | |
256 | ||
0f7d5b1a OZ |
257 | /** |
258 | * fib_find - search for FIB node by prefix | |
259 | * @f: FIB to search in | |
260 | * @n: network address | |
261 | * | |
262 | * Search for a FIB node corresponding to the given prefix, return | |
263 | * a pointer to it or %NULL if no such node exists. | |
264 | */ | |
fe9f1a6d | 265 | void * |
0f7d5b1a | 266 | fib_find(struct fib *f, const net_addr *a) |
fe9f1a6d OZ |
267 | { |
268 | ASSERT(f->addr_type == a->type); | |
269 | ||
270 | switch (f->addr_type) | |
271 | { | |
272 | case NET_IP4: return FIB_FIND(f, a, ip4); | |
273 | case NET_IP6: return FIB_FIND(f, a, ip6); | |
274 | case NET_VPN4: return FIB_FIND(f, a, vpn4); | |
275 | case NET_VPN6: return FIB_FIND(f, a, vpn6); | |
de9b87f5 PT |
276 | case NET_ROA4: return FIB_FIND(f, a, roa4); |
277 | case NET_ROA6: return FIB_FIND(f, a, roa6); | |
77234bbb OZ |
278 | case NET_FLOW4: return FIB_FIND(f, a, flow4); |
279 | case NET_FLOW6: return FIB_FIND(f, a, flow6); | |
be17805c | 280 | case NET_IP6_SADR: return FIB_FIND(f, a, ip6_sadr); |
66acbc8d | 281 | case NET_MPLS: return FIB_FIND(f, a, mpls); |
fe9f1a6d OZ |
282 | default: bug("invalid type"); |
283 | } | |
284 | } | |
285 | ||
286 | static void | |
0f7d5b1a | 287 | fib_insert(struct fib *f, const net_addr *a, struct fib_node *e) |
fe9f1a6d | 288 | { |
3f358161 JMM |
289 | ASSERT(f->addr_type == a->type); |
290 | ||
fe9f1a6d OZ |
291 | switch (f->addr_type) |
292 | { | |
293 | case NET_IP4: FIB_INSERT(f, a, e, ip4); return; | |
294 | case NET_IP6: FIB_INSERT(f, a, e, ip6); return; | |
295 | case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return; | |
296 | case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return; | |
de9b87f5 PT |
297 | case NET_ROA4: FIB_INSERT(f, a, e, roa4); return; |
298 | case NET_ROA6: FIB_INSERT(f, a, e, roa6); return; | |
77234bbb OZ |
299 | case NET_FLOW4: FIB_INSERT(f, a, e, flow4); return; |
300 | case NET_FLOW6: FIB_INSERT(f, a, e, flow6); return; | |
be17805c | 301 | case NET_IP6_SADR: FIB_INSERT(f, a, e, ip6_sadr); return; |
66acbc8d | 302 | case NET_MPLS: FIB_INSERT(f, a, e, mpls); return; |
fe9f1a6d OZ |
303 | default: bug("invalid type"); |
304 | } | |
305 | } | |
306 | ||
307 | ||
ce4aca09 MM |
308 | /** |
309 | * fib_get - find or create a FIB node | |
310 | * @f: FIB to work with | |
0f7d5b1a | 311 | * @n: network address |
ce4aca09 MM |
312 | * |
313 | * Search for a FIB node corresponding to the given prefix and | |
314 | * return a pointer to it. If no such node exists, create it. | |
315 | */ | |
62aa008a | 316 | void * |
0f7d5b1a | 317 | fib_get(struct fib *f, const net_addr *a) |
62aa008a | 318 | { |
23c212e7 | 319 | void *b = fib_find(f, a); |
fe9f1a6d OZ |
320 | if (b) |
321 | return b; | |
d82fc18d | 322 | |
fe9f1a6d OZ |
323 | if (f->fib_slab) |
324 | b = sl_alloc(f->fib_slab); | |
325 | else | |
326 | b = mb_alloc(f->fib_pool, f->node_size + a->length); | |
d82fc18d | 327 | |
23c212e7 | 328 | struct fib_node *e = fib_user_to_node(f, b); |
fe9f1a6d | 329 | e->readers = NULL; |
fe9f1a6d | 330 | fib_insert(f, a, e); |
d82fc18d | 331 | |
fe9f1a6d OZ |
332 | memset(b, 0, f->node_offset); |
333 | if (f->init) | |
334 | f->init(b); | |
d82fc18d | 335 | |
62aa008a | 336 | if (f->entries++ > f->entries_max) |
3ab001b9 | 337 | fib_rehash(f, HASH_HI_STEP); |
d82fc18d | 338 | |
fe9f1a6d | 339 | return b; |
62aa008a MM |
340 | } |
341 | ||
04632fd7 OZ |
342 | static inline void * |
343 | fib_route_ip4(struct fib *f, net_addr_ip4 *n) | |
0f7d5b1a | 344 | { |
04632fd7 | 345 | void *r; |
0f7d5b1a | 346 | |
04632fd7 | 347 | while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
0f7d5b1a OZ |
348 | { |
349 | n->pxlen--; | |
350 | ip4_clrbit(&n->prefix, n->pxlen); | |
351 | } | |
352 | ||
04632fd7 | 353 | return r; |
0f7d5b1a OZ |
354 | } |
355 | ||
04632fd7 OZ |
356 | static inline void * |
357 | fib_route_ip6(struct fib *f, net_addr_ip6 *n) | |
0f7d5b1a | 358 | { |
04632fd7 | 359 | void *r; |
0f7d5b1a | 360 | |
04632fd7 | 361 | while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0)) |
0f7d5b1a OZ |
362 | { |
363 | n->pxlen--; | |
364 | ip6_clrbit(&n->prefix, n->pxlen); | |
365 | } | |
366 | ||
04632fd7 | 367 | return r; |
0f7d5b1a OZ |
368 | } |
369 | ||
ce4aca09 MM |
370 | /** |
371 | * fib_route - CIDR routing lookup | |
372 | * @f: FIB to search in | |
0f7d5b1a | 373 | * @n: network address |
ce4aca09 MM |
374 | * |
375 | * Search for a FIB node with longest prefix matching the given | |
376 | * network, that is a node which a CIDR router would use for routing | |
377 | * that network. | |
378 | */ | |
56d6c530 | 379 | void * |
0f7d5b1a | 380 | fib_route(struct fib *f, const net_addr *n) |
56d6c530 | 381 | { |
0f7d5b1a | 382 | ASSERT(f->addr_type == n->type); |
56d6c530 | 383 | |
04632fd7 OZ |
384 | net_addr *n0 = alloca(n->length); |
385 | net_copy(n0, n); | |
386 | ||
0f7d5b1a OZ |
387 | switch (n->type) |
388 | { | |
389 | case NET_IP4: | |
390 | case NET_VPN4: | |
de9b87f5 | 391 | case NET_ROA4: |
77234bbb | 392 | case NET_FLOW4: |
04632fd7 | 393 | return fib_route_ip4(f, (net_addr_ip4 *) n0); |
0f7d5b1a OZ |
394 | |
395 | case NET_IP6: | |
396 | case NET_VPN6: | |
de9b87f5 | 397 | case NET_ROA6: |
77234bbb | 398 | case NET_FLOW6: |
04632fd7 | 399 | return fib_route_ip6(f, (net_addr_ip6 *) n0); |
0f7d5b1a OZ |
400 | |
401 | default: | |
402 | return NULL; | |
403 | } | |
56d6c530 MM |
404 | } |
405 | ||
04632fd7 | 406 | |
3ab001b9 MM |
407 | static inline void |
408 | fib_merge_readers(struct fib_iterator *i, struct fib_node *to) | |
409 | { | |
410 | if (to) | |
411 | { | |
412 | struct fib_iterator *j = to->readers; | |
413 | if (!j) | |
414 | { | |
415 | /* Fast path */ | |
416 | to->readers = i; | |
417 | i->prev = (struct fib_iterator *) to; | |
3ab001b9 | 418 | } |
8abbde02 MM |
419 | else |
420 | { | |
421 | /* Really merging */ | |
422 | while (j->next) | |
423 | j = j->next; | |
424 | j->next = i; | |
425 | i->prev = j; | |
426 | } | |
427 | while (i && i->node) | |
428 | { | |
429 | i->node = NULL; | |
430 | i = i->next; | |
431 | } | |
3ab001b9 MM |
432 | } |
433 | else /* No more nodes */ | |
434 | while (i) | |
435 | { | |
436 | i->prev = NULL; | |
437 | i = i->next; | |
438 | } | |
439 | } | |
440 | ||
ce4aca09 MM |
441 | /** |
442 | * fib_delete - delete a FIB node | |
443 | * @f: FIB to delete from | |
444 | * @E: entry to delete | |
445 | * | |
446 | * This function removes the given entry from the FIB, | |
447 | * taking care of all the asynchronous readers by shifting | |
448 | * them to the next node in the canonical reading order. | |
449 | */ | |
62aa008a MM |
450 | void |
451 | fib_delete(struct fib *f, void *E) | |
452 | { | |
fe9f1a6d OZ |
453 | struct fib_node *e = fib_user_to_node(f, E); |
454 | uint h = fib_hash(f, e->addr); | |
3ab001b9 MM |
455 | struct fib_node **ee = f->hash_table + h; |
456 | struct fib_iterator *it; | |
62aa008a MM |
457 | |
458 | while (*ee) | |
459 | { | |
460 | if (*ee == e) | |
461 | { | |
462 | *ee = e->next; | |
3ab001b9 MM |
463 | if (it = e->readers) |
464 | { | |
465 | struct fib_node *l = e->next; | |
466 | while (!l) | |
467 | { | |
468 | h++; | |
469 | if (h >= f->hash_size) | |
470 | break; | |
471 | else | |
472 | l = f->hash_table[h]; | |
473 | } | |
474 | fib_merge_readers(it, l); | |
475 | } | |
04632fd7 OZ |
476 | |
477 | if (f->fib_slab) | |
478 | sl_free(f->fib_slab, E); | |
479 | else | |
480 | mb_free(E); | |
481 | ||
62aa008a | 482 | if (f->entries-- < f->entries_min) |
3ab001b9 | 483 | fib_rehash(f, -HASH_LO_STEP); |
62aa008a MM |
484 | return; |
485 | } | |
486 | ee = &((*ee)->next); | |
487 | } | |
08c69a77 | 488 | bug("fib_delete() called for invalid node"); |
62aa008a MM |
489 | } |
490 | ||
ce4aca09 MM |
491 | /** |
492 | * fib_free - delete a FIB | |
493 | * @f: FIB to be deleted | |
494 | * | |
495 | * This function deletes a FIB -- it frees all memory associated | |
496 | * with it and all its entries. | |
497 | */ | |
62aa008a MM |
498 | void |
499 | fib_free(struct fib *f) | |
500 | { | |
501 | fib_ht_free(f->hash_table); | |
502 | rfree(f->fib_slab); | |
503 | } | |
3ab001b9 MM |
504 | |
505 | void | |
506 | fit_init(struct fib_iterator *i, struct fib *f) | |
507 | { | |
508 | unsigned h; | |
509 | struct fib_node *n; | |
510 | ||
511 | i->efef = 0xff; | |
512 | for(h=0; h<f->hash_size; h++) | |
513 | if (n = f->hash_table[h]) | |
514 | { | |
515 | i->prev = (struct fib_iterator *) n; | |
516 | if (i->next = n->readers) | |
517 | i->next->prev = i; | |
518 | n->readers = i; | |
519 | i->node = n; | |
520 | return; | |
521 | } | |
522 | /* The fib is empty, nothing to do */ | |
523 | i->prev = i->next = NULL; | |
524 | i->node = NULL; | |
525 | } | |
526 | ||
527 | struct fib_node * | |
528 | fit_get(struct fib *f, struct fib_iterator *i) | |
529 | { | |
530 | struct fib_node *n; | |
531 | struct fib_iterator *j, *k; | |
532 | ||
533 | if (!i->prev) | |
534 | { | |
535 | /* We are at the end */ | |
8abbde02 | 536 | i->hash = ~0 - 1; |
3ab001b9 MM |
537 | return NULL; |
538 | } | |
539 | if (!(n = i->node)) | |
540 | { | |
541 | /* No node info available, we are a victim of merging. Try harder. */ | |
542 | j = i; | |
543 | while (j->efef == 0xff) | |
544 | j = j->prev; | |
545 | n = (struct fib_node *) j; | |
546 | } | |
547 | j = i->prev; | |
548 | if (k = i->next) | |
549 | k->prev = j; | |
550 | j->next = k; | |
fe9f1a6d | 551 | i->hash = fib_hash(f, n->addr); |
3ab001b9 MM |
552 | return n; |
553 | } | |
554 | ||
555 | void | |
556 | fit_put(struct fib_iterator *i, struct fib_node *n) | |
557 | { | |
558 | struct fib_iterator *j; | |
559 | ||
560 | i->node = n; | |
561 | if (j = n->readers) | |
562 | j->prev = i; | |
563 | i->next = j; | |
564 | n->readers = i; | |
565 | i->prev = (struct fib_iterator *) n; | |
566 | } | |
567 | ||
8465dccb OZ |
568 | void |
569 | fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos) | |
570 | { | |
571 | if (n = n->next) | |
572 | goto found; | |
573 | ||
574 | while (++hpos < f->hash_size) | |
575 | if (n = f->hash_table[hpos]) | |
576 | goto found; | |
577 | ||
578 | /* We are at the end */ | |
579 | i->prev = i->next = NULL; | |
580 | i->node = NULL; | |
581 | return; | |
582 | ||
583 | found: | |
584 | fit_put(i, n); | |
585 | } | |
586 | ||
3ab001b9 MM |
587 | #ifdef DEBUGGING |
588 | ||
ce4aca09 MM |
589 | /** |
590 | * fib_check - audit a FIB | |
591 | * @f: FIB to be checked | |
592 | * | |
593 | * This debugging function audits a FIB by checking its internal consistency. | |
58f7d004 | 594 | * Use when you suspect somebody of corrupting innocent data structures. |
ce4aca09 | 595 | */ |
3ab001b9 MM |
596 | void |
597 | fib_check(struct fib *f) | |
598 | { | |
e87a95d9 | 599 | uint i, ec, nulls; |
3ab001b9 MM |
600 | |
601 | ec = 0; | |
602 | for(i=0; i<f->hash_size; i++) | |
603 | { | |
604 | struct fib_node *n; | |
3ab001b9 MM |
605 | for(n=f->hash_table[i]; n; n=n->next) |
606 | { | |
607 | struct fib_iterator *j, *j0; | |
e87a95d9 OZ |
608 | uint h0 = fib_hash(f, n->addr); |
609 | if (h0 != i) | |
08c69a77 | 610 | bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order); |
3ab001b9 MM |
611 | j0 = (struct fib_iterator *) n; |
612 | nulls = 0; | |
613 | for(j=n->readers; j; j=j->next) | |
614 | { | |
615 | if (j->prev != j0) | |
08c69a77 | 616 | bug("fib_check: iterator->prev mismatch"); |
3ab001b9 MM |
617 | j0 = j; |
618 | if (!j->node) | |
619 | nulls++; | |
620 | else if (nulls) | |
08c69a77 | 621 | bug("fib_check: iterator nullified"); |
3ab001b9 | 622 | else if (j->node != n) |
08c69a77 | 623 | bug("fib_check: iterator->node mismatch"); |
3ab001b9 MM |
624 | } |
625 | ec++; | |
626 | } | |
627 | } | |
628 | if (ec != f->entries) | |
08c69a77 | 629 | bug("fib_check: invalid entry count (%d != %d)", ec, f->entries); |
23c212e7 | 630 | return; |
3ab001b9 MM |
631 | } |
632 | ||
fe9f1a6d OZ |
633 | /* |
634 | int | |
635 | fib_histogram(struct fib *f) | |
636 | { | |
637 | log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries); | |
638 | ||
639 | int i, j; | |
640 | struct fib_node *e; | |
641 | ||
642 | for (i = 0; i < f->hash_size; i++) | |
643 | { | |
644 | j = 0; | |
645 | for (e = f->hash_table[i]; e != NULL; e = e->next) | |
646 | j++; | |
647 | if (j > 0) | |
a82f692e | 648 | log(L_WARN "Histogram line %d: %d", i, j); |
fe9f1a6d OZ |
649 | } |
650 | ||
651 | log(L_WARN "Histogram dump end"); | |
652 | } | |
653 | */ | |
654 | ||
3ab001b9 MM |
655 | #endif |
656 | ||
657 | #ifdef TEST | |
658 | ||
659 | #include "lib/resource.h" | |
660 | ||
661 | struct fib f; | |
662 | ||
663 | void dump(char *m) | |
664 | { | |
ae80a2de | 665 | uint i; |
3ab001b9 MM |
666 | |
667 | debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size); | |
668 | for(i=0; i<f.hash_size; i++) | |
669 | { | |
670 | struct fib_node *n; | |
671 | struct fib_iterator *j; | |
672 | for(n=f.hash_table[i]; n; n=n->next) | |
673 | { | |
fe9f1a6d | 674 | debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr); |
3ab001b9 MM |
675 | for(j=n->readers; j; j=j->next) |
676 | debug(" %p[%p]", j, j->node); | |
677 | debug("\n"); | |
678 | } | |
679 | } | |
680 | fib_check(&f); | |
681 | debug("-----\n"); | |
682 | } | |
683 | ||
684 | void init(struct fib_node *n) | |
685 | { | |
686 | } | |
687 | ||
688 | int main(void) | |
689 | { | |
690 | struct fib_node *n; | |
691 | struct fib_iterator i, j; | |
692 | ip_addr a; | |
693 | int c; | |
694 | ||
695 | log_init_debug(NULL); | |
696 | resource_init(); | |
697 | fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); | |
698 | dump("init"); | |
699 | ||
700 | a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32); | |
701 | a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32); | |
702 | a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32); | |
703 | a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32); | |
704 | a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32); | |
705 | a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); | |
706 | dump("fill"); | |
707 | ||
708 | fit_init(&i, &f); | |
709 | dump("iter init"); | |
710 | ||
711 | fib_rehash(&f, 1); | |
712 | dump("rehash up"); | |
713 | ||
714 | fib_rehash(&f, -1); | |
715 | dump("rehash down"); | |
716 | ||
717 | next: | |
718 | c = 0; | |
719 | FIB_ITERATE_START(&f, &i, z) | |
720 | { | |
721 | if (c) | |
722 | { | |
723 | FIB_ITERATE_PUT(&i, z); | |
724 | dump("iter"); | |
725 | goto next; | |
726 | } | |
727 | c = 1; | |
728 | debug("got %p\n", z); | |
729 | } | |
6264aad1 | 730 | FIB_ITERATE_END(z); |
3ab001b9 MM |
731 | dump("iter end"); |
732 | ||
733 | fit_init(&i, &f); | |
734 | fit_init(&j, &f); | |
735 | dump("iter init 2"); | |
736 | ||
737 | n = fit_get(&f, &i); | |
738 | dump("iter step 2"); | |
739 | ||
740 | fit_put(&i, n->next); | |
741 | dump("iter step 3"); | |
742 | ||
743 | a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); | |
744 | fib_delete(&f, n); | |
745 | dump("iter step 3"); | |
746 | ||
747 | return 0; | |
748 | } | |
749 | ||
750 | #endif |