Skip to content

lib: add RIB and FIB liraries

Vladimir Medvedkin dpdk-dev 2 versions – Applied

Status from this message: Applied, thanks

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v6 Latest12 patches 7 repliesApplied
  2. v512 patches 6 repliesSuperseded

Changes in v6 from the cover letter

Move long-running tests into a pref test section

Patches in v6 Applied

#Subject and filesSizeRepliesApplied
1/12rib: add RIB libraryconfig/common_base doc/api/doxy-api.conf.in lib/Makefile +7 more+872 -10 replies
2/12test/rib: add RIB library autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+362 -00 replies
3/12rib: add ipv6 support for RIBlib/librte_rib/Makefile lib/librte_rib/meson.build lib/librte_rib/rte_rib6.c +2 more+951 -40 replies
4/12test/rib: add ipv6 support for RIB autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+366 -00 replies
5/12fib: add FIB libraryconfig/common_base doc/api/doxy-api.conf.in lib/Makefile +7 more+537 -00 replies
6/12fib: add FIB ipv6 supportlib/librte_fib/Makefile lib/librte_fib/meson.build lib/librte_fib/rte_fib6.c +2 more+500 -40 replies
7/12fib: add DIR24-8 dataplane algorithmlib/librte_fib/Makefile lib/librte_fib/dir24_8.c lib/librte_fib/dir24_8.h +3 more+805 -30 replies
8/12fib: add dataplane algorithm for ipv6lib/librte_fib/Makefile lib/librte_fib/meson.build lib/librte_fib/rte_fib6.c +3 more+827 -20 replies
9/12test/fib: add FIB library autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+431 -00 replies
10/12test/fib: add ipv6 support for FIB autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+439 -00 replies
11/12test/fib: add FIB library performance autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+420 -00 replies
12/12test/fib: add FIB library ipv6 performance autotestsapp/test/Makefile app/test/autotest_data.py app/test/meson.build +1 more+166 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v6 yet.

Read the v6 thread

Cover letter [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

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
Signature · 1 line
2.7.4