chiark / gitweb /
shared: switch our hash table implementation over to SipHash
authorLennart Poettering <lennart@poettering.net>
Sun, 22 Dec 2013 18:59:12 +0000 (19:59 +0100)
committerLennart Poettering <lennart@poettering.net>
Sun, 22 Dec 2013 20:12:25 +0000 (21:12 +0100)
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:
Makefile.am
src/core/dbus-client-track.c
src/core/manager.c
src/journal/catalog.c
src/journal/catalog.h
src/journal/journal-file.c
src/journal/journald-rate-limit.c
src/libsystemd-bus/bus-objects.c
src/libsystemd-dhcp/dhcp-client.c
src/login/logind-session.c
src/shared/ask-password-api.c
src/shared/hashmap.c
src/shared/hashmap.h
src/shared/siphash24.c [new file with mode: 0644]
src/shared/siphash24.h [new file with mode: 0644]
src/shared/util.c
src/shared/util.h
src/systemd/sd-id128.h
src/test/test-prioq.c
src/udev/net/link-config.c

index 034dfc4..66d3911 100644 (file)
@@ -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 \
index d98f21d..07dfea4 100644 (file)
 #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) {
index b9aa6dc..d8d5667 100644 (file)
@@ -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;
index e3a3354..2823232 100644 (file)
@@ -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) {
index 5e15b99..fdde67a 100644 (file)
@@ -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);
index b7e5cf0..121b40a 100644 (file)
@@ -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);
index 4b76221..6d779d2 100644 (file)
@@ -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)
index 68437f1..30f6124 100644 (file)
@@ -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) {
index 68a7328..9f7a826 100644 (file)
@@ -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);
 
index 10ea526..dc4b3e1 100644 (file)
 #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) {
index 755abf0..c9c82b2 100644 (file)
@@ -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));
index 3762e3a..b1dccaf 100644 (file)
 #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;
 }
index b912af8..154f68e 100644 (file)
@@ -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 (file)
index 0000000..f68bd28
--- /dev/null
@@ -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 (file)
index 0000000..62e1168
--- /dev/null
@@ -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]);
index 481c172..5c9d0bb 100644 (file)
 #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;
index 488ce3b..338d79c 100644 (file)
@@ -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)                   \
index 015ffb0..fb82b6f 100644 (file)
@@ -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;
 
index aeac739..cdb1e4a 100644 (file)
@@ -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) {
index 9b91d9d..e6618b8 100644 (file)
@@ -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 */