1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * SPDX-License-Identifier: MPL-2.0
5 *
6 * This Source Code Form is subject to the terms of the Mozilla Public
7 * License, v. 2.0. If a copy of the MPL was not distributed with this
8 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
9 *
10 * See the COPYRIGHT file distributed with this work for additional
11 * information regarding copyright ownership.
12 */
13
14 #if HAVE_CMOCKA
15
16 #include <inttypes.h>
17 #include <sched.h> /* IWYU pragma: keep */
18 #include <setjmp.h>
19 #include <stdarg.h>
20 #include <stddef.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #define UNIT_TESTING
26 #include <cmocka.h>
27
28 #include <isc/hash.h>
29 #include <isc/ht.h>
30 #include <isc/mem.h>
31 #include <isc/print.h>
32 #include <isc/string.h>
33 #include <isc/util.h>
34
35 #include "isctest.h"
36
37 static int
_setup(void ** state)38 _setup(void **state) {
39 isc_result_t result;
40
41 UNUSED(state);
42
43 result = isc_test_begin(NULL, true, 0);
44 assert_int_equal(result, ISC_R_SUCCESS);
45
46 return (0);
47 }
48
49 static int
_teardown(void ** state)50 _teardown(void **state) {
51 UNUSED(state);
52
53 isc_test_end();
54
55 return (0);
56 }
57
58 static void
test_ht_full(int bits,uintptr_t count)59 test_ht_full(int bits, uintptr_t count) {
60 isc_ht_t *ht = NULL;
61 isc_result_t result;
62 uintptr_t i;
63
64 result = isc_ht_init(&ht, test_mctx, bits);
65 assert_int_equal(result, ISC_R_SUCCESS);
66 assert_non_null(ht);
67
68 for (i = 1; i < count; i++) {
69 /*
70 * Note: snprintf() is followed with strlcat()
71 * to ensure we are always filling the 16 byte key.
72 */
73 unsigned char key[16];
74 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
75 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
76 result = isc_ht_add(ht, key, 16, (void *)i);
77 assert_int_equal(result, ISC_R_SUCCESS);
78 }
79
80 for (i = 1; i < count; i++) {
81 unsigned char key[16];
82 void *f = NULL;
83 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
84 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
85 result = isc_ht_find(ht, key, 16, &f);
86 assert_int_equal(result, ISC_R_SUCCESS);
87 assert_ptr_equal((void *)i, (uintptr_t)f);
88 }
89
90 for (i = 1; i < count; i++) {
91 unsigned char key[16];
92 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
93 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
94 result = isc_ht_add(ht, key, 16, (void *)i);
95 assert_int_equal(result, ISC_R_EXISTS);
96 }
97
98 for (i = 1; i < count; i++) {
99 char key[64];
100 /*
101 * Note: the key size is now strlen(key) which is bigger
102 * then the keys added above.
103 */
104 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
105 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
106 result = isc_ht_add(ht, (const unsigned char *)key, strlen(key),
107 (void *)i);
108 assert_int_equal(result, ISC_R_SUCCESS);
109 }
110
111 for (i = 1; i < count; i++) {
112 unsigned char key[16];
113 void *f = NULL;
114 /*
115 * Note: case of KEY is now in capitals,
116 */
117 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
118 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
119 result = isc_ht_find(ht, key, 16, &f);
120 assert_int_equal(result, ISC_R_NOTFOUND);
121 assert_null(f);
122 }
123
124 for (i = 1; i < count; i++) {
125 char key[64];
126 void *f = NULL;
127 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
128 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
129 result = isc_ht_find(ht, (const unsigned char *)key,
130 strlen(key), &f);
131 assert_int_equal(result, ISC_R_SUCCESS);
132 assert_ptr_equal(f, (void *)i);
133 }
134
135 for (i = 1; i < count; i++) {
136 unsigned char key[16];
137 void *f = NULL;
138 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
139 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
140 result = isc_ht_delete(ht, key, 16);
141 assert_int_equal(result, ISC_R_SUCCESS);
142 result = isc_ht_find(ht, key, 16, &f);
143 assert_int_equal(result, ISC_R_NOTFOUND);
144 assert_null(f);
145 }
146
147 for (i = 1; i < count; i++) {
148 unsigned char key[16];
149 /*
150 * Note: upper case KEY.
151 */
152 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
153 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
154 result = isc_ht_add(ht, key, 16, (void *)i);
155 assert_int_equal(result, ISC_R_SUCCESS);
156 }
157
158 for (i = 1; i < count; i++) {
159 char key[64];
160 void *f = NULL;
161 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
162 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
163 result = isc_ht_delete(ht, (const unsigned char *)key,
164 strlen(key));
165 assert_int_equal(result, ISC_R_SUCCESS);
166 result = isc_ht_find(ht, (const unsigned char *)key,
167 strlen(key), &f);
168 assert_int_equal(result, ISC_R_NOTFOUND);
169 assert_null(f);
170 }
171
172 for (i = 1; i < count; i++) {
173 unsigned char key[16];
174 void *f = NULL;
175 /*
176 * Note: case of KEY is now in capitals,
177 */
178 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
179 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key));
180 result = isc_ht_find(ht, key, 16, &f);
181 assert_int_equal(result, ISC_R_SUCCESS);
182 assert_ptr_equal((void *)i, (uintptr_t)f);
183 }
184
185 for (i = 1; i < count; i++) {
186 unsigned char key[16];
187 void *f = NULL;
188 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
189 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key));
190 result = isc_ht_find(ht, key, 16, &f);
191 assert_int_equal(result, ISC_R_NOTFOUND);
192 assert_null(f);
193 }
194
195 isc_ht_destroy(&ht);
196 assert_null(ht);
197 }
198
199 static void
test_ht_iterator()200 test_ht_iterator() {
201 isc_ht_t *ht = NULL;
202 isc_result_t result;
203 isc_ht_iter_t *iter = NULL;
204 uintptr_t i;
205 uintptr_t count = 10000;
206 uint32_t walked;
207 unsigned char key[16];
208 size_t tksize;
209
210 result = isc_ht_init(&ht, test_mctx, 16);
211 assert_int_equal(result, ISC_R_SUCCESS);
212 assert_non_null(ht);
213 for (i = 1; i <= count; i++) {
214 /*
215 * Note that the string we're snprintfing is always > 16 bytes
216 * so we are always filling the key.
217 */
218 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
219 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
220 result = isc_ht_add(ht, key, 16, (void *)i);
221 assert_int_equal(result, ISC_R_SUCCESS);
222 }
223
224 walked = 0;
225 result = isc_ht_iter_create(ht, &iter);
226 assert_int_equal(result, ISC_R_SUCCESS);
227
228 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS;
229 result = isc_ht_iter_next(iter))
230 {
231 unsigned char *tkey = NULL;
232 void *v = NULL;
233
234 isc_ht_iter_current(iter, &v);
235 isc_ht_iter_currentkey(iter, &tkey, &tksize);
236 assert_int_equal(tksize, 16);
237 i = (uintptr_t)v;
238 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
239 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
240 assert_memory_equal(key, tkey, 16);
241 walked++;
242 }
243 assert_int_equal(walked, count);
244 assert_int_equal(result, ISC_R_NOMORE);
245
246 /* erase odd */
247 walked = 0;
248 result = isc_ht_iter_first(iter);
249 while (result == ISC_R_SUCCESS) {
250 unsigned char *tkey = NULL;
251 void *v = NULL;
252
253 isc_ht_iter_current(iter, &v);
254 isc_ht_iter_currentkey(iter, &tkey, &tksize);
255 assert_int_equal(tksize, 16);
256 i = (uintptr_t)v;
257 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
258 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
259 assert_memory_equal(key, tkey, 16);
260 if ((uintptr_t)v % 2 == 0) {
261 result = isc_ht_iter_delcurrent_next(iter);
262 } else {
263 result = isc_ht_iter_next(iter);
264 }
265 walked++;
266 }
267 assert_int_equal(result, ISC_R_NOMORE);
268 assert_int_equal(walked, count);
269
270 /* erase even */
271 walked = 0;
272 result = isc_ht_iter_first(iter);
273 while (result == ISC_R_SUCCESS) {
274 unsigned char *tkey = NULL;
275 void *v = NULL;
276
277 isc_ht_iter_current(iter, &v);
278 isc_ht_iter_currentkey(iter, &tkey, &tksize);
279 assert_int_equal(tksize, 16);
280 i = (uintptr_t)v;
281 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i);
282 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key));
283 assert_memory_equal(key, tkey, 16);
284 if ((uintptr_t)v % 2 == 1) {
285 result = isc_ht_iter_delcurrent_next(iter);
286 } else {
287 result = isc_ht_iter_next(iter);
288 }
289 walked++;
290 }
291 assert_int_equal(result, ISC_R_NOMORE);
292 assert_int_equal(walked, count / 2);
293
294 walked = 0;
295 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS;
296 result = isc_ht_iter_next(iter))
297 {
298 walked++;
299 }
300
301 assert_int_equal(result, ISC_R_NOMORE);
302 assert_int_equal(walked, 0);
303
304 isc_ht_iter_destroy(&iter);
305 assert_null(iter);
306
307 isc_ht_destroy(&ht);
308 assert_null(ht);
309 }
310
311 /* 20 bit, 200K elements test */
312 static void
isc_ht_20(void ** state)313 isc_ht_20(void **state) {
314 UNUSED(state);
315 test_ht_full(20, 200000);
316 }
317
318 /* 8 bit, 20000 elements crowded test */
319 static void
isc_ht_8(void ** state)320 isc_ht_8(void **state) {
321 UNUSED(state);
322 test_ht_full(8, 20000);
323 }
324
325 /* 8 bit, 100 elements corner case test */
326 static void
isc_ht_1(void ** state)327 isc_ht_1(void **state) {
328 UNUSED(state);
329 test_ht_full(1, 100);
330 }
331
332 /* test hashtable iterator */
333 static void
isc_ht_iterator_test(void ** state)334 isc_ht_iterator_test(void **state) {
335 UNUSED(state);
336 test_ht_iterator();
337 }
338
339 int
main(void)340 main(void) {
341 const struct CMUnitTest tests[] = {
342 cmocka_unit_test(isc_ht_20),
343 cmocka_unit_test(isc_ht_8),
344 cmocka_unit_test(isc_ht_1),
345 cmocka_unit_test(isc_ht_iterator_test),
346 };
347
348 return (cmocka_run_group_tests(tests, _setup, _teardown));
349 }
350
351 #else /* HAVE_CMOCKA */
352
353 #include <stdio.h>
354
355 int
main(void)356 main(void) {
357 printf("1..0 # Skipped: cmocka not available\n");
358 return (SKIPPED_TEST_EXIT_CODE);
359 }
360
361 #endif /* if HAVE_CMOCKA */
362