nest/rt-fib.c

   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                  /* Must be at most 16 */
  65 #define HASH_LO_MARK /5
  66 #define HASH_LO_STEP 2
  67 #define HASH_LO_MIN 10
  68
  69 static void
  70 fib_ht_alloc(struct fib *f)
  71 {
  72   f->hash_size = 1 << f->hash_order;
  73   f->hash_shift = 16 - f->hash_order;
  74   if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP)
  75     f->entries_max = ~0;
  76   else
  77     f->entries_max = f->hash_size HASH_HI_MARK;
  78   if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP)
  79     f->entries_min = 0;
  80   else
  81     f->entries_min = f->hash_size HASH_LO_MARK;
  82   DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",
  83       f->hash_order, f->hash_size, f->entries_min, f->entries_max);
  84   f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
  85 }
  86
  87 static inline void
  88 fib_ht_free(struct fib_node **h)
  89 {
  90   mb_free(h);
  91 }
  92
  93 static inline unsigned
  94 fib_hash(struct fib *f, ip_addr *a)
  95 {
  96   return ipa_hash(*a) >> f->hash_shift;
  97 }
  98
  99 static void
 100 fib_dummy_init(struct fib_node *dummy UNUSED)
 101 {
 102 }
 103
 104 /**
 105  * fib_init - initialize a new FIB
 106  * @f: the FIB to be initialized (the structure itself being allocated by the caller)
 107  * @p: pool to allocate the nodes in
 108  * @node_size: node size to be used (each node consists of a standard header &fib_node
 109  * followed by user data)
 110  * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
 111  * (recommended)
 112  * @init: pointer a function to be called to initialize a newly created node
 113  *
 114  * This function initializes a newly allocated FIB and prepares it for use.
 115  */
 116 void
 117 fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, fib_init_func init)
 118 {
 119   if (!hash_order)
 120     hash_order = HASH_DEF_ORDER;
 121   f->fib_pool = p;
 122   f->fib_slab = sl_new(p, node_size);
 123   f->hash_order = hash_order;
 124   fib_ht_alloc(f);
 125   bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
 126   f->entries = 0;
 127   f->entries_min = 0;
 128   f->init = init ? : fib_dummy_init;
 129 }
 130
 131 static void
 132 fib_rehash(struct fib *f, int step)
 133 {
 134   unsigned old, new, oldn, newn, ni, nh;
 135   struct fib_node **n, *e, *x, **t, **m, **h;
 136
 137   old = f->hash_order;
 138   oldn = f->hash_size;
 139   new = old + step;
 140   m = h = f->hash_table;
 141   DBG("Re-hashing FIB from order %d to %d\n", old, new);
 142   f->hash_order = new;
 143   fib_ht_alloc(f);
 144   t = n = f->hash_table;
 145   newn = f->hash_size;
 146   ni = 0;
 147
 148   while (oldn--)
 149     {
 150       x = *h++;
 151       while (e = x)
 152         {
 153           x = e->next;
 154           nh = fib_hash(f, &e->prefix);
 155           while (nh > ni)
 156             {
 157               *t = NULL;
 158               ni++;
 159               t = ++n;
 160             }
 161           *t = e;
 162           t = &e->next;
 163         }
 164     }
 165   while (ni < newn)
 166     {
 167       *t = NULL;
 168       ni++;
 169       t = ++n;
 170     }
 171   fib_ht_free(m);
 172 }
 173
 174 /**
 175  * fib_find - search for FIB node by prefix
 176  * @f: FIB to search in
 177  * @a: pointer to IP address of the prefix
 178  * @len: prefix length
 179  *
 180  * Search for a FIB node corresponding to the given prefix, return
 181  * a pointer to it or %NULL if no such node exists.
 182  */
 183 void *
 184 fib_find(struct fib *f, ip_addr *a, int len)
 185 {
 186   struct fib_node *e = f->hash_table[fib_hash(f, a)];
 187
 188   while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
 189     e = e->next;
 190   return e;
 191 }
 192
 193 /*
 194 int
 195 fib_histogram(struct fib *f)
 196 {
 197   log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
 198
 199   int i, j;
 200   struct fib_node *e;
 201
 202   for (i = 0; i < f->hash_size; i++)
 203     {
 204       j = 0;
 205       for (e = f->hash_table[i]; e != NULL; e = e->next)
 206         j++;
 207       if (j > 0)
 208         log(L_WARN "Histogram line %d: %d", i, j);
 209     }
 210
 211   log(L_WARN "Histogram dump end");
 212 }
 213 */
 214
 215 /**
 216  * fib_get - find or create a FIB node
 217  * @f: FIB to work with
 218  * @a: pointer to IP address of the prefix
 219  * @len: prefix length
 220  *
 221  * Search for a FIB node corresponding to the given prefix and
 222  * return a pointer to it. If no such node exists, create it.
 223  */
 224 void *
 225 fib_get(struct fib *f, ip_addr *a, int len)
 226 {
 227   uint h = ipa_hash(*a);
 228   struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
 229   struct fib_node *g, *e = *ee;
 230   u32 uid = h << 16;
 231
 232   while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
 233     e = e->next;
 234   if (e)
 235     return e;
 236 #ifdef DEBUGGING
 237   if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
 238     bug("fib_get() called for invalid address");
 239 #endif
 240
 241   while ((g = *ee) && g->uid < uid)
 242     ee = &g->next;
 243   while ((g = *ee) && g->uid == uid)
 244     {
 245       ee = &g->next;
 246       uid++;
 247     }
 248
 249   if ((uid >> 16) != h)
 250     log(L_ERR "FIB hash table chains are too long");
 251
 252   // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
 253
 254   e = sl_alloc(f->fib_slab);
 255   e->prefix = *a;
 256   e->pxlen = len;
 257   e->next = *ee;
 258   e->uid = uid;
 259   *ee = e;
 260   e->readers = NULL;
 261   f->init(e);
 262   if (f->entries++ > f->entries_max)
 263     fib_rehash(f, HASH_HI_STEP);
 264
 265   return e;
 266 }
 267
 268 /**
 269  * fib_route - CIDR routing lookup
 270  * @f: FIB to search in
 271  * @a: pointer to IP address of the prefix
 272  * @len: prefix length
 273  *
 274  * Search for a FIB node with longest prefix matching the given
 275  * network, that is a node which a CIDR router would use for routing
 276  * that network.
 277  */
 278 void *
 279 fib_route(struct fib *f, ip_addr a, int len)
 280 {
 281   ip_addr a0;
 282   void *t;
 283
 284   while (len >= 0)
 285     {
 286       a0 = ipa_and(a, ipa_mkmask(len));
 287       t = fib_find(f, &a0, len);
 288       if (t)
 289         return t;
 290       len--;
 291     }
 292   return NULL;
 293 }
 294
 295 static inline void
 296 fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
 297 {
 298   if (to)
 299     {
 300       struct fib_iterator *j = to->readers;
 301       if (!j)
 302         {
 303           /* Fast path */
 304           to->readers = i;
 305           i->prev = (struct fib_iterator *) to;
 306         }
 307       else
 308         {
 309           /* Really merging */
 310           while (j->next)
 311             j = j->next;
 312           j->next = i;
 313           i->prev = j;
 314         }
 315       while (i && i->node)
 316         {
 317           i->node = NULL;
 318           i = i->next;
 319         }
 320     }
 321   else                                  /* No more nodes */
 322     while (i)
 323       {
 324         i->prev = NULL;
 325         i = i->next;
 326       }
 327 }
 328
 329 /**
 330  * fib_delete - delete a FIB node
 331  * @f: FIB to delete from
 332  * @E: entry to delete
 333  *
 334  * This function removes the given entry from the FIB,
 335  * taking care of all the asynchronous readers by shifting
 336  * them to the next node in the canonical reading order.
 337  */
 338 void
 339 fib_delete(struct fib *f, void *E)
 340 {
 341   struct fib_node *e = E;
 342   uint h = fib_hash(f, &e->prefix);
 343   struct fib_node **ee = f->hash_table + h;
 344   struct fib_iterator *it;
 345
 346   while (*ee)
 347     {
 348       if (*ee == e)
 349         {
 350           *ee = e->next;
 351           if (it = e->readers)
 352             {
 353               struct fib_node *l = e->next;
 354               while (!l)
 355                 {
 356                   h++;
 357                   if (h >= f->hash_size)
 358                     break;
 359                   else
 360                     l = f->hash_table[h];
 361                 }
 362               fib_merge_readers(it, l);
 363             }
 364           sl_free(f->fib_slab, e);
 365           if (f->entries-- < f->entries_min)
 366             fib_rehash(f, -HASH_LO_STEP);
 367           return;
 368         }
 369       ee = &((*ee)->next);
 370     }
 371   bug("fib_delete() called for invalid node");
 372 }
 373
 374 /**
 375  * fib_free - delete a FIB
 376  * @f: FIB to be deleted
 377  *
 378  * This function deletes a FIB -- it frees all memory associated
 379  * with it and all its entries.
 380  */
 381 void
 382 fib_free(struct fib *f)
 383 {
 384   fib_ht_free(f->hash_table);
 385   rfree(f->fib_slab);
 386 }
 387
 388 void
 389 fit_init(struct fib_iterator *i, struct fib *f)
 390 {
 391   unsigned h;
 392   struct fib_node *n;
 393
 394   i->efef = 0xff;
 395   for(h=0; h<f->hash_size; h++)
 396     if (n = f->hash_table[h])
 397       {
 398         i->prev = (struct fib_iterator *) n;
 399         if (i->next = n->readers)
 400           i->next->prev = i;
 401         n->readers = i;
 402         i->node = n;
 403         return;
 404       }
 405   /* The fib is empty, nothing to do */
 406   i->prev = i->next = NULL;
 407   i->node = NULL;
 408 }
 409
 410 struct fib_node *
 411 fit_get(struct fib *f, struct fib_iterator *i)
 412 {
 413   struct fib_node *n;
 414   struct fib_iterator *j, *k;
 415
 416   if (!i->prev)
 417     {
 418       /* We are at the end */
 419       i->hash = ~0 - 1;
 420       return NULL;
 421     }
 422   if (!(n = i->node))
 423     {
 424       /* No node info available, we are a victim of merging. Try harder. */
 425       j = i;
 426       while (j->efef == 0xff)
 427         j = j->prev;
 428       n = (struct fib_node *) j;
 429     }
 430   j = i->prev;
 431   if (k = i->next)
 432     k->prev = j;
 433   j->next = k;
 434   i->hash = fib_hash(f, &n->prefix);
 435   return n;
 436 }
 437
 438 void
 439 fit_put(struct fib_iterator *i, struct fib_node *n)
 440 {
 441   struct fib_iterator *j;
 442
 443   i->node = n;
 444   if (j = n->readers)
 445     j->prev = i;
 446   i->next = j;
 447   n->readers = i;
 448   i->prev = (struct fib_iterator *) n;
 449 }
 450
 451 void
 452 fit_put_next(struct fib *f, struct fib_iterator *i, struct fib_node *n, uint hpos)
 453 {
 454   if (n = n->next)
 455     goto found;
 456
 457   while (++hpos < f->hash_size)
 458     if (n = f->hash_table[hpos])
 459       goto found;
 460
 461   /* We are at the end */
 462   i->prev = i->next = NULL;
 463   i->node = NULL;
 464   return;
 465
 466 found:
 467   fit_put(i, n);
 468 }
 469
 470 #ifdef DEBUGGING
 471
 472 /**
 473  * fib_check - audit a FIB
 474  * @f: FIB to be checked
 475  *
 476  * This debugging function audits a FIB by checking its internal consistency.
 477  * Use when you suspect somebody of corrupting innocent data structures.
 478  */
 479 void
 480 fib_check(struct fib *f)
 481 {
 482   uint i, ec, lo, nulls;
 483
 484   ec = 0;
 485   for(i=0; i<f->hash_size; i++)
 486     {
 487       struct fib_node *n;
 488       lo = 0;
 489       for(n=f->hash_table[i]; n; n=n->next)
 490         {
 491           struct fib_iterator *j, *j0;
 492           uint h0 = ipa_hash(n->prefix);
 493           if (h0 < lo)
 494             bug("fib_check: discord in hash chains");
 495           lo = h0;
 496           if ((h0 >> f->hash_shift) != i)
 497             bug("fib_check: mishashed %x->%x (order %d)", h0, i, f->hash_order);
 498           j0 = (struct fib_iterator *) n;
 499           nulls = 0;
 500           for(j=n->readers; j; j=j->next)
 501             {
 502               if (j->prev != j0)
 503                 bug("fib_check: iterator->prev mismatch");
 504               j0 = j;
 505               if (!j->node)
 506                 nulls++;
 507               else if (nulls)
 508                 bug("fib_check: iterator nullified");
 509               else if (j->node != n)
 510                 bug("fib_check: iterator->node mismatch");
 511             }
 512           ec++;
 513         }
 514     }
 515   if (ec != f->entries)
 516     bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
 517 }
 518
 519 #endif
 520
 521 #ifdef TEST
 522
 523 #include "lib/resource.h"
 524
 525 struct fib f;
 526
 527 void dump(char *m)
 528 {
 529   uint i;
 530
 531   debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);
 532   for(i=0; i<f.hash_size; i++)
 533     {
 534       struct fib_node *n;
 535       struct fib_iterator *j;
 536       for(n=f.hash_table[i]; n; n=n->next)
 537         {
 538           debug("%04x %04x %p %I/%2d", i, ipa_hash(n->prefix), n, n->prefix, n->pxlen);
 539           for(j=n->readers; j; j=j->next)
 540             debug(" %p[%p]", j, j->node);
 541           debug("\n");
 542         }
 543     }
 544   fib_check(&f);
 545   debug("-----\n");
 546 }
 547
 548 void init(struct fib_node *n)
 549 {
 550 }
 551
 552 int main(void)
 553 {
 554   struct fib_node *n;
 555   struct fib_iterator i, j;
 556   ip_addr a;
 557   int c;
 558
 559   log_init_debug(NULL);
 560   resource_init();
 561   fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init);
 562   dump("init");
 563
 564   a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32);
 565   a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32);
 566   a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32);
 567   a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32);
 568   a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32);
 569   a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
 570   dump("fill");
 571
 572   fit_init(&i, &f);
 573   dump("iter init");
 574
 575   fib_rehash(&f, 1);
 576   dump("rehash up");
 577
 578   fib_rehash(&f, -1);
 579   dump("rehash down");
 580
 581 next:
 582   c = 0;
 583   FIB_ITERATE_START(&f, &i, z)
 584     {
 585       if (c)
 586         {
 587           FIB_ITERATE_PUT(&i, z);
 588           dump("iter");
 589           goto next;
 590         }
 591       c = 1;
 592       debug("got %p\n", z);
 593     }
 594   FIB_ITERATE_END(z);
 595   dump("iter end");
 596
 597   fit_init(&i, &f);
 598   fit_init(&j, &f);
 599   dump("iter init 2");
 600
 601   n = fit_get(&f, &i);
 602   dump("iter step 2");
 603
 604   fit_put(&i, n->next);
 605   dump("iter step 3");
 606
 607   a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32);
 608   fib_delete(&f, n);
 609   dump("iter step 3");
 610
 611   return 0;
 612 }
 613
 614 #endif