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