1 files changed, 290 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/processor/metis_FIB.c b/metis/ccnx/forwarder/metis/processor/metis_FIB.c
new file mode 100644
index 00000000..3c76a072
--- /dev/null
+++ b/metis/ccnx/forwarder/metis/processor/metis_FIB.c
@@ -0,0 +1,290 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+
+/**
+ * Right now, the FIB table is sparse.  There can be an entry for /a and for /a/b/c, but
+ * not for /a/b.  This means we need to exhastively lookup all the components to make sure
+ * there's not a route for it.
+ *
+ */
+
+#include <config.h>
+#include <stdio.h>
+
+#include <ccnx/forwarder/metis/processor/metis_FIB.h>
+#include <ccnx/forwarder/metis/processor/metis_FibEntry.h>
+#include <ccnx/forwarder/metis/processor/metis_HashTableFunction.h>
+#include <parc/algol/parc_Memory.h>
+#include <parc/algol/parc_TreeRedBlack.h>
+
+#include <LongBow/runtime.h>
+
+// =====================================================
+
+/**
+ * @function hashTableFunction_FibEntryDestroyer
+ * @abstract Used in the hash table to destroy the data pointer when an item's removed
+ * @discussion
+ *   <#Discussion#>
+ *
+ * @param <#param1#>
+ * @return <#return#>
+ */
+static void
+_hashTableFunction_FibEntryDestroyer(void **dataPtr)
+{
+    metisFibEntry_Release((MetisFibEntry **) dataPtr);
+}
+
+/**
+ * @function hashTableFunction_TlvNameDestroyer
+ * @abstract Used in the hash table to destroy the key pointer when an item's removed
+ * @discussion
+ *   <#Discussion#>
+ *
+ * @param <#param1#>
+ * @return <#return#>
+ */
+static void
+_hashTableFunction_TlvNameDestroyer(void **dataPtr)
+{
+    metisTlvName_Release((MetisTlvName **) dataPtr);
+}
+
+// =====================================================
+
+struct metis_fib {
+    // KEY = tlvName, VALUE = FibEntry
+    PARCHashCodeTable *tableByName;
+
+    // KEY = tlvName.  We use a tree for the keys because that
+    // has the same average insert and remove time.  The tree
+    // is only used by GetEntries, which in turn is used by things
+    // that want to enumerate the FIB
+    PARCTreeRedBlack *tableOfKeys;
+
+    MetisLogger *logger;
+
+    // If there are no forward paths, we return an emtpy set.  Allocate this
+    // once and return a reference to it whenever we need an empty set.
+    MetisNumberSet *emptySet;
+};
+
+static MetisFibEntry *_metisFIB_CreateFibEntry(MetisFIB *fib, MetisTlvName *tlvName, const char *fwdStrategy);
+
+// =====================================================
+// Public API
+
+MetisFIB *
+metisFIB_Create(MetisLogger *logger)
+{
+    unsigned initialSize = 1024;
+
+    MetisFIB *fib = parcMemory_AllocateAndClear(sizeof(MetisFIB));
+    assertNotNull(fib, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisFIB));
+    fib->emptySet = metisNumberSet_Create();
+    fib->logger = metisLogger_Acquire(logger);
+    fib->tableByName = parcHashCodeTable_Create_Size(metisHashTableFunction_TlvNameEquals,
+                                                     metisHashTableFunction_TlvNameHashCode,
+                                                     _hashTableFunction_TlvNameDestroyer,
+                                                     _hashTableFunction_FibEntryDestroyer,
+                                                     initialSize);
+
+    fib->tableOfKeys =
+        parcTreeRedBlack_Create(metisHashTableFunction_TlvNameCompare, NULL, NULL, NULL, NULL, NULL);
+
+    if (metisLogger_IsLoggable(fib->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) {
+        metisLogger_Log(fib->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__,
+                        "FIB %p created with initialSize %u",
+                        (void *) fib, initialSize);
+    }
+
+    return fib;
+}
+
+void
+metisFIB_Destroy(MetisFIB **fibPtr)
+{
+    assertNotNull(fibPtr, "Parameter must be non-null double pointer");
+    assertNotNull(*fibPtr, "Parameter must dereference to non-null pointer");
+
+    MetisFIB *fib = *fibPtr;
+
+    if (metisLogger_IsLoggable(fib->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) {
+        metisLogger_Log(fib->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__,
+                        "FIB %p destroyed",
+                        (void *) fib);
+    }
+
+    metisNumberSet_Release(&fib->emptySet);
+    metisLogger_Release(&fib->logger);
+    parcTreeRedBlack_Destroy(&fib->tableOfKeys);
+    parcHashCodeTable_Destroy(&fib->tableByName);
+    parcMemory_Deallocate((void **) &fib);
+    *fibPtr = NULL;
+}
+
+MetisFibEntry *
+metisFIB_Match(MetisFIB *fib, const MetisMessage *interestMessage)
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+    assertNotNull(interestMessage, "Parameter interestMessage must be non-null");
+
+    if (metisMessage_HasName(interestMessage)) {
+        // this is NOT reference counted, don't destroy it
+        MetisTlvName *tlvName = metisMessage_GetName(interestMessage);
+        MetisFibEntry *longestMatchingFibEntry = NULL;
+
+        // because the FIB table is sparse, we need to scan all the name segments in order.
+        for (size_t i = 0; i < metisTlvName_SegmentCount(tlvName); i++) {
+            MetisTlvName *prefixName = metisTlvName_Slice(tlvName, i + 1);
+            MetisFibEntry *fibEntry = parcHashCodeTable_Get(fib->tableByName, prefixName);
+            if (fibEntry != NULL) {
+
+                // we can accept the FIB entry if it does not contain the ingress connection id or if
+                // there is more than one forward path besides the ingress connection id.
+                const MetisNumberSet *nexthops = metisFibEntry_GetNexthops(fibEntry);
+                bool containsIngressConnectionId = metisNumberSet_Contains(nexthops, metisMessage_GetIngressConnectionId(interestMessage));
+                size_t nextHopsCount = metisNumberSet_Length(nexthops);
+                // Further control on the nextHopCount, because if the first condition is true (no ingress connection among the next hops), the number of next hops could still be 0.
+                if ((!containsIngressConnectionId && nextHopsCount > 0) || nextHopsCount > 1) {
+                    longestMatchingFibEntry = fibEntry;
+                }
+            }
+            metisTlvName_Release(&prefixName);
+        }
+        return longestMatchingFibEntry;
+    }
+    
+    return NULL;
+}
+
+bool
+metisFIB_AddOrUpdate(MetisFIB *fib, CPIRouteEntry *route, char const * fwdStrategy) 
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+    assertNotNull(route, "Parameter route must be non-null");
+
+    const CCNxName *ccnxName = cpiRouteEntry_GetPrefix(route);
+    MetisTlvName *tlvName = metisTlvName_CreateFromCCNxName(ccnxName);
+
+    MetisFibEntry *fibEntry = parcHashCodeTable_Get(fib->tableByName, tlvName);
+    if (fibEntry == NULL) {
+        if(fwdStrategy == NULL){
+            fwdStrategy = "random"; //default strategy for now
+        }
+        fibEntry = _metisFIB_CreateFibEntry(fib, tlvName, fwdStrategy);
+    }
+
+    metisFibEntry_AddNexthop(fibEntry, route);
+
+    // if anyone saved the name in a table, they copied it.
+    metisTlvName_Release(&tlvName);
+
+    return true;
+}
+
+bool
+metisFIB_Remove(MetisFIB *fib, CPIRouteEntry *route)
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+    assertNotNull(route, "Parameter route must be non-null");
+
+    bool routeRemoved = false;
+
+    const CCNxName *ccnxName = cpiRouteEntry_GetPrefix(route);
+    MetisTlvName *tlvName = metisTlvName_CreateFromCCNxName(ccnxName);
+
+    MetisFibEntry *fibEntry = parcHashCodeTable_Get(fib->tableByName, tlvName);
+    if (fibEntry != NULL) {
+        metisFibEntry_RemoveNexthopByRoute(fibEntry, route);
+        if (metisFibEntry_NexthopCount(fibEntry) == 0) {
+            parcTreeRedBlack_Remove(fib->tableOfKeys, tlvName);
+
+            // this will de-allocate the key, so must be done last
+            parcHashCodeTable_Del(fib->tableByName, tlvName);
+
+            routeRemoved = true;
+        }
+    }
+
+    metisTlvName_Release(&tlvName);
+    return routeRemoved;
+}
+
+size_t
+metisFIB_Length(const MetisFIB *fib)
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+    return parcHashCodeTable_Length(fib->tableByName);
+}
+
+MetisFibEntryList *
+metisFIB_GetEntries(const MetisFIB *fib)
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+    MetisFibEntryList *list = metisFibEntryList_Create();
+
+    PARCArrayList *values = parcTreeRedBlack_Values(fib->tableOfKeys);
+    for (size_t i = 0; i < parcArrayList_Size(values); i++) {
+        MetisFibEntry *original = (MetisFibEntry *) parcArrayList_Get(values, i);
+        metisFibEntryList_Append(list, original);
+    }
+    parcArrayList_Destroy(&values);
+    return list;
+}
+
+void
+metisFIB_RemoveConnectionIdFromRoutes(MetisFIB *fib, unsigned connectionId)
+{
+    assertNotNull(fib, "Parameter fib must be non-null");
+
+    // Walk the entire tree and remove the connection id from every entry.
+    PARCArrayList *values = parcTreeRedBlack_Values(fib->tableOfKeys);
+    for (size_t i = 0; i < parcArrayList_Size(values); i++) {
+        MetisFibEntry *original = (MetisFibEntry *) parcArrayList_Get(values, i);
+        metisFibEntry_RemoveNexthopByConnectionId(original, connectionId);
+    }
+    parcArrayList_Destroy(&values);
+}
+
+// =========================================================================
+// Private API
+
+/**
+ * @function metisFib_CreateFibEntry
+ * @abstract Create the given FIB entry
+ * @discussion
+ *    PRECONDITION: You know that the FIB entry does not exist already
+ *
+ * @param <#param1#>
+ * @return <#return#>
+ */
+static MetisFibEntry *
+_metisFIB_CreateFibEntry(MetisFIB *fib, MetisTlvName *tlvName, const char *fwdStrategy)
+{
+    MetisFibEntry *entry = metisFibEntry_Create(tlvName, fwdStrategy);
+
+    // add a reference counted name, as we specified a key destroyer when we
+    // created the table.
+    MetisTlvName *copy = metisTlvName_Acquire(tlvName);
+    parcHashCodeTable_Add(fib->tableByName, copy, entry);
+
+    // this is an index structure.  It does not have its own destroyer functions in
+    // the data structure.  The data in this table is the same pointer as in the hash table.
+    parcTreeRedBlack_Insert(fib->tableOfKeys, copy, entry);
+
+    return entry;
+}