Asterisk - The Open Source Telephony Project  18.5.0
Data Structures | Macros | Functions | Variables
test_hashtab_thrash.c File Reference
#include "asterisk.h"
#include <pthread.h>
#include "asterisk/hashtab.h"
#include "asterisk/lock.h"
#include "asterisk/module.h"
#include "asterisk/test.h"
#include "asterisk/time.h"
#include "asterisk/utils.h"
Include dependency graph for test_hashtab_thrash.c:

Go to the source code of this file.

Data Structures

struct  hash_test
 

Macros

#define MAX_HASH_ENTRIES   30000
 
#define MAX_TEST_SECONDS   60
 

Functions

static void __reg_module (void)
 
static void __unreg_module (void)
 
struct ast_moduleAST_MODULE_SELF_SYM (void)
 
 AST_TEST_DEFINE (hash_test)
 
static void * hash_test_count (void *d)
 
static void * hash_test_grow (void *d)
 
static void * hash_test_lookup (void *d)
 
static void * hash_test_shrink (void *d)
 
static void ht_delete (void *obj)
 
static char * ht_new (int i)
 
static int is_timed_out (struct hash_test const *data)
 
static int load_module (void)
 
static int unload_module (void)
 

Variables

static struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Hash test" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
 
static const struct ast_module_infoast_module_info = &__mod_info
 

Macro Definition Documentation

◆ MAX_HASH_ENTRIES

#define MAX_HASH_ENTRIES   30000

Definition at line 46 of file test_hashtab_thrash.c.

Referenced by AST_TEST_DEFINE().

◆ MAX_TEST_SECONDS

#define MAX_TEST_SECONDS   60

Definition at line 47 of file test_hashtab_thrash.c.

Referenced by AST_TEST_DEFINE().

Function Documentation

◆ __reg_module()

static void __reg_module ( void  )
static

Definition at line 333 of file test_hashtab_thrash.c.

◆ __unreg_module()

static void __unreg_module ( void  )
static

Definition at line 333 of file test_hashtab_thrash.c.

◆ AST_MODULE_SELF_SYM()

struct ast_module* AST_MODULE_SELF_SYM ( void  )

Definition at line 333 of file test_hashtab_thrash.c.

◆ AST_TEST_DEFINE()

AST_TEST_DEFINE ( hash_test  )

Definition at line 227 of file test_hashtab_thrash.c.

References ast_hashtab_compare_strings_nocase(), ast_hashtab_create, ast_hashtab_destroy(), ast_hashtab_hash_string_nocase(), ast_hashtab_insert_immediate, ast_hashtab_newsize_java(), ast_hashtab_resize_java(), ast_hashtab_size(), ast_pthread_create, AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, ast_tv(), ast_tvadd(), ast_tvnow(), hash_test::deadline, hash_test_count(), hash_test_grow(), hash_test_lookup(), hash_test_shrink(), ht_delete(), ht_new(), sip_to_pjsip::info(), hash_test::max_grow, MAX_HASH_ENTRIES, MAX_TEST_SECONDS, NULL, hash_test::preload, hash_test::test, TEST_EXECUTE, TEST_INIT, and hash_test::to_be_thrashed.

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 }
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)
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
struct timeval ast_tvnow(void)
Returns current timeval. Meant to replace calls to gettimeofday().
Definition: time.h:150
#define NULL
Definition: resample.c:96
static void ht_delete(void *obj)
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
#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
static void * hash_test_shrink(void *d)
static void * hash_test_lookup(void *d)
static char * ht_new(int i)
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)
#define ast_pthread_create(a, b, c, d)
Definition: utils.h:559
#define MAX_HASH_ENTRIES
struct timeval ast_tv(ast_time_t sec, ast_suseconds_t usec)
Returns a timeval from sec, usec.
Definition: time.h:226
struct ao2_container * to_be_thrashed
#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
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
static struct ast_test * test
Definition: localtime.c:115
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

◆ hash_test_count()

static void* hash_test_count ( void *  d)
static

Continuously iterate through all the entries in the hash

Definition at line 188 of file test_hashtab_thrash.c.

References ast_hashtab_end_traversal(), ast_hashtab_next(), ast_hashtab_start_write_traversal, d, is_timed_out(), hash_test::max_grow, NULL, and hash_test::to_be_thrashed.

Referenced by AST_TEST_DEFINE().

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 }
static struct test_val d
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
#define NULL
Definition: resample.c:96
static int is_timed_out(struct hash_test const *data)
void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
end the traversal, free the iterator, unlock if necc.
Definition: hashtab.c:674
#define ast_hashtab_start_write_traversal(tab)
Definition: hashtab.h:377
an iterator for traversing the buckets
Definition: hashtab.h:105
struct ao2_container * to_be_thrashed

◆ hash_test_grow()

static void* hash_test_grow ( void *  d)
static

/brief Grow the hash data as specified

Definition at line 97 of file test_hashtab_thrash.c.

References ast_atomic_fetchadd_int(), ast_hashtab_insert_immediate, d, hash_test::grow_count, ht_new(), is_timed_out(), hash_test::max_grow, NULL, and hash_test::to_be_thrashed.

Referenced by AST_TEST_DEFINE().

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 }
static struct test_val d
#define NULL
Definition: resample.c:96
static int is_timed_out(struct hash_test const *data)
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
#define ast_hashtab_insert_immediate(tab, obj)
Definition: hashtab.h:291
static char * ht_new(int i)
struct ao2_container * to_be_thrashed

◆ hash_test_lookup()

static void* hash_test_lookup ( void *  d)
static

Randomly lookup data in the hash

Definition at line 118 of file test_hashtab_thrash.c.

References ast_atomic_fetchadd_int(), ast_hashtab_lookup(), d, hash_test::grow_count, ht_delete(), ht_new(), is_timed_out(), max, hash_test::max_grow, NULL, and hash_test::to_be_thrashed.

Referenced by AST_TEST_DEFINE().

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 }
void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
Lookup this object in the hash table.
Definition: hashtab.c:486
static struct test_val d
#define NULL
Definition: resample.c:96
static int is_timed_out(struct hash_test const *data)
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 void ht_delete(void *obj)
static char * ht_new(int i)
struct ao2_container * to_be_thrashed
#define max(a, b)
Definition: f2c.h:198

◆ hash_test_shrink()

static void* hash_test_shrink ( void *  d)
static

Delete entries from the hash

Definition at line 159 of file test_hashtab_thrash.c.

References ast_hashtab_remove_object_via_lookup(), d, ht_delete(), ht_new(), is_timed_out(), NULL, hash_test::preload, and hash_test::to_be_thrashed.

Referenced by AST_TEST_DEFINE().

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 }
static struct test_val d
#define NULL
Definition: resample.c:96
static int is_timed_out(struct hash_test const *data)
static void ht_delete(void *obj)
static char * ht_new(int i)
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
struct ao2_container * to_be_thrashed

◆ ht_delete()

static void ht_delete ( void *  obj)
static

/brief Free test element

Definition at line 91 of file test_hashtab_thrash.c.

References ast_free.

Referenced by AST_TEST_DEFINE(), hash_test_lookup(), and hash_test_shrink().

92 {
93  ast_free(obj);
94 }
#define ast_free(a)
Definition: astmm.h:182

◆ ht_new()

static char* ht_new ( int  i)
static

/brief Create test element

Definition at line 77 of file test_hashtab_thrash.c.

References ast_assert, ast_malloc, and NULL.

Referenced by AST_TEST_DEFINE(), hash_test_grow(), hash_test_lookup(), and hash_test_shrink().

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 }
#define ast_assert(a)
Definition: utils.h:695
#define NULL
Definition: resample.c:96
#define ast_malloc(len)
A wrapper for malloc()
Definition: astmm.h:193

◆ is_timed_out()

static int is_timed_out ( struct hash_test const *  data)
static

Definition at line 64 of file test_hashtab_thrash.c.

References ast_test_status_update, ast_tvdiff_us(), ast_tvnow(), hash_test::deadline, and hash_test::test.

Referenced by hash_test_count(), hash_test_grow(), hash_test_lookup(), and hash_test_shrink().

64  {
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 }
Definition: ast_expr2.c:325
struct timeval ast_tvnow(void)
Returns current timeval. Meant to replace calls to gettimeofday().
Definition: time.h:150
#define ast_test_status_update(a, b, c...)
Definition: test.h:129
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

◆ load_module()

static int load_module ( void  )
static

Definition at line 327 of file test_hashtab_thrash.c.

References AST_MODULE_LOAD_SUCCESS, and AST_TEST_REGISTER.

328 {
331 }
#define AST_TEST_REGISTER(cb)
Definition: test.h:127

◆ unload_module()

static int unload_module ( void  )
static

Definition at line 321 of file test_hashtab_thrash.c.

References AST_TEST_UNREGISTER.

322 {
324  return 0;
325 }
#define AST_TEST_UNREGISTER(cb)
Definition: test.h:128

Variable Documentation

◆ __mod_info

struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Hash test" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
static

Definition at line 333 of file test_hashtab_thrash.c.

◆ ast_module_info

const struct ast_module_info* ast_module_info = &__mod_info
static

Definition at line 333 of file test_hashtab_thrash.c.