route.c 35.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"
42
#include "disambiguation.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
43

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

51 52 53
static int smoothing_half_life = 0;
static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */

54 55 56 57 58 59 60
static int
check_specific_first(void)
{
    /* All source-specific routes are in front of the list */
    int specific = 1;
    int i;
    for(i = 0; i < route_slots; i++) {
61
        if(is_default(routes[i]->src->src_prefix, routes[i]->src->src_plen)) {
62 63 64 65 66 67 68 69
            specific = 0;
        } else if(!specific) {
            return 0;
        }
    }
    return 1;
}

70 71 72 73 74 75
/* 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,
76
              const unsigned char *src_prefix, unsigned char src_plen,
77
              struct babel_route *route)
78
{
79
    int i;
80 81
    int is_ss = !is_default(src_prefix, src_plen);
    int is_ss_rt = !is_default(route->src->src_prefix, route->src->src_plen);
82 83

    /* Put all source-specific routes in the front of the list. */
84
    if(!is_ss && is_ss_rt) {
85
        return 1;
86
    } else if(is_ss && !is_ss_rt) {
87 88 89 90
        return -1;
    }

    i = memcmp(prefix, route->src->prefix, 16);
91 92 93 94 95
    if(i != 0)
        return i;

    if(plen < route->src->plen)
        return -1;
96
    if(plen > route->src->plen)
97
        return 1;
98

99
    if(is_ss) {
100 101 102 103 104 105 106 107 108 109
        i = memcmp(src_prefix, route->src->src_prefix, 16);
        if(i != 0)
            return i;
        if(src_plen < route->src->src_plen)
            return -1;
        if(src_plen > route->src->src_plen)
            return 1;
    }

    return 0;
110 111 112 113 114 115 116
}

/* 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,
117
                const unsigned char *src_prefix, unsigned char src_plen,
118 119 120 121 122 123 124 125 126 127 128 129 130 131
                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;
132
        c = route_compare(prefix, plen, src_prefix, src_plen, routes[m]);
133 134 135 136 137 138 139 140 141 142 143 144 145 146
        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;
}

147
struct babel_route *
148
find_route(const unsigned char *prefix, unsigned char plen,
149
           const unsigned char *src_prefix, unsigned char src_plen,
150
           struct neighbour *neigh, const unsigned char *nexthop)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
151
{
152
    struct babel_route *route;
153
    int i = find_route_slot(prefix, plen, src_prefix, src_plen, NULL);
154 155 156 157 158 159 160 161 162 163

    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
164
    }
165

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
166 167 168
    return NULL;
}

169
struct babel_route *
170 171
find_installed_route(const unsigned char *prefix, unsigned char plen,
                     const unsigned char *src_prefix, unsigned char src_plen)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
172
{
173
    int i = find_route_slot(prefix, plen, src_prefix, src_plen, NULL);
174 175 176 177

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

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
178 179 180
    return NULL;
}

181 182 183 184 185 186 187
/* Returns an overestimate of the number of installed routes. */
int
installed_routes_estimate(void)
{
    return route_slots;
}

188 189 190
static int
resize_route_table(int new_slots)
{
191
    struct babel_route **new_routes;
192 193 194 195 196 197
    assert(new_slots >= route_slots);

    if(new_slots == 0) {
        new_routes = NULL;
        free(routes);
    } else {
198
        new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
199 200 201 202 203 204 205 206 207 208 209
        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. */
210 211
static struct babel_route *
insert_route(struct babel_route *route)
212 213 214 215 216
{
    int i, n;

    assert(!route->installed);

217 218
    i = find_route_slot(route->src->prefix, route->src->plen,
                        route->src->src_prefix, route->src->src_plen, &n);
219 220 221 222 223 224 225 226 227

    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,
228
                    (route_slots - n) * sizeof(struct babel_route*));
229 230 231
        route_slots++;
        routes[n] = route;
    } else {
232
        struct babel_route *r;
233 234 235 236 237 238 239 240 241 242
        r = routes[i];
        while(r->next)
            r = r->next;
        r->next = route;
        route->next = NULL;
    }

    return route;
}

243 244 245 246 247 248 249
static void
destroy_route(struct babel_route *route)
{
    free(route->channels);
    free(route);
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
250
void
251
flush_route(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
252
{
253
    int i;
254
    struct source *src;
255 256
    unsigned oldmetric;
    int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
257

258
    oldmetric = route_metric(route);
259
    src = route->src;
260

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
261 262
    if(route->installed) {
        uninstall_route(route);
263
        lost = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
264 265
    }

266 267
    i = find_route_slot(route->src->prefix, route->src->plen,
                        route->src->src_prefix, route->src->src_plen, NULL);
268
    assert(i >= 0 && i < route_slots);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
269

270
    local_notify_route(route, LOCAL_FLUSH);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
271

272 273 274
    if(route == routes[i]) {
        routes[i] = route->next;
        route->next = NULL;
275
        destroy_route(route);
276 277 278

        if(routes[i] == NULL) {
            if(i < route_slots - 1)
279
                memmove(routes + i, routes + i + 1,
280
                        (route_slots - i - 1) * sizeof(struct babel_route*));
281 282
            routes[route_slots - 1] = NULL;
            route_slots--;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
283
            VALGRIND_MAKE_MEM_UNDEFINED(routes + route_slots, sizeof(struct route *));
284
        }
285 286 287 288 289 290

        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 {
291
        struct babel_route *r = routes[i];
292 293 294 295
        while(r->next != route)
            r = r->next;
        r->next = route->next;
        route->next = NULL;
296
        destroy_route(route);
297 298
    }

299 300
    if(lost)
        route_lost(src, oldmetric);
301 302

    release_source(src);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
303 304
}

305 306 307
void
flush_all_routes()
{
308 309
    int i;

310
    /* Start from the end, to avoid shifting the table. */
311
    i = route_slots - 1;
312 313
    while(i >= 0) {
        while(i < route_slots) {
314
            /* Uninstall first, to avoid calling route_lost. */
315
            if(routes[i]->installed)
316
                uninstall_route(routes[i]);
317 318 319 320
            flush_route(routes[i]);
        }
        i--;
    }
321 322

    check_sources_released();
323 324
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
325 326 327 328 329
void
flush_neighbour_routes(struct neighbour *neigh)
{
    int i;

330 331
    i = 0;
    while(i < route_slots) {
332
        struct babel_route *r;
333 334 335 336 337 338 339
        r = routes[i];
        while(r) {
            if(r->neigh == neigh) {
                flush_route(r);
                goto again;
            }
            r = r->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
340
        }
341 342 343
        i++;
    again:
        ;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
344 345 346
    }
}

347
void
348
flush_interface_routes(struct interface *ifp, int v4only)
349 350 351
{
    int i;

352 353
    i = 0;
    while(i < route_slots) {
354
        struct babel_route *r;
355 356 357 358 359 360 361 362 363
        r = routes[i];
        while(r) {
            if(r->neigh->ifp == ifp &&
               (!v4only || v4mapped(r->nexthop))) {
                flush_route(r);
                goto again;
            }
            r = r->next;
        }
364 365 366
        i++;
    again:
        ;
367 368 369
    }
}

370 371 372 373 374 375 376 377
struct route_stream {
    int installed;
    int index;
    struct babel_route *next;
};


struct route_stream *
378
route_stream(int which)
379
{
380
    struct route_stream *stream;
381

382 383 384
    if(!check_specific_first())
        fprintf(stderr, "Invariant failed: specific routes first in RIB.\n");

385
    stream = calloc(1, sizeof(struct route_stream));
386
    if(stream == NULL)
Matthieu Boutier's avatar
Matthieu Boutier committed
387
        return NULL;
388

389 390
    stream->installed = which;
    stream->index = which == ROUTE_ALL ? -1 : 0;
391 392 393 394 395 396 397 398 399
    stream->next = NULL;

    return stream;
}

struct babel_route *
route_stream_next(struct route_stream *stream)
{
    if(stream->installed) {
400 401
        while(stream->index < route_slots)
            if(stream->installed == ROUTE_SS_INSTALLED &&
402 403
               is_default(routes[stream->index]->src->src_prefix,
                          routes[stream->index]->src->src_plen))
404 405 406 407 408
                return NULL;
            else if(routes[stream->index]->installed)
                break;
            else
                stream->index++;
409 410 411 412 413 414 415 416 417 418 419 420

        if(stream->index < route_slots)
            return routes[stream->index++];
        else
            return NULL;
    } else {
        struct babel_route *next;
        if(!stream->next) {
            stream->index++;
            if(stream->index >= route_slots)
                return NULL;
            stream->next = routes[stream->index];
421
        }
422 423 424
        next = stream->next;
        stream->next = next->next;
        return next;
425 426 427 428
    }
}

void
429
route_stream_done(struct route_stream *stream)
430
{
431
    free(stream);
432 433
}

434
int
435 436
metric_to_kernel(int metric)
{
Dave Taht's avatar
Dave Taht committed
437 438 439 440 441 442 443 444
        if(metric >= INFINITY) {
                return KERNEL_INFINITY;
        } else if(reflect_kernel_metric) {
                int r = kernel_metric + metric;
                return r >= KERNEL_INFINITY ? KERNEL_INFINITY : r;
        } else {
                return kernel_metric;
        }
445
}
446

447 448 449
/* This is used to maintain the invariant that the installed route is at
   the head of the list. */
static void
450
move_installed_route(struct babel_route *route, int i)
451 452 453 454 455
{
    assert(i >= 0 && i < route_slots);
    assert(route->installed);

    if(route != routes[i]) {
456
        struct babel_route *r = routes[i];
457 458 459 460 461 462 463 464
        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
465
void
466
install_route(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
467
{
468
    int i, rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
469 470 471 472

    if(route->installed)
        return;

473 474 475 476
    if(!route_feasible(route))
        fprintf(stderr, "WARNING: installing unfeasible route "
                "(this shouldn't happen).");

477 478
    i = find_route_slot(route->src->prefix, route->src->plen,
                        route->src->src_prefix, route->src->src_plen, NULL);
479 480 481 482 483 484 485 486
    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;
    }

487 488 489 490
    rc = kinstall_route(route);
    if(rc < 0 && errno != EEXIST)
        return;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
491
    route->installed = 1;
492 493
    move_installed_route(route, i);

494
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
495 496 497
}

void
498
uninstall_route(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
499 500 501 502 503
{
    if(!route->installed)
        return;

    route->installed = 0;
504 505 506

    kuninstall_route(route);

507
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
508 509
}

510 511 512 513
/* This is equivalent to uninstall_route followed with install_route,
   but without the race condition.  The destination of both routes
   must be the same. */

514
static void
515
switch_routes(struct babel_route *old, struct babel_route *new)
516 517 518 519 520 521 522 523 524 525 526
{
    int rc;

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

    if(!old->installed)
        return;

527 528 529 530
    if(!route_feasible(new))
        fprintf(stderr, "WARNING: switching to unfeasible route "
                "(this shouldn't happen).");

531 532
    rc = kswitch_routes(old, new);
    if(rc < 0)
533 534 535 536
        return;

    old->installed = 0;
    new->installed = 1;
537
    move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
538 539
                                              new->src->src_prefix,
                                              new->src->src_plen,
540
                                              NULL));
541 542
    local_notify_route(old, LOCAL_CHANGE);
    local_notify_route(new, LOCAL_CHANGE);
543 544
}

545
static void
546
change_route_metric(struct babel_route *route,
547
                    unsigned refmetric, unsigned cost, unsigned add)
548
{
549
    int old, new;
550
    int newmetric = MIN(refmetric + cost + add, INFINITY);
551

552
    old = metric_to_kernel(route_metric(route));
553
    new = metric_to_kernel(newmetric);
554 555 556

    if(route->installed && old != new) {
        int rc;
557 558
        rc = kchange_route_metric(route, refmetric, cost, add);
        if(rc < 0)
559 560 561
            return;
    }

562 563 564
    /* Update route->smoothed_metric using the old metric. */
    route_smoothed_metric(route);

565
    route->refmetric = refmetric;
566 567
    route->cost = cost;
    route->add_metric = add;
568 569 570 571 572 573

    if(smoothing_half_life == 0) {
        route->smoothed_metric = route_metric(route);
        route->smoothed_metric_time = now.tv_sec;
    }

574
    local_notify_route(route, LOCAL_CHANGE);
575 576
}

577
static void
578
retract_route(struct babel_route *route)
579
{
580 581
    /* We cannot simply remove the route from the kernel, as that might
       cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
582
    change_route_metric(route, INFINITY, INFINITY, 0);
583 584
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
585
int
586
route_feasible(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
587
{
588
    return update_feasible(route->src, route->seqno, route->refmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
589 590
}

591
int
592
route_old(struct babel_route *route)
593 594 595 596 597
{
    return route->time < now.tv_sec - route->hold_time * 7 / 8;
}

int
598
route_expired(struct babel_route *route)
599 600 601 602
{
    return route->time < now.tv_sec - route->hold_time;
}

603
static int
604
channels_interfere(int ch1, int ch2)
605
{
606
    if(ch1 == IF_CHANNEL_NONINTERFERING || ch2 == IF_CHANNEL_NONINTERFERING)
607
        return 0;
608
    if(ch1 == IF_CHANNEL_INTERFERING || ch2 == IF_CHANNEL_INTERFERING)
609 610 611 612
        return 1;
    return ch1 == ch2;
}

613
int
614
route_interferes(struct babel_route *route, struct interface *ifp)
615
{
616 617 618 619
    switch(diversity_kind) {
    case DIVERSITY_NONE:
        return 1;
    case DIVERSITY_INTERFACE_1:
620
        return route->neigh->ifp == ifp;
621
    case DIVERSITY_CHANNEL_1:
622
    case DIVERSITY_CHANNEL:
623
        if(route->neigh->ifp == ifp)
624
            return 1;
625
        if(channels_interfere(ifp->channel, route->neigh->ifp->channel))
626
            return 1;
627 628
        if(diversity_kind == DIVERSITY_CHANNEL) {
            int i;
629 630 631
            for(i = 0; i < route->channels_len; i++) {
                if(route->channels[i] != 0 &&
                   channels_interfere(ifp->channel, route->channels[i]))
632 633 634 635
                    return 1;
            }
        }
        return 0;
636 637 638 639
    default:
        fprintf(stderr, "Unknown kind of diversity.\n");
        return 1;
    }
640 641
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
642
int
643
update_feasible(struct source *src,
644
                unsigned short seqno, unsigned short refmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
645
{
646 647 648
    if(src == NULL)
        return 1;

649
    if(src->time < now.tv_sec - SOURCE_GC_TIME)
650 651 652
        /* Never mind what is probably stale data */
        return 1;

653 654 655 656 657 658
    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
659 660
}

661 662 663 664 665 666 667 668 669 670 671 672 673 674
void
change_smoothing_half_life(int half_life)
{
    if(half_life <= 0) {
        smoothing_half_life = 0;
        two_to_the_one_over_hl = 0;
        return;
    }

    smoothing_half_life = half_life;
    switch(smoothing_half_life) {
    case 1: two_to_the_one_over_hl = 131072; break;
    case 2: two_to_the_one_over_hl = 92682; break;
    case 3: two_to_the_one_over_hl = 82570; break;
675
    case 4: two_to_the_one_over_hl = 77935; break;
676
    default:
677
        /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
678 679 680 681 682 683 684 685 686 687
        two_to_the_one_over_hl = 0x10000 + 45426 / half_life;
    }
}

/* Update the smoothed metric, return the new value. */
int
route_smoothed_metric(struct babel_route *route)
{
    int metric = route_metric(route);

688 689 690 691
    if(smoothing_half_life <= 0 ||                 /* no smoothing */
       metric >= INFINITY ||                       /* route retracted */
       route->smoothed_metric_time > now.tv_sec || /* clock stepped */
       route->smoothed_metric == metric) {         /* already converged */
692 693 694 695 696 697 698 699 700 701 702 703 704 705
        route->smoothed_metric = metric;
        route->smoothed_metric_time = now.tv_sec;
    } else {
        int diff;
        /* We randomise the computation, to minimise global synchronisation
           and hence oscillations. */
        while(route->smoothed_metric_time <= now.tv_sec - smoothing_half_life) {
            diff = metric - route->smoothed_metric;
            route->smoothed_metric += roughly(diff) / 2;
            route->smoothed_metric_time += smoothing_half_life;
        }
        while(route->smoothed_metric_time < now.tv_sec) {
            diff = metric - route->smoothed_metric;
            route->smoothed_metric +=
706
                roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000;
707 708 709 710 711 712 713 714 715 716 717 718 719
            route->smoothed_metric_time++;
        }

        diff = metric - route->smoothed_metric;
        if(diff > -4 && diff < 4)
            route->smoothed_metric = metric;
    }

    /* change_route_metric relies on this */
    assert(route->smoothed_metric_time == now.tv_sec);
    return route->smoothed_metric;
}

720 721 722 723 724 725 726 727 728 729 730 731 732
static int
route_acceptable(struct babel_route *route, int feasible,
                 struct neighbour *exclude)
{
    if(route_expired(route))
        return 0;
    if(feasible && !route_feasible(route))
        return 0;
    if(exclude && route->neigh == exclude)
        return 0;
    return 1;
}

733 734 735 736 737
/* Find the best route according to the weak ordering.  Any
   linearisation of the strong ordering (see consider_route) will do,
   we use sm <= sm'.  We could probably use a lexical ordering, but
   that's probably overkill. */

738
struct babel_route *
739 740 741
find_best_route(const unsigned char *prefix, unsigned char plen,
                const unsigned char *src_prefix, unsigned char src_plen,
                int feasible, struct neighbour *exclude)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
742
{
743
    struct babel_route *route, *r;
744
    int i = find_route_slot(prefix, plen, src_prefix, src_plen, NULL);
745 746 747 748 749

    if(i < 0)
        return NULL;

    route = routes[i];
750 751 752 753 754
    while(route && !route_acceptable(route, feasible, exclude))
        route = route->next;

    if(!route)
        return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
755

756 757
    r = route->next;
    while(r) {
758
        if(route_acceptable(r, feasible, exclude) &&
759
           (route_smoothed_metric(r) < route_smoothed_metric(route)))
760 761
            route = r;
        r = r->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
762
    }
763

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
764 765 766 767
    return route;
}

void
768
update_route_metric(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
769
{
770
    int oldmetric = route_metric(route);
771
    int old_smoothed_metric = route_smoothed_metric(route);
772

773
    if(route_expired(route)) {
774
        if(route->refmetric < INFINITY) {
775
            route->seqno = seqno_plus(route->src->seqno, 1);
776 777 778
            retract_route(route);
            if(oldmetric < INFINITY)
                route_changed(route, route->src, oldmetric);
779
        }
780
    } else {
781 782 783
        struct neighbour *neigh = route->neigh;
        int add_metric = input_filter(route->src->id,
                                      route->src->prefix, route->src->plen,
784 785
                                      route->src->src_prefix,
                                      route->src->src_plen,
786
                                      neigh->address,
787
                                      neigh->ifp->ifindex);
788
        change_route_metric(route, route->refmetric,
789
                            neighbour_cost(route->neigh), add_metric);
790 791
        if(route_metric(route) != oldmetric ||
           route_smoothed_metric(route) != old_smoothed_metric)
792
            route_changed(route, route->src, oldmetric);
793
    }
794
}
795

796 797
/* Called whenever a neighbour's cost changes, to update the metric of
   all routes through that neighbour.  Calls local_notify_neighbour. */
798
void
799
update_neighbour_metric(struct neighbour *neigh, int changed)
800 801
{

802 803 804
    if(changed) {
        int i;

805
        for(i = 0; i < route_slots; i++) {
806
            struct babel_route *r = routes[i];
807 808 809 810 811
            while(r) {
                if(r->neigh == neigh)
                    update_route_metric(r);
                r = r->next;
            }
812
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
813
    }
814

815
    local_notify_neighbour(neigh, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
816 817
}

818
void
819
update_interface_metric(struct interface *ifp)
820 821 822
{
    int i;

823
    for(i = 0; i < route_slots; i++) {
824
        struct babel_route *r = routes[i];
825 826 827 828 829
        while(r) {
            if(r->neigh->ifp == ifp)
                update_route_metric(r);
            r = r->next;
        }
830 831 832
    }
}

833
/* This is called whenever we receive an update. */
834
struct babel_route *
835 836
update_route(const unsigned char *id,
             const unsigned char *prefix, unsigned char plen,
837
             const unsigned char *src_prefix, unsigned char src_plen,
838
             unsigned short seqno, unsigned short refmetric,
839
             unsigned short interval,
840 841
             struct neighbour *neigh, const unsigned char *nexthop,
             const unsigned char *channels, int channels_len)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
842
{
843
    struct babel_route *route;
844 845
    struct source *src;
    int metric, feasible;
846
    int add_metric;
847
    int hold_time = MAX((4 * interval) / 100 + interval / 50, 15);
848
    int is_v4;
849
    if(memcmp(id, myid, 8) == 0)
850
        return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
851

852
    if(martian_prefix(prefix, plen) || martian_prefix(src_prefix, src_plen)) {
853 854
        fprintf(stderr, "Rejecting martian route to %s from %s through %s.\n",
                format_prefix(prefix, plen),
855
                format_prefix(src_prefix, src_plen), format_address(nexthop));
856 857 858 859
        return NULL;
    }

    is_v4 = v4mapped(prefix);
860
    if(is_v4 != v4mapped(src_prefix))
861 862
        return NULL;

863
    add_metric = input_filter(id, prefix, plen, src_prefix, src_plen,
864
                              neigh->address, neigh->ifp->ifindex);
865
    if(add_metric >= INFINITY)
866 867
        return NULL;

868
    route = find_route(prefix, plen, src_prefix, src_plen, neigh, nexthop);
869 870 871 872 873

    if(route && memcmp(route->src->id, id, 8) == 0)
        /* Avoid scanning the source table. */
        src = route->src;
    else
874
        src = find_source(id, prefix, plen, src_prefix, src_plen, 1, seqno);
875

876
    if(src == NULL)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
877 878
        return NULL;

879
    feasible = update_feasible(src, seqno, refmetric);
880
    metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
881

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
882
    if(route) {
883
        struct source *oldsrc;
884
        unsigned short oldmetric, oldinstalled;
885
        int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
886

887
        oldinstalled = route->installed;
888
        oldsrc = route->src;
889
        oldmetric = route_metric(route);
890 891

        /* If a successor switches sources, we must accept his update even
892 893
           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
894
           the update. */
895 896 897 898
        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),
899
                   format_eui64(route->src->id),
900
                   route->seqno, route->refmetric,
901
                   format_eui64(src->id), seqno, refmetric);
902 903 904
            if(src != route->src) {
                uninstall_route(route);
                lost = 1;
905
            }
906 907
        }

908
        route->src = retain_source(src);
909
        if(refmetric < INFINITY)
910
            route->time = now.tv_sec;
911
        route->seqno = seqno;
912

913 914
        if(channels_len == 0) {
            free(route->channels);
915
            route->channels = NULL;
916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
            route->channels_len = 0;
        } else {
            if(channels_len != route->channels_len) {
                unsigned char *new_channels =
                    realloc(route->channels, channels_len);
                if(new_channels == NULL) {
                    perror("malloc(channels)");
                    /* Truncate the data. */
                    channels_len = MIN(channels_len, route->channels_len);
                } else {
                    route->channels = new_channels;
                }
            }
            memcpy(route->channels, channels, channels_len);
            route->channels_len = channels_len;
        }
932

933 934
        change_route_metric(route,
                            refmetric, neighbour_cost(neigh), add_metric);
935
        route->hold_time = hold_time;
936

937
        route_changed(route, oldsrc, oldmetric);
938 939 940 941
        if(!lost) {
            lost = oldinstalled &&
                find_installed_route(prefix, plen, src_prefix, src_plen) == NULL;
        }
942 943
        if(lost)
            route_lost(oldsrc, oldmetric);
944 945
        else if(!feasible)
            send_unfeasible_request(neigh, route_old(route), seqno, metric, src);
946
        release_source(oldsrc);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
947
    } else {
948
        struct babel_route *new_route;
949

950 951 952
        if(refmetric >= INFINITY)
            /* Somebody's retracting a route we never saw. */
            return NULL;
953
        if(!feasible) {
954
            send_unfeasible_request(neigh, 0, seqno, metric, src);
955
        }
956

957
        route = calloc(1, sizeof(struct babel_route));
958 959 960
        if(route == NULL) {
            perror("malloc(route)");
            return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
961
        }
962

963
        route->src = retain_source(src);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
964
        route->refmetric = refmetric;
965 966
        route->cost = neighbour_cost(neigh);
        route->add_metric = add_metric;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
967
        route->seqno = seqno;
968
        route->neigh = neigh;
969
        memcpy(route->nexthop, nexthop, 16);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
970
        route->time = now.tv_sec;
971
        route->hold_time = hold_time;
972 973
        route->smoothed_metric = MAX(route_metric(route), INFINITY / 2);
        route->smoothed_metric_time = now.tv_sec;
974 975 976 977 978 979 980 981
        if(channels_len > 0) {
            route->channels = malloc(channels_len);
            if(route->channels == NULL) {
                perror("malloc(channels)");
            } else {
                memcpy(route->channels, channels, channels_len);
            }
        }
982 983 984 985
        route->next = NULL;
        new_route = insert_route(route);
        if(new_route == NULL) {
            fprintf(stderr, "Couldn't insert route.\n");
986
            destroy_route(route);
987 988
            return NULL;
        }
989
        local_notify_route(route, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
990 991 992 993 994
        consider_route(route);
    }
    return route;
}

995 996 997
/* We just received an unfeasible update.  If it's any good, send
   a request for a new seqno. */
void
998
send_unfeasible_request(struct neighbour *neigh, int force,
999
                        unsigned short seqno, unsigned short metric,
1000
                        struct source *src)
1001
{
1002 1003 1004
    struct babel_route *route = find_installed_route(src->prefix, src->plen,
                                                     src->src_prefix,
                                                     src->src_plen);
1005

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1006
    if(seqno_minus(src->seqno, seqno) > 100) {
1007 1008 1009 1010
        /* Probably a source that lost its seqno.  Let it time-out. */
        return;
    }

1011
    if(force || !route || route_metric(route) >= metric + 512) {
1012
        send_unicast_multihop_request(neigh, src->prefix, src->plen,
1013
                                      src->src_prefix, src->src_plen,
1014 1015 1016 1017
                                      src->metric >= INFINITY ?
                                      src->seqno :
                                      seqno_plus(src->seqno, 1),
                                      src->id, 127);
1018 1019 1020
    }
}

1021 1022 1023 1024
/* This takes a feasible route and decides whether to install it.
   This uses the strong ordering, which is defined by sm <= sm' AND
   m <= m'.  This ordering is not total, which is what causes
   hysteresis. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1025

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1026
void
1027
consider_route(struct babel_route *route)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1028
{
1029
    struct babel_route *installed;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1030
    struct xroute *xroute;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1031 1032 1033 1034

    if(route->installed)
        return;

1035
    if(!route_feasible(route))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1036 1037
        return;

1038 1039
    xroute = find_xroute(route->src->prefix, route->src->plen,
                         route->src->src_prefix, route->src->src_plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1040 1041
    if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
        return;
1042

1043 1044 1045
    installed = find_installed_route(route->src->prefix, route->src->plen,
                                     route->src->src_prefix,
                                     route->src->src_plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1046 1047 1048 1049

    if(installed == NULL)
        goto install;

1050
    if(route_metric(route) >= INFINITY)
1051 1052
        return;

1053
    if(route_metric(installed) >= INFINITY)
1054 1055
        goto install;

1056 1057
    if(route_metric(installed) >= route_metric(route) &&
       route_smoothed_metric(installed) > route_smoothed_metric(route))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1058 1059 1060 1061 1062
        goto install;

    return;

 install:
1063
    switch_routes(installed, route);
1064
    if(installed && route->installed)
1065
        send_triggered_update(route, installed->src, route_metric(installed));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1066
    else
1067 1068
        send_update(NULL, 1, route->src->prefix, route->src->plen,
                    route->src->src_prefix, route->src->src_plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1069 1070 1071
    return;
}

1072 1073 1074 1075 1076
void
retract_neighbour_routes(struct neighbour *neigh)
{
    int i;

1077
    for(i = 0; i < route_slots; i++) {
1078
        struct babel_route *r = routes[i];
1079 1080 1081 1082 1083
        while(r) {
            if(r->neigh == neigh) {
                if(r->refmetric != INFINITY) {
                    unsigned short oldmetric = route_metric(r);
                    retract_route(r);
1084
                    if(oldmetric != INFINITY)
1085 1086
                        route_changed(r, r->src, oldmetric);
                }
1087
            }
1088
            r = r->next;
1089 1090 1091 1092
        }
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1093
void
1094
send_triggered_update(struct babel_route *route, struct source *oldsrc,
1095
                      unsigned oldmetric)
1096
{
1097
    unsigned newmetric, diff;
1098 1099
    /* 1 means send speedily, 2 means resend */
    int urgent;
1100

1101 1102 1103
    if(!route->installed)
        return;

1104
    newmetric = route_metric(route);
1105 1106
    diff =
        newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
1107

1108 1109
    if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
        /* Switching sources can cause transient routing loops.
1110
           Retractions can cause blackholes. */
1111
        urgent = 2;
1112 1113
    else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
        /* Route getting significantly worse */
1114
        urgent = 1;
1115
    else if(unsatisfied_request(route->src->prefix, route->src->plen,
1116
                                route->src->src_prefix, route->src->src_plen,
1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
                                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 */
1129
        return;
1130 1131
    else
        urgent = 0;
1132

1133
    if(urgent >= 2)
1134 1135
        send_update_resend(NULL, route->src->prefix, route->src->plen,
                           route->src->src_prefix, route->src->src_plen);
1136
    else
1137 1138
        send_update(NULL, urgent, route->src->prefix, route->src->plen,
                    route->src->src_prefix, route->src->src_plen);
1139 1140

    if(oldmetric < INFINITY) {
1141
        if(newmetric >= oldmetric + 288) {
1142 1143
            send_request(NULL, route->src->prefix, route->src->plen,
                         route->src->src_prefix, route->src->src_plen);
1144
        }
1145 1146 1147 1148 1149 1150
    }
}

/* A route has just changed.  Decide whether to switch to a different route or
   send an update. */
void
1151
route_changed(struct babel_route *route,
1152
              struct source *oldsrc, unsigned short oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1153
{
1154
    if(route->installed) {
1155 1156 1157
        struct babel_route *better_route;
        /* Do this unconditionally -- microoptimisation is not worth it. */
        better_route =
1158 1159 1160
            find_best_route(route->src->prefix, route->src->plen,
                            route->src->src_prefix, route->src->src_plen,
                            1, NULL);
1161 1162
        if(better_route && route_metric(better_route) < route_metric(route))
            consider_route(better_route);
1163
    }
1164

1165 1166 1167
    if(route->installed) {
        /* We didn't change routes after all. */
        send_triggered_update(route, oldsrc, oldmetric);
1168
    } else {
1169 1170 1171
        /* 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
1172 1173 1174
    }
}

1175
/* We just lost the installed route to a given destination. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1176
void
1177
route_lost(struct source *src, unsigned oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1178
{
1179
    struct babel_route *new_route;
1180 1181
    new_route = find_best_route(src->prefix, src->plen,
                                src->src_prefix, src->src_plen, 1, NULL);
1182 1183
    if(new_route) {
        consider_route(new_route);
1184
    } else if(oldmetric < INFINITY) {
1185
        /* Avoid creating a blackhole. */
1186 1187
        send_update_resend(NULL, src->prefix, src->plen,
                           src->src_prefix, src->src_plen);
1188 1189 1190 1191
        /* If the route was usable enough, try to get an alternate one.
           If it was not, we could be dealing with oscillations around
           the value of INFINITY. */
        if(oldmetric <= INFINITY / 2)
1192
            send_request_resend(src->prefix, src->plen,
1193
                                src->src_prefix, src->src_plen,
1194 1195 1196
                                src->metric >= INFINITY ?
                                src->seqno : seqno_plus(src->seqno, 1),
                                src->id);
1197 1198 1199
    }
}