1 /*
2 * Copyright 2024 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 * Sets a uint8_t (blob) field in a hash table key
144 */
145 #define HT_SET_KEY_BLOB(key, member, value, len) do { \
146 if (value != NULL) \
147 memcpy((key)->keyfields.member, value, len); \
148 } while(0)
149
150 /*
151 * Converts a defined key type to an HT_KEY
152 */
153 #define TO_HT_KEY(key) &(key)->key_header
154
155 /*
156 * Converts an HT_KEY back to its defined
157 * type
158 */
159 #define FROM_HT_KEY(key, type) (type)(key)
160
161 /*
162 * Implements the following type safe operations for a hash table
163 * ossl_ht_NAME_TYPE_insert - insert a value to a hash table of type TYPE
164 * ossl_ht_NAME_TYPE_get - gets a value of a specific type from the hash table
165 * ossl_ht_NAME_TYPE_from_value - converts an HT_VALUE to its type
166 * ossl_ht_NAME_TYPE_to_value - converts a TYPE to an HT_VALUE
167 * ossl_ht_NAME_TYPE_type - boolean to detect if a value is of TYPE
168 */
169 #define IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx) \
170 static uintptr_t name##_##vtype##_id = 0; \
171 pfx ossl_unused int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, \
172 vtype *data, \
173 vtype **olddata) { \
174 HT_VALUE inval; \
175 HT_VALUE *oval = NULL; \
176 int rc; \
177 \
178 inval.value = data; \
179 inval.type_id = &name##_##vtype##_id; \
180 rc = ossl_ht_insert(h, key, &inval, olddata == NULL ? NULL : &oval); \
181 if (oval != NULL) \
182 *olddata = (vtype *)oval->value; \
183 return rc; \
184 } \
185 \
186 pfx ossl_unused vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v) \
187 { \
188 uintptr_t *expect_type = &name##_##vtype##_id; \
189 if (v == NULL) \
190 return NULL; \
191 if (v->type_id != expect_type) \
192 return NULL; \
193 return (vtype *)v->value; \
194 } \
195 \
196 pfx ossl_unused vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
197 HT_KEY *key, \
198 HT_VALUE **v)\
199 { \
200 HT_VALUE *vv; \
201 vv = ossl_ht_get(h, key); \
202 if (vv == NULL) \
203 return NULL; \
204 *v = ossl_rcu_deref(&vv); \
205 return ossl_ht_##name##_##vtype##_from_value(*v); \
206 } \
207 \
208 pfx ossl_unused HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, \
209 HT_VALUE *v) \
210 { \
211 v->type_id = &name##_##vtype##_id; \
212 v->value = data; \
213 return v; \
214 } \
215 \
216 pfx ossl_unused int ossl_ht_##name##_##vtype##_type(HT_VALUE *h) \
217 { \
218 return h->type_id == &name##_##vtype##_id; \
219 }
220
221 #define DECLARE_HT_VALUE_TYPE_FNS(vtype, name) \
222 int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, vtype *data, \
223 vtype **olddata); \
224 vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v); \
225 vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h, \
226 HT_KEY *key, \
227 HT_VALUE **v); \
228 HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, HT_VALUE *v); \
229 int ossl_ht_##name##_##vtype##_type(HT_VALUE *h); \
230
231 /*
232 * Helper function to construct case insensitive keys
233 */
ossl_ht_strcase(char * tgt,const char * src,int len)234 static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len)
235 {
236 int i;
237 #if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
238 const long int case_adjust = ~0x40;
239 #else
240 const long int case_adjust = ~0x20;
241 #endif
242
243 if (src == NULL)
244 return;
245
246 for (i = 0; src[i] != '\0' && i < len; i++)
247 tgt[i] = case_adjust & src[i];
248 }
249
250 /*
251 * Create a new hashtable
252 */
253 HT *ossl_ht_new(const HT_CONFIG *conf);
254
255 /*
256 * Frees a hash table, potentially freeing all elements
257 */
258 void ossl_ht_free(HT *htable);
259
260 /*
261 * Lock the table for reading
262 */
263 void ossl_ht_read_lock(HT *htable);
264
265 /*
266 * Lock the table for writing
267 */
268 void ossl_ht_write_lock(HT *htable);
269
270 /*
271 * Read unlock
272 */
273 void ossl_ht_read_unlock(HT *htable);
274
275 /*
276 * Write unlock
277 */
278 void ossl_ht_write_unlock (HT *htable);
279
280 /*
281 * Empties a hash table, potentially freeing all elements
282 */
283 int ossl_ht_flush(HT *htable);
284
285 /*
286 * Inserts an element to a hash table, optionally returning
287 * replaced data to caller
288 * Returns 1 if the insert was successful, 0 on error
289 */
290 int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data,
291 HT_VALUE **olddata);
292
293 /*
294 * Deletes a value from a hash table, based on key
295 * Returns 1 if the key was removed, 0 if they key was not found
296 */
297 int ossl_ht_delete(HT *htable, HT_KEY *key);
298
299 /*
300 * Returns number of elements in the hash table
301 */
302 size_t ossl_ht_count(HT *htable);
303
304 /*
305 * Iterates over each element in the table.
306 * aborts the loop when cb returns 0
307 * Contents of elements in the list may be modified during
308 * this traversal, assuming proper thread safety is observed while doing
309 * so (holding the table write lock is sufficient). However, elements of the
310 * table may not be inserted or removed while iterating.
311 */
312 void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg),
313 void *arg);
314 /*
315 * Returns a list of elements in a hash table based on
316 * filter function return value. Returns NULL on error,
317 * or an HT_VALUE_LIST object on success. Note it is possible
318 * That a list will be returned with 0 entries, if none were found.
319 * The zero length list must still be freed via ossl_ht_value_list_free
320 */
321 HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len,
322 int (*filter)(HT_VALUE *obj, void *arg),
323 void *arg);
324 /*
325 * Frees the list returned from ossl_ht_filter
326 */
327 void ossl_ht_value_list_free(HT_VALUE_LIST *list);
328
329 /*
330 * Fetches a value from the hash table, based
331 * on key. Returns NULL if the element was not found.
332 */
333 HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key);
334
335 #endif
336
