hashmap: refactor hash_func

All our hash functions are based on siphash24(), factor out
siphash_init() and siphash24_finalize() and pass the siphash
state to the hash functions rather than the hash key.

This simplifies the hash functions, and in particular makes
composition simpler as calling siphash24_compress() repeatedly
on separate chunks of input has the same effect as first
concatenating the input and then calling siphash23_compress()
on the result.

diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c
index 7d2a4160c6489c416e7f99ec854e77da336daa27..3c05bee56d7487bdfa135f438f73c52cec16ecc1 100644 (file)
--- a/src/basic/hashmap.c
+++ b/src/basic/hashmap.c
@@ -276,10 +276,8 @@ static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
         },
 };
 
-unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
-        siphash24((uint8_t*) &u, p, strlen(p), hash_key);
-        return (unsigned long) u;
+void string_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, strlen(p), state);
 }
 
 int string_compare_func(const void *a, const void *b) {
@@ -291,10 +289,8 @@ const struct hash_ops string_hash_ops = {
         .compare = string_compare_func
 };
 
-unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
-        siphash24((uint8_t*) &u, &p, sizeof(p), hash_key);
-        return (unsigned long) u;
+void trivial_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(&p, sizeof(p), state);
 }
 
 int trivial_compare_func(const void *a, const void *b) {
@@ -306,10 +302,8 @@ const struct hash_ops trivial_hash_ops = {
         .compare = trivial_compare_func
 };
 
-unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
-        siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key);
-        return (unsigned long) u;
+void uint64_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, sizeof(uint64_t), state);
 }
 
 int uint64_compare_func(const void *_a, const void *_b) {
@@ -325,10 +319,8 @@ const struct hash_ops uint64_hash_ops = {
 };
 
 #if SIZEOF_DEV_T != 8
-unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
-        siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key);
-        return (unsigned long) u;
+void devt_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, sizeof(dev_t), state);
 }
 
 int devt_compare_func(const void *_a, const void *_b) {
@@ -379,7 +371,13 @@ static uint8_t *hash_key(HashmapBase *h) {
 }
 
 static unsigned base_bucket_hash(HashmapBase *h, const void *p) {
-        return (unsigned) (h->hash_ops->hash(p, hash_key(h)) % n_buckets(h));
+        struct siphash state;
+
+        siphash_init(&state, hash_key(h));
+
+        h->hash_ops->hash(p, &state);
+
+        return (unsigned) (siphash24_finalize(&state) % n_buckets(h));
 }
 #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p)
 

diff --git a/src/basic/hashmap.h b/src/basic/hashmap.h
index 2af23024dee8d4058aef259aea4284274bf9310d..ed6a092d82360cb10231736f5ddd87d6083aa99d 100644 (file)
--- a/src/basic/hashmap.h
+++ b/src/basic/hashmap.h
@@ -25,6 +25,7 @@
 #include <stdbool.h>
 
 #include "macro.h"
+#include "siphash24.h"
 #include "util.h"
 
 /*
@@ -67,7 +68,7 @@ typedef struct {
 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
 
-typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
+typedef void (*hash_func_t)(const void *p, struct siphash *state);
 typedef int (*compare_func_t)(const void *a, const void *b);
 
 struct hash_ops {
@@ -75,28 +76,28 @@ struct hash_ops {
         compare_func_t compare;
 };
 
-unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
+void string_hash_func(const void *p, struct siphash *state);
 int string_compare_func(const void *a, const void *b) _pure_;
 extern const struct hash_ops string_hash_ops;
 
 /* This will compare the passed pointers directly, and will not
  * dereference them. This is hence not useful for strings or
  * suchlike. */
-unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
+void trivial_hash_func(const void *p, struct siphash *state);
 int trivial_compare_func(const void *a, const void *b) _const_;
 extern const struct hash_ops trivial_hash_ops;
 
 /* 32bit values we can always just embedd in the pointer itself, but
  * in order to support 32bit archs we need store 64bit values
  * indirectly, since they don't fit in a pointer. */
-unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
+void uint64_hash_func(const void *p, struct siphash *state);
 int uint64_compare_func(const void *a, const void *b) _pure_;
 extern const struct hash_ops uint64_hash_ops;
 
 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
  * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
 #if SIZEOF_DEV_T != 8
-unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
+void devt_hash_func(const void *p, struct siphash *state) _pure_;
 int devt_compare_func(const void *a, const void *b) _pure_;
 extern const struct hash_ops devt_hash_ops = {
         .hash = devt_hash_func,

diff --git a/src/journal/catalog.c b/src/journal/catalog.c
index 78ca4b02e85c7c3ad4578a66d7483a76ea3f7978..4c43500ef5f320a045761d3c7308df2a713fb6ca 100644 (file)
--- a/src/journal/catalog.c
+++ b/src/journal/catalog.c
@@ -62,21 +62,11 @@ typedef struct CatalogItem {
         le64_t offset;
 } CatalogItem;
 
-static unsigned long catalog_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
+static void catalog_hash_func(const void *p, struct siphash *state) {
         const CatalogItem *i = p;
-        uint64_t u;
-        size_t l, sz;
-        void *v;
 
-        l = strlen(i->language);
-        sz = sizeof(i->id) + l;
-        v = alloca(sz);
-
-        memcpy(mempcpy(v, &i->id, sizeof(i->id)), i->language, l);
-
-        siphash24((uint8_t*) &u, v, sz, hash_key);
-
-        return (unsigned long) u;
+        siphash24_compress(&i->id, sizeof(i->id), state);
+        siphash24_compress(i->language, strlen(i->language), state);
 }
 
 static int catalog_compare_func(const void *a, const void *b) {

diff --git a/src/journal/journald-rate-limit.c b/src/journal/journald-rate-limit.c
index 6f83035a4ee36f050bbfb26620c8839e65893a09..7e06117b31de3b5fba94b8cabc8b8ab01b2d03f8 100644 (file)
--- a/src/journal/journald-rate-limit.c
+++ b/src/journal/journald-rate-limit.c
@@ -145,6 +145,7 @@ static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
 
 static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
         JournalRateLimitGroup *g;
+        struct siphash state;
 
         assert(r);
         assert(id);
@@ -157,7 +158,9 @@ static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r,
         if (!g->id)
                 goto fail;
 
-        g->hash = string_hash_func(g->id, r->hash_key);
+        siphash_init(&state, r->hash_key);
+        string_hash_func(g->id, &state);
+        g->hash = siphash24_finalize(&state);
 
         journal_rate_limit_vacuum(r, ts);
 
@@ -207,6 +210,7 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u
         unsigned long h;
         JournalRateLimitGroup *g;
         JournalRateLimitPool *p;
+        struct siphash state;
         unsigned burst;
         usec_t ts;
 
@@ -222,7 +226,9 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u
 
         ts = now(CLOCK_MONOTONIC);
 
-        h = string_hash_func(id, r->hash_key);
+        siphash_init(&state, r->hash_key);
+        string_hash_func(id, &state);
+        h = siphash24_finalize(&state);
         g = r->buckets[h % BUCKETS_MAX];
 
         LIST_FOREACH(bucket, g, g)

diff --git a/src/libsystemd-network/dhcp-server-internal.h b/src/libsystemd-network/dhcp-server-internal.h
index 5dc3c7aa2624d38ea0b4e5a65e29db224468b256..3b88b93d9a5b1ab3a8db7ee259fe56647f465915 100644 (file)
--- a/src/libsystemd-network/dhcp-server-internal.h
+++ b/src/libsystemd-network/dhcp-server-internal.h
@@ -96,5 +96,5 @@ int dhcp_server_send_packet(sd_dhcp_server *server,
                             DHCPRequest *req, DHCPPacket *packet,
                             int type, size_t optoffset);
 
-unsigned long client_id_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
+void client_id_hash_func(const void *p, struct siphash *state);
 int client_id_compare_func(const void *_a, const void *_b);

diff --git a/src/libsystemd-network/sd-dhcp-server.c b/src/libsystemd-network/sd-dhcp-server.c
index 1f167485e333635554c613f13d1061b984a80142..4ea5a29e5c35860713c05085b266d5148b11c093 100644 (file)
--- a/src/libsystemd-network/sd-dhcp-server.c
+++ b/src/libsystemd-network/sd-dhcp-server.c
@@ -110,18 +110,14 @@ sd_dhcp_server *sd_dhcp_server_ref(sd_dhcp_server *server) {
         return server;
 }
 
-unsigned long client_id_hash_func(const void *p,
-                                  const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
+void client_id_hash_func(const void *p, struct siphash *state) {
         const DHCPClientId *id = p;
 
         assert(id);
         assert(id->length);
         assert(id->data);
 
-        siphash24((uint8_t*) &u, id->data, id->length, hash_key);
-
-        return (unsigned long) u;
+        siphash24_compress(id->data, id->length, state);
 }
 
 int client_id_compare_func(const void *_a, const void *_b) {
@@ -743,13 +739,16 @@ int dhcp_server_handle_message(sd_dhcp_server *server, DHCPMessage *message,
                 if (existing_lease)
                         address = existing_lease->address;
                 else {
+                        struct siphash state;
                         uint32_t next_offer;
 
                         /* even with no persistence of leases, we try to offer the same client
                            the same IP address. we do this by using the hash of the client id
                            as the offset into the pool of leases when finding the next free one */
 
-                        next_offer = client_id_hash_func(&req->client_id, HASH_KEY.bytes) % server->pool_size;
+                        siphash_init(&state, HASH_KEY.bytes);
+                        client_id_hash_func(&req->client_id, &state);
+                        next_offer = siphash24_finalize(&state) % server->pool_size;
 
                         for (i = 0; i < server->pool_size; i++) {
                                 if (!server->bound_leases[next_offer]) {

diff --git a/src/libsystemd-network/sd-lldp.c b/src/libsystemd-network/sd-lldp.c
index 17512884f555cfaa2deaaea0b74be276e75a94c8..b9bf4d3c00aeebd5fc39f199201aa45872fa04dd 100644 (file)
--- a/src/libsystemd-network/sd-lldp.c
+++ b/src/libsystemd-network/sd-lldp.c
@@ -68,16 +68,13 @@ struct sd_lldp {
         lldp_agent_statistics statistics;
 };
 
-static unsigned long chassis_id_hash_func(const void *p,
-                                          const uint8_t hash_key[HASH_KEY_SIZE]) {
-        uint64_t u;
+static void chassis_id_hash_func(const void *p, struct siphash *state) {
         const lldp_chassis_id *id = p;
 
         assert(id);
+        assert(id->data);
 
-        siphash24((uint8_t *) &u, id->data, id->length, hash_key);
-
-        return (unsigned long) u;
+        siphash24_compress(id->data, id->length, state);
 }
 
 static int chassis_id_compare_func(const void *_a, const void *_b) {

diff --git a/src/libsystemd-network/test-dhcp-server.c b/src/libsystemd-network/test-dhcp-server.c
index 7d8a1f6bd9bdb27465bceb67ee2992b488f651a3..01205efc1877bd7f008141799f0c2444e76acde4 100644 (file)
--- a/src/libsystemd-network/test-dhcp-server.c
+++ b/src/libsystemd-network/test-dhcp-server.c
@@ -198,6 +198,14 @@ static void test_message_handler(void) {
         assert_se(dhcp_server_handle_message(server, (DHCPMessage*)&test, sizeof(test)) == 0);
 }
 
+static uint64_t client_id_hash_helper(DHCPClientId *id, uint8_t key[HASH_KEY_SIZE]) {
+        struct siphash state;
+
+        siphash_init(&state, key);
+        client_id_hash_func(id, &state);
+        return siphash24_finalize(&state);
+}
+
 static void test_client_id_hash(void) {
         DHCPClientId a = {
                 .length = 4,
@@ -213,18 +221,18 @@ static void test_client_id_hash(void) {
         b.data = (uint8_t*)strdup("abcd");
 
         assert_se(client_id_compare_func(&a, &b) == 0);
-        assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key));
+        assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key));
         a.length = 3;
         assert_se(client_id_compare_func(&a, &b) != 0);
         a.length = 4;
         assert_se(client_id_compare_func(&a, &b) == 0);
-        assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key));
+        assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key));
 
         b.length = 3;
         assert_se(client_id_compare_func(&a, &b) != 0);
         b.length = 4;
         assert_se(client_id_compare_func(&a, &b) == 0);
-        assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key));
+        assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key));
 
         free(b.data);
         b.data = (uint8_t*)strdup("abce");

diff --git a/src/libsystemd/sd-bus/bus-objects.c b/src/libsystemd/sd-bus/bus-objects.c
index 1d061cb9cfe6921ca281db8d80506f127cf04962..728f20447a8405bfd45900cfbde56fe88e8fbfd5 100644 (file)
--- a/src/libsystemd/sd-bus/bus-objects.c
+++ b/src/libsystemd/sd-bus/bus-objects.c
@@ -1578,25 +1578,14 @@ _public_ int sd_bus_add_fallback(
         return bus_add_object(bus, slot, true, prefix, callback, userdata);
 }
 
-static unsigned long vtable_member_hash_func(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) {
+static void vtable_member_hash_func(const void *a, struct siphash *state) {
         const struct vtable_member *m = a;
-        uint8_t hash_key2[HASH_KEY_SIZE];
-        unsigned long ret;
 
         assert(m);
 
-        ret = string_hash_func(m->path, hash_key);
-
-        /* Use a slightly different hash key for the interface */
-        memcpy(hash_key2, hash_key, HASH_KEY_SIZE);
-        hash_key2[0]++;
-        ret ^= string_hash_func(m->interface, hash_key2);
-
-        /* And an even different one for the  member */
-        hash_key2[0]++;
-        ret ^= string_hash_func(m->member, hash_key2);
-
-        return ret;
+        string_hash_func(m->path, state);
+        string_hash_func(m->interface, state);
+        string_hash_func(m->member, state);
 }
 
 static int vtable_member_compare_func(const void *a, const void *b) {

diff --git a/src/libsystemd/sd-bus/busctl.c b/src/libsystemd/sd-bus/busctl.c
index ab8816942c4bcd011161729396991d4cdc27606d..496b9a7b4ead5d3ae35581b4874ed09db35580fd 100644 (file)
--- a/src/libsystemd/sd-bus/busctl.c
+++ b/src/libsystemd/sd-bus/busctl.c
@@ -628,22 +628,19 @@ typedef struct Member {
         uint64_t flags;
 } Member;
 
-static unsigned long member_hash_func(const void *p, const uint8_t hash_key[]) {
+static void member_hash_func(const void *p, struct siphash *state) {
         const Member *m = p;
-        unsigned long ul;
 
         assert(m);
         assert(m->type);
 
-        ul = string_hash_func(m->type, hash_key);
+        string_hash_func(m->type, state);
 
         if (m->name)
-                ul ^= string_hash_func(m->name, hash_key);
+                string_hash_func(m->name, state);
 
         if (m->interface)
-                ul ^= string_hash_func(m->interface, hash_key);
-
-        return ul;
+                string_hash_func(m->interface, state);
 }
 
 static int member_compare_func(const void *a, const void *b) {

diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index fd2f53f40bdcf3dd041fc33af96c8c0a1aa13b63..2bc8cc16397ad2d1f4c0c76ca76e849381dea344 100644 (file)
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -146,15 +146,14 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec
         return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
 }
 
-static unsigned long dns_resource_key_hash_func(const void *i, const uint8_t hash_key[HASH_KEY_SIZE]) {
+static void dns_resource_key_hash_func(const void *i, struct siphash *state) {
         const DnsResourceKey *k = i;
-        unsigned long ul;
 
-        ul = dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), hash_key);
-        ul = ul * hash_key[0] + ul + k->class;
-        ul = ul * hash_key[1] + ul + k->type;
+        assert(k);
 
-        return ul;
+        dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), state);
+        siphash24_compress(&k->class, sizeof(k->class), state);
+        siphash24_compress(&k->type, sizeof(k->type), state);
 }
 
 static int dns_resource_key_compare_func(const void *a, const void *b) {

diff --git a/src/resolve/resolved-dns-server.c b/src/resolve/resolved-dns-server.c
index 2ff5b192df691a5646fa4689200c7d7f7f0e123b..8693911e65440180ccd1aedababa4c0937137bde 100644 (file)
--- a/src/resolve/resolved-dns-server.c
+++ b/src/resolve/resolved-dns-server.c
@@ -137,14 +137,13 @@ void dns_server_packet_lost(DnsServer *s, usec_t usec) {
                 s->resend_timeout = MIN(s->resend_timeout * 2, DNS_TIMEOUT_MAX_USEC);
 }
 
-static unsigned long dns_server_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
+static void dns_server_hash_func(const void *p, struct siphash *state) {
         const DnsServer *s = p;
-        uint64_t u;
 
-        siphash24((uint8_t*) &u, &s->address, FAMILY_ADDRESS_SIZE(s->family), hash_key);
-        u = u * hash_key[0] + u + s->family;
+        assert(s);
 
-        return u;
+        siphash24_compress(&s->family, sizeof(s->family), state);
+        siphash24_compress(&s->address, FAMILY_ADDRESS_SIZE(s->family), state);
 }
 
 static int dns_server_compare_func(const void *a, const void *b) {

diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c
index 6dc04d51e409767ef39c993ec837cef535e89f70..1517443736d24b70b80a86a5c244368a7ead058e 100644 (file)
--- a/src/shared/dns-domain.c
+++ b/src/shared/dns-domain.c
@@ -379,9 +379,8 @@ int dns_name_concat(const char *a, const char *b, char **_ret) {
         return 0;
 }
 
-unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]) {
+void dns_name_hash_func(const void *s, struct siphash *state) {
         const char *p = s;
-        unsigned long ul = hash_key[0];
         int r;
 
         assert(p);
@@ -403,10 +402,8 @@ unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_
                 label[r] = 0;
                 ascii_strlower(label);
 
-                ul = ul * hash_key[1] + ul + string_hash_func(label, hash_key);
+                string_hash_func(label, state);
         }
-
-        return ul;
 }
 
 int dns_name_compare_func(const void *a, const void *b) {

diff --git a/src/shared/dns-domain.h b/src/shared/dns-domain.h
index 8e73d9c20f83b441de40c53783420fad2d86f17b..1f0d242c18bb0e5aecde3aba12a4e2a5f571ac26 100644 (file)
--- a/src/shared/dns-domain.h
+++ b/src/shared/dns-domain.h
@@ -54,7 +54,7 @@ static inline int dns_name_is_valid(const char *s) {
         return 1;
 }
 
-unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]);
+void dns_name_hash_func(const void *s, struct siphash *state);
 int dns_name_compare_func(const void *a, const void *b);
 extern const struct hash_ops dns_name_hash_ops;
 

diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c
index 33ac93b395e6decd4b8e347b7099ac29463acf55..78f9c19f5b9e2921c4c5968ca9ef6057e8ce9361 100644 (file)
--- a/src/test/test-hashmap-plain.c
+++ b/src/test/test-hashmap-plain.c
@@ -692,8 +692,8 @@ static void test_hashmap_get2(void) {
         hashmap_free_free_free(m);
 }
 
-static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
-        return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), hash_key);
+static void crippled_hashmap_func(const void *p, struct siphash *state) {
+        return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), state);
 }
 
 static const struct hash_ops crippled_hashmap_ops = {

diff --git a/src/test/test-prioq.c b/src/test/test-prioq.c
index dfedc9b8dce32000886baec72ddd75a85edcb249..1e2e42cbca1713440533d8faf51393895db5bbfb 100644 (file)
--- a/src/test/test-prioq.c
+++ b/src/test/test-prioq.c
@@ -89,13 +89,10 @@ static int test_compare(const void *a, const void *b) {
         return 0;
 }
 
-static unsigned long test_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) {
+static void test_hash(const void *a, struct siphash *state) {
         const struct test *x = a;
-        uint64_t u;
 
-        siphash24((uint8_t*) &u, &x->value, sizeof(x->value), hash_key);
-
-        return (unsigned long) u;
+        siphash24_compress(&x->value, sizeof(x->value), state);
 }
 
 static const struct hash_ops test_hash_ops = {