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 */ 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