Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-fib.c @ 08c69a77

History | View | Annotate | Download (8.27 KB)

1
/*
2
 *        BIRD -- Forwarding Information Base -- Data Structures
3
 *
4
 *        (c) 1998 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#define LOCAL_DEBUG
10

    
11
#include <string.h>
12

    
13
#include "nest/bird.h"
14
#include "nest/route.h"
15

    
16
#define HASH_DEF_ORDER 10
17
#define HASH_HI_MARK *4
18
#define HASH_HI_STEP 2
19
#define HASH_HI_MAX 16                        /* Must be at most 16 */
20
#define HASH_LO_MARK /5
21
#define HASH_LO_STEP 2
22
#define HASH_LO_MIN 10
23

    
24
static void
25
fib_ht_alloc(struct fib *f)
26
{
27
  f->hash_size = 1 << f->hash_order;
28
  f->hash_shift = 16 - f->hash_order;
29
  if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
30
    f->entries_max = ~0;
31
  else
32
    f->entries_max = f->hash_size HASH_HI_MARK;
33
  if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
34
    f->entries_min = 0;
35
  else
36
    f->entries_min = f->hash_size HASH_LO_MARK;
37
  DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
38
      f->hash_order, f->hash_size, f->entries_min, f->entries_max);
39
  f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
40
}
41

    
42
static inline void
43
fib_ht_free(struct fib_node **h)
44
{
45
  mb_free(h);
46
}
47

    
48
static inline unsigned
49
fib_hash(struct fib *f, ip_addr *a)
50
{
51
  return ipa_hash(*a) >> f->hash_shift;
52
}
53

    
54
void
55
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, void (*init)(struct fib_node *))
56
{
57
  if (!hash_order)
58
    hash_order = HASH_DEF_ORDER;
59
  f->fib_pool = p;
60
  f->fib_slab = sl_new(p, node_size);
61
  f->hash_order = hash_order;
62
  fib_ht_alloc(f);
63
  bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
64
  f->entries = 0;
65
  f->entries_min = 0;
66
  f->init = init;
67
}
68

    
69
static void
70
fib_rehash(struct fib *f, int step)
71
{
72
  unsigned old, new, oldn, newn, ni, nh;
73
  struct fib_node **n, *e, *x, **t, **m, **h;
74

    
75
  old = f->hash_order;
76
  oldn = f->hash_size;
77
  new = old + step;
78
  m = h = f->hash_table;
79
  DBG("Re-hashing FIB from order %d to %d\n", old, new);
80
  f->hash_order = new;
81
  fib_ht_alloc(f);
82
  t = n = f->hash_table;
83
  newn = f->hash_size;
84
  ni = 0;
85

    
86
  while (old--)
87
    {
88
      x = *h++;
89
      while (e = x)
90
        {
91
          x = e->next;
92
          nh = fib_hash(f, &e->prefix);
93
          while (nh > ni)
94
            {
95
              *t = NULL;
96
              ni++;
97
              t = ++n;
98
            }
99
          *t = e;
100
          t = &e->next;
101
        }
102
    }
103
  while (ni < newn)
104
    {
105
      *t = NULL;
106
      ni++;
107
      t = ++n;
108
    }
109
  fib_ht_free(m);
110
}
111

    
112
void *
113
fib_find(struct fib *f, ip_addr *a, int len)
114
{
115
  struct fib_node *e = f->hash_table[fib_hash(f, a)];
116

    
117
  while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
118
    e = e->next;
119
  return e;
120
}
121

    
122
void *
123
fib_get(struct fib *f, ip_addr *a, int len)
124
{
125
  unsigned int h = ipa_hash(*a);
126
  struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
127
  struct fib_node *g, *e = *ee;
128

    
129
  while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
130
    e = e->next;
131
  if (e)
132
    return e;
133
#ifdef DEBUGGING
134
  if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
135
    bug("fib_get() called for invalid address");
136
#endif
137
  e = sl_alloc(f->fib_slab);
138
  e->prefix = *a;
139
  e->pxlen = len;
140
  while ((g = *ee) && ipa_hash(g->prefix) < h)
141
    ee = &g->next;
142
  e->next = *ee;
143
  *ee = e;
144
  e->readers = NULL;
145
  f->init(e);
146
  if (f->entries++ > f->entries_max)
147
    fib_rehash(f, HASH_HI_STEP);
148
  return e;
149
}
150

    
151
static inline void
152
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
153
{
154
  if (to)
155
    {
156
      struct fib_iterator *j = to->readers;
157
      if (!j)
158
        {
159
          /* Fast path */
160
          to->readers = i;
161
          i->prev = (struct fib_iterator *) to;
162
        fixup:
163
          while (i && i->node)
164
            {
165
              i->node = NULL;
166
              i = i->next;
167
            }
168
          return;
169
        }
170
      /* Really merging */
171
      while (j->next)
172
        j = j->next;
173
      j->next = i;
174
      i->prev = j;
175
      goto fixup;
176
    }
177
  else                                        /* No more nodes */
178
    while (i)
179
      {
180
        i->prev = NULL;
181
        i = i->next;
182
      }
183
}
184

    
185
void
186
fib_delete(struct fib *f, void *E)
187
{
188
  struct fib_node *e = E;
189
  unsigned int h = fib_hash(f, &e->prefix);
190
  struct fib_node **ee = f->hash_table + h;
191
  struct fib_iterator *it;
192

    
193
  while (*ee)
194
    {
195
      if (*ee == e)
196
        {
197
          *ee = e->next;
198
          if (it = e->readers)
199
            {
200
              struct fib_node *l = e->next;
201
              while (!l)
202
                {
203
                  h++;
204
                  if (h >= f->hash_size)
205
                    break;
206
                  else
207
                    l = f->hash_table[h];
208
                }
209
              fib_merge_readers(it, l);
210
            }
211
          sl_free(f->fib_slab, e);
212
          if (f->entries-- < f->entries_min)
213
            fib_rehash(f, -HASH_LO_STEP);
214
          return;
215
        }
216
      ee = &((*ee)->next);
217
    }
218
  bug("fib_delete() called for invalid node");
219
}
220

    
221
void
222
fib_free(struct fib *f)
223
{
224
  fib_ht_free(f->hash_table);
225
  rfree(f->fib_slab);
226
}
227

    
228
void
229
fit_init(struct fib_iterator *i, struct fib *f)
230
{
231
  unsigned h;
232
  struct fib_node *n;
233

    
234
  i->efef = 0xff;
235
  for(h=0; h<f->hash_size; h++)
236
    if (n = f->hash_table[h])
237
      {
238
        i->prev = (struct fib_iterator *) n;
239
        if (i->next = n->readers)
240
          i->next->prev = i;
241
        n->readers = i;
242
        i->node = n;
243
        return;
244
      }
245
  /* The fib is empty, nothing to do */
246
  i->prev = i->next = NULL;
247
  i->node = NULL;
248
}
249

    
250
struct fib_node *
251
fit_get(struct fib *f, struct fib_iterator *i)
252
{
253
  struct fib_node *n;
254
  struct fib_iterator *j, *k;
255

    
256
  if (!i->prev)
257
    {
258
      /* We are at the end */
259
      i->hash = f->hash_size;
260
      return NULL;
261
    }
262
  if (!(n = i->node))
263
    {
264
      /* No node info available, we are a victim of merging. Try harder. */
265
      j = i;
266
      while (j->efef == 0xff)
267
        j = j->prev;
268
      n = (struct fib_node *) j;
269
    }
270
  j = i->prev;
271
  if (k = i->next)
272
    k->prev = j;
273
  j->next = k;
274
  i->hash = fib_hash(f, &n->prefix);
275
  return n;
276
}
277

    
278
void
279
fit_put(struct fib_iterator *i, struct fib_node *n)
280
{
281
  struct fib_iterator *j;
282

    
283
  i->node = n;
284
  if (j = n->readers)
285
    j->prev = i;
286
  i->next = j;
287
  n->readers = i;
288
  i->prev = (struct fib_iterator *) n;
289
}
290

    
291
#ifdef DEBUGGING
292

    
293
void
294
fib_check(struct fib *f)
295
{
296
  unsigned int i, ec, lo, nulls;
297

    
298
  ec = 0;
299
  for(i=0; i<f->hash_size; i++)
300
    {
301
      struct fib_node *n;
302
      lo = 0;
303
      for(n=f->hash_table[i]; n; n=n->next)
304
        {
305
          struct fib_iterator *j, *j0;
306
          unsigned int h0 = ipa_hash(n->prefix);
307
          if (h0 < lo)
308
            bug("fib_check: discord in hash chains");
309
          lo = h0;
310
          if ((h0 >> f->hash_shift) != i)
311
            bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
312
          j0 = (struct fib_iterator *) n;
313
          nulls = 0;
314
          for(j=n->readers; j; j=j->next)
315
            {
316
              if (j->prev != j0)
317
                bug("fib_check: iterator->prev mismatch");
318
              j0 = j;
319
              if (!j->node)
320
                nulls++;
321
              else if (nulls)
322
                bug("fib_check: iterator nullified");
323
              else if (j->node != n)
324
                bug("fib_check: iterator->node mismatch");
325
            }
326
          ec++;
327
        }
328
    }
329
  if (ec != f->entries)
330
    bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
331
}
332

    
333
#endif
334

    
335
#ifdef TEST
336

    
337
#include "lib/resource.h"
338

    
339
struct fib f;
340

    
341
void dump(char *m)
342
{
343
  unsigned int i;
344

    
345
  debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
346
  for(i=0; i<f.hash_size; i++)
347
    {
348
      struct fib_node *n;
349
      struct fib_iterator *j;
350
      for(n=f.hash_table[i]; n; n=n->next)
351
        {
352
          debug("%04x %04x %p %I/%2d", i, ipa_hash(n->prefix), n, n->prefix, n->pxlen);
353
          for(j=n->readers; j; j=j->next)
354
            debug(" %p[%p]", j, j->node);
355
          debug("\n");
356
        }
357
    }
358
  fib_check(&f);
359
  debug("-----\n");
360
}
361

    
362
void init(struct fib_node *n)
363
{
364
}
365

    
366
int main(void)
367
{
368
  struct fib_node *n;
369
  struct fib_iterator i, j;
370
  ip_addr a;
371
  int c;
372

    
373
  log_init_debug(NULL);
374
  resource_init();
375
  fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
376
  dump("init");
377

    
378
  a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
379
  a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
380
  a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
381
  a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
382
  a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
383
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
384
  dump("fill");
385

    
386
  fit_init(&i, &f);
387
  dump("iter init");
388

    
389
  fib_rehash(&f, 1);
390
  dump("rehash up");
391

    
392
  fib_rehash(&f, -1);
393
  dump("rehash down");
394

    
395
next:
396
  c = 0;
397
  FIB_ITERATE_START(&f, &i, z)
398
    {
399
      if (c)
400
        {
401
          FIB_ITERATE_PUT(&i, z);
402
          dump("iter");
403
          goto next;
404
        }
405
      c = 1;
406
      debug("got %p\n", z);
407
    }
408
  FIB_ITERATE_END;
409
  dump("iter end");
410

    
411
  fit_init(&i, &f);
412
  fit_init(&j, &f);
413
  dump("iter init 2");
414

    
415
  n = fit_get(&f, &i);
416
  dump("iter step 2");
417

    
418
  fit_put(&i, n->next);
419
  dump("iter step 3");
420

    
421
  a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
422
  fib_delete(&f, n);
423
  dump("iter step 3");
424

    
425
  return 0;
426
}
427

    
428
#endif