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 E50FC42D8E; Thu, 29 Jun 2023 19:33:28 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 7795140EDB; Thu, 29 Jun 2023 19:33:28 +0200 (CEST) Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.173]) by mails.dpdk.org (Postfix) with ESMTP id 9C03B406B7 for ; Thu, 29 Jun 2023 19:33:26 +0200 (CEST) Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-6686a05bc66so708111b3a.1 for ; Thu, 29 Jun 2023 10:33:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1688060005; x=1690652005; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=OEQykyD0KT22kzYXqODKP8he32dOMNAxzx/noD9wbNY=; b=GVRf7E5ThfWt41rt28OV/CiAIDNOoA1OwKzYGV0t/bTSoUQJpYTIrFRF5YcoVKTANn rJPbGz286Ls92KLyAPWBbSXZpYXwH8u2PG7viwqKXF75k3UIZQjGpt76ox43++SbDll6 2oSnCds8bAM6zR2TADR8XV1liaN1PRYNMtfBrO5KYqg2Cjo7ICZ7KeK1o+9oQMf1jLvW D7hQCKtktd1hpgcoh1C+Dxgyq+TLDSuU1Ln3aWU6gIJH8yeHJSPoqvahJIAIJbI3bPNI yvjcpLfXc63XzrzHN5k84yNGZPHCGD/jqSOjr5DqtO96FoA7RBy21sGaEdjFmNjdEAH5 QaFw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688060005; x=1690652005; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=OEQykyD0KT22kzYXqODKP8he32dOMNAxzx/noD9wbNY=; b=Mvz68jJj2gYXzX2RJfuVBe+9T4vYavyoswSpqH0pQoVlOnT8FkMc0jl0BX0BuCp5ay 07f4Sc5th87prS65soYqb1psMEls0MXzKZS6/T/ajRM8NvNxC0bApl+P63UpsEbN+iQf BMNGd6KmRZOcE5dtP0buTk7G3gaqoP8G2TbbaFJ9bu8AcO/025wM8AY/TIDVvZt9pFQD Ps6HZ/7cDls+Psf6w/uabxTEzNxgAurPDGwYhori6Jbl/X+bwGgpgWh8wsJkHM/HrHrT tGNCj+2fcCGtyOGsWdRmUTL/pjv1eABFH8aJW0iJc74lMz1IHjdePfEOXGrqv7ap+25E R9og== X-Gm-Message-State: ABy/qLaJv6hX9JjsFVFenOhfhqmD6tzegMPFnGpWJB7uK147deaKj7JI Zum8BgTuDbRiBbtFxUJMnKaCTGriglQ= X-Google-Smtp-Source: APBJJlFoNoR/TbYPTPSFeXfNvf8pFHgTO30dQhZxO8gPJf75sZnPCB3QIF5vXpigrKLy0Xy0rkWZQA== X-Received: by 2002:a05:6a00:3a1a:b0:679:9639:1f6a with SMTP id fj26-20020a056a003a1a00b0067996391f6amr556791pfb.14.1688060005061; Thu, 29 Jun 2023 10:33:25 -0700 (PDT) Received: from bilid.c.googlers.com.com (30.161.125.34.bc.googleusercontent.com. [34.125.161.30]) by smtp.gmail.com with ESMTPSA id n7-20020aa78a47000000b00678339238d3sm6293553pfa.35.2023.06.29.10.33.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Jun 2023 10:33:24 -0700 (PDT) From: Bili Dong To: dev@dpdk.org Cc: cristian.dumitrescu@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com, vladimir.medvedkin@intel.com, Bili Dong Subject: [PATCH v8] hash: add XOR32 hash function Date: Thu, 29 Jun 2023 17:33:00 +0000 Message-ID: <20230629173304.2195376-1-qobilidop@gmail.com> X-Mailer: git-send-email 2.41.0.162.gfafddb0af9-goog In-Reply-To: <20230620191253.3218830-1-qobilidop@gmail.com> References: <20230620191253.3218830-1-qobilidop@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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 An XOR32 hash is needed in the Software Switch (SWX) Pipeline for its use case in P4. We implement it in this patch so it could be easily registered in the pipeline later. Signed-off-by: Bili Dong --- v8: * Removed unnecessary helper function. (re Vladimir Medvedkin ) v7: * Simplified byte ordering conversion logic. (re Vladimir Medvedkin ) * Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin ) * Adopted a better way to access bytes. (re Mattias Rönnblom ) * Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom ) .mailmap | 1 + app/test/test_hash_functions.c | 47 +++++++++++---- lib/hash/rte_hash_xor.h | 101 +++++++++++++++++++++++++++++++++ 3 files changed, 139 insertions(+), 10 deletions(-) create mode 100644 lib/hash/rte_hash_xor.h diff --git a/.mailmap b/.mailmap index 8e3940a253..997d89388f 100644 --- a/.mailmap +++ b/.mailmap @@ -164,6 +164,7 @@ Bernard Iremonger Bert van Leeuwen Bhagyada Modali Bharat Mota +Bili Dong Bill Hong Billy McFall Billy O'Mahony diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c index 76d51b6e71..61f1341cbc 100644 --- a/app/test/test_hash_functions.c +++ b/app/test/test_hash_functions.c @@ -15,6 +15,7 @@ #include #include #include +#include #include "test.h" @@ -22,35 +23,48 @@ * Hash values calculated for key sizes from array "hashtest_key_lens" * and for initial values from array "hashtest_initvals. * Each key will be formed by increasing each byte by 1: - * e.g.: key size = 4, key = 0x03020100 - * key size = 8, key = 0x0706050403020100 + * e.g.: key size = 4, key = 0x00010203 + * key size = 8, key = 0x0001020304050607 */ -static uint32_t hash_values_jhash[2][12] = {{ - 0x8ba9414b, 0xdf0d39c9, +static uint32_t hash_values_jhash[2][14] = {{ + 0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8, 0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe, 0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816, 0x12926a31, 0x1c9fa888 }, { - 0x5c62c303, 0x1b8cf784, + 0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928, 0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f, 0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494, 0x91d0e462, 0x768087fc } }; -static uint32_t hash_values_crc[2][12] = {{ - 0x00000000, 0xf26b8303, +static uint32_t hash_values_crc[2][14] = {{ + 0x00000000, 0xf26b8303, 0xf299e880, 0x18678721, 0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4, 0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e, 0x43f44466, 0x4a11475e }, { - 0xbdfd3980, 0x70204542, + 0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1, 0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c, 0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539, 0x789c104f, 0x53028d3e } }; +static uint32_t hash_values_xor32[2][14] = {{ + 0x00000000, 0x00010000, 0x00010200, 0x4040403, + 0x00010203, 0x04040404, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f, + 0x04212223, 0x04040404 +}, +{ + 0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec, + 0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef, + 0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0, + 0xda8c9ccc, 0xdaa9baeb +} +}; /******************************************************************************* * Hash function performance test configuration section. Each performance test @@ -61,10 +75,10 @@ static uint32_t hash_values_crc[2][12] = {{ */ #define HASHTEST_ITERATIONS 1000000 #define MAX_KEYSIZE 64 -static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc}; +static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hash_xor32}; static uint32_t hashtest_initvals[] = {0, 0xdeadbeef}; static uint32_t hashtest_key_lens[] = { - 1, 2, /* Unusual key sizes */ + 1, 2, 3, 7, /* Unusual key sizes */ 4, 8, 16, 32, 48, 64, /* standard key sizes */ 9, /* IPv4 SRC + DST + protocol, unpadded */ 13, /* IPv4 5-tuple, unpadded */ @@ -85,6 +99,9 @@ get_hash_name(rte_hash_function f) if (f == rte_hash_crc) return "rte_hash_crc"; + if (f == rte_hash_xor32) + return "rte_hash_xor32"; + return "UnknownHash"; } @@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void) hash_values_crc[j][i], hash); return -1; } + + hash = rte_hash_xor32(key, hashtest_key_lens[i], + hashtest_initvals[j]); + if (hash != hash_values_xor32[j][i]) { + printf("XOR32 for %u bytes with initial value 0x%x." + " Expected 0x%x, but got 0x%x\n", + hashtest_key_lens[i], hashtest_initvals[j], + hash_values_xor32[j][i], hash); + return -1; + } } } diff --git a/lib/hash/rte_hash_xor.h b/lib/hash/rte_hash_xor.h new file mode 100644 index 0000000000..223154b45c --- /dev/null +++ b/lib/hash/rte_hash_xor.h @@ -0,0 +1,101 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Intel Corporation + */ + +#ifndef _RTE_HASH_XOR_H_ +#define _RTE_HASH_XOR_H_ + +/** + * @file + * + * RTE XOR Hash + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#include + +#include +#include + +/** + * The following bytes access helper functions are expected to work + * without any particular input buffer alignment requirements. + */ + +static inline uint64_t +rte_hash_access64(const void *data) +{ + uint64_t v; + memcpy(&v, data, sizeof(v)); + return v; +} + +static inline uint32_t +rte_hash_access32(const void *data) +{ + uint32_t v; + memcpy(&v, data, sizeof(v)); + return v; +} + +static inline uint16_t +rte_hash_access16(const void *data) +{ + uint16_t v; + memcpy(&v, data, sizeof(v)); + return v; +} + +/** + * Calculate XOR32 hash on user-supplied byte array. + * + * @param data + * Data to perform hash on. + * @param data_len + * How many bytes to use to calculate hash value. + * @param init_val + * Value to initialise hash generator. + * @return + * 32bit calculated hash value. + */ +static inline uint32_t +rte_hash_xor32(const void *data, uint32_t data_len, uint32_t init_val) +{ + uint32_t hash32 = init_val; + uint64_t hash64 = 0; + + /* Batch process in 8 bytes for better performance. */ + uint32_t i; + for (i = 0; i < data_len / 8; i++) { + hash64 ^= rte_hash_access64(data); + data = RTE_PTR_ADD(data, 8); + } + + if (data_len & 0x4) { + hash64 ^= rte_hash_access32(data); + data = RTE_PTR_ADD(data, 4); + } + + /* Deal with remaining (< 4) bytes. */ + uint8_t bit_offset = 0; + if (data_len & 0x2) { + hash64 ^= rte_hash_access16(data); + data = RTE_PTR_ADD(data, 2); + bit_offset += 16; + + } + if (data_len & 0x1) + hash64 ^= (*(const uint8_t *)data) << bit_offset; + + hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32)); + return hash32; +} + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_HASH_XOR_H_ */ -- 2.34.1