Line data Source code
1 : /*
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:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
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.
14 : */
15 :
16 : #include "lpm.h"
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>
21 :
22 : static uint32_t
23 8329 : masked_address32 (uint32_t addr, uint8_t len)
24 : {
25 8329 : u32 a = ntohl(addr);
26 8329 : return htonl(len == 32 ? a : a & ~(~0u >> len));
27 : }
28 : static uint64_t
29 16502 : masked_address64 (uint64_t addr, uint8_t len)
30 : {
31 16502 : return len == 64 ? addr : addr & ~(~0ull >> len);
32 : }
33 :
34 : static void
35 4120 : lpm_32_add (lpm_t *lpm, void *addr_v, u8 pfxlen,
36 : u32 value)
37 : {
38 : uword * hash, * result;
39 : u32 key;
40 4120 : ip4_address_t *addr = addr_v;
41 4120 : key = masked_address32(addr->data_u32, pfxlen);
42 4120 : hash = lpm->hash[pfxlen];
43 4120 : result = hash_get (hash, key);
44 4120 : if (result) /* Entry exists */
45 20 : clib_warning("%U/%d already exists in table for domain %d",
46 : format_ip4_address, addr, pfxlen, result[0]);
47 :
48 : /*
49 : * adding a new entry
50 : */
51 4120 : if (hash == NULL) {
52 4 : hash = hash_create (32 /* elts */, sizeof (uword));
53 4 : hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
54 : }
55 4120 : hash = hash_set(hash, key, value);
56 4120 : lpm->hash[pfxlen] = hash;
57 4120 : }
58 :
59 : static void
60 4097 : lpm_32_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
61 : {
62 : uword * hash, * result;
63 : u32 key;
64 4097 : ip4_address_t *addr = addr_v;
65 4097 : key = masked_address32(addr->data_u32, pfxlen);
66 4097 : hash = lpm->hash[pfxlen];
67 4097 : result = hash_get (hash, key);
68 4097 : if (result)
69 4097 : hash_unset(hash, key);
70 4097 : lpm->hash[pfxlen] = hash;
71 4097 : }
72 :
73 : static u32
74 59 : lpm_32_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
75 : {
76 : uword * hash, * result;
77 : i32 mask_len;
78 : u32 key;
79 59 : ip4_address_t *addr = addr_v;
80 938 : for (mask_len = pfxlen; mask_len >= 0; mask_len--) {
81 931 : hash = lpm->hash[mask_len];
82 931 : if (hash) {
83 112 : key = masked_address32(addr->data_u32, mask_len);
84 112 : result = hash_get (hash, key);
85 112 : if (result != NULL) {
86 52 : return (result[0]);
87 : }
88 : }
89 : }
90 7 : return (~0);
91 : }
92 :
93 : static int
94 34 : lpm_128_lookup_core (lpm_t *lpm, ip6_address_t *addr, u8 pfxlen, u32 *value)
95 : {
96 : BVT(clib_bihash_kv) kv, v;
97 : int rv;
98 34 : kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
99 34 : kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
100 34 : kv.key[2] = pfxlen;
101 34 : rv = BV(clib_bihash_search_inline_2)(&lpm->bihash, &kv, &v);
102 34 : if (rv != 0)
103 12 : return -1;
104 22 : *value = v.value;
105 22 : return 0;
106 : }
107 :
108 : static u32
109 23 : lpm_128_lookup (lpm_t *lpm, void *addr_v, u8 pfxlen)
110 : {
111 23 : ip6_address_t *addr = addr_v;
112 23 : int i = 0, rv;
113 : u32 value;
114 35 : clib_bitmap_foreach (i, lpm->prefix_lengths_bitmap)
115 : {
116 34 : rv = lpm_128_lookup_core(lpm, addr, i, &value);
117 34 : if (rv == 0)
118 22 : return value;
119 : }
120 1 : return ~0;
121 : }
122 :
123 : static void
124 4120 : lpm_128_add (lpm_t *lpm, void *addr_v, u8 pfxlen, u32 value)
125 : {
126 : BVT(clib_bihash_kv) kv;
127 4120 : ip6_address_t *addr = addr_v;
128 :
129 4120 : kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
130 4120 : kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
131 4120 : kv.key[2] = pfxlen;
132 4120 : kv.value = value;
133 4120 : BV(clib_bihash_add_del)(&lpm->bihash, &kv, 1);
134 4120 : lpm->prefix_length_refcount[pfxlen]++;
135 4120 : lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap, 128 - pfxlen, 1);
136 4120 : }
137 :
138 : static void
139 4097 : lpm_128_delete (lpm_t *lpm, void *addr_v, u8 pfxlen)
140 : {
141 4097 : ip6_address_t *addr = addr_v;
142 : BVT(clib_bihash_kv) kv;
143 4097 : kv.key[0] = masked_address64(addr->as_u64[0], pfxlen > 64 ? 64 : pfxlen);
144 4097 : kv.key[1] = masked_address64(addr->as_u64[1], pfxlen > 64 ? pfxlen - 64 : 0);
145 4097 : kv.key[2] = pfxlen;
146 4097 : BV(clib_bihash_add_del)(&lpm->bihash, &kv, 0);
147 :
148 : /* refcount accounting */
149 4097 : ASSERT (lpm->prefix_length_refcount[pfxlen] > 0);
150 4097 : if (--lpm->prefix_length_refcount[pfxlen] == 0) {
151 2 : lpm->prefix_lengths_bitmap = clib_bitmap_set (lpm->prefix_lengths_bitmap,
152 2 : 128 - pfxlen, 0);
153 : }
154 4097 : }
155 :
156 : lpm_t *
157 1677 : lpm_table_init (enum lpm_type_e lpm_type)
158 : {
159 1677 : lpm_t * lpm = clib_mem_alloc(sizeof(*lpm));
160 1677 : memset(lpm, 0, sizeof(*lpm));
161 :
162 1677 : switch (lpm_type) {
163 559 : case LPM_TYPE_KEY32:
164 559 : lpm->add = lpm_32_add;
165 559 : lpm->delete = lpm_32_delete;
166 559 : lpm->lookup = lpm_32_lookup;
167 559 : break;
168 1118 : case LPM_TYPE_KEY128:
169 1118 : lpm->add = lpm_128_add;
170 1118 : lpm->delete = lpm_128_delete;
171 1118 : lpm->lookup = lpm_128_lookup;
172 : /* Make bihash sizes configurable */
173 1118 : BV (clib_bihash_init) (&(lpm->bihash),
174 : "LPM 128", 64*1024, 32<<20);
175 :
176 1118 : break;
177 0 : default:
178 0 : ASSERT(0);
179 : }
180 1677 : return lpm;
181 : }
|
