sys/contrib/dpdk_rte_lpm/rte_lpm.h

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