Migrate hashtest/hashtest2 to be unit tests.

Both hashtest and hashtest2 are manual testing apps that thrash hash
tables (hashtab and ao2 containers, respectively), by spinning up
several threads that randomly insert, delete, lookup and iterate over
the hash table. If the app doesn't crash, the hash table probably passes
the test. Those utils are not a part of the typical Asterisk build, so
they do not usually get compiled. This all makes them less that useful.

This patch removes those manual test programs and replaces them with
Asterisk unit test modules (test_{hashtab,astobj2}_thrash.so). It also
attempts to make the tests more deterministic.

* Rather than spinning up some number of threads that operate on the
  hash table randomly, spin up four threads that concurrenly add,
  remove, lookup and iterate over the hash table.
* Each thread checks the state of the hash table both during and after
  execution, and indicates a test failure if things are not as expected.
* Each thread times out after 60 seconds to prevent deadlocking the unit
  test run.

(closes issue ASTERISK-20505)
Reported by: Matt Jordan
Review: https://reviewboard.asterisk.org/r/2189/
........

Merged revisions 376306 from http://svn.asterisk.org/svn/asterisk/branches/1.8
........

Merged revisions 376315 from http://svn.asterisk.org/svn/asterisk/branches/10
........

Merged revisions 376339 from http://svn.asterisk.org/svn/asterisk/branches/11


git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@376341 65c4cc65-6c06-0410-ace0-fbb531ad65f3

1 files changed, 321 insertions, 0 deletions

diff --git a/tests/test_hashtab_thrash.c b/tests/test_hashtab_thrash.c
new file mode 100644
index 000000000..373922bf8
--- /dev/null
+++ b/tests/test_hashtab_thrash.c
@@ -0,0 +1,321 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2012, David M. Lee, II
+ *
+ * David M. Lee, II <dlee@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+
+/*
+ *! \file \brief Thrash a hash table, for fun and profit.
+ *
+ * \author\verbatim David M. Lee, II <dlee@digium.com> \endverbatim
+ *
+ * Inspired by the original hashtest.c by Steve Murphy <murf@digium.com>.  This test runs
+ * several threads manipulatings a concurrent hastab to see if they maintain
+ * consistency. While the tests attempt to check consistency and error normally, threading
+ * errors often result in segfaults.
+ * \ingroup tests
+ */
+
+/*** MODULEINFO
+	<depend>TEST_FRAMEWORK</depend>
+	<support_level>core</support_level>
+ ***/
+
+#include "asterisk.h"
+
+ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
+#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"
+
+#define MAX_HASH_ENTRIES 30000
+#define MAX_TEST_SECONDS 60
+
+struct hash_test {
+	/*! Unit under test */
+	struct ast_hashtab *to_be_thrashed;
+	/*! Number of entries to insert in the grow thread. */
+	int max_grow;
+	/*! Number of enteries added by the grow thread. */
+	int grow_count;
+	/*! Entries preloaded into the hashtab; to be deleted by the shrink thread */
+	int preload;
+	/*! When to give up on the tests */
+	struct timeval deadline;
+};
+
+static int is_timed_out(struct hash_test const *data) {
+	return ast_tvdiff_us(data->deadline, ast_tvnow()) < 0;
+}
+
+/*! /brief Create test element */
+static char *ht_new(int i)
+{
+	const int buflen = 12;
+	char *keybuf = ast_malloc(buflen);
+	int needed;
+	if (keybuf == NULL) {
+		return NULL;
+	}
+	needed = snprintf(keybuf, buflen, "key%08x", i);
+	ast_assert(needed + 1 <= buflen);
+	return keybuf;
+}
+
+/*! /brief Free test element */
+static void ht_delete(void *obj)
+{
+	ast_free(obj);
+}
+
+/*! /brief Grow the hash data as specified */
+static void *hash_test_grow(void *d)
+{
+	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;
+}
+
+/*! Randomly lookup data in the hash */
+static void *hash_test_lookup(void *d)
+{
+	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;
+}
+
+/*! Delete entries from the hash */
+static void *hash_test_shrink(void *d)
+{
+	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;
+}
+
+/*! Continuously iterate through all the entries in the hash */
+static void *hash_test_count(void *d)
+{
+	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) {
+			/* Allow other threads to run. */
+			sched_yield();
+		} 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;
+}
+
+AST_TEST_DEFINE(hash_test)
+{
+	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.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;
+}
+
+static int unload_module(void)
+{
+	AST_TEST_UNREGISTER(hash_test);
+	return 0;
+}
+
+static int load_module(void)
+{
+	AST_TEST_REGISTER(hash_test);
+	return AST_MODULE_LOAD_SUCCESS;
+}
+
+AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Hash test");