From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg1-f193.google.com (mail-pg1-f193.google.com [209.85.215.193]) by dpdk.org (Postfix) with ESMTP id 2CF581B49D for ; Wed, 11 Jul 2018 22:30:29 +0200 (CEST) Received: by mail-pg1-f193.google.com with SMTP id n9-v6so2920885pgp.12 for ; Wed, 11 Jul 2018 13:30:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=networkplumber-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=ZzvFQY9Vc5SO4kC3m0UkLZdjGquJskrEec2pvAhHJRc=; b=lHVTwifOCta+uRbVHFvyWLpNm32d9a2dKswXx0+HgAtYVLSaKsaBHE1hm+/5WEGpZv wLISg0QqWZvD/nIrLd4646j9akU5K856TZnzqBP1/78FFp07FOsmfK2+9j6drahZfhd1 EORUrcdnlWNECZWTAr5pdLzi3w0QHUoOJU3LFlRb4ZWvk0aWltNCcjQ14WRM+C72pV9D RjHNaTNpWWp0PH7kwwYRQGy2o1tuw7saUroDRJZnXVs8dYTrG6hXyNBJQ8U2e3WZGX59 TASBYW4bVDbnAUn8QAonLHZPdNiLCjEEsKOBDm2E+YLfn/1r81sQzkjkapiTR3S8eKvm Dv0Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ZzvFQY9Vc5SO4kC3m0UkLZdjGquJskrEec2pvAhHJRc=; b=jfiXp/8YaJWFh8EKOk1w7EiyY7jIC5ErLXR0JEKkLaCPkAnBSXGzRxRNn61O+UT5YX kC86IlXjaO6VT6kA0NQXiyNPlDXsWhTbG0TyoAmMhcCKYKcpVoeKla58x5LAUgXJHDtf kUOJugi8iOrDQNUdEVoQjxKn4JnIvs1DUFcu17VmssJd2zvwNfqdxTLnY4Q+4Ff4MtXo 5dUS9A3VS6nvhr95EgndXIVbcMGe9B3zO5kH7uc0jm036XrGVjPP1rZkpFEzjXtHUzkB eRYwXnsnrIlMTOAJE6009r4BNbymiXwS/pK4ZXfwH72c3WYAE+k0NM+3znQe0XO0akcA TJIQ== X-Gm-Message-State: AOUpUlEWaAqi/ZGsiKIy/u+meoIslFB6adtQLgePnBz8me/S0WrKERkY 4Y1XOHQNAMrztm8oyc5QPp7P/w== X-Google-Smtp-Source: AAOMgpfKuct7Z+HVpAiB86DWTr+POIVODUNqS/kdxchFxg1TJa67M+P9y2PwRtgMsBSm5rezKaUabg== X-Received: by 2002:a63:6383:: with SMTP id x125-v6mr111069pgb.127.1531341028121; Wed, 11 Jul 2018 13:30:28 -0700 (PDT) Received: from xeon-e3 (204-195-22-127.wavecable.com. [204.195.22.127]) by smtp.gmail.com with ESMTPSA id c12-v6sm19580921pfl.20.2018.07.11.13.30.27 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 11 Jul 2018 13:30:28 -0700 (PDT) Date: Wed, 11 Jul 2018 13:30:25 -0700 From: Stephen Hemminger To: Alex Kiselev Cc: "dev@dpdk.org" , Bruce Richardson Message-ID: <20180711133025.256a8ae1@xeon-e3> In-Reply-To: <20180711175356.035761B462@dpdk.org> References: <20180711175356.035761B462@dpdk.org> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Subject: Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 11 Jul 2018 20:30:29 -0000 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.