fib: fib api updates

Enhance the route add/del APIs to take a set of paths rather than just one.
Most unicast routing protocols calcualte all the available paths in one
run of the algorithm so updating all the paths at once is beneficial for the client.
two knobs control the behaviour:
  is_multipath - if set the the set of paths passed will be added to those
                 that already exist, otherwise the set will replace them.
  is_add - add or remove the set

is_add=0, is_multipath=1 and an empty set, results in deleting the route.

It is also considerably faster to add multiple paths at once, than one at a time:

vat# ip_add_del_route 1.1.1.1/32 count 100000 multipath via 10.10.10.11
100000 routes in .572240 secs, 174751.80 routes/sec
vat# ip_add_del_route 1.1.1.1/32 count 100000 multipath via 10.10.10.12
100000 routes in .528383 secs, 189256.54 routes/sec
vat# ip_add_del_route 1.1.1.1/32 count 100000 multipath via 10.10.10.13
100000 routes in .757131 secs, 132077.52 routes/sec
vat# ip_add_del_route 1.1.1.1/32 count 100000 multipath via 10.10.10.14
100000 routes in .878317 secs, 113854.12 routes/sec

vat# ip_route_add_del 1.1.1.1/32 count 100000 multipath via 10.10.10.11 via 10.10.10.12 via 10.10.10.13 via 10.10.10.14
100000 routes in .900212 secs, 111084.93 routes/sec

Change-Id: I416b93f7684745099c1adb0b33edac58c9339c1a
Signed-off-by: Neale Ranns <neale.ranns@cisco.com>
Signed-off-by: Ole Troan <ot@cisco.com>
Signed-off-by: Paul Vinciguerra <pvinci@vinciconsulting.com>

1 files changed, 144 insertions, 92 deletions

diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c
index 47170adf864..7c57c807327 100644
--- a/src/vnet/fib/fib_path_list.c
+++ b/src/vnet/fib/fib_path_list.c
@@ -830,12 +830,14 @@ fib_path_list_find_rpath (fib_node_index_t path_list_index,
  * The path-list returned could either have been newly created, or
  * can be a shared path-list from the data-base.
  */
-fib_node_index_t
-fib_path_list_path_add (fib_node_index_t path_list_index,
-                        const fib_route_path_t *rpaths)
+fib_node_index_t*
+fib_path_list_paths_add (fib_node_index_t path_list_index,
+                         const fib_route_path_t *rpaths)
 {
-    fib_node_index_t new_path_index, *orig_path_index;
+    fib_node_index_t *new_path_indices, *path_index;
+    const fib_route_path_t *rpath;
     fib_path_list_t *path_list;
+    u32 ii;
 
     /*
      * alloc the new list before we retrieve the old one, lest
@@ -843,40 +845,65 @@ fib_path_list_path_add (fib_node_index_t path_list_index,
      */
     path_list = fib_path_list_get(path_list_index);
 
-    ASSERT(1 == vec_len(rpaths));
     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
 
-    FIB_PATH_LIST_DBG(path_list, "path-add");
+    FIB_PATH_LIST_DBG(path_list, "paths-add");
 
-    new_path_index = fib_path_create(path_list_index,
-                                     rpaths);
+    new_path_indices = NULL;
+    vec_validate_init_empty(new_path_indices,
+                            vec_len(rpaths) - 1,
+                            FIB_NODE_INDEX_INVALID);
 
-    vec_foreach (orig_path_index, path_list->fpl_paths)
+    vec_foreach (path_index, path_list->fpl_paths)
     {
         /*
          * don't add duplicate paths
          */
-	if (0 == fib_path_cmp(new_path_index, *orig_path_index))
+        int found = 0;
+
+        vec_foreach_index(ii, rpaths)
         {
-            fib_path_destroy(new_path_index);
-            return (*orig_path_index);
+            rpath = &rpaths[ii];
+            if (0 == fib_path_cmp_w_route_path(*path_index, rpath))
+            {
+                found = 1;
+                break;
+            }
+        }
+        if (found)
+        {
+            new_path_indices[ii] = *path_index;
         }
     }
 
     /*
-     * Add the new path - no sort, no sharing, no key..
+     * new_path_indices array contains INVALID for each path not found
+     * and something valid for matches
      */
-    vec_add1(path_list->fpl_paths, new_path_index);
+    vec_foreach_index (ii, new_path_indices)
+    {
+        path_index = &new_path_indices[ii];
+        rpath = &rpaths[ii];
 
-    FIB_PATH_LIST_DBG(path_list, "path-added");
+        if (FIB_NODE_INDEX_INVALID == *path_index)
+        {
+            *path_index = fib_path_create(path_list_index, rpath);
+            /*
+             * Add the new path - no sort, no sharing, no key..
+             */
+            vec_add1(path_list->fpl_paths, *path_index);
 
-    /*
-     * no shared path list requested. resolve and use the one
-     * just created.
-     */
-    fib_path_resolve(new_path_index);
+            /*
+             * no shared path list requested. resolve and use the one
+             * just created.
+             */
+            fib_path_resolve(*path_index);
+        }
+    }
+
+    FIB_PATH_LIST_DBG(path_list, "paths-added");
 
-    return (new_path_index);
+    return (new_path_indices);
 }
 
 fib_node_index_t
@@ -884,14 +911,13 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
                                  fib_path_list_flags_t flags,
                                  const fib_route_path_t *rpaths)
 {
-    fib_node_index_t path_index, new_path_index, *orig_path_index;
+    fib_node_index_t new_path_index, *orig_path_index;
     fib_path_list_t *path_list, *orig_path_list;
     fib_node_index_t exist_path_list_index;
     fib_node_index_t path_list_index;
+    const fib_route_path_t *rpath;
     fib_node_index_t pi;
 
-    ASSERT(1 == vec_len(rpaths));
-
     /*
      * alloc the new list before we retrieve the old one, lest
      * the alloc result in a realloc
@@ -905,32 +931,50 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
     flags = fib_path_list_flags_fixup(flags);
     path_list->fpl_flags = flags;
 
-    vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
+    vec_validate(path_list->fpl_paths,
+                 (vec_len(orig_path_list->fpl_paths) +
+                  vec_len(rpaths) - 1));
     pi = 0;
 
-    new_path_index = fib_path_create(path_list_index,
-                                     rpaths);
-
-    vec_foreach (orig_path_index, orig_path_list->fpl_paths)
+    vec_foreach(orig_path_index, orig_path_list->fpl_paths)
     {
         /*
-         * don't add duplicate paths
-         * In the unlikely event the path is a duplicate, then we'll
-         * find a matching path-list later and this one will be toast.
+         * copy the original paths over to the new list
          */
-	if (0 != fib_path_cmp(new_path_index, *orig_path_index))
+        path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
+                                                   path_list_index);
+    }
+    vec_foreach(rpath, rpaths)
+    {
+        int duplicate = 0;
+
+        new_path_index = fib_path_create(path_list_index, rpath);
+
+        vec_foreach(orig_path_index, orig_path_list->fpl_paths)
         {
-            path_index = fib_path_copy(*orig_path_index, path_list_index);
-            path_list->fpl_paths[pi++] = path_index;
+            /*
+             * don't add duplicate paths
+             * In the unlikely event the path is a duplicate, then we'll
+             * find a matching path-list later and this one will be toast.
+             */
+            if (0 == fib_path_cmp(new_path_index, *orig_path_index))
+            {
+                duplicate = 1;
+                break;
+            }
+        }
+        if (duplicate)
+        {
+            _vec_len(path_list->fpl_paths) =
+                vec_len(path_list->fpl_paths) - 1;
+            fib_path_destroy(new_path_index);
         }
         else
         {
-            _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
+            path_list->fpl_paths[pi++] = new_path_index;
         }
     }
 
-    path_list->fpl_paths[pi] = new_path_index;
-
     /*
      * we sort the paths since the key for the path-list is
      * the description of the paths it contains. The paths need to
@@ -978,51 +1022,60 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
 }
 
 /*
- * fib_path_list_path_remove
+ * fib_path_list_paths_remove
  */
-fib_node_index_t
-fib_path_list_path_remove (fib_node_index_t path_list_index,
+fib_node_index_t*
+fib_path_list_paths_remove (fib_node_index_t path_list_index,
                            const fib_route_path_t *rpaths)
 {
-    fib_node_index_t match_path_index, tmp_path_index;
+    fib_node_index_t *match_path_indices;
     fib_path_list_t *path_list;
-    fib_node_index_t pi;
+    i32 ii, jj;
 
     path_list = fib_path_list_get(path_list_index);
+    match_path_indices = NULL;
+    vec_validate_init_empty(match_path_indices,
+                            vec_len(rpaths) - 1,
+                            FIB_NODE_INDEX_INVALID);
 
-    ASSERT(1 == vec_len(rpaths));
     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
 
     FIB_PATH_LIST_DBG(path_list, "path-remove");
 
     /*
-     * create a representation of the path to be removed, so it
-     * can be used as a comparison object during the copy.
+     * the number of existing paths is likely to be larger than the
+     * number of paths being added.
+     * walk in reverse so the vec_del is ok
      */
-    tmp_path_index = fib_path_create(path_list_index,
-				     rpaths);
-    match_path_index = FIB_NODE_INDEX_INVALID;
-
-    vec_foreach_index (pi, path_list->fpl_paths)
+    vec_foreach_index_backwards(ii, path_list->fpl_paths)
     {
-	if (0 == fib_path_cmp(tmp_path_index,
-                              path_list->fpl_paths[pi]))
+        int found = ~0;
+
+        vec_foreach_index(jj, rpaths)
         {
+            if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
+                                               &rpaths[jj]))
+            {
+                found = jj;
+                break;
+            }
+        }
+        if (~0 != found)
+        {
+            fib_node_index_t match_path_index;
             /*
              * match - remove it
              */
-            match_path_index = path_list->fpl_paths[pi];
+            match_path_index = path_list->fpl_paths[ii];
+            vec_del1(path_list->fpl_paths, ii);
             fib_path_destroy(match_path_index);
-            vec_del1(path_list->fpl_paths, pi);
-	}
+            match_path_indices[jj] = match_path_index;
+        }
     }
 
-    /*
-     * done with the temporary now
-     */
-    fib_path_destroy(tmp_path_index);
+    FIB_PATH_LIST_DBG(path_list, "paths-removed");
 
-    return (match_path_index);
+    return (match_path_indices);
 }
 
 /*
@@ -1035,10 +1088,11 @@ fib_path_list_path_remove (fib_node_index_t path_list_index,
 fib_node_index_t
 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
 				    fib_path_list_flags_t flags,
-				    const fib_route_path_t *rpath)
+				    const fib_route_path_t *rpaths)
 {
-    fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
+    fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
     fib_path_list_t *path_list,  *orig_path_list;
+    const fib_route_path_t *rpath;
     fib_node_index_t pi;
 
     path_list = fib_path_list_alloc(&path_list_index);
@@ -1053,44 +1107,42 @@ fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
      * allocate as many paths as we might need in one go, rather than
      * using vec_add to do a few at a time.
      */
-    if (vec_len(orig_path_list->fpl_paths) > 1)
-    {
-	vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
-    }
+    vec_validate(path_list->fpl_paths,
+                 vec_len(orig_path_list->fpl_paths) - 1);
     pi = 0;
 
     /*
      * create a representation of the path to be removed, so it
      * can be used as a comparison object during the copy.
      */
-    tmp_path_index = fib_path_create(path_list_index, rpath);
-
-    vec_foreach (orig_path_index, orig_path_list->fpl_paths)
+    vec_foreach(orig_path_index, orig_path_list->fpl_paths)
     {
-	if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
-	    path_index = fib_path_copy(*orig_path_index, path_list_index);
-	    if (pi < vec_len(path_list->fpl_paths))
-	    {
-		path_list->fpl_paths[pi++] = path_index;
-	    }
-	    else
-	    {
-		/*
-		 * this is the unlikely case that the path being
-		 * removed does not match one in the path-list, so
-		 * we end up with as many paths as we started with.
-		 * the paths vector was sized above with the expectation
-		 * that we would have 1 less.
-		 */
-		vec_add1(path_list->fpl_paths, path_index);
-	    }
-	}
+        /*
+         * copy the original paths over to the new list
+         */
+        path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
+                                                   path_list_index);
     }
+    vec_foreach(rpath, rpaths)
+    {
+        int found = 0;
+        tmp_path_index = fib_path_create(path_list_index, rpath);
 
-    /*
-     * done with the temporary now
-     */
-    fib_path_destroy(tmp_path_index);
+        vec_foreach_index(pi, path_list->fpl_paths)
+        {
+            if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
+            {
+                found = 1;
+                break;
+            }
+        }
+        if (found)
+        {
+            fib_path_destroy(path_list->fpl_paths[pi]);
+            vec_del1(path_list->fpl_paths, pi);
+        }
+        fib_path_destroy(tmp_path_index);
+    }
 
     /*
      * if there are no paths, then the new path-list is aborted