Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-fib.c @ 600998fc

History | View | Annotate | Download (14.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

    
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("Re-hashing 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