2 * Copyright (c) 2018 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
17 #include <vnet/ip/ip4_packet.h>
18 #include <vnet/ip/ip6_packet.h>
19 #include <arpa/inet.h>
20 #include <vnet/ip/format.h>
23 masked_address32 (uint32_t addr, uint8_t len)
26 return htonl(len == 32 ? a : a & ~(~0u >> len));
29 masked_address64 (uint64_t addr, uint8_t len)
31 return len == 64 ? addr : addr & ~(~0ull >> len);
35 lpm_32_add (lpm_t *lpm, void *addr_v, u8 pfxlen,
38 uword * hash, * result;
40 ip4_address_t *addr = addr_v;
41 key = masked_address32(addr->data_u32, pfxlen);
42 hash = lpm->hash[pfxlen];
43 result = hash_get (hash, key);
44 if (result) /* Entry exists */
45 clib_warning("%U/%d already exists in table for domain %d",
46 format_ip4_address, addr, pfxlen, result[0]);
52 hash = hash_create (32 /* elts */, sizeof (uword));
53 hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
55 hash = hash_set(hash, key, value);
56 lpm->hash[pfxlen] = hash;
60 lpm_32_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
62 uword * hash, * result;
64 ip4_address_t *addr = addr_v;
65 key = masked_address32(addr->data_u32, pfxlen);
66 hash = lpm->hash[pfxlen];
67 result = hash_get (hash, key);
69 hash_unset(hash, key);
70 lpm->hash[pfxlen] = hash;
74 lpm_32_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
76 uword * hash, * result;
79 ip4_address_t *addr = addr_v;
80 for (mask_len = pfxlen; mask_len >= 0; mask_len--) {
81 hash = lpm->hash[mask_len];
83 key = masked_address32(addr->data_u32, mask_len);
84 result = hash_get (hash, key);
94 lpm_128_lookup_core (lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
96 BVT(clib_bihash_kv) kv, v;
98 kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
99 kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
101 rv = BV(clib_bihash_search_inline_2)(&lpm->bihash, &kv, &v);
109 lpm_128_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
111 ip6_address_t *addr = addr_v;
114 clib_bitmap_foreach (i, lpm->prefix_lengths_bitmap,
116 rv = lpm_128_lookup_core(lpm, addr, i, &value);
124 lpm_128_add (lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
126 BVT(clib_bihash_kv) kv;
127 ip6_address_t *addr = addr_v;
129 kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
130 kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
133 BV(clib_bihash_add_del)(&lpm->bihash, &kv, 1);
134 lpm->prefix_length_refcount[pfxlen]++;
135 lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap, 128 - pfxlen, 1);
139 lpm_128_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
141 ip6_address_t *addr = addr_v;
142 BVT(clib_bihash_kv) kv;
143 kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
144 kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
146 BV(clib_bihash_add_del)(&lpm->bihash, &kv, 0);
148 /* refcount accounting */
149 ASSERT (lpm->prefix_length_refcount[pfxlen] > 0);
150 if (--lpm->prefix_length_refcount[pfxlen] == 0) {
151 lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap,
157 lpm_table_init (enum lpm_type_e lpm_type)
159 lpm_t * lpm = clib_mem_alloc(sizeof(*lpm));
160 memset(lpm, 0, sizeof(*lpm));
164 lpm->add = lpm_32_add;
165 lpm->delete = lpm_32_delete;
166 lpm->lookup = lpm_32_lookup;
168 case LPM_TYPE_KEY128:
169 lpm->add = lpm_128_add;
170 lpm->delete = lpm_128_delete;
171 lpm->lookup = lpm_128_lookup;
172 /* Make bihash sizes configurable */
173 BV (clib_bihash_init) (&(lpm->bihash),
174 "LPM 128", 64*1024, 32<<20);