Migrate hashtest/hashtest2 to be unit tests.
[asterisk/asterisk.git] / tests / test_hashtab_thrash.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2012, David M. Lee, II
5  *
6  * David M. Lee, II <dlee@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*
20  *! \file \brief Thrash a hash table, for fun and profit.
21  *
22  * \author\verbatim David M. Lee, II <dlee@digium.com> \endverbatim
23  *
24  * Inspired by the original hashtest.c by Steve Murphy <murf@digium.com>.  This test runs
25  * several threads manipulatings a concurrent hastab to see if they maintain
26  * consistency. While the tests attempt to check consistency and error normally, threading
27  * errors often result in segfaults.
28  * \ingroup tests
29  */
30
31 /*** MODULEINFO
32         <depend>TEST_FRAMEWORK</depend>
33         <support_level>core</support_level>
34  ***/
35
36 #include "asterisk.h"
37
38 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
39 #include <pthread.h>
40 #include "asterisk/hashtab.h"
41 #include "asterisk/lock.h"
42 #include "asterisk/module.h"
43 #include "asterisk/test.h"
44 #include "asterisk/time.h"
45 #include "asterisk/utils.h"
46
47 #define MAX_HASH_ENTRIES 30000
48 #define MAX_TEST_SECONDS 60
49
50 struct hash_test {
51         /*! Unit under test */
52         struct ast_hashtab *to_be_thrashed;
53         /*! Number of entries to insert in the grow thread. */
54         int max_grow;
55         /*! Number of enteries added by the grow thread. */
56         int grow_count;
57         /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
58         int preload;
59         /*! When to give up on the tests */
60         struct timeval deadline;
61 };
62
63 static int is_timed_out(struct hash_test const *data) {
64         return ast_tvdiff_us(data->deadline, ast_tvnow()) < 0;
65 }
66
67 /*! /brief Create test element */
68 static char *ht_new(int i)
69 {
70         const int buflen = 12;
71         char *keybuf = ast_malloc(buflen);
72         int needed;
73         if (keybuf == NULL) {
74                 return NULL;
75         }
76         needed = snprintf(keybuf, buflen, "key%08x", i);
77         ast_assert(needed + 1 <= buflen);
78         return keybuf;
79 }
80
81 /*! /brief Free test element */
82 static void ht_delete(void *obj)
83 {
84         ast_free(obj);
85 }
86
87 /*! /brief Grow the hash data as specified */
88 static void *hash_test_grow(void *d)
89 {
90         struct hash_test *data = d;
91         int i;
92
93         for (i = 0; i < data->max_grow; ++i) {
94                 char *obj;
95                 if (is_timed_out(data)) {
96                         return "Growth timed out";
97                 }
98                 obj = ht_new(i);
99                 if (obj == NULL) {
100                         return "Allocation failed";
101                 }
102                 ast_hashtab_insert_immediate(data->to_be_thrashed, obj);
103                 ast_atomic_fetchadd_int(&data->grow_count, 1);
104         }
105         return NULL;
106 }
107
108 /*! Randomly lookup data in the hash */
109 static void *hash_test_lookup(void *d)
110 {
111         struct hash_test *data = d;
112         int max;
113         unsigned seed = time(NULL);
114
115         /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
116          * optimize away reads.
117          */
118         while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
119                 int i;
120                 char *obj;
121                 int is_in_hashtab;
122
123                 if (is_timed_out(data)) {
124                         return "Lookup timed out";
125                 }
126
127                 if (max == 0) {
128                         /* No data yet; yield and try again */
129                         sched_yield();
130                         continue;
131                 }
132
133                 /* Randomly lookup one object from the hash */
134                 i = rand_r(&seed) % max;
135                 obj = ht_new(i);
136                 if (obj == NULL) {
137                         return "Allocation failed.";
138                 }
139                 is_in_hashtab = (ast_hashtab_lookup(data->to_be_thrashed, obj) != NULL);
140                 ht_delete(obj);
141                 if (!is_in_hashtab) {
142                         return "key unexpectedly missing";
143                 }
144         }
145
146         return NULL;
147 }
148
149 /*! Delete entries from the hash */
150 static void *hash_test_shrink(void *d)
151 {
152         const struct hash_test *data = d;
153         int i;
154
155         for (i = 1; i < data->preload; ++i) {
156                 char *obj = ht_new(-i);
157                 char *from_hashtab;
158                 int deleted;
159
160                 if (obj == NULL) {
161                         return "Allocation failed";
162                 }
163                 from_hashtab = ast_hashtab_remove_object_via_lookup(data->to_be_thrashed, obj);
164                 deleted = from_hashtab != NULL;
165
166                 ht_delete(obj);
167                 ht_delete(from_hashtab);
168                 if (!deleted) {
169                         return "could not delete object";
170                 }
171                 if (is_timed_out(data)) {
172                         return "Shrink timed out";
173                 }
174         }
175         return NULL;
176 }
177
178 /*! Continuously iterate through all the entries in the hash */
179 static void *hash_test_count(void *d)
180 {
181         const struct hash_test *data = d;
182         int count = 0;
183         int last_count = 0;
184
185         while (count < data->max_grow) {
186                 struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(data->to_be_thrashed);
187                 char *ht = ast_hashtab_next(it);
188                 last_count = count;
189                 count = 0;
190                 while (ht) {
191                         /* only count keys added by grow thread */
192                         if (strncmp(ht, "key0", 4) == 0) {
193                                 ++count;
194                         }
195                         ht = ast_hashtab_next(it);
196                 }
197                 ast_hashtab_end_traversal(it);
198
199                 if (last_count == count) {
200                         /* Allow other threads to run. */
201                         sched_yield();
202                 } else if (last_count > count) {
203                         /* Make sure the hashtable never shrinks */
204                         return "hashtab unexpectedly shrank";
205                 }
206
207                 if (is_timed_out(data)) {
208                         return "Count timed out";
209                 }
210         }
211
212         /* Successfully iterated over all of the expected elements */
213         return NULL;
214 }
215
216 AST_TEST_DEFINE(hash_test)
217 {
218         enum ast_test_result_state res = AST_TEST_PASS;
219         struct hash_test data = {};
220         pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
221         void *thread_results;
222         int i;
223
224         switch (cmd) {
225         case TEST_INIT:
226                 info->name = "thrash";
227                 info->category = "/main/hashtab/";
228                 info->summary = "Testing hashtab concurrency";
229                 info->description = "Test hashtab concurrency correctness.";
230                 return AST_TEST_NOT_RUN;
231         case TEST_EXECUTE:
232                 break;
233         }
234
235         ast_test_status_update(test, "Executing hash concurrency test...\n");
236         data.preload = MAX_HASH_ENTRIES / 2;
237         data.max_grow = MAX_HASH_ENTRIES - data.preload;
238         data.deadline = ast_tvadd(ast_tvnow(), ast_tv(MAX_TEST_SECONDS, 0));
239         data.to_be_thrashed = ast_hashtab_create(MAX_HASH_ENTRIES / 100,
240                 ast_hashtab_compare_strings_nocase, ast_hashtab_resize_java,
241                 ast_hashtab_newsize_java, ast_hashtab_hash_string_nocase, 1);
242
243         if (data.to_be_thrashed == NULL) {
244                 ast_test_status_update(test, "Allocation failed\n");
245                 /* Nothing needs to be freed; early return is fine */
246                 return AST_TEST_FAIL;
247         }
248
249
250         /* preload with data to delete */
251         for (i = 1; i < data.preload; ++i) {
252                 char *obj = ht_new(-i);
253                 if (obj == NULL) {
254                         ast_test_status_update(test, "Allocation failed\n");
255                         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
256                         return AST_TEST_FAIL;
257                 }
258                 ast_hashtab_insert_immediate(data.to_be_thrashed, obj);
259         }
260
261         /* add data.max_grow entries to the hashtab */
262         ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
263         /* continually count the keys added by the grow thread */
264         ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
265         /* continually lookup keys added by the grow thread */
266         ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
267         /* delete all keys preloaded into the hashtab */
268         ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);
269
270         pthread_join(grow_thread, &thread_results);
271         if (thread_results != NULL) {
272                 ast_test_status_update(test, "Growth thread failed: %s\n",
273                         (char *)thread_results);
274                 res = AST_TEST_FAIL;
275         }
276
277         pthread_join(count_thread, &thread_results);
278         if (thread_results != NULL) {
279                 ast_test_status_update(test, "Count thread failed: %s\n",
280                         (char *)thread_results);
281                 res = AST_TEST_FAIL;
282         }
283
284         pthread_join(lookup_thread, &thread_results);
285         if (thread_results != NULL) {
286                 ast_test_status_update(test, "Lookup thread failed: %s\n",
287                         (char *)thread_results);
288                 res = AST_TEST_FAIL;
289         }
290
291         pthread_join(shrink_thread, &thread_results);
292         if (thread_results != NULL) {
293                 ast_test_status_update(test, "Shrink thread failed: %s\n",
294                         (char *)thread_results);
295                 res = AST_TEST_FAIL;
296         }
297
298         if (ast_hashtab_size(data.to_be_thrashed) != data.max_grow) {
299                 ast_test_status_update(test,
300                         "Invalid hashtab size. Expected: %d, Actual: %d\n",
301                         data.max_grow, ast_hashtab_size(data.to_be_thrashed));
302                 res = AST_TEST_FAIL;
303         }
304
305         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
306         return res;
307 }
308
309 static int unload_module(void)
310 {
311         AST_TEST_UNREGISTER(hash_test);
312         return 0;
313 }
314
315 static int load_module(void)
316 {
317         AST_TEST_REGISTER(hash_test);
318         return AST_MODULE_LOAD_SUCCESS;
319 }
320
321 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Hash test");