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 #elif defined(RTE_ARCH_X86) 409 #include "rte_lpm_sse.h" 410 #else 411 #include "rte_lpm_scalar.h" 412 #endif 413 414 #ifdef __cplusplus 415 } 416 #endif 417 418 #endif /* _RTE_LPM_H_ */ 419