/* * OpenVPN -- An application to securely tunnel IP networks * over a single TCP/UDP port, with support for SSL/TLS-based * session authentication and key exchange, * packet encryption, packet authentication, and * packet compression. * * Copyright (C) 2002-2018 OpenVPN Inc * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 * as published by the Free Software Foundation. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License along * with this program; if not, write to the Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_MSC_VER) #include "config-msvc.h" #endif #include "syshead.h" #include "integer.h" #include "list.h" #include "misc.h" #include "memdbg.h" struct hash * hash_init(const int n_buckets, const uint32_t iv, uint32_t (*hash_function)(const void *key, uint32_t iv), bool (*compare_function)(const void *key1, const void *key2)) { struct hash *h; int i; ASSERT(n_buckets > 0); ALLOC_OBJ_CLEAR(h, struct hash); h->n_buckets = (int) adjust_power_of_2(n_buckets); h->mask = h->n_buckets - 1; h->hash_function = hash_function; h->compare_function = compare_function; h->iv = iv; ALLOC_ARRAY(h->buckets, struct hash_bucket, h->n_buckets); for (i = 0; i < h->n_buckets; ++i) { struct hash_bucket *b = &h->buckets[i]; b->list = NULL; } return h; } void hash_free(struct hash *hash) { int i; for (i = 0; i < hash->n_buckets; ++i) { struct hash_bucket *b = &hash->buckets[i]; struct hash_element *he = b->list; while (he) { struct hash_element *next = he->next; free(he); he = next; } } free(hash->buckets); free(hash); } struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv) { struct hash_element *he; struct hash_element *prev = NULL; he = bucket->list; while (he) { if (hv == he->hash_value && (*hash->compare_function)(key, he->key)) { /* move to head of list */ if (prev) { prev->next = he->next; he->next = bucket->list; bucket->list = he; } return he; } prev = he; he = he->next; } return NULL; } bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv) { struct hash_element *he; struct hash_element *prev = NULL; he = bucket->list; while (he) { if (hv == he->hash_value && (*hash->compare_function)(key, he->key)) { if (prev) { prev->next = he->next; } else { bucket->list = he->next; } free(he); --hash->n_elements; return true; } prev = he; he = he->next; } return false; } bool hash_add(struct hash *hash, const void *key, void *value, bool replace) { uint32_t hv; struct hash_bucket *bucket; struct hash_element *he; bool ret = false; hv = hash_value(hash, key); bucket = &hash->buckets[hv & hash->mask]; if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */ { if (replace) { he->value = value; ret = true; } } else { hash_add_fast(hash, bucket, key, hv, value); ret = true; } return ret; } void hash_remove_by_value(struct hash *hash, void *value) { struct hash_iterator hi; struct hash_element *he; hash_iterator_init(hash, &hi); while ((he = hash_iterator_next(&hi))) { if (he->value == value) { hash_iterator_delete_element(&hi); } } hash_iterator_free(&hi); } static void hash_remove_marked(struct hash *hash, struct hash_bucket *bucket) { struct hash_element *prev = NULL; struct hash_element *he = bucket->list; while (he) { if (!he->key) /* marked? */ { struct hash_element *newhe; if (prev) { newhe = prev->next = he->next; } else { newhe = bucket->list = he->next; } free(he); --hash->n_elements; he = newhe; } else { prev = he; he = he->next; } } } void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket) { if (end_bucket > hash->n_buckets) { end_bucket = hash->n_buckets; } ASSERT(start_bucket >= 0 && start_bucket <= end_bucket); hi->hash = hash; hi->elem = NULL; hi->bucket = NULL; hi->last = NULL; hi->bucket_marked = false; hi->bucket_index_start = start_bucket; hi->bucket_index_end = end_bucket; hi->bucket_index = hi->bucket_index_start - 1; } void hash_iterator_init(struct hash *hash, struct hash_iterator *hi) { hash_iterator_init_range(hash, hi, 0, hash->n_buckets); } static inline void hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b) { hi->bucket = b; hi->last = NULL; hi->bucket_marked = false; } static inline void hash_iterator_unlock(struct hash_iterator *hi) { if (hi->bucket) { if (hi->bucket_marked) { hash_remove_marked(hi->hash, hi->bucket); hi->bucket_marked = false; } hi->bucket = NULL; hi->last = NULL; } } static inline void hash_iterator_advance(struct hash_iterator *hi) { hi->last = hi->elem; hi->elem = hi->elem->next; } void hash_iterator_free(struct hash_iterator *hi) { hash_iterator_unlock(hi); } struct hash_element * hash_iterator_next(struct hash_iterator *hi) { struct hash_element *ret = NULL; if (hi->elem) { ret = hi->elem; hash_iterator_advance(hi); } else { while (++hi->bucket_index < hi->bucket_index_end) { struct hash_bucket *b; hash_iterator_unlock(hi); b = &hi->hash->buckets[hi->bucket_index]; if (b->list) { hash_iterator_lock(hi, b); hi->elem = b->list; if (hi->elem) { ret = hi->elem; hash_iterator_advance(hi); break; } } } } return ret; } void hash_iterator_delete_element(struct hash_iterator *hi) { ASSERT(hi->last); hi->last->key = NULL; hi->bucket_marked = true; } #ifdef LIST_TEST /* * Test the hash code by implementing a simple * word frequency algorithm. */ struct word { const char *word; int n; }; static uint32_t word_hash_function(const void *key, uint32_t iv) { const char *str = (const char *) key; const int len = strlen(str); return hash_func((const uint8_t *)str, len, iv); } static bool word_compare_function(const void *key1, const void *key2) { return strcmp((const char *)key1, (const char *)key2) == 0; } static void print_nhash(struct hash *hash) { struct hash_iterator hi; struct hash_element *he; int count = 0; hash_iterator_init(hash, &hi, true); while ((he = hash_iterator_next(&hi))) { printf("%d ", (int) he->value); ++count; } printf("\n"); hash_iterator_free(&hi); ASSERT(count == hash_n_elements(hash)); } static void rmhash(struct hash *hash, const char *word) { hash_remove(hash, word); } void list_test(void) { openvpn_thread_init(); { struct gc_arena gc = gc_new(); struct hash *hash = hash_init(10000, get_random(), word_hash_function, word_compare_function); struct hash *nhash = hash_init(256, get_random(), word_hash_function, word_compare_function); printf("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask); /* parse words from stdin */ while (true) { char buf[256]; char wordbuf[256]; int wbi; int bi; char c; if (!fgets(buf, sizeof(buf), stdin)) { break; } bi = wbi = 0; do { c = buf[bi++]; if (isalnum(c) || c == '_') { ASSERT(wbi < (int) sizeof(wordbuf)); wordbuf[wbi++] = c; } else { if (wbi) { struct word *w; ASSERT(wbi < (int) sizeof(wordbuf)); wordbuf[wbi++] = '\0'; /* word is parsed from stdin */ /* does it already exist in table? */ w = (struct word *) hash_lookup(hash, wordbuf); if (w) { /* yes, increment count */ ++w->n; } else { /* no, make a new object */ ALLOC_OBJ_GC(w, struct word, &gc); w->word = string_alloc(wordbuf, &gc); w->n = 1; ASSERT(hash_add(hash, w->word, w, false)); ASSERT(hash_add(nhash, w->word, (void *) ((random() & 0x0F) + 1), false)); } } wbi = 0; } } while (c); } #if 1 /* remove some words from the table */ { rmhash(hash, "true"); rmhash(hash, "false"); } #endif /* output contents of hash table */ { int base; int inc = 0; int count = 0; for (base = 0; base < hash_n_buckets(hash); base += inc) { struct hash_iterator hi; struct hash_element *he; inc = (get_random() % 3) + 1; hash_iterator_init_range(hash, &hi, true, base, base + inc); while ((he = hash_iterator_next(&hi))) { struct word *w = (struct word *) he->value; printf("%6d '%s'\n", w->n, w->word); ++count; } hash_iterator_free(&hi); } ASSERT(count == hash_n_elements(hash)); } #if 1 /* test hash_remove_by_value function */ { int i; for (i = 1; i <= 16; ++i) { printf("[%d] ***********************************\n", i); print_nhash(nhash); hash_remove_by_value(nhash, (void *) i, true); } printf("FINAL **************************\n"); print_nhash(nhash); } #endif hash_free(hash); hash_free(nhash); gc_free(&gc); } openvpn_thread_cleanup(); } #endif /* ifdef LIST_TEST */ /* * -------------------------------------------------------------------- * hash() -- hash a variable-length key into a 32-bit value * k : the key (the unaligned variable-length array of bytes) * len : the length of the key, counting by bytes * level : can be any 4-byte value * Returns a 32-bit value. Every bit of the key affects every bit of * the return value. Every 1-bit and 2-bit delta achieves avalanche. * About 36+6len instructions. * * The best hash table sizes are powers of 2. There is no need to do * mod a prime (mod is sooo slow!). If you need less than 32 bits, * use a bitmask. For example, if you need only 10 bits, do * h = (h & hashmask(10)); * In which case, the hash table should have hashsize(10) elements. * * If you are hashing n strings (uint8_t **)k, do it like this: * for (i=0, h=0; i>13); * b -= c; a ^= x; * b -= a; x = (a<<8); * c -= a; b ^= x; * c -= b; x = (b>>13); * ... * Unfortunately, superscalar Pentiums and Sparcs can't take advantage * of that parallelism. They've also turned some of those single-cycle * latency instructions into multi-cycle latency instructions. Still, * this is the fastest good hash I could find. There were about 2^^68 * to choose from. I only looked at a billion or so. * * James Yonan Notes: * * This function is faster than it looks, and appears to be * appropriate for our usage in OpenVPN which is primarily * for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC). * NOTE: This function is never used for cryptographic purposes, only * to produce evenly-distributed indexes into hash tables. * * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz, * and 12.1 machine cycles per byte on a * 2.2 Ghz P4 when hashing a 6 byte string. * -------------------------------------------------------------------- */ #define mix(a,b,c) \ { \ a -= b; a -= c; a ^= (c>>13); \ b -= c; b -= a; b ^= (a<<8); \ c -= a; c -= b; c ^= (b>>13); \ a -= b; a -= c; a ^= (c>>12); \ b -= c; b -= a; b ^= (a<<16); \ c -= a; c -= b; c ^= (b>>5); \ a -= b; a -= c; a ^= (c>>3); \ b -= c; b -= a; b ^= (a<<10); \ c -= a; c -= b; c ^= (b>>15); \ } uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval) { uint32_t a, b, c, len; /* Set up the internal state */ len = length; a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ c = initval; /* the previous hash value */ /*---------------------------------------- handle most of the key */ while (len >= 12) { a += (k[0] + ((uint32_t) k[1] << 8) + ((uint32_t) k[2] << 16) + ((uint32_t) k[3] << 24)); b += (k[4] + ((uint32_t) k[5] << 8) + ((uint32_t) k[6] << 16) + ((uint32_t) k[7] << 24)); c += (k[8] + ((uint32_t) k[9] << 8) + ((uint32_t) k[10] << 16) + ((uint32_t) k[11] << 24)); mix(a, b, c); k += 12; len -= 12; } /*------------------------------------- handle the last 11 bytes */ c += length; switch (len) /* all the case statements fall through */ { case 11: c += ((uint32_t) k[10] << 24); case 10: c += ((uint32_t) k[9] << 16); case 9: c += ((uint32_t) k[8] << 8); /* the first byte of c is reserved for the length */ case 8: b += ((uint32_t) k[7] << 24); case 7: b += ((uint32_t) k[6] << 16); case 6: b += ((uint32_t) k[5] << 8); case 5: b += k[4]; case 4: a += ((uint32_t) k[3] << 24); case 3: a += ((uint32_t) k[2] << 16); case 2: a += ((uint32_t) k[1] << 8); case 1: a += k[0]; /* case 0: nothing left to add */ } mix(a, b, c); /*-------------------------------------- report the result */ return c; }