From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 11464A2EEB for ; Wed, 11 Sep 2019 19:11:35 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 2956F1E918; Wed, 11 Sep 2019 19:10:36 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id A1CD91E8F5 for ; Wed, 11 Sep 2019 19:10:28 +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 fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 11 Sep 2019 10:10:27 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.64,492,1559545200"; d="scan'208";a="196952253" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga002.jf.intel.com with ESMTP; 11 Sep 2019 10:10:26 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com Date: Wed, 11 Sep 2019 18:09:47 +0100 Message-Id: <287966d228df112528c529e0db76f22bd2d64549.1568221364.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> Subject: [dpdk-dev] [PATCH v5 07/12] fib: add DIR24-8 dataplane algorithm X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 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" Add fib implementation for DIR24_8 algorithm for ipv4. Implementation is similar to current LPM implementation but has few enhancements: faster control plabe operations more bits for userdata in table entries configurable userdata size Signed-off-by: Vladimir Medvedkin --- lib/librte_fib/Makefile | 2 +- lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++++++++++++ lib/librte_fib/dir24_8.h | 36 +++ lib/librte_fib/meson.build | 2 +- lib/librte_fib/rte_fib.c | 14 + lib/librte_fib/rte_fib.h | 17 +- 6 files changed, 805 insertions(+), 3 deletions(-) create mode 100644 lib/librte_fib/dir24_8.c create mode 100644 lib/librte_fib/dir24_8.h diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile index 0bdf55b..67fde9a 100644 --- a/lib/librte_fib/Makefile +++ b/lib/librte_fib/Makefile @@ -17,7 +17,7 @@ EXPORT_MAP := rte_fib_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h diff --git a/lib/librte_fib/dir24_8.c b/lib/librte_fib/dir24_8.c new file mode 100644 index 0000000..c9dce3c --- /dev/null +++ b/lib/librte_fib/dir24_8.c @@ -0,0 +1,737 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include +#include +#include "dir24_8.h" + +#define DIR24_8_NAMESIZE 64 + +#define DIR24_8_TBL24_NUM_ENT (1 << 24) +#define DIR24_8_TBL8_GRP_NUM_ENT 256U +#define DIR24_8_EXT_ENT 1 +#define DIR24_8_TBL24_MASK 0xffffff00 + +#define BITMAP_SLAB_BIT_SIZE_LOG2 6 +#define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2) +#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) + +struct dir24_8_tbl { + uint32_t number_tbl8s; /**< Total number of tbl8s */ + uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ + uint32_t cur_tbl8s; /**< Current number of tbl8s */ + enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */ + uint64_t def_nh; /**< Default next hop */ + uint64_t *tbl8; /**< tbl8 table. */ + uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/ + /* tbl24 table. */ + __extension__ uint64_t tbl24[0] __rte_cache_aligned; +}; + +#define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y))) + +enum lookup_type { + MACRO, + INLINE, + UNI +}; +enum lookup_type test_lookup = MACRO; + +static inline void * +get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) +{ + return (void *)&((uint8_t *)dp->tbl24)[(ip & + DIR24_8_TBL24_MASK) >> (8 - nh_sz)]; +} + +static inline uint8_t +bits_in_nh(uint8_t nh_sz) +{ + return 8 * (1 << nh_sz); +} + +static inline uint64_t +get_max_nh(uint8_t nh_sz) +{ + return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); +} + +static inline uint32_t +get_tbl24_idx(uint32_t ip) +{ + return ip >> 8; +} + +static inline uint32_t +get_tbl8_idx(uint32_t res, uint32_t ip) +{ + return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip; +} + +static inline uint64_t +lookup_msk(uint8_t nh_sz) +{ + return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; +} + +static inline uint8_t +get_psd_idx(uint32_t val, uint8_t nh_sz) +{ + return val & ((1 << (3 - nh_sz)) - 1); +} + +static inline uint32_t +get_tbl_idx(uint32_t val, uint8_t nh_sz) +{ + return val >> (3 - nh_sz); +} + +static inline uint64_t +get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) +{ + return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >> + (get_psd_idx(get_tbl24_idx(ip), nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline uint64_t +get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz) +{ + return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >> + (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline int +is_entry_extended(uint64_t ent) +{ + return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT; +} + +#define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \ +static void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \ + uint64_t *next_hops, const unsigned int n) \ +{ \ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \ + uint64_t tmp; \ + uint32_t i; \ + uint32_t prefetch_offset = \ + RTE_MIN((unsigned int)bulk_prefetch, n); \ + \ + for (i = 0; i < prefetch_offset; i++) \ + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \ + for (i = 0; i < (n - prefetch_offset); i++) { \ + rte_prefetch0(get_tbl24_p(dp, \ + ips[i + prefetch_offset], nh_sz)); \ + tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ + if (unlikely(is_entry_extended(tmp))) \ + tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ + ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ + next_hops[i] = tmp >> 1; \ + } \ + for (; i < n; i++) { \ + tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ + if (unlikely(is_entry_extended(tmp))) \ + tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ + ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ + next_hops[i] = tmp >> 1; \ + } \ +} \ + +LOOKUP_FUNC(1b, uint8_t, 5, 0) +LOOKUP_FUNC(2b, uint16_t, 6, 1) +LOOKUP_FUNC(4b, uint32_t, 15, 2) +LOOKUP_FUNC(8b, uint64_t, 12, 3) + +static inline void +dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n, uint8_t nh_sz) +{ + uint64_t tmp; + uint32_t i; + uint32_t prefetch_offset = RTE_MIN(15U, n); + + for (i = 0; i < prefetch_offset; i++) + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); + for (i = 0; i < (n - prefetch_offset); i++) { + rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], + nh_sz)); + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } + for (; i < n; i++) { + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } +} + +static void +dir24_8_lookup_bulk_0(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 0); +} + +static void +dir24_8_lookup_bulk_1(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 1); +} + +static void +dir24_8_lookup_bulk_2(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 2); +} + +static void +dir24_8_lookup_bulk_3(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 3); +} + +static void +dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + uint64_t tmp; + uint32_t i; + uint32_t prefetch_offset = RTE_MIN(15U, n); + uint8_t nh_sz = dp->nh_sz; + + for (i = 0; i < prefetch_offset; i++) + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); + for (i = 0; i < (n - prefetch_offset); i++) { + rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], + nh_sz)); + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } + for (; i < n; i++) { + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } +} + +rte_fib_lookup_fn_t +dir24_8_get_lookup_fn(struct rte_fib_conf *fib_conf) +{ + enum rte_fib_dir24_8_nh_sz nh_sz = fib_conf->dir24_8.nh_sz; + + if (test_lookup == MACRO) { + switch (nh_sz) { + case RTE_FIB_DIR24_8_1B: + return dir24_8_lookup_bulk_1b; + case RTE_FIB_DIR24_8_2B: + return dir24_8_lookup_bulk_2b; + case RTE_FIB_DIR24_8_4B: + return dir24_8_lookup_bulk_4b; + case RTE_FIB_DIR24_8_8B: + return dir24_8_lookup_bulk_8b; + } + } else if (test_lookup == INLINE) { + switch (nh_sz) { + case RTE_FIB_DIR24_8_1B: + return dir24_8_lookup_bulk_0; + case RTE_FIB_DIR24_8_2B: + return dir24_8_lookup_bulk_1; + case RTE_FIB_DIR24_8_4B: + return dir24_8_lookup_bulk_2; + case RTE_FIB_DIR24_8_8B: + return dir24_8_lookup_bulk_3; + } + } else + return dir24_8_lookup_bulk_uni; + return NULL; +} + +static void +write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n) +{ + int i; + uint8_t *ptr8 = (uint8_t *)ptr; + uint16_t *ptr16 = (uint16_t *)ptr; + uint32_t *ptr32 = (uint32_t *)ptr; + uint64_t *ptr64 = (uint64_t *)ptr; + + switch (size) { + case RTE_FIB_DIR24_8_1B: + for (i = 0; i < n; i++) + ptr8[i] = (uint8_t)val; + break; + case RTE_FIB_DIR24_8_2B: + for (i = 0; i < n; i++) + ptr16[i] = (uint16_t)val; + break; + case RTE_FIB_DIR24_8_4B: + for (i = 0; i < n; i++) + ptr32[i] = (uint32_t)val; + break; + case RTE_FIB_DIR24_8_8B: + for (i = 0; i < n; i++) + ptr64[i] = (uint64_t)val; + break; + } +} + +static int +tbl8_get_idx(struct dir24_8_tbl *dp) +{ + uint32_t i; + int bit_idx; + + for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) && + (dp->tbl8_idxes[i] == UINT64_MAX); i++) + ; + if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) { + bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]); + dp->tbl8_idxes[i] |= (1ULL << bit_idx); + return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx; + } + return -ENOSPC; +} + +static inline void +tbl8_free_idx(struct dir24_8_tbl *dp, int idx) +{ + dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &= + ~(1ULL << (idx & BITMAP_SLAB_BITMASK)); +} + +static int +tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh) +{ + int64_t tbl8_idx; + uint8_t *tbl8_ptr; + + tbl8_idx = tbl8_get_idx(dp); + if (tbl8_idx < 0) + return tbl8_idx; + tbl8_ptr = (uint8_t *)dp->tbl8 + + ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << + dp->nh_sz); + /*Init tbl8 entries with nexthop from tbl24*/ + write_to_fib((void *)tbl8_ptr, nh| + DIR24_8_EXT_ENT, dp->nh_sz, + DIR24_8_TBL8_GRP_NUM_ENT); + dp->cur_tbl8s++; + return tbl8_idx; +} + +static void +tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx) +{ + uint32_t i; + uint64_t nh; + uint8_t *ptr8; + uint16_t *ptr16; + uint32_t *ptr32; + uint64_t *ptr64; + + switch (dp->nh_sz) { + case RTE_FIB_DIR24_8_1B: + ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr8; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr8[i]) + return; + } + ((uint8_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr8[i] = 0; + break; + case RTE_FIB_DIR24_8_2B: + ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr16; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr16[i]) + return; + } + ((uint16_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr16[i] = 0; + break; + case RTE_FIB_DIR24_8_4B: + ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr32; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr32[i]) + return; + } + ((uint32_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr32[i] = 0; + break; + case RTE_FIB_DIR24_8_8B: + ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr64; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr64[i]) + return; + } + ((uint64_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr64[i] = 0; + break; + } + tbl8_free_idx(dp, tbl8_idx); + dp->cur_tbl8s--; +} + +static int +install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge, + uint64_t next_hop) +{ + uint64_t tbl24_tmp; + int tbl8_idx; + int tmp_tbl8_idx; + uint8_t *tbl8_ptr; + uint32_t len; + + len = ((ledge == 0) && (redge == 0)) ? 1 << 24 : + ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8; + + if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) { + if ((ROUNDUP(ledge, 24) - ledge) != 0) { + tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + /** + * Make sure there is space for two TBL8. + * This is necessary when installing range that + * needs tbl8 for ledge and redge. + */ + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + tmp_tbl8_idx = tbl8_get_idx(dp); + if (tbl8_idx < 0) + return -ENOSPC; + else if (tmp_tbl8_idx < 0) { + tbl8_free_idx(dp, tbl8_idx); + return -ENOSPC; + } + tbl8_free_idx(dp, tmp_tbl8_idx); + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, ledge, + dp->nh_sz), (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + + (ledge & ~DIR24_8_TBL24_MASK)) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, ROUNDUP(ledge, 24) - ledge); + tbl8_recycle(dp, ledge, tbl8_idx); + } + write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz), + next_hop << 1, dp->nh_sz, len); + if (redge & ~DIR24_8_TBL24_MASK) { + tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + if (tbl8_idx < 0) + return -ENOSPC; + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, redge, + dp->nh_sz), (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, redge & ~DIR24_8_TBL24_MASK); + tbl8_recycle(dp, redge, tbl8_idx); + } + } else if ((redge - ledge) != 0) { + tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + if (tbl8_idx < 0) + return -ENOSPC; + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz), + (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + + (ledge & ~DIR24_8_TBL24_MASK)) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, redge - ledge); + tbl8_recycle(dp, ledge, tbl8_idx); + } + return 0; +} + +static int +modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip, + uint8_t depth, uint64_t next_hop) +{ + struct rte_rib_node *tmp = NULL; + uint32_t ledge, redge, tmp_ip; + int ret; + uint8_t tmp_depth; + + ledge = ip; + do { + tmp = rte_rib_get_nxt(rib, ip, depth, tmp, + RTE_RIB_GET_NXT_COVER); + if (tmp != NULL) { + rte_rib_get_depth(tmp, &tmp_depth); + if (tmp_depth == depth) + continue; + rte_rib_get_ip(tmp, &tmp_ip); + redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth); + if (ledge == redge) { + ledge = redge + + (uint32_t)(1ULL << (32 - tmp_depth)); + continue; + } + ret = install_to_fib(dp, ledge, redge, + next_hop); + if (ret != 0) + return ret; + ledge = redge + + (uint32_t)(1ULL << (32 - tmp_depth)); + } else { + redge = ip + (uint32_t)(1ULL << (32 - depth)); + if (ledge == redge) + break; + ret = install_to_fib(dp, ledge, redge, + next_hop); + if (ret != 0) + return ret; + } + } while (tmp); + + return 0; +} + +int +dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, + uint64_t next_hop, int op) +{ + struct dir24_8_tbl *dp; + struct rte_rib *rib; + struct rte_rib_node *tmp = NULL; + struct rte_rib_node *node; + struct rte_rib_node *parent; + int ret = 0; + uint64_t par_nh, node_nh; + + if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH)) + return -EINVAL; + + dp = rte_fib_get_dp(fib); + rib = rte_fib_get_rib(fib); + RTE_ASSERT((dp != NULL) && (rib != NULL)); + + if (next_hop > get_max_nh(dp->nh_sz)) + return -EINVAL; + + ip &= rte_rib_depth_to_mask(depth); + + node = rte_rib_lookup_exact(rib, ip, depth); + switch (op) { + case RTE_FIB_ADD: + if (node != NULL) { + rte_rib_get_nh(node, &node_nh); + if (node_nh == next_hop) + return 0; + ret = modify_fib(dp, rib, ip, depth, next_hop); + if (ret == 0) + rte_rib_set_nh(node, next_hop); + return 0; + } + if (depth > 24) { + tmp = rte_rib_get_nxt(rib, ip, 24, NULL, + RTE_RIB_GET_NXT_COVER); + if ((tmp == NULL) && + (dp->rsvd_tbl8s >= dp->number_tbl8s)) + return -ENOSPC; + + } + node = rte_rib_insert(rib, ip, depth); + if (node == NULL) + return -rte_errno; + rte_rib_set_nh(node, next_hop); + parent = rte_rib_lookup_parent(node); + if (parent != NULL) { + rte_rib_get_nh(parent, &par_nh); + if (par_nh == next_hop) + return 0; + } + ret = modify_fib(dp, rib, ip, depth, next_hop); + if (ret != 0) { + rte_rib_remove(rib, ip, depth); + return ret; + } + if ((depth > 24) && (tmp == NULL)) + dp->rsvd_tbl8s++; + return 0; + case RTE_FIB_DEL: + if (node == NULL) + return -ENOENT; + + parent = rte_rib_lookup_parent(node); + if (parent != NULL) { + rte_rib_get_nh(parent, &par_nh); + rte_rib_get_nh(node, &node_nh); + if (par_nh != node_nh) + ret = modify_fib(dp, rib, ip, depth, par_nh); + } else + ret = modify_fib(dp, rib, ip, depth, dp->def_nh); + if (ret == 0) { + rte_rib_remove(rib, ip, depth); + if (depth > 24) { + tmp = rte_rib_get_nxt(rib, ip, 24, NULL, + RTE_RIB_GET_NXT_COVER); + if (tmp == NULL) + dp->rsvd_tbl8s--; + } + } + return ret; + default: + break; + } + return -EINVAL; +} + +void * +dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf) +{ + char mem_name[DIR24_8_NAMESIZE]; + struct dir24_8_tbl *dp; + uint64_t def_nh; + uint32_t num_tbl8; + enum rte_fib_dir24_8_nh_sz nh_sz; + + if ((name == NULL) || (fib_conf == NULL) || + (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) || + (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) || + (fib_conf->dir24_8.num_tbl8 > + get_max_nh(fib_conf->dir24_8.nh_sz)) || + (fib_conf->dir24_8.num_tbl8 == 0) || + (fib_conf->default_nh > + get_max_nh(fib_conf->dir24_8.nh_sz))) { + rte_errno = EINVAL; + return NULL; + } + + def_nh = fib_conf->default_nh; + nh_sz = fib_conf->dir24_8.nh_sz; + num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8, + BITMAP_SLAB_BIT_SIZE); + + snprintf(mem_name, sizeof(mem_name), "DP_%s", name); + dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) + + DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE, + socket_id); + if (dp == NULL) { + rte_errno = ENOMEM; + return NULL; + } + + /* Init table with default value */ + write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24); + + snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp); + uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) * + (num_tbl8 + 1); + dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz, + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8 == NULL) { + rte_errno = ENOMEM; + rte_free(dp); + return NULL; + } + dp->def_nh = def_nh; + dp->nh_sz = nh_sz; + dp->number_tbl8s = num_tbl8; + + snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp); + dp->tbl8_idxes = rte_zmalloc_socket(mem_name, + RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3, + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8_idxes == NULL) { + rte_errno = ENOMEM; + rte_free(dp->tbl8); + rte_free(dp); + return NULL; + } + + return dp; +} + +void +dir24_8_free(void *p) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + rte_free(dp->tbl8_idxes); + rte_free(dp->tbl8); + rte_free(dp); +} diff --git a/lib/librte_fib/dir24_8.h b/lib/librte_fib/dir24_8.h new file mode 100644 index 0000000..34ddb91 --- /dev/null +++ b/lib/librte_fib/dir24_8.h @@ -0,0 +1,36 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _DIR24_8_H_ +#define _DIR24_8_H_ + +/** + * @file + * DIR24_8 algorithm + */ + +#ifdef __cplusplus +extern "C" { +#endif + +void * +dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf); + +void +dir24_8_free(void *p); + +rte_fib_lookup_fn_t +dir24_8_get_lookup_fn(struct rte_fib_conf *conf); + +int +dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, + uint64_t next_hop, int op); + +#ifdef __cplusplus +} +#endif + +#endif /* _DIR24_8_H_ */ + diff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build index 32dfdec..c63cac8 100644 --- a/lib/librte_fib/meson.build +++ b/lib/librte_fib/meson.build @@ -3,6 +3,6 @@ # Copyright(c) 2019 Intel Corporation allow_experimental_apis = true -sources = files('rte_fib.c', 'rte_fib6.c') +sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c') headers = files('rte_fib.h', 'rte_fib6.h') deps += ['rib'] diff --git a/lib/librte_fib/rte_fib.c b/lib/librte_fib/rte_fib.c index 4d8a771..e090808 100644 --- a/lib/librte_fib/rte_fib.c +++ b/lib/librte_fib/rte_fib.c @@ -17,6 +17,8 @@ #include #include +#include "dir24_8.h" + TAILQ_HEAD(rte_fib_list, rte_tailq_entry); static struct rte_tailq_elem rte_fib_tailq = { .name = "RTE_FIB", @@ -92,12 +94,22 @@ static int init_dataplane(struct rte_fib *fib, __rte_unused int socket_id, struct rte_fib_conf *conf) { + char dp_name[sizeof(void *)]; + + snprintf(dp_name, sizeof(dp_name), "%p", fib); switch (conf->type) { case RTE_FIB_DUMMY: fib->dp = fib; fib->lookup = dummy_lookup; fib->modify = dummy_modify; return 0; + case RTE_FIB_DIR24_8: + fib->dp = dir24_8_create(dp_name, socket_id, conf); + if (fib->dp == NULL) + return -rte_errno; + fib->lookup = dir24_8_get_lookup_fn(conf); + fib->modify = dir24_8_modify; + return 0; default: return -EINVAL; } @@ -258,6 +270,8 @@ free_dataplane(struct rte_fib *fib) switch (fib->type) { case RTE_FIB_DUMMY: return; + case RTE_FIB_DIR24_8: + dir24_8_free(fib->dp); default: return; } diff --git a/lib/librte_fib/rte_fib.h b/lib/librte_fib/rte_fib.h index 096cc92..d06c5ef 100644 --- a/lib/librte_fib/rte_fib.h +++ b/lib/librte_fib/rte_fib.h @@ -15,6 +15,7 @@ #include struct rte_fib; +struct rte_rib; /** Maximum depth value possible for IPv4 FIB. */ #define RTE_FIB_MAXDEPTH 32 @@ -22,6 +23,7 @@ struct rte_fib; /** Type of FIB struct */ enum rte_fib_type { RTE_FIB_DUMMY, /**< RIB tree based FIB */ + RTE_FIB_DIR24_8, /**< DIR24_8 based FIB */ RTE_FIB_TYPE_MAX }; @@ -37,12 +39,26 @@ enum rte_fib_op { RTE_FIB_DEL, }; +/** Size of nexthop (1 << nh_sz) bits for DIR24_8 based FIB */ +enum rte_fib_dir24_8_nh_sz { + RTE_FIB_DIR24_8_1B, + RTE_FIB_DIR24_8_2B, + RTE_FIB_DIR24_8_4B, + RTE_FIB_DIR24_8_8B +}; + /** FIB configuration structure */ struct rte_fib_conf { enum rte_fib_type type; /**< Type of FIB struct */ /** Default value returned on lookup if there is no route */ uint64_t default_nh; int max_routes; + union { + struct { + enum rte_fib_dir24_8_nh_sz nh_sz; + uint32_t num_tbl8; + } dir24_8; + }; }; /** @@ -143,7 +159,6 @@ __rte_experimental int rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips, uint64_t *next_hops, int n); - /** * Get pointer to the dataplane specific struct * -- 2.7.4