crypto/mlx5: add maximum segments configuration
[dpdk.git] / lib / lpm / rte_lpm.h
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
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
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 #ifdef RTE_HAS_SVE_ACLE
406 #include "rte_lpm_sve.h"
407 #else
408 #include "rte_lpm_neon.h"
409 #endif
410 #elif defined(RTE_ARCH_PPC_64)
411 #include "rte_lpm_altivec.h"
412 #else
413 #include "rte_lpm_sse.h"
414 #endif
415
416 #ifdef __cplusplus
417 }
418 #endif
419
420 #endif /* _RTE_LPM_H_ */