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-2023 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 #endif
27 
28 #include "syshead.h"
29 
30 
31 #include "integer.h"
32 #include "list.h"
33 #include "misc.h"
34 
35 #include "memdbg.h"
36 
37 struct hash *
38 hash_init(const int n_buckets,
39  const uint32_t iv,
40  uint32_t (*hash_function)(const void *key, uint32_t iv),
41  bool (*compare_function)(const void *key1, const void *key2))
42 {
43  struct hash *h;
44  int i;
45 
46  ASSERT(n_buckets > 0);
47  ALLOC_OBJ_CLEAR(h, struct hash);
49  h->mask = h->n_buckets - 1;
52  h->iv = iv;
53  ALLOC_ARRAY(h->buckets, struct hash_bucket, h->n_buckets);
54  for (i = 0; i < h->n_buckets; ++i)
55  {
56  struct hash_bucket *b = &h->buckets[i];
57  b->list = NULL;
58  }
59  return h;
60 }
61 
62 void
64 {
65  int i;
66  for (i = 0; i < hash->n_buckets; ++i)
67  {
68  struct hash_bucket *b = &hash->buckets[i];
69  struct hash_element *he = b->list;
70 
71  while (he)
72  {
73  struct hash_element *next = he->next;
74  free(he);
75  he = next;
76  }
77  }
78  free(hash->buckets);
79  free(hash);
80 }
81 
82 struct hash_element *
84  struct hash_bucket *bucket,
85  const void *key,
86  uint32_t hv)
87 {
88  struct hash_element *he;
89  struct hash_element *prev = NULL;
90 
91  he = bucket->list;
92 
93  while (he)
94  {
95  if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
96  {
97  /* move to head of list */
98  if (prev)
99  {
100  prev->next = he->next;
101  he->next = bucket->list;
102  bucket->list = he;
103  }
104  return he;
105  }
106  prev = he;
107  he = he->next;
108  }
109 
110  return NULL;
111 }
112 
113 bool
115  struct hash_bucket *bucket,
116  const void *key,
117  uint32_t hv)
118 {
119  struct hash_element *he;
120  struct hash_element *prev = NULL;
121 
122  he = bucket->list;
123 
124  while (he)
125  {
126  if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
127  {
128  if (prev)
129  {
130  prev->next = he->next;
131  }
132  else
133  {
134  bucket->list = he->next;
135  }
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 
157  if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */
158  {
159  if (replace)
160  {
161  he->value = value;
162  ret = true;
163  }
164  }
165  else
166  {
167  hash_add_fast(hash, bucket, key, hv, value);
168  ret = true;
169  }
170 
171  return ret;
172 }
173 
174 void
176 {
177  struct hash_iterator hi;
178  struct hash_element *he;
179 
180  hash_iterator_init(hash, &hi);
181  while ((he = hash_iterator_next(&hi)))
182  {
183  if (he->value == value)
184  {
186  }
187  }
188  hash_iterator_free(&hi);
189 }
190 
191 static void
192 hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
193 {
194  struct hash_element *prev = NULL;
195  struct hash_element *he = bucket->list;
196 
197  while (he)
198  {
199  if (!he->key) /* marked? */
200  {
201  struct hash_element *newhe;
202  if (prev)
203  {
204  newhe = prev->next = he->next;
205  }
206  else
207  {
208  newhe = bucket->list = he->next;
209  }
210  free(he);
211  --hash->n_elements;
212  he = newhe;
213  }
214  else
215  {
216  prev = he;
217  he = he->next;
218  }
219  }
220 }
221 
222 void
224  struct hash_iterator *hi,
225  int start_bucket,
226  int end_bucket)
227 {
228  if (end_bucket > hash->n_buckets)
229  {
230  end_bucket = hash->n_buckets;
231  }
232 
233  ASSERT(start_bucket >= 0 && start_bucket <= end_bucket);
234 
235  hi->hash = hash;
236  hi->elem = NULL;
237  hi->bucket = NULL;
238  hi->last = NULL;
239  hi->bucket_marked = false;
240  hi->bucket_index_start = start_bucket;
241  hi->bucket_index_end = end_bucket;
242  hi->bucket_index = hi->bucket_index_start - 1;
243 }
244 
245 void
247  struct hash_iterator *hi)
248 {
250 }
251 
252 static inline void
254 {
255  hi->bucket = b;
256  hi->last = NULL;
257  hi->bucket_marked = false;
258 }
259 
260 static inline void
262 {
263  if (hi->bucket)
264  {
265  if (hi->bucket_marked)
266  {
267  hash_remove_marked(hi->hash, hi->bucket);
268  hi->bucket_marked = false;
269  }
270  hi->bucket = NULL;
271  hi->last = NULL;
272  }
273 }
274 
275 static inline void
277 {
278  hi->last = hi->elem;
279  hi->elem = hi->elem->next;
280 }
281 
282 void
284 {
286 }
287 
288 struct hash_element *
290 {
291  struct hash_element *ret = NULL;
292  if (hi->elem)
293  {
294  ret = hi->elem;
296  }
297  else
298  {
299  while (++hi->bucket_index < hi->bucket_index_end)
300  {
301  struct hash_bucket *b;
303  b = &hi->hash->buckets[hi->bucket_index];
304  if (b->list)
305  {
306  hash_iterator_lock(hi, b);
307  hi->elem = b->list;
308  if (hi->elem)
309  {
310  ret = hi->elem;
312  break;
313  }
314  }
315  }
316  }
317  return ret;
318 }
319 
320 void
322 {
323  ASSERT(hi->last);
324  hi->last->key = NULL;
325  hi->bucket_marked = true;
326 }
327 
328 
329 #ifdef LIST_TEST
330 
331 /*
332  * Test the hash code by implementing a simple
333  * word frequency algorithm.
334  */
335 
336 struct word
337 {
338  const char *word;
339  int n;
340 };
341 
342 static uint32_t
343 word_hash_function(const void *key, uint32_t iv)
344 {
345  const char *str = (const char *) key;
346  const int len = strlen(str);
347  return hash_func((const uint8_t *)str, len, iv);
348 }
349 
350 static bool
351 word_compare_function(const void *key1, const void *key2)
352 {
353  return strcmp((const char *)key1, (const char *)key2) == 0;
354 }
355 
356 static void
357 print_nhash(struct hash *hash)
358 {
359  struct hash_iterator hi;
360  struct hash_element *he;
361  int count = 0;
362 
363  hash_iterator_init(hash, &hi, true);
364 
365  while ((he = hash_iterator_next(&hi)))
366  {
367  printf("%d ", (int) he->value);
368  ++count;
369  }
370  printf("\n");
371 
372  hash_iterator_free(&hi);
373  ASSERT(count == hash_n_elements(hash));
374 }
375 
376 static void
377 rmhash(struct hash *hash, const char *word)
378 {
379  hash_remove(hash, word);
380 }
381 
382 void
383 list_test(void)
384 {
385  openvpn_thread_init();
386 
387  {
388  struct gc_arena gc = gc_new();
389  struct hash *hash = hash_init(10000, get_random(), word_hash_function, word_compare_function);
390  struct hash *nhash = hash_init(256, get_random(), word_hash_function, word_compare_function);
391 
392  printf("hash_init n_buckets=%d mask=0x%08x\n", hash->n_buckets, hash->mask);
393 
394  /* parse words from stdin */
395  while (true)
396  {
397  char buf[256];
398  char wordbuf[256];
399  int wbi;
400  int bi;
401  char c;
402 
403  if (!fgets(buf, sizeof(buf), stdin))
404  {
405  break;
406  }
407 
408  bi = wbi = 0;
409  do
410  {
411  c = buf[bi++];
412  if (isalnum(c) || c == '_')
413  {
414  ASSERT(wbi < (int) sizeof(wordbuf));
415  wordbuf[wbi++] = c;
416  }
417  else
418  {
419  if (wbi)
420  {
421  struct word *w;
422  ASSERT(wbi < (int) sizeof(wordbuf));
423  wordbuf[wbi++] = '\0';
424 
425  /* word is parsed from stdin */
426 
427  /* does it already exist in table? */
428  w = (struct word *) hash_lookup(hash, wordbuf);
429 
430  if (w)
431  {
432  /* yes, increment count */
433  ++w->n;
434  }
435  else
436  {
437  /* no, make a new object */
438  ALLOC_OBJ_GC(w, struct word, &gc);
439  w->word = string_alloc(wordbuf, &gc);
440  w->n = 1;
441  ASSERT(hash_add(hash, w->word, w, false));
442  ASSERT(hash_add(nhash, w->word, (void *) ((random() & 0x0F) + 1), false));
443  }
444  }
445  wbi = 0;
446  }
447  } while (c);
448  }
449 
450 #if 1
451  /* remove some words from the table */
452  {
453  rmhash(hash, "true");
454  rmhash(hash, "false");
455  }
456 #endif
457 
458  /* output contents of hash table */
459  {
460  int base;
461  int inc = 0;
462  int count = 0;
463 
464  for (base = 0; base < hash_n_buckets(hash); base += inc)
465  {
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 /* ifdef LIST_TEST */
507 
508 /*
509  * --------------------------------------------------------------------
510  * hash() -- 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
514  * Returns a 32-bit value. Every bit of the key affects every bit of
515  * the return value. Every 1-bit and 2-bit delta achieves avalanche.
516  * About 36+6len instructions.
517  *
518  * The best hash table sizes are powers of 2. There is no need to do
519  * mod a prime (mod is sooo slow!). If you need less than 32 bits,
520  * use a bitmask. For example, if you need only 10 bits, do
521  * h = (h & hashmask(10));
522  * In which case, the hash table should have hashsize(10) elements.
523  *
524  * If 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  *
527  * By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
528  * code any way you wish, private, educational, or commercial. It's free.
529  *
530  * See http://burlteburtle.net/bob/hash/evahash.html
531  * Use for hash table lookup, or anything where one collision in 2^32 is
532  * acceptable. Do NOT use for cryptographic purposes.
533  *
534  * --------------------------------------------------------------------
535  *
536  * mix -- mix 3 32-bit values reversibly.
537  * For 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.)
544  * mix() 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  *
559  * James 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 
586 uint32_t
587 hash_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 
620  case 10:
621  c += ((uint32_t) k[9] << 16);
622 
623  case 9:
624  c += ((uint32_t) k[8] << 8);
625 
626  /* the first byte of c is reserved for the length */
627  case 8:
628  b += ((uint32_t) k[7] << 24);
629 
630  case 7:
631  b += ((uint32_t) k[6] << 16);
632 
633  case 6:
634  b += ((uint32_t) k[5] << 8);
635 
636  case 5:
637  b += k[4];
638 
639  case 4:
640  a += ((uint32_t) k[3] << 24);
641 
642  case 3:
643  a += ((uint32_t) k[2] << 16);
644 
645  case 2:
646  a += ((uint32_t) k[1] << 8);
647 
648  case 1:
649  a += k[0];
650  /* case 0: nothing left to add */
651  }
652  mix(a, b, c);
653  /*-------------------------------------- report the result */
654  return c;
655 }
hash::n_elements
int n_elements
Definition: list.h:61
hash_n_elements
static int hash_n_elements(const struct hash *hash)
Definition: list.h:129
hash_init
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:38
gc_new
static struct gc_arena gc_new(void)
Definition: buffer.h:1031
hash_iterator
Definition: list.h:90
hash
Definition: list.h:58
hash_element::next
struct hash_element * next
Definition: list.h:50
key1
static const char *const key1
Definition: cert_data.h:56
get_random
long int get_random(void)
Definition: crypto.c:1611
hash_iterator::bucket_index_end
int bucket_index_end
Definition: list.h:99
hash_add
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition: list.c:147
hash_element::value
void * value
Definition: list.h:47
hash_remove
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:183
hash_lookup
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:147
hash::buckets
struct hash_bucket * buckets
Definition: list.h:66
hash_iterator_lock
static void hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b)
Definition: list.c:253
key
Container for unidirectional cipher and HMAC key material.
Definition: crypto.h:149
hash_remove_by_value
void hash_remove_by_value(struct hash *hash, void *value)
Definition: list.c:175
hash_iterator_free
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:283
string_alloc
char * string_alloc(const char *str, struct gc_arena *gc)
Definition: buffer.c:693
hash::hash_function
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition: list.h:64
ASSERT
#define ASSERT(x)
Definition: error.h:201
hash_iterator_next
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:289
hash_add_fast
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition: list.h:165
hash_element::key
const void * key
Definition: list.h:48
hash_bucket::list
struct hash_element * list
Definition: list.h:55
misc.h
hash_lookup_fast
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:83
hash_iterator::elem
struct hash_element * elem
Definition: list.h:95
adjust_power_of_2
static size_t adjust_power_of_2(size_t u)
Definition: integer.h:168
hash::mask
int mask
Definition: list.h:62
hash_iterator_delete_element
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition: list.c:321
hash_iterator::bucket_index
int bucket_index
Definition: list.h:93
syshead.h
hash_iterator_init
void hash_iterator_init(struct hash *hash, struct hash_iterator *hi)
Definition: list.c:246
gc_arena
Garbage collection arena used to keep track of dynamically allocated memory.
Definition: buffer.h:116
hash::iv
uint32_t iv
Definition: list.h:63
hash_iterator::bucket
struct hash_bucket * bucket
Definition: list.h:94
hash_remove_marked
static void hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
Definition: list.c:192
hash_free
void hash_free(struct hash *hash)
Definition: list.c:63
hash_iterator_unlock
static void hash_iterator_unlock(struct hash_iterator *hi)
Definition: list.c:261
hash_remove_fast
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:114
hash_element
Definition: list.h:45
gc_free
static void gc_free(struct gc_arena *a)
Definition: buffer.h:1039
mix
#define mix(a, b, c)
Definition: list.c:573
hash_bucket
Definition: list.h:53
ALLOC_OBJ_CLEAR
#define ALLOC_OBJ_CLEAR(dptr, type)
Definition: buffer.h:1066
hash_iterator_advance
static void hash_iterator_advance(struct hash_iterator *hi)
Definition: list.c:276
hash_iterator::bucket_index_start
int bucket_index_start
Definition: list.h:98
config.h
hash_iterator::hash
struct hash * hash
Definition: list.h:92
hash_element::hash_value
unsigned int hash_value
Definition: list.h:49
key2
Container for bidirectional cipher and HMAC key material.
Definition: crypto.h:179
hash::n_buckets
int n_buckets
Definition: list.h:60
hash_iterator::bucket_marked
bool bucket_marked
Definition: list.h:97
hash_n_buckets
static int hash_n_buckets(const struct hash *hash)
Definition: list.h:135
list.h
hash::compare_function
bool(* compare_function)(const void *key1, const void *key2)
Definition: list.h:65
random
#define random
Definition: syshead.h:44
memdbg.h
hash_iterator::last
struct hash_element * last
Definition: list.h:96
ALLOC_ARRAY
#define ALLOC_ARRAY(dptr, type, n)
Definition: buffer.h:1072
hash_func
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:587
integer.h
hash_iterator_init_range
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition: list.c:223
ALLOC_OBJ_GC
#define ALLOC_OBJ_GC(dptr, type, gc)
Definition: buffer.h:1098
hash_value
static uint32_t hash_value(const struct hash *hash, const void *key)
Definition: list.h:123