1/*
2 * Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2017, Oracle and/or its affiliates.  All rights reserved.
4 *
5 * Licensed under the Apache License 2.0 (the "License").  You may not use
6 * this file except in compliance with the License.  You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 */
10
11#include <stdio.h>
12#include <string.h>
13
14#include <openssl/opensslconf.h>
15#include <openssl/lhash.h>
16#include <openssl/err.h>
17#include <openssl/crypto.h>
18
19#include "internal/nelem.h"
20#include "testutil.h"
21
22/*
23 * The macros below generate unused functions which error out one of the clang
24 * builds.  We disable this check here.
25 */
26#ifdef __clang__
27#pragma clang diagnostic ignored "-Wunused-function"
28#endif
29
30DEFINE_LHASH_OF(int);
31
32static int int_tests[] = { 65537, 13, 1, 3, -5, 6, 7, 4, -10, -12, -14, 22, 9,
33                           -17, 16, 17, -23, 35, 37, 173, 11 };
34static const unsigned int n_int_tests = OSSL_NELEM(int_tests);
35static short int_found[OSSL_NELEM(int_tests)];
36static short int_not_found;
37
38static unsigned long int int_hash(const int *p)
39{
40    return 3 & *p;      /* To force collisions */
41}
42
43static int int_cmp(const int *p, const int *q)
44{
45    return *p != *q;
46}
47
48static int int_find(int n)
49{
50    unsigned int i;
51
52    for (i = 0; i < n_int_tests; i++)
53        if (int_tests[i] == n)
54            return i;
55    return -1;
56}
57
58static void int_doall(int *v)
59{
60    const int n = int_find(*v);
61
62    if (n < 0)
63        int_not_found++;
64    else
65        int_found[n]++;
66}
67
68static void int_doall_arg(int *p, short *f)
69{
70    const int n = int_find(*p);
71
72    if (n < 0)
73        int_not_found++;
74    else
75        f[n]++;
76}
77
78IMPLEMENT_LHASH_DOALL_ARG(int, short);
79
80static int test_int_lhash(void)
81{
82    static struct {
83        int data;
84        int null;
85    } dels[] = {
86        { 65537,    0 },
87        { 173,      0 },
88        { 999,      1 },
89        { 37,       0 },
90        { 1,        0 },
91        { 34,       1 }
92    };
93    const unsigned int n_dels = OSSL_NELEM(dels);
94    LHASH_OF(int) *h = lh_int_new(&int_hash, &int_cmp);
95    unsigned int i;
96    int testresult = 0, j, *p;
97
98    if (!TEST_ptr(h))
99        goto end;
100
101    /* insert */
102    for (i = 0; i < n_int_tests; i++)
103        if (!TEST_ptr_null(lh_int_insert(h, int_tests + i))) {
104            TEST_info("int insert %d", i);
105            goto end;
106        }
107
108    /* num_items */
109    if (!TEST_int_eq(lh_int_num_items(h), n_int_tests))
110        goto end;
111
112    /* retrieve */
113    for (i = 0; i < n_int_tests; i++)
114        if (!TEST_int_eq(*lh_int_retrieve(h, int_tests + i), int_tests[i])) {
115            TEST_info("lhash int retrieve value %d", i);
116            goto end;
117        }
118    for (i = 0; i < n_int_tests; i++)
119        if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + i), int_tests + i)) {
120            TEST_info("lhash int retrieve address %d", i);
121            goto end;
122        }
123    j = 1;
124    if (!TEST_ptr_eq(lh_int_retrieve(h, &j), int_tests + 2))
125        goto end;
126
127    /* replace */
128    j = 13;
129    if (!TEST_ptr(p = lh_int_insert(h, &j)))
130        goto end;
131    if (!TEST_ptr_eq(p, int_tests + 1))
132        goto end;
133    if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + 1), &j))
134        goto end;
135
136    /* do_all */
137    memset(int_found, 0, sizeof(int_found));
138    int_not_found = 0;
139    lh_int_doall(h, &int_doall);
140    if (!TEST_int_eq(int_not_found, 0)) {
141        TEST_info("lhash int doall encountered a not found condition");
142        goto end;
143    }
144    for (i = 0; i < n_int_tests; i++)
145        if (!TEST_int_eq(int_found[i], 1)) {
146            TEST_info("lhash int doall %d", i);
147            goto end;
148        }
149
150    /* do_all_arg */
151    memset(int_found, 0, sizeof(int_found));
152    int_not_found = 0;
153    lh_int_doall_short(h, int_doall_arg, int_found);
154    if (!TEST_int_eq(int_not_found, 0)) {
155        TEST_info("lhash int doall arg encountered a not found condition");
156        goto end;
157    }
158    for (i = 0; i < n_int_tests; i++)
159        if (!TEST_int_eq(int_found[i], 1)) {
160            TEST_info("lhash int doall arg %d", i);
161            goto end;
162        }
163
164    /* delete */
165    for (i = 0; i < n_dels; i++) {
166        const int b = lh_int_delete(h, &dels[i].data) == NULL;
167        if (!TEST_int_eq(b ^ dels[i].null,  0)) {
168            TEST_info("lhash int delete %d", i);
169            goto end;
170        }
171    }
172
173    /* error */
174    if (!TEST_int_eq(lh_int_error(h), 0))
175        goto end;
176
177    testresult = 1;
178end:
179    lh_int_free(h);
180    return testresult;
181}
182
183static unsigned long int stress_hash(const int *p)
184{
185    return *p;
186}
187
188static int test_stress(void)
189{
190    LHASH_OF(int) *h = lh_int_new(&stress_hash, &int_cmp);
191    const unsigned int n = 2500000;
192    unsigned int i;
193    int testresult = 0, *p;
194
195    if (!TEST_ptr(h))
196        goto end;
197
198    /* insert */
199    for (i = 0; i < n; i++) {
200        p = OPENSSL_malloc(sizeof(i));
201        if (!TEST_ptr(p)) {
202            TEST_info("lhash stress out of memory %d", i);
203            goto end;
204        }
205        *p = 3 * i + 1;
206        lh_int_insert(h, p);
207    }
208
209    /* num_items */
210    if (!TEST_int_eq(lh_int_num_items(h), n))
211            goto end;
212
213    TEST_info("hash full statistics:");
214    OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err);
215    TEST_note("hash full node usage:");
216    OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err);
217
218    /* delete in a different order */
219    for (i = 0; i < n; i++) {
220        const int j = (7 * i + 4) % n * 3 + 1;
221
222        if (!TEST_ptr(p = lh_int_delete(h, &j))) {
223            TEST_info("lhash stress delete %d\n", i);
224            goto end;
225        }
226        if (!TEST_int_eq(*p, j)) {
227            TEST_info("lhash stress bad value %d", i);
228            goto end;
229        }
230        OPENSSL_free(p);
231    }
232
233    TEST_info("hash empty statistics:");
234    OPENSSL_LH_stats_bio((OPENSSL_LHASH *)h, bio_err);
235    TEST_note("hash empty node usage:");
236    OPENSSL_LH_node_usage_stats_bio((OPENSSL_LHASH *)h, bio_err);
237
238    testresult = 1;
239end:
240    lh_int_free(h);
241    return testresult;
242}
243
244int setup_tests(void)
245{
246    ADD_TEST(test_int_lhash);
247    ADD_TEST(test_stress);
248    return 1;
249}
250