/*
 * DF-5688 — randomized differential harness for sys/libkern/linux_idr.c
 * (the kernel branch, compiled UNMODIFIED via the shim headers).
 *
 * Defect under test: struct idr_node.allocated is a *cumulative subtree
 * allocation count* (comment at linux_idr.c:212-217), but idr_remove()
 * (linux_idr.c:473) and idr_get_node() (linux_idr.c:187, used by
 * idr_replace) test it as if it were the leaf's own allocated state.
 * Calling idr_remove() with an id that was never allocated but whose
 * Fenwick coverage is non-zero therefore performs a PHANTOM DECREMENT of
 * the counters (idr_reserve(idp, id, -1), linux_idr.c:479) and returns
 * NULL — exactly the call pattern of DRM_IOCTL_SYNCOBJ_DESTROY
 * (sys/dev/drm/drm_syncobj.c:363-377), which feeds the raw u32 ioctl
 * handle into idr_remove() and treats its return value as the lookup.
 *
 * Once the counters lie, idr_find_free() (linux_idr.c:202-249) can return
 * an ALREADY-ALLOCATED leaf: idr_get_new_above()/idr_alloc() then hand
 * out a DUPLICATE id and silently overwrite nodes[id].data
 * (linux_idr.c:346-347, 401-402) — the previous kernel object pointer is
 * lost (leak / handle aliasing) and two user handles map to the same id.
 *
 * The reference model tracks only per-leaf truth (used/ptr).  After every
 * operation we recompute the TRUE cumulative counters from the model and
 * compare them with the tree state (immediate phantom detection), and we
 * flag any duplicate-id issuance, any overwritten pointer, any remove of
 * a free id that returned non-NULL, and any idr_replace of a free id that
 * did not return -ENOENT (Linux semantics: no-op).
 *
 * usage: df5688_rig fuzz <iterations> <seed>
 *        df5688_rig minimal
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdarg.h>
#include <assert.h>
#include <signal.h>
#include <unistd.h>

#include "linux_idr.c"			/* file under audit, kernel branch */

#define	MODEL_MAX	16384

static uint8_t	mused[MODEL_MAX];
static void	   *mval[MODEL_MAX];

#define	OPHIST	65536
static char	ophist[OPHIST][112];
static int	oph_n;

static int	diverged;
static int	lenient;	/* count counter-divergences, keep fuzzing:
				 * we want the resulting MEMORY-SAFETY
				 * divergence (dup id / overwrite) */
static int	n_dup, n_phantom_cnt, n_stale_ptr, n_badremove, n_badreplace;

unsigned long rig_live_chunks, rig_live_bytes, rig_free_poisons;
struct rig_mycpu rig_mycpu;

static void dump_tail(void);
static void do_alloc_re(struct idr *idp, int start, int end, int tag);
static void do_getnew_re(struct idr *idp, int sid, int tag);
static void do_remove_re(struct idr *idp, int id);
static void do_replace_re(struct idr *idp, int id);

#ifdef RIG_SOFTASSERT
jmp_buf rig_jmp;
int rig_panics;
void
rig_softpanic(const char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	va_end(ap);
	fprintf(stderr, "\n");
	rig_panics++;
	longjmp(rig_jmp, 1);
}
#else
static void
abrt_handler(int sig __attribute__((unused)))
{
	fprintf(stderr,
	    "--- SIGABRT (kernel KKASSERT/panic equivalent) ---\n");
	dump_tail();
	_exit(3);
}
#endif

static uint32_t
xshift(uint32_t *s)
{
	*s ^= *s << 13; *s ^= *s >> 17; *s ^= *s << 5;
	return (*s);
}

/* ---- op recorder + replayer (for ddmin shrinking) ---- */
struct rec {
	int	type;			/* 0 alloc 1 getnew 2 remove 3 replace */
	int	a, b;
};
static struct rec	recs[262144];
static int		nrec;
static int		rec_on;
static unsigned char	drop[262144];

static void
rec(int type, int a, int b)
{
	if (rec_on && nrec < 262144) {
		recs[nrec].type = type;
		recs[nrec].a = a;
		recs[nrec].b = b;
		nrec++;
	}
}

/*
 * Replay recs[0..lim) on a fresh idr; return non-zero iff a DUPLICATE id
 * is still issued.  The model is resynced to the observable tree state
 * (what idr_find reports) after every op, so earlier non-dup divergences
 * do not abort the hunt.
 */
static int
replay(int lim)
{
	struct idr idr;
	int i, k, bad = 0;

	memset(mused, 0, sizeof(mused));
	memset(mval, 0, sizeof(mval));
	n_dup = n_stale_ptr = n_badremove = 0;
	idr_init(&idr);

	for (i = 0; i < lim; i++) {
		if (drop[i])
			continue;
		diverged = 0;
		switch (recs[i].type) {
		case 0:
			do_alloc_re(&idr, recs[i].a, recs[i].b, i);
			break;
		case 1:
			do_getnew_re(&idr, recs[i].a, i);
			break;
		case 2:
			do_remove_re(&idr, recs[i].a);
			break;
		case 3:
			do_replace_re(&idr, recs[i].a);
			break;
		}
		/* resync model to observables */
		for (k = 0; k < idr.idr_count && k < MODEL_MAX; k++) {
			void *p = idr_find(&idr, k);

			mused[k] = (p != NULL);
			mval[k] = p;
		}
	}
	bad = (n_dup > 0);			/* dup-only shrink criterion */
	idr_destroy(&idr);
	return (bad);
}

static void
oph_add(const char *fmt, ...)
{
	va_list ap;

	if (oph_n < OPHIST) {
		va_start(ap, fmt);
		vsnprintf(ophist[oph_n], sizeof(ophist[0]), fmt, ap);
		va_end(ap);
	}
	oph_n++;
}

static void
dump_tail(void)
{
	int i, first;

	first = (oph_n > 40) ? oph_n - 40 : 0;
	for (i = first; i < oph_n; i++)
		fprintf(stderr, "  op[%d] %s\n", i,
		    ophist[i % OPHIST]);
}

static void
dump_tree(struct idr *idp)
{
	int i;

	fprintf(stderr, "  idr: count=%d last=%d free=%d maxwant=%d\n",
	    idp->idr_count, idp->idr_lastindex, idp->idr_freeindex,
	    idp->idr_maxwant);
	for (i = 0; i < 64 && i < idp->idr_count; i++)
		fprintf(stderr,
		    "  node[%3d] data=%p alloc=%3d (model used=%d val=%p)\n",
		    i, idp->idr_nodes[i].data, idp->idr_nodes[i].allocated,
		    mused[i], mused[i] ? mval[i] : NULL);
}

/*
 * Recompute the TRUE cumulative counters implied by the model's leaf
 * set and compare with the live tree.  This detects a phantom decrement
 * the moment it happens (before any duplicate id is handed out).
 */
static void
check_counts(struct idr *idp, const char *ctx)
{
	static int *truth;
	static int truth_cap;
	int i, id;

	if (idp->idr_count > truth_cap) {
		truth_cap = idp->idr_count + 256;
		truth = realloc(truth, truth_cap * sizeof(int));
	}
	memset(truth, 0, idp->idr_count * sizeof(int));
	for (i = 0; i < idp->idr_count && i < MODEL_MAX; i++) {
		if (!mused[i])
			continue;
		for (id = i; id >= 0; id = left_ancestor(id))
			truth[id]++;
	}
	for (i = 0; i < idp->idr_count; i++) {
		if (truth[i] != idp->idr_nodes[i].allocated) {
			n_phantom_cnt++;
			fprintf(stderr,
			    "DIVERGENCE[%s]: counter corrupted at node %d: "
			    "tree=%d truth=%d (delta %d)\n", ctx, i,
			    idp->idr_nodes[i].allocated, truth[i],
			    idp->idr_nodes[i].allocated - truth[i]);
			if (lenient) {
				/* model re-syncs to the LIED tree so we can
				 * keep hunting the safety divergence */
				return;
			}
			dump_tail();
			dump_tree(idp);
			diverged = 1;
			return;
		}
	}
}

static void
check_sweep(struct idr *idp)
{
	int i;

	for (i = 0; i < idp->idr_count && i < MODEL_MAX; i++) {
		void *p = idr_find(idp, i);

		if (mused[i] && p != mval[i]) {
			n_stale_ptr++;
			fprintf(stderr,
			    "DIVERGENCE[sweep]: idr_find(%d)=%p but model=%p "
			    "(silent overwrite / duplicate id)\n", i, p,
			    mval[i]);
			dump_tail();
			dump_tree(idp);
			diverged = 1;
			return;
		}
		if (!mused[i] && p != NULL) {
			n_stale_ptr++;
			fprintf(stderr,
			    "DIVERGENCE[sweep]: idr_find(%d)=%p for FREE id\n",
			    i, p);
			dump_tail();
			dump_tree(idp);
			diverged = 1;
			return;
		}
	}
}

static uintptr_t
mkval(int tag)
{
	return (0x515000000000UL + (tag << 8));
}

/* ---- parameterized op bodies (used by fuzz AND by replay) ---- */

static void
do_alloc_re(struct idr *idp, int start, int end, int tag)
{
	int id = idr_alloc(idp, (void *)mkval(tag), start, end, 0);

	if (id >= 0) {
		if (id >= MODEL_MAX) {
			fprintf(stderr, "alloc id %d beyond model\n", id);
			diverged = 1;
			return;
		}
		if (mused[id]) {
			n_dup++;
			fprintf(stderr,
			    "DIVERGENCE: idr_alloc returned DUPLICATE id %d "
			    "(already holds %p, new %p)\n", id, mval[id],
			    (void *)mkval(tag));
			dump_tail();
			diverged = 1;
			return;
		}
		if (end > 0 && id >= end) {
			fprintf(stderr,
			    "DIVERGENCE: idr_alloc id %d violates end %d\n",
			    id, end);
			diverged = 1;
			return;
		}
		if (id < start) {
			fprintf(stderr,
			    "DIVERGENCE: idr_alloc id %d < start %d\n", id,
			    start);
			diverged = 1;
			return;
		}
		mused[id] = 1;
		mval[id] = (void *)mkval(tag);
	}
}

static void
do_getnew_re(struct idr *idp, int sid, int tag)
{
	int id = -1, tries, error;

	for (tries = 0; tries < 4; tries++) {
		if (idr_pre_get(idp, 0) == 0)
			break;
		error = idr_get_new_above(idp, (void *)mkval(tag), sid, &id);
		if (error == 0)
			break;
		if (error != -EAGAIN) {
			fprintf(stderr, "get_new err %d\n", error);
			diverged = 1;
			return;
		}
		id = -1;
	}
	if (id >= 0) {
		if (id >= MODEL_MAX) {
			fprintf(stderr, "get_new id %d beyond model\n", id);
			diverged = 1;
			return;
		}
		if (mused[id]) {
			n_dup++;
			fprintf(stderr,
			    "DIVERGENCE: idr_get_new_above returned DUPLICATE "
			    "id %d (holds %p, new %p)\n", id, mval[id],
			    (void *)mkval(tag));
			dump_tail();
			diverged = 1;
			return;
		}
		mused[id] = 1;
		mval[id] = (void *)mkval(tag);
	}
}

static void
do_remove_re(struct idr *idp, int id)
{
	void *p = idr_remove(idp, id);

	if (id < 0 || id >= MODEL_MAX)
		return;
	if (mused[id]) {
		if (p != mval[id]) {
			n_badremove++;
			fprintf(stderr,
			    "DIVERGENCE: remove(%d) returned %p, model %p\n",
			    id, p, mval[id]);
			dump_tail();
			diverged = 1;
			return;
		}
		mused[id] = 0;
		mval[id] = NULL;
	} else {
		if (p != NULL) {
			n_badremove++;
			fprintf(stderr,
			    "DIVERGENCE: remove(%d) of FREE id returned %p "
			    "(Linux semantics: NULL no-op)\n", id, p);
			dump_tail();
			dump_tree(idp);
			diverged = 1;
			return;
		}
	}
}

static void
do_replace_re(struct idr *idp, int id)
{
	void *old = idr_replace(idp, (void *)0x5150000000AAUL, id);

	if (id < 0 || id >= MODEL_MAX)
		return;
	if (mused[id]) {
		if (old != mval[id]) {
			n_badreplace++;
			diverged = 1;
			return;
		}
		mval[id] = (void *)0x5150000000AAUL;
	} else {
		if (old != (void *)(uintptr_t)(unsigned long)-ENOENT) {
			n_badreplace++;
			fprintf(stderr,
			    "DIVERGENCE: replace(%d) of FREE id returned %p "
			    "and WROTE it (Linux: -ENOENT no-op)\n", id, old);
			if (lenient) {
				mused[id] = 1;
				mval[id] = (void *)0x5150000000AAUL;
				return;
			}
			dump_tail();
			diverged = 1;
			return;
		}
	}
}

static void
do_alloc(struct idr *idp, uint32_t *rs)
{
	uint32_t r = xshift(rs);
	int start = r % 600;
	int end;
	int id;

	if ((r >> 16) & 1)
		end = 0;
	else
		end = start + 1 + ((r >> 8) % 64);

	rec(0, start, end);
	do_alloc_re(idp, start, end, nrec - 1);
	/* recover id for the log */
	id = idp->idr_lastindex;	/* approx; log only */
	oph_add("alloc(start=%d,end=%d)", start, end);
	(void)id;
}

static void
do_getnew(struct idr *idp, uint32_t *rs)
{
	int sid = xshift(rs) % 600;

	rec(1, sid, 0);
	do_getnew_re(idp, sid, nrec - 1);
	oph_add("get_new(sid=%d)", sid);
}

static int
pick_used(uint32_t *rs)
{
	int i, n = 0, want;

	for (i = 0; i < MODEL_MAX; i++)
		if (mused[i])
			n++;
	if (n == 0)
		return (-1);
	want = xshift(rs) % n;
	for (i = 0; i < MODEL_MAX; i++) {
		if (mused[i] && want-- == 0)
			return (i);
	}
	return (-1);
}

static void
do_remove(struct idr *idp, uint32_t *rs)
{
	uint32_t r = xshift(rs);
	int id;

	if (((r >> 24) & 7) < 4) {
		id = pick_used(rs);			/* legit remove */
		if (id < 0) {
			oph_add("remove(none)");
			return;
		}
	} else if (((r >> 28) & 3) == 0) {
		/*
		 * smart bogus: a left-ancestor (internal covered node) of
		 * a used leaf — precisely the SYNCOBJ_DESTROY attacker
		 * shape (bogus handle that is an internal tree index)
		 */
		int u = pick_used(rs);

		id = (u < 0) ? -1 : left_ancestor(u);
		if (id < 0)
			id = (r >> 4) % 600;
	} else {
		id = (r >> 4) % 600;			/* random bogus id */
	}
	if (id < 0)
		return;

	rec(2, id, 0);
	do_remove_re(idp, id);
	oph_add("remove(%d)", id);
}

static void
do_replace(struct idr *idp, uint32_t *rs)
{
	uint32_t r = xshift(rs);
	int id;

	if (((r >> 20) & 3) == 0)
		id = pick_used(rs);
	else
		id = (r >> 6) % 600;		/* bogus replace */
	if (id < 0)
		return;

	rec(3, id, 0);
	do_replace_re(idp, id);
	oph_add("replace(%d)", id);
}

static void
do_find(struct idr *idp, uint32_t *rs)
{
	int id = (xshift(rs) >> 3) % 700;
	void *p = idr_find(idp, id);

	if (mused[id] && p != mval[id]) {
		n_stale_ptr++;
		fprintf(stderr,
		    "DIVERGENCE: find(%d)=%p model=%p\n", id, p, mval[id]);
		dump_tail();
		diverged = 1;
		return;
	}
	if (!mused[id] && p != NULL) {
		n_stale_ptr++;
		fprintf(stderr,
		    "DIVERGENCE: find(%d) non-NULL for free id\n", id);
		diverged = 1;
		return;
	}
	oph_add("find(%d) -> %p", id, p);
}

static void
do_remove_all(struct idr *idp)
{
	idr_remove_all(idp);
	memset(mused, 0, sizeof(mused));
	memset(mval, 0, sizeof(mval));
	oph_add("remove_all");
}

static void
do_reinit(struct idr *idp)
{
	idr_destroy(idp);
	idr_init(idp);
	memset(mused, 0, sizeof(mused));
	memset(mval, 0, sizeof(mval));
	oph_add("destroy+init");
}

int
main(int ac, char **av)
{
	struct idr idr;
	uint32_t rs = 1;
	long iters = 20000;
	long i;
	int sweep = 0;

	if (ac >= 3 && strcmp(av[1], "fuzz") == 0) {
		iters = strtol(av[2], NULL, 0);
		rs = (ac >= 4) ? (uint32_t)strtoul(av[3], NULL, 0) : 1;
		lenient = (ac >= 5 && strcmp(av[4], "lenient") == 0);
	} else if (ac >= 2 && strcmp(av[1], "minimal") == 0) {
		iters = -1;
	} else if (ac >= 2 && strcmp(av[1], "minimal_panic") == 0) {
		/*
		 * Hand-derived 5-op sequence that drives a cumulative
		 * counter NEGATIVE and trips the kernel's own
		 * KKASSERT(idr_nodes[id].allocated >= 0) in idr_reserve()
		 * (linux_idr.c:197) — an in-kernel panic():
		 *
		 *   chain(289) = {289, 287, 255}; chain(287) = {287, 255}
		 *   alloc(289):            289:1  287:1  255:1
		 *   bogus remove(287):     289:1  287:0  255:0   (guard
		 *                              passes: nodes[287].allocated!=0)
		 *   alloc(290):            290:1  289:2  287:1  255:1
		 *   bogus remove(287):     290:1  289:2  287:0  255:0
		 *   legit remove(290):     290:0  289:1  287:-1 255:-1  <- KKASSERT
		 */
		iters = -2;
	} else if (ac >= 2 && strcmp(av[1], "minimal_dup") == 0) {
		/* Part B only: the 4-op pure duplicate-id sequence — no
		 * counter goes negative, so it runs with live KKASSERT
		 * (hard build) and in-kernel (df5688_mod.c) */
		iters = -3;
	} else if (ac >= 4 && strcmp(av[1], "shrink") == 0) {
		/*
		 * shrink <iters> <seed>: capture until the first safety
		 * divergence, then greedily drop ops that are not needed
		 * to reproduce it; emit the minimized sequence as C
		 * statements for df5688_minimal.h.
		 */
		long lim = 0;
		int kept = 0, j;

		iters = strtol(av[2], NULL, 0);
		rs = (uint32_t)strtoul(av[3], NULL, 0);
		lenient = 1;
		rec_on = 1;

		idr_init(&idr);
#ifdef RIG_SOFTASSERT
		if (setjmp(rig_jmp) != 0)
			oph_add("PANIC(longjmp) recovered");
#endif
		for (i = 0; i < iters && !(n_dup > 0); i++) {
			uint32_t r = xshift(&rs);

			diverged = 0;	/* keep hunting past other
					 * divergence kinds */
			switch ((r >> 26) % 10) {
			case 0: case 1: case 2: case 3:
				do_alloc(&idr, &rs);
				break;
			case 4:
				do_getnew(&idr, &rs);
				break;
			case 5: case 6: case 7:
				do_remove(&idr, &rs);
				break;
			case 8:
				do_replace(&idr, &rs);
				break;
			case 9:
				break;		/* find/remove_all/reinit off */
			}
		}
		idr_destroy(&idr);
		lim = nrec;
		if (!diverged || lim == 0) {
			fprintf(stderr, "shrink: no divergence captured\n");
			return (1);
		}
		fprintf(stderr,
		    "shrink: captured safety divergence after %ld ops "
		    "(%d recorded); minimizing...\n", i, nrec);

		memset(drop, 0, sizeof(drop));
		for (j = (int)lim - 1; j >= 0; j--) {
			drop[j] = 1;
			if (!replay((int)lim))
				drop[j] = 0;	/* needed: restore */
		}
		if (!replay((int)lim)) {
			fprintf(stderr, "shrink: INTERNAL ERROR (lost it)\n");
			return (1);
		}
		for (j = 0; j < (int)lim; j++)
			if (!drop[j])
				kept++;
		fprintf(stderr,
		    "shrink: minimized to %d ops; emit for "
		    "df5688_minimal.h:\n\n", kept);
		for (j = 0; j < (int)lim; j++) {
			if (drop[j])
				continue;
			switch (recs[j].type) {
			case 0:
				printf("{ int _id; _id = idr_alloc(&idr, "
				    "(void *)(0x515000000000UL + 0x100UL*%d), "
				    "%d, %d, 0); "
				    "printf(\"alloc(%%d,%%d) -> %%d\\n\", "
				    "%d, %d, _id); }\n",
				    j, recs[j].a, recs[j].b, recs[j].a,
				    recs[j].b);
				break;
			case 1:
				printf("{ int _id = -1, _t; for (_t = 0; "
				    "_t < 4; _t++) { if (idr_pre_get(&idr, 0) "
				    "== 0) break; if (idr_get_new_above(&idr, "
				    "(void *)(0x515000000000UL + 0x100UL*%d), "
				    "%d, &_id) == 0) break; } "
				    "printf(\"get_new(%%d) -> %%d\\n\", %d, "
				    "_id); }\n", j, recs[j].a, recs[j].a);
				break;
			case 2:
				printf("printf(\"remove(%%d) -> %%p\\n\", %d, "
				    "idr_remove(&idr, %d));\n",
				    recs[j].a, recs[j].a);
				break;
			case 3:
				printf("printf(\"replace(%%d) -> %%p\\n\", %d, "
				    "idr_replace(&idr, "
				    "(void *)0x5150000000AAUL, %d));\n",
				    recs[j].a, recs[j].a);
				break;
			}
		}
		printf("\n/* kept=%d of %ld */\n", kept, lim);
		return (0);
	} else {
		fprintf(stderr, "usage: %s fuzz [iters seed [lenient]] | "
		    "minimal | shrink <iters> <seed>\n", av[0]);
		return (1);
	}

	idr_init(&idr);
#ifndef RIG_SOFTASSERT
	signal(SIGABRT, abrt_handler);
#endif

	if (iters == -2) {
		int id;

		id = idr_alloc(&idr, (void *)0x515000290000UL, 289, 290, 0);
		printf("alloc(289,290) -> %d\n", id);
		printf("remove(287) [never allocated] -> %p\n",
		    idr_remove(&idr, 287));
		id = idr_alloc(&idr, (void *)0x5150002a0000UL, 290, 0, 0);
		printf("alloc(290,0) -> %d\n", id);
		printf("remove(287) [never allocated] -> %p\n",
		    idr_remove(&idr, 287));
		printf("remove(290) [live] -> %p\n", idr_remove(&idr, 290));
		printf("if you read this, the counters stayed >= 0; "
		    "the KKASSERT fires on the next reserve through a "
		    "negative node\n");
		check_counts(&idr, "minimal_panic");
		check_sweep(&idr);
	} else if (iters == -3) {
		/* Part B only (see df5688_minimal.h): 4-op duplicate */
		{ int id = idr_alloc(&idr, (void *)0x5150000f6000UL, 526, 0, 0);
		  printf("alloc(526,0) -> %d\n", id);
		  if (id >= 0) { mused[id] = 1; mval[id] = (void *)0x5150000f6000UL; } }

		printf("remove(525) [never allocated] -> %p\n",
		    idr_remove(&idr, 525));

		{ int id = idr_alloc(&idr, (void *)0x5150014700UL, 525, 532, 0);
		  printf("alloc(525,532) -> %d\n", id);
		  if (id >= 0) { mused[id] = 1; mval[id] = (void *)0x5150014700UL; } }

		{ int id = idr_alloc(&idr, (void *)0x5150016a00UL, 525, 0, 0);
		  printf("alloc(525,0) -> %d\n", id);
		  if (id >= 0) {
		      if (mused[id]) {
			  n_dup++;
			  diverged = 1;
			  printf(">>> DUPLICATE ID %d: idr_alloc returned an "
				 "id STILL ALLOCATED (ptr %p) — silently "
				 "overwritten with %p\n",
				 id, mval[id], (void *)0x5150016a00UL);
		      } else {
			  mused[id] = 1;
			  mval[id] = (void *)0x5150016a00UL;
		      }
		  } }
		check_counts(&idr, "minimal_dup");
	} else if (iters == -1) {
#include "df5688_minimal.h"
		check_counts(&idr, "minimal");
		check_sweep(&idr);
	} else {
#ifdef RIG_SOFTASSERT
		if (setjmp(rig_jmp) != 0) {
			/* a panic() fired mid-op: record it and continue;
			 * the model marks nothing for the aborted op */
			oph_add("PANIC(longjmp) recovered");
		}
#endif
		for (i = 0; i < iters && !diverged; i++) {
			uint32_t r = xshift(&rs);

			switch ((r >> 26) % 10) {
			case 0: case 1: case 2: case 3:
				do_alloc(&idr, &rs);
				break;
			case 4:
				do_getnew(&idr, &rs);
				break;
			case 5: case 6: case 7:
				do_remove(&idr, &rs);
				break;
			case 8:
				do_replace(&idr, &rs);
				break;
			case 9:
				if ((r & 0xff) == 0xff)
					do_remove_all(&idr);
				else if ((r & 0xff) == 0xfe)
					do_reinit(&idr);
				else
					do_find(&idr, &rs);
				break;
			}
			check_counts(&idr, "fuzz");
			if (++sweep % 64 == 0)
				check_sweep(&idr);
		}
	}

	if (!diverged) {
		check_sweep(&idr);
		check_counts(&idr, "final");
	}

	idr_destroy(&idr);

	printf("ops=%d dup=%d phantom=%d stale=%d badremove=%d "
	    "badreplace=%d chunks_live=%lu -> %s\n", oph_n, n_dup,
	    n_phantom_cnt, n_stale_ptr, n_badremove, n_badreplace,
	    rig_live_chunks, diverged ? "DIVERGED" : "clean");
	return (diverged ? 2 : 0);
}