FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
ip4_mtrie.h
Go to the documentation of this file.
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). */
53 
54 #define IP4_FIB_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)
64 {
65  /**
66  * The leaves/slots/buckets to be filed with leafs
67  */
68  union
69  {
70  ip4_fib_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  */
82 
83 /**
84  * @brief One ply of the 4 ply mtrie fib.
85  */
86 typedef struct ip4_fib_mtrie_8_ply_t_
87 {
88  /**
89  * The leaves/slots/buckets to be filed with leafs
90  */
91  union
92  {
93  ip4_fib_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  */
104 
105  /**
106  * Number of non-empty leafs (whether terminal or not).
107  */
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  */
116 
117  /* Pad to cache line boundary. */
118  u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
119 }
121 
122 STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
123  "IP4 Mtrie ply cache line");
124 
125 /**
126  * @brief The mutiway-TRIE.
127  * There is no data associated with the mtrie apart from the top PLY
128  */
129 typedef struct
130 {
131  /**
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 cacheline misses in the data-path.
135  */
138 
139 /**
140  * @brief Initialise an mtrie
141  */
143 
144 /**
145  * @brief Free an mtrie, It must be emty when free'd
146  */
148 
149 /**
150  * @brief Add a route/entry to the mtrie
151  */
153  const ip4_address_t * dst_address,
154  u32 dst_address_length, u32 adj_index);
155 /**
156  * @brief remove a route/entry to the mtrie
157  */
159  const ip4_address_t * dst_address,
160  u32 dst_address_length,
161  u32 adj_index,
162  u32 cover_address_length, u32 cover_adj_index);
163 
164 /**
165  * @brief return the memory used by the table
166  */
168 
169 /**
170  * @brief Format/display the contents of the mtrie
171  */
173 
174 /**
175  * @brief A global pool of 8bit stride plys
176  */
177 extern ip4_fib_mtrie_8_ply_t *ip4_ply_pool;
178 
179 /**
180  * Is the leaf terminal (i.e. an LB index) or non-terminal (i.e. a PLY index)
181  */
183 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
184 {
185  return n & 1;
186 }
187 
188 /**
189  * From the stored slot value extract the LB index value
190  */
192 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
193 {
195  return n >> 1;
196 }
197 
198 /**
199  * @brief Lookup step. Processes 1 byte of 4 byte ip4 address.
200  */
201 always_inline ip4_fib_mtrie_leaf_t
203  ip4_fib_mtrie_leaf_t current_leaf,
204  const ip4_address_t * dst_address,
205  u32 dst_address_byte_index)
206 {
207  ip4_fib_mtrie_8_ply_t *ply;
208 
209  uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
210 
211  if (!current_is_terminal)
212  {
213  ply = ip4_ply_pool + (current_leaf >> 1);
214  return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
215  }
216 
217  return current_leaf;
218 }
219 
220 /**
221  * @brief Lookup step number 1. Processes 2 bytes of 4 byte ip4 address.
222  */
223 always_inline ip4_fib_mtrie_leaf_t
225  const ip4_address_t * dst_address)
226 {
227  ip4_fib_mtrie_leaf_t next_leaf;
228 
229  next_leaf = m->root_ply.leaves[dst_address->as_u16[0]];
230 
231  return next_leaf;
232 }
233 
234 #endif /* included_ip_ip4_fib_h */
235 
236 /*
237  * fd.io coding-style-patch-verification: ON
238  *
239  * Local Variables:
240  * eval: (c-set-style "gnu")
241  * End:
242  */
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
The mutiway-TRIE.
Definition: ip4_mtrie.h:129
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step(const ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
Lookup step.
Definition: ip4_mtrie.h:202
void ip4_mtrie_free(ip4_fib_mtrie_t *m)
Free an mtrie, It must be emty when free&#39;d.
Definition: ip4_mtrie.c:199
Definitions for all things IP (v4|v6) unicast and multicast lookup related.
ip4_fib_mtrie_leaf_t leaves[256]
Definition: ip4_mtrie.h:93
#define PLY_16_SIZE
the 16 way stride that is the top PLY of the mtrie We do not maintain the count of &#39;real&#39; leaves in t...
Definition: ip4_mtrie.h:62
unsigned char u8
Definition: types.h:56
u8 dst_address_bits_of_leaves[PLY_16_SIZE]
Prefix length for terminal leaves.
Definition: ip4_mtrie.h:80
One ply of the 4 ply mtrie fib.
Definition: ip4_mtrie.h:86
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
void ip4_fib_mtrie_route_del(ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index)
remove a route/entry to the mtrie
Definition: ip4_mtrie.c:641
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
uword ip4_fib_mtrie_memory_usage(ip4_fib_mtrie_t *m)
return the memory used by the table
Definition: ip4_mtrie.c:681
ip4_fib_mtrie_leaf_t leaves[PLY_16_SIZE]
Definition: ip4_mtrie.h:70
unsigned int u32
Definition: types.h:88
static u32 ip4_fib_mtrie_leaf_get_adj_index(ip4_fib_mtrie_leaf_t n)
From the stored slot value extract the LB index value.
Definition: ip4_mtrie.h:192
struct ip4_fib_mtrie_8_ply_t_ ip4_fib_mtrie_8_ply_t
One ply of the 4 ply mtrie fib.
u16 as_u16[2]
Definition: ip4_packet.h:55
#define always_inline
Definition: ipsec.h:28
ip4_fib_mtrie_8_ply_t * ip4_ply_pool
A global pool of 8bit stride plys.
Definition: ip4_mtrie.c:48
ip4_fib_mtrie_16_ply_t root_ply
Embed the PLY with the mtrie struct.
Definition: ip4_mtrie.h:136
void ip4_fib_mtrie_route_add(ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index)
Add a route/entry to the mtrie.
Definition: ip4_mtrie.c:624
signed int i32
Definition: types.h:77
#define ASSERT(truth)
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one(const ip4_fib_mtrie_t *m, const ip4_address_t *dst_address)
Lookup step number 1.
Definition: ip4_mtrie.h:224
i32 n_non_empty_leafs
Number of non-empty leafs (whether terminal or not).
Definition: ip4_mtrie.h:108
i32 dst_address_bits_base
The length of the ply&#39;s covering prefix.
Definition: ip4_mtrie.h:115
format_function_t format_ip4_fib_mtrie
Format/display the contents of the mtrie.
Definition: ip4_mtrie.h:172
void ip4_mtrie_init(ip4_fib_mtrie_t *m)
Initialise an mtrie.
Definition: ip4_mtrie.c:215
u64 uword
Definition: types.h:112
unsigned long long u32x4
Definition: ixge.c:28
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
struct ip4_fib_mtrie_16_ply_t_ ip4_fib_mtrie_16_ply_t
static u32 ip4_fib_mtrie_leaf_is_terminal(ip4_fib_mtrie_leaf_t n)
Is the leaf terminal (i.e.
Definition: ip4_mtrie.h:183
STATIC_ASSERT(0==sizeof(ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, "IP4 Mtrie ply cache line")