* [dpdk-dev] [PATCH 1/3] lpm6 speed inmprovement on delete rule
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
@ 2016-06-09 0:53 ` Nikita Kozlov
2016-06-09 0:53 ` [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common Nikita Kozlov
` (4 subsequent siblings)
5 siblings, 0 replies; 14+ messages in thread
From: Nikita Kozlov @ 2016-06-09 0:53 UTC (permalink / raw)
To: dev; +Cc: Nikita Kozlov
Rewrite rte_lpm6_delete* logic for deleting only the selected rule
instead of deleting all rules and re-inserting them.
the delete_step() function is called recursively and delete the rule
until the rule depth is covered. Then it calls delete_expand_step()
which will ensure to delete the expanded part of the rule if any.
The tbl8 are now allocated more dynamically through tbl8_alloc() which
will walk through all tbl8 for finding an empty one.
The rules are now stored in a RB-tree so we can have a dynamic number of
them. This part of the patch is inspired by
http://dpdk.org/dev/patchwork/patch/7981/ .
Adding of rte_lpm6_tbl8_count() and rte_lpm6_tbl8_free_count() which
permits to check that we are freeing correctly our tbl8 and permits to
check how much free tbl8 we have for adding new rules.
For consistency with lpm4, increase lpm6 nexthop size from 8bit to
16bit.
This patch was written in collaboration with Baptiste Daroussin from Gandi.
Signed-off-by: Nikita Kozlov <nikita@gandi.net>
---
lib/librte_lpm/Makefile | 2 +-
lib/librte_lpm/rte_lpm6.c | 576 ++++++++++++++++++++++++++-----------
lib/librte_lpm/rte_lpm6.h | 49 +++-
lib/librte_lpm/rte_lpm_version.map | 12 +
4 files changed, 474 insertions(+), 165 deletions(-)
diff --git a/lib/librte_lpm/Makefile b/lib/librte_lpm/Makefile
index 656ade2..cbab7da 100644
--- a/lib/librte_lpm/Makefile
+++ b/lib/librte_lpm/Makefile
@@ -39,7 +39,7 @@ CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
EXPORT_MAP := rte_lpm_version.map
-LIBABIVER := 2
+LIBABIVER := 3
# all source are stored in SRCS-y
SRCS-$(CONFIG_RTE_LIBRTE_LPM) := rte_lpm.c rte_lpm6.c
diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
index 32fdba0..a9de0e1 100644
--- a/lib/librte_lpm/rte_lpm6.c
+++ b/lib/librte_lpm/rte_lpm6.c
@@ -52,6 +52,8 @@
#include <rte_errno.h>
#include <rte_rwlock.h>
#include <rte_spinlock.h>
+#include <rte_compat.h>
+#include <tree.h>
#include "rte_lpm6.h"
@@ -97,27 +99,46 @@ struct rte_lpm6_tbl_entry {
/** Rules tbl entry structure. */
struct rte_lpm6_rule {
uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
- uint8_t next_hop; /**< Rule next hop. */
+ uint16_t next_hop; /**< Rule next hop. */
uint8_t depth; /**< Rule depth. */
+ RB_ENTRY(rte_lpm6_rule) link;
};
/** LPM6 structure. */
struct rte_lpm6 {
/* LPM metadata. */
char name[RTE_LPM6_NAMESIZE]; /**< Name of the lpm. */
- 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 rules. */
+ RB_HEAD(rte_lpm6_rules_tree, rte_lpm6_rule) rules[RTE_LPM6_MAX_DEPTH + 1];
/* LPM Tables. */
- struct rte_lpm6_rule *rules_tbl; /**< LPM rules. */
struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
__rte_cache_aligned; /**< LPM tbl24 table. */
struct rte_lpm6_tbl_entry tbl8[0]
__rte_cache_aligned; /**< LPM tbl8 table. */
};
+/* Comparison function for red-black tree nodes.
+ "If the first argument is smaller than the second, the function
+ returns a value smaller than zero. If they are equal, the function
+ returns zero. Otherwise, it should return a value greater than zero."
+*/
+static inline int rules_cmp(const struct rte_lpm6_rule *r1,
+ const struct rte_lpm6_rule *r2)
+{
+ return memcmp(r1->ip, r2->ip, RTE_LPM6_IPV6_ADDR_SIZE);
+}
+
+/* Satisfy old style attribute in tree.h header */
+#ifndef __unused
+#define __unused __attribute__ ((unused))
+#endif
+
+/* Generate internal functions and make them static. */
+RB_GENERATE_STATIC(rte_lpm6_rules_tree, rte_lpm6_rule, link, rules_cmp)
+
/*
* Takes an array of uint8_t (IPv6 address) and masks it using the depth.
* It leaves untouched one bit per unit in the depth variable
@@ -126,8 +147,8 @@ struct rte_lpm6 {
static inline void
mask_ip(uint8_t *ip, uint8_t depth)
{
- int16_t part_depth, mask;
- int i;
+ int16_t part_depth, mask;
+ int i;
part_depth = depth;
@@ -152,7 +173,8 @@ 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;
+ unsigned int depth;
struct rte_lpm6_list *lpm_list;
lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
@@ -161,7 +183,6 @@ rte_lpm6_create(const char *name, int socket_id,
/* Check user arguments. */
if ((name == NULL) || (socket_id < -1) || (config == NULL) ||
- (config->max_rules == 0) ||
config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) {
rte_errno = EINVAL;
return NULL;
@@ -172,7 +193,6 @@ rte_lpm6_create(const char *name, int socket_id,
/* 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);
@@ -205,22 +225,14 @@ rte_lpm6_create(const char *name, int socket_id,
goto exit;
}
- lpm->rules_tbl = (struct rte_lpm6_rule *)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);
- goto exit;
- }
-
/* Save user arguments. */
- lpm->max_rules = config->max_rules;
lpm->number_tbl8s = config->number_tbl8s;
snprintf(lpm->name, sizeof(lpm->name), "%s", name);
+ /* Vyatta change to use red-black tree */
+ for (depth = 0; depth <= RTE_LPM6_MAX_DEPTH; ++depth)
+ RB_INIT(&lpm->rules[depth]);
+
te->data = (void *) lpm;
TAILQ_INSERT_TAIL(lpm_list, te, next);
@@ -286,8 +298,8 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
TAILQ_REMOVE(lpm_list, te, next);
rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+ rte_lpm6_delete_all(lpm);
- rte_free(lpm->rules_tbl);
rte_free(lpm);
rte_free(te);
}
@@ -296,41 +308,85 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
* 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.
*/
-static inline int32_t
-rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t next_hop, uint8_t depth)
+static struct rte_lpm6_rule *
+rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint16_t next_hop, uint8_t depth)
{
- uint32_t rule_index;
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule *r, *old;
+
+ /*
+ * NB: uses regular malloc to avoid chewing up precious
+ * memory pool space for rules.
+ */
+ r = malloc(sizeof(*r));
+ if (!r)
+ return NULL;
+
+ rte_memcpy(r->ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ r->next_hop = next_hop;
+ r->depth = depth;
- /* Scan through rule list to see if rule already exists. */
- for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
+ old = RB_INSERT(rte_lpm6_rules_tree, head, r);
+ if (!old)
+ return r;
- /* 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;
+ /* collision with existing rule */
+ free(r);
- return rule_index;
+ return old;
+}
+
+/*
+ * Find, clean and allocate a tbl8.
+ */
+static inline int32_t
+tbl8_alloc(struct rte_lpm6 *lpm)
+{
+ uint32_t tbl8_gindex; /* tbl8 group index. */
+ struct rte_lpm6_tbl_entry *tbl8_entry;
+ struct rte_lpm6_tbl_entry *tbl8 = lpm->tbl8;
+
+ /* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */
+ for (tbl8_gindex = 0; tbl8_gindex < lpm->number_tbl8s;
+ tbl8_gindex++) {
+ tbl8_entry = &tbl8[tbl8_gindex * RTE_LPM6_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_LPM6_TBL8_GROUP_NUM_ENTRIES *
+ sizeof(tbl8_entry[0]));
+
+ tbl8_entry->valid_group = VALID;
+
+ /* Return group index for allocated tbl8 group. */
+ return tbl8_gindex;
}
}
- /*
- * 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) {
- return -ENOSPC;
- }
+ /* If there are no tbl8 groups free then return error. */
+ 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;
+static inline void
+tbl8_free(struct rte_lpm6_tbl_entry *tbl8, uint32_t tbl8_group_start)
+{
+ /* Set tbl8 group invalid*/
+ memset(&tbl8[tbl8_group_start], 0, RTE_LPM6_TBL8_GROUP_NUM_ENTRIES *
+ sizeof(tbl8[0]));
+}
- /* Increment the used rules counter for this rule group. */
- lpm->used_rules++;
+static int
+tbl8_is_free(struct rte_lpm6_tbl_entry *tbl8, uint32_t tbl8_group_start)
+{
+ uint32_t i, tbl8_group_end;
+ tbl8_group_end = tbl8_group_start +
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
- return rule_index;
+ for (i = tbl8_group_start; i < tbl8_group_end; i++) {
+ if (tbl8[i].valid)
+ return 0;
+ }
+ return 1;
}
/*
@@ -340,7 +396,7 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t next_hop, uint8_t depth)
*/
static void
expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
- uint8_t next_hop)
+ uint16_t next_hop)
{
uint32_t tbl8_group_end, tbl8_gindex_next, j;
@@ -354,6 +410,8 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
.ext_entry = 0,
};
+ rte_compiler_barrier();
+
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)) {
@@ -377,7 +435,7 @@ 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, uint8_t next_hop)
+ uint8_t first_byte, uint8_t depth, uint16_t next_hop)
{
uint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;
int32_t tbl8_gindex;
@@ -404,20 +462,22 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
* expand the rule across the relevant positions in the table.
*/
if (depth <= bits_covered) {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = next_hop,
+ .depth = depth,
+ .valid = VALID,
+ .valid_group = VALID,
+ .ext_entry = 0,
+ };
+
+ rte_compiler_barrier();
+
tbl_range = 1 << (bits_covered - depth);
for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
tbl[i].depth <= depth)) {
- struct rte_lpm6_tbl_entry new_tbl_entry = {
- .next_hop = next_hop,
- .depth = depth,
- .valid = VALID,
- .valid_group = VALID,
- .ext_entry = 0,
- };
-
tbl[i] = new_tbl_entry;
} else if (tbl[i].ext_entry == 1) {
@@ -441,10 +501,10 @@ 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
+ tbl8_gindex = tbl8_alloc(lpm);
+ if (tbl8_gindex < 0) {
return -ENOSPC;
+ }
struct rte_lpm6_tbl_entry new_tbl_entry = {
.lpm6_tbl8_gindex = tbl8_gindex,
@@ -454,6 +514,8 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
.ext_entry = 1,
};
+ rte_compiler_barrier();
+
tbl[tbl_index] = new_tbl_entry;
}
/*
@@ -461,12 +523,10 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
* 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
+ tbl8_gindex = tbl8_alloc(lpm);
+ if (tbl8_gindex < 0) {
return -ENOSPC;
-
+ }
tbl8_group_start = tbl8_gindex *
RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
tbl8_group_end = tbl8_group_start +
@@ -493,6 +553,8 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
.ext_entry = 1,
};
+ rte_compiler_barrier();
+
tbl[tbl_index] = new_tbl_entry;
}
@@ -503,19 +565,26 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
return 1;
}
+int
+rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint8_t next_hop)
+{
+ return rte_lpm6_add_v1607(lpm, ip, depth, next_hop);
+}
+VERSION_SYMBOL(rte_lpm6_add, _v20, 2.0);
+
/*
* Add a route
*/
int
-rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
- uint8_t next_hop)
+rte_lpm6_add_v1607(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop)
{
struct rte_lpm6_tbl_entry *tbl;
struct rte_lpm6_tbl_entry *tbl_next;
- int32_t rule_index;
- int status;
+ struct rte_lpm6_rule *rule;
+ int status, i;
uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
- int i;
/* Check user arguments. */
if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
@@ -526,14 +595,14 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
mask_ip(masked_ip, depth);
/* Add the rule to the rule table. */
- rule_index = rule_add(lpm, masked_ip, next_hop, depth);
+ rule = rule_add(lpm, masked_ip, next_hop, depth);
/* If there is no space available for new rule return error. */
- if (rule_index < 0) {
- return rule_index;
+ if (rule == NULL) {
+ return -EINVAL;
}
- /* Inspect the first three bytes through tbl24 on the first step. */
+ /* 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);
@@ -544,7 +613,7 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
}
/*
- * Inspect one by one the rest of the bytes until
+ * 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 && status == 1; i++) {
@@ -560,6 +629,9 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
return status;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_add, _v1607, 16.07);
+MAP_STATIC_SYMBOL(int rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip,
+ uint8_t depth, uint16_t next_hop), rte_lpm6_add_v1607);
/*
* Takes a pointer to a table entry and inspect one level.
@@ -569,7 +641,7 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
static inline int
lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
const struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip,
- uint8_t first_byte, uint8_t *next_hop)
+ uint8_t first_byte, uint16_t *next_hop)
{
uint32_t tbl8_index, tbl_entry;
@@ -589,16 +661,22 @@ lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
return 1;
} else {
/* If not extended then we can have a match. */
- *next_hop = (uint8_t)tbl_entry;
+ *next_hop = (uint16_t)tbl_entry;
return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
}
}
+int
+rte_lpm6_lookup_v20(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
+{
+ return rte_lpm6_lookup_v1607(lpm, ip, (uint16_t*)next_hop);
+}
+VERSION_SYMBOL(rte_lpm6_lookup, _v20, 2.0);
/*
* Looks up an IP
*/
int
-rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
+rte_lpm6_lookup_v1607(const struct rte_lpm6 *lpm, uint8_t *ip, uint16_t *next_hop)
{
const struct rte_lpm6_tbl_entry *tbl;
const struct rte_lpm6_tbl_entry *tbl_next = NULL;
@@ -625,20 +703,33 @@ rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
return status;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_lookup, _v1607, 16.07);
+MAP_STATIC_SYMBOL(int rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip,
+ uint16_t *next_hop), rte_lpm6_lookup_v1607);
+
+int
+rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int16_t *next_hops, unsigned n)
+{
+ return rte_lpm6_lookup_bulk_func_v1607(lpm, ips, (int32_t*)next_hops, n);
+}
+VERSION_SYMBOL(rte_lpm6_lookup_bulk_func, _v20, 2.0);
/*
* Looks up a group of IP addresses
*/
int
-rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
+rte_lpm6_lookup_bulk_func_v1607(const struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
- int16_t * next_hops, unsigned n)
+ int32_t *next_hops, unsigned n)
{
unsigned i;
const struct rte_lpm6_tbl_entry *tbl;
const struct rte_lpm6_tbl_entry *tbl_next = NULL;
uint32_t tbl24_index;
- uint8_t first_byte, next_hop;
+ uint8_t first_byte;
+ uint16_t next_hop;
int status;
/* DEBUG: Check user input arguments. */
@@ -669,40 +760,64 @@ rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
return 0;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_lookup_bulk_func, _v1607, 16.07);
+MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm, uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int32_t *next_hops, unsigned n), rte_lpm6_lookup_bulk_func_v1607);
/*
* Finds a rule in rule table.
- * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
+ * NOTE: Valid range for depth parameter is 0 .. 128 inclusive.
*/
-static inline int32_t
+static struct rte_lpm6_rule *
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) {
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule k;
+
+ rte_memcpy(k.ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+
+ return RB_FIND(rte_lpm6_rules_tree, head, &k);
+}
+
+static struct rte_lpm6_rule *
+find_previous_rule(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint8_t *sub_rule_depth)
+{
+ struct rte_lpm6_rule *rule;
+ uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+ int prev_depth;
- return rule_index;
+ /* Copy the IP and mask it to avoid modifying user's input data. */
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ for (prev_depth = depth; prev_depth >= 0; prev_depth--) {
+ mask_ip(ip_masked, prev_depth);
+ rule = rule_find(lpm, ip_masked, prev_depth);
+ if (rule) {
+ *sub_rule_depth = prev_depth;
+ return rule;
}
}
- /* If rule is not found return -ENOENT. */
- return -ENOENT;
+ return NULL;
}
+int
+rte_lpm6_is_rule_present_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint8_t *next_hop)
+{
+ return rte_lpm6_is_rule_present_v1607(lpm, ip, depth, (uint16_t*)next_hop);
+}
+VERSION_SYMBOL(rte_lpm6_is_rule_present, _v20, 2.0);
/*
* Look for a rule in the high-level rules table
*/
int
-rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
-uint8_t *next_hop)
+rte_lpm6_is_rule_present_v1607(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint16_t *next_hop)
{
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
- int32_t rule_index;
+ struct rte_lpm6_rule *rule;
/* Check user arguments. */
if ((lpm == NULL) || next_hop == NULL || ip == NULL ||
@@ -710,34 +825,175 @@ uint8_t *next_hop)
return -EINVAL;
/* Copy the IP and mask it to avoid modifying user's input data. */
- memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
mask_ip(ip_masked, depth);
/* Look for the rule using rule_find. */
- rule_index = rule_find(lpm, ip_masked, depth);
+ rule = rule_find(lpm, ip, depth);
- if (rule_index >= 0) {
- *next_hop = lpm->rules_tbl[rule_index].next_hop;
+ if (rule != NULL) {
+ *next_hop = rule->next_hop;
return 1;
}
/* If rule is not found return 0. */
return 0;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_is_rule_present, _v1607, 16.07);
+MAP_STATIC_SYMBOL(int rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, uint8_t *ip,
+ uint8_t depth, uint16_t *next_hop), rte_lpm6_is_rule_present_v1607);
/*
* Delete a rule from the rule table.
- * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
+ * NOTE: Valid range for depth parameter is 0 .. 128 inclusive.
*/
static inline void
-rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)
+rule_delete(struct rte_lpm6 *lpm, struct rte_lpm6_rule *r, uint8_t depth)
{
- /*
- * Overwrite redundant rule with last rule in group and decrement rule
- * counter.
- */
- lpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->used_rules-1];
- lpm->used_rules--;
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+
+ RB_REMOVE(rte_lpm6_rules_tree, head, r);
+
+ free(r);
+}
+
+/*
+ * Function that run through the data structure when and clean entries
+ * that where expanded by expand_rule().
+ */
+static void
+delete_expand_step(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
+ uint16_t next_hop)
+{
+ 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 empty_tbl8_entry = {
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .depth = 0,
+ .next_hop = 0,
+ .ext_entry = 0,
+ };
+
+ rte_compiler_barrier();
+
+ 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].next_hop == next_hop) {
+
+ lpm->tbl8[j] = empty_tbl8_entry;
+
+ } else if (lpm->tbl8[j].ext_entry == 1) {
+
+ tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
+ * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ delete_expand_step(lpm, tbl8_gindex_next, depth, next_hop);
+ }
+ }
+
+}
+/*
+ * Partially delete a route from the data structure (tbl24+tbl8s).
+ * It may be called and partially added routes (after an unsuccesful add_step).
+ */
+static void
+delete_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
+ uint8_t *ip, uint32_t tbl_group_start, struct rte_lpm6_rule *sub_rule, uint8_t depth, uint8_t bits_covered, uint16_t next_hop)
+{
+ uint32_t i, tbl_index = tbl_group_start + ip[bits_covered / 8 - 1];
+ struct rte_lpm6_tbl_entry empty_tbl8_entry = {
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .depth = 0,
+ .next_hop = 0,
+ .ext_entry = 0,
+ };
+
+ rte_compiler_barrier();
+
+ /* recurse until we are at the last tbl8 that should have been deleted for this rule without an expand */
+ if (depth > bits_covered) {
+ uint32_t tbl_group_next;
+
+ /* check if we have a partially added rule */
+ if (tbl[tbl_index].ext_entry == 1) {
+ /* calculate the next tbl_index */
+ tbl_group_next = tbl[tbl_index].lpm6_tbl8_gindex * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ delete_step(lpm, lpm->tbl8, ip, tbl_group_next, sub_rule, depth, bits_covered + 8, next_hop);
+ }
+ } else {
+ uint32_t tbl_range;
+
+ /* last iteration, we may need to remove what we have done through the expand */
+ tbl_range = 1 << (bits_covered - depth);
+ for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
+ if (tbl[i].ext_entry == 1) {
+ uint32_t tbl8_gindex = tbl[i].lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ delete_expand_step(lpm, tbl8_gindex, depth, next_hop);
+ } else {
+ /* do a normal cleaning */
+ if (tbl[i].depth == depth) {
+ if (sub_rule) {
+ tbl[i].depth = sub_rule->depth;
+ tbl[i].next_hop = sub_rule->next_hop;
+ } else {
+ tbl[i] = empty_tbl8_entry;
+ }
+ }
+ }
+ }
+ return;
+ }
+
+ /* check if we can recycle the current tbl_entry because we have cleaned all its childs */
+ if (tbl[tbl_index].ext_entry) {
+ if (tbl8_is_free(lpm->tbl8, tbl[tbl_index].lpm6_tbl8_gindex * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES)) {
+ tbl[tbl_index] = empty_tbl8_entry;
+ }
+ }
+
+ /* we are recursing on the tbl24 so we don't need to check those cases */
+ if (bits_covered == 24) {
+ return;
+ }
+
+ /* try to clean our current tbl group from tbl_group_start to tbl_group_end */
+ for (i = tbl_group_start; i < tbl_group_start + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; i++) {
+ if (tbl[i].valid == 1) {
+ break;
+ }
+ }
+ if (i == tbl_group_start + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES) {
+ /* we can free a whole group */
+ tbl8_free(lpm->tbl8, tbl_group_start);
+ }
+}
+
+/*
+ * Find rule to replace the just deleted. If there is no rule to
+ * replace the rule_to_delete we return NULL and invalidate the table
+ * entries associated with this rule.
+ */
+static void
+rule_replace(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth, uint16_t next_hop)
+{
+ uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+ struct rte_lpm6_rule *sub_rule;
+ uint8_t sub_depth = 0;
+ uint32_t tbl_index;
+
+ /* Copy the IP and mask it to avoid modifying user's input data. */
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ mask_ip(ip_masked, depth);
+
+ sub_rule = find_previous_rule(lpm, ip_masked, depth, &sub_depth);
+
+ tbl_index = (ip_masked[0] << BYTES2_SIZE) | (ip_masked[1] << BYTE_SIZE);
+
+ delete_step(lpm, lpm->tbl24, ip_masked, tbl_index, sub_rule, depth, 24, next_hop);
}
/*
@@ -746,9 +1002,9 @@ rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)
int
rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
{
- int32_t rule_to_delete_index;
+ struct rte_lpm6_rule *rule;
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
- unsigned i;
+ uint16_t next_hop;
/*
* Check input arguments.
@@ -758,42 +1014,29 @@ rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
}
/* Copy the IP and mask it to avoid modifying user's input data. */
- memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
mask_ip(ip_masked, depth);
/*
* 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);
+ rule = rule_find(lpm, ip_masked, depth);
/*
* Check if rule_to_delete_index was found. If no rule was found the
* function rule_find returns -ENOENT.
*/
- if (rule_to_delete_index < 0)
- return rule_to_delete_index;
+ if (rule == NULL)
+ return -EINVAL;
- /* Delete the rule from the rule table. */
- rule_delete(lpm, rule_to_delete_index);
+ next_hop = rule->next_hop;
- /*
- * 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);
+ /* Delete the rule from the rule table. */
+ rule_delete(lpm, rule, depth);
- /*
- * Add every rule again (except for the one that was removed from
- * the rules table).
- */
- for (i = 0; i < lpm->used_rules; i++) {
- rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
- lpm->rules_tbl[i].next_hop);
- }
+ /* Replace with next level up rule */
+ rule_replace(lpm, ip_masked, depth, next_hop);
return 0;
}
@@ -805,9 +1048,10 @@ int
rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)
{
- int32_t rule_to_delete_index;
+ struct rte_lpm6_rule *rule;
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
unsigned i;
+ uint16_t next_hop;
/*
* Check input arguments.
@@ -825,51 +1069,45 @@ rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
* 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, depths[i]);
+ rule = rule_find(lpm, ip_masked, depths[i]);
/*
* Check if rule_to_delete_index was found. If no rule was found the
* function rule_find returns -ENOENT.
*/
- if (rule_to_delete_index < 0)
+ if (rule == NULL)
continue;
- /* Delete the rule from the rule table. */
- rule_delete(lpm, rule_to_delete_index);
- }
+ next_hop = rule->next_hop;
- /*
- * 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);
+ /* Delete the rule from the rule table. */
+ rule_delete(lpm, rule, depths[i]);
- /*
- * Add every rule again (except for the ones that were removed from
- * the rules table).
- */
- for (i = 0; i < lpm->used_rules; i++) {
- rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
- lpm->rules_tbl[i].next_hop);
+ /* Replace with next level up rule */
+ rule_replace(lpm, ip_masked, depths[i], next_hop);
}
return 0;
}
+
/*
* Delete all rules from the LPM table.
*/
void
rte_lpm6_delete_all(struct rte_lpm6 *lpm)
{
- /* Zero used rules counter. */
- lpm->used_rules = 0;
+ uint8_t depth;
+
+ /* Delete all rules form the rules table. */
+ for (depth = 0; depth < RTE_LPM6_MAX_DEPTH; ++depth) {
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule *r, *n;
- /* Zero next tbl8 index. */
- lpm->next_tbl8 = 0;
+ RB_FOREACH_SAFE(r, rte_lpm6_rules_tree, head, n) {
+ rule_delete(lpm, r, depth);
+ }
+ }
/* Zero tbl24. */
memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
@@ -877,7 +1115,25 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)
/* Zero tbl8. */
memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
+}
- /* Delete all rules form the rules table. */
- memset(lpm->rules_tbl, 0, sizeof(struct rte_lpm6_rule) * lpm->max_rules);
+/* Count usage of tbl8 */
+unsigned
+rte_lpm6_tbl8_count(const struct rte_lpm6 *lpm)
+{
+ unsigned i, count = 0;
+
+ for (i = 0; i < lpm->number_tbl8s ; i++) {
+ const struct rte_lpm6_tbl_entry *tbl8_entry
+ = lpm->tbl8 + i * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ if (tbl8_entry->valid_group)
+ ++count;
+ }
+ return count;
+}
+
+unsigned
+rte_lpm6_tbl8_free_count(const struct rte_lpm6 *lpm)
+{
+ return lpm->number_tbl8s - rte_lpm6_tbl8_count(lpm);
}
diff --git a/lib/librte_lpm/rte_lpm6.h b/lib/librte_lpm/rte_lpm6.h
index 13d027f..5890669 100644
--- a/lib/librte_lpm/rte_lpm6.h
+++ b/lib/librte_lpm/rte_lpm6.h
@@ -55,7 +55,7 @@ struct rte_lpm6;
/** LPM configuration structure. */
struct rte_lpm6_config {
- uint32_t max_rules; /**< Max number of rules. */
+ uint32_t max_rules; /**< This field is currently unused. */
uint32_t number_tbl8s; /**< Number of tbl8s to allocate. */
int flags; /**< This field is currently unused. */
};
@@ -123,8 +123,13 @@ rte_lpm6_free(struct rte_lpm6 *lpm);
*/
int
rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop);
+int
+rte_lpm6_add_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
uint8_t next_hop);
-
+int
+rte_lpm6_add_v1607(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop);
/**
* Check if a rule is present in the LPM table,
* and provide its next hop if it is.
@@ -142,7 +147,13 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
*/
int
rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint16_t *next_hop);
+int
+rte_lpm6_is_rule_present_v20(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
uint8_t *next_hop);
+int
+rte_lpm6_is_rule_present_v1607(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint16_t *next_hop);
/**
* Delete a rule from the LPM table.
@@ -199,7 +210,11 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm);
* -EINVAL for incorrect arguments, -ENOENT on lookup miss, 0 on lookup hit
*/
int
-rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
+rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint16_t *next_hop);
+int
+rte_lpm6_lookup_v20(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
+int
+rte_lpm6_lookup_v1607(const struct rte_lpm6 *lpm, uint8_t *ip, uint16_t *next_hop);
/**
* Lookup multiple IP addresses in an LPM table.
@@ -220,7 +235,33 @@ rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
int
rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
- int16_t * next_hops, unsigned n);
+ int32_t *next_hops, unsigned n);
+int
+rte_lpm6_lookup_bulk_func_v20(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int16_t *next_hops, unsigned n);
+int
+rte_lpm6_lookup_bulk_func_v1607(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int32_t *next_hops, unsigned n);
+/**
+ * Return the number of entries in the Tbl8 array
+ *
+ * @param lpm
+ * LPM object handle
+ */
+unsigned
+rte_lpm6_tbl8_count(const struct rte_lpm6 *lpm);
+
+
+/**
+ * Return the number of free entries in the Tbl8 array
+ *
+ * @param lpm
+ * LPM object handle
+ */
+unsigned
+rte_lpm6_tbl8_free_count(const struct rte_lpm6 *lpm);
#ifdef __cplusplus
}
diff --git a/lib/librte_lpm/rte_lpm_version.map b/lib/librte_lpm/rte_lpm_version.map
index 239b371..9168473 100644
--- a/lib/librte_lpm/rte_lpm_version.map
+++ b/lib/librte_lpm/rte_lpm_version.map
@@ -34,3 +34,15 @@ DPDK_16.04 {
rte_lpm_delete_all;
} DPDK_2.0;
+
+DPDK_16.07 {
+ global:
+
+ rte_lpm6_add;
+ rte_lpm6_is_rule_present;
+ rte_lpm6_lookup;
+ rte_lpm6_lookup_bulk_func;
+ rte_lpm6_tbl8_count;
+ rte_lpm6_tbl8_free_count;
+
+} DPDK_16.04;
--
2.8.1
^ permalink raw reply [flat|nested] 14+ messages in thread* [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
2016-06-09 0:53 ` [dpdk-dev] [PATCH 1/3] lpm6 speed inmprovement " Nikita Kozlov
@ 2016-06-09 0:53 ` Nikita Kozlov
2016-06-09 0:58 ` Stephen Hemminger
2016-06-09 0:53 ` [dpdk-dev] [PATCH 3/3] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib Nikita Kozlov
` (3 subsequent siblings)
5 siblings, 1 reply; 14+ messages in thread
From: Nikita Kozlov @ 2016-06-09 0:53 UTC (permalink / raw)
To: dev; +Cc: Nikita Kozlov
This structure is used inside the rte_lpm6 lib for storing added rules.
It's imported from FreeBSD-10.3 from /usr/include/sys/tree.h, another
solution could have been to use on Linux the version from libbsd but it
would create an external dependency.
Signed-off-by: Nikita Kozlov <nikita@gandi.net>
---
lib/librte_eal/common/Makefile | 2 +-
lib/librte_eal/common/include/sys/tree.h | 801 +++++++++++++++++++++++++++++++
2 files changed, 802 insertions(+), 1 deletion(-)
create mode 100644 lib/librte_eal/common/include/sys/tree.h
diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
index f5ea0ee..57f58d6 100644
--- a/lib/librte_eal/common/Makefile
+++ b/lib/librte_eal/common/Makefile
@@ -40,7 +40,7 @@ INC += rte_string_fns.h rte_version.h
INC += rte_eal_memconfig.h rte_malloc_heap.h
INC += rte_hexdump.h rte_devargs.h rte_dev.h
INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
-INC += rte_malloc.h rte_keepalive.h rte_time.h
+INC += rte_malloc.h rte_keepalive.h rte_time.h sys/tree.h
ifeq ($(CONFIG_RTE_INSECURE_FUNCTION_WARNING),y)
INC += rte_warnings.h
diff --git a/lib/librte_eal/common/include/sys/tree.h b/lib/librte_eal/common/include/sys/tree.h
new file mode 100644
index 0000000..1f5c628
--- /dev/null
+++ b/lib/librte_eal/common/include/sys/tree.h
@@ -0,0 +1,801 @@
+/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
+/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
+/* $FreeBSD: head/sys/sys/tree.h 277642 2015-01-24 12:43:36Z kib $ */
+
+/*-
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_TREE_H_
+#define _SYS_TREE_H_
+
+#include <sys/cdefs.h>
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure. Every operation
+ * on the tree causes a splay to happen. The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree. On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n). The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute. It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ * same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type) \
+struct name { \
+ struct type *sph_root; /* root of the tree */ \
+}
+
+#define SPLAY_INITIALIZER(root) \
+ { NULL }
+
+#define SPLAY_INIT(root) do { \
+ (root)->sph_root = NULL; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ENTRY(type) \
+struct { \
+ struct type *spe_left; /* left element */ \
+ struct type *spe_right; /* right element */ \
+}
+
+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
+#define SPLAY_ROOT(head) (head)->sph_root
+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do { \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do { \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp) \
+void name##_SPLAY(struct name *, struct type *); \
+void name##_SPLAY_MINMAX(struct name *, int); \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
+ \
+/* Finds the node with the same key as elm */ \
+static __inline struct type * \
+name##_SPLAY_FIND(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) \
+ return(NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) \
+ return (head->sph_root); \
+ return (NULL); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_NEXT(struct name *head, struct type *elm) \
+{ \
+ name##_SPLAY(head, elm); \
+ if (SPLAY_RIGHT(elm, field) != NULL) { \
+ elm = SPLAY_RIGHT(elm, field); \
+ while (SPLAY_LEFT(elm, field) != NULL) { \
+ elm = SPLAY_LEFT(elm, field); \
+ } \
+ } else \
+ elm = NULL; \
+ return (elm); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_MIN_MAX(struct name *head, int val) \
+{ \
+ name##_SPLAY_MINMAX(head, val); \
+ return (SPLAY_ROOT(head)); \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return ((head)->sph_root); \
+ } \
+ (head)->sph_root = (elm); \
+ return (NULL); \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return (NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return (elm); \
+ } \
+ return (NULL); \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+ int __comp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) > 0){ \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+} \
+ \
+/* Splay with either the minimum or the maximum element \
+ * Used to find minimum or maximum element in tree. \
+ */ \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while (1) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp > 0) { \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+}
+
+#define SPLAY_NEGINF -1
+#define SPLAY_INF 1
+
+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head) \
+ for ((x) = SPLAY_MIN(name, head); \
+ (x) != NULL; \
+ (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type) \
+struct name { \
+ struct type *rbh_root; /* root of the tree */ \
+}
+
+#define RB_INITIALIZER(root) \
+ { NULL }
+
+#define RB_INIT(root) do { \
+ (root)->rbh_root = NULL; \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_BLACK 0
+#define RB_RED 1
+#define RB_ENTRY(type) \
+struct { \
+ struct type *rbe_left; /* left element */ \
+ struct type *rbe_right; /* right element */ \
+ struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
+}
+
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ROOT(head) (head)->rbh_root
+#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do { \
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_SET_BLACKRED(black, red, field) do { \
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x) do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+#define RB_PROTOTYPE(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+ RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
+ RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
+ RB_PROTOTYPE_INSERT(name, type, attr); \
+ RB_PROTOTYPE_REMOVE(name, type, attr); \
+ RB_PROTOTYPE_FIND(name, type, attr); \
+ RB_PROTOTYPE_NFIND(name, type, attr); \
+ RB_PROTOTYPE_NEXT(name, type, attr); \
+ RB_PROTOTYPE_PREV(name, type, attr); \
+ RB_PROTOTYPE_MINMAX(name, type, attr);
+#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
+ attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
+#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
+ attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+#define RB_PROTOTYPE_REMOVE(name, type, attr) \
+ attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT(name, type, attr) \
+ attr struct type *name##_RB_INSERT(struct name *, struct type *)
+#define RB_PROTOTYPE_FIND(name, type, attr) \
+ attr struct type *name##_RB_FIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NFIND(name, type, attr) \
+ attr struct type *name##_RB_NFIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NEXT(name, type, attr) \
+ attr struct type *name##_RB_NEXT(struct type *)
+#define RB_PROTOTYPE_PREV(name, type, attr) \
+ attr struct type *name##_RB_PREV(struct type *)
+#define RB_PROTOTYPE_MINMAX(name, type, attr) \
+ attr struct type *name##_RB_MINMAX(struct name *, int)
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define RB_GENERATE(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define RB_GENERATE_STATIC(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+ RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+ RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+ RB_GENERATE_INSERT(name, type, field, cmp, attr) \
+ RB_GENERATE_REMOVE(name, type, field, attr) \
+ RB_GENERATE_FIND(name, type, field, cmp, attr) \
+ RB_GENERATE_NFIND(name, type, field, cmp, attr) \
+ RB_GENERATE_NEXT(name, type, field, attr) \
+ RB_GENERATE_PREV(name, type, field, attr) \
+ RB_GENERATE_MINMAX(name, type, field, attr)
+
+#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+attr void \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = RB_PARENT(elm, field)) != NULL && \
+ RB_COLOR(parent, field) == RB_RED) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RIGHT(parent, field) == elm) { \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_LEFT(parent, field) == elm) { \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+}
+
+#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+attr void \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
+ elm != RB_ROOT(head)) { \
+ if (RB_LEFT(parent, field) == elm) { \
+ tmp = RB_RIGHT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+ struct type *oleft; \
+ if ((oleft = RB_LEFT(tmp, field)) \
+ != NULL) \
+ RB_COLOR(oleft, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_RIGHT(tmp, field)) \
+ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = RB_LEFT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+ struct type *oright; \
+ if ((oright = RB_RIGHT(tmp, field)) \
+ != NULL) \
+ RB_COLOR(oright, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_LEFT(head, tmp, oright, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_LEFT(tmp, field)) \
+ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ RB_COLOR(elm, field) = RB_BLACK; \
+}
+
+#define RB_GENERATE_REMOVE(name, type, field, attr) \
+attr struct type * \
+name##_RB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (RB_LEFT(elm, field) == NULL) \
+ child = RB_RIGHT(elm, field); \
+ else if (RB_RIGHT(elm, field) == NULL) \
+ child = RB_LEFT(elm, field); \
+ else { \
+ struct type *left; \
+ elm = RB_RIGHT(elm, field); \
+ while ((left = RB_LEFT(elm, field)) != NULL) \
+ elm = left; \
+ child = RB_RIGHT(elm, field); \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+ if (RB_PARENT(elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (RB_PARENT(old, field)) { \
+ if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+ RB_LEFT(RB_PARENT(old, field), field) = elm;\
+ else \
+ RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+ RB_AUGMENT(RB_PARENT(old, field)); \
+ } else \
+ RB_ROOT(head) = elm; \
+ RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ if (RB_RIGHT(old, field)) \
+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \
+ if (parent) { \
+ left = parent; \
+ do { \
+ RB_AUGMENT(left); \
+ } while ((left = RB_PARENT(left, field)) != NULL); \
+ } \
+ goto color; \
+ } \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+color: \
+ if (color == RB_BLACK) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
+ return (old); \
+} \
+
+#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_RB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = RB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ return (NULL); \
+}
+
+#define RB_GENERATE_FIND(name, type, field, cmp, attr) \
+/* Finds the node with the same key as elm */ \
+attr struct type * \
+name##_RB_FIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+}
+
+#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \
+/* Finds the first node greater than or equal to the search key */ \
+attr struct type * \
+name##_RB_NFIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = RB_LEFT(tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (res); \
+}
+
+#define RB_GENERATE_NEXT(name, type, field, attr) \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_NEXT(struct type *elm) \
+{ \
+ if (RB_RIGHT(elm, field)) { \
+ elm = RB_RIGHT(elm, field); \
+ while (RB_LEFT(elm, field)) \
+ elm = RB_LEFT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define RB_GENERATE_PREV(name, type, field, attr) \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_PREV(struct type *elm) \
+{ \
+ if (RB_LEFT(elm, field)) { \
+ elm = RB_LEFT(elm, field); \
+ while (RB_RIGHT(elm, field)) \
+ elm = RB_RIGHT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define RB_GENERATE_MINMAX(name, type, field, attr) \
+attr struct type * \
+name##_RB_MINMAX(struct name *head, int val) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else \
+ tmp = RB_RIGHT(tmp, field); \
+ } \
+ return (parent); \
+}
+
+#define RB_NEGINF -1
+#define RB_INF 1
+
+#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
+#define RB_PREV(name, x, y) name##_RB_PREV(y)
+#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head) \
+ for ((x) = RB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = RB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#endif /* _SYS_TREE_H_ */
--
2.8.1
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common
2016-06-09 0:53 ` [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common Nikita Kozlov
@ 2016-06-09 0:58 ` Stephen Hemminger
2016-06-09 7:25 ` Thomas Monjalon
2016-06-09 14:54 ` Nikita Kozlov
0 siblings, 2 replies; 14+ messages in thread
From: Stephen Hemminger @ 2016-06-09 0:58 UTC (permalink / raw)
To: Nikita Kozlov; +Cc: dev, Nikita Kozlov
On Thu, 9 Jun 2016 02:53:53 +0200
Nikita Kozlov <nikita@elyzion.net> wrote:
> This structure is used inside the rte_lpm6 lib for storing added rules.
> It's imported from FreeBSD-10.3 from /usr/include/sys/tree.h, another
> solution could have been to use on Linux the version from libbsd but it
> would create an external dependency.
>
> Signed-off-by: Nikita Kozlov <nikita@gandi.net>
Using Red-black tree is a good idea, and we have been doing it for a while
both on v4 and v6.
But this is not the way to handle it.
Please don't copy a header file which is available already on both BSD and Linux.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common
2016-06-09 0:58 ` Stephen Hemminger
@ 2016-06-09 7:25 ` Thomas Monjalon
2016-06-09 14:54 ` Nikita Kozlov
1 sibling, 0 replies; 14+ messages in thread
From: Thomas Monjalon @ 2016-06-09 7:25 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: dev, Nikita Kozlov, Nikita Kozlov
2016-06-08 17:58, Stephen Hemminger:
> On Thu, 9 Jun 2016 02:53:53 +0200
> Nikita Kozlov <nikita@elyzion.net> wrote:
>
> > This structure is used inside the rte_lpm6 lib for storing added rules.
> > It's imported from FreeBSD-10.3 from /usr/include/sys/tree.h, another
> > solution could have been to use on Linux the version from libbsd but it
> > would create an external dependency.
>
> Using Red-black tree is a good idea, and we have been doing it for a while
> both on v4 and v6.
When you say "we", you mean Vyatta? Brocade? in a commercial code?
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common
2016-06-09 0:58 ` Stephen Hemminger
2016-06-09 7:25 ` Thomas Monjalon
@ 2016-06-09 14:54 ` Nikita Kozlov
2016-06-09 15:14 ` Thomas Monjalon
1 sibling, 1 reply; 14+ messages in thread
From: Nikita Kozlov @ 2016-06-09 14:54 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: dev
On 06/ 9/16 02:58 AM, Stephen Hemminger wrote:
> On Thu, 9 Jun 2016 02:53:53 +0200
> Nikita Kozlov <nikita@elyzion.net> wrote:
>
>> This structure is used inside the rte_lpm6 lib for storing added rules.
>> It's imported from FreeBSD-10.3 from /usr/include/sys/tree.h, another
>> solution could have been to use on Linux the version from libbsd but it
>> would create an external dependency.
>>
>> Signed-off-by: Nikita Kozlov <nikita@gandi.net>
> Using Red-black tree is a good idea, and we have been doing it for a while
> both on v4 and v6.
Yes, like I said in 1/3, the idea is taken from your patch.
I have tested it and it seemed to work pretty fine, maybe we could try
to split it a little bit and try to send it again ?
It's quite difficult to tell what was wrong with it since I cannot see
any public discussion about it.
>
> But this is not the way to handle it.
> Please don't copy a header file which is available already on both BSD and Linux.
>
>
I was quite hesitant on how to handle it. I had the feeling that dpdk
wanted to avoid external dependency so I copied that file. If it's not
the case I would be happy to resend the patches without that external
import.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common
2016-06-09 14:54 ` Nikita Kozlov
@ 2016-06-09 15:14 ` Thomas Monjalon
0 siblings, 0 replies; 14+ messages in thread
From: Thomas Monjalon @ 2016-06-09 15:14 UTC (permalink / raw)
To: Nikita Kozlov; +Cc: dev, Stephen Hemminger, Takuya ASADA, Takuya ASADA
2016-06-09 16:54, Nikita Kozlov:
> On 06/ 9/16 02:58 AM, Stephen Hemminger wrote:
> > Please don't copy a header file which is available already on both BSD and Linux.
> >
> I was quite hesitant on how to handle it. I had the feeling that dpdk
> wanted to avoid external dependency so I copied that file. If it's not
> the case I would be happy to resend the patches without that external
> import.
Yes please let's use external libraries where possible.
Being able to run in a bare metal environment has been a requirement
in the early days of DPDK. Now we got rid of this idea and run on
Linux and FreeBSD. An attempt to run on OSv has been done but without
more follow-up.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [dpdk-dev] [PATCH 3/3] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
2016-06-09 0:53 ` [dpdk-dev] [PATCH 1/3] lpm6 speed inmprovement " Nikita Kozlov
2016-06-09 0:53 ` [dpdk-dev] [PATCH 2/3] librte_eal: Import FreeBSD sys/tree.h into librte_eal/common Nikita Kozlov
@ 2016-06-09 0:53 ` Nikita Kozlov
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule Nikita Kozlov
` (2 subsequent siblings)
5 siblings, 0 replies; 14+ messages in thread
From: Nikita Kozlov @ 2016-06-09 0:53 UTC (permalink / raw)
To: dev; +Cc: Nikita Kozlov
Modify of test_lpm6.c to reflect that we no longer have a maximum number
of rules.
Check in some places that we are using the same number of tbl8 as the
previous implementation after a rte_lpm6_delete.
Signed-off-by: Nikita Kozlov <nikita@gandi.net>
---
app/test/test_lpm6.c | 131 +++++++++++++++++-----------------
app/test/test_lpm6_perf.c | 5 +-
lib/librte_table/rte_table_lpm_ipv6.c | 7 +-
3 files changed, 72 insertions(+), 71 deletions(-)
diff --git a/app/test/test_lpm6.c b/app/test/test_lpm6.c
index 458a10b..612bcef 100644
--- a/app/test/test_lpm6.c
+++ b/app/test/test_lpm6.c
@@ -114,7 +114,6 @@ rte_lpm6_test tests6[] = {
#define NUM_LPM6_TESTS (sizeof(tests6)/sizeof(tests6[0]))
#define MAX_DEPTH 128
-#define MAX_RULES 1000000
#define NUMBER_TBL8S (1 << 16)
#define MAX_NUM_TBL8S (1 << 21)
#define PASS 0
@@ -153,7 +152,6 @@ test0(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -161,14 +159,7 @@ test0(void)
lpm = rte_lpm6_create(NULL, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm == NULL);
- /* rte_lpm6_create: max_rules = 0 */
- /* Note: __func__ inserts the function name, in this case "test0". */
- config.max_rules = 0;
- lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
- TEST_LPM_ASSERT(lpm == NULL);
-
/* socket_id < -1 is invalid */
- config.max_rules = MAX_RULES;
lpm = rte_lpm6_create(__func__, -2, &config);
TEST_LPM_ASSERT(lpm == NULL);
@@ -195,7 +186,6 @@ test1(void)
struct rte_lpm6 *lpm1 = NULL, *lpm2 = NULL, *lpm3 = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -233,7 +223,6 @@ test2(void)
/* rte_lpm6_free: Free NULL */
for (i = 0; i < 20; i++) {
- config.max_rules = MAX_RULES - i;
lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm != NULL);
@@ -256,7 +245,6 @@ test3(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -278,10 +266,10 @@ test4(void)
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 24, next_hop = 100;
+ uint8_t depth = 24;
+ uint16_t next_hop = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -319,7 +307,6 @@ test5(void)
uint8_t depth = 24;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -354,10 +341,9 @@ test6(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t next_hop_return = 0;
+ uint16_t next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -392,10 +378,9 @@ test7(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[10][16];
- int16_t next_hop_return[10];
+ int32_t next_hop_return[10];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -433,7 +418,6 @@ test8(void)
uint8_t depth[10];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -469,11 +453,11 @@ test9(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 16, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 16;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
uint8_t i;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -517,14 +501,13 @@ test10(void)
int32_t status = 0;
int i;
- config.max_rules = 127;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm != NULL);
- for (i = 1; i < 128; i++) {
+ for (i = 1; i <= 128; i++) {
depth = (uint8_t)i;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
@@ -532,9 +515,9 @@ test10(void)
depth = 128;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == -ENOSPC);
+ TEST_LPM_ASSERT(status == 0);
- depth = 127;
+ depth = 128;
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
@@ -560,43 +543,69 @@ test11(void)
uint8_t depth, next_hop_add = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 16;
config.flags = 0;
lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm != NULL);
+ //use 13 tlb8
depth = 128;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ //14
ip[0] = 1;
depth = 25;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 14);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ //15
depth = 33;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 15);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ //16
depth = 41;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 16);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ //17
depth = 49;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == -ENOSPC);
+ //16
depth = 41;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
@@ -620,7 +629,6 @@ test12(void)
uint8_t depth, next_hop_add = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 16;
config.flags = 0;
@@ -658,7 +666,6 @@ test13(void)
uint8_t depth, next_hop_add = 100;
int32_t status = 0;
- config.max_rules = 2;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -675,9 +682,9 @@ test13(void)
depth = 3;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == -ENOSPC);
+ TEST_LPM_ASSERT(status == 0);
- depth = 2;
+ depth = 3;
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
@@ -706,7 +713,6 @@ test14(void)
int32_t status = 0;
int i;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 256;
config.flags = 0;
@@ -748,10 +754,10 @@ test15(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 24, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 24;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -784,10 +790,10 @@ test16(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {12,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 128, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 128;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -828,10 +834,10 @@ test17(void)
uint8_t ip1[] = {127,255,255,255,255,255,255,255,255,
255,255,255,255,255,255,255};
uint8_t ip2[] = {128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -893,11 +899,11 @@ test18(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16], ip_1[16], ip_2[16];
- uint8_t depth, depth_1, depth_2, next_hop_add, next_hop_add_1,
+ uint8_t depth, depth_1, depth_2;
+ uint16_t next_hop_add, next_hop_add_1,
next_hop_add_2, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1055,10 +1061,10 @@ test19(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1253,10 +1259,10 @@ test20(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1320,11 +1326,11 @@ test21(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip_batch[4][16];
- uint8_t depth, next_hop_add;
- int16_t next_hop_return[4];
+ uint8_t depth;
+ uint16_t next_hop_add;
+ int32_t next_hop_return[4];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1379,10 +1385,9 @@ test22(void)
struct rte_lpm6_config config;
uint8_t ip_batch[5][16];
uint8_t depth[5], next_hop_add;
- int16_t next_hop_return[5];
+ int32_t next_hop_return[5];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1495,10 +1500,10 @@ test23(void)
struct rte_lpm6_config config;
uint32_t i;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1542,7 +1547,6 @@ test24(void)
struct rte_lpm6 *lpm = NULL, *result = NULL;
struct rte_lpm6_config config;
- config.max_rules = 256 * 32;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1579,10 +1583,10 @@ test25(void)
struct rte_lpm6_config config;
uint8_t ip[16];
uint32_t i;
- uint8_t depth, next_hop_add, next_hop_return, next_hop_expected;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return, next_hop_expected;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1629,13 +1633,12 @@ test26(void)
uint8_t d_ip_10_32 = 32;
uint8_t d_ip_10_24 = 24;
uint8_t d_ip_20_25 = 25;
- uint8_t next_hop_ip_10_32 = 100;
- uint8_t next_hop_ip_10_24 = 105;
- uint8_t next_hop_ip_20_25 = 111;
- uint8_t next_hop_return = 0;
+ uint16_t next_hop_ip_10_32 = 100;
+ uint16_t next_hop_ip_10_24 = 105;
+ uint16_t next_hop_ip_20_25 = 111;
+ uint16_t next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1647,7 +1650,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_10_32, &next_hop_return);
- uint8_t test_hop_10_32 = next_hop_return;
+ uint16_t test_hop_10_32 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
@@ -1656,7 +1659,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_10_24, &next_hop_return);
- uint8_t test_hop_10_24 = next_hop_return;
+ uint16_t test_hop_10_24 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
@@ -1665,7 +1668,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_20_25, &next_hop_return);
- uint8_t test_hop_20_25 = next_hop_return;
+ uint16_t test_hop_20_25 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_20_25);
@@ -1704,11 +1707,11 @@ test27(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,0};
- uint8_t depth = 128, next_hop_add = 100, next_hop_return;
+ uint8_t depth = 128;
+ uint16_t next_hop_add = 100, next_hop_return;
int32_t status = 0;
int i, j;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
diff --git a/app/test/test_lpm6_perf.c b/app/test/test_lpm6_perf.c
index b7d4631..ca2ff1e 100644
--- a/app/test/test_lpm6_perf.c
+++ b/app/test/test_lpm6_perf.c
@@ -86,11 +86,10 @@ test_lpm6_perf(void)
struct rte_lpm6_config config;
uint64_t begin, total_time;
unsigned i, j;
- uint8_t next_hop_add = 0xAA, next_hop_return = 0;
+ uint16_t next_hop_add = 0xAA, next_hop_return = 0;
int status = 0;
int64_t count = 0;
- config.max_rules = 1000000;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -143,7 +142,7 @@ test_lpm6_perf(void)
count = 0;
uint8_t ip_batch[NUM_IPS_ENTRIES][16];
- int16_t next_hops[NUM_IPS_ENTRIES];
+ int32_t next_hops[NUM_IPS_ENTRIES];
for (i = 0; i < NUM_IPS_ENTRIES; i++)
memcpy(ip_batch[i], large_ips_table[i].ip, 16);
diff --git a/lib/librte_table/rte_table_lpm_ipv6.c b/lib/librte_table/rte_table_lpm_ipv6.c
index 836f4cf..abd5b28 100644
--- a/lib/librte_table/rte_table_lpm_ipv6.c
+++ b/lib/librte_table/rte_table_lpm_ipv6.c
@@ -129,7 +129,6 @@ rte_table_lpm_ipv6_create(void *params, int socket_id, uint32_t entry_size)
}
/* LPM low-level table creation */
- lpm6_config.max_rules = p->n_rules;
lpm6_config.number_tbl8s = p->number_tbl8s;
lpm6_config.flags = 0;
lpm->lpm = rte_lpm6_create(p->name, socket_id, &lpm6_config);
@@ -213,7 +212,7 @@ rte_table_lpm_ipv6_entry_add(
(struct rte_table_lpm_ipv6_key *) key;
uint32_t nht_pos, nht_pos0_valid;
int status;
- uint8_t nht_pos0;
+ uint16_t nht_pos0;
/* Check input parameters */
if (lpm == NULL) {
@@ -280,7 +279,7 @@ rte_table_lpm_ipv6_entry_delete(
struct rte_table_lpm_ipv6 *lpm = (struct rte_table_lpm_ipv6 *) table;
struct rte_table_lpm_ipv6_key *ip_prefix =
(struct rte_table_lpm_ipv6_key *) key;
- uint8_t nht_pos;
+ uint16_t nht_pos;
int status;
/* Check input parameters */
@@ -356,7 +355,7 @@ rte_table_lpm_ipv6_lookup(
uint8_t *ip = RTE_MBUF_METADATA_UINT8_PTR(pkt,
lpm->offset);
int status;
- uint8_t nht_pos;
+ uint16_t nht_pos;
status = rte_lpm6_lookup(lpm->lpm, ip, &nht_pos);
if (status == 0) {
--
2.8.1
^ permalink raw reply [flat|nested] 14+ messages in thread* [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
` (2 preceding siblings ...)
2016-06-09 0:53 ` [dpdk-dev] [PATCH 3/3] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib Nikita Kozlov
@ 2016-08-24 22:59 ` Nikita Kozlov
2016-09-16 13:15 ` Nikita Kozlov
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 1/2] lpm6: speed inmprovement " Nikita Kozlov
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 2/2] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib Nikita Kozlov
5 siblings, 1 reply; 14+ messages in thread
From: Nikita Kozlov @ 2016-08-24 22:59 UTC (permalink / raw)
To: dev
This serie of pathes focus on improving the speed of deleting rules in lpm6.
It also contains some other improvement like having a dynamic number of
rules in lpm6 and increasing the lpm6 nexthop size to 16bit for matching
the nexthop size in lpm4.
The performances improvement can be seen by running test_lpm6_perf but
because of the limited number of rules added (1000) the improvement seen is
just about a x10 with this test.
For testing it further we have tested it with a full ipv6 bgp view which
represent 29296 routes in our test:
* With the dpdk 16.04 it tooks an average of 8.46095e+09 cycles to delete a rule
(calculated with mesuring rte_rdtsc before and after the delete, the
average is calculated by the first 10 delete, it represents several
seconds on a E5-2650 v2)
* With the patch it tooks 10077.1 cycles (same number of deleted rules,
same machine, same rules inserted) for the same test.
This patch was written in collaboration with Baptiste Daroussin from Gandi.
Changes since V1:
- use system bsd-tree.h
- fix a bug when valid_group field was overwritten
Nikita Kozlov (2):
lpm6: speed inmprovement on delete rule
test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib
app/test/test_lpm6.c | 244 +++++--------
app/test/test_lpm6_perf.c | 6 +-
lib/librte_lpm/Makefile | 2 +-
lib/librte_lpm/rte_lpm6.c | 626 +++++++++++++++++++++++++---------
lib/librte_lpm/rte_lpm6.h | 50 ++-
lib/librte_lpm/rte_lpm_version.map | 12 +
lib/librte_table/rte_table_lpm_ipv6.c | 7 +-
7 files changed, 609 insertions(+), 338 deletions(-)
--
2.9.2
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule Nikita Kozlov
@ 2016-09-16 13:15 ` Nikita Kozlov
2016-12-23 6:07 ` Paras Kumar
2017-02-22 15:23 ` Bruce Richardson
0 siblings, 2 replies; 14+ messages in thread
From: Nikita Kozlov @ 2016-09-16 13:15 UTC (permalink / raw)
To: dev
On 08/25/2016 00:59, Nikita Kozlov wrote:
> This serie of pathes focus on improving the speed of deleting rules in lpm6.
>
> It also contains some other improvement like having a dynamic number of
> rules in lpm6 and increasing the lpm6 nexthop size to 16bit for matching
> the nexthop size in lpm4.
>
> The performances improvement can be seen by running test_lpm6_perf but
> because of the limited number of rules added (1000) the improvement seen is
> just about a x10 with this test.
>
> For testing it further we have tested it with a full ipv6 bgp view which
> represent 29296 routes in our test:
> * With the dpdk 16.04 it tooks an average of 8.46095e+09 cycles to delete a rule
> (calculated with mesuring rte_rdtsc before and after the delete, the
> average is calculated by the first 10 delete, it represents several
> seconds on a E5-2650 v2)
> * With the patch it tooks 10077.1 cycles (same number of deleted rules,
> same machine, same rules inserted) for the same test.
>
> This patch was written in collaboration with Baptiste Daroussin from Gandi.
>
> Changes since V1:
> - use system bsd-tree.h
> - fix a bug when valid_group field was overwritten
>
> Nikita Kozlov (2):
> lpm6: speed inmprovement on delete rule
> test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib
>
> app/test/test_lpm6.c | 244 +++++--------
> app/test/test_lpm6_perf.c | 6 +-
> lib/librte_lpm/Makefile | 2 +-
> lib/librte_lpm/rte_lpm6.c | 626 +++++++++++++++++++++++++---------
> lib/librte_lpm/rte_lpm6.h | 50 ++-
> lib/librte_lpm/rte_lpm_version.map | 12 +
> lib/librte_table/rte_table_lpm_ipv6.c | 7 +-
> 7 files changed, 609 insertions(+), 338 deletions(-)
>
Hello,
If someone have some time, I feel that this patch needs some polishing
so any comments on the code are more than welcome, even if they are not
directly related to the lpm part itself.
thanks.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule
2016-09-16 13:15 ` Nikita Kozlov
@ 2016-12-23 6:07 ` Paras Kumar
2017-02-22 15:23 ` Bruce Richardson
1 sibling, 0 replies; 14+ messages in thread
From: Paras Kumar @ 2016-12-23 6:07 UTC (permalink / raw)
To: dev
Hi,
I have used this lpm6 speed improvement patch for BGPv6 by *Nikita
Kozlov*. it works great for fixed prefix length however, when i use
variable prefix length for routes after 2 iterations of addition and
deletion of routes (30000 approx) lpm6 crashes in expand_rule due to
stack overflow. The ext bit in rte_lpm6_tbl_entry comes out to be 1
every time.
Regards
Paras
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule
2016-09-16 13:15 ` Nikita Kozlov
2016-12-23 6:07 ` Paras Kumar
@ 2017-02-22 15:23 ` Bruce Richardson
1 sibling, 0 replies; 14+ messages in thread
From: Bruce Richardson @ 2017-02-22 15:23 UTC (permalink / raw)
To: Nikita Kozlov; +Cc: dev
On Fri, Sep 16, 2016 at 03:15:01PM +0200, Nikita Kozlov wrote:
> On 08/25/2016 00:59, Nikita Kozlov wrote:
> > This serie of pathes focus on improving the speed of deleting rules in lpm6.
> >
> > It also contains some other improvement like having a dynamic number of
> > rules in lpm6 and increasing the lpm6 nexthop size to 16bit for matching
> > the nexthop size in lpm4.
> >
> > The performances improvement can be seen by running test_lpm6_perf but
> > because of the limited number of rules added (1000) the improvement seen is
> > just about a x10 with this test.
> >
> > For testing it further we have tested it with a full ipv6 bgp view which
> > represent 29296 routes in our test:
> > * With the dpdk 16.04 it tooks an average of 8.46095e+09 cycles to delete a rule
> > (calculated with mesuring rte_rdtsc before and after the delete, the
> > average is calculated by the first 10 delete, it represents several
> > seconds on a E5-2650 v2)
> > * With the patch it tooks 10077.1 cycles (same number of deleted rules,
> > same machine, same rules inserted) for the same test.
> >
> > This patch was written in collaboration with Baptiste Daroussin from Gandi.
> >
> > Changes since V1:
> > - use system bsd-tree.h
> > - fix a bug when valid_group field was overwritten
> >
> > Nikita Kozlov (2):
> > lpm6: speed inmprovement on delete rule
> > test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib
> >
> > app/test/test_lpm6.c | 244 +++++--------
> > app/test/test_lpm6_perf.c | 6 +-
> > lib/librte_lpm/Makefile | 2 +-
> > lib/librte_lpm/rte_lpm6.c | 626 +++++++++++++++++++++++++---------
> > lib/librte_lpm/rte_lpm6.h | 50 ++-
> > lib/librte_lpm/rte_lpm_version.map | 12 +
> > lib/librte_table/rte_table_lpm_ipv6.c | 7 +-
> > 7 files changed, 609 insertions(+), 338 deletions(-)
> >
> Hello,
> If someone have some time, I feel that this patch needs some polishing
> so any comments on the code are more than welcome, even if they are not
> directly related to the lpm part itself.
>
> thanks.
Resurrecting this old thread, having spotted the patches in patchwork.
I've run some before/after tests with lpm6_perf_autotest. The results I
get show the delete performance improving ~33x with this patch applied.
(That's 33x, not 33%!). That's less than the numbers claimed above for a
real-world case, but still very, very impressive.
I see some regression with the add cycles, but *only* about 20% or so. I
can live with that for the improvement in delete speed.
The big issue I spotted with these two patches is that they need to be
merged together, since patch 2 fixes the compile errors introduced with
patch 1. Once the patches are combined then that combined patch should
ideally be split into smaller onces for the individual changes made:
i.e. any changes not part of the rework of delete, should be in
different patches, but the repo should compile after each patch has been
applied.
I note also, that there is another patches outstanding on DPDK to
increase the next-hop size to 21 bits. That patch conflicts with this
one, but it probably should go in first as it's a smaller simpler
change, and this set needs a revision.
So, any plans for a V3 of this set?
Regards,
/Bruce
^ permalink raw reply [flat|nested] 14+ messages in thread
* [dpdk-dev] [PATCH v2 1/2] lpm6: speed inmprovement on delete rule
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
` (3 preceding siblings ...)
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 0/2] lpm6: speed improvement on delete rule Nikita Kozlov
@ 2016-08-24 22:59 ` Nikita Kozlov
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 2/2] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib Nikita Kozlov
5 siblings, 0 replies; 14+ messages in thread
From: Nikita Kozlov @ 2016-08-24 22:59 UTC (permalink / raw)
To: dev; +Cc: Nikita Kozlov, Baptiste Daroussin
Rewrite rte_lpm6_delete* logic for deleting only the selected rule
instead of deleting all rules and re-inserting them.
the delete_step() function is called recursively and delete the rule
until the rule depth is covered. Then it calls delete_expand_step()
which will ensure to delete the expanded part of the rule if any.
The tbl8 are now allocated more dynamically through tbl8_alloc() which
will walk through all tbl8 for finding an empty one.
The rules are now stored in a RB-tree so we can have a dynamic number of
them. This part of the patch is inspired by
http://dpdk.org/dev/patchwork/patch/7981/ .
Adding of rte_lpm6_tbl8_count() and rte_lpm6_tbl8_free_count() which
permits to check that we are freeing correctly our tbl8 and permits to
check how much free tbl8 we have for adding new rules.
For consistency with lpm4, increase lpm6 nexthop size from 8bit to
16bit.
This patch was written in collaboration with Baptiste Daroussin from Gandi.
Signed-off-by: Nikita Kozlov <nikita@gandi.net>
Signed-off-by: Baptiste Daroussin <bapt@gandi.net>
---
lib/librte_lpm/Makefile | 2 +-
lib/librte_lpm/rte_lpm6.c | 626 +++++++++++++++++++++++++++----------
lib/librte_lpm/rte_lpm6.h | 50 ++-
lib/librte_lpm/rte_lpm_version.map | 12 +
4 files changed, 525 insertions(+), 165 deletions(-)
diff --git a/lib/librte_lpm/Makefile b/lib/librte_lpm/Makefile
index 656ade2..cbab7da 100644
--- a/lib/librte_lpm/Makefile
+++ b/lib/librte_lpm/Makefile
@@ -39,7 +39,7 @@ CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
EXPORT_MAP := rte_lpm_version.map
-LIBABIVER := 2
+LIBABIVER := 3
# all source are stored in SRCS-y
SRCS-$(CONFIG_RTE_LIBRTE_LPM) := rte_lpm.c rte_lpm6.c
diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
index 32fdba0..e449152 100644
--- a/lib/librte_lpm/rte_lpm6.c
+++ b/lib/librte_lpm/rte_lpm6.c
@@ -52,6 +52,12 @@
#include <rte_errno.h>
#include <rte_rwlock.h>
#include <rte_spinlock.h>
+#include <rte_compat.h>
+#ifdef RTE_EXEC_ENV_BSDAPP
+# include <sys/tree.h>
+#else
+# include <bsd/sys/tree.h>
+#endif
#include "rte_lpm6.h"
@@ -97,27 +103,46 @@ struct rte_lpm6_tbl_entry {
/** Rules tbl entry structure. */
struct rte_lpm6_rule {
uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
- uint8_t next_hop; /**< Rule next hop. */
+ uint16_t next_hop; /**< Rule next hop. */
uint8_t depth; /**< Rule depth. */
+ RB_ENTRY(rte_lpm6_rule) link;
};
/** LPM6 structure. */
struct rte_lpm6 {
/* LPM metadata. */
char name[RTE_LPM6_NAMESIZE]; /**< Name of the lpm. */
- 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 rules. */
+ RB_HEAD(rte_lpm6_rules_tree, rte_lpm6_rule) rules[RTE_LPM6_MAX_DEPTH + 1];
/* LPM Tables. */
- struct rte_lpm6_rule *rules_tbl; /**< LPM rules. */
struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
__rte_cache_aligned; /**< LPM tbl24 table. */
struct rte_lpm6_tbl_entry tbl8[0]
__rte_cache_aligned; /**< LPM tbl8 table. */
};
+/* Comparison function for red-black tree nodes.
+ "If the first argument is smaller than the second, the function
+ returns a value smaller than zero. If they are equal, the function
+ returns zero. Otherwise, it should return a value greater than zero."
+*/
+static inline int rules_cmp(const struct rte_lpm6_rule *r1,
+ const struct rte_lpm6_rule *r2)
+{
+ return memcmp(r1->ip, r2->ip, RTE_LPM6_IPV6_ADDR_SIZE);
+}
+
+/* Satisfy old style attribute in tree.h header */
+#ifndef __unused
+#define __unused __attribute__ ((unused))
+#endif
+
+/* Generate internal functions and make them static. */
+RB_GENERATE_STATIC(rte_lpm6_rules_tree, rte_lpm6_rule, link, rules_cmp)
+
/*
* Takes an array of uint8_t (IPv6 address) and masks it using the depth.
* It leaves untouched one bit per unit in the depth variable
@@ -126,8 +151,8 @@ struct rte_lpm6 {
static inline void
mask_ip(uint8_t *ip, uint8_t depth)
{
- int16_t part_depth, mask;
- int i;
+ int16_t part_depth, mask;
+ int i;
part_depth = depth;
@@ -152,7 +177,8 @@ 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;
+ unsigned int depth;
struct rte_lpm6_list *lpm_list;
lpm_list = RTE_TAILQ_CAST(rte_lpm6_tailq.head, rte_lpm6_list);
@@ -161,7 +187,6 @@ rte_lpm6_create(const char *name, int socket_id,
/* Check user arguments. */
if ((name == NULL) || (socket_id < -1) || (config == NULL) ||
- (config->max_rules == 0) ||
config->number_tbl8s > RTE_LPM6_TBL8_MAX_NUM_GROUPS) {
rte_errno = EINVAL;
return NULL;
@@ -172,7 +197,6 @@ rte_lpm6_create(const char *name, int socket_id,
/* 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);
@@ -205,22 +229,14 @@ rte_lpm6_create(const char *name, int socket_id,
goto exit;
}
- lpm->rules_tbl = (struct rte_lpm6_rule *)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);
- goto exit;
- }
-
/* Save user arguments. */
- lpm->max_rules = config->max_rules;
lpm->number_tbl8s = config->number_tbl8s;
snprintf(lpm->name, sizeof(lpm->name), "%s", name);
+ /* Vyatta change to use red-black tree */
+ for (depth = 0; depth <= RTE_LPM6_MAX_DEPTH; ++depth)
+ RB_INIT(&lpm->rules[depth]);
+
te->data = (void *) lpm;
TAILQ_INSERT_TAIL(lpm_list, te, next);
@@ -286,8 +302,8 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
TAILQ_REMOVE(lpm_list, te, next);
rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+ rte_lpm6_delete_all(lpm);
- rte_free(lpm->rules_tbl);
rte_free(lpm);
rte_free(te);
}
@@ -296,41 +312,87 @@ rte_lpm6_free(struct rte_lpm6 *lpm)
* 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.
*/
-static inline int32_t
-rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t next_hop, uint8_t depth)
+static struct rte_lpm6_rule *
+rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint16_t next_hop, uint8_t depth)
{
- uint32_t rule_index;
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule *r, *old;
+
+ /*
+ * NB: uses regular malloc to avoid chewing up precious
+ * memory pool space for rules.
+ */
+ r = malloc(sizeof(*r));
+ if (!r)
+ return NULL;
+
+ rte_memcpy(r->ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ r->next_hop = next_hop;
+ r->depth = depth;
- /* Scan through rule list to see if rule already exists. */
- for (rule_index = 0; rule_index < lpm->used_rules; rule_index++) {
+ old = RB_INSERT(rte_lpm6_rules_tree, head, r);
+ if (!old)
+ return r;
- /* 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;
+ /* collision with existing rule */
+ free(r);
- return rule_index;
+ return old;
+}
+
+/*
+ * Find, clean and allocate a tbl8.
+ */
+static inline int32_t
+tbl8_alloc(struct rte_lpm6 *lpm)
+{
+ uint32_t tbl8_gindex; /* tbl8 group index. */
+ struct rte_lpm6_tbl_entry *tbl8_entry;
+ struct rte_lpm6_tbl_entry *tbl8 = lpm->tbl8;
+
+ /* Scan through tbl8 to find a free (i.e. INVALID) tbl8 group. */
+ for (tbl8_gindex = 0; tbl8_gindex < lpm->number_tbl8s;
+ tbl8_gindex++) {
+ tbl8_entry = &tbl8[tbl8_gindex * RTE_LPM6_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_LPM6_TBL8_GROUP_NUM_ENTRIES *
+ sizeof(tbl8_entry[0]));
+
+ tbl8_entry->valid_group = VALID;
+ rte_compiler_barrier();
+
+ /* Return group index for allocated tbl8 group. */
+ return tbl8_gindex;
}
}
- /*
- * 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) {
- return -ENOSPC;
- }
+ /* If there are no tbl8 groups free then return error. */
+ 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;
+static inline void
+tbl8_free(struct rte_lpm6_tbl_entry *tbl8, uint32_t tbl8_group_start)
+{
+ /* Set tbl8 group invalid */
+ /* XXX: a tbl8[tbl8_group_start].valid_group = INVALID should be enough */
+ memset(&tbl8[tbl8_group_start], 0, RTE_LPM6_TBL8_GROUP_NUM_ENTRIES *
+ sizeof(tbl8[0]));
+}
- /* Increment the used rules counter for this rule group. */
- lpm->used_rules++;
+static int
+tbl8_is_free(struct rte_lpm6_tbl_entry *tbl8, uint32_t tbl8_group_start)
+{
+ uint32_t i, tbl8_group_end;
+ tbl8_group_end = tbl8_group_start +
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
- return rule_index;
+ for (i = tbl8_group_start; i < tbl8_group_end; i++) {
+ if (tbl8[i].valid)
+ return 0;
+ }
+ return 1;
}
/*
@@ -340,7 +402,7 @@ rule_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t next_hop, uint8_t depth)
*/
static void
expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
- uint8_t next_hop)
+ uint16_t next_hop)
{
uint32_t tbl8_group_end, tbl8_gindex_next, j;
@@ -354,6 +416,8 @@ expand_rule(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
.ext_entry = 0,
};
+ rte_compiler_barrier();
+
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)) {
@@ -377,7 +441,7 @@ 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, uint8_t next_hop)
+ uint8_t first_byte, uint8_t depth, uint16_t next_hop)
{
uint32_t tbl_index, tbl_range, tbl8_group_start, tbl8_group_end, i;
int32_t tbl8_gindex;
@@ -404,20 +468,22 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
* expand the rule across the relevant positions in the table.
*/
if (depth <= bits_covered) {
+ struct rte_lpm6_tbl_entry new_tbl_entry = {
+ .next_hop = next_hop,
+ .depth = depth,
+ .valid = VALID,
+ .valid_group = VALID,
+ .ext_entry = 0,
+ };
+
+ rte_compiler_barrier();
+
tbl_range = 1 << (bits_covered - depth);
for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
if (!tbl[i].valid || (tbl[i].ext_entry == 0 &&
tbl[i].depth <= depth)) {
- struct rte_lpm6_tbl_entry new_tbl_entry = {
- .next_hop = next_hop,
- .depth = depth,
- .valid = VALID,
- .valid_group = VALID,
- .ext_entry = 0,
- };
-
tbl[i] = new_tbl_entry;
} else if (tbl[i].ext_entry == 1) {
@@ -441,10 +507,10 @@ 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
+ tbl8_gindex = tbl8_alloc(lpm);
+ if (tbl8_gindex < 0) {
return -ENOSPC;
+ }
struct rte_lpm6_tbl_entry new_tbl_entry = {
.lpm6_tbl8_gindex = tbl8_gindex,
@@ -454,6 +520,8 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
.ext_entry = 1,
};
+ rte_compiler_barrier();
+
tbl[tbl_index] = new_tbl_entry;
}
/*
@@ -461,12 +529,10 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
* 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
+ tbl8_gindex = tbl8_alloc(lpm);
+ if (tbl8_gindex < 0) {
return -ENOSPC;
-
+ }
tbl8_group_start = tbl8_gindex *
RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
tbl8_group_end = tbl8_group_start +
@@ -493,6 +559,8 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
.ext_entry = 1,
};
+ rte_compiler_barrier();
+
tbl[tbl_index] = new_tbl_entry;
}
@@ -503,19 +571,26 @@ add_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
return 1;
}
+int
+rte_lpm6_add_v1604(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint8_t next_hop)
+{
+ return rte_lpm6_add_v1611(lpm, ip, depth, next_hop);
+}
+VERSION_SYMBOL(rte_lpm6_add, _v1604, 16.04);
+
/*
* Add a route
*/
int
-rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
- uint8_t next_hop)
+rte_lpm6_add_v1611(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop)
{
struct rte_lpm6_tbl_entry *tbl;
struct rte_lpm6_tbl_entry *tbl_next;
- int32_t rule_index;
- int status;
+ struct rte_lpm6_rule *rule;
+ int status, i;
uint8_t masked_ip[RTE_LPM6_IPV6_ADDR_SIZE];
- int i;
/* Check user arguments. */
if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM6_MAX_DEPTH))
@@ -526,14 +601,14 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
mask_ip(masked_ip, depth);
/* Add the rule to the rule table. */
- rule_index = rule_add(lpm, masked_ip, next_hop, depth);
+ rule = rule_add(lpm, masked_ip, next_hop, depth);
/* If there is no space available for new rule return error. */
- if (rule_index < 0) {
- return rule_index;
+ if (rule == NULL) {
+ return -EINVAL;
}
- /* Inspect the first three bytes through tbl24 on the first step. */
+ /* 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);
@@ -544,7 +619,7 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
}
/*
- * Inspect one by one the rest of the bytes until
+ * 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 && status == 1; i++) {
@@ -560,6 +635,10 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
return status;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_add, _v1611, 16.11);
+MAP_STATIC_SYMBOL(int rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip,
+ uint8_t depth, uint16_t next_hop), rte_lpm6_add_v1611);
+
/*
* Takes a pointer to a table entry and inspect one level.
@@ -569,7 +648,7 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
static inline int
lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
const struct rte_lpm6_tbl_entry **tbl_next, uint8_t *ip,
- uint8_t first_byte, uint8_t *next_hop)
+ uint8_t first_byte, uint16_t *next_hop)
{
uint32_t tbl8_index, tbl_entry;
@@ -589,16 +668,24 @@ lookup_step(const struct rte_lpm6 *lpm, const struct rte_lpm6_tbl_entry *tbl,
return 1;
} else {
/* If not extended then we can have a match. */
- *next_hop = (uint8_t)tbl_entry;
+ *next_hop = (uint16_t)tbl_entry;
return (tbl_entry & RTE_LPM6_LOOKUP_SUCCESS) ? 0 : -ENOENT;
}
}
+int
+rte_lpm6_lookup_v1604(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
+{
+ return rte_lpm6_lookup_v1611(lpm, ip, (uint16_t *)next_hop);
+}
+VERSION_SYMBOL(rte_lpm6_lookup, _v1604, 16.04);
+
/*
* Looks up an IP
*/
int
-rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
+rte_lpm6_lookup_v1611(const struct rte_lpm6 *lpm, uint8_t *ip,
+ uint16_t *next_hop)
{
const struct rte_lpm6_tbl_entry *tbl;
const struct rte_lpm6_tbl_entry *tbl_next = NULL;
@@ -625,20 +712,33 @@ rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop)
return status;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_lookup, _v1611, 16.11);
+MAP_STATIC_SYMBOL(int rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip,
+ uint16_t *next_hop), rte_lpm6_lookup_v1611);
+
+int
+rte_lpm6_lookup_bulk_func_v1604(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int16_t *next_hops, unsigned n)
+{
+ return rte_lpm6_lookup_bulk_func_v1611(lpm, ips, (int32_t *)next_hops, n);
+}
+VERSION_SYMBOL(rte_lpm6_lookup_bulk_func, _v1604, 16.04);
/*
* Looks up a group of IP addresses
*/
int
-rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
+rte_lpm6_lookup_bulk_func_v1611(const struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
- int16_t * next_hops, unsigned n)
+ int32_t * next_hops, unsigned n)
{
unsigned i;
const struct rte_lpm6_tbl_entry *tbl;
const struct rte_lpm6_tbl_entry *tbl_next = NULL;
uint32_t tbl24_index;
- uint8_t first_byte, next_hop;
+ uint8_t first_byte;
+ uint16_t next_hop;
int status;
/* DEBUG: Check user input arguments. */
@@ -669,40 +769,66 @@ rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
return 0;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_lookup_bulk_func, _v1611, 16.11);
+MAP_STATIC_SYMBOL(int rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], int32_t *next_hops,
+ unsigned n), rte_lpm6_lookup_bulk_func_v1611);
/*
* Finds a rule in rule table.
- * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
+ * NOTE: Valid range for depth parameter is 0 .. 128 inclusive.
*/
-static inline int32_t
+static struct rte_lpm6_rule *
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) {
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule k;
+
+ rte_memcpy(k.ip, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+
+ return RB_FIND(rte_lpm6_rules_tree, head, &k);
+}
+
+static struct rte_lpm6_rule *
+find_previous_rule(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint8_t *sub_rule_depth)
+{
+ struct rte_lpm6_rule *rule;
+ uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+ int prev_depth;
- return rule_index;
+ /* Copy the IP and mask it to avoid modifying user's input data. */
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ for (prev_depth = depth; prev_depth >= 0; prev_depth--) {
+ mask_ip(ip_masked, prev_depth);
+ rule = rule_find(lpm, ip_masked, prev_depth);
+ if (rule) {
+ *sub_rule_depth = prev_depth;
+ return rule;
}
}
- /* If rule is not found return -ENOENT. */
- return -ENOENT;
+ return NULL;
+}
+
+int
+rte_lpm6_is_rule_present_v1604(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint8_t *next_hop)
+{
+ return rte_lpm6_is_rule_present_v1611(lpm, ip, depth, (uint16_t*)next_hop);
}
+VERSION_SYMBOL(rte_lpm6_is_rule_present, _v1604, 16.04);
/*
* Look for a rule in the high-level rules table
*/
int
-rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
-uint8_t *next_hop)
+rte_lpm6_is_rule_present_v1611(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t *next_hop)
{
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
- int32_t rule_index;
+ struct rte_lpm6_rule *rule;
/* Check user arguments. */
if ((lpm == NULL) || next_hop == NULL || ip == NULL ||
@@ -710,34 +836,214 @@ uint8_t *next_hop)
return -EINVAL;
/* Copy the IP and mask it to avoid modifying user's input data. */
- memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
mask_ip(ip_masked, depth);
/* Look for the rule using rule_find. */
- rule_index = rule_find(lpm, ip_masked, depth);
+ rule = rule_find(lpm, ip, depth);
- if (rule_index >= 0) {
- *next_hop = lpm->rules_tbl[rule_index].next_hop;
+ if (rule != NULL) {
+ *next_hop = rule->next_hop;
return 1;
}
/* If rule is not found return 0. */
return 0;
}
+BIND_DEFAULT_SYMBOL(rte_lpm6_is_rule_present, _v1611, 16.11);
+MAP_STATIC_SYMBOL(int rte_lpm6_is_rule_present(struct rte_lpm6 *lpm,
+ uint8_t *ip, uint8_t depth, uint16_t *next_hop),
+ rte_lpm6_is_rule_present_v1611);
/*
* Delete a rule from the rule table.
- * NOTE: Valid range for depth parameter is 1 .. 128 inclusive.
+ * NOTE: Valid range for depth parameter is 0 .. 128 inclusive.
*/
static inline void
-rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)
+rule_delete(struct rte_lpm6 *lpm, struct rte_lpm6_rule *r, uint8_t depth)
{
- /*
- * Overwrite redundant rule with last rule in group and decrement rule
- * counter.
- */
- lpm->rules_tbl[rule_index] = lpm->rules_tbl[lpm->used_rules-1];
- lpm->used_rules--;
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+
+ RB_REMOVE(rte_lpm6_rules_tree, head, r);
+
+ free(r);
+}
+
+/*
+ * Function that run through the data structure when and clean entries
+ * that where expanded by expand_rule().
+ */
+static void
+delete_expand_step(struct rte_lpm6 *lpm, uint32_t tbl8_gindex, uint8_t depth,
+ uint16_t next_hop, struct rte_lpm6_rule *sub_rule)
+{
+ 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 empty_tbl8_entry = {
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .depth = 0,
+ .next_hop = 0,
+ .ext_entry = 0,
+ };
+
+ if (sub_rule) {
+ empty_tbl8_entry.depth = sub_rule->depth;
+ empty_tbl8_entry.next_hop = sub_rule->next_hop;
+ }
+
+ rte_compiler_barrier();
+
+ 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].next_hop == next_hop) {
+
+ if (lpm->tbl8[j].valid_group) {
+ lpm->tbl8[j] = empty_tbl8_entry;
+ lpm->tbl8[j].valid_group = VALID;
+ } else {
+ lpm->tbl8[j] = empty_tbl8_entry;
+ }
+
+ } else if (lpm->tbl8[j].ext_entry == 1) {
+
+ tbl8_gindex_next = lpm->tbl8[j].lpm6_tbl8_gindex
+ * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ delete_expand_step(lpm, tbl8_gindex_next, depth, next_hop, sub_rule);
+ }
+ }
+}
+/*
+ * Partially delete a route from the data structure (tbl24+tbl8s).
+ * It may be called and partially added routes (after an unsuccesful add_step).
+ */
+static void
+delete_step(struct rte_lpm6 *lpm, struct rte_lpm6_tbl_entry *tbl,
+ uint8_t *ip, uint32_t tbl_group_start, struct rte_lpm6_rule *sub_rule,
+ uint8_t depth, uint8_t bits_covered, uint16_t next_hop)
+{
+ uint32_t i, tbl_index = tbl_group_start + ip[bits_covered / 8 - 1];
+ struct rte_lpm6_tbl_entry empty_tbl8_entry = {
+ .valid = INVALID,
+ .valid_group = INVALID,
+ .depth = 0,
+ .next_hop = 0,
+ .ext_entry = 0,
+ };
+
+ rte_compiler_barrier();
+
+ /* recurse until we are at the last tbl8 that should have been deleted for
+ * this rule without an expand */
+ if (depth > bits_covered) {
+ uint32_t tbl_group_next;
+
+ /* check if we have a partially added rule */
+ if (tbl[tbl_index].ext_entry == 1) {
+ /* calculate the next tbl_index */
+ tbl_group_next = tbl[tbl_index].lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ delete_step(lpm, lpm->tbl8, ip, tbl_group_next, sub_rule, depth,
+ bits_covered + 8, next_hop);
+ }
+ } else {
+ uint32_t tbl_range;
+
+ /* last iteration, we may need to remove what we have done through the
+ * expand */
+ tbl_range = 1 << (bits_covered - depth);
+ for (i = tbl_index; i < (tbl_index + tbl_range); i++) {
+ if (tbl[i].ext_entry == 1) {
+ uint32_t tbl_group_next = tbl[i].lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+
+ delete_expand_step(lpm, tbl_group_next, depth, next_hop, sub_rule);
+ } else {
+ /* do a normal cleaning */
+ if (tbl[i].depth == depth) {
+ if (sub_rule) {
+ tbl[i].depth = sub_rule->depth;
+ tbl[i].next_hop = sub_rule->next_hop;
+ } else {
+ if (tbl[i].valid_group) {
+ tbl[i] = empty_tbl8_entry;
+ tbl[i].valid_group = VALID;
+ } else {
+ tbl[i] = empty_tbl8_entry;
+ }
+ }
+ }
+ }
+ }
+
+ /* if we have free the whole range (no more valid entry), clean it totally,
+ * maybe a tbl8[tbl_group_start].valid_group = INVALID maybe enough */
+ if (tbl8_is_free(lpm->tbl8, tbl_group_start)) {
+ tbl8_free(lpm->tbl8, tbl_group_start);
+ }
+ return;
+ }
+
+ /* check if we can recycle the current tbl_entry because we have cleaned all
+ * its childs */
+ if (tbl[tbl_index].ext_entry) {
+ if (tbl8_is_free(lpm->tbl8, tbl[tbl_index].lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES)) {
+ tbl8_free(lpm->tbl8, tbl[tbl_index].lpm6_tbl8_gindex *
+ RTE_LPM6_TBL8_GROUP_NUM_ENTRIES);
+ if (tbl[tbl_index].valid_group) {
+ tbl[tbl_index] = empty_tbl8_entry;
+ tbl[tbl_index].valid_group = VALID;
+ } else {
+ tbl[tbl_index] = empty_tbl8_entry;
+ }
+ }
+ }
+
+ /* we are recursing on the tbl24 so we don't need to check those cases */
+ if (bits_covered == 24) {
+ return;
+ }
+
+ /* try to clean our current tbl group from tbl_group_start to tbl_group_end */
+ for (i = tbl_group_start;
+ i < tbl_group_start + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES; i++) {
+ if (tbl[i].valid == 1) {
+ break;
+ }
+ }
+ if (i == tbl_group_start + RTE_LPM6_TBL8_GROUP_NUM_ENTRIES) {
+ /* we can free a whole group */
+ tbl8_free(lpm->tbl8, tbl_group_start);
+ }
+}
+
+/*
+ * Find rule to replace the just deleted. If there is no rule to
+ * replace the rule_to_delete we return NULL and invalidate the table
+ * entries associated with this rule.
+ */
+static void
+rule_replace(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop)
+{
+ uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
+ struct rte_lpm6_rule *sub_rule;
+ uint8_t sub_depth = 0;
+ uint32_t tbl_index;
+
+ /* Copy the IP and mask it to avoid modifying user's input data. */
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ mask_ip(ip_masked, depth);
+
+ sub_rule = find_previous_rule(lpm, ip_masked, depth, &sub_depth);
+
+ tbl_index = (ip_masked[0] << BYTES2_SIZE) | (ip_masked[1] << BYTE_SIZE);
+
+ delete_step(lpm, lpm->tbl24, ip_masked, tbl_index, sub_rule, depth, 24,
+ next_hop);
}
/*
@@ -746,9 +1052,9 @@ rule_delete(struct rte_lpm6 *lpm, int32_t rule_index)
int
rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
{
- int32_t rule_to_delete_index;
+ struct rte_lpm6_rule *rule;
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
- unsigned i;
+ uint16_t next_hop;
/*
* Check input arguments.
@@ -758,42 +1064,29 @@ rte_lpm6_delete(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth)
}
/* Copy the IP and mask it to avoid modifying user's input data. */
- memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
+ rte_memcpy(ip_masked, ip, RTE_LPM6_IPV6_ADDR_SIZE);
mask_ip(ip_masked, depth);
/*
* 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);
+ rule = rule_find(lpm, ip_masked, depth);
/*
* Check if rule_to_delete_index was found. If no rule was found the
* function rule_find returns -ENOENT.
*/
- if (rule_to_delete_index < 0)
- return rule_to_delete_index;
+ if (rule == NULL)
+ return -EINVAL;
- /* Delete the rule from the rule table. */
- rule_delete(lpm, rule_to_delete_index);
+ next_hop = rule->next_hop;
- /*
- * 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);
+ /* Delete the rule from the rule table. */
+ rule_delete(lpm, rule, depth);
- /*
- * Add every rule again (except for the one that was removed from
- * the rules table).
- */
- for (i = 0; i < lpm->used_rules; i++) {
- rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
- lpm->rules_tbl[i].next_hop);
- }
+ /* Replace with next level up rule */
+ rule_replace(lpm, ip_masked, depth, next_hop);
return 0;
}
@@ -805,9 +1098,10 @@ int
rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE], uint8_t *depths, unsigned n)
{
- int32_t rule_to_delete_index;
+ struct rte_lpm6_rule *rule;
uint8_t ip_masked[RTE_LPM6_IPV6_ADDR_SIZE];
unsigned i;
+ uint16_t next_hop;
/*
* Check input arguments.
@@ -825,51 +1119,45 @@ rte_lpm6_delete_bulk_func(struct rte_lpm6 *lpm,
* 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, depths[i]);
+ rule = rule_find(lpm, ip_masked, depths[i]);
/*
* Check if rule_to_delete_index was found. If no rule was found the
* function rule_find returns -ENOENT.
*/
- if (rule_to_delete_index < 0)
+ if (rule == NULL)
continue;
- /* Delete the rule from the rule table. */
- rule_delete(lpm, rule_to_delete_index);
- }
+ next_hop = rule->next_hop;
- /*
- * 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);
+ /* Delete the rule from the rule table. */
+ rule_delete(lpm, rule, depths[i]);
- /*
- * Add every rule again (except for the ones that were removed from
- * the rules table).
- */
- for (i = 0; i < lpm->used_rules; i++) {
- rte_lpm6_add(lpm, lpm->rules_tbl[i].ip, lpm->rules_tbl[i].depth,
- lpm->rules_tbl[i].next_hop);
+ /* Replace with next level up rule */
+ rule_replace(lpm, ip_masked, depths[i], next_hop);
}
return 0;
}
+
/*
* Delete all rules from the LPM table.
*/
void
rte_lpm6_delete_all(struct rte_lpm6 *lpm)
{
- /* Zero used rules counter. */
- lpm->used_rules = 0;
+ uint8_t depth;
- /* Zero next tbl8 index. */
- lpm->next_tbl8 = 0;
+ /* Delete all rules form the rules table. */
+ for (depth = 0; depth < RTE_LPM6_MAX_DEPTH; ++depth) {
+ struct rte_lpm6_rules_tree *head = &lpm->rules[depth];
+ struct rte_lpm6_rule *r, *n;
+
+ RB_FOREACH_SAFE(r, rte_lpm6_rules_tree, head, n) {
+ rule_delete(lpm, r, depth);
+ }
+ }
/* Zero tbl24. */
memset(lpm->tbl24, 0, sizeof(lpm->tbl24));
@@ -877,7 +1165,25 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm)
/* Zero tbl8. */
memset(lpm->tbl8, 0, sizeof(lpm->tbl8[0]) *
RTE_LPM6_TBL8_GROUP_NUM_ENTRIES * lpm->number_tbl8s);
+}
- /* Delete all rules form the rules table. */
- memset(lpm->rules_tbl, 0, sizeof(struct rte_lpm6_rule) * lpm->max_rules);
+/* Count usage of tbl8 */
+unsigned
+rte_lpm6_tbl8_count(const struct rte_lpm6 *lpm)
+{
+ unsigned i, count = 0;
+
+ for (i = 0; i < lpm->number_tbl8s; i++) {
+ const struct rte_lpm6_tbl_entry *tbl8_entry
+ = lpm->tbl8 + i * RTE_LPM6_TBL8_GROUP_NUM_ENTRIES;
+ if (tbl8_entry->valid_group)
+ ++count;
+ }
+ return count;
+}
+
+unsigned
+rte_lpm6_tbl8_free_count(const struct rte_lpm6 *lpm)
+{
+ return lpm->number_tbl8s - rte_lpm6_tbl8_count(lpm);
}
diff --git a/lib/librte_lpm/rte_lpm6.h b/lib/librte_lpm/rte_lpm6.h
index 13d027f..cda3b83 100644
--- a/lib/librte_lpm/rte_lpm6.h
+++ b/lib/librte_lpm/rte_lpm6.h
@@ -55,7 +55,7 @@ struct rte_lpm6;
/** LPM configuration structure. */
struct rte_lpm6_config {
- uint32_t max_rules; /**< Max number of rules. */
+ uint32_t max_rules; /**< This field is currently unused. */
uint32_t number_tbl8s; /**< Number of tbl8s to allocate. */
int flags; /**< This field is currently unused. */
};
@@ -123,8 +123,13 @@ rte_lpm6_free(struct rte_lpm6 *lpm);
*/
int
rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop);
+int
+rte_lpm6_add_v1604(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
uint8_t next_hop);
-
+int
+rte_lpm6_add_v1611(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+ uint16_t next_hop);
/**
* Check if a rule is present in the LPM table,
* and provide its next hop if it is.
@@ -142,7 +147,13 @@ rte_lpm6_add(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
*/
int
rte_lpm6_is_rule_present(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint16_t *next_hop);
+int
+rte_lpm6_is_rule_present_v1604(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
uint8_t *next_hop);
+int
+rte_lpm6_is_rule_present_v1611(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth,
+uint16_t *next_hop);
/**
* Delete a rule from the LPM table.
@@ -199,7 +210,11 @@ rte_lpm6_delete_all(struct rte_lpm6 *lpm);
* -EINVAL for incorrect arguments, -ENOENT on lookup miss, 0 on lookup hit
*/
int
-rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
+rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint16_t *next_hop);
+int
+rte_lpm6_lookup_v1604(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
+int
+rte_lpm6_lookup_v1611(const struct rte_lpm6 *lpm, uint8_t *ip, uint16_t *next_hop);
/**
* Lookup multiple IP addresses in an LPM table.
@@ -220,7 +235,34 @@ rte_lpm6_lookup(const struct rte_lpm6 *lpm, uint8_t *ip, uint8_t *next_hop);
int
rte_lpm6_lookup_bulk_func(const struct rte_lpm6 *lpm,
uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
- int16_t * next_hops, unsigned n);
+ int32_t *next_hops, unsigned n);
+int
+rte_lpm6_lookup_bulk_func_v1604(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int16_t *next_hops, unsigned n);
+int
+rte_lpm6_lookup_bulk_func_v1611(const struct rte_lpm6 *lpm,
+ uint8_t ips[][RTE_LPM6_IPV6_ADDR_SIZE],
+ int32_t *next_hops, unsigned n);
+
+/**
+ * Return the number of entries in the Tbl8 array
+ *
+ * @param lpm
+ * LPM object handle
+ */
+unsigned
+rte_lpm6_tbl8_count(const struct rte_lpm6 *lpm);
+
+
+/**
+ * Return the number of free entries in the Tbl8 array
+ *
+ * @param lpm
+ * LPM object handle
+ */
+unsigned
+rte_lpm6_tbl8_free_count(const struct rte_lpm6 *lpm);
#ifdef __cplusplus
}
diff --git a/lib/librte_lpm/rte_lpm_version.map b/lib/librte_lpm/rte_lpm_version.map
index 239b371..bdf3d8d 100644
--- a/lib/librte_lpm/rte_lpm_version.map
+++ b/lib/librte_lpm/rte_lpm_version.map
@@ -34,3 +34,15 @@ DPDK_16.04 {
rte_lpm_delete_all;
} DPDK_2.0;
+
+DPDK_16.11 {
+ global:
+
+ rte_lpm6_add;
+ rte_lpm6_is_rule_present;
+ rte_lpm6_lookup;
+ rte_lpm6_lookup_bulk_func;
+ rte_lpm6_tbl8_count;
+ rte_lpm6_tbl8_free_count;
+
+} DPDK_16.04;
--
2.9.2
^ permalink raw reply [flat|nested] 14+ messages in thread* [dpdk-dev] [PATCH v2 2/2] test_lpm6: make test_lpm6* compatible with the new rte_lpm6.c lib
2016-06-09 0:53 [dpdk-dev] [PATCH 0/3] lpm6: speed improvement on delete rule Nikita Kozlov
` (4 preceding siblings ...)
2016-08-24 22:59 ` [dpdk-dev] [PATCH v2 1/2] lpm6: speed inmprovement " Nikita Kozlov
@ 2016-08-24 22:59 ` Nikita Kozlov
5 siblings, 0 replies; 14+ messages in thread
From: Nikita Kozlov @ 2016-08-24 22:59 UTC (permalink / raw)
To: dev; +Cc: Nikita Kozlov, Baptiste Daroussin
Modify of test_lpm6.c to reflect that we no longer have a maximum number
of rules.
Check in some places that we are using the same number of tbl8 as the
previous implementation after a rte_lpm6_delete.
Signed-off-by: Nikita Kozlov <nikita@gandi.net>
Signed-off-by: Baptiste Daroussin <bapt@gandi.net>
---
app/test/test_lpm6.c | 244 +++++++++++-----------------------
app/test/test_lpm6_perf.c | 6 +-
lib/librte_table/rte_table_lpm_ipv6.c | 7 +-
3 files changed, 84 insertions(+), 173 deletions(-)
diff --git a/app/test/test_lpm6.c b/app/test/test_lpm6.c
index 0fd0ef7..7929e44 100644
--- a/app/test/test_lpm6.c
+++ b/app/test/test_lpm6.c
@@ -77,8 +77,6 @@ static int32_t test22(void);
static int32_t test23(void);
static int32_t test24(void);
static int32_t test25(void);
-static int32_t test26(void);
-static int32_t test27(void);
rte_lpm6_test tests6[] = {
/* Test Cases */
@@ -108,13 +106,10 @@ rte_lpm6_test tests6[] = {
test23,
test24,
test25,
- test26,
- test27,
};
#define NUM_LPM6_TESTS (sizeof(tests6)/sizeof(tests6[0]))
#define MAX_DEPTH 128
-#define MAX_RULES 1000000
#define NUMBER_TBL8S (1 << 16)
#define MAX_NUM_TBL8S (1 << 21)
#define PASS 0
@@ -153,7 +148,6 @@ test0(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -161,14 +155,7 @@ test0(void)
lpm = rte_lpm6_create(NULL, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm == NULL);
- /* rte_lpm6_create: max_rules = 0 */
- /* Note: __func__ inserts the function name, in this case "test0". */
- config.max_rules = 0;
- lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
- TEST_LPM_ASSERT(lpm == NULL);
-
/* socket_id < -1 is invalid */
- config.max_rules = MAX_RULES;
lpm = rte_lpm6_create(__func__, -2, &config);
TEST_LPM_ASSERT(lpm == NULL);
@@ -195,7 +182,6 @@ test1(void)
struct rte_lpm6 *lpm1 = NULL, *lpm2 = NULL, *lpm3 = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -219,7 +205,6 @@ test1(void)
/*
* Create lpm table then delete lpm table 20 times
- * Use a slightly different rules size each time
*/
int32_t
test2(void)
@@ -233,7 +218,6 @@ test2(void)
/* rte_lpm6_free: Free NULL */
for (i = 0; i < 20; i++) {
- config.max_rules = MAX_RULES - i;
lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm != NULL);
@@ -256,7 +240,6 @@ test3(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -278,10 +261,10 @@ test4(void)
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 24, next_hop = 100;
+ uint8_t depth = 24;
+ uint16_t next_hop = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -319,7 +302,6 @@ test5(void)
uint8_t depth = 24;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -354,10 +336,9 @@ test6(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t next_hop_return = 0;
+ uint16_t next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -392,10 +373,9 @@ test7(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[10][16];
- int16_t next_hop_return[10];
+ int32_t next_hop_return[10];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -433,7 +413,6 @@ test8(void)
uint8_t depth[10];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -469,11 +448,11 @@ test9(void)
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 16, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 16;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
uint8_t i;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -503,56 +482,13 @@ test9(void)
return PASS;
}
-/*
- * Adds max_rules + 1 and expects a failure. Deletes a rule, then adds
- * another one and expects success.
- */
-int32_t
-test10(void)
-{
- struct rte_lpm6 *lpm = NULL;
- struct rte_lpm6_config config;
- uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth, next_hop_add = 100;
- int32_t status = 0;
- int i;
-
- config.max_rules = 127;
- config.number_tbl8s = NUMBER_TBL8S;
- config.flags = 0;
-
- lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
- TEST_LPM_ASSERT(lpm != NULL);
-
- for (i = 1; i < 128; i++) {
- depth = (uint8_t)i;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == 0);
- }
-
- depth = 128;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == -ENOSPC);
-
- depth = 127;
- status = rte_lpm6_delete(lpm, ip, depth);
- TEST_LPM_ASSERT(status == 0);
-
- depth = 128;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == 0);
-
- rte_lpm6_free(lpm);
-
- return PASS;
-}
/*
* Creates an LPM table with a small number of tbl8s and exhaust them in the
* middle of the process of creating a rule.
*/
int32_t
-test11(void)
+test10(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
@@ -560,43 +496,69 @@ test11(void)
uint8_t depth, next_hop_add = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 16;
config.flags = 0;
lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
TEST_LPM_ASSERT(lpm != NULL);
+ /* use 13 tlb8 */
depth = 128;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ /* use 14 tbl8 */
ip[0] = 1;
depth = 25;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 14);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ /* use 15 tbl8 */
depth = 33;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 15);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ /* use 16 tbl8 */
depth = 41;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 16);
+
status = rte_lpm6_delete(lpm, ip, depth);
TEST_LPM_ASSERT(status == 0);
+ status = rte_lpm6_tbl8_count(lpm);
+ TEST_LPM_ASSERT(status == 13);
+
+ /* try to use 17 tbl8 */
depth = 49;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == -ENOSPC);
+ /* use 16 tbl8 */
depth = 41;
status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
TEST_LPM_ASSERT(status == 0);
@@ -612,7 +574,7 @@ test11(void)
* in that position and needs to be extended.
*/
int32_t
-test12(void)
+test11(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
@@ -620,7 +582,6 @@ test12(void)
uint8_t depth, next_hop_add = 100;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 16;
config.flags = 0;
@@ -646,58 +607,13 @@ test12(void)
}
/*
- * Creates an LPM table with max_rules = 2 and tries to add 3 rules.
- * Delete one of the rules and tries to add the third one again.
- */
-int32_t
-test13(void)
-{
- struct rte_lpm6 *lpm = NULL;
- struct rte_lpm6_config config;
- uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth, next_hop_add = 100;
- int32_t status = 0;
-
- config.max_rules = 2;
- config.number_tbl8s = NUMBER_TBL8S;
- config.flags = 0;
-
- lpm = rte_lpm6_create(__func__, SOCKET_ID_ANY, &config);
- TEST_LPM_ASSERT(lpm != NULL);
-
- depth = 1;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == 0);
-
- depth = 2;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == 0);
-
- depth = 3;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == -ENOSPC);
-
- depth = 2;
- status = rte_lpm6_delete(lpm, ip, depth);
- TEST_LPM_ASSERT(status == 0);
-
- depth = 3;
- status = rte_lpm6_add(lpm, ip, depth, next_hop_add);
- TEST_LPM_ASSERT(status == 0);
-
- rte_lpm6_free(lpm);
-
- return PASS;
-}
-
-/*
* Add 2^12 routes with different first 12 bits and depth 25.
* Add one more route with the same depth and check that results in a failure.
* After that delete the last rule and create the one that was attempted to be
* created. This checks tbl8 exhaustion.
*/
int32_t
-test14(void)
+test12(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
@@ -706,7 +622,6 @@ test14(void)
int32_t status = 0;
int i;
- config.max_rules = MAX_RULES;
config.number_tbl8s = 256;
config.flags = 0;
@@ -743,15 +658,15 @@ test14(void)
* Call add, lookup and delete for a single rule with depth = 24
*/
int32_t
-test15(void)
+test13(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 24, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 24;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -779,15 +694,15 @@ test15(void)
* Call add, lookup and delete for a single rule with depth > 24
*/
int32_t
-test16(void)
+test14(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {12,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth = 128, next_hop_add = 100, next_hop_return = 0;
+ uint8_t depth = 128;
+ uint16_t next_hop_add = 100, next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -821,17 +736,17 @@ test16(void)
* previous depth value (i.e. depth -1).
*/
int32_t
-test17(void)
+test15(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip1[] = {127,255,255,255,255,255,255,255,255,
255,255,255,255,255,255,255};
uint8_t ip2[] = {128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -888,16 +803,16 @@ test17(void)
* - Add & lookup to hit valid extended TBL24 entry with valid TBL8 entry
*/
int32_t
-test18(void)
+test16(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16], ip_1[16], ip_2[16];
- uint8_t depth, depth_1, depth_2, next_hop_add, next_hop_add_1,
+ uint8_t depth, depth_1, depth_2;
+ uint16_t next_hop_add, next_hop_add_1,
next_hop_add_2, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1050,15 +965,15 @@ test18(void)
* - Delete a rule that is not present in the TBL8 & lookup
*/
int32_t
-test19(void)
+test17(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1248,15 +1163,15 @@ test19(void)
* add a more specific rule than the existing rule, lookup again
*/
int32_t
-test20(void)
+test18(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1315,16 +1230,16 @@ test20(void)
* and checks that the result is as expected.
*/
int32_t
-test21(void)
+test19(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip_batch[4][16];
- uint8_t depth, next_hop_add;
- int16_t next_hop_return[4];
+ uint8_t depth;
+ uint16_t next_hop_add;
+ int32_t next_hop_return[4];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1373,16 +1288,15 @@ test21(void)
* Use the delete_bulk function to delete the remaining one. Lookup again.
*/
int32_t
-test22(void)
+test20(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip_batch[5][16];
uint8_t depth[5], next_hop_add;
- int16_t next_hop_return[5];
+ int32_t next_hop_return[5];
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1489,16 +1403,16 @@ test22(void)
* and contraction.
*/
int32_t
-test23(void)
+test21(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint32_t i;
uint8_t ip[16];
- uint8_t depth, next_hop_add, next_hop_return;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1537,12 +1451,11 @@ test23(void)
* - find non-existing table: miss
*/
int32_t
-test24(void)
+test22(void)
{
struct rte_lpm6 *lpm = NULL, *result = NULL;
struct rte_lpm6_config config;
- config.max_rules = 256 * 32;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1573,16 +1486,16 @@ test24(void)
* precalculated by using a python script and stored in a .h file.
*/
int32_t
-test25(void)
+test23(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[16];
uint32_t i;
- uint8_t depth, next_hop_add, next_hop_return, next_hop_expected;
+ uint8_t depth;
+ uint16_t next_hop_add, next_hop_return, next_hop_expected;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1619,7 +1532,7 @@ test25(void)
* - lookup /32 and /24 rule to ensure the table has not been overwritten.
*/
int32_t
-test26(void)
+test24(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
@@ -1629,13 +1542,12 @@ test26(void)
uint8_t d_ip_10_32 = 32;
uint8_t d_ip_10_24 = 24;
uint8_t d_ip_20_25 = 25;
- uint8_t next_hop_ip_10_32 = 100;
- uint8_t next_hop_ip_10_24 = 105;
- uint8_t next_hop_ip_20_25 = 111;
- uint8_t next_hop_return = 0;
+ uint16_t next_hop_ip_10_32 = 100;
+ uint16_t next_hop_ip_10_24 = 105;
+ uint16_t next_hop_ip_20_25 = 111;
+ uint16_t next_hop_return = 0;
int32_t status = 0;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -1647,7 +1559,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_10_32, &next_hop_return);
- uint8_t test_hop_10_32 = next_hop_return;
+ uint16_t test_hop_10_32 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_32);
@@ -1656,7 +1568,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_10_24, &next_hop_return);
- uint8_t test_hop_10_24 = next_hop_return;
+ uint16_t test_hop_10_24 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_10_24);
@@ -1665,7 +1577,7 @@ test26(void)
return -1;
status = rte_lpm6_lookup(lpm, ip_20_25, &next_hop_return);
- uint8_t test_hop_20_25 = next_hop_return;
+ uint16_t test_hop_20_25 = next_hop_return;
TEST_LPM_ASSERT(status == 0);
TEST_LPM_ASSERT(next_hop_return == next_hop_ip_20_25);
@@ -1699,16 +1611,16 @@ test26(void)
* This tests tbl expansion.
*/
int32_t
-test27(void)
+test25(void)
{
struct rte_lpm6 *lpm = NULL;
struct rte_lpm6_config config;
uint8_t ip[] = {128,128,128,128,128,128,128,128,128,128,128,128,128,128,0,0};
- uint8_t depth = 128, next_hop_add = 100, next_hop_return;
+ uint8_t depth = 128;
+ uint16_t next_hop_add = 100, next_hop_return;
int32_t status = 0;
int i, j;
- config.max_rules = MAX_RULES;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
diff --git a/app/test/test_lpm6_perf.c b/app/test/test_lpm6_perf.c
index be47d4a..169318c 100644
--- a/app/test/test_lpm6_perf.c
+++ b/app/test/test_lpm6_perf.c
@@ -86,11 +86,10 @@ test_lpm6_perf(void)
struct rte_lpm6_config config;
uint64_t begin, total_time;
unsigned i, j;
- uint8_t next_hop_add = 0xAA, next_hop_return = 0;
+ uint16_t next_hop_add = 0xAA, next_hop_return = 0;
int status = 0;
int64_t count = 0;
- config.max_rules = 1000000;
config.number_tbl8s = NUMBER_TBL8S;
config.flags = 0;
@@ -143,7 +142,7 @@ test_lpm6_perf(void)
count = 0;
uint8_t ip_batch[NUM_IPS_ENTRIES][16];
- int16_t next_hops[NUM_IPS_ENTRIES];
+ int32_t next_hops[NUM_IPS_ENTRIES];
for (i = 0; i < NUM_IPS_ENTRIES; i++)
memcpy(ip_batch[i], large_ips_table[i].ip, 16);
@@ -185,3 +184,4 @@ test_lpm6_perf(void)
}
REGISTER_TEST_COMMAND(lpm6_perf_autotest, test_lpm6_perf);
+
diff --git a/lib/librte_table/rte_table_lpm_ipv6.c b/lib/librte_table/rte_table_lpm_ipv6.c
index 836f4cf..abd5b28 100644
--- a/lib/librte_table/rte_table_lpm_ipv6.c
+++ b/lib/librte_table/rte_table_lpm_ipv6.c
@@ -129,7 +129,6 @@ rte_table_lpm_ipv6_create(void *params, int socket_id, uint32_t entry_size)
}
/* LPM low-level table creation */
- lpm6_config.max_rules = p->n_rules;
lpm6_config.number_tbl8s = p->number_tbl8s;
lpm6_config.flags = 0;
lpm->lpm = rte_lpm6_create(p->name, socket_id, &lpm6_config);
@@ -213,7 +212,7 @@ rte_table_lpm_ipv6_entry_add(
(struct rte_table_lpm_ipv6_key *) key;
uint32_t nht_pos, nht_pos0_valid;
int status;
- uint8_t nht_pos0;
+ uint16_t nht_pos0;
/* Check input parameters */
if (lpm == NULL) {
@@ -280,7 +279,7 @@ rte_table_lpm_ipv6_entry_delete(
struct rte_table_lpm_ipv6 *lpm = (struct rte_table_lpm_ipv6 *) table;
struct rte_table_lpm_ipv6_key *ip_prefix =
(struct rte_table_lpm_ipv6_key *) key;
- uint8_t nht_pos;
+ uint16_t nht_pos;
int status;
/* Check input parameters */
@@ -356,7 +355,7 @@ rte_table_lpm_ipv6_lookup(
uint8_t *ip = RTE_MBUF_METADATA_UINT8_PTR(pkt,
lpm->offset);
int status;
- uint8_t nht_pos;
+ uint16_t nht_pos;
status = rte_lpm6_lookup(lpm->lpm, ip, &nht_pos);
if (status == 0) {
--
2.9.2
^ permalink raw reply [flat|nested] 14+ messages in thread