/*
 * harness.c - Userspace replication of the unbounded run-list walk in
 *             ntfs_runtovrun() (sys/vfs/ntfs/ntfs_subr.c:582-634).
 *
 * THE BUG (confirmed by source trace)
 * -----------------------------------
 * ntfs_runtovrun(cn_t **rcnp, cn_t **rclp, u_long *rcntp, u_int8_t *run)
 *   :595-598   while (run[off]) { off += (run[off]&0xF)+((run[off]>>4)&0xF)+1; cnt++; }
 *   :599-600   cn = kmalloc(cnt * sizeof(cn_t));  cl = kmalloc(cnt * sizeof(cn_t));
 *   :605-629   while (run[off]) { sz=run[off++]; for(i<sz&0xF) cl[cnt]+=run[off++]; ... }
 *
 * There is NO length parameter. Both loops walk run[off] until a zero byte is
 * found. If the on-disk run list has no zero terminator, the walk reads past the
 * attribute's data extent, past the MFT record buffer (kmalloc(4096, M_TEMP)),
 * into adjacent kernel heap — an OOB read. If the adjacent memory has no zero
 * byte (e.g. INVARIANTS-poisoned freed slab = 0xdeadc0de), it is an infinite loop.
 *
 * The disabled ntfs_parserun() at :1745-1780 shows the correct pattern: it takes
 * a `len` parameter and bounds-checks at :1760 and :1770.
 *
 * WHY A HARNESS
 * -------------
 * The live trigger (mount_ntfs crafted image) fires ntfs_runtovrun at mount time
 * inside ntfs_attrtontvattr for the first non-resident attribute. On the default
 * GENERIC kernel the outcome depends on adjacent slab content (OOB read vs hang).
 * To make the bug DETERMINISTIC, this harness replicates the exact walk against a
 * run-list buffer placed at the end of a writable page with a PROT_NONE guard page
 * after it, so any OOB read faults and any unterminated walk is caught by an
 * iteration cap that the kernel does NOT have.
 *
 * Build:  cc -O2 -o harness harness.c
 * Run:    ./harness {clean|oob_short|oob_fill|oob_infinite} [apply_fix]
 * Exit:   0 = walk completed cleanly (proper terminator found, or fix rejected)
 *         1 = iteration cap hit (would be infinite loop in kernel)
 *         2 = SIGSEGV (OOB read past the run-list buffer)
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <signal.h>
#include <setjmp.h>
#include <sys/mman.h>

#define RUN_BUF_BYTES  200    /* mirror a typical run-list extent within a 4096-byte MFT record */
#define ITER_CAP       500000 /* kernel has no cap; this catches infinite loops */

/*
 * Mirror of ntfs_runtovrun() lines 582-634 — the BUGGY version (no length bound).
 * Returns: 0 = clean (found terminator), 1 = iteration cap (infinite loop).
 * A SIGSEGV during this function = OOB read past the buffer (caught by handler).
 */
static int buggy_runtovrun(uint8_t *run)
{
    uint32_t off, sz, i;
    unsigned cnt = 0;
    uint64_t prev = 0, tmp;

    /* ---- count phase (lines 595-598) ---- */
    off = 0;
    cnt = 0;
    while (run[off]) {
        off += (run[off] & 0xF) + ((run[off] >> 4) & 0xF) + 1;
        cnt++;
        if (cnt > ITER_CAP)
            return 1;  /* infinite loop */
    }

    /* mirror the kmalloc(cnt * sizeof(cn_t)) at :599-600 — in userspace we
       just note the count; an absurdly large cnt from OOB bytes is itself a
       memory-exhaustion signal in the kernel. */
    if (cnt > 65536) {
        printf("  [!] count phase read %u entries from OOB — kernel would "
               "kmalloc(%lu bytes)\n", cnt, (unsigned long)cnt * 8);
    }

    /* ---- decode phase (lines 605-629) ---- */
    off = 0;
    cnt = 0;
    prev = 0;
    while (run[off]) {
        sz = run[off++];
        /* cluster length */
        for (i = 0; i < (sz & 0xF); i++)
            (void)((uint32_t)run[off++] << (i << 3));
        /* cluster offset */
        sz >>= 4;
        if (off > 0 && (run[off + sz - 1] & 0x80)) {
            tmp = ((uint64_t)-1) << (sz << 3);
            for (i = 0; i < sz; i++)
                tmp |= (uint64_t)run[off++] << (i << 3);
        } else {
            tmp = 0;
            for (i = 0; i < sz; i++)
                tmp |= (uint64_t)run[off++] << (i << 3);
        }
        prev = tmp ? prev + tmp : tmp;
        (void)prev;
        cnt++;
        if (cnt > ITER_CAP)
            return 1;
    }
    return 0;
}

/*
 * The proposed FIX: thread a runlen parameter and bound both loops.
 * Returns 0 on success, -1 (EINVAL) if the walk would exceed runlen.
 */
static int fixed_runtovrun(uint8_t *run, uint32_t runlen)
{
    uint32_t off, sz, i, adv;
    unsigned cnt = 0;
    uint64_t prev = 0, tmp;

    /* ---- count phase, bounded ---- */
    off = 0;
    cnt = 0;
    while (off < runlen && run[off]) {
        sz = run[off];
        adv = (sz & 0xF) + ((sz >> 4) & 0xF) + 1;
        if (off + adv > runlen)
            return -1;  /* entry straddles buffer end */
        off += adv;
        cnt++;
    }
    if (off >= runlen && (runlen == 0 || run[runlen > 0 ? runlen - 1 : 0] != 0)) {
        /* walked to the end without a terminator inside the buffer */
        /* (the loop above stops when off >= runlen even if run[off-1] was nonzero) */
    }

    /* ---- decode phase, bounded ---- */
    off = 0;
    cnt = 0;
    prev = 0;
    while (off < runlen && run[off]) {
        sz = run[off++];
        if (off + (sz & 0xF) + (sz >> 4) > runlen)
            return -1;
        (void)0;
        for (i = 0; i < (sz & 0xF); i++)
            (void)((uint32_t)run[off++] << (i << 3));
        sz >>= 4;
        if (off + sz > runlen)
            return -1;
        if (sz > 0 && (run[off + sz - 1] & 0x80)) {
            tmp = ((uint64_t)-1) << (sz << 3);
            for (i = 0; i < sz; i++)
                tmp |= (uint64_t)run[off++] << (i << 3);
        } else {
            tmp = 0;
            for (i = 0; i < sz; i++)
                tmp |= (uint64_t)run[off++] << (i << 3);
        }
        prev = tmp ? prev + tmp : tmp;
        (void)prev;
        cnt++;
    }
    return 0;
}

/* ---- signal handling to catch the OOB SIGSEGV cleanly ---- */
static sigjmp_buf jb;
static volatile int got_sig;
static void segv_handler(int sig) { (void)sig; got_sig = SIGSEGV; siglongjmp(jb, 1); }

static uint8_t *runbuf;  /* the run-list buffer, placed at end of writable page */

/*
 * Fill the run-list buffer per mode:
 *   clean        — one valid entry + proper 0x00 terminator (kernel happy path)
 *   oob_short    — one entry, NO terminator; bytes after it are zero (walk stops
 *                  at the first zero byte — marginal, but proves no internal bound)
 *   oob_fill     — fill entire buffer with 0x11 (nonzero), no terminator — walk
 *                  runs off the end into the guard page (SIGSEGV = OOB read)
 *   oob_infinite — fill with 0x01 pattern causing huge advance but no zero —
 *                  same as oob_fill, exercises the count-phase overflow
 */
static void fill_runbuf(const char *mode)
{
    memset(runbuf, 0, RUN_BUF_BYTES);

    if (strcmp(mode, "clean") == 0) {
        /* 0x11 = 1 len byte + 1 off byte; entry: 11 clusters at offset 0x0B */
        runbuf[0] = 0x11;
        runbuf[1] = 0x0B;  /* length = 11 clusters */
        runbuf[2] = 0x02;  /* offset = 2 (positive) */
        runbuf[3] = 0x00;  /* terminator */
    } else if (strcmp(mode, "oob_short") == 0) {
        /* one entry, no terminator; rest is zero — walk stops at byte 3 */
        runbuf[0] = 0x11;
        runbuf[1] = 0x0B;
        runbuf[2] = 0x02;
        /* runbuf[3] = 0x00 (already zeroed) — acts as terminator */
    } else if (strcmp(mode, "oob_fill") == 0) {
        /* fill ALL bytes with 0x11 — every 3 bytes is a "valid" entry, no
           terminator anywhere; the walk runs off the end of the buffer */
        memset(runbuf, 0x11, RUN_BUF_BYTES);
    } else if (strcmp(mode, "oob_infinite") == 0) {
        /* fill with 0x22 pattern (2 len + 2 off per entry = 5-byte entries);
           no terminator; count phase inflates cnt */
        memset(runbuf, 0x22, RUN_BUF_BYTES);
    } else {
        fprintf(stderr, "unknown mode '%s'\n", mode);
        exit(3);
    }
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        fprintf(stderr, "usage: %s {clean|oob_short|oob_fill|oob_infinite} [apply_fix]\n",
                argv[0]);
        return 3;
    }
    const char *mode = argv[1];
    int apply_fix = (argc >= 3 && strcmp(argv[2], "apply_fix") == 0);

    long pagesz = 4096;
    size_t mapsz = (RUN_BUF_BYTES + pagesz - 1) & ~(pagesz - 1);
    uint8_t *base = mmap(NULL, mapsz + pagesz, PROT_READ | PROT_WRITE,
                         MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (base == MAP_FAILED) { perror("mmap"); return 3; }
    if (mprotect(base + mapsz, pagesz, PROT_NONE) != 0) { perror("mprotect"); return 3; }
    /* place runbuf at the END of the writable region so the guard page is
       immediately after byte RUN_BUF_BYTES-1 (truest mirror of the run-list
       extent living at the end of a kmalloc'd MFT record). */
    runbuf = base + mapsz - RUN_BUF_BYTES;

    fill_runbuf(mode);

    struct sigaction sa, oldsa;
    memset(&sa, 0, sizeof(sa));
    sa.sa_handler = segv_handler;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = 0;
    sigaction(SIGSEGV, &sa, &oldsa);

    got_sig = 0;
    int rc;
    if (sigsetjmp(jb, 1) == 0) {
        if (apply_fix)
            rc = fixed_runtovrun(runbuf, RUN_BUF_BYTES);
        else
            rc = buggy_runtovrun(runbuf);
    } else {
        rc = 2;  /* SIGSEGV caught */
    }
    sigaction(SIGSEGV, &oldsa, NULL);

    const char *verdict;
    switch (rc) {
        case 0:  verdict = "clean exit (terminator found within buffer)"; break;
        case 1:  verdict = "ITERATION CAP HIT -> infinite loop (unterminated OOB walk)"; break;
        case 2:  verdict = "SIGSEGV -> OOB read past run-list buffer (into adjacent slab in kernel)"; break;
        case -1: verdict = "FIX REJECTED input (EINVAL — bounded walk caught overflow)"; break;
        default: verdict = "unknown"; break;
    }
    printf("mode=%-14s apply_fix=%-3d  -> rc=%d  %s\n",
           mode, apply_fix, rc, verdict);
    return (rc == 0 || rc == -1) ? 0 : rc;
}