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