1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
3 * Copyright(c) 2020 Arm Limited
4 */
5
6 #ifndef _RTE_LPM_H_
7 #define _RTE_LPM_H_
8
9 /**
10 * @file
11 * RTE Longest Prefix Match (LPM)
12 */
13
14 #include <errno.h>
15 #include <sys/queue.h>
16 #include <stdint.h>
17 #include <stdlib.h>
18 #include <rte_branch_prediction.h>
19 #include <rte_byteorder.h>
20 #include <rte_config.h>
21 #include <rte_memory.h>
22 #include <rte_common.h>
23 #include <rte_vect.h>
24 #include <rte_rcu_qsbr.h>
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29
30 /** Max number of characters in LPM name. */
31 #define RTE_LPM_NAMESIZE 32
32
33 /** Maximum depth value possible for IPv4 LPM. */
34 #define RTE_LPM_MAX_DEPTH 32
35
36 /** @internal Total number of tbl24 entries. */
37 #define RTE_LPM_TBL24_NUM_ENTRIES (1 << 24)
38
39 /** @internal Number of entries in a tbl8 group. */
40 #define RTE_LPM_TBL8_GROUP_NUM_ENTRIES 256
41
42 /** @internal Max number of tbl8 groups in the tbl8. */
43 #define RTE_LPM_MAX_TBL8_NUM_GROUPS (1 << 24)
44
45 /** @internal Total number of tbl8 groups in the tbl8. */
46 #define RTE_LPM_TBL8_NUM_GROUPS 256
47
48 /** @internal Total number of tbl8 entries. */
49 #define RTE_LPM_TBL8_NUM_ENTRIES (RTE_LPM_TBL8_NUM_GROUPS * \
50 RTE_LPM_TBL8_GROUP_NUM_ENTRIES)
51
52 /** @internal Macro to enable/disable run-time checks. */
53 #if defined(RTE_LIBRTE_LPM_DEBUG)
54 #define RTE_LPM_RETURN_IF_TRUE(cond, retval) do { \
55 if (cond) return (retval); \
56 } while (0)
57 #else
58 #define RTE_LPM_RETURN_IF_TRUE(cond, retval)
59 #endif
60
61 /** @internal bitmask with valid and valid_group fields set */
62 #define RTE_LPM_VALID_EXT_ENTRY_BITMASK 0x03000000
63
64 /** Bitmask used to indicate successful lookup */
65 #define RTE_LPM_LOOKUP_SUCCESS 0x01000000
66
67 /** @internal Default RCU defer queue entries to reclaim in one go. */
68 #define RTE_LPM_RCU_DQ_RECLAIM_MAX 16
69
70 /** RCU reclamation modes */
71 enum rte_lpm_qsbr_mode {
72 /** Create defer queue for reclaim. */
73 RTE_LPM_QSBR_MODE_DQ = 0,
74 /** Use blocking mode reclaim. No defer queue created. */
75 RTE_LPM_QSBR_MODE_SYNC
76 };
77
78 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
79 /** @internal Tbl24 entry structure. */
80 __extension__
81 struct rte_lpm_tbl_entry {
82 /**
83 * Stores Next hop (tbl8 or tbl24 when valid_group is not set) or
84 * a group index pointing to a tbl8 structure (tbl24 only, when
85 * valid_group is set)
86 */
87 uint32_t next_hop :24;
88 /* Using single uint8_t to store 3 values. */
89 uint32_t valid :1; /**< Validation flag. */
90 /**
91 * For tbl24:
92 * - valid_group == 0: entry stores a next hop
93 * - valid_group == 1: entry stores a group_index pointing to a tbl8
94 * For tbl8:
95 * - valid_group indicates whether the current tbl8 is in use or not
96 */
97 uint32_t valid_group :1;
98 uint32_t depth :6; /**< Rule depth. */
99 };
100
101 #else
102
103 __extension__
104 struct rte_lpm_tbl_entry {
105 uint32_t depth :6;
106 uint32_t valid_group :1;
107 uint32_t valid :1;
108 uint32_t next_hop :24;
109
110 };
111
112 #endif
113
114 /** LPM configuration structure. */
115 struct rte_lpm_config {
116 uint32_t max_rules; /**< Max number of rules. */
117 uint32_t number_tbl8s; /**< Number of tbl8s to allocate. */
118 int flags; /**< This field is currently unused. */
119 };
120
121 /** @internal LPM structure. */
122 struct rte_lpm {
123 /* LPM Tables. */
124 struct rte_lpm_tbl_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES]
125 __rte_cache_aligned; /**< LPM tbl24 table. */
126 struct rte_lpm_tbl_entry *tbl8; /**< LPM tbl8 table. */
127 };
128
129 /** LPM RCU QSBR configuration structure. */
130 struct rte_lpm_rcu_config {
131 struct rte_rcu_qsbr *v; /* RCU QSBR variable. */
132 /* Mode of RCU QSBR. RTE_LPM_QSBR_MODE_xxx
133 * '0' for default: create defer queue for reclaim.
134 */
135 enum rte_lpm_qsbr_mode mode;
136 uint32_t dq_size; /* RCU defer queue size.
137 * default: lpm->number_tbl8s.
138 */
139 uint32_t reclaim_thd; /* Threshold to trigger auto reclaim. */
140 uint32_t reclaim_max; /* Max entries to reclaim in one go.
141 * default: RTE_LPM_RCU_DQ_RECLAIM_MAX.
142 */
143 };
144
145 /**
146 * Create an LPM object.
147 *
148 * @param name
149 * LPM object name
150 * @param socket_id
151 * NUMA socket ID for LPM table memory allocation
152 * @param config
153 * Structure containing the configuration
154 * @return
155 * Handle to LPM object on success, NULL otherwise with rte_errno set
156 * to an appropriate values. Possible rte_errno values include:
157 * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure
158 * - E_RTE_SECONDARY - function was called from a secondary process instance
159 * - EINVAL - invalid parameter passed to function
160 * - ENOSPC - the maximum number of memzones has already been allocated
161 * - EEXIST - a memzone with the same name already exists
162 * - ENOMEM - no appropriate memory area found in which to create memzone
163 */
164 struct rte_lpm *
165 rte_lpm_create(const char *name, int socket_id,
166 const struct rte_lpm_config *config);
167
168 /**
169 * Find an existing LPM object and return a pointer to it.
170 *
171 * @param name
172 * Name of the lpm object as passed to rte_lpm_create()
173 * @return
174 * Pointer to lpm object or NULL if object not found with rte_errno
175 * set appropriately. Possible rte_errno values include:
176 * - ENOENT - required entry not available to return.
177 */
178 struct rte_lpm *
179 rte_lpm_find_existing(const char *name);
180
181 /**
182 * Free an LPM object.
183 *
184 * @param lpm
185 * LPM object handle
186 * @return
187 * None
188 */
189 void
190 rte_lpm_free(struct rte_lpm *lpm);
191
192 /**
193 * @warning
194 * @b EXPERIMENTAL: this API may change without prior notice
195 *
196 * Associate RCU QSBR variable with an LPM object.
197 *
198 * @param lpm
199 * the lpm object to add RCU QSBR
200 * @param cfg
201 * RCU QSBR configuration
202 * @return
203 * On success - 0
204 * On error - 1 with error code set in rte_errno.
205 * Possible rte_errno codes are:
206 * - EINVAL - invalid pointer
207 * - EEXIST - already added QSBR
208 * - ENOMEM - memory allocation failure
209 */
210 __rte_experimental
211 int rte_lpm_rcu_qsbr_add(struct rte_lpm *lpm, struct rte_lpm_rcu_config *cfg);
212
213 /**
214 * Add a rule to the LPM table.
215 *
216 * @param lpm
217 * LPM object handle
218 * @param ip
219 * IP of the rule to be added to the LPM table
220 * @param depth
221 * Depth of the rule to be added to the LPM table
222 * @param next_hop
223 * Next hop of the rule to be added to the LPM table
224 * @return
225 * 0 on success, negative value otherwise
226 */
227 int
228 rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint32_t next_hop);
229
230 /**
231 * Check if a rule is present in the LPM table,
232 * and provide its next hop if it is.
233 *
234 * @param lpm
235 * LPM object handle
236 * @param ip
237 * IP of the rule to be searched
238 * @param depth
239 * Depth of the rule to searched
240 * @param next_hop
241 * Next hop of the rule (valid only if it is found)
242 * @return
243 * 1 if the rule exists, 0 if it does not, a negative value on failure
244 */
245 int
246 rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
247 uint32_t *next_hop);
248
249 /**
250 * Delete a rule from the LPM table.
251 *
252 * @param lpm
253 * LPM object handle
254 * @param ip
255 * IP of the rule to be deleted from the LPM table
256 * @param depth
257 * Depth of the rule to be deleted from the LPM table
258 * @return
259 * 0 on success, negative value otherwise
260 */
261 int
262 rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
263
264 /**
265 * Delete all rules from the LPM table.
266 *
267 * @param lpm
268 * LPM object handle
269 */
270 void
271 rte_lpm_delete_all(struct rte_lpm *lpm);
272
273 /**
274 * Lookup an IP into the LPM table.
275 *
276 * @param lpm
277 * LPM object handle
278 * @param ip
279 * IP to be looked up in the LPM table
280 * @param next_hop
281 * Next hop of the most specific rule found for IP (valid on lookup hit only)
282 * @return
283 * -EINVAL for incorrect arguments, -ENOENT on lookup miss, 0 on lookup hit
284 */
285 static inline int
rte_lpm_lookup(struct rte_lpm * lpm,uint32_t ip,uint32_t * next_hop)286 rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint32_t *next_hop)
287 {
288 unsigned tbl24_index = (ip >> 8);
289 uint32_t tbl_entry;
290 const uint32_t *ptbl;
291
292 /* DEBUG: Check user input arguments. */
293 RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL);
294
295 /* Copy tbl24 entry */
296 ptbl = (const uint32_t *)(&lpm->tbl24[tbl24_index]);
297 tbl_entry = *ptbl;
298
299 /* Memory ordering is not required in lookup. Because dataflow
300 * dependency exists, compiler or HW won't be able to re-order
301 * the operations.
302 */
303 /* Copy tbl8 entry (only if needed) */
304 if (unlikely((tbl_entry & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
305 RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
306
307 unsigned tbl8_index = (uint8_t)ip +
308 (((uint32_t)tbl_entry & 0x00FFFFFF) *
309 RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
310
311 ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
312 tbl_entry = *ptbl;
313 }
314
315 *next_hop = ((uint32_t)tbl_entry & 0x00FFFFFF);
316 return (tbl_entry & RTE_LPM_LOOKUP_SUCCESS) ? 0 : -ENOENT;
317 }
318
319 /**
320 * Lookup multiple IP addresses in an LPM table. This may be implemented as a
321 * macro, so the address of the function should not be used.
322 *
323 * @param lpm
324 * LPM object handle
325 * @param ips
326 * Array of IPs to be looked up in the LPM table
327 * @param next_hops
328 * Next hop of the most specific rule found for IP (valid on lookup hit only).
329 * This is an array of two byte values. The most significant byte in each
330 * value says whether the lookup was successful (bitmask
331 * RTE_LPM_LOOKUP_SUCCESS is set). The least significant byte is the
332 * actual next hop.
333 * @param n
334 * Number of elements in ips (and next_hops) array to lookup. This should be a
335 * compile time constant, and divisible by 8 for best performance.
336 * @return
337 * -EINVAL for incorrect arguments, otherwise 0
338 */
339 #define rte_lpm_lookup_bulk(lpm, ips, next_hops, n) \
340 rte_lpm_lookup_bulk_func(lpm, ips, next_hops, n)
341
342 static inline int
rte_lpm_lookup_bulk_func(const struct rte_lpm * lpm,const uint32_t * ips,uint32_t * next_hops,const unsigned n)343 rte_lpm_lookup_bulk_func(const struct rte_lpm *lpm, const uint32_t *ips,
344 uint32_t *next_hops, const unsigned n)
345 {
346 unsigned i;
347 unsigned tbl24_indexes[n];
348 const uint32_t *ptbl;
349
350 /* DEBUG: Check user input arguments. */
351 RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (ips == NULL) ||
352 (next_hops == NULL)), -EINVAL);
353
354 for (i = 0; i < n; i++) {
355 tbl24_indexes[i] = ips[i] >> 8;
356 }
357
358 for (i = 0; i < n; i++) {
359 /* Simply copy tbl24 entry to output */
360 ptbl = (const uint32_t *)&lpm->tbl24[tbl24_indexes[i]];
361 next_hops[i] = *ptbl;
362
363 /* Overwrite output with tbl8 entry if needed */
364 if (unlikely((next_hops[i] & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
365 RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
366
367 unsigned tbl8_index = (uint8_t)ips[i] +
368 (((uint32_t)next_hops[i] & 0x00FFFFFF) *
369 RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
370
371 ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
372 next_hops[i] = *ptbl;
373 }
374 }
375 return 0;
376 }
377
378 /* Mask four results. */
379 #define RTE_LPM_MASKX4_RES UINT64_C(0x00ffffff00ffffff)
380
381 /**
382 * Lookup four IP addresses in an LPM table.
383 *
384 * @param lpm
385 * LPM object handle
386 * @param ip
387 * Four IPs to be looked up in the LPM table
388 * @param hop
389 * Next hop of the most specific rule found for IP (valid on lookup hit only).
390 * This is an 4 elements array of two byte values.
391 * If the lookup was successful for the given IP, then least significant byte
392 * of the corresponding element is the actual next hop and the most
393 * significant byte is zero.
394 * If the lookup for the given IP failed, then corresponding element would
395 * contain default value, see description of then next parameter.
396 * @param defv
397 * Default value to populate into corresponding element of hop[] array,
398 * if lookup would fail.
399 */
400 static inline void
401 rte_lpm_lookupx4(const struct rte_lpm *lpm, xmm_t ip, uint32_t hop[4],
402 uint32_t defv);
403
404 #if defined(RTE_ARCH_ARM)
405 #include "rte_lpm_neon.h"
406 #elif defined(RTE_ARCH_PPC_64)
407 #include "rte_lpm_altivec.h"
408 #else
409 #include "rte_lpm_sse.h"
410 #endif
411
412 #ifdef __cplusplus
413 }
414 #endif
415
416 #endif /* _RTE_LPM_H_ */
417