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