test/lhash_test.c

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