/*
 * DF-5146 -- in-kernel demonstration, using the REAL, UNMODIFIED
 * sys/dev/drm/drm_hashtab.c compiled into this module (see Makefile).
 *
 * What it shows (all output prefixed HTCOLLAPSE:):
 *   1. drm_ht_create(&ht, 12)  -- the exact order used by drm_drv.c:603
 *      (dev->map_hash) and drm_gem.c:148 (mm->offset_hash).
 *   2. Insert N items whose keys mimic drm_gem.c:576 (alloc_unr():
 *      sequential 1..N). Per-chunk wall time grows linearly with the
 *      number already inserted => O(n^2) total, because every key hashes
 *      to bucket 0 and the chain is kept sorted (drm_hashtab.c:117-126).
 *   3. Bucket occupancy: exactly ONE non-empty bucket (#0) holding all
 *      N items; 4095 buckets empty. With the fixed linux/hash.h
 *      (make FIX=1), occupancy spreads across ~4096 buckets and insert
 *      time is flat.
 *   4. Correctness is NOT broken: exact-key finds still succeed
 *      (sorted chain), duplicate insert still -EINVAL, remove/re-insert
 *      cycles fine => impact is CPU (local DoS), not memory corruption.
 */
#include <sys/param.h>
#include <sys/kernel.h>
#include <sys/systm.h>
#include <sys/module.h>
#include <sys/time.h>
#include <sys/stdint.h>
#include <drm/drm_hashtab.h>

/*
 * drm_hashtab.c's DRM_ERROR() resolves to drm_err(), which normally
 * lives in the drm module. Provide a local definition so this harness
 * is self-contained (drm.ko is NOT loaded on this guest).
 */
void		drm_err(const char *func, const char *format, ...);
void		drm_dbg(const char *func, unsigned int category,
		    const char *format, ...);

/* DRM_DEBUG() backend used by drm_ht_verbose_list(); make it a no-op. */
void
drm_dbg(const char *func, unsigned int category, const char *format, ...)
{
}

void
drm_err(const char *func, const char *format, ...)
{
	__va_list ap;

	kprintf("htcollapse: drm_err[%s]: ", func);
	__va_start(ap, format);
	kvprintf(format, ap);
	__va_end(ap);
	kprintf("\n");
}

#define NITEMS	8192
#define CHUNK	1024

struct htc_item {
	struct drm_hash_item	h;
};

static struct drm_open_hash ht;
static struct htc_item items[NITEMS];

static uint64_t
now_us(void)
{
	struct timespec ts;
	nanouptime(&ts);
	return (uint64_t)ts.tv_sec * 1000000ULL + ts.tv_nsec / 1000;
}

static int
htcollapse_modevent(module_t mod, int type, void *arg)
{
	int i, ret, nonempty = 0, maxlen = 0, errors = 0;
	uint64_t t0 = 0, t1, chunk_us[NITEMS / CHUNK];
	struct drm_hash_item *found;
	struct hlist_node *n;

	switch (type) {
	case MOD_LOAD:
		ret = drm_ht_create(&ht, 12);
		if (ret) {
			kprintf("HTCOLLAPSE: drm_ht_create failed %d\n", ret);
			return (ret);
		}
		kprintf("HTCOLLAPSE: order=12 table=4096 buckets, insert %d "
		    "sequential keys (alloc_unr style, drm_gem.c:576)\n",
		    NITEMS);
		for (i = 0; i < NITEMS; i++) {
			if ((i % CHUNK) == 0)
				t0 = now_us();
			items[i].h.key = i + 1;
			ret = drm_ht_insert_item(&ht, &items[i].h);
			if (ret) {
				kprintf("HTCOLLAPSE: insert %d failed %d\n",
				    i, ret);
				errors++;
			}
			if ((i % CHUNK) == CHUNK - 1) {
				t1 = now_us();
				chunk_us[i / CHUNK] = t1 - t0;
			}
		}
		kprintf("HTCOLLAPSE: per-%d-insert wall time (us):", CHUNK);
		for (i = 0; i < NITEMS / CHUNK; i++)
			kprintf(" %llu", (unsigned long long)chunk_us[i]);
		kprintf("\n");
		for (i = 0; i < (1 << ht.order); i++) {
			int len = 0;
			n = ht.table[i].first;
			while (n) {
				len++;
				n = n->next;
			}
			if (len) {
				nonempty++;
				if (len > maxlen)
					maxlen = len;
			}
		}
		kprintf("HTCOLLAPSE: nonempty_buckets=%d/4096 "
		    "max_chain=%d total_items=%d errors=%d\n",
		    nonempty, maxlen, NITEMS, errors);
		/* correctness: sorted-chain finds still work */
		ret = drm_ht_find_item(&ht, 1, &found);
		kprintf("HTCOLLAPSE: find(key=1)=%d (%s)\n", ret,
		    ret == 0 ? "found" : "MISSING");
		if (ret)
			errors++;
		ret = drm_ht_find_item(&ht, NITEMS, &found);
		kprintf("HTCOLLAPSE: find(key=%d)=%d (%s)\n", NITEMS, ret,
		    ret == 0 ? "found" : "MISSING");
		if (ret)
			errors++;
		ret = drm_ht_find_item(&ht, 0xDEAD0000, &found);
		kprintf("HTCOLLAPSE: find(key=0xdead0000)=%d (%s)\n", ret,
		    ret != 0 ? "absent (ok)" : "FALSE HIT");
		if (ret == 0)
			errors++;
		/* duplicate key must fail */
		ret = drm_ht_insert_item(&ht, &items[0].h);
		kprintf("HTCOLLAPSE: dup-insert=%d (%s)\n", ret,
		    ret == -EINVAL ? "rejected (ok)" : "ACCEPTED (bad)");
		if (ret != -EINVAL)
			errors++;
		/* remove/re-insert cycle (double-remove safety too) */
		drm_ht_remove_item(&ht, &items[2].h);
		drm_ht_remove_item(&ht, &items[2].h);	/* idempotent? */
		ret = drm_ht_insert_item(&ht, &items[2].h);
		kprintf("HTCOLLAPSE: remove/reinsert=%d (0=ok)\n", ret);
		if (ret)
			errors++;
		kprintf("HTCOLLAPSE: VERDICT errors=%d nonempty_buckets=%d "
		    "max_chain=%d => %s\n", errors, nonempty, maxlen,
		    (nonempty == 1 && maxlen == NITEMS) ?
		    "hash_long collapse CONFIRMED in-kernel" :
		    "hash distributed normally (fixed header in effect)");
		/* cleanup */
		for (i = 0; i < NITEMS; i++)
			drm_ht_remove_item(&ht, &items[i].h);
		drm_ht_remove(&ht);
		return (0);
	case MOD_UNLOAD:
		return (0);
	default:
		return (EOPNOTSUPP);
	}
}

static moduledata_t htcollapse_mod = {
	"htcollapse", htcollapse_modevent, NULL
};

DECLARE_MODULE(htcollapse, htcollapse_mod, SI_SUB_DRIVERS, SI_ORDER_ANY);
MODULE_VERSION(htcollapse, 1);