<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <meta name="Generator" content="Microsoft Word 15 (filtered medium)"> <style></style> </head> <body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word"> <div class="WordSection1"> Minimize the performance impact of large numbers of BGP peering<o:p></o:p> routes by updating LPM's IPv4 code to use a hash like the IPv6 code.<o:p></o:p> <o:p> </o:p> Co-authored-by: Julien Charbon <jcharbon@verisign.com><o:p></o:p> Signed-off-by: Julien Charbon <jcharbon@verisign.com><o:p></o:p> Signed-off-by: Jeff Warrington <jwarrington@verisign.com><o:p></o:p> Co-authored-by: Nicolas Witkowski <nitkowski@verisign.com><o:p></o:p> Signed-off-by: Nicolas Witkowski <nitkowski@verisign.com><o:p></o:p> Co-authored-by: Rohit Gupta rogupta@verisign.com<o:p></o:p> Signed-off-by: Rohit Gupta rogupta@verisign.com<o:p></o:p> ---<o:p></o:p> lib/lpm/rte_lpm.c | 306 ++++++++++++++++++++++------------------------<o:p></o:p> lib/lpm/rte_lpm.h | 6 +<o:p></o:p> 2 files changed, 149 insertions(+), 163 deletions(-)<o:p></o:p> <o:p> </o:p> diff --git a/lib/lpm/rte_lpm.c b/lib/lpm/rte_lpm.c<o:p></o:p> index cdcd1b7f9e..c951be8946 100644<o:p></o:p> --- a/lib/lpm/rte_lpm.c<o:p></o:p> +++ b/lib/lpm/rte_lpm.c<o:p></o:p> @@ -16,9 +16,13 @@<o:p></o:p> #include <rte_string_fns.h><o:p></o:p> #include <rte_errno.h><o:p></o:p> #include <rte_tailq.h><o:p></o:p> +#include <rte_hash.h><o:p></o:p> +#include <rte_jhash.h><o:p></o:p> <o:p></o:p> #include "rte_lpm.h"<o:p></o:p> <o:p></o:p> +#define RULE_HASH_TABLE_EXTRA_SPACE 64<o:p></o:p> +<o:p></o:p> TAILQ_HEAD(rte_lpm_list, rte_tailq_entry);<o:p></o:p> <o:p></o:p> static struct rte_tailq_elem rte_lpm_tailq = {<o:p></o:p> @@ -53,10 +57,11 @@ struct __rte_lpm {<o:p></o:p> /* LPM metadata. */<o:p></o:p> char name[RTE_LPM_NAMESIZE]; /**< Name of the lpm. */<o:p></o:p> uint32_t max_rules; /**< Max. balanced rules per lpm. */<o:p></o:p> + uint32_t used_rules; /**< Used rules so far. */<o:p></o:p> uint32_t number_tbl8s; /**< Number of tbl8s. */<o:p></o:p> /**< Rule info table. */<o:p></o:p> struct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];<o:p></o:p> - struct rte_lpm_rule *rules_tbl; /**< LPM rules. */<o:p></o:p> + struct rte_hash *rules_tbl; /**< LPM rules. */<o:p></o:p> <o:p></o:p> /* RCU config. */<o:p></o:p> struct rte_rcu_qsbr *v; /* RCU QSBR variable. */<o:p></o:p> @@ -76,6 +81,47 @@ struct __rte_lpm {<o:p></o:p> #define VERIFY_DEPTH(depth)<o:p></o:p> #endif<o:p></o:p> <o:p></o:p> +/*<o:p></o:p> + * LPM rule hash function<o:p></o:p> + *<o:p></o:p> + * It's used as a hash function for the rte_hash<o:p></o:p> + * containing rules<o:p></o:p> + */<o:p></o:p> +static inline uint32_t<o:p></o:p> +rule_hash(const void *data, __rte_unused uint32_t data_len,<o:p></o:p> + uint32_t init_val)<o:p></o:p> +{<o:p></o:p> + return rte_jhash(data, sizeof(struct rte_lpm_rule_key), init_val);<o:p></o:p> +}<o:p></o:p> +<o:p></o:p> +static inline void<o:p></o:p> +rule_key_init(struct rte_lpm_rule_key *key, uint32_t ip, uint8_t depth)<o:p></o:p> +{<o:p></o:p> + key->ip = ip;<o:p></o:p> + key->depth = depth;<o:p></o:p> +}<o:p></o:p> +<o:p></o:p> +/* Find a rule */<o:p></o:p> +static inline int<o:p></o:p> +rule_find_with_key(struct rte_lpm *lpm, const struct rte_lpm_rule_key *rule_key, uint32_t *next_hop)<o:p></o:p> +{<o:p></o:p> + struct __rte_lpm *i_lpm;<o:p></o:p> + uint64_t hash_val;<o:p></o:p> + int ret;<o:p></o:p> +<o:p></o:p> + i_lpm = container_of(lpm, struct __rte_lpm, lpm);<o:p></o:p> +<o:p></o:p> + /* lookup for a rule */<o:p></o:p> + ret = rte_hash_lookup_data(i_lpm->rules_tbl, (const void *) rule_key,<o:p></o:p> + (void **) &hash_val);<o:p></o:p> + if (ret >= 0) {<o:p></o:p> + *next_hop = (uint32_t) hash_val;<o:p></o:p> + return 1;<o:p></o:p> + }<o:p></o:p> +<o:p></o:p> + return 0;<o:p></o:p> +}<o:p></o:p> +<o:p></o:p> /*<o:p></o:p> * Converts a given depth value to its corresponding mask value.<o:p></o:p> *<o:p></o:p> @@ -150,8 +196,9 @@ rte_lpm_create(const char *name, int socket_id,<o:p></o:p> struct __rte_lpm *i_lpm;<o:p></o:p> struct rte_lpm *lpm = NULL;<o:p></o:p> struct rte_tailq_entry *te;<o:p></o:p> - uint32_t mem_size, rules_size, tbl8s_size;<o:p></o:p> + uint32_t mem_size, tbl8s_size;<o:p></o:p> struct rte_lpm_list *lpm_list;<o:p></o:p> + struct rte_hash *rules_tbl = NULL;<o:p></o:p> <o:p></o:p> lpm_list = RTE_TAILQ_CAST(rte_lpm_tailq.head, rte_lpm_list);<o:p></o:p> <o:p></o:p> @@ -164,7 +211,25 @@ rte_lpm_create(const char *name, int socket_id,<o:p></o:p> return NULL;<o:p></o:p> }<o:p></o:p> <o:p></o:p> - snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);<o:p></o:p> + snprintf(mem_name, sizeof(mem_name), "LRHv4_%s", name);<o:p></o:p> + struct rte_hash_parameters rule_hash_tbl_params = {<o:p></o:p> + .entries = config->max_rules * 1.2 + RULE_HASH_TABLE_EXTRA_SPACE,<o:p></o:p> + .key_len = sizeof(struct rte_lpm_rule_key),<o:p></o:p> + .hash_func = rule_hash,<o:p></o:p> + .hash_func_init_val = 0,<o:p></o:p> + .name = mem_name,<o:p></o:p> + .reserved = 0,<o:p></o:p> + .socket_id = socket_id,<o:p></o:p> + .extra_flag = 0<o:p></o:p> + };<o:p></o:p> +<o:p></o:p> + rules_tbl = rte_hash_create(&rule_hash_tbl_params);<o:p></o:p> + if (rules_tbl == NULL) {<o:p></o:p> + RTE_LOG(ERR, LPM, "LPM rules hash table allocation failed: %s (%d)",<o:p></o:p> + rte_strerror(rte_errno), rte_errno);<o:p></o:p> +<o:p></o:p> + return NULL;<o:p></o:p> + }<o:p></o:p> <o:p></o:p> rte_mcfg_tailq_write_lock();<o:p></o:p> <o:p></o:p> @@ -182,7 +247,6 @@ rte_lpm_create(const char *name, int socket_id,<o:p></o:p> <o:p></o:p> /* Determine the amount of memory to allocate. */<o:p></o:p> mem_size = sizeof(*i_lpm);<o:p></o:p> - rules_size = sizeof(struct rte_lpm_rule) * config->max_rules;<o:p></o:p> tbl8s_size = sizeof(struct rte_lpm_tbl_entry) *<o:p></o:p> RTE_LPM_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s;<o:p></o:p> <o:p></o:p> @@ -204,18 +268,6 @@ rte_lpm_create(const char *name, int socket_id,<o:p></o:p> goto exit;<o:p></o:p> }<o:p></o:p> <o:p></o:p> - i_lpm->rules_tbl = rte_zmalloc_socket(NULL,<o:p></o:p> - (size_t)rules_size, RTE_CACHE_LINE_SIZE, socket_id);<o:p></o:p> -<o:p></o:p> - if (i_lpm->rules_tbl == NULL) {<o:p></o:p> - RTE_LOG(ERR, LPM, "LPM rules_tbl memory allocation failed\n");<o:p></o:p> - rte_free(i_lpm);<o:p></o:p> - i_lpm = NULL;<o:p></o:p> - rte_free(te);<o:p></o:p> - rte_errno = ENOMEM;<o:p></o:p> - goto exit;<o:p></o:p> - }<o:p></o:p> -<o:p></o:p> i_lpm->lpm.tbl8 = rte_zmalloc_socket(NULL,<o:p></o:p> (size_t)tbl8s_size, RTE_CACHE_LINE_SIZE, socket_id);<o:p></o:p> <o:p></o:p> @@ -230,6 +282,7 @@ rte_lpm_create(const char *name, int socket_id,<o:p></o:p> }<o:p></o:p> <o:p></o:p> /* Save user arguments. */<o:p></o:p> + i_lpm->rules_tbl = rules_tbl;<o:p></o:p> i_lpm->max_rules = config->max_rules;<o:p></o:p> i_lpm->number_tbl8s = config->number_tbl8s;<o:p></o:p> strlcpy(i_lpm->name, name, sizeof(i_lpm->name));<o:p></o:p> @@ -277,7 +330,7 @@ rte_lpm_free(struct rte_lpm *lpm)<o:p></o:p> if (i_lpm->dq != NULL)<o:p></o:p> rte_rcu_qsbr_dq_delete(i_lpm->dq);<o:p></o:p> rte_free(i_lpm->lpm.tbl8);<o:p></o:p> - rte_free(i_lpm->rules_tbl);<o:p></o:p> + rte_hash_free(i_lpm->rules_tbl);<o:p></o:p> rte_free(i_lpm);<o:p></o:p> rte_free(te);<o:p></o:p> }<o:p></o:p> @@ -359,106 +412,64 @@ rte_lpm_rcu_qsbr_add(struct rte_lpm *lpm, struct rte_lpm_rcu_config *cfg)<o:p></o:p> * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.<o:p></o:p> */<o:p></o:p> static int32_t<o:p></o:p> -rule_add(struct __rte_lpm *i_lpm, uint32_t ip_masked, uint8_t depth,<o:p></o:p> - uint32_t next_hop)<o:p></o:p> +rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, uint32_t next_hop)<o:p></o:p> {<o:p></o:p> - uint32_t rule_gindex, rule_index, last_rule;<o:p></o:p> - int i;<o:p></o:p> + int ret, rule_exist;<o:p></o:p> + struct rte_lpm_rule_key rule_key;<o:p></o:p> + uint32_t unused;<o:p></o:p> <o:p></o:p> VERIFY_DEPTH(depth);<o:p></o:p> <o:p></o:p> - /* Scan through rule group to see if rule already exists. */<o:p></o:p> - if (i_lpm->rule_info[depth - 1].used_rules > 0) {<o:p></o:p> + /* init a rule key */<o:p></o:p> + rule_key_init(&rule_key, ip_masked, depth);<o:p></o:p> <o:p></o:p> - /* rule_gindex stands for rule group index. */<o:p></o:p> - rule_gindex = i_lpm->rule_info[depth - 1].first_rule;<o:p></o:p> - /* Initialise rule_index to point to start of rule group. */<o:p></o:p> - rule_index = rule_gindex;<o:p></o:p> - /* Last rule = Last used rule in this rule group. */<o:p></o:p> - last_rule = rule_gindex + i_lpm->rule_info[depth - 1].used_rules;<o:p></o:p> + /* Scan through rule list to see if rule already exists. */<o:p></o:p> + rule_exist = rule_find_with_key(lpm, &rule_key, &unused);<o:p></o:p> <o:p></o:p> - for (; rule_index < last_rule; rule_index++) {<o:p></o:p> + struct __rte_lpm *i_lpm = container_of(lpm, struct __rte_lpm, lpm);<o:p></o:p> <o:p></o:p> - /* If rule already exists update next hop and return. */<o:p></o:p> - if (i_lpm->rules_tbl[rule_index].ip == ip_masked) {<o:p></o:p> + if (!rule_exist && i_lpm->used_rules == i_lpm->max_rules)<o:p></o:p> + return -ENOSPC;<o:p></o:p> <o:p></o:p> - if (i_lpm->rules_tbl[rule_index].next_hop<o:p></o:p> - == next_hop)<o:p></o:p> - return -EEXIST;<o:p></o:p> - i_lpm->rules_tbl[rule_index].next_hop = next_hop;<o:p></o:p> + ret = rte_hash_add_key_data(i_lpm->rules_tbl, &rule_key,<o:p></o:p> + (void *)(uintptr_t) next_hop);<o:p></o:p> <o:p></o:p> - return rule_index;<o:p></o:p> - }<o:p></o:p> - }<o:p></o:p> -<o:p></o:p> - if (rule_index == i_lpm->max_rules)<o:p></o:p> - return -ENOSPC;<o:p></o:p> - } else {<o:p></o:p> - /* Calculate the position in which the rule will be stored. */<o:p></o:p> - rule_index = 0;<o:p></o:p> -<o:p></o:p> - for (i = depth - 1; i > 0; i--) {<o:p></o:p> - if (i_lpm->rule_info[i - 1].used_rules > 0) {<o:p></o:p> - rule_index = i_lpm->rule_info[i - 1].first_rule<o:p></o:p> - + i_lpm->rule_info[i - 1].used_rules;<o:p></o:p> - break;<o:p></o:p> - }<o:p></o:p> - }<o:p></o:p> - if (rule_index == i_lpm->max_rules)<o:p></o:p> - return -ENOSPC;<o:p></o:p> -<o:p></o:p> - i_lpm->rule_info[depth - 1].first_rule = rule_index;<o:p></o:p> - }<o:p></o:p> -<o:p></o:p> - /* Make room for the new rule in the array. */<o:p></o:p> - for (i = RTE_LPM_MAX_DEPTH; i > depth; i--) {<o:p></o:p> - if (i_lpm->rule_info[i - 1].first_rule<o:p></o:p> - + i_lpm->rule_info[i - 1].used_rules == i_lpm->max_rules)<o:p></o:p> - return -ENOSPC;<o:p></o:p> -<o:p></o:p> - if (i_lpm->rule_info[i - 1].used_rules > 0) {<o:p></o:p> - i_lpm->rules_tbl[i_lpm->rule_info[i - 1].first_rule<o:p></o:p> - + i_lpm->rule_info[i - 1].used_rules]<o:p></o:p> - = i_lpm->rules_tbl[i_lpm->rule_info[i - 1].first_rule];<o:p></o:p> - i_lpm->rule_info[i - 1].first_rule++;<o:p></o:p> - }<o:p></o:p> - }<o:p></o:p> -<o:p></o:p> - /* Add the new rule. */<o:p></o:p> - i_lpm->rules_tbl[rule_index].ip = ip_masked;<o:p></o:p> - i_lpm->rules_tbl[rule_index].next_hop = next_hop;<o:p></o:p> + if (ret < 0)<o:p></o:p> + return ret;<o:p></o:p> <o:p></o:p> /* Increment the used rules counter for this rule group. */<o:p></o:p> - i_lpm->rule_info[depth - 1].used_rules++;<o:p></o:p> + if (!rule_exist) {<o:p></o:p> + i_lpm->rule_info[depth - 1].used_rules++;<o:p></o:p> + i_lpm->used_rules++;<o:p></o:p> + return 1;<o:p></o:p> + }<o:p></o:p> <o:p></o:p> - return rule_index;<o:p></o:p> + return 0;<o:p></o:p> }<o:p></o:p> <o:p></o:p> /*<o:p></o:p> * Delete a rule from the rule table.<o:p></o:p> * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.<o:p></o:p> */<o:p></o:p> -static void<o:p></o:p> -rule_delete(struct __rte_lpm *i_lpm, int32_t rule_index, uint8_t depth)<o:p></o:p> +static int<o:p></o:p> +rule_delete(struct __rte_lpm *i_lpm, int32_t ip, uint8_t depth)<o:p></o:p> {<o:p></o:p> - int i;<o:p></o:p> + int ret;<o:p></o:p> + struct rte_lpm_rule_key rule_key;<o:p></o:p> <o:p></o:p> VERIFY_DEPTH(depth);<o:p></o:p> <o:p></o:p> - i_lpm->rules_tbl[rule_index] =<o:p></o:p> - i_lpm->rules_tbl[i_lpm->rule_info[depth - 1].first_rule<o:p></o:p> - + i_lpm->rule_info[depth - 1].used_rules - 1];<o:p></o:p> + rule_key_init(&rule_key, ip, depth);<o:p></o:p> <o:p></o:p> - for (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {<o:p></o:p> - if (i_lpm->rule_info[i].used_rules > 0) {<o:p></o:p> - i_lpm->rules_tbl[i_lpm->rule_info[i].first_rule - 1] =<o:p></o:p> - i_lpm->rules_tbl[i_lpm->rule_info[i].first_rule<o:p></o:p> - + i_lpm->rule_info[i].used_rules - 1];<o:p></o:p> - i_lpm->rule_info[i].first_rule--;<o:p></o:p> - }<o:p></o:p> + /* delete the rule */<o:p></o:p> + ret = rte_hash_del_key(i_lpm->rules_tbl, (void *) &rule_key);<o:p></o:p> +<o:p></o:p> + if (ret >= 0) {<o:p></o:p> + i_lpm->rule_info[depth - 1].used_rules--;<o:p></o:p> + i_lpm->used_rules--;<o:p></o:p> }<o:p></o:p> <o:p></o:p> - i_lpm->rule_info[depth - 1].used_rules--;<o:p></o:p> + return ret;<o:p></o:p> }<o:p></o:p> <o:p></o:p> /*<o:p></o:p> @@ -466,24 +477,14 @@ rule_delete(struct __rte_lpm *i_lpm, int32_t rule_index, uint8_t depth)<o:p></o:p> * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.<o:p></o:p> */<o:p></o:p> static int32_t<o:p></o:p> -rule_find(struct __rte_lpm *i_lpm, uint32_t ip_masked, uint8_t depth)<o:p></o:p> +rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth, uint32_t *next_hop)<o:p></o:p> {<o:p></o:p> - uint32_t rule_gindex, last_rule, rule_index;<o:p></o:p> -<o:p></o:p> - VERIFY_DEPTH(depth);<o:p></o:p> -<o:p></o:p> - rule_gindex = i_lpm->rule_info[depth - 1].first_rule;<o:p></o:p> - last_rule = rule_gindex + i_lpm->rule_info[depth - 1].used_rules;<o:p></o:p> + struct rte_lpm_rule_key rule_key;<o:p></o:p> <o:p></o:p> - /* Scan used rules at given depth to find rule. */<o:p></o:p> - for (rule_index = rule_gindex; rule_index < last_rule; rule_index++) {<o:p></o:p> - /* If rule is found return the rule index. */<o:p></o:p> - if (i_lpm->rules_tbl[rule_index].ip == ip_masked)<o:p></o:p> - return rule_index;<o:p></o:p> - }<o:p></o:p> + /* init a rule key */<o:p></o:p> + rule_key_init(&rule_key, ip_masked, depth);<o:p></o:p> <o:p></o:p> - /* If rule is not found return -EINVAL. */<o:p></o:p> - return -EINVAL;<o:p></o:p> + return rule_find_with_key(lpm, &rule_key, next_hop);<o:p></o:p> }<o:p></o:p> <o:p></o:p> /*<o:p></o:p> @@ -799,7 +800,7 @@ int<o:p></o:p> rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,<o:p></o:p> uint32_t next_hop)<o:p></o:p> {<o:p></o:p> - int32_t rule_index, status = 0;<o:p></o:p> + int32_t status = 0;<o:p></o:p> struct __rte_lpm *i_lpm;<o:p></o:p> uint32_t ip_masked;<o:p></o:p> <o:p></o:p> @@ -811,17 +812,11 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,<o:p></o:p> ip_masked = ip & depth_to_mask(depth);<o:p></o:p> <o:p></o:p> /* Add the rule to the rule table. */<o:p></o:p> - rule_index = rule_add(i_lpm, ip_masked, depth, next_hop);<o:p></o:p> -<o:p></o:p> - /* Skip table entries update if The rule is the same as<o:p></o:p> - * the rule in the rules table.<o:p></o:p> - */<o:p></o:p> - if (rule_index == -EEXIST)<o:p></o:p> - return 0;<o:p></o:p> + status = rule_add(lpm, ip_masked, depth, next_hop);<o:p></o:p> <o:p></o:p> /* If the is no space available for new rule return error. */<o:p></o:p> - if (rule_index < 0) {<o:p></o:p> - return rule_index;<o:p></o:p> + if (status < 0) {<o:p></o:p> + return status;<o:p></o:p> }<o:p></o:p> <o:p></o:p> if (depth <= MAX_DEPTH_TBL24) {<o:p></o:p> @@ -834,7 +829,7 @@ rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,<o:p></o:p> * rule that was added to rule table.<o:p></o:p> */<o:p></o:p> if (status < 0) {<o:p></o:p> - rule_delete(i_lpm, rule_index, depth);<o:p></o:p> + rule_delete(i_lpm, ip_masked, depth);<o:p></o:p> <o:p></o:p> return status;<o:p></o:p> }<o:p></o:p> @@ -850,9 +845,7 @@ int<o:p></o:p> rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,<o:p></o:p> uint32_t *next_hop)<o:p></o:p> {<o:p></o:p> - struct __rte_lpm *i_lpm;<o:p></o:p> uint32_t ip_masked;<o:p></o:p> - int32_t rule_index;<o:p></o:p> <o:p></o:p> /* Check user arguments. */<o:p></o:p> if ((lpm == NULL) ||<o:p></o:p> @@ -861,44 +854,42 @@ uint32_t *next_hop)<o:p></o:p> return -EINVAL;<o:p></o:p> <o:p></o:p> /* Look for the rule using rule_find. */<o:p></o:p> - i_lpm = container_of(lpm, struct __rte_lpm, lpm);<o:p></o:p> ip_masked = ip & depth_to_mask(depth);<o:p></o:p> - rule_index = rule_find(i_lpm, ip_masked, depth);<o:p></o:p> <o:p></o:p> - if (rule_index >= 0) {<o:p></o:p> - *next_hop = i_lpm->rules_tbl[rule_index].next_hop;<o:p></o:p> + if (rule_find(lpm, ip_masked, depth, next_hop))<o:p></o:p> return 1;<o:p></o:p> - }<o:p></o:p> <o:p></o:p> /* If rule is not found return 0. */<o:p></o:p> return 0;<o:p></o:p> }<o:p></o:p> <o:p></o:p> static int32_t<o:p></o:p> -find_previous_rule(struct __rte_lpm *i_lpm, uint32_t ip, uint8_t depth,<o:p></o:p> - uint8_t *sub_rule_depth)<o:p></o:p> +find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,<o:p></o:p> + uint32_t *subrule_prev_hop, uint8_t *subrule_prev_depth)<o:p></o:p> {<o:p></o:p> - int32_t rule_index;<o:p></o:p> uint32_t ip_masked;<o:p></o:p> + uint32_t prev_hop;<o:p></o:p> uint8_t prev_depth;<o:p></o:p> + int found;<o:p></o:p> <o:p></o:p> for (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {<o:p></o:p> ip_masked = ip & depth_to_mask(prev_depth);<o:p></o:p> <o:p></o:p> - rule_index = rule_find(i_lpm, ip_masked, prev_depth);<o:p></o:p> + found = rule_find(lpm, ip_masked, prev_depth, &prev_hop);<o:p></o:p> <o:p></o:p> - if (rule_index >= 0) {<o:p></o:p> - *sub_rule_depth = prev_depth;<o:p></o:p> - return rule_index;<o:p></o:p> + if (found) {<o:p></o:p> + *subrule_prev_hop = prev_hop;<o:p></o:p> + *subrule_prev_depth = prev_depth;<o:p></o:p> + return 1;<o:p></o:p> }<o:p></o:p> }<o:p></o:p> <o:p></o:p> - return -1;<o:p></o:p> + return 0;<o:p></o:p> }<o:p></o:p> <o:p></o:p> static int32_t<o:p></o:p> delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> - uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)<o:p></o:p> + uint8_t depth, int found, uint32_t sub_rule_hop, uint8_t sub_rule_depth)<o:p></o:p> {<o:p></o:p> #define group_idx next_hop<o:p></o:p> uint32_t tbl24_range, tbl24_index, tbl8_group_index, tbl8_index, i, j;<o:p></o:p> @@ -912,7 +903,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> * Firstly check the sub_rule_index. A -1 indicates no replacement rule<o:p></o:p> * and a positive number indicates a sub_rule_index.<o:p></o:p> */<o:p></o:p> - if (sub_rule_index < 0) {<o:p></o:p> + if (!found) {<o:p></o:p> /*<o:p></o:p> * If no replacement rule exists then invalidate entries<o:p></o:p> * associated with this rule.<o:p></o:p> @@ -949,7 +940,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> */<o:p></o:p> <o:p></o:p> struct rte_lpm_tbl_entry new_tbl24_entry = {<o:p></o:p> - .next_hop = i_lpm->rules_tbl[sub_rule_index].next_hop,<o:p></o:p> + .next_hop = sub_rule_hop,<o:p></o:p> .valid = VALID,<o:p></o:p> .valid_group = 0,<o:p></o:p> .depth = sub_rule_depth,<o:p></o:p> @@ -959,8 +950,7 @@ delete_depth_small(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> .valid = VALID,<o:p></o:p> .valid_group = VALID,<o:p></o:p> .depth = sub_rule_depth,<o:p></o:p> - .next_hop = i_lpm->rules_tbl<o:p></o:p> - [sub_rule_index].next_hop,<o:p></o:p> + .next_hop = sub_rule_hop,<o:p></o:p> };<o:p></o:p> <o:p></o:p> for (i = tbl24_index; i < (tbl24_index + tbl24_range); i++) {<o:p></o:p> @@ -1052,7 +1042,7 @@ tbl8_recycle_check(struct rte_lpm_tbl_entry *tbl8,<o:p></o:p> <o:p></o:p> static int32_t<o:p></o:p> delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> - uint8_t depth, int32_t sub_rule_index, uint8_t sub_rule_depth)<o:p></o:p> + uint8_t depth, int found, uint32_t sub_rule_hop, uint8_t sub_rule_depth)<o:p></o:p> {<o:p></o:p> #define group_idx next_hop<o:p></o:p> uint32_t tbl24_index, tbl8_group_index, tbl8_group_start, tbl8_index,<o:p></o:p> @@ -1071,7 +1061,7 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> tbl8_index = tbl8_group_start + (ip_masked & 0xFF);<o:p></o:p> tbl8_range = depth_to_range(depth);<o:p></o:p> <o:p></o:p> - if (sub_rule_index < 0) {<o:p></o:p> + if (!found) {<o:p></o:p> /*<o:p></o:p> * Loop through the range of entries on tbl8 for which the<o:p></o:p> * rule_to_delete must be removed or modified.<o:p></o:p> @@ -1086,7 +1076,7 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> .valid = VALID,<o:p></o:p> .depth = sub_rule_depth,<o:p></o:p> .valid_group = i_lpm->lpm.tbl8[tbl8_group_start].valid_group,<o:p></o:p> - .next_hop = i_lpm->rules_tbl[sub_rule_index].next_hop,<o:p></o:p> + .next_hop = sub_rule_hop,<o:p></o:p> };<o:p></o:p> <o:p></o:p> /*<o:p></o:p> @@ -1142,9 +1132,10 @@ delete_depth_big(struct __rte_lpm *i_lpm, uint32_t ip_masked,<o:p></o:p> int<o:p></o:p> rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)<o:p></o:p> {<o:p></o:p> - int32_t rule_to_delete_index, sub_rule_index;<o:p></o:p> + int32_t found;<o:p></o:p> struct __rte_lpm *i_lpm;<o:p></o:p> uint32_t ip_masked;<o:p></o:p> + uint32_t sub_rule_hop;<o:p></o:p> uint8_t sub_rule_depth;<o:p></o:p> /*<o:p></o:p> * Check input arguments. Note: IP must be a positive integer of 32<o:p></o:p> @@ -1157,21 +1148,9 @@ rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)<o:p></o:p> i_lpm = container_of(lpm, struct __rte_lpm, lpm);<o:p></o:p> ip_masked = ip & depth_to_mask(depth);<o:p></o:p> <o:p></o:p> - /*<o:p></o:p> - * Find the index of the input rule, that needs to be deleted, in the<o:p></o:p> - * rule table.<o:p></o:p> - */<o:p></o:p> - rule_to_delete_index = rule_find(i_lpm, ip_masked, depth);<o:p></o:p> -<o:p></o:p> - /*<o:p></o:p> - * Check if rule_to_delete_index was found. If no rule was found the<o:p></o:p> - * function rule_find returns -EINVAL.<o:p></o:p> - */<o:p></o:p> - if (rule_to_delete_index < 0)<o:p></o:p> - return -EINVAL;<o:p></o:p> -<o:p></o:p> /* Delete the rule from the rule table. */<o:p></o:p> - rule_delete(i_lpm, rule_to_delete_index, depth);<o:p></o:p> + if (rule_delete(i_lpm, ip_masked, depth) < 0)<o:p></o:p> + return -EINVAL;<o:p></o:p> <o:p></o:p> /*<o:p></o:p> * Find rule to replace the rule_to_delete. If there is no rule to<o:p></o:p> @@ -1179,18 +1158,18 @@ rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth)<o:p></o:p> * entries associated with this rule.<o:p></o:p> */<o:p></o:p> sub_rule_depth = 0;<o:p></o:p> - sub_rule_index = find_previous_rule(i_lpm, ip, depth, &sub_rule_depth);<o:p></o:p> + found = find_previous_rule(lpm, ip, depth, &sub_rule_hop, &sub_rule_depth);<o:p></o:p> <o:p></o:p> /*<o:p></o:p> * If the input depth value is less than 25 use function<o:p></o:p> * delete_depth_small otherwise use delete_depth_big.<o:p></o:p> */<o:p></o:p> if (depth <= MAX_DEPTH_TBL24) {<o:p></o:p> - return delete_depth_small(i_lpm, ip_masked, depth,<o:p></o:p> - sub_rule_index, sub_rule_depth);<o:p></o:p> - } else { /* If depth > MAX_DEPTH_TBL24 */<o:p></o:p> - return delete_depth_big(i_lpm, ip_masked, depth, sub_rule_index,<o:p></o:p> - sub_rule_depth);<o:p></o:p> + return delete_depth_small(i_lpm, ip_masked, depth, found,<o:p></o:p> + sub_rule_hop, sub_rule_depth);<o:p></o:p> + } else {<o:p></o:p> + return delete_depth_big(i_lpm, ip_masked, depth, found,<o:p></o:p> + sub_rule_hop, sub_rule_depth);<o:p></o:p> }<o:p></o:p> }<o:p></o:p> <o:p></o:p> @@ -1205,6 +1184,7 @@ rte_lpm_delete_all(struct rte_lpm *lpm)<o:p></o:p> i_lpm = container_of(lpm, struct __rte_lpm, lpm);<o:p></o:p> /* Zero rule information. */<o:p></o:p> memset(i_lpm->rule_info, 0, sizeof(i_lpm->rule_info));<o:p></o:p> + i_lpm->used_rules = 0;<o:p></o:p> <o:p></o:p> /* Zero tbl24. */<o:p></o:p> memset(i_lpm->lpm.tbl24, 0, sizeof(i_lpm->lpm.tbl24));<o:p></o:p> @@ -1214,5 +1194,5 @@ rte_lpm_delete_all(struct rte_lpm *lpm)<o:p></o:p> * RTE_LPM_TBL8_GROUP_NUM_ENTRIES * i_lpm->number_tbl8s);<o:p></o:p> <o:p></o:p> /* Delete all rules form the rules table. */<o:p></o:p> - memset(i_lpm->rules_tbl, 0, sizeof(i_lpm->rules_tbl[0]) * i_lpm->max_rules);<o:p></o:p> + rte_hash_reset(i_lpm->rules_tbl);<o:p></o:p> }<o:p></o:p> diff --git a/lib/lpm/rte_lpm.h b/lib/lpm/rte_lpm.h<o:p></o:p> index 75e27ff164..605445f3a7 100644<o:p></o:p> --- a/lib/lpm/rte_lpm.h<o:p></o:p> +++ b/lib/lpm/rte_lpm.h<o:p></o:p> @@ -108,6 +108,12 @@ struct rte_lpm_tbl_entry {<o:p></o:p> <o:p></o:p> #endif<o:p></o:p> <o:p></o:p> +/** Rules tbl entry key. */<o:p></o:p> +struct rte_lpm_rule_key {<o:p></o:p> + uint32_t ip; /**< Rule IP address. */<o:p></o:p> + uint32_t depth; /**< Rule depth. */<o:p></o:p> +};<o:p></o:p> +<o:p></o:p> /** LPM configuration structure. */<o:p></o:p> struct rte_lpm_config {<o:p></o:p> uint32_t max_rules; /**< Max number of rules. */<o:p></o:p> -- <o:p></o:p> 2.42.0<o:p></o:p> <o:p> </o:p> </div> </body> </html>