From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 862C2A0C4E; Mon, 8 Nov 2021 18:50:43 +0100 (CET) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 6CE66410FB; Mon, 8 Nov 2021 18:50:43 +0100 (CET) Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by mails.dpdk.org (Postfix) with ESMTP id E5213410FB for ; Mon, 8 Nov 2021 18:50:40 +0100 (CET) X-IronPort-AV: E=McAfee;i="6200,9189,10162"; a="295726472" X-IronPort-AV: E=Sophos;i="5.87,218,1631602800"; d="scan'208";a="295726472" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Nov 2021 09:37:58 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.87,218,1631602800"; d="scan'208";a="491306995" Received: from silpixa00400072.ir.intel.com (HELO silpixa00400072.ger.corp.intel.com) ([10.237.222.91]) by orsmga007.jf.intel.com with ESMTP; 08 Nov 2021 09:37:57 -0800 From: Vladimir Medvedkin To: dev@dpdk.org Date: Mon, 8 Nov 2021 17:37:26 +0000 Message-Id: <20211108173727.133124-2-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211108173727.133124-1-vladimir.medvedkin@intel.com> References: <20211108173727.133124-1-vladimir.medvedkin@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH 2/2] doc: add programmer's guide for the FIB library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Currently, programmer's guide for the FIB library is missing. This commit adds it. Signed-off-by: Vladimir Medvedkin --- doc/guides/prog_guide/fib_lib.rst | 139 +++++++++++++++++++++ doc/guides/prog_guide/img/dir_24_8_alg.svg | 136 ++++++++++++++++++++ doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/rib_lib.rst | 2 +- 4 files changed, 277 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/fib_lib.rst create mode 100644 doc/guides/prog_guide/img/dir_24_8_alg.svg diff --git a/doc/guides/prog_guide/fib_lib.rst b/doc/guides/prog_guide/fib_lib.rst new file mode 100644 index 0000000000..4aa02e1ed9 --- /dev/null +++ b/doc/guides/prog_guide/fib_lib.rst @@ -0,0 +1,139 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2021 Intel Corporation. + +.. _FIB_Library: + +FIB Library +=========== + +The FIB library provides a fast Longest Prefix Match (LPM) search for 32-bit +keys or 128-bit for IPv6. It can be used in a variety of applications, +the most typical of which is IPv4/IPv6 forwarding. + +.. note:: + + The API and implementation are very similar for IPv4's ``fib`` library and + IPv6's ``fib6`` library, therefore only the ``fib`` library will be discussed here. + Everything within this document except for the size of the prefixes applies + to the ``rib6`` library. + +FIB API Overview +---------------- + +The main configuration struct contains: + +* Type of :ref:`dataplane algorithm `. + +* Default next hop ID. + +* The maximum number of routes. + +* Settings for the data algorithm (:ref:`will be discussed later `). + +A FIB rule consists of a prefix and an associated next hop ID. The prefix consists +of an IPv4 network address (``uint32_t``) and the corresponding prefix length. +The prefix serves as the key and the next hop ID as the value while doing an LPM +search within FIB. The size of the next hop ID is variable and must be configured +during initialization. + +The main methods within the ``fib`` library are: + +* ``rte_fib_add()``: Add a new route with a corresponding next hop ID to the + table or update the next hop ID if the prefix already exists in a table. + +* ``rte_fib_delete()``: Delete an existing route from the table. + +* ``rte_fib_lookup_bulk()``: Provides a bulk Longest Prefix Match (LPM) lookup function + for a set of IP addresses, it will return a set of corresponding next hop IDs. + + +Implementation details +---------------------- + +Internally FIB contains the ``rte_rib`` data struct to help maintain the dataplane struct. +The dataplane struct is opaque, so that users can add their own algorithm implementations. + + +.. _fib_dataplane_algorithms: + +Dataplane Algorithms +-------------------- + +Dummy +~~~~~ + +This algorithm uses ``rte_rib`` as a dataplane struct. Lookups are relatively slow, +but extra memory isn't used for the dataplane struct. This algorithm should only +be used for testing and debugging purposes. + +This algorithm will be used if the ``RTE_FIB_DUMMY`` type is configured as the +dataplane algorithm on FIB creation. + + +DIR-24-8 +~~~~~~~~ + +The current implementation of this algorithm uses a variation of the DIR-24-8 +algorithm that trades memory usage for improved LPM lookup speed. +This algorithm allows the lookup operation to be performed using only a single +memory read access in most cases. In the statistically rare case where the best +match rule has a depth larger than 24, the lookup operation will require two +memory read accesses. + +This algorithm will be used if the ``RTE_FIB_DIR24_8`` type is configured as the +dataplane algorithm on FIB creation. + +The main FIB configuration struct stores the dataplane parameters inside ``dir24_8`` +within the ``rte_fib_conf`` and it consists of: + +* ``nh_sz``: The size of the entry containing the next hop ID. + This could be 1, 2, 4 or 8 bytes long. + Note that all available bits except one are used to store the actual next hop ID. + +* ``num_tbl8``: The number of tbl8 groups, each group consists of 256 entries + corresponding to the ``nh_sz`` size. + +The main elements of the dataplane struct for the DIR-24-8 algorithm are: + +* TBL24: An array with 2\ :sup:`24` entries, corresponding to the ``nh_sz`` size. + +* TBL8: An array of ``num_tbl8`` tbl8 groups. + +The lookup algorithms logic can be seen in :numref:`figure_dir_24_8_alg`: + +.. _figure_dir_24_8_alg: + +.. figure:: img/dir_24_8_alg.* + + DIR-24-8 Lookup algorithm + +The first table ``tbl24``, is indexed using the first 24 bits of the IP address to be looked up, +while the second table(s) ``tbl8``, is indexed using the last 8 bits of the IP address. +This means that depending on the outcome of trying to match the IP address of an incoming packet +to a rule stored in the tbl24 we might need to continue the lookup process in the second level. + +Since every entry of the tbl24 can potentially point to a tbl8, +ideally we would have 2\ :sup:`24` tbl8s, which would be the same as having a +single table with 2\ :sup:`32` entries. This is not feasible due to resource restrictions. +Instead, this approach takes advantage of the fact that rules longer than 24 bits are very rare. +By splitting the process into two different tables/levels and limiting the number of tbl8s, +we can greatly reduce memory consumption while maintaining a very good lookup speed. +This method generally results in one memory access per lookup. + +An entry in a tbl8 contains the following fields: + +* The next hop ID. + +* 1 bit indicating if the lookup should proceed inside the tbl8. + +Use cases +--------- + +The FIB library is useful for any use cases that rely on the Longest Prefix Match (LPM) +algorithm such as IP forwarding or packet classification. + +More complex use cases are also possible, as it is possible to have next hop IDs +which are 63 bits long (using ``RTE_FIB_DIR24_8_8B`` as a next hop size). +These use cases could include storing two next hop IDs inside the 63 bits of the next hop. +This may be useful to provide a fallback next hop ID, ASN or forwarding class +corresponding to a given prefix without having to perform an additional lookup. diff --git a/doc/guides/prog_guide/img/dir_24_8_alg.svg b/doc/guides/prog_guide/img/dir_24_8_alg.svg new file mode 100644 index 0000000000..17725b7b97 --- /dev/null +++ b/doc/guides/prog_guide/img/dir_24_8_alg.svg @@ -0,0 +1,136 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + uint[8,16,32,64]_t + + + + + + + nh_id + + + + + + + + + + + + + + + + + + + uint[8,16,32,64]_t + + + + nh_id + + + + + + + 24 + + + + 8 + + + + + + + Extended entry? + + + + Return nh_id + + + + + no + + + + + + + nh_id * 256 + ip & 0xff + + + + + + + + + + + yes + + + + + + + IPv4 Address + + + + tbl24 + + + + tbl8 + + + diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index 0a53ec71c8..42c4a690c6 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -38,6 +38,7 @@ Programmer's Guide member_lib lpm_lib lpm6_lib + fib_lib rib_lib flow_classify_lib packet_distrib_lib diff --git a/doc/guides/prog_guide/rib_lib.rst b/doc/guides/prog_guide/rib_lib.rst index e8bb35a2b6..0a6c3d7063 100644 --- a/doc/guides/prog_guide/rib_lib.rst +++ b/doc/guides/prog_guide/rib_lib.rst @@ -7,7 +7,7 @@ RIB Library The Routing Information Base (RIB) library provides a data store for routing information. This library is intended for use in control or management plane applications. There are more suitable libraries for use in data plane applications such as -:ref:`LPM ` or FIB. +:ref:`LPM ` or :ref:`FIB `. Implementation details -- 2.25.1