test/lhash_test.c

   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
  30 DEFINE_LHASH_OF(int);
  31
  32 static 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 };
  34 static const unsigned int n_int_tests = OSSL_NELEM(int_tests);
  35 static short int_found[OSSL_NELEM(int_tests)];
  36 static short int_not_found;
  37
  38 static unsigned long int int_hash(const int *p)
  39 {
  40     return 3 & *p;      /* To force collisions */
  41 }
  42
  43 static int int_cmp(const int *p, const int *q)
  44 {
  45     return *p != *q;
  46 }
  47
  48 static 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
  58 static 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
  68 static 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
  78 IMPLEMENT_LHASH_DOALL_ARG(int, short);
  79
  80 static 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;
 178 end:
 179     lh_int_free(h);
 180     return testresult;
 181 }
 182
 183 static unsigned long int stress_hash(const int *p)
 184 {
 185     return *p;
 186 }
 187
 188 static 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;
 239 end:
 240     lh_int_free(h);
 241     return testresult;
 242 }
 243
 244 int setup_tests(void)
 245 {
 246     ADD_TEST(test_int_lhash);
 247     ADD_TEST(test_stress);
 248     return 1;
 249 }