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 : * @brief The IPv4 FIB
17 : *
18 : * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding
19 : * table contains all the routes that the control plane has programmed, the
20 : * forwarding table contains the sub-set of those routes that can be used to
21 : * forward packets.
22 : * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed
23 : * by mask length, the forwarding table is an mtrie
24 : *
25 : * This IPv4 FIB is used by the protocol independent FIB. So directly using
26 : * this APIs in client code is not encouraged. However, this IPv4 FIB can be
27 : * used if all the client wants is an IPv4 prefix data-base
28 : */
29 :
30 : #ifndef __IP4_FIB_H__
31 : #define __IP4_FIB_H__
32 :
33 : #include <vlib/vlib.h>
34 : #include <vnet/ip/ip.h>
35 : #include <vnet/fib/fib_entry.h>
36 : #include <vnet/fib/fib_table.h>
37 : #include <vnet/fib/ip4_fib_8.h>
38 : #include <vnet/fib/ip4_fib_16.h>
39 :
40 : // for the VPP_IP_FIB_MTRIE_16 definition
41 : #include <vpp/vnet/config.h>
42 :
43 : /**
44 : * the FIB module uses the 16-8-8 stride trie
45 : */
46 : #ifdef VPP_IP_FIB_MTRIE_16
47 : typedef ip4_fib_16_t ip4_fib_t;
48 :
49 : #define ip4_fibs ip4_fib_16s
50 : #define ip4_fib_table_lookup ip4_fib_16_table_lookup
51 : #define ip4_fib_table_lookup_exact_match ip4_fib_16_table_lookup_exact_match
52 : #define ip4_fib_table_entry_remove ip4_fib_16_table_entry_remove
53 : #define ip4_fib_table_entry_insert ip4_fib_16_table_entry_insert
54 : #define ip4_fib_table_fwding_dpo_update ip4_fib_16_table_fwding_dpo_update
55 : #define ip4_fib_table_fwding_dpo_remove ip4_fib_16_table_fwding_dpo_remove
56 : #define ip4_fib_table_lookup_lb ip4_fib_16_table_lookup_lb
57 : #define ip4_fib_table_walk ip4_fib_16_table_walk
58 : #define ip4_fib_table_sub_tree_walk ip4_fib_16_table_sub_tree_walk
59 : #define ip4_fib_table_init ip4_fib_16_table_init
60 : #define ip4_fib_table_free ip4_fib_16_table_free
61 : #define ip4_mtrie_memory_usage ip4_mtrie_16_memory_usage
62 : #define format_ip4_mtrie format_ip4_mtrie_16
63 :
64 : #else
65 : typedef ip4_fib_8_t ip4_fib_t;
66 :
67 : #define ip4_fibs ip4_fib_8s
68 : #define ip4_fib_table_lookup ip4_fib_8_table_lookup
69 : #define ip4_fib_table_lookup_exact_match ip4_fib_8_table_lookup_exact_match
70 : #define ip4_fib_table_entry_remove ip4_fib_8_table_entry_remove
71 : #define ip4_fib_table_entry_insert ip4_fib_8_table_entry_insert
72 : #define ip4_fib_table_fwding_dpo_update ip4_fib_8_table_fwding_dpo_update
73 : #define ip4_fib_table_fwding_dpo_remove ip4_fib_8_table_fwding_dpo_remove
74 : #define ip4_fib_table_lookup_lb ip4_fib_8_table_lookup_lb
75 : #define ip4_fib_table_walk ip4_fib_8_table_walk
76 : #define ip4_fib_table_sub_tree_walk ip4_fib_8_table_sub_tree_walk
77 : #define ip4_fib_table_init ip4_fib_8_table_init
78 : #define ip4_fib_table_free ip4_fib_8_table_free
79 : #define ip4_mtrie_memory_usage ip4_mtrie_8_memory_usage
80 : #define format_ip4_mtrie format_ip4_mtrie_8
81 :
82 : #endif
83 :
84 : /**
85 : * @brief Get the FIB at the given index
86 : */
87 : static inline ip4_fib_t *
88 16096926 : ip4_fib_get (u32 index)
89 : {
90 16096926 : return (pool_elt_at_index(ip4_fibs, index));
91 : }
92 :
93 : always_inline u32
94 : ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
95 : {
96 : return (ip4_fib_table_lookup_lb(
97 : ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
98 : dst));
99 : }
100 :
101 : /**
102 : * @brief Get or create an IPv4 fib.
103 : *
104 : * Get or create an IPv4 fib with the provided table ID.
105 : *
106 : * @param table_id
107 : * When set to \c ~0, an arbitrary and unused fib ID is picked
108 : * and can be retrieved with \c ret->table_id.
109 : * Otherwise, the fib ID to be used to retrieve or create the desired fib.
110 : * @returns A pointer to the retrieved or created fib.
111 : *
112 : */
113 : extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id,
114 : fib_source_t src);
115 : extern u32 ip4_fib_table_create_and_lock(fib_source_t src);
116 : extern void ip4_fib_table_destroy(u32 fib_index);
117 :
118 : extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
119 :
120 : static inline
121 23318 : u32 ip4_fib_index_from_table_id (u32 table_id)
122 : {
123 23318 : ip4_main_t * im = &ip4_main;
124 : uword * p;
125 :
126 23318 : p = hash_get (im->fib_index_by_table_id, table_id);
127 23318 : if (!p)
128 1929 : return ~0;
129 :
130 21389 : return p[0];
131 : }
132 :
133 : extern u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index);
134 :
135 : #ifdef VPP_IP_FIB_MTRIE_16
136 : always_inline index_t
137 553004 : ip4_fib_forwarding_lookup (u32 fib_index,
138 : const ip4_address_t * addr)
139 : {
140 : ip4_mtrie_leaf_t leaf;
141 : ip4_mtrie_16_t * mtrie;
142 :
143 553004 : mtrie = &ip4_fib_get(fib_index)->mtrie;
144 :
145 553004 : leaf = ip4_mtrie_16_lookup_step_one (mtrie, addr);
146 553004 : leaf = ip4_mtrie_16_lookup_step (leaf, addr, 2);
147 553004 : leaf = ip4_mtrie_16_lookup_step (leaf, addr, 3);
148 :
149 553004 : return (ip4_mtrie_leaf_get_adj_index(leaf));
150 : }
151 :
152 : static_always_inline void
153 550836 : ip4_fib_forwarding_lookup_x2 (u32 fib_index0,
154 : u32 fib_index1,
155 : const ip4_address_t * addr0,
156 : const ip4_address_t * addr1,
157 : index_t *lb0,
158 : index_t *lb1)
159 : {
160 : ip4_mtrie_leaf_t leaf[2];
161 : ip4_mtrie_16_t * mtrie[2];
162 :
163 550836 : mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
164 550836 : mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
165 :
166 550836 : leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
167 550836 : leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
168 550836 : leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2);
169 550836 : leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2);
170 550836 : leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3);
171 550836 : leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3);
172 :
173 550836 : *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
174 550836 : *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
175 550836 : }
176 :
177 : static_always_inline void
178 3511770 : ip4_fib_forwarding_lookup_x4 (u32 fib_index0,
179 : u32 fib_index1,
180 : u32 fib_index2,
181 : u32 fib_index3,
182 : const ip4_address_t * addr0,
183 : const ip4_address_t * addr1,
184 : const ip4_address_t * addr2,
185 : const ip4_address_t * addr3,
186 : index_t *lb0,
187 : index_t *lb1,
188 : index_t *lb2,
189 : index_t *lb3)
190 : {
191 : ip4_mtrie_leaf_t leaf[4];
192 : ip4_mtrie_16_t * mtrie[4];
193 :
194 3511770 : mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
195 3511770 : mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
196 3511770 : mtrie[2] = &ip4_fib_get(fib_index2)->mtrie;
197 3511770 : mtrie[3] = &ip4_fib_get(fib_index3)->mtrie;
198 :
199 3511770 : leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
200 3511770 : leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
201 3511770 : leaf[2] = ip4_mtrie_16_lookup_step_one (mtrie[2], addr2);
202 3511770 : leaf[3] = ip4_mtrie_16_lookup_step_one (mtrie[3], addr3);
203 :
204 3511770 : leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2);
205 3511770 : leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2);
206 3511770 : leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 2);
207 3511770 : leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 2);
208 :
209 3511770 : leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3);
210 3511770 : leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3);
211 3511770 : leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 3);
212 3511770 : leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 3);
213 :
214 3511770 : *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
215 3511770 : *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
216 3511770 : *lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]);
217 3511770 : *lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]);
218 3511770 : }
219 :
220 : #else
221 :
222 : always_inline index_t
223 : ip4_fib_forwarding_lookup (u32 fib_index,
224 : const ip4_address_t * addr)
225 : {
226 : ip4_mtrie_leaf_t leaf;
227 : ip4_mtrie_8_t * mtrie;
228 :
229 : mtrie = &ip4_fib_get(fib_index)->mtrie;
230 :
231 : leaf = ip4_mtrie_8_lookup_step_one (mtrie, addr);
232 : leaf = ip4_mtrie_8_lookup_step (leaf, addr, 1);
233 : leaf = ip4_mtrie_8_lookup_step (leaf, addr, 2);
234 : leaf = ip4_mtrie_8_lookup_step (leaf, addr, 3);
235 :
236 : return (ip4_mtrie_leaf_get_adj_index(leaf));
237 : }
238 :
239 : static_always_inline void
240 : ip4_fib_forwarding_lookup_x2 (u32 fib_index0,
241 : u32 fib_index1,
242 : const ip4_address_t * addr0,
243 : const ip4_address_t * addr1,
244 : index_t *lb0,
245 : index_t *lb1)
246 : {
247 : ip4_mtrie_leaf_t leaf[2];
248 : ip4_mtrie_8_t * mtrie[2];
249 :
250 : mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
251 : mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
252 :
253 : leaf[0] = ip4_mtrie_8_lookup_step_one (mtrie[0], addr0);
254 : leaf[1] = ip4_mtrie_8_lookup_step_one (mtrie[1], addr1);
255 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 1);
256 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 1);
257 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 2);
258 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 2);
259 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 3);
260 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 3);
261 :
262 : *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
263 : *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
264 : }
265 :
266 : static_always_inline void
267 : ip4_fib_forwarding_lookup_x4 (u32 fib_index0,
268 : u32 fib_index1,
269 : u32 fib_index2,
270 : u32 fib_index3,
271 : const ip4_address_t * addr0,
272 : const ip4_address_t * addr1,
273 : const ip4_address_t * addr2,
274 : const ip4_address_t * addr3,
275 : index_t *lb0,
276 : index_t *lb1,
277 : index_t *lb2,
278 : index_t *lb3)
279 : {
280 : ip4_mtrie_leaf_t leaf[4];
281 : ip4_mtrie_8_t * mtrie[4];
282 :
283 : mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
284 : mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
285 : mtrie[2] = &ip4_fib_get(fib_index2)->mtrie;
286 : mtrie[3] = &ip4_fib_get(fib_index3)->mtrie;
287 :
288 : leaf[0] = ip4_mtrie_8_lookup_step_one (mtrie[0], addr0);
289 : leaf[1] = ip4_mtrie_8_lookup_step_one (mtrie[1], addr1);
290 : leaf[2] = ip4_mtrie_8_lookup_step_one (mtrie[2], addr2);
291 : leaf[3] = ip4_mtrie_8_lookup_step_one (mtrie[3], addr3);
292 :
293 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 1);
294 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 1);
295 : leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 1);
296 : leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 1);
297 :
298 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 2);
299 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 2);
300 : leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 2);
301 : leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 2);
302 :
303 : leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 3);
304 : leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 3);
305 : leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 3);
306 : leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 3);
307 :
308 : *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
309 : *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
310 : *lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]);
311 : *lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]);
312 : }
313 :
314 : #endif
315 :
316 : #endif
|
