From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 75D71A034C; Fri, 19 Aug 2022 21:52:47 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id A50D941614; Fri, 19 Aug 2022 21:52:34 +0200 (CEST) Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by mails.dpdk.org (Postfix) with ESMTP id 9C5D240DDC for ; Fri, 19 Aug 2022 21:52:30 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1660938750; x=1692474750; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=7N5N3Zv8OT4vIy5WpzqsB5ZRgmJc0eWDEKWNGLmloK4=; b=l7zqvliOUsBEMFfOgGNusnL0gqjxl7CAgIkZPwqTb+pVNvsz3Lx9rZSO P82yZBXcB2pXvZ+JIqcAadJN5sC2Egll2MhDCCwIOfpCPsxeg/lAzTXOz 6aNQx9pCbpLy2WSNXbGNnkOVHRiE/UMOuFFDGw/V6fhIKNUKwLL0RYu1d iTu0EOfbj2E3LZLUYzsjkstG45W7lh4ELJDTnWEpcue5Cjnwf1VkmLzKb LlkGdAyDHjVBq3bnmH9zQwsOp7IIYpnwzjsMGy66uwTki/5yfFugRU/4D r+lAq5IT2au6YxpM2H6SZFJMmzjJUap83NNm1IbXPIY6XzPBqmtTDZSui A==; X-IronPort-AV: E=McAfee;i="6500,9779,10444"; a="280047522" X-IronPort-AV: E=Sophos;i="5.93,249,1654585200"; d="scan'208";a="280047522" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga101.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 19 Aug 2022 12:52:30 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.93,248,1654585200"; d="scan'208";a="604695951" Received: from silpixa00400573.ir.intel.com (HELO silpixa00400573.ger.corp.intel.com.) ([10.237.223.157]) by orsmga007.jf.intel.com with ESMTP; 19 Aug 2022 12:52:29 -0700 From: Cristian Dumitrescu To: dev@dpdk.org Cc: "Kamalakannan R ." Subject: [PATCH V2 3/6] table: configure the hash function for regular tables Date: Fri, 19 Aug 2022 19:52:22 +0000 Message-Id: <20220819195225.1483020-4-cristian.dumitrescu@intel.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220819195225.1483020-1-cristian.dumitrescu@intel.com> References: <20220818114449.1408226-1-cristian.dumitrescu@intel.com> <20220819195225.1483020-1-cristian.dumitrescu@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 Make the hash function configurable. The internal hash function that was not configurable, mask-based and limited to 64 bytes is removed. Signed-off-by: Cristian Dumitrescu Signed-off-by: Kamalakannan R. --- lib/table/rte_swx_table.h | 8 ++ lib/table/rte_swx_table_em.c | 266 ++++++----------------------------- 2 files changed, 49 insertions(+), 225 deletions(-) diff --git a/lib/table/rte_swx_table.h b/lib/table/rte_swx_table.h index c1383c2e57..4b8dc06798 100644 --- a/lib/table/rte_swx_table.h +++ b/lib/table/rte_swx_table.h @@ -19,6 +19,8 @@ extern "C" { #include +#include "rte_swx_hash_func.h" + /** Match type. */ enum rte_swx_table_match_type { /** Wildcard Match (WM). */ @@ -58,6 +60,12 @@ struct rte_swx_table_params { */ uint32_t action_data_size; + /** Hash function. Ignored when not needed by the table implementation. + * When needed but set to NULL, the table implementation will select the + * hash function to use. + */ + rte_swx_hash_func_t hash_func; + /** Maximum number of keys to be stored in the table together with their * associated data. */ diff --git a/lib/table/rte_swx_table_em.c b/lib/table/rte_swx_table_em.c index f783cfe282..568e76e249 100644 --- a/lib/table/rte_swx_table_em.c +++ b/lib/table/rte_swx_table_em.c @@ -7,7 +7,10 @@ #include #include +#include +#include +#include "rte_swx_keycmp.h" #include "rte_swx_table_em.h" #define CHECK(condition, err_code) \ @@ -54,181 +57,10 @@ env_free(void *start, size_t size) #endif -#if defined(RTE_ARCH_X86_64) - -#include - -#define crc32_u64(crc, v) _mm_crc32_u64(crc, v) - -#else - -static inline uint64_t -crc32_u64_generic(uint64_t crc, uint64_t value) -{ - int i; - - crc = (crc & 0xFFFFFFFFLLU) ^ value; - for (i = 63; i >= 0; i--) { - uint64_t mask; - - mask = -(crc & 1LLU); - crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask); - } - - return crc; -} - -#define crc32_u64(crc, v) crc32_u64_generic(crc, v) - -#endif - -/* Key size needs to be one of: 8, 16, 32 or 64. */ -static inline uint32_t -hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed) -{ - uint64_t *k = key; - uint64_t *m = key_mask; - uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5; - - switch (key_size) { - case 8: - crc0 = crc32_u64(seed, k[0] & m[0]); - return crc0; - - case 16: - k0 = k[0] & m[0]; - - crc0 = crc32_u64(k0, seed); - crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); - - crc0 ^= crc1; - - return crc0; - - case 32: - k0 = k[0] & m[0]; - k2 = k[2] & m[2]; - - crc0 = crc32_u64(k0, seed); - crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); - - crc2 = crc32_u64(k2, k[3] & m[3]); - crc3 = k2 >> 32; - - crc0 = crc32_u64(crc0, crc1); - crc1 = crc32_u64(crc2, crc3); - - crc0 ^= crc1; - - return crc0; - - case 64: - k0 = k[0] & m[0]; - k2 = k[2] & m[2]; - k5 = k[5] & m[5]; - - crc0 = crc32_u64(k0, seed); - crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); - - crc2 = crc32_u64(k2, k[3] & m[3]); - crc3 = crc32_u64(k2 >> 32, k[4] & m[4]); - - crc4 = crc32_u64(k5, k[6] & m[6]); - crc5 = crc32_u64(k5 >> 32, k[7] & m[7]); - - crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2); - crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5); - - crc0 ^= crc1; - - return crc0; - - default: - crc0 = 0; - return crc0; - } -} - -/* n_bytes needs to be a multiple of 8 bytes. */ static void -keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes) +keycpy(void *dst, void *src, uint32_t n_bytes) { - uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask; - uint32_t i; - - for (i = 0; i < n_bytes / sizeof(uint64_t); i++) - dst64[i] = src64[i] & src_mask64[i]; -} - -/* - * Return: 0 = Keys are NOT equal; 1 = Keys are equal. - */ -static inline uint32_t -keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes) -{ - uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask; - - switch (n_bytes) { - case 8: { - uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); - uint32_t result = 1; - - if (xor0) - result = 0; - return result; - } - - case 16: { - uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); - uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); - uint64_t or = xor0 | xor1; - uint32_t result = 1; - - if (or) - result = 0; - return result; - } - - case 32: { - uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); - uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); - uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]); - uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]); - uint64_t or = (xor0 | xor1) | (xor2 | xor3); - uint32_t result = 1; - - if (or) - result = 0; - return result; - } - - case 64: { - uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); - uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); - uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]); - uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]); - uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]); - uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]); - uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]); - uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]); - uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) | - ((xor4 | xor5) | (xor6 | xor7)); - uint32_t result = 1; - - if (or) - result = 0; - return result; - } - - default: { - uint32_t i; - - for (i = 0; i < n_bytes / sizeof(uint64_t); i++) - if (a64[i] != (b64[i] & b_mask64[i])) - return 0; - return 1; - } - } + memcpy(dst, src, n_bytes); } #define KEYS_PER_BUCKET 4 @@ -244,8 +76,6 @@ struct table { struct rte_swx_table_params params; /* Internal. */ - uint32_t key_size; - uint32_t data_size; uint32_t key_size_shl; uint32_t data_size_shl; uint32_t n_buckets; @@ -253,9 +83,9 @@ struct table { uint32_t key_stack_tos; uint32_t bkt_ext_stack_tos; uint64_t total_size; + rte_swx_keycmp_func_t keycmp_func; /* Memory arrays. */ - uint8_t *key_mask; struct bucket_extension *buckets; struct bucket_extension *buckets_ext; uint8_t *keys; @@ -279,8 +109,7 @@ table_key_data(struct table *t, uint32_t key_id) static inline int bkt_is_empty(struct bucket_extension *bkt) { - return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ? - 1 : 0; + return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ? 1 : 0; } /* Return: @@ -311,7 +140,7 @@ bkt_keycmp(struct table *t, /* Key comparison. */ bkt_key_id = bkt->key_id[bkt_pos]; bkt_key = table_key(t, bkt_key_id); - return keycmp(bkt_key, input_key, t->key_mask, t->key_size); + return t->keycmp_func(bkt_key, input_key, t->params.key_size); } static inline void @@ -331,15 +160,13 @@ bkt_key_install(struct table *t, /* Key. */ bkt->key_id[bkt_pos] = bkt_key_id; bkt_key = table_key(t, bkt_key_id); - keycpy(bkt_key, input->key, t->key_mask, t->key_size); + keycpy(bkt_key, input->key, t->params.key_size); /* Key data. */ bkt_data = table_key_data(t, bkt_key_id); bkt_data[0] = input->action_id; if (t->params.action_data_size && input->action_data) - memcpy(&bkt_data[1], - input->action_data, - t->params.action_data_size); + memcpy(&bkt_data[1], input->action_data, t->params.action_data_size); } static inline void @@ -358,9 +185,7 @@ bkt_key_data_update(struct table *t, bkt_data = table_key_data(t, bkt_key_id); bkt_data[0] = input->action_id; if (t->params.action_data_size && input->action_data) - memcpy(&bkt_data[1], - input->action_data, - t->params.action_data_size); + memcpy(&bkt_data[1], input->action_data, t->params.action_data_size); } #define CL RTE_CACHE_LINE_ROUNDUP @@ -374,9 +199,9 @@ __table_create(struct table **table, { struct table *t; uint8_t *memory; - size_t table_meta_sz, key_mask_sz, bucket_sz, bucket_ext_sz, key_sz, + size_t table_meta_sz, bucket_sz, bucket_ext_sz, key_sz, key_stack_sz, bkt_ext_stack_sz, data_sz, total_size; - size_t key_mask_offset, bucket_offset, bucket_ext_offset, key_offset, + size_t bucket_offset, bucket_ext_offset, key_offset, key_stack_offset, bkt_ext_stack_offset, data_offset; uint32_t key_size, key_data_size, n_buckets, n_buckets_ext, i; @@ -384,30 +209,34 @@ __table_create(struct table **table, CHECK(params, EINVAL); CHECK(params->match_type == RTE_SWX_TABLE_MATCH_EXACT, EINVAL); CHECK(params->key_size, EINVAL); - CHECK(params->key_size <= 64, EINVAL); + + if (params->key_mask0) { + for (i = 0; i < params->key_size; i++) + if (params->key_mask0[i] != 0xFF) + break; + + CHECK(i == params->key_size, EINVAL); + } + CHECK(params->n_keys_max, EINVAL); /* Memory allocation. */ key_size = rte_align64pow2(params->key_size); - if (key_size < 8) - key_size = 8; key_data_size = rte_align64pow2(params->action_data_size + 8); - n_buckets = params->n_keys_max / KEYS_PER_BUCKET; - n_buckets_ext = params->n_keys_max / KEYS_PER_BUCKET; + n_buckets = rte_align64pow2((params->n_keys_max + KEYS_PER_BUCKET - 1) / KEYS_PER_BUCKET); + n_buckets_ext = n_buckets; table_meta_sz = CL(sizeof(struct table)); - key_mask_sz = CL(key_size); bucket_sz = CL(n_buckets * sizeof(struct bucket_extension)); bucket_ext_sz = CL(n_buckets_ext * sizeof(struct bucket_extension)); key_sz = CL(params->n_keys_max * key_size); key_stack_sz = CL(params->n_keys_max * sizeof(uint32_t)); bkt_ext_stack_sz = CL(n_buckets_ext * sizeof(uint32_t)); data_sz = CL(params->n_keys_max * key_data_size); - total_size = table_meta_sz + key_mask_sz + bucket_sz + bucket_ext_sz + + total_size = table_meta_sz + bucket_sz + bucket_ext_sz + key_sz + key_stack_sz + bkt_ext_stack_sz + data_sz; - key_mask_offset = table_meta_sz; - bucket_offset = key_mask_offset + key_mask_sz; + bucket_offset = table_meta_sz; bucket_ext_offset = bucket_offset + bucket_sz; key_offset = bucket_ext_offset + bucket_ext_sz; key_stack_offset = key_offset + key_sz; @@ -427,16 +256,17 @@ __table_create(struct table **table, /* Initialization. */ t = (struct table *)memory; memcpy(&t->params, params, sizeof(*params)); + t->params.key_mask0 = NULL; + if (!params->hash_func) + t->params.hash_func = rte_hash_crc; - t->key_size = key_size; - t->data_size = key_data_size; t->key_size_shl = __builtin_ctzl(key_size); t->data_size_shl = __builtin_ctzl(key_data_size); t->n_buckets = n_buckets; t->n_buckets_ext = n_buckets_ext; t->total_size = total_size; + t->keycmp_func = rte_swx_keycmp_func_get(params->key_size); - t->key_mask = &memory[key_mask_offset]; t->buckets = (struct bucket_extension *)&memory[bucket_offset]; t->buckets_ext = (struct bucket_extension *)&memory[bucket_ext_offset]; t->keys = &memory[key_offset]; @@ -444,13 +274,6 @@ __table_create(struct table **table, t->bkt_ext_stack = (uint32_t *)&memory[bkt_ext_stack_offset]; t->data = &memory[data_offset]; - t->params.key_mask0 = t->key_mask; - - if (!params->key_mask0) - memset(t->key_mask, 0xFF, params->key_size); - else - memcpy(t->key_mask, params->key_mask0, params->key_size); - for (i = 0; i < t->params.n_keys_max; i++) t->key_stack[i] = t->params.n_keys_max - 1 - i; t->key_stack_tos = t->params.n_keys_max; @@ -485,7 +308,7 @@ table_add(void *table, struct rte_swx_table_entry *entry) CHECK(entry, EINVAL); CHECK(entry->key, EINVAL); - input_sig = hash(entry->key, t->key_mask, t->key_size, 0); + input_sig = t->params.hash_func(entry->key, t->params.key_size, 0); bkt_id = input_sig & (t->n_buckets - 1); bkt0 = &t->buckets[bkt_id]; input_sig = (input_sig >> 16) | 1; @@ -506,10 +329,8 @@ table_add(void *table, struct rte_swx_table_entry *entry) /* Allocate new key & install. */ CHECK(t->key_stack_tos, ENOSPC); - new_bkt_key_id = - t->key_stack[--t->key_stack_tos]; - bkt_key_install(t, bkt, entry, i, - new_bkt_key_id, input_sig); + new_bkt_key_id = t->key_stack[--t->key_stack_tos]; + bkt_key_install(t, bkt, entry, i, new_bkt_key_id, input_sig); return 0; } @@ -526,8 +347,7 @@ table_add(void *table, struct rte_swx_table_entry *entry) /* Allocate new key & install. */ new_bkt_key_id = t->key_stack[--t->key_stack_tos]; - bkt_key_install(t, new_bkt, entry, 0, - new_bkt_key_id, input_sig); + bkt_key_install(t, new_bkt, entry, 0, new_bkt_key_id, input_sig); return 0; } @@ -545,7 +365,7 @@ table_del(void *table, struct rte_swx_table_entry *entry) CHECK(entry, EINVAL); CHECK(entry->key, EINVAL); - input_sig = hash(entry->key, t->key_mask, t->key_size, 0); + input_sig = t->params.hash_func(entry->key, t->params.key_size, 0); bkt_id = input_sig & (t->n_buckets - 1); bkt0 = &t->buckets[bkt_id]; input_sig = (input_sig >> 16) | 1; @@ -556,17 +376,13 @@ table_del(void *table, struct rte_swx_table_entry *entry) if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) { /* Key free. */ bkt->sig[i] = 0; - t->key_stack[t->key_stack_tos++] = - bkt->key_id[i]; + t->key_stack[t->key_stack_tos++] = bkt->key_id[i]; - /* Bucket extension free if empty and not the - * 1st in bucket. - */ + /* Bucket extension free if empty and not the 1st in bucket. */ if (bkt_prev && bkt_is_empty(bkt)) { bkt_prev->next = bkt->next; bkt_id = bkt - t->buckets_ext; - t->bkt_ext_stack[t->bkt_ext_stack_tos++] - = bkt_id; + t->bkt_ext_stack[t->bkt_ext_stack_tos++] = bkt_id; } return 0; @@ -596,7 +412,7 @@ table_lookup_unoptimized(void *table, input_key = &(*key)[t->params.key_offset]; - input_sig = hash(input_key, t->key_mask, t->key_size, 0); + input_sig = t->params.hash_func(input_key, t->params.key_size, 0); bkt_id = input_sig & (t->n_buckets - 1); bkt0 = &t->buckets[bkt_id]; input_sig = (input_sig >> 16) | 1; @@ -695,7 +511,7 @@ table_lookup(void *table, struct bucket_extension *bkt; uint32_t input_sig, bkt_id; - input_sig = hash(input_key, t->key_mask, t->key_size, 0); + input_sig = t->params.hash_func(input_key, t->params.key_size, 0); bkt_id = input_sig & (t->n_buckets - 1); bkt = &t->buckets[bkt_id]; rte_prefetch0(bkt); @@ -756,7 +572,7 @@ table_lookup(void *table, uint64_t *bkt_data = table_key_data(t, bkt_key_id); uint32_t lkp_hit; - lkp_hit = keycmp(bkt_key, input_key, t->key_mask, t->key_size); + lkp_hit = t->keycmp_func(bkt_key, input_key, t->params.key_size); lkp_hit &= m->sig_match; *action_id = bkt_data[0]; *action_data = (uint8_t *)&bkt_data[1]; -- 2.34.1