Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-fib.c @ 62e64905

History | View | Annotate | Download (15.4 KB)

1 62aa008a Martin Mares
/*
2
 *        BIRD -- Forwarding Information Base -- Data Structures
3
 *
4 6998bb9e Martin Mares
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5 62aa008a Martin Mares
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8
9 ce4aca09 Martin Mares
/**
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 58f7d004 Martin Mares
 * The lists of nodes in each bucket are sorted according to the primary hash
25 ce4aca09 Martin Mares
 * 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 6b9fa320 Martin Mares
#undef LOCAL_DEBUG
38 62aa008a Martin Mares
39
#include "nest/bird.h"
40
#include "nest/route.h"
41 221135d6 Martin Mares
#include "lib/string.h"
42 62aa008a Martin Mares
43 3ab001b9 Martin Mares
#define HASH_DEF_ORDER 10
44
#define HASH_HI_MARK *4
45
#define HASH_HI_STEP 2
46 04632fd7 Ondrej Zajicek (work)
#define HASH_HI_MAX 16
47 3ab001b9 Martin Mares
#define HASH_LO_MARK /5
48
#define HASH_LO_STEP 2
49
#define HASH_LO_MIN 10
50 62aa008a Martin Mares
51 fe9f1a6d Ondrej Zajicek (work)
52 62aa008a Martin Mares
static void
53
fib_ht_alloc(struct fib *f)
54
{
55 3ab001b9 Martin Mares
  f->hash_size = 1 << f->hash_order;
56 23c212e7 Ondrej Zajicek (work)
  f->hash_shift = 32 - f->hash_order;
57 3ab001b9 Martin Mares
  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 62aa008a Martin Mares
    f->entries_min = 0;
63 3ab001b9 Martin Mares
  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 62aa008a Martin Mares
  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 fe9f1a6d Ondrej Zajicek (work)
static u32
78 0f7d5b1a Ondrej Zajicek (work)
fib_hash(struct fib *f, const net_addr *a);
79 ce45fc12 Pavel Machek
80 ce4aca09 Martin Mares
/**
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 62aa008a Martin Mares
void
93 fe9f1a6d Ondrej Zajicek (work)
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)
94 62aa008a Martin Mares
{
95 fe9f1a6d Ondrej Zajicek (work)
  uint addr_length = net_addr_length[addr_type];
96
97 3ab001b9 Martin Mares
  if (!hash_order)
98
    hash_order = HASH_DEF_ORDER;
99 62aa008a Martin Mares
  f->fib_pool = p;
100 fe9f1a6d Ondrej Zajicek (work)
  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 3ab001b9 Martin Mares
  f->hash_order = hash_order;
105 62aa008a Martin Mares
  fib_ht_alloc(f);
106 3ab001b9 Martin Mares
  bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
107 62aa008a Martin Mares
  f->entries = 0;
108
  f->entries_min = 0;
109 fe9f1a6d Ondrej Zajicek (work)
  f->init = init;
110 62aa008a Martin Mares
}
111
112
static void
113 3ab001b9 Martin Mares
fib_rehash(struct fib *f, int step)
114 62aa008a Martin Mares
{
115 3ab001b9 Martin Mares
  unsigned old, new, oldn, newn, ni, nh;
116 62aa008a Martin Mares
  struct fib_node **n, *e, *x, **t, **m, **h;
117
118 3ab001b9 Martin Mares
  old = f->hash_order;
119
  oldn = f->hash_size;
120
  new = old + step;
121 62aa008a Martin Mares
  m = h = f->hash_table;
122 3ab001b9 Martin Mares
  DBG("Re-hashing FIB from order %d to %d\n", old, new);
123
  f->hash_order = new;
124 62aa008a Martin Mares
  fib_ht_alloc(f);
125 3ab001b9 Martin Mares
  t = n = f->hash_table;
126
  newn = f->hash_size;
127
  ni = 0;
128
129 6998bb9e Martin Mares
  while (oldn--)
130 62aa008a Martin Mares
    {
131
      x = *h++;
132
      while (e = x)
133
        {
134
          x = e->next;
135 fe9f1a6d Ondrej Zajicek (work)
          nh = fib_hash(f, e->addr);
136 3ab001b9 Martin Mares
          while (nh > ni)
137
            {
138
              *t = NULL;
139
              ni++;
140
              t = ++n;
141
            }
142 62aa008a Martin Mares
          *t = e;
143 3ab001b9 Martin Mares
          t = &e->next;
144 62aa008a Martin Mares
        }
145
    }
146 3ab001b9 Martin Mares
  while (ni < newn)
147
    {
148
      *t = NULL;
149
      ni++;
150
      t = ++n;
151
    }
152 62aa008a Martin Mares
  fib_ht_free(m);
153
}
154
155 0f7d5b1a Ondrej Zajicek (work)
#define CAST(t) (const net_addr_##t *)
156
#define CAST2(t) (net_addr_##t *)
157 fe9f1a6d Ondrej Zajicek (work)
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 600998fc Ondrej Zajicek (work)
    fib_node_to_user(f, e);                                                \
166 fe9f1a6d Ondrej Zajicek (work)
  })
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 0f7d5b1a Ondrej Zajicek (work)
  net_copy_##t(CAST2(t) e->addr, CAST(t) a);                                \
178 fe9f1a6d Ondrej Zajicek (work)
  e->next = *ee;                                                        \
179
  *ee = e;                                                                \
180
  })
181
182
183
static u32
184 0f7d5b1a Ondrej Zajicek (work)
fib_hash(struct fib *f, const net_addr *a)
185 fe9f1a6d Ondrej Zajicek (work)
{
186 3f358161 Jan Moskyto Matejka
  ASSERT(f->addr_type == a->type);
187
188 fe9f1a6d Ondrej Zajicek (work)
  switch (f->addr_type)
189
  {
190
  case NET_IP4: return FIB_HASH(f, a, ip4);
191
  case NET_IP6: return FIB_HASH(f, a, ip6);
192
  case NET_VPN4: return FIB_HASH(f, a, vpn4);
193
  case NET_VPN6: return FIB_HASH(f, a, vpn6);
194 de9b87f5 Pavel Tvrdík
  case NET_ROA4: return FIB_HASH(f, a, roa4);
195
  case NET_ROA6: return FIB_HASH(f, a, roa6);
196 77234bbb Ondrej Zajicek (work)
  case NET_FLOW4: return FIB_HASH(f, a, flow4);
197
  case NET_FLOW6: return FIB_HASH(f, a, flow6);
198 fe9f1a6d Ondrej Zajicek (work)
  default: bug("invalid type");
199
  }
200
}
201
202 0264ccf6 Pavel Tvrdík
void *
203
fib_get_chain(struct fib *f, const net_addr *a)
204
{
205
  ASSERT(f->addr_type == a->type);
206
207
  struct fib_node *e = f->hash_table[fib_hash(f, a)];
208
  return e;
209
}
210
211 0f7d5b1a Ondrej Zajicek (work)
/**
212
 * fib_find - search for FIB node by prefix
213
 * @f: FIB to search in
214
 * @n: network address
215
 *
216
 * Search for a FIB node corresponding to the given prefix, return
217
 * a pointer to it or %NULL if no such node exists.
218
 */
219 fe9f1a6d Ondrej Zajicek (work)
void *
220 0f7d5b1a Ondrej Zajicek (work)
fib_find(struct fib *f, const net_addr *a)
221 fe9f1a6d Ondrej Zajicek (work)
{
222
  ASSERT(f->addr_type == a->type);
223
224
  switch (f->addr_type)
225
  {
226
  case NET_IP4: return FIB_FIND(f, a, ip4);
227
  case NET_IP6: return FIB_FIND(f, a, ip6);
228
  case NET_VPN4: return FIB_FIND(f, a, vpn4);
229
  case NET_VPN6: return FIB_FIND(f, a, vpn6);
230 de9b87f5 Pavel Tvrdík
  case NET_ROA4: return FIB_FIND(f, a, roa4);
231
  case NET_ROA6: return FIB_FIND(f, a, roa6);
232 77234bbb Ondrej Zajicek (work)
  case NET_FLOW4: return FIB_FIND(f, a, flow4);
233
  case NET_FLOW6: return FIB_FIND(f, a, flow6);
234 fe9f1a6d Ondrej Zajicek (work)
  default: bug("invalid type");
235
  }
236
}
237
238
static void
239 0f7d5b1a Ondrej Zajicek (work)
fib_insert(struct fib *f, const net_addr *a, struct fib_node *e)
240 fe9f1a6d Ondrej Zajicek (work)
{
241 3f358161 Jan Moskyto Matejka
  ASSERT(f->addr_type == a->type);
242
243 fe9f1a6d Ondrej Zajicek (work)
  switch (f->addr_type)
244
  {
245
  case NET_IP4: FIB_INSERT(f, a, e, ip4); return;
246
  case NET_IP6: FIB_INSERT(f, a, e, ip6); return;
247
  case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return;
248
  case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return;
249 de9b87f5 Pavel Tvrdík
  case NET_ROA4: FIB_INSERT(f, a, e, roa4); return;
250
  case NET_ROA6: FIB_INSERT(f, a, e, roa6); return;
251 77234bbb Ondrej Zajicek (work)
  case NET_FLOW4: FIB_INSERT(f, a, e, flow4); return;
252
  case NET_FLOW6: FIB_INSERT(f, a, e, flow6); return;
253 fe9f1a6d Ondrej Zajicek (work)
  default: bug("invalid type");
254
  }
255
}
256
257
258 ce4aca09 Martin Mares
/**
259
 * fib_get - find or create a FIB node
260
 * @f: FIB to work with
261 0f7d5b1a Ondrej Zajicek (work)
 * @n: network address
262 ce4aca09 Martin Mares
 *
263
 * Search for a FIB node corresponding to the given prefix and
264
 * return a pointer to it. If no such node exists, create it.
265
 */
266 62aa008a Martin Mares
void *
267 0f7d5b1a Ondrej Zajicek (work)
fib_get(struct fib *f, const net_addr *a)
268 62aa008a Martin Mares
{
269 23c212e7 Ondrej Zajicek (work)
  void *b = fib_find(f, a);
270 fe9f1a6d Ondrej Zajicek (work)
  if (b)
271
    return b;
272 d82fc18d Ondrej Zajicek
273 fe9f1a6d Ondrej Zajicek (work)
  if (f->fib_slab)
274
    b = sl_alloc(f->fib_slab);
275
  else
276
    b = mb_alloc(f->fib_pool, f->node_size + a->length);
277 d82fc18d Ondrej Zajicek
278 23c212e7 Ondrej Zajicek (work)
  struct fib_node *e = fib_user_to_node(f, b);
279 fe9f1a6d Ondrej Zajicek (work)
  e->readers = NULL;
280
  e->flags = 0;
281
  fib_insert(f, a, e);
282 d82fc18d Ondrej Zajicek
283 fe9f1a6d Ondrej Zajicek (work)
  memset(b, 0, f->node_offset);
284
  if (f->init)
285
    f->init(b);
286 d82fc18d Ondrej Zajicek
287 62aa008a Martin Mares
  if (f->entries++ > f->entries_max)
288 3ab001b9 Martin Mares
    fib_rehash(f, HASH_HI_STEP);
289 d82fc18d Ondrej Zajicek
290 fe9f1a6d Ondrej Zajicek (work)
  return b;
291 62aa008a Martin Mares
}
292
293 04632fd7 Ondrej Zajicek (work)
static inline void *
294
fib_route_ip4(struct fib *f, net_addr_ip4 *n)
295 0f7d5b1a Ondrej Zajicek (work)
{
296 04632fd7 Ondrej Zajicek (work)
  void *r;
297 0f7d5b1a Ondrej Zajicek (work)
298 04632fd7 Ondrej Zajicek (work)
  while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0))
299 0f7d5b1a Ondrej Zajicek (work)
  {
300
    n->pxlen--;
301
    ip4_clrbit(&n->prefix, n->pxlen);
302
  }
303
304 04632fd7 Ondrej Zajicek (work)
  return r;
305 0f7d5b1a Ondrej Zajicek (work)
}
306
307 04632fd7 Ondrej Zajicek (work)
static inline void *
308
fib_route_ip6(struct fib *f, net_addr_ip6 *n)
309 0f7d5b1a Ondrej Zajicek (work)
{
310 04632fd7 Ondrej Zajicek (work)
  void *r;
311 0f7d5b1a Ondrej Zajicek (work)
312 04632fd7 Ondrej Zajicek (work)
  while (!(r = fib_find(f, (net_addr *) n)) && (n->pxlen > 0))
313 0f7d5b1a Ondrej Zajicek (work)
  {
314
    n->pxlen--;
315
    ip6_clrbit(&n->prefix, n->pxlen);
316
  }
317
318 04632fd7 Ondrej Zajicek (work)
  return r;
319 0f7d5b1a Ondrej Zajicek (work)
}
320
321 ce4aca09 Martin Mares
/**
322
 * fib_route - CIDR routing lookup
323
 * @f: FIB to search in
324 0f7d5b1a Ondrej Zajicek (work)
 * @n: network address
325 ce4aca09 Martin Mares
 *
326
 * Search for a FIB node with longest prefix matching the given
327
 * network, that is a node which a CIDR router would use for routing
328
 * that network.
329
 */
330 56d6c530 Martin Mares
void *
331 0f7d5b1a Ondrej Zajicek (work)
fib_route(struct fib *f, const net_addr *n)
332 56d6c530 Martin Mares
{
333 0f7d5b1a Ondrej Zajicek (work)
  ASSERT(f->addr_type == n->type);
334 56d6c530 Martin Mares
335 04632fd7 Ondrej Zajicek (work)
  net_addr *n0 = alloca(n->length);
336
  net_copy(n0, n);
337
338 0f7d5b1a Ondrej Zajicek (work)
  switch (n->type)
339
  {
340
  case NET_IP4:
341
  case NET_VPN4:
342 de9b87f5 Pavel Tvrdík
  case NET_ROA4:
343 77234bbb Ondrej Zajicek (work)
  case NET_FLOW4:
344 04632fd7 Ondrej Zajicek (work)
    return fib_route_ip4(f, (net_addr_ip4 *) n0);
345 0f7d5b1a Ondrej Zajicek (work)
346
  case NET_IP6:
347
  case NET_VPN6:
348 de9b87f5 Pavel Tvrdík
  case NET_ROA6:
349 77234bbb Ondrej Zajicek (work)
  case NET_FLOW6:
350 04632fd7 Ondrej Zajicek (work)
    return fib_route_ip6(f, (net_addr_ip6 *) n0);
351 0f7d5b1a Ondrej Zajicek (work)
352
  default:
353
    return NULL;
354
  }
355 56d6c530 Martin Mares
}
356
357 04632fd7 Ondrej Zajicek (work)
358 3ab001b9 Martin Mares
static inline void
359
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
360
{
361
  if (to)
362
    {
363
      struct fib_iterator *j = to->readers;
364
      if (!j)
365
        {
366
          /* Fast path */
367
          to->readers = i;
368
          i->prev = (struct fib_iterator *) to;
369
        }
370 8abbde02 Martin Mares
      else
371
        {
372
          /* Really merging */
373
          while (j->next)
374
            j = j->next;
375
          j->next = i;
376
          i->prev = j;
377
        }
378
      while (i && i->node)
379
        {
380
          i->node = NULL;
381
          i = i->next;
382
        }
383 3ab001b9 Martin Mares
    }
384
  else                                        /* No more nodes */
385
    while (i)
386
      {
387
        i->prev = NULL;
388
        i = i->next;
389
      }
390
}
391
392 ce4aca09 Martin Mares
/**
393
 * fib_delete - delete a FIB node
394
 * @f: FIB to delete from
395
 * @E: entry to delete
396
 *
397
 * This function removes the given entry from the FIB,
398
 * taking care of all the asynchronous readers by shifting
399
 * them to the next node in the canonical reading order.
400
 */
401 62aa008a Martin Mares
void
402
fib_delete(struct fib *f, void *E)
403
{
404 fe9f1a6d Ondrej Zajicek (work)
  struct fib_node *e = fib_user_to_node(f, E);
405
  uint h = fib_hash(f, e->addr);
406 3ab001b9 Martin Mares
  struct fib_node **ee = f->hash_table + h;
407
  struct fib_iterator *it;
408 62aa008a Martin Mares
409
  while (*ee)
410
    {
411
      if (*ee == e)
412
        {
413
          *ee = e->next;
414 3ab001b9 Martin Mares
          if (it = e->readers)
415
            {
416
              struct fib_node *l = e->next;
417
              while (!l)
418
                {
419
                  h++;
420
                  if (h >= f->hash_size)
421
                    break;
422
                  else
423
                    l = f->hash_table[h];
424
                }
425
              fib_merge_readers(it, l);
426
            }
427 04632fd7 Ondrej Zajicek (work)
428
          if (f->fib_slab)
429
            sl_free(f->fib_slab, E);
430
          else
431
            mb_free(E);
432
433 62aa008a Martin Mares
          if (f->entries-- < f->entries_min)
434 3ab001b9 Martin Mares
            fib_rehash(f, -HASH_LO_STEP);
435 62aa008a Martin Mares
          return;
436
        }
437
      ee = &((*ee)->next);
438
    }
439 08c69a77 Martin Mares
  bug("fib_delete() called for invalid node");
440 62aa008a Martin Mares
}
441
442 ce4aca09 Martin Mares
/**
443
 * fib_free - delete a FIB
444
 * @f: FIB to be deleted
445
 *
446
 * This function deletes a FIB -- it frees all memory associated
447
 * with it and all its entries.
448
 */
449 62aa008a Martin Mares
void
450
fib_free(struct fib *f)
451
{
452
  fib_ht_free(f->hash_table);
453
  rfree(f->fib_slab);
454
}
455 3ab001b9 Martin Mares
456
void
457
fit_init(struct fib_iterator *i, struct fib *f)
458
{
459
  unsigned h;
460
  struct fib_node *n;
461
462
  i->efef = 0xff;
463
  for(h=0; h<f->hash_size; h++)
464
    if (n = f->hash_table[h])
465
      {
466
        i->prev = (struct fib_iterator *) n;
467
        if (i->next = n->readers)
468
          i->next->prev = i;
469
        n->readers = i;
470
        i->node = n;
471
        return;
472
      }
473
  /* The fib is empty, nothing to do */
474
  i->prev = i->next = NULL;
475
  i->node = NULL;
476
}
477
478
struct fib_node *
479
fit_get(struct fib *f, struct fib_iterator *i)
480
{
481
  struct fib_node *n;
482
  struct fib_iterator *j, *k;
483
484
  if (!i->prev)
485
    {
486
      /* We are at the end */
487 8abbde02 Martin Mares
      i->hash = ~0 - 1;
488 3ab001b9 Martin Mares
      return NULL;
489
    }
490
  if (!(n = i->node))
491
    {
492
      /* No node info available, we are a victim of merging. Try harder. */
493
      j = i;
494
      while (j->efef == 0xff)
495
        j = j->prev;
496
      n = (struct fib_node *) j;
497
    }
498
  j = i->prev;
499
  if (k = i->next)
500
    k->prev = j;
501
  j->next = k;
502 fe9f1a6d Ondrej Zajicek (work)
  i->hash = fib_hash(f, n->addr);
503 3ab001b9 Martin Mares
  return n;
504
}
505
506
void
507
fit_put(struct fib_iterator *i, struct fib_node *n)
508
{
509
  struct fib_iterator *j;
510
511
  i->node = n;
512
  if (j = n->readers)
513
    j->prev = i;
514
  i->next = j;
515
  n->readers = i;
516
  i->prev = (struct fib_iterator *) n;
517
}
518
519 8465dccb Ondrej Zajicek (work)
void
520
fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos)
521
{
522
  if (n = n->next)
523
    goto found;
524
525
  while (++hpos < f->hash_size)
526
    if (n = f->hash_table[hpos])
527
      goto found;
528
529
  /* We are at the end */
530
  i->prev = i->next = NULL;
531
  i->node = NULL;
532
  return;
533
534
found:
535
  fit_put(i, n);
536
}
537
538 3ab001b9 Martin Mares
#ifdef DEBUGGING
539
540 ce4aca09 Martin Mares
/**
541
 * fib_check - audit a FIB
542
 * @f: FIB to be checked
543
 *
544
 * This debugging function audits a FIB by checking its internal consistency.
545 58f7d004 Martin Mares
 * Use when you suspect somebody of corrupting innocent data structures.
546 ce4aca09 Martin Mares
 */
547 3ab001b9 Martin Mares
void
548
fib_check(struct fib *f)
549
{
550 23c212e7 Ondrej Zajicek (work)
#if 0
551 ae80a2de Pavel Tvrdík
  uint i, ec, lo, nulls;
552 3ab001b9 Martin Mares

553
  ec = 0;
554
  for(i=0; i<f->hash_size; i++)
555
    {
556
      struct fib_node *n;
557
      lo = 0;
558
      for(n=f->hash_table[i]; n; n=n->next)
559
        {
560
          struct fib_iterator *j, *j0;
561 ae80a2de Pavel Tvrdík
          uint h0 = ipa_hash(n->prefix);
562 3ab001b9 Martin Mares
          if (h0 < lo)
563 08c69a77 Martin Mares
            bug("fib_check: discord in hash chains");
564 3ab001b9 Martin Mares
          lo = h0;
565
          if ((h0 >> f->hash_shift) != i)
566 08c69a77 Martin Mares
            bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
567 3ab001b9 Martin Mares
          j0 = (struct fib_iterator *) n;
568
          nulls = 0;
569
          for(j=n->readers; j; j=j->next)
570
            {
571
              if (j->prev != j0)
572 08c69a77 Martin Mares
                bug("fib_check: iterator->prev mismatch");
573 3ab001b9 Martin Mares
              j0 = j;
574
              if (!j->node)
575
                nulls++;
576
              else if (nulls)
577 08c69a77 Martin Mares
                bug("fib_check: iterator nullified");
578 3ab001b9 Martin Mares
              else if (j->node != n)
579 08c69a77 Martin Mares
                bug("fib_check: iterator->node mismatch");
580 3ab001b9 Martin Mares
            }
581
          ec++;
582
        }
583
    }
584
  if (ec != f->entries)
585 08c69a77 Martin Mares
    bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
586 23c212e7 Ondrej Zajicek (work)
#endif
587
  return;
588 3ab001b9 Martin Mares
}
589
590 fe9f1a6d Ondrej Zajicek (work)
/*
591
int
592
fib_histogram(struct fib *f)
593
{
594
  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
595

596
  int i, j;
597
  struct fib_node *e;
598

599
  for (i = 0; i < f->hash_size; i++)
600
    {
601
      j = 0;
602
      for (e = f->hash_table[i]; e != NULL; e = e->next)
603
        j++;
604
      if (j > 0)
605
        log(L_WARN "Histogram line %d: %d", i, j);
606
    }
607

608
  log(L_WARN "Histogram dump end");
609
}
610
*/
611
612 3ab001b9 Martin Mares
#endif
613
614
#ifdef TEST
615
616
#include "lib/resource.h"
617
618
struct fib f;
619
620
void dump(char *m)
621
{
622 ae80a2de Pavel Tvrdík
  uint i;
623 3ab001b9 Martin Mares
624
  debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
625
  for(i=0; i<f.hash_size; i++)
626
    {
627
      struct fib_node *n;
628
      struct fib_iterator *j;
629
      for(n=f.hash_table[i]; n; n=n->next)
630
        {
631 fe9f1a6d Ondrej Zajicek (work)
          debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr);
632 3ab001b9 Martin Mares
          for(j=n->readers; j; j=j->next)
633
            debug(" %p[%p]", j, j->node);
634
          debug("\n");
635
        }
636
    }
637
  fib_check(&f);
638
  debug("-----\n");
639
}
640
641
void init(struct fib_node *n)
642
{
643
}
644
645
int main(void)
646
{
647
  struct fib_node *n;
648
  struct fib_iterator i, j;
649
  ip_addr a;
650
  int c;
651
652
  log_init_debug(NULL);
653
  resource_init();
654
  fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
655
  dump("init");
656
657
  a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
658
  a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
659
  a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
660
  a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
661
  a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
662
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
663
  dump("fill");
664
665
  fit_init(&i, &f);
666
  dump("iter init");
667
668
  fib_rehash(&f, 1);
669
  dump("rehash up");
670
671
  fib_rehash(&f, -1);
672
  dump("rehash down");
673
674
next:
675
  c = 0;
676
  FIB_ITERATE_START(&f, &i, z)
677
    {
678
      if (c)
679
        {
680
          FIB_ITERATE_PUT(&i, z);
681
          dump("iter");
682
          goto next;
683
        }
684
      c = 1;
685
      debug("got %p\n", z);
686
    }
687 6264aad1 Pavel Tvrdík
  FIB_ITERATE_END(z);
688 3ab001b9 Martin Mares
  dump("iter end");
689
690
  fit_init(&i, &f);
691
  fit_init(&j, &f);
692
  dump("iter init 2");
693
694
  n = fit_get(&f, &i);
695
  dump("iter step 2");
696
697
  fit_put(&i, n->next);
698
  dump("iter step 3");
699
700
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
701
  fib_delete(&f, n);
702
  dump("iter step 3");
703
704
  return 0;
705
}
706
707
#endif