lib/librte_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 #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_ */