MAP: Add longest matching prefix (LPM) data structures

In preparation for adding input feature MAP support, as opposed to
going via the FIB, add MAP's own LPM data structures.

Change-Id: Ie363f0961b0ac9dde2a0fb76cb0c58c904876974
Signed-off-by: Ole Troan <ot@cisco.com>

3 files changed, 220 insertions, 0 deletions

diff --git a/src/plugins/map/CMakeLists.txt b/src/plugins/map/CMakeLists.txt
index 20d5dfebbe6..2d604e6e4d8 100644
--- a/src/plugins/map/CMakeLists.txt
+++ b/src/plugins/map/CMakeLists.txt
@@ -20,6 +20,7 @@ add_vpp_plugin(map
   map_api.c
   map.c
   map_dpo.c
+  lpm.c
 
   API_FILES
   map.api
diff --git a/src/plugins/map/lpm.c b/src/plugins/map/lpm.c
new file mode 100644
index 00000000000..4abeefca06d
--- /dev/null
+++ b/src/plugins/map/lpm.c
@@ -0,0 +1,181 @@
+/*
+ * Copyright (c) 2018 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 "lpm.h"
+#include <vnet/ip/ip4_packet.h>
+#include <vnet/ip/ip6_packet.h>
+#include <arpa/inet.h>
+#include <vnet/ip/format.h>
+
+static uint32_t
+masked_address32 (uint32_t addr, uint8_t len)
+{
+  u32 a = ntohl(addr);
+  return htonl(len == 32 ? a : a & ~(~0u >> len));
+}
+static uint64_t
+masked_address64 (uint64_t addr, uint8_t len)
+{
+  return len == 64 ? addr : addr & ~(~0ull >> len);
+}
+
+static void
+lpm_32_add (lpm_t *lpm, void *addr_v, u8 pfxlen,
+	    u32 value)
+{
+  uword * hash, * result;
+  u32 key;
+  ip4_address_t *addr = addr_v;
+  key = masked_address32(addr->data_u32, pfxlen);
+  hash = lpm->hash[pfxlen];
+  result = hash_get (hash, key);
+  if (result) /* Entry exists */
+    clib_warning("%U/%d already exists in table for domain %d",
+		 format_ip4_address, addr, pfxlen, result[0]);
+
+  /*
+   * adding a new entry
+   */
+  if (hash == NULL) {
+    hash = hash_create (32 /* elts */, sizeof (uword));
+    hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
+  }
+  hash = hash_set(hash, key, value);
+  lpm->hash[pfxlen] = hash;
+}
+
+static void
+lpm_32_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
+{
+  uword * hash, * result;
+  u32 key;
+  ip4_address_t *addr = addr_v;
+  key = masked_address32(addr->data_u32, pfxlen);
+  hash = lpm->hash[pfxlen];
+  result = hash_get (hash, key);
+  if (result)
+    hash_unset(hash, key);
+  lpm->hash[pfxlen] = hash;
+}
+
+static u32
+lpm_32_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
+{
+  uword * hash, * result;
+  i32 mask_len;
+  u32 key;
+  ip4_address_t *addr = addr_v;
+  for (mask_len = pfxlen; mask_len >= 0; mask_len--) {
+    hash = lpm->hash[mask_len];
+    if (hash) {
+      key = masked_address32(addr->data_u32, mask_len);
+      result = hash_get (hash, key);
+      if (result != NULL) {
+	return (result[0]);
+      }
+    }
+  }
+  return (~0);
+}
+
+static int
+lpm_128_lookup_core (lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
+{
+  BVT(clib_bihash_kv) kv, v;
+  int rv;
+  kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
+  kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
+  kv.key[2] = pfxlen;
+  rv = BV(clib_bihash_search_inline_2)(&lpm->bihash, &kv, &v);
+  if (rv != 0)
+    return -1;
+  *value = v.value;
+  return 0;
+}
+
+static u32
+lpm_128_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
+{
+  ip6_address_t *addr = addr_v;
+  int i = 0, rv;
+  u32 value;
+  clib_bitmap_foreach (i, lpm->prefix_lengths_bitmap,
+    ({
+      rv = lpm_128_lookup_core(lpm, addr, i, &value);
+      if (rv == 0)
+	return value;
+    }));
+  return ~0;
+}
+
+static void
+lpm_128_add (lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
+{
+  BVT(clib_bihash_kv) kv;
+  ip6_address_t *addr = addr_v;
+
+  kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
+  kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
+  kv.key[2] = pfxlen;
+  kv.value = value;
+  BV(clib_bihash_add_del)(&lpm->bihash, &kv, 1);
+  lpm->prefix_length_refcount[pfxlen]++;
+  lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap, 128 - pfxlen, 1);
+}
+
+static void
+lpm_128_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
+{
+  ip6_address_t *addr = addr_v;
+  BVT(clib_bihash_kv) kv;
+  kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
+  kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
+  kv.key[2] = pfxlen;
+  BV(clib_bihash_add_del)(&lpm->bihash, &kv, 0);
+
+  /* refcount accounting */
+  ASSERT (lpm->prefix_length_refcount[pfxlen] > 0);
+  if (--lpm->prefix_length_refcount[pfxlen] == 0) {
+    lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap, 
+						  128 - pfxlen, 0);
+  }
+}
+
+lpm_t *
+lpm_table_init (enum lpm_type_e lpm_type)
+{
+  lpm_t * lpm = clib_mem_alloc(sizeof(*lpm));
+  memset(lpm, 0, sizeof(*lpm));
+
+  switch (lpm_type) {
+  case LPM_TYPE_KEY32:
+    lpm->add = lpm_32_add;
+    lpm->delete = lpm_32_delete;
+    lpm->lookup = lpm_32_lookup;
+    break;
+  case LPM_TYPE_KEY128:
+    lpm->add = lpm_128_add;
+    lpm->delete = lpm_128_delete;
+    lpm->lookup = lpm_128_lookup;
+    /* Make bihash sizes configurable */
+    BV (clib_bihash_init) (&(lpm->bihash),
+			   "LPM 128", 64*1024, 32<<20);
+
+    break;
+  default:
+    ASSERT(0);
+  }
+  return lpm;
+}
diff --git a/src/plugins/map/lpm.h b/src/plugins/map/lpm.h
new file mode 100644
index 00000000000..5fe373a4abd
--- /dev/null
+++ b/src/plugins/map/lpm.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (c) 2018 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 <vppinfra/types.h>
+#include <vppinfra/bihash_24_8.h>
+
+enum lpm_type_e {
+  LPM_TYPE_KEY32,
+  LPM_TYPE_KEY128,
+};
+
+typedef struct lpm_ {
+  void (*add) (struct lpm_ *lpm, void *addr_v, u8 pfxlen, u32 value);
+  void (*delete) (struct lpm_ *lpm, void *addr_v, u8 pfxlen);
+  u32 (*lookup) (struct lpm_ *lpm, void *addr_v, u8 pfxlen);
+
+  /* IPv4 LPM */
+  uword *hash[33];
+
+  /* IPv6 LPM */
+  BVT (clib_bihash) bihash;
+  uword *prefix_lengths_bitmap;
+  u32 prefix_length_refcount[129];
+} lpm_t;
+
+lpm_t *lpm_table_init (enum lpm_type_e lpm_type);