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
  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