From b826ab586c9e0a9c0d438a75c28cf3a8ab485929 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Sun, 4 Oct 2015 00:22:41 +0200 Subject: hashmap: refactor hash_func All our hash functions are based on siphash24(), factor out siphash_init() and siphash24_finalize() and pass the siphash state to the hash functions rather than the hash key. This simplifies the hash functions, and in particular makes composition simpler as calling siphash24_compress() repeatedly on separate chunks of input has the same effect as first concatenating the input and then calling siphash23_compress() on the result. --- src/basic/hashmap.c | 32 +++++++++++++-------------- src/basic/hashmap.h | 11 ++++----- src/journal/catalog.c | 16 +++----------- src/journal/journald-rate-limit.c | 10 +++++++-- src/libsystemd-network/dhcp-server-internal.h | 2 +- src/libsystemd-network/sd-dhcp-server.c | 13 +++++------ src/libsystemd-network/sd-lldp.c | 9 +++----- src/libsystemd-network/test-dhcp-server.c | 14 +++++++++--- src/libsystemd/sd-bus/bus-objects.c | 19 ++++------------ src/libsystemd/sd-bus/busctl.c | 11 ++++----- src/resolve/resolved-dns-rr.c | 11 +++++---- src/resolve/resolved-dns-server.c | 9 ++++---- src/shared/dns-domain.c | 7 ++---- src/shared/dns-domain.h | 2 +- src/test/test-hashmap-plain.c | 4 ++-- src/test/test-prioq.c | 7 ++---- 16 files changed, 77 insertions(+), 100 deletions(-) (limited to 'src') diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index 7d2a4160c6..3c05bee56d 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -276,10 +276,8 @@ static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = { }, }; -unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, strlen(p), hash_key); - return (unsigned long) u; +void string_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, strlen(p), state); } int string_compare_func(const void *a, const void *b) { @@ -291,10 +289,8 @@ const struct hash_ops string_hash_ops = { .compare = string_compare_func }; -unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, &p, sizeof(p), hash_key); - return (unsigned long) u; +void trivial_hash_func(const void *p, struct siphash *state) { + siphash24_compress(&p, sizeof(p), state); } int trivial_compare_func(const void *a, const void *b) { @@ -306,10 +302,8 @@ const struct hash_ops trivial_hash_ops = { .compare = trivial_compare_func }; -unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, sizeof(uint64_t), hash_key); - return (unsigned long) u; +void uint64_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, sizeof(uint64_t), state); } int uint64_compare_func(const void *_a, const void *_b) { @@ -325,10 +319,8 @@ const struct hash_ops uint64_hash_ops = { }; #if SIZEOF_DEV_T != 8 -unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; - siphash24((uint8_t*) &u, p, sizeof(dev_t), hash_key); - return (unsigned long) u; +void devt_hash_func(const void *p, struct siphash *state) { + siphash24_compress(p, sizeof(dev_t), state); } int devt_compare_func(const void *_a, const void *_b) { @@ -379,7 +371,13 @@ static uint8_t *hash_key(HashmapBase *h) { } static unsigned base_bucket_hash(HashmapBase *h, const void *p) { - return (unsigned) (h->hash_ops->hash(p, hash_key(h)) % n_buckets(h)); + struct siphash state; + + siphash_init(&state, hash_key(h)); + + h->hash_ops->hash(p, &state); + + return (unsigned) (siphash24_finalize(&state) % n_buckets(h)); } #define bucket_hash(h, p) base_bucket_hash(HASHMAP_BASE(h), p) diff --git a/src/basic/hashmap.h b/src/basic/hashmap.h index 2af23024de..ed6a092d82 100644 --- a/src/basic/hashmap.h +++ b/src/basic/hashmap.h @@ -25,6 +25,7 @@ #include #include "macro.h" +#include "siphash24.h" #include "util.h" /* @@ -67,7 +68,7 @@ typedef struct { #define _IDX_ITERATOR_FIRST (UINT_MAX - 1) #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL }) -typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); +typedef void (*hash_func_t)(const void *p, struct siphash *state); typedef int (*compare_func_t)(const void *a, const void *b); struct hash_ops { @@ -75,28 +76,28 @@ struct hash_ops { compare_func_t compare; }; -unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void string_hash_func(const void *p, struct siphash *state); int string_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops string_hash_ops; /* This will compare the passed pointers directly, and will not * dereference them. This is hence not useful for strings or * suchlike. */ -unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void trivial_hash_func(const void *p, struct siphash *state); int trivial_compare_func(const void *a, const void *b) _const_; extern const struct hash_ops trivial_hash_ops; /* 32bit values we can always just embedd in the pointer itself, but * in order to support 32bit archs we need store 64bit values * indirectly, since they don't fit in a pointer. */ -unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void uint64_hash_func(const void *p, struct siphash *state); int uint64_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops uint64_hash_ops; /* On some archs dev_t is 32bit, and on others 64bit. And sometimes * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */ #if SIZEOF_DEV_T != 8 -unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_; +void devt_hash_func(const void *p, struct siphash *state) _pure_; int devt_compare_func(const void *a, const void *b) _pure_; extern const struct hash_ops devt_hash_ops = { .hash = devt_hash_func, diff --git a/src/journal/catalog.c b/src/journal/catalog.c index 78ca4b02e8..4c43500ef5 100644 --- a/src/journal/catalog.c +++ b/src/journal/catalog.c @@ -62,21 +62,11 @@ typedef struct CatalogItem { le64_t offset; } CatalogItem; -static unsigned long catalog_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void catalog_hash_func(const void *p, struct siphash *state) { const CatalogItem *i = p; - uint64_t u; - size_t l, sz; - void *v; - l = strlen(i->language); - sz = sizeof(i->id) + l; - v = alloca(sz); - - memcpy(mempcpy(v, &i->id, sizeof(i->id)), i->language, l); - - siphash24((uint8_t*) &u, v, sz, hash_key); - - return (unsigned long) u; + siphash24_compress(&i->id, sizeof(i->id), state); + siphash24_compress(i->language, strlen(i->language), state); } static int catalog_compare_func(const void *a, const void *b) { diff --git a/src/journal/journald-rate-limit.c b/src/journal/journald-rate-limit.c index 6f83035a4e..7e06117b31 100644 --- a/src/journal/journald-rate-limit.c +++ b/src/journal/journald-rate-limit.c @@ -145,6 +145,7 @@ static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) { static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) { JournalRateLimitGroup *g; + struct siphash state; assert(r); assert(id); @@ -157,7 +158,9 @@ static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, if (!g->id) goto fail; - g->hash = string_hash_func(g->id, r->hash_key); + siphash_init(&state, r->hash_key); + string_hash_func(g->id, &state); + g->hash = siphash24_finalize(&state); journal_rate_limit_vacuum(r, ts); @@ -207,6 +210,7 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u unsigned long h; JournalRateLimitGroup *g; JournalRateLimitPool *p; + struct siphash state; unsigned burst; usec_t ts; @@ -222,7 +226,9 @@ int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, u ts = now(CLOCK_MONOTONIC); - h = string_hash_func(id, r->hash_key); + siphash_init(&state, r->hash_key); + string_hash_func(id, &state); + h = siphash24_finalize(&state); g = r->buckets[h % BUCKETS_MAX]; LIST_FOREACH(bucket, g, g) diff --git a/src/libsystemd-network/dhcp-server-internal.h b/src/libsystemd-network/dhcp-server-internal.h index 5dc3c7aa26..3b88b93d9a 100644 --- a/src/libsystemd-network/dhcp-server-internal.h +++ b/src/libsystemd-network/dhcp-server-internal.h @@ -96,5 +96,5 @@ int dhcp_server_send_packet(sd_dhcp_server *server, DHCPRequest *req, DHCPPacket *packet, int type, size_t optoffset); -unsigned long client_id_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]); +void client_id_hash_func(const void *p, struct siphash *state); int client_id_compare_func(const void *_a, const void *_b); diff --git a/src/libsystemd-network/sd-dhcp-server.c b/src/libsystemd-network/sd-dhcp-server.c index 1f167485e3..4ea5a29e5c 100644 --- a/src/libsystemd-network/sd-dhcp-server.c +++ b/src/libsystemd-network/sd-dhcp-server.c @@ -110,18 +110,14 @@ sd_dhcp_server *sd_dhcp_server_ref(sd_dhcp_server *server) { return server; } -unsigned long client_id_hash_func(const void *p, - const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; +void client_id_hash_func(const void *p, struct siphash *state) { const DHCPClientId *id = p; assert(id); assert(id->length); assert(id->data); - siphash24((uint8_t*) &u, id->data, id->length, hash_key); - - return (unsigned long) u; + siphash24_compress(id->data, id->length, state); } int client_id_compare_func(const void *_a, const void *_b) { @@ -743,13 +739,16 @@ int dhcp_server_handle_message(sd_dhcp_server *server, DHCPMessage *message, if (existing_lease) address = existing_lease->address; else { + struct siphash state; uint32_t next_offer; /* even with no persistence of leases, we try to offer the same client the same IP address. we do this by using the hash of the client id as the offset into the pool of leases when finding the next free one */ - next_offer = client_id_hash_func(&req->client_id, HASH_KEY.bytes) % server->pool_size; + siphash_init(&state, HASH_KEY.bytes); + client_id_hash_func(&req->client_id, &state); + next_offer = siphash24_finalize(&state) % server->pool_size; for (i = 0; i < server->pool_size; i++) { if (!server->bound_leases[next_offer]) { diff --git a/src/libsystemd-network/sd-lldp.c b/src/libsystemd-network/sd-lldp.c index 17512884f5..b9bf4d3c00 100644 --- a/src/libsystemd-network/sd-lldp.c +++ b/src/libsystemd-network/sd-lldp.c @@ -68,16 +68,13 @@ struct sd_lldp { lldp_agent_statistics statistics; }; -static unsigned long chassis_id_hash_func(const void *p, - const uint8_t hash_key[HASH_KEY_SIZE]) { - uint64_t u; +static void chassis_id_hash_func(const void *p, struct siphash *state) { const lldp_chassis_id *id = p; assert(id); + assert(id->data); - siphash24((uint8_t *) &u, id->data, id->length, hash_key); - - return (unsigned long) u; + siphash24_compress(id->data, id->length, state); } static int chassis_id_compare_func(const void *_a, const void *_b) { diff --git a/src/libsystemd-network/test-dhcp-server.c b/src/libsystemd-network/test-dhcp-server.c index 7d8a1f6bd9..01205efc18 100644 --- a/src/libsystemd-network/test-dhcp-server.c +++ b/src/libsystemd-network/test-dhcp-server.c @@ -198,6 +198,14 @@ static void test_message_handler(void) { assert_se(dhcp_server_handle_message(server, (DHCPMessage*)&test, sizeof(test)) == 0); } +static uint64_t client_id_hash_helper(DHCPClientId *id, uint8_t key[HASH_KEY_SIZE]) { + struct siphash state; + + siphash_init(&state, key); + client_id_hash_func(id, &state); + return siphash24_finalize(&state); +} + static void test_client_id_hash(void) { DHCPClientId a = { .length = 4, @@ -213,18 +221,18 @@ static void test_client_id_hash(void) { b.data = (uint8_t*)strdup("abcd"); assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); a.length = 3; assert_se(client_id_compare_func(&a, &b) != 0); a.length = 4; assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); b.length = 3; assert_se(client_id_compare_func(&a, &b) != 0); b.length = 4; assert_se(client_id_compare_func(&a, &b) == 0); - assert_se(client_id_hash_func(&a, hash_key) == client_id_hash_func(&b, hash_key)); + assert_se(client_id_hash_helper(&a, hash_key) == client_id_hash_helper(&b, hash_key)); free(b.data); b.data = (uint8_t*)strdup("abce"); diff --git a/src/libsystemd/sd-bus/bus-objects.c b/src/libsystemd/sd-bus/bus-objects.c index 1d061cb9cf..728f20447a 100644 --- a/src/libsystemd/sd-bus/bus-objects.c +++ b/src/libsystemd/sd-bus/bus-objects.c @@ -1578,25 +1578,14 @@ _public_ int sd_bus_add_fallback( return bus_add_object(bus, slot, true, prefix, callback, userdata); } -static unsigned long vtable_member_hash_func(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void vtable_member_hash_func(const void *a, struct siphash *state) { const struct vtable_member *m = a; - uint8_t hash_key2[HASH_KEY_SIZE]; - unsigned long ret; assert(m); - ret = string_hash_func(m->path, hash_key); - - /* Use a slightly different hash key for the interface */ - memcpy(hash_key2, hash_key, HASH_KEY_SIZE); - hash_key2[0]++; - ret ^= string_hash_func(m->interface, hash_key2); - - /* And an even different one for the member */ - hash_key2[0]++; - ret ^= string_hash_func(m->member, hash_key2); - - return ret; + string_hash_func(m->path, state); + string_hash_func(m->interface, state); + string_hash_func(m->member, state); } static int vtable_member_compare_func(const void *a, const void *b) { diff --git a/src/libsystemd/sd-bus/busctl.c b/src/libsystemd/sd-bus/busctl.c index ab8816942c..496b9a7b4e 100644 --- a/src/libsystemd/sd-bus/busctl.c +++ b/src/libsystemd/sd-bus/busctl.c @@ -628,22 +628,19 @@ typedef struct Member { uint64_t flags; } Member; -static unsigned long member_hash_func(const void *p, const uint8_t hash_key[]) { +static void member_hash_func(const void *p, struct siphash *state) { const Member *m = p; - unsigned long ul; assert(m); assert(m->type); - ul = string_hash_func(m->type, hash_key); + string_hash_func(m->type, state); if (m->name) - ul ^= string_hash_func(m->name, hash_key); + string_hash_func(m->name, state); if (m->interface) - ul ^= string_hash_func(m->interface, hash_key); - - return ul; + string_hash_func(m->interface, state); } static int member_compare_func(const void *a, const void *b) { diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c index fd2f53f40b..2bc8cc1639 100644 --- a/src/resolve/resolved-dns-rr.c +++ b/src/resolve/resolved-dns-rr.c @@ -146,15 +146,14 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key)); } -static unsigned long dns_resource_key_hash_func(const void *i, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void dns_resource_key_hash_func(const void *i, struct siphash *state) { const DnsResourceKey *k = i; - unsigned long ul; - ul = dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), hash_key); - ul = ul * hash_key[0] + ul + k->class; - ul = ul * hash_key[1] + ul + k->type; + assert(k); - return ul; + dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), state); + siphash24_compress(&k->class, sizeof(k->class), state); + siphash24_compress(&k->type, sizeof(k->type), state); } static int dns_resource_key_compare_func(const void *a, const void *b) { diff --git a/src/resolve/resolved-dns-server.c b/src/resolve/resolved-dns-server.c index 2ff5b192df..8693911e65 100644 --- a/src/resolve/resolved-dns-server.c +++ b/src/resolve/resolved-dns-server.c @@ -137,14 +137,13 @@ void dns_server_packet_lost(DnsServer *s, usec_t usec) { s->resend_timeout = MIN(s->resend_timeout * 2, DNS_TIMEOUT_MAX_USEC); } -static unsigned long dns_server_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void dns_server_hash_func(const void *p, struct siphash *state) { const DnsServer *s = p; - uint64_t u; - siphash24((uint8_t*) &u, &s->address, FAMILY_ADDRESS_SIZE(s->family), hash_key); - u = u * hash_key[0] + u + s->family; + assert(s); - return u; + siphash24_compress(&s->family, sizeof(s->family), state); + siphash24_compress(&s->address, FAMILY_ADDRESS_SIZE(s->family), state); } static int dns_server_compare_func(const void *a, const void *b) { diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c index 6dc04d51e4..1517443736 100644 --- a/src/shared/dns-domain.c +++ b/src/shared/dns-domain.c @@ -379,9 +379,8 @@ int dns_name_concat(const char *a, const char *b, char **_ret) { return 0; } -unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]) { +void dns_name_hash_func(const void *s, struct siphash *state) { const char *p = s; - unsigned long ul = hash_key[0]; int r; assert(p); @@ -403,10 +402,8 @@ unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_ label[r] = 0; ascii_strlower(label); - ul = ul * hash_key[1] + ul + string_hash_func(label, hash_key); + string_hash_func(label, state); } - - return ul; } int dns_name_compare_func(const void *a, const void *b) { diff --git a/src/shared/dns-domain.h b/src/shared/dns-domain.h index 8e73d9c20f..1f0d242c18 100644 --- a/src/shared/dns-domain.h +++ b/src/shared/dns-domain.h @@ -54,7 +54,7 @@ static inline int dns_name_is_valid(const char *s) { return 1; } -unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]); +void dns_name_hash_func(const void *s, struct siphash *state); int dns_name_compare_func(const void *a, const void *b); extern const struct hash_ops dns_name_hash_ops; diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 33ac93b395..78f9c19f5b 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -692,8 +692,8 @@ static void test_hashmap_get2(void) { hashmap_free_free_free(m); } -static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { - return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), hash_key); +static void crippled_hashmap_func(const void *p, struct siphash *state) { + return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), state); } static const struct hash_ops crippled_hashmap_ops = { diff --git a/src/test/test-prioq.c b/src/test/test-prioq.c index dfedc9b8dc..1e2e42cbca 100644 --- a/src/test/test-prioq.c +++ b/src/test/test-prioq.c @@ -89,13 +89,10 @@ static int test_compare(const void *a, const void *b) { return 0; } -static unsigned long test_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) { +static void test_hash(const void *a, struct siphash *state) { const struct test *x = a; - uint64_t u; - siphash24((uint8_t*) &u, &x->value, sizeof(x->value), hash_key); - - return (unsigned long) u; + siphash24_compress(&x->value, sizeof(x->value), state); } static const struct hash_ops test_hash_ops = { -- cgit v1.2.3-54-g00ecf