1=pod 2 3=head1 NAME 4 5ossl_ht_new, ossl_ht_free, 6ossl_ht_read_lock, ossl_ht_read_unlock, 7ossl_ht_write_lock, ossl_ht_write_unlock, 8ossl_ht_flush, ossl_ht_insert, 9ossl_ht_delete, ossl_ht_count, 10ossl_ht_foreach_until, ossl_ht_filter, 11ossl_ht_value_list_free, ossl_ht_get, 12ossl_ht_put, HT_START_KEY_DEFN, 13HT_END_KEY_DEFN, HT_DEF_KEY_FIELD_CHAR_ARRAY, 14HT_DEF_KEY_FIELD_UINT8T_ARRAY, HT_DEF_KEY_FIELD, 15HT_INIT_KEY, HT_KEY_RESET, HT_SET_KEY_FIELD, 16HT_SET_KEY_STRING, HT_SET_KEY_BLOB, 17TO_HT_KEY, FROM_HT_KEY, 18IMPLEMENT_HT_VALUE_TYPE_FNS 19- internal rcu locked hashtables 20 21=head1 SYNOPSIS 22 23 HT *ossl_ht_new(const HT_CONFIG *conf); 24 void ossl_ht_free(HT *htable); 25 void ossl_ht_read_lock(HT *htable); 26 void ossl_ht_read_unlock(HT *htable); 27 void ossl_ht_write_lock(HT *htable); 28 void ossl_ht_write_unlock(HT *htable); 29 int ossl_ht_flush(HT *htable); 30 int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata); 31 int ossl_ht_delete(HT *htable, HT_KEY *key); 32 size_t ossl_ht_count(HT *htable); 33 void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg), void *arg); 34 HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len, int (*filter)(HT_VALUE *obj)); 35 void ossl_ht_value_list_free(HT_VALUE_LIST *list); 36 HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key); 37 void ossl_ht_put(HT_VALUE *value); 38 HT_START_KEY_DEFN(keyname); 39 HT_END_KEY_DEFN(keyname); 40 HT_DEF_KEY_FIELD(name, type); 41 HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size); 42 HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size); 43 HT_INIT_KEY(key); 44 HT_KEY_RESET(key); 45 HT_SET_KEY_FIELD(key, member, value); 46 HT_SET_KEY_STRING(key, member, value); 47 HT_SET_KEY_BLOB(key, member, value, len); 48 TO_HT_KEY(key); 49 FROM_HT_KEY(key, type); 50 IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx); 51 52=head1 DESCRIPTION 53 54This API provides a library-internal implementation of a hashtable that provides 55reference counted object retrieval under the protection of an rcu lock. API 56type safety is offered via conversion macros to and from the generic B<HT_VALUE> 57type. 58 59=over 2 60 61=item * 62 63ossl_ht_new() returns a new B<HT> (hashtable object) used to store data 64elements based on a defined key. The call accepts an HT_CONFIG pointer which 65contains configurations options for hashtable. Current config options consist 66of: 67 I<ht_free_fn> The function to call to free a value, may be NULL. 68 I<ht_hash_fn> The function to generate a hash value for a key, may be NULL. 69 I<init_neighborhoods> The initial number of neighborhoods in the hash table. 70 71Note that init_bucket_len may be set to zero, which will use the default initial 72bucket size, which will be automatically expanded with the hash table load 73average reaches 0.75. 74 75Note that lockless_read operation implies behavioral restrictions. Specifically 76only element additions are allowed, deletion operations will fail 77 Hash table growth is inhibited. init_bucket_len should be set to an 78 appropriate value to prevent performance degradation 79 The table owner is responsible for ensuring there are no readers during a 80 freeing of the table. 81 82Note that lockless_write operations are done at your own risk. Lockless 83 operation in a multithreaded environment will cause data corruption. It 84 is the callers responsibility in this mode of operation to provide thread 85 synchronization. 86 87=item * 88 89ossl_ht_free() frees an allocated hash table. Each element in the table 90will have its reference count dropped, and, if said count reaches zero, the hash 91tables registered free function will be called to release the element data. 92 93=item * 94 95ossl_ht_read_lock(), ossl_ht_read_unlock(), ossl_ht_write_lock() and 96ossl_ht_write_unlock() lock the table for reading and writing/modification. 97These function are not required for use in the event a table is to be used in a 98lockless fashion, but if they are not used, it is the responsibility of the caller 99to ensure thread synchronization. Note that an rcu lock is used internally for these 100operations, so for table modifying actions (ossl_ht_flush() and ossl_ht_delete() 101the write lock must be taken and released to ensure rcu synchronization takes 102place. 103 104=item * 105 106ossl_ht_flush() empties a hash table. All elements will have their 107reference counts decremented, and, on reaching zero, the free function will be 108called to release the element data. 109 110=item * 111 112ossl_ht_insert() inserts an B<HT_VALUE> element into the hash table, to be 113hashed using the corresponding B<HT_KEY> value. 114 115=item * 116 117ossl_ht_delete() deletes an entry from the hashtable indexed by the passed 118B<HT_KEY> value. 119 120=item * 121 122ossl_ht_count() returns the number of elements within the hash table. 123 124=item * 125 126ossl_ht_foreach_until() iterates over all elements in the hash table, calling 127the passed callback function for each. The return value of the callback 128indicates if the iteration should continue or not. Returning 1 indicates 129iteration should continue, while returning 0 indicates that iteration should 130terminate. 131 132Note that the iteration is done under read lock protection, and as such 133modifications to the table are disallowed in the callback function. 134Modification to the value content are permitted, if the caller is able to 135properly synchronize such modifications with other threads. 136 137=item * 138 139ossl_ht_filter() iterates over all elements of the hash table, calling 140the filter callback for each element. If the callback returns 1, the 141corresponding B<HT_VALUE> is placed on a list, and its reference count incremented. 142The completed list is returned to the caller as an B<HT_VALUE_LIST> object 143 144=item * 145 146ossl_ht_value_list_free() frees an B<HT_VALUE_LIST>. For each element on 147the list, its reference count is decremented, and after traversing the list, the 148list object is freed. Note, NULL elements are allowed on the list, but for any 149element which is taken from the list by a caller, they must call 150ossl_ht_put() on the B<HT_VALUE> to prevent memory leaks. 151 152=item * 153 154ossl_ht_get() performs a lookup of an B<HT_KEY> in the hashtable, returning 155its corresponding value. 156 157=item * 158 159HT_START_KEY_DEFN() Begins the definition of a key type. the keyname parameter 160defines the structure name, and presets a common key header. 161 162=item * 163 164HT_END_KEY_DEFN() Finalizes a key definition. the keyname parameter (which may 165differ from the name passed in HT_START_KEY_DEFN(), defines the key type name. 166The resulting type may be converted to an HT_KEY variable via the HT_TO_KEY() 167macro, and back using the HT_FROM_KEY() macro. 168 169=item * 170 171HT_DEF_KEY_FIELD() Allows for the creation of data fields within a key. Note, 172this macro can be used for any data type, but it is recommended that strings and 173binary arrays be created with the HT_DEF_KEY_FIELD_CHAR_ARRAY() and 174HT_DEF_KEY_FIELD_UINT8T_ARRAY() macros to ensure proper in-lining of key data. 175 176=item * 177 178HT_DEF_KEY_FIELD_CHAR_ARRAY() Creates a string field of fixed size 179within a key definition. Note these items will be NULL terminated. 180 181=item * 182 183HT_DEF_KEY_FIELD_UINT8T_ARRAY() Creates an array of uint8_t elements within a 184key. 185 186=item * 187 188HT_INIT_KEY() Initializes a key for use. Can be called multiple times, but must 189be called at least once before using in any hashtable method. 190 191=item * 192 193HT_KEY_RESET() Resets a key's data to all zeros. 194 195=item * 196 197HT_SET_KEY_FIELD() Sets a field in a key (as defined by HT_DEF_KEY_FIELD()) to a 198given value. 199 200=item * 201 202HT_SET_KEY_STRING() Performs a strncpy() of a source string to the destination 203key field. 204 205=item * 206 207HT_SET_KEY_BLOB() Performs a memcpy() of a source uint8_t buffer to a 208destination key field. 209 210=item * 211 212TO_HT_KEY() Converts a key type as defined by HT_START_KEY_DEFN() and 213HE_END_KEY_DEFN() to the generic HT_KEY type 214 215=item * 216 217FROM_HT_KEY() Converts an HT_KEY back to a specific key type as defined by 218HT_START_KEY_DEFN() and HT_END_KEY_DEFN() 219 220=item * 221 222IMPLEMENT_HT_VALUE_TYPE_FNS() creates template conversion functions for 223manipulating the hashtable using specific data types. This macro accepts two 224parameters, a NAME, which is used to prefix the hashtable function so that it 225may be associated with a specific hash table, and TYPE which defines the type of 226data the instantiated function accepts. The list of functions instantiated by 227this macro are below. 228 229=over 2 230 231=item * 232 233int ossl_ht_NAME_TYPE_insert(HT* h, HT_KEY *key, <type> *value, HT_VALUE **olddata) 234Inserts a value to the hash table of type TYPE into the hash table using the 235provided key. If olddata is not NULL, and a matching key already exists in the 236table, the operation is a replacement, and the old data is returned in this 237pointer 238 239=item * 240 241<TYPE> ossl_ht_NAME_TYPE_get(HT *h, HT_KEY *key, HT_VALUE **v) 242Looks up an item in the hash table based on key, and returns the data it found, 243if any. v holds a pointer to the B<HT_VALUE> associated with the data. 244 245=item * 246 247<TYPE> *ossl_ht_NAME_TYPE_from_value(HT_VALUE *v) 248Validates that the B<HT_VALUE> provided matches the TYPE specified, and returns the 249value data. If there is a type mismatch, NULL is returned 250 251=item * 252 253HT_VALUE *ossl_ht_NAME_TYPE_to_value(<TYPE> *data) 254Converts the data pointer provided to an B<HT_VALUE> object 255 256=item * 257 258int ossl_ht_NAME_TYPE_type(HT_VALUE *v) 259Returns true if the B<HT_VALUE> object passed in is of type <TYPE> 260 261=back 262 263=back 264 265=head1 RETURN VALUES 266 267ossl_ht_new() returns an B<HT*> struct on success and NULL on error 268 269void ossl_ht_free(HT *htable); 270 271ossl_ht_flush() and ossl_ht_insert() return 1 on success and 0 on error 272 273ossl_ht_delete() returns 1 if the key was successfully deleted, and 0 if the 274key was not found. 275 276ossl_ht_count() returns the number of elements in the hash table 277 278ossl_ht_filter() returns an B<HT_VALUE_LIST> of all elements matching the 279provided filter 280 281ossl_ht_get() returns an B<HT_VALUE> pointer, or NULL if the element was not 282found. 283 284ossl_ht_insert() returns 1 if an element was inserted, 0 if the element is 285already present, -1 on fatal errors (memory allocation or growth not allowed). 286 287=head1 EXAMPLES 288 289#include <stdio.h> 290#include <string.h> 291 292#include <openssl/err.h> 293#include <openssl/crypto.h> 294#include <internal/hashtable.h> 295 296HT_START_KEY_DEFN(intkey) 297HT_DEF_KEY_FIELD(myintkey, int) 298HT_END_KEY_DEFN(INTKEY) 299 300IMPLEMENT_HT_VALUE_TYPE_FNS(int, test, static) 301 302static void int_free_fn(HT_VALUE *v) 303{ 304 int *i = ossl_crypto_test_int_from_value(v); 305 306 fprintf(stderr, "Freeing an element\n"); 307 OPENSSL_free(i); 308} 309 310static int test_int_hashtable(void) 311{ 312 /* 313 * our config says: 314 * int_free_fn - Our free handler 315 * NULL - Use default hash fn 316 * 0 - use default initial bucket size 317 */ 318 HT_CONFIG hash_conf = { 319 int_free_fn, 320 NULL, 321 0 322 }; 323 INTKEY key; 324 HT *ht = NULL; 325 HT_VALUE *v; 326 int rc; 327 int *newval = OPENSSL_malloc(sizeof(int)); 328 329 ht = ossl_ht_new(&hash_conf); 330 331 if (ht == NULL) 332 return 0; 333 334 if (newval == NULL) 335 goto out; 336 337 *newval = 1; 338 339 /* insert */ 340 HT_INIT_KEY(&key); 341 HT_SET_KEY_FIELD(&key, myintkey, 47); 342 ossl_ht_write_lock(ht); 343 rc = ossl_ht_test_int_insert(ht, TO_HT_KEY(&key), newval, NULL); 344 ossl_ht_write_unlock(ht); 345 if (rc == 0) 346 goto out; 347 348 /* num_items */ 349 if (ossl_ht_count(ht) != 1) 350 goto out; 351 352 /* lookup */ 353 HT_RESET_KEY(&key); 354 HT_SET_KEY_FIELD(&key, myintkey, 47); 355 ossl_ht_read_lock(ht); 356 v = ossl_ht_get(ht, TO_HT_KEY(&key); 357 fprintf(stderr, "found element with key 47 holding value %d\n", 358 *ossl_ht_test_int_from_value(v)); 359 ossl_ht_read_unlock(ht); 360 361 rc = 1; 362end: 363 /* this will call the free function for our element */ 364 ossl_ht_free(ht); 365 return rc; 366} 367 368=head1 COPYRIGHT 369 370Copyright 2024 The OpenSSL Project Authors. All Rights Reserved. 371 372Licensed under the Apache License 2.0 (the "License"). You may not use 373this file except in compliance with the License. You can obtain a copy 374in the file LICENSE in the source distribution or at 375L<https://www.openssl.org/source/license.html>. 376 377=cut 378
