2 * Copyright (c) 2015 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.
16 * ip/ip4_fib.h: ip4 mtrie fib
18 * Copyright (c) 2012 Eliot Dresselhaus
20 * Permission is hereby granted, free of charge, to any person obtaining
21 * a copy of this software and associated documentation files (the
22 * "Software"), to deal in the Software without restriction, including
23 * without limitation the rights to use, copy, modify, merge, publish,
24 * distribute, sublicense, and/or sell copies of the Software, and to
25 * permit persons to whom the Software is furnished to do so, subject to
26 * the following conditions:
28 * The above copyright notice and this permission notice shall be
29 * included in all copies or substantial portions of the Software.
31 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
40 #ifndef included_ip_ip4_fib_h
41 #define included_ip_ip4_fib_h
43 #include <vppinfra/cache.h>
44 #include <vppinfra/vector.h>
45 #include <vnet/ip/lookup.h>
46 #include <vnet/ip/ip4_packet.h> /* for ip4_address_t */
48 /* ip4 fib leafs: 4 ply 8-8-8-8 mtrie.
49 1 + 2*adj_index for terminal leaves.
50 0 + 2*next_ply_index for non-terminals, i.e. PLYs
51 1 => empty (adjacency index of zero is special miss adjacency). */
52 typedef u32 ip4_fib_mtrie_leaf_t;
54 #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
57 * @brief the 16 way stride that is the top PLY of the mtrie
58 * We do not maintain the count of 'real' leaves in this PLY, since
59 * it is never removed. The FIB will destroy the mtrie and the ply once
60 * the FIB is destroyed.
62 #define PLY_16_SIZE (1<<16)
63 typedef struct ip4_fib_mtrie_16_ply_t_
66 * The leaves/slots/buckets to be filed with leafs
70 ip4_fib_mtrie_leaf_t leaves[PLY_16_SIZE];
72 #ifdef CLIB_HAVE_VEC128
73 u32x4 leaves_as_u32x4[PLY_16_SIZE / 4];
78 * Prefix length for terminal leaves.
80 u8 dst_address_bits_of_leaves[PLY_16_SIZE];
81 } ip4_fib_mtrie_16_ply_t;
84 * @brief One ply of the 4 ply mtrie fib.
86 typedef struct ip4_fib_mtrie_8_ply_t_
89 * The leaves/slots/buckets to be filed with leafs
93 ip4_fib_mtrie_leaf_t leaves[256];
95 #ifdef CLIB_HAVE_VEC128
96 u32x4 leaves_as_u32x4[256 / 4];
101 * Prefix length for leaves/ply.
103 u8 dst_address_bits_of_leaves[256];
106 * Number of non-empty leafs (whether terminal or not).
108 i32 n_non_empty_leafs;
111 * The length of the ply's coviering prefix. Also a measure of its depth
112 * If a leaf in a slot has a mask length longer than this then it is
113 * 'non-empty'. Otherwise it is the value of the cover.
115 i32 dst_address_bits_base;
117 /* Pad to cache line boundary. */
118 u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
120 ip4_fib_mtrie_8_ply_t;
122 STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
123 "IP4 Mtrie ply cache line");
126 * @brief The mutiway-TRIE.
127 * There is no data associated with the mtrie apart from the top PLY
132 * Embed the PLY with the mtrie struct. This means that the Data-plane
133 * 'get me the mtrie' returns the first ply, and not an indirect 'pointer'
134 * to it. therefore no cachline misses in the data-path.
136 ip4_fib_mtrie_16_ply_t root_ply;
140 * @brief Initialise an mtrie
142 void ip4_mtrie_init (ip4_fib_mtrie_t * m);
145 * @brief Free an mtrie, It must be emty when free'd
147 void ip4_mtrie_free (ip4_fib_mtrie_t * m);
150 * @brief Add a route/rntry to the mtrie
152 void ip4_fib_mtrie_route_add (ip4_fib_mtrie_t * m,
153 const ip4_address_t * dst_address,
154 u32 dst_address_length, u32 adj_index);
156 * @brief remove a route/rntry to the mtrie
158 void ip4_fib_mtrie_route_del (ip4_fib_mtrie_t * m,
159 const ip4_address_t * dst_address,
160 u32 dst_address_length,
162 u32 cover_address_length, u32 cover_adj_index);
165 * @brief Format/display the contents of the mtrie
167 format_function_t format_ip4_fib_mtrie;
170 * @brief A global pool of 8bit stride plys
172 extern ip4_fib_mtrie_8_ply_t *ip4_ply_pool;
175 * Is the leaf terminal (i.e. an LB index) or non-terminak (i.e. a PLY index)
178 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
184 * From the stored slot value extract the LB index value
187 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
189 ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
194 * @brief Lookup step. Processes 1 byte of 4 byte ip4 address.
196 always_inline ip4_fib_mtrie_leaf_t
197 ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m,
198 ip4_fib_mtrie_leaf_t current_leaf,
199 const ip4_address_t * dst_address,
200 u32 dst_address_byte_index)
202 ip4_fib_mtrie_8_ply_t *ply;
204 uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
206 if (!current_is_terminal)
208 ply = ip4_ply_pool + (current_leaf >> 1);
209 return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
216 * @brief Lookup step number 1. Processes 2 bytes of 4 byte ip4 address.
218 always_inline ip4_fib_mtrie_leaf_t
219 ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t * m,
220 const ip4_address_t * dst_address)
222 ip4_fib_mtrie_leaf_t next_leaf;
224 next_leaf = m->root_ply.leaves[dst_address->as_u16[0]];
229 #endif /* included_ip_ip4_fib_h */
232 * fd.io coding-style-patch-verification: ON
235 * eval: (c-set-style "gnu")