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.

20 files changed, 325 insertions, 150 deletions

diff --git a/Makefile.am b/Makefile.am
index 034dfc4a09..66d391103c 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 d98f21d46f..07dfea49e6 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 b9aa6dcfd5..d8d5667dc2 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 e3a3354ab7..2823232cbf 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 5e15b99ac0..fdde67aeed 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 b7e5cf0ab5..121b40a583 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 4b76221527..6d779d2966 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 68437f1e37..30f6124b99 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 68a7328348..9f7a826211 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 10ea526517..dc4b3e1621 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 755abf0b5e..c9c82b2520 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 3762e3ab0d..b1dccaf4e7 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -24,13 +24,10 @@
 #include <string.h>
 #include <errno.h>
 
-#ifdef HAVE_SYS_AUXV_H
-#include <sys/auxv.h>
-#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 b912af8d8f..154f68eaf0 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 0000000000..f68bd283a1
--- /dev/null
+++ b/src/shared/siphash24.c
@@ -0,0 +1,135 @@
+/*
+   SipHash reference C implementation
+
+   Written in 2012 by
+   Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+   Daniel J. Bernstein <djb@cr.yp.to>
+
+   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 <http://creativecommons.org/publicdomain/zero/1.0/>.
+
+   (Minimal changes made by Lennart Poettering, to make clean for inclusion in systemd)
+*/
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#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 0000000000..62e1168a79
--- /dev/null
+++ b/src/shared/siphash24.h
@@ -0,0 +1,6 @@
+#pragma once
+
+#include <inttypes.h>
+#include <sys/types.h>
+
+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 481c17245d..5c9d0bb730 100644
--- a/src/shared/util.c
+++ b/src/shared/util.c
@@ -61,6 +61,10 @@
 #include <libgen.h>
 #undef basename
 
+#ifdef HAVE_SYS_AUXV_H
+#include <sys/auxv.h>
+#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 488ce3ba6d..338d79c7ac 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 015ffb04c7..fb82b6fa48 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 aeac73973b..cdb1e4ad52 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 9b91d9d145..e6618b8cbf 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 */