/*
 * radeon_sa_uaf.c - deterministic userspace proof of the dangling-fence UAF
 * in DragonFlyBSD sys/dev/drm/radeon/radeon_sa.c (radeon_sa_bo_new /
 * radeon_sa_bo_next_hole), which is missing the `fences[i] = NULL;`
 * per-scan initialization fixed upstream by Linux commit 0381ac3ca2e7
 * ("drm/radeon: Initialize fences array entries in radeon_sa_bo_next_hole",
 *  Xiaohui Zhang, 2022; amdgpu twin: 6a15f3ff19a8).
 *
 * The allocator logic below (radeon_sa_bo_remove_locked, radeon_sa_bo_try_free,
 * radeon_sa_bo_hole_soffset/eoffset, radeon_sa_bo_try_alloc, radeon_sa_event,
 * radeon_sa_bo_next_hole, and the inner loop of radeon_sa_bo_new) is ported
 * 1:1 from sys/dev/drm/radeon/radeon_sa.c lines 142-374 of the audit tree.
 * Only the following are substituted (they cannot change the algorithm):
 *   - linux list.h  -> minimal list_head implementation with identical
 *     semantics (list_add adds AFTER head, list_del_init, etc.)
 *   - lockmgr/waitqueue plumbing -> dropped; the bug is entirely
 *     single-threaded (the fence is destroyed by the *same* thread between
 *     two iterations of the same locked inner loop).
 *   - radeon_fence_* -> instrumented refcount layer: refcount==0 marks the
 *     object dead (model of kfree() in dma_fence_release,
 *     sys/dev/drm/linux_fence.c:43-51); ref/unref of a dead object is
 *     reported exactly as the kernel UAF write / double-free it models.
 *   - GPU progress -> a check-counting simulator that flips the target
 *     fence to "signaled" on its 3rd radeon_fence_signaled() check,
 *     i.e. after it was borrowed into fences[] by one next_hole() call
 *     and before the next iteration inspects it (exactly the window the
 *     upstream commit message describes).
 *
 * Scenario (deterministic, no race needed):
 *   ring GFX: X[0,1024)   freed-by-owner, fence F pending (refcount 1,
 *             the state radeon_ib_free leaves behind: radeon_ib.c:95-98)
 *   ring DMA: A[1024,2048) fence signaled, B[2048,3072) fence signaled,
 *             Z[3072,4096) fence pending
 *   allocation request: 3500 bytes (does not fit any hole)
 *
 * Build (baseline):  cc -O2 -o radeon_sa_uaf        radeon_sa_uaf.c
 * Build (fixed):     cc -O2 -DFIXED -o radeon_sa_uaf_fixed radeon_sa_uaf.c
 *                     (adds exactly the upstream one-liner `fences[i]=NULL;`)
 *
 * Expected baseline output: UAF-REF, UAF-WAIT, DOUBLE-FREE events, exit 42.
 * Expected fixed output:    clean allocation failure, exit 0.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define RADEON_NUM_RINGS 8
/* rings used by the scenario */
#define RING_GFX 0
#define RING_DMA 1

/* ------------------------------------------------------------------ */
/* minimal linux-style list (semantics copied from                     */
/* sys/dev/drm/include/linux/list.h)                                   */
struct list_head {
	struct list_head *prev, *next;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0)
#define container_of(ptr, type, member) \
	((type *)((char *)(ptr) - offsetof(type, member)))
#define offsetof(t, m) __builtin_offsetof(t, m)
#define list_entry(ptr, type, member)	container_of(ptr, type, member)
#define list_first_entry(ptr, type, member)	list_entry((ptr)->next, type, member)

static inline void __list_add(struct list_head *ne,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = ne;
	ne->next = next;
	ne->prev = prev;
	prev->next = ne;
}
/* list_add: insert NEW right after HEAD (linux semantics) */
static inline void list_add(struct list_head *ne, struct list_head *head)
{
	__list_add(ne, head, head->next);
}
static inline void list_add_tail(struct list_head *ne, struct list_head *head)
{
	__list_add(ne, head->prev, head);
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}
static inline void list_del_init(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	INIT_LIST_HEAD(entry);
}
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
#define list_for_each_entry_safe_from(pos, n, head, member)		\
	for (n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/* ------------------------------------------------------------------ */
/* instrumented fence layer                                            */
struct radeon_fence {
	int	id;
	int	ring;
	int	refcount;	/* models struct dma_fence refcount   */
	bool	signaled;
	bool	dead;		/* models kfree() in dma_fence_release */
	int	checks;		/* radeon_fence_signaled() call count  */
};

static struct radeon_fence *target_fence;	/* the one the "GPU" completes */

struct radeon_sa_manager;

struct radeon_sa_bo {
	struct list_head		olist;
	struct list_head		flist;
	struct radeon_sa_manager	*manager;
	unsigned			soffset;
	unsigned			eoffset;
	struct radeon_fence		*fence;
};

struct radeon_sa_manager {
	unsigned		size;
	struct list_head	*hole;
	struct list_head	flist[RADEON_NUM_RINGS];
	struct list_head	olist;
};

static int uaf_refs, uaf_waits, double_frees;
static int log_on = 1;
#ifdef TRACE
#define STAGE(x) do { fprintf(stderr, "[%s]\n", x); } while (0)
#else
#define STAGE(x) do { } while (0)
#endif
static void report(const char *ev, struct radeon_fence *f, const char *where)
{
	if (log_on)
		printf("  *** %-10s fence F%d (refcount=%d) at %s\n",
		       ev, f->id, f->refcount, where);
}

/*
 * Model of GPU progress: fences complete asynchronously with respect to
 * the suballocator loop (the GPU IRQ updates last_seq without holding
 * sa_manager->wq.lock - see radeon_fence.c radeon_fence_seq_signaled).
 * The target fence flips to signaled on its 3rd check: check #1/#2 happen
 * inside the first next_hole() call (try_free + the un-signaled borrow),
 * check #3 happens in the NEXT iteration - after which the same thread
 * frees the fence via radeon_sa_bo_remove_locked.
 */
static void sim_gpu_progress(struct radeon_fence *f)
{
	if (f == target_fence && ++f->checks >= 3)
		f->signaled = true;
}

static bool radeon_fence_signaled(struct radeon_fence *fence)
{
	if (!fence)
		return true;
	sim_gpu_progress(fence);
	return fence->signaled;
}

static struct radeon_fence *radeon_fence_ref(struct radeon_fence *fence)
{
	if (fence == NULL)			/* dma_fence_get(NULL) no-op */
		return NULL;
	if (fence->dead) {			/* UAF write on kfree'd slab */
		report("UAF-REF", fence, "radeon_sa_bo_new:352 fence_ref");
		uaf_refs++;
	}
	fence->refcount++;
	return fence;
}

static void radeon_fence_unref(struct radeon_fence **fence)
{
	struct radeon_fence *tmp = *fence;

	*fence = NULL;
	if (tmp) {
		if (tmp->dead) {		/* double free of kfree'd slab */
			report("DOUBLE-FREE", tmp,
			       "radeon_sa_bo_new:358 fence_unref");
			double_frees++;
			return;
		}
		if (--tmp->refcount == 0) {
			tmp->dead = true;	/* kfree() */
			if (log_on)
				printf("    [fence F%d refcount 0 -> kfree]\n",
				       tmp->id);
		}
	}
}

/* ------------------------------------------------------------------ */
/* ==== ported 1:1 from sys/dev/drm/radeon/radeon_sa.c:142-152 ====    */
static void radeon_sa_bo_remove_locked(struct radeon_sa_bo *sa_bo)
{
	struct radeon_sa_manager *sa_manager = sa_bo->manager;
	if (sa_manager->hole == &sa_bo->olist) {
		sa_manager->hole = sa_bo->olist.prev;
	}
	list_del_init(&sa_bo->olist);
	list_del_init(&sa_bo->flist);
	radeon_fence_unref(&sa_bo->fence);
	free(sa_bo);
}

/* ==== ported 1:1 from radeon_sa.c:154-168 ==== */
static void radeon_sa_bo_try_free(struct radeon_sa_manager *sa_manager)
{
	struct radeon_sa_bo *sa_bo, *tmp;

	if (sa_manager->hole->next == &sa_manager->olist)
		return;

	sa_bo = list_entry(sa_manager->hole->next, struct radeon_sa_bo, olist);
	list_for_each_entry_safe_from(sa_bo, tmp, &sa_manager->olist, olist) {
		if (sa_bo->fence == NULL || !radeon_fence_signaled(sa_bo->fence)) {
			return;
		}
		radeon_sa_bo_remove_locked(sa_bo);
	}
}

/* ==== ported 1:1 from radeon_sa.c:170-188 ==== */
static inline unsigned radeon_sa_bo_hole_soffset(struct radeon_sa_manager *sa_manager)
{
	struct list_head *hole = sa_manager->hole;

	if (hole != &sa_manager->olist) {
		return list_entry(hole, struct radeon_sa_bo, olist)->eoffset;
	}
	return 0;
}

static inline unsigned radeon_sa_bo_hole_eoffset(struct radeon_sa_manager *sa_manager)
{
	struct list_head *hole = sa_manager->hole;

	if (hole->next != &sa_manager->olist) {
		return list_entry(hole->next, struct radeon_sa_bo, olist)->soffset;
	}
	return sa_manager->size;
}

/* ==== ported 1:1 from radeon_sa.c:190-212 ==== */
static bool radeon_sa_bo_try_alloc(struct radeon_sa_manager *sa_manager,
				   struct radeon_sa_bo *sa_bo,
				   unsigned size, unsigned align)
{
	unsigned soffset, eoffset, wasted;

	soffset = radeon_sa_bo_hole_soffset(sa_manager);
	eoffset = radeon_sa_bo_hole_eoffset(sa_manager);
	wasted = (align - (soffset % align)) % align;

	if ((eoffset - soffset) >= (size + wasted)) {
		soffset += wasted;

		sa_bo->manager = sa_manager;
		sa_bo->soffset = soffset;
		sa_bo->eoffset = soffset + size;
		list_add(&sa_bo->olist, sa_manager->hole);
		INIT_LIST_HEAD(&sa_bo->flist);
		sa_manager->hole = &sa_bo->olist;
		return true;
	}
	return false;
}

/* ==== ported 1:1 from radeon_sa.c:224-245 ==== */
static bool radeon_sa_event(struct radeon_sa_manager *sa_manager,
			    unsigned size, unsigned align)
{
	unsigned soffset, eoffset, wasted;
	int i;

	for (i = 0; i < RADEON_NUM_RINGS; ++i) {
		if (!list_empty(&sa_manager->flist[i])) {
			return true;
		}
	}

	soffset = radeon_sa_bo_hole_soffset(sa_manager);
	eoffset = radeon_sa_bo_hole_eoffset(sa_manager);
	wasted = (align - (soffset % align)) % align;

	if ((eoffset - soffset) >= (size + wasted)) {
		return true;
	}

	return false;
}

/* ==== ported 1:1 from radeon_sa.c:247-310 ====                  */
/* FIXED mode adds exactly the upstream fix from Linux 0381ac3ca2e7 */
static bool radeon_sa_bo_next_hole(struct radeon_sa_manager *sa_manager,
				   struct radeon_fence **fences,
				   unsigned *tries)
{
	struct radeon_sa_bo *best_bo = NULL;
	unsigned i, soffset, best, tmp;

	/* if hole points to the end of the buffer */
	if (sa_manager->hole->next == &sa_manager->olist) {
		/* try again with its beginning */
		sa_manager->hole = &sa_manager->olist;
		return true;
	}

	soffset = radeon_sa_bo_hole_soffset(sa_manager);
	/* to handle wrap around we add sa_manager->size */
	best = sa_manager->size * 2;
	/* go over all fence list and try to find the closest sa_bo
	 * of the current last
	 */
	for (i = 0; i < RADEON_NUM_RINGS; ++i) {
		struct radeon_sa_bo *sa_bo;

#ifdef FIXED
		fences[i] = NULL;	/* <-- the missing upstream fix */
#endif

		if (list_empty(&sa_manager->flist[i])) {
			continue;
		}

		sa_bo = list_first_entry(&sa_manager->flist[i],
					 struct radeon_sa_bo, flist);

		if (!radeon_fence_signaled(sa_bo->fence)) {
			fences[i] = sa_bo->fence;	/* borrowed, no refcount! */
			continue;
		}

		/* limit the number of tries each ring gets */
		if (tries[i] > 2) {
			continue;
		}

		tmp = sa_bo->soffset;
		if (tmp < soffset) {
			/* wrap around, pretend it's after */
			tmp += sa_manager->size;
		}
		tmp -= soffset;
		if (tmp < best) {
			/* this sa bo is the closest one */
			best = tmp;
			best_bo = sa_bo;
		}
	}

	if (best_bo) {
		++tries[best_bo->fence->ring];
		sa_manager->hole = best_bo->olist.prev;

		/* we knew that this one is signaled,
		   so it's save to remote it */
		radeon_sa_bo_remove_locked(best_bo);
		return true;
	}
	return false;
}

/* model of radeon_fence_wait_any (radeon_fence.c:604): reads fence->seq */
static int radeon_fence_wait_any(struct radeon_fence **fences)
{
	int i, nr = 0, any_signaled = 0;

	for (i = 0; i < RADEON_NUM_RINGS; ++i) {
		if (!fences[i])
			continue;
		nr++;
		if (fences[i]->dead) {		/* UAF read */
			report("UAF-WAIT", fences[i],
			       "radeon_sa_bo_new:356 fence_wait_any");
			uaf_waits++;
			any_signaled = 1;	/* stale seq looks done */
		} else if (fences[i]->signaled) {
			any_signaled = 1;
		}
	}
	if (nr == 0)
		return -35;	/* -ENOENT */
	return any_signaled ? 0 : -35;	/* pretend timeout->signaled */
}

/* ==== inner/outer loop of radeon_sa_bo_new, ported 1:1 from
 * ==== radeon_sa.c:312-374 (lock plumbing dropped, see file header) */
static int radeon_sa_bo_new(struct radeon_sa_manager *sa_manager,
			    struct radeon_sa_bo **sa_bo,
			    unsigned size, unsigned align)
{
	struct radeon_fence *fences[RADEON_NUM_RINGS];
	unsigned tries[RADEON_NUM_RINGS];
	int i, r;

	*sa_bo = calloc(1, sizeof(struct radeon_sa_bo));
	if ((*sa_bo) == NULL)
		return -12;		/* -ENOMEM */
	(*sa_bo)->manager = sa_manager;
	(*sa_bo)->fence = NULL;
	INIT_LIST_HEAD(&(*sa_bo)->olist);
	INIT_LIST_HEAD(&(*sa_bo)->flist);

	/* --- sa_manager->wq.lock held (single thread: all under one lock) */
	do {
		STAGE("outer-iteration");
		for (i = 0; i < RADEON_NUM_RINGS; ++i) {
			fences[i] = NULL;
			tries[i] = 0;
		}

		do {
			STAGE("inner: try_free");
			radeon_sa_bo_try_free(sa_manager);

			STAGE("inner: try_alloc");
			if (radeon_sa_bo_try_alloc(sa_manager, *sa_bo,
						   size, align)) {
				/* --- unlock --- */
				return 0;
			}

			/* see if we can skip over some allocations */
			STAGE("inner: next_hole");
		} while (radeon_sa_bo_next_hole(sa_manager, fences, tries));

		STAGE("ref loop (sa.c:352-353)");
		for (i = 0; i < RADEON_NUM_RINGS; ++i) {
			STAGE("ref-loop-entry");
			radeon_fence_ref(fences[i]);	/* <-- UAF here */
		}

		/* --- unlock --- */
		STAGE("wait_any (sa.c:356)");
		r = radeon_fence_wait_any(fences);
		STAGE("unref loop (sa.c:357-358)");
		for (i = 0; i < RADEON_NUM_RINGS; ++i)
			radeon_fence_unref(&fences[i]); /* <-- double-free */
		/* --- lock --- */

		/* terminate the model after the decisive pass:
		 * r==0 would loop; -ENOENT would wait. Either way the
		 * UAF/double-free (if present) already happened above.
		 */
		r = -513;	/* -ERESTARTSYS: interrupted */

	} while (!r);

	free(*sa_bo);
	*sa_bo = NULL;
	return r;
}

/* ------------------------------------------------------------------ */
static struct radeon_sa_bo *place(struct radeon_sa_manager *m, unsigned so,
				  unsigned eo, int ring, struct radeon_fence *f)
{
	struct radeon_sa_bo *b = calloc(1, sizeof(*b));

	b->soffset = so;
	b->eoffset = eo;
	b->fence = radeon_fence_ref(f);	/* sa_bo takes its own reference */
	b->manager = m;
	INIT_LIST_HEAD(&b->olist);
	INIT_LIST_HEAD(&b->flist);
	list_add_tail(&b->olist, &m->olist);
	list_add_tail(&b->flist, &m->flist[ring]);
	return b;
}

int main(void)
{
	struct radeon_sa_manager mgr;
	struct radeon_fence *F, *FA, *FB, *FZ;
	struct radeon_sa_bo *out = NULL;
	int i, r;

	setvbuf(stdout, NULL, _IONBF, 0);

	printf("DF-4927 radeon_sa fence-borrow UAF - %s mode\n",
#ifdef FIXED
	       "FIXED (upstream 0381ac3ca2e7 guard applied)"
#else
	       "BASELINE (DragonFly sys/dev/drm/radeon/radeon_sa.c as-is)"
#endif
	       );
	printf("scenario: X[0,1024)GFX/F-pending  A[1024,2048)DMA/sig  "
	       "B[2048,3072)DMA/sig  Z[3072,4096)DMA/pending; request 3500B\n");

	memset(&mgr, 0, sizeof(mgr));
	mgr.size = 4096;
	mgr.hole = &mgr.olist;
	INIT_LIST_HEAD(&mgr.olist);
	for (i = 0; i < RADEON_NUM_RINGS; i++)
		INIT_LIST_HEAD(&mgr.flist[i]);

	F  = &(struct radeon_fence){ .id = 1, .ring = RING_GFX, .refcount = 1 };
	FA = &(struct radeon_fence){ .id = 2, .ring = RING_DMA, .refcount = 1, .signaled = true };
	FB = &(struct radeon_fence){ .id = 3, .ring = RING_DMA, .refcount = 1, .signaled = true };
	FZ = &(struct radeon_fence){ .id = 4, .ring = RING_DMA, .refcount = 1 };
	target_fence = F;	/* GPU completes F between borrow and re-check */

	/* emulate radeon_ib_free(): the owner frees the sa_bo passing its
	 * fence; radeon_sa_bo_free takes a reference for the sa_bo
	 * (sa.c:388) and the owner then drops its own (radeon_ib.c:98),
	 * leaving the sa_bo's reference as the LAST one (refcount == 1). */
	place(&mgr,    0, 1024, RING_GFX, F);
	place(&mgr, 1024, 2048, RING_DMA, FA);
	place(&mgr, 2048, 3072, RING_DMA, FB);
	place(&mgr, 3072, 4096, RING_DMA, FZ);
	radeon_fence_unref(&F);
	radeon_fence_unref(&FA);
	radeon_fence_unref(&FB);
	radeon_fence_unref(&FZ);

	printf("sa_bo_new(3500, 256):\n");
	log_on = 1;
	r = radeon_sa_bo_new(&mgr, &out, 3500, 256);
	printf("radeon_sa_bo_new -> %d (%s)\n", r,
	       r == 0 ? "allocated" : "would block/fail");

	printf("\n===== RESULT =====\n");
	printf("UAF fence_ref     (sa.c:352-353): %d\n", uaf_refs);
	printf("UAF fence_wait    (sa.c:356)    : %d\n", uaf_waits);
	printf("double fence_free (sa.c:357-358): %d\n", double_frees);
	if (uaf_refs || uaf_waits || double_frees) {
		printf("VERDICT: UAF/double-free REPRODUCED on the ported "
		       "allocator logic\n");
		return 42;
	}
	printf("VERDICT: clean - no dangling fence dereference\n");
	return 0;
}