Merge tag 'v1.6.2' into int-new

6 files changed, 89 insertions, 35 deletions

diff --git a/nest/a-path.c b/nest/a-path.c
index 32e2d27e..e1031b7b 100644
--- a/nest/a-path.c
+++ b/nest/a-path.c
@@ -435,18 +435,23 @@ parse_path(struct adata *path, struct pm_pos *pos)
 
 
 static int
-pm_match(struct pm_pos *pos, u32 asn)
+pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
 {
+  u32 gas;
   if (! pos->set)
-    return pos->val.asn == asn;
+    return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
 
   u8 *p = pos->val.sp;
   int len = *p++;
   int i;
 
   for (i = 0; i < len; i++)
-    if (get_as(p + i * BS) == asn)
+  {
+    gas = get_as(p + i * BS);
+
+    if ((gas >= asn) && (gas <= asn2))
       return 1;
+  }
 
   return 0;
 }
@@ -490,7 +495,7 @@ pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
  * next part of mask, we advance each marked state.
  * We start with marked first position, when we
  * run out of marked positions, we reject. When
- * we process the whole mask, we accept iff final position
+ * we process the whole mask, we accept if final position
  * (auxiliary position after last real position in AS path)
  * is marked.
  */
@@ -502,6 +507,7 @@ as_path_match(struct adata *path, struct f_path_mask *mask)
   int plen = parse_path(path, pos);
   int l, h, i, nh, nl;
   u32 val = 0;
+  u32 val2 = 0;
 
   /* l and h are bound of interval of positions where
      are marked states */
@@ -525,12 +531,16 @@ as_path_match(struct adata *path, struct f_path_mask *mask)
 	  h = plen;
 	  break;
 
-	case PM_ASN:
-	  val = mask->val;
+	case PM_ASN:	/* Define single ASN as ASN..ASN - very narrow interval */
+	  val2 = val = mask->val;
 	  goto step;
 	case PM_ASN_EXPR:
-	  val = f_eval_asn((struct f_inst *) mask->val);
+	  val2 = val = f_eval_asn((struct f_inst *) mask->val);
 	  goto step;
+	case PM_ASN_RANGE:
+	  val = mask->val;
+	  val2 = mask->val2;
+          goto step;
 	case PM_QUESTION:
 	step:
 	  nh = nl = -1;
@@ -538,7 +548,7 @@ as_path_match(struct adata *path, struct f_path_mask *mask)
 	    if (pos[i].mark)
 	      {
 		pos[i].mark = 0;
-		if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val))
+		if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
 		  pm_mark(pos, i, plen, &nl, &nh);
 	      }
 
diff --git a/nest/attrs.h b/nest/attrs.h
index 0171c6a8..670b048f 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -45,11 +45,13 @@ struct adata *as_path_filter(struct linpool *pool, struct adata *path, struct f_
 #define PM_QUESTION	1
 #define PM_ASTERISK	2
 #define PM_ASN_EXPR	3
+#define PM_ASN_RANGE	4
 
 struct f_path_mask {
   struct f_path_mask *next;
   int kind;
   uintptr_t val;
+  uintptr_t val2;
 };
 
 int as_path_match(struct adata *path, struct f_path_mask *mask);
diff --git a/nest/config.Y b/nest/config.Y
index 2961dafb..2a746657 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -74,7 +74,7 @@ CF_KEYWORDS(RELOAD, IN, OUT, MRTDUMP, MESSAGES, RESTRICT, MEMORY, IGP_METRIC, CL
 CF_KEYWORDS(GRACEFUL, RESTART, WAIT, MAX, FLUSH, AS)
 
 CF_ENUM(T_ENUM_RTS, RTS_, DUMMY, STATIC, INHERIT, DEVICE, STATIC_DEVICE, REDIRECT,
-	RIP, OSPF, OSPF_IA, OSPF_EXT1, OSPF_EXT2, BGP, PIPE)
+	RIP, OSPF, OSPF_IA, OSPF_EXT1, OSPF_EXT2, BGP, PIPE, BABEL)
 CF_ENUM(T_ENUM_SCOPE, SCOPE_, HOST, LINK, SITE, ORGANIZATION, UNIVERSE, UNDEFINED)
 CF_ENUM(T_ENUM_RTC, RTC_, UNICAST, BROADCAST, MULTICAST, ANYCAST)
 CF_ENUM(T_ENUM_RTD, RTD_, ROUTER, DEVICE, BLACKHOLE, UNREACHABLE, PROHIBIT, MULTIPATH)
diff --git a/nest/route.h b/nest/route.h
index b5885ee3..a536def7 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -287,7 +287,7 @@ void rte_update2(struct channel *c, net_addr *n, rte *new, struct rte_src *src);
 /* rte_update() moved to protocol.h to avoid dependency conflicts */
 void rte_discard(rtable *tab, rte *old);
 int rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter);
-rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, struct ea_list **tmpa, int silent);
+rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, struct ea_list **tmpa, linpool *pool, int silent);
 void rt_refresh_begin(rtable *t, struct channel *c);
 void rt_refresh_end(rtable *t, struct channel *c);
 void rt_schedule_prune(rtable *t);
@@ -509,6 +509,8 @@ int mpnh__same(struct mpnh *x, struct mpnh *y); /* Compare multipath nexthops */
 static inline int mpnh_same(struct mpnh *x, struct mpnh *y)
 { return (x == y) || mpnh__same(x, y); }
 struct mpnh *mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp);
+void mpnh_insert(struct mpnh **n, struct mpnh *y);
+int mpnh_is_sorted(struct mpnh *x);
 
 void rta_init(void);
 rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index 167bfc44..bb2b3561 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -250,6 +250,34 @@ mpnh_merge(struct mpnh *x, struct mpnh *y, int rx, int ry, int max, linpool *lp)
   return root;
 }
 
+void
+mpnh_insert(struct mpnh **n, struct mpnh *x)
+{
+  for (; *n; n = &((*n)->next))
+  {
+    int cmp = mpnh_compare_node(*n, x);
+
+    if (cmp < 0)
+      continue;
+    else if (cmp > 0)
+      break;
+    else
+      return;
+  }
+
+  x->next = *n;
+  *n = x;
+}
+
+int
+mpnh_is_sorted(struct mpnh *x)
+{
+  for (; x && x->next; x = x->next)
+    if (mpnh_compare_node(x, x->next) >= 0)
+      return 0;
+
+  return 1;
+}
 
 static struct mpnh *
 mpnh_copy(struct mpnh *o)
@@ -1114,7 +1142,7 @@ rta_dump(rta *a)
   static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
 			 "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP",
 			 "RTS_OSPF", "RTS_OSPF_IA", "RTS_OSPF_EXT1",
-                         "RTS_OSPF_EXT2", "RTS_BGP" };
+                         "RTS_OSPF_EXT2", "RTS_BGP", "RTS_PIPE", "RTS_BABEL" };
   static char *rtc[] = { "", " BC", " MC", " AC" };
   static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
 
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 9e9d4c7a..eb9dc3a5 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -50,7 +50,7 @@ static linpool *rte_update_pool;
 
 static list routing_tables;
 
-static void rt_format_via(rte *e, byte *via);
+static byte *rt_format_via(rte *e);
 static void rt_free_hostcache(rtable *tab);
 static void rt_notify_hostcache(rtable *tab, net *net);
 static void rt_update_hostcache(rtable *tab);
@@ -346,10 +346,7 @@ rte_mergable(rte *pri, rte *sec)
 static void
 rte_trace(struct proto *p, rte *e, int dir, char *msg)
 {
-  byte via[IPA_MAX_TEXT_LENGTH+32];
-
-  rt_format_via(e, via);
-  log(L_TRACE "%s %c %s %N %s", p->name, dir, msg, e->net->n.addr, via);
+  log(L_TRACE "%s %c %s %N %s", p->name, dir, msg, e->net->n.addr, rt_format_via(e));
 }
 
 static inline void
@@ -367,7 +364,7 @@ rte_trace_out(uint flag, struct proto *p, rte *e, char *msg)
 }
 
 static rte *
-export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
+export_filter_(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
 {
   struct proto *p = c->proto;
   struct filter *filter = c->out_filter;
@@ -382,9 +379,9 @@ export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int si
   if (!tmpa)
     tmpa = &tmpb;
 
-  *tmpa = make_tmp_attrs(rt, rte_update_pool);
+  *tmpa = make_tmp_attrs(rt, pool);
 
-  v = p->import_control ? p->import_control(p, &rt, tmpa, rte_update_pool) : 0;
+  v = p->import_control ? p->import_control(p, &rt, tmpa, pool) : 0;
   if (v < 0)
     {
       if (silent)
@@ -403,7 +400,7 @@ export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int si
     }
 
   v = filter && ((filter == FILTER_REJECT) ||
-		 (f_run(filter, &rt, tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT));
+		 (f_run(filter, &rt, tmpa, pool, FF_FORCE_TMPATTR) > F_ACCEPT));
   if (v)
     {
       if (silent)
@@ -426,6 +423,12 @@ export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int si
   return NULL;
 }
 
+static inline rte *
+export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
+{
+  return export_filter_(c, rt0, rt_free, tmpa, rte_update_pool, silent);
+}
+
 static void
 do_rt_notify(struct channel *c, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
 {
@@ -706,7 +709,7 @@ rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_chang
 
 
 static struct mpnh *
-mpnh_merge_rta(struct mpnh *nhs, rta *a, int max)
+mpnh_merge_rta(struct mpnh *nhs, rta *a, linpool *pool, int max)
 {
   struct mpnh nh = { .gw = a->gw, .iface = a->iface };
   struct mpnh *nh2 = (a->dest == RTD_MULTIPATH) ? a->nexthops : &nh;
@@ -714,7 +717,7 @@ mpnh_merge_rta(struct mpnh *nhs, rta *a, int max)
 }
 
 rte *
-rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, int silent)
+rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
 {
   // struct proto *p = c->proto;
   struct mpnh *nhs = NULL;
@@ -726,7 +729,7 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, int
   if (!rte_is_valid(best0))
     return NULL;
 
-  best = export_filter(c, best0, rt_free, tmpa, silent);
+  best = export_filter_(c, best0, rt_free, tmpa, pool, silent);
 
   if (!best || !rte_is_reachable(best))
     return best;
@@ -736,13 +739,13 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, int
     if (!rte_mergable(best0, rt0))
       continue;
 
-    rt = export_filter(c, rt0, &tmp, NULL, 1);
+    rt = export_filter_(c, rt0, &tmp, NULL, pool, 1);
 
     if (!rt)
       continue;
 
     if (rte_is_reachable(rt))
-      nhs = mpnh_merge_rta(nhs, rt->attrs, c->merge_limit);
+      nhs = mpnh_merge_rta(nhs, rt->attrs, pool, c->merge_limit);
 
     if (tmp)
       rte_free(tmp);
@@ -750,11 +753,11 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, int
 
   if (nhs)
   {
-    nhs = mpnh_merge_rta(nhs, best->attrs, c->merge_limit);
+    nhs = mpnh_merge_rta(nhs, best->attrs, pool, c->merge_limit);
 
     if (nhs->next)
     {
-      best = rte_cow_rta(best, rte_update_pool);
+      best = rte_cow_rta(best, pool);
       best->attrs->dest = RTD_MULTIPATH;
       best->attrs->nexthops = nhs;
     }
@@ -805,7 +808,7 @@ rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed
 
   /* Prepare new merged route */
   if (new_best)
-    new_best = rt_export_merged(c, net, &new_best_free, &tmpa, 0);
+    new_best = rt_export_merged(c, net, &new_best_free, &tmpa, rte_update_pool, 0);
 
   /* Prepare old merged route (without proper merged next hops) */
   /* There are some issues with running filter on old route - see rt_notify_basic() */
@@ -919,6 +922,13 @@ rte_validate(rte *e)
     return 0;
   }
 
+  if ((e->attrs->dest == RTD_MULTIPATH) && !mpnh_is_sorted(e->attrs->nexthops))
+    {
+      log(L_WARN "Ignoring unsorted multipath route %N received via %s",
+	  n->n.addr, e->sender->proto->name);
+      return 0;
+    }
+
   return 1;
 }
 
@@ -1848,7 +1858,7 @@ rt_next_hop_update_net(rtable *tab, net *n)
   /* FIXME: Better announcement of merged routes */
   rte_announce_i(tab, RA_MERGED, n, new, old_best, new, old_best);
 
-   if (free_old_best)
+  if (free_old_best)
     rte_free_quick(old_best);
 
   return count;
@@ -2426,11 +2436,14 @@ rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_add
  *  CLI commands
  */
 
-static void
-rt_format_via(rte *e, byte *via)
+static byte *
+rt_format_via(rte *e)
 {
   rta *a = e->attrs;
 
+  /* Max text length w/o IP addr and interface name is 16 */
+  static byte via[IPA_MAX_TEXT_LENGTH+sizeof(a->iface->name)+16];
+
   switch (a->dest)
     {
     case RTD_ROUTER:	bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
@@ -2441,12 +2454,12 @@ rt_format_via(rte *e, byte *via)
     case RTD_MULTIPATH:	bsprintf(via, "multipath"); break;
     default:		bsprintf(via, "???");
     }
+  return via;
 }
 
 static void
 rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
 {
-  byte via[IPA_MAX_TEXT_LENGTH+32];
   byte from[IPA_MAX_TEXT_LENGTH+8];
   byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
   rta *a = e->attrs;
@@ -2455,7 +2468,6 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
   void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs);
   struct mpnh *nh;
 
-  rt_format_via(e, via);
   tm_format_datetime(tm, &config->tf_route, e->lastmod);
   if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
     bsprintf(from, " from %I", a->from);
@@ -2476,7 +2488,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
     get_route_info(e, info, tmpa);
   else
     bsprintf(info, " (%d)", e->pref);
-  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->src->proto->name,
+  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, rt_format_via(e), a->src->proto->name,
 	     tm, from, primary ? (sync_error ? " !" : " *") : "", info);
   for (nh = a->nexthops; nh; nh = nh->next)
     cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1);
@@ -2517,7 +2529,7 @@ rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
       if ((d->export_mode == RSEM_EXPORT) && (ec->ra_mode == RA_MERGED))
         {
 	  rte *rt_free;
-	  e = rt_export_merged(ec, n, &rt_free, &tmpa, 1);
+	  e = rt_export_merged(ec, n, &rt_free, &tmpa, rte_update_pool, 1);
 	  pass = 1;
 
 	  if (!e)