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 5147543B85; Tue, 27 Feb 2024 22:57:12 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id D4F424026E; Tue, 27 Feb 2024 22:57:11 +0100 (CET) Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3]) by mails.dpdk.org (Postfix) with ESMTP id 683D640150 for ; Tue, 27 Feb 2024 22:57:10 +0100 (CET) Received: from mail.lysator.liu.se (localhost [127.0.0.1]) by mail.lysator.liu.se (Postfix) with ESMTP id 1119511105 for ; Tue, 27 Feb 2024 22:57:10 +0100 (CET) Received: by mail.lysator.liu.se (Postfix, from userid 1004) id DB68C10FBF; Tue, 27 Feb 2024 22:57:09 +0100 (CET) X-Spam-Checker-Version: SpamAssassin 4.0.0 (2022-12-13) on hermod.lysator.liu.se X-Spam-Level: X-Spam-Status: No, score=-1.4 required=5.0 tests=ALL_TRUSTED,AWL, T_SCC_BODY_TEXT_LINE autolearn=disabled version=4.0.0 X-Spam-Score: -1.4 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 X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.lysator.liu.se (Postfix) with ESMTPSA id 9424510FBD; Tue, 27 Feb 2024 22:57:07 +0100 (CET) Message-ID: <256907dd-f8d5-4cd4-a51d-e176ae332761@lysator.liu.se> Date: Tue, 27 Feb 2024 22:57:06 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2] lib/hash: add siphash To: Stephen Hemminger , dev@dpdk.org Cc: Yipeng Wang , Sameh Gobriel , Bruce Richardson , Vladimir Medvedkin References: <20240227174012.343004-1-stephen@networkplumber.org> <20240227191437.346593-2-stephen@networkplumber.org> Content-Language: en-US From: =?UTF-8?Q?Mattias_R=C3=B6nnblom?= In-Reply-To: <20240227191437.346593-2-stephen@networkplumber.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit 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 2024-02-27 20:14, Stephen Hemminger wrote: > Add SipHash which is a fast and cryptographicly sound hash > created by Jean-Philippe Aumasson and Daniel J. Bernstein. > Siphash is widely used by Linux, FreeBSD, OpenBSD and other > projects because it is fast and resistant to DoS attacks. > This version is designed to be useful as alternative hash > with cuckoo hash in DPDK. > > Implementation is based of the public domain and Creative > Common license reference version as well as some optimizations > from the GPL-2 or BSD-3 licensed version in Linux. > > Signed-off-by: Stephen Hemminger > --- > v2 - fix non x86 accessor > > app/test/test_hash_functions.c | 71 ++++++++++++++- > lib/hash/meson.build | 2 + > lib/hash/rte_siphash.c | 156 +++++++++++++++++++++++++++++++++ > lib/hash/rte_siphash.h | 84 ++++++++++++++++++ > lib/hash/version.map | 7 ++ > 5 files changed, 316 insertions(+), 4 deletions(-) > create mode 100644 lib/hash/rte_siphash.c > create mode 100644 lib/hash/rte_siphash.h > > diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c > index 70820d1f1976..3bffbe4ed4ba 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" > > @@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{ > } > }; > > +static uint32_t hash_values_hsiphash[2][12] = { > + { > + 0x8e01e473, 0xc41e3669, > + 0x813e4dbd, 0x7ebe2eea, > + 0x33a5c5b7, 0xc910629b, > + 0xba50237f, 0xbbc870c6, > + 0x95124362, 0x850f8e0d, > + 0x192ff266, 0xb41d8206, > + }, { > + 0x66200aa0, 0x769e7201, > + 0x0e934d03, 0x96d7c892, > + 0xb4643534, 0xcb758913, > + 0x498b66e9, 0x116b4082, > + 0x603030dc, 0x644b608b, > + 0x74b29c27, 0x513f3a9c, > + } > +}; > + > +static uint64_t hash_values_siphash[2][12] = { > + { > + 0x8b5a0baa49fbc58d, 0x62c3506f27376c25, > + 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938, > + 0xc902632ed88f897f, 0xab631e00063006f5, > + 0x7b821577565ea3a4, 0x8b19265d1c12cdc7, > + 0x610e7ab6ada60b22, 0x3c6f1970dd62f235, > + 0x4b8db19fd6940031, 0xa43827a530b08989, > + }, { > + 0x86e1bbae2893aaf1, 0x9c05614a696cda03, > + 0x9ee31847083019c3, 0x600e860c97264e31, > + 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e, > + 0xb2d6388922af426f, 0x7d05b8e82e38cf30, > + 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5, > + 0x5622bb0da20658ff, 0x409d76de4adcd475, > + } > +}; > + > /******************************************************************************* > * Hash function performance test configuration section. Each performance test > * will be performed HASHTEST_ITERATIONS times. > @@ -61,9 +98,11 @@ 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 uint32_t hashtest_initvals[] = {0, 0xdeadbeef}; > -static uint32_t hashtest_key_lens[] = { > +static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash}; > +static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef}; > +static const uint64_t hashtest_initkeys[] = {0, UINT64_C(0xfeedc0dedeadbeef)}; > + > +static const uint32_t hashtest_key_lens[] = { > 1, 2, /* Unusual key sizes */ > 4, 8, 16, 32, 48, 64, /* standard key sizes */ > 9, /* IPv4 SRC + DST + protocol, unpadded */ > @@ -85,6 +124,9 @@ get_hash_name(rte_hash_function f) > if (f == rte_hash_crc) > return "rte_hash_crc"; > > + if (f == rte_hsiphash) > + return "hsiphash"; > + > return "UnknownHash"; > } > > @@ -126,6 +168,7 @@ run_hash_func_perf_tests(void) > printf(" Number of iterations for each test = %d\n", > HASHTEST_ITERATIONS); > printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n"); > + fflush(stdout); > > for (i = 0; i < RTE_DIM(hashtest_initvals); i++) { > for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) { > @@ -147,13 +190,15 @@ verify_precalculated_hash_func_tests(void) > { > unsigned i, j; > uint8_t key[64]; > - uint32_t hash; > > for (i = 0; i < 64; i++) > key[i] = (uint8_t) i; > > for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) { > for (j = 0; j < RTE_DIM(hashtest_initvals); j++) { > + uint32_t hash; > + uint64_t shash; > + > hash = rte_jhash(key, hashtest_key_lens[i], > hashtest_initvals[j]); > if (hash != hash_values_jhash[j][i]) { > @@ -173,6 +218,24 @@ verify_precalculated_hash_func_tests(void) > hash_values_crc[j][i], hash); > return -1; > } > + > + hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]); > + if (hash != hash_values_hsiphash[j][i]) { > + printf("Hsiphash 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_hsiphash[j][i], hash); > + return -1; > + } > + > + shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]); > + if (shash != hash_values_siphash[j][i]) { > + printf("siphash for %u bytes with initial %#"PRIx64"." > + "Expected %#"PRIx64", but got %#"PRIx64"\n", > + hashtest_key_lens[i], hashtest_initkeys[j], > + hash_values_siphash[j][i], shash); > + return -1; > + } > } > } > > diff --git a/lib/hash/meson.build b/lib/hash/meson.build > index 277eb9fa9366..913855124d2b 100644 > --- a/lib/hash/meson.build > +++ b/lib/hash/meson.build > @@ -6,6 +6,7 @@ headers = files( > 'rte_hash_crc.h', > 'rte_hash.h', > 'rte_jhash.h', > + 'rte_siphash.h', > 'rte_thash.h', > 'rte_thash_gfni.h', > ) > @@ -21,6 +22,7 @@ sources = files( > 'rte_cuckoo_hash.c', > 'rte_hash_crc.c', > 'rte_fbk_hash.c', > + 'rte_siphash.c', > 'rte_thash.c', > 'rte_thash_gfni.c', > ) > diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c > new file mode 100644 > index 000000000000..75a350f27c19 > --- /dev/null > +++ b/lib/hash/rte_siphash.c > @@ -0,0 +1,156 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * > + * Based on code reference code licensed as CC0 and MIT. > + * Copyright (c) 2012-2022 Jean-Philippe Aumasson > + * Copyright (c) 2012-2014 Daniel J. Bernstein > + */ > + > +#include > + > +#include > +#include "rte_siphash.h" > + > +static __rte_always_inline uint64_t > +rol64(uint64_t x, unsigned int b) > +{ > + return (x << b) | (x >> (64 - b)); > +} > + > +#if defined(RTE_ARCH_X86) > +static __rte_always_inline uint64_t u8to64_le(const uint8_t *p) > +{ > + return *(const uint64_t *)p; > +} > + > +static __rte_always_inline uint32_t u8to32_le(const uint8_t *p) > +{ > + return *(const uint32_t *)p; > +} > + > +static __rte_always_inline uint16_t u8to16_le(const uint8_t *p) > +{ > + return *(const uint16_t *)p; > +} > +#else > +/* Portable version */ > +static __rte_always_inline uint64_t u8to64_le(const uint8_t *p) > +{ > + return (uint64_t)p[0] | (uint64_t)p[1] << 8 | > + (uint64_t)p[2] << 16 | (uint64_t)p[3] << 24 | > + (uint64_t)p[4] << 32 | (uint64_t)p[5] << 40 | > + (uint64_t)p[6] << 48 | (uint64_t)p[7] << 56; > +} > + The portable and x86 version will compile to the same thing on x86. A simpler implementation would be static __rte_always_inline uint64_t u8to64_le(const uint8_t *p) { uint64_t w; memcpy(&w, p, sizeof(w)); return rte_cpu_to_le(w); } ...which probably also compiles to the same code. Do you want the same hash value on big and little endian, or why the conversion? > +static __rte_always_inline uint32_t u8to32_le(const uint8_t *p) > +{ > + return (uint32_t)p[0] | (uint32_t)p[1] << 8 | > + (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; > +} > + > +static __rte_always_inline uint16_t u8to16_le(const uint8_t *p) > +{ > + return (uint16_t)p[0] | (uint16_t)p[1] << 8; > +} > +#endif > + > +#define SIPROUND do { \ > + v0 += v1; \ > + v1 = rol64(v1, 13); \ > + v1 ^= v0; \ > + v0 = rol64(v0, 32); \ > + v2 += v3; \ > + v3 = rol64(v3, 16); \ > + v3 ^= v2; \ > + v0 += v3; \ > + v3 = rol64(v3, 21); \ > + v3 ^= v0; \ > + v2 += v1; \ > + v1 = rol64(v1, 17); \ > + v1 ^= v2; \ > + v2 = rol64(v2, 32); \ > +} while (0) > + > +/* > + * Use a 64bit version of SipHash for both full and > + * half versions, The difference is the number of rounds. > + */ > +static inline uint64_t > +siphash(const uint8_t *data, uint32_t len, uint64_t key[2], > + const unsigned int cround, const unsigned int dround) > +{ > + const uint32_t left = len & 7; > + const uint8_t *end = data + len - left; > + unsigned int i; > + uint64_t m; > + uint64_t v0 = UINT64_C(0x736f6d6570736575); > + uint64_t v1 = UINT64_C(0x646f72616e646f6d); > + uint64_t v2 = UINT64_C(0x6c7967656e657261); > + uint64_t v3 = UINT64_C(0x7465646279746573); > + uint64_t b = (uint64_t)len << 56; > + > + v3 ^= key[1]; > + v2 ^= key[0]; > + v1 ^= key[1]; > + v0 ^= key[0]; > + > + for (; data != end; data += 8) { > + m = u8to64_le(data); > + v3 ^= m; > + > + for (i = 0; i < cround; i++) > + SIPROUND; > + > + v0 ^= m; > + } > + > + switch (left) { > + case 7: > + b |= ((uint64_t)end[6]) << 48; > + /* fallthrough */ > + case 6: > + b |= ((uint64_t)end[5]) << 40; > + /* fallthrough */ > + case 5: > + b |= ((uint64_t)end[4]) << 32; > + /* fallthrough */ > + case 4: > + b |= u8to32_le(end); > + break; > + case 3: > + b |= ((uint64_t)end[2]) << 16; > + /* fallthrough */ > + case 2: > + b |= u8to16_le(end); > + break; > + case 1: > + b |= data[0]; > + } > + > + v3 ^= b; > + for (i = 0; i < cround; i++) > + SIPROUND; > + > + v0 ^= b; > + v2 ^= 0xff; > + > + for (i = 0; i < dround; i++) > + SIPROUND; > + > + return (v0 ^ v1) ^ (v2 ^ v3); > +} > + > +uint64_t > +rte_siphash(const void *data, uint32_t len, uint64_t init_val) > +{ > + uint64_t key[2] = { init_val }; > + > + return siphash(data, len, key, 2, 4); > +} > + > +uint32_t > +rte_hsiphash(const void *data, uint32_t len, uint32_t init_val) > +{ > + uint64_t key[2] = { init_val }; > + > + return siphash(data, len, key, 1, 3); > +} > diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h > new file mode 100644 > index 000000000000..9ac417517f33 > --- /dev/null > +++ b/lib/hash/rte_siphash.h > @@ -0,0 +1,84 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * > + * Based on code reference code licensed as CC0 and MIT. > + * Copyright (c) 2012-2022 Jean-Philippe Aumasson > + * Copyright (c) 2012-2014 Daniel J. Bernstein > + */ > + > +#ifndef _RTE_SIPHASH_H > +#define _RTE_SIPHASH_H > + > +/** > + * @file > + * > + * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages. > + * > + * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense > + * against hash-flooding DoS attacks. > + * > + * SipHash is simpler and faster on short messages than previous cryptographic algorithms, > + * such as MACs based on universal hashing. > + * Competitive in performance with insecure non-cryptographic algorithms. > + * > + * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects > + * by leading cryptographers. > + * > + * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS), > + * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.) > + * and applications (Wireguard, Redis, etc.). > + * > + * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as > + * a secure message authentication code (MAC). But SipHash is not a hash in the sense of > + * general-purpose key-less hash function such as BLAKE3 or SHA-3. > + * SipHash should therefore always be used with a secret key in order to be secure. > + * siphash functions. > + * > + */ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include > + > +#include > + > +/** > + * Compute a SipHash-2-4 > + * uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds. > + * > + * @param data > + * Data to perform hash on. > + * @param len > + * How many bytes to use to calculate hash value. > + * @param initval > + * Value to initialise hash generator. > + * @return > + * 64bit calculated hash value. > + */ > +__rte_experimental > +uint64_t > +rte_siphash(const void *data, uint32_t len, uint64_t init_val); > + > +/** > + * Compute Siphash-1-3; > + * uses a 32 bit key; does 1 compression round, and 3 finalization rounds. > + * > + * @param data > + * Data to perform hash on. > + * @param len > + * How many bytes to use to calculate hash value. > + * @param initval > + * Value to initialise hash generator. > + * @return > + * 32bit calculated hash value. > + */ > +__rte_experimental > +uint32_t > +rte_hsiphash(const void *data, uint32_t len, uint32_t init_val); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_SIPHASH_H */ > diff --git a/lib/hash/version.map b/lib/hash/version.map > index 6b2afebf6b46..16221fc1d8c7 100644 > --- a/lib/hash/version.map > +++ b/lib/hash/version.map > @@ -48,3 +48,10 @@ DPDK_24 { > > local: *; > }; > + > +EXPERIMENTAL { > + global: > + > + rte_siphash; > + rte_hsiphash; > +};