Imported Upstream version 2.3_rc1

1 files changed, 649 insertions, 0 deletions

diff --git a/src/openvpn/list.c b/src/openvpn/list.c
new file mode 100644
index 0000000..ea6bd74
--- /dev/null
+++ b/src/openvpn/list.c
@@ -0,0 +1,649 @@
+/*
+ *  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. <sales@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 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<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 */