Asterisk - The Open Source Telephony Project  GIT-master-44aef04
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 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 */
60  /*! Number of entries to insert in the grow thread. */
61  int max_grow;
62  /*! Number of enteries added by the grow thread. */
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 {
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);
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);
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;
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 
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 
347 static int unload_module(void)
348 {
350  return 0;
351 }
352 
353 static int load_module(void)
354 {
357 }
358 
359 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "astobj2 container thrash test");
#define AST_MODULE_INFO_STANDARD(keystr, desc)
Definition: module.h:567
#define MAX_HASH_ENTRIES
Asterisk locking-related definitions:
Asterisk main include file. File version handling, generic pbx functions.
int ao2_container_count(struct ao2_container *c)
Returns the number of elements in a container.
Time-related functions and macros.
#define OBJ_POINTER
Definition: astobj2.h:1154
static int alloc_count
static struct test_val d
#define ao2_callback(c, flags, cb_fn, arg)
Definition: astobj2.h:1716
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
Test Framework API.
static int compare_strings(void *lhs, void *rhs, int flags)
#define AST_TEST_REGISTER(cb)
Definition: test.h:127
struct timeval ast_tvnow(void)
Returns current timeval. Meant to replace calls to gettimeofday().
Definition: time.h:150
#define ast_assert(a)
Definition: utils.h:650
AST_TEST_DEFINE(hash_test)
#define MAX_TEST_SECONDS
#define NULL
Definition: resample.c:96
static int load_module(void)
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:755
static int hash_string(const void *obj, const int flags)
Utility functions.
static int unload_module(void)
#define ast_test_status_update(a, b, c...)
Definition: test.h:129
static void * hash_test_grow(void *d)
#define HASH_BUCKETS
#define ao2_ref(o, delta)
Definition: astobj2.h:464
#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn)
Definition: astobj2.h:1310
#define AST_TEST_UNREGISTER(cb)
Definition: test.h:128
def info(msg)
struct timeval ast_tvadd(struct timeval a, struct timeval b)
Returns the sum of two timevals a + b.
Definition: extconf.c:2283
#define ao2_alloc(data_size, destructor_fn)
Definition: astobj2.h:411
#define ast_pthread_create(a, b, c, d)
Definition: utils.h:499
static void * hash_test_lookup(void *d)
#define ao2_find(container, arg, flags)
Definition: astobj2.h:1756
#define COUNT_SLEEP_US
static char * ht_new(int i)
struct timeval ast_tv(ast_time_t sec, ast_suseconds_t usec)
Returns a timeval from sec, usec.
Definition: time.h:226
static void ht_delete(void *obj)
struct ao2_container * to_be_thrashed
int64_t ast_tvdiff_us(struct timeval end, struct timeval start)
Computes the difference (in microseconds) between two struct timeval instances.
Definition: time.h:78
static void * hash_test_shrink(void *d)
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
Definition: hashtab.c:181
Generic container type.
struct timeval deadline
#define ASTERISK_GPL_KEY
The text the key() function should return.
Definition: module.h:46
Asterisk module definitions.
ast_test_result_state
Definition: test.h:200
static void * hash_test_count(void *d)
static int increment_count(void *obj, void *arg, int flags)
static int is_timed_out(struct hash_test const *data)
#define ao2_link(container, obj)
Definition: astobj2.h:1549
#define max(a, b)
Definition: f2c.h:198