route.c 18.8 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 "babel.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 46

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

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

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

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

82 83
    oldmetric = route->metric;

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

89
    local_notify_route(route, LOCAL_FLUSH);
90

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

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

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

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

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

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

131 132 133 134 135
static int
metric_to_kernel(int metric)
{
    return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
}
136

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
137 138 139
void
install_route(struct route *route)
{
140
    int rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
141 142 143 144

    if(route->installed)
        return;

145 146 147 148
    if(!route_feasible(route))
        fprintf(stderr, "WARNING: installing unfeasible route "
                "(this shouldn't happen).");

149
    rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
150
                      route->nexthop,
151
                      route->neigh->network->ifindex,
152
                      metric_to_kernel(route->metric), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
153
    if(rc < 0) {
154
        int save = errno;
155
        perror("kernel_route(ADD)");
156
        if(save != EEXIST)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
157 158 159
            return;
    }
    route->installed = 1;
160
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
161 162 163 164 165
}

void
uninstall_route(struct route *route)
{
166 167
    int rc;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
168 169 170
    if(!route->installed)
        return;

171
    rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
172
                      route->nexthop,
173
                      route->neigh->network->ifindex,
174
                      metric_to_kernel(route->metric), NULL, 0, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
175
    if(rc < 0)
176
        perror("kernel_route(FLUSH)");
177

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
178
    route->installed = 0;
179
    local_notify_route(route, LOCAL_CHANGE);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
180 181
}

182 183 184 185
/* This is equivalent to uninstall_route followed with install_route,
   but without the race condition.  The destination of both routes
   must be the same. */

186
static void
187
switch_routes(struct route *old, struct route *new)
188 189 190 191 192 193 194 195 196 197 198
{
    int rc;

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

    if(!old->installed)
        return;

199 200 201 202
    if(!route_feasible(new))
        fprintf(stderr, "WARNING: switching to unfeasible route "
                "(this shouldn't happen).");

203
    rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
204
                      old->nexthop, old->neigh->network->ifindex,
205
                      metric_to_kernel(old->metric),
206
                      new->nexthop, new->neigh->network->ifindex,
207
                      metric_to_kernel(new->metric));
208 209 210
    if(rc < 0) {
        perror("kernel_route(MODIFY)");
        return;
211
    }
212 213 214 215

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

216 217
    local_notify_route(old, LOCAL_CHANGE);
    local_notify_route(new, LOCAL_CHANGE);
218 219
}

220
void
221
change_route_metric(struct route *route, unsigned newmetric)
222
{
223 224
    int old, new;

225 226 227
    if(route->metric == newmetric)
        return;

228 229
    old = metric_to_kernel(route->metric);
    new = metric_to_kernel(newmetric);
230 231 232 233 234 235 236 237 238 239 240 241 242 243

    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;
        }
    }

244
    route->metric = newmetric;
245
    local_notify_route(route, LOCAL_CHANGE);
246 247
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
248 249 250
int
route_feasible(struct route *route)
{
251
    return update_feasible(route->src, route->seqno, route->refmetric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
252 253
}

254 255 256 257 258 259 260 261 262 263 264 265
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
266
int
267
update_feasible(struct source *src,
268
                unsigned short seqno, unsigned short refmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
269
{
270 271 272
    if(src == NULL)
        return 1;

273
    if(src->time < now.tv_sec - SOURCE_GC_TIME)
274 275 276
        /* Never mind what is probably stale data */
        return 1;

277 278 279 280 281 282
    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
283 284
}

285
/* This returns the feasible route with the smallest metric. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
286
struct route *
287 288
find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
                struct neighbour *exclude)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
289 290 291 292 293
{
    struct route *route = NULL;
    int i;

    for(i = 0; i < numroutes; i++) {
294
        if(!source_match(routes[i].src, prefix, plen))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
295
            continue;
296
        if(route_expired(&routes[i]))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
297
            continue;
298
        if(feasible && !route_feasible(&routes[i]))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
299
            continue;
300 301
        if(exclude && routes[i].neigh == exclude)
            continue;
302 303
        if(route && route->metric <= routes[i].metric)
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
304 305 306 307 308 309 310 311
        route = &routes[i];
    }
    return route;
}

void
update_route_metric(struct route *route)
{
312
    int oldmetric;
313
    int newmetric;
314

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
315
    oldmetric = route->metric;
316
    if(route_expired(route)) {
317
        if(route->refmetric < INFINITY) {
318
            route->seqno = seqno_plus(route->src->seqno, 1);
319 320 321
            route->refmetric = INFINITY;
        }
        newmetric = INFINITY;
322
    } else {
323
        newmetric = MIN(route->refmetric + neighbour_cost(route->neigh),
324 325 326
                        INFINITY);
    }

327 328
    if(newmetric != oldmetric) {
        change_route_metric(route, newmetric);
329
        route_changed(route, route->src, oldmetric);
330
    }
331
}
332

333 334 335 336 337 338 339
void
update_neighbour_metric(struct neighbour *neigh)
{
    int i;

    i = 0;
    while(i < numroutes) {
340
        if(routes[i].neigh == neigh)
341 342
            update_route_metric(&routes[i]);
        i++;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
343 344 345
    }
}

346 347 348 349 350 351 352 353 354 355 356 357 358
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++;
    }
}

359
/* This is called whenever we receive an update. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
360
struct route *
361 362
update_route(const unsigned char *a, const unsigned char *p, unsigned char plen,
             unsigned short seqno, unsigned short refmetric,
363
             unsigned short interval,
364
             struct neighbour *neigh, const unsigned char *nexthop)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
365 366
{
    struct route *route;
367 368
    struct source *src;
    int metric, feasible;
369
    int add_metric;
370 371 372 373
    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
374

375 376 377
    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
378 379 380
        return NULL;
    }

381 382
    add_metric = input_filter(a, p, plen,
                              neigh->address, neigh->network->ifindex);
383
    if(add_metric >= INFINITY)
384 385
        return NULL;

386 387
    src = find_source(a, p, plen, 1, seqno);
    if(src == NULL)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
388 389
        return NULL;

390
    feasible = update_feasible(src, seqno, refmetric);
391
    route = find_route(p, plen, neigh, nexthop);
392
    metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
393

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
394
    if(route) {
395 396 397
        struct source *oldsrc;
        unsigned short oldmetric;
        int lost = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
398

399
        oldsrc = route->src;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
400
        oldmetric = route->metric;
401 402

        /* If a successor switches sources, we must accept his update even
403 404
           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
405
           the update. */
406 407 408 409
        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),
410
                   format_address(route->src->id),
411
                   route->seqno, route->refmetric,
412
                   format_address(src->id), seqno, refmetric);
413 414 415
            if(src != route->src) {
                uninstall_route(route);
                lost = 1;
416
            }
417 418 419
        }

        route->src = src;
420
        if(feasible && refmetric < INFINITY)
421
            route->time = now.tv_sec;
422 423 424
        route->seqno = seqno;
        route->refmetric = refmetric;
        change_route_metric(route, metric);
425
        route->hold_time = hold_time;
426

427
        route_changed(route, oldsrc, oldmetric);
428 429
        if(lost)
            route_lost(oldsrc, oldmetric);
430 431 432

        if(!feasible)
            send_unfeasible_request(neigh, route->installed && route_old(route),
433
                                    seqno, metric, src);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
434
    } else {
435 436 437
        if(refmetric >= INFINITY)
            /* Somebody's retracting a route we never saw. */
            return NULL;
438
        if(!feasible) {
439
            send_unfeasible_request(neigh, 0, seqno, metric, src);
440
            return NULL;
441
        }
442 443 444 445 446 447 448 449 450 451
        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
452 453
        }
        route = &routes[numroutes];
454
        route->src = src;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
455 456 457
        route->refmetric = refmetric;
        route->seqno = seqno;
        route->metric = metric;
458
        route->neigh = neigh;
459
        memcpy(route->nexthop, nexthop, 16);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
460
        route->time = now.tv_sec;
461
        route->hold_time = hold_time;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
462 463
        route->installed = 0;
        numroutes++;
464
        local_notify_route(route, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
465 466 467 468 469
        consider_route(route);
    }
    return route;
}

470 471 472
/* We just received an unfeasible update.  If it's any good, send
   a request for a new seqno. */
void
473
send_unfeasible_request(struct neighbour *neigh, int force,
474
                        unsigned short seqno, unsigned short metric,
475
                        struct source *src)
476
{
477
    struct route *route = find_installed_route(src->prefix, src->plen);
478

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
479
    if(seqno_minus(src->seqno, seqno) > 100) {
480 481 482 483
        /* Probably a source that lost its seqno.  Let it time-out. */
        return;
    }

484
    if(force || !route || route->metric >= metric + 512) {
485
        send_unicast_multihop_request(neigh, src->prefix, src->plen,
486 487 488 489
                                      src->metric >= INFINITY ?
                                      src->seqno :
                                      seqno_plus(src->seqno, 1),
                                      src->id, 127);
490 491 492
    }
}

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

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
495 496 497 498 499 500 501 502
void
consider_route(struct route *route)
{
    struct route *installed;

    if(route->installed)
        return;

503
    if(!route_feasible(route))
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
504 505
        return;

506
    if(find_xroute(route->src->prefix, route->src->plen))
507 508 509
       return;

    installed = find_installed_route(route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
510 511 512 513

    if(installed == NULL)
        goto install;

514 515 516 517 518 519
    if(route->metric >= INFINITY)
        return;

    if(installed->metric >= INFINITY)
        goto install;

520 521 522 523 524 525 526
    if(installed->metric >= route->metric + 192)
        goto install;

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

527
    if(installed->metric >= route->metric + 64)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
528 529 530 531 532
        goto install;

    return;

 install:
533
    switch_routes(installed, route);
534 535
    if(installed && route->installed)
        send_triggered_update(route, installed->src, installed->metric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
536
    else
537
        send_update(NULL, 1, route->src->prefix, route->src->plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
538 539 540
    return;
}

541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
void
retract_neighbour_routes(struct neighbour *neigh)
{
    int i;

    i = 0;
    while(i < numroutes) {
        if(routes[i].neigh == neigh) {
            unsigned short oldmetric = routes[i].metric;
            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
559
void
560 561
send_triggered_update(struct route *route, struct source *oldsrc,
                      unsigned oldmetric)
562
{
563
    unsigned newmetric, diff;
564 565
    /* 1 means send speedily, 2 means resend */
    int urgent;
566

567 568 569
    if(!route->installed)
        return;

570
    newmetric = route->metric;
571 572
    diff =
        newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
573

574 575
    if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
        /* Switching sources can cause transient routing loops.
576
           Retractions can cause blackholes. */
577
        urgent = 2;
578 579
    else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
        /* Route getting significantly worse */
580
        urgent = 1;
581 582 583 584 585 586 587 588 589 590 591 592 593
    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 */
594
        return;
595 596
    else
        urgent = 0;
597

598 599 600 601
    if(urgent >= 2)
        send_update_resend(NULL, route->src->prefix, route->src->plen);
    else
        send_update(NULL, urgent, route->src->prefix, route->src->plen);
602 603

    if(oldmetric < INFINITY) {
604
        if(newmetric >= oldmetric + 512) {
605
            send_request_resend(NULL, route->src->prefix, route->src->plen,
606 607 608
                                route->src->metric >= INFINITY ?
                                route->src->seqno :
                                seqno_plus(route->src->seqno, 1),
609
                                route->src->id);
610
        } else if(newmetric >= oldmetric + 288) {
611
            send_request(NULL, route->src->prefix, route->src->plen);
612
        }
613 614 615 616 617 618
    }
}

/* A route has just changed.  Decide whether to switch to a different route or
   send an update. */
void
619 620
route_changed(struct route *route,
              struct source *oldsrc, unsigned short oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
621
{
622
    if(route->installed) {
623 624 625
        if(route->metric > oldmetric) {
            struct route *better_route;
            better_route =
626
                find_best_route(route->src->prefix, route->src->plen, 1, NULL);
627 628
            if(better_route && better_route->metric <= route->metric - 96)
                consider_route(better_route);
629
        }
630

631
        if(route->installed)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
632
            /* We didn't change routes after all. */
633
            send_triggered_update(route, oldsrc, oldmetric);
634
    } else {
635 636 637
        /* 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
638 639 640
    }
}

641
/* We just lost the installed route to a given destination. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
642
void
643
route_lost(struct source *src, unsigned oldmetric)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
644
{
645
    struct route *new_route;
646
    new_route = find_best_route(src->prefix, src->plen, 1, NULL);
647 648
    if(new_route) {
        consider_route(new_route);
649
    } else if(oldmetric < INFINITY) {
650
        /* Complain loudly. */
651
        send_update_resend(NULL, src->prefix, src->plen);
652 653 654
        send_request_resend(NULL, src->prefix, src->plen,
                            src->metric >= INFINITY ?
                            src->seqno : seqno_plus(src->seqno, 1),
655
                            src->id);
656 657 658 659 660 661 662
    }
}

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

664
    debugf("Expiring old routes.\n");
665

666 667 668 669
    i = 0;
    while(i < numroutes) {
        struct route *route = &routes[i];

670
        if(route->time > now.tv_sec || /* clock stepped */
671
           route_old(route)) {
672 673
            flush_route(route);
            continue;
674
        }
675 676 677 678

        update_route_metric(route);

        if(route->installed && route->refmetric < INFINITY) {
679
            if(route_old(route))
680
                send_unicast_request(route->neigh,
681
                                     route->src->prefix, route->src->plen);
682 683
        }
        i++;
684
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
685
}