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