Coverage Report

Created: 2024-11-21 07:03

/src/openssl/include/internal/hashtable.h
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 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
39.2k
#define HT_INIT_KEY(key) do { \
108
39.2k
memset((key), 0, sizeof(*(key))); \
109
39.2k
(key)->key_header.keysize = (sizeof(*(key)) - sizeof(HT_KEY)); \
110
39.2k
(key)->key_header.keybuf = (((uint8_t *)key) + sizeof(HT_KEY)); \
111
39.2k
} 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
39.2k
#define HT_SET_KEY_STRING_CASE(key, member, value) do { \
139
39.2k
   ossl_ht_strcase((key)->keyfields.member, value, sizeof((key)->keyfields.member) -1); \
140
39.2k
} 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
39.2k
#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
 */
234
static void ossl_unused ossl_ht_strcase(char *tgt, const char *src, int len)
235
39.2k
{
236
39.2k
    int i;
237
#if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
238
    const long int case_adjust = ~0x40;
239
#else
240
39.2k
    const long int case_adjust = ~0x20;
241
39.2k
#endif
242
243
39.2k
    if (src == NULL)
244
0
        return;
245
246
338k
    for (i = 0; src[i] != '\0' && i < len; i++)
247
299k
        tgt[i] = case_adjust & src[i];
248
39.2k
}
core_namemap.c:ossl_ht_strcase
Line
Count
Source
235
39.2k
{
236
39.2k
    int i;
237
#if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
238
    const long int case_adjust = ~0x40;
239
#else
240
39.2k
    const long int case_adjust = ~0x20;
241
39.2k
#endif
242
243
39.2k
    if (src == NULL)
244
0
        return;
245
246
338k
    for (i = 0; src[i] != '\0' && i < len; i++)
247
299k
        tgt[i] = case_adjust & src[i];
248
39.2k
}
Unexecuted instantiation: hashtable.c:ossl_ht_strcase
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