OpenVPN
list.c
Go to the documentation of this file.
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-2018 OpenVPN 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 along
20  * with this program; if not, write to the Free Software Foundation, Inc.,
21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22  */
23 
24 #ifdef HAVE_CONFIG_H
25 #include "config.h"
26 #elif defined(_MSC_VER)
27 #include "config-msvc.h"
28 #endif
29 
30 #include "syshead.h"
31 
32 #if P2MP_SERVER
33 
34 #include "integer.h"
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  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;
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 
65 void
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 
85 struct hash_element *
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 
116 bool
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  {
133  prev->next = he->next;
134  }
135  else
136  {
137  bucket->list = he->next;
138  }
139  free(he);
140  --hash->n_elements;
141  return true;
142  }
143  prev = he;
144  he = he->next;
145  }
146  return false;
147 }
148 
149 bool
150 hash_add(struct hash *hash, const void *key, void *value, bool replace)
151 {
152  uint32_t hv;
153  struct hash_bucket *bucket;
154  struct hash_element *he;
155  bool ret = false;
156 
157  hv = hash_value(hash, key);
158  bucket = &hash->buckets[hv & hash->mask];
159 
160  if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */
161  {
162  if (replace)
163  {
164  he->value = value;
165  ret = true;
166  }
167  }
168  else
169  {
170  hash_add_fast(hash, bucket, key, hv, value);
171  ret = true;
172  }
173 
174  return ret;
175 }
176 
177 void
179 {
180  struct hash_iterator hi;
181  struct hash_element *he;
182 
183  hash_iterator_init(hash, &hi);
184  while ((he = hash_iterator_next(&hi)))
185  {
186  if (he->value == value)
187  {
189  }
190  }
191  hash_iterator_free(&hi);
192 }
193 
194 static void
195 hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
196 {
197  struct hash_element *prev = NULL;
198  struct hash_element *he = bucket->list;
199 
200  while (he)
201  {
202  if (!he->key) /* marked? */
203  {
204  struct hash_element *newhe;
205  if (prev)
206  {
207  newhe = prev->next = he->next;
208  }
209  else
210  {
211  newhe = bucket->list = he->next;
212  }
213  free(he);
214  --hash->n_elements;
215  he = newhe;
216  }
217  else
218  {
219  prev = he;
220  he = he->next;
221  }
222  }
223 }
224 
225 uint32_t
226 void_ptr_hash_function(const void *key, uint32_t iv)
227 {
228  return hash_func((const void *)&key, sizeof(key), iv);
229 }
230 
231 bool
232 void_ptr_compare_function(const void *key1, const void *key2)
233 {
234  return key1 == key2;
235 }
236 
237 void
239  struct hash_iterator *hi,
240  int start_bucket,
241  int end_bucket)
242 {
243  if (end_bucket > hash->n_buckets)
244  {
245  end_bucket = hash->n_buckets;
246  }
247 
248  ASSERT(start_bucket >= 0 && start_bucket <= end_bucket);
249 
250  hi->hash = hash;
251  hi->elem = NULL;
252  hi->bucket = NULL;
253  hi->last = NULL;
254  hi->bucket_marked = false;
255  hi->bucket_index_start = start_bucket;
256  hi->bucket_index_end = end_bucket;
257  hi->bucket_index = hi->bucket_index_start - 1;
258 }
259 
260 void
262  struct hash_iterator *hi)
263 {
264  hash_iterator_init_range(hash, hi, 0, hash->n_buckets);
265 }
266 
267 static inline void
269 {
270  hi->bucket = b;
271  hi->last = NULL;
272  hi->bucket_marked = false;
273 }
274 
275 static inline void
277 {
278  if (hi->bucket)
279  {
280  if (hi->bucket_marked)
281  {
282  hash_remove_marked(hi->hash, hi->bucket);
283  hi->bucket_marked = false;
284  }
285  hi->bucket = NULL;
286  hi->last = NULL;
287  }
288 }
289 
290 static inline void
292 {
293  hi->last = hi->elem;
294  hi->elem = hi->elem->next;
295 }
296 
297 void
299 {
301 }
302 
303 struct hash_element *
305 {
306  struct hash_element *ret = NULL;
307  if (hi->elem)
308  {
309  ret = hi->elem;
311  }
312  else
313  {
314  while (++hi->bucket_index < hi->bucket_index_end)
315  {
316  struct hash_bucket *b;
318  b = &hi->hash->buckets[hi->bucket_index];
319  if (b->list)
320  {
321  hash_iterator_lock(hi, b);
322  hi->elem = b->list;
323  if (hi->elem)
324  {
325  ret = hi->elem;
327  break;
328  }
329  }
330  }
331  }
332  return ret;
333 }
334 
335 void
337 {
338  ASSERT(hi->last);
339  hi->last->key = NULL;
340  hi->bucket_marked = true;
341 }
342 
343 
344 #ifdef LIST_TEST
345 
346 /*
347  * Test the hash code by implementing a simple
348  * word frequency algorithm.
349  */
350 
351 struct word
352 {
353  const char *word;
354  int n;
355 };
356 
357 static uint32_t
358 word_hash_function(const void *key, uint32_t iv)
359 {
360  const char *str = (const char *) key;
361  const int len = strlen(str);
362  return hash_func((const uint8_t *)str, len, iv);
363 }
364 
365 static bool
366 word_compare_function(const void *key1, const void *key2)
367 {
368  return strcmp((const char *)key1, (const char *)key2) == 0;
369 }
370 
371 static void
372 print_nhash(struct hash *hash)
373 {
374  struct hash_iterator hi;
375  struct hash_element *he;
376  int count = 0;
377 
378  hash_iterator_init(hash, &hi, true);
379 
380  while ((he = hash_iterator_next(&hi)))
381  {
382  printf("%d ", (int) he->value);
383  ++count;
384  }
385  printf("\n");
386 
387  hash_iterator_free(&hi);
388  ASSERT(count == hash_n_elements(hash));
389 }
390 
391 static void
392 rmhash(struct hash *hash, const char *word)
393 {
394  hash_remove(hash, word);
395 }
396 
397 void
398 list_test(void)
399 {
400  openvpn_thread_init();
401 
402  {
403  struct gc_arena gc = gc_new();
404  struct hash *hash = hash_init(10000, get_random(), word_hash_function, word_compare_function);
405  struct hash *nhash = hash_init(256, get_random(), word_hash_function, word_compare_function);
406 
407  printf("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask);
408 
409  /* parse words from stdin */
410  while (true)
411  {
412  char buf[256];
413  char wordbuf[256];
414  int wbi;
415  int bi;
416  char c;
417 
418  if (!fgets(buf, sizeof(buf), stdin))
419  {
420  break;
421  }
422 
423  bi = wbi = 0;
424  do
425  {
426  c = buf[bi++];
427  if (isalnum(c) || c == '_')
428  {
429  ASSERT(wbi < (int) sizeof(wordbuf));
430  wordbuf[wbi++] = c;
431  }
432  else
433  {
434  if (wbi)
435  {
436  struct word *w;
437  ASSERT(wbi < (int) sizeof(wordbuf));
438  wordbuf[wbi++] = '\0';
439 
440  /* word is parsed from stdin */
441 
442  /* does it already exist in table? */
443  w = (struct word *) hash_lookup(hash, wordbuf);
444 
445  if (w)
446  {
447  /* yes, increment count */
448  ++w->n;
449  }
450  else
451  {
452  /* no, make a new object */
453  ALLOC_OBJ_GC(w, struct word, &gc);
454  w->word = string_alloc(wordbuf, &gc);
455  w->n = 1;
456  ASSERT(hash_add(hash, w->word, w, false));
457  ASSERT(hash_add(nhash, w->word, (void *) ((random() & 0x0F) + 1), false));
458  }
459  }
460  wbi = 0;
461  }
462  } while (c);
463  }
464 
465 #if 1
466  /* remove some words from the table */
467  {
468  rmhash(hash, "true");
469  rmhash(hash, "false");
470  }
471 #endif
472 
473  /* output contents of hash table */
474  {
475  int base;
476  int inc = 0;
477  int count = 0;
478 
479  for (base = 0; base < hash_n_buckets(hash); base += inc)
480  {
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 /* ifdef LIST_TEST */
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 
635  case 10:
636  c += ((uint32_t) k[9] << 16);
637 
638  case 9:
639  c += ((uint32_t) k[8] << 8);
640 
641  /* the first byte of c is reserved for the length */
642  case 8:
643  b += ((uint32_t) k[7] << 24);
644 
645  case 7:
646  b += ((uint32_t) k[6] << 16);
647 
648  case 6:
649  b += ((uint32_t) k[5] << 8);
650 
651  case 5:
652  b += k[4];
653 
654  case 4:
655  a += ((uint32_t) k[3] << 24);
656 
657  case 3:
658  a += ((uint32_t) k[2] << 16);
659 
660  case 2:
661  a += ((uint32_t) k[1] << 8);
662 
663  case 1:
664  a += k[0];
665  /* case 0: nothing left to add */
666  }
667  mix(a, b, c);
668  /*-------------------------------------- report the result */
669  return c;
670 }
671 
672 #else /* if P2MP_SERVER */
673 static void
674 dummy(void)
675 {
676 }
677 #endif /* P2MP_SERVER */
char * string_alloc(const char *str, struct gc_arena *gc)
Definition: buffer.c:663
void hash_free(struct hash *hash)
Definition: list.c:66
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition: list.h:171
struct hash_element * next
Definition: list.h:52
static void gc_free(struct gc_arena *a)
Definition: buffer.h:999
int n_elements
Definition: list.h:63
#define ASSERT(x)
Definition: error.h:221
const void * key
Definition: list.h:50
static void dummy(void)
Definition: comp-lz4.c:319
#define ALLOC_ARRAY(dptr, type, n)
Definition: buffer.h:1032
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition: list.h:66
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))
Definition: list.c:41
struct hash_bucket * bucket
Definition: list.h:96
#define ALLOC_OBJ_GC(dptr, type, gc)
Definition: buffer.h:1058
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition: list.c:150
struct hash_element * list
Definition: list.h:57
struct hash_bucket * buckets
Definition: list.h:68
int bucket_index_start
Definition: list.h:100
static struct gc_arena gc_new(void)
Definition: buffer.h:991
#define ALLOC_OBJ_CLEAR(dptr, type)
Definition: buffer.h:1026
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:117
static size_t adjust_power_of_2(size_t u)
Definition: integer.h:126
void hash_iterator_init(struct hash *hash, struct hash_iterator *hi)
Definition: list.c:261
static void hash_iterator_unlock(struct hash_iterator *hi)
Definition: list.c:276
unsigned __int32 uint32_t
Definition: config-msvc.h:120
#define mix(a, b, c)
Definition: list.c:588
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:153
bool void_ptr_compare_function(const void *key1, const void *key2)
Definition: list.c:232
static void hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
Definition: list.c:195
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition: list.c:238
uint32_t iv
Definition: list.h:65
int mask
Definition: list.h:64
static int hash_n_buckets(const struct hash *hash)
Definition: list.h:141
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:304
int bucket_index
Definition: list.h:95
Container for bidirectional cipher and HMAC key material.
Definition: crypto.h:181
static uint32_t hash_value(const struct hash *hash, const void *key)
Definition: list.h:129
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:602
unsigned __int8 uint8_t
Definition: config-msvc.h:122
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:298
int n_buckets
Definition: list.h:62
#define random
Definition: syshead.h:43
struct hash_element * last
Definition: list.h:98
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:86
int bucket_index_end
Definition: list.h:101
bool(* compare_function)(const void *key1, const void *key2)
Definition: list.h:67
static int hash_n_elements(const struct hash *hash)
Definition: list.h:135
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:189
bool bucket_marked
Definition: list.h:99
#define free
Definition: cmocka.c:1850
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition: list.c:336
void * value
Definition: list.h:49
uint32_t void_ptr_hash_function(const void *key, uint32_t iv)
Definition: list.c:226
Garbage collection arena used to keep track of dynamically allocated memory.
Definition: buffer.h:116
long int get_random(void)
Definition: crypto.c:1761
void hash_remove_by_value(struct hash *hash, void *value)
Definition: list.c:178
Definition: list.h:60
struct hash_element * elem
Definition: list.h:97
static void hash_iterator_advance(struct hash_iterator *hi)
Definition: list.c:291
Container for unidirectional cipher and HMAC key material.
Definition: crypto.h:151
static void hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b)
Definition: list.c:268
struct hash * hash
Definition: list.h:94
unsigned int hash_value
Definition: list.h:51