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:
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.
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
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
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
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>
40 // for the VPP_IP_FIB_MTRIE_16 definition
41 #include <vpp/vnet/config.h>
44 * the FIB module uses the 16-8-8 stride trie
46 #ifdef VPP_IP_FIB_MTRIE_16
47 typedef ip4_fib_16_t ip4_fib_t;
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
65 typedef ip4_fib_8_t ip4_fib_t;
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
85 * @brief Get the FIB at the given index
87 static inline ip4_fib_t *
88 ip4_fib_get (u32 index)
90 return (pool_elt_at_index(ip4_fibs, index));
94 ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
96 return (ip4_fib_table_lookup_lb(
97 ip4_fib_get(vec_elt (im->fib_index_by_sw_if_index, sw_if_index)),
102 * @brief Get or create an IPv4 fib.
104 * Get or create an IPv4 fib with the provided 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.
113 extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id,
115 extern u32 ip4_fib_table_create_and_lock(fib_source_t src);
116 extern void ip4_fib_table_destroy(u32 fib_index);
118 extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
121 u32 ip4_fib_index_from_table_id (u32 table_id)
123 ip4_main_t * im = &ip4_main;
126 p = hash_get (im->fib_index_by_table_id, table_id);
133 extern u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index);
135 #ifdef VPP_IP_FIB_MTRIE_16
136 always_inline index_t
137 ip4_fib_forwarding_lookup (u32 fib_index,
138 const ip4_address_t * addr)
140 ip4_mtrie_leaf_t leaf;
141 ip4_mtrie_16_t * mtrie;
143 mtrie = &ip4_fib_get(fib_index)->mtrie;
145 leaf = ip4_mtrie_16_lookup_step_one (mtrie, addr);
146 leaf = ip4_mtrie_16_lookup_step (leaf, addr, 2);
147 leaf = ip4_mtrie_16_lookup_step (leaf, addr, 3);
149 return (ip4_mtrie_leaf_get_adj_index(leaf));
152 static_always_inline void
153 ip4_fib_forwarding_lookup_x2 (u32 fib_index0,
155 const ip4_address_t * addr0,
156 const ip4_address_t * addr1,
160 ip4_mtrie_leaf_t leaf[2];
161 ip4_mtrie_16_t * mtrie[2];
163 mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
164 mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
166 leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
167 leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
168 leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2);
169 leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2);
170 leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3);
171 leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3);
173 *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
174 *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
177 static_always_inline void
178 ip4_fib_forwarding_lookup_x4 (u32 fib_index0,
182 const ip4_address_t * addr0,
183 const ip4_address_t * addr1,
184 const ip4_address_t * addr2,
185 const ip4_address_t * addr3,
191 ip4_mtrie_leaf_t leaf[4];
192 ip4_mtrie_16_t * mtrie[4];
194 mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
195 mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
196 mtrie[2] = &ip4_fib_get(fib_index2)->mtrie;
197 mtrie[3] = &ip4_fib_get(fib_index3)->mtrie;
199 leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0);
200 leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1);
201 leaf[2] = ip4_mtrie_16_lookup_step_one (mtrie[2], addr2);
202 leaf[3] = ip4_mtrie_16_lookup_step_one (mtrie[3], addr3);
204 leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2);
205 leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2);
206 leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 2);
207 leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 2);
209 leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3);
210 leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3);
211 leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 3);
212 leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 3);
214 *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
215 *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
216 *lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]);
217 *lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]);
222 always_inline index_t
223 ip4_fib_forwarding_lookup (u32 fib_index,
224 const ip4_address_t * addr)
226 ip4_mtrie_leaf_t leaf;
227 ip4_mtrie_8_t * mtrie;
229 mtrie = &ip4_fib_get(fib_index)->mtrie;
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);
236 return (ip4_mtrie_leaf_get_adj_index(leaf));
239 static_always_inline void
240 ip4_fib_forwarding_lookup_x2 (u32 fib_index0,
242 const ip4_address_t * addr0,
243 const ip4_address_t * addr1,
247 ip4_mtrie_leaf_t leaf[2];
248 ip4_mtrie_8_t * mtrie[2];
250 mtrie[0] = &ip4_fib_get(fib_index0)->mtrie;
251 mtrie[1] = &ip4_fib_get(fib_index1)->mtrie;
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);
262 *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]);
263 *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]);
266 static_always_inline void
267 ip4_fib_forwarding_lookup_x4 (u32 fib_index0,
271 const ip4_address_t * addr0,
272 const ip4_address_t * addr1,
273 const ip4_address_t * addr2,
274 const ip4_address_t * addr3,
280 ip4_mtrie_leaf_t leaf[4];
281 ip4_mtrie_8_t * mtrie[4];
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;
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);
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);
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);
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);
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]);