iofbirddaemon / nest / rtfib.c @ 600998fc
History  View  Annotate  Download (14.5 KB)
1 
/*


2 
* BIRD  Forwarding Information Base  Data Structures

3 
*

4 
* (c) 19982000 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 twostage hashing where we calculate a 16bit 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 
* rehashing 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  
37 
#undef LOCAL_DEBUG

38  
39 
#include "nest/bird.h" 
40 
#include "nest/route.h" 
41 
#include "lib/string.h" 
42  
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 
50  
51  
52 
static void 
53 
fib_ht_alloc(struct fib *f)

54 
{ 
55 
f>hash_size = 1 << f>hash_order;

56 
f>hash_shift = 32  f>hash_order;

57 
if (f>hash_order > HASH_HI_MAX  HASH_HI_STEP)

58 
f>entries_max = ~0;

59 
else

60 
f>entries_max = f>hash_size HASH_HI_MARK; 
61 
if (f>hash_order < HASH_LO_MIN + HASH_LO_STEP)

62 
f>entries_min = 0;

63 
else

64 
f>entries_min = f>hash_size HASH_LO_MARK; 
65 
DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",

66 
f>hash_order, f>hash_size, f>entries_min, f>entries_max); 
67 
f>hash_table = mb_alloc(f>fib_pool, f>hash_size * sizeof(struct fib_node *)); 
68 
} 
69  
70 
static inline void 
71 
fib_ht_free(struct fib_node **h)

72 
{ 
73 
mb_free(h); 
74 
} 
75  
76  
77 
static u32

78 
fib_hash(struct fib *f, const net_addr *a); 
79  
80 
/**

81 
* fib_init  initialize a new FIB

82 
* @f: the FIB to be initialized (the structure itself being allocated by the caller)

83 
* @p: pool to allocate the nodes in

84 
* @node_size: node size to be used (each node consists of a standard header &fib_node

85 
* followed by user data)

86 
* @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order

87 
* (recommended)

88 
* @init: pointer a function to be called to initialize a newly created node

89 
*

90 
* This function initializes a newly allocated FIB and prepares it for use.

91 
*/

92 
void

93 
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)

94 
{ 
95 
uint addr_length = net_addr_length[addr_type]; 
96  
97 
if (!hash_order)

98 
hash_order = HASH_DEF_ORDER; 
99 
f>fib_pool = p; 
100 
f>fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL;

101 
f>addr_type = addr_type; 
102 
f>node_size = node_size; 
103 
f>node_offset = node_offset; 
104 
f>hash_order = hash_order; 
105 
fib_ht_alloc(f); 
106 
bzero(f>hash_table, f>hash_size * sizeof(struct fib_node *)); 
107 
f>entries = 0;

108 
f>entries_min = 0;

109 
f>init = init; 
110 
} 
111  
112 
static void 
113 
fib_rehash(struct fib *f, int step) 
114 
{ 
115 
unsigned old, new, oldn, newn, ni, nh;

116 
struct fib_node **n, *e, *x, **t, **m, **h;

117  
118 
old = f>hash_order; 
119 
oldn = f>hash_size; 
120 
new = old + step; 
121 
m = h = f>hash_table; 
122 
DBG("Rehashing FIB from order %d to %d\n", old, new);

123 
f>hash_order = new; 
124 
fib_ht_alloc(f); 
125 
t = n = f>hash_table; 
126 
newn = f>hash_size; 
127 
ni = 0;

128  
129 
while (oldn)

130 
{ 
131 
x = *h++; 
132 
while (e = x)

133 
{ 
134 
x = e>next; 
135 
nh = fib_hash(f, e>addr); 
136 
while (nh > ni)

137 
{ 
138 
*t = NULL;

139 
ni++; 
140 
t = ++n; 
141 
} 
142 
*t = e; 
143 
t = &e>next; 
144 
} 
145 
} 
146 
while (ni < newn)

147 
{ 
148 
*t = NULL;

149 
ni++; 
150 
t = ++n; 
151 
} 
152 
fib_ht_free(m); 
153 
} 
154  
155 
#define CAST(t) (const net_addr_##t *) 
156 
#define CAST2(t) (net_addr_##t *) 
157  
158 
#define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f>hash_shift) 
159  
160 
#define FIB_FIND(f,a,t) \

161 
({ \ 
162 
struct fib_node *e = f>hash_table[FIB_HASH(f, a, t)]; \

163 
while (e && !net_equal_##t(CAST(t) e>addr, CAST(t) a)) \ 
164 
e = e>next; \ 
165 
fib_node_to_user(f, e); \ 
166 
}) 
167  
168 
#define FIB_INSERT(f,a,e,t) \

169 
({ \ 
170 
u32 h = net_hash_##t(CAST(t) a); \ 
171 
struct fib_node **ee = f>hash_table + (h >> f>hash_shift); \

172 
struct fib_node *g; \

173 
\ 
174 
while ((g = *ee) && (net_hash_##t(CAST(t) g>addr) < h)) \ 
175 
ee = &g>next; \ 
176 
\ 
177 
net_copy_##t(CAST2(t) e>addr, CAST(t) a); \ 
178 
e>next = *ee; \ 
179 
*ee = e; \ 
180 
}) 
181  
182  
183 
static u32

184 
fib_hash(struct fib *f, const net_addr *a) 
185 
{ 
186 
switch (f>addr_type)

187 
{ 
188 
case NET_IP4: return FIB_HASH(f, a, ip4); 
189 
case NET_IP6: return FIB_HASH(f, a, ip6); 
190 
case NET_VPN4: return FIB_HASH(f, a, vpn4); 
191 
case NET_VPN6: return FIB_HASH(f, a, vpn6); 
192 
default: bug("invalid type"); 
193 
} 
194 
} 
195  
196 
/**

197 
* fib_find  search for FIB node by prefix

198 
* @f: FIB to search in

199 
* @n: network address

200 
*

201 
* Search for a FIB node corresponding to the given prefix, return

202 
* a pointer to it or %NULL if no such node exists.

203 
*/

204 
void *

205 
fib_find(struct fib *f, const net_addr *a) 
206 
{ 
207 
ASSERT(f>addr_type == a>type); 
208  
209 
switch (f>addr_type)

210 
{ 
211 
case NET_IP4: return FIB_FIND(f, a, ip4); 
212 
case NET_IP6: return FIB_FIND(f, a, ip6); 
213 
case NET_VPN4: return FIB_FIND(f, a, vpn4); 
214 
case NET_VPN6: return FIB_FIND(f, a, vpn6); 
215 
default: bug("invalid type"); 
216 
} 
217 
} 
218  
219 
static void 
220 
fib_insert(struct fib *f, const net_addr *a, struct fib_node *e) 
221 
{ 
222 
switch (f>addr_type)

223 
{ 
224 
case NET_IP4: FIB_INSERT(f, a, e, ip4); return; 
225 
case NET_IP6: FIB_INSERT(f, a, e, ip6); return; 
226 
case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return; 
227 
case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return; 
228 
default: bug("invalid type"); 
229 
} 
230 
} 
231  
232  
233 
/**

234 
* fib_get  find or create a FIB node

235 
* @f: FIB to work with

236 
* @n: network address

237 
*

238 
* Search for a FIB node corresponding to the given prefix and

239 
* return a pointer to it. If no such node exists, create it.

240 
*/

241 
void *

242 
fib_get(struct fib *f, const net_addr *a) 
243 
{ 
244 
void *b = fib_find(f, a);

245 
if (b)

246 
return b;

247  
248 
if (f>fib_slab)

249 
b = sl_alloc(f>fib_slab); 
250 
else

251 
b = mb_alloc(f>fib_pool, f>node_size + a>length); 
252  
253 
struct fib_node *e = fib_user_to_node(f, b);

254 
e>readers = NULL;

255 
e>flags = 0;

256 
e>uid = 0;

257 
fib_insert(f, a, e); 
258  
259 
memset(b, 0, f>node_offset);

260 
if (f>init)

261 
f>init(b); 
262  
263 
if (f>entries++ > f>entries_max)

264 
fib_rehash(f, HASH_HI_STEP); 
265  
266 
return b;

267 
} 
268  
269 
static void * 
270 
fib_route_ip4(struct fib *f, const net_addr *n0) 
271 
{ 
272 
net_addr net; 
273 
net_addr_ip4 *n = (net_addr_ip4 *) &net; 
274 
void *b;

275  
276 
net_copy(&net, n0); 
277 
while (!(b = fib_find(f, &net)) && (n>pxlen > 0)) 
278 
{ 
279 
n>pxlen; 
280 
ip4_clrbit(&n>prefix, n>pxlen); 
281 
} 
282  
283 
return b;

284 
} 
285  
286 
static void * 
287 
fib_route_ip6(struct fib *f, const net_addr *n0) 
288 
{ 
289 
net_addr net; 
290 
net_addr_ip6 *n = (net_addr_ip6 *) &net; 
291 
void *b;

292  
293 
net_copy(&net, n0); 
294 
while (!(b = fib_find(f, &net)) && (n>pxlen > 0)) 
295 
{ 
296 
n>pxlen; 
297 
ip6_clrbit(&n>prefix, n>pxlen); 
298 
} 
299  
300 
return b;

301 
} 
302  
303 
/**

304 
* fib_route  CIDR routing lookup

305 
* @f: FIB to search in

306 
* @n: network address

307 
*

308 
* Search for a FIB node with longest prefix matching the given

309 
* network, that is a node which a CIDR router would use for routing

310 
* that network.

311 
*/

312 
void *

313 
fib_route(struct fib *f, const net_addr *n) 
314 
{ 
315 
ASSERT(f>addr_type == n>type); 
316  
317 
switch (n>type)

318 
{ 
319 
case NET_IP4:

320 
case NET_VPN4:

321 
return fib_route_ip4(f, n);

322  
323 
case NET_IP6:

324 
case NET_VPN6:

325 
return fib_route_ip6(f, n);

326  
327 
default:

328 
return NULL; 
329 
} 
330 
} 
331  
332 
static inline void 
333 
fib_merge_readers(struct fib_iterator *i, struct fib_node *to) 
334 
{ 
335 
if (to)

336 
{ 
337 
struct fib_iterator *j = to>readers;

338 
if (!j)

339 
{ 
340 
/* Fast path */

341 
to>readers = i; 
342 
i>prev = (struct fib_iterator *) to;

343 
} 
344 
else

345 
{ 
346 
/* Really merging */

347 
while (j>next)

348 
j = j>next; 
349 
j>next = i; 
350 
i>prev = j; 
351 
} 
352 
while (i && i>node)

353 
{ 
354 
i>node = NULL;

355 
i = i>next; 
356 
} 
357 
} 
358 
else /* No more nodes */ 
359 
while (i)

360 
{ 
361 
i>prev = NULL;

362 
i = i>next; 
363 
} 
364 
} 
365  
366 
/**

367 
* fib_delete  delete a FIB node

368 
* @f: FIB to delete from

369 
* @E: entry to delete

370 
*

371 
* This function removes the given entry from the FIB,

372 
* taking care of all the asynchronous readers by shifting

373 
* them to the next node in the canonical reading order.

374 
*/

375 
void

376 
fib_delete(struct fib *f, void *E) 
377 
{ 
378 
struct fib_node *e = fib_user_to_node(f, E);

379 
uint h = fib_hash(f, e>addr); 
380 
struct fib_node **ee = f>hash_table + h;

381 
struct fib_iterator *it;

382  
383 
while (*ee)

384 
{ 
385 
if (*ee == e)

386 
{ 
387 
*ee = e>next; 
388 
if (it = e>readers)

389 
{ 
390 
struct fib_node *l = e>next;

391 
while (!l)

392 
{ 
393 
h++; 
394 
if (h >= f>hash_size)

395 
break;

396 
else

397 
l = f>hash_table[h]; 
398 
} 
399 
fib_merge_readers(it, l); 
400 
} 
401 
sl_free(f>fib_slab, e); 
402 
if (f>entries < f>entries_min)

403 
fib_rehash(f, HASH_LO_STEP); 
404 
return;

405 
} 
406 
ee = &((*ee)>next); 
407 
} 
408 
bug("fib_delete() called for invalid node");

409 
} 
410  
411 
/**

412 
* fib_free  delete a FIB

413 
* @f: FIB to be deleted

414 
*

415 
* This function deletes a FIB  it frees all memory associated

416 
* with it and all its entries.

417 
*/

418 
void

419 
fib_free(struct fib *f)

420 
{ 
421 
fib_ht_free(f>hash_table); 
422 
rfree(f>fib_slab); 
423 
} 
424  
425 
void

426 
fit_init(struct fib_iterator *i, struct fib *f) 
427 
{ 
428 
unsigned h;

429 
struct fib_node *n;

430  
431 
i>efef = 0xff;

432 
for(h=0; h<f>hash_size; h++) 
433 
if (n = f>hash_table[h])

434 
{ 
435 
i>prev = (struct fib_iterator *) n;

436 
if (i>next = n>readers)

437 
i>next>prev = i; 
438 
n>readers = i; 
439 
i>node = n; 
440 
return;

441 
} 
442 
/* The fib is empty, nothing to do */

443 
i>prev = i>next = NULL;

444 
i>node = NULL;

445 
} 
446  
447 
struct fib_node *

448 
fit_get(struct fib *f, struct fib_iterator *i) 
449 
{ 
450 
struct fib_node *n;

451 
struct fib_iterator *j, *k;

452  
453 
if (!i>prev)

454 
{ 
455 
/* We are at the end */

456 
i>hash = ~0  1; 
457 
return NULL; 
458 
} 
459 
if (!(n = i>node))

460 
{ 
461 
/* No node info available, we are a victim of merging. Try harder. */

462 
j = i; 
463 
while (j>efef == 0xff) 
464 
j = j>prev; 
465 
n = (struct fib_node *) j;

466 
} 
467 
j = i>prev; 
468 
if (k = i>next)

469 
k>prev = j; 
470 
j>next = k; 
471 
i>hash = fib_hash(f, n>addr); 
472 
return n;

473 
} 
474  
475 
void

476 
fit_put(struct fib_iterator *i, struct fib_node *n) 
477 
{ 
478 
struct fib_iterator *j;

479  
480 
i>node = n; 
481 
if (j = n>readers)

482 
j>prev = i; 
483 
i>next = j; 
484 
n>readers = i; 
485 
i>prev = (struct fib_iterator *) n;

486 
} 
487  
488 
void

489 
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos) 
490 
{ 
491 
if (n = n>next)

492 
goto found;

493  
494 
while (++hpos < f>hash_size)

495 
if (n = f>hash_table[hpos])

496 
goto found;

497  
498 
/* We are at the end */

499 
i>prev = i>next = NULL;

500 
i>node = NULL;

501 
return;

502  
503 
found:

504 
fit_put(i, n); 
505 
} 
506  
507 
#ifdef DEBUGGING

508  
509 
/**

510 
* fib_check  audit a FIB

511 
* @f: FIB to be checked

512 
*

513 
* This debugging function audits a FIB by checking its internal consistency.

514 
* Use when you suspect somebody of corrupting innocent data structures.

515 
*/

516 
void

517 
fib_check(struct fib *f)

518 
{ 
519 
#if 0

520 
uint i, ec, lo, nulls;

521 

522 
ec = 0;

523 
for(i=0; i<f>hash_size; i++)

524 
{

525 
struct fib_node *n;

526 
lo = 0;

527 
for(n=f>hash_table[i]; n; n=n>next)

528 
{

529 
struct fib_iterator *j, *j0;

530 
uint h0 = ipa_hash(n>prefix);

531 
if (h0 < lo)

532 
bug("fib_check: discord in hash chains");

533 
lo = h0;

534 
if ((h0 >> f>hash_shift) != i)

535 
bug("fib_check: mishashed %x>%x (order %d)", h0, i, f>hash_order);

536 
j0 = (struct fib_iterator *) n;

537 
nulls = 0;

538 
for(j=n>readers; j; j=j>next)

539 
{

540 
if (j>prev != j0)

541 
bug("fib_check: iterator>prev mismatch");

542 
j0 = j;

543 
if (!j>node)

544 
nulls++;

545 
else if (nulls)

546 
bug("fib_check: iterator nullified");

547 
else if (j>node != n)

548 
bug("fib_check: iterator>node mismatch");

549 
}

550 
ec++;

551 
}

552 
}

553 
if (ec != f>entries)

554 
bug("fib_check: invalid entry count (%d != %d)", ec, f>entries);

555 
#endif

556 
return;

557 
} 
558  
559 
/*

560 
int

561 
fib_histogram(struct fib *f)

562 
{

563 
log(L_WARN "Histogram dump start %d %d", f>hash_size, f>entries);

564 

565 
int i, j;

566 
struct fib_node *e;

567 

568 
for (i = 0; i < f>hash_size; i++)

569 
{

570 
j = 0;

571 
for (e = f>hash_table[i]; e != NULL; e = e>next)

572 
j++;

573 
if (j > 0)

574 
log(L_WARN "Histogram line %d: %d", i, j);

575 
}

576 

577 
log(L_WARN "Histogram dump end");

578 
}

579 
*/

580  
581 
#endif

582  
583 
#ifdef TEST

584  
585 
#include "lib/resource.h" 
586  
587 
struct fib f;

588  
589 
void dump(char *m) 
590 
{ 
591 
uint i; 
592  
593 
debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);

594 
for(i=0; i<f.hash_size; i++) 
595 
{ 
596 
struct fib_node *n;

597 
struct fib_iterator *j;

598 
for(n=f.hash_table[i]; n; n=n>next)

599 
{ 
600 
debug("%04x %08x %p %N", i, ipa_hash(n>prefix), n, n>addr);

601 
for(j=n>readers; j; j=j>next)

602 
debug(" %p[%p]", j, j>node);

603 
debug("\n");

604 
} 
605 
} 
606 
fib_check(&f); 
607 
debug("\n");

608 
} 
609  
610 
void init(struct fib_node *n) 
611 
{ 
612 
} 
613  
614 
int main(void) 
615 
{ 
616 
struct fib_node *n;

617 
struct fib_iterator i, j;

618 
ip_addr a; 
619 
int c;

620  
621 
log_init_debug(NULL);

622 
resource_init(); 
623 
fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); 
624 
dump("init");

625  
626 
a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32); 
627 
a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32); 
628 
a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32); 
629 
a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32); 
630 
a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32); 
631 
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); 
632 
dump("fill");

633  
634 
fit_init(&i, &f); 
635 
dump("iter init");

636  
637 
fib_rehash(&f, 1);

638 
dump("rehash up");

639  
640 
fib_rehash(&f, 1);

641 
dump("rehash down");

642  
643 
next:

644 
c = 0;

645 
FIB_ITERATE_START(&f, &i, z) 
646 
{ 
647 
if (c)

648 
{ 
649 
FIB_ITERATE_PUT(&i, z); 
650 
dump("iter");

651 
goto next;

652 
} 
653 
c = 1;

654 
debug("got %p\n", z);

655 
} 
656 
FIB_ITERATE_END(z); 
657 
dump("iter end");

658  
659 
fit_init(&i, &f); 
660 
fit_init(&j, &f); 
661 
dump("iter init 2");

662  
663 
n = fit_get(&f, &i); 
664 
dump("iter step 2");

665  
666 
fit_put(&i, n>next); 
667 
dump("iter step 3");

668  
669 
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); 
670 
fib_delete(&f, n); 
671 
dump("iter step 3");

672  
673 
return 0; 
674 
} 
675  
676 
#endif
