From 9bf3b53533cdc9b95c921b71da755401f223f765 Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Sun, 22 Dec 2013 19:59:12 +0100 Subject: [PATCH] shared: switch our hash table implementation over to SipHash SipHash appears to be the new gold standard for hashing smaller strings for hashtables these days, so let's make use of it. --- Makefile.am | 2 + src/core/dbus-client-track.c | 4 +- src/core/manager.c | 2 +- src/journal/catalog.c | 34 ++++---- src/journal/catalog.h | 2 +- src/journal/journal-file.c | 4 +- src/journal/journald-rate-limit.c | 12 ++- src/libsystemd-bus/bus-objects.c | 20 +++-- src/libsystemd-dhcp/dhcp-client.c | 7 +- src/login/logind-session.c | 4 +- src/shared/ask-password-api.c | 2 +- src/shared/hashmap.c | 104 +++++++++++------------ src/shared/hashmap.h | 10 ++- src/shared/siphash24.c | 135 ++++++++++++++++++++++++++++++ src/shared/siphash24.h | 6 ++ src/shared/util.c | 60 +++++++------ src/shared/util.h | 15 +++- src/systemd/sd-id128.h | 6 +- src/test/test-prioq.c | 8 +- src/udev/net/link-config.c | 38 +++++---- 20 files changed, 325 insertions(+), 150 deletions(-) create mode 100644 src/shared/siphash24.c create mode 100644 src/shared/siphash24.h diff --git a/Makefile.am b/Makefile.am index 034dfc4a0..66d391103 100644 --- a/Makefile.am +++ b/Makefile.am @@ -694,6 +694,8 @@ libsystemd_shared_la_SOURCES = \ src/shared/time-util.h \ src/shared/hashmap.c \ src/shared/hashmap.h \ + src/shared/siphash24.c \ + src/shared/siphash24.h \ src/shared/set.c \ src/shared/set.h \ src/shared/fdset.c \ diff --git a/src/core/dbus-client-track.c b/src/core/dbus-client-track.c index d98f21d46..07dfea49e 100644 --- a/src/core/dbus-client-track.c +++ b/src/core/dbus-client-track.c @@ -22,10 +22,10 @@ #include "bus-util.h" #include "dbus-client-track.h" -static unsigned tracked_client_hash(const void *a) { +static unsigned long tracked_client_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { const BusTrackedClient *x = a; - return string_hash_func(x->name) ^ PTR_TO_UINT(x->bus); + return string_hash_func(x->name, hash_key) ^ trivial_hash_func(x->bus, hash_key); } static int tracked_client_compare(const void *a, const void *b) { diff --git a/src/core/manager.c b/src/core/manager.c index b9aa6dcfd..d8d5667dc 100644 --- a/src/core/manager.c +++ b/src/core/manager.c @@ -482,7 +482,7 @@ static int manager_setup_notify(Manager *m) { } if (getpid() != 1 || detect_container(NULL) > 0) - snprintf(sa.un.sun_path, sizeof(sa.un.sun_path), NOTIFY_SOCKET "/%llu", random_ull()); + snprintf(sa.un.sun_path, sizeof(sa.un.sun_path), NOTIFY_SOCKET "/%" PRIx64, random_u64()); else strncpy(sa.un.sun_path, NOTIFY_SOCKET, sizeof(sa.un.sun_path)); sa.un.sun_path[0] = 0; diff --git a/src/journal/catalog.c b/src/journal/catalog.c index e3a3354ab..2823232cb 100644 --- a/src/journal/catalog.c +++ b/src/journal/catalog.c @@ -39,6 +39,7 @@ #include "conf-files.h" #include "mkdir.h" #include "catalog.h" +#include "siphash24.h" const char * const catalog_file_dirs[] = { "/usr/local/lib/systemd/catalog/", @@ -63,28 +64,21 @@ typedef struct CatalogItem { le64_t offset; } CatalogItem; -unsigned catalog_hash_func(const void *p) { +unsigned long catalog_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { const CatalogItem *i = p; + uint64_t u; + size_t l, sz; + void *v; - assert_cc(sizeof(unsigned) == sizeof(uint8_t)*4); - - return (((unsigned) i->id.bytes[0] << 24) | - ((unsigned) i->id.bytes[1] << 16) | - ((unsigned) i->id.bytes[2] << 8) | - ((unsigned) i->id.bytes[3])) ^ - (((unsigned) i->id.bytes[4] << 24) | - ((unsigned) i->id.bytes[5] << 16) | - ((unsigned) i->id.bytes[6] << 8) | - ((unsigned) i->id.bytes[7])) ^ - (((unsigned) i->id.bytes[8] << 24) | - ((unsigned) i->id.bytes[9] << 16) | - ((unsigned) i->id.bytes[10] << 8) | - ((unsigned) i->id.bytes[11])) ^ - (((unsigned) i->id.bytes[12] << 24) | - ((unsigned) i->id.bytes[13] << 16) | - ((unsigned) i->id.bytes[14] << 8) | - ((unsigned) i->id.bytes[15])) ^ - string_hash_func(i->language); + 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; } int catalog_compare_func(const void *a, const void *b) { diff --git a/src/journal/catalog.h b/src/journal/catalog.h index 5e15b99ac..fdde67aee 100644 --- a/src/journal/catalog.h +++ b/src/journal/catalog.h @@ -28,7 +28,7 @@ #include "strbuf.h" int catalog_import_file(Hashmap *h, struct strbuf *sb, const char *path); -unsigned catalog_hash_func(const void *p); +unsigned long catalog_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); int catalog_compare_func(const void *a, const void *b) _pure_; int catalog_update(const char* database, const char* root, const char* const* dirs); int catalog_get(const char* database, sd_id128_t id, char **data); diff --git a/src/journal/journal-file.c b/src/journal/journal-file.c index b7e5cf0ab..121b40a58 100644 --- a/src/journal/journal-file.c +++ b/src/journal/journal-file.c @@ -2696,10 +2696,10 @@ int journal_file_open_reliably( /* The file is corrupted. Rotate it away and try it again (but only once) */ l = strlen(fname); - if (asprintf(&p, "%.*s@%016llx-%016llx.journal~", + if (asprintf(&p, "%.*s@%016llx-%016" PRIx64 ".journal~", (int) l - 8, fname, (unsigned long long) now(CLOCK_REALTIME), - random_ull()) < 0) + random_u64()) < 0) return -ENOMEM; r = rename(fname, p); diff --git a/src/journal/journald-rate-limit.c b/src/journal/journald-rate-limit.c index 4b7622152..6d779d296 100644 --- a/src/journal/journald-rate-limit.c +++ b/src/journal/journald-rate-limit.c @@ -56,7 +56,7 @@ struct JournalRateLimitGroup { char *id; JournalRateLimitPool pools[POOLS_MAX]; - unsigned hash; + unsigned long hash; LIST_FIELDS(JournalRateLimitGroup, bucket); LIST_FIELDS(JournalRateLimitGroup, lru); @@ -70,6 +70,8 @@ struct JournalRateLimit { JournalRateLimitGroup *lru, *lru_tail; unsigned n_groups; + + uint8_t hash_key[16]; }; JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) { @@ -84,6 +86,8 @@ JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) { r->interval = interval; r->burst = burst; + random_bytes(r->hash_key, sizeof(r->hash_key)); + return r; } @@ -152,7 +156,7 @@ static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, if (!g->id) goto fail; - g->hash = string_hash_func(g->id); + g->hash = string_hash_func(g->id, r->hash_key); journal_rate_limit_vacuum(r, ts); @@ -199,7 +203,7 @@ static unsigned burst_modulate(unsigned burst, uint64_t available) { } int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) { - unsigned h; + unsigned long h; JournalRateLimitGroup *g; JournalRateLimitPool *p; unsigned burst; @@ -217,7 +221,7 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u ts = now(CLOCK_MONOTONIC); - h = string_hash_func(id); + h = string_hash_func(id, r->hash_key); g = r->buckets[h % BUCKETS_MAX]; LIST_FOREACH(bucket, g, g) diff --git a/src/libsystemd-bus/bus-objects.c b/src/libsystemd-bus/bus-objects.c index 68437f1e3..30f6124b9 100644 --- a/src/libsystemd-bus/bus-objects.c +++ b/src/libsystemd-bus/bus-objects.c @@ -1593,15 +1593,25 @@ static void free_node_vtable(sd_bus *bus, struct node_vtable *w) { free(w); } -static unsigned vtable_member_hash_func(const void *a) { +static unsigned long vtable_member_hash_func(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { const struct vtable_member *m = a; + uint8_t hash_key2[HASH_KEY_SIZE]; + unsigned long ret; assert(m); - return - string_hash_func(m->path) ^ - string_hash_func(m->interface) ^ - string_hash_func(m->member); + 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; } static int vtable_member_compare_func(const void *a, const void *b) { diff --git a/src/libsystemd-dhcp/dhcp-client.c b/src/libsystemd-dhcp/dhcp-client.c index 68a732834..9f7a82621 100644 --- a/src/libsystemd-dhcp/dhcp-client.c +++ b/src/libsystemd-dhcp/dhcp-client.c @@ -540,7 +540,6 @@ static int client_timeout_resend(sd_event_source *s, uint64_t usec, time_left = 60; next_timeout = usec + time_left * USEC_PER_SEC; - break; case DHCP_STATE_INIT: @@ -558,7 +557,7 @@ static int client_timeout_resend(sd_event_source *s, uint64_t usec, break; } - next_timeout += (random_u() & 0x1fffff); + next_timeout += (random_u32() & 0x1fffff); err = sd_event_add_monotonic(client->event, next_timeout, 10 * USEC_PER_MSEC, @@ -894,7 +893,7 @@ static uint64_t client_compute_timeout(uint64_t request_sent, uint32_t lifetime) { return request_sent + (lifetime - 3) * USEC_PER_SEC + - + (random_u() & 0x1fffff); + + (random_u32() & 0x1fffff); } static int client_set_lease_timeouts(sd_dhcp_client *client, uint64_t usec) @@ -1065,7 +1064,7 @@ int sd_dhcp_client_start(sd_dhcp_client *client) assert_return(client->state == DHCP_STATE_INIT || client->state == DHCP_STATE_INIT_REBOOT, -EBUSY); - client->xid = random_u(); + client->xid = random_u32(); r = dhcp_network_bind_raw_socket(client->index, &client->link); diff --git a/src/login/logind-session.c b/src/login/logind-session.c index 10ea52651..dc4b3e162 100644 --- a/src/login/logind-session.c +++ b/src/login/logind-session.c @@ -40,10 +40,10 @@ #include "bus-error.h" #include "logind-session.h" -static unsigned devt_hash_func(const void *p) { +static unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { uint64_t u = *(const dev_t*)p; - return uint64_hash_func(&u); + return uint64_hash_func(&u, hash_key); } static int devt_compare_func(const void *_a, const void *_b) { diff --git a/src/shared/ask-password-api.c b/src/shared/ask-password-api.c index 755abf0b5..c9c82b252 100644 --- a/src/shared/ask-password-api.c +++ b/src/shared/ask-password-api.c @@ -262,7 +262,7 @@ static int create_socket(char **name) { return -errno; } - snprintf(sa.un.sun_path, sizeof(sa.un.sun_path)-1, "/run/systemd/ask-password/sck.%llu", random_ull()); + snprintf(sa.un.sun_path, sizeof(sa.un.sun_path)-1, "/run/systemd/ask-password/sck.%" PRIx64, random_u64()); RUN_WITH_UMASK(0177) { r = bind(fd, &sa.sa, offsetof(struct sockaddr_un, sun_path) + strlen(sa.un.sun_path)); diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c index 3762e3ab0..b1dccaf4e 100644 --- a/src/shared/hashmap.c +++ b/src/shared/hashmap.c @@ -24,13 +24,10 @@ #include #include -#ifdef HAVE_SYS_AUXV_H -#include -#endif - #include "util.h" #include "hashmap.h" #include "macro.h" +#include "siphash24.h" #define INITIAL_N_BUCKETS 31 @@ -50,8 +47,8 @@ struct Hashmap { struct hashmap_entry ** buckets; unsigned n_buckets, n_entries; - unsigned random_xor; - bool from_pool; + uint8_t hash_key[HASH_KEY_SIZE]; + bool from_pool:1; }; struct pool { @@ -134,51 +131,60 @@ __attribute__((destructor)) static void cleanup_pool(void) { #endif -unsigned string_hash_func(const void *p) { - unsigned hash = 5381; - const signed char *c; - - /* DJB's hash function */ - - for (c = p; *c; c++) - hash = (hash << 5) + hash + (unsigned) *c; - - return hash; +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; } int string_compare_func(const void *a, const void *b) { return strcmp(a, b); } -unsigned trivial_hash_func(const void *p) { - return PTR_TO_UINT(p); +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; } int trivial_compare_func(const void *a, const void *b) { return a < b ? -1 : (a > b ? 1 : 0); } -unsigned uint64_hash_func(const void *p) { +unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { uint64_t u; - - assert_cc(sizeof(uint64_t) == 2*sizeof(unsigned)); - - u = *(const uint64_t*) p; - - return (unsigned) ((u >> 32) ^ u); + siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key); + return (unsigned long) u; } int uint64_compare_func(const void *_a, const void *_b) { uint64_t a, b; - a = *(const uint64_t*) _a; b = *(const uint64_t*) _b; - return a < b ? -1 : (a > b ? 1 : 0); } static unsigned bucket_hash(Hashmap *h, const void *p) { - return (h->hash_func(p) ^ h->random_xor) % h->n_buckets; + return (unsigned) (h->hash_func(p, h->hash_key) % h->n_buckets); +} + +static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) { + static uint8_t current[HASH_KEY_SIZE]; + static bool current_initialized = false; + + /* Returns a hash function key to use. In order to keep things + * fast we will not generate a new key each time we allocate a + * new hash table. Instead, we'll just reuse the most recently + * generated one, except if we never generated one or when we + * are rehashing an entire hash table because we reached a + * fill level */ + + if (!current_initialized || !reuse_is_ok) { + random_bytes(current, sizeof(current)); + current_initialized = true; + } + + memcpy(hash_key, current, sizeof(current)); } Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { @@ -214,21 +220,7 @@ Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { h->from_pool = b; - /* Let's randomize our hash functions a bit so that they are - * harder to guess for clients. For this, start out by cheaply - * using some bits the kernel passed into the process using - * the auxiliary vector. If the hashmap grows later on we will - * rehash everything using a new random XOR mask from - * /dev/random. */ -#ifdef HAVE_SYS_AUXV_H - { - void *auxv; - auxv = (void*) getauxval(AT_RANDOM); - h->random_xor = auxv ? *(unsigned*) auxv : random_u(); - } -#else - h->random_xor = random_u(); -#endif + get_hash_key(h->hash_key, true); return h; } @@ -407,7 +399,8 @@ static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *ke static bool resize_buckets(Hashmap *h) { struct hashmap_entry **n, *i; - unsigned m, nxor; + unsigned m; + uint8_t nkey[HASH_KEY_SIZE]; assert(h); @@ -422,15 +415,15 @@ static bool resize_buckets(Hashmap *h) { if (!n) return false; - /* Let's use a different randomized xor value for the + /* Let's use a different randomized hash key for the * extension, so that people cannot guess what we are using * here forever */ - nxor = random_u(); + get_hash_key(nkey, false); for (i = h->iterate_list_head; i; i = i->iterate_next) { - unsigned hash, x; + unsigned long old_bucket, new_bucket; - hash = h->hash_func(i->key); + old_bucket = h->hash_func(i->key, h->hash_key) % h->n_buckets; /* First, drop from old bucket table */ if (i->bucket_next) @@ -439,16 +432,16 @@ static bool resize_buckets(Hashmap *h) { if (i->bucket_previous) i->bucket_previous->bucket_next = i->bucket_next; else - h->buckets[(hash ^ h->random_xor) % h->n_buckets] = i->bucket_next; + h->buckets[old_bucket] = i->bucket_next; /* Then, add to new backet table */ - x = (hash ^ nxor) % m; + new_bucket = h->hash_func(i->key, nkey) % m; - i->bucket_next = n[x]; + i->bucket_next = n[new_bucket]; i->bucket_previous = NULL; - if (n[x]) - n[x]->bucket_previous = i; - n[x] = i; + if (n[new_bucket]) + n[new_bucket]->bucket_previous = i; + n[new_bucket] = i; } if (h->buckets != (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)))) @@ -456,7 +449,8 @@ static bool resize_buckets(Hashmap *h) { h->buckets = n; h->n_buckets = m; - h->random_xor = nxor; + + memcpy(h->hash_key, nkey, HASH_KEY_SIZE); return true; } diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h index b912af8d8..154f68eaf 100644 --- a/src/shared/hashmap.h +++ b/src/shared/hashmap.h @@ -31,6 +31,8 @@ * for all read operations. That way it is not necessary to * instantiate an object for each Hashmap use. */ +#define HASH_KEY_SIZE 16 + typedef struct Hashmap Hashmap; typedef struct _IteratorStruct _IteratorStruct; typedef _IteratorStruct* Iterator; @@ -38,19 +40,19 @@ typedef _IteratorStruct* Iterator; #define ITERATOR_FIRST ((Iterator) 0) #define ITERATOR_LAST ((Iterator) -1) -typedef unsigned (*hash_func_t)(const void *p); +typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); typedef int (*compare_func_t)(const void *a, const void *b); -unsigned string_hash_func(const void *p) _pure_; +unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; int string_compare_func(const void *a, const void *b) _pure_; /* This will compare the passed pointers directly, and will not * dereference them. This is hence not useful for strings or * suchlike. */ -unsigned trivial_hash_func(const void *p) _const_; +unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; int trivial_compare_func(const void *a, const void *b) _const_; -unsigned uint64_hash_func(const void *p) _pure_; +unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; int uint64_compare_func(const void *a, const void *b) _pure_; Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func); diff --git a/src/shared/siphash24.c b/src/shared/siphash24.c new file mode 100644 index 000000000..f68bd283a --- /dev/null +++ b/src/shared/siphash24.c @@ -0,0 +1,135 @@ +/* + SipHash reference C implementation + + Written in 2012 by + Jean-Philippe Aumasson + Daniel J. Bernstein + + To the extent possible under law, the author(s) have dedicated all copyright + and related and neighboring rights to this software to the public domain + worldwide. This software is distributed without any warranty. + + You should have received a copy of the CC0 Public Domain Dedication along with + this software. If not, see . + + (Minimal changes made by Lennart Poettering, to make clean for inclusion in systemd) +*/ +#include +#include +#include + +#include "siphash24.h" + +typedef uint64_t u64; +typedef uint32_t u32; +typedef uint8_t u8; + +#define ROTL(x,b) (u64)( ((x) << (b)) | ( (x) >> (64 - (b))) ) + +#define U32TO8_LE(p, v) \ + (p)[0] = (u8)((v) ); (p)[1] = (u8)((v) >> 8); \ + (p)[2] = (u8)((v) >> 16); (p)[3] = (u8)((v) >> 24); + +#define U64TO8_LE(p, v) \ + U32TO8_LE((p), (u32)((v) )); \ + U32TO8_LE((p) + 4, (u32)((v) >> 32)); + +#define U8TO64_LE(p) \ + (((u64)((p)[0]) ) | \ + ((u64)((p)[1]) << 8) | \ + ((u64)((p)[2]) << 16) | \ + ((u64)((p)[3]) << 24) | \ + ((u64)((p)[4]) << 32) | \ + ((u64)((p)[5]) << 40) | \ + ((u64)((p)[6]) << 48) | \ + ((u64)((p)[7]) << 56)) + +#define SIPROUND \ + 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); \ + } while(0) + +/* 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; + 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; + + 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) compress %08x %08x\n", ( int )inlen, ( u32 )( m >> 32 ), ( u32 )m ); +#endif + v3 ^= m; + SIPROUND; + SIPROUND; + v0 ^= m; + } + + switch( left ) + { + case 7: b |= ( ( u64 )in[ 6] ) << 48; + + case 6: b |= ( ( u64 )in[ 5] ) << 40; + + case 5: b |= ( ( u64 )in[ 4] ) << 32; + + case 4: b |= ( ( u64 )in[ 3] ) << 24; + + case 3: b |= ( ( u64 )in[ 2] ) << 16; + + case 2: b |= ( ( u64 )in[ 1] ) << 8; + + case 1: b |= ( ( u64 )in[ 0] ); break; + + case 0: break; + } + +#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) padding %08x %08x\n", ( int )inlen, ( u32 )( b >> 32 ), ( u32 )b ); +#endif + v3 ^= b; + SIPROUND; + SIPROUND; + 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 ); +#endif + v2 ^= 0xff; + SIPROUND; + SIPROUND; + SIPROUND; + SIPROUND; + b = v0 ^ v1 ^ v2 ^ v3; + U64TO8_LE( out, b ); +} diff --git a/src/shared/siphash24.h b/src/shared/siphash24.h new file mode 100644 index 000000000..62e1168a7 --- /dev/null +++ b/src/shared/siphash24.h @@ -0,0 +1,6 @@ +#pragma once + +#include +#include + +void siphash24(uint8_t out[8], const void *in, size_t inlen, const uint8_t k[16]); diff --git a/src/shared/util.c b/src/shared/util.c index 481c17245..5c9d0bb73 100644 --- a/src/shared/util.c +++ b/src/shared/util.c @@ -61,6 +61,10 @@ #include #undef basename +#ifdef HAVE_SYS_AUXV_H +#include +#endif + #include "macro.h" #include "util.h" #include "ioprio.h" @@ -2345,42 +2349,48 @@ char* dirname_malloc(const char *path) { return dir; } -unsigned long long random_ull(void) { +void random_bytes(void *p, size_t n) { + static bool srand_called = false; _cleanup_close_ int fd; - uint64_t ull; - ssize_t r; + ssize_t k; + uint8_t *q; fd = open("/dev/urandom", O_RDONLY|O_CLOEXEC|O_NOCTTY); if (fd < 0) goto fallback; - r = loop_read(fd, &ull, sizeof(ull), true); - if (r != sizeof(ull)) + k = loop_read(fd, p, n, true); + if (k < 0 || (size_t) k != n) goto fallback; - return ull; + return; fallback: - return random() * RAND_MAX + random(); -} -unsigned random_u(void) { - _cleanup_close_ int fd; - unsigned u; - ssize_t r; + if (!srand_called) { - fd = open("/dev/urandom", O_RDONLY|O_CLOEXEC|O_NOCTTY); - if (fd < 0) - goto fallback; +#ifdef HAVE_SYS_AUXV_H + /* The kernel provides us with a bit of entropy in + * auxv, so let's try to make use of that to seed the + * pseudo-random generator. It's better than + * nothing... */ - r = loop_read(fd, &u, sizeof(u), true); - if (r != sizeof(u)) - goto fallback; + void *auxv; - return u; + auxv = (void*) getauxval(AT_RANDOM); + if (auxv) + srand(*(unsigned*) auxv); + else +#endif + srand(time(NULL) + gettid()); -fallback: - return random() * RAND_MAX + random(); + srand_called = true; + } + + /* If some idiot made /dev/urandom unavailable to us, he'll + * get a PRNG instead. */ + for (q = p; q < (uint8_t*) p + n; q ++) + *q = rand(); } void rename_process(const char name[8]) { @@ -4137,7 +4147,7 @@ int symlink_atomic(const char *from, const char *to) { _cleanup_free_ char *t; const char *fn; size_t k; - unsigned long long ull; + uint64_t u; unsigned i; int r; @@ -4154,10 +4164,10 @@ int symlink_atomic(const char *from, const char *to) { t[k] = '.'; x = stpcpy(t+k+1, fn); - ull = random_ull(); + u = random_u64(); for (i = 0; i < 16; i++) { - *(x++) = hexchar(ull & 0xF); - ull >>= 4; + *(x++) = hexchar(u & 0xF); + u >>= 4; } *x = 0; diff --git a/src/shared/util.h b/src/shared/util.h index 488ce3ba6..338d79c7a 100644 --- a/src/shared/util.h +++ b/src/shared/util.h @@ -249,8 +249,19 @@ int make_stdio(int fd); int make_null_stdio(void); int make_console_stdio(void); -unsigned long long random_ull(void); -unsigned random_u(void); +void random_bytes(void *p, size_t n); + +static inline uint64_t random_u64(void) { + uint64_t u; + random_bytes(&u, sizeof(u)); + return u; +} + +static inline uint32_t random_u32(void) { + uint32_t u; + random_bytes(&u, sizeof(u)); + return u; +} /* For basic lookup tables with strictly enumerated entries */ #define __DEFINE_STRING_TABLE_LOOKUP(name,type,scope) \ diff --git a/src/systemd/sd-id128.h b/src/systemd/sd-id128.h index 015ffb04c..fb82b6fa4 100644 --- a/src/systemd/sd-id128.h +++ b/src/systemd/sd-id128.h @@ -51,7 +51,7 @@ int sd_id128_get_machine(sd_id128_t *ret); int sd_id128_get_boot(sd_id128_t *ret); #define SD_ID128_MAKE(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) \ - ((sd_id128_t) { .bytes = { 0x##v0, 0x##v1, 0x##v2, 0x##v3, 0x##v4, 0x##v5, 0x##v6, 0x##v7, \ + ((const sd_id128_t) { .bytes = { 0x##v0, 0x##v1, 0x##v2, 0x##v3, 0x##v4, 0x##v5, 0x##v6, 0x##v7, \ 0x##v8, 0x##v9, 0x##v10, 0x##v11, 0x##v12, 0x##v13, 0x##v14, 0x##v15 }}) /* Note that SD_ID128_FORMAT_VAL will evaluate the passed argument 16 @@ -63,7 +63,7 @@ int sd_id128_get_boot(sd_id128_t *ret); #define SD_ID128_FORMAT_VAL(x) (x).bytes[0], (x).bytes[1], (x).bytes[2], (x).bytes[3], (x).bytes[4], (x).bytes[5], (x).bytes[6], (x).bytes[7], (x).bytes[8], (x).bytes[9], (x).bytes[10], (x).bytes[11], (x).bytes[12], (x).bytes[13], (x).bytes[14], (x).bytes[15] #define SD_ID128_CONST_STR(x) \ - ((char[SD_ID128_STRING_MAX]) { \ + ((const char[SD_ID128_STRING_MAX]) { \ ((x).bytes[0] >> 4) >= 10 ? 'a' + ((x).bytes[0] >> 4) - 10 : '0' + ((x).bytes[0] >> 4), \ ((x).bytes[0] & 15) >= 10 ? 'a' + ((x).bytes[0] & 15) - 10 : '0' + ((x).bytes[0] & 15), \ ((x).bytes[1] >> 4) >= 10 ? 'a' + ((x).bytes[1] >> 4) - 10 : '0' + ((x).bytes[1] >> 4), \ @@ -102,7 +102,7 @@ _sd_pure_ static inline int sd_id128_equal(sd_id128_t a, sd_id128_t b) { return memcmp(&a, &b, 16) == 0; } -#define SD_ID128_NULL ((sd_id128_t) { .qwords = { 0, 0 }}) +#define SD_ID128_NULL ((const sd_id128_t) { .qwords = { 0, 0 }}) _SD_END_DECLARATIONS; diff --git a/src/test/test-prioq.c b/src/test/test-prioq.c index aeac73973..cdb1e4ad5 100644 --- a/src/test/test-prioq.c +++ b/src/test/test-prioq.c @@ -24,6 +24,7 @@ #include "util.h" #include "set.h" #include "prioq.h" +#include "siphash24.h" #define SET_SIZE 1024*4 @@ -88,10 +89,13 @@ static int test_compare(const void *a, const void *b) { return 0; } -static unsigned test_hash(const void *a) { +static unsigned long test_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { const struct test *x = a; + uint64_t u; - return x->value; + siphash24((uint8_t*) &u, &x->value, sizeof(x->value), hash_key); + + return (unsigned long) u; } static void test_struct(void) { diff --git a/src/udev/net/link-config.c b/src/udev/net/link-config.c index 9b91d9d14..e6618b8cb 100644 --- a/src/udev/net/link-config.c +++ b/src/udev/net/link-config.c @@ -39,6 +39,7 @@ #include "hashmap.h" #include "rtnl-util.h" #include "net-util.h" +#include "siphash24.h" struct link_config_ctx { LIST_HEAD(link_config, links); @@ -301,17 +302,18 @@ static bool mac_is_permanent(struct udev_device *device) { return type == 0; } +#define HASH_KEY SD_ID128_MAKE(d3,1e,48,fa,90,fe,4b,4c,9d,af,d5,d7,a1,b1,2e,8a) + static int get_mac(struct udev_device *device, bool want_random, struct ether_addr *mac) { - unsigned int seed; - int r, i; + int r; if (want_random) - seed = random_u(); + random_bytes(mac->ether_addr_octet, ETH_ALEN); else { const char *name; - sd_id128_t machine; - char machineid_buf[33]; - const char *seed_str; + uint8_t result[8]; + size_t l, sz; + uint8_t *v; /* fetch some persistent data unique (on this machine) to this device */ name = udev_device_get_property_value(device, "ID_NET_NAME_ONBOARD"); @@ -323,22 +325,24 @@ static int get_mac(struct udev_device *device, bool want_random, struct ether_ad return -ENOENT; } } + + l = strlen(name); + sz = sizeof(sd_id128_t) + l; + v = alloca(sz); + /* fetch some persistent data unique to this machine */ - r = sd_id128_get_machine(&machine); + r = sd_id128_get_machine((sd_id128_t*) v); if (r < 0) return r; + memcpy(v + sizeof(sd_id128_t), name, l); - /* combine the data */ - seed_str = strappenda(name, sd_id128_to_string(machine, machineid_buf)); - - /* hash to get seed */ - seed = string_hash_func(seed_str); - } - - srandom(seed); + /* Let's hash the machine ID plus the device name. We + * use a fixed, but originally randomly created hash + * key here. */ + siphash24(result, v, sz, HASH_KEY.bytes); - for (i = 0; i < ETH_ALEN; i++) { - mac->ether_addr_octet[i] = random(); + assert_cc(ETH_ALEN <= sizeof(result)); + memcpy(mac->ether_addr_octet, result, ETH_ALEN); } /* see eth_random_addr in the kernel */ -- 2.30.2