Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-fib.c @ fe9f1a6d

History | View | Annotate | Download (14.4 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 inline void * fib_node_to_user(struct fib *f, struct fib_node *e)
53
{ return (void *) ((char *) e - f->node_offset); }
54

    
55
static inline struct fib_node * fib_user_to_node(struct fib *f, void *e)
56
{ return (void *) ((char *) e + f->node_offset); }
57

    
58
static void
59
fib_ht_alloc(struct fib *f)
60
{
61
  f->hash_size = 1 << f->hash_order;
62
  f->hash_shift = 16 - f->hash_order;
63
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
64
    f->entries_max = ~0;
65
  else
66
    f->entries_max = f->hash_size HASH_HI_MARK;
67
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
68
    f->entries_min = 0;
69
  else
70
    f->entries_min = f->hash_size HASH_LO_MARK;
71
  DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
72
      f->hash_order, f->hash_size, f->entries_min, f->entries_max);
73
  f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
74
}
75

    
76
static inline void
77
fib_ht_free(struct fib_node **h)
78
{
79
  mb_free(h);
80
}
81

    
82

    
83
static u32
84
fib_hash(struct fib *f, net_addr *a);
85

    
86
/**
87
 * fib_init - initialize a new FIB
88
 * @f: the FIB to be initialized (the structure itself being allocated by the caller)
89
 * @p: pool to allocate the nodes in
90
 * @node_size: node size to be used (each node consists of a standard header &fib_node
91
 * followed by user data)
92
 * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
93
 * (recommended)
94
 * @init: pointer a function to be called to initialize a newly created node
95
 *
96
 * This function initializes a newly allocated FIB and prepares it for use.
97
 */
98
void
99
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)
100
{
101
  uint addr_length = net_addr_length[addr_type];
102

    
103
  if (!hash_order)
104
    hash_order = HASH_DEF_ORDER;
105
  f->fib_pool = p;
106
  f->fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL;
107
  f->addr_type = addr_type;
108
  f->node_size = node_size;
109
  f->node_offset = node_offset;
110
  f->hash_order = hash_order;
111
  fib_ht_alloc(f);
112
  bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
113
  f->entries = 0;
114
  f->entries_min = 0;
115
  f->init = init;
116
}
117

    
118
static void
119
fib_rehash(struct fib *f, int step)
120
{
121
  unsigned old, new, oldn, newn, ni, nh;
122
  struct fib_node **n, *e, *x, **t, **m, **h;
123

    
124
  old = f->hash_order;
125
  oldn = f->hash_size;
126
  new = old + step;
127
  m = h = f->hash_table;
128
  DBG("Re-hashing FIB from order %d to %d\n", old, new);
129
  f->hash_order = new;
130
  fib_ht_alloc(f);
131
  t = n = f->hash_table;
132
  newn = f->hash_size;
133
  ni = 0;
134

    
135
  while (oldn--)
136
    {
137
      x = *h++;
138
      while (e = x)
139
        {
140
          x = e->next;
141
          nh = fib_hash(f, e->addr);
142
          while (nh > ni)
143
            {
144
              *t = NULL;
145
              ni++;
146
              t = ++n;
147
            }
148
          *t = e;
149
          t = &e->next;
150
        }
151
    }
152
  while (ni < newn)
153
    {
154
      *t = NULL;
155
      ni++;
156
      t = ++n;
157
    }
158
  fib_ht_free(m);
159
}
160

    
161
#define CAST(t) (net_addr_##t *)
162

    
163
#define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift)
164

    
165
#define FIB_FIND(f,a,t)                                                        \
166
  ({                                                                        \
167
    struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)];                \
168
    while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a))                \
169
      e = e->next;                                                        \
170
    fib_node_to_user(f, e);                                                \
171
  })
172

    
173
#define FIB_INSERT(f,a,e,t)                                                \
174
  ({                                                                        \
175
  u32 h = net_hash_##t(CAST(t) a);                                        \
176
  struct fib_node **ee = f->hash_table + (h >> f->hash_shift);                \
177
  struct fib_node *g;                                                        \
178
                                                                        \
179
  while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h))                \
180
    ee = &g->next;                                                        \
181
                                                                        \
182
  net_copy_##t(CAST(t) e->addr, CAST(t) a);                                \
183
  e->next = *ee;                                                        \
184
  *ee = e;                                                                \
185
  })
186

    
187

    
188
static u32
189
fib_hash(struct fib *f, net_addr *a)
190
{
191
  switch (f->addr_type)
192
  {
193
  case NET_IP4: return FIB_HASH(f, a, ip4);
194
  case NET_IP6: return FIB_HASH(f, a, ip6);
195
  case NET_VPN4: return FIB_HASH(f, a, vpn4);
196
  case NET_VPN6: return FIB_HASH(f, a, vpn6);
197
  default: bug("invalid type");
198
  }
199
}
200

    
201
void *
202
fib_find(struct fib *f, net_addr *a)
203
{
204
  ASSERT(f->addr_type == a->type);
205

    
206
  switch (f->addr_type)
207
  {
208
  case NET_IP4: return FIB_FIND(f, a, ip4);
209
  case NET_IP6: return FIB_FIND(f, a, ip6);
210
  case NET_VPN4: return FIB_FIND(f, a, vpn4);
211
  case NET_VPN6: return FIB_FIND(f, a, vpn6);
212
  default: bug("invalid type");
213
  }
214
}
215

    
216
static void
217
fib_insert(struct fib *f, net_addr *a, struct fib_node *e)
218
{
219
  switch (f->addr_type)
220
  {
221
  case NET_IP4: FIB_INSERT(f, a, e, ip4); return;
222
  case NET_IP6: FIB_INSERT(f, a, e, ip6); return;
223
  case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return;
224
  case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return;
225
  default: bug("invalid type");
226
  }
227
}
228

    
229

    
230

    
231
/**
232
 * fib_find - search for FIB node by prefix
233
 * @f: FIB to search in
234
 * @a: pointer to IP address of the prefix
235
 * @len: prefix length
236
 *
237
 * Search for a FIB node corresponding to the given prefix, return
238
 * a pointer to it or %NULL if no such node exists.
239
 */
240
/*
241
void *
242
fib_find(struct fib *f, net_addr *a)
243
{
244
  struct fib_node *e = f->hash_table[fib_hash(f, a)];
245

246
  while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
247
    e = e->next;
248
  return e;
249
}
250
*/
251

    
252
/**
253
 * fib_get - find or create a FIB node
254
 * @f: FIB to work with
255
 * @a: pointer to IP address of the prefix
256
 * @len: prefix length
257
 *
258
 * Search for a FIB node corresponding to the given prefix and
259
 * return a pointer to it. If no such node exists, create it.
260
 */
261
void *
262
fib_get(struct fib *f, net_addr *a)
263
{
264
  char *b = fib_find(f, a);
265
  if (b)
266
    return b;
267

    
268
  if (f->fib_slab)
269
    b = sl_alloc(f->fib_slab);
270
  else
271
    b = mb_alloc(f->fib_pool, f->node_size + a->length);
272

    
273
  struct fib_node *e = (void *) (b + f->node_offset);
274
  e->readers = NULL;
275
  e->flags = 0;
276
  e->uid = 0;
277
  fib_insert(f, a, e);
278

    
279
  memset(b, 0, f->node_offset);
280
  if (f->init)
281
    f->init(b);
282

    
283
  if (f->entries++ > f->entries_max)
284
    fib_rehash(f, HASH_HI_STEP);
285

    
286
  return b;
287
}
288

    
289
/**
290
 * fib_route - CIDR routing lookup
291
 * @f: FIB to search in
292
 * @a: pointer to IP address of the prefix
293
 * @len: prefix length
294
 *
295
 * Search for a FIB node with longest prefix matching the given
296
 * network, that is a node which a CIDR router would use for routing
297
 * that network.
298
 */
299
/*
300
void *
301
fib_route(struct fib *f, ip_addr a, int len)
302
{
303
  ip_addr a0;
304
  void *t;
305

306
  while (len >= 0)
307
    {
308
      a0 = ipa_and(a, ipa_mkmask(len));
309
      t = fib_find(f, &a0, len);
310
      if (t)
311
        return t;
312
      len--;
313
    }
314
  return NULL;
315
}
316
*/
317

    
318
static inline void
319
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
320
{
321
  if (to)
322
    {
323
      struct fib_iterator *j = to->readers;
324
      if (!j)
325
        {
326
          /* Fast path */
327
          to->readers = i;
328
          i->prev = (struct fib_iterator *) to;
329
        }
330
      else
331
        {
332
          /* Really merging */
333
          while (j->next)
334
            j = j->next;
335
          j->next = i;
336
          i->prev = j;
337
        }
338
      while (i && i->node)
339
        {
340
          i->node = NULL;
341
          i = i->next;
342
        }
343
    }
344
  else                                        /* No more nodes */
345
    while (i)
346
      {
347
        i->prev = NULL;
348
        i = i->next;
349
      }
350
}
351

    
352
/**
353
 * fib_delete - delete a FIB node
354
 * @f: FIB to delete from
355
 * @E: entry to delete
356
 *
357
 * This function removes the given entry from the FIB,
358
 * taking care of all the asynchronous readers by shifting
359
 * them to the next node in the canonical reading order.
360
 */
361
void
362
fib_delete(struct fib *f, void *E)
363
{
364
  struct fib_node *e = fib_user_to_node(f, E);
365
  uint h = fib_hash(f, e->addr);
366
  struct fib_node **ee = f->hash_table + h;
367
  struct fib_iterator *it;
368

    
369
  while (*ee)
370
    {
371
      if (*ee == e)
372
        {
373
          *ee = e->next;
374
          if (it = e->readers)
375
            {
376
              struct fib_node *l = e->next;
377
              while (!l)
378
                {
379
                  h++;
380
                  if (h >= f->hash_size)
381
                    break;
382
                  else
383
                    l = f->hash_table[h];
384
                }
385
              fib_merge_readers(it, l);
386
            }
387
          sl_free(f->fib_slab, e);
388
          if (f->entries-- < f->entries_min)
389
            fib_rehash(f, -HASH_LO_STEP);
390
          return;
391
        }
392
      ee = &((*ee)->next);
393
    }
394
  bug("fib_delete() called for invalid node");
395
}
396

    
397
/**
398
 * fib_free - delete a FIB
399
 * @f: FIB to be deleted
400
 *
401
 * This function deletes a FIB -- it frees all memory associated
402
 * with it and all its entries.
403
 */
404
void
405
fib_free(struct fib *f)
406
{
407
  fib_ht_free(f->hash_table);
408
  rfree(f->fib_slab);
409
}
410

    
411
void
412
fit_init(struct fib_iterator *i, struct fib *f)
413
{
414
  unsigned h;
415
  struct fib_node *n;
416

    
417
  i->efef = 0xff;
418
  for(h=0; h<f->hash_size; h++)
419
    if (n = f->hash_table[h])
420
      {
421
        i->prev = (struct fib_iterator *) n;
422
        if (i->next = n->readers)
423
          i->next->prev = i;
424
        n->readers = i;
425
        i->node = n;
426
        return;
427
      }
428
  /* The fib is empty, nothing to do */
429
  i->prev = i->next = NULL;
430
  i->node = NULL;
431
}
432

    
433
struct fib_node *
434
fit_get(struct fib *f, struct fib_iterator *i)
435
{
436
  struct fib_node *n;
437
  struct fib_iterator *j, *k;
438

    
439
  if (!i->prev)
440
    {
441
      /* We are at the end */
442
      i->hash = ~0 - 1;
443
      return NULL;
444
    }
445
  if (!(n = i->node))
446
    {
447
      /* No node info available, we are a victim of merging. Try harder. */
448
      j = i;
449
      while (j->efef == 0xff)
450
        j = j->prev;
451
      n = (struct fib_node *) j;
452
    }
453
  j = i->prev;
454
  if (k = i->next)
455
    k->prev = j;
456
  j->next = k;
457
  i->hash = fib_hash(f, n->addr);
458
  return n;
459
}
460

    
461
void
462
fit_put(struct fib_iterator *i, struct fib_node *n)
463
{
464
  struct fib_iterator *j;
465

    
466
  i->node = n;
467
  if (j = n->readers)
468
    j->prev = i;
469
  i->next = j;
470
  n->readers = i;
471
  i->prev = (struct fib_iterator *) n;
472
}
473

    
474
void
475
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos)
476
{
477
  if (n = n->next)
478
    goto found;
479

    
480
  while (++hpos < f->hash_size)
481
    if (n = f->hash_table[hpos])
482
      goto found;
483

    
484
  /* We are at the end */
485
  i->prev = i->next = NULL;
486
  i->node = NULL;
487
  return;
488

    
489
found:
490
  fit_put(i, n);
491
}
492

    
493
#ifdef DEBUGGING
494

    
495
/**
496
 * fib_check - audit a FIB
497
 * @f: FIB to be checked
498
 *
499
 * This debugging function audits a FIB by checking its internal consistency.
500
 * Use when you suspect somebody of corrupting innocent data structures.
501
 */
502
void
503
fib_check(struct fib *f)
504
{
505
  uint i, ec, lo, nulls;
506

    
507
  ec = 0;
508
  for(i=0; i<f->hash_size; i++)
509
    {
510
      struct fib_node *n;
511
      lo = 0;
512
      for(n=f->hash_table[i]; n; n=n->next)
513
        {
514
          struct fib_iterator *j, *j0;
515
          uint h0 = ipa_hash(n->prefix);
516
          if (h0 < lo)
517
            bug("fib_check: discord in hash chains");
518
          lo = h0;
519
          if ((h0 >> f->hash_shift) != i)
520
            bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
521
          j0 = (struct fib_iterator *) n;
522
          nulls = 0;
523
          for(j=n->readers; j; j=j->next)
524
            {
525
              if (j->prev != j0)
526
                bug("fib_check: iterator->prev mismatch");
527
              j0 = j;
528
              if (!j->node)
529
                nulls++;
530
              else if (nulls)
531
                bug("fib_check: iterator nullified");
532
              else if (j->node != n)
533
                bug("fib_check: iterator->node mismatch");
534
            }
535
          ec++;
536
        }
537
    }
538
  if (ec != f->entries)
539
    bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
540
}
541

    
542
/*
543
int
544
fib_histogram(struct fib *f)
545
{
546
  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
547

548
  int i, j;
549
  struct fib_node *e;
550

551
  for (i = 0; i < f->hash_size; i++)
552
    {
553
      j = 0;
554
      for (e = f->hash_table[i]; e != NULL; e = e->next)
555
        j++;
556
      if (j > 0)
557
        log(L_WARN "Histogram line %d: %d", i, j);
558
    }
559

560
  log(L_WARN "Histogram dump end");
561
}
562
*/
563

    
564
#endif
565

    
566
#ifdef TEST
567

    
568
#include "lib/resource.h"
569

    
570
struct fib f;
571

    
572
void dump(char *m)
573
{
574
  uint i;
575

    
576
  debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
577
  for(i=0; i<f.hash_size; i++)
578
    {
579
      struct fib_node *n;
580
      struct fib_iterator *j;
581
      for(n=f.hash_table[i]; n; n=n->next)
582
        {
583
          debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr);
584
          for(j=n->readers; j; j=j->next)
585
            debug(" %p[%p]", j, j->node);
586
          debug("\n");
587
        }
588
    }
589
  fib_check(&f);
590
  debug("-----\n");
591
}
592

    
593
void init(struct fib_node *n)
594
{
595
}
596

    
597
int main(void)
598
{
599
  struct fib_node *n;
600
  struct fib_iterator i, j;
601
  ip_addr a;
602
  int c;
603

    
604
  log_init_debug(NULL);
605
  resource_init();
606
  fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
607
  dump("init");
608

    
609
  a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
610
  a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
611
  a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
612
  a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
613
  a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
614
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
615
  dump("fill");
616

    
617
  fit_init(&i, &f);
618
  dump("iter init");
619

    
620
  fib_rehash(&f, 1);
621
  dump("rehash up");
622

    
623
  fib_rehash(&f, -1);
624
  dump("rehash down");
625

    
626
next:
627
  c = 0;
628
  FIB_ITERATE_START(&f, &i, z)
629
    {
630
      if (c)
631
        {
632
          FIB_ITERATE_PUT(&i, z);
633
          dump("iter");
634
          goto next;
635
        }
636
      c = 1;
637
      debug("got %p\n", z);
638
    }
639
  FIB_ITERATE_END(z);
640
  dump("iter end");
641

    
642
  fit_init(&i, &f);
643
  fit_init(&j, &f);
644
  dump("iter init 2");
645

    
646
  n = fit_get(&f, &i);
647
  dump("iter step 2");
648

    
649
  fit_put(&i, n->next);
650
  dump("iter step 3");
651

    
652
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
653
  fib_delete(&f, n);
654
  dump("iter step 3");
655

    
656
  return 0;
657
}
658

    
659
#endif