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