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