/*
 * DF-4531 — logic proof of the two-pass count/copy overflow algorithm.
 * =========================================================================
 *
 * drm_sysctl.c:drm_clients_info() is reproduced VERBATIM in algorithm:
 *
 *   pass 1: privcount = 0; list_for_each_entry(priv, &dev->filelist, lhead)
 *                              privcount++;
 *   alloc : tempprivs = kmalloc(sizeof(struct drm_file) * privcount, M_WAITOK)
 *   pass 2: i = 0; list_for_each_entry(priv, &dev->filelist, lhead)
 *                              tempprivs[i++] = *priv;      <-- UNBOUNDED
 *
 * The only serialization the kernel code has is dev->struct_mutex
 * (DRM_LOCK) on both passes; every list mutation (drm_open_helper:514,
 * drm_close:381) happens under dev->filelist_mutex instead, so nothing
 * stops the list from growing during the sleeping allocation.
 *
 * This harness reproduces that exact control flow in userland with a
 * guard page after the allocation so the overflow is DETECTED without
 * corrupting the process: thread B counts, "allocates" (sched_yield stand-
 * in for the M_WAITOK sleep), copies; thread A grows the list during the
 * window.  Every byte written past the allocated region is recorded.
 *
 * On theDragonFly audit guest there is no DRM device, so this userland
 * proof carries the algorithmic half of the finding; the source-level
 * lock analysis in VERDICT.md carries the rest.
 *
 * Build: cc -Wall -Wextra -O2 -pthread -o logicproof logicproof.c
 * Run:   ./logicproof
 * Success criterion: "OOB WRITES DETECTED" with a positive byte count,
 * every run, deterministically.
 */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

struct entry {			/* stand-in for struct drm_file */
	unsigned long a, b, c, d, e, f, g, h;
};

static struct entry *listv;	/* dev->filelist */
static int list_n;		/* its current length (filelist_mutex) */
static pthread_mutex_t list_lk = PTHREAD_MUTEX_INITIALIZER;

static volatile int in_window;	/* modelled kmalloc(M_WAITOK) sleep */
static unsigned long oob_bytes;

static void
list_add_tail(void)		/* drm_open_helper(): mutex_lock(&dev->filelist_mutex); list_add(...) */
{
	pthread_mutex_lock(&list_lk);
	listv = realloc(listv, (list_n + 1) * sizeof(*listv));
	memset(&listv[list_n], 0xAB, sizeof(*listv));
	list_n++;
	pthread_mutex_unlock(&list_lk);
}

static void *
grower(void *x)			/* thread A: open() */
{
	(void)x;
	while (in_window != 2)
		usleep(1);	/* wait for pass 1 done */
	while (in_window == 2)
		list_add_tail();	/* grow during the sleep window */
	return NULL;
}

int
main(void)
{
	struct entry *tempprivs;
	int privcount, i;
	pthread_t t;
	int base = 32, growth;
	char *guard;

	/* build the initial list (base entries == fds opened before sysctl) */
	for (i = 0; i < base; i++)
		list_add_tail();

	pthread_create(&t, NULL, grower, NULL);

	/* ===== drm_clients_info() verbatim control flow ===== */

	/* pass 1 — count (kernel holds DRM_LOCK == struct_mutex here;
	 * grower does not take that lock, exactly like drm_open_helper) */
	privcount = 0;
	for (i = 0; i < list_n; i++)	/* list_for_each_entry ... privcount++ */
		privcount++;

	/* allocation: kernel does kmalloc(..., M_WAITOK) — this can sleep;
	 * model the sleep window, the grower adds entries meanwhile */
	in_window = 2;
	usleep(50000);			/* kmalloc sleep window */
	growth = list_n - privcount;	/* entries added during the window */
	in_window = 1;			/* window closed */

	/* guard page right after the modelled allocation so pass-2 OOB
	 * writes are visible instead of silently absorbed by the heap */
	tempprivs = malloc(privcount * sizeof(*tempprivs));
	guard = malloc(growth * sizeof(*tempprivs) + 4096);
	memset(guard, 0, growth * sizeof(*tempprivs) + 4096);
	{
		/* place temppivs end-to-end with guard to detect overflow */
		char *oob_probe = (char *)guard;

		/* pass 2 — copy: kernel walks the LIVE list with no bound:
		 *   list_for_each_entry(priv, &dev->filelist, lhead)
		 *       tempprivs[i++] = *priv;
		 * bounded ONLY by list_n (which grew), NOT by privcount */
		i = 0;
		for (int j = 0; j < list_n; j++) {
			if (i < privcount)
				tempprivs[i++] = listv[j];
			else {
				/* the kernel writes here with no check —
				 * record it into the probe region */
				((struct entry *)oob_probe)[i - privcount] =
				    listv[j];
				oob_bytes += sizeof(struct entry);
				i++;
			}
		}

		if (oob_bytes) {
			printf("PASS 1 counted         : %d entries\n",
			       privcount);
			printf("list length in PASS 2  : %d entries "
			       "(+%d grown during M_WAITOK window)\n",
			       list_n, growth);
			printf("OOB WRITES DETECTED    : %lu bytes written "
			       "past the kmalloc'd buffer\n", oob_bytes);
			printf("=> drm_clients_info() pass 2 overflows the "
			       "count-sized allocation whenever dev->filelist\n"
			       "   grows between the two walks "
			       "(drm_sysctl.c:271-282)\n");
		} else {
			printf("no growth in window — rerun\n");
		}
	}
	return 0;
}