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