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 void
227  struct hash_iterator *hi,
228  int start_bucket,
229  int end_bucket)
230 {
231  if (end_bucket > hash->n_buckets)
232  {
233  end_bucket = hash->n_buckets;
234  }
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 
248 void
250  struct hash_iterator *hi)
251 {
252  hash_iterator_init_range(hash, hi, 0, hash->n_buckets);
253 }
254 
255 static inline void
257 {
258  hi->bucket = b;
259  hi->last = NULL;
260  hi->bucket_marked = false;
261 }
262 
263 static inline void
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 
278 static inline void
280 {
281  hi->last = hi->elem;
282  hi->elem = hi->elem->next;
283 }
284 
285 void
287 {
289 }
290 
291 struct hash_element *
293 {
294  struct hash_element *ret = NULL;
295  if (hi->elem)
296  {
297  ret = hi->elem;
299  }
300  else
301  {
302  while (++hi->bucket_index < hi->bucket_index_end)
303  {
304  struct hash_bucket *b;
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;
315  break;
316  }
317  }
318  }
319  }
320  return ret;
321 }
322 
323 void
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 
339 struct word
340 {
341  const char *word;
342  int n;
343 };
344 
345 static uint32_t
346 word_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 
353 static bool
354 word_compare_function(const void *key1, const void *key2)
355 {
356  return strcmp((const char *)key1, (const char *)key2) == 0;
357 }
358 
359 static void
360 print_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 
379 static void
380 rmhash(struct hash *hash, const char *word)
381 {
382  hash_remove(hash, word);
383 }
384 
385 void
386 list_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  {
408  break;
409  }
410 
411  bi = wbi = 0;
412  do
413  {
414  c = buf[bi++];
415  if (isalnum(c) || c == '_')
416  {
417  ASSERT(wbi < (int) sizeof(wordbuf));
418  wordbuf[wbi++] = c;
419  }
420  else
421  {
422  if (wbi)
423  {
424  struct word *w;
425  ASSERT(wbi < (int) sizeof(wordbuf));
426  wordbuf[wbi++] = '\0';
427 
428  /* word is parsed from stdin */
429 
430  /* does it already exist in table? */
431  w = (struct word *) hash_lookup(hash, wordbuf);
432 
433  if (w)
434  {
435  /* yes, increment count */
436  ++w->n;
437  }
438  else
439  {
440  /* no, make a new object */
441  ALLOC_OBJ_GC(w, struct word, &gc);
442  w->word = string_alloc(wordbuf, &gc);
443  w->n = 1;
444  ASSERT(hash_add(hash, w->word, w, false));
445  ASSERT(hash_add(nhash, w->word, (void *) ((random() & 0x0F) + 1), false));
446  }
447  }
448  wbi = 0;
449  }
450  } while (c);
451  }
452 
453 #if 1
454  /* remove some words from the table */
455  {
456  rmhash(hash, "true");
457  rmhash(hash, "false");
458  }
459 #endif
460 
461  /* output contents of hash table */
462  {
463  int base;
464  int inc = 0;
465  int count = 0;
466 
467  for (base = 0; base < hash_n_buckets(hash); base += inc)
468  {
469  struct hash_iterator hi;
470  struct hash_element *he;
471  inc = (get_random() % 3) + 1;
472  hash_iterator_init_range(hash, &hi, true, base, base + inc);
473 
474  while ((he = hash_iterator_next(&hi)))
475  {
476  struct word *w = (struct word *) he->value;
477  printf("%6d '%s'\n", w->n, w->word);
478  ++count;
479  }
480 
481  hash_iterator_free(&hi);
482  }
483  ASSERT(count == hash_n_elements(hash));
484  }
485 
486 #if 1
487  /* test hash_remove_by_value function */
488  {
489  int i;
490  for (i = 1; i <= 16; ++i)
491  {
492  printf("[%d] ***********************************\n", i);
493  print_nhash(nhash);
494  hash_remove_by_value(nhash, (void *) i, true);
495  }
496  printf("FINAL **************************\n");
497  print_nhash(nhash);
498  }
499 #endif
500 
501  hash_free(hash);
502  hash_free(nhash);
503  gc_free(&gc);
504  }
505 
506  openvpn_thread_cleanup();
507 }
508 
509 #endif /* ifdef LIST_TEST */
510 
511 /*
512  * --------------------------------------------------------------------
513  * hash() -- hash a variable-length key into a 32-bit value
514  * k : the key (the unaligned variable-length array of bytes)
515  * len : the length of the key, counting by bytes
516  * level : can be any 4-byte value
517  * Returns a 32-bit value. Every bit of the key affects every bit of
518  * the return value. Every 1-bit and 2-bit delta achieves avalanche.
519  * About 36+6len instructions.
520  *
521  * The best hash table sizes are powers of 2. There is no need to do
522  * mod a prime (mod is sooo slow!). If you need less than 32 bits,
523  * use a bitmask. For example, if you need only 10 bits, do
524  * h = (h & hashmask(10));
525  * In which case, the hash table should have hashsize(10) elements.
526  *
527  * If you are hashing n strings (uint8_t **)k, do it like this:
528  * for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
529  *
530  * By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
531  * code any way you wish, private, educational, or commercial. It's free.
532  *
533  * See http://burlteburtle.net/bob/hash/evahash.html
534  * Use for hash table lookup, or anything where one collision in 2^32 is
535  * acceptable. Do NOT use for cryptographic purposes.
536  *
537  * --------------------------------------------------------------------
538  *
539  * mix -- mix 3 32-bit values reversibly.
540  * For every delta with one or two bit set, and the deltas of all three
541  * high bits or all three low bits, whether the original value of a,b,c
542  * is almost all zero or is uniformly distributed,
543  * If mix() is run forward or backward, at least 32 bits in a,b,c
544  * have at least 1/4 probability of changing.
545  * If mix() is run forward, every bit of c will change between 1/3 and
546  * 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
547  * mix() was built out of 36 single-cycle latency instructions in a
548  * structure that could supported 2x parallelism, like so:
549  * a -= b;
550  * a -= c; x = (c>>13);
551  * b -= c; a ^= x;
552  * b -= a; x = (a<<8);
553  * c -= a; b ^= x;
554  * c -= b; x = (b>>13);
555  * ...
556  * Unfortunately, superscalar Pentiums and Sparcs can't take advantage
557  * of that parallelism. They've also turned some of those single-cycle
558  * latency instructions into multi-cycle latency instructions. Still,
559  * this is the fastest good hash I could find. There were about 2^^68
560  * to choose from. I only looked at a billion or so.
561  *
562  * James Yonan Notes:
563  *
564  * This function is faster than it looks, and appears to be
565  * appropriate for our usage in OpenVPN which is primarily
566  * for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC).
567  * NOTE: This function is never used for cryptographic purposes, only
568  * to produce evenly-distributed indexes into hash tables.
569  *
570  * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz,
571  * and 12.1 machine cycles per byte on a
572  * 2.2 Ghz P4 when hashing a 6 byte string.
573  * --------------------------------------------------------------------
574  */
575 
576 #define mix(a,b,c) \
577  { \
578  a -= b; a -= c; a ^= (c>>13); \
579  b -= c; b -= a; b ^= (a<<8); \
580  c -= a; c -= b; c ^= (b>>13); \
581  a -= b; a -= c; a ^= (c>>12); \
582  b -= c; b -= a; b ^= (a<<16); \
583  c -= a; c -= b; c ^= (b>>5); \
584  a -= b; a -= c; a ^= (c>>3); \
585  b -= c; b -= a; b ^= (a<<10); \
586  c -= a; c -= b; c ^= (b>>15); \
587  }
588 
589 uint32_t
590 hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
591 {
592  uint32_t a, b, c, len;
593 
594  /* Set up the internal state */
595  len = length;
596  a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
597  c = initval; /* the previous hash value */
598 
599  /*---------------------------------------- handle most of the key */
600  while (len >= 12)
601  {
602  a += (k[0] + ((uint32_t) k[1] << 8)
603  + ((uint32_t) k[2] << 16)
604  + ((uint32_t) k[3] << 24));
605  b += (k[4] + ((uint32_t) k[5] << 8)
606  + ((uint32_t) k[6] << 16)
607  + ((uint32_t) k[7] << 24));
608  c += (k[8] + ((uint32_t) k[9] << 8)
609  + ((uint32_t) k[10] << 16)
610  + ((uint32_t) k[11] << 24));
611  mix(a, b, c);
612  k += 12;
613  len -= 12;
614  }
615 
616  /*------------------------------------- handle the last 11 bytes */
617  c += length;
618  switch (len) /* all the case statements fall through */
619  {
620  case 11:
621  c += ((uint32_t) k[10] << 24);
622 
623  case 10:
624  c += ((uint32_t) k[9] << 16);
625 
626  case 9:
627  c += ((uint32_t) k[8] << 8);
628 
629  /* the first byte of c is reserved for the length */
630  case 8:
631  b += ((uint32_t) k[7] << 24);
632 
633  case 7:
634  b += ((uint32_t) k[6] << 16);
635 
636  case 6:
637  b += ((uint32_t) k[5] << 8);
638 
639  case 5:
640  b += k[4];
641 
642  case 4:
643  a += ((uint32_t) k[3] << 24);
644 
645  case 3:
646  a += ((uint32_t) k[2] << 16);
647 
648  case 2:
649  a += ((uint32_t) k[1] << 8);
650 
651  case 1:
652  a += k[0];
653  /* case 0: nothing left to add */
654  }
655  mix(a, b, c);
656  /*-------------------------------------- report the result */
657  return c;
658 }
659 
660 #else /* if P2MP_SERVER */
661 static void
662 dummy(void)
663 {
664 }
665 #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:167
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:249
static void hash_iterator_unlock(struct hash_iterator *hi)
Definition: list.c:264
unsigned __int32 uint32_t
Definition: config-msvc.h:121
#define mix(a, b, c)
Definition: list.c:576
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:149
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:226
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:137
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:292
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:125
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:590
unsigned __int8 uint8_t
Definition: config-msvc.h:123
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:286
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:131
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:185
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:324
void * value
Definition: list.h:49
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:279
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:256
struct hash * hash
Definition: list.h:94
unsigned int hash_value
Definition: list.h:51