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