diff options
Diffstat (limited to 'list.c')
| -rw-r--r-- | list.c | 664 |
1 files changed, 664 insertions, 0 deletions
@@ -0,0 +1,664 @@ +/* + * 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-2005 OpenVPN Solutions LLC <info@openvpn.net> + * + * 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 WIN32 +#include "config-win32.h" +#else +#include "config.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, + 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 = get_random (); + 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; + mutex_init (&b->mutex); + } + 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; + + mutex_destroy (&b->mutex); + 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]; + mutex_lock (&bucket->mutex); + + 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; + } + + mutex_unlock (&bucket->mutex); + + return ret; +} + +void +hash_remove_by_value (struct hash *hash, void *value, bool autolock) +{ + struct hash_iterator hi; + struct hash_element *he; + + hash_iterator_init (hash, &hi, autolock); + 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, + bool autolock, + 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->autolock = autolock; + 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, + bool autolock) +{ + hash_iterator_init_range (hash, hi, autolock, 0, hash->n_buckets); +} + +static inline void +hash_iterator_lock (struct hash_iterator *hi, struct hash_bucket *b) +{ + if (hi->autolock) + { + mutex_lock (&b->mutex); + } + 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; + } + if (hi->autolock) + { + mutex_unlock (&hi->bucket->mutex); + } + 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, word_hash_function, word_compare_function); + struct hash *nhash = hash_init (256, 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<n; ++i) h = hash( k[i], len[i], h); + +By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this +code any way you wish, private, educational, or commercial. It's free. + +See http://burlteburtle.net/bob/hash/evahash.html +Use for hash table lookup, or anything where one collision in 2^32 is +acceptable. Do NOT use for cryptographic purposes. + +-------------------------------------------------------------------- + +mix -- mix 3 32-bit values reversibly. +For every delta with one or two bit set, and the deltas of all three + high bits or all three low bits, whether the original value of a,b,c + is almost all zero or is uniformly distributed, +* If mix() is run forward or backward, at least 32 bits in a,b,c + have at least 1/4 probability of changing. +* If mix() is run forward, every bit of c will change between 1/3 and + 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) +mix() was built out of 36 single-cycle latency instructions in a + structure that could supported 2x parallelism, like so: + a -= b; + a -= c; x = (c>>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 */ |