On Mon, Jul 02, 2018 at 07:42:11PM +0300, Alex Kiselev wrote:
> There are two major problems with the library:
> first, there is no need to rebuild the whole LPM tree
> when a rule is deleted and second, due to the current
> rules algorithm with complexity O(n) it's almost
> impossible to deal with large rule sets (50k or so rules).
> This patch addresses those two issues.
>
> Signed-off-by: Alex Kiselev <a...@therouter.net>
Hi,
Some initial review comments inline below
/Bruce
> ---
> lib/librte_lpm/rte_lpm6.c | 1073
> ++++++++++++++++++++++++++++++++++-----------
> 1 file changed, 816 insertions(+), 257 deletions(-)
>
> diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
> index 149677eb1..438db0831 100644
> --- a/lib/librte_lpm/rte_lpm6.c
> +++ b/lib/librte_lpm/rte_lpm6.c
> @@ -21,6 +21,10 @@
> #include <rte_errno.h>
> #include <rte_rwlock.h>
> #include <rte_spinlock.h>
> +#include <rte_hash.h>
> +#include <rte_hash_crc.h>
> +#include <rte_mempool.h>
> +#include <assert.h>
>
> #include "rte_lpm6.h"
>
> @@ -37,6 +41,9 @@
> #define BYTE_SIZE 8
> #define BYTES2_SIZE 16
>
> +#define RULE_HASH_TABLE_EXTRA_SPACE 256
> +#define TBL24_IND UINT32_MAX
> +
> #define lpm6_tbl8_gindex next_hop
>
> /** Flags for setting an entry as valid/invalid. */
> @@ -70,6 +77,23 @@ struct rte_lpm6_rule {
> uint8_t depth; /**< Rule depth. */
> };
>
> +/** Rules tbl entry key. */
> +struct rte_lpm6_rule_key {
> + uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
> + uint8_t depth; /**< Rule depth. */
> +};
> +
> +/* Header of tbl8 */
> +struct rte_lpm_tbl8_hdr {
> + uint32_t owner_tbl_ind; /**< owner table: TBL24_IND if owner is tbl24,
> + * otherwise index of tbl8
> + */
> + uint32_t owner_entry_ind; /**< index of the owner table entry where
> + * pointer to the tbl8 is stored
> + */
> + uint32_t ref_cnt; /**< table reference counter */
> +};
> +
> /** LPM6 structure. */
> struct rte_lpm6 {
> /* LPM metadata. */
> @@ -77,12 +101,18 @@ struct rte_lpm6 {
> uint32_t max_rules; /**< Max number of rules. */
> uint32_t used_rules; /**< Used rules so far. */
> uint32_t number_tbl8s; /**< Number of tbl8s to allocate. */
> - uint32_t next_tbl8; /**< Next tbl8 to be used. */
>
> /* LPM Tables. */
> - struct rte_lpm6_rule *rules_tbl; /**< LPM rules. */
> + struct rte_mempool *rules_pool; /**< LPM rules mempool. */
> + struct rte_hash *rules_tbl; /**< LPM rules. */
> struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
> __rte_cache_aligned; /**< LPM tbl24 table. */
> +
> + uint32_t *tbl8_pool; /**< pool of indexes of free tbl8s */
> + uint32_t tbl8_pool_pos; /**< current position in the tbl8 pool */
> +
> + struct rte_lpm_tbl8_hdr *tbl8_hdrs; /* array of tbl8 headers */
> +
> struct rte_lpm6_tbl_entry tbl8[0]
> __rte_cache_aligned; /**< LPM tbl8 table. */
> };
> @@ -93,22 +123,130 @@ struct rte_lpm6 {
> * and set the rest to 0.
> */
> static inline void
> -mask_ip(uint8_t *ip, uint8_t depth)
> +ip6_mask_addr(uint8_t *ip, uint8_t depth)
> {
> - int16_t part_depth, mask;
> - int i;
> + int16_t part_depth, mask;
> + int i;
>
> - part_depth = depth;
> + part_depth = depth;
>
> - for (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {
> - if (part_depth < BYTE_SIZE && part_depth >= 0) {
> - mask = (uint16_t)(~(UINT8_MAX >> part_depth));
> - ip[i] = (uint8_t)(ip[i] & mask);
> - } else if (part_depth < 0) {
> - ip[i] = 0;
> - }
> - part_depth -= BYTE_SIZE;
> - }
> + for (i = 0; i < RTE_LPM6_IPV6_ADDR_SIZE; i++) {
> + if (part_depth < BYTE_SIZE && part_depth >= 0) {
> + mask = (uint16_t)(~(UINT8_MAX >> part_depth));
> + ip[i] = (uint8_t)(ip[i] & mask);
> + } else if (part_depth < 0)
> + ip[i] = 0;
> +
> + part_depth -= BYTE_SIZE;
> + }
> +}
This block is just a whitespace cleanup, as far as I can see. If there are
other little cleanups like that as part of this set, it would be nice to
have them as a separate initial patch, to make it easier to review the more
complicated changes.
> +
> +/* copy ipv6 address */
> +static inline void
> +ip6_copy_addr(uint8_t *dst, const uint8_t *src)
> +{
> + rte_memcpy(dst, src, RTE_LPM6_IPV6_ADDR_SIZE);
> +}
> +
> +/*
> + * LPM6 rule hash function
> + */
> +static inline uint32_t
> +rule_hash_crc(const void *data, __rte_unused uint32_t data_len,
> + uint32_t init_val)
> +{
> + return rte_hash_crc(data, sizeof(struct rte_lpm6_rule_key), init_val);
> +}
Why bother passing in the length and making the data a void pointer. Why
not just have the prototype:
rule_hash_crc(struct rte_lpm6_rule_key *data, uint32_t init_val)
> +
> +/*
> + * Init pool of free tbl8 indexes
> + */
> +static void
> +tbl8_pool_init(struct rte_lpm6 *lpm)
> +{
> + /* put entire range of indexes to the tbl8 pool */
> + uint32_t i;
> + for (i = 0; i < lpm->number_tbl8s; i++)
> + lpm->tbl8_pool[i] = i;
> +
> + lpm->tbl8_pool_pos = 0;
> +}
> +
> +/*
> + * Get an index of a free tbl8 from the pool
> + */
> +static inline uint32_t
> +tbl8_get(struct rte_lpm6 *lpm, uint32_t *tbl8_ind)
> +{
> + if (lpm->tbl8_pool_pos == lpm->number_tbl8s)
> + /* no more free tbl8 */
> + return -ENOSPC;
> +
> + /* next index */
> + *tbl8_ind = lpm->tbl8_pool[lpm->tbl8_pool_pos++];
> + return 0;
> +}
> +
> +/*
> + * Put an index of a free tbl8 back to the pool
> + */
> +static inline uint32_t
> +tbl8_put(struct rte_lpm6 *lpm, uint32_t tbl8_ind)
> +{
> + if (lpm->tbl8_pool_pos == 0)
> + /* pool is full */
> + return -ENOSPC;
> +
> + lpm->tbl8_pool[--lpm->tbl8_pool_pos] = tbl8_ind;
> + return 0;
> +}
> +
> +/*
> + * Returns number of tbl8s awailable in the pool
Typo: available
> + */
> +static inline uint32_t
> +tbl8_available(struct rte_lpm6 *lpm)
> +{
> + return lpm->number_tbl8s - lpm->tbl8_pool_pos;
> +}
> +
> +/*
> + * Init a rule key.
> + * note that ip must be already masked
> + */
> +static inline void
> +rule_key_init(struct rte_lpm6_rule_key *key, uint8_t *ip, uint8_t depth)
> +{
> + ip6_copy_addr(key->ip, ip);
> + key->depth = depth;
> +}
> +
> +/*
> + * Recreate the entire LPM tree by reinserting all rules
> + */
> +static void
> +recreate_lpm(struct rte_lpm6 *lpm)
> +{
> + struct rte_lpm6_rule *rule;
> + struct rte_lpm6_rule *rule_key;
> + uint32_t iter = 0;
> + while (rte_hash_iterate(lpm->rules_tbl, (const void **) &rule_key,
> + (void **) &rule, &iter) >= 0)
> + rte_lpm6_add(lpm, rule->ip, rule->depth, rule->next_hop);
> +}
> +
> +/*
> + * Free all rules
> + */
> +static void
> +rules_free(struct rte_lpm6 *lpm)
> +{
> + struct rte_lpm6_rule *rule;
> + struct rte_lpm6_rule *rule_key;
> + uint32_t iter = 0;
> + while (rte_hash_iterate(lpm->rules_tbl, (const void **) &rule_key,
> + (void **) &rule, &iter) >= 0)
> + rte_mempool_put(lpm->rules_pool, rule);
> }
>
> /*
> @@ -121,7 +259,7 @@ rte_lpm6_create(const char *name, int socket_id,
> char mem_name[RTE_LPM6_NAMESIZE];
> struct rte_lpm6 *lpm = NULL;
> struct rte_tailq_entry *te;
> - uint64_t mem_size, rules_size;
> + uint64_t mem_size;
> struct rte_lpm6_list *lpm_list;
>
> lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
> @@ -136,12 +274,72 @@ rte_lpm6_create(const char *name, int socket_id,
> return NULL;
> }
>
> + struct rte_mempool *rules_mempool = NULL;
> + struct rte_hash *rules_tbl = NULL;
> + uint32_t *tbl8_pool = NULL;
> + struct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;
> +
> + /* allocate rules mempool */
> + snprintf(mem_name, sizeof(mem_name), "LRM_%s", name);
LRM == "LPM Rules Mempool" I assume? [Not that it actually matters]
> + rules_mempool = rte_mempool_create(mem_name,
> + config->max_rules, sizeof(struct rte_lpm6_rule), 0, 0,
> + NULL, NULL, NULL, NULL, socket_id,
> + MEMPOOL_F_NO_CACHE_ALIGN);
> + if (rules_mempool == NULL) {
> + RTE_LOG(ERR, LPM, "LPM rules mempool allocation failed: %s
> (%d)",
> + rte_strerror(rte_errno), rte_errno);
> + rte_errno = ENOMEM;
> + goto fail_wo_unlock;
> + }
> +
> + /* create rules hash table */
> + snprintf(mem_name, sizeof(mem_name), "LRH_%s", name);
> +
> + struct rte_hash_parameters rule_hash_tbl_params = {
> + .entries = config->max_rules + RULE_HASH_TABLE_EXTRA_SPACE,
Are 256 extra slots going to be enough here? Would it be safer to multiply
max_rules by e.g. 1.2 or similar?
> + .key_len = sizeof(struct rte_lpm6_rule_key),
> + .hash_func = rule_hash_crc,
Given that this is not for data plane use, it might be better to use jhash
as the hash function. It's slower, but it does give a better rule
distribution so allows more compact tables.
> + .hash_func_init_val = 0,
> + .name = mem_name,
> + .reserved = 0,
> + .socket_id = socket_id,
> + .extra_flag = 0
> + };
> +
> + rules_tbl = rte_hash_create(&rule_hash_tbl_params);
> + if (rules_tbl == NULL) {
> + RTE_LOG(ERR, LPM, "LPM rules hash table allocation failed: %s
> (%d)",
> + rte_strerror(rte_errno), rte_errno);
> + goto fail_wo_unlock;
> + }
> +
> + /* allocate tbl8 indexes pool */
> + tbl8_pool = rte_malloc(NULL,
> + sizeof(uint32_t) * config->number_tbl8s,
> + RTE_CACHE_LINE_SIZE);
> + if (tbl8_pool == NULL) {
> + RTE_LOG(ERR, LPM, "LPM tbl8 pool allocation failed: %s (%d)",
> + rte_strerror(rte_errno), rte_errno);
> + rte_errno = ENOMEM;
> + goto fail_wo_unlock;
> + }
> +
> + /* allocate tbl8 headers */
> + tbl8_hdrs = rte_malloc(NULL,
> + sizeof(struct rte_lpm_tbl8_hdr) * config->number_tbl8s,
> + RTE_CACHE_LINE_SIZE);
> + if (tbl8_hdrs == NULL) {
> + RTE_LOG(ERR, LPM, "LPM tbl8 headers allocation failed: %s (%d)",
> + rte_strerror(rte_errno), rte_errno);
> + rte_errno = ENOMEM;
> + goto fail_wo_unlock;
> + }
> +
> snprintf(mem_name, sizeof(mem_name), "LPM_%s", name);
>
> /* Determine the amount of memory to allocate. */
> mem_size = sizeof(*lpm) + (sizeof(lpm->tbl8[0]) *
> RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * config->number_tbl8s);
> - rules_size = sizeof(struct rte_lpm6_rule) * config->max_rules;
>
> rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
>
> @@ -154,7 +352,7 @@ rte_lpm6_create(const char *name, int socket_id,
> lpm = NULL;
> if (te != NULL) {
> rte_errno = EEXIST;
> - goto exit;
> + goto fail;
> }
>
> /* allocate tailq entry */
> @@ -162,30 +360,18 @@ rte_lpm6_create(const char *name, int socket_id,
> if (te == NULL) {
> RTE_LOG(ERR, LPM, "Failed to allocate tailq entry!\n");
> rte_errno = ENOMEM;
> - goto exit;
> + goto fail;
> }
>
> /* Allocate memory to store the LPM data structures. */
> - lpm = rte_zmalloc_socket(mem_name, (size_t)mem_size,
> + lpm = (struct rte_lpm6 *)rte_zmalloc_socket(mem_name, (size_t)mem_size,
> RTE_CACHE_LINE_SIZE, socket_id);
>
> if (lpm == NULL) {
> RTE_LOG(ERR, LPM, "LPM memory allocation failed\n");
> rte_free(te);
> rte_errno = ENOMEM;
> - goto exit;
> - }
> -
> - lpm->rules_tbl = rte_zmalloc_socket(NULL,
> - (size_t)rules_size, RTE_CACHE_LINE_SIZE, socket_id);
> -
> - if (lpm->rules_tbl == NULL) {
> - RTE_LOG(ERR, LPM, "LPM rules_tbl allocation failed\n");
> - rte_free(lpm);
> - lpm = NULL;
> - rte_free(te);
> - rte_errno = ENOMEM;
> - goto exit;
> + goto fail;
> }
>
> /* Save user arguments. */
> @@ -193,14 +379,37 @@ rte_lpm6_create(const char *name, int socket_id,
> lpm->number_tbl8s = config->number_tbl8s;
> snprintf(lpm->name, sizeof(lpm->name), "%s", name);
>
> + lpm->rules_tbl = rules_tbl;
> + lpm->tbl8_pool = tbl8_pool;
> + lpm->tbl8_hdrs = tbl8_hdrs;
> + lpm->rules_pool = rules_mempool;
> +
> + /* init the stack */
> + tbl8_pool_init(lpm);
> +
> te->data = (void *) lpm;
>
> TAILQ_INSERT_TAIL(lpm_list, te, next);
> + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> + return lpm;
>
> -exit:
> +fail:
> rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
>
> - return lpm;
> +fail_wo_unlock:
> + if (rules_mempool != NULL)
> + rte_mempool_free(rules_mempool);
> +
> + if (tbl8_hdrs != NULL)
> + rte_free(tbl8_hdrs);
> +
> + if (tbl8_pool != NULL)
> + rte_free(tbl8_pool);
> +
> + if (rules_tbl != NULL)
> + rte_hash_free(rules_tbl);
> +
rte_free doesn't have an issue with taking NULL as parameter, so you can
omit the various NULL checks and just have the series of free calls.
> + return NULL;
> }
>
> /*
> @@ -259,50 +468,93 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
>
> rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
>
> - rte_free(lpm->rules_tbl);
> + rte_mempool_free(lpm->rules_pool);
> + rte_free(lpm->tbl8_hdrs);
> + rte_free(lpm->tbl8_pool);
> + rte_hash_free(lpm->rules_tbl);
> rte_free(lpm);
> rte_free(te);
> }
>
> +/* Find a rule */
> +static inline struct rte_lpm6_rule*
> +rule_find_with_key(struct rte_lpm6 *lpm,
> + const struct rte_lpm6_rule_key *rule_key)
> +{
> + /* look for a rule */
> + struct rte_lpm6_rule *rule;
> + int ret = rte_hash_lookup_data(lpm->rules_tbl,
> + (const void *) rule_key, (void **) &rule);
> + return (ret >= 0) ? rule : NULL;
> +}
> +
> +/* Find a rule */
> +static struct rte_lpm6_rule*
> +rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
> +{
> + /* init a rule key */
> + struct rte_lpm6_rule_key rule_key;
> + rule_key_init(&rule_key, ip, depth);
> +
> + return rule_find_with_key(lpm, &rule_key);
> +}
> +
> /*
> * Checks if a rule already exists in the rules table and updates
> * the nexthop if so. Otherwise it adds a new rule if enough space is
> available.
> + *
> + * Returns:
> + * 0 - next hop of existed rule is updated
> + * 1 - new rule successfuly added
> + * <0 - error
> */
> -static inline int32_t
> -rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint32_t next_hop, uint8_t depth)
> +static inline int
> +rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)
> {
> - uint32_t rule_index;
> + /* init a rule key */
> + struct rte_lpm6_rule_key rule_key;
> + rule_key_init(&rule_key, ip, depth);
>
> /* Scan through rule list to see if rule already exists. */
> - for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
> -
> - /* If rule already exists update its next_hop and return. */
> - if ((memcmp (lpm->rules_tbl[rule_index].ip, ip,
> - RTE_LPM6_IPV6_ADDR_SIZE) == 0) &&
> - lpm->rules_tbl[rule_index].depth == depth) {
> - lpm->rules_tbl[rule_index].next_hop = next_hop;
> + struct rte_lpm6_rule *rule = rule_find_with_key(lpm, &rule_key);
>
> - return rule_index;
> - }
> + /* If rule already exists update its next_hop and return. */
> + if (rule != NULL) {
> + rule->next_hop = next_hop;
> + return 0;
> }
>
> /*
> * If rule does not exist check if there is space to add a new rule to
> * this rule group. If there is no space return error.
> */
> - if (lpm->used_rules == lpm->max_rules) {
> + if (lpm->used_rules == lpm->max_rules)
> return -ENOSPC;
> - }
>
> - /* If there is space for the new rule add it. */
> - rte_memcpy(lpm->rules_tbl[rule_index].ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
> - lpm->rules_tbl[rule_index].next_hop = next_hop;
> - lpm->rules_tbl[rule_index].depth = depth;
> + /*
> + * If there is space for the new rule add it.
> + */
> +
> + /* get a new rule */
> + int ret = rte_mempool_get(lpm->rules_pool, (void **) &rule);
> + if (ret < 0)
> + return ret;
> +
> + /* init the rule */
> + rule->depth = depth;
> + ip6_copy_addr(rule->ip, ip);
> + rule->next_hop = next_hop;
> +
> + /* add the rule */
> + ret = rte_hash_add_key_data(lpm->rules_tbl, &rule_key, rule);
> + if (ret < 0) {
> + rte_mempool_put(lpm->rules_pool, rule);
> + return ret;
> + }
>
> /* Increment the used rules counter for this rule group. */
> lpm->used_rules++;
> -
> - return rule_index;
> + return 1;
> }
>
> /*
> @@ -311,24 +563,24 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint32_t
> next_hop, uint8_t depth)
> * in the IP address returns a match.
> */
> static void
> -expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
> - uint32_t next_hop)
> +expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t old_depth,
> + uint8_t new_depth, uint32_t next_hop, uint8_t valid)
Is this change to have separate old depths and new depths a bug fix for an
existing issue, or just a change needed due to the rework below?
> {
> uint32_t tbl8_group_end, tbl8_gindex_next, j;
>
> tbl8_group_end = tbl8_gindex + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
>
> struct rte_lpm6_tbl_entry new_tbl8_entry = {
> - .valid = VALID,
> - .valid_group = VALID,
> - .depth = depth,
> + .valid = valid,
> + .valid_group = valid,
> + .depth = new_depth,
> .next_hop = next_hop,
> .ext_entry = 0,
> };
>
> for (j = tbl8_gindex; j < tbl8_group_end; j++) {
> if (!lpm->tbl8[j].valid || (lpm->tbl8[j].ext_entry == 0
> - && lpm->tbl8[j].depth <= depth)) {
> + && lpm->tbl8[j].depth <= old_depth)) {
>
> lpm->tbl8[j] = new_tbl8_entry;
>
> @@ -336,11 +588,101 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t
> tbl8_gindex, uint8_t depth,
>
> tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
> * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
> - expand_rule(lpm, tbl8_gindex_next, depth, next_hop);
> + expand_rule(lpm, tbl8_gindex_next, old_depth, new_depth,
> + next_hop, valid);
> }
> }
> }
>
> +/*
> + * Init a tbl8 header
> + */
> +static inline void
> +init_tbl8_header(struct rte_lpm6 *lpm, uint32_t tbl_ind,
> + uint32_t owner_tbl_ind, uint32_t owner_entry_ind)
> +{
> + struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];
> + tbl_hdr->owner_tbl_ind = owner_tbl_ind;
> + tbl_hdr->owner_entry_ind = owner_entry_ind;
> + tbl_hdr->ref_cnt = 0;
> +}
> +
> +/*
> + * Calculate index to the table based on the number and position
> + * of the bytes being inspected in this step.
> + */
> +static uint32_t
> +get_bitshift(const uint8_t *ip, uint8_t first_byte, uint8_t bytes)
> +{
> + uint32_t entry_ind, i;
> + int8_t bitshift;
> +
> + entry_ind = 0;
> + for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {
> + bitshift = (int8_t)((bytes - i)*BYTE_SIZE);
> +
> + if (bitshift < 0)
> + bitshift = 0;
> + entry_ind = entry_ind | ip[i-1] << bitshift;
> + }
> +
> + return entry_ind;
> +}
> +
> +/*
> + * Simulate adding a new route to the LPM counting number
> + * of new tables that will be needed
> + *
> + * It returns 0 on success, or 1 if
> + * the process needs to be continued by calling the function again.
> + */
> +static inline int
> +simulate_add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
> + struct rte_lpm6_tbl_entry **next_tbl, const uint8_t *ip,
> + uint8_t bytes, uint8_t first_byte, uint8_t depth,
> + uint32_t *need_tbl_nb)
> +{
> + uint32_t entry_ind;
> + uint8_t bits_covered;
> + uint32_t next_tbl_ind;
> +
> + /*
> + * Calculate index to the table based on the number and position
> + * of the bytes being inspected in this step.
> + */
> + entry_ind = get_bitshift(ip, first_byte, bytes);
> +
> + /* Number of bits covered in this step */
> + bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
> +
> + if (depth <= bits_covered) {
> + *need_tbl_nb = 0;
> + return 0;
> + }
> +
> + if (tbl[entry_ind].valid == 0 || tbl[entry_ind].ext_entry == 0) {
> + /* from this point on a new table is needed on each level
> + * that is not covered yet
> + */
> + depth -= bits_covered;
> + uint32_t cnt = depth >> 3; /* depth / 3 */
depth / 8, not / 3. Perhaps "/ BYTE_SIZE" might be best.
> + if (depth & 7) /* 0b00000111 */
> + /* if depth % 8 > 0 then one more table is needed
> + * for those last bits
> + */
> + cnt++;
> +
> + *need_tbl_nb = cnt;
> + return 0;
> + }
> +
> + next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;
> + *next_tbl = &(lpm->tbl8[next_tbl_ind *
> + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
> + *need_tbl_nb = 0;
> + return 1;
> +}
> +
> /*
> * Partially adds a new route to the data structure (tbl24+tbl8s).
> * It returns 0 on success, a negative number on failure, or 1 if
> @@ -348,25 +690,21 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex,
> uint8_t depth,
> */
> static inline int
> add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
> - struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip, uint8_t
> bytes,
> - uint8_t first_byte, uint8_t depth, uint32_t next_hop)
> + uint32_t tbl_ind, struct rte_lpm6_tbl_entry **next_tbl,
> + uint32_t *next_tbl_ind, uint8_t *ip, uint8_t bytes,
> + uint8_t first_byte, uint8_t depth, uint32_t next_hop,
> + uint8_t is_new_rule)
> {
> - uint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;
> - int32_t tbl8_gindex;
> - int8_t bitshift;
> + uint32_t entry_ind, tbl_range, tbl8_group_start, tbl8_group_end, i;
> + uint32_t tbl8_gindex;
> uint8_t bits_covered;
> + int ret;
>
> /*
> * Calculate index to the table based on the number and position
> * of the bytes being inspected in this step.
> */
> - tbl_index = 0;
> - for (i = first_byte; i < (uint32_t)(first_byte + bytes); i++) {
> - bitshift = (int8_t)((bytes - i)*BYTE_SIZE);
> -
> - if (bitshift < 0) bitshift = 0;
> - tbl_index = tbl_index | ip[i-1] << bitshift;
> - }
> + entry_ind = get_bitshift(ip, first_byte, bytes);
>
> /* Number of bits covered in this step */
> bits_covered = (uint8_t)((bytes+first_byte-1)*BYTE_SIZE);
> @@ -378,7 +716,7 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry
> *tbl,
> if (depth <= bits_covered) {
> tbl_range = 1 << (bits_covered - depth);
>
> - for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
> + for (i = entry_ind; i < (entry_ind + tbl_range); i++) {
> if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
> tbl[i].depth <= depth)) {
>
> @@ -400,10 +738,15 @@ add_step(struct rte_lpm6 *lpm, struct
> rte_lpm6_tbl_entry *tbl,
> */
> tbl8_gindex = tbl[i].lpm6_tbl8_gindex *
> RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
> - expand_rule(lpm, tbl8_gindex, depth, next_hop);
> + expand_rule(lpm, tbl8_gindex, depth, depth,
> + next_hop, VALID);
> }
> }
>
> + /* update tbl8 rule reference counter */
> + if (tbl_ind != TBL24_IND && is_new_rule)
> + lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
> +
> return 0;
> }
> /*
> @@ -412,12 +755,24 @@ add_step(struct rte_lpm6 *lpm, struct
> rte_lpm6_tbl_entry *tbl,
> */
> else {
> /* If it's invalid a new tbl8 is needed */
> - if (!tbl[tbl_index].valid) {
> - if (lpm->next_tbl8 < lpm->number_tbl8s)
> - tbl8_gindex = (lpm->next_tbl8)++;
> - else
> + if (!tbl[entry_ind].valid) {
> + /* get a new table */
> + ret = tbl8_get(lpm, &tbl8_gindex);
> + if (ret != 0)
> return -ENOSPC;
>
> + /* invalidate all new tbl8 entries */
> + tbl8_group_start = tbl8_gindex *
> + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
> + memset(&lpm->tbl8[tbl8_group_start], 0,
> + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);
> +
> + /* init the new table's header:
> + * save the reference to the owner table
> + */
> + init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);
> +
> + /* reference to a new tbl8 */
> struct rte_lpm6_tbl_entry new_tbl_entry = {
> .lpm6_tbl8_gindex = tbl8_gindex,
> .depth = 0,
> @@ -426,17 +781,20 @@ add_step(struct rte_lpm6 *lpm, struct
> rte_lpm6_tbl_entry *tbl,
> .ext_entry = 1,
> };
>
> - tbl[tbl_index] = new_tbl_entry;
> + tbl[entry_ind] = new_tbl_entry;
> +
> + /* update the current table's reference counter */
> + if (tbl_ind != TBL24_IND)
> + lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
> }
> /*
> - * If it's valid but not extended the rule that was stored *
> + * If it's valid but not extended the rule that was stored
> * here needs to be moved to the next table.
> */
> - else if (tbl[tbl_index].ext_entry == 0) {
> - /* Search for free tbl8 group. */
> - if (lpm->next_tbl8 < lpm->number_tbl8s)
> - tbl8_gindex = (lpm->next_tbl8)++;
> - else
> + else if (tbl[entry_ind].ext_entry == 0) {
> + /* get a new tbl8 index */
> + ret = tbl8_get(lpm, &tbl8_gindex);
> + if (ret != 0)
> return -ENOSPC;
>
> tbl8_group_start = tbl8_gindex *
> @@ -444,13 +802,22 @@ add_step(struct rte_lpm6 *lpm, struct
> rte_lpm6_tbl_entry *tbl,
> tbl8_group_end = tbl8_group_start +
> RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
>
> + struct rte_lpm6_tbl_entry tbl_entry = {
> + .next_hop = tbl[entry_ind].next_hop,
> + .depth = tbl[entry_ind].depth,
> + .valid = VALID,
> + .valid_group = VALID,
> + .ext_entry = 0
> + };
> +
> /* Populate new tbl8 with tbl value. */
> - for (i = tbl8_group_start; i < tbl8_group_end; i++) {
> - lpm->tbl8[i].valid = VALID;
> - lpm->tbl8[i].depth = tbl[tbl_index].depth;
> - lpm->tbl8[i].next_hop = tbl[tbl_index].next_hop;
> - lpm->tbl8[i].ext_entry = 0;
> - }
> + for (i = tbl8_group_start; i < tbl8_group_end; i++)
> + lpm->tbl8[i] = tbl_entry;
> +
> + /* init the new table's header:
> + * save the reference to the owner table
> + */
> + init_tbl8_header(lpm, tbl8_gindex, tbl_ind, entry_ind);
>
> /*
> * Update tbl entry to point to new tbl8 entry. Note:
> The
> @@ -465,11 +832,16 @@ add_step(struct rte_lpm6 *lpm, struct
> rte_lpm6_tbl_entry *tbl,
> .ext_entry = 1,
> };
>
> - tbl[tbl_index] = new_tbl_entry;
> + tbl[entry_ind] = new_tbl_entry;
> +
> + /* update the current table's reference counter */
> + if (tbl_ind != TBL24_IND)
> + lpm->tbl8_hdrs[tbl_ind].ref_cnt++;
> }
>
> - *tbl_next = &(lpm->tbl8[tbl[tbl_index].lpm6_tbl8_gindex *
> - RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
> + *next_tbl_ind = tbl[entry_ind].lpm6_tbl8_gindex;
> + *next_tbl = &(lpm->tbl8[*next_tbl_ind *
> + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES]);
> }
>
> return 1;
> @@ -486,13 +858,55 @@ rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip,
> uint8_t depth,
> }
> VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0);
>
> +
> +/*
> + * Simulate adding a route to LPM
> + *
> + * Returns:
> + * 0 if success
> + * -ENOSPC not enought tbl8 left
> + */
> +static int
> +simulate_add(struct rte_lpm6 *lpm, const uint8_t *masked_ip, uint8_t depth)
> +{
> + struct rte_lpm6_tbl_entry *tbl;
> + struct rte_lpm6_tbl_entry *tbl_next = NULL;
> + int ret, i;
> +
> + /* number of new tables needed for a step */
> + uint32_t need_tbl_nb;
> + /* total number of new tables needed */
> + uint32_t total_need_tbl_nb;
> +
> + /* Inspect the first three bytes through tbl24 on the first step. */
> + ret = simulate_add_step(lpm, lpm->tbl24, &tbl_next, masked_ip,
> + ADD_FIRST_BYTE, 1, depth, &need_tbl_nb);
> + total_need_tbl_nb = need_tbl_nb;
> + /*
> + * Inspect one by one the rest of the bytes until
> + * the process is completed.
> + */
> + for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && ret == 1; i++) {
> + tbl = tbl_next;
> + ret = simulate_add_step(lpm, tbl, &tbl_next, masked_ip, 1,
> + (uint8_t)(i+1), depth, &need_tbl_nb);
> + total_need_tbl_nb += need_tbl_nb;
> + }
> +
> + if (tbl8_available(lpm) < total_need_tbl_nb)
> + /* not enought tbl8 to add a rule */
> + return -ENOSPC;
> +
> + return 0;
> +}
> +
> int
> rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
> uint32_t next_hop)
> {
> struct rte_lpm6_tbl_entry *tbl;
> struct rte_lpm6_tbl_entry *tbl_next = NULL;
> - int32_t rule_index;
> + uint32_t tbl_next_num;
> int status;
> uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
> int i;
> @@ -502,26 +916,26 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip,
> uint8_t depth,
> return -EINVAL;
>
> /* Copy the IP and mask it to avoid modifying user's input data. */
> - memcpy(masked_ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
> - mask_ip(masked_ip, depth);
> + ip6_copy_addr(masked_ip, ip);
> + ip6_mask_addr(masked_ip, depth);
>
> /* Add the rule to the rule table. */
> - rule_index = rule_add(lpm, masked_ip, next_hop, depth);
> -
> + int is_new_rule = rule_add(lpm, masked_ip, depth, next_hop);
> /* If there is no space available for new rule return error. */
> - if (rule_index < 0) {
> - return rule_index;
> - }
> + if (is_new_rule < 0)
> + return is_new_rule;
> +
> + /* Simulate adding a new route */
> + int ret = simulate_add(lpm, masked_ip, depth);
> + if (ret < 0)
> + return ret;
Do we need any rollback here for the rule that was just added?
>
> /* Inspect the first three bytes through tbl24 on the first step. */
> tbl = lpm->tbl24;
> - status = add_step (lpm, tbl, &tbl_next, masked_ip, ADD_FIRST_BYTE, 1,
> - depth, next_hop);
> - if (status < 0) {
> - rte_lpm6_delete(lpm, masked_ip, depth);
> -
> - return status;
> - }
> + status = add_step(lpm, tbl, TBL24_IND, &tbl_next, &tbl_next_num,
> + masked_ip, ADD_FIRST_BYTE, 1, depth, next_hop,
> + is_new_rule);
> + assert(status >= 0);
>
> /*
> * Inspect one by one the rest of the bytes until
> @@ -529,13 +943,10 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip,
> uint8_t depth,
> */
> for (i = ADD_FIRST_BYTE; i < RTE_LPM6_IPV6_ADDR_SIZE && status == 1;
> i++) {
> tbl = tbl_next;
> - status = add_step (lpm, tbl, &tbl_next, masked_ip, 1,
> (uint8_t)(i+1),
> - depth, next_hop);
> - if (status < 0) {
> - rte_lpm6_delete(lpm, masked_ip, depth);
> -
> - return status;
> - }
> + status = add_step(lpm, tbl, tbl_next_num, &tbl_next,
> + &tbl_next_num, masked_ip, 1, (uint8_t)(i+1),
> + depth, next_hop, is_new_rule);
> + assert(status >= 0);
> }
>
> return status;
> @@ -610,9 +1021,8 @@ rte_lpm6_lookup_v1705(const struct rte_lpm6 *lpm,
> uint8_t *ip,
> uint32_t tbl24_index;
>
> /* DEBUG: Check user input arguments. */
> - if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL)) {
> + if ((lpm == NULL) || (ip == NULL) || (next_hop == NULL))
> return -EINVAL;
> - }
>
> first_byte = LOOKUP_FIRST_BYTE;
> tbl24_index = (ip[0] << BYTES2_SIZE) | (ip[1] << BYTE_SIZE) | ip[2];
> @@ -648,9 +1058,8 @@ rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,
> int status;
>
> /* DEBUG: Check user input arguments. */
> - if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL)) {
> + if ((lpm == NULL) || (ips == NULL) || (next_hops == NULL))
> return -EINVAL;
> - }
>
> for (i = 0; i < n; i++) {
> first_byte = LOOKUP_FIRST_BYTE;
> @@ -724,30 +1133,6 @@ MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const
> struct rte_lpm6 *lpm,
> int32_t *next_hops, unsigned int n),
> rte_lpm6_lookup_bulk_func_v1705);
>
> -/*
> - * Finds a rule in rule table.
> - * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
> - */
> -static inline int32_t
> -rule_find(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
> -{
> - uint32_t rule_index;
> -
> - /* Scan used rules at given depth to find rule. */
> - for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
> - /* If rule is found return the rule index. */
> - if ((memcmp (lpm->rules_tbl[rule_index].ip, ip,
> - RTE_LPM6_IPV6_ADDR_SIZE) == 0) &&
> - lpm->rules_tbl[rule_index].depth == depth) {
> -
> - return rule_index;
> - }
> - }
> -
> - /* If rule is not found return -ENOENT. */
> - return -ENOENT;
> -}
> -
> /*
> * Look for a rule in the high-level rules table
> */
> @@ -775,23 +1160,20 @@ int
> rte_lpm6_is_rule_present_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t
> depth,
> uint32_t *next_hop)
> {
> - uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
> - int32_t rule_index;
> -
> /* Check user arguments. */
> if ((lpm == NULL) || next_hop == NULL || ip == NULL ||
> (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
> return -EINVAL;
>
> /* Copy the IP and mask it to avoid modifying user's input data. */
> - memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
> - mask_ip(ip_masked, depth);
> + uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
The line above doesn't strictly need to be moved. It's still recommended to
have variables at the top of the block.
> + ip6_copy_addr(masked_ip, ip);
> + ip6_mask_addr(masked_ip, depth);
>
> - /* Look for the rule using rule_find. */
> - rule_index = rule_find(lpm, ip_masked, depth);
> + struct rte_lpm6_rule *rule = rule_find(lpm, masked_ip, depth);
>
Can mark this as const, which can help justify having it declared
mid-block. :-)
<rest snipped>
