/*
 * fuzz_alist.c - pass-2 differential model test for sys/kern/subr_alist.c
 *
 * Compiles the real kernel source in userland (!_KERNEL branch) and hammers
 * it with LEGAL api sequences (per sys/sys/alist.h contract):
 *   - alist_alloc(start, count) with pow2 and non-pow2 counts
 *   - alist_free(blkno, count) of ranges that are fully allocated (piecemeal)
 * checking after every operation:
 *   H1  no overlapping allocation (returned range was free in the reference)
 *   H2  returned block is count-aligned, >= start, in domain
 *   H3  bl_free == reference free-block count  (accounting drift detector)
 *   H4  alist_free_info returns consistent data (free count + really-free range)
 * and after every round:
 *   H5  full radix-tree resolve() == reference map (protocol state machine)
 *   H6  no reserved '10' meta state ever appears
 *   H7  poison persistence: records slots outside the initialized subtree
 *       (alist_init records pre-poisoned w/ 0xAA) are NEVER written
 *       (the DF-2789-class out-of-domain write detector)
 *   H8  KKASSERTs live (INVARIANTS emulation); panic() catches double-free
 *
 * strict first-fit checking is enabled for start==0 rounds; for random-start
 * rounds false-NONE divergences are tallied separately (DF-0052 family).
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h>
#include <signal.h>

static FILE *jf;
static char opbuf[64];
static uint64_t opseq;

static void dump_state(void);
static void wd(int sig __unused) {
	fprintf(stderr, "WATCHDOG: harness hung 60s (attribution: see last "
		"marker)\n");
	_exit(99);
}

#define main alist_debug_main
#include "kern/subr_alist.c"
#undef main

#define POISON32	0xAAAAAAAAU
#define MAXBLOCKS	70000
#define MAXRECS		(ALIST_RECORDS_1048576 + 64)

static struct alist bl_store;
static almeta_t records[MAXRECS];
static uint8_t ref[MAXBLOCKS];		/* 0 = free, 1 = allocated */
static uint8_t resolved[MAXBLOCKS];
static uint8_t touched[MAXRECS];	/* slots radix_init initializes  */
static uint32_t nblocks;
static uint32_t ref_free;			/* incremental ref free count   */
static uint64_t ops, false_none, strict_mismatch;
static int strict_firstfit;

static void
mark_range(uint32_t b, uint32_t n, uint8_t v)
{
	uint32_t i;
	for (i = 0; i < n && b + i < nblocks; ++i)
		resolved[b + i] = v;
}

/* reconstruct the free map exactly per the 2-bit discipline */
static void
resolve(almeta_t *scan, uint32_t blkbase, uint32_t radix, uint32_t skip)
{
	uint32_t ns, j, pair;

	if (radix == ALIST_BMAP_RADIX) {
		uint32_t i;
		for (i = 0; i < ALIST_BMAP_RADIX; ++i)
			mark_range(blkbase + i, 1,
				   (scan->bm_bitmap & (1U << i)) ? 0 : 1);
		return;
	}
	radix /= ALIST_META_RADIX;
	ns = skip / ALIST_META_RADIX;
	for (j = 0; j < ALIST_META_RADIX; ++j) {
		pair = (scan->bm_bitmap >> (j * 2)) & 3;
		switch (pair) {
		case 0:				/* all allocated */
			mark_range(blkbase + j * radix, radix, 1);
			break;
		case 3:				/* all free */
			mark_range(blkbase + j * radix, radix, 0);
			break;
		case 1:				/* partial: recurse */
			resolve(&scan[1 + j * ns], blkbase + j * radix,
				radix, ns - 1);
			break;
		default:
			fprintf(stderr, "H6 FAIL: reserved '10' meta state "
				"at blk=%u radix=%u\n",
				blkbase + j * radix, radix);
			exit(9);
		}
	}
}

/* mirror of alst_radix_init's touched-slot pattern */
static void
touch(almeta_t *scan, uint32_t blkbase, uint32_t radix, uint32_t skip)
{
	uint32_t ns, j;

	touched[scan - records] = 1;
	if (radix == ALIST_BMAP_RADIX)
		return;
	radix /= ALIST_META_RADIX;
	ns = skip / ALIST_META_RADIX;
	for (j = 0; j < ALIST_META_RADIX; ++j) {
		if (blkbase + j * radix >= nblocks)
			break;
		touch(&scan[1 + j * ns], blkbase + j * radix, radix, ns - 1);
	}
}

static void	 classify_false_none(uint32_t, uint32_t, uint32_t);

static uint32_t
ref_free_count(void)
{
	return ref_free;
}

/* first pow2(ncount)-aligned fit at or after start */
static int64_t
expected_fit(uint32_t start, uint32_t ncount)
{
	uint32_t j, k;
	j = (start + ncount - 1) / ncount * ncount;
	for (; j + ncount <= nblocks; j += ncount) {
		for (k = 0; k < ncount; ++k)
			if (ref[j + k])
				break;
		if (k == ncount)
			return (int64_t)j;
	}
	return -1;
}

static uint32_t
pow2_below(uint32_t v)
{
	uint32_t p = 1;
	while (p * 2 <= v)
		p *= 2;
	return p;
}

static void
check_full_invariants(const char *tag)
{
	uint32_t i;

	memset(resolved, 0xFF, nblocks);	/* 0xFF = unknown marker */
	resolve(bl_store.bl_root, 0, bl_store.bl_radix, bl_store.bl_skip);
	for (i = 0; i < nblocks; ++i) {
		if (resolved[i] == 0xFF) {
			fprintf(stderr, "H5 FAIL(%s): block %u not covered "
				"by tree resolve\n", tag, i);
			exit(8);
		}
		if (resolved[i] != ref[i]) {
			fprintf(stderr, "H5 FAIL(%s): block %u tree=%u "
				"ref=%u\n", tag, i, resolved[i], ref[i]);
			exit(8);
		}
	}
	/* H7: poison persistence outside initialized slots */
	for (i = 0; i < (uint32_t)bl_store.bl_rootblks; ++i) {
		if (!touched[i] &&
		    (records[i].bm_bitmap != POISON32 ||
		     records[i].bm_bighint != POISON32)) {
			fprintf(stderr, "H7 FAIL(%s): out-of-domain slot %u "
				"was written: bitmap=%08x bighint=%08x\n",
				tag, i, records[i].bm_bitmap,
				records[i].bm_bighint);
			exit(7);
		}
	}
}

static void
dump_state(void)
{
	uint32_t i;
	if (!jf) return;
	fprintf(stderr, "\n=== DUMP at opseq %llu ===\n",
		(unsigned long long)opseq);
	fprintf(stderr, "ref   :");
	for (i = 0; i < nblocks; ++i)
		fprintf(stderr, "%u", ref[i]);
	fprintf(stderr, "\nbitmap:");
	for (i = 0; i < 32 && i < nblocks; ++i)
		fprintf(stderr, "%u", (bl_store.bl_root->bm_bitmap >> i) & 1);
	fprintf(stderr, "\nbl_free=%u ref_free=%u nblocks=%u\n",
		bl_store.bl_free, ref_free, nblocks);
}

static void
setup(uint32_t blocks)
{
	memset(records, 0xAA, sizeof(records));
	memset(&bl_store, 0, sizeof(bl_store));
	memset(touched, 0, sizeof(touched));
	nblocks = blocks;
	alarm(120);			/* refresh watchdog per geometry */
	alist_init(&bl_store, blocks, records, MAXRECS);
	memset(ref, 0, nblocks);			/* all allocated */
	alist_free(&bl_store, 0, blocks);		/* boot-style free-all */
	memset(ref, 0, nblocks);			/* now free */
	ref_free = nblocks;
	if (jf) { fprintf(jf, "S %u\n", blocks); fflush(jf); }
	touch(bl_store.bl_root, 0, bl_store.bl_radix, bl_store.bl_skip);
	assert(bl_store.bl_free == blocks);
}

static void
do_alloc(void)
{
	uint32_t start, count, ncount, k;
	int64_t exp;
	alist_blk_t r;

	if ((rand() & 3) == 0) {
		start = 0;
	} else {
		start = rand() % nblocks;
	}
	if (rand() & 1) {
		count = 1U << (rand() % 6);			/* pow2 1..32 */
		if (count > nblocks)
			count = pow2_below(nblocks);
		ncount = count;
	} else {
		count = 2 + rand() % 300;			/* often non-pow2 */
		if (count > nblocks)
			count = nblocks;
		if ((count | (count - 1)) == (count << 1) - 1)
			count--;				/* force non-pow2 */
		if (count < 2)
			count = 3;
		ncount = (count < 256) ? 1 : 256;
		while (ncount < count)
			ncount <<= 1;
	}
	if (ncount > nblocks)
		return;

	/* modeled alist off-by-one (DF-candidate): top-level guard
	 * count < bl_radix rejects count == 32 on leaf-root alists */
	exp = expected_fit(start, ncount);
	if (ncount >= bl_store.bl_radix)
		exp = -1;
	if (jf) { fprintf(jf, "A %u %u\n", start, count); fflush(jf); }
	opseq++;
	r = alist_alloc(&bl_store, start, count);
	ops++;

	if (r == ALIST_BLOCK_NONE) {
		if (exp >= 0) {
			false_none++;		/* DF-0052 family tally */
			if (start == 0)
				classify_false_none(start, ncount,
						    (uint32_t)exp);
		}
		return;
	}
	/* H1/H2: returned range must be free, aligned, >= start, in domain */
	if (r % ncount != 0 || r < start || r + ncount > nblocks) {
		fprintf(stderr, "H2 FAIL: alloc(start=%u,count=%u,nc=%u) "
			"returned %u\n", start, count, ncount, r);
		exit(5);
	}
	for (k = 0; k < ncount; ++k) {
		if (ref[r + k]) {
			fprintf(stderr, "H1 FAIL: overlapping allocation at "
				"%u (start=%u count=%u ncount=%u r=%u)\n",
				r + k, start, count, ncount, r);
			exit(4);
		}
	}
	if (strict_firstfit && start == 0 && exp >= 0 && (uint32_t)exp != r) {
		strict_mismatch++;	/* classify: leaf gate = DF-0052 known */
		classify_false_none(start, ncount, (uint32_t)exp);
	}
	/* mark [r, r+count) allocated (tail [r+count, r+ncount) auto-freed) */
	for (k = 0; k < count; ++k)
		ref[r + k] = 1;
	ref_free -= count;
}

static void
do_free(void)
{
	uint32_t b, f, e;

	if (ref_free_count() == 0)
		return;
	{
		uint32_t tries = 0;
		do {
			b = rand() % nblocks;
		} while (!ref[b] && ++tries < 64);
	}
	if (!ref[b])
		return;
	f = b;
	while (f > 0 && ref[f - 1])
		--f;
	e = b + 1;
	while (e < nblocks && ref[e])
		++e;
	/* optionally free only a random subrange (piecemeal frees are legal) */
	if (rand() & 1 && e - f > 1) {
		uint32_t nf = f + rand() % (e - f);
		uint32_t ne = nf + 1 + rand() % (e - nf);
		if (ne > e)
			ne = e;
		f = nf;
		e = ne;
	}
	if (jf) { fprintf(jf, "F %u %u\n", f, e - f); fflush(jf); }
	opseq++;
	memset(ref + f, 0, e - f);
	ref_free += e - f;
	alist_free(&bl_store, f, e - f);
	ops++;
}

/*
 * Attribute a false-NONE / first-fit miss: walk the full root->leaf path
 * of the expected fit and collect every bighint gate (count <= hint) that
 * blocks it.  Report the DEEPEST blocked gate:
 *   deepest = LEAF -> DF-0052 (known); metas above = its propagation
 *             via alst_meta_alloc:649-650 lowering after a :615 skip
 *   deepest = META (all leaf gates pass) -> independent NEW meta bug
 */
static int meta_block_count;	/* stats */
static void
classify_false_none(uint32_t start, uint32_t count, uint32_t fit)
{
	almeta_t *scan = bl_store.bl_root;
	uint32_t radix = bl_store.bl_radix, skip = bl_store.bl_skip, ns;
	uint32_t blk = 0, j;
	int deepest_is_meta = 0;
	uint32_t deepest_blk = 0, deepest_hint = 0;

	while (radix != ALIST_BMAP_RADIX) {
		radix /= ALIST_META_RADIX;
		ns = skip / ALIST_META_RADIX;
		j = (fit - blk) / radix;
		if (count > scan[1 + j * ns].bm_bighint) {
			deepest_is_meta = (radix != ALIST_BMAP_RADIX);
			deepest_blk = blk + j * radix;
			deepest_hint = scan[1 + j * ns].bm_bighint;
		}
		scan = &scan[1 + j * ns];
		blk += j * radix;
		skip = ns - 1;
	}
	(void)start;
	if (deepest_is_meta) {
		meta_block_count++;
		if (meta_block_count <= 5)
			fprintf(stderr, "*** META-DEEPEST gate blk=%u hint=%u "
				"count=%u (candidate NEW)\n",
				deepest_blk, deepest_hint, count);
	} else if (deepest_hint) {
		/* leaf-deepest: DF-0052 known + upward propagation */
	}
}

static void
do_free_info(void)
{
	alist_blk_t startp = 0x77, countp = 0x77, bf;
	uint32_t k;

	bf = alist_free_info(&bl_store, &startp, &countp);
	if (bf != ref_free_count()) {
		fprintf(stderr, "H4 FAIL: free_info bl_free=%u ref=%u\n",
			bf, ref_free_count());
		exit(3);
	}
	if (countp) {
		if (startp + countp > nblocks) {
			fprintf(stderr, "H4 FAIL: free_info range %u+%u "
				"out of domain (%u)\n", startp, countp,
				nblocks);
			exit(3);
		}
		for (k = 0; k < countp; ++k) {
			if (ref[startp + k]) {
				fprintf(stderr, "H4 FAIL: free_info claims "
					"allocated block %u free\n", startp + k);
				exit(3);
			}
		}
	}
}

int
main(int argc, char **argv)
{
	unsigned seed;
	uint32_t blocks;
	int rounds, r, i;
	long per_round;

	if (argc > 1)
		seed = strtoul(argv[1], NULL, 0);
	else
		seed = 1;
	srand(seed);
	signal(SIGALRM, wd);
	alarm(60);
	jf = fopen("journal.txt", "w");
	atexit(dump_state);

	const uint32_t geoms[] = { 1, 2, 31, 32, 33, 63, 64, 100, 127, 128,
		129, 255, 256, 257, 511, 512, 513, 1000, 1023, 1024, 1025,
		2047, 2048, 4095, 4096, 5000, 8192, 65535, 65536 };

	for (i = 0; i < (int)(sizeof(geoms) / sizeof(geoms[0])); ++i) {
		blocks = geoms[i];
		setup(blocks);
		strict_firstfit = 1;
		if (blocks <= 1024) { rounds = 400; per_round = 120; }
		else if (blocks <= 8192) { rounds = 120; per_round = 60; }
		else { rounds = 40; per_round = 40; }
		for (r = 0; r < rounds; ++r) {
			long op;
			for (op = 0; op < per_round; ++op) {
				switch (rand() % 10) {
				case 0: case 1: case 2: case 3:
				case 4: case 5:		do_alloc(); break;
				case 6: case 7: case 8:	do_free();  break;
				default:		do_free_info(); break;
				}
				if (bl_store.bl_free != ref_free_count()) {
					fprintf(stderr, "H3 FAIL: geometry "
						"%u bl_free=%u ref=%u\n",
						blocks, bl_store.bl_free,
						ref_free_count());
					return 2;
				}
			}
			/* churn: free everything, refill */
			if (r % 64 == 63) {
				uint32_t f, e2;
				check_full_invariants("churn");
				for (f = 0; f < nblocks; ++f) {
					if (!ref[f])
						continue;
					e2 = f + 1;
					while (e2 < nblocks && ref[e2])
						++e2;
					if (jf) {
						fprintf(jf, "F %u %u\n", f,
							e2 - f);
						fflush(jf);
					}
					memset(ref + f, 0, e2 - f);
					ref_free += e2 - f;
					alist_free(&bl_store, f, e2 - f);
				}
			}
		}
		check_full_invariants("final");
		printf("geometry %6u: OK  (rootblks=%u radix=%u skip=%u)\n",
		       blocks, bl_store.bl_rootblks, bl_store.bl_radix,
		       bl_store.bl_skip);
	}
	printf("ALL GEOMETRIES CLEAN: ops=%llu false_none=%llu "
	       "firstfit_miss=%llu meta_deepest_blocked=%d\n",
	       (unsigned long long)ops, (unsigned long long)false_none,
	       (unsigned long long)strict_mismatch, meta_block_count);
	return 0;
}