X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=blobdiff_plain;f=src%2Fshared%2Fhashmap.c;h=65b7b741284bdcb5c0ad673cf6ae6b24110d66ea;hp=633079277d758f7961a2c854d84c0e861d6ffafa;hb=4de33e7f3238a6fe616e61139ab87e221572e5e5;hpb=45fa9e29f8c9759c8f2f4238fed956f695c73dc3 diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c index 633079277..65b7b7412 100644 --- a/src/shared/hashmap.c +++ b/src/shared/hashmap.c @@ -27,6 +27,7 @@ #include "util.h" #include "hashmap.h" #include "macro.h" +#include "siphash24.h" #define INITIAL_N_BUCKETS 31 @@ -46,7 +47,8 @@ struct Hashmap { struct hashmap_entry ** buckets; unsigned n_buckets, n_entries; - bool from_pool; + uint8_t hash_key[HASH_KEY_SIZE]; + bool from_pool:1; }; struct pool { @@ -61,13 +63,14 @@ static void *first_hashmap_tile = NULL; static struct pool *first_entry_pool = NULL; static void *first_entry_tile = NULL; -static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size) { +static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) { unsigned i; /* When a tile is released we add it to the list and simply * place the next pointer at its offset 0. */ assert(tile_size >= sizeof(void*)); + assert(at_least > 0); if (*first_tile) { void *r; @@ -83,7 +86,7 @@ static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t t struct pool *p; n = *first_pool ? (*first_pool)->n_tiles : 0; - n = MAX(512U, n * 2); + n = MAX(at_least, n * 2); size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size); n = (size - ALIGN(sizeof(struct pool))) / tile_size; @@ -128,49 +131,62 @@ __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 (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) { bool b; Hashmap *h; @@ -181,11 +197,11 @@ Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*); if (b) { - h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size); + h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8); if (!h) return NULL; - memset(h, 0, size); + memzero(h, size); } else { h = malloc0(size); @@ -204,6 +220,8 @@ Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) { h->from_pool = b; + get_hash_key(h->hash_key, true); + return h; } @@ -284,8 +302,7 @@ static void remove_entry(Hashmap *h, struct hashmap_entry *e) { assert(h); assert(e); - hash = h->hash_func(e->key) % h->n_buckets; - + hash = bucket_hash(h, e->key); unlink_entry(h, e, hash); if (h->from_pool) @@ -368,7 +385,6 @@ void hashmap_clear_free_free(Hashmap *h) { } } - static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) { struct hashmap_entry *e; assert(h); @@ -382,8 +398,9 @@ static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *ke } static bool resize_buckets(Hashmap *h) { - unsigned m; struct hashmap_entry **n, *i; + unsigned m; + uint8_t nkey[HASH_KEY_SIZE]; assert(h); @@ -398,10 +415,15 @@ static bool resize_buckets(Hashmap *h) { if (!n) return false; + /* Let's use a different randomized hash key for the + * extension, so that people cannot guess what we are using + * here forever */ + 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) @@ -410,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->n_buckets] = i->bucket_next; + h->buckets[old_bucket] = i->bucket_next; /* Then, add to new backet table */ - x = hash % 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)))) @@ -428,6 +450,8 @@ static bool resize_buckets(Hashmap *h) { h->buckets = n; h->n_buckets = m; + memcpy(h->hash_key, nkey, HASH_KEY_SIZE); + return true; } @@ -437,7 +461,7 @@ int hashmap_put(Hashmap *h, const void *key, void *value) { assert(h); - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (e) { if (e->value == value) @@ -446,10 +470,10 @@ int hashmap_put(Hashmap *h, const void *key, void *value) { } if (resize_buckets(h)) - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); if (h->from_pool) - e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry)); + e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U); else e = new(struct hashmap_entry, 1); @@ -470,7 +494,7 @@ int hashmap_replace(Hashmap *h, const void *key, void *value) { assert(h); - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (e) { e->key = key; @@ -487,7 +511,7 @@ int hashmap_update(Hashmap *h, const void *key, void *value) { assert(h); - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) return -ENOENT; @@ -503,7 +527,7 @@ void* hashmap_get(Hashmap *h, const void *key) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) return NULL; @@ -518,7 +542,7 @@ void* hashmap_get2(Hashmap *h, const void *key, void **key2) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) return NULL; @@ -535,12 +559,8 @@ bool hashmap_contains(Hashmap *h, const void *key) { if (!h) return false; - hash = h->hash_func(key) % h->n_buckets; - - if (!hash_scan(h, hash, key)) - return false; - - return true; + hash = bucket_hash(h, key); + return !!hash_scan(h, hash, key); } void* hashmap_remove(Hashmap *h, const void *key) { @@ -551,9 +571,9 @@ void* hashmap_remove(Hashmap *h, const void *key) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; - - if (!(e = hash_scan(h, hash, key))) + hash = bucket_hash(h, key); + e = hash_scan(h, hash, key); + if (!e) return NULL; data = e->value; @@ -569,11 +589,12 @@ int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, if (!h) return -ENOENT; - old_hash = h->hash_func(old_key) % h->n_buckets; - if (!(e = hash_scan(h, old_hash, old_key))) + old_hash = bucket_hash(h, old_key); + e = hash_scan(h, old_hash, old_key); + if (!e) return -ENOENT; - new_hash = h->hash_func(new_key) % h->n_buckets; + new_hash = bucket_hash(h, new_key); if (hash_scan(h, new_hash, new_key)) return -EEXIST; @@ -594,12 +615,14 @@ int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_ if (!h) return -ENOENT; - old_hash = h->hash_func(old_key) % h->n_buckets; - if (!(e = hash_scan(h, old_hash, old_key))) + old_hash = bucket_hash(h, old_key); + e = hash_scan(h, old_hash, old_key); + if (!e) return -ENOENT; - new_hash = h->hash_func(new_key) % h->n_buckets; - if ((k = hash_scan(h, new_hash, new_key))) + new_hash = bucket_hash(h, new_key); + k = hash_scan(h, new_hash, new_key); + if (k) if (e != k) remove_entry(h, k); @@ -620,7 +643,7 @@ void* hashmap_remove_value(Hashmap *h, const void *key, void *value) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) @@ -711,7 +734,7 @@ void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) @@ -820,9 +843,9 @@ int hashmap_merge(Hashmap *h, Hashmap *other) { for (e = other->iterate_list_head; e; e = e->iterate_next) { int r; - if ((r = hashmap_put(h, e->key, e->value)) < 0) - if (r != -EEXIST) - return r; + r = hashmap_put(h, e->key, e->value); + if (r < 0 && r != -EEXIST) + return r; } return 0; @@ -844,13 +867,11 @@ void hashmap_move(Hashmap *h, Hashmap *other) { n = e->iterate_next; - h_hash = h->hash_func(e->key) % h->n_buckets; - + h_hash = bucket_hash(h, e->key); if (hash_scan(h, h_hash, e->key)) continue; - other_hash = other->hash_func(e->key) % other->n_buckets; - + other_hash = bucket_hash(other, e->key); unlink_entry(other, e, other_hash); link_entry(h, e, h_hash); } @@ -865,11 +886,11 @@ int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) { assert(h); - h_hash = h->hash_func(key) % h->n_buckets; + h_hash = bucket_hash(h, key); if (hash_scan(h, h_hash, key)) return -EEXIST; - other_hash = other->hash_func(key) % other->n_buckets; + other_hash = bucket_hash(other, key); e = hash_scan(other, other_hash, key); if (!e) return -ENOENT; @@ -925,7 +946,7 @@ void *hashmap_next(Hashmap *h, const void *key) { if (!h) return NULL; - hash = h->hash_func(key) % h->n_buckets; + hash = bucket_hash(h, key); e = hash_scan(h, hash, key); if (!e) return NULL;