babeld/route.c

   1 /*
   2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
   3 Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a copy
   6 of this software and associated documentation files (the "Software"), to deal
   7 in the Software without restriction, including without limitation the rights
   8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 copies of the Software, and to permit persons to whom the Software is
  10 furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  21 THE SOFTWARE.
  22 */
  23
  24 #include <zebra.h>
  25 #include "if.h"
  26
  27 #include "babeld.h"
  28 #include "util.h"
  29 #include "kernel.h"
  30 #include "babel_interface.h"
  31 #include "source.h"
  32 #include "neighbour.h"
  33 #include "route.h"
  34 #include "xroute.h"
  35 #include "message.h"
  36 #include "resend.h"
  37 #include "babel_errors.h"
  38
  39 static void consider_route(struct babel_route *route);
  40
  41 struct babel_route **routes = NULL;
  42 static int route_slots = 0, max_route_slots = 0;
  43 int kernel_metric = 0;
  44 enum babel_diversity diversity_kind = DIVERSITY_NONE;
  45 int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR;
  46 int keep_unfeasible = 0;
  47
  48 int smoothing_half_life = 0;
  49 static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */
  50
  51 /* We maintain a list of "slots", ordered by prefix.  Every slot
  52    contains a linked list of the routes to this prefix, with the
  53    installed route, if any, at the head of the list. */
  54
  55 static int
  56 route_compare(const unsigned char *prefix, unsigned char plen,
  57                struct babel_route *route)
  58 {
  59     int i = memcmp(prefix, route->src->prefix, 16);
  60     if(i != 0)
  61         return i;
  62
  63     if(plen < route->src->plen)
  64         return -1;
  65     else if(plen > route->src->plen)
  66         return 1;
  67     else
  68         return 0;
  69 }
  70
  71 /* Performs binary search, returns -1 in case of failure.  In the latter
  72    case, new_return is the place where to insert the new element. */
  73
  74 static int
  75 find_route_slot(const unsigned char *prefix, unsigned char plen,
  76                 int *new_return)
  77 {
  78     int p, m, g, c;
  79
  80     if(route_slots < 1) {
  81         if(new_return)
  82             *new_return = 0;
  83         return -1;
  84     }
  85
  86     p = 0; g = route_slots - 1;
  87
  88     do {
  89         m = (p + g) / 2;
  90         c = route_compare(prefix, plen, routes[m]);
  91         if(c == 0)
  92             return m;
  93         else if(c < 0)
  94             g = m - 1;
  95         else
  96             p = m + 1;
  97     } while(p <= g);
  98
  99     if(new_return)
 100         *new_return = p;
 101
 102     return -1;
 103 }
 104
 105 struct babel_route *
 106 find_route(const unsigned char *prefix, unsigned char plen,
 107            struct neighbour *neigh, const unsigned char *nexthop)
 108 {
 109     struct babel_route *route;
 110     int i = find_route_slot(prefix, plen, NULL);
 111
 112     if(i < 0)
 113         return NULL;
 114
 115     route = routes[i];
 116
 117     while(route) {
 118         if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
 119             return route;
 120         route = route->next;
 121     }
 122
 123     return NULL;
 124 }
 125
 126 struct babel_route *
 127 find_installed_route(const unsigned char *prefix, unsigned char plen)
 128 {
 129     int i = find_route_slot(prefix, plen, NULL);
 130
 131     if(i >= 0 && routes[i]->installed)
 132         return routes[i];
 133
 134     return NULL;
 135 }
 136
 137 /* Returns an overestimate of the number of installed routes. */
 138 int
 139 installed_routes_estimate(void)
 140 {
 141     return route_slots;
 142 }
 143
 144 static int
 145 resize_route_table(int new_slots)
 146 {
 147     struct babel_route **new_routes;
 148     assert(new_slots >= route_slots);
 149
 150     if(new_slots == 0) {
 151         new_routes = NULL;
 152         free(routes);
 153     } else {
 154         new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
 155         if(new_routes == NULL)
 156             return -1;
 157     }
 158
 159     max_route_slots = new_slots;
 160     routes = new_routes;
 161     return 1;
 162 }
 163
 164 /* Insert a route into the table.  If successful, retains the route.
 165    On failure, caller must free the route. */
 166 static struct babel_route *
 167 insert_route(struct babel_route *route)
 168 {
 169     int i, n;
 170
 171     assert(!route->installed);
 172
 173     i = find_route_slot(route->src->prefix, route->src->plen, &n);
 174
 175     if(i < 0) {
 176         if(route_slots >= max_route_slots)
 177             resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
 178         if(route_slots >= max_route_slots)
 179             return NULL;
 180         assert(routes);
 181         route->next = NULL;
 182         if(n < route_slots)
 183             memmove(routes + n + 1, routes + n,
 184                     (route_slots - n) * sizeof(struct babel_route*));
 185         route_slots++;
 186         routes[n] = route;
 187     } else {
 188         struct babel_route *r;
 189         r = routes[i];
 190         while(r->next)
 191             r = r->next;
 192         r->next = route;
 193         route->next = NULL;
 194     }
 195
 196     return route;
 197 }
 198
 199 void
 200 flush_route(struct babel_route *route)
 201 {
 202     int i;
 203     struct source *src;
 204     unsigned oldmetric;
 205     int lost = 0;
 206
 207     oldmetric = route_metric(route);
 208     src = route->src;
 209
 210     if(route->installed) {
 211         uninstall_route(route);
 212         lost = 1;
 213     }
 214
 215     i = find_route_slot(route->src->prefix, route->src->plen, NULL);
 216     assert(i >= 0 && i < route_slots);
 217
 218     if(route == routes[i]) {
 219         routes[i] = route->next;
 220         route->next = NULL;
 221         free(route);
 222
 223         if(routes[i] == NULL) {
 224             if(i < route_slots - 1)
 225                 memmove(routes + i, routes + i + 1,
 226                         (route_slots - i - 1) * sizeof(struct babel_route*));
 227             routes[route_slots - 1] = NULL;
 228             route_slots--;
 229         }
 230
 231         if(route_slots == 0)
 232             resize_route_table(0);
 233         else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
 234             resize_route_table(max_route_slots / 2);
 235     } else {
 236         struct babel_route *r = routes[i];
 237         while(r->next != route)
 238             r = r->next;
 239         r->next = route->next;
 240         route->next = NULL;
 241         free(route);
 242     }
 243
 244     if(lost)
 245         route_lost(src, oldmetric);
 246
 247     release_source(src);
 248 }
 249
 250 void
 251 flush_all_routes(void)
 252 {
 253     int i;
 254
 255     /* Start from the end, to avoid shifting the table. */
 256     i = route_slots - 1;
 257     while(i >= 0) {
 258         while(i < route_slots) {
 259         /* Uninstall first, to avoid calling route_lost. */
 260             if(routes[i]->installed)
 261                 uninstall_route(routes[i]);
 262             flush_route(routes[i]);
 263         }
 264         i--;
 265     }
 266
 267     check_sources_released();
 268 }
 269
 270 void
 271 flush_neighbour_routes(struct neighbour *neigh)
 272 {
 273     int i;
 274
 275     i = 0;
 276     while(i < route_slots) {
 277         struct babel_route *r;
 278         r = routes[i];
 279         while(r) {
 280             if(r->neigh == neigh) {
 281                 flush_route(r);
 282                 goto again;
 283             }
 284             r = r->next;
 285         }
 286         i++;
 287     again:
 288         ;
 289     }
 290 }
 291
 292 void
 293 flush_interface_routes(struct interface *ifp, int v4only)
 294 {
 295     int i;
 296
 297     i = 0;
 298     while(i < route_slots) {
 299         struct babel_route *r;
 300         r = routes[i];
 301         while(r) {
 302             if(r->neigh->ifp == ifp &&
 303                (!v4only || v4mapped(r->nexthop))) {
 304                 flush_route(r);
 305                 goto again;
 306             }
 307             r = r->next;
 308         }
 309         i++;
 310     again:
 311         ;
 312     }
 313 }
 314
 315 struct route_stream {
 316     int installed;
 317     int index;
 318     struct babel_route *next;
 319 };
 320
 321
 322 struct route_stream *
 323 route_stream(int installed)
 324 {
 325     struct route_stream *stream;
 326
 327     stream = malloc(sizeof(struct route_stream));
 328     if(stream == NULL)
 329        return NULL;
 330
 331     stream->installed = installed;
 332     stream->index = installed ? 0 : -1;
 333     stream->next = NULL;
 334
 335     return stream;
 336 }
 337
 338 struct babel_route *
 339 route_stream_next(struct route_stream *stream)
 340 {
 341     if(stream->installed) {
 342         while(stream->index < route_slots && !routes[stream->index]->installed)
 343             stream->index++;
 344
 345         if(stream->index < route_slots)
 346             return routes[stream->index++];
 347         else
 348             return NULL;
 349     } else {
 350         struct babel_route *next;
 351         if(!stream->next) {
 352             stream->index++;
 353             if(stream->index >= route_slots)
 354                 return NULL;
 355             stream->next = routes[stream->index];
 356         }
 357         next = stream->next;
 358         stream->next = next->next;
 359         return next;
 360     }
 361 }
 362
 363 void
 364 route_stream_done(struct route_stream *stream)
 365 {
 366     free(stream);
 367 }
 368
 369 static int
 370 metric_to_kernel(int metric)
 371 {
 372     return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
 373 }
 374
 375 /* This is used to maintain the invariant that the installed route is at
 376    the head of the list. */
 377 static void
 378 move_installed_route(struct babel_route *route, int i)
 379 {
 380     assert(i >= 0 && i < route_slots);
 381     assert(route->installed);
 382
 383     if(route != routes[i]) {
 384         struct babel_route *r = routes[i];
 385         while(r->next != route)
 386             r = r->next;
 387         r->next = route->next;
 388         route->next = routes[i];
 389         routes[i] = route;
 390     }
 391 }
 392
 393 void
 394 install_route(struct babel_route *route)
 395 {
 396     int i, rc;
 397
 398     if(route->installed)
 399         return;
 400
 401     if(!route_feasible(route))
 402         flog_err(EC_BABEL_ROUTE, "WARNING: installing unfeasible route (this shouldn't happen).");
 403
 404     i = find_route_slot(route->src->prefix, route->src->plen, NULL);
 405     assert(i >= 0 && i < route_slots);
 406
 407     if(routes[i] != route && routes[i]->installed) {
 408         flog_err(EC_BABEL_ROUTE,
 409                   "WARNING: attempting to install duplicate route (this shouldn't happen).");
 410         return;
 411     }
 412
 413     rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
 414                       route->nexthop,
 415                       route->neigh->ifp->ifindex,
 416                       metric_to_kernel(route_metric(route)), NULL, 0, 0);
 417     if(rc < 0) {
 418         int save = errno;
 419         flog_err(EC_BABEL_ROUTE, "kernel_route(ADD): %s",
 420                   safe_strerror(errno));
 421         if(save != EEXIST)
 422             return;
 423     }
 424     route->installed = 1;
 425     move_installed_route(route, i);
 426
 427 }
 428
 429 void
 430 uninstall_route(struct babel_route *route)
 431 {
 432     int rc;
 433
 434     if(!route->installed)
 435         return;
 436
 437     rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
 438                       route->nexthop,
 439                       route->neigh->ifp->ifindex,
 440                       metric_to_kernel(route_metric(route)), NULL, 0, 0);
 441     if(rc < 0)
 442         flog_err(EC_BABEL_ROUTE, "kernel_route(FLUSH): %s",
 443                   safe_strerror(errno));
 444
 445     route->installed = 0;
 446 }
 447
 448 /* This is equivalent to uninstall_route followed with install_route,
 449    but without the race condition.  The destination of both routes
 450    must be the same. */
 451
 452 static void
 453 switch_routes(struct babel_route *old, struct babel_route *new)
 454 {
 455     int rc;
 456
 457     if(!old) {
 458         install_route(new);
 459         return;
 460     }
 461
 462     if(!old->installed)
 463         return;
 464
 465     if(!route_feasible(new))
 466         flog_err(EC_BABEL_ROUTE, "WARNING: switching to unfeasible route (this shouldn't happen).");
 467
 468     rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
 469                       old->nexthop, old->neigh->ifp->ifindex,
 470                       metric_to_kernel(route_metric(old)),
 471                       new->nexthop, new->neigh->ifp->ifindex,
 472                       metric_to_kernel(route_metric(new)));
 473     if(rc < 0) {
 474         flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY): %s",
 475                   safe_strerror(errno));
 476         return;
 477     }
 478
 479     old->installed = 0;
 480     new->installed = 1;
 481     move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
 482                                               NULL));
 483 }
 484
 485 static void
 486 change_route_metric(struct babel_route *route,
 487                     unsigned refmetric, unsigned cost, unsigned add)
 488 {
 489     int old, new;
 490     int newmetric = MIN(refmetric + cost + add, INFINITY);
 491
 492     old = metric_to_kernel(route_metric(route));
 493     new = metric_to_kernel(newmetric);
 494
 495     if(route->installed && old != new) {
 496         int rc;
 497         rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen,
 498                           route->nexthop, route->neigh->ifp->ifindex,
 499                           old,
 500                           route->nexthop, route->neigh->ifp->ifindex,
 501                           new);
 502         if(rc < 0) {
 503             flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY metric): %s",
 504                       safe_strerror(errno));
 505             return;
 506         }
 507     }
 508
 509     /* Update route->smoothed_metric using the old metric. */
 510     route_smoothed_metric(route);
 511
 512     route->refmetric = refmetric;
 513     route->cost = cost;
 514     route->add_metric = add;
 515
 516     if(smoothing_half_life == 0) {
 517         route->smoothed_metric = route_metric(route);
 518         route->smoothed_metric_time = babel_now.tv_sec;
 519     }
 520 }
 521
 522 static void
 523 retract_route(struct babel_route *route)
 524 {
 525     /* We cannot simply remove the route from the kernel, as that might
 526        cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
 527     change_route_metric(route, INFINITY, INFINITY, 0);
 528 }
 529
 530 int
 531 route_feasible(struct babel_route *route)
 532 {
 533     return update_feasible(route->src, route->seqno, route->refmetric);
 534 }
 535
 536 int
 537 route_old(struct babel_route *route)
 538 {
 539     return route->time < babel_now.tv_sec - route->hold_time * 7 / 8;
 540 }
 541
 542 int
 543 route_expired(struct babel_route *route)
 544 {
 545     return route->time < babel_now.tv_sec - route->hold_time;
 546 }
 547
 548 static int
 549 channels_interfere(int ch1, int ch2)
 550 {
 551     if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING
 552        || ch2 == BABEL_IF_CHANNEL_NONINTERFERING)
 553         return 0;
 554     if(ch1 == BABEL_IF_CHANNEL_INTERFERING
 555        || ch2 == BABEL_IF_CHANNEL_INTERFERING)
 556         return 1;
 557     return ch1 == ch2;
 558 }
 559
 560 int
 561 route_interferes(struct babel_route *route, struct interface *ifp)
 562 {
 563     struct babel_interface *babel_ifp = NULL;
 564     switch(diversity_kind) {
 565     case DIVERSITY_NONE:
 566         return 1;
 567     case DIVERSITY_INTERFACE_1:
 568         return route->neigh->ifp == ifp;
 569     case DIVERSITY_CHANNEL_1:
 570     case DIVERSITY_CHANNEL:
 571         if(route->neigh->ifp == ifp)
 572             return 1;
 573         babel_ifp = babel_get_if_nfo(ifp);
 574         if(channels_interfere(babel_ifp->channel,
 575                               babel_get_if_nfo(route->neigh->ifp)->channel))
 576             return 1;
 577         if(diversity_kind == DIVERSITY_CHANNEL) {
 578             int i;
 579             for(i = 0; i < DIVERSITY_HOPS; i++) {
 580                 if(route->channels[i] == 0)
 581                     break;
 582                 if(channels_interfere(babel_ifp->channel, route->channels[i]))
 583                     return 1;
 584             }
 585         }
 586         return 0;
 587     }
 588
 589     return 1;
 590 }
 591
 592 int
 593 update_feasible(struct source *src,
 594                 unsigned short seqno, unsigned short refmetric)
 595 {
 596     if(src == NULL)
 597         return 1;
 598
 599     if(src->time < babel_now.tv_sec - SOURCE_GC_TIME)
 600         /* Never mind what is probably stale data */
 601         return 1;
 602
 603     if(refmetric >= INFINITY)
 604         /* Retractions are always feasible */
 605         return 1;
 606
 607     return (seqno_compare(seqno, src->seqno) > 0 ||
 608             (src->seqno == seqno && refmetric < src->metric));
 609 }
 610
 611 void
 612 change_smoothing_half_life(int half_life)
 613 {
 614     if(half_life <= 0) {
 615         smoothing_half_life = 0;
 616         two_to_the_one_over_hl = 0;
 617         return;
 618     }
 619
 620     smoothing_half_life = half_life;
 621     switch(smoothing_half_life) {
 622     case 1: two_to_the_one_over_hl = 131072; break;
 623     case 2: two_to_the_one_over_hl = 92682; break;
 624     case 3: two_to_the_one_over_hl = 82570; break;
 625     case 4: two_to_the_one_over_hl = 77935; break;
 626     default:
 627         /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
 628         two_to_the_one_over_hl = 0x10000 + 45426 / half_life;
 629     }
 630 }
 631
 632 /* Update the smoothed metric, return the new value. */
 633 int
 634 route_smoothed_metric(struct babel_route *route)
 635 {
 636     int metric = route_metric(route);
 637
 638     if(smoothing_half_life <= 0 ||                 /* no smoothing */
 639        metric >= INFINITY ||                       /* route retracted */
 640        route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */
 641        route->smoothed_metric == metric) {         /* already converged */
 642         route->smoothed_metric = metric;
 643         route->smoothed_metric_time = babel_now.tv_sec;
 644     } else {
 645         int diff;
 646         /* We randomise the computation, to minimise global synchronisation
 647            and hence oscillations. */
 648         while(route->smoothed_metric_time <=
 649               babel_now.tv_sec - smoothing_half_life) {
 650             diff = metric - route->smoothed_metric;
 651             route->smoothed_metric += roughly(diff) / 2;
 652             route->smoothed_metric_time += smoothing_half_life;
 653         }
 654         while(route->smoothed_metric_time < babel_now.tv_sec) {
 655             diff = metric - route->smoothed_metric;
 656             route->smoothed_metric +=
 657                 roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000;
 658             route->smoothed_metric_time++;
 659         }
 660
 661         diff = metric - route->smoothed_metric;
 662         if(diff > -4 && diff < 4)
 663             route->smoothed_metric = metric;
 664     }
 665
 666     /* change_route_metric relies on this */
 667     assert(route->smoothed_metric_time == babel_now.tv_sec);
 668     return route->smoothed_metric;
 669 }
 670
 671 static int
 672 route_acceptable(struct babel_route *route, int feasible,
 673                  struct neighbour *exclude)
 674 {
 675     if(route_expired(route))
 676         return 0;
 677     if(feasible && !route_feasible(route))
 678         return 0;
 679     if(exclude && route->neigh == exclude)
 680         return 0;
 681     return 1;
 682 }
 683
 684 /* Find the best route according to the weak ordering.  Any
 685    linearisation of the strong ordering (see consider_route) will do,
 686    we use sm <= sm'.  We could probably use a lexical ordering, but
 687    that's probably overkill. */
 688
 689 struct babel_route *
 690 find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
 691                 struct neighbour *exclude)
 692 {
 693     struct babel_route *route = NULL, *r = NULL;
 694     int i = find_route_slot(prefix, plen, NULL);
 695
 696     if(i < 0)
 697         return NULL;
 698
 699     route = routes[i];
 700     while(route && !route_acceptable(route, feasible, exclude))
 701         route = route->next;
 702
 703     if(!route)
 704         return NULL;
 705
 706     r = route->next;
 707     while(r) {
 708         if(route_acceptable(r, feasible, exclude) &&
 709            (route_smoothed_metric(r) < route_smoothed_metric(route)))
 710             route = r;
 711         r = r->next;
 712     }
 713
 714     return route;
 715 }
 716
 717 void
 718 update_route_metric(struct babel_route *route)
 719 {
 720     int oldmetric = route_metric(route);
 721     int old_smoothed_metric = route_smoothed_metric(route);
 722
 723     if(route_expired(route)) {
 724         if(route->refmetric < INFINITY) {
 725             route->seqno = seqno_plus(route->src->seqno, 1);
 726             retract_route(route);
 727             if(oldmetric < INFINITY)
 728                 route_changed(route, route->src, oldmetric);
 729         }
 730     } else {
 731         struct neighbour *neigh = route->neigh;
 732         int add_metric = input_filter(route->src->id,
 733                                       route->src->prefix, route->src->plen,
 734                                       neigh->address,
 735                                       neigh->ifp->ifindex);
 736         change_route_metric(route, route->refmetric,
 737                             neighbour_cost(route->neigh), add_metric);
 738         if(route_metric(route) != oldmetric ||
 739            route_smoothed_metric(route) != old_smoothed_metric)
 740             route_changed(route, route->src, oldmetric);
 741     }
 742 }
 743
 744 /* Called whenever a neighbour's cost changes, to update the metric of
 745    all routes through that neighbour. */
 746 void
 747 update_neighbour_metric(struct neighbour *neigh, int changed)
 748 {
 749
 750     if(changed) {
 751         int i;
 752
 753         for(i = 0; i < route_slots; i++) {
 754             struct babel_route *r = routes[i];
 755             while(r) {
 756                 if(r->neigh == neigh)
 757                     update_route_metric(r);
 758                 r = r->next;
 759             }
 760         }
 761     }
 762 }
 763
 764 void
 765 update_interface_metric(struct interface *ifp)
 766 {
 767     int i;
 768
 769     for(i = 0; i < route_slots; i++) {
 770         struct babel_route *r = routes[i];
 771         while(r) {
 772             if(r->neigh->ifp == ifp)
 773                 update_route_metric(r);
 774             r = r->next;
 775         }
 776     }
 777 }
 778
 779 /* This is called whenever we receive an update. */
 780 struct babel_route *
 781 update_route(const unsigned char *router_id,
 782              const unsigned char *prefix, unsigned char plen,
 783              unsigned short seqno, unsigned short refmetric,
 784              unsigned short interval,
 785              struct neighbour *neigh, const unsigned char *nexthop,
 786              const unsigned char *channels, int channels_len)
 787 {
 788     struct babel_route *route;
 789     struct source *src;
 790     int metric, feasible;
 791     int add_metric;
 792     int hold_time = MAX((4 * interval) / 100 + interval / 50, 15);
 793
 794     if(memcmp(router_id, myid, 8) == 0)
 795         return NULL;
 796
 797     if(martian_prefix(prefix, plen)) {
 798         flog_err(EC_BABEL_ROUTE, "Rejecting martian route to %s through %s.",
 799                  format_prefix(prefix, plen), format_address(nexthop));
 800         return NULL;
 801     }
 802
 803     add_metric = input_filter(router_id, prefix, plen,
 804                               neigh->address, neigh->ifp->ifindex);
 805     if(add_metric >= INFINITY)
 806         return NULL;
 807
 808     route = find_route(prefix, plen, neigh, nexthop);
 809
 810     if(route && memcmp(route->src->id, router_id, 8) == 0)
 811         /* Avoid scanning the source table. */
 812         src = route->src;
 813     else
 814         src = find_source(router_id, prefix, plen, 1, seqno);
 815
 816     if(src == NULL)
 817         return NULL;
 818
 819     feasible = update_feasible(src, seqno, refmetric);
 820     metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
 821
 822     if(route) {
 823         struct source *oldsrc;
 824         unsigned short oldmetric;
 825         int lost = 0;
 826
 827         oldsrc = route->src;
 828         oldmetric = route_metric(route);
 829
 830         /* If a successor switches sources, we must accept his update even
 831            if it makes a route unfeasible in order to break any routing loops
 832            in a timely manner.  If the source remains the same, we ignore
 833            the update. */
 834         if(!feasible && route->installed) {
 835             debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s (%s %d %d -> %s %d %d).",
 836                    format_prefix(src->prefix, src->plen),
 837                    format_eui64(route->src->id),
 838                    route->seqno, route->refmetric,
 839                    format_eui64(src->id), seqno, refmetric);
 840             if(src != route->src) {
 841                 uninstall_route(route);
 842                 lost = 1;
 843             }
 844         }
 845
 846         route->src = retain_source(src);
 847         if((feasible || keep_unfeasible) && refmetric < INFINITY)
 848             route->time = babel_now.tv_sec;
 849         route->seqno = seqno;
 850
 851         memset(&route->channels, 0, sizeof(route->channels));
 852         if(channels_len > 0)
 853             memcpy(&route->channels, channels,
 854                    MIN(channels_len, DIVERSITY_HOPS));
 855
 856         change_route_metric(route,
 857                             refmetric, neighbour_cost(neigh), add_metric);
 858         route->hold_time = hold_time;
 859
 860         route_changed(route, oldsrc, oldmetric);
 861         if(lost)
 862             route_lost(oldsrc, oldmetric);
 863
 864         if(!feasible)
 865             send_unfeasible_request(neigh, route->installed && route_old(route),
 866                                     seqno, metric, src);
 867         release_source(oldsrc);
 868     } else {
 869         struct babel_route *new_route;
 870
 871         if(refmetric >= INFINITY)
 872             /* Somebody's retracting a route we never saw. */
 873             return NULL;
 874         if(!feasible) {
 875             send_unfeasible_request(neigh, 0, seqno, metric, src);
 876             if(!keep_unfeasible)
 877                 return NULL;
 878         }
 879
 880         route = malloc(sizeof(struct babel_route));
 881         if(route == NULL) {
 882             perror("malloc(route)");
 883             return NULL;
 884         }
 885
 886         route->src = retain_source(src);
 887         route->refmetric = refmetric;
 888         route->cost = neighbour_cost(neigh);
 889         route->add_metric = add_metric;
 890         route->seqno = seqno;
 891         route->neigh = neigh;
 892         memcpy(route->nexthop, nexthop, 16);
 893         route->time = babel_now.tv_sec;
 894         route->hold_time = hold_time;
 895         route->smoothed_metric = MAX(route_metric(route), INFINITY / 2);
 896         route->smoothed_metric_time = babel_now.tv_sec;
 897         route->installed = 0;
 898         memset(&route->channels, 0, sizeof(route->channels));
 899         if(channels_len > 0)
 900             memcpy(&route->channels, channels,
 901                    MIN(channels_len, DIVERSITY_HOPS));
 902         route->next = NULL;
 903         new_route = insert_route(route);
 904         if(new_route == NULL) {
 905             flog_err(EC_BABEL_ROUTE, "Couldn't insert route.");
 906             free(route);
 907             return NULL;
 908         }
 909         consider_route(route);
 910     }
 911     return route;
 912 }
 913
 914 /* We just received an unfeasible update.  If it's any good, send
 915    a request for a new seqno. */
 916 void
 917 send_unfeasible_request(struct neighbour *neigh, int force,
 918                         unsigned short seqno, unsigned short metric,
 919                         struct source *src)
 920 {
 921     struct babel_route *route = find_installed_route(src->prefix, src->plen);
 922
 923     if(seqno_minus(src->seqno, seqno) > 100) {
 924         /* Probably a source that lost its seqno.  Let it time-out. */
 925         return;
 926     }
 927
 928     if(force || !route || route_metric(route) >= metric + 512) {
 929         send_unicast_multihop_request(neigh, src->prefix, src->plen,
 930                                       src->metric >= INFINITY ?
 931                                       src->seqno :
 932                                       seqno_plus(src->seqno, 1),
 933                                       src->id, 127);
 934     }
 935 }
 936
 937 /* This takes a feasible route and decides whether to install it.
 938    This uses the strong ordering, which is defined by sm <= sm' AND
 939    m <= m'.  This ordering is not total, which is what causes
 940    hysteresis. */
 941
 942 static void
 943 consider_route(struct babel_route *route)
 944 {
 945     struct babel_route *installed;
 946     struct xroute *xroute;
 947
 948     if(route->installed)
 949         return;
 950
 951     if(!route_feasible(route))
 952         return;
 953
 954     xroute = find_xroute(route->src->prefix, route->src->plen);
 955     if(xroute)
 956         return;
 957
 958     installed = find_installed_route(route->src->prefix, route->src->plen);
 959
 960     if(installed == NULL)
 961         goto install;
 962
 963     if(route_metric(route) >= INFINITY)
 964         return;
 965
 966     if(route_metric(installed) >= INFINITY)
 967         goto install;
 968
 969     if(route_metric(installed) >= route_metric(route) &&
 970        route_smoothed_metric(installed) > route_smoothed_metric(route))
 971         goto install;
 972
 973     return;
 974
 975  install:
 976     switch_routes(installed, route);
 977     if(installed && route->installed)
 978         send_triggered_update(route, installed->src, route_metric(installed));
 979     else
 980         send_update(NULL, 1, route->src->prefix, route->src->plen);
 981     return;
 982 }
 983
 984 void
 985 retract_neighbour_routes(struct neighbour *neigh)
 986 {
 987     int i;
 988
 989     for(i = 0; i < route_slots; i++) {
 990         struct babel_route *r = routes[i];
 991         while(r) {
 992             if(r->neigh == neigh) {
 993                 if(r->refmetric != INFINITY) {
 994                     unsigned short oldmetric = route_metric(r);
 995                     retract_route(r);
 996                     if(oldmetric != INFINITY)
 997                         route_changed(r, r->src, oldmetric);
 998                 }
 999             }
1000             r = r->next;
1001         }
1002     }
1003 }
1004
1005 void
1006 send_triggered_update(struct babel_route *route, struct source *oldsrc,
1007                       unsigned oldmetric)
1008 {
1009     unsigned newmetric, diff;
1010     /* 1 means send speedily, 2 means resend */
1011     int urgent;
1012
1013     if(!route->installed)
1014         return;
1015
1016     newmetric = route_metric(route);
1017     diff =
1018         newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
1019
1020     if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
1021         /* Switching sources can cause transient routing loops.
1022            Retractions can cause blackholes. */
1023         urgent = 2;
1024     else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
1025         /* Route getting significantly worse */
1026         urgent = 1;
1027     else if(unsatisfied_request(route->src->prefix, route->src->plen,
1028                                 route->seqno, route->src->id))
1029         /* Make sure that requests are satisfied speedily */
1030         urgent = 1;
1031     else if(oldmetric >= INFINITY && newmetric < INFINITY)
1032         /* New route */
1033         urgent = 0;
1034     else if(newmetric < oldmetric && diff < 1024)
1035         /* Route getting better.  This may be a transient fluctuation, so
1036            don't advertise it to avoid making routes unfeasible later on. */
1037         return;
1038     else if(diff < 384)
1039         /* Don't fret about trivialities */
1040         return;
1041     else
1042         urgent = 0;
1043
1044     if(urgent >= 2)
1045         send_update_resend(NULL, route->src->prefix, route->src->plen);
1046     else
1047         send_update(NULL, urgent, route->src->prefix, route->src->plen);
1048
1049     if(oldmetric < INFINITY) {
1050         if(newmetric >= oldmetric + 512) {
1051             send_request_resend(NULL, route->src->prefix, route->src->plen,
1052                                 route->src->metric >= INFINITY ?
1053                                 route->src->seqno :
1054                                 seqno_plus(route->src->seqno, 1),
1055                                 route->src->id);
1056         } else if(newmetric >= oldmetric + 288) {
1057             send_request(NULL, route->src->prefix, route->src->plen);
1058         }
1059     }
1060 }
1061
1062 /* A route has just changed.  Decide whether to switch to a different route or
1063    send an update. */
1064 void
1065 route_changed(struct babel_route *route,
1066               struct source *oldsrc, unsigned short oldmetric)
1067 {
1068     if(route->installed) {
1069         struct babel_route *better_route;
1070         /* Do this unconditionally -- microoptimisation is not worth it. */
1071         better_route =
1072             find_best_route(route->src->prefix, route->src->plen, 1, NULL);
1073         if(better_route && route_metric(better_route) < route_metric(route))
1074             consider_route(better_route);
1075     }
1076
1077     if(route->installed) {
1078         /* We didn't change routes after all. */
1079         send_triggered_update(route, oldsrc, oldmetric);
1080     } else {
1081         /* Reconsider routes even when their metric didn't decrease,
1082            they may not have been feasible before. */
1083         consider_route(route);
1084     }
1085 }
1086
1087 /* We just lost the installed route to a given destination. */
1088 void
1089 route_lost(struct source *src, unsigned oldmetric)
1090 {
1091     struct babel_route *new_route;
1092     new_route = find_best_route(src->prefix, src->plen, 1, NULL);
1093     if(new_route) {
1094         consider_route(new_route);
1095     } else if(oldmetric < INFINITY) {
1096         /* Avoid creating a blackhole. */
1097         send_update_resend(NULL, src->prefix, src->plen);
1098         /* If the route was usable enough, try to get an alternate one.
1099            If it was not, we could be dealing with oscillations around
1100            the value of INFINITY. */
1101         if(oldmetric <= INFINITY / 2)
1102             send_request_resend(NULL, src->prefix, src->plen,
1103                                 src->metric >= INFINITY ?
1104                                 src->seqno : seqno_plus(src->seqno, 1),
1105                                 src->id);
1106     }
1107 }
1108
1109 /* This is called periodically to flush old routes.  It will also send
1110    requests for routes that are about to expire. */
1111 void
1112 expire_routes(void)
1113 {
1114     struct babel_route *r;
1115     int i;
1116
1117     debugf(BABEL_DEBUG_COMMON,"Expiring old routes.");
1118
1119     i = 0;
1120     while(i < route_slots) {
1121         r = routes[i];
1122         while(r) {
1123             /* Protect against clock being stepped. */
1124             if(r->time > babel_now.tv_sec || route_old(r)) {
1125                 flush_route(r);
1126                 goto again;
1127             }
1128
1129             update_route_metric(r);
1130
1131             if(r->installed && r->refmetric < INFINITY) {
1132                 if(route_old(r))
1133                     /* Route about to expire, send a request. */
1134                     send_unicast_request(r->neigh,
1135                                          r->src->prefix, r->src->plen);
1136             }
1137             r = r->next;
1138         }
1139         i++;
1140     again:
1141         ;
1142     }
1143 }