From patchwork Tue Apr 6 19:50:41 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 90752 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id DA3B9A0546; Tue, 6 Apr 2021 21:50:55 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 4BFA8140F8E; Tue, 6 Apr 2021 21:50:52 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by mails.dpdk.org (Postfix) with ESMTP id BE74D140F8B for ; Tue, 6 Apr 2021 21:50:50 +0200 (CEST) IronPort-SDR: xkxpYWI2Jr9UcQ6hd196vSa4ST57eyEskuh/vwDjnzHf5HzupghuX+Wt0s/fikTr5/KcQ2T8YO H4OeoAxG2Ziw== X-IronPort-AV: E=McAfee;i="6000,8403,9946"; a="172619767" X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="172619767" Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Apr 2021 12:50:50 -0700 IronPort-SDR: IPvSzT5mevaqBPCeuvU2eIyvMFVBngC2JW4ceVoKs9UKMx3JsvZiXKVgzLH1sM4hdFNjE7A1Gx 7qP5yYR59gfA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="448740699" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga002.fm.intel.com with ESMTP; 06 Apr 2021 12:50:48 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, andrey.chilikin@intel.com, ray.kinsella@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Tue, 6 Apr 2021 20:50:41 +0100 Message-Id: <1617738643-258635-2-git-send-email-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> References: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> In-Reply-To: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v2 1/3] hash: add predictable RSS API 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" This patch adds predictable RSS API. It is based on the idea of searching partial Toeplitz hash collisions. Signed-off-by: Vladimir Medvedkin --- lib/librte_hash/meson.build | 3 +- lib/librte_hash/rte_thash.c | 96 ++++++++++++++++++++++++++++++ lib/librte_hash/rte_thash.h | 138 ++++++++++++++++++++++++++++++++++++++++++++ lib/librte_hash/version.map | 7 +++ 4 files changed, 243 insertions(+), 1 deletion(-) create mode 100644 lib/librte_hash/rte_thash.c diff --git a/lib/librte_hash/meson.build b/lib/librte_hash/meson.build index 242859f..3546014 100644 --- a/lib/librte_hash/meson.build +++ b/lib/librte_hash/meson.build @@ -8,6 +8,7 @@ headers = files('rte_fbk_hash.h', 'rte_thash.h') indirect_headers += files('rte_crc_arm64.h') -sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c') +sources = files('rte_cuckoo_hash.c', 'rte_fbk_hash.c', 'rte_thash.c') +deps += ['net'] deps += ['ring'] deps += ['rcu'] diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c new file mode 100644 index 0000000..79e8724 --- /dev/null +++ b/lib/librte_hash/rte_thash.c @@ -0,0 +1,96 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2021 Intel Corporation + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#define THASH_NAME_LEN 64 + +struct thash_lfsr { + uint32_t ref_cnt; + uint32_t poly; + /**< polynomial associated with the lfsr */ + uint32_t rev_poly; + /**< polynomial to generate the sequence in reverse direction */ + uint32_t state; + /**< current state of the lfsr */ + uint32_t rev_state; + /**< current state of the lfsr for reverse direction */ + uint32_t deg; /**< polynomial degree*/ + uint32_t bits_cnt; /**< number of bits generated by lfsr*/ +}; + +struct rte_thash_subtuple_helper { + char name[THASH_NAME_LEN]; /** < Name of subtuple configuration */ + LIST_ENTRY(rte_thash_subtuple_helper) next; + struct thash_lfsr *lfsr; + uint32_t offset; /** < Offset in bits of the subtuple */ + uint32_t len; /** < Length in bits of the subtuple */ + uint32_t lsb_msk; /** < (1 << reta_sz_log) - 1 */ + __extension__ uint32_t compl_table[0] __rte_cache_aligned; + /** < Complimentary table */ +}; + +struct rte_thash_ctx { + char name[THASH_NAME_LEN]; + LIST_HEAD(, rte_thash_subtuple_helper) head; + uint32_t key_len; /** < Length of the NIC RSS hash key */ + uint32_t reta_sz_log; /** < size of the RSS ReTa in bits */ + uint32_t subtuples_nb; /** < number of subtuples */ + uint32_t flags; + uint8_t hash_key[0]; +}; + +struct rte_thash_ctx * +rte_thash_init_ctx(const char *name __rte_unused, + uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused, + uint8_t *key __rte_unused, uint32_t flags __rte_unused) +{ + return NULL; +} + +struct rte_thash_ctx * +rte_thash_find_existing(const char *name __rte_unused) +{ + return NULL; +} + +void +rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused) +{ +} + +int +rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused, + const char *name __rte_unused, uint32_t len __rte_unused, + uint32_t offset __rte_unused) +{ + return 0; +} + +struct rte_thash_subtuple_helper * +rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused, + const char *name __rte_unused) +{ + return NULL; +} + +uint32_t +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h __rte_unused, + uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused) +{ + return 0; +} + +const uint8_t * +rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused) +{ + return NULL; +} diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h index 061efa2..38a641b 100644 --- a/lib/librte_hash/rte_thash.h +++ b/lib/librte_hash/rte_thash.h @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: BSD-3-Clause * Copyright(c) 2015-2019 Vladimir Medvedkin + * Copyright(c) 2021 Intel Corporation */ #ifndef _RTE_THASH_H @@ -222,6 +223,143 @@ rte_softrss_be(uint32_t *input_tuple, uint32_t input_len, return ret; } +/** + * LFSR will ignore if generated m-sequence has more than 2^n -1 bits + */ +#define RTE_THASH_IGNORE_PERIOD_OVERFLOW 0x1 +/** + * Generate minimal required bit (equal to ReTa LSB) sequence into + * the hash_key + */ +#define RTE_THASH_MINIMAL_SEQ 0x2 + +/** @internal thash context structure. */ +struct rte_thash_ctx; +/** @internal thash helper structure. */ +struct rte_thash_subtuple_helper; + +/** + * Create a new thash context. + * + * @param name + * context name + * @param key_len + * length of the toeplitz hash key + * @param reta_sz + * logarithm of the NIC's Redirection Table (ReTa) size, + * i.e. number of the LSBs if the hash used to determine + * the reta entry. + * @param key + * pointer to the key used to init an internal key state. + * Could be NULL, in this case internal key will be inited with random. + * @param flags + * supported flags are: + * RTE_THASH_IGNORE_PERIOD_OVERFLOW + * RTE_THASH_MINIMAL_SEQ + * @return + * A pointer to the created context on success + * NULL otherwise + */ +__rte_experimental +struct rte_thash_ctx * +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz, + uint8_t *key, uint32_t flags); + +/** + * Find an existing thash context and return a pointer to it. + * + * @param name + * Name of the thash context + * @return + * Pointer to the thash context or NULL if it was not found with rte_errno + * set appropriately. Possible rte_errno values include: + * - ENOENT - required entry not available to return. + */ +__rte_experimental +struct rte_thash_ctx * +rte_thash_find_existing(const char *name); + +/** + * Free a thash context object + * + * @param ctx + * thash context + * @return + * None + */ +__rte_experimental +void +rte_thash_free_ctx(struct rte_thash_ctx *ctx); + +/** + * Add a special properties to the toeplitz hash key inside a thash context. + * Creates an internal helper struct which has a complimentary table + * to calculate toeplitz hash collisions. + * + * @param ctx + * thash context + * @param name + * name of the helper + * @param len + * length in bits of the target subtuple + * @param offset + * offset in bits of the subtuple + * @return + * 0 on success + * negative on error + */ +__rte_experimental +int +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len, + uint32_t offset); + +/** + * Find a helper in the context by the given name + * + * @param ctx + * thash context + * @param name + * name of the helper + * @return + * Pointer to the thash helper or NULL if it was not found. + */ +__rte_experimental +struct rte_thash_subtuple_helper * +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name); + +/** + * Get a complimentary value for the subtuple to produce a + * partial toeplitz hash collision. It muxt be XOR'ed with the + * subtuple to produce the hash value with the desired hash LSB's + * + * @param h + * Pointer to the helper struct + * @param hash + * toeplitz hash value calculated for the given tuple + * @param desired_hash + * desired hash value to find a collision for + * @return + * A complimentary value which must be xored with the corresponding subtuple + */ +__rte_experimental +uint32_t +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h, + uint32_t hash, uint32_t desired_hash); + +/** + * Get a pointer to the toeplitz hash contained in the context. + * It changes after each addition of a helper. It should be installed to + * the NIC. + * + * @param ctx + * thash context + * @return + * A pointer to the toeplitz hash key + */ +__rte_experimental +const uint8_t * +rte_thash_get_key(struct rte_thash_ctx *ctx); + #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map index c6d7308..93cb230 100644 --- a/lib/librte_hash/version.map +++ b/lib/librte_hash/version.map @@ -37,4 +37,11 @@ EXPERIMENTAL { rte_hash_lookup_with_hash_bulk_data; rte_hash_max_key_id; rte_hash_rcu_qsbr_add; + rte_thash_add_helper; + rte_thash_find_existing; + rte_thash_free_ctx; + rte_thash_get_compliment; + rte_thash_get_helper; + rte_thash_get_key; + rte_thash_init_ctx; }; From patchwork Tue Apr 6 19:50:42 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 90753 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 47A07A0546; Tue, 6 Apr 2021 21:51:02 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 861EF140FA4; Tue, 6 Apr 2021 21:50:56 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by mails.dpdk.org (Postfix) with ESMTP id BC479140FA4 for ; Tue, 6 Apr 2021 21:50:54 +0200 (CEST) IronPort-SDR: 5kpyAKJojCd//HI5y5rhhYvASN8IPX401q5uDXCBOcwZKh0iNFLa8oOQ7HnR5VDw+2f7YtX64g homEHGv09EDg== X-IronPort-AV: E=McAfee;i="6000,8403,9946"; a="172619776" X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="172619776" Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Apr 2021 12:50:54 -0700 IronPort-SDR: JLKyr6lQSg7abrhYyzqpiyAc9C44n2zkdEPtPvb9lTMG+SK3KXPxxlXcxWCMZ8bL8YOxmbrGs2 b1oVb2NJWdWQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="448740712" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga002.fm.intel.com with ESMTP; 06 Apr 2021 12:50:50 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, andrey.chilikin@intel.com, ray.kinsella@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Tue, 6 Apr 2021 20:50:42 +0100 Message-Id: <1617738643-258635-3-git-send-email-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> References: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> In-Reply-To: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v2 2/3] hash: add predictable RSS implementation 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" This patch implements predictable RSS functionality. Signed-off-by: Vladimir Medvedkin Acked-by: Konstantin Ananyev --- lib/librte_hash/rte_thash.c | 577 ++++++++++++++++++++++++++++++++++++++++++-- lib/librte_hash/rte_thash.h | 42 ++++ lib/librte_hash/version.map | 1 + 3 files changed, 602 insertions(+), 18 deletions(-) diff --git a/lib/librte_hash/rte_thash.c b/lib/librte_hash/rte_thash.c index 79e8724..cc60ada 100644 --- a/lib/librte_hash/rte_thash.c +++ b/lib/librte_hash/rte_thash.c @@ -12,6 +12,45 @@ #include #define THASH_NAME_LEN 64 +#define TOEPLITZ_HASH_LEN 32 + +#define RETA_SZ_MIN 2U +#define RETA_SZ_MAX 16U +#define RETA_SZ_IN_RANGE(reta_sz) ((reta_sz >= RETA_SZ_MIN) && \ + (reta_sz <= RETA_SZ_MAX)) + +TAILQ_HEAD(rte_thash_list, rte_tailq_entry); +static struct rte_tailq_elem rte_thash_tailq = { + .name = "RTE_THASH", +}; +EAL_REGISTER_TAILQ(rte_thash_tailq) + +/** + * Table of some irreducible polinomials over GF(2). + * For lfsr they are reperesented in BE bit order, and + * x^0 is masked out. + * For example, poly x^5 + x^2 + 1 will be represented + * as (101001b & 11111b) = 01001b = 0x9 + */ +static const uint32_t irreducible_poly_table[][4] = { + {0, 0, 0, 0}, /** < degree 0 */ + {1, 1, 1, 1}, /** < degree 1 */ + {0x3, 0x3, 0x3, 0x3}, /** < degree 2 and so on... */ + {0x5, 0x3, 0x5, 0x3}, + {0x9, 0x3, 0x9, 0x3}, + {0x9, 0x1b, 0xf, 0x5}, + {0x21, 0x33, 0x1b, 0x2d}, + {0x41, 0x11, 0x71, 0x9}, + {0x71, 0xa9, 0xf5, 0x8d}, + {0x21, 0xd1, 0x69, 0x1d9}, + {0x81, 0x2c1, 0x3b1, 0x185}, + {0x201, 0x541, 0x341, 0x461}, + {0x941, 0x609, 0xe19, 0x45d}, + {0x1601, 0x1f51, 0x1171, 0x359}, + {0x2141, 0x2111, 0x2db1, 0x2109}, + {0x4001, 0x801, 0x101, 0x7301}, + {0x7781, 0xa011, 0x4211, 0x86d9}, +}; struct thash_lfsr { uint32_t ref_cnt; @@ -31,8 +70,10 @@ struct rte_thash_subtuple_helper { char name[THASH_NAME_LEN]; /** < Name of subtuple configuration */ LIST_ENTRY(rte_thash_subtuple_helper) next; struct thash_lfsr *lfsr; - uint32_t offset; /** < Offset in bits of the subtuple */ - uint32_t len; /** < Length in bits of the subtuple */ + uint32_t offset; /** < Offset of the m-sequence */ + uint32_t len; /** < Length of the m-sequence */ + uint32_t tuple_offset; /** < Offset in bits of the subtuple */ + uint32_t tuple_len; /** < Length in bits of the subtuple */ uint32_t lsb_msk; /** < (1 << reta_sz_log) - 1 */ __extension__ uint32_t compl_table[0] __rte_cache_aligned; /** < Complimentary table */ @@ -48,49 +89,549 @@ struct rte_thash_ctx { uint8_t hash_key[0]; }; +static inline uint32_t +get_bit_lfsr(struct thash_lfsr *lfsr) +{ + uint32_t bit, ret; + + /* + * masking the TAP bits defined by the polynomial and + * calculating parity + */ + bit = __builtin_popcount(lfsr->state & lfsr->poly) & 0x1; + ret = lfsr->state & 0x1; + lfsr->state = ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) & + ((1 << lfsr->deg) - 1); + + lfsr->bits_cnt++; + return ret; +} + +static inline uint32_t +get_rev_bit_lfsr(struct thash_lfsr *lfsr) +{ + uint32_t bit, ret; + + bit = __builtin_popcount(lfsr->rev_state & lfsr->rev_poly) & 0x1; + ret = lfsr->rev_state & (1 << (lfsr->deg - 1)); + lfsr->rev_state = ((lfsr->rev_state << 1) | bit) & + ((1 << lfsr->deg) - 1); + + lfsr->bits_cnt++; + return ret; +} + +static inline uint32_t +thash_get_rand_poly(uint32_t poly_degree) +{ + return irreducible_poly_table[poly_degree][rte_rand() % + RTE_DIM(irreducible_poly_table[poly_degree])]; +} + +static struct thash_lfsr * +alloc_lfsr(struct rte_thash_ctx *ctx) +{ + struct thash_lfsr *lfsr; + uint32_t i; + + if (ctx == NULL) + return NULL; + + lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0); + if (lfsr == NULL) + return NULL; + + lfsr->deg = ctx->reta_sz_log; + lfsr->poly = thash_get_rand_poly(lfsr->deg); + do { + lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1); + } while (lfsr->state == 0); + /* init reverse order polynomial */ + lfsr->rev_poly = (lfsr->poly >> 1) | (1 << (lfsr->deg - 1)); + /* init proper rev_state*/ + lfsr->rev_state = lfsr->state; + for (i = 0; i <= lfsr->deg; i++) + get_rev_bit_lfsr(lfsr); + + /* clear bits_cnt after rev_state was inited */ + lfsr->bits_cnt = 0; + lfsr->ref_cnt = 1; + + return lfsr; +} + +static void +attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr *lfsr) +{ + lfsr->ref_cnt++; + h->lfsr = lfsr; +} + +static void +free_lfsr(struct thash_lfsr *lfsr) +{ + lfsr->ref_cnt--; + if (lfsr->ref_cnt == 0) + rte_free(lfsr); +} + struct rte_thash_ctx * -rte_thash_init_ctx(const char *name __rte_unused, - uint32_t key_len __rte_unused, uint32_t reta_sz __rte_unused, - uint8_t *key __rte_unused, uint32_t flags __rte_unused) +rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz, + uint8_t *key, uint32_t flags) { + struct rte_thash_ctx *ctx; + struct rte_tailq_entry *te; + struct rte_thash_list *thash_list; + uint32_t i; + if ((name == NULL) || (key_len == 0) || !RETA_SZ_IN_RANGE(reta_sz)) { + rte_errno = EINVAL; + return NULL; + } + + thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list); + + rte_mcfg_tailq_write_lock(); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, thash_list, next) { + ctx = (struct rte_thash_ctx *)te->data; + if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0) + break; + } + ctx = NULL; + if (te != NULL) { + rte_errno = EEXIST; + goto exit; + } + + /* allocate tailq entry */ + te = rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, + "Can not allocate tailq entry for thash context %s\n", + name); + rte_errno = ENOMEM; + goto exit; + } + + ctx = rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0); + if (ctx == NULL) { + RTE_LOG(ERR, HASH, "thash ctx %s memory allocation failed\n", + name); + rte_errno = ENOMEM; + goto free_te; + } + + rte_strlcpy(ctx->name, name, sizeof(ctx->name)); + ctx->key_len = key_len; + ctx->reta_sz_log = reta_sz; + LIST_INIT(&ctx->head); + ctx->flags = flags; + + if (key) + rte_memcpy(ctx->hash_key, key, key_len); + else { + for (i = 0; i < key_len; i++) + ctx->hash_key[i] = rte_rand(); + } + + te->data = (void *)ctx; + TAILQ_INSERT_TAIL(thash_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return ctx; +free_te: + rte_free(te); +exit: + rte_mcfg_tailq_write_unlock(); return NULL; } struct rte_thash_ctx * -rte_thash_find_existing(const char *name __rte_unused) +rte_thash_find_existing(const char *name) { - return NULL; + struct rte_thash_ctx *ctx; + struct rte_tailq_entry *te; + struct rte_thash_list *thash_list; + + thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, thash_list, next) { + ctx = (struct rte_thash_ctx *)te->data; + if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0) + break; + } + + rte_mcfg_tailq_read_unlock(); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + + return ctx; } void -rte_thash_free_ctx(struct rte_thash_ctx *ctx __rte_unused) +rte_thash_free_ctx(struct rte_thash_ctx *ctx) { + struct rte_tailq_entry *te; + struct rte_thash_list *thash_list; + struct rte_thash_subtuple_helper *ent, *tmp; + + if (ctx == NULL) + return; + + thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list); + rte_mcfg_tailq_write_lock(); + TAILQ_FOREACH(te, thash_list, next) { + if (te->data == (void *)ctx) + break; + } + + if (te != NULL) + TAILQ_REMOVE(thash_list, te, next); + + rte_mcfg_tailq_write_unlock(); + ent = LIST_FIRST(&(ctx->head)); + while (ent) { + free_lfsr(ent->lfsr); + tmp = ent; + ent = LIST_NEXT(ent, next); + LIST_REMOVE(tmp, next); + rte_free(tmp); + } + + rte_free(ctx); + rte_free(te); +} + +static inline void +set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) +{ + uint32_t byte_idx = pos >> 3; + uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1)); + uint8_t tmp; + + tmp = ptr[byte_idx]; + tmp &= ~(1 << bit_idx); + tmp |= bit << bit_idx; + ptr[byte_idx] = tmp; +} + +/** + * writes m-sequence to the hash_key for range [start, end] + * (i.e. including start and end positions) + */ +static int +generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr, + uint32_t start, uint32_t end) +{ + uint32_t i; + uint32_t req_bits = (start < end) ? (end - start) : (start - end); + req_bits++; /* due to incuding end */ + + /* check if lfsr overflow period of the m-sequence */ + if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) && + ((ctx->flags & RTE_THASH_IGNORE_PERIOD_OVERFLOW) != + RTE_THASH_IGNORE_PERIOD_OVERFLOW)) + return -ENOSPC; + + if (start < end) { + /* original direction (from left to right)*/ + for (i = start; i <= end; i++) + set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i); + + } else { + /* reverse direction (from right to left) */ + for (i = end; i >= start; i--) + set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i); + } + + return 0; +} + +static inline uint32_t +get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset) +{ + uint32_t *tmp, val; + + tmp = (uint32_t *)(&ctx->hash_key[offset >> 3]); + val = rte_be_to_cpu_32(*tmp); + val >>= (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) + + ctx->reta_sz_log)); + + return val & ((1 << ctx->reta_sz_log) - 1); +} + +static inline void +generate_compliment_table(struct rte_thash_ctx *ctx, + struct rte_thash_subtuple_helper *h) +{ + int i, j, k; + uint32_t val; + uint32_t start; + + start = h->offset + h->len - (2 * ctx->reta_sz_log - 1); + + for (i = 1; i < (1 << ctx->reta_sz_log); i++) { + val = 0; + for (j = i; j; j &= (j - 1)) { + k = rte_bsf32(j); + val ^= get_subvalue(ctx, start - k + + ctx->reta_sz_log - 1); + } + h->compl_table[val] = i; + } +} + +static inline int +insert_before(struct rte_thash_ctx *ctx, + struct rte_thash_subtuple_helper *ent, + struct rte_thash_subtuple_helper *cur_ent, + struct rte_thash_subtuple_helper *next_ent, + uint32_t start, uint32_t end, uint32_t range_end) +{ + int ret; + + if (end < cur_ent->offset) { + ent->lfsr = alloc_lfsr(ctx); + if (ent->lfsr == NULL) { + rte_free(ent); + return -ENOMEM; + } + /* generate nonoverlapping range [start, end) */ + ret = generate_subkey(ctx, ent->lfsr, start, end - 1); + if (ret != 0) { + free_lfsr(ent->lfsr); + rte_free(ent); + return ret; + } + } else if ((next_ent != NULL) && (end > next_ent->offset)) { + rte_free(ent); + return -ENOSPC; + } + attach_lfsr(ent, cur_ent->lfsr); + + /** + * generate partially overlapping range + * [start, cur_ent->start) in reverse order + */ + ret = generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start); + if (ret != 0) { + free_lfsr(ent->lfsr); + rte_free(ent); + return ret; + } + + if (end > range_end) { + /** + * generate partially overlapping range + * (range_end, end) + */ + ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1); + if (ret != 0) { + free_lfsr(ent->lfsr); + rte_free(ent); + return ret; + } + } + + LIST_INSERT_BEFORE(cur_ent, ent, next); + generate_compliment_table(ctx, ent); + ctx->subtuples_nb++; + return 0; +} + +static inline int +insert_after(struct rte_thash_ctx *ctx, + struct rte_thash_subtuple_helper *ent, + struct rte_thash_subtuple_helper *cur_ent, + struct rte_thash_subtuple_helper *next_ent, + struct rte_thash_subtuple_helper *prev_ent, + uint32_t end, uint32_t range_end) +{ + int ret; + + if ((next_ent != NULL) && (end > next_ent->offset)) { + rte_free(ent); + return -EEXIST; + } + + attach_lfsr(ent, cur_ent->lfsr); + if (end > range_end) { + /** + * generate partially overlapping range + * (range_end, end) + */ + ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1); + if (ret != 0) { + free_lfsr(ent->lfsr); + rte_free(ent); + return ret; + } + } + + LIST_INSERT_AFTER(prev_ent, ent, next); + generate_compliment_table(ctx, ent); + ctx->subtuples_nb++; + + return 0; } int -rte_thash_add_helper(struct rte_thash_ctx *ctx __rte_unused, - const char *name __rte_unused, uint32_t len __rte_unused, - uint32_t offset __rte_unused) +rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len, + uint32_t offset) { + struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent, *next_ent; + uint32_t start, end; + int ret; + + if ((ctx == NULL) || (name == NULL) || (len < ctx->reta_sz_log) || + ((offset + len + TOEPLITZ_HASH_LEN - 1) > + ctx->key_len * CHAR_BIT)) + return -EINVAL; + + /* Check for existing name*/ + LIST_FOREACH(cur_ent, &ctx->head, next) { + if (strncmp(name, cur_ent->name, sizeof(cur_ent->name)) == 0) + return -EEXIST; + } + + end = offset + len + TOEPLITZ_HASH_LEN - 1; + start = ((ctx->flags & RTE_THASH_MINIMAL_SEQ) == + RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log - 1)) : + offset; + + ent = rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) + + sizeof(uint32_t) * (1 << ctx->reta_sz_log), 0); + if (ent == NULL) + return -ENOMEM; + + rte_strlcpy(ent->name, name, sizeof(ent->name)); + ent->offset = start; + ent->len = end - start; + ent->tuple_offset = offset; + ent->tuple_len = len; + ent->lsb_msk = (1 << ctx->reta_sz_log) - 1; + + cur_ent = LIST_FIRST(&ctx->head); + while (cur_ent) { + uint32_t range_end = cur_ent->offset + cur_ent->len; + next_ent = LIST_NEXT(cur_ent, next); + prev_ent = cur_ent; + /* Iterate through overlapping ranges */ + while ((next_ent != NULL) && (next_ent->offset < range_end)) { + range_end = RTE_MAX(next_ent->offset + next_ent->len, + range_end); + if (start > next_ent->offset) + prev_ent = next_ent; + + next_ent = LIST_NEXT(next_ent, next); + } + + if (start < cur_ent->offset) + return insert_before(ctx, ent, cur_ent, next_ent, + start, end, range_end); + else if (start < range_end) + return insert_after(ctx, ent, cur_ent, next_ent, + prev_ent, end, range_end); + + cur_ent = next_ent; + continue; + } + + ent->lfsr = alloc_lfsr(ctx); + if (ent->lfsr == NULL) { + rte_free(ent); + return -ENOMEM; + } + + /* generate nonoverlapping range [start, end) */ + ret = generate_subkey(ctx, ent->lfsr, start, end - 1); + if (ret != 0) { + free_lfsr(ent->lfsr); + rte_free(ent); + return ret; + } + if (LIST_EMPTY(&ctx->head)) { + LIST_INSERT_HEAD(&ctx->head, ent, next); + } else { + LIST_FOREACH(next_ent, &ctx->head, next) + prev_ent = next_ent; + + LIST_INSERT_AFTER(prev_ent, ent, next); + } + generate_compliment_table(ctx, ent); + ctx->subtuples_nb++; + return 0; } struct rte_thash_subtuple_helper * -rte_thash_get_helper(struct rte_thash_ctx *ctx __rte_unused, - const char *name __rte_unused) +rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name) { + struct rte_thash_subtuple_helper *ent; + + if ((ctx == NULL) || (name == NULL)) + return NULL; + + LIST_FOREACH(ent, &ctx->head, next) { + if (strncmp(name, ent->name, sizeof(ent->name)) == 0) + return ent; + } + return NULL; } uint32_t -rte_thash_get_compliment(struct rte_thash_subtuple_helper *h __rte_unused, - uint32_t hash __rte_unused, uint32_t desired_hash __rte_unused) +rte_thash_get_compliment(struct rte_thash_subtuple_helper *h, + uint32_t hash, uint32_t desired_hash) { - return 0; + return h->compl_table[(hash ^ desired_hash) & h->lsb_msk]; } const uint8_t * -rte_thash_get_key(struct rte_thash_ctx *ctx __rte_unused) +rte_thash_get_key(struct rte_thash_ctx *ctx) { - return NULL; + return ctx->hash_key; +} + +static inline void +xor_bit(uint8_t *ptr, uint32_t bit, uint32_t pos) +{ + uint32_t byte_idx = pos >> 3; + uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1)); + uint8_t tmp; + + tmp = ptr[byte_idx]; + tmp ^= bit << bit_idx; + ptr[byte_idx] = tmp; +} + +int +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h, + uint8_t *orig_tuple, uint32_t adj_bits, + rte_thash_check_tuple_t fn, void *userdata) +{ + unsigned i; + + if ((h == NULL) || (orig_tuple == NULL)) + return -EINVAL; + + adj_bits &= h->lsb_msk; + /* Hint: LSB of adj_bits corresponds to offset + len bit of tuple */ + for (i = 0; i < sizeof(uint32_t) * CHAR_BIT; i++) { + uint8_t bit = (adj_bits >> i) & 0x1; + if (bit) + xor_bit(orig_tuple, bit, + h->tuple_offset + h->tuple_len - 1 - i); + } + + if (fn != NULL) + return (fn(userdata, orig_tuple)) ? 0 : -EEXIST; + + return 0; } diff --git a/lib/librte_hash/rte_thash.h b/lib/librte_hash/rte_thash.h index 38a641b..fd67931 100644 --- a/lib/librte_hash/rte_thash.h +++ b/lib/librte_hash/rte_thash.h @@ -360,6 +360,48 @@ __rte_experimental const uint8_t * rte_thash_get_key(struct rte_thash_ctx *ctx); +/** + * Function prototype for the rte_thash_adjust_tuple + * to check if adjusted tuple could be used. + * Generally it is some kind of lookup function to check + * if adjusted tuple is already in use. + * + * @param userdata + * Pointer to the userdata. It could be a pointer to the + * table with used tuples to search. + * @param tuple + * Pointer to the tuple to check + * + * @return + * 1 on success + * 0 otherwise + */ +typedef int (*rte_thash_check_tuple_t)(void *userdata, uint8_t *tuple); + +/** + * Adjust tuple with complimentary bits. + * + * @param h + * Pointer to the helper struct + * @param orig_tuple + * Pointer to the tuple to be adjusted + * @param adj_bits + * Valure returned by rte_thash_get_compliment + * @param fn + * Callback function to check adjusted tuple. Could be NULL + * @param userdata + * Pointer to the userdata to be passed to fn(). Could be NULL + * + * @return + * 0 on success + * negative otherwise + */ +__rte_experimental +int +rte_thash_adjust_tuple(struct rte_thash_subtuple_helper *h, + uint8_t *orig_tuple, uint32_t adj_bits, + rte_thash_check_tuple_t fn, void *userdata); + #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/version.map b/lib/librte_hash/version.map index 93cb230..a992a1e 100644 --- a/lib/librte_hash/version.map +++ b/lib/librte_hash/version.map @@ -32,6 +32,7 @@ DPDK_21 { EXPERIMENTAL { global: + rte_thash_adjust_tuple; rte_hash_free_key_with_position; rte_hash_lookup_with_hash_bulk; rte_hash_lookup_with_hash_bulk_data; From patchwork Tue Apr 6 19:50:43 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 90754 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id C09FAA0546; Tue, 6 Apr 2021 21:51:10 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 153EA140FB4; Tue, 6 Apr 2021 21:51:00 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by mails.dpdk.org (Postfix) with ESMTP id 86775140FB8 for ; Tue, 6 Apr 2021 21:50:58 +0200 (CEST) IronPort-SDR: p1GO/1sb32Q2BeRu4jlB5n5aaFB+SkZmEYg1ID+helfbRTzxKC0PsUrK+qzpriCu8AFCSwCRe7 DCGV4FesEgPw== X-IronPort-AV: E=McAfee;i="6000,8403,9946"; a="172619785" X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="172619785" Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Apr 2021 12:50:58 -0700 IronPort-SDR: 4ohKmcG4DGOSguRprOpMEPx6PEKFyGULKr3ZfaJn5vWK4v/K91tDmVZba9vpaXtU41Vy0ICqKG sv7/KTemnsyw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.82,201,1613462400"; d="scan'208";a="448740723" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga002.fm.intel.com with ESMTP; 06 Apr 2021 12:50:54 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, andrey.chilikin@intel.com, ray.kinsella@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Tue, 6 Apr 2021 20:50:43 +0100 Message-Id: <1617738643-258635-4-git-send-email-vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> References: <1617738643-258635-1-git-send-email-vladimir.medvedkin@intel.com> In-Reply-To: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> References: <1615919077-77774-1-git-send-email-vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v2 3/3] test/hash: add additional thash tests 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" This patch adds tests for predictable RSS feature Signed-off-by: Vladimir Medvedkin --- app/test/test_thash.c | 468 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 462 insertions(+), 6 deletions(-) diff --git a/app/test/test_thash.c b/app/test/test_thash.c index a6aadd1..28ae767 100644 --- a/app/test/test_thash.c +++ b/app/test/test_thash.c @@ -5,11 +5,15 @@ #include #include #include +#include #include "test.h" #include +#define HASH_MSK(reta_sz) ((1 << reta_sz) - 1) +#define TUPLE_SZ (RTE_THASH_V4_L4_LEN * 4) + struct test_thash_v4 { uint32_t dst_ip; uint32_t src_ip; @@ -75,7 +79,7 @@ uint8_t default_rss_key[] = { }; static int -test_thash(void) +test_toeplitz_hash_calc(void) { uint32_t i, j; union rte_thash_tuple tuple; @@ -100,7 +104,7 @@ test_thash(void) RTE_THASH_V4_L4_LEN, default_rss_key); if ((rss_l3 != v4_tbl[i].hash_l3) || (rss_l3l4 != v4_tbl[i].hash_l3l4)) - return -1; + return -TEST_FAILED; /*Calculate hash with converted key*/ rss_l3 = rte_softrss_be((uint32_t *)&tuple, RTE_THASH_V4_L3_LEN, rss_key_be); @@ -108,7 +112,7 @@ test_thash(void) RTE_THASH_V4_L4_LEN, rss_key_be); if ((rss_l3 != v4_tbl[i].hash_l3) || (rss_l3l4 != v4_tbl[i].hash_l3l4)) - return -1; + return -TEST_FAILED; } for (i = 0; i < RTE_DIM(v6_tbl); i++) { /*Fill ipv6 hdr*/ @@ -127,7 +131,7 @@ test_thash(void) RTE_THASH_V6_L4_LEN, default_rss_key); if ((rss_l3 != v6_tbl[i].hash_l3) || (rss_l3l4 != v6_tbl[i].hash_l3l4)) - return -1; + return -TEST_FAILED; /*Calculate hash with converted key*/ rss_l3 = rte_softrss_be((uint32_t *)&tuple, RTE_THASH_V6_L3_LEN, rss_key_be); @@ -135,9 +139,461 @@ test_thash(void) RTE_THASH_V6_L4_LEN, rss_key_be); if ((rss_l3 != v6_tbl[i].hash_l3) || (rss_l3l4 != v6_tbl[i].hash_l3l4)) - return -1; + return -TEST_FAILED; } - return 0; + return TEST_SUCCESS; +} + +static int +test_create_invalid(void) +{ + struct rte_thash_ctx *ctx; + int key_len = 40; + int reta_sz = 7; + + ctx = rte_thash_init_ctx(NULL, key_len, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx == NULL, + "Call succeeded with invalid parameters\n"); + + ctx = rte_thash_init_ctx("test", 0, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx == NULL, + "Call succeeded with invalid parameters\n"); + + ctx = rte_thash_init_ctx(NULL, key_len, 1, NULL, 0); + RTE_TEST_ASSERT(ctx == NULL, + "Call succeeded with invalid parameters\n"); + + ctx = rte_thash_init_ctx(NULL, key_len, 17, NULL, 0); + RTE_TEST_ASSERT(ctx == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +static int +test_multiple_create(void) +{ + struct rte_thash_ctx *ctx; + int key_len = 40; + int reta_sz = 7; + int i; + + for (i = 0; i < 100; i++) { + ctx = rte_thash_init_ctx("test", key_len, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "Can not create CTX\n"); + + rte_thash_free_ctx(ctx); + } + + return TEST_SUCCESS; +} + +static int +test_free_null(void) +{ + struct rte_thash_ctx *ctx; + + ctx = rte_thash_init_ctx("test", 40, 7, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "Can not create CTX\n"); + + rte_thash_free_ctx(ctx); + rte_thash_free_ctx(NULL); + + return TEST_SUCCESS; +} + +static int +test_add_invalid_helper(void) +{ + struct rte_thash_ctx *ctx; + const int key_len = 40; + int reta_sz = 7; + int ret; + + ctx = rte_thash_init_ctx("test", key_len, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "can not create thash ctx\n"); + + ret = rte_thash_add_helper(NULL, "test", reta_sz, 0); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + ret = rte_thash_add_helper(ctx, NULL, reta_sz, 0); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + ret = rte_thash_add_helper(ctx, "test", reta_sz - 1, 0); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + ret = rte_thash_add_helper(ctx, "test", reta_sz, key_len * 8); + RTE_TEST_ASSERT(ret == -EINVAL, + "Call succeeded with invalid parameters\n"); + + ret = rte_thash_add_helper(ctx, "first_range", reta_sz, 0); + RTE_TEST_ASSERT(ret == 0, "Can not create helper\n"); + + ret = rte_thash_add_helper(ctx, "first_range", reta_sz, 0); + RTE_TEST_ASSERT(ret == -EEXIST, + "Call succeeded with duplicated name\n"); + + /* + * Create second helper with offset 3 * reta_sz. + * Note firts_range helper created range in key: + * [0, 32 + length{= reta_sz} - 1), i.e [0, 37). + * second range is [44, 81) + */ + ret = rte_thash_add_helper(ctx, "second_range", reta_sz, + 32 + 2 * reta_sz); + RTE_TEST_ASSERT(ret == 0, "Can not create helper\n"); + + /* + * Try to create overlapping with first_ and second_ ranges, + * i.e. [6, 49) + */ + ret = rte_thash_add_helper(ctx, "third_range", 2 * reta_sz, reta_sz); + RTE_TEST_ASSERT(ret == -EEXIST, + "Call succeeded with overlapping ranges\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static int +test_find_existing(void) +{ + struct rte_thash_ctx *ctx, *ret_ctx; + + ctx = rte_thash_init_ctx("test", 40, 7, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "can not create thash ctx\n"); + + ret_ctx = rte_thash_find_existing("test"); + RTE_TEST_ASSERT(ret_ctx != NULL, "can not find existing ctx\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static int +test_get_helper(void) +{ + struct rte_thash_ctx *ctx; + struct rte_thash_subtuple_helper *h; + int ret; + + ctx = rte_thash_init_ctx("test", 40, 7, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "Can not create thash ctx\n"); + + h = rte_thash_get_helper(NULL, "first_range"); + RTE_TEST_ASSERT(h == NULL, "Call succeeded with invalid parameters\n"); + + h = rte_thash_get_helper(ctx, NULL); + RTE_TEST_ASSERT(h == NULL, "Call succeeded with invalid parameters\n"); + + ret = rte_thash_add_helper(ctx, "first_range", 8, 0); + RTE_TEST_ASSERT(ret == 0, "Can not create helper\n"); + + h = rte_thash_get_helper(ctx, "first_range"); + RTE_TEST_ASSERT(h != NULL, "Can not find helper\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static int +test_period_overflow(void) +{ + struct rte_thash_ctx *ctx; + int reta_sz = 7; /* reflects polynomial degree */ + int ret; + + /* first create without RTE_THASH_IGNORE_PERIOD_OVERFLOW flag */ + ctx = rte_thash_init_ctx("test", 40, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "Can not create thash ctx\n"); + + /* requested range > (2^reta_sz) - 1 */ + ret = rte_thash_add_helper(ctx, "test", (1 << reta_sz), 0); + RTE_TEST_ASSERT(ret == -ENOSPC, + "Call succeeded with invalid parameters\n"); + + /* requested range == len + 32 - 1, smaller than (2^reta_sz) - 1 */ + ret = rte_thash_add_helper(ctx, "test", (1 << reta_sz) - 32, 0); + RTE_TEST_ASSERT(ret == 0, "Can not create helper\n"); + + rte_thash_free_ctx(ctx); + + /* create with RTE_THASH_IGNORE_PERIOD_OVERFLOW flag */ + ctx = rte_thash_init_ctx("test", 40, reta_sz, NULL, + RTE_THASH_IGNORE_PERIOD_OVERFLOW); + RTE_TEST_ASSERT(ctx != NULL, "Can not create thash ctx\n"); + + /* requested range > (2^reta_sz - 1) */ + ret = rte_thash_add_helper(ctx, "test", (1 << reta_sz) + 10, 0); + RTE_TEST_ASSERT(ret == 0, "Can not create helper\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static int +test_predictable_rss_min_seq(void) +{ + struct rte_thash_ctx *ctx; + struct rte_thash_subtuple_helper *h; + const int key_len = 40; + int reta_sz = 6; + uint8_t initial_key[key_len]; + const uint8_t *new_key; + int ret; + union rte_thash_tuple tuple; + uint32_t orig_hash, adj_hash, adj; + unsigned int desired_value = 27 & HASH_MSK(reta_sz); + uint16_t port_value = 22; + + memset(initial_key, 0, key_len); + + ctx = rte_thash_init_ctx("test", key_len, reta_sz, initial_key, + RTE_THASH_MINIMAL_SEQ); + RTE_TEST_ASSERT(ctx != NULL, "can not create thash ctx\n"); + + ret = rte_thash_add_helper(ctx, "snat", sizeof(uint16_t) * 8, + offsetof(union rte_thash_tuple, v4.sport) * 8); + RTE_TEST_ASSERT(ret == 0, "can not add helper, ret %d\n", ret); + + h = rte_thash_get_helper(ctx, "snat"); + RTE_TEST_ASSERT(h != NULL, "can not find helper\n"); + + new_key = rte_thash_get_key(ctx); + tuple.v4.src_addr = RTE_IPV4(0, 0, 0, 0); + tuple.v4.dst_addr = RTE_IPV4(0, 0, 0, 0); + tuple.v4.sport = 0; + tuple.v4.sport = rte_cpu_to_be_16(port_value); + tuple.v4.dport = 0; + tuple.v4.sctp_tag = rte_be_to_cpu_32(tuple.v4.sctp_tag); + + orig_hash = rte_softrss((uint32_t *)&tuple, + RTE_THASH_V4_L4_LEN, new_key); + adj = rte_thash_get_compliment(h, orig_hash, desired_value); + + tuple.v4.sctp_tag = rte_cpu_to_be_32(tuple.v4.sctp_tag); + tuple.v4.sport ^= rte_cpu_to_be_16(adj); + tuple.v4.sctp_tag = rte_be_to_cpu_32(tuple.v4.sctp_tag); + + adj_hash = rte_softrss((uint32_t *)&tuple, + RTE_THASH_V4_L4_LEN, new_key); + RTE_TEST_ASSERT((adj_hash & HASH_MSK(reta_sz)) == + desired_value, "bad desired value\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +/* + * This test creates 7 subranges in the folowing order: + * range_one = [56, 95), len = 8, offset = 56 + * range_two = [64, 103), len = 8, offset = 64 + * range_three = [120, 159), len = 8, offset = 120 + * range_four = [48, 87), len = 8, offset = 48 + * range_five = [57, 95), len = 7, offset = 57 + * range_six = [40, 111), len = 40, offset = 40 + * range_seven = [0, 39), len = 8, offset = 0 + */ +struct range { + const char *name; + int len; + int offset; + int byte_idx; +}; + +struct range rng_arr[] = { + {"one", 8, 56, 7}, + {"two", 8, 64, 8}, + {"three", 8, 120, 15}, + {"four", 8, 48, 6}, + {"six", 40, 40, 9}, + {"five", 7, 57, 7}, + {"seven", 8, 0, 0} +}; + +static int +test_predictable_rss_multirange(void) +{ + struct rte_thash_ctx *ctx; + struct rte_thash_subtuple_helper *h[RTE_DIM(rng_arr)]; + const uint8_t *new_key; + const int key_len = 40; + int reta_sz = 7; + unsigned int i, j, k; + int ret; + uint32_t desired_value = rte_rand() & HASH_MSK(reta_sz); + uint8_t tuples[RTE_DIM(rng_arr)][16] = { {0} }; + uint32_t *ptr; + uint32_t hashes[RTE_DIM(rng_arr)]; + uint32_t adj_hashes[RTE_DIM(rng_arr)]; + uint32_t adj; + + ctx = rte_thash_init_ctx("test", key_len, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "can not create thash ctx\n"); + + for (i = 0; i < RTE_DIM(rng_arr); i++) { + ret = rte_thash_add_helper(ctx, rng_arr[i].name, + rng_arr[i].len, rng_arr[i].offset); + RTE_TEST_ASSERT(ret == 0, "can not add helper\n"); + + h[i] = rte_thash_get_helper(ctx, rng_arr[i].name); + RTE_TEST_ASSERT(h[i] != NULL, "can not find helper\n"); + } + new_key = rte_thash_get_key(ctx); + + /* + * calculate hashes, compliments, then adjust keys with + * compliments and recalsulate hashes + */ + for (i = 0; i < RTE_DIM(rng_arr); i++) { + for (k = 0; k < 100; k++) { + /* init with random keys */ + ptr = (uint32_t *)&tuples[i][0]; + for (j = 0; j < 4; j++) + ptr[j] = rte_rand(); + /* convert keys from BE to CPU byte order */ + for (j = 0; j < 4; j++) + ptr[j] = rte_be_to_cpu_32(ptr[j]); + + hashes[i] = rte_softrss(ptr, 4, new_key); + adj = rte_thash_get_compliment(h[i], hashes[i], + desired_value); + /* convert back to BE to adjust the value */ + for (j = 0; j < 4; j++) + ptr[j] = rte_cpu_to_be_32(ptr[j]); + + tuples[i][rng_arr[i].byte_idx] ^= adj; + + for (j = 0; j < 4; j++) + ptr[j] = rte_be_to_cpu_32(ptr[j]); + + adj_hashes[i] = rte_softrss(ptr, 4, new_key); + RTE_TEST_ASSERT((adj_hashes[i] & HASH_MSK(reta_sz)) == + desired_value, + "bad desired value for %d tuple\n", i); + } + } + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static int +cmp_tuple_eq(void *userdata, uint8_t *tuple) +{ + return memcmp(userdata, tuple, TUPLE_SZ); +} + +static int +test_adjust_tuple(void) +{ + struct rte_thash_ctx *ctx; + struct rte_thash_subtuple_helper *h; + const int key_len = 40; + int reta_sz = CHAR_BIT; + const uint8_t *new_key; + int ret; + uint8_t be_tuple[TUPLE_SZ]; + uint8_t be_tuple_tmp[TUPLE_SZ]; + uint8_t le_tuple[TUPLE_SZ]; + uint32_t orig_hash, adj_hash, adj; + unsigned int i; + unsigned int desired_value = 27 & HASH_MSK(reta_sz); + + memset(be_tuple, 0xab, TUPLE_SZ); + memset(le_tuple, 0xab, TUPLE_SZ); + + ctx = rte_thash_init_ctx("test", key_len, reta_sz, NULL, 0); + RTE_TEST_ASSERT(ctx != NULL, "can not create thash ctx\n"); + + /* set offset to be in the middle of a byte */ + ret = rte_thash_add_helper(ctx, "test", CHAR_BIT, (5 * CHAR_BIT) + 4); + RTE_TEST_ASSERT(ret == 0, "can not add helper, ret %d\n", ret); + + h = rte_thash_get_helper(ctx, "test"); + RTE_TEST_ASSERT(h != NULL, "can not find helper\n"); + + new_key = rte_thash_get_key(ctx); + + /* at the moment be_ and le_ tuples are the same */ + orig_hash = rte_softrss((uint32_t *)le_tuple, + RTE_THASH_V4_L4_LEN, new_key); + + adj = rte_thash_get_compliment(h, orig_hash, desired_value); + + ret = rte_thash_adjust_tuple(h, be_tuple, adj, NULL, NULL); + RTE_TEST_ASSERT(ret == 0, "can not adjust tuple, ret %d\n", ret); + + for (i = 0; i < (TUPLE_SZ / 4); i++) + *(uint32_t *)&le_tuple[i * 4] = + rte_be_to_cpu_32(*(uint32_t *)&be_tuple[i * 4]); + + adj_hash = rte_softrss((uint32_t *)le_tuple, + RTE_THASH_V4_L4_LEN, new_key); + RTE_TEST_ASSERT((adj_hash & HASH_MSK(reta_sz)) == + desired_value, "bad desired value\n"); + + /* Pass previously calculated tuple to callback function */ + memcpy(be_tuple_tmp, be_tuple, TUPLE_SZ); + + memset(be_tuple, 0xab, TUPLE_SZ); + ret = rte_thash_adjust_tuple(h, be_tuple, adj, cmp_tuple_eq, + &be_tuple_tmp); + RTE_TEST_ASSERT(ret == -EEXIST, "adjust tuple didn't indicate collision\n"); + + /* Pass another tuple to check with */ + memset(be_tuple, 0xab, TUPLE_SZ); + ret = rte_thash_adjust_tuple(h, be_tuple, adj, cmp_tuple_eq, + &le_tuple); + RTE_TEST_ASSERT(ret == 0, "can not adjust tuple, ret %d\n", ret); + + for (i = 0; i < (TUPLE_SZ / 4); i++) + *(uint32_t *)&le_tuple[i * 4] = + rte_be_to_cpu_32(*(uint32_t *)&be_tuple[i * 4]); + + adj_hash = rte_softrss((uint32_t *)le_tuple, + RTE_THASH_V4_L4_LEN, new_key); + RTE_TEST_ASSERT((adj_hash & HASH_MSK(reta_sz)) == + desired_value, "bad desired value\n"); + + rte_thash_free_ctx(ctx); + + return TEST_SUCCESS; +} + +static struct unit_test_suite thash_tests = { + .suite_name = "thash autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_toeplitz_hash_calc), + TEST_CASE(test_create_invalid), + TEST_CASE(test_multiple_create), + TEST_CASE(test_free_null), + TEST_CASE(test_add_invalid_helper), + TEST_CASE(test_find_existing), + TEST_CASE(test_get_helper), + TEST_CASE(test_period_overflow), + TEST_CASE(test_predictable_rss_min_seq), + TEST_CASE(test_predictable_rss_multirange), + TEST_CASE(test_adjust_tuple), + TEST_CASES_END() + } +}; + +static int +test_thash(void) +{ + return unit_test_suite_runner(&thash_tests); } REGISTER_TEST_COMMAND(thash_autotest, test_thash);