babel.c 60.2 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,
Jan Moskyto Matejka's avatar
Jan Moskyto Matejka committed
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 850
  TRACE(D_PACKETS, "Sending route request for %N to %I",
        e->n.addr, n->addr);
851 852

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

855
  babel_send_unicast(&msg, n->ifa, n->addr);
856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873
}

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

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

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

  babel_enqueue(&msg, ifa);
}

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

  msg.type = BABEL_TLV_SEQNO_REQUEST;
879 880 881
  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;
882
  net_copy(&msg.seqno_request.net, e->n.addr);
883

884 885 886 887
  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);
888

889 890 891 892 893 894
    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);
895

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

/**
 * 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
913
babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable)
914 915 916
{
  struct babel_proto *p = ifa->proto;

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

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

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

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

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

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

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

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

959 960 961
    babel_enqueue(&msg, ifa);

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

      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;
      }
973 974 975 976 977
    }
  }
  FIB_WALK_END;
}

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

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

987 988 989 990 991 992 993 994 995 996 997 998
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);

999
  ifa->want_triggered = current_time();
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018
  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
1019
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
1020 1021 1022 1023
{
  struct babel_proto *p = ifa->proto;
  union babel_msg msg = {};

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

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

  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;
1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058

  babel_enqueue(&msg, ifa);
}


/*
 *	TLV handler helpers
 */

/* Update hello history according to Appendix A1 of the RFC */
static void
1059
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
{
  /*
   * 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);

1070
  if ((delta == 0) || (n->hello_cnt == 0))
1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096
  {
    /* 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++;
1097 1098

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


/*
 *	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;

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

  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;

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

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

1132
  babel_update_hello_history(n, msg->seqno, msg->interval);
1133 1134 1135 1136
  babel_update_cost(n);

  /* Speed up session establishment by sending IHU immediately */
  if (first_hello)
1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149
    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;

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

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

/**
 * 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;

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

1183 1184 1185 1186 1187
  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);
1188

1189 1190
  nbr = babel_find_neighbor(ifa, msg->sender);
  if (!nbr)
1191 1192 1193 1194 1195 1196 1197