Basic route aggregation

Add a new protocol offering route aggregation.

User can specify list of route attributes in the configuration file and
run route aggregation on the export side of the pipe protocol. Routes are
sorted and for every group of equivalent routes new route is created and
exported to the routing table. It is also possible to specify filter
which will run for every route before aggregation.

Furthermore, it will be possible to set attributes of new routes
according to attributes of the aggregated routes.

This is a work in progress.

Original work by Igor Putovny, subsequent cleanups and finalization by
Maria Matejka.

7 files changed, 37 insertions, 7 deletions

diff --git a/nest/a-path.c b/nest/a-path.c
index c421b41f..aba2c86d 100644
--- a/nest/a-path.c
+++ b/nest/a-path.c
@@ -670,6 +670,29 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_va
 }
 
 int
+as_path_compare(const struct adata *path1, const struct adata *path2)
+{
+  uint pos1 = 0;
+  uint pos2 = 0;
+  uint val1 = 0;
+  uint val2 = 0;
+
+  while (1)
+  {
+    int res1 = as_path_walk(path1, &pos1, &val1);
+    int res2 = as_path_walk(path2, &pos2, &val2);
+
+    if (res1 == 0 && res2 == 0)
+      return 0;
+
+    if (val1 == val2)
+      continue;
+
+    return val1 < val2 ? -1 : 1;
+  }
+}
+
+int
 as_path_walk(const struct adata *path, uint *pos, uint *val)
 {
   if (!path)
diff --git a/nest/attrs.h b/nest/attrs.h
index fcd5ac16..aee3468b 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -51,6 +51,7 @@ u32 as_path_get_last_nonaggregated(const struct adata *path);
 int as_path_contains(const struct adata *path, u32 as, int min);
 int as_path_match_set(const struct adata *path, const struct f_tree *set);
 const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos);
+int as_path_compare(const struct adata *path1, const struct adata *path2);
 int as_path_walk(const struct adata *path, uint *pos, uint *val);
 
 static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as)
@@ -238,6 +239,7 @@ int lc_set_max(const struct adata *list, lcomm *val);
 int int_set_walk(const struct adata *list, uint *pos, u32 *val);
 int ec_set_walk(const struct adata *list, uint *pos, u64 *val);
 int lc_set_walk(const struct adata *list, uint *pos, lcomm *val);
+int rte_set_walk(const struct adata *list, u32 *pos, struct rte **val);
 
 void ec_set_sort_x(struct adata *set); /* Sort in place */
 
diff --git a/nest/proto.c b/nest/proto.c
index bc7b7cc8..48ffade5 100644
--- a/nest/proto.c
+++ b/nest/proto.c
@@ -90,7 +90,6 @@ proto_log_state_change(struct proto *p)
     p->last_state_name_announced = NULL;
 }
 
-
 struct channel_config *
 proto_cf_find_channel(struct proto_config *pc, uint net_type)
 {
diff --git a/nest/protocol.h b/nest/protocol.h
index dad0b781..596e810e 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -39,6 +39,7 @@ struct symbol;
 
 enum protocol_class {
   PROTOCOL_NONE,
+  PROTOCOL_AGGREGATOR,
   PROTOCOL_BABEL,
   PROTOCOL_BFD,
   PROTOCOL_BGP,
@@ -103,7 +104,7 @@ void protos_dump_all(void);
 
 extern struct protocol
   proto_device, proto_radv, proto_rip, proto_static, proto_mrt,
-  proto_ospf, proto_perf,
+  proto_ospf, proto_perf, proto_aggregator,
   proto_pipe, proto_bgp, proto_bmp, proto_bfd, proto_babel, proto_rpki;
 
 /*
diff --git a/nest/route.h b/nest/route.h
index 7aec7117..feb1fa60 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -342,6 +342,8 @@ void rt_prune_sync(rtable *t, int all);
 int rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old0, int refeed);
 struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
 
+int rte_same(rte *x, rte *y);
+
 static inline int rt_is_ip(rtable *tab)
 { return (tab->addr_type == NET_IP4) || (tab->addr_type == NET_IP6); }
 
@@ -474,7 +476,8 @@ typedef struct rta {
 #define RTS_BABEL 13			/* Babel route */
 #define RTS_RPKI 14			/* Route Origin Authorization */
 #define RTS_PERF 15			/* Perf checker */
-#define RTS_MAX 16
+#define RTS_AGGREGATED 16		/* Aggregated route */
+#define RTS_MAX 17
 
 #define RTD_NONE 0			/* Undefined next hop */
 #define RTD_UNICAST 1			/* Next hop is neighbor router */
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index d793c72e..b341ff46 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -75,6 +75,8 @@ const char * const rta_src_names[RTS_MAX] = {
   [RTS_PIPE]		= "pipe",
   [RTS_BABEL]		= "Babel",
   [RTS_RPKI]		= "RPKI",
+  [RTS_PERF]		= "Perf",
+  [RTS_AGGREGATED]	= "aggregated",
 };
 
 const char * rta_dest_names[RTD_MAX] = {
@@ -1272,7 +1274,8 @@ rta_dump(rta *a)
   static char *rts[] = { "", "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_PIPE", "RTS_BABEL" };
+			 "RTS_OSPF_EXT2", "RTS_BGP", "RTS_PIPE", "RTS_BABEL",
+			 "RTS_RPKI", "RTS_PERF", "RTS_AGGREGATED", };
   static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
 
   debug("pref=%d uc=%d %s %s%s h=%04x",
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 742e2f05..8b41ffee 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -117,7 +117,7 @@
 pool *rt_table_pool;
 
 static slab *rte_slab;
-static linpool *rte_update_pool;
+linpool *rte_update_pool;
 
 list routing_tables;
 
@@ -975,7 +975,6 @@ rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int
   return best;
 }
 
-
 static void
 rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed,
 		 rte *new_best, rte *old_best, int refeed)
@@ -1206,7 +1205,7 @@ rte_free_quick(rte *e)
   sl_free(e);
 }
 
-static int
+int
 rte_same(rte *x, rte *y)
 {
   /* rte.flags / rte.pflags are not checked, as they are internal to rtable */