test_astobj2_thrash.c 8.9 KB

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