RAdv: Buffer prefixes awhile after they disappear

Keep a cache of all the relevant prefixes we send out. When a prefix
appears, insert it into the cache. If it dies, keep it there for a
while, marked as dead.

Send out the dead prefixes with zero lifetime.

3 files changed, 170 insertions, 52 deletions

diff --git a/proto/radv/packets.c b/proto/radv/packets.c
index bf051f62..088d177c 100644
--- a/proto/radv/packets.c
+++ b/proto/radv/packets.c
@@ -70,36 +70,6 @@ struct radv_opt_dnssl
   char domain[];
 };
 
-
-static struct radv_prefix_config default_prefix = {
-  .onlink = 1,
-  .autonomous = 1,
-  .valid_lifetime = DEFAULT_VALID_LIFETIME,
-  .preferred_lifetime = DEFAULT_PREFERRED_LIFETIME
-};
-
-
-static struct radv_prefix_config *
-radv_prefix_match(struct radv_iface *ifa, struct ifa *a)
-{
-  struct radv_proto *p = ifa->ra;
-  struct radv_config *cf = (struct radv_config *) (p->p.cf);
-  struct radv_prefix_config *pc;
-
-  if (a->scope <= SCOPE_LINK)
-    return NULL;
-
-  WALK_LIST(pc, ifa->cf->pref_list)
-    if ((a->pxlen >= pc->pxlen) && ipa_in_net(a->prefix, pc->prefix, pc->pxlen))
-      return pc;
-
-  WALK_LIST(pc, cf->pref_list)
-    if ((a->pxlen >= pc->pxlen) && ipa_in_net(a->prefix, pc->prefix, pc->pxlen))
-      return pc;
-
-  return &default_prefix;
-}
-
 static int
 radv_prepare_rdnss(struct radv_iface *ifa, list *rdnss_list, char **buf, char *bufend)
 {
@@ -236,9 +206,10 @@ radv_prepare_dnssl(struct radv_iface *ifa, list *dnssl_list, char **buf, char *b
 }
 
 static int
-radv_prepare_prefix(struct radv_iface *ifa, struct radv_prefix_config *pc,
-  struct ifa *addr, char **buf, char *bufend)
+radv_prepare_prefix(struct radv_iface *ifa, struct radv_prefix *prefix,
+		    char **buf, char *bufend)
 {
+  struct radv_prefix_config *pc = prefix->config;
   struct radv_opt_prefix *op = (void *) *buf;
 
   if (*buf + sizeof(*op) > bufend)
@@ -250,7 +221,7 @@ radv_prepare_prefix(struct radv_iface *ifa, struct radv_prefix_config *pc,
 
   op->type = OPT_PREFIX;
   op->length = 4;
-  op->pxlen = addr->pxlen;
+  op->pxlen = prefix->len;
   op->flags = (pc->onlink ? OPT_PX_ONLINK : 0) |
     (pc->autonomous ? OPT_PX_AUTONOMOUS : 0);
   op->valid_lifetime = (ifa->ra->active || !pc->valid_lifetime_sensitive) ?
@@ -258,7 +229,7 @@ radv_prepare_prefix(struct radv_iface *ifa, struct radv_prefix_config *pc,
   op->preferred_lifetime = (ifa->ra->active || !pc->preferred_lifetime_sensitive) ?
     htonl(pc->preferred_lifetime) : 0;
   op->reserved = 0;
-  op->prefix = addr->prefix;
+  op->prefix = prefix->prefix;
   ipa_hton(op->prefix);
   *buf += sizeof(*op);
 
@@ -300,16 +271,10 @@ radv_prepare_ra(struct radv_iface *ifa)
     buf += sizeof (*om);
   }
 
-  struct ifa *addr;
-  WALK_LIST(addr, ifa->iface->addrs)
+  struct radv_prefix *prefix;
+  WALK_LIST(prefix, ifa->prefixes)
   {
-    struct radv_prefix_config *pc;
-    pc = radv_prefix_match(ifa, addr);
-
-    if (!pc || pc->skip)
-      continue;
-
-    if (radv_prepare_prefix(ifa, pc, addr, &buf, bufend) < 0)
+    if (radv_prepare_prefix(ifa, prefix, &buf, bufend) < 0)
       goto done;
   }
 
@@ -419,7 +384,7 @@ radv_err_hook(sock *sk, int err)
 int
 radv_sk_open(struct radv_iface *ifa)
 {
-  sock *sk = sk_new(ifa->ra->p.pool);
+  sock *sk = sk_new(ifa->pool);
   sk->type = SK_IP;
   sk->dport = ICMPV6_PROTO;
   sk->saddr = ifa->addr->ip;
diff --git a/proto/radv/radv.c b/proto/radv/radv.c
index 91f9853d..303cf251 100644
--- a/proto/radv/radv.c
+++ b/proto/radv/radv.c
@@ -51,6 +51,15 @@ 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 != 0 && ifa->prefix_expires <= now)
+    radv_iface_notify(ifa, RA_EV_GC);
+
   radv_send_ra(ifa, 0);
 
   /* Update timer */
@@ -67,7 +76,129 @@ radv_timer(timer *tm)
   tm_start(ifa->timer, after);
 }
 
-static char* ev_name[] = { NULL, "Init", "Change", "RS" };
+static struct radv_prefix_config default_prefix = {
+  .onlink = 1,
+  .autonomous = 1,
+  .valid_lifetime = DEFAULT_VALID_LIFETIME,
+  .preferred_lifetime = DEFAULT_PREFERRED_LIFETIME
+};
+
+static struct radv_prefix_config dead_prefix = {
+};
+
+/* Find a corresponding config for the given prefix */
+static struct radv_prefix_config *
+radv_prefix_match(struct radv_iface *ifa, struct ifa *a)
+{
+  struct radv_proto *p = ifa->ra;
+  struct radv_config *cf = (struct radv_config *) (p->p.cf);
+  struct radv_prefix_config *pc;
+
+  if (a->scope <= SCOPE_LINK)
+    return NULL;
+
+  WALK_LIST(pc, ifa->cf->pref_list)
+    if ((a->pxlen >= pc->pxlen) && ipa_in_net(a->prefix, pc->prefix, pc->pxlen))
+      return pc;
+
+  WALK_LIST(pc, cf->pref_list)
+    if ((a->pxlen >= pc->pxlen) && ipa_in_net(a->prefix, pc->prefix, pc->pxlen))
+      return pc;
+
+  return &default_prefix;
+}
+
+/*
+ * Go through the list of prefixes, compare them with configs and decide if we
+ * want them or not. */
+static void
+prefixes_prepare(struct radv_iface *ifa)
+{
+  struct radv_proto *p = ifa->ra;
+  /* First mark all the prefixes as unused */
+  struct radv_prefix *pfx;
+
+  WALK_LIST(pfx, ifa->prefixes)
+    pfx->mark = 0;
+
+  /* Now find all the prefixes we want to use and make sure they are in the
+   * list. */
+  struct ifa *addr;
+  WALK_LIST(addr, ifa->iface->addrs)
+  {
+    struct radv_prefix_config *pc = radv_prefix_match(ifa, addr);
+
+    if (!pc || pc->skip)
+      continue;
+
+    /* Do we have it already? */
+    struct radv_prefix *existing = NULL;
+    WALK_LIST(pfx, ifa->prefixes)
+      if (pfx->len == addr->pxlen &&
+	  memcmp(&pfx->prefix, &addr->prefix, sizeof pfx->prefix) == 0)
+      {
+	existing = pfx;
+	break;
+      }
+
+    if (!existing)
+    {
+      RADV_TRACE(D_EVENTS, "Allocating new prefix %I on %s", addr->prefix,
+		 ifa->iface->name);
+      existing = mb_allocz(ifa->pool, sizeof *existing);
+      existing->prefix = addr->prefix;
+      existing->len = addr->pxlen;
+      add_tail(&ifa->prefixes, NODE existing);
+    }
+    /*
+     * Update the information (it may have changed, or even bring a prefix back
+     * to life).
+     */
+    existing->alive = 1;
+    existing->mark = 1;
+    existing->config = 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.
+   */
+  // XXX: Make these 5 minutes it configurable
+  bird_clock_t rotten = now + 300;
+  struct radv_prefix *next;
+  bird_clock_t expires_soonest = 0;
+  WALK_LIST_DELSAFE(pfx, next, ifa->prefixes) {
+    if (pfx->alive && !pfx->mark)
+    {
+      RADV_TRACE(D_EVENTS, "Marking prefix %I on %s as dead", pfx->prefix,
+		 ifa->iface->name);
+      // It just died
+      pfx->alive = 0;
+      pfx->expires = rotten;
+      pfx->config = &dead_prefix;
+    }
+    if (!pfx->alive)
+      if (pfx->expires <= now)
+      {
+	RADV_TRACE(D_EVENTS, "Dropping long dead prefix %I on %s", pfx->prefix,
+		   ifa->iface->name);
+	// It's dead and rotten, clean it up
+	rem_node(NODE pfx);
+	mb_free(pfx);
+      }
+      else
+      {
+	ASSERT(pfx->expires != 0);
+	// Let it rot for a while more, but look when it's ripe.
+	if (expires_soonest == 0 || pfx->expires < expires_soonest)
+	  expires_soonest = pfx->expires;
+      }
+  }
+  ifa->prefix_expires = expires_soonest;
+}
+
+static char* ev_name[] = { NULL, "Init", "Change", "RS", "Garbage collect" };
 
 void
 radv_iface_notify(struct radv_iface *ifa, int event)
@@ -82,6 +213,7 @@ radv_iface_notify(struct radv_iface *ifa, int event)
   switch (event)
   {
   case RA_EV_CHANGE:
+  case RA_EV_GC:
     ifa->plen = 0;
   case RA_EV_INIT:
     ifa->initial = MAX_INITIAL_RTR_ADVERTISEMENTS;
@@ -91,6 +223,8 @@ radv_iface_notify(struct radv_iface *ifa, int event)
     break;
   }
 
+  prefixes_prepare(ifa);
+
   /* Update timer */
   unsigned delta = now - ifa->last;
   unsigned after = 0;
@@ -152,15 +286,17 @@ find_lladdr(struct iface *iface)
 static void
 radv_iface_new(struct radv_proto *p, struct iface *iface, struct radv_iface_config *cf)
 {
-  pool *pool = p->p.pool;
   struct radv_iface *ifa;
 
   RADV_TRACE(D_EVENTS, "Adding interface %s", iface->name);
 
+  pool *pool = rp_new(p->p.pool, iface->name);
   ifa = mb_allocz(pool, sizeof(struct radv_iface));
+  ifa->pool = pool;
   ifa->ra = p;
   ifa->cf = cf;
   ifa->iface = iface;
+  init_list(&ifa->prefixes);
 
   add_tail(&p->iface_list, NODE ifa);
 
@@ -198,11 +334,7 @@ radv_iface_remove(struct radv_iface *ifa)
 
   rem_node(NODE ifa);
 
-  rfree(ifa->sk);
-  rfree(ifa->timer);
-  rfree(ifa->lock);
-
-  mb_free(ifa);
+  rfree(ifa->pool);
 }
 
 static void
diff --git a/proto/radv/radv.h b/proto/radv/radv.h
index 559a3f3f..54d7c6f0 100644
--- a/proto/radv/radv.h
+++ b/proto/radv/radv.h
@@ -121,6 +121,23 @@ struct radv_proto
   u8 active;			/* Whether radv is active w.r.t. triggers */
 };
 
+struct radv_prefix		/* One prefix we advertise */
+{
+  node n;
+  ip_addr prefix;
+  u8 len;
+  /* Is the prefix alive? If not, we advertise it with 0 lifetime, so clients
+   * stop using it. */
+  u8 alive;
+  u8 mark;			/* A temporary mark for processing */
+  /* The (absolute) time when we drop this prefix from advertising. It is valid
+   * only if !alive. */
+  bird_clock_t expires;
+  /* The config tied to this prefix. Always valid (we place a dummy config here
+   * when !alive). */
+  struct radv_prefix_config *config;
+};
+
 struct radv_iface
 {
   node n;
@@ -128,6 +145,9 @@ struct radv_iface
   struct radv_iface_config *cf;	/* Related config, must be updated in reconfigure */
   struct iface *iface;
   struct ifa *addr;		/* Link-local address of iface */
+  struct pool *pool;		/* A pool for interface-specific things */
+  list prefixes;		/* The prefixes we advertise */
+  bird_clock_t prefix_expires;	/* When the soonest prefix expires (0 = none dead) */
 
   timer *timer;
   struct object_lock *lock;
@@ -135,12 +155,13 @@ struct radv_iface
 
   bird_clock_t last;		/* Time of last sending of RA */
   u16 plen;			/* Length of prepared RA in tbuf, or 0 if not valid */
-  byte initial;			/* List of active ifaces */
+  byte initial;			/* How many RAs are still to be sent as initial */
 };
 
 #define RA_EV_INIT 1		/* Switch to initial mode */
 #define RA_EV_CHANGE 2		/* Change of options or prefixes */
 #define RA_EV_RS 3		/* Received RS */
+#define RA_EV_GC 4		/* Internal garbage collection of prefixes */
 
 /* Default Router Preferences (RFC 4191) */
 #define RA_PREF_LOW	0x18