summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOle Troan <ot@cisco.com>2018-12-18 12:33:26 +0100
committerDamjan Marion <dmarion@me.com>2018-12-18 13:02:45 +0000
commit91bfa6e2666c56f79cc97407c929d188cb34e90f (patch)
tree47eb4d66b08e0f93ba2218a8a24116daee80e78d
parent9e829a856fdf88b3ea5770048ea20dcd50d1b4eb (diff)
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>
-rw-r--r--src/plugins/map/CMakeLists.txt1
-rw-r--r--src/plugins/map/lpm.c181
-rw-r--r--src/plugins/map/lpm.h38
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);