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