Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions

[Stephen Hemminger <stephen@networkplumber.org>]

On Wed, 11 Jul 2018 20:53:46 +0300
Alex Kiselev <alex@therouter.net> 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.
> 
> Signed-off-by: Alex Kiselev <alex@therouter.net>
> ---
>  lib/Makefile               |   2 +-
>  lib/librte_lpm/meson.build |   1 +
>  lib/librte_lpm/rte_lpm6.c  | 406 ++++++++++++++++++++++++++++-----------------
>  3 files changed, 255 insertions(+), 154 deletions(-)
> 
> diff --git a/lib/Makefile b/lib/Makefile
> index d82462ba2..79aeaa04f 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -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
> diff --git a/lib/librte_lpm/meson.build b/lib/librte_lpm/meson.build
> index 067849427..fcb5bed2c 100644
> --- a/lib/librte_lpm/meson.build
> +++ b/lib/librte_lpm/meson.build
> @@ -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']
> diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
> index 149677eb1..d40eeb043 100644
> --- a/lib/librte_lpm/rte_lpm6.c
> +++ b/lib/librte_lpm/rte_lpm6.c
> @@ -21,6 +21,10 @@
>  #include <rte_errno.h>
>  #include <rte_rwlock.h>
>  #include <rte_spinlock.h>
> +#include <rte_hash.h>
> +#include <rte_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]
> @@ -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.