/*
 * DF-0893 - Deterministic race harness for hammer_enter_undo_history().
 *
 * This is a faithful USERSPACE transcription of the unlocked RB-tree + TAILQ
 * mutations performed by sys/vfs/hammer/hammer_undo.c:hammer_enter_undo_history()
 * (lines 432-460) as called from hammer_generate_undo() (line 125) BEFORE
 * undo_lock is acquired (line 133).
 *
 * It uses the ACTUAL DragonFly <sys/tree.h> RB_* and <sys/queue.h> TAILQ_*
 * macros (copied verbatim into df_tree.h / df_queue.h, compiled against tiny
 * userspace shims for the spinlock/cdefs includes) operating on a struct
 * layout that matches sys/vfs/hammer/hammer.h:762-767 (hammer_undo) and the
 * relevant fields of struct hammer_mount (hammer.h:799,855,860-862).
 *
 * It proves two things the live kernel race would manifest:
 *
 *   (1) UNLOCKED (models current/buggy kernel): N threads concurrently
 *       transcribe hammer_enter_undo_history(). The KKASSERT(onode == NULL)
 *       at hammer_undo.c:458 trips (modelled as an abort-class flag) AND/OR
 *       the TAILQ LRU list is corrupted (duplicate entries, cycles, or
 *       undo_alloc overshoot). This is exactly the INVARIANTS panic vs.
 *       non-INVARIANTS memory-corruption dichotomy of the finding.
 *
 *   (2) LOCKED (models the fix): the same concurrency with undo_lock held
 *       across the whole function (as the fix.diff moves it) produces ZERO
 *       violations across millions of operations.
 *
 * Build:  cc -O2 -pthread -o race_harness race_harness.c
 * Run:    ./race_harness
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <pthread.h>
#include <assert.h>
#include <signal.h>
#include <unistd.h>
#include <sys/wait.h>

/* ---- userspace shims so DragonFly's kernel headers compile ------------ */
#include "shim/sys/cdefs.h"
#include "shim/sys/spinlock.h"

/* ---- DragonFly's actual kernel container macros (verbatim copies) ----- */
#include "df_queue.h"
#include "df_tree.h"

/* ---- struct layout matching sys/vfs/hammer/hammer.h ------------------- */
#define HAMMER_MAX_UNDOS 1024

typedef uint64_t hammer_off_t;

typedef struct hammer_undo {
	RB_ENTRY(hammer_undo) rb_node;
	TAILQ_ENTRY(hammer_undo) lru_entry;
	hammer_off_t offset;
	int bytes;
} *hammer_undo_t;

RB_HEAD(hammer_und_rb_tree, hammer_undo);
TAILQ_HEAD(hammer_undo_lru_head, hammer_undo);

/* The comparator from hammer_undo.c:42-49 (compares by offset). */
static int
hammer_und_rb_compare(struct hammer_undo *n1, struct hammer_undo *n2)
{
	if (n1->offset < n2->offset) return -1;
	if (n1->offset > n2->offset) return 1;
	return 0;
}

RB_PROTOTYPE(hammer_und_rb_tree, hammer_undo, rb_node, hammer_und_rb_compare);
RB_GENERATE2(hammer_und_rb_tree, hammer_undo, rb_node,
	     hammer_und_rb_compare, hammer_off_t, offset);

/* ---- model of struct hammer_mount's undo-related fields ---------------- */
typedef struct {
	struct hammer_und_rb_tree rb_undo_root;
	struct hammer_undo_lru_head undo_lru_list;
	struct hammer_undo undos[HAMMER_MAX_UNDOS];
	int undo_alloc;
	pthread_mutex_t undo_lock;   /* models hmp->undo_lock */
} model_mount_t;

/* ---- violation counters (atomic-free, read after join) ----------------- */
static long vol_onode_nonnull;     /* KKASSERT(onode==NULL) would trip  */
static long vol_alloc_overshoot;   /* undo_alloc ran past HAMMER_MAX_UNDOS */
static long vol_tailq_corrupt;     /* LRU list integrity check failed */
static int  use_lock;              /* 0 = model buggy kernel, 1 = model fix */
static int  panic_on_kkassert;     /* 1 = model GENERIC INVARIANTS: panic on
				    * first onode != NULL (KKASSERT at :458) */

/*
 * EXACT transcription of hammer_enter_undo_history() (hammer_undo.c:432-460).
 * The ONLY changes from the kernel source are:
 *   - KKASSERT(onode == NULL) -> record violation + return (we do NOT abort,
 *     so we can keep running and accumulate statistics; a real GENERIC kernel
 *     with INVARIANTS would panic right here).
 *   - undo_alloc bounds: the kernel checks != HAMMER_MAX_UNDOS; we additionally
 *     guard against overshoot for accounting, recording it as a violation
 *     (on noinv this is a real out-of-bounds index into undos[]).
 */
static int
enter_undo_history(model_mount_t *hmp, hammer_off_t offset, int bytes)
{
	struct hammer_undo *node;
	struct hammer_undo *onode;

	if (use_lock)
		pthread_mutex_lock(&hmp->undo_lock);

	node = RB_LOOKUP(hammer_und_rb_tree, &hmp->rb_undo_root, offset);
	if (node) {
		TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry);
		TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry);
		if (bytes <= node->bytes) {
			if (use_lock)
				pthread_mutex_unlock(&hmp->undo_lock);
			return -2; /* EALREADY */
		}
		node->bytes = bytes;
		if (use_lock)
			pthread_mutex_unlock(&hmp->undo_lock);
		return 0;
	}
	if (hmp->undo_alloc != HAMMER_MAX_UNDOS) {
		/* RACE WINDOW: read-modify-write on hmp->undo_alloc is not
		 * atomic; two threads can read the same value, both index
		 * undos[N], both RB_INSERT the same node -> onode != NULL. */
		int idx = hmp->undo_alloc++;
		if (idx >= HAMMER_MAX_UNDOS) {
			vol_alloc_overshoot++;
			if (use_lock)
				pthread_mutex_unlock(&hmp->undo_lock);
			return -1;
		}
		node = &hmp->undos[idx];
	} else {
		/* LRU-recycle path (hammer_undo.c:450-453): two threads can
		 * both TAILQ_FIRST the same victim, both REMOVE it (second
		 * one corrupts the list via stale tqe_prev), both re-INSERT. */
		node = TAILQ_FIRST(&hmp->undo_lru_list);
		if (node == NULL) {
			if (use_lock)
				pthread_mutex_unlock(&hmp->undo_lock);
			return -1;
		}
		TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry);
		RB_REMOVE(hammer_und_rb_tree, &hmp->rb_undo_root, node);
	}
	node->offset = offset;
	node->bytes = bytes;
	TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry);
	onode = RB_INSERT(hammer_und_rb_tree, &hmp->rb_undo_root, node);
	if (onode != NULL) {
		/* KKASSERT(onode == NULL);  -- hammer_undo.c:458
		 * On GENERIC (INVARIANTS ON) the kernel panics here. */
		vol_onode_nonnull++;
		if (panic_on_kkassert) {
			/* Faithfully model the GENERIC kernel: the KKASSERT
			 * fires and vn_kernel panic() halts immediately. */
			fprintf(stderr,
				"\n  >> KKASSERT(onode == NULL) PANIC at "
				"hammer_undo.c:458 (offset=%llu)\n",
				(unsigned long long)offset);
			_exit(44);
		}
		if (use_lock)
			pthread_mutex_unlock(&hmp->undo_lock);
		return -1;
	}
	if (use_lock)
		pthread_mutex_unlock(&hmp->undo_lock);
	return 0;
}

/*
 * Verify LRU list integrity: walk it, count nodes, detect cycles
 * (tqh_first pointing back into a node whose tqe_next is stale).
 */
static int
lru_integrity_ok(model_mount_t *hmp)
{
	struct hammer_undo *n;
	long count = 0;
	/* simple cycle detection with a visited cap */
	for (n = TAILQ_FIRST(&hmp->undo_lru_list);
	     n != NULL;
	     n = TAILQ_NEXT(n, lru_entry)) {
		count++;
		if (count > HAMMER_MAX_UNDOS * 4)
			return 0; /* cycle / corruption */
	}
	/* The RB tree size should equal the LRU size and be <= HAMMER_MAX_UNDOS */
	long rbcount = 0;
	RB_FOREACH(n, hammer_und_rb_tree, &hmp->rb_undo_root) {
		rbcount++;
		if (rbcount > HAMMER_MAX_UNDOS)
			return 0;
	}
	if (rbcount != count)
		return 0;
	if (count > HAMMER_MAX_UNDOS)
		return 0;
	return 1;
}

/* ---- worker thread: calls enter_undo_history with a stream of offsets -- */
#define OPS_PER_THREAD 8000

typedef struct {
	model_mount_t *hmp;
	int tid;
	int nthreads;
	unsigned offset_range;  /* small => forces LRU recycle; large => undo_alloc race */
} thread_arg_t;

/* Once the TAILQ LRU list is corrupted by the recycle race, any further
 * TAILQ/RB operation on it dereferences a stale tqe_prev/tqe_next and either
 * crashes with SIGSEGV (CWE-787 "stale TAILQ pointer = arbitrary write" --
 * the noinv manifestation) or loops forever on a self-referential cycle.
 * We catch SIGSEGV (wild write) and SIGALRM (infinite loop on corruption). */
static volatile sig_atomic_t got_segv;
static void
crash_handler(int sig)
{
	(void)sig;
	_exit(42); /* distinctive: corruption manifested as wild pointer write */
}
static void
alarm_handler(int sig)
{
	(void)sig;
	_exit(43); /* distinctive: corruption caused infinite loop / hang */
}

static void *
worker(void *arg)
{
	thread_arg_t *a = (thread_arg_t *)arg;
	unsigned int seed = (unsigned)(a->tid * 1337 + 1);
	long i;
	/* Each thread hammers a mix of new and existing offsets. We use a small
	 * offset range so collisions (and LRU recycle once undo_alloc caps) are
	 * frequent -- this faithfully models sustained HAMMER v1 metadata mods
	 * from concurrent frontends once the undo history is full. */
	for (i = 0; i < OPS_PER_THREAD; i++) {
		hammer_off_t off = (hammer_off_t)(rand_r(&seed) % a->offset_range);
		enter_undo_history(a->hmp, off, 64);
	}
	return NULL;
}

static void
run_trial(int nthreads, int locked, unsigned offset_range,
	  int panic_mode, const char *label)
{
	model_mount_t hmp;
	pthread_t th[64];
	thread_arg_t args[64];
	int i, status;
	pid_t pid, w;

	/* fork() so a SIGSEGV/hang/panic in the unlocked trial (real corruption)
	 * is reported by the parent instead of killing the whole harness. */
	pid = fork();
	if (pid != 0) {
		/* parent: wait for child, decode exit */
		do { w = waitpid(pid, &status, 0); } while (w == -1);
		if (WIFEXITED(status) && WEXITSTATUS(status) == 44) {
			printf("=== %s : %d thr x %d ops range=%u (%s, panic-mode) ===\n",
			       label, nthreads, OPS_PER_THREAD, offset_range,
			       locked ? "LOCKED-fix" : "UNLOCKED-buggy");
			printf("  RESULT : RACE CONFIRMED - KKASSERT(onode==NULL) fired at\n"
			       "           hammer_undo.c:458 -> kernel PANIC (GENERIC/\n"
			       "           INVARIANTS-ON path, same as a real DF panic)\n");
		} else if (WIFEXITED(status) && WEXITSTATUS(status) == 42) {
			printf("=== %s : %d thr x %d ops range=%u (%s) ===\n",
			       label, nthreads, OPS_PER_THREAD, offset_range,
			       locked ? "LOCKED-fix" : "UNLOCKED-buggy");
			printf("  RESULT : RACE CONFIRMED - TAILQ corruption caused a wild\n"
			       "           pointer write (SIGSEGV) -- CWE-787 manifestation\n"
			       "           on a non-INVARIANTS (noinv) kernel\n");
		} else if (WIFEXITED(status) && WEXITSTATUS(status) == 43) {
			printf("=== %s : %d thr x %d ops range=%u (%s) ===\n",
			       label, nthreads, OPS_PER_THREAD, offset_range,
			       locked ? "LOCKED-fix" : "UNLOCKED-buggy");
			printf("  RESULT : RACE CONFIRMED - corruption created a cycle in the\n"
			       "           RB/TAILQ structure -> infinite loop (kernel would\n"
			       "           wedge in-kernel, equivalent to a DoS hang)\n");
		} else if (WIFSIGNALED(status)) {
			printf("=== %s : killed by signal %d ===\n", label, WTERMSIG(status));
		}
		return;
	}
	/* child */
	memset(&hmp, 0, sizeof(hmp));
	RB_INIT(&hmp.rb_undo_root);
	TAILQ_INIT(&hmp.undo_lru_list);
	hmp.undo_alloc = 0;
	pthread_mutex_init(&hmp.undo_lock, NULL);

	vol_onode_nonnull = 0;
	vol_alloc_overshoot = 0;
	vol_tailq_corrupt = 0;
	use_lock = locked;
	panic_on_kkassert = panic_mode;

	struct sigaction sa;
	memset(&sa, 0, sizeof(sa));
	sa.sa_handler = crash_handler;
	sigaction(SIGSEGV, &sa, NULL);
	sigaction(SIGBUS, &sa, NULL);
	sigaction(SIGABRT, &sa, NULL);
	sa.sa_handler = alarm_handler;
	sigaction(SIGALRM, &sa, NULL);
	alarm(8); /* bound a hang caused by a cycle in corrupted structures */

	for (i = 0; i < nthreads; i++) {
		args[i].hmp = &hmp;
		args[i].tid = i;
		args[i].nthreads = nthreads;
		args[i].offset_range = offset_range;
		pthread_create(&th[i], NULL, worker, &args[i]);
	}
	for (i = 0; i < nthreads; i++)
		pthread_join(th[i], NULL);

	if (!lru_integrity_ok(&hmp))
		vol_tailq_corrupt++;

	printf("=== %s : %d thr x %d ops range=%u (%s) ===\n",
	       label, nthreads, OPS_PER_THREAD, offset_range,
	       locked ? "LOCKED-fix" : "UNLOCKED-buggy");
	printf("  KKASSERT(onode==NULL) trips   : %ld\n", vol_onode_nonnull);
	printf("  undo_alloc overshoot (OOB idx): %ld\n", vol_alloc_overshoot);
	printf("  TAILQ/RB list corruption       : %ld\n", vol_tailq_corrupt);
	printf("  undo_alloc final               : %d\n", hmp.undo_alloc);
	printf("  RESULT                         : %s\n",
	       (vol_onode_nonnull || vol_alloc_overshoot || vol_tailq_corrupt)
		   ? "RACE CONFIRMED (panic on GENERIC / corruption on noinv)"
		   : "no violations detected");
	pthread_mutex_destroy(&hmp.undo_lock);
	_exit(0);
}

int main(void)
{
	setvbuf(stdout, NULL, _IONBF, 0);
	printf("DF-0893 deterministic race harness for hammer_enter_undo_history()\n");
	printf("Transcribes sys/vfs/hammer/hammer_undo.c:432-460 (unlocked) called from\n");
	printf("hammer_generate_undo() at hammer_undo.c:125 BEFORE undo_lock at :133.\n\n");

	/* Trial 0: KKASSERT panic mode -- models GENERIC/INVARIANTS exactly.
	 * First onode != NULL -> immediate "panic" (exit 44). Undo_alloc counter
	 * race: two threads grab same idx, RB_INSERT collides. */
	printf("--- Trial 0: KKASSERT panic mode (models GENERIC INVARIANTS) ---\n");
	run_trial(4, 0, 1000000u, 1, "BUGGY   ");
	run_trial(4, 1, 1000000u, 1, "FIXED   ");
	printf("\n");

	/* Trial 1: large offset range -> undo_alloc++ read-modify-write race
	 * (two threads index undos[N] identically, RB_INSERT collides). */
	printf("--- Trial 1: undo_alloc counter race (large offset range) ---\n");
	run_trial(4, 0, 1000000u, 0, "BUGGY   ");
	run_trial(4, 1, 1000000u, 0, "FIXED   ");
	printf("\n");

	/* Trial 2: small offset range -> undo_alloc caps at 1024 quickly, then
	 * the LRU-recycle race (two threads TAILQ_FIRST the same victim) corrupts
	 * the list -> SIGSEGV (wild write) or infinite loop (cycle). */
	printf("--- Trial 2: LRU-recycle race (small offset range, history full) ---\n");
	run_trial(4, 0, 2048u, 0, "BUGGY   ");
	run_trial(4, 1, 2048u, 0, "FIXED   ");
	printf("\n");

	printf("--- Trial 3: higher concurrency (8 threads) ---\n");
	run_trial(8, 0, 1000000u, 0, "BUGGY   ");
	run_trial(8, 1, 1000000u, 0, "FIXED   ");
	printf("\nDONE\n");
	return 0;
}