Revision 3b3b0910

View differences:

nest/route.h
236 236
#endif
237 237
#ifdef CONFIG_BABEL
238 238
    struct {
239
      u16 seqno;			/* Babel seqno */
239 240
      u16 metric;			/* Babel metric */
240 241
      u64 router_id;			/* Babel router id */
241 242
    } babel;
proto/babel/babel.c
2 2
 *	BIRD -- The Babel protocol
3 3
 *
4 4
 *	Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
5 7
 *
6 8
 *	Can be freely distributed and used under the terms of the GNU GPL.
7 9
 *
......
29 31
 *
30 32
 * The main route selection is done in babel_select_route(). This is called when
31 33
 * an entry is updated by receiving updates from the network or when modified by
32
 * internal timers. It performs feasibility checks on the available routes for
33
 * the prefix and selects the one with the lowest metric to be announced to the
34
 * core.
34
 * internal timers. The function selects from feasible and reachable routes the
35
 * one with the lowest metric to be announced to the core.
35 36
 */
36 37

  
37 38
#include <stdlib.h>
38 39
#include "babel.h"
39 40

  
40 41

  
41
#define OUR_ROUTE(r) (r->neigh == NULL)
42

  
43 42
/*
44 43
 * Is one number greater or equal than another mod 2^16? This is based on the
45 44
 * definition of serial number space in RFC 1982. Note that arguments are of
......
49 48
{ return (u16)(a - b) < 0x8000; }
50 49

  
51 50
static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e);
52
static void babel_select_route(struct babel_proto *p, struct babel_entry *e);
51
static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod);
52
static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e);
53 53
static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n);
54 54
static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr);
55 55
static void babel_update_cost(struct babel_neighbor *n);
......
161 161

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

  
164 165
  r->e = e;
166
  r->neigh = nbr;
165 167
  add_tail(&e->routes, NODE r);
166

  
167
  if (nbr)
168
  {
169
    r->neigh = nbr;
170
    r->expires = current_time() + BABEL_GARBAGE_INTERVAL;
171
    add_tail(&nbr->routes, NODE &r->neigh_route);
172
  }
168
  add_tail(&nbr->routes, NODE &r->neigh_route);
173 169

  
174 170
  return r;
175 171
}
176 172

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

  
178
  if (r == r->e->selected)
179
    babel_select_route(p, r->e, r);
180
}
181

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

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

  
185
  if (r->neigh)
186
    rem_node(&r->neigh_route);
187

  
188
  if (r->e->selected_in == r)
189
    r->e->selected_in = NULL;
190

  
191
  if (r->e->selected_out == r)
192
    r->e->selected_out = NULL;
191
  if (r->e->selected == r)
192
    r->e->selected = NULL;
193 193

  
194 194
  sl_free(p->route_slab, r);
195 195
}
......
197 197
static void
198 198
babel_expire_route(struct babel_proto *p, struct babel_route *r)
199 199
{
200
  struct babel_entry *e = r->e;
200
  struct babel_config *cf = (void *) p->p.cf;
201 201

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

  
205 205
  if (r->metric < BABEL_INFINITY)
206 206
  {
207 207
    r->metric = r->advert_metric = BABEL_INFINITY;
208
    r->expires = current_time() + r->expiry_interval;
208
    r->expires = current_time() + cf->hold_time;
209 209
  }
210 210
  else
211 211
  {
......
216 216
static void
217 217
babel_refresh_route(struct babel_proto *p, struct babel_route *r)
218 218
{
219
  if (!OUR_ROUTE(r) && (r == r->e->selected_in))
219
  if (r == r->e->selected)
220 220
    babel_send_route_request(p, r->e, r->neigh);
221 221

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

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

  
......
255 256
       * synchronous events babel_select_route() -> nest table change ->
256 257
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
257 258
       */
259
      FIB_ITERATE_PUT(&fit);
260
      babel_select_route(p, e, NULL);
261
      goto loop;
262
    }
263

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

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

  
......
265 277
    babel_expire_requests(p, e);
266 278

  
267 279
    /* Remove empty entries */
268
    if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes) && EMPTY_LIST(e->requests))
280
    if (!e->valid && EMPTY_LIST(e->routes) && EMPTY_LIST(e->sources) && EMPTY_LIST(e->requests))
269 281
    {
270 282
      FIB_ITERATE_PUT(&fit);
271 283
      fib_delete(rtable, e);
......
425 437
static void
426 438
babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr)
427 439
{
440
  struct babel_route *r;
428 441
  node *n;
429 442

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

  
432 445
  WALK_LIST_FIRST(n, nbr->routes)
433 446
  {
434
    struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n);
435
    struct babel_entry *e = r->e;
436
    int selected = (r == e->selected_in);
437

  
447
    r = SKIP_BACK(struct babel_route, neigh_route, n);
448
    babel_retract_route(p, r);
438 449
    babel_flush_route(p, r);
439

  
440
    if (selected)
441
      babel_select_route(p, e);
442 450
  }
443 451

  
444 452
  nbr->ifa = NULL;
......
600 608
    WALK_LIST2(r, n, nbr->routes, neigh_route)
601 609
    {
602 610
      r->metric = babel_compute_metric(nbr, r->advert_metric);
603
      babel_select_route(p, r->e);
611
      babel_select_route(p, r->e, r);
604 612
    }
605 613
  }
606 614
}
......
611 619
 * @e: Babel route entry to announce
612 620
 *
613 621
 * This function announces a Babel entry to the core if it has a selected
614
 * incoming path, and retracts it otherwise. If the selected entry has infinite
615
 * metric, the route is announced as unreachable.
622
 * incoming path, and retracts it otherwise. If there is no selected route but
623
 * the entry is valid and ours, the unreachable route is announced instead.
616 624
 */
617 625
static void
618 626
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
619 627
{
620
  struct babel_route *r = e->selected_in;
628
  struct babel_route *r = e->selected;
621 629
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
622 630

  
623 631
  if (r)
624 632
  {
625
    rta *ap0 = allocz(RTA_MAX_SIZE);
626
    *ap0 = (rta) {
633
    rta a0 = {
627 634
      .src = p->p.main_source,
628 635
      .source = RTS_BABEL,
629 636
      .scope = SCOPE_UNIVERSE,
630
      .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_UNICAST,
637
      .dest = RTD_UNICAST,
631 638
      .from = r->neigh->addr,
639
      .nh.gw = r->next_hop,
632 640
      .nh.iface = r->neigh->ifa->iface,
633 641
    };
634 642

  
635
    if (r->metric < BABEL_INFINITY)
636
      ap0->nh.gw = r->next_hop;
637

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

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

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

  
669
    e->unreachable = 1;
645 670
    rte_update2(c, e->n.addr, rte, p->p.main_source);
646 671
  }
647 672
  else
648 673
  {
649 674
    /* Retraction */
675
    e->unreachable = 0;
650 676
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
651 677
  }
652 678
}
653 679

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

  
689

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

  
675
  /* try to find the best feasible route */
676
  WALK_LIST(r, e->routes)
677
    if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */
678
	(!cur || r->metric < cur->metric) &&
679
        babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
680
      cur = r;
681

  
682
  if (cur && !OUR_ROUTE(cur) && (cur->metric < BABEL_INFINITY) &&
683
      (!best || (cur->metric < best->metric) || ((cur == best) && (cur->metric != cur->old_metric))))
723
  /* Shortcut if only non-best was modified */
724
  if (mod && (mod != best))
684 725
  {
685
    if (cur != best)
686
      TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
687
	    e->n.addr, cur->router_id, cur->metric);
688

  
689
    e->selected_in = cur;
690
    e->updated = current_time();
691
    babel_announce_rte(p, e);
726
    /* Either select modified route, or keep old best route */
727
    if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible)
728
      best = mod;
729
    else
730
      return;
692 731
  }
693
  else if (!cur || cur->metric == BABEL_INFINITY)
732
  else
694 733
  {
695
    /* Couldn't find a feasible route. If we have a selected route, that means
696
       it just became infeasible; so set it's metric to infinite and install it
697
       (as unreachable), then send a seqno request.
698

  
699
       babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
700
    if (best)
701
    {
702
      TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr);
703

  
704
      best->metric = best->advert_metric = BABEL_INFINITY;
705
      e->updated = current_time();
734
    /* Selected route may be modified and no longer admissible */
735
    if (!best || (best->metric == BABEL_INFINITY) || !best->feasible)
736
      best = NULL;
706 737

  
707
      babel_add_seqno_request(p, e, best->router_id, best->seqno + 1, 0, NULL);
708
      babel_announce_rte(p, e);
738
    /* Find the best feasible route from all routes */
739
    WALK_LIST(r, e->routes)
740
      if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible)
741
	best = r;
742
  }
709 743

  
710
      /* Section 3.6 of the RFC forbids an infeasible from being selected. This
711
	 is cleared after announcing the route to the core to make sure an
712
	 unreachable route is propagated first. */
713
      e->selected_in = NULL;
714
    }
715
    else
716
    {
717
      /* No route currently selected, and no new one selected; this means we
718
	 don't have a route to this destination anymore (and were probably
719
	 called from an expiry timer). Remove the route from the nest. */
720
      // TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
744
  if (best)
745
  {
746
    if (best != e->selected)
747
      TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d",
748
	    e->n.addr, best->router_id, best->metric);
749
  }
750
  else if (e->selected)
751
  {
752
    /*
753
     * We have lost all feasible routes. We have to broadcast seqno request
754
     * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8).
755
     * The later is done automatically by babel_announce_rte().
756
     */
721 757

  
722
      e->selected_in = NULL;
723
      e->updated = current_time();
724
      babel_announce_rte(p, e);
725
    }
758
    TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr);
759
    if (e->valid && (e->selected->router_id == e->router_id))
760
      babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL);
726 761
  }
762
  else
763
    return;
764

  
765
  e->selected = best;
766
  babel_announce_rte(p, e);
727 767
}
728 768

  
729 769
/*
......
883 923

  
884 924
  FIB_WALK(rtable, struct babel_entry, e)
885 925
  {
886
    struct babel_route *r = e->selected_out;
887

  
888
    if (!r)
926
    if (!e->valid)
889 927
      continue;
890 928

  
891 929
    /* Our own seqno might have changed, in which case we update the routes we
892 930
       originate. */
893
    if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno))
931
    if ((e->router_id == p->router_id) && (e->seqno < p->update_seqno))
894 932
    {
895
      r->seqno = p->update_seqno;
933
      e->seqno = p->update_seqno;
896 934
      e->updated = current_time();
897 935
    }
898 936

  
......
901 939
      continue;
902 940

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

  
906 944
    union babel_msg msg = {};
907 945
    msg.type = BABEL_TLV_UPDATE;
908 946
    msg.update.interval = ifa->cf->update_interval;
909
    msg.update.seqno = r->seqno;
910
    msg.update.metric = r->metric;
911
    msg.update.router_id = r->router_id;
947
    msg.update.seqno = e->seqno;
948
    msg.update.metric = e->metric;
949
    msg.update.router_id = e->router_id;
912 950
    net_copy(&msg.update.net, e->n.addr);
913 951

  
914 952
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
......
917 955
    babel_enqueue(&msg, ifa);
918 956

  
919 957
    /* Update feasibility distance for redistributed routes */
920
    if (!OUR_ROUTE(r))
958
    if (e->router_id != p->router_id)
921 959
    {
922
      struct babel_source *s = babel_get_source(p, e, r->router_id);
960
      struct babel_source *s = babel_get_source(p, e, e->router_id);
923 961
      s->expires = current_time() + BABEL_GARBAGE_INTERVAL;
924 962

  
925 963
      if ((msg.update.seqno > s->seqno) ||
......
1164 1202
    return;
1165 1203
  }
1166 1204

  
1167
  /*
1168
   * RFC section 3.5.4:
1169
   *
1170
   * When a Babel node receives an update (id, prefix, seqno, metric) from a
1171
   * neighbour neigh with a link cost value equal to cost, it checks whether it
1172
   * already has a routing table entry indexed by (neigh, id, prefix).
1173
   *
1174
   * If no such entry exists:
1175
   *
1176
   * o if the update is unfeasible, it is ignored;
1177
   *
1178
   * o if the metric is infinite (the update is a retraction), the update is
1179
   *   ignored;
1180
   *
1181
   * o otherwise, a new route table entry is created, indexed by (neigh, id,
1182
   *   prefix), with seqno equal to seqno and an advertised metric equal to the
1183
   *   metric carried by the update.
1184
   *
1185
   * If such an entry exists:
1186
   *
1187
   * o if the entry is currently installed and the update is unfeasible, then
1188
   *   the behaviour depends on whether the router-ids of the two entries match.
1189
   *   If the router-ids are different, the update is treated as though it were
1190
   *   a retraction (i.e., as though the metric were FFFF hexadecimal). If the
1191
   *   router-ids are equal, the update is ignored;
1192
   *
1193
   * o otherwise (i.e., if either the update is feasible or the entry is not
1194
   *   currently installed), then the entry's sequence number, advertised
1195
   *   metric, metric, and router-id are updated and, unless the advertised
1196
   *   metric is infinite, the route's expiry timer is reset to a small multiple
1197
   *   of the Interval value included in the update.
1198
   */
1199

  
1200 1205
  /* Retraction */
1201 1206
  if (msg->metric == BABEL_INFINITY)
1202 1207
  {
......
1209 1214
      WALK_LIST(n, nbr->routes)
1210 1215
      {
1211 1216
	r = SKIP_BACK(struct babel_route, neigh_route, n);
1212
	r->metric = r->advert_metric = BABEL_INFINITY;
1213
	babel_select_route(p, r->e);
1217
	babel_retract_route(p, r);
1214 1218
      }
1215 1219
    }
1216 1220
    else
......
1226 1230
      if (!r)
1227 1231
	return;
1228 1232

  
1229
      r->metric = r->advert_metric = BABEL_INFINITY;
1230
      babel_select_route(p, e);
1233
      /* Router-id, next-hop and seqno are ignored for retractions */
1234
      babel_retract_route(p, r);
1231 1235
    }
1232 1236

  
1233 1237
    /* Done with retractions */
1234 1238
    return;
1235 1239
  }
1236 1240

  
1241
  /* Regular update */
1237 1242
  e = babel_get_entry(p, &msg->net);
1238
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1243
  r = babel_get_route(p, e, nbr); /* the route entry indexed by neighbour */
1239 1244
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1240 1245
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1241 1246
  metric = babel_compute_metric(nbr, msg->metric);
1242
  best = e->selected_in;
1247
  best = e->selected;
1243 1248

  
1244 1249
  /* RFC section 3.8.2.2 - Dealing with unfeasible updates */
1245 1250
  if (!feasible && (metric != BABEL_INFINITY) &&
1246 1251
      (!best || (r == best) || (metric < best->metric)))
1247 1252
    babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr);
1248 1253

  
1249
  if (!r)
1250
  {
1251
    if (!feasible)
1252
      return;
1253

  
1254
    r = babel_get_route(p, e, nbr);
1255
    r->advert_metric = msg->metric;
1256
    r->router_id = msg->router_id;
1257
    r->metric = metric;
1258
    r->next_hop = msg->next_hop;
1259
    r->seqno = msg->seqno;
1260
  }
1261
  else if (r == best && !feasible)
1262
  {
1263
    /* Penultimate paragraph above - ignore or retract */
1264
    if (msg->router_id == r->router_id)
1265
      return;
1254
  /* Special case - ignore unfeasible update to best route */
1255
  if (r == best && !feasible && (msg->router_id == r->router_id))
1256
    return;
1266 1257

  
1267
    /* Treat as retraction */
1268
    r->metric = r->advert_metric = BABEL_INFINITY;
1269
  }
1270
  else
1271
  {
1272
    /* Last paragraph above - update the entry */
1273
    r->advert_metric = msg->metric;
1274
    r->metric = metric;
1275
    r->next_hop = msg->next_hop;
1258
  r->expires = current_time() + BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1259
  r->refresh_time = current_time() + BABEL_ROUTE_REFRESH_FACTOR(msg->interval);
1276 1260

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

  
1280
    r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1281
    r->expires = current_time() + r->expiry_interval;
1282
    if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
1283
      r->refresh_time = current_time() + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
1267
  /* Last paragraph above - update the entry */
1268
  r->feasible = feasible;
1269
  r->seqno = msg->seqno;
1270
  r->metric = metric;
1271
  r->advert_metric = msg->metric;
1272
  r->router_id = msg->router_id;
1273
  r->next_hop = msg->next_hop;
1284 1274

  
1285
    /* If received update satisfies seqno request, we send triggered updates */
1286
    if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno))
1287
    {
1288
      babel_trigger_update(p);
1289
      e->updated = current_time();
1290
    }
1275
  /* If received update satisfies seqno request, we send triggered updates */
1276
  if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno))
1277
  {
1278
    babel_trigger_update(p);
1279
    e->updated = current_time();
1291 1280
  }
1292 1281

  
1293
  babel_select_route(p, e);
1282
  babel_select_route(p, e, r);
1294 1283
}
1295 1284

  
1296 1285
void
......
1338 1327

  
1339 1328
  /* Ignore if we have no such entry or entry has infinite metric */
1340 1329
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1341
  if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
1330
  if (!e || !e->valid || (e->metric == BABEL_INFINITY))
1342 1331
    return;
1343 1332

  
1344 1333
  /* Trigger update on incoming interface if we have a selected route with
1345 1334
     different router id or seqno no smaller than requested */
1346
  struct babel_route *r = e->selected_out;
1347
  if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno))
1335
  if ((e->router_id != msg->router_id) || ge_mod64k(e->seqno, msg->seqno))
1348 1336
  {
1349 1337
    babel_trigger_iface_update(ifa);
1350 1338
    e->updated = current_time();
......
1365 1353
    /* Find best admissible route */
1366 1354
    struct babel_route *r, *best1 = NULL, *best2 = NULL;
1367 1355
    WALK_LIST(r, e->routes)
1368
      if ((r->router_id == msg->router_id) && r->neigh && !ipa_equal(r->neigh->addr, msg->sender))
1356
      if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender))
1369 1357
      {
1370 1358
	/* Find best feasible route */
1371
	if (babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric) &&
1372
	    (!best1 || r->metric < best1->metric))
1359
	if ((!best1 || r->metric < best1->metric) && r->feasible)
1373 1360
	  best1 = r;
1374 1361

  
1375 1362
	/* Find best not necessary feasible route */
......
1483 1470
  struct babel_neighbor *nbr;
1484 1471
  struct babel_route *r;
1485 1472
  node *n;
1486
  btime now_ = current_time();
1487 1473

  
1488 1474
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1489 1475

  
......
1497 1483
    WALK_LIST(n, nbr->routes)
1498 1484
    {
1499 1485
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1500
      r->metric = r->advert_metric = BABEL_INFINITY;
1501
      r->expires = now_ + r->expiry_interval;
1502

  
1503
      if (r == r->e->selected_in)
1504
	babel_select_route(p, r->e);
1486
      babel_retract_route(p, r);
1505 1487
    }
1506 1488
  }
1507 1489

  
......
1777 1759
babel_dump_route(struct babel_route *r)
1778 1760
{
1779 1761
  debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %t\n",
1780
	r->neigh ? r->neigh->addr : IPA_NONE,
1781
        r->neigh ? r->neigh->ifa->ifname : "(none)",
1782
        r->seqno, r->advert_metric, r->metric, r->router_id,
1783
	r->expires ? r->expires - current_time() : 0);
1762
	r->neigh->addr, r->neigh->ifa->ifname, r->seqno, r->advert_metric, r->metric,
1763
	r->router_id, r->expires ? r->expires - current_time() : 0);
1784 1764
}
1785 1765

  
1786 1766
static void
......
1797 1777
  WALK_LIST(r,e->routes)
1798 1778
  {
1799 1779
    debug(" ");
1800
    if (r == e->selected_out) debug("*");
1801
    if (r == e->selected_in) debug("+");
1780
    if (r == e->selected) debug("*");
1802 1781
    babel_dump_route(r);
1803 1782
  }
1804 1783
}
......
1956 1935
}
1957 1936

  
1958 1937
static void
1959
babel_show_entries_(struct babel_proto *p, struct fib *rtable)
1938
babel_show_entries_(struct babel_proto *p UNUSED, struct fib *rtable)
1960 1939
{
1961
  struct babel_source *s = NULL;
1962
  struct babel_route *r = NULL;
1963

  
1964
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1965

  
1966 1940
  FIB_WALK(rtable, struct babel_entry, e)
1967 1941
  {
1968
    r = e->selected_in ? e->selected_in : e->selected_out;
1942
    struct babel_route *r = NULL;
1943
    uint rts = 0, srcs = 0;
1944
    node *n;
1969 1945

  
1970
    int srcs = 0;
1971
    WALK_LIST(s, e->sources)
1972
      srcs++;
1946
    WALK_LIST(n, e->routes)
1947
      rts++;
1973 1948

  
1974
    if (r)
1975
    {
1976
      if (r->router_id == p->router_id)
1977
        bsprintf(ridbuf, "%s", "<self>");
1978
      else
1979
        bsprintf(ridbuf, "%lR", r->router_id);
1949
    WALK_LIST(n, e->sources)
1950
      srcs++;
1980 1951

  
1981
      btime time = r->expires ? r->expires - current_time() : 0;
1982
      cli_msg(-1025, "%-29N %-23s %6u %5u %7t %7u",
1983
	      e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
1984
    }
1952
    if (e->valid)
1953
      cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u",
1954
	      e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs);
1955
    else if (r = e->selected)
1956
      cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u",
1957
	      e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs);
1985 1958
    else
1986
    {
1987
      cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs);
1988
    }
1959
      cli_msg(-1025, "%-24N %-23s %6s %5s %7u %7u",
1960
	      e->n.addr, "<none>", "-", "-", rts, srcs);
1989 1961
  }
1990 1962
  FIB_WALK_END;
1991 1963
}
......
2003 1975
  }
2004 1976

  
2005 1977
  cli_msg(-1025, "%s:", p->p.name);
2006
  cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
2007
	  "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
1978
  cli_msg(-1025, "%-24s %-23s %6s %5s %7s %7s",
1979
	  "Prefix", "Router ID", "Metric", "Seqno", "Routes", "Sources");
2008 1980

  
2009 1981
  babel_show_entries_(p, &p->ip4_rtable);
2010 1982
  babel_show_entries_(p, &p->ip6_rtable);
......
2012 1984
  cli_msg(0, "");
2013 1985
}
2014 1986

  
1987
static void
1988
babel_show_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
1989
{
1990
  FIB_WALK(rtable, struct babel_entry, e)
1991
  {
1992
    struct babel_route *r;
1993
    WALK_LIST(r, e->routes)
1994
    {
1995
      char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' ');
1996
      btime time = r->expires ? r->expires - current_time() : 0;
1997
      cli_msg(-1025, "%-24N %-25I %-10s %5u %c %5u %7t",
1998
	      e->n.addr, r->next_hop, r->neigh->ifa->ifname,
1999
	      r->metric, c, r->seqno, MAX(time, 0));
2000
    }
2001
  }
2002
  FIB_WALK_END;
2003
}
2004

  
2005
void
2006
babel_show_routes(struct proto *P)
2007
{
2008
  struct babel_proto *p = (void *) P;
2009

  
2010
  if (p->p.proto_state != PS_UP)
2011
  {
2012
    cli_msg(-1025, "%s: is not up", p->p.name);
2013
    cli_msg(0, "");
2014
    return;
2015
  }
2016

  
2017
  cli_msg(-1025, "%s:", p->p.name);
2018
  cli_msg(-1025, "%-24s %-25s %-9s %6s F %5s %7s",
2019
	  "Prefix", "Nexthop", "Interface", "Metric", "Seqno", "Expires");
2020

  
2021
  babel_show_routes_(p, &p->ip4_rtable);
2022
  babel_show_routes_(p, &p->ip6_rtable);
2023

  
2024
  cli_msg(0, "");
2025
}
2026

  
2015 2027

  
2016 2028
/*
2017 2029
 *	Babel protocol glue
......
2069 2081

  
2070 2082

  
2071 2083
static int
2072
babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool)
2084
babel_import_control(struct proto *P, struct rte **new, struct ea_list **attrs, struct linpool *pool)
2073 2085
{
2074 2086
  struct babel_proto *p = (void *) P;
2087
  rte *rt = *new;
2088

  
2089
  /* Reject our own unreachable routes */
2090
  if ((rt->attrs->dest == RTD_UNREACHABLE) && (rt->attrs->src->proto == P))
2091
    return -1;
2092

  
2075 2093

  
2076 2094
  /* Prepare attributes with initial values */
2077
  if ((*rt)->attrs->source != RTS_BABEL)
2095
  if (rt->attrs->source != RTS_BABEL)
2078 2096
    *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
2079 2097

  
2080 2098
  return 0;
......
2102 2120
{
2103 2121
  struct babel_proto *p = (void *) P;
2104 2122
  struct babel_entry *e;
2105
  struct babel_route *r;
2106 2123

  
2107 2124
  if (new)
2108 2125
  {
2109 2126
    /* Update */
2110
    e = babel_get_entry(p, net->n.addr);
2127
    uint internal = (new->attrs->src->proto == P);
2128
    uint rt_seqno = internal ? new->u.babel.seqno : p->update_seqno;
2129
    uint rt_metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
2130
    uint rt_router_id = internal ? new->u.babel.router_id : p->router_id;
2111 2131

  
2112
    if (new->attrs->src->proto != P)
2132
    if (rt_metric > BABEL_INFINITY)
2113 2133
    {
2114
      r = babel_get_route(p, e, NULL);
2115
      r->seqno = p->update_seqno;
2116
      r->router_id = p->router_id;
2117
      r->metric = 0;	/* FIXME: should be selectable */
2134
      log(L_WARN "%s: Invalid babel_metric value %u for route %N",
2135
	  p->p.name, rt_metric, net->n.addr);
2136
      rt_metric = BABEL_INFINITY;
2118 2137
    }
2119
    else
2120
      r = e->selected_in;
2121 2138

  
2122
    if (r != e->selected_out)
2139
    e = babel_get_entry(p, net->n.addr);
2140

  
2141
    /* Activate triggered updates */
2142
    if ((e->valid |= BABEL_ENTRY_VALID) ||
2143
	(e->router_id != rt_router_id))
2123 2144
    {
2124 2145
      babel_trigger_update(p);
2125 2146
      e->updated = current_time();
2126
      e->selected_out = r;
2127 2147
    }
2148

  
2149
    e->valid = BABEL_ENTRY_VALID;
2150
    e->seqno = rt_seqno;
2151
    e->metric = rt_metric;
2152
    e->router_id = rt_router_id;
2128 2153
  }
2129 2154
  else
2130 2155
  {
2131 2156
    /* Withdraw */
2132 2157
    e = babel_find_entry(p, net->n.addr);
2133
    if (!e || !e->selected_out)
2158

  
2159
    if (!e || e->valid != BABEL_ENTRY_VALID)
2134 2160
      return;
2135 2161

  
2136
    if (OUR_ROUTE(e->selected_out))
2137
    {
2138
      /*
2139
       * We originate this route, so set its metric to infinity and set an
2140
       * expiry time. This causes a retraction to be sent, and later the route
2141
       * to be flushed once the hold time has passed.
2142
       */
2143
      babel_trigger_update(p);
2144
      e->updated = current_time();
2145
      e->selected_out->metric = BABEL_INFINITY;
2146
      e->selected_out->expires = current_time() + BABEL_HOLD_TIME;
2147
    }
2148
    else
2149
    {
2150
      /*
2151
       * This is a route originating from someone else that was lost; presumably
2152
       * because an export filter was updated to filter it. This means we can't
2153
       * set the metric to infinity (it would be overridden on subsequent
2154
       * updates from the peer originating the route), so just clear the
2155
       * exported route.
2156
       *
2157
       * This causes peers to expire the route after a while (like if we just
2158
       * shut down), but it's the best we can do in these circumstances; and
2159
       * since export filters presumably aren't updated that often this is
2160
       * acceptable.
2161
       */
2162
      e->selected_out = NULL;
2163
    }
2162
    e->valid = BABEL_ENTRY_STALE;
2163
    e->metric = BABEL_INFINITY;
2164

  
2165
    babel_trigger_update(p);
2166
    e->updated = current_time();
2164 2167
  }
2165 2168
}
2166 2169

  
......
2173 2176
static int
2174 2177
babel_rte_same(struct rte *new, struct rte *old)
2175 2178
{
2176
  return ((new->u.babel.router_id == old->u.babel.router_id) &&
2177
          (new->u.babel.metric == old->u.babel.metric));
2179
  return ((new->u.babel.seqno == old->u.babel.seqno) &&
2180
	  (new->u.babel.metric == old->u.babel.metric) &&
2181
	  (new->u.babel.router_id == old->u.babel.router_id));
2178 2182
}
2179 2183

  
2180 2184

  
proto/babel/babel.h
2 2
 *	BIRD -- The Babel protocol
3 3
 *
4 4
 *	Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
5 7
 *
6 8
 *	Can be freely distributed and used under the terms of the GNU GPL.
7 9
 *
......
37 39
#define BABEL_HELLO_LIMIT		12
38 40
#define BABEL_UPDATE_INTERVAL_FACTOR	4
39 41
#define BABEL_IHU_INTERVAL_FACTOR	3
42
#define BABEL_HOLD_TIME_FACTOR		4	/* How long we keep unreachable route relative to update interval */
40 43
#define BABEL_IHU_EXPIRY_FACTOR(X)	((btime)(X)*7/2)	/* 3.5 */
41 44
#define BABEL_HELLO_EXPIRY_FACTOR(X)	((btime)(X)*3/2)	/* 1.5 */
42 45
#define BABEL_ROUTE_EXPIRY_FACTOR(X)	((btime)(X)*7/2)	/* 3.5 */
43
#define BABEL_ROUTE_REFRESH_INTERVAL	(2 S_)	/* Time before route expiry to send route request */
44
#define BABEL_HOLD_TIME			(10 S_)	/* Expiry time for our own routes */
46
#define BABEL_ROUTE_REFRESH_FACTOR(X)	((btime)(X)*5/2)	/* 2.5 */
45 47
#define BABEL_SEQNO_REQUEST_RETRY	4
46 48
#define BABEL_SEQNO_REQUEST_EXPIRY	(2 S_)
47 49
#define BABEL_GARBAGE_INTERVAL		(300 S_)
......
105 107

  
106 108
struct babel_config {
107 109
  struct proto_config c;
108

  
109
  list iface_list;              /* Patterns configured -- keep it first; see babel_reconfigure why */
110
  list iface_list;			/* List of iface configs (struct babel_iface_config) */
111
  uint hold_time;			/* Time to hold stale entries and unreachable routes */
110 112
};
111 113

  
112 114
struct babel_iface_config {
......
220 222
  struct babel_entry    *e;
221 223
  struct babel_neighbor *neigh;
222 224

  
225
  u8 feasible;
223 226
  u16 seqno;
224
  u16 advert_metric;
225 227
  u16 metric;
226
  u16 old_metric;
228
  u16 advert_metric;
227 229
  u64 router_id;
228 230
  ip_addr next_hop;
229 231
  btime refresh_time;
230 232
  btime expires;
231
  btime expiry_interval;
232 233
};
233 234

  
234 235
struct babel_seqno_request {
......
242 243
};
243 244

  
244 245
struct babel_entry {
245
  struct babel_route *selected_in;
246
  struct babel_route *selected_out;
246
  struct babel_route *selected;
247 247

  
248
  btime updated;
249

  
250
  list requests;
251
  list sources;				/* Source entries for this prefix (struct babel_source). */
252 248
  list routes;				/* Routes for this prefix (struct babel_route) */
249
  list sources;				/* Source entries for this prefix (struct babel_source). */
250
  list requests;
251

  
252
  u8 valid;				/* Entry validity state (BABEL_ENTRY_*) */
253
  u8 unreachable;			/* Unreachable route is announced */
254
  u16 seqno;				/* Outgoing seqno */
255
  u16 metric;				/* Outgoing metric */
256
  u64 router_id;			/* Outgoing router ID */
257
  btime updated;			/* Last change of outgoing rte, for triggered updates */
253 258

  
254 259
  struct fib_node n;
255 260
};
256 261

  
257
/* Stores forwarded seqno requests for duplicate suppression. */
262
#define BABEL_ENTRY_DUMMY	0	/* No outgoing route */
263
#define BABEL_ENTRY_VALID	1	/* Valid outgoing route */
264
#define BABEL_ENTRY_STALE	2	/* Stale outgoing route, waiting for GC */
258 265

  
259 266

  
260 267
/*
......
346 353
void babel_show_interfaces(struct proto *P, char *iff);
347 354
void babel_show_neighbors(struct proto *P, char *iff);
348 355
void babel_show_entries(struct proto *P);
356
void babel_show_routes(struct proto *P);
349 357

  
350 358
/* packets.c */
351 359
void babel_enqueue(union babel_msg *msg, struct babel_iface *ifa);
proto/babel/config.Y
2 2
 *	BIRD -- Babel Configuration
3 3
 *
4 4
 *	Copyright (c) 2015-2016 Toke Hoiland-Jorgensen
5
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
5 7
 *
6 8
 *	Can be freely distributed and used under the terms of the GNU GPL.
7 9
 */
......
32 34
{
33 35
  this_proto = proto_config_new(&proto_babel, $1);
34 36
  init_list(&BABEL_CFG->iface_list);
37
  BABEL_CFG->hold_time = 1 S_;
35 38
};
36 39

  
37 40
babel_proto_item:
......
84 87
  if (!BABEL_IFACE->update_interval)
85 88
    BABEL_IFACE->update_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR, BABEL_MAX_INTERVAL);
86 89
  BABEL_IFACE->ihu_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_IHU_INTERVAL_FACTOR, BABEL_MAX_INTERVAL);
90

  
91
  BABEL_CFG->hold_time = MAX_(BABEL_CFG->hold_time, BABEL_IFACE->update_interval*BABEL_HOLD_TIME_FACTOR);
87 92
};
88 93

  
89 94

  
......
131 136
CF_CLI(SHOW BABEL ENTRIES, optsym opttext, [<name>], [[Show information about Babel prefix entries]])
132 137
{ babel_show_entries(proto_get_named($4, &proto_babel)); };
133 138

  
139
CF_CLI(SHOW BABEL ROUTES, optsym opttext, [<name>], [[Show information about Babel route entries]])
140
{ babel_show_routes(proto_get_named($4, &proto_babel)); };
141

  
134 142
CF_CODE
135 143

  
136 144
CF_END
proto/babel/packets.c
2 2
 *	BIRD -- The Babel protocol
3 3
 *
4 4
 *	Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
5 7
 *
6 8
 *	Can be freely distributed and used under the terms of the GNU GPL.
7 9
 *

Also available in: Unified diff