1 /*
2 * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #ifndef OPENSSL_HASHTABLE_H
11 #define OPENSSL_HASHTABLE_H
12 #pragma once
13
14 #include <stddef.h>
15 #include <stdint.h>
16 #include <openssl/e_os2.h>
17 #include <internal/rcu.h>
18 #include "crypto/context.h"
19
20 typedef struct ht_internal_st HT;
21
22 /*
23 * Represents a key to a hashtable
24 */
25 typedef struct ht_key_header_st {
26 size_t keysize;
27 uint8_t *keybuf;
28 } HT_KEY;
29
30 /*
31 * Represents a value in the hash table
32 */
33 typedef struct ht_value_st {
34 void *value;
35 uintptr_t *type_id;
36 HT_KEY key;
37 } HT_VALUE;
38
39 /*
40 * Represents a list of values filtered from a hash table
41 */
42 typedef struct ht_value_list_st {
43 size_t list_len;
44 HT_VALUE **list;
45 } HT_VALUE_LIST;
46
47 /*
48 * Hashtable configuration
49 */
50 typedef struct ht_config_st {
51 OSSL_LIB_CTX *ctx;
52 void (*ht_free_fn)(HT_VALUE *obj);
53 uint64_t (*ht_hash_fn)(uint8_t *key, size_t keylen);
54 size_t init_neighborhoods;
55 uint32_t collision_check;
56 uint32_t lockless_reads;
57 } HT_CONFIG;
58
59 /*
60 * Hashtable key rules
61 * Any struct can be used to formulate a hash table key, as long as the
62 * following rules
63 * 1) The first element of the struct defining the key must be an HT_KEY
64 * 2) All struct elements must have a compile time defined length
65 * 3) Pointers can be used, but the value of the pointer, rather than
66 * the contents of the address it points to will be used to compute
67 * the hash
68 * The key definition macros will assist with enforcing these rules
69 */
70
71 /*
72 * Starts the definition of a hash table key
73 */
74 #define HT_START_KEY_DEFN(keyname) \
75 typedef struct keyname##_st { \
76 HT_KEY key_header; \
77 struct {
78
79 /*
80 * Ends a hash table key definitions
81 */
82 #define HT_END_KEY_DEFN(keyname) \
83 } \
84 keyfields; \
85 } \
86 keyname;
87
88 /*
89 * Defines a field in a hash table key
90 */
91 #define HT_DEF_KEY_FIELD(name, type) type name;
92
93 /*
94 * convenience macro to define a static char
95 * array field in a hash table key
96 */
97 #define HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size) \
98 HT_DEF_KEY_FIELD(name[size], char)
99
100 /*
101 * Defines a uint8_t (blob) field in a hash table key
102 */
103 #define HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size) \
104 HT_DEF_KEY_FIELD(name[size], uint8_t)
105
106 /*
107 * Initializes a key
108 */
109 #define HT_INIT_KEY(key) \
110 do { \
111 memset((key), 0, sizeof(*(key))); \
112 (key)->key_header.keysize = (sizeof(*(key)) - sizeof(HT_KEY)); \
113 (key)->key_header.keybuf = (((uint8_t *)key) + sizeof(HT_KEY)); \
114 } while (0)
115
116 /*
117 * Resets a hash table key to a known state
118 */
119 #define HT_KEY_RESET(key) memset((key)->key_header.keybuf, 0, (key)->key_header.keysize)
120
121 /*
122 * Sets a scalar field in a hash table key
123 */
124 #define HT_SET_KEY_FIELD(key, member, value) (key)->keyfields.member = value;
125
126 /*
127 * Sets a string field in a hash table key, preserving
128 * null terminator
129 */
130 #define HT_SET_KEY_STRING(key, member, value) \
131 do { \
132 if ((value) != NULL) \
133 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
134 } while (0)
135
136 /*
137 * This is the same as HT_SET_KEY_STRING, except that it uses
138 * ossl_ht_strcase to make the value being passed case insensitive
139 * This is useful for instances in which we want upper and lower case
140 * key value to hash to the same entry
141 */
142 #define HT_SET_KEY_STRING_CASE(key, member, value) \
143 do { \
144 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
145 } while (0)
146
147 /*
148 * Same as HT_SET_KEY_STRING but also takes length of the string.
149 */
150 #define HT_SET_KEY_STRING_N(key, member, value, len) \
151 do { \
152 if ((value) != NULL) { \
153 if (len < sizeof((key)->keyfields.member)) \
154 strncpy((key)->keyfields.member, value, len); \
155 else \
156 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
157 } \
158 } while (0)
159
160 /* Same as HT_SET_KEY_STRING_CASE but also takes length of the string. */
161 #define HT_SET_KEY_STRING_CASE_N(key, member, value, len) \
162 do { \
163 if (len < sizeof((key)->keyfields.member)) \
164 ossl_ht_strcase((key)->keyfields.member, value, len); \
165 else \
166 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
167 } while (0)
168
169 /*
170 * Sets a uint8_t (blob) field in a hash table key
171 */
172 #define HT_SET_KEY_BLOB(key, member, value, len) \
173 do { \
174 if (value != NULL) \
175 memcpy((key)->keyfields.member, value, len); \
176 } while (0)
177
178 /*
179 * Converts a defined key type to an HT_KEY
180 */
181 #define TO_HT_KEY(key) &(key)->key_header
182
183 /*
184 * Converts an HT_KEY back to its defined
185 * type
186 */
187 #define FROM_HT_KEY(key, type) (type)(key)
188
189 /*
190 * Implements the following type safe operations for a hash table
191 * ossl_ht_NAME_TYPE_insert - insert a value to a hash table of type TYPE
192 * ossl_ht_NAME_TYPE_get - gets a value of a specific type from the hash table
193 * ossl_ht_NAME_TYPE_from_value - converts an HT_VALUE to its type
194 * ossl_ht_NAME_TYPE_to_value - converts a TYPE to an HT_VALUE
195 * ossl_ht_NAME_TYPE_type - boolean to detect if a value is of TYPE
196 */
197 #define IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx) \
198 static uintptr_t name##_##vtype##_id = 0; \
199 pfx ossl_unused int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, \
200 vtype *data, \
201 vtype **olddata) \
202 { \
203 HT_VALUE inval; \
204 HT_VALUE *oval = NULL; \
205 int rc; \
206 \
207 inval.value = data; \
208 inval.type_id = &name##_##vtype##_id; \
209 rc = ossl_ht_insert(h, key, &inval, olddata == NULL ? NULL : &oval); \
210 if (oval != NULL) \
211 *olddata = (vtype *)oval->value; \
212 return rc; \
213 } \
214 \
215 pfx ossl_unused vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v) \
216 { \
217 uintptr_t *expect_type = &name##_##vtype##_id; \
218 if (v == NULL) \
219 return NULL; \
220 if (v->type_id != expect_type) \
221 return NULL; \
222 return (vtype *)v->value; \
223 } \
224 \
225 pfx ossl_unused vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
226 HT_KEY *key, \
227 HT_VALUE **v) \
228 { \
229 HT_VALUE *vv; \
230 vv = ossl_ht_get(h, key); \
231 if (vv == NULL) \
232 return NULL; \
233 *v = ossl_rcu_deref(&vv); \
234 return ossl_ht_##name##_##vtype##_from_value(*v); \
235 } \
236 \
237 pfx ossl_unused HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, \
238 HT_VALUE *v) \
239 { \
240 v->type_id = &name##_##vtype##_id; \
241 v->value = data; \
242 return v; \
243 } \
244 \
245 pfx ossl_unused int ossl_ht_##name##_##vtype##_type(HT_VALUE *h) \
246 { \
247 return h->type_id == &name##_##vtype##_id; \
248 }
249
250 #define DECLARE_HT_VALUE_TYPE_FNS(vtype, name) \
251 int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, vtype *data, \
252 vtype **olddata); \
253 vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v); \
254 vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
255 HT_KEY *key, \
256 HT_VALUE **v); \
257 HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, HT_VALUE *v); \
258 int ossl_ht_##name##_##vtype##_type(HT_VALUE *h);
259
260 /*
261 * Helper function to construct case insensitive keys
262 */
ossl_ht_strcase(char * tgt,const char * src,int len)263 static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len)
264 {
265 int i;
266 #if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
267 const long int case_adjust = ~0x40;
268 #else
269 const long int case_adjust = ~0x20;
270 #endif
271
272 if (src == NULL)
273 return;
274
275 for (i = 0; src[i] != '\0' && i < len; i++)
276 tgt[i] = case_adjust & src[i];
277 }
278
279 /*
280 * Create a new hashtable
281 */
282 HT *ossl_ht_new(const HT_CONFIG *conf);
283
284 /*
285 * Frees a hash table, potentially freeing all elements
286 */
287 void ossl_ht_free(HT *htable);
288
289 /*
290 * Lock the table for reading
291 */
292 void ossl_ht_read_lock(HT *htable);
293
294 /*
295 * Lock the table for writing
296 */
297 void ossl_ht_write_lock(HT *htable);
298
299 /*
300 * Read unlock
301 */
302 void ossl_ht_read_unlock(HT *htable);
303
304 /*
305 * Write unlock
306 */
307 void ossl_ht_write_unlock(HT *htable);
308
309 /*
310 * Empties a hash table, potentially freeing all elements
311 */
312 int ossl_ht_flush(HT *htable);
313
314 /*
315 * Inserts an element to a hash table, optionally returning
316 * replaced data to caller
317 * Returns 1 if the insert was successful, 0 on error
318 */
319 int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data,
320 HT_VALUE **olddata);
321
322 /*
323 * Deletes a value from a hash table, based on key
324 * Returns 1 if the key was removed, 0 if they key was not found
325 */
326 int ossl_ht_delete(HT *htable, HT_KEY *key);
327
328 /*
329 * Returns number of elements in the hash table
330 */
331 size_t ossl_ht_count(HT *htable);
332
333 /*
334 * Iterates over each element in the table.
335 * aborts the loop when cb returns 0
336 * Contents of elements in the list may be modified during
337 * this traversal, assuming proper thread safety is observed while doing
338 * so (holding the table write lock is sufficient). However, elements of the
339 * table may not be inserted or removed while iterating.
340 */
341 void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg),
342 void *arg);
343 /*
344 * Returns a list of elements in a hash table based on
345 * filter function return value. Returns NULL on error,
346 * or an HT_VALUE_LIST object on success. Note it is possible
347 * That a list will be returned with 0 entries, if none were found.
348 * The zero length list must still be freed via ossl_ht_value_list_free
349 */
350 HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len,
351 int (*filter)(HT_VALUE *obj, void *arg),
352 void *arg);
353 /*
354 * Frees the list returned from ossl_ht_filter
355 */
356 void ossl_ht_value_list_free(HT_VALUE_LIST *list);
357
358 /*
359 * Fetches a value from the hash table, based
360 * on key. Returns NULL if the element was not found.
361 */
362 HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key);
363
364 #endif
365