DPDK patches and discussions
 help / color / Atom feed
From: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
To: dev@dpdk.org
Cc: bruce.richardson@intel.com
Subject: [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries
Date: Wed, 11 Sep 2019 18:09:40 +0100
Message-ID: <cover.1568221361.git.vladimir.medvedkin@intel.com> (raw)
In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com>

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)


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          |  36 ++
 app/test/meson.build               |  14 +
 app/test/test_fib.c                | 397 +++++++++++++++++++
 app/test/test_fib6.c               | 405 ++++++++++++++++++++
 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, 6614 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

-- 
2.7.4


  parent reply index

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-26 22:03 [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 1/4] Add RIB library Medvedkin Vladimir
2018-04-26 22:17   ` Stephen Hemminger
2018-04-26 22:18   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:20   ` Stephen Hemminger
2018-04-27  6:45     ` Vladimir Medvedkin
2018-06-29 13:54   ` Bruce Richardson
2018-06-29 14:02   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 2/4] Add dir24_8 implementation for rib library Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 3/4] Add autotests for RIB library Medvedkin Vladimir
2018-06-29 14:13   ` Bruce Richardson
2018-06-29 15:07   ` Bruce Richardson
2018-06-29 15:31   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 4/4] Add support for lpm and rib bulk lookup Medvedkin Vladimir
2018-04-26 22:24 ` [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library Stephen Hemminger
2018-04-26 22:27   ` Thomas Monjalon
2018-04-26 22:42     ` Stephen Hemminger
2018-04-26 22:49     ` Stephen Hemminger
2018-04-27  8:27   ` Vladimir Medvedkin
2018-06-29 15:48 ` Bruce Richardson
2019-09-11 17:09 ` Vladimir Medvedkin [this message]
2019-09-12  7:37   ` [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries Morten Brørup
2019-09-12  9:47     ` Medvedkin, Vladimir
2019-09-12 12:00       ` Morten Brørup
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 " Vladimir Medvedkin
2019-11-05 23:14     ` Thomas Monjalon
2019-11-06  5:50       ` David Marchand
2019-11-06  7:50         ` Thomas Monjalon
2019-11-06 11:53           ` Medvedkin, Vladimir
2019-11-06 11:59             ` Thomas Monjalon
2019-11-06 14:37               ` Aaron Conole
2019-11-06 11:50         ` Medvedkin, Vladimir
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 01/12] rib: add RIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 05/12] fib: add FIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 07/12] fib: add DIR24-8 dataplane algorithm Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 01/12] rib: add RIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 05/12] fib: add FIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 07/12] fib: add DIR24-8 dataplane algorithm Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-09-12 14:07   ` Aaron Conole
2019-10-01 17:12     ` Medvedkin, Vladimir
2019-10-24 15:55       ` Thomas Monjalon
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=cover.1568221361.git.vladimir.medvedkin@intel.com \
    --to=vladimir.medvedkin@intel.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

DPDK patches and discussions

Archives are clonable:
	git clone --mirror http://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ http://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev


Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/ public-inbox