Merge "Revert "app_voicemail: Remove need to subscribe to stasis""
[asterisk/asterisk.git] / tests / test_astobj2_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 astobj2 container, for fun and profit.
21  *
22  * \author\verbatim David M. Lee, II <dlee@digium.com> \endverbatim
23  *
24  * Inspired by the original hashtest2.c by Steve Murphy <murf@digium.com>.  This test runs
25  * several threads manipulatings a concurrent astobj2 container 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/astobj2.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 15000
48 /*
49  * Use one of the online calculators to find the first prime number
50  * greater than MAX_HASH_ENTRIES / 100.
51  */
52 #define HASH_BUCKETS 151
53
54 #define COUNT_SLEEP_US 500
55 #define MAX_TEST_SECONDS 60
56
57 struct hash_test {
58         /*! Unit under test */
59         struct ao2_container *to_be_thrashed;
60         /*! Number of entries to insert in the grow thread. */
61         int max_grow;
62         /*! Number of enteries added by the grow thread. */
63         int grow_count;
64         /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
65         int preload;
66         /*! When to give up on the tests */
67         struct timeval deadline;
68 };
69
70 static int alloc_count = 0;
71
72 static int is_timed_out(struct hash_test const *data) {
73         return ast_tvdiff_us(data->deadline, ast_tvnow()) < 0;
74 }
75
76 /*! /brief Free test element */
77 static void ht_delete(void *obj)
78 {
79         ast_atomic_fetchadd_int(&alloc_count, -1);
80 }
81
82 /*! /brief Create test element */
83 static char *ht_new(int i)
84 {
85         const int buflen = 12;
86         char *keybuf = ao2_alloc(buflen, ht_delete);
87         int needed;
88         if (keybuf == NULL) {
89                 return NULL;
90         }
91         needed = snprintf(keybuf, buflen, "key%08x", (unsigned)i);
92         ast_atomic_fetchadd_int(&alloc_count, 1);
93         ast_assert(needed + 1 <= buflen);
94         return keybuf;
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 *ht;
105                 if (is_timed_out(data)) {
106                         printf("Growth timed out at %d\n", i);
107                         return "Growth timed out";
108                 }
109                 ht = ht_new(i);
110                 if (ht == NULL) {
111                         return "Allocation failed";
112                 }
113                 ao2_link(data->to_be_thrashed, ht);
114                 ao2_ref(ht, -1);
115                 ast_atomic_fetchadd_int(&data->grow_count, 1);
116         }
117         return NULL;
118 }
119
120 /*! Randomly lookup data in the hash */
121 static void *hash_test_lookup(void *d)
122 {
123         struct hash_test *data = d;
124         int max;
125         unsigned seed = time(NULL);
126
127         /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
128          * optimize away reads.
129          */
130         while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
131                 int i;
132                 char *obj;
133                 char *from_ao2;
134
135                 if (is_timed_out(data)) {
136                         return "Lookup timed out";
137                 }
138
139                 if (max == 0) {
140                         /* No data yet; yield and try again */
141                         sched_yield();
142                         continue;
143                 }
144
145                 /* Randomly lookup one object from the hash */
146                 i = rand_r(&seed) % max;
147                 obj = ht_new(i);
148                 if (obj == NULL) {
149                         return "Allocation failed";
150                 }
151                 from_ao2 = ao2_find(data->to_be_thrashed, obj, OBJ_POINTER);
152                 ao2_ref(obj, -1);
153                 ao2_ref(from_ao2, -1);
154                 if (from_ao2 == NULL) {
155                         return "Key unexpectedly missing";
156                 }
157         }
158
159         return NULL;
160 }
161
162 /*! Delete entries from the hash */
163 static void *hash_test_shrink(void *d)
164 {
165         const struct hash_test *data = d;
166         int i;
167
168         for (i = 1; i < data->preload; ++i) {
169                 char *obj = ht_new(-i);
170                 char *from_ao2;
171
172                 if (obj == NULL) {
173                         return "Allocation failed";
174                 }
175                 from_ao2 = ao2_find(data->to_be_thrashed, obj, OBJ_UNLINK | OBJ_POINTER);
176
177                 ao2_ref(obj, -1);
178                 if (from_ao2) {
179                         ao2_ref(from_ao2, -1);
180                 } else {
181                         return "Could not find object to delete";
182                 }
183
184                 if (is_timed_out(data)) {
185                         return "Shrink timed out";
186                 }
187         }
188
189         return NULL;
190 }
191
192 /*! ao2_callback for hash_test_count */
193 static int increment_count(void *obj, void *arg, int flags) {
194         char *ht = obj;
195         int *count = arg;
196         if (strncmp(ht, "key0", 4) == 0) {
197                 ++(*count);
198         }
199         return 0;
200 }
201
202 /*! Continuously iterate through all the entries in the hash */
203 static void *hash_test_count(void *d)
204 {
205         const struct hash_test *data = d;
206         int count = 0;
207         int last_count = 0;
208
209         while (count < data->max_grow) {
210                 last_count = count;
211                 count = 0;
212                 ao2_callback(data->to_be_thrashed, OBJ_MULTIPLE, increment_count, &count);
213
214                 if (last_count == count) {
215                         /* Allow other threads to run. */
216                         usleep(COUNT_SLEEP_US);
217                 } else if (last_count > count) {
218                         /* Make sure the ao2 container never shrinks */
219                         return "ao2 container unexpectedly shrank";
220                 }
221
222                 if (is_timed_out(data)) {
223                         return "Count timed out";
224                 }
225         }
226
227         /* Successfully iterated over all of the expected elements */
228         return NULL;
229 }
230
231 static int hash_string(const void *obj, const int flags)
232 {
233         return ast_hashtab_hash_string_nocase(obj);
234 }
235
236 static int compare_strings(void *lhs, void *rhs, int flags)
237 {
238         const char *lhs_str = lhs;
239         const char *rhs_str = rhs;
240         if (strcasecmp(lhs_str, rhs_str) == 0) {
241                 return CMP_MATCH | CMP_STOP;
242         } else {
243                 return 0;
244         }
245 }
246
247 AST_TEST_DEFINE(hash_test)
248 {
249         enum ast_test_result_state res = AST_TEST_PASS;
250         struct hash_test data = {};
251         pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
252         void *thread_results;
253         int i;
254
255         switch (cmd) {
256         case TEST_INIT:
257                 info->name = "thrash";
258                 info->category = "/main/astobj2/";
259                 info->summary = "Testing astobj2 container concurrency";
260                 info->description = "Test astobj2 container concurrency correctness.";
261                 return AST_TEST_NOT_RUN;
262         case TEST_EXECUTE:
263                 break;
264         }
265
266         ast_test_status_update(test, "Executing hash concurrency test...\n");
267         data.preload = MAX_HASH_ENTRIES / 2;
268         data.max_grow = MAX_HASH_ENTRIES - data.preload;
269         data.deadline = ast_tvadd(ast_tvnow(), ast_tv(MAX_TEST_SECONDS, 0));
270         data.to_be_thrashed = ao2_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, 0,
271                 HASH_BUCKETS, hash_string, NULL, compare_strings);
272
273         if (data.to_be_thrashed == NULL) {
274                 ast_test_status_update(test, "Allocation failed\n");
275                 /* Nothing needs to be freed; early return is fine */
276                 return AST_TEST_FAIL;
277         }
278
279         /* preload with data to delete */
280         for (i = 1; i < data.preload; ++i) {
281                 char *ht = ht_new(-i);
282                 if (ht == NULL) {
283                         ast_test_status_update(test, "Allocation failed\n");
284                         ao2_ref(data.to_be_thrashed, -1);
285                         return AST_TEST_FAIL;
286                 }
287                 ao2_link(data.to_be_thrashed, ht);
288                 ao2_ref(ht, -1);
289         }
290
291         /* add data.max_grow entries to the ao2 container */
292         ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
293         /* continually count the keys added by the grow thread */
294         ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
295         /* continually lookup keys added by the grow thread */
296         ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
297         /* delete all keys preloaded into the ao2 container */
298         ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);
299
300         pthread_join(grow_thread, &thread_results);
301         if (thread_results != NULL) {
302                 ast_test_status_update(test, "Growth thread failed: %s\n",
303                         (char *)thread_results);
304                 res = AST_TEST_FAIL;
305         }
306
307         pthread_join(count_thread, &thread_results);
308         if (thread_results != NULL) {
309                 ast_test_status_update(test, "Count thread failed: %s\n",
310                         (char *)thread_results);
311                 res = AST_TEST_FAIL;
312         }
313
314         pthread_join(lookup_thread, &thread_results);
315         if (thread_results != NULL) {
316                 ast_test_status_update(test, "Lookup thread failed: %s\n",
317                         (char *)thread_results);
318                 res = AST_TEST_FAIL;
319         }
320
321         pthread_join(shrink_thread, &thread_results);
322         if (thread_results != NULL) {
323                 ast_test_status_update(test, "Shrink thread failed: %s\n",
324                         (char *)thread_results);
325                 res = AST_TEST_FAIL;
326         }
327
328         if (ao2_container_count(data.to_be_thrashed) != data.max_grow) {
329                 ast_test_status_update(test,
330                         "Invalid ao2 container size. Expected: %d, Actual: %d\n",
331                         data.max_grow, ao2_container_count(data.to_be_thrashed));
332                 res = AST_TEST_FAIL;
333         }
334
335         ao2_ref(data.to_be_thrashed, -1);
336
337         /* check for object leaks */
338         if (ast_atomic_fetchadd_int(&alloc_count, 0) != 0) {
339                 ast_test_status_update(test, "Leaked %d objects!\n",
340                         ast_atomic_fetchadd_int(&alloc_count, 0));
341                 res = AST_TEST_FAIL;
342         }
343
344         return res;
345 }
346
347 static int unload_module(void)
348 {
349         AST_TEST_UNREGISTER(hash_test);
350         return 0;
351 }
352
353 static int load_module(void)
354 {
355         AST_TEST_REGISTER(hash_test);
356         return AST_MODULE_LOAD_SUCCESS;
357 }
358
359 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "astobj2 container thrash test");