Line data Source code
1 : /*
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:
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 : * ip/ip4_fib.h: ip4 mtrie fib
17 : *
18 : * Copyright (c) 2012 Eliot Dresselhaus
19 : *
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:
27 : *
28 : * The above copyright notice and this permission notice shall be
29 : * included in all copies or substantial portions of the Software.
30 : *
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.
38 : */
39 :
40 : #ifndef included_ip_ip4_fib_h
41 : #define included_ip_ip4_fib_h
42 :
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 */
47 :
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_mtrie_leaf_t;
53 :
54 : #define IP4_MTRIE_LEAF_EMPTY (1 + 2 * 0)
55 :
56 : /**
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.
61 : */
62 : #define PLY_16_SIZE (1<<16)
63 : typedef struct ip4_mtrie_16_ply_t_
64 : {
65 : /**
66 : * The leaves/slots/buckets to be filed with leafs
67 : */
68 : ip4_mtrie_leaf_t leaves[PLY_16_SIZE];
69 :
70 : /**
71 : * Prefix length for terminal leaves.
72 : */
73 : u8 dst_address_bits_of_leaves[PLY_16_SIZE];
74 : } ip4_mtrie_16_ply_t;
75 :
76 : /**
77 : * @brief One ply of the 4 ply mtrie fib.
78 : */
79 : typedef struct ip4_mtrie_8_ply_t_
80 : {
81 : CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
82 : /**
83 : * The leaves/slots/buckets to be filed with leafs
84 : */
85 : ip4_mtrie_leaf_t leaves[256];
86 :
87 : /**
88 : * Prefix length for leaves/ply.
89 : */
90 : u8 dst_address_bits_of_leaves[256];
91 :
92 : /**
93 : * Number of non-empty leafs (whether terminal or not).
94 : */
95 : i32 n_non_empty_leafs;
96 :
97 : /**
98 : * The length of the ply's covering prefix. Also a measure of its depth
99 : * If a leaf in a slot has a mask length longer than this then it is
100 : * 'non-empty'. Otherwise it is the value of the cover.
101 : */
102 : i32 dst_address_bits_base;
103 : } ip4_mtrie_8_ply_t;
104 :
105 : STATIC_ASSERT (0 == sizeof (ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
106 : "IP4 Mtrie ply cache line");
107 :
108 : /**
109 : * @brief The mutiway-TRIE with a 16-8-8 stride.
110 : * There is no data associated with the mtrie apart from the top PLY
111 : */
112 : typedef struct
113 : {
114 : /**
115 : * Embed the PLY with the mtrie struct. This means that the Data-plane
116 : * 'get me the mtrie' returns the first ply, and not an indirect 'pointer'
117 : * to it. therefore no cacheline misses in the data-path.
118 : */
119 : ip4_mtrie_16_ply_t root_ply;
120 : } ip4_mtrie_16_t;
121 :
122 : /**
123 : * @brief The mutiway-TRIE with a 8-8-8-8 stride.
124 : * There is no data associated with the mtrie apart from the top PLY
125 : */
126 : typedef struct
127 : {
128 : /* pool index of the root ply */
129 : u32 root_ply;
130 : } ip4_mtrie_8_t;
131 :
132 : /**
133 : * @brief Initialise an mtrie
134 : */
135 : void ip4_mtrie_16_init (ip4_mtrie_16_t *m);
136 : void ip4_mtrie_8_init (ip4_mtrie_8_t *m);
137 :
138 : /**
139 : * @brief Free an mtrie, It must be empty when free'd
140 : */
141 : void ip4_mtrie_16_free (ip4_mtrie_16_t *m);
142 : void ip4_mtrie_8_free (ip4_mtrie_8_t *m);
143 :
144 : /**
145 : * @brief Add a route/entry to the mtrie
146 : */
147 : void ip4_mtrie_16_route_add (ip4_mtrie_16_t *m,
148 : const ip4_address_t *dst_address,
149 : u32 dst_address_length, u32 adj_index);
150 : void ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
151 : u32 dst_address_length, u32 adj_index);
152 :
153 : /**
154 : * @brief remove a route/entry to the mtrie
155 : */
156 : void ip4_mtrie_16_route_del (ip4_mtrie_16_t *m,
157 : const ip4_address_t *dst_address,
158 : u32 dst_address_length, u32 adj_index,
159 : u32 cover_address_length, u32 cover_adj_index);
160 : void ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
161 : u32 dst_address_length, u32 adj_index,
162 : u32 cover_address_length, u32 cover_adj_index);
163 :
164 : /**
165 : * @brief return the memory used by the table
166 : */
167 : uword ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m);
168 : uword ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m);
169 :
170 : /**
171 : * @brief Format/display the contents of the mtrie
172 : */
173 : format_function_t format_ip4_mtrie_16;
174 : format_function_t format_ip4_mtrie_8;
175 :
176 : /**
177 : * @brief A global pool of 8bit stride plys
178 : */
179 : extern ip4_mtrie_8_ply_t *ip4_ply_pool;
180 :
181 : /**
182 : * Is the leaf terminal (i.e. an LB index) or non-terminal (i.e. a PLY index)
183 : */
184 : always_inline u32
185 213552233 : ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n)
186 : {
187 213552233 : return n & 1;
188 : }
189 :
190 : /**
191 : * From the stored slot value extract the LB index value
192 : */
193 : always_inline u32
194 98913381 : ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n)
195 : {
196 98913381 : ASSERT (ip4_mtrie_leaf_is_terminal (n));
197 98913381 : return n >> 1;
198 : }
199 :
200 : /**
201 : * @brief Lookup step. Processes 1 byte of 4 byte ip4 address.
202 : */
203 : always_inline ip4_mtrie_leaf_t
204 31403462 : ip4_mtrie_16_lookup_step (ip4_mtrie_leaf_t current_leaf,
205 : const ip4_address_t *dst_address,
206 : u32 dst_address_byte_index)
207 : {
208 : ip4_mtrie_8_ply_t *ply;
209 :
210 31403462 : uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf);
211 :
212 31403462 : if (!current_is_terminal)
213 : {
214 31391853 : ply = ip4_ply_pool + (current_leaf >> 1);
215 31391853 : return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
216 : }
217 :
218 11590 : return current_leaf;
219 : }
220 :
221 : /**
222 : * @brief Lookup step number 1. Processes 2 bytes of 4 byte ip4 address.
223 : */
224 : always_inline ip4_mtrie_leaf_t
225 15701781 : ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m,
226 : const ip4_address_t *dst_address)
227 : {
228 : ip4_mtrie_leaf_t next_leaf;
229 :
230 15701781 : next_leaf = m->root_ply.leaves[dst_address->as_u16[0]];
231 :
232 15701781 : return next_leaf;
233 : }
234 :
235 : always_inline ip4_mtrie_leaf_t
236 : ip4_mtrie_8_lookup_step (ip4_mtrie_leaf_t current_leaf,
237 : const ip4_address_t *dst_address,
238 : u32 dst_address_byte_index)
239 : {
240 : ip4_mtrie_8_ply_t *ply;
241 :
242 : uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf);
243 :
244 : if (!current_is_terminal)
245 : {
246 : ply = ip4_ply_pool + (current_leaf >> 1);
247 : return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
248 : }
249 :
250 : return current_leaf;
251 : }
252 :
253 : always_inline ip4_mtrie_leaf_t
254 : ip4_mtrie_8_lookup_step_one (const ip4_mtrie_8_t *m,
255 : const ip4_address_t *dst_address)
256 : {
257 : ip4_mtrie_leaf_t next_leaf;
258 : ip4_mtrie_8_ply_t *ply;
259 :
260 : ply = pool_elt_at_index (ip4_ply_pool, m->root_ply);
261 : next_leaf = ply->leaves[dst_address->as_u8[0]];
262 :
263 : return next_leaf;
264 : }
265 :
266 : #endif /* included_ip_ip4_fib_h */
267 :
268 : /*
269 : * fd.io coding-style-patch-verification: ON
270 : *
271 : * Local Variables:
272 : * eval: (c-set-style "gnu")
273 : * End:
274 : */
|
