librte_lpm: Improve performance of the delete and add functions

librte_lpm: Improve lpm6 performance

Rework the lpm6 rule subsystem and replace current rules algorithm complexity O(n) with hashtables which allow dealing with large (50k) rule sets.

Signed-off-by Alex Kiselev <[email protected]>

---
 lib/Makefile               |   2 +-
 lib/librte_lpm/meson.build |   1 +
 lib/librte_lpm/rte_lpm6.c  | 406 ++++++++++++++++++++++++++++-----------------
 3 files changed, 255 insertions(+), 154 deletions(-)

lib/Makefile +1 -1

index d82462ba2..79aeaa04f 100644
@@ -47,7 +47,7 @@ DEPDIRS-librte_hash := librte_eal librte_ring
 DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
-DEPDIRS-librte_lpm := librte_eal
+DEPDIRS-librte_lpm := librte_eal librte_mempool librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
 DEPDIRS-librte_acl := librte_eal
 DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member

lib/librte_lpm/meson.build +1 -0

index 067849427..fcb5bed2c 100644
@@ -7,3 +7,4 @@ headers = files('rte_lpm.h', 'rte_lpm6.h')
 # since header files have different names, we can install all vector headers
 # without worrying about which architecture we actually need
 headers += files('rte_lpm_altivec.h', 'rte_lpm_neon.h', 'rte_lpm_sse.h')
+deps += ['mempool', 'hash']

lib/librte_lpm/rte_lpm6.c +14 -1

index 149677eb1..d40eeb043 100644
@@ -21,6 +21,10 @@
 #include <rte_errno.h>
 #include <rte_rwlock.h>
 #include <rte_spinlock.h>
+#include <rte_hash.h>
+#include <rte_mempool.h>
+#include <assert.h>
+#include <rte_jhash.h>
 
 #include "rte_lpm6.h"
 

@@ -37,6 +41,8 @@
 #define BYTE_SIZE                                 8
 #define BYTES2_SIZE                              16
 
+#define RULE_HASH_TABLE_EXTRA_SPACE              64
+
 #define lpm6_tbl8_gindex next_hop
 
 /** Flags for setting an entry as valid/invalid. */

@@ -70,6 +76,12 @@ struct rte_lpm6_rule {
 	uint8_t depth; /**< Rule depth. */
 };
 
+/** Rules tbl entry key. */
+struct rte_lpm6_rule_key {
+	uint8_t ip[RTE_LPM6_IPV6_ADDR_SIZE]; /**< Rule IP address. */
+	uint8_t depth; /**< Rule depth. */
+};
+
 /** LPM6 structure. */
 struct rte_lpm6 {
 	/* LPM metadata. */

@@ -80,7 +92,8 @@ struct rte_lpm6 {
 	uint32_t next_tbl8;              /**< Next tbl8 to be used. */
 
 	/* LPM Tables. */
-	struct rte_lpm6_rule *rules_tbl; /**< LPM rules. */
+	struct rte_mempool *rules_pool; /**< LPM rules mempool. */
+	struct rte_hash *rules_tbl; /**< LPM rules. */
 	struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
 			__rte_cache_aligned; /**< LPM tbl24 table. */
 	struct rte_lpm6_tbl_entry tbl8[0]

Quoted 1 line · On Wed, 11 Jul 2018 20:53:46 +0300 Alex Kiselev <[email protected]> wrote:

librte_lpm: Improve lpm6 performance

lib/librte_lpm/rte_lpm6.c struct rte_lpm6 { · line 106

Quoted 10 lines

 
      /* LPM Tables. */

lib/librte_lpm/rte_lpm6.c +2 -1

-     struct rte_lpm6_rule *rules_tbl; /**< LPM rules. */
+     struct rte_mempool *rules_pool; /**< LPM rules mempool. */
+     struct rte_hash *rules_tbl; /**< LPM rules. */
      struct rte_lpm6_tbl_entry tbl24[RTE_LPM6_TBL24_NUM_ENTRIES]
                      __rte_cache_aligned; /**< LPM tbl24 table. */
      struct rte_lpm6_tbl_entry tbl8[0]

@@ -93,22 +106,81 @@ struct rte_lpm6 {
  * and set the rest to 0.

What is the increased memory overhead of having a hash table?

Wouldn't it make more sense to use something like tree, and use left/right in the rules entry. That way the memory is spread and scales with the number of rules.

Remember on a internet router, it is not unusual to 2M or more rules.

Also. Please run checkpatch shell script on your patches. For example, there should be blank line between declarations and code.

Also. Please run checkpatch shell script on your patches. For example, there should be blank line between declarations and code.

Quoted 6 lines · On Wed, 11 Jul 2018 20:53:46 +0300 Alex Kiselev <[email protected]> wrote:

librte_lpm: Improve lpm6 performance

Rework the lpm6 rule subsystem and replace current rules algorithm complexity O(n) with hashtables which allow dealing with large (50k) rule sets.

Wouldn't it make more sense to use something like tree, and use left/right in the rules entry. That way the memory is spread and scales with the number of rules.

Quoted 9 lines

Quoted 6 lines · On Wed, 11 Jul 2018 20:53:46 +0300 Alex Kiselev <[email protected]> wrote:

librte_lpm: Improve lpm6 performance

Rework the lpm6 rule subsystem and replace current rules algorithm complexity O(n) with hashtables which allow dealing with large (50k) rule sets.

Quoted 3 lines

Wouldn't it make more sense to use something like tree, and use left/right in the rules entry. That way the memory is spread and scales with the number of rules.

I guess you are trying to propose using a radix tree. I agree, it uses memory more efficient than hashtable. But, it would require to add a new dpdk library implementing a radix tree, then we can talk about using it as a lpm rule storage.