/*
 * rng_harness.c -- verification harness for DF-2250 / DF-2251
 * (sys/libkern/random.c).  GUEST-ONLY FILE: compiled into the DragonFly
 * kernel via sys/conf/files for PoC verification.  Never part of a fix.
 *
 * Trigger (as root on the guest):
 *   sysctl debug.rng_race=1000000   -> SMP race test: 6 lwkt threads pinned
 *                                      to CPUs 0..5, each calling the REAL
 *                                      krandom() 1e6 times; outputs merged,
 *                                      sorted, duplicate pairs counted.
 *   sysctl debug.rng_race=-1000000  -> control: ONE thread pinned to CPU0
 *                                      doing 6e6 draws; a serial MINSTD
 *                                      chain NEVER repeats inside its
 *                                      2^31-2 period, so expected dups = 0.
 *   sysctl debug.rng_pred=1         -> DF-2251: record 8 real krandom()
 *                                      outputs; forward-predict from v0,
 *                                      backward-recover from v7, predict
 *                                      the next 1000 draws, simulate the
 *                                      ffs i_gen consumer (2-candidate
 *                                      state recovery + next-value verify),
 *                                      and demonstrate the sppp CHAP
 *                                      XOR-differential state leak
 *                                      (2^31 offline search).
 *
 * All results are printed on the console (serial log) and returned as the
 * sysctl value.
 */
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/sysctl.h>
#include <sys/thread.h>
#include <sys/thread2.h>
#include <sys/libkern.h>
#include <sys/time.h>
#include <machine/atomic.h>
#include <machine/cpufunc.h>

#define RNGH_MAX_THREADS	16
#define RNGH_MAX_DRAWS		4000000

#define MM	2147483647UL		/* 2^31 - 1 */
#define AA	16807UL		/* MINSTD multiplier */
#define AINV	1407677000UL		/* 16807^-1 mod (2^31-1), verified */

struct rng_ent {
	u_long v;
	int cpu;
	int idx;
};

struct rng_ctx {
	int cpu;
	long count;
	struct rng_ent *buf;
	volatile int done;
};

static volatile int rngh_go;
static int rngh_last_dups;

static u_long
lcg_fwd(u_long x)
{
	return ((u_long)(((u_int64_t)x * AA) % MM));
}

static u_long
lcg_bwd(u_long x)
{
	return ((u_long)(((u_int64_t)x * AINV) % MM));
}

static int
rng_ent_cmp(const void *a, const void *b)
{
	const struct rng_ent *ea = a, *eb = b;

	if (ea->v < eb->v)
		return (-1);
	if (ea->v > eb->v)
		return (1);
	return (0);
}

/*
 * Worker thread: pinned to one CPU by lwkt_create(); spins until the
 * coordinator drops the gate, then calls the REAL krandom() in a tight
 * loop, recording every value with attribution.
 */
static void
rng_race_thread(void *arg)
{
	struct rng_ctx *c = arg;
	long i;

	while (atomic_load_acq_int(&rngh_go) == 0)
		cpu_ccfence();
	for (i = 0; i < c->count; i++) {
		c->buf[i].v = krandom();
		c->buf[i].cpu = c->cpu;
		c->buf[i].idx = i;
	}
	atomic_store_rel_int(&c->done, 1);
	wakeup((void *)c);
	/* lwkt_exit() happens automatically on return */
}

static int
rng_race_run(long per_thread)
{
	struct rng_ctx ctx[RNGH_MAX_THREADS];
	struct rng_ent *merged;
	struct thread *td;
	long total, i;
	int nthreads, ctrl = 0, c, error = 0, dups = 0, intra = 0, shown = 0;
	struct timespec t0, t1;
	int ms;

	if (per_thread < 0) {
		ctrl = 1;
		per_thread = -per_thread;
	}
	if (per_thread == 0 || per_thread > RNGH_MAX_DRAWS)
		return (EINVAL);

	nthreads = ctrl ? 1 : ncpus;
	if (nthreads > RNGH_MAX_THREADS)
		nthreads = RNGH_MAX_THREADS;

	nanouptime(&t0);
	bzero(ctx, sizeof(ctx));
	atomic_store_rel_int(&rngh_go, 0);
	total = 0;
	for (c = 0; c < nthreads; c++) {
		ctx[c].cpu = ctrl ? mycpuid : c;
		ctx[c].count = per_thread * (ctrl ? ncpus : 1);
		total += ctx[c].count;
		ctx[c].buf = kmalloc(ctx[c].count * sizeof(struct rng_ent),
				     M_TEMP, M_WAITOK);
		if (ctx[c].buf == NULL) {
			error = ENOMEM;
			break;
		}
		error = lwkt_create(rng_race_thread, &ctx[c], &td, NULL, 0,
				    ctx[c].cpu, "rngrace%d", ctx[c].cpu);
		if (error)
			break;
	}
	/*
	 * Always open the gate so any created spinners finish into their
	 * (valid) buffers, then reap them before touching/freeing anything.
	 */
	atomic_store_rel_int(&rngh_go, 1);
	for (;;) {
		int alldone = 1;

		for (c = 0; c < nthreads; c++) {
			if (ctx[c].buf &&
			    !atomic_load_acq_int(&ctx[c].done)) {
				alldone = 0;
				break;
			}
		}
		if (alldone)
			break;
		tsleep(&ctx[0], 0, "rngrace", hz / 4);
	}
	nanouptime(&t1);
	ms = (t1.tv_sec - t0.tv_sec) * 1000 + (t1.tv_nsec - t0.tv_nsec) / 1000000;
	if (error)
		goto out;

	merged = kmalloc((size_t)total * sizeof(struct rng_ent),
			 M_TEMP, M_WAITOK);
	if (merged == NULL) {
		error = ENOMEM;
		goto out;
	}
	{
		size_t off = 0;

		for (c = 0; c < nthreads; c++) {
			bcopy(ctx[c].buf, (char *)merged + off,
			      ctx[c].count * sizeof(struct rng_ent));
			off += ctx[c].count * sizeof(struct rng_ent);
		}
		kqsort(merged, (size_t)total, sizeof(struct rng_ent),
		       rng_ent_cmp);
		for (i = 1; i < total; i++) {
			if (merged[i].v == merged[i - 1].v) {
				dups++;
				if (merged[i].cpu == merged[i - 1].cpu)
					intra++;
				if (shown < 8) {
					kprintf("RNGRACE: dup value=0x%016lx "
					    "A[cpu=%d idx=%d] B[cpu=%d idx=%d]\n",
					    merged[i].v,
					    merged[i - 1].cpu,
					    merged[i - 1].idx,
					    merged[i].cpu, merged[i].idx);
					shown++;
				}
			}
		}
		kfree(merged, M_TEMP);
	}
	rngh_last_dups = dups;
	kprintf("RNGRACE: mode=%s threads=%d draws/thread=%ld total=%ld "
	    "elapsed=%dms\n", ctrl ? "CONTROL(1 thread pinned)" : "SMP",
	    nthreads, per_thread * (ctrl ? ncpus : 1), total, ms);
	kprintf("RNGRACE: duplicates=%d (rate per 1e6 draws: %lu.%02lu) "
	    "same-cpu-dups=%d\n", dups,
	    (u_long)dups * 1000000UL / (u_long)total,
	    ((u_long)dups * 1000000UL % (u_long)total) * 100UL / (u_long)total,
	    intra);
	if (ctrl)
		kprintf("RNGRACE: control note: serial MINSTD chain never "
		    "repeats within its 2^31-2 period; expected dups = 0\n");
out:
	for (c = 0; c < nthreads; c++) {
		if (ctx[c].buf)
			kfree(ctx[c].buf, M_TEMP);
	}
	return (error);
}

static int
sysctl_rng_race(SYSCTL_HANDLER_ARGS)
{
	int t, error;

	t = 0;
	error = sysctl_handle_int(oidp, &t, 0, req);
	if (error || req->newptr == NULL)
		return (error);
	error = rng_race_run((long)t);
	if (error == 0)
		t = rngh_last_dups;
	return (error);
}

/*
 * DF-2251: predictability demonstration against the REAL krandom().
 */
static int
rng_pred_run(void)
{
	u_long v[8], p, q;
	u_long gen1, gen2, gpred;
	u_long ch[4], seed, d1, d2, cand;
	int i, hits, attempt, ok, chattempt;
	int chap_found = 0;
	u_long chap_state = 0, chap_real = 0;

	for (attempt = 1; attempt <= 50; attempt++) {
		/* deterministic start so results are reproducible */
		skrandom(12345);
		for (i = 0; i < 8; i++)
			v[i] = krandom();

		/* forward prediction from v[0] */
		p = v[0];
		ok = 1;
		for (i = 1; i < 8; i++) {
			p = lcg_fwd(p);
			if (p != v[i])
				ok = 0;
		}
		if (!ok) {
			kprintf("RNGPRED: attempt %d: forward chain broken "
			    "(interference); retrying\n", attempt);
			continue;
		}

		/* backward recovery from v[7] via modular inverse */
		q = v[7];
		ok = 1;
		for (i = 6; i >= 0; i--) {
			q = lcg_bwd(q);
			if (q != v[i])
				ok = 0;
		}
		if (!ok) {
			kprintf("RNGPRED: attempt %d: backward chain broken; "
			    "retrying\n", attempt);
			continue;
		}

		/* predict the NEXT 1000 real draws */
		hits = 0;
		p = v[7];
		for (i = 0; i < 1000; i++) {
			p = lcg_fwd(p);
			if (p == krandom())
				hits++;
		}
		if (hits != 1000) {
			kprintf("RNGPRED: attempt %d: 1000-draw prediction "
			    "hit %d/1000 (interference); retrying\n",
			    attempt, hits);
			continue;
		}

		kprintf("RNGPRED: attempt %d SUCCESS on real krandom():\n",
		    attempt);
		kprintf("RNGPRED: v0..v7 =");
		for (i = 0; i < 8; i++)
			kprintf(" %09lu", v[i]);
		kprintf("\n");
		kprintf("RNGPRED: forward  x[n+1]=16807*x mod (2^31-1) from "
		    "v0 reproduces v1..v7 exactly\n");
		kprintf("RNGPRED: backward x[n-1]=1407677000*x mod (2^31-1) "
		    "from v7 recovers v6..v0 exactly\n");
		kprintf("RNGPRED: predicted NEXT 1000 real krandom() draws: "
		    "%d/1000 exact matches\n", hits);

		/*
		 * ffs i_gen consumer simulation (ffs_alloc.c:642):
		 *   g = krandom()/2 + 1  -- observer sees g, recovers the
		 *   state t in {2(g-1), 2(g-1)+1} (2 candidates), then
		 *   predicts the NEXT inode generation.
		 */
		gen1 = krandom() / 2 + 1;
		gen2 = krandom() / 2 + 1;
		ok = 0;
		for (cand = 2 * (gen1 - 1); cand <= 2 * (gen1 - 1) + 1; cand++) {
			gpred = lcg_fwd(cand) / 2 + 1;
			if (gpred == gen2) {
				ok = 1;
				break;
			}
		}
		kprintf("RNGPRED: i_gen consumer: g1=%lu g2=%lu "
		    "state-recovered=%lu next-prediction-match=%s\n",
		    gen1, gen2, cand, ok ? "YES" : "NO");
		break;
	}
	if (attempt > 50)
		return (ENOENT);

	/*
	 * sppp CHAP XOR-differential (if_spppsubr.c:4260-4268):
	 *   ch[i] = seed ^ krandom()  (seed = fresh strong read_random)
	 * Observer computes ch[0]^ch[1] = v0^v1, ch[1]^ch[2] = v1^v2 --
	 * the strong seed cancels; a 2^31 offline search then recovers the
	 * MINSTD state.  The seed keeps the challenge WORDS unpredictable,
	 * but the kernel-global PRNG state leaks.
	 */
	for (chattempt = 1; chattempt <= 10; chattempt++) {
		seed = karc4random();	/* stand-in for read_random strong seed */
		for (i = 0; i < 4; i++)
			ch[i] = seed ^ krandom();
		d1 = ch[0] ^ ch[1];
		d2 = ch[1] ^ ch[2];
		/* verify the search will find the real state first */
		{
			u_long r0 = seed ^ ch[0];

			chap_real = r0;
		}
		chap_found = 0;
		for (cand = 1; cand < MM; cand++) {
			u_long f1 = lcg_fwd(cand);
			u_long f2;

			if ((cand ^ f1) != d1)
				continue;
			f2 = lcg_fwd(f1);
			if ((f1 ^ f2) != d2)
				continue;
			chap_state = cand;
			chap_found = 1;
			break;
		}
		if (chap_found && chap_state == chap_real)
			break;
	}
	kprintf("RNGPRED: chap-diff: found=%s recovered-state=%09lu "
	    "matches-real-state=%s (search <= 2^31 offline, ~seconds on one "
	    "CPU)\n", chap_found ? "YES" : "NO", chap_state,
	    (chap_found && chap_state == chap_real) ? "YES" : "NO");
	kprintf("RNGPRED: RESULT: single observed output => full state "
	    "(past via inverse, future via multiplier) for the REAL "
	    "krandom()\n");
	return (0);
}

static int
sysctl_rng_pred(SYSCTL_HANDLER_ARGS)
{
	int t, error;

	t = 0;
	error = sysctl_handle_int(oidp, &t, 0, req);
	if (error || req->newptr == NULL)
		return (error);
	if (t != 1)
		return (EINVAL);
	return (rng_pred_run());
}

SYSCTL_PROC(_debug, OID_AUTO, rng_race, CTLTYPE_INT | CTLFLAG_RW,
	    0, 0, sysctl_rng_race, "I",
	    "DF-2250: >0 draws/thread SMP race test, <0 single-CPU control");
SYSCTL_PROC(_debug, OID_AUTO, rng_pred, CTLTYPE_INT | CTLFLAG_RW,
	    0, 0, sysctl_rng_pred, "I",
	    "DF-2251: write 1 to run MINSTD prediction demo on real krandom");
SYSCTL_INT(_debug, OID_AUTO, rng_race_dups, CTLFLAG_RD,
	    &rngh_last_dups, 0, "DF-2250: duplicate count from last race run");