/src/openssl/include/internal/hashtable.h

Source (jump to first uncovered line)
/*
 * Copyright 2024 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#ifndef OPENSSL_HASHTABLE_H
# define OPENSSL_HASHTABLE_H
# pragma once

#include <stddef.h>
#include <stdint.h>
#include <openssl/e_os2.h>
#include <internal/rcu.h>
#include "crypto/context.h"

typedef struct ht_internal_st HT;

/*
 * Represents a value in the hash table
 */
typedef struct ht_value_st {
    void *value;
    uintptr_t *type_id;
} HT_VALUE;

/*
 * Represents a list of values filtered from a hash table
 */
typedef struct ht_value_list_st {
    size_t list_len;
    HT_VALUE **list;
} HT_VALUE_LIST;

/*
 * Hashtable configuration
 */
typedef struct ht_config_st {
    OSSL_LIB_CTX *ctx;
    void (*ht_free_fn)(HT_VALUE *obj);
    uint64_t (*ht_hash_fn)(uint8_t *key, size_t keylen);
    uint32_t init_neighborhoods;
} HT_CONFIG;

/*
 * Key value for a hash lookup
 */
typedef struct ht_key_header_st {
    size_t keysize;
    uint8_t *keybuf;
} HT_KEY;

/*
 * Hashtable key rules
 * Any struct can be used to formulate a hash table key, as long as the
 * following rules
 * 1) The first element of the struct defining the key must be an HT_KEY
 * 2) All struct elements must have a compile time defined length
 * 3) Pointers can be used, but the value of the pointer, rather than
 *    the contents of the address it points to will be used to compute
 *    the hash
 * The key definition macros will assist with enforcing these rules
 */

/*
 * Starts the definition of a hash table key
 */
#define HT_START_KEY_DEFN(keyname) \
typedef struct keyname##_st { \
    HT_KEY key_header; \
    struct {

/*
 * Ends a hash table key definitions
 */
#define HT_END_KEY_DEFN(keyname) \
    } keyfields; \
} keyname;

/*
 * Defines a field in a hash table key
 */
#define HT_DEF_KEY_FIELD(name, type) type name;

/*
 * convenience macro to define a static char
 * array field in a hash table key
 */
#define HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size) \
     HT_DEF_KEY_FIELD(name[size], char)

/*
 * Defines a uint8_t (blob) field in a hash table key
 */
#define HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size) \
    HT_DEF_KEY_FIELD(name[size], uint8_t)

/*
 * Initializes a key
 */
#define HT_INIT_KEY(key) do { \
memset((key), 0, sizeof(*(key))); \
(key)->key_header.keysize = (sizeof(*(key)) - sizeof(HT_KEY)); \
(key)->key_header.keybuf = (((uint8_t *)key) + sizeof(HT_KEY)); \
} while(0)

/*
 * Resets a hash table key to a known state
 */
#define HT_KEY_RESET(key) memset((key)->key_header.keybuf, 0, (key)->key_header.keysize)

/*
 * Sets a scalar field in a hash table key
 */
#define HT_SET_KEY_FIELD(key, member, value) (key)->keyfields.member = value;

/*
 * Sets a string field in a hash table key, preserving
 * null terminator
 */
#define HT_SET_KEY_STRING(key, member, value) do { \
    if ((value) != NULL) \
        strncpy((key)->keyfields.member, value, sizeof((key)->keyfields.member) - 1); \
} while(0)

/*
 * This is the same as HT_SET_KEY_STRING, except that it uses
 * ossl_ht_strcase to make the value being passed case insensitive
 * This is useful for instances in which we want upper and lower case
 * key value to hash to the same entry
 */
#define HT_SET_KEY_STRING_CASE(key, member, value) do { \
   ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) -1); \
} while(0)

/*
 * Sets a uint8_t (blob) field in a hash table key
 */
#define HT_SET_KEY_BLOB(key, member, value, len) do { \
    if (value != NULL) \
        memcpy((key)->keyfields.member, value, len); \
} while(0)

/*
 * Converts a defined key type to an HT_KEY
 */
#define TO_HT_KEY(key) &(key)->key_header

/*
 * Converts an HT_KEY back to its defined
 * type
 */
#define FROM_HT_KEY(key, type) (type)(key)

/*
 * Implements the following type safe operations for a hash table
 * ossl_ht_NAME_TYPE_insert - insert a value to a hash table of type TYPE
 * ossl_ht_NAME_TYPE_get - gets a value of a specific type from the hash table
 * ossl_ht_NAME_TYPE_from_value - converts an HT_VALUE to its type
 * ossl_ht_NAME_TYPE_to_value - converts a TYPE to an HT_VALUE
 * ossl_ht_NAME_TYPE_type - boolean to detect if a value is of TYPE
 */
#define IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx) \
static uintptr_t name##_##vtype##_id = 0; \
pfx ossl_unused int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key,      \
                                                      vtype *data,             \
                                                      vtype **olddata) {       \
    HT_VALUE inval;                                                            \
    HT_VALUE *oval = NULL;                                                     \
    int rc;                                                                    \
                                                                               \
    inval.value = data;                                                        \
    inval.type_id = &name##_##vtype##_id;                                      \
    rc = ossl_ht_insert(h, key, &inval, olddata == NULL ? NULL : &oval);       \
    if (oval != NULL)                                                          \
        *olddata = (vtype *)oval->value;                                       \
    return rc;                                                                 \
}                                                                              \
                                                                               \
pfx ossl_unused vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v)      \
{                                                                              \
    uintptr_t *expect_type = &name##_##vtype##_id;                             \
    if (v == NULL)                                                             \
        return NULL;                                                           \
    if (v->type_id != expect_type)                                             \
        return NULL;                                                           \
    return (vtype *)v->value;                                                  \
}                                                                              \
                                                                               \
pfx ossl_unused vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h,       \
                                                                  HT_KEY *key, \
                                                                  HT_VALUE **v)\
{                                                                              \
    HT_VALUE *vv;                                                              \
    vv = ossl_ht_get(h, key);                                                  \
    if (vv == NULL)                                                            \
        return NULL;                                                           \
    *v = ossl_rcu_deref(&vv);                                                  \
    return ossl_ht_##name##_##vtype##_from_value(*v);                          \
}                                                                              \
                                                                               \
pfx ossl_unused HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data,     \
                                                              HT_VALUE *v)     \
{                                                                              \
    v->type_id = &name##_##vtype##_id;                                         \
    v->value = data;                                                           \
    return v;                                                                  \
}                                                                              \
                                                                               \
pfx ossl_unused int ossl_ht_##name##_##vtype##_type(HT_VALUE *h)               \
{                                                                              \
    return h->type_id == &name##_##vtype##_id;                                 \
}

#define DECLARE_HT_VALUE_TYPE_FNS(vtype, name)                                 \
int ossl_ht_##name##_##vtype##_insert(HT *h, HT_KEY *key, vtype *data,         \
                                      vtype **olddata);                        \
vtype *ossl_ht_##name##_##vtype##_from_value(HT_VALUE *v);                     \
vtype *ossl_unused ossl_ht_##name##_##vtype##_get(HT *h,                       \
                                                  HT_KEY *key,                 \
                                                  HT_VALUE **v);               \
HT_VALUE *ossl_ht_##name##_##vtype##_to_value(vtype *data, HT_VALUE *v);       \
int ossl_ht_##name##_##vtype##_type(HT_VALUE *h);                              \

/*
 * Helper function to construct case insensitive keys
 */
static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len)
{
    int i;
#if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
    const long int case_adjust = ~0x40;
#else
    const long int case_adjust = ~0x20;
#endif

    if (src == NULL)
        return;

    for (i = 0; src[i] != '\0' && i < len; i++)
        tgt[i] = case_adjust & src[i];
}

/*
 * Create a new hashtable
 */
HT *ossl_ht_new(HT_CONFIG *conf);

/*
 * Frees a hash table, potentially freeing all elements
 */
void ossl_ht_free(HT *htable);

/*
 * Lock the table for reading
 */
void ossl_ht_read_lock(HT *htable);

/*
 * Lock the table for writing
 */
void ossl_ht_write_lock(HT *htable);

/*
 * Read unlock
 */
void ossl_ht_read_unlock(HT *htable);

/*
 * Write unlock
 */
void ossl_ht_write_unlock (HT *htable);

/*
 * Empties a hash table, potentially freeing all elements
 */
int  ossl_ht_flush(HT *htable);

/*
 * Inserts an element to a hash table, optionally returning
 * replaced data to caller
 * Returns 1 if the insert was successful, 0 on error
 */
int ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data,
                   HT_VALUE **olddata);

/*
 * Deletes a value from a hash table, based on key
 * Returns 1 if the key was removed, 0 if they key was not found
 */
int ossl_ht_delete(HT *htable, HT_KEY *key);

/*
 * Returns number of elements in the hash table
 */
size_t ossl_ht_count(HT *htable);

/*
 * Iterates over each element in the table.
 * aborts the loop when cb returns 0
 * Contents of elements in the list may be modified during
 * this traversal, assuming proper thread safety is observed while doing
 * so (holding the table write lock is sufficient).  However, elements of the
 * table may not be inserted or removed while iterating.
 */
void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg),
                           void *arg);
/*
 * Returns a list of elements in a hash table based on
 * filter function return value.  Returns NULL on error,
 * or an HT_VALUE_LIST object on success.  Note it is possible
 * That a list will be returned with 0 entries, if none were found.
 * The zero length list must still be freed via ossl_ht_value_list_free 
 */
HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len,
                              int (*filter)(HT_VALUE *obj, void *arg),
                              void *arg);
/*
 * Frees the list returned from ossl_ht_filter
 */
void ossl_ht_value_list_free(HT_VALUE_LIST *list);

/*
 * Fetches a value from the hash table, based
 * on key.  Returns NULL if the element was not found.
 */
HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key);

#endif

Coverage Report

Created: 2024-07-27 06:36

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