RAdv: Support for more specific routes (RFC 4191)

The patch implements Default Router Preferences and More-Specific Routes
(RFC 4191) for RAdv protocol, allowing to announce router preference and
more specific routes in router advertisements. Routes can be exported to
RAdv like to regular routing protocols.

Some cleanups, bugfixes and other changes done by Ondrej Zajicek.

1 files changed, 249 insertions, 73 deletions

diff --git a/proto/radv/radv.c b/proto/radv/radv.c
index c53a0a95..d799dab5 100644
--- a/proto/radv/radv.c
+++ b/proto/radv/radv.c
@@ -12,37 +12,41 @@
 /**
  * DOC: Router Advertisements
  *
- * The RAdv protocol is implemented in two files: |radv.c| containing
- * the interface with BIRD core and the protocol logic and |packets.c|
- * handling low level protocol stuff (RX, TX and packet formats).
- * The protocol does not export any routes.
+ * The RAdv protocol is implemented in two files: |radv.c| containing the
+ * interface with BIRD core and the protocol logic and |packets.c| handling low
+ * level protocol stuff (RX, TX and packet formats). The protocol does not
+ * export any routes.
  *
- * The RAdv is structured in the usual way - for each handled interface
- * there is a structure &radv_iface that contains a state related to
- * that interface together with its resources (a socket, a timer).
- * There is also a prepared RA stored in a TX buffer of the socket
- * associated with an iface. These iface structures are created
- * and removed according to iface events from BIRD core handled by
- * radv_if_notify() callback.
+ * The RAdv is structured in the usual way - for each handled interface there is
+ * a structure &radv_iface that contains a state related to that interface
+ * together with its resources (a socket, a timer). There is also a prepared RA
+ * stored in a TX buffer of the socket associated with an iface. These iface
+ * structures are created and removed according to iface events from BIRD core
+ * handled by radv_if_notify() callback.
  *
- * The main logic of RAdv consists of two functions:
- * radv_iface_notify(), which processes asynchronous events (specified
- * by RA_EV_* codes), and radv_timer(), which triggers sending RAs and
- * computes the next timeout.
+ * The main logic of RAdv consists of two functions: radv_iface_notify(), which
+ * processes asynchronous events (specified by RA_EV_* codes), and radv_timer(),
+ * which triggers sending RAs and computes the next timeout.
  *
- * The RAdv protocol could receive routes (through
- * radv_import_control() and radv_rt_notify()), but only the
- * configured trigger route is tracked (in &active var).  When a radv
- * protocol is reconfigured, the connected routing table is examined
- * (in radv_check_active()) to have proper &active value in case of
- * the specified trigger prefix was changed.
+ * The RAdv protocol could receive routes (through radv_import_control() and
+ * radv_rt_notify()), but only the configured trigger route is tracked (in
+ * &active var).  When a radv protocol is reconfigured, the connected routing
+ * table is examined (in radv_check_active()) to have proper &active value in
+ * case of the specified trigger prefix was changed.
  *
  * Supported standards:
  * - RFC 4861 - main RA standard
+ * - RFC 4191 - Default Router Preferences and More-Specific Routes
  * - RFC 6106 - DNS extensions (RDDNS, DNSSL)
- * - RFC 4191 (partial) - Default Router Preference
  */
 
+static void radv_prune_prefixes(struct radv_iface *ifa);
+static void radv_prune_routes(struct radv_proto *p);
+
+/* Invalidate cached RA packet */
+static inline void radv_invalidate(struct radv_iface *ifa)
+{ ifa->plen = 0; }
+
 static void
 radv_timer(timer *tm)
 {
@@ -51,17 +55,13 @@ radv_timer(timer *tm)
 
   RADV_TRACE(D_EVENTS, "Timer fired on %s", ifa->iface->name);
 
-  /*
-   * If some dead prefixes expired, regenerate the prefix list and the packet.
-   * We do so by pretending there was a change on the interface.
-   *
-   * This sets the timer, but we replace it just at the end of this function
-   * (replacing a timer is fine).
-   */
-  if (ifa->prefix_expires && (ifa->prefix_expires <= now))
-    radv_iface_notify(ifa, RA_EV_GC);
+  if (ifa->prune_time <= now)
+    radv_prune_prefixes(ifa);
+
+  if (p->prune_time <= now)
+    radv_prune_routes(p);
 
-  radv_send_ra(ifa, 0);
+  radv_send_ra(ifa);
 
   /* Update timer */
   ifa->last = now;
@@ -118,7 +118,7 @@ radv_prepare_prefixes(struct radv_iface *ifa)
 {
   struct radv_proto *p = ifa->ra;
   struct radv_iface_config *cf = ifa->cf;
-  struct radv_prefix *pfx;
+  struct radv_prefix *pfx, *next;
 
   /* First mark all the prefixes as unused */
   WALK_LIST(pfx, ifa->prefixes)
@@ -162,49 +162,53 @@ radv_prepare_prefixes(struct radv_iface *ifa)
     existing->cf = pc;
   }
 
-  /*
-   * Garbage-collect the prefixes. If something isn't used, it dies (but isn't
-   * dropped just yet). If something is dead and rots there for long enough,
-   * clean it up.
-   */
-  bird_clock_t expires = now + cf->linger_time;
-  bird_clock_t expires_min = 0;
-  struct radv_prefix *next;
   WALK_LIST_DELSAFE(pfx, next, ifa->prefixes)
   {
     if (pfx->alive && !pfx->mark)
     {
-      RADV_TRACE(D_EVENTS, "Marking prefix %I/$d on %s as dead",
+      RADV_TRACE(D_EVENTS, "Invalidating prefix %I/$d on %s",
 		 pfx->prefix, pfx->len, ifa->iface->name);
 
       pfx->alive = 0;
-      pfx->expires = expires;
+      pfx->expires = now + cf->linger_time;
       pfx->cf = &dead_prefix;
     }
+  }
+}
+
+static void
+radv_prune_prefixes(struct radv_iface *ifa)
+{
+  struct radv_proto *p = ifa->ra;
+  bird_clock_t next = TIME_INFINITY;
+  int changed = 0;
 
-    if (!pfx->alive)
+  struct radv_prefix *px, *pxn;
+  WALK_LIST_DELSAFE(px, pxn, ifa->prefixes)
+  {
+    if (!px->alive)
     {
-      if (pfx->expires <= now)
+      if (px->expires <= now)
       {
 	RADV_TRACE(D_EVENTS, "Removing prefix %I/%d on %s",
-		   pfx->prefix, pfx->len, ifa->iface->name);
+		   px->prefix, px->len, ifa->iface->name);
 
-	rem_node(NODE pfx);
-	mb_free(pfx);
+	rem_node(NODE px);
+	mb_free(px);
+	changed = 1;
       }
       else
-      {
-	/* Find minimum expiration time */
-	if (!expires_min || (pfx->expires < expires_min))
-	  expires_min = pfx->expires;
-      }
+	next = MIN(next, px->expires);
     }
   }
 
-  ifa->prefix_expires = expires_min;
+  if (changed)
+    radv_invalidate(ifa);
+
+  ifa->prune_time = next;
 }
 
-static char* ev_name[] = { NULL, "Init", "Change", "RS", "Garbage collect" };
+static char* ev_name[] = { NULL, "Init", "Change", "RS" };
 
 void
 radv_iface_notify(struct radv_iface *ifa, int event)
@@ -219,18 +223,17 @@ radv_iface_notify(struct radv_iface *ifa, int event)
   switch (event)
   {
   case RA_EV_CHANGE:
-  case RA_EV_GC:
-    ifa->plen = 0;
+    radv_invalidate(ifa);
   case RA_EV_INIT:
     ifa->initial = MAX_INITIAL_RTR_ADVERTISEMENTS;
+    radv_prepare_prefixes(ifa);
+    radv_prune_prefixes(ifa);
     break;
 
   case RA_EV_RS:
     break;
   }
 
-  radv_prepare_prefixes(ifa);
-
   /* Update timer */
   unsigned delta = now - ifa->last;
   unsigned after = 0;
@@ -250,7 +253,6 @@ radv_iface_notify_all(struct radv_proto *p, int event)
     radv_iface_notify(ifa, event);
 }
 
-
 static struct radv_iface *
 radv_iface_find(struct radv_proto *p, struct iface *what)
 {
@@ -303,6 +305,7 @@ radv_iface_new(struct radv_proto *p, struct iface *iface, struct radv_iface_conf
   ifa->cf = cf;
   ifa->iface = iface;
   init_list(&ifa->prefixes);
+  ifa->prune_time = TIME_INFINITY;
 
   add_tail(&p->iface_list, NODE ifa);
 
@@ -409,14 +412,18 @@ radv_import_control(struct proto *P, rte **new, ea_list **attrs UNUSED, struct l
   if (radv_net_match_trigger(cf, (*new)->net))
     return RIC_PROCESS;
 
-  return RIC_DROP;
+  if (cf->propagate_routes)
+    return RIC_PROCESS;
+  else
+    return RIC_DROP;
 }
 
 static void
-radv_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *attrs UNUSED)
+radv_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old UNUSED, ea_list *attrs)
 {
   struct radv_proto *p = (struct radv_proto *) P;
   struct radv_config *cf = (struct radv_config *) (P->cf);
+  struct radv_route *rt;
 
   if (radv_net_match_trigger(cf, n))
   {
@@ -432,7 +439,117 @@ radv_rt_notify(struct proto *P, rtable *tbl UNUSED, net *n, rte *new, rte *old U
       RADV_TRACE(D_EVENTS, "Suppressed");
 
     radv_iface_notify_all(p, RA_EV_CHANGE);
+    return;
   }
+
+  if (!cf->propagate_routes)
+    return;
+
+  /*
+   * Some other route we want to send (or stop sending). Update the cache,
+   * with marking a removed one as dead or creating a new one as needed.
+   *
+   * And yes, we exclude the trigger route on purpose.
+   */
+
+  if (new)
+  {
+    /* Update */
+    uint preference = ea_get_int(attrs, EA_RA_PREFERENCE, RA_PREF_MEDIUM);
+    uint lifetime = ea_get_int(attrs, EA_RA_LIFETIME, 0);
+    uint lifetime_set = !!ea_find(attrs, EA_RA_LIFETIME);
+
+    if ((preference != RA_PREF_LOW) &&
+	(preference != RA_PREF_MEDIUM) &&
+	(preference != RA_PREF_HIGH))
+    {
+      log(L_WARN "%s: Invalid ra_preference value %u on route %I/%d",
+	  p->p.name, preference, n->n.prefix, n->n.pxlen);
+      preference = RA_PREF_MEDIUM;
+      lifetime = 0;
+      lifetime_set = 1;
+    }
+
+    rt = fib_get(&p->routes, &n->n.prefix, n->n.pxlen);
+
+    /* Ignore update if nothing changed */
+    if (rt->alive &&
+	(rt->preference == preference) &&
+	(rt->lifetime == lifetime) &&
+	(rt->lifetime_set == lifetime_set))
+      return;
+
+    if (p->routes.entries == 18)
+      log(L_WARN "%s: More than 17 routes exported to RAdv", p->p.name);
+
+    rt->alive = 1;
+    rt->preference = preference;
+    rt->lifetime = lifetime;
+    rt->lifetime_set = lifetime_set;
+  }
+  else
+  {
+    /* Withdraw */
+    rt = fib_find(&p->routes, &n->n.prefix, n->n.pxlen);
+
+    if (!rt || !rt->alive)
+      return;
+
+    /* Invalidate the route */
+    rt->alive = 0;
+    rt->expires = now + cf->route_linger_time;
+    p->prune_time = MIN(p->prune_time, rt->expires);
+  }
+
+  radv_iface_notify_all(p, RA_EV_CHANGE);
+}
+
+/*
+ * Cleans up all the dead routes that expired and schedules itself to be run
+ * again if there are more routes waiting for expiration.
+ */
+static void
+radv_prune_routes(struct radv_proto *p)
+{
+  bird_clock_t next = TIME_INFINITY;
+  int changed = 0;
+
+  /* Should not happen */
+  if (!p->fib_up)
+    return;
+
+  struct fib_iterator fit;
+  FIB_ITERATE_INIT(&fit, &p->routes);
+
+again:
+  FIB_ITERATE_START(&p->routes, &fit, node)
+  {
+    struct radv_route *rt = (void *) node;
+
+    if (!rt->alive)
+    {
+      /* Delete expired nodes */
+      if (rt->expires <= now)
+      {
+	FIB_ITERATE_PUT(&fit, node);
+	fib_delete(&p->routes, node);
+	changed = 1;
+	goto again;
+      }
+      else
+	next = MIN(next, rt->expires);
+    }
+  }
+  FIB_ITERATE_END(node);
+
+  if (changed)
+  {
+    struct radv_iface *ifa;
+    WALK_LIST(ifa, p->iface_list)
+      radv_invalidate(ifa);
+  }
+
+  p->prune_time = next;
 }
 
 static int
@@ -461,6 +578,21 @@ radv_init(struct proto_config *c)
   return P;
 }
 
+static void
+radv_set_fib(struct radv_proto *p, int up)
+{
+  if (up == p->fib_up)
+    return;
+
+  if (up)
+    fib_init(&p->routes, p->p.pool, sizeof(struct radv_route), 4, NULL);
+  else
+    fib_free(&p->routes);
+
+  p->fib_up = up;
+  p->prune_time = TIME_INFINITY;
+}
+
 static int
 radv_start(struct proto *P)
 {
@@ -468,8 +600,13 @@ radv_start(struct proto *P)
   struct radv_config *cf = (struct radv_config *) (P->cf);
 
   init_list(&(p->iface_list));
+  p->valid = 1;
   p->active = !cf->trigger_valid;
 
+  p->fib_up = 0;
+  radv_set_fib(p, cf->propagate_routes);
+  p->prune_time = TIME_INFINITY;
+
   return PS_UP;
 }
 
@@ -477,7 +614,10 @@ static inline void
 radv_iface_shutdown(struct radv_iface *ifa)
 {
   if (ifa->sk)
-    radv_send_ra(ifa, 1);
+  {
+    radv_invalidate(ifa);
+    radv_send_ra(ifa);
+  }
 }
 
 static int
@@ -485,6 +625,8 @@ radv_shutdown(struct proto *P)
 {
   struct radv_proto *p = (struct radv_proto *) P;
 
+  p->valid = 0;
+
   struct radv_iface *ifa;
   WALK_LIST(ifa, p->iface_list)
     radv_iface_shutdown(ifa);
@@ -496,20 +638,19 @@ static int
 radv_reconfigure(struct proto *P, struct proto_config *c)
 {
   struct radv_proto *p = (struct radv_proto *) P;
-  // struct radv_config *old = (struct radv_config *) (p->cf);
+  struct radv_config *old = (struct radv_config *) (P->cf);
   struct radv_config *new = (struct radv_config *) c;
 
-  /*
-   * The question is why there is a reconfigure function for RAdv if
-   * it has almost none internal state so restarting the protocol
-   * would probably suffice. One small reason is that restarting the
-   * protocol would lead to sending a RA with Router Lifetime 0
-   * causing nodes to temporary remove their default routes.
-   */
-
   P->cf = c; /* radv_check_active() requires proper P->cf */
   p->active = radv_check_active(p);
 
+  /* Allocate or free FIB */
+  radv_set_fib(p, new->propagate_routes);
+
+  /* We started to accept routes so we need to refeed them */
+  if (!old->propagate_routes && new->propagate_routes)
+    proto_request_feeding(&p->p);
+
   struct iface *iface;
   WALK_LIST(iface, iface_list)
   {
@@ -561,14 +702,49 @@ radv_get_status(struct proto *P, byte *buf)
     strcpy(buf, "Suppressed");
 }
 
+static const char *
+radv_pref_str(u32 pref)
+{
+  switch (pref)
+  {
+    case RA_PREF_LOW:
+      return "low";
+    case RA_PREF_MEDIUM:
+      return "medium";
+    case RA_PREF_HIGH:
+      return "high";
+    default:
+      return "??";
+  }
+}
+
+/* The buffer has some minimal size */
+static int
+radv_get_attr(eattr *a, byte *buf, int buflen UNUSED)
+{
+  switch (a->id)
+  {
+  case EA_RA_PREFERENCE:
+    bsprintf(buf, "preference: %s", radv_pref_str(a->u.data));
+    return GA_FULL;
+  case EA_RA_LIFETIME:
+    bsprintf(buf, "lifetime");
+    return GA_NAME;
+  default:
+    return GA_UNKNOWN;
+  }
+}
+
 struct protocol proto_radv = {
   .name =		"RAdv",
   .template =		"radv%d",
+  .attr_class =		EAP_RADV,
   .config_size =	sizeof(struct radv_config),
   .init =		radv_init,
   .start =		radv_start,
   .shutdown =		radv_shutdown,
   .reconfigure =	radv_reconfigure,
   .copy_config =	radv_copy_config,
-  .get_status =		radv_get_status
+  .get_status =		radv_get_status,
+  .get_attr =		radv_get_attr
 };