[dpdk-dev] [PATCH v2] librte_lpm: Improve performance of the delete and add functions

[Bruce Richardson]

On Mon, Jul 02, 2018 at 07:42:11PM +0300, Alex Kiselev wrote:
> There are two major problems with the library:
> first, there is no need to rebuild the whole LPM tree
> when a rule is deleted and second, due to the current
> rules algorithm with complexity O(n) it's almost
> impossible to deal with large rule sets (50k or so rules).
> This patch addresses those two issues.
> 
> Signed-off-by: Alex Kiselev <alex at therouter.net>
> ---
>  lib/librte_lpm/rte_lpm6.c | 1073 ++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 816 insertions(+), 257 deletions(-)
> 
> diff --git a/lib/librte_lpm/rte_lpm6.c b/lib/librte_lpm/rte_lpm6.c
> index 149677eb1..438db0831 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_hash_crc.h>
> +#include <rte_mempool.h>
> +#include <assert.h>

For correct compilation, you now need to specify the dependency on the hash
and mempool libraries in both make and meson build files. I believe
something like this should do the trick:

--- 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

--- 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']