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_module *	AST_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_info *	ast_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.

{
   enum ast_test_result_state res = AST_TEST_PASS;
   struct hash_test data = {};
   pthread_t grow_thread, count_thread, lookup_thread, shrink_thread;
   void *thread_results;
   int i;

   switch (cmd) {
   case TEST_INIT:
      info->name = "thrash";
      info->category = "/main/hashtab/";
      info->summary = "Testing hashtab concurrency";
      info->description = "Test hashtab concurrency correctness.";
      return AST_TEST_NOT_RUN;
   case TEST_EXECUTE:
      break;
   }

   ast_test_status_update(test, "Executing hash concurrency test...\n");
   data.test = test;
   data.preload = MAX_HASH_ENTRIES / 2;
   data.max_grow = MAX_HASH_ENTRIES - data.preload;
   data.deadline = ast_tvadd(ast_tvnow(), ast_tv(MAX_TEST_SECONDS, 0));
   data.to_be_thrashed = ast_hashtab_create(MAX_HASH_ENTRIES / 100,
      ast_hashtab_compare_strings_nocase, ast_hashtab_resize_java,
      ast_hashtab_newsize_java, ast_hashtab_hash_string_nocase, 1);

   if (data.to_be_thrashed == NULL) {
      ast_test_status_update(test, "Allocation failed\n");
      /* Nothing needs to be freed; early return is fine */
      return AST_TEST_FAIL;
   }


   /* preload with data to delete */
   for (i = 1; i < data.preload; ++i) {
      char *obj = ht_new(-i);
      if (obj == NULL) {
         ast_test_status_update(test, "Allocation failed\n");
         ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
         return AST_TEST_FAIL;
      }
      ast_hashtab_insert_immediate(data.to_be_thrashed, obj);
   }

   /* add data.max_grow entries to the hashtab */
   ast_pthread_create(&grow_thread, NULL, hash_test_grow, &data);
   /* continually count the keys added by the grow thread */
   ast_pthread_create(&count_thread, NULL, hash_test_count, &data);
   /* continually lookup keys added by the grow thread */
   ast_pthread_create(&lookup_thread, NULL, hash_test_lookup, &data);
   /* delete all keys preloaded into the hashtab */
   ast_pthread_create(&shrink_thread, NULL, hash_test_shrink, &data);

   pthread_join(grow_thread, &thread_results);
   if (thread_results != NULL) {
      ast_test_status_update(test, "Growth thread failed: %s\n",
         (char *)thread_results);
      res = AST_TEST_FAIL;
   }

   pthread_join(count_thread, &thread_results);
   if (thread_results != NULL) {
      ast_test_status_update(test, "Count thread failed: %s\n",
         (char *)thread_results);
      res = AST_TEST_FAIL;
   }

   pthread_join(lookup_thread, &thread_results);
   if (thread_results != NULL) {
      ast_test_status_update(test, "Lookup thread failed: %s\n",
         (char *)thread_results);
      res = AST_TEST_FAIL;
   }

   pthread_join(shrink_thread, &thread_results);
   if (thread_results != NULL) {
      ast_test_status_update(test, "Shrink thread failed: %s\n",
         (char *)thread_results);
      res = AST_TEST_FAIL;
   }

   if (ast_hashtab_size(data.to_be_thrashed) != data.max_grow) {
      ast_test_status_update(test,
         "Invalid hashtab size. Expected: %d, Actual: %d\n",
         data.max_grow, ast_hashtab_size(data.to_be_thrashed));
      res = AST_TEST_FAIL;
   }

   ast_hashtab_destroy(data.to_be_thrashed, ht_delete);
   return res;
}

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().

{
   const struct hash_test *data = d;
   int count = 0;
   int last_count = 0;

   while (count < data->max_grow) {
      struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(data->to_be_thrashed);
      char *ht = ast_hashtab_next(it);
      last_count = count;
      count = 0;
      while (ht) {
         /* only count keys added by grow thread */
         if (strncmp(ht, "key0", 4) == 0) {
            ++count;
         }
         ht = ast_hashtab_next(it);
      }
      ast_hashtab_end_traversal(it);

      if (last_count == count) {
         /* Give other threads ample chance to run, note that using sched_yield here does not
          * provide enough of a chance and can cause this thread to starve others.
          */
         usleep(1);
      } else if (last_count > count) {
         /* Make sure the hashtable never shrinks */
         return "hashtab unexpectedly shrank";
      }

      if (is_timed_out(data)) {
         return "Count timed out";
      }
   }

   /* Successfully iterated over all of the expected elements */
   return NULL;
}

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().

{
   struct hash_test *data = d;
   int i;

   for (i = 0; i < data->max_grow; ++i) {
      char *obj;
      if (is_timed_out(data)) {
         return "Growth timed out";
      }
      obj = ht_new(i);
      if (obj == NULL) {
         return "Allocation failed";
      }
      ast_hashtab_insert_immediate(data->to_be_thrashed, obj);
      ast_atomic_fetchadd_int(&data->grow_count, 1);
   }
   return NULL;
}

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().

{
   struct hash_test *data = d;
   int max;
   unsigned seed = time(NULL);

   /* ast_atomic_fetchadd_int provide a memory fence so that the optimizer doesn't
    * optimize away reads.
    */
   while ((max = ast_atomic_fetchadd_int(&data->grow_count, 0)) < data->max_grow) {
      int i;
      char *obj;
      int is_in_hashtab;

      if (is_timed_out(data)) {
         return "Lookup timed out";
      }

      if (max == 0) {
         /* No data yet; yield and try again */
         sched_yield();
         continue;
      }

      /* Randomly lookup one object from the hash */
      i = rand_r(&seed) % max;
      obj = ht_new(i);
      if (obj == NULL) {
         return "Allocation failed.";
      }
      is_in_hashtab = (ast_hashtab_lookup(data->to_be_thrashed, obj) != NULL);
      ht_delete(obj);
      if (!is_in_hashtab) {
         return "key unexpectedly missing";
      }
   }

   return NULL;
}

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().

{
   const struct hash_test *data = d;
   int i;

   for (i = 1; i < data->preload; ++i) {
      char *obj = ht_new(-i);
      char *from_hashtab;
      int deleted;

      if (obj == NULL) {
         return "Allocation failed";
      }
      from_hashtab = ast_hashtab_remove_object_via_lookup(data->to_be_thrashed, obj);
      deleted = from_hashtab != NULL;

      ht_delete(obj);
      ht_delete(from_hashtab);
      if (!deleted) {
         return "could not delete object";
      }
      if (is_timed_out(data)) {
         return "Shrink timed out";
      }
   }
   return NULL;
}

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().

{
   ast_free(obj);
}

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().

{
   const int buflen = 12;
   char *keybuf = ast_malloc(buflen);
   int needed;
   if (keybuf == NULL) {
      return NULL;
   }
   needed = snprintf(keybuf, buflen, "key%08x", (unsigned)i);
   ast_assert(needed + 1 <= buflen);
   return keybuf;
}

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().

                                                      {
   struct timeval now = ast_tvnow();
   int val = ast_tvdiff_us(data->deadline, now) < 0;
   if (val) {
      /* tv_usec is suseconds_t, which could be int or long */
      ast_test_status_update(data->test, "Now: %ld.%06ld Deadline: %ld.%06ld\n",
         now.tv_sec, (long)now.tv_usec,
         data->deadline.tv_sec, (long)data->deadline.tv_usec);
   }
   return val;
}

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.

{
   AST_TEST_REGISTER(hash_test);
   return AST_MODULE_LOAD_SUCCESS;
}

unload_module()

static int unload_module ( void  )

static

Definition at line 321 of file test_hashtab_thrash.c.

References AST_TEST_UNREGISTER.

{
   AST_TEST_UNREGISTER(hash_test);
   return 0;
}

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.