/*
 * DF-4335 — logic-model reproducer (no hardware required).
 *
 * Models the exact queue-state machine of sys/dev/raid/twa/tw_cl_io.c:
 *
 *   tw_cli_get_param()/tw_cli_set_param()  (tw_cl_io.c:781-814 / 899-931)
 *       error = tw_cli_submit_and_poll_request(req, 60s);
 *       if (error) goto out;
 *   out:
 *       ...
 *       if (req)
 *           tw_cli_req_q_insert_tail(req, TW_CLI_FREE_Q);   <-- (B)
 *
 *   tw_cli_submit_and_poll_request()  (tw_cl_io.c:947-1033)
 *       ... poll loop times out ...
 *       if (req->state == TW_CLI_REQ_STATE_PENDING) {
 *               tw_cli_req_q_remove_item(req, TW_CLI_PENDING_Q);
 *               ...
 *               tw_cli_req_q_insert_tail(req, TW_CLI_FREE_Q); <-- (A)
 *       }
 *       return (TW_OSL_ETIMEDOUT);
 *
 * On a poll timeout with the request still PENDING, (A) already returned the
 * request to the FREE queue, and the caller's unconditional (B) inserts the
 * SAME request a second time.  Every queue insert/remove in the real driver
 * is individually gen_lock-protected (tw_cl.h:270-313), so the second insert
 * is not lost: the node now appears at two positions of the same doubly
 * linked list, and two subsequent tw_cli_get_request() calls hand the same
 * `struct tw_cli_req_context` to two different owners (one of which may
 * still be tracked as BUSY by the firmware when the ETIMEDOUT request was
 * in the BUSY state instead — the dual-queue membership case).
 *
 * This program reproduces that state machine with the driver's own list
 * macros (copied verbatim from tw_cl_share.h) and shows:
 *   1. the FREE queue containing the same request twice, and
 *   2. two consumers receiving the identical request pointer,
 *   3. the BUSY-timeout variant: one request simultaneously linked into
 *      FREE_Q (via B) while still linked in BUSY_Q.
 *
 * Build:  cc -O2 -o poc_dblinsert poc_dblinsert.c
 * Run:    ./poc_dblinsert
 * Success criterion: "SAME REQUEST CONTEXT ISSUED TO TWO OWNERS" /
 *                     "REQUEST SIMULTANEOUSLY IN BUSY_Q AND FREE_Q".
 */
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/* ---- verbatim from sys/dev/raid/twa/tw_cl_share.h ---- */
struct tw_cl_link {
	struct tw_cl_link *next;
	struct tw_cl_link *prev;
};
#define TW_CL_Q_INIT(head) do { (head)->prev = (head)->next = head; } while (0)
#define TW_CL_Q_INSERT_TAIL(head, item) do {	\
	(item)->next = head;			\
	(item)->prev = (head)->prev;		\
	(head)->prev->next = item;		\
	(head)->prev = item;			\
} while (0)
#define TW_CL_Q_REMOVE_ITEM(head, item) do {	\
	(item)->prev->next = (item)->next;	\
	(item)->next->prev = (item)->prev;	\
} while (0)
#define TW_CL_Q_FIRST_ITEM(head) \
	(((head)->next != head) ? ((head)->next) : (void *)0)
/* ------------------------------------------------------ */

/* request states (tw_cl.h) */
enum { FREE, INIT, PENDING, BUSY, COMPLETE };

struct tw_cli_req_context {
	unsigned long		request_id;
	unsigned long		state;
	struct tw_cl_link	link;
};
#define TW_CL_STRUCT_OFFSET(struct_type, field) \
	(char *)(&((struct_type *)0)->field)
#define TW_CL_STRUCT_HEAD(addr, struct_type, field) \
	(struct_type *)((char *)addr - TW_CL_STRUCT_OFFSET(struct_type, field))

static struct tw_cl_link free_q, busy_q, pending_q;

/* tw_cli_req_q_remove_head (tw_cl.h:284-299) */
static struct tw_cli_req_context *
q_remove_head(struct tw_cl_link *head)
{
	struct tw_cli_req_context *req = NULL;
	struct tw_cl_link *link;
	if ((link = TW_CL_Q_FIRST_ITEM(head)) != NULL) {
		req = TW_CL_STRUCT_HEAD(link, struct tw_cli_req_context, link);
		TW_CL_Q_REMOVE_ITEM(head, &req->link);
	}
	return req;
}

/* tw_cli_req_q_insert_tail (tw_cl.h:270-278) */
static void q_insert_tail(struct tw_cli_req_context *req, struct tw_cl_link *head)
{
	TW_CL_Q_INSERT_TAIL(head, &req->link);
}

/*
 * The driver's own queue walkers (tw_cli_req_q_remove_head, drains) traverse
 * via ->next without any cycle guard.  After the double insert the victim's
 * ->next points at itself, so a walker that reaches it never terminates.
 * In the kernel that walker runs under ctlr->gen_lock (a spinlock!) -- the
 * corruption wedges every CPU that next touches any CL request queue.
 * We bound the walks here only so the reproducer terminates.
 */
static int q_length(struct tw_cl_link *head)
{
	int n = 0, guard = 1000;
	struct tw_cl_link *l;
	for (l = head->next; l != head; l = l->next) {
		if (++n > guard)
			return -1;	/* cycle: queue unwalkable */
	}
	return n;
}

static int on_queue(struct tw_cli_req_context *req, struct tw_cl_link *head)
{
	int n = 0;
	struct tw_cl_link *l;
	for (l = head->next; l != head; l = l->next) {
		if (++n > 1000)
			return 0;	/* cycle: unreachable past it */
		if (TW_CL_STRUCT_HEAD(l, struct tw_cli_req_context, link) == req)
			return 1;
	}
	return 0;
}

/* tw_cli_submit_and_poll_request, timeout tail (tw_cl_io.c:1014-1032) */
static int submit_and_poll_timeout(struct tw_cli_req_context *req)
{
	if (req->state == PENDING) {
		/* tw_cli_req_q_remove_item(req, TW_CLI_PENDING_Q) */
		TW_CL_Q_REMOVE_ITEM(&pending_q, &req->link);
		q_insert_tail(req, &free_q);		/* (A) */
	}
	/* BUSY case: request left linked in busy_q, per the documented
	 * contract (tw_cl_io.c:999-1006): "the caller is expected to NOT
	 * cleanup when TW_OSL_ETIMEDOUT is returned". */
	return 60;	/* TW_OSL_ETIMEDOUT */
}

/* tw_cli_get_param / tw_cli_set_param error path (tw_cl_io.c:804-814) */
static int get_param(struct tw_cli_req_context *req)
{
	int error = submit_and_poll_timeout(req);
	if (error)
		goto out;
	return 0;
out:
	/* (B) unconditional: */
	q_insert_tail(req, &free_q);
	return 1;
}

/* tw_cli_get_param / tw_cli_set_param error path WITH fix.diff applied:
 * caller no longer re-queues on ETIMEDOUT. */
static int get_param_fixed(struct tw_cli_req_context *req)
{
	int error = submit_and_poll_timeout(req);
	if (error)
		goto out;
	return 0;
out:
	if (error == 60)	/* TW_OSL_ETIMEDOUT: helper owns cleanup */
		return 1;
	q_insert_tail(req, &free_q);
	return 1;
}

int main(void)
{
	/* ===== Case 1: PENDING timeout -> FREE_Q double insert ===== */
	TW_CL_Q_INIT(&free_q); TW_CL_Q_INIT(&busy_q); TW_CL_Q_INIT(&pending_q);

	struct tw_cli_req_context pool[4];
	for (unsigned long i = 0; i < 4; i++) {
		memset(&pool[i], 0, sizeof(pool[i]));
		pool[i].request_id = i;
		q_insert_tail(&pool[i], &free_q);
	}

	/* consumer takes a request, marks it PENDING because fw cmd queue
	 * is full for the entire 60s poll window */
	struct tw_cli_req_context *victim = q_remove_head(&free_q);
	victim->state = PENDING;
	q_insert_tail(victim, &pending_q);

	get_param(victim);	/* returns ETIMEDOUT; victim inserted twice */

	int len = q_length(&free_q);
	printf("Case 1 (PENDING timeout): FREE_Q walk=%s\n",
	       len < 0 ? "INFINITE CYCLE (queue unwalkable; in-kernel this "
			"spins while holding the gen_lock spinlock)  <-- BUG"
		       : "clean");
	if (len >= 0 && len != 4)
		printf("  (queue length corrupted: %d)\n", len);

	/*
	 * Even before any walk spins, once the doubly-inserted victim reaches
	 * the head, EVERY tw_cli_req_q_remove_head() returns the SAME context:
	 * remove(v) splices v.next<->v.prev which are both v itself, so
	 * head->next keeps pointing at v.  Model a few consumers.
	 */
	struct tw_cli_req_context *owners[6];
	int n_owners = 0, dup = 0;
	for (int i = 0; i < 6; i++) {
		owners[i] = q_remove_head(&free_q);
		if (!owners[i])
			break;
		n_owners++;
		if (owners[i] == victim && ++dup == 2)
			break;
	}
	printf("  consumers received %d request(s); victim handed out %d time(s)"
	       " -> %s\n", n_owners, dup,
	       dup >= 2 ? "SAME REQUEST CONTEXT ISSUED TO TWO OWNERS  <-- BUG"
			: "distinct (no bug)");

	/* ===== Case 2: BUSY timeout -> BUSY_Q + FREE_Q membership ===== */
	TW_CL_Q_INIT(&free_q); TW_CL_Q_INIT(&busy_q); TW_CL_Q_INIT(&pending_q);
	for (unsigned long i = 0; i < 4; i++) {
		memset(&pool[i], 0, sizeof(pool[i]));
		pool[i].request_id = i;
		q_insert_tail(&pool[i], &free_q);
	}
	victim = q_remove_head(&free_q);
	victim->state = BUSY;
	q_insert_tail(victim, &busy_q);		/* submitted to firmware  */

	get_param(victim);	/* ETIMEDOUT; caller inserts to FREE_Q (B) */

	printf("Case 2 (BUSY timeout):   victim on BUSY_Q=%d on FREE_Q=%d -> %s\n",
	       on_queue(victim, &busy_q), on_queue(victim, &free_q),
	       (on_queue(victim, &busy_q) && on_queue(victim, &free_q))
	           ? "REQUEST SIMULTANEOUSLY IN BUSY_Q AND FREE_Q  <-- BUG"
	           : "single queue (no bug)");

	/* ===== Case 3: fix.diff applied -> both cases stay clean ===== */
	TW_CL_Q_INIT(&free_q); TW_CL_Q_INIT(&busy_q); TW_CL_Q_INIT(&pending_q);
	for (unsigned long i = 0; i < 4; i++) {
		memset(&pool[i], 0, sizeof(pool[i]));
		pool[i].request_id = i;
		q_insert_tail(&pool[i], &free_q);
	}
	victim = q_remove_head(&free_q);
	victim->state = PENDING;
	q_insert_tail(victim, &pending_q);
	get_param_fixed(victim);
	printf("Case 3 (PENDING, fixed): FREE_Q walk=%d victim_on_free=%d "
	       "(expect 4 / 1, no cycle)\n",
	       q_length(&free_q), on_queue(victim, &free_q));

	TW_CL_Q_INIT(&free_q); TW_CL_Q_INIT(&busy_q); TW_CL_Q_INIT(&pending_q);
	for (unsigned long i = 0; i < 4; i++) {
		memset(&pool[i], 0, sizeof(pool[i]));
		pool[i].request_id = i;
		q_insert_tail(&pool[i], &free_q);
	}
	victim = q_remove_head(&free_q);
	victim->state = BUSY;
	q_insert_tail(victim, &busy_q);
	get_param_fixed(victim);
	printf("Case 3 (BUSY, fixed):    victim on BUSY_Q=%d on FREE_Q=%d "
	       "(expect 1 / 0; reset-drain hook requeues once later)\n",
	       on_queue(victim, &busy_q), on_queue(victim, &free_q));
	return 0;
}