mbox series

[v6,00/12] lib: add RIB and FIB liraries

Message ID cover.1572621162.git.vladimir.medvedkin@intel.com (mailing list archive)
Headers show
Series lib: add RIB and FIB liraries | expand

Message

Medvedkin, Vladimir 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

Thomas Monjalon Nov. 5, 2019, 11:14 p.m. UTC | #1
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
David Marchand Nov. 6, 2019, 5:50 a.m. UTC | #2
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
Thomas Monjalon Nov. 6, 2019, 7:50 a.m. UTC | #3
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?
Medvedkin, Vladimir Nov. 6, 2019, 11:50 a.m. UTC | #4
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.
Medvedkin, Vladimir Nov. 6, 2019, 11:53 a.m. UTC | #5
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.
Thomas Monjalon Nov. 6, 2019, 11:59 a.m. UTC | #6
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.
Aaron Conole Nov. 6, 2019, 2:37 p.m. UTC | #7
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.