Line data Source code
1 : /*
2 : * Copyright (c) 2016 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 <vnet/fib/fib_table.h>
17 : #include <vnet/fib/fib_entry.h>
18 : #include <vnet/fib/ip4_fib.h>
19 :
20 : /*
21 : * ip4_fib_hash_table_lookup_exact_match
22 : *
23 : * Exact match prefix lookup
24 : */
25 : fib_node_index_t
26 190295 : ip4_fib_hash_table_lookup_exact_match (const ip4_fib_hash_t *fib,
27 : const ip4_address_t *addr,
28 : u32 len)
29 : {
30 : uword * hash, * result;
31 : u32 key;
32 :
33 190295 : hash = fib->fib_entry_by_dst_address[len];
34 190295 : key = (addr->data_u32 & ip4_main.fib_masks[len]);
35 :
36 190295 : result = hash_get(hash, key);
37 :
38 190295 : if (NULL != result) {
39 165614 : return (result[0]);
40 : }
41 24681 : return (FIB_NODE_INDEX_INVALID);
42 : }
43 :
44 : /*
45 : * ip4_fib_hash_table_lookup_adj
46 : *
47 : * Longest prefix match
48 : */
49 : index_t
50 100 : ip4_fib_hash_table_lookup_lb (const ip4_fib_hash_t *fib,
51 : const ip4_address_t *addr)
52 : {
53 : fib_node_index_t fei;
54 :
55 100 : fei = ip4_fib_hash_table_lookup(fib, addr, 32);
56 :
57 100 : if (FIB_NODE_INDEX_INVALID != fei)
58 : {
59 : const dpo_id_t *dpo;
60 :
61 100 : dpo = fib_entry_contribute_ip_forwarding(fei);
62 :
63 100 : return (dpo->dpoi_index);
64 : }
65 0 : return (INDEX_INVALID);
66 : }
67 :
68 : /*
69 : * ip4_fib_hash_table_lookup
70 : *
71 : * Longest prefix match
72 : */
73 : fib_node_index_t
74 118211 : ip4_fib_hash_table_lookup (const ip4_fib_hash_t *fib,
75 : const ip4_address_t *addr,
76 : u32 len)
77 : {
78 : uword * hash, * result;
79 : i32 mask_len;
80 : u32 key;
81 :
82 755169 : for (mask_len = len; mask_len >= 0; mask_len--)
83 : {
84 755169 : hash = fib->fib_entry_by_dst_address[mask_len];
85 755169 : key = (addr->data_u32 & ip4_main.fib_masks[mask_len]);
86 :
87 755169 : result = hash_get (hash, key);
88 :
89 755169 : if (NULL != result) {
90 118211 : return (result[0]);
91 : }
92 : }
93 0 : return (FIB_NODE_INDEX_INVALID);
94 : }
95 :
96 : void
97 21954 : ip4_fib_hash_table_entry_insert (ip4_fib_hash_t *fib,
98 : const ip4_address_t *addr,
99 : u32 len,
100 : fib_node_index_t fib_entry_index)
101 : {
102 : uword * hash, * result;
103 : u32 key;
104 :
105 21954 : key = (addr->data_u32 & ip4_main.fib_masks[len]);
106 21954 : hash = fib->fib_entry_by_dst_address[len];
107 21954 : result = hash_get (hash, key);
108 :
109 21954 : if (NULL == result) {
110 : /*
111 : * adding a new entry
112 : */
113 :
114 21954 : if (NULL == hash) {
115 2519 : hash = hash_create (32 /* elts */, sizeof (uword));
116 2519 : hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
117 :
118 : }
119 21954 : hash = hash_set(hash, key, fib_entry_index);
120 21954 : fib->fib_entry_by_dst_address[len] = hash;
121 : }
122 : else
123 : {
124 0 : ASSERT(0);
125 : }
126 21954 : }
127 :
128 : void
129 15812 : ip4_fib_hash_table_entry_remove (ip4_fib_hash_t *fib,
130 : const ip4_address_t *addr,
131 : u32 len)
132 : {
133 : uword * hash, * result;
134 : u32 key;
135 :
136 15812 : key = (addr->data_u32 & ip4_main.fib_masks[len]);
137 15812 : hash = fib->fib_entry_by_dst_address[len];
138 15812 : result = hash_get (hash, key);
139 :
140 15812 : if (NULL == result)
141 : {
142 : /*
143 : * removing a non-existent entry. i'll allow it.
144 : */
145 : }
146 : else
147 : {
148 15812 : hash_unset(hash, key);
149 : }
150 :
151 15812 : fib->fib_entry_by_dst_address[len] = hash;
152 15812 : }
153 :
154 : void
155 3169 : ip4_fib_hash_table_walk (ip4_fib_hash_t *fib,
156 : fib_table_walk_fn_t fn,
157 : void *ctx)
158 : {
159 3169 : fib_prefix_t root = {
160 : .fp_proto = FIB_PROTOCOL_IP4,
161 : // address and length default to all 0
162 : };
163 :
164 : /*
165 : * A full tree walk is the dengenerate case of a sub-tree from
166 : * the very root
167 : */
168 3169 : return (ip4_fib_hash_table_sub_tree_walk(fib, &root, fn, ctx));
169 : }
170 :
171 : void
172 3225 : ip4_fib_hash_table_sub_tree_walk (ip4_fib_hash_t *fib,
173 : const fib_prefix_t *root,
174 : fib_table_walk_fn_t fn,
175 : void *ctx)
176 : {
177 3225 : fib_prefix_t *sub_trees = NULL;
178 : int i;
179 :
180 : /*
181 : * There is no efficient way to walk this array of hash tables.
182 : * so we walk each table with a mask length greater than and equal to
183 : * the required root and check it is covered by the root.
184 : */
185 3225 : for (i = root->fp_len;
186 108044 : i < ARRAY_LEN (fib->fib_entry_by_dst_address);
187 104819 : i++)
188 : {
189 104819 : uword * hash = fib->fib_entry_by_dst_address[i];
190 :
191 104819 : if (NULL != hash)
192 : {
193 : ip4_address_t key;
194 : hash_pair_t * p;
195 :
196 1391040 : hash_foreach_pair (p, hash,
197 : ({
198 : key.as_u32 = p->key;
199 : if (ip4_destination_matches_route(&ip4_main,
200 : &key,
201 : &root->fp_addr.ip4,
202 : root->fp_len))
203 : {
204 : const fib_prefix_t *sub_tree;
205 : int skip = 0;
206 :
207 : /*
208 : * exclude sub-trees the walk does not want to explore
209 : */
210 : vec_foreach(sub_tree, sub_trees)
211 : {
212 : if (ip4_destination_matches_route(&ip4_main,
213 : &key,
214 : &sub_tree->fp_addr.ip4,
215 : sub_tree->fp_len))
216 : {
217 : skip = 1;
218 : break;
219 : }
220 : }
221 :
222 : if (!skip)
223 : {
224 : switch (fn(p->value[0], ctx))
225 : {
226 : case FIB_TABLE_WALK_CONTINUE:
227 : break;
228 : case FIB_TABLE_WALK_SUB_TREE_STOP: {
229 : fib_prefix_t pfx = {
230 : .fp_proto = FIB_PROTOCOL_IP4,
231 : .fp_len = i,
232 : .fp_addr.ip4 = key,
233 : };
234 : vec_add1(sub_trees, pfx);
235 : break;
236 : }
237 : case FIB_TABLE_WALK_STOP:
238 : goto done;
239 : }
240 : }
241 : }
242 : }));
243 : }
244 : }
245 3225 : done:
246 3225 : vec_free(sub_trees);
247 3225 : return;
248 : }
249 :
|
