tests/test_hashtab_thrash.c

   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 hash table, for fun and profit.
  21  *
  22  * \author\verbatim David M. Lee, II <dlee@digium.com> \endverbatim
  23  *
  24  * Inspired by the original hashtest.c by Steve Murphy <murf@digium.com>.  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 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
  39 #include <pthread.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 30000
  48 #define MAX_TEST_SECONDS 60
  49
  50 struct hash_test {
  51         /*! Unit under test */
  52         struct ast_hashtab *to_be_thrashed;
  53         /*! Number of entries to insert in the grow thread. */
  54         int max_grow;
  55         /*! Number of enteries added by the grow thread. */
  56         int grow_count;
  57         /*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
  58         int preload;
  59         /*! When to give up on the tests */
  60         struct timeval deadline;
  61         /*! The actual test object */
  62         struct ast_test *test;
  63 };
  64
  65 static int is_timed_out(struct hash_test const *data) {
  66         struct timeval now = ast_tvnow();
  67         int val = ast_tvdiff_us(data->deadline, now) < 0;
  68         if (val) {
  69                 /* tv_usec is suseconds_t, which could be int or long */
  70                 ast_test_status_update(data->test, "Now: %ld.%06ld Deadline: %ld.%06ld\n",
  71                         now.tv_sec, (long)now.tv_usec,
  72                         data->deadline.tv_sec, (long)data->deadline.tv_usec);
  73         }
  74         return val;
  75 }
  76
  77 /*! /brief Create test element */
  78 static char *ht_new(int i)
  79 {
  80         const int buflen = 12;
  81         char *keybuf = ast_malloc(buflen);
  82         int needed;
  83         if (keybuf == NULL) {
  84                 return NULL;
  85         }
  86         needed = snprintf(keybuf, buflen, "key%08x", i);
  87         ast_assert(needed + 1 <= buflen);
  88         return keybuf;
  89 }
  90
  91 /*! /brief Free test element */
  92 static void ht_delete(void *obj)
  93 {
  94         ast_free(obj);
  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 *obj;
 105                 if (is_timed_out(data)) {
 106                         return "Growth timed out";
 107                 }
 108                 obj = ht_new(i);
 109                 if (obj == NULL) {
 110                         return "Allocation failed";
 111                 }
 112                 ast_hashtab_insert_immediate(data->to_be_thrashed, obj);
 113                 ast_atomic_fetchadd_int(&data->grow_count, 1);
 114         }
 115         return NULL;
 116 }
 117
 118 /*! Randomly lookup data in the hash */
 119 static void *hash_test_lookup(void *d)
 120 {
 121         struct hash_test *data = d;
 122         int max;
 123         unsigned seed = time(NULL);
 124
 125         /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
 126          * optimize away reads.
 127          */
 128         while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
 129                 int i;
 130                 char *obj;
 131                 int is_in_hashtab;
 132
 133                 if (is_timed_out(data)) {
 134                         return "Lookup timed out";
 135                 }
 136
 137                 if (max == 0) {
 138                         /* No data yet; yield and try again */
 139                         sched_yield();
 140                         continue;
 141                 }
 142
 143                 /* Randomly lookup one object from the hash */
 144                 i = rand_r(&seed) % max;
 145                 obj = ht_new(i);
 146                 if (obj == NULL) {
 147                         return "Allocation failed.";
 148                 }
 149                 is_in_hashtab = (ast_hashtab_lookup(data->to_be_thrashed, obj) != NULL);
 150                 ht_delete(obj);
 151                 if (!is_in_hashtab) {
 152                         return "key unexpectedly missing";
 153                 }
 154         }
 155
 156         return NULL;
 157 }
 158
 159 /*! Delete entries from the hash */
 160 static void *hash_test_shrink(void *d)
 161 {
 162         const struct hash_test *data = d;
 163         int i;
 164
 165         for (i = 1; i < data->preload; ++i) {
 166                 char *obj = ht_new(-i);
 167                 char *from_hashtab;
 168                 int deleted;
 169
 170                 if (obj == NULL) {
 171                         return "Allocation failed";
 172                 }
 173                 from_hashtab = ast_hashtab_remove_object_via_lookup(data->to_be_thrashed, obj);
 174                 deleted = from_hashtab != NULL;
 175
 176                 ht_delete(obj);
 177                 ht_delete(from_hashtab);
 178                 if (!deleted) {
 179                         return "could not delete object";
 180                 }
 181                 if (is_timed_out(data)) {
 182                         return "Shrink timed out";
 183                 }
 184         }
 185         return NULL;
 186 }
 187
 188 /*! Continuously iterate through all the entries in the hash */
 189 static void *hash_test_count(void *d)
 190 {
 191         const struct hash_test *data = d;
 192         int count = 0;
 193         int last_count = 0;
 194
 195         while (count < data->max_grow) {
 196                 struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(data->to_be_thrashed);
 197                 char *ht = ast_hashtab_next(it);
 198                 last_count = count;
 199                 count = 0;
 200                 while (ht) {
 201                         /* only count keys added by grow thread */
 202                         if (strncmp(ht, "key0", 4) == 0) {
 203                                 ++count;
 204                         }
 205                         ht = ast_hashtab_next(it);
 206                 }
 207                 ast_hashtab_end_traversal(it);
 208
 209                 if (last_count == count) {
 210                         /* Allow other threads to run. */
 211                         sched_yield();
 212                 } else if (last_count > count) {
 213                         /* Make sure the hashtable never shrinks */
 214                         return "hashtab unexpectedly shrank";
 215                 }
 216
 217                 if (is_timed_out(data)) {
 218                         return "Count timed out";
 219                 }
 220         }
 221
 222         /* Successfully iterated over all of the expected elements */
 223         return NULL;
 224 }
 225
 226 AST_TEST_DEFINE(hash_test)
 227 {
 228         enum ast_test_result_state res = AST_TEST_PASS;
 229         struct hash_test data = {};
 230         pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
 231         void *thread_results;
 232         int i;
 233
 234         switch (cmd) {
 235         case TEST_INIT:
 236                 info->name = "thrash";
 237                 info->category = "/main/hashtab/";
 238                 info->summary = "Testing hashtab concurrency";
 239                 info->description = "Test hashtab concurrency correctness.";
 240                 return AST_TEST_NOT_RUN;
 241         case TEST_EXECUTE:
 242                 break;
 243         }
 244
 245         ast_test_status_update(test, "Executing hash concurrency test...\n");
 246         data.test = test;
 247         data.preload = MAX_HASH_ENTRIES / 2;
 248         data.max_grow = MAX_HASH_ENTRIES - data.preload;
 249         data.deadline = ast_tvadd(ast_tvnow(), ast_tv(MAX_TEST_SECONDS, 0));
 250         data.to_be_thrashed = ast_hashtab_create(MAX_HASH_ENTRIES / 100,
 251                 ast_hashtab_compare_strings_nocase, ast_hashtab_resize_java,
 252                 ast_hashtab_newsize_java, ast_hashtab_hash_string_nocase, 1);
 253
 254         if (data.to_be_thrashed == NULL) {
 255                 ast_test_status_update(test, "Allocation failed\n");
 256                 /* Nothing needs to be freed; early return is fine */
 257                 return AST_TEST_FAIL;
 258         }
 259
 260
 261         /* preload with data to delete */
 262         for (i = 1; i < data.preload; ++i) {
 263                 char *obj = ht_new(-i);
 264                 if (obj == NULL) {
 265                         ast_test_status_update(test, "Allocation failed\n");
 266                         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
 267                         return AST_TEST_FAIL;
 268                 }
 269                 ast_hashtab_insert_immediate(data.to_be_thrashed, obj);
 270         }
 271
 272         /* add data.max_grow entries to the hashtab */
 273         ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
 274         /* continually count the keys added by the grow thread */
 275         ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
 276         /* continually lookup keys added by the grow thread */
 277         ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
 278         /* delete all keys preloaded into the hashtab */
 279         ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);
 280
 281         pthread_join(grow_thread, &thread_results);
 282         if (thread_results != NULL) {
 283                 ast_test_status_update(test, "Growth thread failed: %s\n",
 284                         (char *)thread_results);
 285                 res = AST_TEST_FAIL;
 286         }
 287
 288         pthread_join(count_thread, &thread_results);
 289         if (thread_results != NULL) {
 290                 ast_test_status_update(test, "Count thread failed: %s\n",
 291                         (char *)thread_results);
 292                 res = AST_TEST_FAIL;
 293         }
 294
 295         pthread_join(lookup_thread, &thread_results);
 296         if (thread_results != NULL) {
 297                 ast_test_status_update(test, "Lookup thread failed: %s\n",
 298                         (char *)thread_results);
 299                 res = AST_TEST_FAIL;
 300         }
 301
 302         pthread_join(shrink_thread, &thread_results);
 303         if (thread_results != NULL) {
 304                 ast_test_status_update(test, "Shrink thread failed: %s\n",
 305                         (char *)thread_results);
 306                 res = AST_TEST_FAIL;
 307         }
 308
 309         if (ast_hashtab_size(data.to_be_thrashed) != data.max_grow) {
 310                 ast_test_status_update(test,
 311                         "Invalid hashtab size. Expected: %d, Actual: %d\n",
 312                         data.max_grow, ast_hashtab_size(data.to_be_thrashed));
 313                 res = AST_TEST_FAIL;
 314         }
 315
 316         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
 317         return res;
 318 }
 319
 320 static int unload_module(void)
 321 {
 322         AST_TEST_UNREGISTER(hash_test);
 323         return 0;
 324 }
 325
 326 static int load_module(void)
 327 {
 328         AST_TEST_REGISTER(hash_test);
 329         return AST_MODULE_LOAD_SUCCESS;
 330 }
 331
 332 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Hash test");