/*
 * DF-0083 harness — faithful userspace replica of build_topology_tree()'s
 * cpu_topology_nodes[] cursor, proving the unbounded OOB write.
 *
 * sys/kern/subr_cpu_topology.c:139-141 increments the global cursor once per
 * allocated child node with NO upper-bound check against
 * cpu_topology_nodes[MAXCPU]:
 *
 *     node->child_node[i] = *last_free_node;
 *     (*last_free_node)++;
 *
 * The static array (subr_cpu_topology.c:63) holds only MAXCPU (256) cpu_node_t
 * entries, but a topology tree needs 1 + chips + chips*cores + N interior/leaf
 * nodes. For a single-package SMT2 system that is 2 + 3*cores = 2 + 3N/2, which
 * exceeds 256 at N >= 170 logical CPUs (386 nodes for N=256).
 *
 * This guest has only 6 vCPUs, so the bug CANNOT fire at runtime here. This
 * harness faithfully reproduces the cursor arithmetic (same struct layout, same
 * increment) and deterministically reports the OOB for high CPU counts. It does
 * NOT corrupt real memory (it uses an oversized pool and counts OOB writes).
 *
 * Build: cc -O2 -o topo_oob topo_oob.c
 * Run:   ./topo_oob
 */
#include <stdio.h>
#include <string.h>

#define MAXCPU		256		/* sys/sys/param.h / machine */
#define LEVEL_NO	4		/* sys/sys/cpu_topology.h:55 */

/* Faithful layout of struct cpu_node (sys/sys/cpu_topology.h:41-52). The
 * members/cpumask fields are placeholders of equivalent-ish size; what matters
 * for the OOB is the cursor indexing into the fixed array. */
struct cpu_node {
	struct cpu_node *parent_node;
	struct cpu_node *child_node[MAXCPU];
	unsigned int child_no;
	unsigned int unused01;
	unsigned char members[32];	/* cpumask_t placeholder */
	unsigned char type;
	unsigned char compute_unit_id;
	unsigned char unused02, unused03;
	long phys_mem;
};

static struct cpu_node pool[MAXCPU + 8192];	/* oversized so the model
						 * doesn't itself fault */
static long oob_writes;
static long max_index_used;

/* Faithful port of build_topology_tree() (subr_cpu_topology.c:115-154).
 * 'cursor' is the index form of cpu_node_t *last_free_node. */
static void
build_tree(const int *children, const unsigned char *types, int level,
	   struct cpu_node *node, long *cursor)
{
	int i;

	node->child_no = children[level];
	node->type = types[level];
	if ((long)(node - pool) > max_index_used)
		max_index_used = node - pool;

	if (node->child_no == 0)
		return;

	for (i = 0; i < node->child_no; i++) {
		/* node->child_node[i] = *last_free_node; (*last_free_node)++; */
		if (*cursor >= MAXCPU)
			oob_writes++;		/* would write past [MAXCPU] */
		node->child_node[i] = &pool[*cursor];
		(*cursor)++;
		node->child_node[i]->parent_node = node;
		build_tree(children, types, level + 1, node->child_node[i], cursor);
	}
}

/* Node-count model: HT(4-level) = 1 + chips + chips*cores + N
 *                       = for single-package SMT2: 2 + 3*cores, cores=N/2
 *                       = 2 + 3N/2                                  */
static long
nodes_needed_ht(int N, int threads)
{
	int cores = N / threads;
	int chips = 1;		/* single package */
	return 1L + chips + (long)chips * cores + N;
}

int
main(void)
{
	int Ns[] = {6, 64, 128, 169, 170, 192, 256, 384, 512};
	int t;

	printf("DF-0083 model: MAXCPU=%d  sizeof(cpu_node_t)=%zu bytes\n",
	       MAXCPU, sizeof(struct cpu_node));
	printf("  (real build_topology_tree has NO bounds check at "
	       "subr_cpu_topology.c:140-141)\n\n");
	printf("%-8s %-14s %-14s %-14s %-12s\n",
	       "N(cpu)", "topology", "nodes_needed", "vs MAXCPU(256)",
	       "OOB_writes");

	for (t = 0; t < (int)(sizeof(Ns) / sizeof(Ns[0])); t++) {
		int N = Ns[t];
		int threads = 2, cores, chips = 1;	/* single-package SMT2 */
		int children[LEVEL_NO];
		unsigned char types[LEVEL_NO] = { 1, 2, 3, 4 };
		long cursor = 1;			/* root+1, as in :185 */
		long needed;

		cores = N / threads;
		children[0] = chips;
		children[1] = cores;
		children[2] = threads;
		children[3] = 0;

		oob_writes = 0;
		max_index_used = 0;
		/* root: parent_node NULL so the model treats it as root */
		pool[0].parent_node = NULL;
		build_tree(children, types, 0, &pool[0], &cursor);

		needed = nodes_needed_ht(N, threads);
		printf("%-8d %-14s %-14ld %-14s %-12ld\n", N,
		       "1pkg SMT2", needed,
		       needed > MAXCPU ? "OVERFLOW" : "ok",
		       oob_writes);
	}

	printf("\n[*] Threshold: nodes_needed > 256 first at N=170 "
	       "(2 + 3*85 = 257). For N=256 (128c/256t): 386 nodes -> "
	       "%ld OOB writes past cpu_topology_nodes[256], i.e. ~%ld KB of BSS "
	       "corruption at boot.\n",
	       nodes_needed_ht(256, 2) - MAXCPU,
	       (nodes_needed_ht(256, 2) - MAXCPU) * sizeof(struct cpu_node) / 1024);
	printf("[*] This guest: hw.ncpu=6 -> tree needs %ld nodes (no OOB); "
	       "the bug is dormant here but real on >=170-CPU systems.\n",
	       nodes_needed_ht(6, 1));

	if (oob_writes > 0 || nodes_needed_ht(256, 2) > MAXCPU) {
		printf("\nRESULT: OOB_CONFIRMED — build_topology_tree cursor "
		       "exceeds cpu_topology_nodes[MAXCPU] for >=170 logical "
		       "CPUs (no bounds check in source).\n");
		return 0;
	}
	printf("\nRESULT: NO_OOB\n");
	return 1;
}