Message ID | cover.1568221361.git.vladimir.medvedkin@intel.com (mailing list archive) |
---|---|
Headers |
Return-Path: <dev-bounces@dpdk.org> X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 662961E56F; Wed, 11 Sep 2019 19:10:16 +0200 (CEST) Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by dpdk.org (Postfix) with ESMTP id 135941C06A for <dev@dpdk.org>; Wed, 11 Sep 2019 19:10:13 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga105.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Sep 2019 10:10:13 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.64,492,1559545200"; d="scan'208";a="196952123" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga002.jf.intel.com with ESMTP; 11 Sep 2019 10:10:11 -0700 From: Vladimir Medvedkin <vladimir.medvedkin@intel.com> To: dev@dpdk.org Cc: bruce.richardson@intel.com Date: Wed, 11 Sep 2019 18:09:40 +0100 Message-Id: <cover.1568221361.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> References: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> Subject: [dpdk-dev] [PATCH v5 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
Sept. 11, 2019, 5:09 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) 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
Comments
> -----Original Message----- > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir Medvedkin > > 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. > Great! > 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). The feedback following here is meant as a comment, not an objection. Feel free to ignore! This FIB library is designed for IP based forwarding only. How about forwarding based on other criteria? E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC. Such a FIB would probably require a different library, based on a hash structure, and would also require a compare-and-set function callable from the data plane in order to provide wire speed learning. So I suggest that the documentation highlights that this FIB library is for IP based forwarding. Optionally also reconsider the name of the library and its functions, structures 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) > Med venlig hilsen / kind regards - Morten Brørup
Hi Brørup, On 12/09/2019 08:37, Morten Brørup wrote: >> -----Original Message----- >> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir Medvedkin >> >> 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. >> > Great! > > >> 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). > The feedback following here is meant as a comment, not an objection. Feel free to ignore! > > This FIB library is designed for IP based forwarding only. > > How about forwarding based on other criteria? > E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC. > > Such a FIB would probably require a different library, based on a hash structure, and would also require a compare-and-set function callable from the data plane in order to provide wire speed learning. > > So I suggest that the documentation highlights that this FIB library is for IP based forwarding. Optionally also reconsider the name of the library and its functions, structures etc.. Thanks for the feedback. Yes, at the moment FIB has only longest prefix match algorithms. However, it is possible to add different exact match algorithms for VLAN+MAC/MPLS/etc processing. It is always hard to find proper name for library/function/variable, so if you think that fib name is not relevant feel free to suggest better :) > >> 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) >> > > Med venlig hilsen / kind regards > - Morten Brørup
Hi Vladimir, > -----Original Message----- > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Medvedkin, > Vladimir > > Hi Brørup, > > On 12/09/2019 08:37, Morten Brørup wrote: > >> -----Original Message----- > >> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir > Medvedkin > >> > >> This is heavily reworked version of previous RIB library series: > >> https://mails.dpdk.org/archives/dev/2018-April/099492.html > >> [snip] > >> 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). > > The feedback following here is meant as a comment, not an objection. > Feel free to ignore! > > > > This FIB library is designed for IP based forwarding only. > > > > How about forwarding based on other criteria? > > E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC. > > > > Such a FIB would probably require a different library, based on a > hash structure, and would also require a compare-and-set function > callable from the data plane in order to provide wire speed learning. > > > > So I suggest that the documentation highlights that this FIB library > is for IP based forwarding. Optionally also reconsider the name of the > library and its functions, structures etc.. > > Thanks for the feedback. > > Yes, at the moment FIB has only longest prefix match algorithms. > However, it is possible to add different exact match algorithms for > VLAN+MAC/MPLS/etc processing. > > It is always hard to find proper name for library/function/variable, so > if you think that fib name is not relevant feel free to suggest better > :) > You can use ip_/ipv4_/ipv6_ somewhere in the common prefix, like the ip_frag library, and unlike many other libraries. :-) And again: Feel free to ignore! > > -- > Regards, > Vladimir > Med venlig hilsen / kind regards - Morten Brørup