Dynamically compute ip feature subgraph order

This change-set enables plugins to add themselves to the ip4/ip6
feature subgraphs without having to modify core vpp engine code
at all. Add VNET_IP4/IP6_UNICAST/MULTICAST_FEATURE_INIT macros
which express the required ordering constraints, and off you go.

Along the way, added an implementation of Warshall's algorithm to
vppinfra; to compute the positive transitive closure of a relation. In
this case, the relation is "feature A runs before feature B."

With that in hand, ip_feature_init_cast(...) computes a partial order
across the set of configured feature subgraph nodes.

In unit-testing, we discovered VPP-145 - ip4/6 inacl wiped out
vnet_buffer(b)->ip>current_config_index, which exists in main. So, we
fixed that by moving b->trace_index, adding b->current_config_index,
and removing the ip opaque union current_config_index.

Change-Id: Iff132116f66413dc6b31ac3377198c7a32d51f48
Signed-off-by: Dave Barach <dave@barachs.net>

1 files changed, 26 insertions, 8 deletions

diff --git a/vpp/api/api.c b/vpp/api/api.c
index f99d9ce2..bb9a2963 100644
--- a/vpp/api/api.c
+++ b/vpp/api/api.c
@@ -1345,6 +1345,8 @@ static void
 vl_api_sw_interface_set_vpath_t_handler (vl_api_sw_interface_set_vpath_t *mp)
 {
     vlib_main_t *vm = vlib_get_main();
+    ip4_main_t * im4 = &ip4_main;
+    ip6_main_t * im6 = &ip6_main;
     vl_api_sw_interface_set_vpath_reply_t * rmp;
     int rv = 0;
     u32 ci;
@@ -1364,36 +1366,52 @@ vl_api_sw_interface_set_vpath_t_handler (vl_api_sw_interface_set_vpath_t *mp)
     if (mp->enable) {
         ci = rx_cm4u->config_index_by_sw_if_index[sw_if_index]; //IP4 unicast
         ci = vnet_config_add_feature(vm, &rx_cm4u->config_main,
-                                     ci, IP4_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im4->ip4_unicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm4u->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm4m->config_index_by_sw_if_index[sw_if_index]; //IP4 mcast
         ci = vnet_config_add_feature(vm, &rx_cm4m->config_main,
-                                     ci, IP4_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im4->ip4_multicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm4m->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm6u->config_index_by_sw_if_index[sw_if_index]; //IP6 unicast
         ci = vnet_config_add_feature(vm, &rx_cm6u->config_main,
-                                     ci, IP6_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im6->ip6_unicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm6u->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm6m->config_index_by_sw_if_index[sw_if_index]; //IP6 mcast
         ci = vnet_config_add_feature(vm, &rx_cm6m->config_main,
-                                     ci, IP6_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im6->ip6_multicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm6m->config_index_by_sw_if_index[sw_if_index] = ci;
     } else {
         ci = rx_cm4u->config_index_by_sw_if_index[sw_if_index]; //IP4 unicast
         ci = vnet_config_del_feature(vm, &rx_cm4u->config_main,
-                                     ci, IP4_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im4->ip4_unicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm4u->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm4m->config_index_by_sw_if_index[sw_if_index]; //IP4 mcast
         ci = vnet_config_del_feature(vm, &rx_cm4m->config_main,
-                                     ci, IP4_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im4->ip4_multicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm4m->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm6u->config_index_by_sw_if_index[sw_if_index]; //IP6 unicast
         ci = vnet_config_del_feature(vm, &rx_cm6u->config_main,
-                                     ci, IP6_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im6->ip6_unicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm6u->config_index_by_sw_if_index[sw_if_index] = ci;
         ci = rx_cm6m->config_index_by_sw_if_index[sw_if_index]; //IP6 mcast
         ci = vnet_config_del_feature(vm, &rx_cm6m->config_main,
-                                     ci, IP6_RX_FEATURE_VPATH, 0, 0);
+                                     ci, 
+                                     im6->ip6_multicast_rx_feature_vpath,
+                                     0, 0);
         rx_cm6m->config_index_by_sw_if_index[sw_if_index] = ci;
     }