Hi. Doing some tests with rte_lpm (adding/deleting bgp full table rules) I noticed that rule subsystem is very slow even considering that probably it was never designed for using in a data forwarding plane. So I want to propose some changes to it.
I reimplemented "rule" part ot the lib using rte_hash, and perfomance of adding/deleted routes have increased dramatically. If increasing speed of adding deleting routes makes sence for anybody else I would like to discuss my patch. The patch also include changes that make next_hop 64 bit, so please just ignore them. The rule changes are in the following functions only: rte_lpm2_create rule_find rule_add rule_delete find_previous_rule delete_depth_small delete_depth_big rte_lpm2_add rte_lpm2_delete rte_lpm2_is_rule_present rte_lpm2_delete_all P.S. the patch was made for 2.2.0 version. P.P.S. Would it be more convinient to include full source file instead of patch? Alex Kiselev. Patch --- ./rte_lpm.c 2016-04-19 13:58:44.670649240 +0300 +++ ./rte_lpm2.c 2016-04-19 13:58:44.686649240 +0300 @@ -45,6 +45,9 @@ #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */ #include <rte_malloc.h> #include <rte_memzone.h> +#include <rte_hash.h> +#include <rte_hash_crc.h> +#include <rte_mempool.h> #include <rte_eal.h> #include <rte_eal_memconfig.h> #include <rte_per_lcore.h> @@ -53,14 +56,14 @@ #include <rte_rwlock.h> #include <rte_spinlock.h> -#include "rte_lpm.h" +#include "rte_lpm2.h" -TAILQ_HEAD(rte_lpm_list, rte_tailq_entry); +TAILQ_HEAD(RTE_LPM2_list, rte_tailq_entry); -static struct rte_tailq_elem rte_lpm_tailq = { - .name = "RTE_LPM", +static struct rte_tailq_elem RTE_LPM2_tailq = { + .name = "RTE_LPM2", }; -EAL_REGISTER_TAILQ(rte_lpm_tailq) +EAL_REGISTER_TAILQ(RTE_LPM2_tailq) #define MAX_DEPTH_TBL24 24 @@ -70,10 +73,10 @@ }; /* Macro to enable/disable run-time checks. */ -#if defined(RTE_LIBRTE_LPM_DEBUG) +#if defined(RTE_LIBRTE_LPM2_DEBUG) #include <rte_debug.h> #define VERIFY_DEPTH(depth) do { \ - if ((depth == 0) || (depth > RTE_LPM_MAX_DEPTH)) \ + if ((depth == 0) || (depth > RTE_LPM2_MAX_DEPTH)) \ rte_panic("LPM: Invalid depth (%u) at line %d", \ (unsigned)(depth), __LINE__); \ } while (0) @@ -113,25 +116,25 @@ return 1 << (MAX_DEPTH_TBL24 - depth); /* Else if depth is greater than 24 */ - return (1 << (RTE_LPM_MAX_DEPTH - depth)); + return (1 << (RTE_LPM2_MAX_DEPTH - depth)); } /* * Find an existing lpm table and return a pointer to it. */ -struct rte_lpm * -rte_lpm_find_existing(const char *name) +struct rte_lpm2 * +rte_lpm2_find_existing(const char *name) { - struct rte_lpm *l = NULL; + struct rte_lpm2 *l = NULL; struct rte_tailq_entry *te; - struct rte_lpm_list *lpm_list; + struct RTE_LPM2_list *lpm_list; - lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list); + lpm_list = RTE_TAILQ_CAST(RTE_LPM2_tailq.head, RTE_LPM2_list); rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); TAILQ_FOREACH(te, lpm_list, next) { - l = (struct rte_lpm *) te->data; - if (strncmp(name, l->name, RTE_LPM_NAMESIZE) == 0) + l = (struct rte_lpm2 *) te->data; + if (strncmp(name, l->name, RTE_LPM2_NAMESIZE) == 0) break; } rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); @@ -145,22 +148,148 @@ } /* + * Finds a rule in rule table. + * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. + */ +static inline struct RTE_LPM2_rule* +rule_find(struct rte_lpm2 *lpm, uint32_t ip_masked, uint8_t depth) +{ + VERIFY_DEPTH(depth); + + lpm_rule_key_t rule_key; + rule_key.net = ip_masked; + rule_key.mask = (uint32_t) depth; + + struct RTE_LPM2_rule* rule; + + int ret = rte_hash_lookup_data(lpm->rules_hash_tbl, (void*) &rule_key, + (void**) &rule); + + if (ret >= 0) { + return rule; + } + + /* rule is not found */ + return NULL; +} + +/* + * Finds a rule in rule table. + * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. + */ +static inline struct RTE_LPM2_rule* +rule_find_by_key(struct rte_lpm2 *lpm, lpm_rule_key_t* rule_key) +{ + struct RTE_LPM2_rule* rule; + + int ret = rte_hash_lookup_data(lpm->rules_hash_tbl, (void*) rule_key, + (void**) &rule); + + if (ret >= 0) { + return rule; + } + + /* rule is not found */ + return NULL; +} + +/* + * Finds a rule in rule table. + * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. + */ +static inline struct RTE_LPM2_rule* +rule_find_by_key_with_hash(struct rte_lpm2 *lpm, lpm_rule_key_t* rule_key, + hash_sig_t sig) +{ + struct RTE_LPM2_rule* rule; + + int ret = rte_hash_lookup_with_hash_data(lpm->rules_hash_tbl, (void*) rule_key, + sig, (void**) &rule); + + if (ret >= 0) { + return rule; + } + + /* rule is not found */ + return NULL; +} + +/* + * hash function for rules hash table + */ +static inline uint32_t lpm_prefix_hash_crc(const void *data, + __rte_unused uint32_t data_len, uint32_t init_val) +{ + // printf("lpm_prefix_hash_crc init: %ul\n", init_val); + + init_val = rte_hash_crc_8byte(*((uint64_t*) data), init_val); + + // printf("lpm_prefix_hash_crc result: %ul\n", init_val); + + return init_val; +} + +/* * Allocates memory for LPM object */ -struct rte_lpm * -rte_lpm_create(const char *name, int socket_id, int max_rules, +struct rte_lpm2 * +rte_lpm2_create(const char *name, int socket_id, int max_rules, __rte_unused int flags) { - char mem_name[RTE_LPM_NAMESIZE]; - struct rte_lpm *lpm = NULL; + char mem_name[RTE_LPM2_NAMESIZE]; + struct rte_lpm2 *lpm = NULL; struct rte_tailq_entry *te; uint32_t mem_size; - struct rte_lpm_list *lpm_list; + struct RTE_LPM2_list *lpm_list; + + /* create rules hash table */ + char rules_hash_tbl_name[RTE_RULES_HASH_TBL_NAMESIZE]; + + /* create hash */ + snprintf(rules_hash_tbl_name, sizeof(rules_hash_tbl_name), "LMP_RHTBL_%s", + name); + + struct rte_hash_parameters rules_hash_tbl_params = { + .entries = max_rules, + .key_len = sizeof(lpm_rule_key_t), + .hash_func = lpm_prefix_hash_crc, + .hash_func_init_val = 0, + .name = rules_hash_tbl_name, + .reserved = 0, + .socket_id = socket_id, + .extra_flag = 0, + }; + + lpm->rules_hash_tbl = rte_hash_create(&rules_hash_tbl_params); + if (unlikely(lpm->rules_hash_tbl == NULL)) { + RTE_LOG(ERR, LPM, "rules hash table memory allocation failed: %d\n", + rte_errno); + return NULL; + } - lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list); + /* create mempool for lpm rules */ + snprintf(rules_hash_tbl_name, sizeof(rules_hash_tbl_name), "LPM_RMP_%s", + name); + lpm->rules_mempool = rte_mempool_create( + rules_hash_tbl_name, + max_rules, + sizeof(struct RTE_LPM2_rule), + 32, + 0, + NULL, NULL, NULL, NULL, + socket_id, + MEMPOOL_F_SP_PUT | MEMPOOL_F_SC_GET + ); - RTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl24_entry) != 2); - RTE_BUILD_BUG_ON(sizeof(struct rte_lpm_tbl8_entry) != 2); + if (unlikely(lpm->rules_mempool == NULL)) { + RTE_LOG(ERR, LPM, "rules mempool allocation failed: %d\n", rte_errno); + return NULL; + } + + lpm_list = RTE_TAILQ_CAST(RTE_LPM2_tailq.head, RTE_LPM2_list); + + RTE_BUILD_BUG_ON(sizeof(struct RTE_LPM2_tbl24_entry) != 10); + RTE_BUILD_BUG_ON(sizeof(struct RTE_LPM2_tbl8_entry) != 10); /* Check user arguments. */ if ((name == NULL) || (socket_id < -1) || (max_rules == 0)){ @@ -170,15 +299,12 @@ snprintf(mem_name, sizeof(mem_name), "LPM_%s", name); - /* Determine the amount of memory to allocate. */ - mem_size = sizeof(*lpm) + (sizeof(lpm->rules_tbl[0]) * max_rules); - rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); /* guarantee there's no existing */ TAILQ_FOREACH(te, lpm_list, next) { - lpm = (struct rte_lpm *) te->data; - if (strncmp(name, lpm->name, RTE_LPM_NAMESIZE) == 0) + lpm = (struct rte_lpm2 *) te->data; + if (strncmp(name, lpm->name, RTE_LPM2_NAMESIZE) == 0) break; } if (te != NULL) @@ -192,7 +318,7 @@ } /* Allocate memory to store the LPM data structures. */ - lpm = (struct rte_lpm *)rte_zmalloc_socket(mem_name, mem_size, + lpm = (struct rte_lpm2 *)rte_zmalloc_socket(mem_name, sizeof(struct rte_lpm2), RTE_CACHE_LINE_SIZE, socket_id); if (lpm == NULL) { RTE_LOG(ERR, LPM, "LPM memory allocation failed\n"); @@ -210,7 +336,6 @@ exit: rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - return lpm; } @@ -218,16 +343,16 @@ * Deallocates memory for given LPM table. */ void -rte_lpm_free(struct rte_lpm *lpm) +rte_lpm2_free(struct rte_lpm2 *lpm) { - struct rte_lpm_list *lpm_list; + struct RTE_LPM2_list *lpm_list; struct rte_tailq_entry *te; /* Check user arguments. */ if (lpm == NULL) return; - lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list); + lpm_list = RTE_TAILQ_CAST(RTE_LPM2_tailq.head, RTE_LPM2_list); rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); @@ -259,143 +384,101 @@ * are stored in the rule table from 0 - 31. * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. */ -static inline int32_t -rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, - uint8_t next_hop) +static inline struct RTE_LPM2_rule* +rule_add(struct rte_lpm2 *lpm, uint32_t ip_masked, uint8_t depth, + uint64_t next_hop) { - uint32_t rule_gindex, rule_index, last_rule; - int i; - VERIFY_DEPTH(depth); - /* Scan through rule group to see if rule already exists. */ - if (lpm->rule_info[depth - 1].used_rules > 0) { - - /* rule_gindex stands for rule group index. */ - rule_gindex = lpm->rule_info[depth - 1].first_rule; - /* Initialise rule_index to point to start of rule group. */ - rule_index = rule_gindex; - /* Last rule = Last used rule in this rule group. */ - last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules; - - for (; rule_index < last_rule; rule_index++) { - - /* If rule already exists update its next_hop and return. */ - if (lpm->rules_tbl[rule_index].ip == ip_masked) { - lpm->rules_tbl[rule_index].next_hop = next_hop; - - return rule_index; - } - } - - if (rule_index == lpm->max_rules) - return -ENOSPC; - } else { - /* Calculate the position in which the rule will be stored. */ - rule_index = 0; - - for (i = depth - 1; i > 0; i--) { - if (lpm->rule_info[i - 1].used_rules > 0) { - rule_index = lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules; - break; - } - } - if (rule_index == lpm->max_rules) - return -ENOSPC; - - lpm->rule_info[depth - 1].first_rule = rule_index; + lpm_rule_key_t rule_key; + rule_key.net = ip_masked; + rule_key.mask = depth; + + /* If rule already exists update its next_hop and return. */ + struct RTE_LPM2_rule* rule = rule_find_by_key(lpm, &rule_key); + if (rule != NULL) { + rule->next_hop = next_hop; + return rule; } - /* Make room for the new rule in the array. */ - for (i = RTE_LPM_MAX_DEPTH; i > depth; i--) { - if (lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules == lpm->max_rules) - return -ENOSPC; - - if (lpm->rule_info[i - 1].used_rules > 0) { - lpm->rules_tbl[lpm->rule_info[i - 1].first_rule + lpm->rule_info[i - 1].used_rules] - = lpm->rules_tbl[lpm->rule_info[i - 1].first_rule]; - lpm->rule_info[i - 1].first_rule++; - } + /* get new rule */ + int ret = rte_mempool_sc_get(lpm->rules_mempool, (void**) &rule); + if (unlikely(ret != 0)) { + RTE_LOG(ERR, LPM, "rule_add() failed to get new rule %d\n", ret); + return NULL; } - /* Add the new rule. */ - lpm->rules_tbl[rule_index].ip = ip_masked; - lpm->rules_tbl[rule_index].next_hop = next_hop; - - /* Increment the used rules counter for this rule group. */ - lpm->rule_info[depth - 1].used_rules++; + /* init a rule */ + rule->ip = ip_masked; + rule->next_hop = next_hop; + + /* add a rule to hash table */ + ret = rte_hash_add_key_data(lpm->rules_hash_tbl, (void*) &rule_key, + (void*) rule); + if (unlikely(ret != 0)) { + RTE_LOG(ERR, LPM, "rule_add() failed to add rule to hashtable %d\n", ret); + return NULL; + } - return rule_index; + return rule; } /* * Delete a rule from the rule table. * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. */ -static inline void -rule_delete(struct rte_lpm *lpm, int32_t rule_index, uint8_t depth) +static inline int32_t +rule_delete(struct rte_lpm2 *lpm, uint32_t ip_masked, uint8_t depth) { - int i; - VERIFY_DEPTH(depth); - lpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->rule_info[depth - 1].first_rule - + lpm->rule_info[depth - 1].used_rules - 1]; + lpm_rule_key_t rule_key; + rule_key.net = ip_masked; + rule_key.mask = depth; - for (i = depth; i < RTE_LPM_MAX_DEPTH; i++) { - if (lpm->rule_info[i].used_rules > 0) { - lpm->rules_tbl[lpm->rule_info[i].first_rule - 1] = - lpm->rules_tbl[lpm->rule_info[i].first_rule + lpm->rule_info[i].used_rules - 1]; - lpm->rule_info[i].first_rule--; - } - } - - lpm->rule_info[depth - 1].used_rules--; + return rte_hash_del_key(lpm->rules_hash_tbl, (void*) &rule_key); } /* - * Finds a rule in rule table. + * Delete a rule from the rule table. * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. */ static inline int32_t -rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth) +rule_delete_by_key(struct rte_lpm2 *lpm, lpm_rule_key_t* rule_key) { - uint32_t rule_gindex, last_rule, rule_index; - - VERIFY_DEPTH(depth); - - rule_gindex = lpm->rule_info[depth - 1].first_rule; - last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules; - - /* Scan used rules at given depth to find rule. */ - for (rule_index = rule_gindex; rule_index < last_rule; rule_index++) { - /* If rule is found return the rule index. */ - if (lpm->rules_tbl[rule_index].ip == ip_masked) - return rule_index; - } + return rte_hash_del_key(lpm->rules_hash_tbl, (void*) rule_key); +} - /* If rule is not found return -EINVAL. */ - return -EINVAL; +/* + * Delete a rule from the rule table. + * NOTE: Valid range for depth parameter is 1 .. 32 inclusive. + */ +static inline int32_t +rule_delete_by_key_with_hash(struct rte_lpm2 *lpm, lpm_rule_key_t* rule_key, + hash_sig_t sig) +{ + return rte_hash_del_key_with_hash(lpm->rules_hash_tbl, (void*) rule_key, sig); } + /* * Find, clean and allocate a tbl8. */ static inline int32_t -tbl8_alloc(struct rte_lpm_tbl8_entry *tbl8) +tbl8_alloc(struct RTE_LPM2_tbl8_entry *tbl8) { uint32_t tbl8_gindex; /* tbl8 group index. */ - struct rte_lpm_tbl8_entry *tbl8_entry; + struct RTE_LPM2_tbl8_entry *tbl8_entry; /* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */ - for (tbl8_gindex = 0; tbl8_gindex < RTE_LPM_TBL8_NUM_GROUPS; + for (tbl8_gindex = 0; tbl8_gindex < RTE_LPM2_TBL8_NUM_GROUPS; tbl8_gindex++) { tbl8_entry = &tbl8[tbl8_gindex * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES]; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES]; /* If a free tbl8 group is found clean it and set as VALID. */ if (!tbl8_entry->valid_group) { memset(&tbl8_entry[0], 0, - RTE_LPM_TBL8_GROUP_NUM_ENTRIES * + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES * sizeof(tbl8_entry[0])); tbl8_entry->valid_group = VALID; @@ -410,15 +493,15 @@ } static inline void -tbl8_free(struct rte_lpm_tbl8_entry *tbl8, uint32_t tbl8_group_start) +tbl8_free(struct RTE_LPM2_tbl8_entry *tbl8, uint32_t tbl8_group_start) { /* Set tbl8 group invalid*/ tbl8[tbl8_group_start].valid_group = INVALID; } static inline int32_t -add_depth_small(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, - uint8_t next_hop) +add_depth_small(struct rte_lpm2 *lpm, uint32_t ip, uint8_t depth, + uint64_t next_hop) { uint32_t tbl24_index, tbl24_range, tbl8_index, tbl8_group_end, i, j; @@ -434,7 +517,7 @@ if (!lpm->tbl24[i].valid || (lpm->tbl24[i].ext_entry == 0 && lpm->tbl24[i].depth <= depth)) { - struct rte_lpm_tbl24_entry new_tbl24_entry = { + struct RTE_LPM2_tbl24_entry new_tbl24_entry = { { .next_hop = next_hop, }, .valid = VALID, .ext_entry = 0, @@ -454,14 +537,14 @@ * index into tbl8. */ tbl8_index = lpm->tbl24[i].tbl8_gindex * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; tbl8_group_end = tbl8_index + - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; for (j = tbl8_index; j < tbl8_group_end; j++) { if (!lpm->tbl8[j].valid || lpm->tbl8[j].depth <= depth) { - struct rte_lpm_tbl8_entry + struct RTE_LPM2_tbl8_entry new_tbl8_entry = { .valid = VALID, .valid_group = VALID, @@ -485,8 +568,8 @@ } static inline int32_t -add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, - uint8_t next_hop) +add_depth_big(struct rte_lpm2 *lpm, uint32_t ip_masked, uint8_t depth, + uint64_t next_hop) { uint32_t tbl24_index; int32_t tbl8_group_index, tbl8_group_start, tbl8_group_end, tbl8_index, @@ -506,7 +589,7 @@ /* Find index into tbl8 and range. */ tbl8_index = (tbl8_group_index * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES) + + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES) + (ip_masked & 0xFF); /* Set tbl8 entry. */ @@ -522,7 +605,7 @@ * so assign whole structure in one go */ - struct rte_lpm_tbl24_entry new_tbl24_entry = { + struct RTE_LPM2_tbl24_entry new_tbl24_entry = { { .tbl8_gindex = (uint8_t)tbl8_group_index, }, .valid = VALID, .ext_entry = 1, @@ -541,9 +624,9 @@ } tbl8_group_start = tbl8_group_index * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; tbl8_group_end = tbl8_group_start + - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; /* Populate new tbl8 with tbl24 value. */ for (i = tbl8_group_start; i < tbl8_group_end; i++) { @@ -573,7 +656,7 @@ * so assign whole structure in one go. */ - struct rte_lpm_tbl24_entry new_tbl24_entry = { + struct RTE_LPM2_tbl24_entry new_tbl24_entry = { { .tbl8_gindex = (uint8_t)tbl8_group_index, }, .valid = VALID, .ext_entry = 1, @@ -588,14 +671,14 @@ */ tbl8_group_index = lpm->tbl24[tbl24_index].tbl8_gindex; tbl8_group_start = tbl8_group_index * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; tbl8_index = tbl8_group_start + (ip_masked & 0xFF); for (i = tbl8_index; i < (tbl8_index + tbl8_range); i++) { if (!lpm->tbl8[i].valid || lpm->tbl8[i].depth <= depth) { - struct rte_lpm_tbl8_entry new_tbl8_entry = { + struct RTE_LPM2_tbl8_entry new_tbl8_entry = { .valid = VALID, .depth = depth, .next_hop = next_hop, @@ -620,30 +703,31 @@ * Add a route */ int -rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, - uint8_t next_hop) +rte_lpm2_add(struct rte_lpm2 *lpm, uint32_t ip, uint8_t depth, + uint64_t next_hop) { - int32_t rule_index, status = 0; + int32_t status = 0; uint32_t ip_masked; + struct RTE_LPM2_rule* rule; /* Check user arguments. */ - if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) + if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM2_MAX_DEPTH)) return -EINVAL; ip_masked = ip & depth_to_mask(depth); /* Add the rule to the rule table. */ - rule_index = rule_add(lpm, ip_masked, depth, next_hop); + rule = rule_add(lpm, ip_masked, depth, next_hop); /* If the is no space available for new rule return error. */ - if (rule_index < 0) { - return rule_index; + if (unlikely(rule == NULL)) { + return -ENOSPC; } if (depth <= MAX_DEPTH_TBL24) { status = add_depth_small(lpm, ip_masked, depth, next_hop); } - else { /* If depth > RTE_LPM_MAX_DEPTH_TBL24 */ + else { /* If depth > RTE_LPM2_MAX_DEPTH_TBL24 */ status = add_depth_big(lpm, ip_masked, depth, next_hop); /* @@ -651,7 +735,10 @@ * rule that was added to rule table. */ if (status < 0) { - rule_delete(lpm, rule_index, depth); + rule_delete(lpm, ip_masked, depth); + + /* return rule to a mempool */ + rte_mempool_sp_put(lpm->rules_mempool, (void*) rule); return status; } @@ -664,24 +751,24 @@ * Look for a rule in the high-level rules table */ int -rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, -uint8_t *next_hop) +rte_lpm2_is_rule_present(struct rte_lpm2 *lpm, uint32_t ip, uint8_t depth, +uint64_t *next_hop) { uint32_t ip_masked; - int32_t rule_index; + struct RTE_LPM2_rule* rule; /* Check user arguments. */ if ((lpm == NULL) || (next_hop == NULL) || - (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) + (depth < 1) || (depth > RTE_LPM2_MAX_DEPTH)) return -EINVAL; /* Look for the rule using rule_find. */ ip_masked = ip & depth_to_mask(depth); - rule_index = rule_find(lpm, ip_masked, depth); + rule = rule_find(lpm, ip_masked, depth); - if (rule_index >= 0) { - *next_hop = lpm->rules_tbl[rule_index].next_hop; + if (rule != NULL) { + *next_hop = rule->next_hop; return 1; } @@ -689,30 +776,34 @@ return 0; } -static inline int32_t -find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint8_t *sub_rule_depth) +/* + * + */ +static inline struct RTE_LPM2_rule* +find_previous_rule(struct rte_lpm2 *lpm, lpm_rule_key_t* rule_key, + uint8_t *sub_rule_depth) { - int32_t rule_index; - uint32_t ip_masked; + uint32_t net; uint8_t prev_depth; + struct RTE_LPM2_rule* rule; - for (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) { - ip_masked = ip & depth_to_mask(prev_depth); + for (prev_depth = (uint8_t)(rule_key->mask - 1); prev_depth > 0; prev_depth--) { + net = rule_key->net & depth_to_mask(prev_depth); - rule_index = rule_find(lpm, ip_masked, prev_depth); + rule = rule_find(lpm, net, prev_depth); - if (rule_index >= 0) { + if (rule != NULL) { *sub_rule_depth = prev_depth; - return rule_index; + return rule; } } - return -1; + return NULL; } static inline int32_t -delete_depth_small(struct rte_lpm *lpm, uint32_t ip_masked, - uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth) +delete_depth_small(struct rte_lpm2 *lpm, uint32_t ip_masked, + uint8_t depth, struct RTE_LPM2_rule* sub_rule, uint8_t sub_rule_depth) { uint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j; @@ -721,10 +812,9 @@ tbl24_index = (ip_masked >> 8); /* - * Firstly check the sub_rule_index. A -1 indicates no replacement rule - * and a positive number indicates a sub_rule_index. + * Firstly check the sub_rule. A NULL indicates no replacement rule. */ - if (sub_rule_index < 0) { + if (sub_rule == NULL) { /* * If no replacement rule exists then invalidate entries * associated with this rule. @@ -734,7 +824,8 @@ if (lpm->tbl24[i].ext_entry == 0 && lpm->tbl24[i].depth <= depth ) { lpm->tbl24[i].valid = INVALID; - } else if (lpm->tbl24[i].ext_entry == 1) { + } + else { /* * If TBL24 entry is extended, then there has * to be a rule with depth >= 25 in the @@ -743,10 +834,10 @@ tbl8_group_index = lpm->tbl24[i].tbl8_gindex; tbl8_index = tbl8_group_index * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; for (j = tbl8_index; j < (tbl8_index + - RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) { + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES); j++) { if (lpm->tbl8[j].depth <= depth) lpm->tbl8[j].valid = INVALID; @@ -760,19 +851,17 @@ * associated with this rule. */ - struct rte_lpm_tbl24_entry new_tbl24_entry = { - {.next_hop = lpm->rules_tbl[sub_rule_index].next_hop,}, + struct RTE_LPM2_tbl24_entry new_tbl24_entry = { + {.next_hop = sub_rule->next_hop,}, .valid = VALID, .ext_entry = 0, .depth = sub_rule_depth, }; - struct rte_lpm_tbl8_entry new_tbl8_entry = { + struct RTE_LPM2_tbl8_entry new_tbl8_entry = { .valid = VALID, - .valid_group = VALID, .depth = sub_rule_depth, - .next_hop = lpm->rules_tbl - [sub_rule_index].next_hop, + .next_hop = sub_rule->next_hop, }; for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) { @@ -780,7 +869,8 @@ if (lpm->tbl24[i].ext_entry == 0 && lpm->tbl24[i].depth <= depth ) { lpm->tbl24[i] = new_tbl24_entry; - } else if (lpm->tbl24[i].ext_entry == 1) { + } + else { /* * If TBL24 entry is extended, then there has * to be a rule with depth >= 25 in the @@ -789,10 +879,10 @@ tbl8_group_index = lpm->tbl24[i].tbl8_gindex; tbl8_index = tbl8_group_index * - RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; for (j = tbl8_index; j < (tbl8_index + - RTE_LPM_TBL8_GROUP_NUM_ENTRIES); j++) { + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES); j++) { if (lpm->tbl8[j].depth <= depth) lpm->tbl8[j] = new_tbl8_entry; @@ -813,14 +903,14 @@ * thus can be recycled */ static inline int32_t -tbl8_recycle_check(struct rte_lpm_tbl8_entry *tbl8, uint32_t tbl8_group_start) +tbl8_recycle_check(struct RTE_LPM2_tbl8_entry *tbl8, uint32_t tbl8_group_start) { uint32_t tbl8_group_end, i; - tbl8_group_end = tbl8_group_start + RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + tbl8_group_end = tbl8_group_start + RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; /* * Check the first entry of the given tbl8. If it is invalid we know - * this tbl8 does not contain any rule with a depth < RTE_LPM_MAX_DEPTH + * this tbl8 does not contain any rule with a depth < RTE_LPM2_MAX_DEPTH * (As they would affect all entries in a tbl8) and thus this table * can not be recycled. */ @@ -859,8 +949,8 @@ } static inline int32_t -delete_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, - uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth) +delete_depth_big(struct rte_lpm2 *lpm, uint32_t ip_masked, + uint8_t depth, struct RTE_LPM2_rule* sub_rule, uint8_t sub_rule_depth) { uint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index, tbl8_range, i; @@ -874,11 +964,11 @@ /* Calculate the index into tbl8 and range. */ tbl8_group_index = lpm->tbl24[tbl24_index].tbl8_gindex; - tbl8_group_start = tbl8_group_index * RTE_LPM_TBL8_GROUP_NUM_ENTRIES; + tbl8_group_start = tbl8_group_index * RTE_LPM2_TBL8_GROUP_NUM_ENTRIES; tbl8_index = tbl8_group_start + (ip_masked & 0xFF); tbl8_range = depth_to_range(depth); - if (sub_rule_index < 0) { + if (sub_rule == NULL) { /* * Loop through the range of entries on tbl8 for which the * rule_to_delete must be removed or modified. @@ -890,11 +980,11 @@ } else { /* Set new tbl8 entry. */ - struct rte_lpm_tbl8_entry new_tbl8_entry = { + struct RTE_LPM2_tbl8_entry new_tbl8_entry = { .valid = VALID, .depth = sub_rule_depth, .valid_group = lpm->tbl8[tbl8_group_start].valid_group, - .next_hop = lpm->rules_tbl[sub_rule_index].next_hop, + .next_hop = sub_rule->next_hop, }; /* @@ -922,7 +1012,7 @@ } else if (tbl8_recycle_index > -1) { /* Update tbl24 entry. */ - struct rte_lpm_tbl24_entry new_tbl24_entry = { + struct RTE_LPM2_tbl24_entry new_tbl24_entry = { { .next_hop = lpm->tbl8[tbl8_recycle_index].next_hop, }, .valid = VALID, .ext_entry = 0, @@ -941,16 +1031,15 @@ * Deletes a rule */ int -rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth) +rte_lpm2_delete(struct rte_lpm2 *lpm, uint32_t ip, uint8_t depth) { - int32_t rule_to_delete_index, sub_rule_index; uint32_t ip_masked; uint8_t sub_rule_depth; /* * Check input arguments. Note: IP must be a positive integer of 32 * bits in length therefore it need not be checked. */ - if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) { + if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM2_MAX_DEPTH)) { return -EINVAL; } @@ -960,17 +1049,27 @@ * Find the index of the input rule, that needs to be deleted, in the * rule table. */ - rule_to_delete_index = rule_find(lpm, ip_masked, depth); + lpm_rule_key_t rule_key; + rule_key.net = ip_masked; + rule_key.mask = (uint32_t) depth; + + hash_sig_t sig = lpm_prefix_hash_crc(&rule_key, 0, 0); + + struct RTE_LPM2_rule* rule_to_delete = rule_find_by_key_with_hash(lpm, + &rule_key, sig); /* - * Check if rule_to_delete_index was found. If no rule was found the + * Check if rule was found. If no rule was found the * function rule_find returns -EINVAL. */ - if (rule_to_delete_index < 0) + if (rule_to_delete == NULL) return -EINVAL; /* Delete the rule from the rule table. */ - rule_delete(lpm, rule_to_delete_index, depth); + rule_delete_by_key_with_hash(lpm, &rule_key, sig); + + /* return to a mempool */ + rte_mempool_sp_put(lpm->rules_mempool, (void*) rule_to_delete); /* * Find rule to replace the rule_to_delete. If there is no rule to @@ -978,18 +1077,18 @@ * entries associated with this rule. */ sub_rule_depth = 0; - sub_rule_index = find_previous_rule(lpm, ip, depth, &sub_rule_depth); + struct RTE_LPM2_rule* sub_rule = find_previous_rule(lpm, &rule_key, + &sub_rule_depth); /* * If the input depth value is less than 25 use function * delete_depth_small otherwise use delete_depth_big. */ if (depth <= MAX_DEPTH_TBL24) { - return delete_depth_small(lpm, ip_masked, depth, - sub_rule_index, sub_rule_depth); + return delete_depth_small(lpm, ip_masked, depth, sub_rule, sub_rule_depth); } else { /* If depth > MAX_DEPTH_TBL24 */ - return delete_depth_big(lpm, ip_masked, depth, sub_rule_index, sub_rule_depth); + return delete_depth_big(lpm, ip_masked, depth, sub_rule, sub_rule_depth); } } @@ -997,7 +1096,7 @@ * Delete all rules from the LPM table. */ void -rte_lpm_delete_all(struct rte_lpm *lpm) +rte_lpm2_delete_all(struct rte_lpm2 *lpm) { /* Zero rule information. */ memset(lpm->rule_info, 0, sizeof(lpm->rule_info)); @@ -1009,5 +1108,15 @@ memset(lpm->tbl8, 0, sizeof(lpm->tbl8)); /* Delete all rules form the rules table. */ - memset(lpm->rules_tbl, 0, sizeof(lpm->rules_tbl[0]) * lpm->max_rules); + const void* next_key; + uint32_t iter = 0; + struct RTE_LPM2_rule* rule; + + while (rte_hash_iterate(lpm->rules_hash_tbl, &next_key, + (void**) &rule, &iter) >= 0) { + /* return rule to a mempool */ + rte_mempool_sp_put(lpm->rules_mempool, (void*) rule); + } + /* zero hash */ + rte_hash_reset(lpm->rules_hash_tbl); }