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 2FF1042CE8; Sat, 17 Jun 2023 22:34:47 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id B0ACF4021E; Sat, 17 Jun 2023 22:34:46 +0200 (CEST) Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3]) by mails.dpdk.org (Postfix) with ESMTP id 1595B4021D for ; Sat, 17 Jun 2023 22:34:45 +0200 (CEST) Received: from mail.lysator.liu.se (localhost [127.0.0.1]) by mail.lysator.liu.se (Postfix) with ESMTP id 8A7961F5F2 for ; Sat, 17 Jun 2023 22:34:44 +0200 (CEST) Received: by mail.lysator.liu.se (Postfix, from userid 1004) id 894301F748; Sat, 17 Jun 2023 22:34:44 +0200 (CEST) X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on hermod.lysator.liu.se X-Spam-Level: X-Spam-Status: No, score=-1.5 required=5.0 tests=ALL_TRUSTED, AWL, NICE_REPLY_A, T_SCC_BODY_TEXT_LINE autolearn=disabled version=3.4.6 X-Spam-Score: -1.5 Received: from [192.168.1.59] (h-62-63-215-114.A163.priv.bahnhof.se [62.63.215.114]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.lysator.liu.se (Postfix) with ESMTPSA id 3BBD11F841; Sat, 17 Jun 2023 22:34:43 +0200 (CEST) Message-ID: Date: Sat, 17 Jun 2023 22:34:39 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: [PATCH v6] hash: add XOR32 hash function To: Bili Dong , Vladimir Medvedkin Cc: vladimir.medvedkin@intel.com, dev@dpdk.org, cristian.dumitrescu@intel.com, Bruce Richardson , yipeng1.wang@intel.com, sameh.gobriel@intel.com, Thomas Monjalon References: <20230221175529.644311-1-qobilidop@gmail.com> <20230221193710.717280-1-qobilidop@gmail.com> Content-Language: en-US From: =?UTF-8?Q?Mattias_R=c3=b6nnblom?= In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Virus-Scanned: ClamAV using ClamSMTP 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 On 2023-06-16 19:15, Bili Dong wrote: > Thanks Vladimir for your suggestion! Indeed your version looks cleaner. > > I will make the changes (including the new test case you mentioned) and > prepare a new version this weekend. > > Regards, > Bili > > On Thu, Jun 15, 2023 at 10:15 AM Vladimir Medvedkin > > wrote: > > Hi Bili, > > The rte_hash_xor32() implementation looks a bit messy with respect > to byte ordering, i.e. in case when data_len >= 8 init_val is byte > swapped, but in other cases the data is byte swapped. > Maybe it could be implemented like: > > static inline uint32_t > rte_hash_xor32(const void *data, uint32_t data_len, uint32_t init_val) > { >         const uint8_t *data8 = data; >         uint64_t hash64 = 0; >         uint32_t hash32; >         unsigned int i; > >         for (i = 0; i < data_len / 8; i++) { >                 hash64 ^= *(const uint64_t *)data8; This statement assumes the data is 8-byte aligned. If you change it to something like: uint64_t v; memcpy(&v, data8, sizeof(v)); hash64 ^= v; the compiler will generate code which works without any particular input buffer alignment requirements. The same for 32- and 16-bit accesses. You could also skip the "data8" pointer, and use the DPDK macros for pointer arithmetic (e.g., RTE_PTR_ADD()) to manipulate the original "data" pointer instead. >                 data8 += 8; >         } > >         if (data_len & 0x4) { >                 hash64 ^= *(const uint32_t *)data8; >                 data8 += 4; >         } > >         int bit_offset = 0; > >         if (data_len & 0x2) { >                 hash64 ^= *(const uint16_t *)data8; >                 bit_offset = 16; >                 data8 += 2; >         } > >         if (data_len & 0x1) >                 hash64 ^= *(const uint8_t *)data8 << bit_offset; > >         hash32 = (hash64 >> 32) ^ (uint32_t)hash64; > >         return rte_be_to_cpu_32(hash32) ^ init_val; > } > > What do you think? > > Also, consider to check in hash_functions_autotest keys with length > equal to 3 (or eq 3 mod 4, for example 7 or 11) > > вт, 21 февр. 2023 г. в 19:37, Bili Dong >: > > 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 > > --- >  .mailmap                       |  1 + >  app/test/test_hash_functions.c | 33 +++++++++++-- >  lib/hash/rte_hash_xor.h        | 87 > ++++++++++++++++++++++++++++++++++ >  3 files changed, 118 insertions(+), 3 deletions(-) >  create mode 100644 lib/hash/rte_hash_xor.h > > diff --git a/.mailmap b/.mailmap > index a9f4f28fba..3e9bec29d5 100644 > --- a/.mailmap > +++ b/.mailmap > @@ -159,6 +159,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..53e296fec4 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,8 +23,8 @@ >   * 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, > @@ -51,6 +52,19 @@ static uint32_t hash_values_crc[2][12] = {{ >         0x789c104f, 0x53028d3e >  } >  }; > +static uint32_t hash_values_xor32[2][12] = {{ > +       0x00000000, 0x00010000, > +       0x00010203, 0x04040404, 0x00000000, 0x00000000, > +       0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f, > +       0x04212223, 0x04040404 > +}, > +{ > +       0xdeadbeef, 0xdeacbeef, > +       0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef, > +       0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0, > +       0xda8c9ccc, 0xdaa9baeb > +} > +}; > >  /******************************************************************************* >   * Hash function performance test configuration section. Each > performance test > @@ -61,7 +75,7 @@ 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 */ > @@ -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..366adbe64c > --- /dev/null > +++ b/lib/hash/rte_hash_xor.h > @@ -0,0 +1,87 @@ > +/* 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 > + > +/** > + * 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; > +       const uint8_t *data8 = data; > + > +       /* Minimize byte order conversions depending on data > length. */ > +       if (data_len >= 8) { > +               /* For longer arrays, operate in big endian. */ > +               uint64_t hash64 = rte_cpu_to_be_32(init_val); > + > +               uint32_t i; > +               for (i = 0; i < data_len / 8; i++) { > +                       hash64 ^= *(const uint64_t *)data8; > +                       data8 += 8; > +               } > + > +               if (data_len & 0x4) { > +                       hash64 ^= *(const uint32_t *)data8; > +                       data8 += 4; > +               } > + > +               hash32 = rte_be_to_cpu_32(hash64 ^ (hash64 >> 32)); > +       } else { > +               /* For shorter arrays, operate in host endian. */ > +               hash32 = init_val; > + > +               if (data_len & 0x4) { > +                       hash32 ^= rte_be_to_cpu_32(*(const > uint32_t *)data8); > +                       data8 += 4; > +               } > +       } > + > +       /* Deal with remaining (< 4) bytes. */ > + > +       uint8_t bit_offset = 0; > + > +       if (data_len & 0x2) { > +               hash32 ^= (uint32_t)rte_be_to_cpu_16(*(const > uint16_t *)data8) << 16; > +               data8 += 2; > +               bit_offset += 16; > +       } > + > +       if (data_len & 0x1) > +               hash32 ^= (uint32_t)(*(const uint8_t *)data8) << > (24 - bit_offset); > + > +       return hash32; > +} > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_HASH_XOR_H_ */ > -- > 2.34.1 > > > > -- > Regards, > Vladimir >