From a245d90a898c2e1a77258aeb4b8a189ec771e804 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 18:41:02 +0200 Subject: test: siphash24 - add regression test --- .gitignore | 1 + Makefile.am | 7 +++++++ src/test/test-siphash24.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 55 insertions(+) create mode 100644 src/test/test-siphash24.c diff --git a/.gitignore b/.gitignore index 6149b01c6c..709c8b53d0 100644 --- a/.gitignore +++ b/.gitignore @@ -249,6 +249,7 @@ /test-sched-prio /test-set /test-sigbus +/test-siphash24 /test-sleep /test-socket-util /test-ssd diff --git a/Makefile.am b/Makefile.am index 30989bfe8e..685d2634cd 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1396,6 +1396,7 @@ tests += \ test-path \ test-path-util \ test-strxcpyx \ + test-siphash24 \ test-unit-name \ test-unit-file \ test-utf8 \ @@ -2010,6 +2011,12 @@ test_execute_CFLAGS = \ test_execute_LDADD = \ libcore.la +test_siphash24_SOURCES = \ + src/test/test-siphash24.c + +test_siphash24_LDADD = \ + libshared.la + test_strxcpyx_SOURCES = \ src/test/test-strxcpyx.c diff --git a/src/test/test-siphash24.c b/src/test/test-siphash24.c new file mode 100644 index 0000000000..ec9f64686f --- /dev/null +++ b/src/test/test-siphash24.c @@ -0,0 +1,47 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +/*** + This file is part of systemd. + + Copyright 2015 Tom Gundersen + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "util.h" +#include "siphash24.h" + +#define ITERATIONS 10000000ULL + +/* see https://131002.net/siphash/siphash.pdf, Appendix A */ +int main(int argc, char *argv[]) { + const uint8_t in[15] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e }; + const uint8_t key[16] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f}; + uint64_t out = 0; + unsigned k; + usec_t ts; + + siphash24((uint8_t *)&out, in, sizeof(in), key); + + assert_se(out == 0xa129ca6149be45e5ULL); + + ts = now(CLOCK_MONOTONIC); + for (k = 0; k < ITERATIONS; k++) + siphash24((uint8_t *)&out, in, sizeof(in), key); + ts = now(CLOCK_MONOTONIC) - ts; + + log_info("%llu iterations per second", (ITERATIONS * USEC_PER_SEC) / ts); +} -- cgit v1.2.3-54-g00ecf From 708684ef227eadafc0a2e8dff04879d6cc29d0f1 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 20:09:43 +0200 Subject: siphash24: introduce state struct Encapsulate the four state variables in a struct so we can more easily pass them around. --- src/basic/siphash24.c | 96 +++++++++++++++++++++++++++++---------------------- 1 file changed, 54 insertions(+), 42 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index f68bd283a1..66e5a6105b 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -44,49 +44,61 @@ typedef uint8_t u8; ((u64)((p)[6]) << 48) | \ ((u64)((p)[7]) << 56)) -#define SIPROUND \ +#define SIPROUND(state) \ do { \ - v0 += v1; v1=ROTL(v1,13); v1 ^= v0; v0=ROTL(v0,32); \ - v2 += v3; v3=ROTL(v3,16); v3 ^= v2; \ - v0 += v3; v3=ROTL(v3,21); v3 ^= v0; \ - v2 += v1; v1=ROTL(v1,17); v1 ^= v2; v2=ROTL(v2,32); \ + (state)->v0 += (state)->v1; (state)->v1=ROTL((state)->v1,13); (state)->v1 ^= (state)->v0; (state)->v0=ROTL((state)->v0,32); \ + (state)->v2 += (state)->v3; (state)->v3=ROTL((state)->v3,16); (state)->v3 ^= (state)->v2; \ + (state)->v0 += (state)->v3; (state)->v3=ROTL((state)->v3,21); (state)->v3 ^= (state)->v0; \ + (state)->v2 += (state)->v1; (state)->v1=ROTL((state)->v1,17); (state)->v1 ^= (state)->v2; (state)->v2=ROTL((state)->v2,32); \ } while(0) +struct siphash { + u64 v0; + u64 v1; + u64 v2; + u64 v3; +}; + +static void siphash_init(struct siphash *state, const uint8_t k[16]) { + u64 k0, k1; + + k0 = U8TO64_LE( k ); + k1 = U8TO64_LE( k + 8 ); + + /* "somepseudorandomlygeneratedbytes" */ + state->v0 = 0x736f6d6570736575ULL ^ k0; + state->v1 = 0x646f72616e646f6dULL ^ k1; + state->v2 = 0x6c7967656e657261ULL ^ k0; + state->v3 = 0x7465646279746573ULL ^ k1; +} + /* SipHash-2-4 */ void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16]) { - /* "somepseudorandomlygeneratedbytes" */ - u64 v0 = 0x736f6d6570736575ULL; - u64 v1 = 0x646f72616e646f6dULL; - u64 v2 = 0x6c7967656e657261ULL; - u64 v3 = 0x7465646279746573ULL; + struct siphash state; u64 b; - u64 k0 = U8TO64_LE( k ); - u64 k1 = U8TO64_LE( k + 8 ); u64 m; const u8 *in = _in; const u8 *end = in + inlen - ( inlen % sizeof( u64 ) ); const int left = inlen & 7; b = ( ( u64 )inlen ) << 56; - v3 ^= k1; - v2 ^= k0; - v1 ^= k1; - v0 ^= k0; + + siphash_init(&state, k); for ( ; in != end; in += 8 ) { m = U8TO64_LE( in ); #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( v0 >> 32 ), ( u32 )v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( v1 >> 32 ), ( u32 )v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( v2 >> 32 ), ( u32 )v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( v3 >> 32 ), ( u32 )v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); printf( "(%3d) compress %08x %08x\n", ( int )inlen, ( u32 )( m >> 32 ), ( u32 )m ); #endif - v3 ^= m; - SIPROUND; - SIPROUND; - v0 ^= m; + state.v3 ^= m; + SIPROUND(&state); + SIPROUND(&state); + state.v0 ^= m; } switch( left ) @@ -109,27 +121,27 @@ void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16 } #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( v0 >> 32 ), ( u32 )v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( v1 >> 32 ), ( u32 )v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( v2 >> 32 ), ( u32 )v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( v3 >> 32 ), ( u32 )v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); printf( "(%3d) padding %08x %08x\n", ( int )inlen, ( u32 )( b >> 32 ), ( u32 )b ); #endif - v3 ^= b; - SIPROUND; - SIPROUND; - v0 ^= b; + state.v3 ^= b; + SIPROUND(&state); + SIPROUND(&state); + state.v0 ^= b; #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( v0 >> 32 ), ( u32 )v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( v1 >> 32 ), ( u32 )v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( v2 >> 32 ), ( u32 )v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( v3 >> 32 ), ( u32 )v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); #endif - v2 ^= 0xff; - SIPROUND; - SIPROUND; - SIPROUND; - SIPROUND; - b = v0 ^ v1 ^ v2 ^ v3; + state.v2 ^= 0xff; + SIPROUND(&state); + SIPROUND(&state); + SIPROUND(&state); + SIPROUND(&state); + b = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; U64TO8_LE( out, b ); } -- cgit v1.2.3-54-g00ecf From 9e77e048d412814bb14fb13cd811973a8e6e5f56 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 20:14:18 +0200 Subject: siphash24: split out the finalization step --- src/basic/siphash24.c | 19 +++++++++++++------ 1 file changed, 13 insertions(+), 6 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index 66e5a6105b..e7adfe48c8 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -72,6 +72,16 @@ static void siphash_init(struct siphash *state, const uint8_t k[16]) { state->v3 = 0x7465646279746573ULL ^ k1; } +static u64 siphash24_finalize(struct siphash *state) { + state->v2 ^= 0xff; + SIPROUND(state); + SIPROUND(state); + SIPROUND(state); + SIPROUND(state); + + return state->v0 ^ state->v1 ^ state->v2 ^ state->v3; +} + /* SipHash-2-4 */ void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16]) { @@ -137,11 +147,8 @@ void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16 printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); #endif - state.v2 ^= 0xff; - SIPROUND(&state); - SIPROUND(&state); - SIPROUND(&state); - SIPROUND(&state); - b = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; + + b = siphash24_finalize(&state); + U64TO8_LE( out, b ); } -- cgit v1.2.3-54-g00ecf From c7b68d84e48b3bd87520cbd87258bb03a1810e70 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 20:21:01 +0200 Subject: siphash24: split out the compression step --- src/basic/siphash24.c | 79 ++++++++++++++++++++++++++++----------------------- 1 file changed, 43 insertions(+), 36 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index e7adfe48c8..86d4975ff4 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -72,43 +72,29 @@ static void siphash_init(struct siphash *state, const uint8_t k[16]) { state->v3 = 0x7465646279746573ULL ^ k1; } -static u64 siphash24_finalize(struct siphash *state) { - state->v2 ^= 0xff; - SIPROUND(state); - SIPROUND(state); - SIPROUND(state); - SIPROUND(state); - - return state->v0 ^ state->v1 ^ state->v2 ^ state->v3; -} - -/* SipHash-2-4 */ -void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16]) -{ - struct siphash state; +static void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) { u64 b; u64 m; const u8 *in = _in; const u8 *end = in + inlen - ( inlen % sizeof( u64 ) ); const int left = inlen & 7; - b = ( ( u64 )inlen ) << 56; - siphash_init(&state, k); + b = ( ( u64 )inlen ) << 56; for ( ; in != end; in += 8 ) { m = U8TO64_LE( in ); #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); printf( "(%3d) compress %08x %08x\n", ( int )inlen, ( u32 )( m >> 32 ), ( u32 )m ); #endif - state.v3 ^= m; - SIPROUND(&state); - SIPROUND(&state); - state.v0 ^= m; + state->v3 ^= m; + SIPROUND(state); + SIPROUND(state); + state->v0 ^= m; } switch( left ) @@ -131,22 +117,43 @@ void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16 } #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); printf( "(%3d) padding %08x %08x\n", ( int )inlen, ( u32 )( b >> 32 ), ( u32 )b ); #endif - state.v3 ^= b; - SIPROUND(&state); - SIPROUND(&state); - state.v0 ^= b; + state->v3 ^= b; + SIPROUND(state); + SIPROUND(state); + state->v0 ^= b; #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state.v0 >> 32 ), ( u32 )state.v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state.v1 >> 32 ), ( u32 )state.v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state.v2 >> 32 ), ( u32 )state.v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state.v3 >> 32 ), ( u32 )state.v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); #endif +} + +static u64 siphash24_finalize(struct siphash *state) { + state->v2 ^= 0xff; + SIPROUND(state); + SIPROUND(state); + SIPROUND(state); + SIPROUND(state); + + return state->v0 ^ state->v1 ^ state->v2 ^ state->v3; +} + +/* SipHash-2-4 */ +void siphash24(uint8_t out[8], const void *_in, size_t inlen, const uint8_t k[16]) +{ + struct siphash state; + u64 b; + + siphash_init(&state, k); + + siphash24_compress(_in, inlen, &state); b = siphash24_finalize(&state); -- cgit v1.2.3-54-g00ecf From f2936011c535b73a712990af34555daad21edfe0 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 21:27:25 +0200 Subject: siphash24: move last compression iteration from compression step to finalization step The last compression is special as it deals with the length byte, and padding. Move it to the finalization step in preparation for making compression decomposable. --- src/basic/siphash24.c | 58 ++++++++++++++++++++++++++++----------------------- 1 file changed, 32 insertions(+), 26 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index 86d4975ff4..8f2f1f5534 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -57,6 +57,8 @@ struct siphash { u64 v1; u64 v2; u64 v3; + u64 padding; + size_t inlen; }; static void siphash_init(struct siphash *state, const uint8_t k[16]) { @@ -70,26 +72,27 @@ static void siphash_init(struct siphash *state, const uint8_t k[16]) { state->v1 = 0x646f72616e646f6dULL ^ k1; state->v2 = 0x6c7967656e657261ULL ^ k0; state->v3 = 0x7465646279746573ULL ^ k1; + state->padding = 0; + state->inlen = 0; } static void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) { - u64 b; u64 m; const u8 *in = _in; const u8 *end = in + inlen - ( inlen % sizeof( u64 ) ); const int left = inlen & 7; - b = ( ( u64 )inlen ) << 56; + state->inlen = inlen; for ( ; in != end; in += 8 ) { m = U8TO64_LE( in ); #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); - printf( "(%3d) compress %08x %08x\n", ( int )inlen, ( u32 )( m >> 32 ), ( u32 )m ); + printf( "(%3d) v0 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); + printf( "(%3d) compress %08x %08x\n", ( int )state->inlen, ( u32 )( m >> 32 ), ( u32 )m ); #endif state->v3 ^= m; SIPROUND(state); @@ -99,43 +102,46 @@ static void siphash24_compress(const void *_in, size_t inlen, struct siphash *st switch( left ) { - case 7: b |= ( ( u64 )in[ 6] ) << 48; + case 7: state->padding |= ( ( u64 )in[ 6] ) << 48; - case 6: b |= ( ( u64 )in[ 5] ) << 40; + case 6: state->padding |= ( ( u64 )in[ 5] ) << 40; - case 5: b |= ( ( u64 )in[ 4] ) << 32; + case 5: state->padding |= ( ( u64 )in[ 4] ) << 32; - case 4: b |= ( ( u64 )in[ 3] ) << 24; + case 4: state->padding |= ( ( u64 )in[ 3] ) << 24; - case 3: b |= ( ( u64 )in[ 2] ) << 16; + case 3: state->padding |= ( ( u64 )in[ 2] ) << 16; - case 2: b |= ( ( u64 )in[ 1] ) << 8; + case 2: state->padding |= ( ( u64 )in[ 1] ) << 8; - case 1: b |= ( ( u64 )in[ 0] ); break; + case 1: state->padding |= ( ( u64 )in[ 0] ); break; case 0: break; } +} + +static u64 siphash24_finalize(struct siphash *state) { + u64 b; + b = state->padding | (( ( u64 )state->inlen ) << 56); #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); - printf( "(%3d) padding %08x %08x\n", ( int )inlen, ( u32 )( b >> 32 ), ( u32 )b ); + printf( "(%3d) v0 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); + printf( "(%3d) padding %08x %08x\n", ( int )state->inlen, ( u32 )( state->padding >> 32 ), ( u32 )state->padding ); #endif state->v3 ^= b; SIPROUND(state); SIPROUND(state); state->v0 ^= b; + #ifdef DEBUG - printf( "(%3d) v0 %08x %08x\n", ( int )inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); - printf( "(%3d) v1 %08x %08x\n", ( int )inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); - printf( "(%3d) v2 %08x %08x\n", ( int )inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); - printf( "(%3d) v3 %08x %08x\n", ( int )inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); + printf( "(%3d) v0 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); #endif -} - -static u64 siphash24_finalize(struct siphash *state) { state->v2 ^= 0xff; SIPROUND(state); SIPROUND(state); -- cgit v1.2.3-54-g00ecf From 2c4cc3bdcd18d554cb2ad076516609c69fdd79aa Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sat, 3 Oct 2015 22:21:44 +0200 Subject: siphash24: make siphash24_compress decomposable This allows the input to siphash24_compress to be decomposed into smaller chunks and the function to be called on each individual chunk. --- src/basic/siphash24.c | 37 +++++++++++++++++++++++++++++++++---- 1 file changed, 33 insertions(+), 4 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index 8f2f1f5534..1c827dff1a 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -79,12 +79,39 @@ static void siphash_init(struct siphash *state, const uint8_t k[16]) { static void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) { u64 m; const u8 *in = _in; - const u8 *end = in + inlen - ( inlen % sizeof( u64 ) ); - const int left = inlen & 7; + const u8 *end = in + inlen; + int left = state->inlen & 7; - state->inlen = inlen; + /* update total length */ + state->inlen += inlen; - for ( ; in != end; in += 8 ) + /* if padding exists, fill it out */ + if (left > 0) { + for ( ; in < end && left < 8; in ++, left ++ ) + state->padding |= ( ( u64 )*in ) << (left * 8); + + if (in == end && left < 8) + /* we did not have enough input to fill out the padding completely */ + return; + +#ifdef DEBUG + printf( "(%3d) v0 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v0 >> 32 ), ( u32 )state->v0 ); + printf( "(%3d) v1 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v1 >> 32 ), ( u32 )state->v1 ); + printf( "(%3d) v2 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v2 >> 32 ), ( u32 )state->v2 ); + printf( "(%3d) v3 %08x %08x\n", ( int )state->inlen, ( u32 )( state->v3 >> 32 ), ( u32 )state->v3 ); + printf( "(%3d) compress padding %08x %08x\n", ( int )state->inlen, ( u32 )( state->padding >> 32 ), ( u32 )state->padding ); +#endif + state->v3 ^= state->padding; + SIPROUND(state); + SIPROUND(state); + state->v0 ^= state->padding; + + state->padding = 0; + } + + end -= ( state->inlen % sizeof (u64) ); + + for ( ; in < end; in += 8 ) { m = U8TO64_LE( in ); #ifdef DEBUG @@ -100,6 +127,8 @@ static void siphash24_compress(const void *_in, size_t inlen, struct siphash *st state->v0 ^= m; } + left = state->inlen & 7; + switch( left ) { case 7: state->padding |= ( ( u64 )in[ 6] ) << 48; -- cgit v1.2.3-54-g00ecf From 7c57f504c935a34362d36f514a409f4cbd23a349 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 00:23:25 +0200 Subject: siphash24: expose the internal helper functions --- src/basic/siphash24.c | 15 +++------------ src/basic/siphash24.h | 13 +++++++++++++ 2 files changed, 16 insertions(+), 12 deletions(-) diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index 1c827dff1a..308e4230c5 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -52,16 +52,7 @@ typedef uint8_t u8; (state)->v2 += (state)->v1; (state)->v1=ROTL((state)->v1,17); (state)->v1 ^= (state)->v2; (state)->v2=ROTL((state)->v2,32); \ } while(0) -struct siphash { - u64 v0; - u64 v1; - u64 v2; - u64 v3; - u64 padding; - size_t inlen; -}; - -static void siphash_init(struct siphash *state, const uint8_t k[16]) { +void siphash_init(struct siphash *state, const uint8_t k[16]) { u64 k0, k1; k0 = U8TO64_LE( k ); @@ -76,7 +67,7 @@ static void siphash_init(struct siphash *state, const uint8_t k[16]) { state->inlen = 0; } -static void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) { +void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) { u64 m; const u8 *in = _in; const u8 *end = in + inlen; @@ -149,7 +140,7 @@ static void siphash24_compress(const void *_in, size_t inlen, struct siphash *st } } -static u64 siphash24_finalize(struct siphash *state) { +uint64_t siphash24_finalize(struct siphash *state) { u64 b; b = state->padding | (( ( u64 )state->inlen ) << 56); diff --git a/src/basic/siphash24.h b/src/basic/siphash24.h index 62e1168a79..c107bdd213 100644 --- a/src/basic/siphash24.h +++ b/src/basic/siphash24.h @@ -3,4 +3,17 @@ #include #include +struct siphash { + uint64_t v0; + uint64_t v1; + uint64_t v2; + uint64_t v3; + uint64_t padding; + size_t inlen; +}; + +void siphash_init(struct siphash *state, const uint8_t k[16]); +void siphash24_compress(const void *in, size_t inlen, struct siphash *state); +uint64_t siphash24_finalize(struct siphash *state); + void siphash24(uint8_t out[8], const void *in, size_t inlen, const uint8_t k[16]); -- cgit v1.2.3-54-g00ecf From 1283d704172cb3852c717fe8cfaebe7a56d0aebf Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 00:24:23 +0200 Subject: test: siphash24 - verify internal state and composability Verify the state of the hash-function according to the reference paper, also verify that we can decompose the input and hash the chunks one by one and still get the same result. --- src/test/test-siphash24.c | 33 ++++++++++++++++++++++++++++++++- 1 file changed, 32 insertions(+), 1 deletion(-) diff --git a/src/test/test-siphash24.c b/src/test/test-siphash24.c index ec9f64686f..65eb2b6f35 100644 --- a/src/test/test-siphash24.c +++ b/src/test/test-siphash24.c @@ -26,15 +26,17 @@ /* see https://131002.net/siphash/siphash.pdf, Appendix A */ int main(int argc, char *argv[]) { + struct siphash state = {}; const uint8_t in[15] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e }; const uint8_t key[16] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f}; uint64_t out = 0; - unsigned k; + unsigned i, j, k; usec_t ts; siphash24((uint8_t *)&out, in, sizeof(in), key); + assert_se(out == 0xa129ca6149be45e5); assert_se(out == 0xa129ca6149be45e5ULL); @@ -44,4 +46,33 @@ int main(int argc, char *argv[]) { ts = now(CLOCK_MONOTONIC) - ts; log_info("%llu iterations per second", (ITERATIONS * USEC_PER_SEC) / ts); + + /* verify the internal state as given in the above paper */ + siphash_init(&state, key); + assert_se(state.v0 == 0x7469686173716475); + assert_se(state.v1 == 0x6b617f6d656e6665); + assert_se(state.v2 == 0x6b7f62616d677361); + assert_se(state.v3 == 0x7b6b696e727e6c7b); + siphash24_compress(in, sizeof(in), &state); + assert_se(state.v0 == 0x4a017198de0a59e0); + assert_se(state.v1 == 0x0d52f6f62a4f59a4); + assert_se(state.v2 == 0x634cb3577b01fd3d); + assert_se(state.v3 == 0xa5224d6f55c7d9c8); + assert_se(siphash24_finalize(&state) == 0xa129ca6149be45e5); + assert_se(state.v0 == 0xf6bcd53893fecff1); + assert_se(state.v1 == 0x54b9964c7ea0d937); + assert_se(state.v2 == 0x1b38329c099bb55a); + assert_se(state.v3 == 0x1814bb89ad7be679); + + /* verify that decomposing the input in three chunks gives the + same result */ + for (i = 0; i < sizeof(in); i++) { + for (j = i; j < sizeof(in); j++) { + siphash_init(&state, key); + siphash24_compress(in, i, &state); + siphash24_compress(&in[i], j - i, &state); + siphash24_compress(&in[j], sizeof(in) - j, &state); + assert_se(siphash24_finalize(&state) == 0xa129ca6149be45e5); + } + } } -- cgit v1.2.3-54-g00ecf From 57217c8f2a2dea07b41ecf05000172ce77a90466 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 01:14:41 +0200 Subject: test: hashmap - cripple the hash function by truncating the input rather than the output The reason for the crippled hash function is to reduce the distribution of the hash function, do this by truncating the domain rather than the range. This does introduce a change in behavoir as the range is no longer contiguous, which greatly reduces collisions. This is needed as a follow-up patch will no longer allow individual hash functions to alter the output directly. --- src/test/test-hashmap-plain.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 057b6c1dc1..33ac93b395 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -693,7 +693,7 @@ static void test_hashmap_get2(void) { } static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - return trivial_hash_func(p, hash_key) & 0xff; + return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), hash_key); } static const struct hash_ops crippled_hashmap_ops = { -- cgit v1.2.3-54-g00ecf From b826ab586c9e0a9c0d438a75c28cf3a8ab485929 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 00:22:41 +0200 Subject: hashmap: refactor hash_func All our hash functions are based on siphash24(), factor out siphash_init() and siphash24_finalize() and pass the siphash state to the hash functions rather than the hash key. This simplifies the hash functions, and in particular makes composition simpler as calling siphash24_compress() repeatedly on separate chunks of input has the same effect as first concatenating the input and then calling siphash23_compress() on the result. --- src/basic/hashmap.c | 32 +++++++++++++-------------- src/basic/hashmap.h | 11 ++++----- src/journal/catalog.c | 16 +++----------- src/journal/journald-rate-limit.c | 10 +++++++-- src/libsystemd-network/dhcp-server-internal.h | 2 +- src/libsystemd-network/sd-dhcp-server.c | 13 +++++------ src/libsystemd-network/sd-lldp.c | 9 +++----- src/libsystemd-network/test-dhcp-server.c | 14 +++++++++--- src/libsystemd/sd-bus/bus-objects.c | 19 ++++------------ src/libsystemd/sd-bus/busctl.c | 11 ++++----- src/resolve/resolved-dns-rr.c | 11 +++++---- src/resolve/resolved-dns-server.c | 9 ++++---- src/shared/dns-domain.c | 7 ++---- src/shared/dns-domain.h | 2 +- src/test/test-hashmap-plain.c | 4 ++-- src/test/test-prioq.c | 7 ++---- 16 files changed, 77 insertions(+), 100 deletions(-) diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index 7d2a4160c6..3c05bee56d 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -276,10 +276,8 @@ static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = { }, }; -unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, strlen(p), hash_key); - return (unsigned long) u; +void string_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, strlen(p), state); } int string_compare_func(const void *a, const void *b) { @@ -291,10 +289,8 @@ const struct hash_ops string_hash_ops = { .compare = string_compare_func }; -unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, &p, sizeof(p), hash_key); - return (unsigned long) u; +void trivial_hash_func(const void *p, struct siphash *state) { + siphash24_compress(&p, sizeof(p), state); } int trivial_compare_func(const void *a, const void *b) { @@ -306,10 +302,8 @@ const struct hash_ops trivial_hash_ops = { .compare = trivial_compare_func }; -unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key); - return (unsigned long) u; +void uint64_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, sizeof(uint64_t), state); } int uint64_compare_func(const void *_a, const void *_b) { @@ -325,10 +319,8 @@ const struct hash_ops uint64_hash_ops = { }; #if SIZEOF_DEV_T != 8 -unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key); - return (unsigned long) u; +void devt_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, sizeof(dev_t), state); } int devt_compare_func(const void *_a, const void *_b) { @@ -379,7 +371,13 @@ static uint8_t *hash_key(HashmapBase *h) { } static unsigned base_bucket_hash(HashmapBase *h, const void *p) { - return (unsigned) (h->hash_ops->hash(p, hash_key(h)) % n_buckets(h)); + struct siphash state; + + siphash_init(&state, hash_key(h)); + + h->hash_ops->hash(p, &state); + + return (unsigned) (siphash24_finalize(&state) % n_buckets(h)); } #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p) diff --git a/src/basic/hashmap.h b/src/basic/hashmap.h index 2af23024de..ed6a092d82 100644 --- a/src/basic/hashmap.h +++ b/src/basic/hashmap.h @@ -25,6 +25,7 @@ #include #include "macro.h" +#include "siphash24.h" #include "util.h" /* @@ -67,7 +68,7 @@ typedef struct { #define _IDX_ITERATOR_FIRST (UINT_MAX - 1) #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL }) -typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); +typedef void (*hash_func_t)(const void *p, struct siphash *state); typedef int (*compare_func_t)(const void *a, const void *b); struct hash_ops { @@ -75,28 +76,28 @@ struct hash_ops { compare_func_t compare; }; -unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void string_hash_func(const void *p, struct siphash *state); int string_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops string_hash_ops; /* This will compare the passed pointers directly, and will not * dereference them. This is hence not useful for strings or * suchlike. */ -unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void trivial_hash_func(const void *p, struct siphash *state); int trivial_compare_func(const void *a, const void *b) _const_; extern const struct hash_ops trivial_hash_ops; /* 32bit values we can always just embedd in the pointer itself, but * in order to support 32bit archs we need store 64bit values * indirectly, since they don't fit in a pointer. */ -unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void uint64_hash_func(const void *p, struct siphash *state); int uint64_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops uint64_hash_ops; /* On some archs dev_t is 32bit, and on others 64bit. And sometimes * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */ #if SIZEOF_DEV_T != 8 -unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void devt_hash_func(const void *p, struct siphash *state) _pure_; int devt_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops devt_hash_ops = { .hash = devt_hash_func, diff --git a/src/journal/catalog.c b/src/journal/catalog.c index 78ca4b02e8..4c43500ef5 100644 --- a/src/journal/catalog.c +++ b/src/journal/catalog.c @@ -62,21 +62,11 @@ typedef struct CatalogItem { le64_t offset; } CatalogItem; -static unsigned long catalog_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void catalog_hash_func(const void *p, struct siphash *state) { const CatalogItem *i = p; - uint64_t u; - size_t l, sz; - void *v; - l = strlen(i->language); - sz = sizeof(i->id) + l; - v = alloca(sz); - - memcpy(mempcpy(v, &i->id, sizeof(i->id)), i->language, l); - - siphash24((uint8_t*) &u, v, sz, hash_key); - - return (unsigned long) u; + siphash24_compress(&i->id, sizeof(i->id), state); + siphash24_compress(i->language, strlen(i->language), state); } static int catalog_compare_func(const void *a, const void *b) { diff --git a/src/journal/journald-rate-limit.c b/src/journal/journald-rate-limit.c index 6f83035a4e..7e06117b31 100644 --- a/src/journal/journald-rate-limit.c +++ b/src/journal/journald-rate-limit.c @@ -145,6 +145,7 @@ static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) { static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) { JournalRateLimitGroup *g; + struct siphash state; assert(r); assert(id); @@ -157,7 +158,9 @@ static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, if (!g->id) goto fail; - g->hash = string_hash_func(g->id, r->hash_key); + siphash_init(&state, r->hash_key); + string_hash_func(g->id, &state); + g->hash = siphash24_finalize(&state); journal_rate_limit_vacuum(r, ts); @@ -207,6 +210,7 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u unsigned long h; JournalRateLimitGroup *g; JournalRateLimitPool *p; + struct siphash state; unsigned burst; usec_t ts; @@ -222,7 +226,9 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u ts = now(CLOCK_MONOTONIC); - h = string_hash_func(id, r->hash_key); + siphash_init(&state, r->hash_key); + string_hash_func(id, &state); + h = siphash24_finalize(&state); g = r->buckets[h % BUCKETS_MAX]; LIST_FOREACH(bucket, g, g) diff --git a/src/libsystemd-network/dhcp-server-internal.h b/src/libsystemd-network/dhcp-server-internal.h index 5dc3c7aa26..3b88b93d9a 100644 --- a/src/libsystemd-network/dhcp-server-internal.h +++ b/src/libsystemd-network/dhcp-server-internal.h @@ -96,5 +96,5 @@ int dhcp_server_send_packet(sd_dhcp_server *server, DHCPRequest *req, DHCPPacket *packet, int type, size_t optoffset); -unsigned long client_id_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); +void client_id_hash_func(const void *p, struct siphash *state); int client_id_compare_func(const void *_a, const void *_b); diff --git a/src/libsystemd-network/sd-dhcp-server.c b/src/libsystemd-network/sd-dhcp-server.c index 1f167485e3..4ea5a29e5c 100644 --- a/src/libsystemd-network/sd-dhcp-server.c +++ b/src/libsystemd-network/sd-dhcp-server.c @@ -110,18 +110,14 @@ sd_dhcp_server *sd_dhcp_server_ref(sd_dhcp_server *server) { return server; } -unsigned long client_id_hash_func(const void *p, - const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; +void client_id_hash_func(const void *p, struct siphash *state) { const DHCPClientId *id = p; assert(id); assert(id->length); assert(id->data); - siphash24((uint8_t*) &u, id->data, id->length, hash_key); - - return (unsigned long) u; + siphash24_compress(id->data, id->length, state); } int client_id_compare_func(const void *_a, const void *_b) { @@ -743,13 +739,16 @@ int dhcp_server_handle_message(sd_dhcp_server *server, DHCPMessage *message, if (existing_lease) address = existing_lease->address; else { + struct siphash state; uint32_t next_offer; /* even with no persistence of leases, we try to offer the same client the same IP address. we do this by using the hash of the client id as the offset into the pool of leases when finding the next free one */ - next_offer = client_id_hash_func(&req->client_id, HASH_KEY.bytes) % server->pool_size; + siphash_init(&state, HASH_KEY.bytes); + client_id_hash_func(&req->client_id, &state); + next_offer = siphash24_finalize(&state) % server->pool_size; for (i = 0; i < server->pool_size; i++) { if (!server->bound_leases[next_offer]) { diff --git a/src/libsystemd-network/sd-lldp.c b/src/libsystemd-network/sd-lldp.c index 17512884f5..b9bf4d3c00 100644 --- a/src/libsystemd-network/sd-lldp.c +++ b/src/libsystemd-network/sd-lldp.c @@ -68,16 +68,13 @@ struct sd_lldp { lldp_agent_statistics statistics; }; -static unsigned long chassis_id_hash_func(const void *p, - const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; +static void chassis_id_hash_func(const void *p, struct siphash *state) { const lldp_chassis_id *id = p; assert(id); + assert(id->data); - siphash24((uint8_t *) &u, id->data, id->length, hash_key); - - return (unsigned long) u; + siphash24_compress(id->data, id->length, state); } static int chassis_id_compare_func(const void *_a, const void *_b) { diff --git a/src/libsystemd-network/test-dhcp-server.c b/src/libsystemd-network/test-dhcp-server.c index 7d8a1f6bd9..01205efc18 100644 --- a/src/libsystemd-network/test-dhcp-server.c +++ b/src/libsystemd-network/test-dhcp-server.c @@ -198,6 +198,14 @@ static void test_message_handler(void) { assert_se(dhcp_server_handle_message(server, (DHCPMessage*)&test, sizeof(test)) == 0); } +static uint64_t client_id_hash_helper(DHCPClientId *id, uint8_t key[HASH_KEY_SIZE]) { + struct siphash state; + + siphash_init(&state, key); + client_id_hash_func(id, &state); + return siphash24_finalize(&state); +} + static void test_client_id_hash(void) { DHCPClientId a = { .length = 4, @@ -213,18 +221,18 @@ static void test_client_id_hash(void) { b.data = (uint8_t*)strdup("abcd"); assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); a.length = 3; assert_se(client_id_compare_func(&a, &b) != 0); a.length = 4; assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); b.length = 3; assert_se(client_id_compare_func(&a, &b) != 0); b.length = 4; assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); free(b.data); b.data = (uint8_t*)strdup("abce"); diff --git a/src/libsystemd/sd-bus/bus-objects.c b/src/libsystemd/sd-bus/bus-objects.c index 1d061cb9cf..728f20447a 100644 --- a/src/libsystemd/sd-bus/bus-objects.c +++ b/src/libsystemd/sd-bus/bus-objects.c @@ -1578,25 +1578,14 @@ _public_ int sd_bus_add_fallback( return bus_add_object(bus, slot, true, prefix, callback, userdata); } -static unsigned long vtable_member_hash_func(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void vtable_member_hash_func(const void *a, struct siphash *state) { const struct vtable_member *m = a; - uint8_t hash_key2[HASH_KEY_SIZE]; - unsigned long ret; assert(m); - ret = string_hash_func(m->path, hash_key); - - /* Use a slightly different hash key for the interface */ - memcpy(hash_key2, hash_key, HASH_KEY_SIZE); - hash_key2[0]++; - ret ^= string_hash_func(m->interface, hash_key2); - - /* And an even different one for the member */ - hash_key2[0]++; - ret ^= string_hash_func(m->member, hash_key2); - - return ret; + string_hash_func(m->path, state); + string_hash_func(m->interface, state); + string_hash_func(m->member, state); } static int vtable_member_compare_func(const void *a, const void *b) { diff --git a/src/libsystemd/sd-bus/busctl.c b/src/libsystemd/sd-bus/busctl.c index ab8816942c..496b9a7b4e 100644 --- a/src/libsystemd/sd-bus/busctl.c +++ b/src/libsystemd/sd-bus/busctl.c @@ -628,22 +628,19 @@ typedef struct Member { uint64_t flags; } Member; -static unsigned long member_hash_func(const void *p, const uint8_t hash_key[]) { +static void member_hash_func(const void *p, struct siphash *state) { const Member *m = p; - unsigned long ul; assert(m); assert(m->type); - ul = string_hash_func(m->type, hash_key); + string_hash_func(m->type, state); if (m->name) - ul ^= string_hash_func(m->name, hash_key); + string_hash_func(m->name, state); if (m->interface) - ul ^= string_hash_func(m->interface, hash_key); - - return ul; + string_hash_func(m->interface, state); } static int member_compare_func(const void *a, const void *b) { diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c index fd2f53f40b..2bc8cc1639 100644 --- a/src/resolve/resolved-dns-rr.c +++ b/src/resolve/resolved-dns-rr.c @@ -146,15 +146,14 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key)); } -static unsigned long dns_resource_key_hash_func(const void *i, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void dns_resource_key_hash_func(const void *i, struct siphash *state) { const DnsResourceKey *k = i; - unsigned long ul; - ul = dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), hash_key); - ul = ul * hash_key[0] + ul + k->class; - ul = ul * hash_key[1] + ul + k->type; + assert(k); - return ul; + dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), state); + siphash24_compress(&k->class, sizeof(k->class), state); + siphash24_compress(&k->type, sizeof(k->type), state); } static int dns_resource_key_compare_func(const void *a, const void *b) { diff --git a/src/resolve/resolved-dns-server.c b/src/resolve/resolved-dns-server.c index 2ff5b192df..8693911e65 100644 --- a/src/resolve/resolved-dns-server.c +++ b/src/resolve/resolved-dns-server.c @@ -137,14 +137,13 @@ void dns_server_packet_lost(DnsServer *s, usec_t usec) { s->resend_timeout = MIN(s->resend_timeout * 2, DNS_TIMEOUT_MAX_USEC); } -static unsigned long dns_server_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void dns_server_hash_func(const void *p, struct siphash *state) { const DnsServer *s = p; - uint64_t u; - siphash24((uint8_t*) &u, &s->address, FAMILY_ADDRESS_SIZE(s->family), hash_key); - u = u * hash_key[0] + u + s->family; + assert(s); - return u; + siphash24_compress(&s->family, sizeof(s->family), state); + siphash24_compress(&s->address, FAMILY_ADDRESS_SIZE(s->family), state); } static int dns_server_compare_func(const void *a, const void *b) { diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c index 6dc04d51e4..1517443736 100644 --- a/src/shared/dns-domain.c +++ b/src/shared/dns-domain.c @@ -379,9 +379,8 @@ int dns_name_concat(const char *a, const char *b, char **_ret) { return 0; } -unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]) { +void dns_name_hash_func(const void *s, struct siphash *state) { const char *p = s; - unsigned long ul = hash_key[0]; int r; assert(p); @@ -403,10 +402,8 @@ unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_ label[r] = 0; ascii_strlower(label); - ul = ul * hash_key[1] + ul + string_hash_func(label, hash_key); + string_hash_func(label, state); } - - return ul; } int dns_name_compare_func(const void *a, const void *b) { diff --git a/src/shared/dns-domain.h b/src/shared/dns-domain.h index 8e73d9c20f..1f0d242c18 100644 --- a/src/shared/dns-domain.h +++ b/src/shared/dns-domain.h @@ -54,7 +54,7 @@ static inline int dns_name_is_valid(const char *s) { return 1; } -unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]); +void dns_name_hash_func(const void *s, struct siphash *state); int dns_name_compare_func(const void *a, const void *b); extern const struct hash_ops dns_name_hash_ops; diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 33ac93b395..78f9c19f5b 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -692,8 +692,8 @@ static void test_hashmap_get2(void) { hashmap_free_free_free(m); } -static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), hash_key); +static void crippled_hashmap_func(const void *p, struct siphash *state) { + return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), state); } static const struct hash_ops crippled_hashmap_ops = { diff --git a/src/test/test-prioq.c b/src/test/test-prioq.c index dfedc9b8dc..1e2e42cbca 100644 --- a/src/test/test-prioq.c +++ b/src/test/test-prioq.c @@ -89,13 +89,10 @@ static int test_compare(const void *a, const void *b) { return 0; } -static unsigned long test_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void test_hash(const void *a, struct siphash *state) { const struct test *x = a; - uint64_t u; - siphash24((uint8_t*) &u, &x->value, sizeof(x->value), hash_key); - - return (unsigned long) u; + siphash24_compress(&x->value, sizeof(x->value), state); } static const struct hash_ops test_hash_ops = { -- cgit v1.2.3-54-g00ecf From 1e2527a6fede996a429bd44b30a15e76ee293437 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 01:59:06 +0200 Subject: hashmap: hash_funcs - make inputs unambiguous Make sure all variable-length inputs are properly terminated or that their length is encoded in some way. This avoids ambiguity of adjacent inputs. E.g., in case of a hash function taking two strings, compressing "ab" followed by "c" is now distinct from "a" followed by "bc". --- src/basic/hashmap.c | 2 +- src/libsystemd-network/sd-dhcp-server.c | 1 + src/libsystemd-network/sd-lldp.c | 1 + src/libsystemd/sd-bus/busctl.c | 5 +++++ src/shared/dns-domain.c | 6 ++++++ 5 files changed, 14 insertions(+), 1 deletion(-) diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index 3c05bee56d..3e17ed30df 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -277,7 +277,7 @@ static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = { }; void string_hash_func(const void *p, struct siphash *state) { - siphash24_compress(p, strlen(p), state); + siphash24_compress(p, strlen(p) + 1, state); } int string_compare_func(const void *a, const void *b) { diff --git a/src/libsystemd-network/sd-dhcp-server.c b/src/libsystemd-network/sd-dhcp-server.c index 4ea5a29e5c..d941e6c0de 100644 --- a/src/libsystemd-network/sd-dhcp-server.c +++ b/src/libsystemd-network/sd-dhcp-server.c @@ -117,6 +117,7 @@ void client_id_hash_func(const void *p, struct siphash *state) { assert(id->length); assert(id->data); + siphash24_compress(&id->length, sizeof(id->length), state); siphash24_compress(id->data, id->length, state); } diff --git a/src/libsystemd-network/sd-lldp.c b/src/libsystemd-network/sd-lldp.c index b9bf4d3c00..0b7d35cdf1 100644 --- a/src/libsystemd-network/sd-lldp.c +++ b/src/libsystemd-network/sd-lldp.c @@ -74,6 +74,7 @@ static void chassis_id_hash_func(const void *p, struct siphash *state) { assert(id); assert(id->data); + siphash24_compress(&id->length, sizeof(id->length), state); siphash24_compress(id->data, id->length, state); } diff --git a/src/libsystemd/sd-bus/busctl.c b/src/libsystemd/sd-bus/busctl.c index 496b9a7b4e..49c97af339 100644 --- a/src/libsystemd/sd-bus/busctl.c +++ b/src/libsystemd/sd-bus/busctl.c @@ -630,12 +630,17 @@ typedef struct Member { static void member_hash_func(const void *p, struct siphash *state) { const Member *m = p; + uint64_t arity = 1; assert(m); assert(m->type); string_hash_func(m->type, state); + arity += !!m->name + !!m->interface; + + uint64_hash_func(&arity, state); + if (m->name) string_hash_func(m->name, state); diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c index 1517443736..5680f01bd9 100644 --- a/src/shared/dns-domain.c +++ b/src/shared/dns-domain.c @@ -399,11 +399,17 @@ void dns_name_hash_func(const void *s, struct siphash *state) { if (k > 0) r = k; + if (r == 0) + break; + label[r] = 0; ascii_strlower(label); string_hash_func(label, state); } + + /* enforce that all names are terminated by the empty label */ + string_hash_func("", state); } int dns_name_compare_func(const void *a, const void *b) { -- cgit v1.2.3-54-g00ecf