bgpd: When advertising a multipath route, the attribute set to be

advertised is based on the bestpath attribute set, but the
following attributes are aggregated from the attribute sets
of the multipath constituents:
- AS_PATH
- ORIGIN
- COMMUNITIES
- EXTENDED COMMUNITIES

In addition the route is advertised with the NEXT_HOP set
to the router's interface IP address, instead of the NEXT_HOP
of the best path. This is to ensure that traffic will go to this
router so it can be fanned out via the multipath route.

* bgpd/ecommunity.c
  * ecommunity_uniq_sort(): Make this function externally accessible
* bgpd/ecommunity.h
  * Add external declaration for ecommunity_uniq_sort()
* bgpd/bgp_mpath.c
  * bgp_info_nexthop_cmp(): Replace calls to bgp_attr_extra_get()
    to avoid unwanted memory allocation
  * bgp_info_mpath_free(): Free aggregate attribute for multipath
  * bgp_info_mpath_attr(): Lookup aggregate attribute of a multipath route
  * bgp_info_mpath_attr_set(): Set aggregate attribute of a multipath route
  * bgp_info_mpath_aggregate_update(): Update the aggregate attribute
    of a multipath route
* bgpd/bgp_mpath.h
  * bgp_info_mpath: Add pointer to hold aggregate attribute of a multipath
  * Add external declarations for new functions
* bgpd/bgp_route.c
  * bgp_announce_check(): Use aggregate attribute when announcing multipath
    route
  * bgp_announce_check_rsclient(): Use aggregate attribute when announcing
    multipath route
  * bgp_best_selection(): After updating multipath set, update the
    multipath aggregate attribute

5 files changed, 218 insertions, 17 deletions

diff --git a/bgpd/bgp_ecommunity.c b/bgpd/bgp_ecommunity.c
index 8d5fa741..244ffd16 100644
--- a/bgpd/bgp_ecommunity.c
+++ b/bgpd/bgp_ecommunity.c
@@ -98,7 +98,7 @@ ecommunity_add_val (struct ecommunity *ecom, struct ecommunity_val *eval)
 /* This function takes pointer to Extended Communites strucutre then
    create a new Extended Communities structure by uniq and sort each
    Extended Communities value.  */
-static struct ecommunity *
+struct ecommunity *
 ecommunity_uniq_sort (struct ecommunity *ecom)
 {
   int i;
diff --git a/bgpd/bgp_ecommunity.h b/bgpd/bgp_ecommunity.h
index 942fdc73..1a225270 100644
--- a/bgpd/bgp_ecommunity.h
+++ b/bgpd/bgp_ecommunity.h
@@ -71,6 +71,7 @@ extern void ecommunity_free (struct ecommunity *);
 extern struct ecommunity *ecommunity_parse (u_int8_t *, u_short);
 extern struct ecommunity *ecommunity_dup (struct ecommunity *);
 extern struct ecommunity *ecommunity_merge (struct ecommunity *, struct ecommunity *);
+extern struct ecommunity *ecommunity_uniq_sort (struct ecommunity *);
 extern struct ecommunity *ecommunity_intern (struct ecommunity *);
 extern int ecommunity_cmp (const void *, const void *);
 extern void ecommunity_unintern (struct ecommunity *);
diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 7944c55f..44823c4b 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -34,6 +34,9 @@
 #include "bgpd/bgp_route.h"
 #include "bgpd/bgp_attr.h"
 #include "bgpd/bgp_debug.h"
+#include "bgpd/bgp_aspath.h"
+#include "bgpd/bgp_community.h"
+#include "bgpd/bgp_ecommunity.h"
 #include "bgpd/bgp_mpath.h"
 
 /*
@@ -103,8 +106,8 @@ bgp_info_nexthop_cmp (struct bgp_info *bi1, struct bgp_info *bi2)
   struct attr_extra *ae1, *ae2;
   int compare;
 
-  ae1 = bgp_attr_extra_get (bi1->attr);
-  ae2 = bgp_attr_extra_get (bi2->attr);
+  ae1 = bi1->attr->extra;
+  ae2 = bi2->attr->extra;
 
   compare = IPV4_ADDR_CMP (&bi1->attr->nexthop, &bi2->attr->nexthop);
 
@@ -226,6 +229,8 @@ bgp_info_mpath_free (struct bgp_info_mpath **mpath)
 {
   if (mpath && *mpath)
     {
+      if ((*mpath)->mp_attr)
+        bgp_attr_unintern ((*mpath)->mp_attr);
       XFREE (MTYPE_BGP_MPATH_INFO, *mpath);
       *mpath = NULL;
     }
@@ -351,6 +356,37 @@ bgp_info_mpath_count_set (struct bgp_info *binfo, u_int32_t count)
 }
 
 /*
+ * bgp_info_mpath_attr
+ *
+ * Given bestpath bgp_info, return aggregated attribute set used
+ * for advertising the multipath route
+ */
+struct attr *
+bgp_info_mpath_attr (struct bgp_info *binfo)
+{
+  if (!binfo->mpath)
+    return NULL;
+  return binfo->mpath->mp_attr;
+}
+
+/*
+ * bgp_info_mpath_attr_set
+ *
+ * Sets the aggregated attribute into bestpath's mpath element
+ */
+static void
+bgp_info_mpath_attr_set (struct bgp_info *binfo, struct attr *attr)
+{
+  struct bgp_info_mpath *mpath;
+  if (!attr && !binfo->mpath)
+    return;
+  mpath = bgp_info_mpath_get (binfo);
+  if (!mpath)
+    return;
+  mpath->mp_attr = attr;
+}
+
+/*
  * bgp_info_mpath_update
  *
  * Compare and sync up the multipath list with the mp_list generated by
@@ -538,3 +574,156 @@ bgp_mp_dmed_deselect (struct bgp_info *dmed_best)
   UNSET_FLAG (dmed_best->flags, BGP_INFO_MULTIPATH_CHG);
   assert (bgp_info_mpath_first (dmed_best) == 0);
 }
+
+/*
+ * bgp_info_mpath_aggregate_update
+ *
+ * Set the multipath aggregate attribute. We need to see if the
+ * aggregate has changed and then set the ATTR_CHANGED flag on the
+ * bestpath info so that a peer update will be generated. The
+ * change is detected by generating the current attribute,
+ * interning it, and then comparing the interned pointer with the
+ * current value. We can skip this generate/compare step if there
+ * is no change in multipath selection and no attribute change in
+ * any multipath.
+ */
+void
+bgp_info_mpath_aggregate_update (struct bgp_info *new_best,
+                                 struct bgp_info *old_best)
+{
+  struct bgp_info *mpinfo;
+  struct aspath *aspath;
+  struct aspath *asmerge;
+  struct attr *new_attr, *old_attr;
+  u_char origin, attr_chg;
+  struct community *community, *commerge;
+  struct ecommunity *ecomm, *ecommerge;
+  struct attr_extra *ae;
+  struct attr attr = { 0 };
+
+  if (old_best && (old_best != new_best) &&
+      (old_attr = bgp_info_mpath_attr (old_best)))
+    {
+      bgp_attr_unintern (old_attr);
+      bgp_info_mpath_attr_set (old_best, NULL);
+    }
+
+  if (!new_best)
+    return;
+
+  if (!bgp_info_mpath_count (new_best))
+    {
+      if ((new_attr = bgp_info_mpath_attr (new_best)))
+        {
+          bgp_attr_unintern (new_attr);
+          bgp_info_mpath_attr_set (new_best, NULL);
+          SET_FLAG (new_best->flags, BGP_INFO_ATTR_CHANGED);
+        }
+      return;
+    }
+
+  /*
+   * Bail out here if the following is true:
+   * - MULTIPATH_CHG bit is not set on new_best, and
+   * - ATTR_CHANGED bit is not set on new_best or any of the multipaths
+   */
+  attr_chg = 0;
+  if (CHECK_FLAG (new_best->flags, BGP_INFO_ATTR_CHANGED))
+    attr_chg = 1;
+  else
+    for (mpinfo = bgp_info_mpath_first (new_best); mpinfo;
+         mpinfo = bgp_info_mpath_next (mpinfo))
+      {
+        if (CHECK_FLAG (mpinfo->flags, BGP_INFO_ATTR_CHANGED))
+          {
+            attr_chg = 1;
+            break;
+          }
+      }
+  if (!CHECK_FLAG (new_best->flags, BGP_INFO_MULTIPATH_CHG) && !attr_chg)
+    {
+      assert (bgp_info_mpath_attr (new_best));
+      return;
+    }
+
+  bgp_attr_dup (&attr, new_best->attr);
+
+  /* aggregate attribute from multipath constituents */
+  aspath = aspath_dup (attr.aspath);
+  origin = attr.origin;
+  community = attr.community ? community_dup (attr.community) : NULL;
+  ae = attr.extra;
+  ecomm = (ae && ae->ecommunity) ? ecommunity_dup (ae->ecommunity) : NULL;
+
+  for (mpinfo = bgp_info_mpath_first (new_best); mpinfo;
+       mpinfo = bgp_info_mpath_next (mpinfo))
+    {
+      asmerge = aspath_aggregate (aspath, mpinfo->attr->aspath);
+      aspath_free (aspath);
+      aspath = asmerge;
+
+      if (origin < mpinfo->attr->origin)
+        origin = mpinfo->attr->origin;
+
+      if (mpinfo->attr->community)
+        {
+          if (community)
+            {
+              commerge = community_merge (community, mpinfo->attr->community);
+              community = community_uniq_sort (commerge);
+              community_free (commerge);
+            }
+          else
+            community = community_dup (mpinfo->attr->community);
+        }
+
+      ae = mpinfo->attr->extra;
+      if (ae && ae->ecommunity)
+        {
+          if (ecomm)
+            {
+              ecommerge = ecommunity_merge (ecomm, ae->ecommunity);
+              ecomm = ecommunity_uniq_sort (ecommerge);
+              ecommunity_free (ecommerge);
+            }
+          else
+            ecomm = ecommunity_dup (ae->ecommunity);
+        }
+    }
+
+  attr.aspath = aspath;
+  attr.origin = origin;
+  if (community)
+    {
+      attr.community = community;
+      attr.flag |= ATTR_FLAG_BIT (BGP_ATTR_COMMUNITIES);
+    }
+  if (ecomm)
+    {
+      ae = bgp_attr_extra_get (&attr);
+      ae->ecommunity = ecomm;
+      attr.flag |= ATTR_FLAG_BIT (BGP_ATTR_EXT_COMMUNITIES);
+    }
+
+  /* Zap multipath attr nexthop so we set nexthop to self */
+  attr.nexthop.s_addr = 0;
+#ifdef HAVE_IPV6
+  if (attr.extra)
+    memset (&attr.extra->mp_nexthop_global, 0, sizeof (struct in6_addr));
+#endif /* HAVE_IPV6 */
+
+  /* TODO: should we set ATOMIC_AGGREGATE and AGGREGATOR? */
+
+  new_attr = bgp_attr_intern (&attr);
+  bgp_attr_extra_free (&attr);
+
+  if (new_attr != bgp_info_mpath_attr (new_best))
+    {
+      if ((old_attr = bgp_info_mpath_attr (new_best)))
+        bgp_attr_unintern (old_attr);
+      bgp_info_mpath_attr_set (new_best, new_attr);
+      SET_FLAG (new_best->flags, BGP_INFO_ATTR_CHANGED);
+    }
+  else
+    bgp_attr_unintern (new_attr);
+}
diff --git a/bgpd/bgp_mpath.h b/bgpd/bgp_mpath.h
index 3712493e..37b9ac8b 100644
--- a/bgpd/bgp_mpath.h
+++ b/bgpd/bgp_mpath.h
@@ -43,6 +43,9 @@ struct bgp_info_mpath
 
   /* When attached to best path, the number of selected multipaths */
   u_int32_t mp_count;
+
+  /* Aggregated attribute for advertising multipath route */
+  struct attr *mp_attr;
 };
 
 /* Functions to support maximum-paths configuration */
@@ -59,6 +62,8 @@ extern void bgp_mp_dmed_deselect (struct bgp_info *);
 extern void bgp_info_mpath_update (struct bgp_node *, struct bgp_info *,
                                    struct bgp_info *, struct list *,
                                    struct bgp_maxpaths_cfg *);
+extern void bgp_info_mpath_aggregate_update (struct bgp_info *,
+                                             struct bgp_info *);
 
 /* Unlink and free multipath information associated with a bgp_info */
 extern void bgp_info_mpath_dequeue (struct bgp_info *);
@@ -70,5 +75,6 @@ extern struct bgp_info *bgp_info_mpath_next (struct bgp_info *);
 
 /* Accessors for multipath information */
 extern u_int32_t bgp_info_mpath_count (struct bgp_info *);
+extern struct attr *bgp_info_mpath_attr (struct bgp_info *);
 
 #endif /* _QUAGGA_BGP_MPATH_H */
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 5c4ab266..a4923f57 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -785,10 +785,12 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
   struct bgp *bgp;
   int transparent;
   int reflect;
+  struct attr *riattr;
 
   from = ri->peer;
   filter = &peer->filter[afi][safi];
   bgp = peer->bgp;
+  riattr = bgp_info_mpath_count (ri) ? bgp_info_mpath_attr (ri) : ri->attr;
   
   if (DISABLE_BGP_ANNOUNCE)
     return 0;
@@ -803,11 +805,11 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
 
   /* If peer's id and route's nexthop are same. draft-ietf-idr-bgp4-23 5.1.3 */
   if (p->family == AF_INET
-      && IPV4_ADDR_SAME(&peer->remote_id, &ri->attr->nexthop))
+      && IPV4_ADDR_SAME(&peer->remote_id, &riattr->nexthop))
     return 0;
 #ifdef HAVE_IPV6
   if (p->family == AF_INET6
-     && IPV6_ADDR_SAME(&peer->remote_id, &ri->attr->nexthop))
+     && IPV6_ADDR_SAME(&peer->remote_id, &riattr->nexthop))
     return 0;
 #endif
 
@@ -835,14 +837,14 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
     transparent = 0;
 
   /* If community is not disabled check the no-export and local. */
-  if (! transparent && bgp_community_filter (peer, ri->attr)) 
+  if (! transparent && bgp_community_filter (peer, riattr))
     return 0;
 
   /* If the attribute has originator-id and it is same as remote
      peer's id. */
-  if (ri->attr->flag & ATTR_FLAG_BIT (BGP_ATTR_ORIGINATOR_ID))
+  if (riattr->flag & ATTR_FLAG_BIT (BGP_ATTR_ORIGINATOR_ID))
     {
-      if (IPV4_ADDR_SAME (&peer->remote_id, &ri->attr->extra->originator_id))
+      if (IPV4_ADDR_SAME (&peer->remote_id, &riattr->extra->originator_id))
 	{
 	  if (BGP_DEBUG (filter, FILTER))  
 	    zlog (peer->log, LOG_DEBUG,
@@ -865,7 +867,7 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
       }
 
   /* Output filter check. */
-  if (bgp_output_filter (peer, p, ri->attr, afi, safi) == FILTER_DENY)
+  if (bgp_output_filter (peer, p, riattr, afi, safi) == FILTER_DENY)
     {
       if (BGP_DEBUG (filter, FILTER))
 	zlog (peer->log, LOG_DEBUG,
@@ -878,7 +880,7 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
 
 #ifdef BGP_SEND_ASPATH_CHECK
   /* AS path loop check. */
-  if (aspath_loop_check (ri->attr->aspath, peer->as))
+  if (aspath_loop_check (riattr->aspath, peer->as))
     {
       if (BGP_DEBUG (filter, FILTER))  
         zlog (peer->log, LOG_DEBUG, 
@@ -891,7 +893,7 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
   /* If we're a CONFED we need to loop check the CONFED ID too */
   if (CHECK_FLAG(bgp->config, BGP_CONFIG_CONFEDERATION))
     {
-      if (aspath_loop_check(ri->attr->aspath, bgp->confed_id))
+      if (aspath_loop_check(riattr->aspath, bgp->confed_id))
 	{
 	  if (BGP_DEBUG (filter, FILTER))  
 	    zlog (peer->log, LOG_DEBUG, 
@@ -932,7 +934,7 @@ bgp_announce_check (struct bgp_info *ri, struct peer *peer, struct prefix *p,
     }
   
   /* For modify attribute, copy it to temporary structure. */
-  bgp_attr_dup (attr, ri->attr);
+  bgp_attr_dup (attr, riattr);
   
   /* If local-preference is not set. */
   if ((peer_sort (peer) == BGP_PEER_IBGP 
@@ -1091,10 +1093,12 @@ bgp_announce_check_rsclient (struct bgp_info *ri, struct peer *rsclient,
   struct bgp_info info;
   struct peer *from;
   struct bgp *bgp;
+  struct attr *riattr;
 
   from = ri->peer;
   filter = &rsclient->filter[afi][safi];
   bgp = rsclient->bgp;
+  riattr = bgp_info_mpath_count (ri) ? bgp_info_mpath_attr (ri) : ri->attr;
 
   if (DISABLE_BGP_ANNOUNCE)
     return 0;
@@ -1122,10 +1126,10 @@ bgp_announce_check_rsclient (struct bgp_info *ri, struct peer *rsclient,
 
   /* If the attribute has originator-id and it is same as remote
      peer's id. */
-  if (ri->attr->flag & ATTR_FLAG_BIT (BGP_ATTR_ORIGINATOR_ID))
+  if (riattr->flag & ATTR_FLAG_BIT (BGP_ATTR_ORIGINATOR_ID))
     {
       if (IPV4_ADDR_SAME (&rsclient->remote_id, 
-                          &ri->attr->extra->originator_id))
+                          &riattr->extra->originator_id))
         {
          if (BGP_DEBUG (filter, FILTER))
            zlog (rsclient->log, LOG_DEBUG,
@@ -1148,7 +1152,7 @@ bgp_announce_check_rsclient (struct bgp_info *ri, struct peer *rsclient,
       }
 
   /* Output filter check. */
-  if (bgp_output_filter (rsclient, p, ri->attr, afi, safi) == FILTER_DENY)
+  if (bgp_output_filter (rsclient, p, riattr, afi, safi) == FILTER_DENY)
     {
       if (BGP_DEBUG (filter, FILTER))
        zlog (rsclient->log, LOG_DEBUG,
@@ -1161,7 +1165,7 @@ bgp_announce_check_rsclient (struct bgp_info *ri, struct peer *rsclient,
 
 #ifdef BGP_SEND_ASPATH_CHECK
   /* AS path loop check. */
-  if (aspath_loop_check (ri->attr->aspath, rsclient->as))
+  if (aspath_loop_check (riattr->aspath, rsclient->as))
     {
       if (BGP_DEBUG (filter, FILTER))
         zlog (rsclient->log, LOG_DEBUG,
@@ -1172,7 +1176,7 @@ bgp_announce_check_rsclient (struct bgp_info *ri, struct peer *rsclient,
 #endif /* BGP_SEND_ASPATH_CHECK */
 
   /* For modify attribute, copy it to temporary structure. */
-  bgp_attr_dup (attr, ri->attr);
+  bgp_attr_dup (attr, riattr);
 
   /* next-hop-set */
   if ((p->family == AF_INET && attr->nexthop.s_addr == 0)
@@ -1410,6 +1414,7 @@ bgp_best_selection (struct bgp *bgp, struct bgp_node *rn,
   if (!bgp_flag_check (bgp, BGP_FLAG_DETERMINISTIC_MED))
     bgp_info_mpath_update (rn, new_select, old_select, &mp_list, mpath_cfg);
 
+  bgp_info_mpath_aggregate_update (new_select, old_select);
   bgp_mp_list_clear (&mp_list);
 
   result->old = old_select;