openvpn/list.c

   1 /*
   2  *  OpenVPN -- An application to securely tunnel IP networks
   3  *             over a single TCP/UDP port, with support for SSL/TLS-based
   4  *             session authentication and key exchange,
   5  *             packet encryption, packet authentication, and
   6  *             packet compression.
   7  *
   8  *  Copyright (C) 2002-2005 OpenVPN Solutions LLC <info@openvpn.net>
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License version 2
  12  *  as published by the Free Software Foundation.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program (see the file COPYING included with this
  21  *  distribution); if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23  */
  24
  25 #ifdef WIN32
  26 #include "config-win32.h"
  27 #else
  28 #include "config.h"
  29 #endif
  30
  31 #include "syshead.h"
  32
  33 #if P2MP_SERVER
  34
  35 #include "list.h"
  36 #include "misc.h"
  37
  38 #include "memdbg.h"
  39
  40 struct hash *
  41 hash_init (const int n_buckets,
  42            uint32_t (*hash_function)(const void *key, uint32_t iv),
  43            bool (*compare_function)(const void *key1, const void *key2))
  44 {
  45   struct hash *h;
  46   int i;
  47
  48   ASSERT (n_buckets > 0);
  49   ALLOC_OBJ_CLEAR (h, struct hash);
  50   h->n_buckets = (int) adjust_power_of_2 (n_buckets);
  51   h->mask = h->n_buckets - 1;
  52   h->hash_function = hash_function;
  53   h->compare_function = compare_function;
  54   h->iv = get_random ();
  55   ALLOC_ARRAY (h->buckets, struct hash_bucket, h->n_buckets);
  56   for (i = 0; i < h->n_buckets; ++i)
  57     {
  58       struct hash_bucket *b = &h->buckets[i];
  59       b->list = NULL;
  60       mutex_init (&b->mutex);
  61     }
  62   return h;
  63 }
  64
  65 void
  66 hash_free (struct hash *hash)
  67 {
  68   int i;
  69   for (i = 0; i < hash->n_buckets; ++i)
  70     {
  71       struct hash_bucket *b = &hash->buckets[i];
  72       struct hash_element *he = b->list;
  73
  74       mutex_destroy (&b->mutex);
  75       while (he)
  76         {
  77           struct hash_element *next = he->next;
  78           free (he);
  79           he = next;
  80         }
  81     }
  82   free (hash->buckets);
  83   free (hash);
  84 }
  85
  86 struct hash_element *
  87 hash_lookup_fast (struct hash *hash,
  88                   struct hash_bucket *bucket,
  89                   const void *key,
  90                   uint32_t hv)
  91 {
  92   struct hash_element *he;
  93   struct hash_element *prev = NULL;
  94
  95   he = bucket->list;
  96
  97   while (he)
  98     {
  99       if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
 100         {
 101           /* move to head of list */
 102           if (prev)
 103             {
 104               prev->next = he->next;
 105               he->next = bucket->list;
 106               bucket->list = he;
 107             }
 108           return he;
 109         }
 110       prev = he;
 111       he = he->next;
 112     }
 113
 114   return NULL;
 115 }
 116
 117 bool
 118 hash_remove_fast (struct hash *hash,
 119                   struct hash_bucket *bucket,
 120                   const void *key,
 121                   uint32_t hv)
 122 {
 123   struct hash_element *he;
 124   struct hash_element *prev = NULL;
 125
 126   he = bucket->list;
 127
 128   while (he)
 129     {
 130       if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
 131         {
 132           if (prev)
 133             prev->next = he->next;
 134           else
 135             bucket->list = he->next;
 136           free (he);
 137           --hash->n_elements;
 138           return true;
 139         }
 140       prev = he;
 141       he = he->next;
 142     }
 143   return false;
 144 }
 145
 146 bool
 147 hash_add (struct hash *hash, const void *key, void *value, bool replace)
 148 {
 149   uint32_t hv;
 150   struct hash_bucket *bucket;
 151   struct hash_element *he;
 152   bool ret = false;
 153
 154   hv = hash_value (hash, key);
 155   bucket = &hash->buckets[hv & hash->mask];
 156   mutex_lock (&bucket->mutex);
 157
 158   if ((he = hash_lookup_fast (hash, bucket, key, hv))) /* already exists? */
 159     {
 160       if (replace)
 161         {
 162           he->value = value;
 163           ret = true;
 164         }
 165     }
 166   else
 167     {
 168       hash_add_fast (hash, bucket, key, hv, value);
 169       ret = true;
 170     }
 171
 172   mutex_unlock (&bucket->mutex);
 173
 174   return ret;
 175 }
 176
 177 void
 178 hash_remove_by_value (struct hash *hash, void *value, bool autolock)
 179 {
 180   struct hash_iterator hi;
 181   struct hash_element *he;
 182
 183   hash_iterator_init (hash, &hi, autolock);
 184   while ((he = hash_iterator_next (&hi)))
 185     {
 186       if (he->value == value)
 187         hash_iterator_delete_element (&hi);
 188     }
 189   hash_iterator_free (&hi);
 190 }
 191
 192 static void
 193 hash_remove_marked (struct hash *hash, struct hash_bucket *bucket)
 194 {
 195   struct hash_element *prev = NULL;
 196   struct hash_element *he = bucket->list;
 197
 198   while (he)
 199     {
 200       if (!he->key) /* marked? */
 201         {
 202           struct hash_element *newhe;
 203           if (prev)
 204             newhe = prev->next = he->next;
 205           else
 206             newhe = bucket->list = he->next;
 207           free (he);
 208           --hash->n_elements;
 209           he = newhe;
 210         }
 211       else
 212         {
 213           prev = he;
 214           he = he->next;
 215         }
 216     }
 217 }
 218
 219 uint32_t
 220 void_ptr_hash_function (const void *key, uint32_t iv)
 221 {
 222   return hash_func ((const void *)&key, sizeof (key), iv);
 223 }
 224
 225 bool
 226 void_ptr_compare_function (const void *key1, const void *key2)
 227 {
 228   return key1 == key2;
 229 }
 230
 231 void
 232 hash_iterator_init_range (struct hash *hash,
 233                        struct hash_iterator *hi,
 234                        bool autolock,
 235                        int start_bucket,
 236                        int end_bucket)
 237 {
 238   if (end_bucket > hash->n_buckets)
 239     end_bucket = hash->n_buckets;
 240
 241   ASSERT (start_bucket >= 0 && start_bucket <= end_bucket);
 242
 243   hi->hash = hash;
 244   hi->elem = NULL;
 245   hi->bucket = NULL;
 246   hi->autolock = autolock;
 247   hi->last = NULL;
 248   hi->bucket_marked = false;
 249   hi->bucket_index_start = start_bucket;
 250   hi->bucket_index_end = end_bucket;
 251   hi->bucket_index = hi->bucket_index_start - 1;
 252 }
 253
 254 void
 255 hash_iterator_init (struct hash *hash,
 256                     struct hash_iterator *hi,
 257                     bool autolock)
 258 {
 259   hash_iterator_init_range (hash, hi, autolock, 0, hash->n_buckets);
 260 }
 261
 262 static inline void
 263 hash_iterator_lock (struct hash_iterator *hi, struct hash_bucket *b)
 264 {
 265   if (hi->autolock)
 266     {
 267       mutex_lock (&b->mutex);
 268     }
 269   hi->bucket = b;
 270   hi->last = NULL;
 271   hi->bucket_marked = false;
 272 }
 273
 274 static inline void
 275 hash_iterator_unlock (struct hash_iterator *hi)
 276 {
 277   if (hi->bucket)
 278     {
 279       if (hi->bucket_marked)
 280         {
 281           hash_remove_marked (hi->hash, hi->bucket);
 282           hi->bucket_marked = false;
 283         }
 284       if (hi->autolock)
 285         {
 286           mutex_unlock (&hi->bucket->mutex);
 287         }
 288       hi->bucket = NULL;
 289       hi->last = NULL;
 290     }
 291 }
 292
 293 static inline void
 294 hash_iterator_advance (struct hash_iterator *hi)
 295 {
 296   hi->last = hi->elem;
 297   hi->elem = hi->elem->next;
 298 }
 299
 300 void
 301 hash_iterator_free (struct hash_iterator *hi)
 302 {
 303   hash_iterator_unlock (hi);
 304 }
 305
 306 struct hash_element *
 307 hash_iterator_next (struct hash_iterator *hi)
 308 {
 309   struct hash_element *ret = NULL;
 310   if (hi->elem)
 311     {
 312       ret = hi->elem;
 313       hash_iterator_advance (hi);
 314     }
 315   else
 316     {
 317       while (++hi->bucket_index < hi->bucket_index_end)
 318         {
 319           struct hash_bucket *b;
 320           hash_iterator_unlock (hi);
 321           b = &hi->hash->buckets[hi->bucket_index];
 322           if (b->list)
 323             {
 324               hash_iterator_lock (hi, b);
 325               hi->elem = b->list;
 326               if (hi->elem)
 327                 {
 328                   ret = hi->elem;
 329                   hash_iterator_advance (hi);
 330                   break;
 331                 }
 332             }
 333         }
 334     }
 335   return ret;
 336 }
 337
 338 void
 339 hash_iterator_delete_element (struct hash_iterator *hi)
 340 {
 341   ASSERT (hi->last);
 342   hi->last->key = NULL;
 343   hi->bucket_marked = true;
 344 }
 345
 346
 347 #ifdef LIST_TEST
 348
 349 /*
 350  * Test the hash code by implementing a simple
 351  * word frequency algorithm.
 352  */
 353
 354 struct word
 355 {
 356   const char *word;
 357   int n;
 358 };
 359
 360 static uint32_t
 361 word_hash_function (const void *key, uint32_t iv)
 362 {
 363   const char *str = (const char *) key;
 364   const int len = strlen (str);
 365   return hash_func ((const uint8_t *)str, len, iv);
 366 }
 367
 368 static bool
 369 word_compare_function (const void *key1, const void *key2)
 370 {
 371   return strcmp ((const char *)key1, (const char *)key2) == 0;
 372 }
 373
 374 static void
 375 print_nhash (struct hash *hash)
 376 {
 377   struct hash_iterator hi;
 378   struct hash_element *he;
 379   int count = 0;
 380
 381   hash_iterator_init (hash, &hi, true);
 382
 383   while ((he = hash_iterator_next (&hi)))
 384     {
 385       printf ("%d ", (int) he->value);
 386       ++count;
 387     }
 388   printf ("\n");
 389
 390   hash_iterator_free (&hi);
 391   ASSERT (count == hash_n_elements (hash));
 392 }
 393
 394 static void
 395 rmhash (struct hash *hash, const char *word)
 396 {
 397   hash_remove (hash, word);
 398 }
 399
 400 void
 401 list_test (void)
 402 {
 403   openvpn_thread_init ();
 404
 405   {
 406     struct gc_arena gc = gc_new ();
 407     struct hash *hash = hash_init (10000, word_hash_function, word_compare_function);
 408     struct hash *nhash = hash_init (256, word_hash_function, word_compare_function);
 409
 410     printf ("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask);
 411
 412     /* parse words from stdin */
 413     while (true)
 414       {
 415         char buf[256];
 416         char wordbuf[256];
 417         int wbi;
 418         int bi;
 419         char c;
 420
 421         if (!fgets(buf, sizeof(buf), stdin))
 422           break;
 423
 424         bi = wbi = 0;
 425         do
 426           {
 427             c = buf[bi++];
 428             if (isalnum (c) || c == '_')
 429               {
 430                 ASSERT (wbi < (int) sizeof (wordbuf));
 431                 wordbuf[wbi++] = c;
 432               }
 433             else
 434               {
 435                 if (wbi)
 436                   {
 437                     struct word *w;
 438                     ASSERT (wbi < (int) sizeof (wordbuf));
 439                     wordbuf[wbi++] = '\0';
 440
 441                     /* word is parsed from stdin */
 442
 443                     /* does it already exist in table? */
 444                     w = (struct word *) hash_lookup (hash, wordbuf);
 445
 446                     if (w)
 447                       {
 448                         /* yes, increment count */
 449                         ++w->n;
 450                       }
 451                     else
 452                       {
 453                         /* no, make a new object */
 454                         ALLOC_OBJ_GC (w, struct word, &gc);
 455                         w->word = string_alloc (wordbuf, &gc);
 456                         w->n = 1;
 457                         ASSERT (hash_add (hash, w->word, w, false));
 458                         ASSERT (hash_add (nhash, w->word, (void*) ((random() & 0x0F) + 1), false));
 459                       }
 460                   }
 461                 wbi = 0;
 462               }
 463           } while (c);
 464       }
 465
 466 #if 1
 467     /* remove some words from the table */
 468     {
 469       rmhash (hash, "true");
 470       rmhash (hash, "false");
 471     }
 472 #endif
 473
 474     /* output contents of hash table */
 475     {
 476       int base;
 477       int inc = 0;
 478       int count = 0;
 479
 480       for (base = 0; base < hash_n_buckets (hash); base += inc) {
 481         struct hash_iterator hi;
 482         struct hash_element *he;
 483         inc = (get_random () % 3) + 1;
 484         hash_iterator_init_range (hash, &hi, true, base, base + inc);
 485
 486         while ((he = hash_iterator_next (&hi)))
 487           {
 488             struct word *w = (struct word *) he->value;
 489             printf ("%6d '%s'\n", w->n, w->word);
 490             ++count;
 491           }
 492
 493         hash_iterator_free (&hi);
 494       }
 495       ASSERT (count == hash_n_elements (hash));
 496     }
 497
 498 #if 1
 499     /* test hash_remove_by_value function */
 500     {
 501       int i;
 502       for (i = 1; i <= 16; ++i)
 503         {
 504           printf ("[%d] ***********************************\n", i);
 505           print_nhash (nhash);
 506           hash_remove_by_value (nhash, (void *) i, true);
 507         }
 508       printf ("FINAL **************************\n");
 509       print_nhash (nhash);
 510     }
 511 #endif
 512
 513     hash_free (hash);
 514     hash_free (nhash);
 515     gc_free (&gc);
 516   }
 517
 518   openvpn_thread_cleanup ();
 519 }
 520
 521 #endif
 522
 523 /*
 524 --------------------------------------------------------------------
 525 hash() -- hash a variable-length key into a 32-bit value
 526   k     : the key (the unaligned variable-length array of bytes)
 527   len   : the length of the key, counting by bytes
 528   level : can be any 4-byte value
 529 Returns a 32-bit value.  Every bit of the key affects every bit of
 530 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 531 About 36+6len instructions.
 532
 533 The best hash table sizes are powers of 2.  There is no need to do
 534 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 535 use a bitmask.  For example, if you need only 10 bits, do
 536   h = (h & hashmask(10));
 537 In which case, the hash table should have hashsize(10) elements.
 538
 539 If you are hashing n strings (uint8_t **)k, do it like this:
 540   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 541
 542 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 543 code any way you wish, private, educational, or commercial.  It's free.
 544
 545 See http://burlteburtle.net/bob/hash/evahash.html
 546 Use for hash table lookup, or anything where one collision in 2^32 is
 547 acceptable.  Do NOT use for cryptographic purposes.
 548
 549 --------------------------------------------------------------------
 550
 551 mix -- mix 3 32-bit values reversibly.
 552 For every delta with one or two bit set, and the deltas of all three
 553   high bits or all three low bits, whether the original value of a,b,c
 554   is almost all zero or is uniformly distributed,
 555 * If mix() is run forward or backward, at least 32 bits in a,b,c
 556   have at least 1/4 probability of changing.
 557 * If mix() is run forward, every bit of c will change between 1/3 and
 558   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 559 mix() was built out of 36 single-cycle latency instructions in a
 560   structure that could supported 2x parallelism, like so:
 561       a -= b;
 562       a -= c; x = (c>>13);
 563       b -= c; a ^= x;
 564       b -= a; x = (a<<8);
 565       c -= a; b ^= x;
 566       c -= b; x = (b>>13);
 567       ...
 568   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 569   of that parallelism.  They've also turned some of those single-cycle
 570   latency instructions into multi-cycle latency instructions.  Still,
 571   this is the fastest good hash I could find.  There were about 2^^68
 572   to choose from.  I only looked at a billion or so.
 573
 574 James Yonan Notes:
 575
 576 * This function is faster than it looks, and appears to be
 577   appropriate for our usage in OpenVPN which is primarily
 578   for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC).
 579   NOTE: This function is never used for cryptographic purposes, only
 580   to produce evenly-distributed indexes into hash tables.
 581
 582 * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz,
 583                      and 12.1 machine cycles per byte on a
 584                      2.2 Ghz P4 when hashing a 6 byte string.
 585 --------------------------------------------------------------------
 586 */
 587
 588 #define mix(a,b,c)               \
 589 {                                \
 590   a -= b; a -= c; a ^= (c>>13);  \
 591   b -= c; b -= a; b ^= (a<<8);   \
 592   c -= a; c -= b; c ^= (b>>13);  \
 593   a -= b; a -= c; a ^= (c>>12);  \
 594   b -= c; b -= a; b ^= (a<<16);  \
 595   c -= a; c -= b; c ^= (b>>5);   \
 596   a -= b; a -= c; a ^= (c>>3);   \
 597   b -= c; b -= a; b ^= (a<<10);  \
 598   c -= a; c -= b; c ^= (b>>15);  \
 599 }
 600
 601 uint32_t
 602 hash_func (const uint8_t *k, uint32_t length, uint32_t initval)
 603 {
 604   uint32_t a, b, c, len;
 605
 606   /* Set up the internal state */
 607   len = length;
 608   a = b = 0x9e3779b9;        /* the golden ratio; an arbitrary value */
 609   c = initval;               /* the previous hash value */
 610
 611    /*---------------------------------------- handle most of the key */
 612   while (len >= 12)
 613     {
 614       a += (k[0] + ((uint32_t) k[1] << 8)
 615                  + ((uint32_t) k[2] << 16)
 616                  + ((uint32_t) k[3] << 24));
 617       b += (k[4] + ((uint32_t) k[5] << 8)
 618                  + ((uint32_t) k[6] << 16)
 619                  + ((uint32_t) k[7] << 24));
 620       c += (k[8] + ((uint32_t) k[9] << 8)
 621                  + ((uint32_t) k[10] << 16)
 622                  + ((uint32_t) k[11] << 24));
 623       mix (a, b, c);
 624       k += 12;
 625       len -= 12;
 626     }
 627
 628    /*------------------------------------- handle the last 11 bytes */
 629   c += length;
 630   switch (len)              /* all the case statements fall through */
 631     {
 632     case 11:
 633       c += ((uint32_t) k[10] << 24);
 634     case 10:
 635       c += ((uint32_t) k[9] << 16);
 636     case 9:
 637       c += ((uint32_t) k[8] << 8);
 638       /* the first byte of c is reserved for the length */
 639     case 8:
 640       b += ((uint32_t) k[7] << 24);
 641     case 7:
 642       b += ((uint32_t) k[6] << 16);
 643     case 6:
 644       b += ((uint32_t) k[5] << 8);
 645     case 5:
 646       b += k[4];
 647     case 4:
 648       a += ((uint32_t) k[3] << 24);
 649     case 3:
 650       a += ((uint32_t) k[2] << 16);
 651     case 2:
 652       a += ((uint32_t) k[1] << 8);
 653     case 1:
 654       a += k[0];
 655       /* case 0: nothing left to add */
 656     }
 657   mix (a, b, c);
 658    /*-------------------------------------- report the result */
 659   return c;
 660 }
 661
 662 #else
 663 static void dummy(void) {}
 664 #endif /* P2MP_SERVER */