iofbirddaemon / nest / rtfib.c @ 04632fd7
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 
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 inline void * 
270 
fib_route_ip4(struct fib *f, net_addr_ip4 *n)

271 
{ 
272 
void *r;

273  
274 
while (!(r = fib_find(f, (net_addr *) n)) && (n>pxlen > 0)) 
275 
{ 
276 
n>pxlen; 
277 
ip4_clrbit(&n>prefix, n>pxlen); 
278 
} 
279  
280 
return r;

281 
} 
282  
283 
static inline void * 
284 
fib_route_ip6(struct fib *f, net_addr_ip6 *n)

285 
{ 
286 
void *r;

287  
288 
while (!(r = fib_find(f, (net_addr *) n)) && (n>pxlen > 0)) 
289 
{ 
290 
n>pxlen; 
291 
ip6_clrbit(&n>prefix, n>pxlen); 
292 
} 
293  
294 
return r;

295 
} 
296  
297 
/**

298 
* fib_route  CIDR routing lookup

299 
* @f: FIB to search in

300 
* @n: network address

301 
*

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

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

304 
* that network.

305 
*/

306 
void *

307 
fib_route(struct fib *f, const net_addr *n) 
308 
{ 
309 
ASSERT(f>addr_type == n>type); 
310  
311 
net_addr *n0 = alloca(n>length); 
312 
net_copy(n0, n); 
313  
314 
switch (n>type)

315 
{ 
316 
case NET_IP4:

317 
case NET_VPN4:

318 
return fib_route_ip4(f, (net_addr_ip4 *) n0);

319  
320 
case NET_IP6:

321 
case NET_VPN6:

322 
return fib_route_ip6(f, (net_addr_ip6 *) n0);

323  
324 
default:

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

334 
{ 
335 
struct fib_iterator *j = to>readers;

336 
if (!j)

337 
{ 
338 
/* Fast path */

339 
to>readers = i; 
340 
i>prev = (struct fib_iterator *) to;

341 
} 
342 
else

343 
{ 
344 
/* Really merging */

345 
while (j>next)

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

351 
{ 
352 
i>node = NULL;

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

358 
{ 
359 
i>prev = NULL;

360 
i = i>next; 
361 
} 
362 
} 
363  
364 
/**

365 
* fib_delete  delete a FIB node

366 
* @f: FIB to delete from

367 
* @E: entry to delete

368 
*

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

370 
* taking care of all the asynchronous readers by shifting

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

372 
*/

373 
void

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

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

379 
struct fib_iterator *it;

380  
381 
while (*ee)

382 
{ 
383 
if (*ee == e)

384 
{ 
385 
*ee = e>next; 
386 
if (it = e>readers)

387 
{ 
388 
struct fib_node *l = e>next;

389 
while (!l)

390 
{ 
391 
h++; 
392 
if (h >= f>hash_size)

393 
break;

394 
else

395 
l = f>hash_table[h]; 
396 
} 
397 
fib_merge_readers(it, l); 
398 
} 
399  
400 
if (f>fib_slab)

401 
sl_free(f>fib_slab, E); 
402 
else

403 
mb_free(E); 
404  
405 
if (f>entries < f>entries_min)

406 
fib_rehash(f, HASH_LO_STEP); 
407 
return;

408 
} 
409 
ee = &((*ee)>next); 
410 
} 
411 
bug("fib_delete() called for invalid node");

412 
} 
413  
414 
/**

415 
* fib_free  delete a FIB

416 
* @f: FIB to be deleted

417 
*

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

419 
* with it and all its entries.

420 
*/

421 
void

422 
fib_free(struct fib *f)

423 
{ 
424 
fib_ht_free(f>hash_table); 
425 
rfree(f>fib_slab); 
426 
} 
427  
428 
void

429 
fit_init(struct fib_iterator *i, struct fib *f) 
430 
{ 
431 
unsigned h;

432 
struct fib_node *n;

433  
434 
i>efef = 0xff;

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

437 
{ 
438 
i>prev = (struct fib_iterator *) n;

439 
if (i>next = n>readers)

440 
i>next>prev = i; 
441 
n>readers = i; 
442 
i>node = n; 
443 
return;

444 
} 
445 
/* The fib is empty, nothing to do */

446 
i>prev = i>next = NULL;

447 
i>node = NULL;

448 
} 
449  
450 
struct fib_node *

451 
fit_get(struct fib *f, struct fib_iterator *i) 
452 
{ 
453 
struct fib_node *n;

454 
struct fib_iterator *j, *k;

455  
456 
if (!i>prev)

457 
{ 
458 
/* We are at the end */

459 
i>hash = ~0  1; 
460 
return NULL; 
461 
} 
462 
if (!(n = i>node))

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

465 
j = i; 
466 
while (j>efef == 0xff) 
467 
j = j>prev; 
468 
n = (struct fib_node *) j;

469 
} 
470 
j = i>prev; 
471 
if (k = i>next)

472 
k>prev = j; 
473 
j>next = k; 
474 
i>hash = fib_hash(f, n>addr); 
475 
return n;

476 
} 
477  
478 
void

479 
fit_put(struct fib_iterator *i, struct fib_node *n) 
480 
{ 
481 
struct fib_iterator *j;

482  
483 
i>node = n; 
484 
if (j = n>readers)

485 
j>prev = i; 
486 
i>next = j; 
487 
n>readers = i; 
488 
i>prev = (struct fib_iterator *) n;

489 
} 
490  
491 
void

492 
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos) 
493 
{ 
494 
if (n = n>next)

495 
goto found;

496  
497 
while (++hpos < f>hash_size)

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

499 
goto found;

500  
501 
/* We are at the end */

502 
i>prev = i>next = NULL;

503 
i>node = NULL;

504 
return;

505  
506 
found:

507 
fit_put(i, n); 
508 
} 
509  
510 
#ifdef DEBUGGING

511  
512 
/**

513 
* fib_check  audit a FIB

514 
* @f: FIB to be checked

515 
*

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

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

518 
*/

519 
void

520 
fib_check(struct fib *f)

521 
{ 
522 
#if 0

523 
uint i, ec, lo, nulls;

524 

525 
ec = 0;

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

527 
{

528 
struct fib_node *n;

529 
lo = 0;

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

531 
{

532 
struct fib_iterator *j, *j0;

533 
uint h0 = ipa_hash(n>prefix);

534 
if (h0 < lo)

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

536 
lo = h0;

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

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

539 
j0 = (struct fib_iterator *) n;

540 
nulls = 0;

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

542 
{

543 
if (j>prev != j0)

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

545 
j0 = j;

546 
if (!j>node)

547 
nulls++;

548 
else if (nulls)

549 
bug("fib_check: iterator nullified");

550 
else if (j>node != n)

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

552 
}

553 
ec++;

554 
}

555 
}

556 
if (ec != f>entries)

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

558 
#endif

559 
return;

560 
} 
561  
562 
/*

563 
int

564 
fib_histogram(struct fib *f)

565 
{

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

567 

568 
int i, j;

569 
struct fib_node *e;

570 

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

572 
{

573 
j = 0;

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

575 
j++;

576 
if (j > 0)

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

578 
}

579 

580 
log(L_WARN "Histogram dump end");

581 
}

582 
*/

583  
584 
#endif

585  
586 
#ifdef TEST

587  
588 
#include "lib/resource.h" 
589  
590 
struct fib f;

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

597 
for(i=0; i<f.hash_size; i++) 
598 
{ 
599 
struct fib_node *n;

600 
struct fib_iterator *j;

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

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

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

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

606 
debug("\n");

607 
} 
608 
} 
609 
fib_check(&f); 
610 
debug("\n");

611 
} 
612  
613 
void init(struct fib_node *n) 
614 
{ 
615 
} 
616  
617 
int main(void) 
618 
{ 
619 
struct fib_node *n;

620 
struct fib_iterator i, j;

621 
ip_addr a; 
622 
int c;

623  
624 
log_init_debug(NULL);

625 
resource_init(); 
626 
fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); 
627 
dump("init");

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

636  
637 
fit_init(&i, &f); 
638 
dump("iter init");

639  
640 
fib_rehash(&f, 1);

641 
dump("rehash up");

642  
643 
fib_rehash(&f, 1);

644 
dump("rehash down");

645  
646 
next:

647 
c = 0;

648 
FIB_ITERATE_START(&f, &i, z) 
649 
{ 
650 
if (c)

651 
{ 
652 
FIB_ITERATE_PUT(&i, z); 
653 
dump("iter");

654 
goto next;

655 
} 
656 
c = 1;

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

658 
} 
659 
FIB_ITERATE_END(z); 
660 
dump("iter end");

661  
662 
fit_init(&i, &f); 
663 
fit_init(&j, &f); 
664 
dump("iter init 2");

665  
666 
n = fit_get(&f, &i); 
667 
dump("iter step 2");

668  
669 
fit_put(&i, n>next); 
670 
dump("iter step 3");

671  
672 
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); 
673 
fib_delete(&f, n); 
674 
dump("iter step 3");

675  
676 
return 0; 
677 
} 
678  
679 
#endif
