server: Overengineered hashtable property test

1 files changed, 332 insertions, 2 deletions

diff --git a/test/hashtable.c b/test/hashtable.c
index cfb2d9d..ea6217c 100644
--- a/test/hashtable.c
+++ b/test/hashtable.c
@@ -1,8 +1,338 @@
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
 #include "test_framework.h"
+#include "../global.h"
+#include "../hashtable.h"
 
 
+static const int NUM_RUNS = 1000;
+static const int NUM_OPERATIONS_PER_RUN = 100000;
+
+
+struct pair {
+	u64 key;
+	void *value;
+};
+
+struct mock {
+	struct pair *pairs;
+	size_t cap, len;
+};
+
+static struct mock* m_alloc(void) {
+	struct mock *ht = malloc(1, struct mock);
+	ht->cap = 16;
+	ht->len = 0;
+	ht->pairs = malloc(ht->cap, struct pair);
+	return ht;
+}
+
+static void m_free(struct mock *ht) {
+	free(ht->pairs);
+	free(ht);
+}
+
+// Returns NULL if key is not present in the table.
+static void* m_find(const struct mock *ht, u64 key) {
+	for (size_t i = 0; i < ht->len; i++) {
+		if (ht->pairs[i].key == key) return ht->pairs[i].value;
+	}
+	return NULL;
+}
+
+static void m_insert(struct mock *ht, u64 key, void *value) {
+	assert(value != NULL);
+	for (size_t i = 0; i < ht->len; i++) {
+		if (ht->pairs[i].key == key) {
+			ht->pairs[i].value = value;
+			return;
+		}
+	}
+
+	if (ht->len == ht->cap) {
+		ht->cap *= 2;
+		ht->pairs = realloc(ht->pairs, ht->cap, struct pair);
+	}
+	ht->pairs[ht->len++] = (struct pair){key, value};
+}
+
+// Does nothing if the key is not present in the table.
+static void m_delete(struct mock *ht, u64 key) {
+	for (size_t i = 0; i < ht->len; i++) {
+		if (ht->pairs[i].key == key) {
+			if (i < ht->len - 1) ht->pairs[i] = ht->pairs[ht->len - 1];
+			ht->len--;
+			break;
+		}
+	}
+}
+
+
+static u64 gen_key(void) {
+	return random();
+}
+
+static u64 gen_existing_key(const struct mock *m) {
+	const size_t index = random() % m->len;
+	return m->pairs[index].key;
+}
+
+static u64 gen_nonexistent_key(const struct mock *m) {
+	u64 key;
+	do key = gen_key(); while (m_find(m, key) != NULL);
+	return key;
+}
+
+static void* gen_value(void) {
+	// Ensure that the key is not NULL
+	return (void*)random() + 8;
+}
+
+struct operation {
+	int type;
+	u64 key;
+	void *value;
+};
+
+struct oplog {
+	struct operation *log;
+	size_t num;
+};
+
+
+static int perform_operation(
+		struct hashtable *ht, struct mock *m, const struct operation *oper) {
+
+	switch (oper->type) {
+		case 0:  // insert key
+			ht_insert(ht, oper->key, oper->value);
+			m_insert(m, oper->key, oper->value);
+			break;
+
+		case 1:  // find existing key
+		case 2: // find nonexistent key
+			if (ht_find(ht, oper->key) != m_find(m, oper->key)) return 1;
+			break;
+
+		case 3:  // delete existing key
+		case 4:  // delete nonexistent key
+			ht_delete(ht, oper->key);
+			m_delete(m, oper->key);
+			break;
+	}
+
+	return 0;
+}
+
+static int gen_perform_operations(
+		struct hashtable *ht, struct mock *m, struct oplog *oplog) {
+
+	for (size_t i = 0; i < NUM_OPERATIONS_PER_RUN; i++) {
+		const int op = (random() % 6) % 5;  // not uniform but I don't care
+		oplog->num = i + 1;
+		oplog->log[i].type = op;
+
+		switch (op) {
+			case 0: {  // insert key
+				const u64 key = oplog->log[i].key = gen_key();
+				void *const value = oplog->log[i].value = gen_value();
+				ht_insert(ht, key, value);
+				m_insert(m, key, value);
+				break;
+			}
+
+			case 1: {  // find existing key
+				if (m->len == 0) { i--; continue; }
+				const u64 key = oplog->log[i].key = gen_existing_key(m);
+				EXPECTRET(1, ht_find(ht, key) == m_find(m, key));
+				break;
+			}
+
+			case 2: {  // find nonexistent key
+				const u64 key = oplog->log[i].key = gen_nonexistent_key(m);
+				EXPECTRET(1, ht_find(ht, key) == NULL);
+				break;
+			}
+
+			case 3: {  // delete existing key
+				if (m->len == 0) { i--; continue; }
+				const u64 key = oplog->log[i].key = gen_existing_key(m);
+				ht_delete(ht, key);
+				m_delete(m, key);
+				break;
+			}
+
+			case 4: {  // delete nonexistent key
+				const u64 key = oplog->log[i].key = gen_nonexistent_key(m);
+				ht_delete(ht, key);
+				break;
+			}
+		}
+	}
+
+	return 0;
+}
+
+static void print_oplog(const struct oplog *oplog, bool verbose) {
+	printf("Note: hashtable oplog: ");
+	for (size_t i = 0; i < oplog->num; i++) {
+		putchar("IFfDd"[oplog->log[i].type]);
+		if (verbose) {
+			printf("(%" PRIi64 ")", oplog->log[i].key);
+		}
+	}
+	putchar('\n');
+}
+
+static int rerun_log(const struct oplog *oplog) {
+	struct hashtable *const ht = ht_alloc();
+	struct mock *const m = m_alloc();
+	int ret;
+	for (size_t i = 0; i < oplog->num; i++) {
+		ret = perform_operation(ht, m, &oplog->log[i]);
+		if (ret != 0) break;
+	}
+	ht_free(ht);
+	m_free(m);
+	return ret;
+}
+
+static void swap_oplog(struct oplog *oplog1, struct oplog *oplog2) {
+	const struct oplog tmp = *oplog1;
+	*oplog1 = *oplog2;
+	*oplog2 = tmp;
+}
+
+static void minimise_log(struct oplog *oplog) {
+	if (rerun_log(oplog) == 0) return;
+
+	printf("Note: minimising oplog, this may take a while\n");
+
+	struct oplog oplog2;
+	oplog2.num = oplog->num;
+	oplog2.log = malloc(NUM_OPERATIONS_PER_RUN, struct operation);
+	memcpy(oplog2.log, oplog->log, oplog->num * sizeof(struct operation));
+
+	// Replace delete_nonexistent with find_nonexistent
+	for (size_t i = 0; i < oplog2.num; i++) {
+		if (oplog2.log[i].type == 4) oplog2.log[i].type = 2;
+	}
+	if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+	swap_oplog(oplog, &oplog2);
+	oplog2.num = 0;
+
+	// Remove find_nonexistent
+	for (size_t i = 0; i < oplog->num; i++) {
+		if (oplog->log[i].type != 2) oplog2.log[oplog2.num++] = oplog->log[i];
+	}
+	if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+	swap_oplog(oplog, &oplog2);
+	oplog2.num = 0;
+
+	// Remove inconsequential insert/delete pairs
+	size_t *indexbuf = malloc(NUM_OPERATIONS_PER_RUN, size_t);
+	for (size_t inserti = 0; inserti < oplog->num; inserti++) {
+		if (oplog->log[inserti].type != 0) continue;
+		const u64 key = oplog->log[inserti].key;
+
+		indexbuf[0] = inserti;
+		size_t indexbuflen = 1;
+
+		size_t deletei;
+		for (deletei = inserti + 1; deletei < oplog->num; deletei++) {
+			if (oplog->log[deletei].type == 1 && oplog->log[deletei].key == key) {
+				indexbuf[indexbuflen++] = deletei;
+			}
+			if (oplog->log[deletei].type == 3 && oplog->log[deletei].key == key) {
+				break;
+			}
+		}
+		if (deletei < oplog->num) {
+			indexbuf[indexbuflen++] = deletei;
+		}
+
+		// Copy operations without those in indexbuf
+		for (size_t i = 0, ii = 0; i < oplog->num; i++) {
+			if (ii < indexbuflen && i == indexbuf[ii]) { ii++; continue; }
+			oplog2.log[oplog2.num++] = oplog->log[i];
+		}
+
+		// If we still error, commit removals
+		if (rerun_log(&oplog2) != 0) {
+			swap_oplog(oplog, &oplog2);
+			inserti--;  // we removed the insert, so move one back
+		}
+
+		oplog2.num = 0;
+	}
+	free(indexbuf);
+
+	// Remove non-final finds
+	size_t final_find_idx = 0;
+	for (size_t i = oplog->num - 1; i > 0; i--) {
+		if (oplog->log[i].type == 1) {
+			final_find_idx = i;
+			break;
+		}
+	}
+	for (size_t i = 0; i < oplog->num; i++) {
+		if (oplog->log[i].type == 1 && i < final_find_idx) continue;
+		oplog2.log[oplog2.num++] = oplog->log[i];
+	}
+	if (rerun_log(&oplog2) == 0) { free(oplog2.log); return; }
+	swap_oplog(oplog, &oplog2);
+	oplog2.num = 0;
+
+	// Make keys smaller; note, afterwards "existing" is not true anymore for D's and F's
+	for (size_t modulus = 2; modulus <= 100; modulus++) {
+		oplog2.num = oplog->num;
+		memcpy(oplog2.log, oplog->log, oplog->num * sizeof(struct operation));
+		for (size_t i = 0; i < oplog2.num; i++) {
+			oplog2.log[i].key %= modulus;
+		}
+		if (rerun_log(&oplog2) != 0) {
+			swap_oplog(oplog, &oplog2);
+			break;
+		}
+	}
+
+	free(oplog2.log);
+	return;
+}
+
 DEFINE_TEST(hashtable) {
-	EXPECT(1);
-	EXPECT(0);
+	int ret = 0;
+	struct oplog oplog;
+	oplog.log = malloc(NUM_OPERATIONS_PER_RUN, struct operation);
+	oplog.num = 0;
+
+	for (size_t i = 0; i < NUM_RUNS; i++) {
+		struct hashtable *const ht = ht_alloc();
+		struct mock *const m = m_alloc();
+
+		ret = gen_perform_operations(ht, m, &oplog);
+
+		ht_free(ht);
+		m_free(m);
+
+		if (ret != 0) {
+			print_oplog(&oplog, false);
+			minimise_log(&oplog);
+			print_oplog(&oplog, true);
+			break;
+		}
+	}
+
+	free(oplog.log);
+
+	return ret;
+}
+
+DEFINE_TEST(hashtable_unit1) {
+	struct hashtable *ht = ht_alloc();
+	ht_insert(ht, 0, (void*)123);
+	ht_insert(ht, 0, (void*)456);
+	EXPECT(ht_find(ht, 0) == (void*)456);
 	return 0;
 }