Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / nest / rt-fib.c @ 6b3f1a54

History | View | Annotate | Download (16.5 KB)

1
/*
2
 *        BIRD -- Forwarding Information Base -- Data Structures
3
 *
4
 *        (c) 1998--2000 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 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.
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
 * 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.
53
 */
54

    
55
#undef LOCAL_DEBUG
56

    
57
#include "nest/bird.h"
58
#include "nest/route.h"
59
#include "lib/string.h"
60

    
61
#define HASH_DEF_ORDER 10
62
#define HASH_HI_MARK *4
63
#define HASH_HI_STEP 2
64
#define HASH_HI_MAX 16
65
#define HASH_LO_MARK /5
66
#define HASH_LO_STEP 2
67
#define HASH_LO_MIN 10
68

    
69

    
70
static void
71
fib_ht_alloc(struct fib *f)
72
{
73
  f->hash_size = 1 << f->hash_order;
74
  f->hash_shift = 32 - f->hash_order;
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)
80
    f->entries_min = 0;
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);
85
  f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
86
}
87

    
88
static inline void
89
fib_ht_free(struct fib_node **h)
90
{
91
  mb_free(h);
92
}
93

    
94

    
95
static u32
96
fib_hash(struct fib *f, const net_addr *a);
97

    
98
/**
99
 * fib_init - initialize a new FIB
100
 * @f: the FIB to be initialized (the structure itself being allocated by the caller)
101
 * @p: pool to allocate the nodes in
102
 * @node_size: node size to be used (each node consists of a standard header &fib_node
103
 * followed by user data)
104
 * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
105
 * (recommended)
106
 * @init: pointer a function to be called to initialize a newly created node
107
 *
108
 * This function initializes a newly allocated FIB and prepares it for use.
109
 */
110
void
111
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)
112
{
113
  uint addr_length = net_addr_length[addr_type];
114

    
115
  if (!hash_order)
116
    hash_order = HASH_DEF_ORDER;
117
  f->fib_pool = p;
118
  f->fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL;
119
  f->addr_type = addr_type;
120
  f->node_size = node_size;
121
  f->node_offset = node_offset;
122
  f->hash_order = hash_order;
123
  fib_ht_alloc(f);
124
  bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
125
  f->entries = 0;
126
  f->entries_min = 0;
127
  f->init = init;
128
}
129

    
130
static void
131
fib_rehash(struct fib *f, int step)
132
{
133
  unsigned old, new, oldn, newn, ni, nh;
134
  struct fib_node **n, *e, *x, **t, **m, **h;
135

    
136
  old = f->hash_order;
137
  oldn = f->hash_size;
138
  new = old + step;
139
  m = h = f->hash_table;
140
  DBG("Re-hashing FIB from order %d to %d\n", old, new);
141
  f->hash_order = new;
142
  fib_ht_alloc(f);
143
  t = n = f->hash_table;
144
  newn = f->hash_size;
145
  ni = 0;
146

    
147
  while (oldn--)
148
    {
149
      x = *h++;
150
      while (e = x)
151
        {
152
          x = e->next;
153
          nh = fib_hash(f, e->addr);
154
          while (nh > ni)
155
            {
156
              *t = NULL;
157
              ni++;
158
              t = ++n;
159
            }
160
          *t = e;
161
          t = &e->next;
162
        }
163
    }
164
  while (ni < newn)
165
    {
166
      *t = NULL;
167
      ni++;
168
      t = ++n;
169
    }
170
  fib_ht_free(m);
171
}
172

    
173
#define CAST(t) (const net_addr_##t *)
174
#define CAST2(t) (net_addr_##t *)
175

    
176
#define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift)
177

    
178
#define FIB_FIND(f,a,t)                                                        \
179
  ({                                                                        \
180
    struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)];                \
181
    while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a))                \
182
      e = e->next;                                                        \
183
    fib_node_to_user(f, e);                                                \
184
  })
185

    
186
#define FIB_INSERT(f,a,e,t)                                                \
187
  ({                                                                        \
188
  u32 h = net_hash_##t(CAST(t) a);                                        \
189
  struct fib_node **ee = f->hash_table + (h >> f->hash_shift);                \
190
  struct fib_node *g;                                                        \
191
                                                                        \
192
  while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h))                \
193
    ee = &g->next;                                                        \
194
                                                                        \
195
  net_copy_##t(CAST2(t) e->addr, CAST(t) a);                                \
196
  e->next = *ee;                                                        \
197
  *ee = e;                                                                \
198
  })
199

    
200

    
201
static u32
202
fib_hash(struct fib *f, const net_addr *a)
203
{
204
  ASSERT(f->addr_type == a->type);
205

    
206
  switch (f->addr_type)
207
  {
208
  case NET_IP4: return FIB_HASH(f, a, ip4);
209
  case NET_IP6: return FIB_HASH(f, a, ip6);
210
  case NET_VPN4: return FIB_HASH(f, a, vpn4);
211
  case NET_VPN6: return FIB_HASH(f, a, vpn6);
212
  case NET_ROA4: return FIB_HASH(f, a, roa4);
213
  case NET_ROA6: return FIB_HASH(f, a, roa6);
214
  case NET_FLOW4: return FIB_HASH(f, a, flow4);
215
  case NET_FLOW6: return FIB_HASH(f, a, flow6);
216
  case NET_MPLS: return FIB_HASH(f, a, mpls);
217
  default: bug("invalid type");
218
  }
219
}
220

    
221
void *
222
fib_get_chain(struct fib *f, const net_addr *a)
223
{
224
  ASSERT(f->addr_type == a->type);
225

    
226
  struct fib_node *e = f->hash_table[fib_hash(f, a)];
227
  return e;
228
}
229

    
230
/**
231
 * fib_find - search for FIB node by prefix
232
 * @f: FIB to search in
233
 * @n: network address
234
 *
235
 * Search for a FIB node corresponding to the given prefix, return
236
 * a pointer to it or %NULL if no such node exists.
237
 */
238
void *
239
fib_find(struct fib *f, const net_addr *a)
240
{
241
  ASSERT(f->addr_type == a->type);
242

    
243
  switch (f->addr_type)
244
  {
245
  case NET_IP4: return FIB_FIND(f, a, ip4);
246
  case NET_IP6: return FIB_FIND(f, a, ip6);
247
  case NET_VPN4: return FIB_FIND(f, a, vpn4);
248
  case NET_VPN6: return FIB_FIND(f, a, vpn6);
249
  case NET_ROA4: return FIB_FIND(f, a, roa4);
250
  case NET_ROA6: return FIB_FIND(f, a, roa6);
251
  case NET_FLOW4: return FIB_FIND(f, a, flow4);
252
  case NET_FLOW6: return FIB_FIND(f, a, flow6);
253
  case NET_MPLS: return FIB_FIND(f, a, mpls);
254
  default: bug("invalid type");
255
  }
256
}
257

    
258
static void
259
fib_insert(struct fib *f, const net_addr *a, struct fib_node *e)
260
{
261
  ASSERT(f->addr_type == a->type);
262

    
263
  switch (f->addr_type)
264
  {
265
  case NET_IP4: FIB_INSERT(f, a, e, ip4); return;
266
  case NET_IP6: FIB_INSERT(f, a, e, ip6); return;
267
  case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return;
268
  case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return;
269
  case NET_ROA4: FIB_INSERT(f, a, e, roa4); return;
270
  case NET_ROA6: FIB_INSERT(f, a, e, roa6); return;
271
  case NET_FLOW4: FIB_INSERT(f, a, e, flow4); return;
272
  case NET_FLOW6: FIB_INSERT(f, a, e, flow6); return;
273
  case NET_MPLS: FIB_INSERT(f, a, e, mpls); return;
274
  default: bug("invalid type");
275
  }
276
}
277

    
278

    
279
/**
280
 * fib_get - find or create a FIB node
281
 * @f: FIB to work with
282
 * @n: network address
283
 *
284
 * Search for a FIB node corresponding to the given prefix and
285
 * return a pointer to it. If no such node exists, create it.
286
 */
287
void *
288
fib_get(struct fib *f, const net_addr *a)
289
{
290
  void *b = fib_find(f, a);
291
  if (b)
292
    return b;
293

    
294
  if (f->fib_slab)
295
    b = sl_alloc(f->fib_slab);
296
  else
297
    b = mb_alloc(f->fib_pool, f->node_size + a->length);
298

    
299
  struct fib_node *e = fib_user_to_node(f, b);
300
  e->readers = NULL;
301
  e->flags = 0;
302
  fib_insert(f, a, e);
303

    
304
  memset(b, 0, f->node_offset);
305
  if (f->init)
306
    f->init(b);
307

    
308
  if (f->entries++ > f->entries_max)
309
    fib_rehash(f, HASH_HI_STEP);
310

    
311
  return b;
312
}
313

    
314
static inline void *
315
fib_route_ip4(struct fib *f, net_addr_ip4 *n)
316
{
317
  void *r;
318

    
319
  while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0))
320
  {
321
    n->pxlen--;
322
    ip4_clrbit(&n->prefix, n->pxlen);
323
  }
324

    
325
  return r;
326
}
327

    
328
static inline void *
329
fib_route_ip6(struct fib *f, net_addr_ip6 *n)
330
{
331
  void *r;
332

    
333
  while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0))
334
  {
335
    n->pxlen--;
336
    ip6_clrbit(&n->prefix, n->pxlen);
337
  }
338

    
339
  return r;
340
}
341

    
342
/**
343
 * fib_route - CIDR routing lookup
344
 * @f: FIB to search in
345
 * @n: network address
346
 *
347
 * Search for a FIB node with longest prefix matching the given
348
 * network, that is a node which a CIDR router would use for routing
349
 * that network.
350
 */
351
void *
352
fib_route(struct fib *f, const net_addr *n)
353
{
354
  ASSERT(f->addr_type == n->type);
355

    
356
  net_addr *n0 = alloca(n->length);
357
  net_copy(n0, n);
358

    
359
  switch (n->type)
360
  {
361
  case NET_IP4:
362
  case NET_VPN4:
363
  case NET_ROA4:
364
  case NET_FLOW4:
365
    return fib_route_ip4(f, (net_addr_ip4 *) n0);
366

    
367
  case NET_IP6:
368
  case NET_VPN6:
369
  case NET_ROA6:
370
  case NET_FLOW6:
371
    return fib_route_ip6(f, (net_addr_ip6 *) n0);
372

    
373
  default:
374
    return NULL;
375
  }
376
}
377

    
378

    
379
static inline void
380
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
381
{
382
  if (to)
383
    {
384
      struct fib_iterator *j = to->readers;
385
      if (!j)
386
        {
387
          /* Fast path */
388
          to->readers = i;
389
          i->prev = (struct fib_iterator *) to;
390
        }
391
      else
392
        {
393
          /* Really merging */
394
          while (j->next)
395
            j = j->next;
396
          j->next = i;
397
          i->prev = j;
398
        }
399
      while (i && i->node)
400
        {
401
          i->node = NULL;
402
          i = i->next;
403
        }
404
    }
405
  else                                        /* No more nodes */
406
    while (i)
407
      {
408
        i->prev = NULL;
409
        i = i->next;
410
      }
411
}
412

    
413
/**
414
 * fib_delete - delete a FIB node
415
 * @f: FIB to delete from
416
 * @E: entry to delete
417
 *
418
 * This function removes the given entry from the FIB,
419
 * taking care of all the asynchronous readers by shifting
420
 * them to the next node in the canonical reading order.
421
 */
422
void
423
fib_delete(struct fib *f, void *E)
424
{
425
  struct fib_node *e = fib_user_to_node(f, E);
426
  uint h = fib_hash(f, e->addr);
427
  struct fib_node **ee = f->hash_table + h;
428
  struct fib_iterator *it;
429

    
430
  while (*ee)
431
    {
432
      if (*ee == e)
433
        {
434
          *ee = e->next;
435
          if (it = e->readers)
436
            {
437
              struct fib_node *l = e->next;
438
              while (!l)
439
                {
440
                  h++;
441
                  if (h >= f->hash_size)
442
                    break;
443
                  else
444
                    l = f->hash_table[h];
445
                }
446
              fib_merge_readers(it, l);
447
            }
448

    
449
          if (f->fib_slab)
450
            sl_free(f->fib_slab, E);
451
          else
452
            mb_free(E);
453

    
454
          if (f->entries-- < f->entries_min)
455
            fib_rehash(f, -HASH_LO_STEP);
456
          return;
457
        }
458
      ee = &((*ee)->next);
459
    }
460
  bug("fib_delete() called for invalid node");
461
}
462

    
463
/**
464
 * fib_free - delete a FIB
465
 * @f: FIB to be deleted
466
 *
467
 * This function deletes a FIB -- it frees all memory associated
468
 * with it and all its entries.
469
 */
470
void
471
fib_free(struct fib *f)
472
{
473
  fib_ht_free(f->hash_table);
474
  rfree(f->fib_slab);
475
}
476

    
477
void
478
fit_init(struct fib_iterator *i, struct fib *f)
479
{
480
  unsigned h;
481
  struct fib_node *n;
482

    
483
  i->efef = 0xff;
484
  for(h=0; h<f->hash_size; h++)
485
    if (n = f->hash_table[h])
486
      {
487
        i->prev = (struct fib_iterator *) n;
488
        if (i->next = n->readers)
489
          i->next->prev = i;
490
        n->readers = i;
491
        i->node = n;
492
        return;
493
      }
494
  /* The fib is empty, nothing to do */
495
  i->prev = i->next = NULL;
496
  i->node = NULL;
497
}
498

    
499
struct fib_node *
500
fit_get(struct fib *f, struct fib_iterator *i)
501
{
502
  struct fib_node *n;
503
  struct fib_iterator *j, *k;
504

    
505
  if (!i->prev)
506
    {
507
      /* We are at the end */
508
      i->hash = ~0 - 1;
509
      return NULL;
510
    }
511
  if (!(n = i->node))
512
    {
513
      /* No node info available, we are a victim of merging. Try harder. */
514
      j = i;
515
      while (j->efef == 0xff)
516
        j = j->prev;
517
      n = (struct fib_node *) j;
518
    }
519
  j = i->prev;
520
  if (k = i->next)
521
    k->prev = j;
522
  j->next = k;
523
  i->hash = fib_hash(f, n->addr);
524
  return n;
525
}
526

    
527
void
528
fit_put(struct fib_iterator *i, struct fib_node *n)
529
{
530
  struct fib_iterator *j;
531

    
532
  i->node = n;
533
  if (j = n->readers)
534
    j->prev = i;
535
  i->next = j;
536
  n->readers = i;
537
  i->prev = (struct fib_iterator *) n;
538
}
539

    
540
void
541
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos)
542
{
543
  if (n = n->next)
544
    goto found;
545

    
546
  while (++hpos < f->hash_size)
547
    if (n = f->hash_table[hpos])
548
      goto found;
549

    
550
  /* We are at the end */
551
  i->prev = i->next = NULL;
552
  i->node = NULL;
553
  return;
554

    
555
found:
556
  fit_put(i, n);
557
}
558

    
559
#ifdef DEBUGGING
560

    
561
/**
562
 * fib_check - audit a FIB
563
 * @f: FIB to be checked
564
 *
565
 * This debugging function audits a FIB by checking its internal consistency.
566
 * Use when you suspect somebody of corrupting innocent data structures.
567
 */
568
void
569
fib_check(struct fib *f)
570
{
571
  uint i, ec, nulls;
572

    
573
  ec = 0;
574
  for(i=0; i<f->hash_size; i++)
575
    {
576
      struct fib_node *n;
577
      for(n=f->hash_table[i]; n; n=n->next)
578
        {
579
          struct fib_iterator *j, *j0;
580
          uint h0 = fib_hash(f, n->addr);
581
          if (h0 != i)
582
            bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
583
          j0 = (struct fib_iterator *) n;
584
          nulls = 0;
585
          for(j=n->readers; j; j=j->next)
586
            {
587
              if (j->prev != j0)
588
                bug("fib_check: iterator->prev mismatch");
589
              j0 = j;
590
              if (!j->node)
591
                nulls++;
592
              else if (nulls)
593
                bug("fib_check: iterator nullified");
594
              else if (j->node != n)
595
                bug("fib_check: iterator->node mismatch");
596
            }
597
          ec++;
598
        }
599
    }
600
  if (ec != f->entries)
601
    bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
602
  return;
603
}
604

    
605
/*
606
int
607
fib_histogram(struct fib *f)
608
{
609
  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
610

611
  int i, j;
612
  struct fib_node *e;
613

614
  for (i = 0; i < f->hash_size; i++)
615
    {
616
      j = 0;
617
      for (e = f->hash_table[i]; e != NULL; e = e->next)
618
        j++;
619
      if (j > 0)
620
        log(L_WARN "Histogram line %d: %d", i, j);
621
    }
622

623
  log(L_WARN "Histogram dump end");
624
}
625
*/
626

    
627
#endif
628

    
629
#ifdef TEST
630

    
631
#include "lib/resource.h"
632

    
633
struct fib f;
634

    
635
void dump(char *m)
636
{
637
  uint i;
638

    
639
  debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
640
  for(i=0; i<f.hash_size; i++)
641
    {
642
      struct fib_node *n;
643
      struct fib_iterator *j;
644
      for(n=f.hash_table[i]; n; n=n->next)
645
        {
646
          debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr);
647
          for(j=n->readers; j; j=j->next)
648
            debug(" %p[%p]", j, j->node);
649
          debug("\n");
650
        }
651
    }
652
  fib_check(&f);
653
  debug("-----\n");
654
}
655

    
656
void init(struct fib_node *n)
657
{
658
}
659

    
660
int main(void)
661
{
662
  struct fib_node *n;
663
  struct fib_iterator i, j;
664
  ip_addr a;
665
  int c;
666

    
667
  log_init_debug(NULL);
668
  resource_init();
669
  fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
670
  dump("init");
671

    
672
  a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
673
  a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
674
  a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
675
  a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
676
  a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
677
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
678
  dump("fill");
679

    
680
  fit_init(&i, &f);
681
  dump("iter init");
682

    
683
  fib_rehash(&f, 1);
684
  dump("rehash up");
685

    
686
  fib_rehash(&f, -1);
687
  dump("rehash down");
688

    
689
next:
690
  c = 0;
691
  FIB_ITERATE_START(&f, &i, z)
692
    {
693
      if (c)
694
        {
695
          FIB_ITERATE_PUT(&i, z);
696
          dump("iter");
697
          goto next;
698
        }
699
      c = 1;
700
      debug("got %p\n", z);
701
    }
702
  FIB_ITERATE_END(z);
703
  dump("iter end");
704

    
705
  fit_init(&i, &f);
706
  fit_init(&j, &f);
707
  dump("iter init 2");
708

    
709
  n = fit_get(&f, &i);
710
  dump("iter step 2");
711

    
712
  fit_put(&i, n->next);
713
  dump("iter step 3");
714

    
715
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
716
  fib_delete(&f, n);
717
  dump("iter step 3");
718

    
719
  return 0;
720
}
721

    
722
#endif