babeld/route.c

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