babeld/route.c

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