* [PATCH v5 2/2] librte_lpm: Improve performance of the delete and add functions
@ 2018-07-16 8:05 Alex Kiselev
0 siblings, 0 replies; only message in thread
From: Alex Kiselev @ 2018-07-16 8:05 UTC (permalink / raw)
To: dev, Bruce Richardson, Stephen Hemminger
librte_lpm: Improve lpm6 performance
There is no need to rebuild the whole LPM tree
when a rule is deleted. This patch addresses this
issue introducing new delete operation.
Signed-off-by: Alex Kiselev <alex@therouter.net>
---
lib/librte_lpm/rte_lpm6.c | 712 ++++++++++++++++++++++++++++++++++++++--------
1 file changed, 597 insertions(+), 115 deletions(-)
diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
index d86e878bc..6f1f94e23 100644
--- a/lib/librte_lpm/rte_lpm6.c
+++ b/lib/librte_lpm/rte_lpm6.c
@@ -41,6 +41,7 @@
#define BYTES2_SIZE 16
#define RULE_HASH_TABLE_EXTRA_SPACE 64
+#define TBL24_IND UINT32_MAX
#define lpm6_tbl8_gindex next_hop
@@ -81,6 +82,17 @@ struct rte_lpm6_rule_key {
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. */
@@ -88,12 +100,17 @@ 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_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. */
};
@@ -142,6 +159,59 @@ rule_hash(const void *data, __rte_unused uint32_t data_len,
return rte_jhash(data, sizeof(struct rte_lpm6_rule_key), init_val);
}
+/*
+ * Init pool of free tbl8 indexes
+ */
+static void
+tbl8_pool_init(struct rte_lpm6 *lpm)
+{
+ uint32_t i;
+
+ /* put entire range of indexes to the tbl8 pool */
+ 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 available in the pool
+ */
+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
@@ -182,6 +252,8 @@ rte_lpm6_create(const char *name, int socket_id,
uint64_t mem_size;
struct rte_lpm6_list *lpm_list;
struct rte_hash *rules_tbl = NULL;
+ uint32_t *tbl8_pool = NULL;
+ struct rte_lpm_tbl8_hdr *tbl8_hdrs = NULL;
lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
@@ -216,6 +288,28 @@ rte_lpm6_create(const char *name, int socket_id,
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. */
@@ -260,6 +354,11 @@ 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;
+
+ /* init the stack */
+ tbl8_pool_init(lpm);
te->data = (void *) lpm;
@@ -271,6 +370,8 @@ rte_lpm6_create(const char *name, int socket_id,
rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
fail_wo_unlock:
+ rte_free(tbl8_hdrs);
+ rte_free(tbl8_pool);
rte_hash_free(rules_tbl);
return NULL;
@@ -332,6 +433,8 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+ rte_free(lpm->tbl8_hdrs);
+ rte_free(lpm->tbl8_pool);
rte_hash_free(lpm->rules_tbl);
rte_free(lpm);
rte_free(te);
@@ -420,24 +523,24 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint32_t next_hop)
* 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)
{
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;
@@ -445,11 +548,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 / BYTE_SIZE */
+ 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
@@ -457,25 +650,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);
@@ -487,7 +676,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)) {
@@ -509,10 +698,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;
}
/*
@@ -521,12 +715,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,
@@ -535,17 +741,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 *
@@ -553,13 +762,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
@@ -574,11 +792,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;
@@ -595,13 +818,56 @@ 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 on 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 ret;
+ /* init to avoid compiler warning */
+ uint32_t tbl_next_num = 123456;
int status;
uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
int i;
@@ -614,21 +880,23 @@ rte_lpm6_add_v1705(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
ip6_copy_addr(masked_ip, ip);
ip6_mask_addr(masked_ip, depth);
- /* Add the rule to the rule table. */
- ret = rule_add(lpm, masked_ip, depth, next_hop);
- /* If there is no space available for new rule return error. */
+ /* Simulate adding a new route */
+ int ret = simulate_add(lpm, masked_ip, depth);
if (ret < 0)
return ret;
+ /* Add the rule to the rule table. */
+ int is_new_rule = rule_add(lpm, masked_ip, depth, next_hop);
+ /* If there is no space available for new rule return error. */
+ if (is_new_rule < 0)
+ return is_new_rule;
+
/* 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
@@ -636,13 +904,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;
@@ -717,9 +982,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];
@@ -755,9 +1019,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;
@@ -900,62 +1163,22 @@ rule_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
return ret;
}
-/*
- * Deletes a rule
- */
-int
-rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
-{
- uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
- int ret;
-
- /*
- * Check input arguments.
- */
- if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH)) {
- return -EINVAL;
- }
-
- /* Copy the IP and mask it to avoid modifying user's input data. */
- ip6_copy_addr(masked_ip, ip);
- ip6_mask_addr(masked_ip, depth);
-
- /* Delete the rule from the rule table. */
- ret = rule_delete(lpm, masked_ip, depth);
- if (ret < 0)
- return -ENOENT;
-
- /*
- * Set all the table entries to 0 (ie delete every rule
- * from the data structure.
- */
- lpm->next_tbl8 = 0;
- memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
- memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
- * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
-
- /*
- * Add every rule again (except for the one that was removed from
- * the rules table).
- */
- rebuild_lpm(lpm);
-
- return 0;
-}
-
/*
* Deletes a group of rules
+ *
+ * Note that the function rebuilds the lpm table,
+ * rather than doing incremental updates like
+ * the regular delete function
*/
int
rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
- uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths,
+ unsigned n)
{
uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
unsigned i;
- /*
- * Check input arguments.
- */
+ /* Check input arguments. */
if ((lpm == NULL) || (ips == NULL) || (depths == NULL))
return -EINVAL;
@@ -969,10 +1192,10 @@ rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
* Set all the table entries to 0 (ie delete every rule
* from the data structure.
*/
- lpm->next_tbl8 = 0;
memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0])
* RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
+ tbl8_pool_init(lpm);
/*
* Add every rule again (except for the ones that were removed from
@@ -992,9 +1215,6 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)
/* Zero used rules counter. */
lpm->used_rules = 0;
- /* Zero next tbl8 index. */
- lpm->next_tbl8 = 0;
-
/* Zero tbl24. */
memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
@@ -1002,6 +1222,268 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)
memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
+ /* init pool of free tbl8 indexes */
+ tbl8_pool_init(lpm);
+
/* Delete all rules form the rules table. */
rte_hash_reset(lpm->rules_tbl);
}
+
+/*
+ * Convert a depth to a one byte long mask
+ * Example: 4 will be converted to 0xF0
+ */
+static uint8_t __attribute__((pure))
+depth_to_mask_1b(uint8_t depth)
+{
+ /* To calculate a mask start with a 1 on the left hand side and right
+ * shift while populating the left hand side with 1's
+ */
+ return (signed char)0x80 >> (depth - 1);
+}
+
+/*
+ * Find a less specific rule
+ */
+static int
+rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ struct rte_lpm6_rule *rule)
+{
+ int ret;
+ uint32_t next_hop;
+ uint8_t mask;
+ struct rte_lpm6_rule_key rule_key;
+
+ if (depth == 1)
+ return 0;
+
+ rule_key_init(&rule_key, ip, depth);
+
+ while (depth > 1) {
+ depth--;
+
+ /* each iteration zero one more bit of the key */
+ mask = depth & 7; /* depth % BYTE_SIZE */
+ if (mask > 0)
+ mask = depth_to_mask_1b(mask);
+
+ rule_key.depth = depth;
+ rule_key.ip[depth >> 3] &= mask;
+
+ ret = rule_find_with_key(lpm, &rule_key, &next_hop);
+ if (ret) {
+ rule->depth = depth;
+ ip6_copy_addr(rule->ip, rule_key.ip);
+ rule->next_hop = next_hop;
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * Find range of tbl8 cells occupied by a rule
+ */
+static void
+rule_find_range(struct rte_lpm6 *lpm, const uint8_t *ip, uint8_t depth,
+ struct rte_lpm6_tbl_entry **from,
+ struct rte_lpm6_tbl_entry **to,
+ uint32_t *out_tbl_ind)
+{
+ uint32_t ind;
+ uint32_t first_3bytes = (uint32_t)ip[0] << 16 | ip[1] << 8 | ip[2];
+
+ if (depth <= 24) {
+ /* rule is within the top level */
+ ind = first_3bytes;
+ *from = &lpm->tbl24[ind];
+ ind += (1 << (24 - depth)) - 1;
+ *to = &lpm->tbl24[ind];
+ *out_tbl_ind = TBL24_IND;
+ } else {
+ /* top level entry */
+ struct rte_lpm6_tbl_entry *tbl = &lpm->tbl24[first_3bytes];
+ assert(tbl->ext_entry == 1);
+ /* first tbl8 */
+ uint32_t tbl_ind = tbl->lpm6_tbl8_gindex;
+ tbl = &lpm->tbl8[tbl_ind *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES];
+ /* current ip byte, the top level is already behind */
+ uint8_t byte = 3;
+ /* minus top level */
+ depth -= 24;
+
+ /* interate through levels (tbl8s)
+ * until we reach the last one
+ */
+ while (depth > 8) {
+ tbl += ip[byte];
+ assert(tbl->ext_entry == 1);
+ /* go to the next level/tbl8 */
+ tbl_ind = tbl->lpm6_tbl8_gindex;
+ tbl = &lpm->tbl8[tbl_ind *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES];
+ byte += 1;
+ depth -= 8;
+ }
+
+ /* last level/tbl8 */
+ ind = ip[byte] & depth_to_mask_1b(depth);
+ *from = &tbl[ind];
+ ind += (1 << (8 - depth)) - 1;
+ *to = &tbl[ind];
+ *out_tbl_ind = tbl_ind;
+ }
+}
+
+/*
+ * Remove a table from the LPM tree
+ */
+static void
+remove_tbl(struct rte_lpm6 *lpm, struct rte_lpm_tbl8_hdr *tbl_hdr,
+ uint32_t tbl_ind, struct rte_lpm6_rule *lsp_rule)
+{
+ struct rte_lpm6_tbl_entry *owner_entry;
+
+ if (tbl_hdr->owner_tbl_ind == TBL24_IND)
+ owner_entry = &lpm->tbl24[tbl_hdr->owner_entry_ind];
+ else {
+ uint32_t owner_tbl_ind = tbl_hdr->owner_tbl_ind;
+ owner_entry = &lpm->tbl8[
+ owner_tbl_ind * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES +
+ tbl_hdr->owner_entry_ind];
+
+ struct rte_lpm_tbl8_hdr *owner_tbl_hdr =
+ &lpm->tbl8_hdrs[owner_tbl_ind];
+ if (--owner_tbl_hdr->ref_cnt == 0)
+ remove_tbl(lpm, owner_tbl_hdr, owner_tbl_ind, lsp_rule);
+ }
+
+ assert(owner_entry->ext_entry == 1);
+
+ /* unlink the table */
+ if (lsp_rule != NULL) {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = lsp_rule->next_hop,
+ .depth = lsp_rule->depth,
+ .valid = VALID,
+ .valid_group = VALID,
+ .ext_entry = 0
+ };
+
+ *owner_entry = new_tbl_entry;
+ } else {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = 0,
+ .depth = 0,
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .ext_entry = 0
+ };
+
+ *owner_entry = new_tbl_entry;
+ }
+
+ /* return the table to the pool */
+ tbl8_put(lpm, tbl_ind);
+}
+
+/*
+ * Deletes a rule
+ */
+int
+rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
+{
+ uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
+ struct rte_lpm6_rule lsp_rule_obj;
+ struct rte_lpm6_rule *lsp_rule;
+ int ret;
+ uint32_t tbl_ind;
+ struct rte_lpm6_tbl_entry *from, *to;
+
+ /* Check input arguments. */
+ if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
+ return -EINVAL;
+
+ /* Copy the IP and mask it to avoid modifying user's input data. */
+ ip6_copy_addr(masked_ip, ip);
+ ip6_mask_addr(masked_ip, depth);
+
+ /* Delete the rule from the rule table. */
+ ret = rule_delete(lpm, masked_ip, depth);
+ if (ret < 0)
+ return -ENOENT;
+
+ /* find rule cells */
+ rule_find_range(lpm, masked_ip, depth, &from, &to, &tbl_ind);
+
+ /* find a less specific rule (a rule with smaller depth)
+ * note: masked_ip will be modified, don't use it anymore
+ */
+ ret = rule_find_less_specific(lpm, masked_ip, depth,
+ &lsp_rule_obj);
+ lsp_rule = ret ? &lsp_rule_obj : NULL;
+
+ /* decrement the table rule counter,
+ * note that tbl24 doesn't have a header
+ */
+ if (tbl_ind != TBL24_IND) {
+ struct rte_lpm_tbl8_hdr *tbl_hdr = &lpm->tbl8_hdrs[tbl_ind];
+ if (--tbl_hdr->ref_cnt == 0) {
+ /* remove the table */
+ remove_tbl(lpm, tbl_hdr, tbl_ind, lsp_rule);
+ return 0;
+ }
+ }
+
+ /* iterate rule cells */
+ for (; from <= to; from++)
+ if (from->ext_entry == 1) {
+ /* reference to a more specific space
+ * of the prefix/rule. Entries in a more
+ * specific space that are not used by
+ * a more specific prefix must be occupied
+ * by the prefix
+ */
+ if (lsp_rule != NULL)
+ expand_rule(lpm,
+ from->lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES,
+ depth, lsp_rule->depth,
+ lsp_rule->next_hop, VALID);
+ else
+ /* since the prefix has no less specific prefix,
+ * its more specific space must be invalidated
+ */
+ expand_rule(lpm,
+ from->lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES,
+ depth, 0, 0, INVALID);
+ } else if (from->depth == depth) {
+ /* entry is not a reference and belongs to the prefix */
+ if (lsp_rule != NULL) {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = lsp_rule->next_hop,
+ .depth = lsp_rule->depth,
+ .valid = VALID,
+ .valid_group = VALID,
+ .ext_entry = 0
+ };
+
+ *from = new_tbl_entry;
+ } else {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = 0,
+ .depth = 0,
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .ext_entry = 0
+ };
+
+ *from = new_tbl_entry;
+ }
+ }
+
+ return 0;
+}
--
2.16.1.windows.1
^ permalink raw reply related [flat|nested] only message in thread
only message in thread, other threads:[~2018-07-16 8:05 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-07-16 8:05 [PATCH v5 2/2] librte_lpm: Improve performance of the delete and add functions Alex Kiselev
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.