BFD-FIB interactions

- single-hop BFD: attach a delegate to the appropriate adjacency
- multi-hop BFD [not supported yet]: attach a delegate to the FIB entry.

adjacency/fib_entry state tracks the BFD session state. when the state is down the object does not contribute forwarding hence and hence dependent objects will not use it.
For example, if a route is ECMP via two adjacencies and one of them is BFD down, then only the other is used to forward (i.e. we don't drop half the traffic).

Change-Id: I0ef53e20e73b067001a132cd0a3045408811a822
Signed-off-by: Neale Ranns <nranns@cisco.com>

5 files changed, 494 insertions, 4 deletions

diff --git a/src/vnet/adj/adj.c b/src/vnet/adj/adj.c
index 7cf9e9d081d..90182006f60 100644
--- a/src/vnet/adj/adj.c
+++ b/src/vnet/adj/adj.c
@@ -18,6 +18,7 @@
 #include <vnet/adj/adj_glean.h>
 #include <vnet/adj/adj_midchain.h>
 #include <vnet/adj/adj_mcast.h>
+#include <vnet/adj/adj_delegate.h>
 #include <vnet/fib/fib_node_list.h>
 
 /* Adjacency packet/byte counters indexed by adjacency index. */
@@ -57,13 +58,14 @@ adj_alloc (fib_protocol_t proto)
     vlib_validate_combined_counter(&adjacency_counters,
                                    adj_get_index(adj));
 
-    adj->rewrite_header.sw_if_index = ~0;
-    adj->lookup_next_index = 0;
-
     fib_node_init(&adj->ia_node,
                   FIB_NODE_TYPE_ADJ);
+
     adj->ia_nh_proto = proto;
     adj->ia_flags = 0;
+    adj->rewrite_header.sw_if_index = ~0;
+    adj->lookup_next_index = 0;
+    adj->ia_delegates = NULL;
 
     ip4_main.lookup_main.adjacency_heap = adj_pool;
     ip6_main.lookup_main.adjacency_heap = adj_pool;
@@ -122,11 +124,19 @@ format_ip_adjacency (u8 * s, va_list * args)
 
     if (fiaf & FORMAT_IP_ADJACENCY_DETAIL)
     {
+        adj_delegate_type_t adt;
+        adj_delegate_t *aed;
         vlib_counter_t counts;
 
         vlib_get_combined_counter(&adjacency_counters, adj_index, &counts);
         s = format (s, "\n counts:[%Ld:%Ld]", counts.packets, counts.bytes);
 	s = format (s, "\n locks:%d", adj->ia_node.fn_locks);
+	s = format(s, "\n delegates:\n  ");
+        FOR_EACH_ADJ_DELEGATE(adj, adt, aed,
+        {
+            s = format(s, "  %U\n", format_adj_deletegate, aed);
+        });
+
 	s = format(s, "\n children:\n  ");
 	s = fib_node_children_format(adj->ia_node.fn_children, s);
     }
@@ -173,7 +183,11 @@ adj_last_lock_gone (ip_adjacency_t *adj)
 	adj_mcast_remove(adj->ia_nh_proto,
 			 adj->rewrite_header.sw_if_index);
 	break;
-    default:
+    case IP_LOOKUP_NEXT_DROP:
+    case IP_LOOKUP_NEXT_PUNT:
+    case IP_LOOKUP_NEXT_LOCAL:
+    case IP_LOOKUP_NEXT_ICMP_ERROR:
+    case IP_LOOKUP_N_NEXT:
 	/*
 	 * type not stored in any DB from which we need to remove it
 	 */
@@ -183,6 +197,8 @@ adj_last_lock_gone (ip_adjacency_t *adj)
     vlib_worker_thread_barrier_release(vm);
 
     fib_node_deinit(&adj->ia_node);
+    ASSERT(0 == vec_len(adj->ia_delegates));
+    vec_free(adj->ia_delegates);
     pool_put(adj_pool, adj);
 }
 
@@ -352,6 +368,33 @@ adj_get_sw_if_index (adj_index_t ai)
 }
 
 /**
+ * @brief Return true if the adjacency is 'UP', i.e. can be used for forwarding
+ * 0 is down, !0 is up.
+ */
+int
+adj_is_up (adj_index_t ai)
+{
+    const adj_delegate_t *aed;
+
+    aed = adj_delegate_get(adj_get(ai), ADJ_DELEGATE_BFD);
+
+    if (NULL == aed)
+    {
+        /*
+         * no BFD tracking - resolved
+         */
+        return (!0);
+    }
+    else
+    {
+        /*
+         * defer to the state of the BFD tracking
+         */
+        return (ADJ_BFD_STATE_UP == aed->ad_bfd_state);
+    }
+}
+
+/**
  * @brief Return the rewrite string of the adjacency
  */
 const u8*
diff --git a/src/vnet/adj/adj.h b/src/vnet/adj/adj.h
index af7730f7086..32997c91f92 100644
--- a/src/vnet/adj/adj.h
+++ b/src/vnet/adj/adj.h
@@ -255,6 +255,15 @@ typedef struct ip_adjacency_t_
 
   /* Rewrite in second/third cache lines */
   vnet_declare_rewrite (VLIB_BUFFER_PRE_DATA_SIZE);
+
+  /**
+   * more control plane members that do not fit on the first cacheline
+   */
+  /**
+   * A sorted vector of delegates
+   */
+  struct adj_delegate_t_ *ia_delegates;
+
 } ip_adjacency_t;
 
 STATIC_ASSERT ((STRUCT_OFFSET_OF (ip_adjacency_t, cacheline0) == 0),
@@ -308,6 +317,12 @@ extern vnet_link_t adj_get_link_type (adj_index_t ai);
 extern u32 adj_get_sw_if_index (adj_index_t ai);
 
 /**
+ * @brief Return true if the adjacency is 'UP', i.e. can be used for forwarding.
+ * 0 is down, !0 is up.
+ */
+extern int adj_is_up (adj_index_t ai);
+
+/**
  * @brief Return the link type of the adjacency
  */
 extern const u8* adj_get_rewrite (adj_index_t ai);
diff --git a/src/vnet/adj/adj_bfd.c b/src/vnet/adj/adj_bfd.c
new file mode 100644
index 00000000000..3d294c4646e
--- /dev/null
+++ b/src/vnet/adj/adj_bfd.c
@@ -0,0 +1,184 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/bfd/bfd_main.h>
+
+#include <vnet/adj/adj_delegate.h>
+#include <vnet/adj/adj_nbr.h>
+#include <vnet/fib/fib_walk.h>
+
+static adj_bfd_state_t
+adj_bfd_bfd_state_to_fib (bfd_state_e bstate)
+{
+    switch (bstate)
+    {
+    case BFD_STATE_up:
+        return (ADJ_BFD_STATE_UP);
+    case BFD_STATE_down:
+    case BFD_STATE_admin_down:
+    case BFD_STATE_init:
+        return (ADJ_BFD_STATE_DOWN);
+    }
+    return (ADJ_BFD_STATE_DOWN);
+}
+
+static void
+adj_bfd_update_walk (adj_index_t ai)
+{
+    /*
+     * initiate a backwalk of dependent children
+     * to notify of the state change of this adj.
+     */
+    fib_node_back_walk_ctx_t ctx = {
+        .fnbw_reason = FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE,
+    };
+    fib_walk_sync(FIB_NODE_TYPE_ADJ, ai, &ctx);
+}
+
+/**
+ * @brief Callback function registered with BFD module to receive notifications
+ * of the CRUD of BFD sessions
+ * would be static but for the fact it's called from the unit-tests
+ */
+void
+adj_bfd_notify (bfd_listen_event_e event,
+                const bfd_session_t *session)
+{
+    const bfd_udp_key_t *key;
+    fib_protocol_t fproto;
+    adj_delegate_t *aed;
+    adj_index_t ai;
+
+    if (BFD_HOP_TYPE_SINGLE != session->hop_type)
+    {
+        /*
+         * multi-hop BFD sessions attach directly to the FIB entry
+         * single-hop adj to the associate adjacency.
+         */
+        return;
+    }
+
+    key = &session->udp.key;
+
+    fproto = (ip46_address_is_ip4 (&key->peer_addr) ?
+              FIB_PROTOCOL_IP4:
+              FIB_PROTOCOL_IP6);
+
+    /*
+     * find the adj that corresponds to the BFD session.
+     */
+    ai = adj_nbr_add_or_lock(fproto,
+                             fib_proto_to_link(fproto),
+                             &key->peer_addr,
+                             key->sw_if_index);
+
+    switch (event)
+    {
+    case BFD_LISTEN_EVENT_CREATE:
+        /*
+         * The creation of a new session
+         */
+        if ((ADJ_INDEX_INVALID != ai) &&
+            (aed = adj_delegate_get(adj_get(ai),
+                                    ADJ_DELEGATE_BFD)))
+        {
+            /*
+             * already got state for this adj
+             */
+        }
+        else
+        {
+            /*
+             * lock the adj. add the delegate.
+             * Lockinging the adj prevents it being removed and thus maintains
+             * the BFD derived states
+             */
+            adj_lock(ai);
+
+            aed = adj_delegate_find_or_add(adj_get(ai), ADJ_DELEGATE_BFD);
+
+            /*
+             * pretend the session is up and skip the walk.
+             * If we set it down then we get traffic loss on new children.
+             * if we walk then we lose traffic for existing children. Wait
+             * for the first BFD UP/DOWN before we let the session's state
+             * influence forwarding.
+             */
+            aed->ad_bfd_state = ADJ_BFD_STATE_UP;
+            aed->ad_bfd_index = session->bs_idx;
+        }
+        break;
+
+    case BFD_LISTEN_EVENT_UPDATE:
+        /*
+         * state change up/dowm and
+         */
+        aed = adj_delegate_get(adj_get(ai), ADJ_DELEGATE_BFD);
+
+        if (NULL != aed)
+        {
+            aed->ad_bfd_state = adj_bfd_bfd_state_to_fib(session->local_state);
+            adj_bfd_update_walk(ai);
+        }
+        /*
+         * else
+         *   not an adj with BFD state
+         */
+        break;
+
+    case BFD_LISTEN_EVENT_DELETE:
+        /*
+         * session has been removed.
+         */
+
+        if (adj_delegate_get(adj_get(ai), ADJ_DELEGATE_BFD))
+        {
+            /*
+             * has an associated BFD tracking delegate
+             * remove the BFD tracking deletgate, update children, then
+             * unlock the adj
+             */
+            adj_delegate_remove(adj_get(ai), ADJ_DELEGATE_BFD);
+
+            adj_bfd_update_walk(ai);
+            adj_unlock(ai);
+        }
+        /*
+         * else
+         *  no BFD associated state
+         */
+        break;
+    }
+
+    /*
+     * unlock match of the add-or-lock at the start
+     */
+    adj_unlock(ai);
+}
+
+static clib_error_t *
+adj_bfd_main_init (vlib_main_t * vm)
+{
+    clib_error_t * error = NULL;
+
+    if ((error = vlib_call_init_function (vm, bfd_main_init)))
+        return (error);
+
+    bfd_register_listener(adj_bfd_notify);
+
+    return (error);
+}
+
+VLIB_INIT_FUNCTION (adj_bfd_main_init);
diff --git a/src/vnet/adj/adj_delegate.c b/src/vnet/adj/adj_delegate.c
new file mode 100644
index 00000000000..701b36e2fd9
--- /dev/null
+++ b/src/vnet/adj/adj_delegate.c
@@ -0,0 +1,144 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/adj/adj_delegate.h>
+#include <vnet/adj/adj.h>
+#include <vnet/adj/adj_internal.h>
+
+static adj_delegate_t *
+adj_delegate_find_i (const ip_adjacency_t *adj,
+                     adj_delegate_type_t type,
+                     u32 *index)
+{
+    adj_delegate_t *delegate;
+    int ii;
+
+    ii = 0;
+    vec_foreach(delegate, adj->ia_delegates)
+    {
+	if (delegate->ad_type == type)
+	{
+            if (NULL != index)
+                *index = ii;
+
+	    return (delegate);
+	}
+	else
+	{
+	    ii++;
+	}
+    }
+
+    return (NULL);
+}
+
+adj_delegate_t *
+adj_delegate_get (const ip_adjacency_t *adj,
+                  adj_delegate_type_t type)
+{
+    return (adj_delegate_find_i(adj, type, NULL));
+}
+
+void
+adj_delegate_remove (ip_adjacency_t *adj,
+                     adj_delegate_type_t type)
+{
+    adj_delegate_t *aed;
+    u32 index = ~0;
+
+    aed = adj_delegate_find_i(adj, type, &index);
+
+    ASSERT(NULL != aed);
+
+    vec_del1(adj->ia_delegates, index);
+}
+
+static int
+adj_delegate_cmp_for_sort (void * v1,
+                           void * v2)
+{
+    adj_delegate_t *delegate1 = v1, *delegate2 = v2;
+
+    return (delegate1->ad_type - delegate2->ad_type);
+}
+
+static void
+adj_delegate_init (ip_adjacency_t *adj,
+                   adj_delegate_type_t type)
+
+{
+    adj_delegate_t delegate = {
+	.ad_adj_index = adj_get_index(adj),
+	.ad_type = type,
+    };
+
+    vec_add1(adj->ia_delegates, delegate);
+    vec_sort_with_function(adj->ia_delegates,
+			   adj_delegate_cmp_for_sort);
+}
+
+adj_delegate_t *
+adj_delegate_find_or_add (ip_adjacency_t *adj,
+                          adj_delegate_type_t adt)
+{
+    adj_delegate_t *delegate;
+
+    delegate = adj_delegate_get(adj, adt);
+
+    if (NULL == delegate)
+    {
+	adj_delegate_init(adj, adt);
+    }
+
+    return (adj_delegate_get(adj, adt));
+}
+
+/**
+ * typedef for printing a delegate
+ */
+typedef u8 * (*adj_delegate_format_t)(const adj_delegate_t *aed,
+                                      u8 *s);
+
+/**
+ * Print a delegate that represents BFD tracking
+ */
+static u8 *
+adj_delegate_fmt_bfd (const adj_delegate_t *aed,
+                      u8 *s)
+{
+    s = format(s, "BFD:[state:%d index:%d]",
+               aed->ad_bfd_state,
+               aed->ad_bfd_index);
+
+    return (s);
+}
+
+/**
+ * A delegate type to formatter map
+ */
+static adj_delegate_format_t aed_formatters[] =
+{
+    [ADJ_DELEGATE_BFD] = adj_delegate_fmt_bfd,
+};
+
+u8 *
+format_adj_deletegate (u8 * s, va_list * args)
+{
+    adj_delegate_t *aed;
+
+    aed = va_arg (*args, adj_delegate_t *);
+
+    return (aed_formatters[aed->ad_type](aed, s));
+}
diff --git a/src/vnet/adj/adj_delegate.h b/src/vnet/adj/adj_delegate.h
new file mode 100644
index 00000000000..176512039d6
--- /dev/null
+++ b/src/vnet/adj/adj_delegate.h
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __ADJ_DELEGATE_T__
+#define __ADJ_DELEGATE_T__
+
+#include <vnet/adj/adj.h>
+
+/**
+ * Delegate types
+ */
+typedef enum adj_delegate_type_t_ {
+    /**
+     * BFD session state
+     */
+    ADJ_DELEGATE_BFD,
+} adj_delegate_type_t;
+
+#define FOR_EACH_ADJ_DELEGATE(_adj, _adt, _aed, _body)        \
+{                                                             \
+    for (_adt = ADJ_DELEGATE_BFD;                             \
+         _adt <= ADJ_DELEGATE_BFD;                            \
+         _adt++)                                              \
+    {                                                         \
+        _aed = adj_delegate_get(_adj, _adt);                  \
+        if (NULL != _aed) {                                   \
+            _body;                                            \
+        }                                                     \
+    }                                                         \
+}
+
+/**
+ * Distillation of the BFD session states into a go/no-go for using
+ * the associated tracked adjacency
+ */
+typedef enum adj_bfd_state_t_
+{
+    ADJ_BFD_STATE_DOWN,
+    ADJ_BFD_STATE_UP,
+} adj_bfd_state_t;
+
+/**
+ * A Delagate is a means to implement the Delagation design pattern;
+ * the extension of an object's functionality through the composition of,
+ * and delgation to, other objects.
+ * These 'other' objects are delegates. Delagates are thus attached to
+ * ADJ objects to extend their functionality.
+ */
+typedef struct adj_delegate_t_
+{
+    /**
+     * The ADJ entry object to which the delagate is attached
+     */
+    adj_index_t ad_adj_index;
+
+    /**
+     * The delagate type
+     */
+    adj_delegate_type_t ad_type;
+
+    /**
+     * A union of data for the different delegate types
+     */
+    union
+    {
+        /**
+         * BFD delegate daa
+         */
+        struct {
+            /**
+             * BFD session state
+             */
+            adj_bfd_state_t ad_bfd_state;
+            /**
+             * BFD session index
+             */
+            u32 ad_bfd_index;
+        };
+    };
+} adj_delegate_t;
+
+extern void adj_delegate_remove(ip_adjacency_t *adj,
+                                adj_delegate_type_t type);
+
+extern adj_delegate_t *adj_delegate_find_or_add(ip_adjacency_t *adj,
+                                                adj_delegate_type_t fdt);
+extern adj_delegate_t *adj_delegate_get(const ip_adjacency_t *adj,
+                                        adj_delegate_type_t type);
+
+extern u8 *format_adj_deletegate(u8 * s, va_list * args);
+
+#endif