/*
 * midi_kq_model.c -- userland harness modeling the DragonFly kernel path
 *
 *   devfs kqueue detach -> midi_filter_detach() [sys/dev/sound/midi/midi.c:932-941]
 *                       -> knote_remove()       [sys/kern/kern_event.c:1902-1909]
 *                       -> SLIST_REMOVE()       [sys/sys/queue.h:208-219]
 *
 * midi.c's single detach callback removes the knote from BOTH the read and
 * the write klist, but midi_kqfilter() (midi.c:901-930) inserted it into
 * exactly ONE (rkq for EVFILT_READ, wkq for EVFILT_WRITE).  knote_remove()
 * uses SLIST_REMOVE, which walks the list to find the element and has NO
 * membership guard: if the element is absent, `curelm` walks off the end,
 * becomes NULL, and `SLIST_NEXT(curelm, field)` dereferences NULL.
 * In the kernel this is a page fault on the kernel unmapped low page =>
 * panic.  In this model it is a SIGSEGV near address 0.
 *
 * The queue macros below are verbatim copies (modulo the _DIAGNOSTIC-only
 * QMD_SAVELINK/TRASHIT no-ops, which the kernel build does not enable) of
 * sys/sys/queue.h:191-219, and knote_remove() is a verbatim copy of
 * sys/kern/kern_event.c:1902-1909 with only the LWKT pool-token
 * acquisition/release omitted (an SMP exclusivity primitive with no
 * bearing on the single-threaded list semantics).
 *
 * Modes:
 *   empty   - buggy detach; other list EMPTY        (immediate NULL deref)
 *   peer    - buggy detach; other list holds another knote (walk, then NULL)
 *   fixed   - split detach callbacks (as in fix.diff); clean removal
 *   control - SLIST_REMOVE on a list that DOES contain the knote (sanity)
 *
 * Exit codes: 0 = clean, 99 = SIGSEGV (model of kernel panic).
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <ucontext.h>

/* ---------- sys/sys/queue.h:191-219 (verbatim) ---------- */
#define SLIST_HEAD(name, type)	struct name { struct type *slh_first; }
#define SLIST_ENTRY(type)	struct { struct type *sle_next; }
#define SLIST_FIRST(head)	((head)->slh_first)
#define SLIST_EMPTY(head)	((head)->slh_first == NULL)
#define SLIST_INSERT_HEAD(head, elm, field) do {			\
	SLIST_NEXT((elm), field) = SLIST_FIRST((head));		\
	SLIST_FIRST((head)) = (elm);				\
} while (0)
#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
#define SLIST_REMOVE_HEAD(head, field) do {				\
	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
} while (0)
#define SLIST_REMOVE(head, elm, type, field) do {			\
	if (SLIST_FIRST((head)) == (elm)) {				\
		SLIST_REMOVE_HEAD((head), field);			\
	}								\
	else {								\
		struct type *curelm = SLIST_FIRST((head));		\
		while (SLIST_NEXT(curelm, field) != (elm))		\
			curelm = SLIST_NEXT(curelm, field);		\
		SLIST_NEXT(curelm, field) =				\
		    SLIST_NEXT(SLIST_NEXT(curelm, field), field);	\
	}								\
} while (0)

/* ---------- kern_event.c knote/klist (minimal) ---------- */
#define EVFILT_READ	(-1)
#define EVFILT_WRITE	(-2)
#define KN_PROCESSING	0x0002	/* knote_acquire() sets this before detach */

struct knote {
	SLIST_ENTRY(knote)	kn_next;	/* on source klist */
	void			*kn_hook;	/* midi.c stores `m' here */
	int			kn_filter;
	int			kn_status;
};

SLIST_HEAD(klist, knote);

/* kern/kern_event.c:1902-1909 (verbatim minus pool token) */
static void
knote_remove(struct klist *klist, struct knote *kn)
{
	/* lwkt_getpooltoken(klist); */
	if (!(kn->kn_status & KN_PROCESSING)) {
		fprintf(stderr, "KKASSERT(kn->kn_status & KN_PROCESSING) "
		    "would fire first -- still a panic\n");
		abort();
	}
	SLIST_REMOVE(klist, kn, knote, kn_next);
	/* lwkt_relpooltoken(klist); */
}

/* ---------- snd_midi (kqueue members only) ---------- */
struct snd_midi {
	struct klist	rkq;		/* midi.c:106: struct kqinfo rkq */
	struct klist	wkq;		/* midi.c:106: struct kqinfo wkq */
};

/* ---------- midi.c:901-930 midi_kqfilter (modeled) ---------- */
static void
midi_kqfilter(struct snd_midi *m, struct knote *kn, int filter,
    struct klist **klistp)
{
	switch (filter) {
	case EVFILT_READ:
		kn->kn_hook = (void *)m;
		*klistp = &m->rkq;
		break;
	case EVFILT_WRITE:
		kn->kn_hook = (void *)m;
		*klistp = &m->wkq;
		break;
	default:
		abort();
	}
	kn->kn_status |= KN_PROCESSING;	/* knote_acquire() equivalent */
	SLIST_INSERT_HEAD(*klistp, kn, kn_next);
}

/* ---------- midi.c:932-941 midi_filter_detach (VERBATIM) ---------- */
static void
midi_filter_detach(struct knote *kn)
{
	struct snd_midi *m = (struct snd_midi *)kn->kn_hook;
	struct klist *rklist = &m->rkq;
	struct klist *wklist = &m->wkq;

	knote_remove(rklist, kn);
	knote_remove(wklist, kn);
}

/* ---------- fixed version (fix.diff): split detach callbacks ---------- */
static void
midi_filter_detach_read(struct knote *kn)
{
	struct snd_midi *m = (struct snd_midi *)kn->kn_hook;
	knote_remove(&m->rkq, kn);
}
static void
midi_filter_detach_write(struct knote *kn)
{
	struct snd_midi *m = (struct snd_midi *)kn->kn_hook;
	knote_remove(&m->wkq, kn);
}

static const char *g_mode;

static void
sigsegv(int sig, siginfo_t *si, void *uc)
{
	fprintf(stderr, "[%s] SIGSEGV at faulting address %p "
	    "(kernel equivalent: page fault on unmapped low page => panic)\n",
	    g_mode, si->si_addr);
	exit(99);
}

int
main(int argc, char **argv)
{
	struct snd_midi m;
	struct knote kn_r, kn_peer;
	struct klist *owner;
	struct sigaction sa;

	g_mode = argc > 1 ? argv[1] : "empty";
	memset(&m, 0, sizeof(m));
	memset(&kn_r, 0, sizeof(kn_r));
	memset(&kn_peer, 0, sizeof(kn_peer));

	memset(&sa, 0, sizeof(sa));
	sa.sa_sigaction = sigsegv;
	sa.sa_flags = SA_SIGINFO;
	sigaction(SIGSEGV, &sa, NULL);

	/*
	 * Exactly what an unprivileged user triggers with:
	 *   fd = open("/dev/midi0.1", O_RDWR);      (mode 0666, midi.c:364-366)
	 *   kq = kqueue();
	 *   kevent(kq, {fd, EVFILT_READ, EV_ADD}, 1, NULL, 0, NULL);
	 *   kevent(kq, {fd, EVFILT_READ, EV_DELETE}, ...) or close(kq)/exit;
	 * kern_event.c:706-708 / 1365-1368 -> knote_detach_and_drop() ->
	 * midi_filter_detach().
	 */
	midi_kqfilter(&m, &kn_r, EVFILT_READ, &owner);
	printf("[%s] knote inserted on rkq only (midi.c:911-916); "
	    "wkq empty=%d\n", g_mode, SLIST_EMPTY(&m.wkq));

	if (strcmp(g_mode, "peer") == 0) {
		SLIST_INSERT_HEAD(&m.wkq, &kn_peer, kn_next);
		kn_peer.kn_status |= KN_PROCESSING;
		printf("[%s] peer knote inserted on wkq (different knote!)\n",
		    g_mode);
	}

	if (strcmp(g_mode, "empty") == 0 || strcmp(g_mode, "peer") == 0) {
		printf("[%s] calling buggy midi_filter_detach()...\n", g_mode);
		fflush(stdout);
		midi_filter_detach(&kn_r);	/* walks off wkq => NULL deref */
		printf("[%s] NOT REACHED: detach returned\n", g_mode);
		return (1);
	} else if (strcmp(g_mode, "fixed") == 0) {
		printf("[%s] calling fixed detach_read()...\n", g_mode);
		fflush(stdout);
		midi_filter_detach_read(&kn_r);
		printf("[%s] clean: knote removed from its owning list, "
		    "no foreign-list walk\n", g_mode);
		return (0);
	} else if (strcmp(g_mode, "control") == 0) {
		/* sanity: SLIST_REMOVE behaves when membership holds */
		midi_filter_detach_read(&kn_r);
		printf("[%s] control ok\n", g_mode);
		return (0);
	}
	fprintf(stderr, "usage: %s empty|peer|fixed|control\n", argv[0]);
	return (2);
}