IP Multicast FIB (mfib)

 - IPv[46] mfib tables with support for (*,G/m), (*,G) and (S,G) exact and longest prefix match
 - Replication represented via a new replicate DPO.
 - RPF configuration and data-plane checking
 - data-plane signals sent to listening control planes.

The functions of multicast forwarding entries differ from their unicast conterparts, so we introduce a new mfib_table_t and mfib_entry_t objects. However, we re-use the fib_path_list to resolve and build the entry's output list. the fib_path_list provides the service to construct a replicate DPO for multicast.

'make tests' is added to with two new suites; TEST=mfib, this is invocation of the CLI command 'test mfib' which deals with many path add/remove, flag set/unset scenarios, TEST=ip-mcast, data-plane forwarding tests.

Updated applications to use the new MIFB functions;
  - IPv6 NS/RA.
  - DHCPv6
 unit tests for these are undated accordingly.

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

1 files changed, 489 insertions, 0 deletions

diff --git a/src/vnet/mfib/mfib_table.c b/src/vnet/mfib/mfib_table.c
new file mode 100644
index 00000000000..e4c0936d6c9
--- /dev/null
+++ b/src/vnet/mfib/mfib_table.c
@@ -0,0 +1,489 @@
+/*
+ * 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 <vlib/vlib.h>
+#include <vnet/dpo/drop_dpo.h>
+
+#include <vnet/mfib/mfib_table.h>
+#include <vnet/mfib/ip4_mfib.h>
+#include <vnet/mfib/ip6_mfib.h>
+#include <vnet/mfib/mfib_entry.h>
+#include <vnet/mfib/mfib_signal.h>
+
+mfib_table_t *
+mfib_table_get (fib_node_index_t index,
+                fib_protocol_t proto)
+{
+    switch (proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        return (pool_elt_at_index(ip4_main.mfibs, index));
+    case FIB_PROTOCOL_IP6:
+        return (pool_elt_at_index(ip6_main.mfibs, index));
+    case FIB_PROTOCOL_MPLS:
+        break;
+    }
+    ASSERT(0);
+    return (NULL);
+}
+
+static inline fib_node_index_t
+mfib_table_lookup_i (const mfib_table_t *mfib_table,
+                     const mfib_prefix_t *prefix)
+{
+    switch (prefix->fp_proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        return (ip4_mfib_table_lookup(&mfib_table->v4,
+                                      &prefix->fp_src_addr.ip4,
+                                      &prefix->fp_grp_addr.ip4,
+                                      prefix->fp_len));
+    case FIB_PROTOCOL_IP6:
+        return (ip6_mfib_table_lookup(&mfib_table->v6,
+                                      &prefix->fp_src_addr.ip6,
+                                      &prefix->fp_grp_addr.ip6,
+                                      prefix->fp_len));
+    case FIB_PROTOCOL_MPLS:
+        break;
+    }
+    return (FIB_NODE_INDEX_INVALID);
+}
+
+fib_node_index_t
+mfib_table_lookup (u32 fib_index,
+                   const mfib_prefix_t *prefix)
+{
+    return (mfib_table_lookup_i(mfib_table_get(fib_index, prefix->fp_proto), prefix));
+}
+
+static inline fib_node_index_t
+mfib_table_lookup_exact_match_i (const mfib_table_t *mfib_table,
+                                 const mfib_prefix_t *prefix)
+{
+    switch (prefix->fp_proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        return (ip4_mfib_table_lookup_exact_match(&mfib_table->v4,
+                                                  &prefix->fp_grp_addr.ip4,
+                                                  &prefix->fp_src_addr.ip4,
+                                                  prefix->fp_len));
+    case FIB_PROTOCOL_IP6:
+        return (ip6_mfib_table_lookup_exact_match(&mfib_table->v6,
+                                                  &prefix->fp_grp_addr.ip6,
+                                                  &prefix->fp_src_addr.ip6,
+                                                  prefix->fp_len));
+    case FIB_PROTOCOL_MPLS:
+        break;
+    }
+    return (FIB_NODE_INDEX_INVALID);
+}
+
+fib_node_index_t
+mfib_table_lookup_exact_match (u32 fib_index,
+                              const mfib_prefix_t *prefix)
+{
+    return (mfib_table_lookup_exact_match_i(mfib_table_get(fib_index,
+                                                          prefix->fp_proto),
+                                            prefix));
+}
+
+static void
+mfib_table_entry_remove (mfib_table_t *mfib_table,
+                         const mfib_prefix_t *prefix,
+                         fib_node_index_t fib_entry_index)
+{
+    vlib_smp_unsafe_warning();
+
+    mfib_table->mft_total_route_counts--;
+
+    switch (prefix->fp_proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        ip4_mfib_table_entry_remove(&mfib_table->v4,
+                                    &prefix->fp_grp_addr.ip4,
+                                    &prefix->fp_src_addr.ip4,
+                                    prefix->fp_len);
+        break;
+    case FIB_PROTOCOL_IP6:
+        ip6_mfib_table_entry_remove(&mfib_table->v6,
+                                    &prefix->fp_grp_addr.ip6,
+                                    &prefix->fp_src_addr.ip6,
+                                    prefix->fp_len);
+        break;
+    case FIB_PROTOCOL_MPLS:
+        ASSERT(0);
+        break;
+    }
+
+    mfib_entry_unlock(fib_entry_index);
+}
+
+static void
+mfib_table_entry_insert (mfib_table_t *mfib_table,
+                         const mfib_prefix_t *prefix,
+                         fib_node_index_t mfib_entry_index)
+{
+    vlib_smp_unsafe_warning();
+
+    mfib_entry_lock(mfib_entry_index);
+    mfib_table->mft_total_route_counts++;
+
+    switch (prefix->fp_proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        ip4_mfib_table_entry_insert(&mfib_table->v4,
+                                    &prefix->fp_grp_addr.ip4,
+                                    &prefix->fp_src_addr.ip4,
+                                    prefix->fp_len,
+                                    mfib_entry_index);
+        break;
+    case FIB_PROTOCOL_IP6:
+        ip6_mfib_table_entry_insert(&mfib_table->v6,
+                                    &prefix->fp_grp_addr.ip6,
+                                    &prefix->fp_src_addr.ip6,
+                                    prefix->fp_len,
+                                    mfib_entry_index);
+        break;
+    case FIB_PROTOCOL_MPLS:
+        break;
+    }
+}
+
+fib_node_index_t
+mfib_table_entry_update (u32 fib_index,
+                         const mfib_prefix_t *prefix,
+                         mfib_source_t source,
+                         mfib_entry_flags_t entry_flags)
+{
+    fib_node_index_t mfib_entry_index;
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, prefix->fp_proto);
+    mfib_entry_index = mfib_table_lookup_exact_match_i(mfib_table, prefix);
+
+    if (FIB_NODE_INDEX_INVALID == mfib_entry_index)
+    {
+        if (MFIB_ENTRY_FLAG_NONE != entry_flags)
+        {
+            /*
+             * update to a non-existing entry with non-zero flags
+             */
+            mfib_entry_index = mfib_entry_create(fib_index, source,
+                                                 prefix, entry_flags);
+
+            mfib_table_entry_insert(mfib_table, prefix, mfib_entry_index);
+        }
+        /*
+         * else
+         *   the entry doesn't exist and the request is to set no flags
+         *   the result would be an entry that doesn't exist - so do nothing
+         */
+    }
+    else
+    {
+        mfib_entry_lock(mfib_entry_index);
+
+        if (mfib_entry_update(mfib_entry_index, source, entry_flags))
+        {
+            /*
+             * this update means we can now remove the entry.
+             */
+            mfib_table_entry_remove(mfib_table, prefix, mfib_entry_index);
+        }
+
+        mfib_entry_unlock(mfib_entry_index);
+    }
+
+    return (mfib_entry_index);
+}
+
+fib_node_index_t
+mfib_table_entry_path_update (u32 fib_index,
+                              const mfib_prefix_t *prefix,
+                              mfib_source_t source,
+                              const fib_route_path_t *rpath,
+                              mfib_itf_flags_t itf_flags)
+{
+    fib_node_index_t mfib_entry_index;
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, prefix->fp_proto);
+    mfib_entry_index = mfib_table_lookup_exact_match_i(mfib_table, prefix);
+
+    if (FIB_NODE_INDEX_INVALID == mfib_entry_index)
+    {
+        mfib_entry_index = mfib_entry_create(fib_index,
+                                             source,
+                                             prefix,
+                                             MFIB_ENTRY_FLAG_NONE);
+
+        mfib_table_entry_insert(mfib_table, prefix, mfib_entry_index);
+    }
+
+    mfib_entry_path_update(mfib_entry_index,
+                           source,
+                           rpath,
+                           itf_flags);
+
+    return (mfib_entry_index);
+}
+
+void
+mfib_table_entry_path_remove (u32 fib_index,
+                              const mfib_prefix_t *prefix,
+                              mfib_source_t source,
+                              const fib_route_path_t *rpath)
+{
+    fib_node_index_t mfib_entry_index;
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, prefix->fp_proto);
+    mfib_entry_index = mfib_table_lookup_exact_match_i(mfib_table, prefix);
+
+    if (FIB_NODE_INDEX_INVALID == mfib_entry_index)
+    {
+        /*
+         * removing an etry that does not exist. i'll allow it.
+         */
+    }
+    else
+    {
+        int no_more_sources;
+
+        /*
+         * don't nobody go nowhere
+         */
+        mfib_entry_lock(mfib_entry_index);
+
+        no_more_sources = mfib_entry_path_remove(mfib_entry_index,
+                                                 source,
+                                                 rpath);
+
+        if (no_more_sources)
+        {
+            /*
+             * last source gone. remove from the table
+             */
+            mfib_table_entry_remove(mfib_table, prefix, mfib_entry_index);
+        }
+
+        mfib_entry_unlock(mfib_entry_index);
+    }
+}
+
+static void
+mfib_table_entry_delete_i (u32 fib_index,
+                           fib_node_index_t mfib_entry_index,
+                           const mfib_prefix_t *prefix,
+                           mfib_source_t source)
+{
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, prefix->fp_proto);
+
+    /*
+     * don't nobody go nowhere
+     */
+    mfib_entry_lock(mfib_entry_index);
+
+    if (mfib_entry_delete(mfib_entry_index, source))
+    {
+        /*
+         * last source gone. remove from the table
+         */
+        mfib_table_entry_remove(mfib_table, prefix, mfib_entry_index);
+    }
+    /*
+     * else
+     *   still has sources, leave it be.
+     */
+
+    mfib_entry_unlock(mfib_entry_index);
+}
+
+void
+mfib_table_entry_delete (u32 fib_index,
+                         const mfib_prefix_t *prefix,
+                         mfib_source_t source)
+{
+    fib_node_index_t mfib_entry_index;
+
+    mfib_entry_index = mfib_table_lookup_exact_match(fib_index, prefix);
+
+    if (FIB_NODE_INDEX_INVALID == mfib_entry_index)
+    {
+        /*
+         * removing an etry that does not exist.
+         * i'll allow it, but i won't like it.
+         */
+        clib_warning("%U not in FIB", format_mfib_prefix, prefix);
+    }
+    else
+    {
+        mfib_table_entry_delete_i(fib_index, mfib_entry_index,
+                                  prefix, source);
+    }
+}
+
+void
+mfib_table_entry_delete_index (fib_node_index_t mfib_entry_index,
+                               mfib_source_t source)
+{
+    mfib_prefix_t prefix;
+
+    mfib_entry_get_prefix(mfib_entry_index, &prefix);
+
+    mfib_table_entry_delete_i(mfib_entry_get_fib_index(mfib_entry_index),
+                              mfib_entry_index, &prefix, source);
+}
+
+u32
+mfib_table_get_index_for_sw_if_index (fib_protocol_t proto,
+                                      u32 sw_if_index)
+{
+    switch (proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        return (ip4_mfib_table_get_index_for_sw_if_index(sw_if_index));
+    case FIB_PROTOCOL_IP6:
+        return (ip6_mfib_table_get_index_for_sw_if_index(sw_if_index));
+    case FIB_PROTOCOL_MPLS:
+        ASSERT(0);
+        break;
+    }
+    return (~0);
+}
+
+u32
+mfib_table_find (fib_protocol_t proto,
+                 u32 table_id)
+{
+    switch (proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        return (ip4_mfib_index_from_table_id(table_id));
+    case FIB_PROTOCOL_IP6:
+        return (ip6_mfib_index_from_table_id(table_id));
+    case FIB_PROTOCOL_MPLS:
+        ASSERT(0);
+        break;
+    }
+    return (~0);
+}
+
+u32
+mfib_table_find_or_create_and_lock (fib_protocol_t proto,
+                                    u32 table_id)
+{
+    mfib_table_t *mfib_table;
+    fib_node_index_t fi;
+
+    switch (proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        fi = ip4_mfib_table_find_or_create_and_lock(table_id);
+        break;
+    case FIB_PROTOCOL_IP6:
+        fi = ip6_mfib_table_find_or_create_and_lock(table_id);
+        break;
+    case FIB_PROTOCOL_MPLS:
+    default:
+        return (~0);
+    }
+
+    mfib_table = mfib_table_get(fi, proto);
+
+    mfib_table->mft_desc = format(NULL, "%U-VRF:%d",
+                                  format_fib_protocol, proto,
+                                  table_id);
+
+    return (fi);
+}
+
+static void
+mfib_table_destroy (mfib_table_t *mfib_table)
+{
+    vec_free(mfib_table->mft_desc);
+
+    switch (mfib_table->mft_proto)
+    {
+    case FIB_PROTOCOL_IP4:
+        ip4_mfib_table_destroy(&mfib_table->v4);
+        break;
+    case FIB_PROTOCOL_IP6:
+        ip6_mfib_table_destroy(&mfib_table->v6);
+        break;
+    case FIB_PROTOCOL_MPLS:
+        ASSERT(0);
+        break;
+    }
+}
+
+void
+mfib_table_unlock (u32 fib_index,
+                   fib_protocol_t proto)
+{
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, proto);
+    mfib_table->mft_locks--;
+
+    if (0 == mfib_table->mft_locks)
+    {
+        mfib_table_destroy(mfib_table);
+    }
+}
+
+void
+mfib_table_lock (u32 fib_index,
+                 fib_protocol_t proto)
+{
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, proto);
+    mfib_table->mft_locks++;
+}
+
+u8*
+format_mfib_table_name (u8* s, va_list ap)
+{
+    fib_node_index_t fib_index = va_arg(ap, fib_node_index_t);
+    fib_protocol_t proto = va_arg(ap, int); // int promotion
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, proto);
+
+    s = format(s, "%v", mfib_table->mft_desc);
+
+    return (s);
+}
+
+static clib_error_t *
+mfib_module_init (vlib_main_t * vm)
+{
+    clib_error_t * error;
+
+    if ((error = vlib_call_init_function (vm, fib_module_init)))
+        return (error);
+    if ((error = vlib_call_init_function (vm, rn_module_init)))
+        return (error);
+
+    mfib_entry_module_init();
+    mfib_signal_module_init();
+
+    return (error);
+}
+
+VLIB_INIT_FUNCTION(mfib_module_init);