[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(-)
> 
The lpm6_autotest is now giving me an error when I run it, which wasn't
there before, though interestingly the test is still passing overall, which
seems wrong:

RTE>>lpm6_autotest
# test 00
# test 01
LPM: LPM rules mempool allocation failed: Unknown error 17 (17)# test 02
# test 03
...

On the other hand, the performance numbers, especially for delete, look far
better:

Before:
	Average LPM Add: 531220 cycles
	Average LPM Lookup: 41.7 cycles (fails = 0.0%)
	BULK LPM Lookup: 33.8 cycles (fails = 0.0%)
	Average LPM Delete: 1.41825e+08 cycles

After:
	Average LPM Add: 487116 cycles
	Average LPM Lookup: 41.7 cycles (fails = 0.0%)
	BULK LPM Lookup: 33.3 cycles (fails = 0.0%)
	Average LPM Delete: 3.65125e+06 cycles

/Bruce