/* * 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-2010 OpenVPN Technologies, 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 (see the file COPYING included with this * distribution); if not, write to the Free Software Foundation, Inc., * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifdef HAVE_CONFIG_H #include "config.h" #elif defined(_MSC_VER) #include "config-msvc.h" #endif #include "syshead.h" #if P2MP_SERVER #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; } } } uint32_t void_ptr_hash_function (const void *key, uint32_t iv) { return hash_func ((const void *)&key, sizeof (key), iv); } bool void_ptr_compare_function (const void *key1, const void *key2) { return key1 == key2; } 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 /* -------------------------------------------------------------------- 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; } #else static void dummy(void) {} #endif /* P2MP_SERVER */