Asterisk - The Open Source Telephony Project  18.5.0
test_hashtab_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 <[email protected]>
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 <[email protected]> \endverbatim
23  *
24  * Inspired by the original hashtest.c by Steve Murphy <[email protected]>. 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 #include <pthread.h>
39 #include "asterisk/hashtab.h"
40 #include "asterisk/lock.h"
41 #include "asterisk/module.h"
42 #include "asterisk/test.h"
43 #include "asterisk/time.h"
44 #include "asterisk/utils.h"
45 
46 #define MAX_HASH_ENTRIES 30000
47 #define MAX_TEST_SECONDS 60
48 
49 struct hash_test {
50  /*! Unit under test */
52  /*! Number of entries to insert in the grow thread. */
53  int max_grow;
54  /*! Number of enteries added by the grow thread. */
55  int grow_count;
56  /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
57  int preload;
58  /*! When to give up on the tests */
59  struct timeval deadline;
60  /*! The actual test object */
61  struct ast_test *test;
62 };
63 
64 static int is_timed_out(struct hash_test const *data) {
65  struct timeval now = ast_tvnow();
66  int val = ast_tvdiff_us(data->deadline, now) < 0;
67  if (val) {
68  /* tv_usec is suseconds_t, which could be int or long */
69  ast_test_status_update(data->test, "Now: %ld.%06ld Deadline: %ld.%06ld\n",
70  now.tv_sec, (long)now.tv_usec,
71  data->deadline.tv_sec, (long)data->deadline.tv_usec);
72  }
73  return val;
74 }
75 
76 /*! /brief Create test element */
77 static char *ht_new(int i)
78 {
79  const int buflen = 12;
80  char *keybuf = ast_malloc(buflen);
81  int needed;
82  if (keybuf == NULL) {
83  return NULL;
84  }
85  needed = snprintf(keybuf, buflen, "key%08x", (unsigned)i);
86  ast_assert(needed + 1 <= buflen);
87  return keybuf;
88 }
89 
90 /*! /brief Free test element */
91 static void ht_delete(void *obj)
92 {
93  ast_free(obj);
94 }
95 
96 /*! /brief Grow the hash data as specified */
97 static void *hash_test_grow(void *d)
98 {
99  struct hash_test *data = d;
100  int i;
101 
102  for (i = 0; i < data->max_grow; ++i) {
103  char *obj;
104  if (is_timed_out(data)) {
105  return "Growth timed out";
106  }
107  obj = ht_new(i);
108  if (obj == NULL) {
109  return "Allocation failed";
110  }
113  }
114  return NULL;
115 }
116 
117 /*! Randomly lookup data in the hash */
118 static void *hash_test_lookup(void *d)
119 {
120  struct hash_test *data = d;
121  int max;
122  unsigned seed = time(NULL);
123 
124  /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
125  * optimize away reads.
126  */
127  while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
128  int i;
129  char *obj;
130  int is_in_hashtab;
131 
132  if (is_timed_out(data)) {
133  return "Lookup timed out";
134  }
135 
136  if (max == 0) {
137  /* No data yet; yield and try again */
138  sched_yield();
139  continue;
140  }
141 
142  /* Randomly lookup one object from the hash */
143  i = rand_r(&seed) % max;
144  obj = ht_new(i);
145  if (obj == NULL) {
146  return "Allocation failed.";
147  }
148  is_in_hashtab = (ast_hashtab_lookup(data->to_be_thrashed, obj) != NULL);
149  ht_delete(obj);
150  if (!is_in_hashtab) {
151  return "key unexpectedly missing";
152  }
153  }
154 
155  return NULL;
156 }
157 
158 /*! Delete entries from the hash */
159 static void *hash_test_shrink(void *d)
160 {
161  const struct hash_test *data = d;
162  int i;
163 
164  for (i = 1; i < data->preload; ++i) {
165  char *obj = ht_new(-i);
166  char *from_hashtab;
167  int deleted;
168 
169  if (obj == NULL) {
170  return "Allocation failed";
171  }
172  from_hashtab = ast_hashtab_remove_object_via_lookup(data->to_be_thrashed, obj);
173  deleted = from_hashtab != NULL;
174 
175  ht_delete(obj);
176  ht_delete(from_hashtab);
177  if (!deleted) {
178  return "could not delete object";
179  }
180  if (is_timed_out(data)) {
181  return "Shrink timed out";
182  }
183  }
184  return NULL;
185 }
186 
187 /*! Continuously iterate through all the entries in the hash */
188 static void *hash_test_count(void *d)
189 {
190  const struct hash_test *data = d;
191  int count = 0;
192  int last_count = 0;
193 
194  while (count < data->max_grow) {
196  char *ht = ast_hashtab_next(it);
197  last_count = count;
198  count = 0;
199  while (ht) {
200  /* only count keys added by grow thread */
201  if (strncmp(ht, "key0", 4) == 0) {
202  ++count;
203  }
204  ht = ast_hashtab_next(it);
205  }
207 
208  if (last_count == count) {
209  /* Give other threads ample chance to run, note that using sched_yield here does not
210  * provide enough of a chance and can cause this thread to starve others.
211  */
212  usleep(1);
213  } else if (last_count > count) {
214  /* Make sure the hashtable never shrinks */
215  return "hashtab unexpectedly shrank";
216  }
217 
218  if (is_timed_out(data)) {
219  return "Count timed out";
220  }
221  }
222 
223  /* Successfully iterated over all of the expected elements */
224  return NULL;
225 }
226 
228 {
230  struct hash_test data = {};
231  pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
232  void *thread_results;
233  int i;
234 
235  switch (cmd) {
236  case TEST_INIT:
237  info->name = "thrash";
238  info->category = "/main/hashtab/";
239  info->summary = "Testing hashtab concurrency";
240  info->description = "Test hashtab concurrency correctness.";
241  return AST_TEST_NOT_RUN;
242  case TEST_EXECUTE:
243  break;
244  }
245 
246  ast_test_status_update(test, "Executing hash concurrency test...\n");
247  data.test = test;
248  data.preload = MAX_HASH_ENTRIES / 2;
249  data.max_grow = MAX_HASH_ENTRIES - data.preload;
254 
255  if (data.to_be_thrashed == NULL) {
256  ast_test_status_update(test, "Allocation failed\n");
257  /* Nothing needs to be freed; early return is fine */
258  return AST_TEST_FAIL;
259  }
260 
261 
262  /* preload with data to delete */
263  for (i = 1; i < data.preload; ++i) {
264  char *obj = ht_new(-i);
265  if (obj == NULL) {
266  ast_test_status_update(test, "Allocation failed\n");
268  return AST_TEST_FAIL;
269  }
271  }
272 
273  /* add data.max_grow entries to the hashtab */
274  ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
275  /* continually count the keys added by the grow thread */
276  ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
277  /* continually lookup keys added by the grow thread */
278  ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
279  /* delete all keys preloaded into the hashtab */
280  ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);
281 
282  pthread_join(grow_thread, &thread_results);
283  if (thread_results != NULL) {
284  ast_test_status_update(test, "Growth thread failed: %s\n",
285  (char *)thread_results);
286  res = AST_TEST_FAIL;
287  }
288 
289  pthread_join(count_thread, &thread_results);
290  if (thread_results != NULL) {
291  ast_test_status_update(test, "Count thread failed: %s\n",
292  (char *)thread_results);
293  res = AST_TEST_FAIL;
294  }
295 
296  pthread_join(lookup_thread, &thread_results);
297  if (thread_results != NULL) {
298  ast_test_status_update(test, "Lookup thread failed: %s\n",
299  (char *)thread_results);
300  res = AST_TEST_FAIL;
301  }
302 
303  pthread_join(shrink_thread, &thread_results);
304  if (thread_results != NULL) {
305  ast_test_status_update(test, "Shrink thread failed: %s\n",
306  (char *)thread_results);
307  res = AST_TEST_FAIL;
308  }
309 
310  if (ast_hashtab_size(data.to_be_thrashed) != data.max_grow) {
312  "Invalid hashtab size. Expected: %d, Actual: %d\n",
314  res = AST_TEST_FAIL;
315  }
316 
318  return res;
319 }
320 
321 static int unload_module(void)
322 {
324  return 0;
325 }
326 
327 static int load_module(void)
328 {
331 }
332 
#define AST_MODULE_INFO_STANDARD(keystr, desc)
Definition: module.h:567
Asterisk locking-related definitions:
Asterisk main include file. File version handling, generic pbx functions.
int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
Compares two strings for equality, ignoring case.
Definition: hashtab.c:57
static void * hash_test_grow(void *d)
void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
Lookup this object in the hash table.
Definition: hashtab.c:486
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
Definition: ast_expr2.c:325
Time-related functions and macros.
static struct test_val d
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
void * ast_hashtab_next(struct ast_hashtab_iter *it)
Gets the next object in the list, advances iter one step returns null on end of traversal.
Definition: hashtab.c:683
Test Framework API.
#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:695
#define NULL
Definition: resample.c:96
static int is_timed_out(struct hash_test const *data)
AST_TEST_DEFINE(hash_test)
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
int ast_hashtab_resize_java(struct ast_hashtab *tab)
Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% o...
Definition: hashtab.c:84
static void ht_delete(void *obj)
Utility functions.
#define MAX_TEST_SECONDS
struct ast_test * test
#define ast_hashtab_insert_immediate(tab, obj)
Definition: hashtab.h:291
#define ast_test_status_update(a, b, c...)
Definition: test.h:129
#define ast_malloc(len)
A wrapper for malloc()
Definition: astmm.h:193
static void * hash_test_shrink(void *d)
void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
end the traversal, free the iterator, unlock if necc.
Definition: hashtab.c:674
static void * hash_test_lookup(void *d)
static char * ht_new(int i)
#define ast_hashtab_start_write_traversal(tab)
Definition: hashtab.h:377
void * ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:746
#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
static void * hash_test_count(void *d)
static int unload_module(void)
an iterator for traversing the buckets
Definition: hashtab.h:105
#define ast_free(a)
Definition: astmm.h:182
#define ast_pthread_create(a, b, c, d)
Definition: utils.h:559
#define MAX_HASH_ENTRIES
struct ast_hashtab * to_be_thrashed
Definition: test.c:65
struct timeval ast_tv(ast_time_t sec, ast_suseconds_t usec)
Returns a timeval from sec, usec.
Definition: time.h:226
static int load_module(void)
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
#define ast_hashtab_create(initial_buckets, compare, resize, newsize, hash, do_locking)
Definition: hashtab.h:261
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
Definition: hashtab.c:181
struct timeval deadline
#define ASTERISK_GPL_KEY
The text the key() function should return.
Definition: module.h:46
Asterisk module definitions.
int ast_hashtab_size(struct ast_hashtab *tab)
Returns the number of elements stored in the hashtab.
Definition: hashtab.c:577
ast_test_result_state
Definition: test.h:200
void ast_hashtab_destroy(struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj))
This func will free the hash table and all its memory.
Definition: hashtab.c:363
#define max(a, b)
Definition: f2c.h:198