Merge "app_voicemail.c: Support multiple file formats for forwarded messages."
[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 #include <pthread.h>
39 #include "asterisk/hashtab.h"
40 #include "asterisk/lock.h"
41 #include "asterisk/module.h"
42 #include "asterisk/test.h"
43 #include "asterisk/time.h"
44 #include "asterisk/utils.h"
45
46 #define MAX_HASH_ENTRIES 30000
47 #define MAX_TEST_SECONDS 60
48
49 struct hash_test {
50         /*! Unit under test */
51         struct ast_hashtab *to_be_thrashed;
52         /*! Number of entries to insert in the grow thread. */
53         int max_grow;
54         /*! Number of enteries added by the grow thread. */
55         int grow_count;
56         /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
57         int preload;
58         /*! When to give up on the tests */
59         struct timeval deadline;
60         /*! The actual test object */
61         struct ast_test *test;
62 };
63
64 static int is_timed_out(struct hash_test const *data) {
65         struct timeval now = ast_tvnow();
66         int val = ast_tvdiff_us(data->deadline, now) < 0;
67         if (val) {
68                 /* tv_usec is suseconds_t, which could be int or long */
69                 ast_test_status_update(data->test, "Now: %ld.%06ld Deadline: %ld.%06ld\n",
70                         now.tv_sec, (long)now.tv_usec,
71                         data->deadline.tv_sec, (long)data->deadline.tv_usec);
72         }
73         return val;
74 }
75
76 /*! /brief Create test element */
77 static char *ht_new(int i)
78 {
79         const int buflen = 12;
80         char *keybuf = ast_malloc(buflen);
81         int needed;
82         if (keybuf == NULL) {
83                 return NULL;
84         }
85         needed = snprintf(keybuf, buflen, "key%08x", (unsigned)i);
86         ast_assert(needed + 1 <= buflen);
87         return keybuf;
88 }
89
90 /*! /brief Free test element */
91 static void ht_delete(void *obj)
92 {
93         ast_free(obj);
94 }
95
96 /*! /brief Grow the hash data as specified */
97 static void *hash_test_grow(void *d)
98 {
99         struct hash_test *data = d;
100         int i;
101
102         for (i = 0; i < data->max_grow; ++i) {
103                 char *obj;
104                 if (is_timed_out(data)) {
105                         return "Growth timed out";
106                 }
107                 obj = ht_new(i);
108                 if (obj == NULL) {
109                         return "Allocation failed";
110                 }
111                 ast_hashtab_insert_immediate(data->to_be_thrashed, obj);
112                 ast_atomic_fetchadd_int(&data->grow_count, 1);
113         }
114         return NULL;
115 }
116
117 /*! Randomly lookup data in the hash */
118 static void *hash_test_lookup(void *d)
119 {
120         struct hash_test *data = d;
121         int max;
122         unsigned seed = time(NULL);
123
124         /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
125          * optimize away reads.
126          */
127         while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
128                 int i;
129                 char *obj;
130                 int is_in_hashtab;
131
132                 if (is_timed_out(data)) {
133                         return "Lookup timed out";
134                 }
135
136                 if (max == 0) {
137                         /* No data yet; yield and try again */
138                         sched_yield();
139                         continue;
140                 }
141
142                 /* Randomly lookup one object from the hash */
143                 i = rand_r(&seed) % max;
144                 obj = ht_new(i);
145                 if (obj == NULL) {
146                         return "Allocation failed.";
147                 }
148                 is_in_hashtab = (ast_hashtab_lookup(data->to_be_thrashed, obj) != NULL);
149                 ht_delete(obj);
150                 if (!is_in_hashtab) {
151                         return "key unexpectedly missing";
152                 }
153         }
154
155         return NULL;
156 }
157
158 /*! Delete entries from the hash */
159 static void *hash_test_shrink(void *d)
160 {
161         const struct hash_test *data = d;
162         int i;
163
164         for (i = 1; i < data->preload; ++i) {
165                 char *obj = ht_new(-i);
166                 char *from_hashtab;
167                 int deleted;
168
169                 if (obj == NULL) {
170                         return "Allocation failed";
171                 }
172                 from_hashtab = ast_hashtab_remove_object_via_lookup(data->to_be_thrashed, obj);
173                 deleted = from_hashtab != NULL;
174
175                 ht_delete(obj);
176                 ht_delete(from_hashtab);
177                 if (!deleted) {
178                         return "could not delete object";
179                 }
180                 if (is_timed_out(data)) {
181                         return "Shrink timed out";
182                 }
183         }
184         return NULL;
185 }
186
187 /*! Continuously iterate through all the entries in the hash */
188 static void *hash_test_count(void *d)
189 {
190         const struct hash_test *data = d;
191         int count = 0;
192         int last_count = 0;
193
194         while (count < data->max_grow) {
195                 struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(data->to_be_thrashed);
196                 char *ht = ast_hashtab_next(it);
197                 last_count = count;
198                 count = 0;
199                 while (ht) {
200                         /* only count keys added by grow thread */
201                         if (strncmp(ht, "key0", 4) == 0) {
202                                 ++count;
203                         }
204                         ht = ast_hashtab_next(it);
205                 }
206                 ast_hashtab_end_traversal(it);
207
208                 if (last_count == count) {
209                         /* Give other threads ample chance to run, note that using sched_yield here does not
210                          * provide enough of a chance and can cause this thread to starve others.
211                          */
212                         usleep(1);
213                 } else if (last_count > count) {
214                         /* Make sure the hashtable never shrinks */
215                         return "hashtab unexpectedly shrank";
216                 }
217
218                 if (is_timed_out(data)) {
219                         return "Count timed out";
220                 }
221         }
222
223         /* Successfully iterated over all of the expected elements */
224         return NULL;
225 }
226
227 AST_TEST_DEFINE(hash_test)
228 {
229         enum ast_test_result_state res = AST_TEST_PASS;
230         struct hash_test data = {};
231         pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
232         void *thread_results;
233         int i;
234
235         switch (cmd) {
236         case TEST_INIT:
237                 info->name = "thrash";
238                 info->category = "/main/hashtab/";
239                 info->summary = "Testing hashtab concurrency";
240                 info->description = "Test hashtab concurrency correctness.";
241                 return AST_TEST_NOT_RUN;
242         case TEST_EXECUTE:
243                 break;
244         }
245
246         ast_test_status_update(test, "Executing hash concurrency test...\n");
247         data.test = test;
248         data.preload = MAX_HASH_ENTRIES / 2;
249         data.max_grow = MAX_HASH_ENTRIES - data.preload;
250         data.deadline = ast_tvadd(ast_tvnow(), ast_tv(MAX_TEST_SECONDS, 0));
251         data.to_be_thrashed = ast_hashtab_create(MAX_HASH_ENTRIES / 100,
252                 ast_hashtab_compare_strings_nocase, ast_hashtab_resize_java,
253                 ast_hashtab_newsize_java, ast_hashtab_hash_string_nocase, 1);
254
255         if (data.to_be_thrashed == NULL) {
256                 ast_test_status_update(test, "Allocation failed\n");
257                 /* Nothing needs to be freed; early return is fine */
258                 return AST_TEST_FAIL;
259         }
260
261
262         /* preload with data to delete */
263         for (i = 1; i < data.preload; ++i) {
264                 char *obj = ht_new(-i);
265                 if (obj == NULL) {
266                         ast_test_status_update(test, "Allocation failed\n");
267                         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
268                         return AST_TEST_FAIL;
269                 }
270                 ast_hashtab_insert_immediate(data.to_be_thrashed, obj);
271         }
272
273         /* add data.max_grow entries to the hashtab */
274         ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
275         /* continually count the keys added by the grow thread */
276         ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
277         /* continually lookup keys added by the grow thread */
278         ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
279         /* delete all keys preloaded into the hashtab */
280         ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);
281
282         pthread_join(grow_thread, &thread_results);
283         if (thread_results != NULL) {
284                 ast_test_status_update(test, "Growth thread failed: %s\n",
285                         (char *)thread_results);
286                 res = AST_TEST_FAIL;
287         }
288
289         pthread_join(count_thread, &thread_results);
290         if (thread_results != NULL) {
291                 ast_test_status_update(test, "Count thread failed: %s\n",
292                         (char *)thread_results);
293                 res = AST_TEST_FAIL;
294         }
295
296         pthread_join(lookup_thread, &thread_results);
297         if (thread_results != NULL) {
298                 ast_test_status_update(test, "Lookup thread failed: %s\n",
299                         (char *)thread_results);
300                 res = AST_TEST_FAIL;
301         }
302
303         pthread_join(shrink_thread, &thread_results);
304         if (thread_results != NULL) {
305                 ast_test_status_update(test, "Shrink thread failed: %s\n",
306                         (char *)thread_results);
307                 res = AST_TEST_FAIL;
308         }
309
310         if (ast_hashtab_size(data.to_be_thrashed) != data.max_grow) {
311                 ast_test_status_update(test,
312                         "Invalid hashtab size. Expected: %d, Actual: %d\n",
313                         data.max_grow, ast_hashtab_size(data.to_be_thrashed));
314                 res = AST_TEST_FAIL;
315         }
316
317         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
318         return res;
319 }
320
321 static int unload_module(void)
322 {
323         AST_TEST_UNREGISTER(hash_test);
324         return 0;
325 }
326
327 static int load_module(void)
328 {
329         AST_TEST_REGISTER(hash_test);
330         return AST_MODULE_LOAD_SUCCESS;
331 }
332
333 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Hash test");