Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions
On Mon, 16 Jul 2018 20:34:45 +0300 Alex Kiselev wrote: > > On Wed, 11 Jul 2018 20:53:46 +0300 > > Alex Kiselev 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. > 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. > I solved this problem several years ago by using the standard BSD red-black tree. This was used by Vyatta/Brocade/ATT and submitted to DPDK but never merged. The BSD red-black tree is in the libbsd-dev package in Linux. The issue which seemed to block merging was the dependency on additional packages. Since DPDK already depends on libnuma not sure why that was an issue.
Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions
> On Wed, 11 Jul 2018 20:53:46 +0300 > Alex Kiselev 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. 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. -- Alex
Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions
> Also. Please run checkpatch shell script on your patches. For example, there > should be blank line between declarations and code. fixed in v5 -- Alex
Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions
> On Wed, 11 Jul 2018 20:53:46 +0300
> Alex Kiselev wrote:
>> librte_lpm: Improve lpm6 performance
...
>>
>> /* 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?
compared to the current rules array it's about 2 times since a prefix is stored
in
a rule (mempool) and in a rule key (hashtable).
I am only talking here about the rule storage.
And I've just realised it doesn't have to be this
way, I don't need the rules mempool anymore. I only need the rules hashtable,
since
it could contains everything a rule needs. A rule prefix is stored in a hash
key,
and a next hop index could be stored in a hash value. That would eliminate
memory overhead.
I'll try this way in next patch series.
> 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.
Maybe. But there is no tree library in the DPDK. So I choose
a fast and simple way to implement
rules storage using the existent hashtable lib.
And it gives good perfomance results.
Anyway, it's not a data plane, add/delete operations are
executed not very often, so it's not critical to find
the most efficient (in terms of memory consumption) way, a good one is ok.
> 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.
I have. It didn't give me any warnings.
--
Alex
Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions
On Wed, 11 Jul 2018 20:53:46 +0300
Alex Kiselev 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
> ---
> 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
> #include
> #include
> +#include
> +#include
> +#include
> +#include
>
> #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.
