route.c 19.7 KB
Newer Older
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1
/*
2
Copyright (c) 2007, 2008 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 28

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>

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

42 43
struct route *routes = NULL;
int numroutes = 0, maxroutes = 0;
44
int kernel_metric = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
45
int allow_duplicates = -1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
46 47

struct route *
48
find_route(const unsigned char *prefix, unsigned char plen,
49
           struct neighbour *neigh, const unsigned char *nexthop)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
50 51 52
{
    int i;
    for(i = 0; i < numroutes; i++) {
53
        if(routes[i].neigh == neigh &&
54
           memcmp(routes[i].nexthop, nexthop, 16) == 0 &&
55
           source_match(routes[i].src, prefix, plen))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
56 57 58 59 60 61
            return &routes[i];
    }
    return NULL;
}

struct route *
62
find_installed_route(const unsigned char *prefix, unsigned char plen)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
63 64 65
{
    int i;
    for(i = 0; i < numroutes; i++) {
66
        if(routes[i].installed && source_match(routes[i].src, prefix, plen))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
67 68 69 70 71 72 73 74
            return &routes[i];
    }
    return NULL;
}

void
flush_route(struct route *route)
{
75
    int i;
76
    struct source *src;
77 78
    unsigned oldmetric;
    int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
79

80 81
    i = route - routes;
    assert(i >= 0 && i < numroutes);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
82

83
    oldmetric = route_metric(route);
84

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
85 86
    if(route->installed) {
        uninstall_route(route);
87
        lost = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
88 89
    }

90
    local_notify_route(route, LOCAL_FLUSH);
91

92
    src = route->src;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
93

94 95
    if(i != numroutes - 1)
        memcpy(routes + i, routes + numroutes - 1, sizeof(struct route));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
96 97 98
    numroutes--;
    VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct route));

99 100 101 102 103
    if(numroutes == 0) {
        free(routes);
        routes = NULL;
        maxroutes = 0;
    } else if(maxroutes > 8 && numroutes < maxroutes / 4) {
104 105 106
        struct route *new_routes;
        int n = maxroutes / 2;
        new_routes = realloc(routes, n * sizeof(struct route));
107 108 109 110
        if(new_routes != NULL) {
            routes = new_routes;
            maxroutes = n;
        }
111 112
    }

113 114
    if(lost)
        route_lost(src, oldmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
115 116 117 118 119 120 121
}

void
flush_neighbour_routes(struct neighbour *neigh)
{
    int i;

122 123
    i = 0;
    while(i < numroutes) {
124
        if(routes[i].neigh == neigh) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
125
            flush_route(&routes[i]);
126
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
127
        }
128
        i++;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
129 130 131
    }
}

132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
void
flush_network_routes(struct network *net, int v4only)
{
    int i;

    i = 0;
    while(i < numroutes) {
        if(routes[i].neigh->network == net &&
           (!v4only || v4mapped(routes[i].nexthop))) {
           flush_route(&routes[i]);
           continue;
        }
        i++;
    }
}

148 149 150 151 152
static int
metric_to_kernel(int metric)
{
    return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
}
153

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
154 155 156
void
install_route(struct route *route)
{
157
    int rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
158 159 160 161

    if(route->installed)
        return;

162 163 164 165
    if(!route_feasible(route))
        fprintf(stderr, "WARNING: installing unfeasible route "
                "(this shouldn't happen).");

166
    rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
167
                      route->nexthop,
168
                      route->neigh->network->ifindex,
169
                      metric_to_kernel(route_metric(route)), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
170
    if(rc < 0) {
171
        int save = errno;
172
        perror("kernel_route(ADD)");
173
        if(save != EEXIST)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
174 175 176
            return;
    }
    route->installed = 1;
177
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
178 179 180 181 182
}

void
uninstall_route(struct route *route)
{
183 184
    int rc;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
185 186 187
    if(!route->installed)
        return;

188
    rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
189
                      route->nexthop,
190
                      route->neigh->network->ifindex,
191
                      metric_to_kernel(route_metric(route)), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
192
    if(rc < 0)
193
        perror("kernel_route(FLUSH)");
194

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
195
    route->installed = 0;
196
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
197 198
}

199 200 201 202
/* This is equivalent to uninstall_route followed with install_route,
   but without the race condition.  The destination of both routes
   must be the same. */

203
static void
204
switch_routes(struct route *old, struct route *new)
205 206 207 208 209 210 211 212 213 214 215
{
    int rc;

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

    if(!old->installed)
        return;

216 217 218 219
    if(!route_feasible(new))
        fprintf(stderr, "WARNING: switching to unfeasible route "
                "(this shouldn't happen).");

220
    rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
221
                      old->nexthop, old->neigh->network->ifindex,
222
                      metric_to_kernel(route_metric(old)),
223
                      new->nexthop, new->neigh->network->ifindex,
224
                      metric_to_kernel(route_metric(new)));
225 226 227
    if(rc < 0) {
        perror("kernel_route(MODIFY)");
        return;
228
    }
229 230 231 232

    old->installed = 0;
    new->installed = 1;

233 234
    local_notify_route(old, LOCAL_CHANGE);
    local_notify_route(new, LOCAL_CHANGE);
235 236
}

237
void
238
change_route_metric(struct route *route, unsigned newmetric)
239
{
240 241
    int old, new;

242
    if(route_metric(route) == newmetric)
243 244
        return;

245
    old = metric_to_kernel(route_metric(route));
246
    new = metric_to_kernel(newmetric);
247 248 249 250 251 252 253 254 255 256 257 258 259 260

    if(route->installed && old != new) {
        int rc;
        rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen,
                          route->nexthop, route->neigh->network->ifindex,
                          old,
                          route->nexthop, route->neigh->network->ifindex,
                          new);
        if(rc < 0) {
            perror("kernel_route(MODIFY metric)");
            return;
        }
    }

261
    route->metric = newmetric;
262
    local_notify_route(route, LOCAL_CHANGE);
263 264
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
265 266 267
int
route_feasible(struct route *route)
{
268
    return update_feasible(route->src, route->seqno, route->refmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
269 270
}

271 272 273 274 275 276 277 278 279 280 281 282
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;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
283
int
284
update_feasible(struct source *src,
285
                unsigned short seqno, unsigned short refmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
286
{
287 288 289
    if(src == NULL)
        return 1;

290
    if(src->time < now.tv_sec - SOURCE_GC_TIME)
291 292 293
        /* Never mind what is probably stale data */
        return 1;

294 295 296 297 298 299
    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
300 301
}

302
/* This returns the feasible route with the smallest metric. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
303
struct route *
304 305
find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
                struct neighbour *exclude)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
306 307 308 309 310
{
    struct route *route = NULL;
    int i;

    for(i = 0; i < numroutes; i++) {
311
        if(!source_match(routes[i].src, prefix, plen))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
312
            continue;
313
        if(route_expired(&routes[i]))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
314
            continue;
315
        if(feasible && !route_feasible(&routes[i]))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
316
            continue;
317 318
        if(exclude && routes[i].neigh == exclude)
            continue;
319
        if(route && route_metric(route) <= route_metric(&routes[i]))
320
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
321 322 323 324 325 326 327 328
        route = &routes[i];
    }
    return route;
}

void
update_route_metric(struct route *route)
{
329
    int oldmetric;
330
    int newmetric;
331

332
    oldmetric = route_metric(route);
333
    if(route_expired(route)) {
334
        if(route->refmetric < INFINITY) {
335
            route->seqno = seqno_plus(route->src->seqno, 1);
336 337 338
            route->refmetric = INFINITY;
        }
        newmetric = INFINITY;
339
    } else {
340 341 342 343 344 345 346 347
        struct neighbour *neigh = route->neigh;
        int add_metric = input_filter(route->src->id,
                                      route->src->prefix, route->src->plen,
                                      neigh->address,
                                      neigh->network->ifindex);
        newmetric = MIN(route->refmetric +
                        add_metric +
                        neighbour_cost(route->neigh),
348 349 350
                        INFINITY);
    }

351 352
    if(newmetric != oldmetric) {
        change_route_metric(route, newmetric);
353
        route_changed(route, route->src, oldmetric);
354
    }
355
}
356

357 358 359 360 361 362 363
void
update_neighbour_metric(struct neighbour *neigh)
{
    int i;

    i = 0;
    while(i < numroutes) {
364
        if(routes[i].neigh == neigh)
365 366
            update_route_metric(&routes[i]);
        i++;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
367 368 369
    }
}

370 371 372 373 374 375 376 377 378 379 380 381 382
void
update_network_metric(struct network *net)
{
    int i;

    i = 0;
    while(i < numroutes) {
        if(routes[i].neigh->network == net)
            update_route_metric(&routes[i]);
        i++;
    }
}

383
/* This is called whenever we receive an update. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
384
struct route *
385 386
update_route(const unsigned char *a, const unsigned char *p, unsigned char plen,
             unsigned short seqno, unsigned short refmetric,
387
             unsigned short interval,
388
             struct neighbour *neigh, const unsigned char *nexthop)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
389 390
{
    struct route *route;
391 392
    struct source *src;
    int metric, feasible;
393
    int add_metric;
394 395 396 397
    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
398

399 400 401
    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
402 403 404
        return NULL;
    }

405 406
    add_metric = input_filter(a, p, plen,
                              neigh->address, neigh->network->ifindex);
407
    if(add_metric >= INFINITY)
408 409
        return NULL;

410 411
    src = find_source(a, p, plen, 1, seqno);
    if(src == NULL)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
412 413
        return NULL;

414
    feasible = update_feasible(src, seqno, refmetric);
415
    route = find_route(p, plen, neigh, nexthop);
416
    metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
417

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
418
    if(route) {
419 420 421
        struct source *oldsrc;
        unsigned short oldmetric;
        int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
422

423
        oldsrc = route->src;
424
        oldmetric = route_metric(route);
425 426

        /* If a successor switches sources, we must accept his update even
427 428
           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
429
           the update. */
430 431 432 433
        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),
434
                   format_address(route->src->id),
435
                   route->seqno, route->refmetric,
436
                   format_address(src->id), seqno, refmetric);
437 438 439
            if(src != route->src) {
                uninstall_route(route);
                lost = 1;
440
            }
441 442 443
        }

        route->src = src;
444
        if(feasible && refmetric < INFINITY)
445
            route->time = now.tv_sec;
446 447 448
        route->seqno = seqno;
        route->refmetric = refmetric;
        change_route_metric(route, metric);
449
        route->hold_time = hold_time;
450

451
        route_changed(route, oldsrc, oldmetric);
452 453
        if(lost)
            route_lost(oldsrc, oldmetric);
454 455 456

        if(!feasible)
            send_unfeasible_request(neigh, route->installed && route_old(route),
457
                                    seqno, metric, src);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
458
    } else {
459 460 461
        if(refmetric >= INFINITY)
            /* Somebody's retracting a route we never saw. */
            return NULL;
462
        if(!feasible) {
463
            send_unfeasible_request(neigh, 0, seqno, metric, src);
464
            return NULL;
465
        }
466 467 468 469 470 471 472 473 474 475
        if(numroutes >= maxroutes) {
            struct route *new_routes;
            int n = maxroutes < 1 ? 8 : 2 * maxroutes;
            new_routes = routes == NULL ?
                malloc(n * sizeof(struct route)) :
                realloc(routes, n * sizeof(struct route));
            if(new_routes == NULL)
                return NULL;
            maxroutes = n;
            routes = new_routes;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
476 477
        }
        route = &routes[numroutes];
478
        route->src = src;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
479 480 481
        route->refmetric = refmetric;
        route->seqno = seqno;
        route->metric = metric;
482
        route->neigh = neigh;
483
        memcpy(route->nexthop, nexthop, 16);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
484
        route->time = now.tv_sec;
485
        route->hold_time = hold_time;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
486 487
        route->installed = 0;
        numroutes++;
488
        local_notify_route(route, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
489 490 491 492 493
        consider_route(route);
    }
    return route;
}

494 495 496
/* We just received an unfeasible update.  If it's any good, send
   a request for a new seqno. */
void
497
send_unfeasible_request(struct neighbour *neigh, int force,
498
                        unsigned short seqno, unsigned short metric,
499
                        struct source *src)
500
{
501
    struct route *route = find_installed_route(src->prefix, src->plen);
502

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
503
    if(seqno_minus(src->seqno, seqno) > 100) {
504 505 506 507
        /* Probably a source that lost its seqno.  Let it time-out. */
        return;
    }

508
    if(force || !route || route_metric(route) >= metric + 512) {
509
        send_unicast_multihop_request(neigh, src->prefix, src->plen,
510 511 512 513
                                      src->metric >= INFINITY ?
                                      src->seqno :
                                      seqno_plus(src->seqno, 1),
                                      src->id, 127);
514 515 516
    }
}

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

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
519 520 521 522
void
consider_route(struct route *route)
{
    struct route *installed;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
523
    struct xroute *xroute;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
524 525 526 527

    if(route->installed)
        return;

528
    if(!route_feasible(route))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
529 530
        return;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
531 532 533
    xroute = find_xroute(route->src->prefix, route->src->plen);
    if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
        return;
534 535

    installed = find_installed_route(route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
536 537 538 539

    if(installed == NULL)
        goto install;

540
    if(route_metric(route) >= INFINITY)
541 542
        return;

543
    if(route_metric(installed) >= INFINITY)
544 545
        goto install;

546
    if(route_metric(installed) >= route_metric(route) + 192)
547 548 549 550 551 552
        goto install;

    /* Avoid switching sources */
    if(installed->src != route->src)
        return;

553
    if(route_metric(installed) >= route_metric(route) + 64)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
554 555 556 557 558
        goto install;

    return;

 install:
559
    switch_routes(installed, route);
560
    if(installed && route->installed)
561
        send_triggered_update(route, installed->src, route_metric(installed));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
562
    else
563
        send_update(NULL, 1, route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
564 565 566
    return;
}

567 568 569 570 571 572 573 574
void
retract_neighbour_routes(struct neighbour *neigh)
{
    int i;

    i = 0;
    while(i < numroutes) {
        if(routes[i].neigh == neigh) {
575
            unsigned short oldmetric = route_metric(&routes[i]);
576 577 578 579 580 581 582 583 584
            if(oldmetric != INFINITY) {
                change_route_metric(&routes[i], INFINITY);
                route_changed(&routes[i], routes[i].src, oldmetric);
            }
        }
        i++;
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
585
void
586 587
send_triggered_update(struct route *route, struct source *oldsrc,
                      unsigned oldmetric)
588
{
589
    unsigned newmetric, diff;
590 591
    /* 1 means send speedily, 2 means resend */
    int urgent;
592

593 594 595
    if(!route->installed)
        return;

596
    newmetric = route_metric(route);
597 598
    diff =
        newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
599

600 601
    if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
        /* Switching sources can cause transient routing loops.
602
           Retractions can cause blackholes. */
603
        urgent = 2;
604 605
    else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
        /* Route getting significantly worse */
606
        urgent = 1;
607 608 609 610 611 612 613 614 615 616 617 618 619
    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 */
620
        return;
621 622
    else
        urgent = 0;
623

624 625 626 627
    if(urgent >= 2)
        send_update_resend(NULL, route->src->prefix, route->src->plen);
    else
        send_update(NULL, urgent, route->src->prefix, route->src->plen);
628 629

    if(oldmetric < INFINITY) {
630
        if(newmetric >= oldmetric + 512) {
631
            send_request_resend(NULL, route->src->prefix, route->src->plen,
632 633 634
                                route->src->metric >= INFINITY ?
                                route->src->seqno :
                                seqno_plus(route->src->seqno, 1),
635
                                route->src->id);
636
        } else if(newmetric >= oldmetric + 288) {
637
            send_request(NULL, route->src->prefix, route->src->plen);
638
        }
639 640 641 642 643 644
    }
}

/* A route has just changed.  Decide whether to switch to a different route or
   send an update. */
void
645 646
route_changed(struct route *route,
              struct source *oldsrc, unsigned short oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
647
{
648
    if(route->installed) {
649
        if(route_metric(route) > oldmetric) {
650 651
            struct route *better_route;
            better_route =
652
                find_best_route(route->src->prefix, route->src->plen, 1, NULL);
653 654
            if(better_route &&
               route_metric(better_route) <= route_metric(route) - 96)
655
                consider_route(better_route);
656
        }
657

658
        if(route->installed)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
659
            /* We didn't change routes after all. */
660
            send_triggered_update(route, oldsrc, oldmetric);
661
    } else {
662 663 664
        /* 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
665 666 667
    }
}

668
/* We just lost the installed route to a given destination. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
669
void
670
route_lost(struct source *src, unsigned oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
671
{
672
    struct route *new_route;
673
    new_route = find_best_route(src->prefix, src->plen, 1, NULL);
674 675
    if(new_route) {
        consider_route(new_route);
676
    } else if(oldmetric < INFINITY) {
677
        /* Complain loudly. */
678
        send_update_resend(NULL, src->prefix, src->plen);
679 680 681
        send_request_resend(NULL, src->prefix, src->plen,
                            src->metric >= INFINITY ?
                            src->seqno : seqno_plus(src->seqno, 1),
682
                            src->id);
683 684 685 686 687 688 689
    }
}

void
expire_routes(void)
{
    int i;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
690

691
    debugf("Expiring old routes.\n");
692

693 694 695 696
    i = 0;
    while(i < numroutes) {
        struct route *route = &routes[i];

697
        if(route->time > now.tv_sec || /* clock stepped */
698
           route_old(route)) {
699 700
            flush_route(route);
            continue;
701
        }
702 703 704 705

        update_route_metric(route);

        if(route->installed && route->refmetric < INFINITY) {
706
            if(route_old(route))
707
                send_unicast_request(route->neigh,
708
                                     route->src->prefix, route->src->plen);
709 710
        }
        i++;
711
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
712
}