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