[PATCH 1/1] Implement general aggregation protocol, v6

Alexander V. Chernikov melifaro at ipfw.ru
Wed Aug 15 01:36:56 CEST 2012


---
 configure.in          |    4 +-
 doc/bird.conf.example |    9 +
 doc/bird.sgml         |   56 +++
 filter/config.Y       |    2 +-
 filter/filter.h       |    7 +-
 filter/trie.c         |  111 +++++-
 nest/proto-hooks.c    |   11 +
 nest/proto.c          |    3 +
 nest/protocol.h       |   10 +-
 nest/rt-table.c       |   19 +-
 proto/bgp/attrs.c     | 1057 +++++++++++++++++++++++++++++++++++++++++++++++++
 proto/bgp/bgp.c       |    8 +-
 proto/bgp/bgp.h       |    5 +
 sysdep/autoconf.h.in  |    1 +
 14 files changed, 1279 insertions(+), 24 deletions(-)

diff --git a/configure.in b/configure.in
index dd57ab5..ca9d72d 100644
--- a/configure.in
+++ b/configure.in
@@ -47,11 +47,11 @@ AC_SUBST(runtimedir)
 if test "$enable_ipv6" = yes ; then
 	ip=ipv6
 	SUFFIX=6
-	all_protocols=bgp,ospf,pipe,radv,rip,static
+	all_protocols=bgp,ospf,pipe,radv,rip,static,agg
 else
 	ip=ipv4
 	SUFFIX=""
-	all_protocols=bgp,ospf,pipe,rip,static
+	all_protocols=bgp,ospf,pipe,rip,static,agg
 fi
 
 if test "$given_suffix" = yes ; then
diff --git a/doc/bird.conf.example b/doc/bird.conf.example
index 5e07ab5..2cab8be 100644
--- a/doc/bird.conf.example
+++ b/doc/bird.conf.example
@@ -163,6 +163,15 @@ protocol static {
 #	};
 #}
 		
+#protocol agg {
+#	bgp id 198.51.100.1 as 65000 {
+#		aggregate address 198.51.100.64/26;
+#		aggregate address 198.51.100.0/26 save attributes; # Aggregate AS_PATH
+#		aggregate address 198.51.100.128/16 mandatory list {
+#			198.51.100.12/32;
+#		}; # Announce summary IFF all prefixes from mandatory list exists
+#	}
+#}
 
 #protocol bgp {
 #	disabled;
diff --git a/doc/bird.sgml b/doc/bird.sgml
index 087a4eb..4be00c8 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -1115,6 +1115,62 @@ undefined value is regarded as empty clist for most purposes.
 
 <chapt>Protocols
 
+<sect>Aggregator
+
+<p>Aggregator protocol is not a real routing protocol. It generates summary routes of
+given protocol type. Currently the only supported protocol is BGP.
+
+<sect1>Configuration
+
+<p>Main part of configuration contains one or more definitions of
+BGP ID and AS to generate summarized routes.
+
+<p> Nested aggregation routes are supported with the following limitations:
+Routes are always aggregated into longest-match summary route only. Summary routes
+does not aggregate more specific summary routes within the same protocol. If you need
+complex nested aggregation scenario you have to use several aggregation protocol instances
+to achieve this.
+
+
+<code>
+protocol aggregator <name> {
+	bgp id <id> as <as< {
+		aggregate address <prefix>;
+		aggregate address <prefix< mandatory list {
+			<prefix<,
+			<prefix<,
+			<prefix<
+			};
+		aggregate address <prefix> save attributes;
+	};
+}
+
+<p><descrip>
+	<tag>bgp id <M>id</M> as <m/number/</tag>
+	 This defines BGP route base attributes to use in summary routes.
+	 Note that protocol can aggregate routes with different local AS and
+	 BGP router id by default.
+
+	<tag>aggregate address <m/prefix/</tag> Announce given prefix if any
+	of more specific routes exists. Additionally, you can specify
+	<cf/save attributes/ to save maximum information from every route.
+	Turning this flag on makes BGP aggregate AS-PATH per RFC 4271.
+	Another option that can be used is <cf/mandatory list { }/
+	Prefix is announced IFF all of the mandatory prefixes currently exists
+	in route table.
+</descrip>
+
+<p>Example configuration looks like this:
+
+<p><code>
+protocol aggregator {
+	bgp id 198.51.100.130 as 65000 {
+		aggregate address 198.51.100.0/24;
+		aggregate address 192.168.0.0/16 mandatory list { 192.168.1.1/32 };
+	}
+}
+</code>
+
 <sect>BGP
 
 <p>The Border Gateway Protocol is the routing protocol used for backbone
diff --git a/filter/config.Y b/filter/config.Y
index 0eeb2ce..7aff013 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -558,7 +558,7 @@ fprefix:
  ;
 
 fprefix_set:
-   fprefix { $$ = f_new_trie(cfg_mem); trie_add_fprefix($$, &($1.val.px)); }
+   fprefix { $$ = f_new_trie(cfg_mem, sizeof(struct f_trie_node)); trie_add_fprefix($$, &($1.val.px)); }
  | fprefix_set ',' fprefix { $$ = $1; trie_add_fprefix($$, &($3.val.px)); }
  ;
 
diff --git a/filter/filter.h b/filter/filter.h
index 2386fc9..f2a5d06 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -79,11 +79,13 @@ struct f_tree *build_tree(struct f_tree *);
 struct f_tree *find_tree(struct f_tree *t, struct f_val val);
 int same_tree(struct f_tree *t1, struct f_tree *t2);
 
-struct f_trie *f_new_trie(linpool *lp);
-void trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
+struct f_trie *f_new_trie(linpool *lp, size_t node_size);
+void *trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
 int trie_match_prefix(struct f_trie *t, ip_addr px, int plen);
+void *trie_match_longest_prefix(struct f_trie *t, ip_addr px, int plen);
 int trie_same(struct f_trie *t1, struct f_trie *t2);
 void trie_print(struct f_trie *t);
+void trie_walk(struct f_trie *t, void *func, void *data);
 
 void fprefix_get_bounds(struct f_prefix *px, int *l, int *h);
 
@@ -186,6 +188,7 @@ struct f_trie
 {
   linpool *lp;
   int zero;
+  size_t node_size;
   struct f_trie_node root;
 };
 
diff --git a/filter/trie.c b/filter/trie.c
index 581332c..17ac896 100644
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -75,23 +75,24 @@
 #include "filter/filter.h"
 
 /**
- * f_new_trie
- *
- * Allocates and returns a new empty trie.
+ * f_new_trie - Allocates and returns a new empty trie.
+ * @lp: linear pool to allocate items from
+ * @node_size: element size to allocate
  */
 struct f_trie *
-f_new_trie(linpool *lp)
+f_new_trie(linpool *lp, size_t node_size)
 {
   struct f_trie * ret;
-  ret = lp_allocz(lp, sizeof(struct f_trie));
+  ret = lp_allocz(lp, sizeof(struct f_trie) + node_size - sizeof(struct f_trie_node));
   ret->lp = lp;
+  ret->node_size = node_size;
   return ret;
 }
 
 static inline struct f_trie_node *
 new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
 {
-  struct f_trie_node *n = lp_allocz(t->lp, sizeof(struct f_trie_node));
+  struct f_trie_node *n = lp_allocz(t->lp, t->node_size);
   n->plen = plen;
   n->addr = paddr;
   n->mask = pmask;
@@ -116,9 +117,13 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child)
  * Adds prefix (prefix pattern) @px/@plen to trie @t.  @l and @h are lower
  * and upper bounds on accepted prefix lengths, both inclusive.
  * 0 <= l, h <= 32 (128 for IPv6).
+ *
+ * Returns pointer to allocated node. Function can return pointer to
+ * existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0)
+ * pointer to root node is returned
  */
 
-void
+void *
 trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
 {
   if (l == 0)
@@ -156,7 +161,7 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
 	  attach_node(o, b);
 	  attach_node(b, n);
 	  attach_node(b, a);
-	  return;
+	  return a;
 	}
 
       if (plen < n->plen)
@@ -166,14 +171,14 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
 	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
 	  attach_node(o, a);
 	  attach_node(a, n);
-	  return;
+	  return a;
 	}
 	
       if (plen == n->plen)
 	{
 	  /* We already found added node in trie. Just update accept mask */
 	  n->accept = ipa_or(n->accept, amask);
-	  return;
+	  return n;
 	}
 
       /* Update accept mask part M2 and go deeper */
@@ -187,6 +192,8 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
   /* We add new tail node 'a' after node 'o' */
   struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
   attach_node(o, a);
+
+  return a;
 }
 
 /**
@@ -234,6 +241,90 @@ trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
   return 0;
 }
 
+#define NODE_IS_BRANCHING(x)	(*((u32 *)(((struct f_trie_node *)(x)) + 1)) == 0)
+/**
+ * trie_match_longest_prefix - find longest prefix match
+ * @t: trie
+ * @px: prefix address
+ * @plen: prefix length
+ *
+ * Tries to find a matching prefix pattern in the trie such that
+ * prefix @px/@plen matches that prefix pattern. Returns prefix pointer
+ * or NULL.
+ */
+void *
+trie_match_longest_prefix(struct f_trie *t, ip_addr px, int plen)
+{
+  ip_addr pmask = ipa_mkmask(plen);
+  ip_addr paddr = ipa_and(px, pmask);
+  ip_addr cmask;
+  struct f_trie_node *n = &t->root, *parent = NULL;
+
+  /* Skip root node since it is cath-all node */
+  n = n->c[(ipa_getbit(paddr, 0)) ? 1 : 0];
+
+  while (n)
+    {
+      cmask = ipa_and(n->mask, pmask);
+
+      /* We are out of path */
+      if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask)))
+	break;
+
+      /* Mask is too specific */
+      if (n->plen > plen)
+	break;
+
+      /* Do not save pointer to branching nodes */
+      if (!NODE_IS_BRANCHING(n))
+	parent = n;
+
+      /* Choose children */
+      n = n->c[(ipa_getbit(paddr, n->plen)) ? 1 : 0];
+    }
+
+  /*
+   * parent is either
+   * 1) NULL (if the first non-null node does not exist oris out of path)
+   * or
+   * 2) points to the last entry that match
+   *
+   * In former case we check if catch-all prefix really exists and return
+   * either pointer to root node or NULL. In latter case we simply return parent.
+   */
+
+  return parent ? parent : (t->zero ? &t->root : NULL);
+}
+
+static void
+trie_walk_call(struct f_trie_node *n, void *func, void *data)
+{
+  void (*f)(struct f_trie_node *, void *) = func;
+
+  if (n)
+    f(n, data);
+
+  if (n->c[0])
+    trie_walk_call(n->c[0], func, data);
+
+  if (n->c[1])
+    trie_walk_call(n->c[1], func, data);
+}
+
+void
+trie_walk(struct f_trie *t, void *func, void *data)
+{
+  void (*f)(struct f_trie_node *, void *) = func;
+
+  if (t->zero)
+    f(&t->root, data);
+
+  if (t->root.c[0])
+    trie_walk_call(t->root.c[0], func, data);
+  if (t->root.c[1])
+  trie_walk_call(t->root.c[1], func, data);
+}
+
 static int
 trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
 {
diff --git a/nest/proto-hooks.c b/nest/proto-hooks.c
index e80f87e..22f22ca 100644
--- a/nest/proto-hooks.c
+++ b/nest/proto-hooks.c
@@ -161,6 +161,17 @@ int get_attr(eattr *a, byte *buf, int buflen)
 { DUMMY; }
 
 /**
+ * get_route_ainfo - get additional route information
+ * @c: pointer to cli
+ * @cli_val: cli format value
+ * @e: a route entry
+ *
+ * This hook is called after printing extended route attributes
+ */
+void get_route_ainfo(struct cli *c, int cli_val, rte *e)
+{ DUMMY; }
+
+/**
  * if_notify - notify instance about interface changes
  * @p: protocol instance
  * @flags: interface change flags
diff --git a/nest/proto.c b/nest/proto.c
index 887d3e5..4ebc9d6 100644
--- a/nest/proto.c
+++ b/nest/proto.c
@@ -705,6 +705,9 @@ protos_build(void)
 #ifdef CONFIG_BGP
   proto_build(&proto_bgp);
 #endif
+#ifdef CONFIG_AGG
+  proto_build(&proto_agg);
+#endif
   proto_pool = rp_new(&root_pool, "Protocols");
   proto_flush_event = ev_new(proto_pool);
   proto_flush_event->hook = proto_flush_loop;
diff --git a/nest/protocol.h b/nest/protocol.h
index 8a63271..0a0d8f7 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -28,6 +28,10 @@ struct event;
 struct ea_list;
 struct eattr;
 struct symbol;
+struct agg_sumroute;
+struct agg_route;
+struct agg_proto;
+struct cli;
 
 /*
  *	Routing Protocol
@@ -54,8 +58,12 @@ struct protocol {
   void (*get_status)(struct proto *, byte *buf); /* Get instance status (for `show protocols' command) */
   void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs); /* Get route information (for `show route' command) */
   int (*get_attr)(struct eattr *, byte *buf, int buflen);	/* ASCIIfy dynamic attribute (returns GA_*) */
+  void (*create_sumroute)(struct agg_proto *, struct agg_sumroute *);	/* Create summary route */
+  void (*update_sumroute)(struct agg_proto *, struct agg_sumroute *, struct agg_route *, struct rta *, struct rta *);	/* Update summary route */
+  int (*check_sumroute)(struct agg_proto *, struct agg_sumroute *, struct agg_sumroute *);	/* Check sumroute parameters  */
   void (*show_proto_info)(struct proto *);	/* Show protocol info (for `show protocols all' command) */
   void (*copy_config)(struct proto_config *, struct proto_config *);	/* Copy config from given protocol instance */
+  void (*get_route_ainfo)(struct cli *, int, struct rte *); /* Print additional information (for `show route' command) */
 };
 
 void protos_build(void);
@@ -75,7 +83,7 @@ void protos_dump_all(void);
 
 extern struct protocol
   proto_device, proto_radv, proto_rip, proto_static,
-  proto_ospf, proto_pipe, proto_bgp;
+  proto_ospf, proto_pipe, proto_bgp, proto_agg;
 
 /*
  *	Routing Protocol Instance
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 165f42b..f224cc4 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -1719,7 +1719,7 @@ rt_init_hostcache(rtable *tab)
   hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
 
   hc->lp = lp_new(rt_table_pool, 1008);
-  hc->trie = f_new_trie(hc->lp);
+  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
 
   tab->hostcache = hc;
 }
@@ -1866,7 +1866,7 @@ rt_update_hostcache(rtable *tab)
 
   /* Reset the trie */
   lp_flush(hc->lp);
-  hc->trie = f_new_trie(hc->lp);
+  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
 
   WALK_LIST_DELSAFE(n, x, hc->hostentries)
     {
@@ -1913,7 +1913,7 @@ rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_add
  *  CLI commands
  */
 
-static void
+void
 rt_format_via(rte *e, byte *via)
 {
   rta *a = e->attrs;
@@ -1939,6 +1939,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
   int primary = (e->net->routes == e);
   int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
   struct mpnh *nh;
+  struct protocol *P = a->proto->proto;
 
   rt_format_via(e, via);
   tm_format_datetime(tm, &config->tf_route, e->lastmod);
@@ -1946,7 +1947,7 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
     bsprintf(from, " from %I", a->from);
   else
     from[0] = 0;
-  if (a->proto->proto->get_route_info || d->verbose)
+  if (P->get_route_info || d->verbose)
     {
       /* Need to normalize the extended attributes */
       ea_list *t = tmpa;
@@ -1955,8 +1956,8 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
       ea_merge(t, tmpa);
       ea_sort(tmpa);
     }
-  if (a->proto->proto->get_route_info)
-    a->proto->proto->get_route_info(e, info, tmpa);
+  if (P->get_route_info)
+    P->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->proto->name,
@@ -1964,7 +1965,11 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tm
   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);
   if (d->verbose)
-    rta_show(c, a, tmpa);
+    {
+      rta_show(c, a, tmpa);
+      if (P->get_route_ainfo)
+	P->get_route_ainfo(c, -1007, e);
+    }
 }
 
 static void
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index e5bc84d..4ad1129 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -19,9 +19,18 @@
 #include "lib/resource.h"
 #include "lib/string.h"
 #include "lib/unaligned.h"
+#ifdef CONFIG_AGG
+#include "filter/filter.h"
+#include "proto/agg/agg.h"
+#endif
 
 #include "bgp.h"
 
+#define BDBG(msg, ...)	log("%s:%d " msg, __FUNCTION__, __LINE__, ##__VA_ARGS__)
+#ifdef LOCAL_DEBUG
+#else
+//#define BDBG(msg, ...)
+#endif
 /*
  *   UPDATE message error handling
  *
@@ -1517,6 +1526,1054 @@ bgp_remove_as4_attrs(struct bgp_proto *p, rta *a)
     }
 }
 
+#ifdef CONFIG_AGG
+
+#define BGP_AS_MAX_NUMBER	256
+#define BGP_AS_MAX_LEN		1024	/* 256 4-byte ASNs (maximum tuple size) */
+#define BGP_AS_MAX_PTRS		64	/* 64 tuples max */
+/*
+ * bgp_sorted_add_as4 - add item to sorted array of fixed size
+ * @number: item
+ * @pbuf: pointer to start of array
+ * @count: pointer to current iterms count
+ *
+ * Returns: 1 if item is added (@count is incremented)
+ * 0 if item already exists
+ * -1 if array size is exceeded
+ */
+static int
+bgp_sorted_add_as4(u32 number, u32 *pbuf, byte *count)
+{
+  int min, max, mid, shift;
+
+  if (*count == 0)
+    {
+      *count = 1;
+      *pbuf = number;
+      return 1;
+    }
+
+  /* Binary search */
+  min = 0;
+  max = *count - 1;
+  mid = 0;
+  while (min <= max)
+    {
+      mid = (min + max) / 2;
+      if (pbuf[mid] == number)
+	  return 0;
+
+      if (pbuf[mid] > number)
+	  max = mid - 1;
+      else
+	  min = mid + 1;
+    }
+
+  /* Not found. */
+  if (*count == BGP_AS_MAX_NUMBER - 1)
+    return -1;
+
+  if (pbuf[mid] < number)
+    shift = mid + 1;
+  else
+    shift = mid;
+
+  if (*count > shift)
+    memmove(pbuf + shift + 1, pbuf + shift, (*count - shift) * sizeof(u32));
+  pbuf[shift] = number;
+  *count = *count + 1;
+
+  return 1;
+}
+
+/*
+ * bgp_append_as_tuple - append ASNs from one or more AS_SEQ/AS_SET tuples to an array
+ * @src_buf: buffer with chain of AS_SEQUNCE or AS_SET tuples
+ * @src_len: buffer length
+ * @asn_skip: number of ASNs to skip in first tuple
+ * @as_set_ptrs: pointer to array of pointers to sorted u32 arrays of ASNs
+ * @as_set_len: pointer to array of length of given arrays
+ * @as_set_index: current array index
+ * @lp: linear pool to allocate data from
+ */
+static void
+bgp_append_as_tuple(byte *src_buf, int src_len, int asn_skip, byte **as_set_ptrs, byte *as_set_length, int *as_set_index, struct linpool *lp)
+{
+  u32 asn;
+  int asn_count, i = *as_set_index;
+  u32 *set_ptr;
+  byte *cnt_ptr;
+
+  set_ptr = (u32 *)as_set_ptrs[i];
+  cnt_ptr = &as_set_length[i];
+
+  while (src_len)
+    {
+      asn_count = src_buf[1];
+      src_len -= 2 + 4 * asn_count;
+      src_buf += 2 + 4 * asn_skip;
+      if (asn_skip)
+	{
+	  asn_count -= asn_skip;
+	  asn_skip = 0;
+	}
+      while (asn_count)
+	{
+	  asn = get_u32(src_buf);
+
+	  /* Append number to array */
+	  if (bgp_sorted_add_as4(asn, set_ptr, cnt_ptr) == -1)
+	    {
+	      /* This tuple is full, let's advance to the next */
+
+	      /* We have to leave room for other BGP data */
+	      if (i == BGP_AS_MAX_PTRS - 2)
+		return;
+
+	      *as_set_index = ++i;
+	      as_set_ptrs[i] = lp_alloc(lp, BGP_AS_MAX_LEN);
+	      set_ptr = (u32 *)as_set_ptrs[i];
+	      cnt_ptr = &as_set_length[i];
+
+	      BDBG("Index increased to %d on asn %d count %d", i, asn, as_set_length[i - 1]);
+
+	      /* Add to empty array */
+	      bgp_sorted_add_as4(asn, set_ptr, cnt_ptr);
+	    }
+
+	  //BDBG("Index: %d asn_count: %d cnt: %d curr_asn=%u", i, asn_count, *cnt_ptr, asn);
+
+	  src_buf += 4;
+	  asn_count--;
+	}
+    }
+}
+
+/*
+ * bgp_compile_sum_aspath - make adata attribute for AS_PATH
+ * @as_data_ptr: pointer to common data for all routes
+ * @as_len: common data length
+ * @as_set_ptrs: pointer to array of pointers to sorted u32 arrays of ASNs
+ * @as_set_len: pointer to array of length of given arrays
+ * @as_set_index: current array index
+ * @lp: linear pool to allocate data from
+ *
+ * Function gets 'common' data (possibly consisting of one or more AS_SEQUNCE / AS_SET tuples) and
+ * several arrays with sorted list of ASNs. Each array is converted to AS_SET tuple, All these AS_SET
+ * tuples are added to the end of 'common' data.
+ *
+ */
+static struct adata *
+bgp_compile_sum_aspath(byte *as_data_ptr, int as_len, byte **as_set_ptrs, byte *as_set_len, int *as_set_index, struct linpool *lp)
+{
+  int i, j, len = 0;
+  u32 *asn;
+  byte *q;
+  struct adata *a;
+
+  for (i = 0; i <= *as_set_index; i++)
+    {
+      if (as_set_len[i])
+	len += 2 + 4 * as_set_len[i];
+    }
+
+  //BDBG("bgp_compile_sum_aspath(): Len=%d as_len=%d", len, as_len);
+
+  /* Merge both paths to contiguous storage */
+  a = bgp_alloc_adata(lp, len + as_len);
+  q = a->data;
+  /* Copy 'common' part */
+  memcpy(q, as_data_ptr, as_len);
+
+  if (!len)
+    return a;
+
+  q += as_len;
+  /* For each array, write AS_SET header and data */
+  for (i = 0; i <= *as_set_index; i++)
+    {
+      *q++ = AS_PATH_SET;
+      *q++ = as_set_len[i];
+      asn = (u32 *)as_set_ptrs[i];
+      for (j = 0; j < as_set_len[i]; j++, q += sizeof(u32))
+	put_u32(q, *asn++);
+    }
+
+  return a;
+}
+
+/*
+ * bgp_split_aspath - split AS_PATH into common and 'summary' paths
+ * @ea: new AS_PATH attribuye
+ * @as_data_ptr: pointer to pointer to store common data
+ * @as_len: common data length
+ * @as_set_ptrs: pointer to array of pointers to sorted u32 arrays of ASNs
+ * @as_set_len: pointer to array of length of given arrays
+ * @as_set_index: current array index
+ * @lp: linear pool to allocate data from
+ */
+static void
+bgp_split_aspath(eattr *ea, byte **as_data_ptr, int as_len, byte ***_as_set_ptrs, byte **_as_set_len, int *as_set_index, struct linpool *lp)
+{
+  int sum_len, asn_count, i;
+  byte *src_buf;
+  u32 *set_ptr;
+  byte **as_set_ptrs, *as_set_len;
+
+  /* Allocate and copy common part */
+  *as_data_ptr = lp_alloc(lp, as_len);
+  memcpy(*as_data_ptr, ea->u.ptr->data, as_len);
+
+  /* Allocate indexes */
+  as_set_ptrs = lp_allocz(lp, BGP_AS_MAX_PTRS * sizeof(byte *));
+  as_set_len = lp_allocz(lp, BGP_AS_MAX_PTRS * sizeof(byte *));
+  *_as_set_ptrs = as_set_ptrs;
+  *_as_set_len = as_set_len;
+
+  /* Determine size and beginning of summary data */
+  sum_len = ea->u.ptr->length - as_len;
+  src_buf = ea->u.ptr->data + as_len;
+  i = 0;
+
+  BDBG("Split AS-PATH: common=%d summary=%d", as_len, sum_len);
+
+  if (sum_len == 0)
+    {
+      as_set_ptrs[i] = lp_alloc(lp, BGP_AS_MAX_LEN);
+      *as_set_index = 0;
+      return;
+    }
+
+  /* Parse remaining summary path */
+  while (sum_len)
+    {
+      asn_count = src_buf[1];
+      sum_len -= 2 + 4 * asn_count;
+      src_buf += 2;
+
+      BDBG("Splitting argument of lenght %d, current index %d", asn_count, i);
+      as_set_ptrs[i] = lp_alloc(lp, BGP_AS_MAX_LEN);
+      as_set_len[i] = asn_count;
+      set_ptr = (u32 *)as_set_ptrs[i];
+      /* We use the fact that we store sorted list of ASNs */
+      while (asn_count)
+	{
+	  *set_ptr++ = get_u32(src_buf);
+	  src_buf += 4;
+	  asn_count--;
+	}
+
+      i++;
+    }
+
+  /* Decrement index to reflect last used tuple */
+  if (i > 0)
+    i--;
+
+  /* Store number of indexes used */
+  *as_set_index = i;
+}
+
+/*
+ * bgp_sum_origin - update summary ORIGIN attribute
+ * @attrs: pointer to new route attributes
+ * @origin: pointer to current ORIGIN value
+ */
+inline void
+bgp_sum_origin(rta *attrs, int *origin)
+{
+  struct eattr *ea;
+  int new_origin;
+
+  if (ea = ea_find(attrs->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)))
+    new_origin = ea->u.data;
+  else
+    {
+      switch (attrs->source)
+	{
+	case RTS_OSPF:
+	case RTS_OSPF_IA:
+	case RTS_OSPF_EXT1:
+	case RTS_OSPF_EXT2:
+	  new_origin = ORIGIN_IGP;
+	  break;
+
+	default:
+	  new_origin = ORIGIN_INCOMPLETE;
+	}
+    }
+
+  if (new_origin == ORIGIN_INCOMPLETE)
+    *origin = ORIGIN_INCOMPLETE;
+  else if ((new_origin == ORIGIN_EGP) && (*origin == ORIGIN_IGP))
+    *origin = ORIGIN_EGP;
+}
+
+void
+bgp_print_as_path(byte *buf, int buflen, struct adata *ad, int as_len)
+{
+  int l, tuple_type, as_count, src_len = ad->length;
+  byte *asn_ptr, *src_data = ad->data;
+
+  while (src_len)
+    {
+      as_count = src_data[1];
+      asn_ptr = src_data + 2;
+      tuple_type = src_data[0];
+      src_len -= 2 + 4 * as_count;
+      src_data += 2 + 4 * as_count;
+      as_len -= 2 + 4 * as_count;
+
+      switch (tuple_type)
+	{
+	case AS_PATH_SEQUENCE:
+	case AS_PATH_SET:
+	  l = bsnprintf(buf, buflen, "."); buf += l; buflen -= l;
+	  if (tuple_type == AS_PATH_SET)
+	    {
+	      l = bsnprintf(buf, buflen, " {"); buf += l; buflen -= l;
+	    }
+
+	  while (as_count)
+	    {
+	      l = bsnprintf(buf, buflen, " %d", get_u32(asn_ptr));
+	      buf += l;
+	      buflen -= l;
+	      asn_ptr += 4;
+	      as_count--;
+	    }
+
+	  if (tuple_type == AS_PATH_SET)
+	    {
+	      l = bsnprintf(buf, buflen, "} "); buf += l; buflen -= l;
+	    }
+	}
+
+      if (as_len == 0)
+	{
+	  l = bsnprintf(buf, buflen, "| "); buf += l; buflen -= l;
+	}
+    }
+}
+
+/*
+ * bgp_sum_aspath - update summary AS_PATH attribute
+ * @ea: new AS_PATH attribute, can be NULL
+ * @as_data_ptr: pointer to common data for all routes
+ * @as_len: common data length
+ * @as_set_ptrs: pointer to array of pointers to sorted u32 arrays of ASNs
+ * @as_set_len: pointer to array of length of given arrays
+ * @as_set_index: current array index
+ * @lp: linear pool to allocate data from
+ */
+void
+bgp_sum_aspath(eattr *ea, byte *as_data_ptr, int *as_len, byte **as_set_ptrs, byte *as_set_len, int *as_set_index, struct linpool *lp)
+{
+  int new_len, mlen, slen, asn_cnt, asn_skip = 0;
+  byte *sum_ptr, *new_ptr, *new_ptr_start;
+
+  new_len = ea ? ea->u.ptr->length : 0;
+  new_ptr_start = ea ? ea->u.ptr->data : NULL;
+
+  /* Check if new AS_PATH is the same */
+  if ((*as_len == new_len) && (memcmp(as_data_ptr, new_ptr_start, new_len) == 0))
+    return;
+
+  /*
+   * New AS_PATH differs. We use easy and naive implementation
+   * from RFC4271 9.2.2.2:
+   * 1) Find as much as possible AS_SEQ / AS_SET segments at the
+   * beginning (usually zero)
+   * 1.5) Try to find some common ASNs within the beginning of first
+   * different segment
+   * 2) put the rest into huge sorted AS_SET (or several AS_SETs)
+   */
+
+  /*
+   * Compare AS_SET / AS_SEQ tuples one by one.
+   * We assume both SETs to be validated
+   */
+
+  mlen = MIN(*as_len, new_len);
+  sum_ptr = as_data_ptr;
+  new_ptr = new_ptr_start;
+
+  while (mlen > 0)
+    {
+      /* Check if segment type is the same */
+      if (sum_ptr[0] != new_ptr[0])
+	  break;
+
+      asn_cnt = MIN(sum_ptr[1], new_ptr[1]);
+      slen = 2 + 4 * asn_cnt;
+      if ((memcmp(sum_ptr, new_ptr, slen)) || (sum_ptr[1] != new_ptr[1]))
+	{
+	  //BDBG("Checking of we can save some common ASNs (max %d) from last segment", asn_cnt);
+	  /*
+	   * Check if we can save at least part of AS_SEQ.
+	   * Probably the most we can save is just several
+	   * first ASNs, so currently we don't bother doing
+	   * binary search.
+	   */
+	  if (new_ptr[0] != AS_PATH_SEQUENCE)
+	    break;
+
+	  while (asn_cnt)
+	    {
+	      if (memcmp(sum_ptr + 2 + 4 * asn_skip, new_ptr + 2 + 4 * asn_skip, 4))
+		break;
+	      asn_skip++;
+	      asn_cnt--;
+	    }
+	  //BDBG("Saved %d/%d ASNs", asn_skip, new_ptr[1]);
+	  break;
+	}
+
+      /* Segment is the same, moving to the next  */
+      sum_ptr += slen;
+      new_ptr += slen;
+      mlen -= slen;
+    }
+
+  //BDBG("MIN=%d common_length=%d as_len=%d asn_skip=%d", MIN(*as_len, new_len), MIN(*as_len, new_len) - mlen, *as_len, asn_skip);
+
+  if (sum_ptr != as_data_ptr + *as_len)
+    {
+      /*
+       * 1) new path length  < current path length (and new path is the same as beginning of summary path) e.g.
+       * start_mlen = '.'
+       * new: XXXXXXX.
+       * sum: XXXXXXX.ZZZ
+       * 2) common path is smaller than mlen:
+       * start_mlen = '.'
+       * new: XXXXMMMM.M
+       * sum: XXXXZZZZ.
+       *
+       * Anyway, we have to
+       * 1) move part of common as-path to summarized AS-SET fragment
+       * 2) decrease common path length
+       */
+      //BDBG("Move ASNs from summary to AS-SET, length=%d", as_data_ptr + *as_len - sum_ptr);
+      bgp_append_as_tuple(sum_ptr, as_data_ptr + *as_len - sum_ptr, asn_skip, as_set_ptrs, as_set_len, as_set_index, lp);
+      *as_len = sum_ptr - as_data_ptr;
+      if (asn_skip)
+	{
+	  /* Add part of AS_SEQ into summary ptr */
+	  //BDBG("Increasing as_len %d->%d", *as_len, *as_len + 2 + 4 * asn_skip);
+	  *as_len += 2 + 4 * asn_skip;
+	  /* Correct number of prefixes in last AS_SEQ */
+	  sum_ptr[1] = asn_skip;
+	}
+    }
+
+  if (new_ptr != new_ptr_start + new_len)
+    {
+      /*
+       * 2) common path is smaller than mlen:
+       * start_mlen = '.'
+       * new: XXXXMMMM.M
+       * sum: XXXXZZZZ.
+       *
+       * 3) new path length > current path length (and summary path is the same as beginning of new path) e.g.
+       * start_mlen = '.'
+       * new: XXXXXXX.ZZZ
+       * sum: XXXXXXX.
+       *
+       * Here we have to move end of new path to summarized AS-SET fragment
+       */
+      //BDBG("Move ASNs from new to AS-SET, length=%d", new_ptr_start + new_len - new_ptr);
+      bgp_append_as_tuple(new_ptr, new_ptr_start + new_len - new_ptr, asn_skip, as_set_ptrs, as_set_len, as_set_index, lp);
+    }
+}
+
+/*
+ * bgp_update_sum_rte - create and announce updated summary rte
+ * @p: pointer to protocol instance
+ * @asr: pointer to summary route
+ * @origin: value of ORIGIN attribute
+ * @as_part: pointer to AS_PATH attribute data
+ * @atomic_agg: value of ATOMIC_AGGREGATE attribute
+ * @aggregator: pointer to AGGREGATOR attribute value
+ *
+ * Function creates stable rta (via rta_clone) and announces it
+ */
+static void
+bgp_update_sum_rte(struct agg_proto *p, struct agg_sumroute *asr, int origin, struct adata *as_path, int atomic_agg, struct adata *aggregator)
+{
+  int i, slen;
+  struct ea_list *eal;
+  rta a, *attrs;
+  rte *route;
+  struct adata *atomic_ad;
+
+  slen = atomic_agg ? 4 : 3;
+  eal = lp_allocz(p->lp, sizeof(struct ea_list) + sizeof(eattr) * slen);
+  eal->flags = EALF_SORTED;
+  eal->count = slen;
+
+  i = 0;
+
+  /* ORIGIN */
+  bgp_set_attr(&eal->attrs[i++], BA_ORIGIN, origin);
+
+  /* AS_PATH */
+  bgp_set_attr(&eal->attrs[i++], BA_AS_PATH, (uintptr_t)as_path);
+
+  /* ATOMIC_AGGREGATE */
+  if (atomic_agg)
+    {
+      atomic_ad = bgp_alloc_adata(p->lp, 0);
+      bgp_set_attr(&eal->attrs[i++], BA_ATOMIC_AGGR, (uintptr_t)atomic_ad);
+    }
+
+  /* AGGREGATOR */
+  bgp_set_attr(&eal->attrs[i++], BA_AGGREGATOR, (uintptr_t)aggregator);
+
+  /* Fill in temporary rta */
+  bzero(&a, sizeof(a));
+  a.proto = &p->p;
+  a.source = RTS_BGP;
+  a.scope = SCOPE_UNIVERSE;
+  a.cast = RTC_UNICAST;
+  a.dest = RTD_BLACKHOLE;
+/*
+  a.gw = r->via;
+  a.iface = NULL;
+*/
+  a.eattrs = eal;
+
+  attrs = rta_lookup(&a);
+
+  route = rte_get_temp(attrs);
+
+  /* Save copy of attributes */
+  attrs = rta_clone(attrs);
+
+  route->net = net_get(p->p.table, asr->tn.addr, asr->tn.plen);
+  route->pflags = 0;
+
+  /* Update summary route */
+  rte_update(p->p.table, route->net, &p->p, &p->p, route);
+
+  /* Free old attrs if any */
+  if (asr->attrs)
+    rta_free(asr->attrs);
+  /* Save copy of attributes */
+  asr->attrs = attrs;
+}
+
+/*
+ * Create and announce summary route
+ * @p: pointer to protocol instance
+ * @asr: pointer to summary route
+ */
+void
+bgp_create_sumroute(struct agg_proto *p, struct agg_sumroute *asr)
+{
+  int as_set = 0, as_len = 0, new_len;
+  struct agg_route *ar;
+  struct eattr *ea;
+  struct rta *attrs;
+  node *n, *n_next;
+  int origin = ORIGIN_IGP, atomic_agg = 0;
+  u32 agg_as, agg_id;
+  byte *new_ptr;
+  int as_set_index = 0;
+  int agg_count = 0;
+  byte *as_data_ptr = NULL;
+  struct adata *ad, *as_path;
+  byte *as_set_ptrs[BGP_AS_MAX_PTRS], as_set_len[BGP_AS_MAX_PTRS];
+
+  BDBG("bgp_create_sumroute() called for %I/%d", asr->tn.addr, asr->tn.plen);
+
+  /*
+   * Do route aggregation per RFC4271 9.2.2.2 rules
+   *
+   * [0] NEXT_HOP (4 or 16 or 2x16)
+   * [1] ORIGIN (internal, u32)
+   * [2] AS_PATH (variable)
+   * [3] AGGREGATOR (8 bytes)
+   * [4] ATOMIC_AGGREGATE (opt, 6 bytes)
+   *
+   */
+  /* Zero set length */
+  memset(&as_set_len, 0, sizeof(as_set_len));
+  as_set_ptrs[0] = lp_alloc(p->lp, BGP_AS_MAX_LEN);
+
+  agg_as = asr->u.bgp.local_as;
+  agg_id = asr->u.bgp.local_id;
+  //BDBG("Summary route ASN/ID set to %d/%R", agg_as, agg_id);
+
+  WALK_LIST_DELSAFE(n, n_next, asr->routes)
+    {
+      ar = SKIP_BACK(struct agg_route, n_sumroute, n);
+
+      attrs = ar->attrs;
+      //BDBG("Working on route %I/%d source=%d", ar->fn.prefix, ar->fn.pxlen, attrs->source);
+
+      /*
+       * FIXME: Routes with different MED should not be aggregated.
+       */
+      /* Check every BGP route for valid AS and router ID */
+#if 0
+      if (attrs->source == RTS_BGP)
+	{
+	  bgp_p = (struct bgp_proto *)attrs->proto;
+	  if ((agg_as != bgp_p->local_as) || (agg_id != bgp_p->local_id))
+	    {
+	      log(L_ERR "%s: Cannot aggregate route %I/%d into %I/%d, skipping",
+		p->p.name, asr->tn.addr, asr->tn.plen, ar->fn.prefix, ar->fn.pxlen);
+	      continue;
+	    }
+	}
+#endif
+
+      /*
+       * Check AS_PATH. AS_PATH is normalized to 4b ASNs in bgp_decode_attr().
+       * We assume all AS_PATH attributes BGP routes are encoded in 4b format
+       */
+      if (ea = ea_find(attrs->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH)))
+	{
+	  /* BGP route */
+	  new_len = ea->u.ptr->length;
+	  new_ptr = ea->u.ptr->data;
+	}
+      else
+	{
+	  /* Non-BGP route, let's set empty attribute */
+	  new_len = 0;
+	  new_ptr = NULL;
+	}
+
+      if (asr->flags & AGG_FLAG_MAXINFO)
+	{
+	  if (!as_set)
+	    {
+	      as_len = new_len;
+	      as_data_ptr = lp_alloc(p->lp, as_len ? as_len : 4);
+	      memcpy(as_data_ptr, new_ptr, as_len);
+	      as_set = 1;
+	    }
+	  else if (new_ptr)
+	    bgp_sum_aspath(ea, as_data_ptr, &as_len, as_set_ptrs, as_set_len, &as_set_index, p->lp);
+	}
+
+      /* Check ORIGIN () */
+      bgp_sum_origin(attrs, &origin);
+
+      /* Check ATOMIC_AGGREGATE */
+      if (ea = ea_find(attrs->eattrs, EA_CODE(EAP_BGP, BA_ATOMIC_AGGR)))
+	atomic_agg = 1;
+
+      agg_count++;
+    }
+
+  /* Skip route? */
+  if (!agg_count)
+    {
+      log(L_ERR "%s: Route %I/%d cannot be summarized (no candidates)", p->p.name, asr->tn.addr, asr->tn.plen);
+      return;
+    }
+
+  /* Save current common AS_PATH length */
+  asr->u.bgp.as_path_common = as_len;
+
+  /*
+   * Make out list sorted by default
+   *
+   * [0] ORIGIN (V=1) (internal, u32)
+   * [1] AS_PATH (V=2) (variable)
+   * [2] ATOMIC_AGGREGATE (V=6) (opt, zero)
+   * [3] AGGREGATOR (V=7) (8 bytes)
+   *
+   */
+
+  /* Prepare AS_PATH */
+  as_path = bgp_compile_sum_aspath(as_data_ptr, as_len, as_set_ptrs, as_set_len, &as_set_index, p->lp);
+
+  /* Prepare AGGREGATOR */
+  ad = bgp_alloc_adata(p->lp, 8);
+  new_ptr = ad->data;
+  put_u32(new_ptr, agg_as);
+  put_u32(new_ptr + 4, agg_id);
+
+  /* Create stable attributes with rte */
+  bgp_update_sum_rte(p, asr, origin, as_path, atomic_agg, ad);
+
+  lp_flush(p->lp);
+}
+
+
+
+#define DBG_UPD(x)  BDBG("Summary route update requires reannounce due to changed " x " attribute")
+/*
+ * Update and reannounce summary route
+ * @p: pointer to protocol instance
+ * @asr: pointer to summary route
+ * @ar: changed route
+ * @old: old attributes
+ * @new: new attributes
+ */
+void
+bgp_update_sumroute(struct agg_proto *p, struct agg_sumroute *asr, struct agg_route *ar, struct rta *old, struct rta *new)
+{
+  struct eattr *ea, *ea_new;
+  rta *a;
+  int origin = ORIGIN_IGP, atomic_agg = 0, rebuild = 0;
+  struct adata *as_path, *aggregator;
+  node *n, *n_next;
+
+  BDBG("bgp_update_sumroute: route %I/%d , summary %I/%d", ar->fn.prefix, ar->fn.pxlen, asr->tn.addr, asr->tn.plen);
+
+  if (!(a = asr->attrs))
+    {
+      if (!new)
+	return;
+
+      bgp_create_sumroute(p, asr);
+      return;
+    }
+
+  /*
+   * [0] ORIGIN (V=1) (internal, u32)
+   * [1] AS_PATH (V=2) (variable)
+   * [3] ATOMIC_AGGREGATE (V=6) (opt, zero)
+   * [4] AGGREGATOR (V=7) (8 bytes)
+   *
+   */
+  if (!new)
+    {
+      /*
+       * Route withdrawal.
+       * Note this is definitely not the last route
+       */
+
+      /* Check if we can skip rebuilding */
+      BDBG("Withdrawing route %I/%d from summary %I/%d", ar->fn.prefix, ar->fn.pxlen, asr->tn.addr, asr->tn.plen);
+
+      /*
+       * AS_PATH
+       * If MAXINFO flag is NOT set we don't care (AS_PATH is empty)
+       * if MAXINFO is set but attribute length is zero we don't care, too
+       * if this is not BGP route we don't care (yes, we CAN possibly optimize AS_PATH but we skip this for prefix stability)
+       * Otherwise, full rebuild is requires
+       */
+      if ((asr->flags & AGG_FLAG_MAXINFO) && (ea = ea_find(old->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH))))
+	{
+	  if ((ea) && (ea->u.ptr->length > 0))
+	    {
+	      /*
+	       * We have to save every AS in AS_PATH and it is not empty.
+	       */
+	      DBG_UPD("AS_PATH");
+	      bgp_create_sumroute(p, asr);
+	      return;
+	    }
+	}
+
+      /* Summary AS_PATH is not changed */
+
+      /*
+       * ORIGIN
+       * In most cases we got INCOMPLETE in both summary route and witdrawn attribute,
+       * so we simply cycle thru all more specific routes to determine new origin attribute
+       *
+       * ATOMIC_AGGREGATE
+       * Check for its new value, too
+       */
+
+      WALK_LIST_DELSAFE(n, n_next, asr->routes)
+	{
+	  ar = SKIP_BACK(struct agg_route, n_sumroute, n);
+
+	  BDBG("Working on route %I/%d", ar->fn.prefix, ar->fn.pxlen);
+	  bgp_sum_origin(ar->attrs, &origin);
+
+	  if (ea = ea_find(ar->attrs->eattrs, EA_CODE(EAP_BGP, BA_ATOMIC_AGGR)))
+	    atomic_agg = 1;
+	}
+
+      if (ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)))
+	{
+	  if ((ea->u.data != origin))
+	    {
+	      DBG_UPD("ORIGIN");
+	      rebuild = 1;
+	    }
+	}
+
+      /*
+       * ATOMIC_AGG attrbiute can only disappear (since we're not generating it locally)
+       * So, we should compare current value (by ea_find) and new value of atomic_agg
+       */
+      if ((ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ATOMIC_AGGR))) && (atomic_agg == 0))
+	{
+	  DBG_UPD("ATOMIC_AGG");
+	  rebuild = 1;
+	}
+
+      if (!rebuild)
+	{
+	  BDBG("Withdrawal of route %I/%d does not require summary route to be updated", ar->fn.prefix, ar->fn.pxlen);
+	  return;
+	}
+
+      BDBG("Withdrawal of route %I/%d require summary route to be updated", ar->fn.prefix, ar->fn.pxlen);
+
+      /*
+       * We don't need full update here since we already know all summarized attributes data:
+       * AS_PATH is empty
+       * ORIGIN / ATOMIC_AGGREGATE values are known
+       * AGGREGATOR value cannot change (so we import it from current summary route)
+       */
+
+      /* AS_PATH is unchanged. Copy from current attribute */
+      ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+      as_path = ea->u.ptr;
+
+      /* Create AGGREGATOR attribute */
+      aggregator = bgp_alloc_adata(p->lp, 8);
+
+      if (ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR)))
+	memcpy(aggregator + 1, ea->u.ptr->data, 8);
+
+      bgp_update_sum_rte(p, asr, origin, as_path, atomic_agg, aggregator);
+      lp_flush(p->lp);
+      return;
+    }
+
+  /************************************************
+  *         New route or route update.            *
+  ************************************************/
+  /* Check ORIGIN */
+  if (ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)))
+    {
+      origin = ea->u.data;
+      bgp_sum_origin(new, &origin);
+      if (origin != ea->u.data)
+	{
+	  DBG_UPD("ORIGIN");
+	  rebuild = 1;
+	}
+    }
+
+  /* Check AS_PATH */
+  ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+
+  byte **as_set_ptrs, *as_set_len;
+  int as_len, as_set_index;
+  byte *as_data_ptr;
+  struct eattr *ea_old;
+
+  /*
+   * Check if new route:
+   * 1) is BGP route (contains AS_PATH)
+   * 2) New AS_PATH is not empty
+   * 3) New AS_PATH is different
+   */
+  as_path = NULL;
+
+  if (asr->flags & AGG_FLAG_MAXINFO)
+    {
+
+      /* BGP new route/route update */
+      ea_new = ea_find(new->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+      if (old)
+	{
+	 /*
+	  *  Route update
+	  *
+	  *    4 different cases here:
+	  *
+	  *             NEW RTE
+	  *           RTS_*  RTS_BGP
+	  *         +---------------+
+	  *         |       |       |
+	  *  RTS_*  | 1 OK  | 2 R   |
+	  *         |       |       |
+	  *  OLD    +----------------
+	  *         |       |       |
+	  * RTS_BGP | 3 R   | 3 OK* |
+	  *         |       |       |
+	  *         +---------------+
+	  *
+	  * 1) Non-BGP route update. Nothing changes
+	  * 2) Non-BGP to BGP route update. Do rebuild
+	  * 3) Vise versa. Do rebuild
+	  * 4) Skip rebuild IFF paths are the same
+	  *
+	  */
+
+	  ea_old = ea_find(old->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+
+	  /*
+	   * Check for case 2 and case 3
+	   */
+	  if ((!ea_old && ea_new) || (ea_old && !ea_new))
+	    {
+	      bgp_create_sumroute(p, asr);
+	      return;
+	    }
+
+	  /*
+	   * Case 4
+	   * We can skip rebuilding IFF AS_PATH is not changed.
+	   * Otherwise, we have to to rebuild since we don't want to keep heavy logic here.
+	   * Good example for doing rebuild is the folllowing:
+	   * old: XXXX YYYY ZZZZ MMMM
+	   * new: XXXX ZZZZ MMMM
+	   */
+	  if ((ea_new && ea_old) && ((ea_new->u.ptr->length != ea_old->u.ptr->length) ||
+		(memcmp(ea_new->u.ptr->data, ea_old->u.ptr->data, ea_new->u.ptr->length))))
+	    {
+	      bgp_create_sumroute(p, asr);
+	      return;
+	    }
+	}
+      else
+	{
+	  /*
+	   * New route.
+	   *
+	   * Let's check if we need to update AS_PATH.
+	   *
+	   * Summary attribute consists of 2 parts:
+	   * 1) common part for all AS_PATHS
+	   * 2) several AS_SETS with evey other ASes (possibly empty)
+	   *
+	   * sum: XXXX YYYY ZZZZ | { AAAA BBBB CCCC }
+	   *      \- as_length -/
+	   * new: KKKK BBBB DDDD
+	   *
+	   * We can skip rebuilding IFF
+	   * 0) This is BGP route
+	   * 1) new length == as_length AND
+	   * 2) these pieces are the same
+	   */
+	  as_len = asr->u.bgp.as_path_common;
+	  if ((!ea_new) || (as_len != ea_new->u.ptr->length) || (memcmp(ea->u.ptr->data, ea_new->u.ptr->data, as_len)))
+	    rebuild = 1;
+	}
+
+      if (rebuild)
+	{
+	  /*
+	   * Either new as-path length is smaller than common path length in aggregated route
+	   * or common part differs between new and aggregated. We have to update attribute (and reannounce route)
+	   */
+	  /* Split summary as_path to 'common' and 'summary' part in proper format */
+	  bgp_split_aspath(ea, &as_data_ptr, as_len, &as_set_ptrs, &as_set_len, &as_set_index, p->lp);
+	  /* Merge new path (NULL path is OK) */
+	  bgp_sum_aspath(ea_new, as_data_ptr, &as_len, as_set_ptrs, as_set_len, &as_set_index, p->lp);
+	  /* Compile resulting path */
+	  as_path = bgp_compile_sum_aspath(as_data_ptr, as_len, as_set_ptrs, as_set_len, &as_set_index, p->lp);
+	  /* Note we have to store upfated as_len below. */
+	  DBG_UPD("AS_PATH");
+	  rebuild = 1;
+	}
+    }
+
+  /* Check ATOMIC_AGGREGATE */
+  if (ea = ea_find(new->eattrs, EA_CODE(EAP_BGP, BA_ATOMIC_AGGR)))
+    atomic_agg = 1;
+
+  if ((ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ATOMIC_AGGR)) == NULL) && (atomic_agg))
+    {
+      DBG_UPD("ATOMIC_AGGREGATE");
+      rebuild = 1;
+    }
+
+  /* Check ORIGIN */
+  if (ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_ORIGIN)))
+    {
+      origin = ea->u.data;
+      bgp_sum_origin(new, &origin);
+      if (origin != ea->u.data)
+	{
+	  DBG_UPD("ORIGIN");
+	  rebuild = 1;
+	}
+    }
+
+  /* Check AGGREGATOR */
+#if 0
+  struct bgp_proto *bgp_p = NULL;
+  byte agg[8];
+  if (new->source == RTS_BGP)
+    {
+      bgp_p = (struct bgp_proto *)new->proto;
+      put_u32(agg, bgp_p->local_as);
+      put_u32(agg + 4, bgp_p->local_id);
+      ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
+      if (memcmp(agg, ea->u.ptr->data, 8))
+	{
+	  BDBG("New route %I/%d %d/%R ASN/BGP ID differs from summary route (%d/%R). Ignoring",
+	    ar->fn.prefix, ar->fn.pxlen, bgp_p->local_as, bgp_p->local_id,
+	    get_u32(ea->u.ptr->data), get_u32(ea->u.ptr->data + 4));
+	  if (rebuild)
+	    lp_flush(p->lp);
+	  return;
+	}
+    }
+#endif
+
+  if (!rebuild)
+    {
+      BDBG("New route %I/%d does not require summary route to be updated", ar->fn.prefix, ar->fn.pxlen);
+      return;
+    }
+
+  DBG("New route %I/%d requires summary route to be updated", ar->fn.prefix, ar->fn.pxlen);
+
+  /* Copy current AS_PATH if not set */
+  if (!as_path)
+    {
+      ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AS_PATH));
+      as_len = ea->u.ptr->length;
+      as_path = bgp_alloc_adata(p->lp, as_len);
+      memcpy(as_path->data, ea->u.ptr->data, as_len);
+    }
+  else
+    {
+      /* Update summary route delimiter */
+      asr->u.bgp.as_path_common = as_len;
+    }
+
+  /* Copy AGGREGATOR attribute */
+  aggregator = bgp_alloc_adata(p->lp, 8);
+
+  /*
+   * We ALWAYS create AGGREGATOR attribute (RFC 4271, 9.2.2.2 / 5.1.7)
+   * and it is ALWAYS the same.
+   */
+  ea = ea_find(a->eattrs, EA_CODE(EAP_BGP, BA_AGGREGATOR));
+  memcpy(aggregator + 1, ea->u.ptr->data, 8);
+
+  bgp_update_sum_rte(p, asr, origin, as_path, atomic_agg, aggregator);
+  lp_flush(p->lp);
+}
+#undef BGP_UPD
+
+/*
+ * bgp_check_sumroute - checks if protocol specific parameters are the same
+ * @p: pointer to protocol instance
+ * @asr_o: old summary route
+ * @asr: new summary route
+ *
+ * Returns 1 if parameters are the same, 0 otherwise.
+ */
+int
+bgp_check_sumroute(struct agg_proto *p, struct agg_sumroute *asr_o, struct agg_sumroute *asr)
+{
+  if ((asr_o->u.bgp.local_id != asr->u.bgp.local_id) ||
+	(asr_o->u.bgp.local_as != asr->u.bgp.local_as))
+    return 0;
+
+  return 1;
+}
+
+#endif /* CONFIG_AGG */
+
 /**
  * bgp_decode_attrs - check and decode BGP attributes
  * @conn: connection
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index 0b52ded..1d89950 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -1203,6 +1203,7 @@ bgp_show_proto_info(struct proto *P)
     }
 }
 
+
 struct protocol proto_bgp = {
   name:			"BGP",
   template:		"bgp%d",
@@ -1217,5 +1218,10 @@ struct protocol proto_bgp = {
   get_status:		bgp_get_status,
   get_attr:		bgp_get_attr,
   get_route_info:	bgp_get_route_info,
-  show_proto_info:	bgp_show_proto_info
+  show_proto_info:	bgp_show_proto_info,
+#ifdef CONFIG_AGG
+  create_sumroute:	bgp_create_sumroute,
+  update_sumroute:	bgp_update_sumroute,
+  check_sumroute:	bgp_check_sumroute
+#endif
 };
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index c3adf25..ae62c30 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -183,6 +183,11 @@ static inline void set_next_hop(byte *b, ip_addr addr) { ((ip_addr *) b)[0] = ad
 
 void bgp_attach_attr(struct ea_list **to, struct linpool *pool, unsigned attr, uintptr_t val);
 byte *bgp_attach_attr_wa(struct ea_list **to, struct linpool *pool, unsigned attr, unsigned len);
+#ifdef CONFIG_AGG
+void bgp_create_sumroute(struct agg_proto *p, struct agg_sumroute *asr);
+void bgp_update_sumroute(struct agg_proto *p, struct agg_sumroute *asr, struct agg_route *ar, struct rta *old, struct rta *new);
+int bgp_check_sumroute(struct agg_proto *p, struct agg_sumroute *asr_o, struct agg_sumroute *asr);
+#endif
 struct rta *bgp_decode_attrs(struct bgp_conn *conn, byte *a, unsigned int len, struct linpool *pool, int mandatory);
 int bgp_get_attr(struct eattr *e, byte *buf, int buflen);
 int bgp_rte_better(struct rte *, struct rte *);
diff --git a/sysdep/autoconf.h.in b/sysdep/autoconf.h.in
index ac6f7a8..4d4dba5 100644
--- a/sysdep/autoconf.h.in
+++ b/sysdep/autoconf.h.in
@@ -42,6 +42,7 @@
 #undef CONFIG_BGP
 #undef CONFIG_OSPF
 #undef CONFIG_PIPE
+#undef CONFIG_AGG
 
 /* We have <syslog.h> and syslog() */
 #undef HAVE_SYSLOG
-- 
1.7.3.2


--------------080704030901000704090208--



More information about the Bird-users mailing list