| Message ID | cover.1572621162.git.vladimir.medvedkin@intel.com (mailing list archive) |
|---|---|
| Headers |
Return-Path: <dev-bounces@dpdk.org> X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id BD61CA00BE; Fri, 1 Nov 2019 16:21:53 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 32F761BED8; Fri, 1 Nov 2019 16:21:53 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 711261BEAA for <dev@dpdk.org>; Fri, 1 Nov 2019 16:21:51 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:21:50 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979057" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:48 -0700 From: Vladimir Medvedkin <vladimir.medvedkin@intel.com> To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:33 +0000 Message-Id: <cover.1572621162.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <cover.1568221361.git.vladimir.medvedkin@intel.com> References: <cover.1568221361.git.vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions <dev.dpdk.org> List-Unsubscribe: <https://mails.dpdk.org/options/dev>, <mailto:dev-request@dpdk.org?subject=unsubscribe> List-Archive: <http://mails.dpdk.org/archives/dev/> List-Post: <mailto:dev@dpdk.org> List-Help: <mailto:dev-request@dpdk.org?subject=help> List-Subscribe: <https://mails.dpdk.org/listinfo/dev>, <mailto:dev-request@dpdk.org?subject=subscribe> Errors-To: dev-bounces@dpdk.org Sender: "dev" <dev-bounces@dpdk.org> |
| Series |
lib: add RIB and FIB liraries
|
|
Message
Vladimir Medvedkin
Nov. 1, 2019, 3:21 p.m. UTC
This is heavily reworked version of previous RIB library series: https://mails.dpdk.org/archives/dev/2018-April/099492.html Current lpm implementation while provides really good lookup performance has number of problems. One of them is very low speed for control plane operations such as add or delete a route. Another disadvantage is fixed number of bits for userdata (24 for v4 and 21 for v6) Also it is hard to introduce changes in existing LPM code or add new algorithms without breaking ABI. This patch series tries to solve this problems by: Introduce two new libraries - RIB and FIB. RIB that is Routing Information Base. It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a given prefix). This structure will be used as a control plane helper structure for FIB implementation. Also it might be used standalone in other different places such as bitmaps for example. Second library is FIB that is Forwarding Information Base. It represents dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks. Initial version provides two implementations for both ipv4 and ipv6: dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc). From our measurements we saw 10x speedup for control plane operations comparing with current LPM library (depending on prefix length distribution) ToDo: - introduce new performance measurement app. - add documentation. - add support into existing examples (l3fwd) v6: Move long-running tests into a pref test section Vladimir Medvedkin (12): rib: add RIB library test/rib: add RIB library autotests rib: add ipv6 support for RIB test/rib: add ipv6 support for RIB autotests fib: add FIB library fib: add FIB ipv6 support fib: add DIR24-8 dataplane algorithm fib: add dataplane algorithm for ipv6 test/fib: add FIB library autotests test/fib: add ipv6 support for FIB autotests test/fib: add FIB library performance autotests test/fib: add FIB library ipv6 performance autotests app/test/Makefile | 7 + app/test/autotest_data.py | 48 +++ app/test/meson.build | 16 + app/test/test_fib.c | 414 ++++++++++++++++++++ app/test/test_fib6.c | 423 +++++++++++++++++++++ app/test/test_fib6_perf.c | 157 ++++++++ app/test/test_fib_perf.c | 411 ++++++++++++++++++++ app/test/test_rib.c | 351 +++++++++++++++++ app/test/test_rib6.c | 357 +++++++++++++++++ config/common_base | 11 + doc/api/doxy-api.conf.in | 2 + lib/Makefile | 4 + lib/librte_fib/Makefile | 25 ++ lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++ lib/librte_fib/dir24_8.h | 36 ++ lib/librte_fib/meson.build | 8 + lib/librte_fib/rte_fib.c | 319 ++++++++++++++++ lib/librte_fib/rte_fib.h | 188 +++++++++ lib/librte_fib/rte_fib6.c | 322 ++++++++++++++++ lib/librte_fib/rte_fib6.h | 193 ++++++++++ lib/librte_fib/rte_fib_version.map | 23 ++ lib/librte_fib/trie.c | 760 +++++++++++++++++++++++++++++++++++++ lib/librte_fib/trie.h | 37 ++ lib/librte_rib/Makefile | 25 ++ lib/librte_rib/meson.build | 8 + lib/librte_rib/rte_rib.c | 532 ++++++++++++++++++++++++++ lib/librte_rib/rte_rib.h | 277 ++++++++++++++ lib/librte_rib/rte_rib6.c | 598 +++++++++++++++++++++++++++++ lib/librte_rib/rte_rib6.h | 334 ++++++++++++++++ lib/librte_rib/rte_rib_version.map | 35 ++ lib/meson.build | 4 +- mk/rte.app.mk | 2 + 32 files changed, 6663 insertions(+), 1 deletion(-) create mode 100644 app/test/test_fib.c create mode 100644 app/test/test_fib6.c create mode 100644 app/test/test_fib6_perf.c create mode 100644 app/test/test_fib_perf.c create mode 100644 app/test/test_rib.c create mode 100644 app/test/test_rib6.c create mode 100644 lib/librte_fib/Makefile create mode 100644 lib/librte_fib/dir24_8.c create mode 100644 lib/librte_fib/dir24_8.h create mode 100644 lib/librte_fib/meson.build create mode 100644 lib/librte_fib/rte_fib.c create mode 100644 lib/librte_fib/rte_fib.h create mode 100644 lib/librte_fib/rte_fib6.c create mode 100644 lib/librte_fib/rte_fib6.h create mode 100644 lib/librte_fib/rte_fib_version.map create mode 100644 lib/librte_fib/trie.c create mode 100644 lib/librte_fib/trie.h create mode 100644 lib/librte_rib/Makefile create mode 100644 lib/librte_rib/meson.build create mode 100644 lib/librte_rib/rte_rib.c create mode 100644 lib/librte_rib/rte_rib.h create mode 100644 lib/librte_rib/rte_rib6.c create mode 100644 lib/librte_rib/rte_rib6.h create mode 100644 lib/librte_rib/rte_rib_version.map
Comments
01/11/2019 16:21, Vladimir Medvedkin: > This is heavily reworked version of previous RIB library series: > https://mails.dpdk.org/archives/dev/2018-April/099492.html > > app/test/Makefile | 7 + > app/test/autotest_data.py | 48 +++ > app/test/meson.build | 16 + > app/test/test_fib.c | 414 ++++++++++++++++++++ > app/test/test_fib6.c | 423 +++++++++++++++++++++ > app/test/test_fib6_perf.c | 157 ++++++++ > app/test/test_fib_perf.c | 411 ++++++++++++++++++++ > app/test/test_rib.c | 351 +++++++++++++++++ > app/test/test_rib6.c | 357 +++++++++++++++++ > config/common_base | 11 + > doc/api/doxy-api.conf.in | 2 + > lib/Makefile | 4 + > lib/librte_fib/Makefile | 25 ++ > lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++ > lib/librte_fib/dir24_8.h | 36 ++ > lib/librte_fib/meson.build | 8 + > lib/librte_fib/rte_fib.c | 319 ++++++++++++++++ > lib/librte_fib/rte_fib.h | 188 +++++++++ > lib/librte_fib/rte_fib6.c | 322 ++++++++++++++++ > lib/librte_fib/rte_fib6.h | 193 ++++++++++ > lib/librte_fib/rte_fib_version.map | 23 ++ > lib/librte_fib/trie.c | 760 +++++++++++++++++++++++++++++++++++++ > lib/librte_fib/trie.h | 37 ++ > lib/librte_rib/Makefile | 25 ++ > lib/librte_rib/meson.build | 8 + > lib/librte_rib/rte_rib.c | 532 ++++++++++++++++++++++++++ > lib/librte_rib/rte_rib.h | 277 ++++++++++++++ > lib/librte_rib/rte_rib6.c | 598 +++++++++++++++++++++++++++++ > lib/librte_rib/rte_rib6.h | 334 ++++++++++++++++ > lib/librte_rib/rte_rib_version.map | 35 ++ > lib/meson.build | 4 +- > mk/rte.app.mk | 2 + > 32 files changed, 6663 insertions(+), 1 deletion(-) You forgot to update MAINTAINERS and the release notes. I did it while merging. Applied, thanks
On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: > > 01/11/2019 16:21, Vladimir Medvedkin: > > This is heavily reworked version of previous RIB library series: > > https://mails.dpdk.org/archives/dev/2018-April/099492.html > > > > app/test/Makefile | 7 + > > app/test/autotest_data.py | 48 +++ > > app/test/meson.build | 16 + > > app/test/test_fib.c | 414 ++++++++++++++++++++ > > app/test/test_fib6.c | 423 +++++++++++++++++++++ > > app/test/test_fib6_perf.c | 157 ++++++++ > > app/test/test_fib_perf.c | 411 ++++++++++++++++++++ > > app/test/test_rib.c | 351 +++++++++++++++++ > > app/test/test_rib6.c | 357 +++++++++++++++++ > > config/common_base | 11 + > > doc/api/doxy-api.conf.in | 2 + > > lib/Makefile | 4 + > > lib/librte_fib/Makefile | 25 ++ > > lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++ > > lib/librte_fib/dir24_8.h | 36 ++ > > lib/librte_fib/meson.build | 8 + > > lib/librte_fib/rte_fib.c | 319 ++++++++++++++++ > > lib/librte_fib/rte_fib.h | 188 +++++++++ > > lib/librte_fib/rte_fib6.c | 322 ++++++++++++++++ > > lib/librte_fib/rte_fib6.h | 193 ++++++++++ > > lib/librte_fib/rte_fib_version.map | 23 ++ > > lib/librte_fib/trie.c | 760 +++++++++++++++++++++++++++++++++++++ > > lib/librte_fib/trie.h | 37 ++ > > lib/librte_rib/Makefile | 25 ++ > > lib/librte_rib/meson.build | 8 + > > lib/librte_rib/rte_rib.c | 532 ++++++++++++++++++++++++++ > > lib/librte_rib/rte_rib.h | 277 ++++++++++++++ > > lib/librte_rib/rte_rib6.c | 598 +++++++++++++++++++++++++++++ > > lib/librte_rib/rte_rib6.h | 334 ++++++++++++++++ > > lib/librte_rib/rte_rib_version.map | 35 ++ > > lib/meson.build | 4 +- > > mk/rte.app.mk | 2 + > > 32 files changed, 6663 insertions(+), 1 deletion(-) > > You forgot to update MAINTAINERS and the release notes. > I did it while merging. > > Applied, thanks The added tests are timeouting: https://travis-ci.com/DPDK/dpdk/jobs/253293904 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s
06/11/2019 06:50, David Marchand: > On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: > > Applied, thanks > > The added tests are timeouting: > https://travis-ci.com/DPDK/dpdk/jobs/253293904 > 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s > 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly?
Hi David, -----Original Message----- From: David Marchand <david.marchand@redhat.com> Sent: Wednesday, November 6, 2019 5:51 AM To: Thomas Monjalon <thomas@monjalon.net>; Medvedkin, Vladimir <vladimir.medvedkin@intel.com> Cc: dev <dev@dpdk.org>; Richardson, Bruce <bruce.richardson@intel.com>; Ananyev, Konstantin <konstantin.ananyev@intel.com>; Aaron Conole <aconole@redhat.com> Subject: Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: > > 01/11/2019 16:21, Vladimir Medvedkin: > > This is heavily reworked version of previous RIB library series: > > https://mails.dpdk.org/archives/dev/2018-April/099492.html > > > > app/test/Makefile | 7 + > > app/test/autotest_data.py | 48 +++ > > app/test/meson.build | 16 + > > app/test/test_fib.c | 414 ++++++++++++++++++++ > > app/test/test_fib6.c | 423 +++++++++++++++++++++ > > app/test/test_fib6_perf.c | 157 ++++++++ > > app/test/test_fib_perf.c | 411 ++++++++++++++++++++ > > app/test/test_rib.c | 351 +++++++++++++++++ > > app/test/test_rib6.c | 357 +++++++++++++++++ > > config/common_base | 11 + > > doc/api/doxy-api.conf.in | 2 + > > lib/Makefile | 4 + > > lib/librte_fib/Makefile | 25 ++ > > lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++ > > lib/librte_fib/dir24_8.h | 36 ++ > > lib/librte_fib/meson.build | 8 + > > lib/librte_fib/rte_fib.c | 319 ++++++++++++++++ > > lib/librte_fib/rte_fib.h | 188 +++++++++ > > lib/librte_fib/rte_fib6.c | 322 ++++++++++++++++ > > lib/librte_fib/rte_fib6.h | 193 ++++++++++ > > lib/librte_fib/rte_fib_version.map | 23 ++ > > lib/librte_fib/trie.c | 760 +++++++++++++++++++++++++++++++++++++ > > lib/librte_fib/trie.h | 37 ++ > > lib/librte_rib/Makefile | 25 ++ > > lib/librte_rib/meson.build | 8 + > > lib/librte_rib/rte_rib.c | 532 ++++++++++++++++++++++++++ > > lib/librte_rib/rte_rib.h | 277 ++++++++++++++ > > lib/librte_rib/rte_rib6.c | 598 +++++++++++++++++++++++++++++ > > lib/librte_rib/rte_rib6.h | 334 ++++++++++++++++ > > lib/librte_rib/rte_rib_version.map | 35 ++ > > lib/meson.build | 4 +- > > mk/rte.app.mk | 2 + > > 32 files changed, 6663 insertions(+), 1 deletion(-) > > You forgot to update MAINTAINERS and the release notes. > I did it while merging. > > Applied, thanks The added tests are timeouting: https://travis-ci.com/DPDK/dpdk/jobs/253293904 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s Oh, ok, I'll send fix today. On my board these tests run in less than 10 seconds, and our CI runs these tests faster, so I split only really slow FIB tests. I'll send fixes asap.
Hi Thomas, -----Original Message----- From: Thomas Monjalon <thomas@monjalon.net> Sent: Wednesday, November 6, 2019 7:51 AM To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com> Cc: David Marchand <david.marchand@redhat.com>; dev <dev@dpdk.org>; Richardson, Bruce <bruce.richardson@intel.com>; Ananyev, Konstantin <konstantin.ananyev@intel.com>; Aaron Conole <aconole@redhat.com> Subject: Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries 06/11/2019 06:50, David Marchand: > On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: > > Applied, thanks > > The added tests are timeouting: > https://travis-ci.com/DPDK/dpdk/jobs/253293904 > 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s > 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly? Yes, I'll send a fix now. In v6 I split only fib_autotests, rib_autotests was not so slow in our CI.
06/11/2019 12:53, Medvedkin, Vladimir: > From: Thomas Monjalon <thomas@monjalon.net> > > 06/11/2019 06:50, David Marchand: > > > On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: > > > > Applied, thanks > > > > > > The added tests are timeouting: > > > https://travis-ci.com/DPDK/dpdk/jobs/253293904 > > > 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s > > > 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s > > > > Vladimir, the slow test were supposed to be moved out of fast tests. > > Please can you fix it quickly? > > Yes, I'll send a fix now. > In v6 I split only fib_autotests, rib_autotests was not so slow in our CI. The goal is to have fast tests that developers can run frequently without being annoyed. I think the whole run should be below a minute. It means a single test case should not exceed one second ideally. Aaron, we should make a status about test duration, agree on a policy and make a plan to apply such policy.
Thomas Monjalon <thomas@monjalon.net> writes: > 06/11/2019 12:53, Medvedkin, Vladimir: >> From: Thomas Monjalon <thomas@monjalon.net> >> > 06/11/2019 06:50, David Marchand: >> > > On Wed, Nov 6, 2019 at 12:14 AM Thomas Monjalon <thomas@monjalon.net> wrote: >> > > > Applied, thanks >> > > >> > > The added tests are timeouting: >> > > https://travis-ci.com/DPDK/dpdk/jobs/253293904 >> > > 47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s >> > > 48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s >> > >> > Vladimir, the slow test were supposed to be moved out of fast tests. >> > Please can you fix it quickly? >> >> Yes, I'll send a fix now. >> In v6 I split only fib_autotests, rib_autotests was not so slow in our CI. > > The goal is to have fast tests that developers can run frequently > without being annoyed. > I think the whole run should be below a minute. > It means a single test case should not exceed one second ideally. > > Aaron, we should make a status about test duration, > agree on a policy and make a plan to apply such policy. Agreed. I'll write something up.