Merge branch 'master' into mq-filter-stack

13 files changed, 134 insertions, 82 deletions

diff --git a/doc/bird.sgml b/doc/bird.sgml
index e0b60c81..c69ab87f 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -2246,7 +2246,7 @@ using the following configuration parameters:
 
 	<tag><label id="bgp-dynamic-name">dynamic name "<m/text/"</tag>
 	Define common prefix of names used for new BGP instances spawned when
-	dynamic BGP behavior is active. Actual names also contain numberic
+	dynamic BGP behavior is active. Actual names also contain numeric
 	index to distinguish individual instances.  Default: "dynbgp".
 
 	<tag><label id="bgp-dynamic-name">dynamic name digits <m/number/</tag>
diff --git a/nest/route.h b/nest/route.h
index 9959ea69..8d799454 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -631,6 +631,7 @@ int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath ne
 static inline int nexthop_same(struct nexthop *x, struct nexthop *y)
 { return (x == y) || nexthop__same(x, y); }
 struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp);
+struct nexthop *nexthop_sort(struct nexthop *x);
 static inline void nexthop_link(struct rta *a, struct nexthop *from)
 { memcpy(&a->nh, from, nexthop_size(from)); }
 void nexthop_insert(struct nexthop **n, struct nexthop *y);
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index 9c38e3ca..8620d321 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -202,7 +202,7 @@ nexthop__same(struct nexthop *x, struct nexthop *y)
 }
 
 static int
-nexthop_compare_node(struct nexthop *x, struct nexthop *y)
+nexthop_compare_node(const struct nexthop *x, const  struct nexthop *y)
 {
   int r;
 
@@ -320,6 +320,24 @@ nexthop_insert(struct nexthop **n, struct nexthop *x)
   *n = x;
 }
 
+struct nexthop *
+nexthop_sort(struct nexthop *x)
+{
+  struct nexthop *s = NULL;
+
+  /* Simple insert-sort */
+  while (x)
+  {
+    struct nexthop *n = x;
+    x = n->next;
+    n->next = NULL;
+
+    nexthop_insert(&s, n);
+  }
+
+  return s;
+}
+
 int
 nexthop_is_sorted(struct nexthop *x)
 {
diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index f5c69199..6e7e498f 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -880,6 +880,7 @@ ospf_iface_reconfigure(struct ospf_iface *ifa, struct ospf_iface_patt *new)
 	       ifname, ifa->priority, new->priority);
 
     ifa->priority = new->priority;
+    ospf_iface_sm(ifa, ISM_NEICH);
     ospf_notify_link_lsa(ifa);
   }
 
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index b6d5570c..510058eb 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -246,18 +246,33 @@ void
 ospf_stop_gr_recovery(struct ospf_proto *p)
 {
   p->gr_recovery = 0;
+  p->gr_cleanup = 1;
   p->gr_timeout = 0;
-  channel_graceful_restart_unlock(p->p.main_channel);
 
   /* Reorigination of router/network LSAs is already scheduled */
-  ospf_mark_lsadb(p);
 
-  /*
-   * NOTE: We should move channel_graceful_restart_unlock() to the end of
-   * ospf_disp() in order to have local LSA reorigination / LSAdb cleanup /
-   * routing table recomputation before official end of GR. It does not matter
-   * when we are single-threaded.
-   */
+  /* Rest is done in ospf_cleanup_gr_recovery() */
+}
+
+static void
+ospf_cleanup_gr_recovery(struct ospf_proto *p)
+{
+  struct top_hash_entry *en;
+
+  /* Flush dirty LSAa except external ones, these will be handled by feed */
+  WALK_SLIST(en, p->lsal)
+    if (en->gr_dirty)
+    {
+      if ((en->lsa_type == LSA_T_EXT) || (en->lsa_type == LSA_T_NSSA))
+	en->mode = LSA_M_EXPORT;
+      else
+	ospf_flush_lsa(p, en);
+    }
+
+  /* End graceful restart on channel, will also schedule feed */
+  channel_graceful_restart_unlock(p->p.main_channel);
+
+  p->gr_cleanup = 0;
 }
 
 static int
@@ -361,6 +376,8 @@ ospf_init(struct proto_config *CF)
   P->ifa_notify = cf->ospf2 ? ospf_ifa_notify2 : ospf_ifa_notify3;
   P->preexport = ospf_preexport;
   P->reload_routes = ospf_reload_routes;
+  P->feed_begin = ospf_feed_begin;
+  P->feed_end = ospf_feed_end;
   P->make_tmp_attrs = ospf_make_tmp_attrs;
   P->store_tmp_attrs = ospf_store_tmp_attrs;
   P->rte_better = ospf_rte_better;
@@ -436,6 +453,7 @@ ospf_disp(timer * timer)
 {
   struct ospf_proto *p = timer->data;
 
+  /* Check for end of graceful restart */
   if (p->gr_recovery)
     ospf_update_gr_recovery(p);
 
@@ -448,6 +466,10 @@ ospf_disp(timer * timer)
   /* Calculate routing table */
   if (p->calcrt)
     ospf_rt_spf(p);
+
+  /* Cleanup after graceful restart */
+  if (p->gr_cleanup)
+    ospf_cleanup_gr_recovery(p);
 }
 
 
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index beecd2b6..3343e5bf 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -223,7 +223,8 @@ struct ospf_proto
   int areano;			/* Number of area I belong to */
   int padj;			/* Number of neighbors in Exchange or Loading state */
   int gr_count;			/* Number of neighbors in graceful restart state */
-  int gr_recovery;		/* Graceful restart recovery is active */
+  u8 gr_recovery;		/* Graceful restart recovery is active */
+  u8 gr_cleanup;		/* GR cleanup scheduled */
   btime gr_timeout;		/* The end time of grace restart recovery */
   struct fib rtf;		/* Routing table */
   struct idm idm;		/* OSPFv3 LSA ID map */
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 126ef201..b5787b54 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -1640,7 +1640,7 @@ ospf_rt_reset(struct ospf_proto *p)
     en->lb = IPA_NONE;
 
     if (en->mode == LSA_M_RTCALC)
-      en->mode = LSA_M_STALE;
+      en->mode = LSA_M_RTCALC_STALE;
   }
 
   WALK_LIST(oa, p->area_list)
@@ -2117,7 +2117,7 @@ again2:
 
   /* Cleanup stale LSAs */
   WALK_SLIST(en, p->lsal)
-    if (en->mode == LSA_M_STALE)
+    if (en->mode == LSA_M_RTCALC_STALE)
       ospf_flush_lsa(p, en);
 }
 
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index efd03b54..2e9c3965 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -71,6 +71,7 @@ ospf_install_lsa(struct ospf_proto *p, struct ospf_lsa_header *lsa, u32 type, u3
   en->lsa = *lsa;
   en->init_age = en->lsa.age;
   en->inst_time = current_time();
+  en->gr_dirty = p->gr_recovery && (lsa->rt == p->router_id);
 
   /*
    * We do not set en->mode. It is either default LSA_M_BASIC, or in a special
@@ -246,7 +247,7 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa
   en->lsa.age = 0;
   en->init_age = 0;
   en->inst_time = current_time();
-  en->dirty = 0;
+  en->gr_dirty = 0;
   lsa_generate_checksum(&en->lsa, en->lsa_body);
 
   OSPF_TRACE(D_EVENTS, "Originating LSA: Type: %04x, Id: %R, Rt: %R, Seq: %08x",
@@ -280,11 +281,15 @@ ospf_do_originate_lsa(struct ospf_proto *p, struct top_hash_entry *en, void *lsa
 struct top_hash_entry *
 ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
 {
-  struct top_hash_entry *en;
+  struct top_hash_entry *en = NULL;
   void *lsa_body = p->lsab;
   u16 lsa_blen = p->lsab_used;
   u16 lsa_length = sizeof(struct ospf_lsa_header) + lsa_blen;
 
+  /* RFC 3623 2 (1) - do not originate topology LSAs during graceful restart */
+  if (p->gr_recovery && (LSA_FUNCTION(lsa->type) <= LSA_FUNCTION(LSA_T_NSSA)))
+    goto drop;
+
   /* For OSPFv2 Opaque LSAs, LS ID consists of Opaque Type and Opaque ID */
   if (ospf_is_v2(p) && lsa_is_opaque(lsa->type))
     lsa->id |= (u32) lsa_get_opaque_type(lsa->type) << 24;
@@ -329,7 +334,7 @@ ospf_originate_lsa(struct ospf_proto *p, struct ospf_new_lsa *lsa)
       (lsa_length == en->lsa.length) &&
       !memcmp(lsa_body, en->lsa_body, lsa_blen) &&
       (!ospf_is_v2(p) || (lsa->opts == lsa_get_options(&en->lsa))) &&
-      !en->dirty)
+      !en->gr_dirty)
     goto drop;
 
   lsa_body = lsab_flush(p);
@@ -422,6 +427,7 @@ void
 ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en)
 {
   en->nf = NULL;
+  en->gr_dirty = 0;
 
   if (en->next_lsa_body)
   {
@@ -520,12 +526,6 @@ ospf_update_lsadb(struct ospf_proto *p)
       continue;
     }
 
-    if (en->dirty)
-    {
-      ospf_flush_lsa(p, en);
-      continue;
-    }
-
     if ((en->lsa.rt == p->router_id) && (real_age >= LSREFRESHTIME))
     {
       ospf_refresh_lsa(p, en);
@@ -543,14 +543,27 @@ ospf_update_lsadb(struct ospf_proto *p)
 }
 
 void
-ospf_mark_lsadb(struct ospf_proto *p)
+ospf_feed_begin(struct channel *C, int initial UNUSED)
 {
+  struct ospf_proto *p = (struct ospf_proto *) C->proto;
   struct top_hash_entry *en;
 
-  /* Mark all local LSAs as dirty */
+  /* Mark all external LSAs as stale */
   WALK_SLIST(en, p->lsal)
-    if (en->lsa.rt == p->router_id)
-      en->dirty = 1;
+    if (en->mode == LSA_M_EXPORT)
+      en->mode = LSA_M_EXPORT_STALE;
+}
+
+void
+ospf_feed_end(struct channel *C)
+{
+  struct ospf_proto *p = (struct ospf_proto *) C->proto;
+  struct top_hash_entry *en;
+
+  /* Flush stale LSAs */
+  WALK_SLIST(en, p->lsal)
+    if (en->mode == LSA_M_EXPORT_STALE)
+      ospf_flush_lsa(p, en);
 }
 
 static u32
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index ffae436a..535d1f1b 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -33,7 +33,7 @@ struct top_hash_entry
   u32 lb_id;			/* Interface ID of link back iface (for bcast or NBMA networks) */
   u32 dist;			/* Distance from the root */
   int ret_count;		/* Number of retransmission lists referencing the entry */
-  u8 dirty;			/* Will be flushed during next LSAdb update unless reoriginated*/
+  u8 gr_dirty;			/* Local LSA received during GR, will be removed unless reoriginated */
   u8 color;
 #define OUTSPF 0
 #define CANDIDATE 1
@@ -115,10 +115,11 @@ struct top_hash_entry
  */
 
 
-#define LSA_M_BASIC	0
-#define LSA_M_EXPORT	1
-#define LSA_M_RTCALC	2
-#define LSA_M_STALE	3
+#define LSA_M_BASIC		0
+#define LSA_M_EXPORT		1
+#define LSA_M_RTCALC		2
+#define LSA_M_EXPORT_STALE	3
+#define LSA_M_RTCALC_STALE	4
 
 /*
  * LSA entry modes:
@@ -128,9 +129,13 @@ struct top_hash_entry
  * routing table calculation is scheduled. This is also the mode used for LSAs
  * received from neighbors. Example: Router-LSAs, Network-LSAs.
  *
- * LSA_M_EXPORT - like LSA_M_BASIC, but the routing table calculation does not
- * depend on the LSA. Therefore, the calculation is not scheduled when the LSA
- * is changed. Example: AS-external-LSAs for exported routes.
+ * LSA_M_EXPORT - The LSA is originated using ospf_originate_lsa() as a
+ * consequence of route export to the OSPF instance. It has to be reoriginated
+ * during each channel feed, otherwise it is flushed automatically at the end of
+ * the feed. May be originated and flushed asynchronously. Also, routing table
+ * calculation does not depend on the LSA. Therefore, the routing table
+ * calculation is not scheduled when the LSA is changed. Example:
+ * AS-external-LSAs for exported routes.
  *
  * LSA_M_RTCALC - The LSA has to be requested using ospf_originate_lsa() during
  * each routing table calculation, otherwise it is flushed automatically at the
@@ -138,8 +143,11 @@ struct top_hash_entry
  * source for it. Therefore, the calculation is not scheduled when the LSA is
  * changed. Example: Summary-LSAs.
  *
- * LSA_M_STALE - Temporary state for LSA_M_RTCALC that is not requested during
- * the current routing table calculation.
+ * LSA_M_EXPORT_STALE - Temporary state for LSA_M_EXPORT that is not requested
+ * during current external route feed.
+ *
+ * LSA_M_RTCALC_STALE - Temporary state for LSA_M_RTCALC that is not requested
+ * during current routing table calculation.
  *
  *
  * Note that we do not schedule the routing table calculation when the age of
@@ -181,7 +189,8 @@ struct top_hash_entry * ospf_originate_lsa(struct ospf_proto *p, struct ospf_new
 void ospf_advance_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_lsa_header *lsa, u32 type, u32 domain, void *body);
 void ospf_flush_lsa(struct ospf_proto *p, struct top_hash_entry *en);
 void ospf_update_lsadb(struct ospf_proto *p);
-void ospf_mark_lsadb(struct ospf_proto *p);
+void ospf_feed_begin(struct channel *C, int initial);
+void ospf_feed_end(struct channel *C);
 
 static inline void ospf_flush2_lsa(struct ospf_proto *p, struct top_hash_entry **en)
 { if (*en) { ospf_flush_lsa(p, *en); *en = NULL; } }
diff --git a/sysdep/linux/netlink.c b/sysdep/linux/netlink.c
index e21f4039..95f0481e 100644
--- a/sysdep/linux/netlink.c
+++ b/sysdep/linux/netlink.c
@@ -725,6 +725,10 @@ nl_parse_multipath(struct nl_parse_state *s, struct krt_proto *p, struct rtattr
       nh = RTNH_NEXT(nh);
     }
 
+  /* Ensure nexthops are sorted to satisfy nest invariant */
+  if (!nexthop_is_sorted(first))
+    first = nexthop_sort(first);
+
   return first;
 }
 
@@ -1393,10 +1397,10 @@ krt_replace_rte(struct krt_proto *p, net *n, rte *new, rte *old)
 }
 
 static int
-nl_mergable_route(struct nl_parse_state *s, net *net, struct krt_proto *p, uint priority, uint krt_type)
+nl_mergable_route(struct nl_parse_state *s, net *net, struct krt_proto *p, uint priority, uint krt_type, uint rtm_family)
 {
-  /* Route merging must be active */
-  if (!s->merge)
+  /* Route merging is used for IPv6 scans */
+  if (!s->scan || (rtm_family != AF_INET6))
     return 0;
 
   /* Saved and new route must have same network, proto/table, and priority */
@@ -1433,12 +1437,11 @@ nl_announce_route(struct nl_parse_state *s)
 }
 
 static inline void
-nl_parse_begin(struct nl_parse_state *s, int scan, int merge)
+nl_parse_begin(struct nl_parse_state *s, int scan)
 {
   memset(s, 0, sizeof (struct nl_parse_state));
   s->pool = nl_linpool;
   s->scan = scan;
-  s->merge = merge;
 }
 
 static inline void
@@ -1581,7 +1584,7 @@ nl_parse_route(struct nl_parse_state *s, struct nlmsghdr *h)
 
   net *net = net_get(p->p.main_channel->table, n);
 
-  if (s->net && !nl_mergable_route(s, net, p, priority, i->rtm_type))
+  if (s->net && !nl_mergable_route(s, net, p, priority, i->rtm_type, i->rtm_family))
     nl_announce_route(s);
 
   rta *ra = lp_allocz(s->pool, RTA_MAX_SIZE);
@@ -1817,34 +1820,14 @@ krt_do_scan(struct krt_proto *p UNUSED)	/* CONFIG_ALL_TABLES_AT_ONCE => p is NUL
   struct nlmsghdr *h;
   struct nl_parse_state s;
 
-  nl_parse_begin(&s, 1, 0);
-  nl_request_dump(AF_INET, RTM_GETROUTE);
+  nl_parse_begin(&s, 1);
+  nl_request_dump(AF_UNSPEC, RTM_GETROUTE);
   while (h = nl_get_scan())
     if (h->nlmsg_type == RTM_NEWROUTE || h->nlmsg_type == RTM_DELROUTE)
       nl_parse_route(&s, h);
     else
       log(L_DEBUG "nl_scan_fire: Unknown packet received (type=%d)", h->nlmsg_type);
   nl_parse_end(&s);
-
-  nl_parse_begin(&s, 1, 1);
-  nl_request_dump(AF_INET6, RTM_GETROUTE);
-  while (h = nl_get_scan())
-    if (h->nlmsg_type == RTM_NEWROUTE || h->nlmsg_type == RTM_DELROUTE)
-      nl_parse_route(&s, h);
-    else
-      log(L_DEBUG "nl_scan_fire: Unknown packet received (type=%d)", h->nlmsg_type);
-  nl_parse_end(&s);
-
-#ifdef HAVE_MPLS_KERNEL
-  nl_parse_begin(&s, 1, 1);
-  nl_request_dump(AF_MPLS, RTM_GETROUTE);
-  while (h = nl_get_scan())
-    if (h->nlmsg_type == RTM_NEWROUTE || h->nlmsg_type == RTM_DELROUTE)
-      nl_parse_route(&s, h);
-    else
-      log(L_DEBUG "nl_scan_fire: Unknown packet received (type=%d)", h->nlmsg_type);
-  nl_parse_end(&s);
-#endif
 }
 
 /*
@@ -1864,7 +1847,7 @@ nl_async_msg(struct nlmsghdr *h)
     case RTM_NEWROUTE:
     case RTM_DELROUTE:
       DBG("KRT: Received async route notification (%d)\n", h->nlmsg_type);
-      nl_parse_begin(&s, 0, 0);
+      nl_parse_begin(&s, 0);
       nl_parse_route(&s, h);
       nl_parse_end(&s);
       break;
diff --git a/sysdep/unix/log.c b/sysdep/unix/log.c
index c9064834..9d107709 100644
--- a/sysdep/unix/log.c
+++ b/sysdep/unix/log.c
@@ -309,14 +309,23 @@ die(const char *msg, ...)
 void
 debug(const char *msg, ...)
 {
+#define MAX_DEBUG_BUFSIZE       65536
   va_list args;
-  char buf[1024];
+  static uint bufsize = 4096;
+  static char *buf = NULL;
+
+  if (!buf)
+    buf = mb_alloc(&root_pool, bufsize);
 
   va_start(args, msg);
   if (dbgf)
     {
-      if (bvsnprintf(buf, sizeof(buf), msg, args) < 0)
-	bsprintf(buf + sizeof(buf) - 100, " ... <too long>\n");
+      while (bvsnprintf(buf, bufsize, msg, args) < 0)
+        if (bufsize >= MAX_DEBUG_BUFSIZE)
+          bug("Extremely long debug output, split it.");
+        else
+          buf = mb_realloc(buf, (bufsize *= 2));
+
       fputs(buf, dbgf);
     }
   va_end(args);
diff --git a/test/birdtest.c b/test/birdtest.c
index 2d1e73de..c0d4bd05 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -44,23 +44,17 @@ int bt_result;			/* Overall program run result */
 int bt_suite_result;		/* One suit result */
 char bt_out_fmt_buf[1024];	/* Temporary memory buffer for output of testing function */
 
-long int
-bt_random(void)
-{
-  /* Seeded in bt_init() */
-  long int rand_low, rand_high;
-
-  rand_low = random();
-  rand_high = random();
-  return (rand_low & 0xffff) | ((rand_high & 0xffff) << 16);
-}
+u64 bt_random_state[] = {
+  0x80241f302bd4d95d, 0xd10ba2e910f772b, 0xea188c9046f507c5, 0x4c4c581f04e6da05,
+  0x53d9772877c1b647, 0xab8ce3eb466de6c5, 0xad02844c8a8e865f, 0xe8cc78080295065d
+};
 
 void
 bt_init(int argc, char *argv[])
 {
   int c;
 
-  srandom(BT_RANDOM_SEED);
+  initstate(BT_RANDOM_SEED, (char *) bt_random_state, sizeof(bt_random_state));
 
   bt_verbose = 0;
   bt_filename = argv[0];
diff --git a/test/birdtest.h b/test/birdtest.h
index 18228711..dacfb095 100644
--- a/test/birdtest.h
+++ b/test/birdtest.h
@@ -33,7 +33,8 @@ extern const char *bt_test_id;
 void bt_init(int argc, char *argv[]);
 int  bt_exit_value(void);
 int bt_test_suite_base(int (*test_fn)(const void *), const char *test_id, const void *test_fn_argument, int forked, int timeout, const char *dsc, ...);
-long int bt_random(void);
+static inline u64 bt_random(void)
+{ return ((u64) random() & 0xffffffff) | ((u64) random() << 32); }
 
 void bt_log_suite_result(int result, const char *fmt, ...);
 void bt_log_suite_case_result(int result, const char *fmt, ...);
@@ -41,7 +42,7 @@ void bt_log_suite_case_result(int result, const char *fmt, ...);
 #define BT_TIMEOUT 			5	/* Default timeout in seconds */
 #define BT_FORKING 			1	/* Forking is enabled in default */
 
-#define BT_RANDOM_SEED 			982451653
+#define BT_RANDOM_SEED 			0x5097d2bb
 
 #define BT_BUFFER_SIZE 			10000