/*
 * DF-5033 harness: race idr_find() against idr_grow()/idr_destroy() on the
 * byte-identical copy of sys/libkern/linux_idr.c (idr_test_core.c).
 *
 * The scenario mirrors the kernel path:
 *   reader  == amdgpu_bo_list_get()   (amdgpu_bo_list.c:167-176: calls
 *             idr_find() under rcu_read_lock() ONLY - no idr_token, no
 *             bo_list_lock)
 *   grower  == amdgpu_bo_list_ioctl() CREATE path (amdgpu_bo_list.c:283)
 *             -> idr_alloc() -> idr_grow() -> kfree(old nodes array)
 *
 * xkfree() poisons freed chunks with 0xDD and quarantines them, so any
 * idr_find() that dereferences a freed idr_nodes[] returns the poison value
 * 0xDDDDDDDDDDDDDDDD (nodes[id].allocated = 0xDDDDDDDD passes the !=0 test)
 * -> detected and reported.
 *
 * Readers park on a mutex/condvar gate while the idr is destroyed and
 * re-initialized (the kernel cannot race idr_destroy() against
 * amdgpu_bo_list_get(): drm core holds the drm_file during in-flight
 * ioctls).  Therefore every reported hit happens in a GROW phase, i.e. on a
 * kfree() issued by idr_grow(), which is exactly the kernel-reachable event.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <stdatomic.h>

#include "idr_test_core.c"	/* generated: kernel linux_idr.c algorithm */

#define NREADERS	4
#define PHASES		400	/* grow phases */
#define GROWTO		1023	/* entries per phase (2 grows: 255->511->1023) */

struct mycpu_s mycpu_stub;

/* ---- instrumented allocators: track size, poison+quarantine on free ---- */
struct ablk {
	void		*p;
	size_t		sz;
	struct ablk	*next;
};
static struct ablk *allocs;
static pthread_mutex_t amtx = PTHREAD_MUTEX_INITIALIZER;
static _Atomic long freed_chunks;

void *
xmalloc(size_t bytes)
{
	struct ablk *a = malloc(sizeof(*a) + bytes);
	void *p;

	memset(a, 0, sizeof(*a));
	a->p = a + 1;
	a->sz = bytes;
	pthread_mutex_lock(&amtx);
	a->next = allocs;
	allocs = a;
	pthread_mutex_unlock(&amtx);
	p = a->p;
	memset(p, 0, bytes);
	return p;
}

void
xkfree(void *ptr)
{
	struct ablk *a, **pp;

	if (ptr == NULL)
		return;
	pthread_mutex_lock(&amtx);
	for (pp = &allocs; (a = *pp) != NULL; pp = &a->next) {
		if (a->p == ptr) {
			*pp = a->next;
			break;
		}
	}
	pthread_mutex_unlock(&amtx);
	if (a == NULL) {
		fprintf(stderr, "xkfree: untracked %p\n", ptr);
		abort();
	}
	memset(ptr, 0xDD, a->sz);	/* poison: stale read -> 0xDD.. */
	atomic_fetch_add(&freed_chunks, 1);
	/* quarantine (leak intentionally): never reuse, poison persists */
}

/* ---- grower vs readers ---- */
static struct idr idr;
static _Atomic int running = 1;
static _Atomic long hits;		/* poison reads during GROW phases */
static _Atomic long anomalies;
static _Atomic long benign_null;

/* park gate: closed during destroy+init */
static pthread_mutex_t gate_mtx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t gate_cv = PTHREAD_COND_INITIALIZER;
static int gate_open = 1;
static int parked;

static void
gate_close(void)
{
	pthread_mutex_lock(&gate_mtx);
	gate_open = 0;
	while (parked < NREADERS)
		pthread_cond_wait(&gate_cv, &gate_mtx);
	pthread_mutex_unlock(&gate_mtx);
}

static void
gate_open_up(void)
{
	pthread_mutex_lock(&gate_mtx);
	gate_open = 1;
	pthread_cond_broadcast(&gate_cv);
	pthread_mutex_unlock(&gate_mtx);
}

static void *
reader(void *x)
{
	unsigned id = 1 + (unsigned)(uintptr_t)x * 8;

	while (atomic_load(&running)) {
		pthread_mutex_lock(&gate_mtx);
		while (!gate_open && atomic_load(&running)) {
			parked++;
			pthread_cond_broadcast(&gate_cv);
			while (!gate_open && atomic_load(&running))
				pthread_cond_wait(&gate_cv, &gate_mtx);
			parked--;
		}
		pthread_mutex_unlock(&gate_mtx);
		if (!atomic_load(&running))
			break;

		/*
		 * amdgpu_bo_list_get() equivalent: no lock of any kind
		 * around idr_find().
		 */
		{
			void *p = idr_find(&idr, id);

			if ((uintptr_t)p == 0xDDDDDDDDDDDDDDDDULL) {
				/* stale idr_nodes[] dereference */
				long h = atomic_fetch_add(&hits, 1);
				if (h < 5)
					fprintf(stderr,
					    "HIT#%ld: idr_find(id=%u) returned"
					    " poisoned 0xDDDDDDDDDDDDDDDD:"
					    " read of freed idr_nodes[]\n",
					    h + 1, id);
				atomic_store(&running, 0);
				gate_open_up();
			} else if (p == NULL) {
				atomic_fetch_add(&benign_null, 1);
			} else if (((uintptr_t)p >> 48) != 0x5100u) {
				atomic_fetch_add(&anomalies, 1);
				fprintf(stderr,
				    "ANOMALY: idr_find(id=%u) = %p "
				    "(not a stored tag)\n", id, p);
				atomic_store(&running, 0);
				gate_open_up();
			}
		}
	}
	return NULL;
}

static void *
grower(void *x)
{
	int ph, i, r;

	(void)x;
	for (ph = 0; ph < PHASES; ph++) {
		if (!atomic_load(&running))
			break;
		for (i = 0; i < GROWTO; i++) {
			r = idr_alloc(&idr, (void *)(0x5100000000000000ULL + i),
			    1, 0, 0);
			if (r < 0) {
				fprintf(stderr, "idr_alloc failed %d\n", r);
				atomic_store(&running, 0);
				return NULL;
			}
		}
		if (ph % 50 == 0)
			fprintf(stderr, "phase %d ok (2 idr_grow kfree's "
			    "done this phase)\n", ph);
		/* reset: park readers, destroy + re-init */
		gate_close();
		if (!atomic_load(&running)) {
			gate_open_up();
			break;
		}
		idr_destroy(&idr);
		idr_init(&idr);
		gate_open_up();
	}
	atomic_store(&running, 0);
	gate_open_up();
	return NULL;
}

int
main(int ac, char **av)
{
	pthread_t rt[NREADERS], gt;
	int i;
	long max_secs = ac > 1 ? atol(av[1]) : 0;

	if (max_secs == 0)
		max_secs = 600;
	setvbuf(stderr, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	idr_init(&idr);
	pthread_create(&gt, NULL, grower, NULL);
	for (i = 0; i < NREADERS; i++)
		pthread_create(&rt[i], NULL, reader, (void *)(uintptr_t)i);

	/* watchdog: force exit if it somehow wedges */
	{
		long s = 0;
		while (s < max_secs && atomic_load(&running))
			sleep(1);
		if (atomic_load(&running)) {
			fprintf(stderr, "WATCHDOG: forcing exit\n");
			atomic_store(&running, 0);
			gate_open_up();
		}
	}
	pthread_join(gt, NULL);
	for (i = 0; i < NREADERS; i++)
		pthread_join(rt[i], NULL);

	printf("RESULT: hits=%ld anomalies=%ld freed_chunks=%ld "
	    "benign_null=%ld\n",
	    atomic_load(&hits), atomic_load(&anomalies),
	    atomic_load(&freed_chunks), atomic_load(&benign_null));
	return atomic_load(&hits) ? 42 : 0;
}