1 files changed, 313 insertions, 0 deletions

diff --git a/bgpd/bgp_mpath.c b/bgpd/bgp_mpath.c
index 09b46951..af1c342c 100644
--- a/bgpd/bgp_mpath.c
+++ b/bgpd/bgp_mpath.c
@@ -27,11 +27,13 @@
 #include "prefix.h"
 #include "linklist.h"
 #include "sockunion.h"
+#include "memory.h"
 
 #include "bgpd/bgpd.h"
 #include "bgpd/bgp_table.h"
 #include "bgpd/bgp_route.h"
 #include "bgpd/bgp_attr.h"
+#include "bgpd/bgp_debug.h"
 #include "bgpd/bgp_mpath.h"
 
 /*
@@ -200,3 +202,314 @@ bgp_mp_list_add (struct list *mp_list, struct bgp_info *mpinfo)
   assert (mp_list && mpinfo);
   listnode_add_sort (mp_list, mpinfo);
 }
+
+/*
+ * bgp_info_mpath_new
+ *
+ * Allocate and zero memory for a new bgp_info_mpath element
+ */
+static struct bgp_info_mpath *
+bgp_info_mpath_new (void)
+{
+  struct bgp_info_mpath *new_mpath;
+  new_mpath = XCALLOC (MTYPE_BGP_MPATH_INFO, sizeof (struct bgp_info_mpath));
+  return new_mpath;
+}
+
+/*
+ * bgp_info_mpath_free
+ *
+ * Release resources for a bgp_info_mpath element and zero out pointer
+ */
+void
+bgp_info_mpath_free (struct bgp_info_mpath **mpath)
+{
+  if (mpath && *mpath)
+    {
+      XFREE (MTYPE_BGP_MPATH_INFO, *mpath);
+      *mpath = NULL;
+    }
+}
+
+/*
+ * bgp_info_mpath_get
+ *
+ * Fetch the mpath element for the given bgp_info. Used for
+ * doing lazy allocation.
+ */
+static struct bgp_info_mpath *
+bgp_info_mpath_get (struct bgp_info *binfo)
+{
+  struct bgp_info_mpath *mpath;
+  if (!binfo->mpath)
+    {
+      mpath = bgp_info_mpath_new();
+      if (!mpath)
+        return NULL;
+      binfo->mpath = mpath;
+      mpath->mp_info = binfo;
+    }
+  return binfo->mpath;
+}
+
+/*
+ * bgp_info_mpath_enqueue
+ *
+ * Enqueue a path onto the multipath list given the previous multipath
+ * list entry
+ */
+static void
+bgp_info_mpath_enqueue (struct bgp_info *prev_info, struct bgp_info *binfo)
+{
+  struct bgp_info_mpath *prev, *mpath;
+
+  prev = bgp_info_mpath_get (prev_info);
+  mpath = bgp_info_mpath_get (binfo);
+  if (!prev || !mpath)
+    return;
+
+  mpath->mp_next = prev->mp_next;
+  mpath->mp_prev = prev;
+  if (prev->mp_next)
+    prev->mp_next->mp_prev = mpath;
+  prev->mp_next = mpath;
+
+  SET_FLAG (binfo->flags, BGP_INFO_MULTIPATH);
+}
+
+/*
+ * bgp_info_mpath_dequeue
+ *
+ * Remove a path from the multipath list
+ */
+void
+bgp_info_mpath_dequeue (struct bgp_info *binfo)
+{
+  struct bgp_info_mpath *mpath = binfo->mpath;
+  if (!mpath)
+    return;
+  if (mpath->mp_prev)
+    mpath->mp_prev->mp_next = mpath->mp_next;
+  if (mpath->mp_next)
+    mpath->mp_next->mp_prev = mpath->mp_prev;
+  mpath->mp_next = mpath->mp_prev = NULL;
+  UNSET_FLAG (binfo->flags, BGP_INFO_MULTIPATH);
+}
+
+/*
+ * bgp_info_mpath_next
+ *
+ * Given a bgp_info, return the next multipath entry
+ */
+struct bgp_info *
+bgp_info_mpath_next (struct bgp_info *binfo)
+{
+  if (!binfo->mpath || !binfo->mpath->mp_next)
+    return NULL;
+  return binfo->mpath->mp_next->mp_info;
+}
+
+/*
+ * bgp_info_mpath_first
+ *
+ * Given bestpath bgp_info, return the first multipath entry.
+ */
+struct bgp_info *
+bgp_info_mpath_first (struct bgp_info *binfo)
+{
+  return bgp_info_mpath_next (binfo);
+}
+
+/*
+ * bgp_info_mpath_count
+ *
+ * Given the bestpath bgp_info, return the number of multipath entries
+ */
+u_int32_t
+bgp_info_mpath_count (struct bgp_info *binfo)
+{
+  if (!binfo->mpath)
+    return 0;
+  return binfo->mpath->mp_count;
+}
+
+/*
+ * bgp_info_mpath_count_set
+ *
+ * Sets the count of multipaths into bestpath's mpath element
+ */
+static void
+bgp_info_mpath_count_set (struct bgp_info *binfo, u_int32_t count)
+{
+  struct bgp_info_mpath *mpath;
+  if (!count && !binfo->mpath)
+    return;
+  mpath = bgp_info_mpath_get (binfo);
+  if (!mpath)
+    return;
+  mpath->mp_count = count;
+}
+
+/*
+ * bgp_info_mpath_update
+ *
+ * Compare and sync up the multipath list with the mp_list generated by
+ * bgp_best_selection
+ */
+void
+bgp_info_mpath_update (struct bgp_node *rn, struct bgp_info *new_best,
+                       struct bgp_info *old_best, struct list *mp_list,
+                       struct bgp_maxpaths_cfg *mpath_cfg)
+{
+  u_int16_t maxpaths, mpath_count, old_mpath_count;
+  struct listnode *mp_node, *mp_next_node;
+  struct bgp_info *cur_mpath, *new_mpath, *next_mpath, *prev_mpath;
+  int mpath_changed, debug;
+  char pfx_buf[INET_ADDRSTRLEN], nh_buf[2][INET_ADDRSTRLEN];
+
+  mpath_changed = 0;
+  maxpaths = BGP_DEFAULT_MAXPATHS;
+  mpath_count = 0;
+  cur_mpath = NULL;
+  old_mpath_count = 0;
+  prev_mpath = new_best;
+  mp_node = listhead (mp_list);
+  debug = BGP_DEBUG (events, EVENTS);
+
+  if (debug)
+    prefix2str (&rn->p, pfx_buf, sizeof (pfx_buf));
+
+  if (new_best)
+    {
+      mpath_count++;
+      if (new_best != old_best)
+        bgp_info_mpath_dequeue (new_best);
+      maxpaths = (peer_sort (new_best->peer) == BGP_PEER_IBGP) ?
+        mpath_cfg->maxpaths_ibgp : mpath_cfg->maxpaths_ebgp;
+    }
+
+  if (old_best)
+    {
+      cur_mpath = bgp_info_mpath_first (old_best);
+      old_mpath_count = bgp_info_mpath_count (old_best);
+      bgp_info_mpath_count_set (old_best, 0);
+      bgp_info_mpath_dequeue (old_best);
+    }
+
+  /*
+   * We perform an ordered walk through both lists in parallel.
+   * The reason for the ordered walk is that if there are paths
+   * that were previously multipaths and are still multipaths, the walk
+   * should encounter them in both lists at the same time. Otherwise
+   * there will be paths that are in one list or another, and we
+   * will deal with these separately.
+   *
+   * Note that new_best might be somewhere in the mp_list, so we need
+   * to skip over it
+   */
+  while (mp_node || cur_mpath)
+    {
+      /*
+       * We can bail out of this loop if all existing paths on the
+       * multipath list have been visited (for cleanup purposes) and
+       * the maxpath requirement is fulfulled
+       */
+      if (!cur_mpath && (mpath_count >= maxpaths))
+        break;
+
+      mp_next_node = mp_node ? listnextnode (mp_node) : NULL;
+      next_mpath = cur_mpath ? bgp_info_mpath_next (cur_mpath) : NULL;
+
+      /*
+       * If equal, the path was a multipath and is still a multipath.
+       * Insert onto new multipath list if maxpaths allows.
+       */
+      if (mp_node && (listgetdata (mp_node) == cur_mpath))
+        {
+          list_delete_node (mp_list, mp_node);
+          bgp_info_mpath_dequeue (cur_mpath);
+          if ((mpath_count < maxpaths) &&
+              bgp_info_nexthop_cmp (prev_mpath, cur_mpath))
+            {
+              bgp_info_mpath_enqueue (prev_mpath, cur_mpath);
+              prev_mpath = cur_mpath;
+              mpath_count++;
+            }
+          else
+            {
+              mpath_changed = 1;
+              if (debug)
+                zlog_debug ("%s remove mpath nexthop %s peer %s", pfx_buf,
+                            inet_ntop (AF_INET, &cur_mpath->attr->nexthop,
+                                       nh_buf[0], sizeof (nh_buf[0])),
+                            sockunion2str (cur_mpath->peer->su_remote,
+                                           nh_buf[1], sizeof (nh_buf[1])));
+            }
+          mp_node = mp_next_node;
+          cur_mpath = next_mpath;
+          continue;
+        }
+
+      if (cur_mpath && (!mp_node ||
+                        (bgp_info_mpath_cmp (cur_mpath,
+                                             listgetdata (mp_node)) < 0)))
+        {
+          /*
+           * If here, we have an old multipath and either the mp_list
+           * is finished or the next mp_node points to a later
+           * multipath, so we need to purge this path from the
+           * multipath list
+           */
+          bgp_info_mpath_dequeue (cur_mpath);
+          mpath_changed = 1;
+          if (debug)
+            zlog_debug ("%s remove mpath nexthop %s peer %s", pfx_buf,
+                        inet_ntop (AF_INET, &cur_mpath->attr->nexthop,
+                                   nh_buf[0], sizeof (nh_buf[0])),
+                        sockunion2str (cur_mpath->peer->su_remote,
+                                       nh_buf[1], sizeof (nh_buf[1])));
+          cur_mpath = next_mpath;
+        }
+      else
+        {
+          /*
+           * If here, we have a path on the mp_list that was not previously
+           * a multipath (due to non-equivalance or maxpaths exceeded),
+           * or the matching multipath is sorted later in the multipath
+           * list. Before we enqueue the path on the new multipath list,
+           * make sure its not on the old_best multipath list or referenced
+           * via next_mpath:
+           * - If next_mpath points to this new path, update next_mpath to
+           *   point to the multipath after this one
+           * - Dequeue the path from the multipath list just to make sure
+           */
+          new_mpath = listgetdata (mp_node);
+          list_delete_node (mp_list, mp_node);
+          if (new_mpath == next_mpath)
+            next_mpath = bgp_info_mpath_next (new_mpath);
+          bgp_info_mpath_dequeue (new_mpath);
+          if ((mpath_count < maxpaths) && (new_mpath != new_best) &&
+              bgp_info_nexthop_cmp (prev_mpath, new_mpath))
+            {
+              bgp_info_mpath_enqueue (prev_mpath, new_mpath);
+              prev_mpath = new_mpath;
+              mpath_changed = 1;
+              mpath_count++;
+              if (debug)
+                zlog_debug ("%s add mpath nexthop %s peer %s", pfx_buf,
+                            inet_ntop (AF_INET, &new_mpath->attr->nexthop,
+                                       nh_buf[0], sizeof (nh_buf[0])),
+                            sockunion2str (new_mpath->peer->su_remote,
+                                           nh_buf[1], sizeof (nh_buf[1])));
+            }
+          mp_node = mp_next_node;
+        }
+    }
+
+  if (new_best)
+    {
+      bgp_info_mpath_count_set (new_best, mpath_count-1);
+      if (mpath_changed || (bgp_info_mpath_count (new_best) != old_mpath_count))
+        SET_FLAG (new_best->flags, BGP_INFO_MULTIPATH_CHG);
+    }
+}