Index: kernel/test/synch/workq-test-core.h
===================================================================
--- kernel/test/synch/workq-test-core.h	(revision 8a64e81e7083acc3dc69cd56c21cca72dd37ca13)
+++ kernel/test/synch/workq-test-core.h	(revision 8a64e81e7083acc3dc69cd56c21cca72dd37ca13)
@@ -0,0 +1,195 @@
+/*
+ * Copyright (c) 2012 Adam Hraska
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <test.h>
+#include <arch.h>
+#include <atomic.h>
+#include <print.h>
+#include <proc/thread.h>
+#include <memstr.h>
+#include <synch/workqueue.h>
+
+
+typedef struct test_work {
+	work_t work_item;
+	int master;
+	int wave;
+	int count_down;
+} test_work_t;
+
+static atomic_t call_cnt[WAVES];
+
+
+/* Fwd decl - implement in your actual test file.. */
+static int core_workq_enqueue(work_t *work_item, work_func_t func);
+
+
+static bool new_wave(test_work_t *work)
+{
+	++work->wave;
+	
+	if (work->wave < WAVES) {
+		work->count_down = COUNT;
+		return true;
+	} else {
+		return false;
+	}
+}
+
+
+static int is_pow2(int num)
+{
+	unsigned n = (unsigned)num;
+	return (n != 0) && 0 == (n & (n-1));
+}
+
+static test_work_t * create_child(test_work_t *work)
+{
+	test_work_t *child = malloc(sizeof(test_work_t), 0);
+	ASSERT(child);
+	if (child) {
+		child->master = false;
+		child->wave = work->wave;
+		child->count_down = work->count_down;
+	}
+	
+	return child;
+}
+
+static void reproduce(work_t *work_item)
+{
+	/* Ensure work_item is ours for the taking. */
+	memsetb(work_item, sizeof(work_t), 0xec);
+	
+	test_work_t *work = (test_work_t *)work_item;
+	
+	atomic_inc(&call_cnt[work->wave]);
+	
+	if (0 < work->count_down) {
+		/* Sleep right before creating the last generation. */
+		if (1 == work->count_down) {
+			bool sleeping_wave = ((work->wave % 2) == 1);
+
+			/* Master never sleeps. */
+			if (sleeping_wave && !work->master) {
+				thread_usleep(WAVE_SLEEP_MS * 1000);
+			}
+		}
+		
+		--work->count_down;
+
+		/* 
+		 * Enqueue a child if count_down is power-of-2. 
+		 * Leads to exponential growth. 
+		 */
+		if (is_pow2(work->count_down + 1)) {
+			test_work_t *child = create_child(work);
+			if (child) {
+				if (!core_workq_enqueue(&child->work_item, reproduce))
+					free(child);
+			}
+		}
+		
+		if (!core_workq_enqueue(work_item, reproduce)) {
+			if (!work->master) {
+				free(work);
+			}
+		}
+	} else {
+		/* We're done with this wave - only the master survives. */
+		
+		if (work->master && new_wave(work)) {
+				core_workq_enqueue(work_item, reproduce);
+		} else {
+			if (work->master)
+				TPRINTF("\nMaster work item done!\n");
+				
+			memsetb(work, sizeof(test_work_t), 0xfa);
+			free(work);
+		}
+	}
+}
+
+static const char *run_workq_core(bool end_prematurely)
+{
+	for (int i = 0; i < WAVES; ++i) {
+		atomic_set(&call_cnt[i], 0);
+	}
+
+	test_work_t *work = malloc(sizeof(test_work_t), 0);
+
+	work->master = true;
+	work->wave = 0;
+	work->count_down = COUNT;
+	
+	/*
+	 * k == COUNT_POW
+	 * 2^k == COUNT + 1
+	 * 
+	 * We have "k" branching points. Therefore:
+	 * exp_call_cnt == k*2^(k-1) + 2^k == (k + 2) * 2^(k-1)
+	 */
+	size_t exp_call_cnt = (COUNT_POW + 2) * (1 << (COUNT_POW - 1));
+	
+	TPRINTF("waves: %d, count_down: %d, total expected calls: %zu\n", 
+		WAVES, COUNT, exp_call_cnt * WAVES);
+	
+
+	core_workq_enqueue(&work->work_item, reproduce);
+	
+	size_t sleep_cnt = 0;
+	/* At least 40 seconds total (or 2 sec to end while there's work). */
+	size_t max_sleep_secs = end_prematurely ? 2 : MAIN_MAX_SLEEP_SEC;
+	size_t max_sleep_cnt = (max_sleep_secs * 1000) / MAIN_POLL_SLEEP_MS;
+	
+	for (int i = 0; i < WAVES; ++i) {
+		while (atomic_get(&call_cnt[i]) < exp_call_cnt 
+			&& sleep_cnt < max_sleep_cnt) {
+			TPRINTF(".");
+			thread_usleep(MAIN_POLL_SLEEP_MS * 1000);
+			++sleep_cnt;
+		}
+	}
+	
+	bool success = true;
+	
+	for (int i = 0; i < WAVES; ++i) {
+		if (atomic_get(&call_cnt[i]) != exp_call_cnt) {
+			success = false;
+			TPRINTF("Error: %u calls in wave %d, but %zu expected.\n",
+				atomic_get(&call_cnt[i]), i, exp_call_cnt);
+		}
+	}
+	
+	
+	if (success)
+		return NULL;
+	else {
+		return "Failed to invoke the expected number of calls.";
+	}
+}
