Asterisk - The Open Source Telephony Project GIT-master-d856a3e
test_astobj2_thrash.c
Go to the documentation of this file.
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 manipulating 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
57struct hash_test {
58 /*! Unit under test */
60 /*! Number of entries to insert in the grow thread. */
62 /*! Number of entries added by the grow thread. */
64 /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
66 /*! When to give up on the tests */
67 struct timeval deadline;
68};
69
70static int alloc_count = 0;
71
72static 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 */
77static void ht_delete(void *obj)
78{
80}
81
82/*! \brief Create test element */
83static 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);
93 ast_assert(needed + 1 <= buflen);
94 return keybuf;
95}
96
97/*! \brief Grow the hash data as specified */
98static 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);
116 }
117 return NULL;
118}
119
120/*! Randomly lookup data in the hash */
121static 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 */
163static 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 */
193static 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 */
203static 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;
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
231static int hash_string(const void *obj, const int flags)
232{
234}
235
236static 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
248{
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;
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) {
330 "Invalid ao2 container size. Expected: %d, Actual: %d\n",
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",
341 res = AST_TEST_FAIL;
342 }
343
344 return res;
345}
346
347static int unload_module(void)
348{
350 return 0;
351}
352
353static int load_module(void)
354{
357}
358
359AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "astobj2 container thrash test");
Asterisk main include file. File version handling, generic pbx functions.
#define ao2_link(container, obj)
Add an object to a container.
Definition: astobj2.h:1532
@ CMP_MATCH
Definition: astobj2.h:1027
@ CMP_STOP
Definition: astobj2.h:1028
#define OBJ_POINTER
Definition: astobj2.h:1150
@ AO2_ALLOC_OPT_LOCK_MUTEX
Definition: astobj2.h:363
#define ao2_callback(c, flags, cb_fn, arg)
ao2_callback() is a generic function that applies cb_fn() to all objects in a container,...
Definition: astobj2.h:1693
int ao2_container_count(struct ao2_container *c)
Returns the number of elements in a container.
#define ao2_find(container, arg, flags)
Definition: astobj2.h:1736
#define ao2_ref(o, delta)
Reference/unreference an object and return the old refcount.
Definition: astobj2.h:459
@ OBJ_MULTIPLE
Definition: astobj2.h:1049
@ OBJ_UNLINK
Definition: astobj2.h:1039
#define ao2_alloc(data_size, destructor_fn)
Definition: astobj2.h:409
#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn)
Allocate and initialize a hash container with the desired number of buckets.
Definition: astobj2.h:1303
#define max(a, b)
Definition: f2c.h:198
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
Definition: hashtab.c:181
Asterisk locking-related definitions:
int ast_atomic_fetchadd_int(volatile int *p, int v)
Atomically add v to *p and return the previous value of *p.
Definition: lock.h:757
Asterisk module definitions.
#define AST_MODULE_INFO_STANDARD(keystr, desc)
Definition: module.h:581
#define ASTERISK_GPL_KEY
The text the key() function should return.
Definition: module.h:46
@ AST_MODULE_LOAD_SUCCESS
Definition: module.h:70
def info(msg)
#define NULL
Definition: resample.c:96
Generic container type.
struct timeval deadline
struct ao2_container * to_be_thrashed
Test Framework API.
@ TEST_INIT
Definition: test.h:200
@ TEST_EXECUTE
Definition: test.h:201
#define AST_TEST_REGISTER(cb)
Definition: test.h:127
#define ast_test_status_update(a, b, c...)
Definition: test.h:129
#define AST_TEST_UNREGISTER(cb)
Definition: test.h:128
ast_test_result_state
Definition: test.h:193
@ AST_TEST_PASS
Definition: test.h:195
@ AST_TEST_FAIL
Definition: test.h:196
@ AST_TEST_NOT_RUN
Definition: test.h:194
static void * hash_test_lookup(void *d)
static void * hash_test_shrink(void *d)
static int is_timed_out(struct hash_test const *data)
static void ht_delete(void *obj)
Free test element.
#define MAX_TEST_SECONDS
static int increment_count(void *obj, void *arg, int flags)
static void * hash_test_count(void *d)
static int compare_strings(void *lhs, void *rhs, int flags)
AST_TEST_DEFINE(hash_test)
static int hash_string(const void *obj, const int flags)
static char * ht_new(int i)
Create test element.
static int load_module(void)
static int unload_module(void)
#define MAX_HASH_ENTRIES
#define COUNT_SLEEP_US
static void * hash_test_grow(void *d)
Grow the hash data as specified.
#define HASH_BUCKETS
static int alloc_count
static struct test_val d
Time-related functions and macros.
int64_t ast_tvdiff_us(struct timeval end, struct timeval start)
Computes the difference (in microseconds) between two struct timeval instances.
Definition: time.h:87
struct timeval ast_tvadd(struct timeval a, struct timeval b)
Returns the sum of two timevals a + b.
Definition: extconf.c:2282
struct timeval ast_tvnow(void)
Returns current timeval. Meant to replace calls to gettimeofday().
Definition: time.h:159
struct timeval ast_tv(ast_time_t sec, ast_suseconds_t usec)
Returns a timeval from sec, usec.
Definition: time.h:235
Utility functions.
#define ast_assert(a)
Definition: utils.h:739
#define ast_pthread_create(a, b, c, d)
Definition: utils.h:584