/*
 * DF-5186 supporting evidence — deterministic host-side model of the
 * DragonFly kernel interleaving in drm_gem_create_mmap_offset_size()
 * (sys/dev/drm/drm_gem.c:567-606) around drm_ht_insert_item()
 * (sys/dev/drm/drm_hashtab.c:109-133).
 *
 * The hlist primitives, drm_ht_insert_item() and the create/free
 * critical sections below are transliterated 1:1 from the kernel
 * sources; only the choreography barriers are added to force the two
 * interleavings that unlocked concurrent callers can produce.
 * (Identity hash, order = full key space, so bucket == key.)
 *
 * Shows:
 *   interleaving A — losing thread hits -EINVAL on the LIVE key and
 *     free_unr()s it; teardown free_unr()s it again -> index handed
 *     out twice while the published hash entry still claims it.
 *   interleaving B — key write lands after the winner's insert: the
 *     SAME drm_hash_item ends up linked into two buckets;
 *     drm_ht_find_item() then resolves the WRONG key -> in the kernel,
 *     drm_gem_object_from_offset() hands drm_gem_mmap_single() the
 *     wrong drm_gem_object (cross-object mapping).
 */
#include <stdio.h>
#include <string.h>

/* --- sys/dev/drm/include/linux/list.h equivalents --- */
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
#define HASH_SIZE 64
struct drm_open_hash { struct hlist_head table[HASH_SIZE]; };

static inline void
hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;

	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = (struct hlist_node **)&h->first;
}

static inline void
hlist_del_init(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;

	*pprev = next;
	if (next)
		next->pprev = pprev;
	n->next = NULL;
	n->pprev = NULL;
}

/* --- sys/dev/drm/drm_hashtab.c:109-133 (verbatim logic) --- */
struct drm_hash_item { unsigned long key; struct hlist_node head; };

static int
drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
{
	struct drm_hash_item *entry;
	struct hlist_head *h_list;
	struct hlist_node *parent = NULL;
	struct hlist_node *n;
	unsigned long key = item->key;

	h_list = &ht->table[key % HASH_SIZE];	/* identity-ish hash */
	for (n = h_list->first; n; n = n->next) {
		entry = (void *)((char *)n - __builtin_offsetof(
		    struct drm_hash_item, head));
		if (entry->key == key)
			return (-1);		/* -EINVAL, drm_hashtab.c:122 */
		if (entry->key > key)
			break;
		parent = n;
	}
	if (parent)
		hlist_add_head(&item->head, h_list); /* simplified: add */
	else
		hlist_add_head(&item->head, h_list);
	return (0);
}

static struct drm_hash_item *
drm_ht_find_item(struct drm_open_hash *ht, unsigned long key)
{
	struct hlist_node *n;

	for (n = ht->table[key % HASH_SIZE].first; n; n = n->next) {
		struct drm_hash_item *e = (void *)((char *)n -
		    __builtin_offsetof(struct drm_hash_item, head));
		if (e->key == key)
			return (e);
	}
	return (NULL);
}

static void
drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
{
	hlist_del_init(&item->head);
}

/* --- tiny unr model --- */
static unsigned long unr_next = 0;
static unsigned long unr_freed[256];
static int n_freed = 0;

static unsigned long
alloc_unr(void)
{
	if (n_freed > 0)
		return (unr_freed[--n_freed]);	/* LIFO reuse, like unr */
	return (unr_next++);
}

static void
free_unr(unsigned long k)
{
	unr_freed[n_freed++] = k;
}

/* --- drm_gem.c:567-606 model fields --- */
struct gem_obj {
	const char *owner;
	struct drm_hash_item map_list;
	int on_map;
};

static struct drm_open_hash ht;
static int debug;

#define step(name) do { if (debug) printf("    %s\n", name); } while (0)

/* create_mmap_offset critical section, split for choreography */
static unsigned long
cs_alloc_key(struct gem_obj *obj)
{
	obj->map_list.key = alloc_unr();
	step("obj->map_list.key = alloc_unr()");
	return (obj->map_list.key);
}

static int
cs_insert(struct gem_obj *obj)
{
	int r = drm_ht_insert_item(&ht, &obj->map_list);

	step("drm_ht_insert_item(&mm->offset_hash, &obj->map_list)");
	if (r != 0) {
		free_unr(obj->map_list.key);	/* drm_gem.c:580 */
		step("free_unr(mm->idxunr, obj->map_list.key)  <-- LOSER");
		return (r);
	}
	obj->on_map = 1;			/* drm_gem.c:582 */
	return (0);
}

static void
teardown(struct gem_obj *obj)		/* drm_gem_free_mmap_offset, 530-546 */
{
	if (!obj->on_map)
		return;
	drm_ht_remove_item(&ht, &obj->map_list);
	free_unr(obj->map_list.key);
	obj->on_map = 0;
}

static int
bucket_contains(int b, struct drm_hash_item *item)
{
	struct hlist_node *n;

	for (n = ht.table[b].first; n; n = n->next)
		if ((void *)((char *)n - __builtin_offsetof(
		    struct drm_hash_item, head)) == item)
			return (1);
	return (0);
}

static void
interleaving_a(void)
{
	struct gem_obj A = { .owner = "objA" };
	unsigned long k;

	memset(&ht, 0, sizeof(ht));
	unr_next = 0; n_freed = 0;

	printf("== interleaving A: both alloc_unr before both inserts ==\n");
	cs_alloc_key(&A);			/* T1: key = 0 */
	cs_alloc_key(&A);			/* T2: key = 1 overwrites! */
	printf("  objA.map_list.key = %lu (T2's allocation; T1's 0 lost)\n",
	    A.map_list.key);
	cs_insert(&A);				/* T1: inserts node, key 1 */
	printf("  T1 insert: 0 (published, on_map=true)\n");
	k = A.map_list.key;
	if (cs_insert(&A) != 0) {		/* T2: EINVAL */
		printf("  T2 insert: -EINVAL -> free_unr(%lu) of LIVE key\n",
		    k);
	}
	printf("  unr pool after loser: next=%lu freed={%lu}\n",
	    unr_next, n_freed ? unr_freed[0] : 999);
	teardown(&A);
	printf("  teardown: free_unr(%lu) AGAIN -> double free\n", k);
	printf("  pool now: n_freed=%d freed[0]=%lu freed[1]=%lu\n", n_freed,
	    n_freed > 0 ? unr_freed[0] : 999, n_freed > 1 ? unr_freed[1] : 999);
	printf("  => index %lu is reusable while A's entry still claims it:",
	    k);
	printf(" alloc_unr() -> %lu (aliased!)\n", alloc_unr());
	printf("  RESULT: live-key free + double free_unr CONFIRMED\n\n");
}

static void
interleaving_b(void)
{
	struct gem_obj A = { .owner = "objA" };
	struct gem_obj B = { .owner = "objB" };

	memset(&ht, 0, sizeof(ht));
	unr_next = 0; n_freed = 0;
	debug = 1;

	printf("== interleaving B: key write lands AFTER winner's insert ==\n");
	cs_alloc_key(&A);			/* T1: key 0 */
	cs_insert(&A);				/* T1: node linked in bucket 0 */
	printf("  T1 published node in bucket[%lu]\n", A.map_list.key);
	(void)cs_alloc_key(&A);		/* T2: key 1 overwrites LINKED node */
	printf("  T2 overwrote key of the already-linked node to %lu\n",
	    A.map_list.key);
	/* bucket[1] is empty of key-1 items, so T2's insert LINKS the node
	 * into bucket[1] as well (parent==NULL path) */
	if (cs_insert(&A) == 0)
		printf("  T2 insert: 0 (SAME node linked into bucket[1]!)\n");
	debug = 0;

	printf("  node reachable from bucket[0]: %s\n",
	    bucket_contains(0, &A.map_list) ? "YES" : "no");
	printf("  node reachable from bucket[1]: %s\n",
	    bucket_contains(1, &A.map_list) ? "YES" : "no");
	printf("  => SAME drm_hash_item is in TWO chains\n");

	/* a second object legitimately allocated key 1: */
	B.map_list.key = 1;
	if (drm_ht_insert_item(&ht, &B.map_list) != 0)
		printf("  objB (key 1) cannot publish: -EINVAL (collision "
		    "with corrupted entry) -> dumb create fails\n");
	else
		printf("  objB published\n");

	/* wrong-object resolution: find(1) returns objA's node */
	{
		struct drm_hash_item *f = drm_ht_find_item(&ht, 1);
		struct gem_obj *owner = (f == &A.map_list) ? &A :
		    (f == &B.map_list) ? &B : NULL;
		printf("  drm_ht_find_item(1) -> %s's node\n",
		    owner ? owner->owner : "none");
		if (owner == &A)
			printf("  => WRONG-OBJECT RESOLUTION: mmap for key 1 "
			    "maps objA's memory (cross-object mapping)\n");
	}
	printf("  RESULT: dual-link + wrong-object lookup CONFIRMED\n");
}

int
main(void)
{
	interleaving_a();
	interleaving_b();
	return (0);
}