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 } keyfields; \
84 } keyname;
85
86 /*
87 * Defines a field in a hash table key
88 */
89 #define HT_DEF_KEY_FIELD(name, type) type name;
90
91 /*
92 * convenience macro to define a static char
93 * array field in a hash table key
94 */
95 #define HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size) \
96 HT_DEF_KEY_FIELD(name[size], char)
97
98 /*
99 * Defines a uint8_t (blob) field in a hash table key
100 */
101 #define HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size) \
102 HT_DEF_KEY_FIELD(name[size], uint8_t)
103
104 /*
105 * Initializes a key
106 */
107 #define HT_INIT_KEY(key) do { \
108 memset((key), 0, sizeof(*(key))); \
109 (key)->key_header.keysize = (sizeof(*(key)) - sizeof(HT_KEY)); \
110 (key)->key_header.keybuf = (((uint8_t *)key) + sizeof(HT_KEY)); \
111 } while(0)
112
113 /*
114 * Resets a hash table key to a known state
115 */
116 #define HT_KEY_RESET(key) memset((key)->key_header.keybuf, 0, (key)->key_header.keysize)
117
118 /*
119 * Sets a scalar field in a hash table key
120 */
121 #define HT_SET_KEY_FIELD(key, member, value) (key)->keyfields.member = value;
122
123 /*
124 * Sets a string field in a hash table key, preserving
125 * null terminator
126 */
127 #define HT_SET_KEY_STRING(key, member, value) do { \
128 if ((value) != NULL) \
129 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
130 } while(0)
131
132 /*
133 * This is the same as HT_SET_KEY_STRING, except that it uses
134 * ossl_ht_strcase to make the value being passed case insensitive
135 * This is useful for instances in which we want upper and lower case
136 * key value to hash to the same entry
137 */
138 #define HT_SET_KEY_STRING_CASE(key, member, value) do { \
139 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) -1); \
140 } while(0)
141
142 /*
143 * Same as HT_SET_KEY_STRING but also takes length of the string.
144 */
145 #define HT_SET_KEY_STRING_N(key, member, value, len) do { \
146 if ((value) != NULL) { \
147 if (len < sizeof((key)->keyfields.member)) \
148 strncpy((key)->keyfields.member, value, len); \
149 else \
150 strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
151 } \
152 } while(0)
153
154 /* Same as HT_SET_KEY_STRING_CASE but also takes length of the string. */
155 #define HT_SET_KEY_STRING_CASE_N(key, member, value, len) do { \
156 if (len < sizeof((key)->keyfields.member)) \
157 ossl_ht_strcase((key)->keyfields.member, value, len); \
158 else \
159 ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
160 } while(0)
161
162 /*
163 * Sets a uint8_t (blob) field in a hash table key
164 */
165 #define HT_SET_KEY_BLOB(key, member, value, len) do { \
166 if (value != NULL) \
167 memcpy((key)->keyfields.member, value, len); \
168 } while(0)
169
170 /*
171 * Converts a defined key type to an HT_KEY
172 */
173 #define TO_HT_KEY(key) &(key)->key_header
174
175 /*
176 * Converts an HT_KEY back to its defined
177 * type
178 */
179 #define FROM_HT_KEY(key, type) (type)(key)
180
181 /*
182 * Implements the following type safe operations for a hash table
183 * ossl_ht_NAME_TYPE_insert - insert a value to a hash table of type TYPE
184 * ossl_ht_NAME_TYPE_get - gets a value of a specific type from the hash table
185 * ossl_ht_NAME_TYPE_from_value - converts an HT_VALUE to its type
186 * ossl_ht_NAME_TYPE_to_value - converts a TYPE to an HT_VALUE
187 * ossl_ht_NAME_TYPE_type - boolean to detect if a value is of TYPE
188 */
189 #define IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx) \
190 static uintptr_t name##_##vtype##_id = 0; \
191 pfx ossl_unused int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, \
192 vtype *data, \
193 vtype **olddata) { \
194 HT_VALUE inval; \
195 HT_VALUE *oval = NULL; \
196 int rc; \
197 \
198 inval.value = data; \
199 inval.type_id = &name##_##vtype##_id; \
200 rc = ossl_ht_insert(h, key, &inval, olddata == NULL ? NULL : &oval); \
201 if (oval != NULL) \
202 *olddata = (vtype *)oval->value; \
203 return rc; \
204 } \
205 \
206 pfx ossl_unused vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v) \
207 { \
208 uintptr_t *expect_type = &name##_##vtype##_id; \
209 if (v == NULL) \
210 return NULL; \
211 if (v->type_id != expect_type) \
212 return NULL; \
213 return (vtype *)v->value; \
214 } \
215 \
216 pfx ossl_unused vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
217 HT_KEY *key, \
218 HT_VALUE **v)\
219 { \
220 HT_VALUE *vv; \
221 vv = ossl_ht_get(h, key); \
222 if (vv == NULL) \
223 return NULL; \
224 *v = ossl_rcu_deref(&vv); \
225 return ossl_ht_##name##_##vtype##_from_value(*v); \
226 } \
227 \
228 pfx ossl_unused HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, \
229 HT_VALUE *v) \
230 { \
231 v->type_id = &name##_##vtype##_id; \
232 v->value = data; \
233 return v; \
234 } \
235 \
236 pfx ossl_unused int ossl_ht_##name##_##vtype##_type(HT_VALUE *h) \
237 { \
238 return h->type_id == &name##_##vtype##_id; \
239 }
240
241 #define DECLARE_HT_VALUE_TYPE_FNS(vtype, name) \
242 int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, vtype *data, \
243 vtype **olddata); \
244 vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v); \
245 vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
246 HT_KEY *key, \
247 HT_VALUE **v); \
248 HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, HT_VALUE *v); \
249 int ossl_ht_##name##_##vtype##_type(HT_VALUE *h); \
250
251 /*
252 * Helper function to construct case insensitive keys
253 */
ossl_ht_strcase(char * tgt,const char * src,int len)254 static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len)
255 {
256 int i;
257 #if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
258 const long int case_adjust = ~0x40;
259 #else
260 const long int case_adjust = ~0x20;
261 #endif
262
263 if (src == NULL)
264 return;
265
266 for (i = 0; src[i] != '\0' && i < len; i++)
267 tgt[i] = case_adjust & src[i];
268 }
269
270 /*
271 * Create a new hashtable
272 */
273 HT *ossl_ht_new(const HT_CONFIG *conf);
274
275 /*
276 * Frees a hash table, potentially freeing all elements
277 */
278 void ossl_ht_free(HT *htable);
279
280 /*
281 * Lock the table for reading
282 */
283 void ossl_ht_read_lock(HT *htable);
284
285 /*
286 * Lock the table for writing
287 */
288 void ossl_ht_write_lock(HT *htable);
289
290 /*
291 * Read unlock
292 */
293 void ossl_ht_read_unlock(HT *htable);
294
295 /*
296 * Write unlock
297 */
298 void ossl_ht_write_unlock (HT *htable);
299
300 /*
301 * Empties a hash table, potentially freeing all elements
302 */
303 int ossl_ht_flush(HT *htable);
304
305 /*
306 * Inserts an element to a hash table, optionally returning
307 * replaced data to caller
308 * Returns 1 if the insert was successful, 0 on error
309 */
310 int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data,
311 HT_VALUE **olddata);
312
313 /*
314 * Deletes a value from a hash table, based on key
315 * Returns 1 if the key was removed, 0 if they key was not found
316 */
317 int ossl_ht_delete(HT *htable, HT_KEY *key);
318
319 /*
320 * Returns number of elements in the hash table
321 */
322 size_t ossl_ht_count(HT *htable);
323
324 /*
325 * Iterates over each element in the table.
326 * aborts the loop when cb returns 0
327 * Contents of elements in the list may be modified during
328 * this traversal, assuming proper thread safety is observed while doing
329 * so (holding the table write lock is sufficient). However, elements of the
330 * table may not be inserted or removed while iterating.
331 */
332 void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg),
333 void *arg);
334 /*
335 * Returns a list of elements in a hash table based on
336 * filter function return value. Returns NULL on error,
337 * or an HT_VALUE_LIST object on success. Note it is possible
338 * That a list will be returned with 0 entries, if none were found.
339 * The zero length list must still be freed via ossl_ht_value_list_free
340 */
341 HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len,
342 int (*filter)(HT_VALUE *obj, void *arg),
343 void *arg);
344 /*
345 * Frees the list returned from ossl_ht_filter
346 */
347 void ossl_ht_value_list_free(HT_VALUE_LIST *list);
348
349 /*
350 * Fetches a value from the hash table, based
351 * on key. Returns NULL if the element was not found.
352 */
353 HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key);
354
355 #endif
356