Patch Detail

HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "id": 62323,
    "url": "http://patches.dpdk.org/api/patches/62323/?format=api",
    "web_url": "http://patches.dpdk.org/project/dpdk/patch/db77f2dced2f3c2cd95f295f2e4fe98bad7442c8.1572621163.git.vladimir.medvedkin@intel.com/",
    "project": {
        "id": 1,
        "url": "http://patches.dpdk.org/api/projects/1/?format=api",
        "name": "DPDK",
        "link_name": "dpdk",
        "list_id": "dev.dpdk.org",
        "list_email": "dev@dpdk.org",
        "web_url": "http://core.dpdk.org",
        "scm_url": "git://dpdk.org/dpdk",
        "webscm_url": "http://git.dpdk.org/dpdk",
        "list_archive_url": "https://inbox.dpdk.org/dev",
        "list_archive_url_format": "https://inbox.dpdk.org/dev/{}",
        "commit_url_format": ""
    },
    "msgid": "<db77f2dced2f3c2cd95f295f2e4fe98bad7442c8.1572621163.git.vladimir.medvedkin@intel.com>",
    "list_archive_url": "https://inbox.dpdk.org/dev/db77f2dced2f3c2cd95f295f2e4fe98bad7442c8.1572621163.git.vladimir.medvedkin@intel.com",
    "date": "2019-11-01T15:21:41",
    "name": "[v6,08/12] fib: add dataplane algorithm for ipv6",
    "commit_ref": null,
    "pull_url": null,
    "state": "accepted",
    "archived": true,
    "hash": "afe6a7e45baee52a79ac1ffe32cbf59000f85c0b",
    "submitter": {
        "id": 1216,
        "url": "http://patches.dpdk.org/api/people/1216/?format=api",
        "name": "Vladimir Medvedkin",
        "email": "vladimir.medvedkin@intel.com"
    },
    "delegate": {
        "id": 1,
        "url": "http://patches.dpdk.org/api/users/1/?format=api",
        "username": "tmonjalo",
        "first_name": "Thomas",
        "last_name": "Monjalon",
        "email": "thomas@monjalon.net"
    },
    "mbox": "http://patches.dpdk.org/project/dpdk/patch/db77f2dced2f3c2cd95f295f2e4fe98bad7442c8.1572621163.git.vladimir.medvedkin@intel.com/mbox/",
    "series": [
        {
            "id": 7198,
            "url": "http://patches.dpdk.org/api/series/7198/?format=api",
            "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=7198",
            "date": "2019-11-01T15:21:33",
            "name": "lib: add RIB and FIB liraries",
            "version": 6,
            "mbox": "http://patches.dpdk.org/series/7198/mbox/"
        }
    ],
    "comments": "http://patches.dpdk.org/api/patches/62323/comments/",
    "check": "success",
    "checks": "http://patches.dpdk.org/api/patches/62323/checks/",
    "tags": {},
    "related": [],
    "headers": {
        "Return-Path": "<dev-bounces@dpdk.org>",
        "X-Original-To": "patchwork@inbox.dpdk.org",
        "Delivered-To": "patchwork@inbox.dpdk.org",
        "Received": [
            "from dpdk.org (dpdk.org [92.243.14.124])\n\tby inbox.dpdk.org (Postfix) with ESMTP id 767DAA00BE;\n\tFri,  1 Nov 2019 16:23:34 +0100 (CET)",
            "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id A01981E886;\n\tFri,  1 Nov 2019 16:22:09 +0100 (CET)",
            "from mga09.intel.com (mga09.intel.com [134.134.136.24])\n by dpdk.org (Postfix) with ESMTP id D37EA1E86E\n for <dev@dpdk.org>; Fri,  1 Nov 2019 16:22:06 +0100 (CET)",
            "from orsmga004.jf.intel.com ([10.7.209.38])\n by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n 01 Nov 2019 08:22:06 -0700",
            "from silpixa00400072.ir.intel.com ([10.237.222.213])\n by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:04 -0700"
        ],
        "X-Amp-Result": "SKIPPED(no attachment in message)",
        "X-Amp-File-Uploaded": "False",
        "X-ExtLoop1": "1",
        "X-IronPort-AV": "E=Sophos;i=\"5.68,256,1569308400\"; d=\"scan'208\";a=\"351979131\"",
        "From": "Vladimir Medvedkin <vladimir.medvedkin@intel.com>",
        "To": "dev@dpdk.org",
        "Cc": "bruce.richardson@intel.com, konstantin.ananyev@intel.com,\n thomas@monjalon.net, aconole@redhat.com",
        "Date": "Fri,  1 Nov 2019 15:21:41 +0000",
        "Message-Id": "\n <db77f2dced2f3c2cd95f295f2e4fe98bad7442c8.1572621163.git.vladimir.medvedkin@intel.com>",
        "X-Mailer": "git-send-email 2.7.4",
        "In-Reply-To": [
            "<cover.1572621162.git.vladimir.medvedkin@intel.com>",
            "<cover.1572621162.git.vladimir.medvedkin@intel.com>"
        ],
        "References": [
            "<cover.1572621162.git.vladimir.medvedkin@intel.com>",
            "<cover.1568221361.git.vladimir.medvedkin@intel.com>\n <cover.1572621162.git.vladimir.medvedkin@intel.com>"
        ],
        "Subject": "[dpdk-dev] [PATCH v6 08/12] fib: add dataplane algorithm for ipv6",
        "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>,\n <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>,\n <mailto:dev-request@dpdk.org?subject=subscribe>",
        "Errors-To": "dev-bounces@dpdk.org",
        "Sender": "\"dev\" <dev-bounces@dpdk.org>"
    },
    "content": "Add fib implementation for ipv6 using modified DIR24_8 algorithm.\nImplementation is similar to current LPM6 implementation but has\nfew enhancements:\nfaster control plabe operations\nmore bits for userdata in table entries\nconfigurable userdata size\n\nSigned-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>\n---\n lib/librte_fib/Makefile    |   2 +-\n lib/librte_fib/meson.build |   2 +-\n lib/librte_fib/rte_fib6.c  |  14 +\n lib/librte_fib/rte_fib6.h  |  14 +\n lib/librte_fib/trie.c      | 760 +++++++++++++++++++++++++++++++++++++++++++++\n lib/librte_fib/trie.h      |  37 +++\n 6 files changed, 827 insertions(+), 2 deletions(-)\n create mode 100644 lib/librte_fib/trie.c\n create mode 100644 lib/librte_fib/trie.h",
    "diff": "diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile\nindex 67fde9a..4abd80b 100644\n--- a/lib/librte_fib/Makefile\n+++ b/lib/librte_fib/Makefile\n@@ -17,7 +17,7 @@ EXPORT_MAP := rte_fib_version.map\n LIBABIVER := 1\n \n # all source are stored in SRCS-y\n-SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c\n+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c trie.c\n \n # install this header file\n SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h\ndiff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build\nindex c63cac8..e2c6f44 100644\n--- a/lib/librte_fib/meson.build\n+++ b/lib/librte_fib/meson.build\n@@ -3,6 +3,6 @@\n # Copyright(c) 2019 Intel Corporation\n \n allow_experimental_apis = true\n-sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c')\n+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c')\n headers = files('rte_fib.h', 'rte_fib6.h')\n deps += ['rib']\ndiff --git a/lib/librte_fib/rte_fib6.c b/lib/librte_fib/rte_fib6.c\nindex 9f00a80..354227d 100644\n--- a/lib/librte_fib/rte_fib6.c\n+++ b/lib/librte_fib/rte_fib6.c\n@@ -17,6 +17,8 @@\n #include <rte_rib6.h>\n #include <rte_fib6.h>\n \n+#include \"trie.h\"\n+\n TAILQ_HEAD(rte_fib6_list, rte_tailq_entry);\n static struct rte_tailq_elem rte_fib6_tailq = {\n \t.name = \"RTE_FIB6\",\n@@ -92,12 +94,22 @@ static int\n init_dataplane(struct rte_fib6 *fib, __rte_unused int socket_id,\n \tstruct rte_fib6_conf *conf)\n {\n+\tchar dp_name[sizeof(void *)];\n+\n+\tsnprintf(dp_name, sizeof(dp_name), \"%p\", fib);\n \tswitch (conf->type) {\n \tcase RTE_FIB6_DUMMY:\n \t\tfib->dp = fib;\n \t\tfib->lookup = dummy_lookup;\n \t\tfib->modify = dummy_modify;\n \t\treturn 0;\n+\tcase RTE_FIB6_TRIE:\n+\t\tfib->dp = trie_create(dp_name, socket_id, conf);\n+\t\tif (fib->dp == NULL)\n+\t\t\treturn -rte_errno;\n+\t\tfib->lookup = rte_trie_get_lookup_fn(conf);\n+\t\tfib->modify = trie_modify;\n+\t\treturn 0;\n \tdefault:\n \t\treturn -EINVAL;\n \t}\n@@ -260,6 +272,8 @@ free_dataplane(struct rte_fib6 *fib)\n \tswitch (fib->type) {\n \tcase RTE_FIB6_DUMMY:\n \t\treturn;\n+\tcase RTE_FIB6_TRIE:\n+\t\ttrie_free(fib->dp);\n \tdefault:\n \t\treturn;\n \t}\ndiff --git a/lib/librte_fib/rte_fib6.h b/lib/librte_fib/rte_fib6.h\nindex 3322123..4268704 100644\n--- a/lib/librte_fib/rte_fib6.h\n+++ b/lib/librte_fib/rte_fib6.h\n@@ -19,10 +19,12 @@\n #define RTE_FIB6_MAXDEPTH       128\n \n struct rte_fib6;\n+struct rte_rib6;\n \n /** Type of FIB struct */\n enum rte_fib6_type {\n \tRTE_FIB6_DUMMY,\t\t/**< RIB6 tree based FIB */\n+\tRTE_FIB6_TRIE,\t\t/**< TRIE based fib  */\n \tRTE_FIB6_TYPE_MAX\n };\n \n@@ -40,12 +42,24 @@ enum rte_fib6_op {\n \tRTE_FIB6_DEL,\n };\n \n+enum rte_fib_trie_nh_sz {\n+\tRTE_FIB6_TRIE_2B = 1,\n+\tRTE_FIB6_TRIE_4B,\n+\tRTE_FIB6_TRIE_8B\n+};\n+\n /** FIB configuration structure */\n struct rte_fib6_conf {\n \tenum rte_fib6_type type; /**< Type of FIB struct */\n \t/** Default value returned on lookup if there is no route */\n \tuint64_t default_nh;\n \tint\tmax_routes;\n+\tunion {\n+\t\tstruct {\n+\t\t\tenum rte_fib_trie_nh_sz nh_sz;\n+\t\t\tuint32_t\tnum_tbl8;\n+\t\t} trie;\n+\t};\n };\n \n /**\ndiff --git a/lib/librte_fib/trie.c b/lib/librte_fib/trie.c\nnew file mode 100644\nindex 0000000..198e815\n--- /dev/null\n+++ b/lib/librte_fib/trie.c\n@@ -0,0 +1,760 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#include <stdint.h>\n+#include <stdlib.h>\n+#include <stdio.h>\n+#include <string.h>\n+#include <inttypes.h>\n+\n+#include <rte_debug.h>\n+#include <rte_malloc.h>\n+#include <rte_prefetch.h>\n+#include <rte_errno.h>\n+#include <rte_memory.h>\n+#include <rte_branch_prediction.h>\n+\n+#include <rte_rib6.h>\n+#include <rte_fib6.h>\n+#include \"trie.h\"\n+\n+/* @internal Total number of tbl24 entries. */\n+#define TRIE_TBL24_NUM_ENT\t(1 << 24)\n+\n+/* Maximum depth value possible for IPv6 LPM. */\n+#define TRIE_MAX_DEPTH\t\t128\n+\n+/* @internal Number of entries in a tbl8 group. */\n+#define TRIE_TBL8_GRP_NUM_ENT\t256ULL\n+\n+/* @internal Total number of tbl8 groups in the tbl8. */\n+#define TRIE_TBL8_NUM_GROUPS\t65536\n+\n+/* @internal bitmask with valid and valid_group fields set */\n+#define TRIE_EXT_ENT\t\t1\n+\n+#define TRIE_NAMESIZE\t\t64\n+\n+#define BITMAP_SLAB_BIT_SIZE_LOG2\t6\n+#define BITMAP_SLAB_BIT_SIZE\t\t(1ULL << BITMAP_SLAB_BIT_SIZE_LOG2)\n+#define BITMAP_SLAB_BITMASK\t\t(BITMAP_SLAB_BIT_SIZE - 1)\n+\n+struct rte_trie_tbl {\n+\tuint32_t\tnumber_tbl8s;\t/**< Total number of tbl8s */\n+\tuint32_t\trsvd_tbl8s;\t/**< Number of reserved tbl8s */\n+\tuint32_t\tcur_tbl8s;\t/**< Current cumber of tbl8s */\n+\tuint64_t\tdef_nh;\t\t/**< Default next hop */\n+\tenum rte_fib_trie_nh_sz\tnh_sz;\t/**< Size of nexthop entry */\n+\tuint64_t\t*tbl8;\t\t/**< tbl8 table. */\n+\tuint32_t\t*tbl8_pool;\t/**< bitmap containing free tbl8 idxes*/\n+\tuint32_t\ttbl8_pool_pos;\n+\t/* tbl24 table. */\n+\t__extension__ uint64_t\ttbl24[0] __rte_cache_aligned;\n+};\n+\n+enum edge {\n+\tLEDGE,\n+\tREDGE\n+};\n+\n+enum lookup_type {\n+\tMACRO,\n+\tINLINE,\n+\tUNI\n+};\n+static enum lookup_type test_lookup = MACRO;\n+\n+static inline uint32_t\n+get_tbl24_idx(const uint8_t *ip)\n+{\n+\treturn ip[0] << 16|ip[1] << 8|ip[2];\n+}\n+\n+static inline void *\n+get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz)\n+{\n+\tuint32_t tbl24_idx;\n+\n+\ttbl24_idx = get_tbl24_idx(ip);\n+\treturn (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz];\n+}\n+\n+static inline uint8_t\n+bits_in_nh(uint8_t nh_sz)\n+{\n+\treturn 8 * (1 << nh_sz);\n+}\n+\n+static inline uint64_t\n+get_max_nh(uint8_t nh_sz)\n+{\n+\treturn ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);\n+}\n+\n+static inline uint64_t\n+lookup_msk(uint8_t nh_sz)\n+{\n+\treturn ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;\n+}\n+\n+static inline uint8_t\n+get_psd_idx(uint32_t val, uint8_t nh_sz)\n+{\n+\treturn val & ((1 << (3 - nh_sz)) - 1);\n+}\n+\n+static inline uint32_t\n+get_tbl_pos(uint32_t val, uint8_t nh_sz)\n+{\n+\treturn val >> (3 - nh_sz);\n+}\n+\n+static inline uint64_t\n+get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz)\n+{\n+\treturn ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) *\n+\t\tbits_in_nh(nh_sz))) & lookup_msk(nh_sz));\n+}\n+\n+static inline void *\n+get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz)\n+{\n+\treturn (uint8_t *)tbl + (idx << nh_sz);\n+}\n+\n+static inline int\n+is_entry_extended(uint64_t ent)\n+{\n+\treturn (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT;\n+}\n+\n+#define LOOKUP_FUNC(suffix, type, nh_sz)\t\t\t\t\\\n+static void rte_trie_lookup_bulk_##suffix(void *p,\t\t\t\\\n+\tuint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],\t\t\t\\\n+\tuint64_t *next_hops, const unsigned int n)\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tstruct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;\t\t\\\n+\tuint64_t tmp;\t\t\t\t\t\t\t\\\n+\tuint32_t i, j;\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tfor (i = 0; i < n; i++) {\t\t\t\t\t\\\n+\t\ttmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])];\t\\\n+\t\tj = 3;\t\t\t\t\t\t\t\\\n+\t\twhile (is_entry_extended(tmp)) {\t\t\t\\\n+\t\t\ttmp = ((type *)dp->tbl8)[ips[i][j++] +\t\t\\\n+\t\t\t\t((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)];\t\\\n+\t\t}\t\t\t\t\t\t\t\\\n+\t\tnext_hops[i] = tmp >> 1;\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+}\n+LOOKUP_FUNC(2b, uint16_t, 1)\n+LOOKUP_FUNC(4b, uint32_t, 2)\n+LOOKUP_FUNC(8b, uint64_t, 3)\n+\n+rte_fib6_lookup_fn_t\n+rte_trie_get_lookup_fn(struct rte_fib6_conf *conf)\n+{\n+\tenum rte_fib_trie_nh_sz nh_sz = conf->trie.nh_sz;\n+\n+\tif (test_lookup == MACRO) {\n+\t\tswitch (nh_sz) {\n+\t\tcase RTE_FIB6_TRIE_2B:\n+\t\t\treturn rte_trie_lookup_bulk_2b;\n+\t\tcase RTE_FIB6_TRIE_4B:\n+\t\t\treturn rte_trie_lookup_bulk_4b;\n+\t\tcase RTE_FIB6_TRIE_8B:\n+\t\t\treturn rte_trie_lookup_bulk_8b;\n+\t\t}\n+\t}\n+\n+\treturn NULL;\n+}\n+\n+static void\n+write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n)\n+{\n+\tint i;\n+\tuint16_t *ptr16 = (uint16_t *)ptr;\n+\tuint32_t *ptr32 = (uint32_t *)ptr;\n+\tuint64_t *ptr64 = (uint64_t *)ptr;\n+\n+\tswitch (size) {\n+\tcase RTE_FIB6_TRIE_2B:\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tptr16[i] = (uint16_t)val;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_4B:\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tptr32[i] = (uint32_t)val;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_8B:\n+\t\tfor (i = 0; i < n; i++)\n+\t\t\tptr64[i] = (uint64_t)val;\n+\t\tbreak;\n+\t}\n+}\n+\n+static void\n+tbl8_pool_init(struct rte_trie_tbl *dp)\n+{\n+\tuint32_t i;\n+\n+\t/* put entire range of indexes to the tbl8 pool */\n+\tfor (i = 0; i < dp->number_tbl8s; i++)\n+\t\tdp->tbl8_pool[i] = i;\n+\n+\tdp->tbl8_pool_pos = 0;\n+}\n+\n+/*\n+ * Get an index of a free tbl8 from the pool\n+ */\n+static inline int32_t\n+tbl8_get(struct rte_trie_tbl *dp)\n+{\n+\tif (dp->tbl8_pool_pos == dp->number_tbl8s)\n+\t\t/* no more free tbl8 */\n+\t\treturn -ENOSPC;\n+\n+\t/* next index */\n+\treturn dp->tbl8_pool[dp->tbl8_pool_pos++];\n+}\n+\n+/*\n+ * Put an index of a free tbl8 back to the pool\n+ */\n+static inline void\n+tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind)\n+{\n+\tdp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind;\n+}\n+\n+static int\n+tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh)\n+{\n+\tint64_t\t\ttbl8_idx;\n+\tuint8_t\t\t*tbl8_ptr;\n+\n+\ttbl8_idx = tbl8_get(dp);\n+\tif (tbl8_idx < 0)\n+\t\treturn tbl8_idx;\n+\ttbl8_ptr = (uint8_t *)dp->tbl8 +\n+\t\t((tbl8_idx * TRIE_TBL8_GRP_NUM_ENT) <<\n+\t\tdp->nh_sz);\n+\t/*Init tbl8 entries with nexthop from tbl24*/\n+\twrite_to_dp((void *)tbl8_ptr, nh, dp->nh_sz,\n+\t\tTRIE_TBL8_GRP_NUM_ENT);\n+\treturn tbl8_idx;\n+}\n+\n+static void\n+tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx)\n+{\n+\tuint32_t i;\n+\tuint64_t nh;\n+\tuint16_t *ptr16;\n+\tuint32_t *ptr32;\n+\tuint64_t *ptr64;\n+\n+\tswitch (dp->nh_sz) {\n+\tcase RTE_FIB6_TRIE_2B:\n+\t\tptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *\n+\t\t\t\tTRIE_TBL8_GRP_NUM_ENT];\n+\t\tnh = *ptr16;\n+\t\tif (nh & TRIE_EXT_ENT)\n+\t\t\treturn;\n+\t\tfor (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {\n+\t\t\tif (nh != ptr16[i])\n+\t\t\t\treturn;\n+\t\t}\n+\t\twrite_to_dp(par, nh, dp->nh_sz, 1);\n+\t\tfor (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)\n+\t\t\tptr16[i] = 0;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_4B:\n+\t\tptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *\n+\t\t\t\tTRIE_TBL8_GRP_NUM_ENT];\n+\t\tnh = *ptr32;\n+\t\tif (nh & TRIE_EXT_ENT)\n+\t\t\treturn;\n+\t\tfor (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {\n+\t\t\tif (nh != ptr32[i])\n+\t\t\t\treturn;\n+\t\t}\n+\t\twrite_to_dp(par, nh, dp->nh_sz, 1);\n+\t\tfor (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)\n+\t\t\tptr32[i] = 0;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_8B:\n+\t\tptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *\n+\t\t\t\tTRIE_TBL8_GRP_NUM_ENT];\n+\t\tnh = *ptr64;\n+\t\tif (nh & TRIE_EXT_ENT)\n+\t\t\treturn;\n+\t\tfor (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {\n+\t\t\tif (nh != ptr64[i])\n+\t\t\t\treturn;\n+\t\t}\n+\t\twrite_to_dp(par, nh, dp->nh_sz, 1);\n+\t\tfor (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)\n+\t\t\tptr64[i] = 0;\n+\t\tbreak;\n+\t}\n+\ttbl8_put(dp, tbl8_idx);\n+}\n+\n+#define BYTE_SIZE\t8\n+static inline uint32_t\n+get_idx(const uint8_t *ip, uint32_t prev_idx, int bytes, int first_byte)\n+{\n+\tint i;\n+\tuint32_t idx = 0;\n+\tuint8_t bitshift;\n+\n+\tfor (i = first_byte; i < (first_byte + bytes); i++) {\n+\t\tbitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE);\n+\t\tidx |= ip[i] <<  bitshift;\n+\t}\n+\treturn (prev_idx * 256) + idx;\n+}\n+\n+static inline uint64_t\n+get_val_by_p(void *p, uint8_t nh_sz)\n+{\n+\tuint64_t val = 0;\n+\n+\tswitch (nh_sz) {\n+\tcase RTE_FIB6_TRIE_2B:\n+\t\tval = *(uint16_t *)p;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_4B:\n+\t\tval = *(uint32_t *)p;\n+\t\tbreak;\n+\tcase RTE_FIB6_TRIE_8B:\n+\t\tval = *(uint64_t *)p;\n+\t\tbreak;\n+\t}\n+\treturn val;\n+}\n+\n+/*\n+ * recursively recycle tbl8's\n+ */\n+static void\n+recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part,\n+\tuint8_t common_tbl8, void *prev)\n+{\n+\tvoid *p;\n+\tuint64_t val;\n+\n+\tval = get_val_by_p(prev, dp->nh_sz);\n+\tif (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT))\n+\t\treturn;\n+\n+\tif (common_tbl8 != 0) {\n+\t\tp = get_tbl_p_by_idx(dp->tbl8, (val >> 1) * 256 + *ip_part,\n+\t\t\tdp->nh_sz);\n+\t\trecycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p);\n+\t}\n+\ttbl8_recycle(dp, prev, val >> 1);\n+}\n+\n+static inline int\n+build_common_root(struct rte_trie_tbl *dp, const uint8_t *ip,\n+\tint common_bytes, void **tbl)\n+{\n+\tvoid *tbl_ptr = NULL;\n+\tuint64_t *cur_tbl;\n+\tuint64_t val;\n+\tint i, j, idx, prev_idx = 0;\n+\n+\tcur_tbl = dp->tbl24;\n+\tfor (i = 3, j = 0; i <= common_bytes; i++) {\n+\t\tidx = get_idx(ip, prev_idx, i - j, j);\n+\t\tval = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);\n+\t\ttbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);\n+\t\tif ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {\n+\t\t\tidx = tbl8_alloc(dp, val);\n+\t\t\tif (unlikely(idx < 0))\n+\t\t\t\treturn idx;\n+\t\t\twrite_to_dp(tbl_ptr, (idx << 1) |\n+\t\t\t\tTRIE_EXT_ENT, dp->nh_sz, 1);\n+\t\t\tprev_idx = idx;\n+\t\t} else\n+\t\t\tprev_idx = val >> 1;\n+\n+\t\tj = i;\n+\t\tcur_tbl = dp->tbl8;\n+\t}\n+\t*tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * 256, dp->nh_sz);\n+\treturn 0;\n+}\n+\n+static int\n+write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop,\n+\tint len, enum edge edge, void *ent)\n+{\n+\tuint64_t val = next_hop << 1;\n+\tint tbl8_idx;\n+\tint ret = 0;\n+\tvoid *p;\n+\n+\tif (len != 0) {\n+\t\tval = get_val_by_p(ent, dp->nh_sz);\n+\t\tif ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT)\n+\t\t\ttbl8_idx = val >> 1;\n+\t\telse {\n+\t\t\ttbl8_idx = tbl8_alloc(dp, val);\n+\t\t\tif (tbl8_idx < 0)\n+\t\t\t\treturn tbl8_idx;\n+\t\t\tval = (tbl8_idx << 1)|TRIE_EXT_ENT;\n+\t\t}\n+\t\tp = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx * 256) + *ip_part,\n+\t\t\tdp->nh_sz);\n+\t\tret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p);\n+\t\tif (ret < 0)\n+\t\t\treturn ret;\n+\t\tif (edge == LEDGE) {\n+\t\t\twrite_to_dp((uint8_t *)p + (1 << dp->nh_sz),\n+\t\t\t\tnext_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part);\n+\t\t} else {\n+\t\t\twrite_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx * 256,\n+\t\t\t\tdp->nh_sz),\n+\t\t\t\tnext_hop << 1, dp->nh_sz, *ip_part);\n+\t\t}\n+\t\ttbl8_recycle(dp, &val, tbl8_idx);\n+\t}\n+\n+\twrite_to_dp(ent, val, dp->nh_sz, 1);\n+\treturn ret;\n+}\n+\n+#define IPV6_MAX_IDX\t(RTE_FIB6_IPV6_ADDR_SIZE - 1)\n+#define TBL24_BYTES\t3\n+#define TBL8_LEN\t(RTE_FIB6_IPV6_ADDR_SIZE - TBL24_BYTES)\n+\n+static int\n+install_to_dp(struct rte_trie_tbl *dp, const uint8_t *ledge, const uint8_t *r,\n+\tuint64_t next_hop)\n+{\n+\tvoid *common_root_tbl;\n+\tvoid *ent;\n+\tint ret;\n+\tint i;\n+\tint common_bytes;\n+\tint llen, rlen;\n+\tuint8_t redge[16];\n+\n+\t/* decrement redge by 1*/\n+\trte_rib6_copy_addr(redge, r);\n+\tfor (i = 15; i >= 0; i--) {\n+\t\tredge[i]--;\n+\t\tif (redge[i] != 0xff)\n+\t\t\tbreak;\n+\t}\n+\n+\tfor (common_bytes = 0; common_bytes < 15; common_bytes++) {\n+\t\tif (ledge[common_bytes] != redge[common_bytes])\n+\t\t\tbreak;\n+\t}\n+\n+\tret = build_common_root(dp, ledge, common_bytes, &common_root_tbl);\n+\tif (unlikely(ret != 0))\n+\t\treturn ret;\n+\t/*first uncommon tbl8 byte idx*/\n+\tuint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES);\n+\n+\tfor (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {\n+\t\tif (ledge[i] != 0)\n+\t\t\tbreak;\n+\t}\n+\n+\tllen = i - first_tbl8_byte + (common_bytes < 3);\n+\n+\tfor (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {\n+\t\tif (redge[i] != UINT8_MAX)\n+\t\t\tbreak;\n+\t}\n+\trlen = i - first_tbl8_byte + (common_bytes < 3);\n+\n+\t/*first noncommon byte*/\n+\tuint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;\n+\tuint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;\n+\n+\tuint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);\n+\tuint32_t right_idx = get_idx(redge, 0, first_idx_len, first_byte_idx);\n+\n+\tent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);\n+\tret = write_edge(dp, &ledge[first_tbl8_byte + !(common_bytes < 3)],\n+\t\tnext_hop, llen, LEDGE, ent);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\tif (right_idx > left_idx + 1) {\n+\t\tent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1,\n+\t\t\tdp->nh_sz);\n+\t\twrite_to_dp(ent, next_hop << 1, dp->nh_sz,\n+\t\t\tright_idx - (left_idx + 1));\n+\t}\n+\tent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz);\n+\tret = write_edge(dp, &redge[first_tbl8_byte + !((common_bytes < 3))],\n+\t\tnext_hop, rlen, REDGE, ent);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\tuint8_t\tcommon_tbl8 = (common_bytes < TBL24_BYTES) ?\n+\t\t\t0 : common_bytes - (TBL24_BYTES - 1);\n+\tent = get_tbl24_p(dp, ledge, dp->nh_sz);\n+\trecycle_root_path(dp, ledge + TBL24_BYTES, common_tbl8, ent);\n+\treturn 0;\n+}\n+\n+static void\n+get_nxt_net(uint8_t *ip, uint8_t depth)\n+{\n+\tint i;\n+\tuint8_t part_depth;\n+\tuint8_t prev_byte;\n+\n+\tfor (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++)\n+\t\t;\n+\n+\tprev_byte = ip[i];\n+\tip[i] += 1 << (8 - part_depth);\n+\tif (ip[i] < prev_byte) {\n+\t\twhile (i > 0) {\n+\t\t\tip[--i] += 1;\n+\t\t\tif (ip[i] != 0)\n+\t\t\t\tbreak;\n+\t\t}\n+\t}\n+}\n+\n+static int\n+modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,\n+\tconst uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],\n+\tuint8_t depth, uint64_t next_hop)\n+{\n+\tstruct rte_rib6_node *tmp = NULL;\n+\tuint8_t ledge[RTE_FIB6_IPV6_ADDR_SIZE];\n+\tuint8_t redge[RTE_FIB6_IPV6_ADDR_SIZE];\n+\tint ret;\n+\tuint8_t tmp_depth;\n+\n+\tif (next_hop > get_max_nh(dp->nh_sz))\n+\t\treturn -EINVAL;\n+\n+\trte_rib6_copy_addr(ledge, ip);\n+\tdo {\n+\t\ttmp = rte_rib6_get_nxt(rib, ip, depth, tmp,\n+\t\t\tRTE_RIB6_GET_NXT_COVER);\n+\t\tif (tmp != NULL) {\n+\t\t\trte_rib6_get_depth(tmp, &tmp_depth);\n+\t\t\tif (tmp_depth == depth)\n+\t\t\t\tcontinue;\n+\t\t\trte_rib6_get_ip(tmp, redge);\n+\t\t\tif (rte_rib6_is_equal(ledge, redge)) {\n+\t\t\t\tget_nxt_net(ledge, tmp_depth);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tret = install_to_dp(dp, ledge, redge,\n+\t\t\t\tnext_hop);\n+\t\t\tif (ret != 0)\n+\t\t\t\treturn ret;\n+\t\t\tget_nxt_net(redge, tmp_depth);\n+\t\t\trte_rib6_copy_addr(ledge, redge);\n+\t\t} else {\n+\t\t\trte_rib6_copy_addr(redge, ip);\n+\t\t\tget_nxt_net(redge, depth);\n+\t\t\tif (rte_rib6_is_equal(ledge, redge))\n+\t\t\t\tbreak;\n+\t\t\tret = install_to_dp(dp, ledge, redge,\n+\t\t\t\tnext_hop);\n+\t\t\tif (ret != 0)\n+\t\t\t\treturn ret;\n+\t\t}\n+\t} while (tmp);\n+\n+\treturn 0;\n+}\n+\n+int\n+trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],\n+\tuint8_t depth, uint64_t next_hop, int op)\n+{\n+\tstruct rte_trie_tbl *dp;\n+\tstruct rte_rib6 *rib;\n+\tstruct rte_rib6_node *tmp = NULL;\n+\tstruct rte_rib6_node *node;\n+\tstruct rte_rib6_node *parent;\n+\tuint8_t\tip_masked[RTE_FIB6_IPV6_ADDR_SIZE];\n+\tint i, ret = 0;\n+\tuint64_t par_nh, node_nh;\n+\tuint8_t tmp_depth, depth_diff = 0, parent_depth = 24;\n+\n+\tif ((fib == NULL) || (ip == NULL) || (depth > RTE_FIB6_MAXDEPTH))\n+\t\treturn -EINVAL;\n+\n+\tdp = rte_fib6_get_dp(fib);\n+\tRTE_ASSERT(dp);\n+\trib = rte_fib6_get_rib(fib);\n+\tRTE_ASSERT(rib);\n+\n+\tfor (i = 0; i < RTE_FIB6_IPV6_ADDR_SIZE; i++)\n+\t\tip_masked[i] = ip[i] & get_msk_part(depth, i);\n+\n+\tif (depth > 24) {\n+\t\ttmp = rte_rib6_get_nxt(rib, ip_masked,\n+\t\t\tRTE_ALIGN_FLOOR(depth, 8), NULL,\n+\t\t\tRTE_RIB6_GET_NXT_COVER);\n+\t\tif (tmp == NULL) {\n+\t\t\ttmp = rte_rib6_lookup(rib, ip);\n+\t\t\tif (tmp != NULL) {\n+\t\t\t\trte_rib6_get_depth(tmp, &tmp_depth);\n+\t\t\t\tparent_depth = RTE_MAX(tmp_depth, 24);\n+\t\t\t}\n+\t\t\tdepth_diff = RTE_ALIGN_CEIL(depth, 8) -\n+\t\t\t\tRTE_ALIGN_CEIL(parent_depth, 8);\n+\t\t\tdepth_diff = depth_diff >> 3;\n+\t\t}\n+\t}\n+\tnode = rte_rib6_lookup_exact(rib, ip_masked, depth);\n+\tswitch (op) {\n+\tcase RTE_FIB6_ADD:\n+\t\tif (node != NULL) {\n+\t\t\trte_rib6_get_nh(node, &node_nh);\n+\t\t\tif (node_nh == next_hop)\n+\t\t\t\treturn 0;\n+\t\t\tret = modify_dp(dp, rib, ip_masked, depth, next_hop);\n+\t\t\tif (ret == 0)\n+\t\t\t\trte_rib6_set_nh(node, next_hop);\n+\t\t\treturn 0;\n+\t\t}\n+\n+\t\tif ((depth > 24) && (dp->rsvd_tbl8s >=\n+\t\t\t\tdp->number_tbl8s - depth_diff))\n+\t\t\treturn -ENOSPC;\n+\n+\t\tnode = rte_rib6_insert(rib, ip_masked, depth);\n+\t\tif (node == NULL)\n+\t\t\treturn -rte_errno;\n+\t\trte_rib6_set_nh(node, next_hop);\n+\t\tparent = rte_rib6_lookup_parent(node);\n+\t\tif (parent != NULL) {\n+\t\t\trte_rib6_get_nh(parent, &par_nh);\n+\t\t\tif (par_nh == next_hop)\n+\t\t\t\treturn 0;\n+\t\t}\n+\t\tret = modify_dp(dp, rib, ip_masked, depth, next_hop);\n+\t\tif (ret != 0) {\n+\t\t\trte_rib6_remove(rib, ip_masked, depth);\n+\t\t\treturn ret;\n+\t\t}\n+\n+\t\tdp->rsvd_tbl8s += depth_diff;\n+\t\treturn 0;\n+\tcase RTE_FIB6_DEL:\n+\t\tif (node == NULL)\n+\t\t\treturn -ENOENT;\n+\n+\t\tparent = rte_rib6_lookup_parent(node);\n+\t\tif (parent != NULL) {\n+\t\t\trte_rib6_get_nh(parent, &par_nh);\n+\t\t\trte_rib6_get_nh(node, &node_nh);\n+\t\t\tif (par_nh != node_nh)\n+\t\t\t\tret = modify_dp(dp, rib, ip_masked, depth,\n+\t\t\t\t\tpar_nh);\n+\t\t} else\n+\t\t\tret = modify_dp(dp, rib, ip_masked, depth, dp->def_nh);\n+\n+\t\tif (ret != 0)\n+\t\t\treturn ret;\n+\t\trte_rib6_remove(rib, ip, depth);\n+\n+\t\tdp->rsvd_tbl8s -= depth_diff;\n+\t\treturn 0;\n+\tdefault:\n+\t\tbreak;\n+\t}\n+\treturn -EINVAL;\n+}\n+\n+void *\n+trie_create(const char *name, int socket_id,\n+\tstruct rte_fib6_conf *conf)\n+{\n+\tchar mem_name[TRIE_NAMESIZE];\n+\tstruct rte_trie_tbl *dp = NULL;\n+\tuint64_t\tdef_nh;\n+\tuint32_t\tnum_tbl8;\n+\tenum rte_fib_trie_nh_sz\tnh_sz;\n+\n+\tif ((name == NULL) || (conf == NULL) ||\n+\t\t\t(conf->trie.nh_sz < RTE_FIB6_TRIE_2B) ||\n+\t\t\t(conf->trie.nh_sz > RTE_FIB6_TRIE_8B) ||\n+\t\t\t(conf->trie.num_tbl8 >\n+\t\t\tget_max_nh(conf->trie.nh_sz)) ||\n+\t\t\t(conf->trie.num_tbl8 == 0) ||\n+\t\t\t(conf->default_nh >\n+\t\t\tget_max_nh(conf->trie.nh_sz))) {\n+\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\tdef_nh = conf->default_nh;\n+\tnh_sz = conf->trie.nh_sz;\n+\tnum_tbl8 = conf->trie.num_tbl8;\n+\n+\tsnprintf(mem_name, sizeof(mem_name), \"DP_%s\", name);\n+\tdp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) +\n+\t\tTRIE_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,\n+\t\tsocket_id);\n+\tif (dp == NULL) {\n+\t\trte_errno = ENOMEM;\n+\t\treturn dp;\n+\t}\n+\n+\twrite_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);\n+\n+\tsnprintf(mem_name, sizeof(mem_name), \"TBL8_%p\", dp);\n+\tdp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT *\n+\t\t\t(1ll << nh_sz) * (num_tbl8 + 1),\n+\t\t\tRTE_CACHE_LINE_SIZE, socket_id);\n+\tif (dp->tbl8 == NULL) {\n+\t\trte_errno = ENOMEM;\n+\t\trte_free(dp);\n+\t\treturn NULL;\n+\t}\n+\tdp->def_nh = def_nh;\n+\tdp->nh_sz = nh_sz;\n+\tdp->number_tbl8s = num_tbl8;\n+\n+\tsnprintf(mem_name, sizeof(mem_name), \"TBL8_idxes_%p\", dp);\n+\tdp->tbl8_pool = rte_zmalloc_socket(mem_name,\n+\t\t\tsizeof(uint32_t) * dp->number_tbl8s,\n+\t\t\tRTE_CACHE_LINE_SIZE, socket_id);\n+\tif (dp->tbl8_pool == NULL) {\n+\t\trte_errno = ENOMEM;\n+\t\trte_free(dp->tbl8);\n+\t\trte_free(dp);\n+\t\treturn NULL;\n+\t}\n+\n+\ttbl8_pool_init(dp);\n+\n+\treturn dp;\n+}\n+\n+void\n+trie_free(void *p)\n+{\n+\tstruct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;\n+\n+\trte_free(dp->tbl8_pool);\n+\trte_free(dp->tbl8);\n+\trte_free(dp);\n+}\n+\ndiff --git a/lib/librte_fib/trie.h b/lib/librte_fib/trie.h\nnew file mode 100644\nindex 0000000..7762fb9\n--- /dev/null\n+++ b/lib/librte_fib/trie.h\n@@ -0,0 +1,37 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#ifndef _TRIE_H_\n+#define _TRIE_H_\n+\n+/**\n+ * @file\n+ * RTE IPv6 Longest Prefix Match (LPM)\n+ */\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+void *\n+trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf);\n+\n+void\n+trie_free(void *p);\n+\n+rte_fib6_lookup_fn_t\n+rte_trie_get_lookup_fn(struct rte_fib6_conf *fib_conf);\n+\n+int\n+trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],\n+\tuint8_t depth, uint64_t next_hop, int op);\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+#endif /* _TRIE_H_ */\n+\n",
    "prefixes": [
        "v6",
        "08/12"
    ]
}