sysdep/unix/krt.c

   1 /*
   2  *      BIRD -- UNIX Kernel Synchronization
   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 #define LOCAL_DEBUG
  10
  11 #include "nest/bird.h"
  12 #include "nest/iface.h"
  13 #include "nest/route.h"
  14 #include "nest/protocol.h"
  15 #include "lib/timer.h"
  16 #include "conf/conf.h"
  17
  18 #include "unix.h"
  19 #include "krt.h"
  20
  21 /*
  22  *  The whole kernel synchronization is a bit messy and touches some internals
  23  *  of the routing table engine, because routing table maintenance is a typical
  24  *  example of the proverbial compatibility between different Unices and we want
  25  *  to keep the overhead of our krt business as low as possible and avoid maintaining
  26  *  a local routing table copy.
  27  *
  28  *  The kernel syncer can work in three different modes (according to system config header):
  29  *      o  Single routing table, single krt protocol.  [traditional Unix]
  30  *      o  Many routing tables, separate krt protocols for all of them.
  31  *      o  Many routing tables, but every scan includes all tables, so we start
  32  *         separate krt protocols which cooperate with each other.  [Linux 2.2]
  33  *         In this case, we keep only a single scan timer.
  34  *
  35  *  The hacky bits:
  36  *      o  We use FIB node flags to keep track of route synchronization status.
  37  *      o  When starting up, we cheat by looking if there is another kernel
  38  *         krt instance to be initialized later and performing table scan
  39  *         only once for all the instances.
  40  *      o  We attach temporary rte's to routing tables.
  41  *
  42  *  If you are brave enough, continue now.  You cannot say you haven't been warned.
  43  */
  44
  45 static int krt_uptodate(rte *k, rte *e);
  46
  47 /*
  48  *      Global resources
  49  */
  50
  51 pool *krt_pool;
  52
  53 void
  54 krt_io_init(void)
  55 {
  56   krt_pool = rp_new(&root_pool, "Kernel Syncer");
  57   krt_if_io_init();
  58 }
  59
  60 /*
  61  *      Interfaces
  62  */
  63
  64 struct proto_config *cf_kif;
  65
  66 static struct kif_proto *kif_proto;
  67 static timer *kif_scan_timer;
  68 static bird_clock_t kif_last_shot;
  69
  70 static void
  71 kif_preconfig(struct protocol *P, struct config *c)
  72 {
  73   cf_kif = NULL;
  74 }
  75
  76 static void
  77 kif_scan(timer *t)
  78 {
  79   struct kif_proto *p = t->data;
  80
  81   DBG("KIF: It's interface scan time...\n");
  82   kif_last_shot = now;
  83   krt_if_scan(p);
  84 }
  85
  86 static void
  87 kif_force_scan(void)
  88 {
  89   if (kif_proto && kif_last_shot + 2 < now)
  90     {
  91       kif_scan(kif_scan_timer);
  92       tm_start(kif_scan_timer, ((struct kif_config *) kif_proto->p.cf)->scan_time);
  93     }
  94 }
  95
  96 static struct proto *
  97 kif_init(struct proto_config *c)
  98 {
  99   struct kif_proto *p = proto_new(c, sizeof(struct kif_proto));
 100   return &p->p;
 101 }
 102
 103 static int
 104 kif_start(struct proto *P)
 105 {
 106   struct kif_proto *p = (struct kif_proto *) P;
 107
 108   kif_proto = p;
 109   krt_if_start(p);
 110
 111   /* Start periodic interface scanning */
 112   kif_scan_timer = tm_new(P->pool);
 113   kif_scan_timer->hook = kif_scan;
 114   kif_scan_timer->data = p;
 115   kif_scan_timer->recurrent = KIF_CF->scan_time;
 116   kif_scan(kif_scan_timer);
 117   tm_start(kif_scan_timer, KIF_CF->scan_time);
 118
 119   return PS_UP;
 120 }
 121
 122 static int
 123 kif_shutdown(struct proto *P)
 124 {
 125   struct kif_proto *p = (struct kif_proto *) P;
 126
 127   tm_stop(kif_scan_timer);
 128   krt_if_shutdown(p);
 129   kif_proto = NULL;
 130
 131   if_start_update();    /* Remove all interfaces */
 132   if_end_update();
 133   /*
 134    *  FIXME: Is it really a good idea?  It causes routes to be flushed,
 135    *  but at the same time it avoids sending of these deletions to the kernel,
 136    *  because krt thinks the kernel itself has already removed the route
 137    *  when downing the interface.  Sad.
 138    */
 139
 140   return PS_DOWN;
 141 }
 142
 143 struct protocol proto_unix_iface = {
 144   name:         "Device",
 145   priority:     100,
 146   preconfig:    kif_preconfig,
 147   init:         kif_init,
 148   start:        kif_start,
 149   shutdown:     kif_shutdown,
 150 };
 151
 152 /*
 153  *      Inherited Routes
 154  */
 155
 156 #ifdef KRT_ALLOW_LEARN
 157
 158 static inline int
 159 krt_same_key(rte *a, rte *b)
 160 {
 161   return a->u.krt.proto == b->u.krt.proto &&
 162          a->u.krt.metric == b->u.krt.metric &&
 163          a->u.krt.type == b->u.krt.type;
 164 }
 165
 166 static void
 167 krt_learn_announce_update(struct krt_proto *p, rte *e)
 168 {
 169   net *n = e->net;
 170   rta *aa = rta_clone(e->attrs);
 171   rte *ee = rte_get_temp(aa);
 172   net *nn = net_get(p->p.table, n->n.prefix, n->n.pxlen);
 173   ee->net = nn;
 174   ee->pflags = 0;
 175   ee->u.krt = e->u.krt;
 176   rte_update(p->p.table, nn, &p->p, ee);
 177 }
 178
 179 static void
 180 krt_learn_announce_delete(struct krt_proto *p, net *n)
 181 {
 182   n = net_find(p->p.table, n->n.prefix, n->n.pxlen);
 183   if (n)
 184     rte_update(p->p.table, n, &p->p, NULL);
 185 }
 186
 187 static void
 188 krt_learn_scan(struct krt_proto *p, rte *e)
 189 {
 190   net *n0 = e->net;
 191   net *n = net_get(&p->krt_table, n0->n.prefix, n0->n.pxlen);
 192   rte *m, **mm;
 193
 194   e->attrs->source = RTS_INHERIT;
 195
 196   for(mm=&n->routes; m = *mm; mm=&m->next)
 197     if (krt_same_key(m, e))
 198       break;
 199   if (m)
 200     {
 201       if (krt_uptodate(m, e))
 202         {
 203           DBG("krt_learn_scan: SEEN\n");
 204           rte_free(e);
 205           m->u.krt.seen = 1;
 206         }
 207       else
 208         {
 209           DBG("krt_learn_scan: OVERRIDE\n");
 210           *mm = m->next;
 211           rte_free(m);
 212           m = NULL;
 213         }
 214     }
 215   else
 216     DBG("krt_learn_scan: CREATE\n");
 217   if (!m)
 218     {
 219       e->attrs = rta_lookup(e->attrs);
 220       e->next = n->routes;
 221       n->routes = e;
 222       e->u.krt.seen = 1;
 223     }
 224 }
 225
 226 static void
 227 krt_learn_prune(struct krt_proto *p)
 228 {
 229   struct fib *fib = &p->krt_table.fib;
 230   struct fib_iterator fit;
 231
 232   DBG("Pruning inheritance data...\n");
 233
 234   FIB_ITERATE_INIT(&fit, fib);
 235 again:
 236   FIB_ITERATE_START(fib, &fit, f)
 237     {
 238       net *n = (net *) f;
 239       rte *e, **ee, *best, **pbest, *old_best;
 240
 241       old_best = n->routes;
 242       best = NULL;
 243       pbest = NULL;
 244       ee = &n->routes;
 245       while (e = *ee)
 246         {
 247           if (!e->u.krt.seen)
 248             {
 249               *ee = e->next;
 250               rte_free(e);
 251               continue;
 252             }
 253           if (!best || best->u.krt.metric > e->u.krt.metric)
 254             {
 255               best = e;
 256               pbest = ee;
 257             }
 258           e->u.krt.seen = 0;
 259           ee = &e->next;
 260         }
 261       if (!n->routes)
 262         {
 263           DBG("%I/%d: deleting\n", n->n.prefix, n->n.pxlen);
 264           if (old_best)
 265             {
 266               krt_learn_announce_delete(p, n);
 267               n->n.flags &= ~KRF_INSTALLED;
 268             }
 269           FIB_ITERATE_PUT(&fit, f);
 270           fib_delete(fib, f);
 271           goto again;
 272         }
 273       *pbest = best->next;
 274       best->next = n->routes;
 275       n->routes = best;
 276       if (best != old_best || !(n->n.flags & KRF_INSTALLED))
 277         {
 278           DBG("%I/%d: announcing (metric=%d)\n", n->n.prefix, n->n.pxlen, best->u.krt.metric);
 279           krt_learn_announce_update(p, best);
 280           n->n.flags |= KRF_INSTALLED;
 281         }
 282       else
 283         DBG("%I/%d: uptodate (metric=%d)\n", n->n.prefix, n->n.pxlen, best->u.krt.metric);
 284     }
 285   FIB_ITERATE_END(f);
 286 }
 287
 288 static void
 289 krt_learn_async(struct krt_proto *p, rte *e, int new)
 290 {
 291   net *n0 = e->net;
 292   net *n = net_get(&p->krt_table, n0->n.prefix, n0->n.pxlen);
 293   rte *g, **gg, *best, **bestp, *old_best;
 294
 295   e->attrs->source = RTS_INHERIT;
 296
 297   old_best = n->routes;
 298   for(gg=&n->routes; g = *gg; gg = &g->next)
 299     if (krt_same_key(g, e))
 300       break;
 301   if (new)
 302     {
 303       if (g)
 304         {
 305           if (krt_uptodate(g, e))
 306             {
 307               DBG("krt_learn_async: same\n");
 308               rte_free(e);
 309               return;
 310             }
 311           DBG("krt_learn_async: update\n");
 312           *gg = g->next;
 313           rte_free(g);
 314         }
 315       else
 316         DBG("krt_learn_async: create\n");
 317       e->attrs = rta_lookup(e->attrs);
 318       e->next = n->routes;
 319       n->routes = e;
 320     }
 321   else if (!g)
 322     {
 323       DBG("krt_learn_async: not found\n");
 324       rte_free(e);
 325       return;
 326     }
 327   else
 328     {
 329       DBG("krt_learn_async: delete\n");
 330       *gg = g->next;
 331       rte_free(e);
 332       rte_free(g);
 333     }
 334   best = n->routes;
 335   bestp = &n->routes;
 336   for(gg=&n->routes; g=*gg; gg=&g->next)
 337     if (best->u.krt.metric > g->u.krt.metric)
 338       {
 339         best = g;
 340         bestp = gg;
 341       }
 342   if (best)
 343     {
 344       *bestp = best->next;
 345       best->next = n->routes;
 346       n->routes = best;
 347     }
 348   if (best != old_best)
 349     {
 350       DBG("krt_learn_async: distributing change\n");
 351       if (best)
 352         {
 353           krt_learn_announce_update(p, best);
 354           n->n.flags |= KRF_INSTALLED;
 355         }
 356       else
 357         {
 358           n->routes = NULL;
 359           krt_learn_announce_delete(p, n);
 360           n->n.flags &= ~KRF_INSTALLED;
 361         }
 362     }
 363 }
 364
 365 static void
 366 krt_learn_init(struct krt_proto *p)
 367 {
 368   if (KRT_CF->learn)
 369     rt_setup(p->p.pool, &p->krt_table, "Inherited");
 370 }
 371
 372 static void
 373 krt_dump(struct proto *P)
 374 {
 375   struct krt_proto *p = (struct krt_proto *) P;
 376
 377   if (!KRT_CF->learn)
 378     return;
 379   debug("KRT: Table of inheritable routes\n");
 380   rt_dump(&p->krt_table);
 381 }
 382
 383 static void
 384 krt_dump_attrs(rte *e)
 385 {
 386   debug(" [m=%d,p=%d,t=%d]", e->u.krt.metric, e->u.krt.proto, e->u.krt.type);
 387 }
 388
 389 #endif
 390
 391 /*
 392  *      Routes
 393  */
 394
 395 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 396 static timer *krt_scan_timer;
 397 static int krt_instance_count;
 398 static list krt_instance_list;
 399 #endif
 400
 401 static void
 402 krt_flush_routes(struct krt_proto *p)
 403 {
 404   struct rtable *t = p->p.table;
 405
 406   DBG("Flushing kernel routes...\n");
 407   FIB_WALK(&t->fib, f)
 408     {
 409       net *n = (net *) f;
 410       rte *e = n->routes;
 411       if (e)
 412         {
 413           rta *a = e->attrs;
 414           if (a->source != RTS_DEVICE && a->source != RTS_INHERIT)
 415             krt_set_notify(p, e->net, NULL, e);
 416         }
 417     }
 418   FIB_WALK_END;
 419 }
 420
 421 static int
 422 krt_uptodate(rte *k, rte *e)
 423 {
 424   rta *ka = k->attrs, *ea = e->attrs;
 425
 426   if (ka->dest != ea->dest)
 427     return 0;
 428   switch (ka->dest)
 429     {
 430     case RTD_ROUTER:
 431       return ipa_equal(ka->gw, ea->gw);
 432     case RTD_DEVICE:
 433       return !strcmp(ka->iface->name, ea->iface->name);
 434     default:
 435       return 1;
 436     }
 437 }
 438
 439 /*
 440  *  This gets called back when the low-level scanning code discovers a route.
 441  *  We expect that the route is a temporary rte and its attributes are uncached.
 442  */
 443
 444 void
 445 krt_got_route(struct krt_proto *p, rte *e)
 446 {
 447   rte *old;
 448   net *net = e->net;
 449   int src = e->u.krt.src;
 450   int verdict;
 451
 452 #ifdef CONFIG_AUTO_ROUTES
 453   if (e->attrs->dest == RTD_DEVICE)
 454     {
 455       /* It's a device route. Probably a kernel-generated one. */
 456       verdict = KRF_IGNORE;
 457       goto sentenced;
 458     }
 459 #endif
 460
 461 #ifdef KRT_ALLOW_LEARN
 462   if (src == KRT_SRC_ALIEN)
 463     {
 464       if (KRT_CF->learn)
 465         krt_learn_scan(p, e);
 466       else
 467         DBG("krt_parse_entry: Alien route, ignoring\n");
 468       return;
 469     }
 470 #endif
 471
 472   if (net->n.flags & KRF_VERDICT_MASK)
 473     {
 474       /* Route to this destination was already seen. Strange, but it happens... */
 475       DBG("Already seen.\n");
 476       return;
 477     }
 478
 479   if (net->n.flags & KRF_INSTALLED)
 480     {
 481       old = net->routes;
 482       ASSERT(old);
 483       if (krt_uptodate(e, old))
 484         verdict = KRF_SEEN;
 485       else
 486         verdict = KRF_UPDATE;
 487     }
 488   else
 489     verdict = KRF_DELETE;
 490
 491 sentenced:
 492   DBG("krt_parse_entry: verdict=%s\n", ((char *[]) { "CREATE", "SEEN", "UPDATE", "DELETE", "IGNORE" }) [verdict]);
 493
 494   net->n.flags = (net->n.flags & ~KRF_VERDICT_MASK) | verdict;
 495   if (verdict == KRF_UPDATE || verdict == KRF_DELETE)
 496     {
 497       /* Get a cached copy of attributes and link the route */
 498       rta *a = e->attrs;
 499       a->source = RTS_DUMMY;
 500       e->attrs = rta_lookup(a);
 501       e->next = net->routes;
 502       net->routes = e;
 503     }
 504   else
 505     rte_free(e);
 506 }
 507
 508 static void
 509 krt_prune(struct krt_proto *p)
 510 {
 511   struct proto *pp = &p->p;
 512   struct rtable *t = p->p.table;
 513   struct fib_node *f;
 514
 515   DBG("Pruning routes in table %s...\n", t->name);
 516   FIB_WALK(&t->fib, f)
 517     {
 518       net *n = (net *) f;
 519       int verdict = f->flags & KRF_VERDICT_MASK;
 520       rte *new, *old;
 521
 522       if (verdict != KRF_CREATE && verdict != KRF_SEEN && verdict != KRF_IGNORE)
 523         {
 524           old = n->routes;
 525           n->routes = old->next;
 526         }
 527       else
 528         old = NULL;
 529       new = n->routes;
 530
 531       switch (verdict)
 532         {
 533         case KRF_CREATE:
 534           if (new && (f->flags & KRF_INSTALLED))
 535             {
 536               DBG("krt_prune: reinstalling %I/%d\n", n->n.prefix, n->n.pxlen);
 537               krt_set_notify(p, n, new, NULL);
 538             }
 539           break;
 540         case KRF_SEEN:
 541         case KRF_IGNORE:
 542           /* Nothing happens */
 543           break;
 544         case KRF_UPDATE:
 545           DBG("krt_prune: updating %I/%d\n", n->n.prefix, n->n.pxlen);
 546           krt_set_notify(p, n, new, old);
 547           break;
 548         case KRF_DELETE:
 549           DBG("krt_prune: deleting %I/%d\n", n->n.prefix, n->n.pxlen);
 550           krt_set_notify(p, n, NULL, old);
 551           break;
 552         default:
 553           bug("krt_prune: invalid route status");
 554         }
 555       if (old)
 556         rte_free(old);
 557       f->flags &= ~KRF_VERDICT_MASK;
 558     }
 559   FIB_WALK_END;
 560
 561 #ifdef KRT_ALLOW_LEARN
 562   if (KRT_CF->learn)
 563     krt_learn_prune(p);
 564 #endif
 565 }
 566
 567 void
 568 krt_got_route_async(struct krt_proto *p, rte *e, int new)
 569 {
 570   net *net = e->net;
 571   rte *old = net->routes;
 572   int src = e->u.krt.src;
 573
 574   switch (src)
 575     {
 576     case KRT_SRC_BIRD:
 577       ASSERT(0);
 578     case KRT_SRC_REDIRECT:
 579       DBG("It's a redirect, kill him! Kill! Kill!\n");
 580       krt_set_notify(p, net, NULL, e);
 581       break;
 582     case KRT_SRC_ALIEN:
 583 #ifdef KRT_ALLOW_LEARN
 584       if (KRT_CF->learn)
 585         {
 586           krt_learn_async(p, e, new);
 587           return;
 588         }
 589 #endif
 590       /* Fall-thru */
 591     default:
 592       DBG("Discarding\n");
 593       rte_update(p->p.table, net, &p->p, NULL);
 594     }
 595   rte_free(e);
 596 }
 597
 598 /*
 599  *      Periodic scanning
 600  */
 601
 602 static void
 603 krt_scan(timer *t)
 604 {
 605   struct krt_proto *p;
 606
 607   kif_force_scan();
 608 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 609   {
 610     void *q;
 611     DBG("KRT: It's route scan time...\n");
 612     krt_scan_fire(NULL);
 613     WALK_LIST(q, krt_instance_list)
 614       {
 615         p = SKIP_BACK(struct krt_proto, instance_node, q);
 616         krt_prune(p);
 617       }
 618   }
 619 #else
 620   p = t->data;
 621   DBG("KRT: It's route scan time for %s...\n", p->p.name);
 622   krt_scan_fire(p);
 623   krt_prune(p);
 624 #endif
 625 }
 626
 627 /*
 628  *      Updates
 629  */
 630
 631 static void
 632 krt_notify(struct proto *P, net *net, rte *new, rte *old, struct ea_list *tmpa)
 633 {
 634   struct krt_proto *p = (struct krt_proto *) P;
 635
 636   if (new && (!krt_capable(new) || new->attrs->source == RTS_INHERIT))
 637     new = NULL;
 638   if (!(net->n.flags & KRF_INSTALLED))
 639     old = NULL;
 640   if (new)
 641     net->n.flags |= KRF_INSTALLED;
 642   else
 643     net->n.flags &= ~KRF_INSTALLED;
 644   krt_set_notify(p, net, new, old);
 645 }
 646
 647 /*
 648  *      Protocol glue
 649  */
 650
 651 struct proto_config *cf_krt;
 652
 653 static void
 654 krt_preconfig(struct protocol *P, struct config *c)
 655 {
 656   cf_krt = NULL;
 657   krt_scan_preconfig(c);
 658 }
 659
 660 static void
 661 krt_postconfig(struct proto_config *C)
 662 {
 663   struct krt_config *c = (struct krt_config *) C;
 664
 665 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 666   struct krt_config *first = (struct krt_config *) cf_krt;
 667   if (first->scan_time != c->scan_time)
 668     cf_error("All kernel syncers must use the same table scan interval");
 669 #endif
 670
 671   if (C->table->krt_attached)
 672     cf_error("Kernel syncer (%s) already attached to table %s", C->table->krt_attached->name, C->table->name);
 673   C->table->krt_attached = C;
 674   krt_scan_postconfig(c);
 675 }
 676
 677 static timer *
 678 krt_start_timer(struct krt_proto *p)
 679 {
 680   timer *t;
 681
 682   t = tm_new(p->krt_pool);
 683   t->hook = krt_scan;
 684   t->data = p;
 685   t->recurrent = KRT_CF->scan_time;
 686   tm_start(t, KRT_CF->scan_time);
 687   return t;
 688 }
 689
 690 static int
 691 krt_start(struct proto *P)
 692 {
 693   struct krt_proto *p = (struct krt_proto *) P;
 694   int first = 1;
 695
 696 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 697   if (!krt_instance_count++)
 698     init_list(&krt_instance_list);
 699   else
 700     first = 0;
 701   p->krt_pool = krt_pool;
 702   add_tail(&krt_instance_list, &p->instance_node);
 703 #else
 704   p->krt_pool = P->pool;
 705 #endif
 706
 707 #ifdef KRT_ALLOW_LEARN
 708   krt_learn_init(p);
 709 #endif
 710
 711   krt_scan_start(p, first);
 712   krt_set_start(p, first);
 713
 714   /* Start periodic routing table scanning */
 715 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 716   if (first)
 717     krt_scan_timer = krt_start_timer(p);
 718   p->scan_timer = krt_scan_timer;
 719   /* If this is the last instance to be initialized, kick the timer */
 720   if (!P->proto->startup_counter)
 721     krt_scan(p->scan_timer);
 722 #else
 723   p->scan_timer = krt_start_timer(p);
 724   krt_scan(p->scan_timer);
 725 #endif
 726
 727   return PS_UP;
 728 }
 729
 730 static int
 731 krt_shutdown(struct proto *P)
 732 {
 733   struct krt_proto *p = (struct krt_proto *) P;
 734   int last = 1;
 735
 736 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 737   rem_node(&p->instance_node);
 738   if (--krt_instance_count)
 739     last = 0;
 740   else
 741 #endif
 742     tm_stop(p->scan_timer);
 743
 744   if (!KRT_CF->persist)
 745     krt_flush_routes(p);
 746
 747   krt_set_shutdown(p, last);
 748   krt_scan_shutdown(p, last);
 749
 750 #ifdef CONFIG_ALL_TABLES_AT_ONCE
 751   if (last)
 752     rfree(krt_scan_timer);
 753 #endif
 754
 755   return PS_DOWN;
 756 }
 757
 758 static struct proto *
 759 krt_init(struct proto_config *c)
 760 {
 761   struct krt_proto *p = proto_new(c, sizeof(struct krt_proto));
 762
 763   p->p.rt_notify = krt_notify;
 764   p->p.min_scope = SCOPE_HOST;
 765   return &p->p;
 766 }
 767
 768 struct protocol proto_unix_kernel = {
 769   name:         "Kernel",
 770   priority:     80,
 771   preconfig:    krt_preconfig,
 772   postconfig:   krt_postconfig,
 773   init:         krt_init,
 774   start:        krt_start,
 775   shutdown:     krt_shutdown,
 776 #ifdef KRT_ALLOW_LEARN
 777   dump:         krt_dump,
 778   dump_attrs:   krt_dump_attrs,
 779 #endif
 780 };