Coverage Report

Created: 2024-07-27 06:36

/src/openssl/crypto/lhash/lhash.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 1995-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
#include <stdio.h>
11
#include <string.h>
12
#include <stdlib.h>
13
#include <openssl/crypto.h>
14
#include <openssl/lhash.h>
15
#include <openssl/err.h>
16
#include "crypto/ctype.h"
17
#include "crypto/lhash.h"
18
#include "lhash_local.h"
19
20
/*
21
 * A hashing implementation that appears to be based on the linear hashing
22
 * algorithm:
23
 * https://en.wikipedia.org/wiki/Linear_hashing
24
 *
25
 * Litwin, Witold (1980), "Linear hashing: A new tool for file and table
26
 * addressing", Proc. 6th Conference on Very Large Databases: 212-223
27
 * https://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf
28
 *
29
 * From the Wikipedia article "Linear hashing is used in the BDB Berkeley
30
 * database system, which in turn is used by many software systems such as
31
 * OpenLDAP, using a C implementation derived from the CACM article and first
32
 * published on the Usenet in 1988 by Esmond Pitt."
33
 *
34
 * The CACM paper is available here:
35
 * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf
36
 */
37
38
#undef MIN_NODES
39
17.2k
#define MIN_NODES       16
40
5.44k
#define UP_LOAD         (2*LH_LOAD_MULT) /* load times 256 (default 2) */
41
5.44k
#define DOWN_LOAD       (LH_LOAD_MULT) /* load times 256 (default 1) */
42
43
static int expand(OPENSSL_LHASH *lh);
44
static void contract(OPENSSL_LHASH *lh);
45
static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash);
46
47
OPENSSL_LHASH *OPENSSL_LH_set_thunks(OPENSSL_LHASH *lh,
48
                                     OPENSSL_LH_HASHFUNCTHUNK hw,
49
                                     OPENSSL_LH_COMPFUNCTHUNK cw,
50
                                     OPENSSL_LH_DOALL_FUNC_THUNK daw,
51
                                     OPENSSL_LH_DOALL_FUNCARG_THUNK daaw)
52
5.44k
{
53
54
5.44k
    if (lh == NULL)
55
0
        return NULL;
56
5.44k
    lh->compw = cw;
57
5.44k
    lh->hashw = hw;
58
5.44k
    lh->daw = daw;
59
5.44k
    lh->daaw = daaw;
60
5.44k
    return lh;
61
5.44k
}
62
63
OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
64
5.44k
{
65
5.44k
    OPENSSL_LHASH *ret;
66
67
5.44k
    if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
68
0
        return NULL;
69
5.44k
    if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
70
0
        goto err;
71
5.44k
    ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
72
5.44k
    ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
73
5.44k
    ret->num_nodes = MIN_NODES / 2;
74
5.44k
    ret->num_alloc_nodes = MIN_NODES;
75
5.44k
    ret->pmax = MIN_NODES / 2;
76
5.44k
    ret->up_load = UP_LOAD;
77
5.44k
    ret->down_load = DOWN_LOAD;
78
5.44k
    return ret;
79
80
0
err:
81
0
    OPENSSL_free(ret->b);
82
0
    OPENSSL_free(ret);
83
0
    return NULL;
84
5.44k
}
85
86
void OPENSSL_LH_free(OPENSSL_LHASH *lh)
87
5.43k
{
88
5.43k
    if (lh == NULL)
89
2
        return;
90
91
5.43k
    OPENSSL_LH_flush(lh);
92
5.43k
    OPENSSL_free(lh->b);
93
5.43k
    OPENSSL_free(lh);
94
5.43k
}
95
96
void OPENSSL_LH_flush(OPENSSL_LHASH *lh)
97
5.46k
{
98
5.46k
    unsigned int i;
99
5.46k
    OPENSSL_LH_NODE *n, *nn;
100
101
5.46k
    if (lh == NULL)
102
0
        return;
103
104
51.4k
    for (i = 0; i < lh->num_nodes; i++) {
105
45.9k
        n = lh->b[i];
106
50.1k
        while (n != NULL) {
107
4.20k
            nn = n->next;
108
4.20k
            OPENSSL_free(n);
109
4.20k
            n = nn;
110
4.20k
        }
111
45.9k
        lh->b[i] = NULL;
112
45.9k
    }
113
114
5.46k
    lh->num_items = 0;
115
5.46k
}
116
117
void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
118
11.2k
{
119
11.2k
    unsigned long hash;
120
11.2k
    OPENSSL_LH_NODE *nn, **rn;
121
11.2k
    void *ret;
122
123
11.2k
    lh->error = 0;
124
11.2k
    if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
125
0
        return NULL;        /* 'lh->error++' already done in 'expand' */
126
127
11.2k
    rn = getrn(lh, data, &hash);
128
129
11.2k
    if (*rn == NULL) {
130
5.16k
        if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
131
0
            lh->error++;
132
0
            return NULL;
133
0
        }
134
5.16k
        nn->data = data;
135
5.16k
        nn->next = NULL;
136
5.16k
        nn->hash = hash;
137
5.16k
        *rn = nn;
138
5.16k
        ret = NULL;
139
5.16k
        lh->num_items++;
140
6.10k
    } else {                    /* replace same key */
141
6.10k
        ret = (*rn)->data;
142
6.10k
        (*rn)->data = data;
143
6.10k
    }
144
11.2k
    return ret;
145
11.2k
}
146
147
void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
148
944
{
149
944
    unsigned long hash;
150
944
    OPENSSL_LH_NODE *nn, **rn;
151
944
    void *ret;
152
153
944
    lh->error = 0;
154
944
    rn = getrn(lh, data, &hash);
155
156
944
    if (*rn == NULL) {
157
0
        return NULL;
158
944
    } else {
159
944
        nn = *rn;
160
944
        *rn = nn->next;
161
944
        ret = nn->data;
162
944
        OPENSSL_free(nn);
163
944
    }
164
165
944
    lh->num_items--;
166
944
    if ((lh->num_nodes > MIN_NODES) &&
167
944
        (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
168
2
        contract(lh);
169
170
944
    return ret;
171
944
}
172
173
void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
174
2.14M
{
175
2.14M
    unsigned long hash;
176
2.14M
    OPENSSL_LH_NODE **rn;
177
178
2.14M
    if (lh->error != 0)
179
0
        lh->error = 0;
180
181
2.14M
    rn = getrn(lh, data, &hash);
182
183
2.14M
    return *rn == NULL ? NULL : (*rn)->data;
184
2.14M
}
185
186
static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
187
                          OPENSSL_LH_DOALL_FUNC_THUNK wfunc,
188
                          OPENSSL_LH_DOALL_FUNC func,
189
                          OPENSSL_LH_DOALL_FUNCARG func_arg,
190
                          OPENSSL_LH_DOALL_FUNCARG_THUNK wfunc_arg,
191
                          void *arg)
192
29.9k
{
193
29.9k
    int i;
194
29.9k
    OPENSSL_LH_NODE *a, *n;
195
196
29.9k
    if (lh == NULL)
197
0
        return;
198
199
    /*
200
     * reverse the order so we search from 'top to bottom' We were having
201
     * memory leaks otherwise
202
     */
203
6.45M
    for (i = lh->num_nodes - 1; i >= 0; i--) {
204
6.42M
        a = lh->b[i];
205
19.2M
        while (a != NULL) {
206
12.8M
            n = a->next;
207
12.8M
            if (use_arg)
208
12.8M
                wfunc_arg(a->data, arg, func_arg);
209
1.62k
            else
210
1.62k
                wfunc(a->data, func);
211
12.8M
            a = n;
212
12.8M
        }
213
6.42M
    }
214
29.9k
}
215
216
void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
217
285
{
218
285
    if (lh == NULL)
219
0
        return;
220
221
285
    doall_util_fn(lh, 0, lh->daw, func, (OPENSSL_LH_DOALL_FUNCARG)NULL,
222
285
                  (OPENSSL_LH_DOALL_FUNCARG_THUNK)NULL, NULL);
223
285
}
224
225
void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh,
226
                          OPENSSL_LH_DOALL_FUNCARG func, void *arg)
227
0
{
228
0
    if (lh == NULL)
229
0
        return;
230
231
0
    doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
232
0
                  (OPENSSL_LH_DOALL_FUNC)NULL, func, lh->daaw, arg);
233
0
}
234
235
void OPENSSL_LH_doall_arg_thunk(OPENSSL_LHASH *lh,
236
                                OPENSSL_LH_DOALL_FUNCARG_THUNK daaw,
237
                                OPENSSL_LH_DOALL_FUNCARG fn, void *arg)
238
29.6k
{
239
29.6k
    doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
240
29.6k
                  (OPENSSL_LH_DOALL_FUNC)NULL, fn, daaw, arg);
241
29.6k
}
242
243
static int expand(OPENSSL_LHASH *lh)
244
2.25k
{
245
2.25k
    OPENSSL_LH_NODE **n, **n1, **n2, *np;
246
2.25k
    unsigned int p, pmax, nni, j;
247
2.25k
    unsigned long hash;
248
249
2.25k
    nni = lh->num_alloc_nodes;
250
2.25k
    p = lh->p;
251
2.25k
    pmax = lh->pmax;
252
2.25k
    if (p + 1 >= pmax) {
253
22
        j = nni * 2;
254
22
        n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j);
255
22
        if (n == NULL) {
256
0
            lh->error++;
257
0
            return 0;
258
0
        }
259
22
        lh->b = n;
260
22
        memset(n + nni, 0, sizeof(*n) * (j - nni));
261
22
        lh->pmax = nni;
262
22
        lh->num_alloc_nodes = j;
263
22
        lh->p = 0;
264
2.23k
    } else {
265
2.23k
        lh->p++;
266
2.23k
    }
267
268
2.25k
    lh->num_nodes++;
269
2.25k
    n1 = &(lh->b[p]);
270
2.25k
    n2 = &(lh->b[p + pmax]);
271
2.25k
    *n2 = NULL;
272
273
9.23k
    for (np = *n1; np != NULL;) {
274
6.97k
        hash = np->hash;
275
6.97k
        if ((hash % nni) != p) { /* move it */
276
1.42k
            *n1 = (*n1)->next;
277
1.42k
            np->next = *n2;
278
1.42k
            *n2 = np;
279
1.42k
        } else
280
5.55k
            n1 = &((*n1)->next);
281
6.97k
        np = *n1;
282
6.97k
    }
283
284
2.25k
    return 1;
285
2.25k
}
286
287
static void contract(OPENSSL_LHASH *lh)
288
2
{
289
2
    OPENSSL_LH_NODE **n, *n1, *np;
290
291
2
    np = lh->b[lh->p + lh->pmax - 1];
292
2
    lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
293
2
    if (lh->p == 0) {
294
0
        n = OPENSSL_realloc(lh->b,
295
0
                            (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax));
296
0
        if (n == NULL) {
297
            /* fputs("realloc error in lhash", stderr); */
298
0
            lh->error++;
299
0
        } else {
300
0
            lh->b = n;
301
0
        }
302
0
        lh->num_alloc_nodes /= 2;
303
0
        lh->pmax /= 2;
304
0
        lh->p = lh->pmax - 1;
305
0
    } else
306
2
        lh->p--;
307
308
2
    lh->num_nodes--;
309
310
2
    n1 = lh->b[(int)lh->p];
311
2
    if (n1 == NULL)
312
2
        lh->b[(int)lh->p] = np;
313
0
    else {
314
0
        while (n1->next != NULL)
315
0
            n1 = n1->next;
316
0
        n1->next = np;
317
0
    }
318
2
}
319
320
static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
321
                               const void *data, unsigned long *rhash)
322
2.15M
{
323
2.15M
    OPENSSL_LH_NODE **ret, *n1;
324
2.15M
    unsigned long hash, nn;
325
326
2.15M
    if (lh->hashw != NULL)
327
2.15M
        hash = lh->hashw(data, lh->hash);
328
0
    else
329
0
        hash = lh->hash(data);
330
331
2.15M
    *rhash = hash;
332
333
2.15M
    nn = hash % lh->pmax;
334
2.15M
    if (nn < lh->p)
335
1.21M
        nn = hash % lh->num_alloc_nodes;
336
337
2.15M
    ret = &(lh->b[(int)nn]);
338
3.86M
    for (n1 = *ret; n1 != NULL; n1 = n1->next) {
339
3.71M
        if (n1->hash != hash) {
340
1.71M
            ret = &(n1->next);
341
1.71M
            continue;
342
1.71M
        }
343
344
2.00M
        if (lh->compw != NULL) {
345
2.00M
            if (lh->compw(n1->data, data, lh->comp) == 0)
346
2.00M
                break;
347
2.00M
        } else {
348
0
            if (lh->comp(n1->data, data) == 0)
349
0
                break;
350
0
        }
351
408
        ret = &(n1->next);
352
408
    }
353
2.15M
    return ret;
354
2.15M
}
355
356
/*
357
 * The following hash seems to work very well on normal text strings no
358
 * collisions on /usr/dict/words and it distributes on %2^n quite well, not
359
 * as good as MD5, but still good.
360
 */
361
unsigned long OPENSSL_LH_strhash(const char *c)
362
674k
{
363
674k
    unsigned long ret = 0;
364
674k
    long n;
365
674k
    unsigned long v;
366
674k
    int r;
367
368
674k
    if ((c == NULL) || (*c == '\0'))
369
673k
        return ret;
370
371
995
    n = 0x100;
372
13.0k
    while (*c) {
373
12.0k
        v = n | (*c);
374
12.0k
        n += 0x100;
375
12.0k
        r = (int)((v >> 2) ^ v) & 0x0f;
376
        /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
377
12.0k
        ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
378
12.0k
        ret &= 0xFFFFFFFFL;
379
12.0k
        ret ^= v * v;
380
12.0k
        c++;
381
12.0k
    }
382
995
    return (ret >> 16) ^ ret;
383
674k
}
384
385
/*
386
 * Case insensitive string hashing.
387
 *
388
 * The lower/upper case bit is masked out (forcing all letters to be capitals).
389
 * The major side effect on non-alpha characters is mapping the symbols and
390
 * digits into the control character range (which should be harmless).
391
 * The duplication (with respect to the hash value) of printable characters
392
 * are that '`', '{', '|', '}' and '~' map to '@', '[', '\', ']' and '^'
393
 * respectively (which seems tolerable).
394
 *
395
 * For EBCDIC, the alpha mapping is to lower case, most symbols go to control
396
 * characters.  The only duplication is '0' mapping to '^', which is better
397
 * than for ASCII.
398
 */
399
unsigned long ossl_lh_strcasehash(const char *c)
400
1.49M
{
401
1.49M
    unsigned long ret = 0;
402
1.49M
    long n;
403
1.49M
    unsigned long v;
404
1.49M
    int r;
405
#if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
406
    const long int case_adjust = ~0x40;
407
#else
408
1.49M
    const long int case_adjust = ~0x20;
409
1.49M
#endif
410
411
1.49M
    if (c == NULL || *c == '\0')
412
0
        return ret;
413
414
11.0M
    for (n = 0x100; *c != '\0'; n += 0x100) {
415
9.59M
        v = n | (case_adjust & *c);
416
9.59M
        r = (int)((v >> 2) ^ v) & 0x0f;
417
        /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
418
9.59M
        ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
419
9.59M
        ret &= 0xFFFFFFFFL;
420
9.59M
        ret ^= v * v;
421
9.59M
        c++;
422
9.59M
    }
423
1.49M
    return (ret >> 16) ^ ret;
424
1.49M
}
425
426
unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
427
30.1k
{
428
30.1k
    return lh ? lh->num_items : 0;
429
30.1k
}
430
431
unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
432
5.19k
{
433
5.19k
    return lh->down_load;
434
5.19k
}
435
436
void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
437
10.3k
{
438
10.3k
    lh->down_load = down_load;
439
10.3k
}
440
441
int OPENSSL_LH_error(OPENSSL_LHASH *lh)
442
1.03k
{
443
1.03k
    return lh->error;
444
1.03k
}