route.c 27.1 KB
Newer Older
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1
/*
2
Copyright (c) 2007-2011 by Juliusz Chroboczek
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <assert.h>
28
#include <sys/time.h>
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
29

30
#include "babeld.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
31 32
#include "util.h"
#include "kernel.h"
33
#include "interface.h"
34
#include "source.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
35 36 37 38
#include "neighbour.h"
#include "route.h"
#include "xroute.h"
#include "message.h"
39
#include "resend.h"
40
#include "configuration.h"
41
#include "local.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
42

43 44
struct route **routes = NULL;
static int route_slots = 0, max_route_slots = 0;
45
int kernel_metric = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
46
int allow_duplicates = -1;
47
int diversity_kind = DIVERSITY_NONE;
48
int diversity_factor = 256;     /* in units of 1/256 */
49
int keep_unfeasible = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
50

51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
/* We maintain a list of "slots", ordered by prefix.  Every slot
   contains a linked list of the routes to this prefix, with the
   installed route, if any, at the head of the list. */

static int
route_compare(const unsigned char *prefix, unsigned char plen,
               struct route *route)
{
    int i = memcmp(prefix, route->src->prefix, 16);
    if(i != 0)
        return i;

    if(plen < route->src->plen)
        return -1;
    else if(plen > route->src->plen)
        return 1;
    else
        return 0;
}

/* Performs binary search, returns -1 in case of failure.  In the latter
   case, new_return is the place where to insert the new element. */

static int
find_route_slot(const unsigned char *prefix, unsigned char plen,
                int *new_return)
{
    int p, m, g, c;

    if(route_slots < 1) {
        if(new_return)
            *new_return = 0;
        return -1;
    }

    p = 0; g = route_slots - 1;

    do {
        m = (p + g) / 2;
        c = route_compare(prefix, plen, routes[m]);
        if(c == 0)
            return m;
        else if(c < 0)
            g = m - 1;
        else
            p = m + 1;
    } while(p <= g);

    if(new_return)
        *new_return = p;

    return -1;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
105
struct route *
106
find_route(const unsigned char *prefix, unsigned char plen,
107
           struct neighbour *neigh, const unsigned char *nexthop)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
108
{
109 110 111 112 113 114 115 116 117 118 119 120
    struct route *route;
    int i = find_route_slot(prefix, plen, NULL);

    if(i < 0)
        return NULL;

    route = routes[i];

    while(route) {
        if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
            return route;
        route = route->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
121
    }
122

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
123 124 125 126
    return NULL;
}

struct route *
127
find_installed_route(const unsigned char *prefix, unsigned char plen)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
128
{
129 130 131 132 133
    int i = find_route_slot(prefix, plen, NULL);

    if(i >= 0 && routes[i]->installed)
        return routes[i];

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
134 135 136
    return NULL;
}

137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
static int
resize_route_table(int new_slots)
{
    struct route **new_routes;
    assert(new_slots >= route_slots);

    if(new_slots == 0) {
        new_routes = NULL;
        free(routes);
    } else {
        new_routes = realloc(routes, new_slots * sizeof(struct route*));
        if(new_routes == NULL)
            return -1;
    }

    max_route_slots = new_slots;
    routes = new_routes;
    return 1;
}

/* Insert a route into the table.  If successful, retains the route.
   On failure, caller must free the route. */
static struct route *
insert_route(struct route *route)
{
    int i, n;

    assert(!route->installed);

    i = find_route_slot(route->src->prefix, route->src->plen, &n);

    if(i < 0) {
        if(route_slots >= max_route_slots)
            resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
        if(route_slots >= max_route_slots)
            return NULL;
        route->next = NULL;
        if(n < route_slots)
            memmove(routes + n + 1, routes + n,
                    (route_slots - n) * sizeof(struct route*));
        route_slots++;
        routes[n] = route;
    } else {
        struct route *r;
        r = routes[i];
        while(r->next)
            r = r->next;
        r->next = route;
        route->next = NULL;
    }

    return route;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
191 192 193
void
flush_route(struct route *route)
{
194
    int i;
195
    struct source *src;
196 197
    unsigned oldmetric;
    int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
198

199
    oldmetric = route_metric(route);
200
    src = route->src;
201

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
202 203
    if(route->installed) {
        uninstall_route(route);
204
        lost = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
205 206
    }

207 208
    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
    assert(i >= 0 && i < route_slots);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
209

210
    local_notify_route(route, LOCAL_FLUSH);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
211

212 213 214 215 216 217 218
    if(route == routes[i]) {
        routes[i] = route->next;
        route->next = NULL;
        free(route);

        if(routes[i] == NULL) {
            if(i < route_slots - 1)
219
                memmove(routes + i, routes + i + 1,
220 221 222
                        (route_slots - i - 1) * sizeof(struct route*));
            routes[route_slots - 1] = NULL;
            route_slots--;
223
        }
224 225 226 227 228 229 230 231 232 233 234 235

        if(route_slots == 0)
            resize_route_table(0);
        else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
            resize_route_table(max_route_slots / 2);
    } else {
        struct route *r = routes[i];
        while(r->next != route)
            r = r->next;
        r->next = route->next;
        route->next = NULL;
        free(route);
236 237
    }

238 239
    if(lost)
        route_lost(src, oldmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
240 241
}

242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
void
flush_all_routes()
{
    /* Start from the end, to avoid shifting the table. */
    int i = route_slots - 1;
    while(i >= 0) {
        while(i < route_slots) {
        /* Uninstall first, to avoid calling route_lost. */
            if(routes[i]->installed)
                uninstall_route(routes[0]);
            flush_route(routes[i]);
        }
        i--;
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
258 259 260 261 262
void
flush_neighbour_routes(struct neighbour *neigh)
{
    int i;

263 264
    i = 0;
    while(i < route_slots) {
265 266 267 268 269 270 271 272
        struct route *r;
        r = routes[i];
        while(r) {
            if(r->neigh == neigh) {
                flush_route(r);
                goto again;
            }
            r = r->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
273
        }
274 275 276
        i++;
    again:
        ;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
277 278 279
    }
}

280
void
281
flush_interface_routes(struct interface *ifp, int v4only)
282 283 284
{
    int i;

285 286
    i = 0;
    while(i < route_slots) {
287 288 289 290 291 292 293 294 295 296
        struct route *r;
        r = routes[i];
        while(r) {
            if(r->neigh->ifp == ifp &&
               (!v4only || v4mapped(r->nexthop))) {
                flush_route(r);
                goto again;
            }
            r = r->next;
        }
297 298 299
        i++;
    again:
        ;
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
    }
}

/* Iterate a function over all routes. */
void
for_all_routes(void (*f)(struct route*, void*), void *closure)
{
    int i;

    for(i = 0; i < route_slots; i++) {
        struct route *r = routes[i];
        while(r) {
            (*f)(r, closure);
            r = r->next;
        }
    }
}

void
for_all_installed_routes(void (*f)(struct route*, void*), void *closure)
{
    int i;

    for(i = 0; i < route_slots; i++) {
        if(routes[i]->installed)
            (*f)(routes[i], closure);
    }
}

/* Find any route with a given source.  This should go when we fix our
   data structures. */
struct route *
find_route_with_source(struct source *src)
{
    int i;

    for(i = 0; i < route_slots; i++) {
        struct route *r = routes[i];
        while(r) {
            if(r->src == src)
                return r;
            r = r->next;
342 343
        }
    }
344
    return NULL;
345 346
}

347 348 349 350 351
static int
metric_to_kernel(int metric)
{
    return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
}
352

353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370
/* This is used to maintain the invariant that the installed route is at
   the head of the list. */
static void
move_installed_route(struct route *route, int i)
{
    assert(i >= 0 && i < route_slots);
    assert(route->installed);

    if(route != routes[i]) {
        struct route *r = routes[i];
        while(r->next != route)
            r = r->next;
        r->next = route->next;
        route->next = routes[i];
        routes[i] = route;
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
371 372 373
void
install_route(struct route *route)
{
374
    int i, rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
375 376 377 378

    if(route->installed)
        return;

379 380 381 382
    if(!route_feasible(route))
        fprintf(stderr, "WARNING: installing unfeasible route "
                "(this shouldn't happen).");

383 384 385 386 387 388 389 390 391
    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
    assert(i >= 0 && i < route_slots);

    if(routes[i] != route && routes[i]->installed) {
        fprintf(stderr, "WARNING: attempting to install duplicate route "
                "(this shouldn't happen).");
        return;
    }

392
    rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
393
                      route->nexthop,
394
                      route->neigh->ifp->ifindex,
395
                      metric_to_kernel(route_metric(route)), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
396
    if(rc < 0) {
397
        int save = errno;
398
        perror("kernel_route(ADD)");
399
        if(save != EEXIST)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
400 401 402
            return;
    }
    route->installed = 1;
403 404
    move_installed_route(route, i);

405
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
406 407 408 409 410
}

void
uninstall_route(struct route *route)
{
411 412
    int rc;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
413 414 415
    if(!route->installed)
        return;

416
    rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
417
                      route->nexthop,
418
                      route->neigh->ifp->ifindex,
419
                      metric_to_kernel(route_metric(route)), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
420
    if(rc < 0)
421
        perror("kernel_route(FLUSH)");
422

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
423
    route->installed = 0;
424
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
425 426
}

427 428 429 430
/* This is equivalent to uninstall_route followed with install_route,
   but without the race condition.  The destination of both routes
   must be the same. */

431
static void
432
switch_routes(struct route *old, struct route *new)
433 434 435 436 437 438 439 440 441 442 443
{
    int rc;

    if(!old) {
        install_route(new);
        return;
    }

    if(!old->installed)
        return;

444 445 446 447
    if(!route_feasible(new))
        fprintf(stderr, "WARNING: switching to unfeasible route "
                "(this shouldn't happen).");

448
    rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
449
                      old->nexthop, old->neigh->ifp->ifindex,
450
                      metric_to_kernel(route_metric(old)),
451
                      new->nexthop, new->neigh->ifp->ifindex,
452
                      metric_to_kernel(route_metric(new)));
453 454 455
    if(rc < 0) {
        perror("kernel_route(MODIFY)");
        return;
456
    }
457 458 459

    old->installed = 0;
    new->installed = 1;
460 461
    move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
                                              NULL));
462 463
    local_notify_route(old, LOCAL_CHANGE);
    local_notify_route(new, LOCAL_CHANGE);
464 465
}

466
static void
467 468
change_route_metric(struct route *route,
                    unsigned refmetric, unsigned cost, unsigned add)
469
{
470
    int old, new;
471
    int newmetric = MIN(refmetric + cost + add, INFINITY);
472

473
    old = metric_to_kernel(route_metric(route));
474
    new = metric_to_kernel(newmetric);
475 476 477 478

    if(route->installed && old != new) {
        int rc;
        rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen,
479
                          route->nexthop, route->neigh->ifp->ifindex,
480
                          old,
481
                          route->nexthop, route->neigh->ifp->ifindex,
482 483 484 485 486 487 488
                          new);
        if(rc < 0) {
            perror("kernel_route(MODIFY metric)");
            return;
        }
    }

489
    route->refmetric = refmetric;
490 491
    route->cost = cost;
    route->add_metric = add;
492
    local_notify_route(route, LOCAL_CHANGE);
493 494
}

495 496 497
static void
retract_route(struct route *route)
{
498
    change_route_metric(route, INFINITY, INFINITY, 0);
499 500
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
501 502 503
int
route_feasible(struct route *route)
{
504
    return update_feasible(route->src, route->seqno, route->refmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
505 506
}

507 508 509 510 511 512 513 514 515 516 517 518
int
route_old(struct route *route)
{
    return route->time < now.tv_sec - route->hold_time * 7 / 8;
}

int
route_expired(struct route *route)
{
    return route->time < now.tv_sec - route->hold_time;
}

519
static int
520
channels_interfere(int ch1, int ch2)
521
{
522
    if(ch1 == IF_CHANNEL_NONINTERFERING || ch2 == IF_CHANNEL_NONINTERFERING)
523
        return 0;
524
    if(ch1 == IF_CHANNEL_INTERFERING || ch2 == IF_CHANNEL_INTERFERING)
525 526 527 528
        return 1;
    return ch1 == ch2;
}

529
int
530
route_interferes(struct route *route, struct interface *ifp)
531
{
532 533 534 535
    switch(diversity_kind) {
    case DIVERSITY_NONE:
        return 1;
    case DIVERSITY_INTERFACE_1:
536
        return route->neigh->ifp == ifp;
537
    case DIVERSITY_CHANNEL_1:
538
    case DIVERSITY_CHANNEL:
539
        if(route->neigh->ifp == ifp)
540
            return 1;
541
        if(channels_interfere(ifp->channel, route->neigh->ifp->channel))
542
            return 1;
543 544 545 546 547
        if(diversity_kind == DIVERSITY_CHANNEL) {
            int i;
            for(i = 0; i < DIVERSITY_HOPS; i++) {
                if(route->channels[i] == 0)
                    break;
548
                if(channels_interfere(ifp->channel, route->channels[i]))
549 550 551 552
                    return 1;
            }
        }
        return 0;
553 554 555 556
    default:
        fprintf(stderr, "Unknown kind of diversity.\n");
        return 1;
    }
557 558
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
559
int
560
update_feasible(struct source *src,
561
                unsigned short seqno, unsigned short refmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
562
{
563 564 565
    if(src == NULL)
        return 1;

566
    if(src->time < now.tv_sec - SOURCE_GC_TIME)
567 568 569
        /* Never mind what is probably stale data */
        return 1;

570 571 572 573 574 575
    if(refmetric >= INFINITY)
        /* Retractions are always feasible */
        return 1;

    return (seqno_compare(seqno, src->seqno) > 0 ||
            (src->seqno == seqno && refmetric < src->metric));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
576 577
}

578
/* This returns the feasible route with the smallest metric. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
579
struct route *
580 581
find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
                struct neighbour *exclude)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
582
{
583 584 585 586 587 588 589
    struct route *route, *r;
    int i = find_route_slot(prefix, plen, NULL);

    if(i < 0)
        return NULL;

    route = routes[i];
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
590

591 592 593 594 595 596 597 598
    r = route->next;
    while(r) {
        if(!route_expired(r) &&
           (!feasible || route_feasible(r)) &&
           (!exclude || r->neigh != exclude) &&
           (route_metric(r) < route_metric(route)))
            route = r;
        r = r->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
599 600 601 602 603 604 605
    }
    return route;
}

void
update_route_metric(struct route *route)
{
606
    int oldmetric = route_metric(route);
607

608
    if(route_expired(route)) {
609
        if(route->refmetric < INFINITY) {
610
            route->seqno = seqno_plus(route->src->seqno, 1);
611 612 613
            retract_route(route);
            if(oldmetric < INFINITY)
                route_changed(route, route->src, oldmetric);
614
        }
615
    } else {
616 617 618 619
        struct neighbour *neigh = route->neigh;
        int add_metric = input_filter(route->src->id,
                                      route->src->prefix, route->src->plen,
                                      neigh->address,
620
                                      neigh->ifp->ifindex);
621
        change_route_metric(route, route->refmetric,
622 623
                            neighbour_cost(route->neigh), add_metric);
        if(route_metric(route) != oldmetric)
624
            route_changed(route, route->src, oldmetric);
625
    }
626
}
627

628 629
/* Called whenever a neighbour's cost changes, to update the metric of
   all routes through that neighbour.  Calls local_notify_neighbour. */
630
void
631
update_neighbour_metric(struct neighbour *neigh, int changed)
632 633
{

634 635 636
    if(changed) {
        int i;

637 638 639 640 641 642 643
        for(i = 0; i < route_slots; i++) {
            struct route *r = routes[i];
            while(r) {
                if(r->neigh == neigh)
                    update_route_metric(r);
                r = r->next;
            }
644
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
645
    }
646

647
    local_notify_neighbour(neigh, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
648 649
}

650
void
651
update_interface_metric(struct interface *ifp)
652 653 654 655
{
    int i;

    i = 0;
656 657 658 659 660 661 662
    for(i = 0; i < route_slots; i++) {
        struct route *r = routes[i];
        while(r) {
            if(r->neigh->ifp == ifp)
                update_route_metric(r);
            r = r->next;
        }
663 664 665
    }
}

666
/* This is called whenever we receive an update. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
667
struct route *
668 669
update_route(const unsigned char *a, const unsigned char *p, unsigned char plen,
             unsigned short seqno, unsigned short refmetric,
670
             unsigned short interval,
671 672
             struct neighbour *neigh, const unsigned char *nexthop,
             const unsigned char *channels, int channels_len)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
673 674
{
    struct route *route;
675 676
    struct source *src;
    int metric, feasible;
677
    int add_metric;
678 679 680 681
    int hold_time = MAX((4 * interval) / 100 + interval / 50, 15);

    if(memcmp(a, myid, 8) == 0)
        return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
682

683 684 685
    if(martian_prefix(p, plen)) {
        fprintf(stderr, "Rejecting martian route to %s through %s.\n",
                format_prefix(p, plen), format_address(a));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
686 687 688
        return NULL;
    }

689
    add_metric = input_filter(a, p, plen,
690
                              neigh->address, neigh->ifp->ifindex);
691
    if(add_metric >= INFINITY)
692 693
        return NULL;

694 695
    src = find_source(a, p, plen, 1, seqno);
    if(src == NULL)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
696 697
        return NULL;

698
    feasible = update_feasible(src, seqno, refmetric);
699
    route = find_route(p, plen, neigh, nexthop);
700
    metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
701
    if(route) {
702 703 704
        struct source *oldsrc;
        unsigned short oldmetric;
        int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
705

706
        oldsrc = route->src;
707
        oldmetric = route_metric(route);
708 709

        /* If a successor switches sources, we must accept his update even
710 711
           if it makes a route unfeasible in order to break any routing loops
           in a timely manner.  If the source remains the same, we ignore
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
712
           the update. */
713 714 715 716
        if(!feasible && route->installed) {
            debugf("Unfeasible update for installed route to %s "
                   "(%s %d %d -> %s %d %d).\n",
                   format_prefix(src->prefix, src->plen),
717
                   format_address(route->src->id),
718
                   route->seqno, route->refmetric,
719
                   format_address(src->id), seqno, refmetric);
720 721 722
            if(src != route->src) {
                uninstall_route(route);
                lost = 1;
723
            }
724 725 726
        }

        route->src = src;
727
        if((feasible || keep_unfeasible) && refmetric < INFINITY)
728
            route->time = now.tv_sec;
729
        route->seqno = seqno;
730 731
        change_route_metric(route,
                            refmetric, neighbour_cost(neigh), add_metric);
732
        route->hold_time = hold_time;
733

734
        route_changed(route, oldsrc, oldmetric);
735 736
        if(lost)
            route_lost(oldsrc, oldmetric);
737 738 739

        if(!feasible)
            send_unfeasible_request(neigh, route->installed && route_old(route),
740
                                    seqno, metric, src);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
741
    } else {
742 743
        struct route *new_route;

744 745 746
        if(refmetric >= INFINITY)
            /* Somebody's retracting a route we never saw. */
            return NULL;
747
        if(!feasible) {
748
            send_unfeasible_request(neigh, 0, seqno, metric, src);
749 750
            if(!keep_unfeasible)
                return NULL;
751
        }
752

753 754 755 756
        route = malloc(sizeof(struct route));
        if(route == NULL) {
            perror("malloc(route)");
            return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
757
        }
758

759
        route->src = src;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
760
        route->refmetric = refmetric;
761 762
        route->cost = neighbour_cost(neigh);
        route->add_metric = add_metric;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
763
        route->seqno = seqno;
764
        route->neigh = neigh;
765
        memcpy(route->nexthop, nexthop, 16);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
766
        route->time = now.tv_sec;
767
        route->hold_time = hold_time;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
768
        route->installed = 0;
769
        memset(&route->channels, 0, sizeof(route->channels));
770 771 772
        if(channels_len > 0)
            memcpy(&route->channels, channels,
                   MIN(channels_len, DIVERSITY_HOPS));
773 774 775 776 777 778 779
        route->next = NULL;
        new_route = insert_route(route);
        if(new_route == NULL) {
            fprintf(stderr, "Couldn't insert route.\n");
            free(route);
            return NULL;
        }
780
        local_notify_route(route, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
781 782 783 784 785
        consider_route(route);
    }
    return route;
}

786 787 788
/* We just received an unfeasible update.  If it's any good, send
   a request for a new seqno. */
void
789
send_unfeasible_request(struct neighbour *neigh, int force,
790
                        unsigned short seqno, unsigned short metric,
791
                        struct source *src)
792
{
793
    struct route *route = find_installed_route(src->prefix, src->plen);
794

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
795
    if(seqno_minus(src->seqno, seqno) > 100) {
796 797 798 799
        /* Probably a source that lost its seqno.  Let it time-out. */
        return;
    }

800
    if(force || !route || route_metric(route) >= metric + 512) {
801
        send_unicast_multihop_request(neigh, src->prefix, src->plen,
802 803 804 805
                                      src->metric >= INFINITY ?
                                      src->seqno :
                                      seqno_plus(src->seqno, 1),
                                      src->id, 127);
806 807 808
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
809 810
/* This takes a feasible route and decides whether to install it. */

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
811 812 813 814
void
consider_route(struct route *route)
{
    struct route *installed;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
815
    struct xroute *xroute;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
816 817 818 819

    if(route->installed)
        return;

820
    if(!route_feasible(route))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
821 822
        return;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
823 824 825
    xroute = find_xroute(route->src->prefix, route->src->plen);
    if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
        return;
826 827

    installed = find_installed_route(route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
828 829 830 831

    if(installed == NULL)
        goto install;

832
    if(route_metric(route) >= INFINITY)
833 834
        return;

835
    if(route_metric(installed) >= INFINITY)
836 837
        goto install;

838
    if(route_metric(installed) >= route_metric(route) + 64)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
839 840 841 842 843
        goto install;

    return;

 install:
844
    switch_routes(installed, route);
845
    if(installed && route->installed)
846
        send_triggered_update(route, installed->src, route_metric(installed));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
847
    else
848
        send_update(NULL, 1, route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
849 850 851
    return;
}

852 853 854 855 856
void
retract_neighbour_routes(struct neighbour *neigh)
{
    int i;

857 858 859 860 861 862 863
    for(i = 0; i < route_slots; i++) {
        struct route *r = routes[i];
        while(r) {
            if(r->neigh == neigh) {
                if(r->refmetric != INFINITY) {
                    unsigned short oldmetric = route_metric(r);
                    retract_route(r);
864
                    if(oldmetric != INFINITY)
865 866
                        route_changed(r, r->src, oldmetric);
                }
867
            }
868
            r = r->next;
869 870 871 872 873
        }
        i++;
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
874
void
875 876
send_triggered_update(struct route *route, struct source *oldsrc,
                      unsigned oldmetric)
877
{
878
    unsigned newmetric, diff;
879 880
    /* 1 means send speedily, 2 means resend */
    int urgent;
881

882 883 884
    if(!route->installed)
        return;

885
    newmetric = route_metric(route);
886 887
    diff =
        newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
888

889 890
    if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
        /* Switching sources can cause transient routing loops.
891
           Retractions can cause blackholes. */
892
        urgent = 2;
893 894
    else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
        /* Route getting significantly worse */
895
        urgent = 1;
896 897 898 899 900 901 902 903 904 905 906 907 908
    else if(unsatisfied_request(route->src->prefix, route->src->plen,
                                route->seqno, route->src->id))
        /* Make sure that requests are satisfied speedily */
        urgent = 1;
    else if(oldmetric >= INFINITY && newmetric < INFINITY)
        /* New route */
        urgent = 0;
    else if(newmetric < oldmetric && diff < 1024)
        /* Route getting better.  This may be a transient fluctuation, so
           don't advertise it to avoid making routes unfeasible later on. */
        return;
    else if(diff < 384)
        /* Don't fret about trivialities */
909
        return;
910 911
    else
        urgent = 0;
912

913 914 915 916
    if(urgent >= 2)
        send_update_resend(NULL, route->src->prefix, route->src->plen);
    else
        send_update(NULL, urgent, route->src->prefix, route->src->plen);
917 918

    if(oldmetric < INFINITY) {
919
        if(newmetric >= oldmetric + 512) {
920
            send_request_resend(NULL, route->src->prefix, route->src->plen,
921 922 923
                                route->src->metric >= INFINITY ?
                                route->src->seqno :
                                seqno_plus(route->src->seqno, 1),
924
                                route->src->id);
925
        } else if(newmetric >= oldmetric + 288) {
926
            send_request(NULL, route->src->prefix, route->src->plen);
927
        }
928 929 930 931 932 933
    }
}

/* A route has just changed.  Decide whether to switch to a different route or
   send an update. */
void
934 935
route_changed(struct route *route,
              struct source *oldsrc, unsigned short oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
936
{
937
    if(route->installed) {
938
        if(route_metric(route) > oldmetric) {
939 940
            struct route *better_route;
            better_route =
941
                find_best_route(route->src->prefix, route->src->plen, 1, NULL);
942 943
            if(better_route &&
               route_metric(better_route) <= route_metric(route) - 96)
944
                consider_route(better_route);
945
        }
946

947
        if(route->installed)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
948
            /* We didn't change routes after all. */
949
            send_triggered_update(route, oldsrc, oldmetric);
950
    } else {
951 952 953
        /* Reconsider routes even when their metric didn't decrease,
           they may not have been feasible before. */
        consider_route(route);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
954 955 956
    }
}

957
/* We just lost the installed route to a given destination. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
958
void
959
route_lost(struct source *src, unsigned oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
960
{
961
    struct route *new_route;
962
    new_route = find_best_route(src->prefix, src->plen, 1, NULL);
963 964
    if(new_route) {
        consider_route(new_route);
965
    } else if(oldmetric < INFINITY) {
966
        /* Complain loudly. */
967
        send_update_resend(NULL, src->prefix, src->plen);
968 969 970
        send_request_resend(NULL, src->prefix, src->plen,
                            src->metric >= INFINITY ?
                            src->seqno : seqno_plus(src->seqno, 1),
971
                            src->id);
972 973 974
    }
}

975 976
/* This is called periodically to flush old routes.  It will also send
   requests for routes that are about to expire. */
977 978 979
void
expire_routes(void)
{
980
    struct route *r;
981
    int i;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
982

983
    debugf("Expiring old routes.\n");
984

985 986
    i = 0;
    while(i < route_slots) {
987 988 989 990 991 992 993
        r = routes[i];
        while(r) {
            /* Protect against clock being stepped. */
            if(r->time > now.tv_sec || route_old(r)) {
                flush_route(r);
                goto again;
            }
994

995
            update_route_metric(r);
996

997 998 999 1000 1001 1002 1003
            if(r->installed && r->refmetric < INFINITY) {
                if(route_old(r))
                    /* Route about to expire, send a request. */
                    send_unicast_request(r->neigh,
                                         r->src->prefix, r->src->plen);
            }
            r = r->next;
1004
        }
1005 1006 1007
        i++;
    again:
        ;
1008
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1009
}