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-2025 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, see <https://www.gnu.org/licenses/>.
21 */
22
23#ifdef HAVE_CONFIG_H
24#include "config.h"
25#endif
26
27#include "syshead.h"
28
29
30#include "integer.h"
31#include "list.h"
32#include "misc.h"
33
34#include "memdbg.h"
35
36struct hash *
37hash_init(const uint32_t n_buckets, const uint32_t iv,
38 uint32_t (*hash_function)(const void *key, uint32_t iv),
39 bool (*compare_function)(const void *key1, const void *key2))
40{
41 struct hash *h;
42
43 ASSERT(n_buckets > 0);
44 ALLOC_OBJ_CLEAR(h, struct hash);
46 h->mask = h->n_buckets - 1;
49 h->iv = iv;
51 for (uint32_t i = 0; i < h->n_buckets; ++i)
52 {
53 struct hash_bucket *b = &h->buckets[i];
54 b->list = NULL;
55 }
56 return h;
57}
58
59void
61{
62 for (uint32_t i = 0; i < hash->n_buckets; ++i)
63 {
64 struct hash_bucket *b = &hash->buckets[i];
65 struct hash_element *he = b->list;
66
67 while (he)
68 {
69 struct hash_element *next = he->next;
70 free(he);
71 he = next;
72 }
73 }
74 free(hash->buckets);
75 free(hash);
76}
77
78struct hash_element *
79hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
80{
81 struct hash_element *he;
82 struct hash_element *prev = NULL;
83
84 he = bucket->list;
85
86 while (he)
87 {
88 if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
89 {
90 /* move to head of list */
91 if (prev)
92 {
93 prev->next = he->next;
94 he->next = bucket->list;
95 bucket->list = he;
96 }
97 return he;
98 }
99 prev = he;
100 he = he->next;
101 }
102
103 return NULL;
104}
105
106bool
107hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
108{
109 struct hash_element *he;
110 struct hash_element *prev = NULL;
111
112 he = bucket->list;
113
114 while (he)
115 {
116 if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
117 {
118 if (prev)
119 {
120 prev->next = he->next;
121 }
122 else
123 {
124 bucket->list = he->next;
125 }
126 free(he);
127 --hash->n_elements;
128 return true;
129 }
130 prev = he;
131 he = he->next;
132 }
133 return false;
134}
135
136bool
137hash_add(struct hash *hash, const void *key, void *value, bool replace)
138{
139 uint32_t hv;
140 struct hash_bucket *bucket;
141 struct hash_element *he;
142 bool ret = false;
143
144 hv = hash_value(hash, key);
145 bucket = &hash->buckets[hv & hash->mask];
146
147 if ((he = hash_lookup_fast(hash, bucket, key, hv))) /* already exists? */
148 {
149 if (replace)
150 {
151 he->value = value;
152 ret = true;
153 }
154 }
155 else
156 {
157 hash_add_fast(hash, bucket, key, hv, value);
158 ret = true;
159 }
160
161 return ret;
162}
163
164void
166{
167 struct hash_iterator hi;
168 struct hash_element *he;
169
171 while ((he = hash_iterator_next(&hi)))
172 {
173 if (he->value == value)
174 {
176 }
177 }
179}
180
181static void
182hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
183{
184 struct hash_element *prev = NULL;
185 struct hash_element *he = bucket->list;
186
187 while (he)
188 {
189 if (!he->key) /* marked? */
190 {
191 struct hash_element *newhe;
192 if (prev)
193 {
194 newhe = prev->next = he->next;
195 }
196 else
197 {
198 newhe = bucket->list = he->next;
199 }
200 free(he);
201 --hash->n_elements;
202 he = newhe;
203 }
204 else
205 {
206 prev = he;
207 he = he->next;
208 }
209 }
210}
211
212void
213hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, uint32_t start_bucket,
214 uint32_t end_bucket)
215{
216 if (end_bucket > hash->n_buckets)
217 {
218 end_bucket = hash->n_buckets;
219 }
220
221 ASSERT(start_bucket <= end_bucket);
222
223 hi->hash = hash;
224 hi->elem = NULL;
225 hi->bucket = NULL;
226 hi->last = NULL;
227 hi->bucket_marked = false;
228 hi->bucket_index_start = start_bucket;
229 hi->bucket_index_end = end_bucket;
230 hi->bucket_index = hi->bucket_index_start - 1;
231}
232
233void
238
239static inline void
241{
242 hi->bucket = b;
243 hi->last = NULL;
244 hi->bucket_marked = false;
245}
246
247static inline void
249{
250 if (hi->bucket)
251 {
252 if (hi->bucket_marked)
253 {
255 hi->bucket_marked = false;
256 }
257 hi->bucket = NULL;
258 hi->last = NULL;
259 }
260}
261
262static inline void
264{
265 hi->last = hi->elem;
266 hi->elem = hi->elem->next;
267}
268
269void
274
275struct hash_element *
277{
278 struct hash_element *ret = NULL;
279 if (hi->elem)
280 {
281 ret = hi->elem;
283 }
284 else
285 {
286 while (++hi->bucket_index < hi->bucket_index_end)
287 {
288 struct hash_bucket *b;
290 b = &hi->hash->buckets[hi->bucket_index];
291 if (b->list)
292 {
293 hash_iterator_lock(hi, b);
294 hi->elem = b->list;
295 if (hi->elem)
296 {
297 ret = hi->elem;
299 break;
300 }
301 }
302 }
303 }
304 return ret;
305}
306
307void
309{
310 ASSERT(hi->last);
311 hi->last->key = NULL;
312 hi->bucket_marked = true;
313}
314
315
316/*
317 * --------------------------------------------------------------------
318 * hash() -- hash a variable-length key into a 32-bit value
319 * k : the key (the unaligned variable-length array of bytes)
320 * len : the length of the key, counting by bytes
321 * level : can be any 4-byte value
322 * Returns a 32-bit value. Every bit of the key affects every bit of
323 * the return value. Every 1-bit and 2-bit delta achieves avalanche.
324 * About 36+6len instructions.
325 *
326 * #define hashsize(n) ((uint32_t)1<<(n))
327 * #define hashmask(n) (hashsize(n)-1)
328 *
329 * The best hash table sizes are powers of 2. There is no need to do
330 * mod a prime (mod is sooo slow!). If you need less than 32 bits,
331 * use a bitmask. For example, if you need only 10 bits, do
332 * h = (h & hashmask(10));
333 * In which case, the hash table should have hashsize(10) elements.
334 *
335 * If you are hashing n strings (uint8_t **)k, do it like this:
336 * for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
337 *
338 * By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
339 * code any way you wish, private, educational, or commercial. It's free.
340 *
341 * See http://burlteburtle.net/bob/hash/evahash.html
342 * Use for hash table lookup, or anything where one collision in 2^32 is
343 * acceptable. Do NOT use for cryptographic purposes.
344 *
345 * --------------------------------------------------------------------
346 *
347 * mix -- mix 3 32-bit values reversibly.
348 * For every delta with one or two bit set, and the deltas of all three
349 * high bits or all three low bits, whether the original value of a,b,c
350 * is almost all zero or is uniformly distributed,
351 * If mix() is run forward or backward, at least 32 bits in a,b,c
352 * have at least 1/4 probability of changing.
353 * If mix() is run forward, every bit of c will change between 1/3 and
354 * 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
355 * mix() was built out of 36 single-cycle latency instructions in a
356 * structure that could supported 2x parallelism, like so:
357 * a -= b;
358 * a -= c; x = (c>>13);
359 * b -= c; a ^= x;
360 * b -= a; x = (a<<8);
361 * c -= a; b ^= x;
362 * c -= b; x = (b>>13);
363 * ...
364 * Unfortunately, superscalar Pentiums and Sparcs can't take advantage
365 * of that parallelism. They've also turned some of those single-cycle
366 * latency instructions into multi-cycle latency instructions. Still,
367 * this is the fastest good hash I could find. There were about 2^^68
368 * to choose from. I only looked at a billion or so.
369 *
370 * James Yonan Notes:
371 *
372 * This function is faster than it looks, and appears to be
373 * appropriate for our usage in OpenVPN which is primarily
374 * for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC).
375 * NOTE: This function is never used for cryptographic purposes, only
376 * to produce evenly-distributed indexes into hash tables.
377 *
378 * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz,
379 * and 12.1 machine cycles per byte on a
380 * 2.2 Ghz P4 when hashing a 6 byte string.
381 * --------------------------------------------------------------------
382 */
383
384#define mix(a, b, c) \
385 { \
386 a -= b; \
387 a -= c; \
388 a ^= (c >> 13); \
389 b -= c; \
390 b -= a; \
391 b ^= (a << 8); \
392 c -= a; \
393 c -= b; \
394 c ^= (b >> 13); \
395 a -= b; \
396 a -= c; \
397 a ^= (c >> 12); \
398 b -= c; \
399 b -= a; \
400 b ^= (a << 16); \
401 c -= a; \
402 c -= b; \
403 c ^= (b >> 5); \
404 a -= b; \
405 a -= c; \
406 a ^= (c >> 3); \
407 b -= c; \
408 b -= a; \
409 b ^= (a << 10); \
410 c -= a; \
411 c -= b; \
412 c ^= (b >> 15); \
413 }
414
415uint32_t
416hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
417{
418 uint32_t a, b, c, len;
419
420 /* Set up the internal state */
421 len = length;
422 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
423 c = initval; /* the previous hash value */
424
425 /*---------------------------------------- handle most of the key */
426 while (len >= 12)
427 {
428 a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) + ((uint32_t)k[3] << 24));
429 b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) + ((uint32_t)k[7] << 24));
430 c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) + ((uint32_t)k[11] << 24));
431 mix(a, b, c);
432 k += 12;
433 len -= 12;
434 }
435
436 /*------------------------------------- handle the last 11 bytes */
437 c += length;
438 switch (len) /* all the case statements fall through */
439 {
440 case 11:
441 c += ((uint32_t)k[10] << 24);
442 /* Intentional [[fallthrough]]; */
443
444 case 10:
445 c += ((uint32_t)k[9] << 16);
446 /* Intentional [[fallthrough]]; */
447
448 case 9:
449 c += ((uint32_t)k[8] << 8);
450 /* Intentional [[fallthrough]]; */
451
452 /* the first byte of c is reserved for the length */
453 case 8:
454 b += ((uint32_t)k[7] << 24);
455 /* Intentional [[fallthrough]]; */
456
457 case 7:
458 b += ((uint32_t)k[6] << 16);
459 /* Intentional [[fallthrough]]; */
460
461 case 6:
462 b += ((uint32_t)k[5] << 8);
463 /* Intentional [[fallthrough]]; */
464
465 case 5:
466 b += k[4];
467 /* Intentional [[fallthrough]]; */
468
469 case 4:
470 a += ((uint32_t)k[3] << 24);
471 /* Intentional [[fallthrough]]; */
472
473 case 3:
474 a += ((uint32_t)k[2] << 16);
475 /* Intentional [[fallthrough]]; */
476
477 case 2:
478 a += ((uint32_t)k[1] << 8);
479 /* Intentional [[fallthrough]]; */
480
481 case 1:
482 a += k[0];
483 /* case 0: nothing left to add */
484 }
485 mix(a, b, c);
486 /*-------------------------------------- report the result */
487 return c;
488}
#define ALLOC_OBJ_CLEAR(dptr, type)
Definition buffer.h:1042
#define ALLOC_ARRAY(dptr, type, n)
Definition buffer.h:1048
static const char *const key1
Definition cert_data.h:55
static size_t adjust_power_of_2(size_t u)
Definition integer.h:205
static void hash_remove_marked(struct hash *hash, struct hash_bucket *bucket)
Definition list.c:182
void hash_iterator_free(struct hash_iterator *hi)
Definition list.c:270
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition list.c:276
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition list.c:308
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition list.c:79
void hash_iterator_init(struct hash *hash, struct hash_iterator *hi)
Definition list.c:234
static void hash_iterator_lock(struct hash_iterator *hi, struct hash_bucket *b)
Definition list.c:240
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition list.c:107
static void hash_iterator_unlock(struct hash_iterator *hi)
Definition list.c:248
struct hash * hash_init(const uint32_t 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:37
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition list.c:416
void hash_free(struct hash *hash)
Definition list.c:60
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition list.c:137
void hash_remove_by_value(struct hash *hash, void *value)
Definition list.c:165
static void hash_iterator_advance(struct hash_iterator *hi)
Definition list.c:263
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, uint32_t start_bucket, uint32_t end_bucket)
Definition list.c:213
#define mix(a, b, c)
Definition list.c:384
static uint32_t hash_value(const struct hash *hash, const void *key)
Definition list.h:104
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition list.h:146
#define ASSERT(x)
Definition error.h:219
struct hash_element * list
Definition list.h:49
void * value
Definition list.h:41
const void * key
Definition list.h:42
struct hash_element * next
Definition list.h:44
uint32_t hash_value
Definition list.h:43
uint32_t bucket_index_end
Definition list.h:87
bool bucket_marked
Definition list.h:85
struct hash_bucket * bucket
Definition list.h:82
struct hash * hash
Definition list.h:80
uint32_t bucket_index
Definition list.h:81
struct hash_element * elem
Definition list.h:83
uint32_t bucket_index_start
Definition list.h:86
struct hash_element * last
Definition list.h:84
Definition list.h:53
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition list.h:58
uint32_t mask
Definition list.h:56
struct hash_bucket * buckets
Definition list.h:60
uint32_t n_elements
Definition list.h:55
uint32_t iv
Definition list.h:57
bool(* compare_function)(const void *key1, const void *key2)
Definition list.h:59
uint32_t n_buckets
Definition list.h:54
Container for bidirectional cipher and HMAC key material.
Definition crypto.h:240
Container for unidirectional cipher and HMAC key material.
Definition crypto.h:152