babel.c 60.7 KB
Newer Older
1 2 3 4
/*
 *	BIRD -- The Babel protocol
 *
 *	Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5 6
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 *
 *	This file contains the main routines for handling and sending TLVs, as
 *	well as timers and interaction with the nest.
 */

/**
 * DOC: The Babel protocol
 *
 * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
 * robust and efficient both in ordinary wired networks and in wireless mesh
 * networks.
 *
 * The Babel protocol keeps state for each neighbour in a &babel_neighbor
 * struct, tracking received Hello and I Heard You (IHU) messages. A
 * &babel_interface struct keeps hello and update times for each interface, and
 * a separate hello seqno is maintained for each interface.
 *
 * For each prefix, Babel keeps track of both the possible routes (with next hop
 * and router IDs), as well as the feasibility distance for each prefix and
 * router id. The prefix itself is tracked in a &babel_entry struct, while the
 * possible routes for the prefix are tracked as &babel_route entries and the
 * feasibility distance is maintained through &babel_source structures.
 *
 * The main route selection is done in babel_select_route(). This is called when
 * an entry is updated by receiving updates from the network or when modified by
34 35
 * internal timers. The function selects from feasible and reachable routes the
 * one with the lowest metric to be announced to the core.
36 37 38 39 40 41 42 43 44 45 46 47 48 49
 */

#include <stdlib.h>
#include "babel.h"


/*
 * Is one number greater or equal than another mod 2^16? This is based on the
 * definition of serial number space in RFC 1982. Note that arguments are of
 * uint type to avoid integer promotion to signed integer.
 */
static inline int ge_mod64k(uint a, uint b)
{ return (u16)(a - b) < 0x8000; }

50
static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e);
51 52
static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod);
static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e);
53
static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n);
54
static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr);
55
static void babel_update_cost(struct babel_neighbor *n);
56 57 58
static inline void babel_kick_timer(struct babel_proto *p);
static inline void babel_iface_kick_timer(struct babel_iface *ifa);

59 60 61 62 63 64
static inline void babel_lock_neighbor(struct babel_neighbor *nbr)
{ if (nbr) nbr->uc++; }

static inline void babel_unlock_neighbor(struct babel_neighbor *nbr)
{ if (nbr && !--nbr->uc) mb_free(nbr); }

65 66 67 68 69 70

/*
 *	Functions to maintain data structures
 */

static void
71
babel_init_entry(void *E)
72
{
73 74
  struct babel_entry *e = E;

75
  e->updated = current_time();
76
  init_list(&e->requests);
77 78 79 80 81
  init_list(&e->sources);
  init_list(&e->routes);
}

static inline struct babel_entry *
82
babel_find_entry(struct babel_proto *p, const net_addr *n)
83
{
84 85
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
  return fib_find(rtable, n);
86 87 88
}

static struct babel_entry *
89
babel_get_entry(struct babel_proto *p, const net_addr *n)
90
{
91 92
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
  struct babel_entry *e = fib_get(rtable, n);
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
  return e;
}

static struct babel_source *
babel_find_source(struct babel_entry *e, u64 router_id)
{
  struct babel_source *s;

  WALK_LIST(s, e->sources)
    if (s->router_id == router_id)
      return s;

  return NULL;
}

static struct babel_source *
109
babel_get_source(struct babel_proto *p, struct babel_entry *e, u64 router_id)
110 111 112 113 114 115 116 117
{
  struct babel_source *s = babel_find_source(e, router_id);

  if (s)
    return s;

  s = sl_alloc(p->source_slab);
  s->router_id = router_id;
118
  s->expires = current_time() + BABEL_GARBAGE_INTERVAL;
119 120 121 122 123 124 125 126
  s->seqno = 0;
  s->metric = BABEL_INFINITY;
  add_tail(&e->sources, NODE s);

  return s;
}

static void
127
babel_expire_sources(struct babel_proto *p, struct babel_entry *e)
128 129
{
  struct babel_source *n, *nx;
130
  btime now_ = current_time();
131 132 133

  WALK_LIST_DELSAFE(n, nx, e->sources)
  {
134
    if (n->expires && n->expires <= now_)
135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
    {
      rem_node(NODE n);
      sl_free(p->source_slab, n);
    }
  }
}

static struct babel_route *
babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
{
  struct babel_route *r;

  WALK_LIST(r, e->routes)
    if (r->neigh == n)
      return r;

  return NULL;
}

static struct babel_route *
155
babel_get_route(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *nbr)
156 157 158 159 160 161 162 163
{
  struct babel_route *r = babel_find_route(e, nbr);

  if (r)
    return r;

  r = sl_alloc(p->route_slab);
  memset(r, 0, sizeof(*r));
164

165
  r->e = e;
166
  r->neigh = nbr;
167
  add_tail(&e->routes, NODE r);
168
  add_tail(&nbr->routes, NODE &r->neigh_route);
169 170 171 172

  return r;
}

173 174 175 176 177 178 179 180 181
static inline void
babel_retract_route(struct babel_proto *p, struct babel_route *r)
{
  r->metric = r->advert_metric = BABEL_INFINITY;

  if (r == r->e->selected)
    babel_select_route(p, r->e, r);
}

182
static void
183
babel_flush_route(struct babel_proto *p, struct babel_route *r)
184
{
185
  DBG("Babel: Flush route %N router_id %lR neigh %I\n",
186
      r->e->n.addr, r->router_id, r->neigh->addr);
187 188

  rem_node(NODE r);
189
  rem_node(&r->neigh_route);
190

191 192
  if (r->e->selected == r)
    r->e->selected = NULL;
193 194 195 196 197

  sl_free(p->route_slab, r);
}

static void
198
babel_expire_route(struct babel_proto *p, struct babel_route *r)
199
{
200
  struct babel_config *cf = (void *) p->p.cf;
201

202
  TRACE(D_EVENTS, "Route expiry timer for %N router-id %lR fired",
203
	r->e->n.addr, r->router_id);
204 205 206

  if (r->metric < BABEL_INFINITY)
  {
207
    r->metric = r->advert_metric = BABEL_INFINITY;
208
    r->expires = current_time() + cf->hold_time;
209 210 211
  }
  else
  {
212
    babel_flush_route(p, r);
213 214 215 216
  }
}

static void
217
babel_refresh_route(struct babel_proto *p, struct babel_route *r)
218
{
219
  if (r == r->e->selected)
220
    babel_send_route_request(p, r->e, r->neigh);
221 222 223 224 225

  r->refresh_time = 0;
}

static void
226
babel_expire_routes_(struct babel_proto *p, struct fib *rtable)
227
{
228
  struct babel_config *cf = (void *) p->p.cf;
229 230
  struct babel_route *r, *rx;
  struct fib_iterator fit;
231
  btime now_ = current_time();
232

233
  FIB_ITERATE_INIT(&fit, rtable);
234 235

loop:
236
  FIB_ITERATE_START(rtable, &fit, struct babel_entry, e)
237 238 239 240 241
  {
    int changed = 0;

    WALK_LIST_DELSAFE(r, rx, e->routes)
    {
242
      if (r->refresh_time && r->refresh_time <= now_)
243
	babel_refresh_route(p, r);
244

245
      if (r->expires && r->expires <= now_)
246
      {
247
	changed = changed || (r == e->selected);
248
	babel_expire_route(p, r);
249 250 251 252 253 254 255 256
      }
    }

    if (changed)
    {
      /*
       * We have to restart the iteration because there may be a cascade of
       * synchronous events babel_select_route() -> nest table change ->
257
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
258
       */
259 260 261 262 263 264 265 266
      FIB_ITERATE_PUT(&fit);
      babel_select_route(p, e, NULL);
      goto loop;
    }

    /* Clean up stale entries */
    if ((e->valid == BABEL_ENTRY_STALE) && ((e->updated + cf->hold_time) <= now_))
      e->valid = BABEL_ENTRY_DUMMY;
267

268 269 270
    /* Clean up unreachable route */
    if (e->unreachable && (!e->valid || (e->router_id == p->router_id)))
    {
271
      FIB_ITERATE_PUT(&fit);
272
      babel_announce_retraction(p, e);
273 274 275
      goto loop;
    }

276
    babel_expire_sources(p, e);
277
    babel_expire_requests(p, e);
278 279

    /* Remove empty entries */
280
    if (!e->valid && EMPTY_LIST(e->routes) && EMPTY_LIST(e->sources) && EMPTY_LIST(e->requests))
281
    {
282
      FIB_ITERATE_PUT(&fit);
283
      fib_delete(rtable, e);
284 285 286
      goto loop;
    }
  }
287
  FIB_ITERATE_END;
288 289
}

290 291 292 293 294 295 296
static void
babel_expire_routes(struct babel_proto *p)
{
  babel_expire_routes_(p, &p->ip4_rtable);
  babel_expire_routes_(p, &p->ip6_rtable);
}

297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
static inline int seqno_request_valid(struct babel_seqno_request *sr)
{ return !sr->nbr || sr->nbr->ifa; }

/*
 * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send
 * it to network. Do nothing if it is already in the table.
 */

static void
babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e,
			u64 router_id, u16 seqno, u8 hop_count,
			struct babel_neighbor *nbr)
{
  struct babel_seqno_request *sr;

  WALK_LIST(sr, e->requests)
    if (sr->router_id == router_id)
    {
      /* Found matching or newer */
      if (ge_mod64k(sr->seqno, seqno) && seqno_request_valid(sr))
	return;

      /* Found older */
      babel_unlock_neighbor(sr->nbr);
      rem_node(NODE sr);
      goto found;
    }

  /* No entries found */
  sr = sl_alloc(p->seqno_slab);

found:
  sr->router_id = router_id;
  sr->seqno = seqno;
  sr->hop_count = hop_count;
  sr->count = 0;
  sr->expires = current_time() + BABEL_SEQNO_REQUEST_EXPIRY;
  babel_lock_neighbor(sr->nbr = nbr);
  add_tail(&e->requests, NODE sr);

  babel_send_seqno_request(p, e, sr);
}

static void
babel_remove_seqno_request(struct babel_proto *p, struct babel_seqno_request *sr)
{
  babel_unlock_neighbor(sr->nbr);
  rem_node(NODE sr);
  sl_free(p->seqno_slab, sr);
}

static int
babel_satisfy_seqno_request(struct babel_proto *p, struct babel_entry *e,
			   u64 router_id, u16 seqno)
{
  struct babel_seqno_request *sr;

  WALK_LIST(sr, e->requests)
    if ((sr->router_id == router_id) && ge_mod64k(seqno, sr->seqno))
    {
      /* Found the request, remove it */
      babel_remove_seqno_request(p, sr);
      return 1;
    }

  return 0;
}

static void
babel_expire_requests(struct babel_proto *p, struct babel_entry *e)
{
  struct babel_seqno_request *sr, *srx;
  btime now_ = current_time();

  WALK_LIST_DELSAFE(sr, srx, e->requests)
  {
    /* Remove seqno requests sent to dead neighbors */
    if (!seqno_request_valid(sr))
    {
      babel_remove_seqno_request(p, sr);
      continue;
    }

    /* Handle expired requests - resend or remove */
    if (sr->expires && sr->expires <= now_)
    {
      if (sr->count < BABEL_SEQNO_REQUEST_RETRY)
      {
	sr->count++;
	sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count);
	babel_send_seqno_request(p, e, sr);
      }
      else
      {
	TRACE(D_EVENTS, "Seqno request for %N router-id %lR expired",
	      e->n.addr, sr->router_id);

	babel_remove_seqno_request(p, sr);
	continue;
      }
    }
  }
}

401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
static struct babel_neighbor *
babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
{
  struct babel_neighbor *nbr;

  WALK_LIST(nbr, ifa->neigh_list)
    if (ipa_equal(nbr->addr, addr))
      return nbr;

  return NULL;
}

static struct babel_neighbor *
babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
{
416
  struct babel_proto *p = ifa->proto;
417 418 419 420 421
  struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);

  if (nbr)
    return nbr;

422 423
  TRACE(D_EVENTS, "New neighbor %I on %s", addr, ifa->iface->name);

424 425 426
  nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
  nbr->ifa = ifa;
  nbr->addr = addr;
427
  nbr->rxcost = BABEL_INFINITY;
428
  nbr->txcost = BABEL_INFINITY;
429
  nbr->cost = BABEL_INFINITY;
430
  init_list(&nbr->routes);
431
  babel_lock_neighbor(nbr);
432 433 434 435 436 437
  add_tail(&ifa->neigh_list, NODE nbr);

  return nbr;
}

static void
438
babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr)
439
{
440
  struct babel_route *r;
441 442
  node *n;

443
  TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name);
444 445 446

  WALK_LIST_FIRST(n, nbr->routes)
  {
447 448
    r = SKIP_BACK(struct babel_route, neigh_route, n);
    babel_retract_route(p, r);
449
    babel_flush_route(p, r);
450 451
  }

452
  nbr->ifa = NULL;
453
  rem_node(NODE nbr);
454
  babel_unlock_neighbor(nbr);
455 456 457
}

static void
458
babel_expire_ihu(struct babel_proto *p, struct babel_neighbor *nbr)
459
{
460 461
  TRACE(D_EVENTS, "IHU from nbr %I on %s expired", nbr->addr, nbr->ifa->iface->name);

462
  nbr->txcost = BABEL_INFINITY;
463
  nbr->ihu_expiry = 0;
464
  babel_update_cost(nbr);
465 466 467
}

static void
468
babel_expire_hello(struct babel_proto *p, struct babel_neighbor *nbr, btime now_)
469
{
470
again:
471 472 473 474 475
  nbr->hello_map <<= 1;

  if (nbr->hello_cnt < 16)
    nbr->hello_cnt++;

476 477 478 479 480 481
  nbr->hello_expiry += nbr->last_hello_int;

  /* We may expire multiple hellos if last_hello_int is too short */
  if (nbr->hello_map && nbr->hello_expiry <= now_)
    goto again;

482 483 484
  TRACE(D_EVENTS, "Hello from nbr %I on %s expired, %d left",
	nbr->addr, nbr->ifa->iface->name, u32_popcount(nbr->hello_map));

485
  if (nbr->hello_map)
486
    babel_update_cost(nbr);
487
  else
488
    babel_flush_neighbor(p, nbr);
489 490 491 492 493 494 495
}

static void
babel_expire_neighbors(struct babel_proto *p)
{
  struct babel_iface *ifa;
  struct babel_neighbor *nbr, *nbx;
496
  btime now_ = current_time();
497 498 499 500 501

  WALK_LIST(ifa, p->interfaces)
  {
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
    {
502
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now_)
503
        babel_expire_ihu(p, nbr);
504

505
      if (nbr->hello_expiry && nbr->hello_expiry <= now_)
506
        babel_expire_hello(p, nbr, now_);
507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
    }
  }
}


/*
 *	Best route selection
 */

/*
 * From the RFC (section 3.5.1):
 *
 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
 * metric) is feasible if one of the following conditions holds:
 *
 * - metric is infinite; or
 *
 * - no entry exists in the source table indexed by (id, prefix, plen); or
 *
 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
 *   table, and either
 *   - seqno' < seqno or
 *   - seqno = seqno' and metric < metric'.
 */
static inline int
babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
{
  return !s ||
    (metric == BABEL_INFINITY) ||
    (seqno > s->seqno) ||
    ((seqno == s->seqno) && (metric < s->metric));
}

540 541 542
/* Simple additive metric - Appendix 3.1 in the RFC */
static inline u16
babel_compute_metric(struct babel_neighbor *n, uint metric)
543
{
544 545
  return MIN(metric + n->cost, BABEL_INFINITY);
}
546

547 548 549 550 551 552 553 554 555
static void
babel_update_cost(struct babel_neighbor *nbr)
{
  struct babel_proto *p = nbr->ifa->proto;
  struct babel_iface_config *cf = nbr->ifa->cf;
  uint rcv = u32_popcount(nbr->hello_map); // number of bits set
  uint max = nbr->hello_cnt;
  uint rxcost = BABEL_INFINITY;	/* Cost to announce in IHU */
  uint txcost = BABEL_INFINITY;	/* Effective cost for route selection */
556

557 558
  if (!rcv || !nbr->ifa->up)
    goto done;
559

560
  switch (cf->type)
561
  {
562
  case BABEL_IFACE_TYPE_WIRED:
563 564
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */

565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
    /* Link is bad if less than cf->limit/16 of expected hellos were received */
    if (rcv * 16 < cf->limit * max)
      break;

    rxcost =  cf->rxcost;
    txcost = nbr->txcost;
    break;

  case BABEL_IFACE_TYPE_WIRELESS:
    /*
     * ETX - Appendix 2.2 in the RFC.
     *
     * alpha  = prob. of successful transmission estimated by the neighbor
     * beta   = prob. of successful transmission estimated by the router
     * rxcost = nominal rxcost of the router / beta
     * txcost = nominal rxcost of the neighbor / (alpha * beta)
     *        = received txcost / beta
     *
     * Note that received txcost is just neighbor's rxcost. Beta is rcv/max,
     * we use inverse values of beta (i.e. max/rcv) to stay in integers.
     */
    rxcost = MIN( cf->rxcost * max / rcv, BABEL_INFINITY);
    txcost = MIN(nbr->txcost * max / rcv, BABEL_INFINITY);
    break;
  }
590

591 592 593
done:
  /* If RX cost changed, send IHU with next Hello */
  if (rxcost != nbr->rxcost)
594
  {
595 596
    nbr->rxcost = rxcost;
    nbr->ihu_cnt = 0;
597
  }
598 599 600

  /* If link cost changed, run route selection */
  if (txcost != nbr->cost)
601
  {
602 603
    TRACE(D_EVENTS, "Cost of nbr %I on %s changed from %u to %u",
	  nbr->addr, nbr->ifa->iface->name, nbr->cost, txcost);
604

605
    nbr->cost = txcost;
606

607 608 609 610
    struct babel_route *r; node *n;
    WALK_LIST2(r, n, nbr->routes, neigh_route)
    {
      r->metric = babel_compute_metric(nbr, r->advert_metric);
611
      babel_select_route(p, r->e, r);
612 613 614
    }
  }
}
615 616 617 618 619 620 621

/**
 * babel_announce_rte - announce selected route to the core
 * @p: Babel protocol instance
 * @e: Babel route entry to announce
 *
 * This function announces a Babel entry to the core if it has a selected
622 623
 * incoming path, and retracts it otherwise. If there is no selected route but
 * the entry is valid and ours, the unreachable route is announced instead.
624 625 626 627
 */
static void
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
{
628
  struct babel_route *r = e->selected;
629
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
630 631 632

  if (r)
  {
633
    rta a0 = {
634 635 636
      .src = p->p.main_source,
      .source = RTS_BABEL,
      .scope = SCOPE_UNIVERSE,
637
      .dest = RTD_UNICAST,
638
      .from = r->neigh->addr,
639
      .nh.gw = r->next_hop,
640
      .nh.iface = r->neigh->ifa->iface,
641 642
    };

643
    rta *a = rta_lookup(&a0);
644
    rte *rte = rte_get_temp(a);
645
    rte->u.babel.seqno = r->seqno;
646 647 648 649
    rte->u.babel.metric = r->metric;
    rte->u.babel.router_id = r->router_id;
    rte->pflags = 0;

650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
    e->unreachable = 0;
    rte_update2(c, e->n.addr, rte, p->p.main_source);
  }
  else if (e->valid && (e->router_id != p->router_id))
  {
    /* Unreachable */
    rta a0 = {
      .src = p->p.main_source,
      .source = RTS_BABEL,
      .scope = SCOPE_UNIVERSE,
      .dest = RTD_UNREACHABLE,
    };

    rta *a = rta_lookup(&a0);
    rte *rte = rte_get_temp(a);
    memset(&rte->u.babel, 0, sizeof(rte->u.babel));
    rte->pflags = 0;
    rte->pref = 1;

    e->unreachable = 1;
670
    rte_update2(c, e->n.addr, rte, p->p.main_source);
671 672 673 674
  }
  else
  {
    /* Retraction */
675
    e->unreachable = 0;
676
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
677 678 679
  }
}

680 681 682 683 684 685 686 687 688 689
/* Special case of babel_announce_rte() just for retraction */
static inline void
babel_announce_retraction(struct babel_proto *p, struct babel_entry *e)
{
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
  e->unreachable = 0;
  rte_update2(c, e->n.addr, NULL, p->p.main_source);
}


690 691
/**
 * babel_select_route - select best route for given route entry
692
 * @p: Babel protocol instance
693
 * @e: Babel entry to select the best route for
694
 * @mod: Babel route that was modified or NULL if unspecified
695
 *
696 697 698 699
 * Select the best reachable and feasible route for a given prefix among the
 * routes received from peers, and propagate it to the nest. This just selects
 * the reachable and feasible route with the lowest metric, but keeps selected
 * the old one in case of tie.
700 701
 *
 * If no feasible route is available for a prefix that previously had a route
702 703 704 705 706 707 708 709 710 711 712 713
 * selected, a seqno request is sent to try to get a valid route. If the entry
 * is valid and not owned by us, the unreachable route is announced to the nest
 * (to blackhole packets going to it, as per section 2.8). It is later removed
 * by babel_expire_routes(). Otherwise, the route is just removed from the nest.
 *
 * Argument @mod is used to optimize best route calculation. When specified, the
 * function can assume that only the @mod route was modified to avoid full best
 * route selection and announcement when non-best route was modified in minor
 * way. The caller is advised to not call babel_select_route() when no change is
 * done (e.g. periodic route updates) to avoid unnecessary announcements of the
 * same best route. The caller is not required to call the function in case of a
 * retraction of a non-best route.
714
 *
715 716
 * Note that the function does not active triggered updates. That is done by
 * babel_rt_notify() when the change is propagated back to Babel.
717 718
 */
static void
719
babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod)
720
{
721
  struct babel_route *r, *best = e->selected;
722

723 724
  /* Shortcut if only non-best was modified */
  if (mod && (mod != best))
725
  {
726 727 728 729 730
    /* Either select modified route, or keep old best route */
    if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible)
      best = mod;
    else
      return;
731
  }
732
  else
733
  {
734 735 736
    /* Selected route may be modified and no longer admissible */
    if (!best || (best->metric == BABEL_INFINITY) || !best->feasible)
      best = NULL;
737

738 739 740 741 742
    /* Find the best feasible route from all routes */
    WALK_LIST(r, e->routes)
      if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible)
	best = r;
  }
743

744 745 746 747 748 749 750 751 752 753 754 755 756
  if (best)
  {
    if (best != e->selected)
      TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d",
	    e->n.addr, best->router_id, best->metric);
  }
  else if (e->selected)
  {
    /*
     * We have lost all feasible routes. We have to broadcast seqno request
     * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8).
     * The later is done automatically by babel_announce_rte().
     */
757

758 759 760
    TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr);
    if (e->valid && (e->selected->router_id == e->router_id))
      babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL);
761
  }
762 763 764 765 766
  else
    return;

  e->selected = best;
  babel_announce_rte(p, e);
767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793
}

/*
 *	Functions to send replies
 */

static void
babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

  TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce);

  msg.type = BABEL_TLV_ACK;
  msg.ack.nonce = nonce;

  babel_send_unicast(&msg, ifa, dest);
}

static void
babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
{
  struct babel_proto *p = ifa->proto;

  msg->type = BABEL_TLV_IHU;
  msg->ihu.addr = n->addr;
794
  msg->ihu.rxcost = n->rxcost;
795 796
  msg->ihu.interval = ifa->cf->ihu_interval;

797 798
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %t",
        msg->ihu.addr, msg->ihu.rxcost, (btime) msg->ihu.interval);
799 800 801 802 803 804 805 806
}

static void
babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
{
  union babel_msg msg = {};
  babel_build_ihu(&msg, ifa, n);
  babel_send_unicast(&msg, ifa, n->addr);
807
  n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
808 809 810 811 812 813 814 815
}

static void
babel_send_ihus(struct babel_iface *ifa)
{
  struct babel_neighbor *n;
  WALK_LIST(n, ifa->neigh_list)
  {
816 817 818 819 820 821 822
    if (n->hello_cnt && (--n->ihu_cnt <= 0))
    {
      union babel_msg msg = {};
      babel_build_ihu(&msg, ifa, n);
      babel_enqueue(&msg, ifa);
      n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
    }
823 824 825 826
  }
}

static void
827
babel_send_hello(struct babel_iface *ifa)
828 829 830 831 832 833 834 835
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

  msg.type = BABEL_TLV_HELLO;
  msg.hello.seqno = ifa->hello_seqno++;
  msg.hello.interval = ifa->cf->hello_interval;

836 837
  TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %t",
	ifa->ifname, msg.hello.seqno, (btime) msg.hello.interval);
838 839 840

  babel_enqueue(&msg, ifa);

841
  babel_send_ihus(ifa);
842 843 844
}

static void
845
babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n)
846 847 848
{
  union babel_msg msg = {};

849
  TRACE(D_PACKETS, "Sending route request for %N to %I", e->n.addr, n->addr);
850 851

  msg.type = BABEL_TLV_ROUTE_REQUEST;
852
  net_copy(&msg.route_request.net, e->n.addr);
853

854
  babel_send_unicast(&msg, n->ifa, n->addr);
855 856 857 858 859 860 861 862
}

static void
babel_send_wildcard_request(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

863
  TRACE(D_PACKETS, "Sending wildcard route request on %s", ifa->ifname);
864 865 866 867 868 869 870 871

  msg.type = BABEL_TLV_ROUTE_REQUEST;
  msg.route_request.full = 1;

  babel_enqueue(&msg, ifa);
}

static void
872
babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr)
873 874 875 876
{
  union babel_msg msg = {};

  msg.type = BABEL_TLV_SEQNO_REQUEST;
877 878 879
  msg.seqno_request.hop_count = sr->hop_count ?: BABEL_INITIAL_HOP_COUNT;
  msg.seqno_request.seqno = sr->seqno;
  msg.seqno_request.router_id = sr->router_id;
880
  net_copy(&msg.seqno_request.net, e->n.addr);
881

882 883 884 885
  if (sr->nbr)
  {
    TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d to %I on %s",
	  e->n.addr, sr->router_id, sr->seqno, sr->nbr->addr, sr->nbr->ifa->ifname);
886

887 888 889 890 891 892
    babel_send_unicast(&msg, sr->nbr->ifa, sr->nbr->addr);
  }
  else
  {
    TRACE(D_PACKETS, "Sending broadcast seqno request for %N router-id %lR seqno %d",
	  e->n.addr, sr->router_id, sr->seqno);
893

894 895 896 897
    struct babel_iface *ifa;
    WALK_LIST(ifa, p->interfaces)
      babel_enqueue(&msg, ifa);
  }
898 899 900 901 902 903 904 905 906 907 908 909 910
}

/**
 * babel_send_update - send route table updates
 * @ifa: Interface to transmit on
 * @changed: Only send entries changed since this time
 *
 * This function produces update TLVs for all entries changed since the time
 * indicated by the &changed parameter and queues them for transmission on the
 * selected interface. During the process, the feasibility distance for each
 * transmitted entry is updated.
 */
static void
911
babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable)
912 913 914
{
  struct babel_proto *p = ifa->proto;

915 916 917 918 919 920 921
  /* Update increase was requested */
  if (p->update_seqno_inc)
  {
    p->update_seqno++;
    p->update_seqno_inc = 0;
  }

922
  FIB_WALK(rtable, struct babel_entry, e)
923
  {
924
    if (!e->valid)
925 926 927 928
      continue;

    /* Our own seqno might have changed, in which case we update the routes we
       originate. */
929
    if ((e->router_id == p->router_id) && (e->seqno < p->update_seqno))
930
    {
931
      e->seqno = p->update_seqno;
932
      e->updated = current_time();
933 934 935 936 937 938
    }

    /* Skip routes that weren't updated since 'changed' time */
    if (e->updated < changed)
      continue;

939
    TRACE(D_PACKETS, "Sending update for %N router-id %lR seqno %d metric %d",
940
	  e->n.addr, e->router_id, e->seqno, e->metric);
941 942 943 944

    union babel_msg msg = {};
    msg.type = BABEL_TLV_UPDATE;
    msg.update.interval = ifa->cf->update_interval;
945 946 947
    msg.update.seqno = e->seqno;
    msg.update.metric = e->metric;
    msg.update.router_id = e->router_id;
948
    net_copy(&msg.update.net, e->n.addr);
949

950 951 952
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
			   ifa->next_hop_ip4 : ifa->next_hop_ip6);

953 954 955 956
    /* Do not send route if next hop is unknown, e.g. no configured IPv4 address */
    if (ipa_zero(msg.update.next_hop))
      continue;

957 958 959
    babel_enqueue(&msg, ifa);

    /* Update feasibility distance for redistributed routes */
960
    if (e->router_id != p->router_id)
961
    {
962
      struct babel_source *s = babel_get_source(p, e, e->router_id);
963
      s->expires = current_time() + BABEL_GARBAGE_INTERVAL;
964 965 966 967 968 969 970

      if ((msg.update.seqno > s->seqno) ||
	  ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
      {
	s->seqno = msg.update.seqno;
	s->metric = msg.update.metric;
      }
971 972 973 974 975
    }
  }
  FIB_WALK_END;
}

976
static void
977
babel_send_update(struct babel_iface *ifa, btime changed)
978 979 980 981 982 983 984
{
  struct babel_proto *p = ifa->proto;

  babel_send_update_(ifa, changed, &p->ip4_rtable);
  babel_send_update_(ifa, changed, &p->ip6_rtable);
}

985 986 987 988 989 990 991 992 993 994 995 996
static void
babel_trigger_iface_update(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;

  /* Interface not active or already scheduled */
  if (!ifa->up || ifa->want_triggered)
    return;

  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
	ifa->iface->name, p->update_seqno);

997
  ifa->want_triggered = current_time();
998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
  babel_iface_kick_timer(ifa);
}

/* Sends and update on all interfaces. */
static void
babel_trigger_update(struct babel_proto *p)
{
  if (p->triggered)
    return;

  struct babel_iface *ifa;
  WALK_LIST(ifa, p->interfaces)
    babel_trigger_iface_update(ifa);

  p->triggered = 1;
}

/* A retraction is an update with an infinite metric */
static void
1017
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
1018 1019 1020 1021
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

1022
  TRACE(D_PACKETS, "Sending retraction for %N seqno %d", n, p->update_seqno);
1023 1024 1025 1026 1027

  msg.type = BABEL_TLV_UPDATE;
  msg.update.interval = ifa->cf->update_interval;
  msg.update.seqno = p->update_seqno;
  msg.update.metric = BABEL_INFINITY;
1028
  msg.update.net = *n;
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045

  babel_enqueue(&msg, ifa);
}

static void
babel_send_wildcard_retraction(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

  TRACE(D_PACKETS, "Sending wildcard retraction on %s", ifa->ifname);

  msg.type = BABEL_TLV_UPDATE;
  msg.update.wildcard = 1;
  msg.update.interval = ifa->cf->update_interval;
  msg.update.seqno = p->update_seqno;
  msg.update.metric = BABEL_INFINITY;
1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056

  babel_enqueue(&msg, ifa);
}


/*
 *	TLV handler helpers
 */

/* Update hello history according to Appendix A1 of the RFC */
static void
1057
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
1058 1059 1060 1061 1062 1063 1064 1065 1066 1067
{
  /*
   * Compute the difference between expected and received seqno (modulo 2^16).
   * If the expected and received seqnos are within 16 of each other, the modular
   * difference is going to be less than 16 for one of the directions. Otherwise,
   * the values differ too much, so just reset the state.
   */

  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);

1068
  if ((delta == 0) || (n->hello_cnt == 0))
1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
  {
    /* Do nothing */
  }
  else if (delta <= 16)
  {
    /* Sending node decreased interval; fast-forward */
    n->hello_map <<= delta;
    n->hello_cnt = MIN(n->hello_cnt + delta, 16);
  }
  else if (delta >= 0xfff0)
  {
    u8 diff = (0xffff - delta);
    /* Sending node increased interval; undo history */
    n->hello_map >>= diff;
    n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
  }
  else
  {
    /* Note state reset - flush entries */
    n->hello_map = n->hello_cnt = 0;
  }

  /* Current entry */
  n->hello_map = (n->hello_map << 1) | 1;
  n->next_hello_seqno = seqno+1;
  if (n->hello_cnt < 16) n->hello_cnt++;
1095 1096

  /* Update expiration */
1097
  n->hello_expiry = current_time() + BABEL_HELLO_EXPIRY_FACTOR(interval);
1098
  n->last_hello_int = interval;
1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111
}


/*
 *	TLV handlers
 */

void
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_ack_req *msg = &m->ack_req;

1112 1113
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %t",
	msg->nonce, (btime) msg->interval);
1114 1115 1116 1117 1118 1119 1120 1121 1122 1123

  babel_send_ack(ifa, msg->sender, msg->nonce);
}

void
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_hello *msg = &m->hello;

1124 1125
  TRACE(D_PACKETS, "Handling hello seqno %d interval %t",
	msg->seqno, (btime) msg->interval);
1126 1127

  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1128 1129
  int first_hello = !n->hello_cnt;

1130
  babel_update_hello_history(n, msg->seqno, msg->interval);
1131 1132 1133 1134
  babel_update_cost(n);

  /* Speed up session establishment by sending IHU immediately */
  if (first_hello)
1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147
    babel_send_ihu(ifa, n);
}

void
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_ihu *msg = &m->ihu;

  /* Ignore IHUs that are not about us */
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
    return;

1148 1149
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %t",
	msg->rxcost, (btime) msg->interval);
1150 1151 1152

  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
  n->txcost = msg->rxcost;
1153
  n->ihu_expiry = current_time() + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1154
  babel_update_cost(n);
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
}

/**
 * babel_handle_update - handle incoming route updates
 * @m: Incoming update TLV
 * @ifa: Interface the update was received on
 *
 * This function is called as a handler for update TLVs and handles the updating
 * and maintenance of route entries in Babel's internal routing cache. The
 * handling follows the actions described in the Babel RFC, and at the end of
 * each update handling, babel_select_route() is called on the affected entry to
 * optionally update the selected routes and propagate them to the core.
 */
void
babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_update *msg = &m->update;

1174
  struct babel_neighbor *nbr;
1175 1176
  struct babel_entry *e;
  struct babel_source *s;
1177
  struct babel_route *r, *best;
1178
  node *n;
1179
  int feasible, metric;
1180

1181 1182 1183 1184 1185
  if (msg->wildcard)
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
  else
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
	  &msg->net, msg->seqno, msg->metric);
1186

1187 1188
  nbr = babel_find_neighbor(ifa, msg->sender);
  if (!nbr)
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
  {
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
    return;
  }

  if (msg->router_id == p->router_id)
  {
    DBG("Babel: Ignoring update for our own router ID.\n");
    return;
  }

1200 1201 1202 1203 1204 1205 1206
  struct channel *c = (msg->net.type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
  if (!c || (c->channel_state != CS_UP))
  {
    DBG("Babel: Ignoring update for inactive address family.\n");
    return;
  }

1207
  /* Retraction */
1208
  if (msg->metric == BABEL_INFINITY)
1209
  {
1210
    if (msg->wildcard)
1211 1212 1213 1214 1215 1216 1217 1218
    {
      /*
       * Special case: This is a retraction of all prefixes announced by this
       * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
       */
      WALK_LIST(n, nbr->routes)
      {
	r = SKIP_BACK(struct babel_route, neigh_route, n);
1219
	babel_retract_route(p, r);
1220 1221 1222 1223
      }
    }
    else
    {
1224
      e = babel_find_entry(p, &msg->net);
1225 1226 1227 1228 1229 1230

      if (!e)
	return;

      /* The route entry indexed by neighbour */
      r = babel_find_route(e, nbr);
1231

1232 1233 1234
      if (!r)
	return;

1235 1236
      /* Router-id, next-hop and seqno are ignored for retractions */
      babel_retract_route(p, r);
1237 1238 1239
    }

    /* Done with retractions */
1240
    return;
1241
  }
1242

1243
  /* Regular update */
1244
  e = babel_get_entry(p, &msg->net);
1245
  r = babel_get_route(p, e, nbr); /* the route entry indexed by neighbour */
1246 1247
  s = babel_find_source(e, msg->router_id); /* for feasibility */
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1248
  metric = babel_compute_metric(nbr, msg->metric);
1249
  best = e->selected;
1250 1251 1252 1253

  /* RFC section 3.8.2.2 - Dealing with unfeasible updates */
  if (!feasible && (metric != BABEL_INFINITY) &&
      (!best || (r == best) || (metric < best->metric)))
1254
    babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr);
1255

1256 1257 1258
  /* Special case - ignore unfeasible update to best route */
  if (r == best && !feasible && (msg->router_id == r->router_id))
    return;
1259

1260 1261
  r->expires = current_time() + BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
  r->refresh_time = current_time() + BABEL_ROUTE_REFRESH_FACTOR(msg->interval);
1262

1263 1264 1265 1266 1267
  /* No further processing if there is no change */
  if ((r->feasible == feasible) && (r->seqno == msg->seqno) &&
      (r->metric == metric) && (r->advert_metric == msg->metric) &&
      (r->router_id == msg->router_id) && ipa_equal(r->next_hop, msg->next_hop))
    return;
1268

1269 1270 1271 1272 1273 1274 1275
  /* Last paragraph above - update the entry */
  r->feasible = feasible;
  r->seqno = msg->seqno;
  r->metric = metric;
  r->advert_metric = msg->metric;
  r->router_id = msg->router_id;
  r->next_hop = msg->next_hop;
1276

1277 1278 1279 1280 1281
  /* If received update satisfies seqno request, we send triggered updates */
  if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno))
  {
    babel_trigger_update(p);
    e->updated = current_time();
1282 1283
  }

1284
  babel_select_route(p, e, r);
1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302
}

void
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_route_request *msg = &m->route_request;

  /* RFC 6126 3.8.1.1 */

  /* Wildcard request - full update on the interface */
  if (msg->full)
  {
    TRACE(D_PACKETS, "Handling wildcard route request");
    ifa->want_triggered = 1;
    return;
  }

1303
  TRACE(D_PACKETS, "Handling route request for %N", &msg->net);
1304 1305 1306

  /* Non-wildcard request - see if we have an entry for the route.
     If not, send a retraction, otherwise send an update. */
1307
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1308 1309
  if (!e)
  {
1310
    babel_send_retraction(ifa, &msg->net);
1311 1312 1313 1314
  }
  else
  {
    babel_trigger_iface_update(ifa);
1315
    e->updated = current_time();
1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326
  }
}

void
babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_msg_seqno_request *msg = &m->seqno_request;

  /* RFC 6126 3.8.1.2 */

1327 1328
  TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d",
	&msg->net, msg->router_id, msg->seqno, msg->hop_count);
1329 1330

  /* Ignore if we have no such entry or entry has infinite metric */
1331
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1332
  if (!e || !e->valid || (e->metric == BABEL_INFINITY))
1333 1334 1335 1336
    return;

  /* Trigger update on incoming interface if we have a selected route with
     different router id or seqno no smaller than requested */
1337
  if ((e->router_id != msg->router_id) || ge_mod64k(e->seqno, msg->seqno))
1338 1339
  {
    babel_trigger_iface_update(ifa);
1340
    e->updated = current_time();
1341 1342 1343 1344 1345 1346
    return;
  }

  /* Seqno is larger; check if we own the router id */
  if (msg->router_id == p->router_id)
  {
1347 1348
    /* Ours; seqno increase and trigger global update */
    p->update_seqno_inc = 1;
1349 1350
    babel_trigger_update(p);
  }
1351
  else if (msg->hop_count > 1)
1352 1353
  {
    /* Not ours; forward if TTL allows it */
1354 1355 1356 1357

    /* Find best admissible route */
    struct babel_route *r, *best1 = NULL, *best2 = NULL;
    WALK_LIST(r, e->routes)
1358
      if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender))
1359 1360
      {
	/* Find best feasible route */
1361
	if ((!best1 || r->metric < best1->metric) && r->feasible)
1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374
	  best1 = r;

	/* Find best not necessary feasible route */
	if (!best2 || r->metric < best2->metric)
	  best2 = r;
      }

    /* If no route is found, do nothing */
    r = best1 ?: best2;
    if (!r)
      return;

    babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, r->neigh);
1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408
  }
}


/*
 *	Babel interfaces
 */

/**
 * babel_iface_timer - Babel interface timer handler
 * @t: Timer
 *
 * This function is called by the per-interface timer and triggers sending of
 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
 * and updates are simply handled by setting the next_{hello,regular} variables
 * on the interface, and triggering an update (and resetting the variable)
 * whenever 'now' exceeds that value.
 *
 * For triggered updates, babel_trigger_iface_update() will set the
 * want_triggered field on the interface to a timestamp value. If this is set
 * (and the next_triggered time has passed; this is a rate limiting mechanism),
 * babel_send_update() will be called with this timestamp as the second
 * parameter. This causes updates to be send consisting of only the routes that
 * have changed since the time saved in want_triggered.
 *
 * Mostly when an update is triggered, the route being modified will be set to
 * the value of 'now' at the time of the trigger; the >= comparison for
 * selecting which routes to send in the update will make sure this is included.
 */
static void
babel_iface_timer(timer *t)
{
  struct babel_iface *ifa = t->data;
  struct babel_proto *p = ifa->proto;
1409 1410 1411
  btime hello_period = ifa->cf->hello_interval;
  btime update_period = ifa->cf->update_interval;
  btime now_ = current_time();
1412

1413
  if (now_ >= ifa->next_hello)
1414
  {
1415
    babel_send_hello(ifa);
1416
    ifa->next_hello += hello_period * (1 + (now_ - ifa->next_hello) / hello_period);
1417 1418
  }

1419
  if (now_ >= ifa->next_regular)
1420 1421 1422
  {
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
    babel_send_update(ifa, 0);
1423
    ifa->next_regular += update_period * (1 + (now_ - ifa->next_regular) / update_period);
1424 1425 1426
    ifa->want_triggered = 0;
    p->triggered = 0;
  }
1427
  else if (ifa->want_triggered && (now_ >= ifa->next_triggered))
1428 1429 1430
  {
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
    babel_send_update(ifa, ifa->want_triggered);
1431
    ifa->next_triggered = now_ + MIN(1 S, update_period / 2);
1432 1433 1434 1435
    ifa->want_triggered = 0;
    p->triggered = 0;
  }

1436 1437
  btime next_event = MIN(ifa->next_hello, ifa->next_regular);
  if (ifa->want_triggered) next_event = MIN(next_event, ifa->next_triggered);
1438
  tm_set(ifa->timer, next_event);
1439 1440 1441 1442 1443
}

static inline void
babel_iface_kick_timer(struct babel_iface *ifa)
{
1444
  if (ifa->timer->expires > (current_time() + 100 MS))
1445
    tm_start(ifa->timer, 100 MS);
1446 1447 1448 1449 1450 1451 1452 1453 1454
}

static void
babel_iface_start(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;

  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);

1455 1456
  ifa->next_hello = current_time() + (random() % ifa->cf->hello_interval);
  ifa->next_regular = current_time() + (random() % ifa->cf->update_interval);
1457
  ifa->next_triggered = current_time() + MIN(1 S, ifa->cf->update_interval / 2);
1458
  ifa->want_triggered = 0;	/* We send an immediate update (below) */
1459
  tm_start(ifa->timer, 100 MS);
1460 1461
  ifa->up = 1;

1462
  babel_send_hello(ifa);
1463
  babel_send_wildcard_retraction(ifa);
1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487
  babel_send_wildcard_request(ifa);
  babel_send_update(ifa, 0);	/* Full update */
}

static void
babel_iface_stop(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;
  struct babel_neighbor *nbr;
  struct babel_route *r;
  node *n;

  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);

  /*
   * Rather than just flushing the neighbours, we set the metric of their routes
   * to infinity. This allows us to keep the neighbour hello state for when the
   * interface comes back up. The routes will also be kept until they expire.
   */
  WALK_LIST(nbr, ifa->neigh_list)
  {
    WALK_LIST(n, nbr->routes)
    {
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1488
      babel_retract_route(p, r);
1489 1490 1491
    }
  }

1492
  tm_stop(ifa->timer);
1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515
  ifa->up = 0;
}

static inline int
babel_iface_link_up(struct babel_iface *ifa)
{
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
}

static void
babel_iface_update_state(struct babel_iface *ifa)
{
  int up = ifa->sk && babel_iface_link_up(ifa);

  if (up == ifa->up)
    return;

  if (up)
    babel_iface_start(ifa);
  else
    babel_iface_stop(ifa);
}

1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530
static void
babel_iface_update_addr4(struct babel_iface *ifa)
{
  struct babel_proto *p = ifa->proto;

  ip_addr addr4 = ifa->iface->addr4 ? ifa->iface->addr4->ip : IPA_NONE;
  ifa->next_hop_ip4 = ipa_nonzero(ifa->cf->next_hop_ip4) ? ifa->cf->next_hop_ip4 : addr4;

  if (ipa_zero(ifa->next_hop_ip4) && p->ip4_channel)
    log(L_WARN "%s: Missing IPv4 next hop address for %s", p->p.name, ifa->ifname);

  if (ifa->up)
    babel_iface_kick_timer(ifa);
}

1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590
static void
babel_iface_update_buffers(struct babel_iface *ifa)
{
  if (!ifa->sk)
    return;

  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
  uint rbsize = ifa