332e34a75ca16896962d717e56b57eb6967100d2
[vpp.git] / src / vnet / ip / ip4_mtrie.h
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   union
69   {
70     ip4_mtrie_leaf_t leaves[PLY_16_SIZE];
71
72 #ifdef CLIB_HAVE_VEC128
73     u32x4 leaves_as_u32x4[PLY_16_SIZE / 4];
74 #endif
75   };
76
77   /**
78    * Prefix length for terminal leaves.
79    */
80   u8 dst_address_bits_of_leaves[PLY_16_SIZE];
81 } ip4_mtrie_16_ply_t;
82
83 /**
84  * @brief One ply of the 4 ply mtrie fib.
85  */
86 typedef struct ip4_mtrie_8_ply_t_
87 {
88   /**
89    * The leaves/slots/buckets to be filed with leafs
90    */
91   union
92   {
93     ip4_mtrie_leaf_t leaves[256];
94
95 #ifdef CLIB_HAVE_VEC128
96     u32x4 leaves_as_u32x4[256 / 4];
97 #endif
98   };
99
100   /**
101    * Prefix length for leaves/ply.
102    */
103   u8 dst_address_bits_of_leaves[256];
104
105   /**
106    * Number of non-empty leafs (whether terminal or not).
107    */
108   i32 n_non_empty_leafs;
109
110   /**
111    * The length of the ply's covering 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.
114    */
115   i32 dst_address_bits_base;
116
117   /* Pad to cache line boundary. */
118   u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
119 } ip4_mtrie_8_ply_t;
120
121 STATIC_ASSERT (0 == sizeof (ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
122                "IP4 Mtrie ply cache line");
123
124 /**
125  * @brief The mutiway-TRIE.
126  * There is no data associated with the mtrie apart from the top PLY
127  */
128 typedef struct
129 {
130   /**
131    * Embed the PLY with the mtrie struct. This means that the Data-plane
132    * 'get me the mtrie' returns the first ply, and not an indirect 'pointer'
133    * to it. therefore no cacheline misses in the data-path.
134    */
135   ip4_mtrie_16_ply_t root_ply;
136 } ip4_mtrie_16_t;
137
138 /**
139  * @brief Initialise an mtrie
140  */
141 void ip4_mtrie_16_init (ip4_mtrie_16_t *m);
142
143 /**
144  * @brief Free an mtrie, It must be emty when free'd
145  */
146 void ip4_mtrie_16_free (ip4_mtrie_16_t *m);
147
148 /**
149  * @brief Add a route/entry to the mtrie
150  */
151 void ip4_mtrie_16_route_add (ip4_mtrie_16_t *m,
152                              const ip4_address_t *dst_address,
153                              u32 dst_address_length, u32 adj_index);
154 /**
155  * @brief remove a route/entry to the mtrie
156  */
157 void ip4_mtrie_16_route_del (ip4_mtrie_16_t *m,
158                              const ip4_address_t *dst_address,
159                              u32 dst_address_length, u32 adj_index,
160                              u32 cover_address_length, u32 cover_adj_index);
161
162 /**
163  * @brief return the memory used by the table
164  */
165 uword ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m);
166
167 /**
168  * @brief Format/display the contents of the mtrie
169  */
170 format_function_t format_ip4_mtrie_16;
171
172 /**
173  * @brief A global pool of 8bit stride plys
174  */
175 extern ip4_mtrie_8_ply_t *ip4_ply_pool;
176
177 /**
178  * Is the leaf terminal (i.e. an LB index) or non-terminal (i.e. a PLY index)
179  */
180 always_inline u32
181 ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n)
182 {
183   return n & 1;
184 }
185
186 /**
187  * From the stored slot value extract the LB index value
188  */
189 always_inline u32
190 ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n)
191 {
192   ASSERT (ip4_mtrie_leaf_is_terminal (n));
193   return n >> 1;
194 }
195
196 /**
197  * @brief Lookup step.  Processes 1 byte of 4 byte ip4 address.
198  */
199 always_inline ip4_mtrie_leaf_t
200 ip4_mtrie_16_lookup_step (const ip4_mtrie_16_t *m,
201                           ip4_mtrie_leaf_t current_leaf,
202                           const ip4_address_t *dst_address,
203                           u32 dst_address_byte_index)
204 {
205   ip4_mtrie_8_ply_t *ply;
206
207   uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf);
208
209   if (!current_is_terminal)
210     {
211       ply = ip4_ply_pool + (current_leaf >> 1);
212       return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
213     }
214
215   return current_leaf;
216 }
217
218 /**
219  * @brief Lookup step number 1.  Processes 2 bytes of 4 byte ip4 address.
220  */
221 always_inline ip4_mtrie_leaf_t
222 ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m,
223                               const ip4_address_t *dst_address)
224 {
225   ip4_mtrie_leaf_t next_leaf;
226
227   next_leaf = m->root_ply.leaves[dst_address->as_u16[0]];
228
229   return next_leaf;
230 }
231
232 #endif /* included_ip_ip4_fib_h */
233
234 /*
235  * fd.io coding-style-patch-verification: ON
236  *
237  * Local Variables:
238  * eval: (c-set-style "gnu")
239  * End:
240  */