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