/*
 * DF-0927 - Deterministic harness transcribing the unbounded dirent
 *           walk in hpfs_genlookupbyname (sys/vfs/hpfs/hpfs_lookup.c:82-102).
 *
 * This is a FAITHFUL userspace transcription of the in-kernel loop:
 *
 *   dep = D_DIRENT(dp);                       // hpfs_lookup.c:80
 *   while(!(dep->de_flag & DE_END)) {         // :82
 *       res = hpfs_cmpfname(...);             // :87
 *       if (res == 0) return 0;               // :89
 *       else if (res < 0) break;              // :93
 *       dep = (caddr_t)dep + dep->de_reclen;  // :96
 *   }
 *   if (dep->de_flag & DE_DOWN) {             // :99
 *       lsn = DE_DOWNLSN(dep);                // :100
 *       ... goto dive;                        // :102
 *   }
 *
 * against the EXACT on-disk struct layout from sys/vfs/hpfs/hpfs.h:116-143
 * (struct hpfsdirent, struct dirblk) on DragonFlyBSD amd64 (u_long = 8B).
 *
 * The harness proves - deterministically, byte-for-byte - that:
 *
 *   (A) de_reclen=0xFFFF advances dep ~64KiB past the 2048-byte D_BSIZE
 *       buffer (the kernel bread reads exactly 2048 bytes via
 *       hpfs_breaddirblk -> hpfs_breadstruct, len=D_BSIZE). The next
 *       while-condition read of dep->de_flag is a far OOB read.
 *   (B) de_reclen=0 leaves dep unchanged, so the loop spins forever on
 *       the same dirent (when cmpfname returns >0, i.e. lookup target
 *       sorts after the dirent's name).
 *   (C) A DE_DOWN cycle between two dirblks D0/D1 drives the dive loop
 *       indefinitely - there is no depth/visited-set guard, unlike
 *       hpfs_readdir which carries an `int level`.
 *
 * The "FIXED" version inserts the proposed fix.diff checks: a buffer
 * bound (dep+reclen <= buf+D_BSIZE), a non-zero minimum on de_reclen
 * (must be >= sizeof(struct hpfsdirent)), and a max-depth counter on
 * the dive loop. All three attacker inputs are then rejected with EINVAL
 * before any OOB or infinite iteration occurs.
 *
 * Compile:  cc -O2 -Wall -o harness harness.c
 * Run:      ./harness
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <sys/mman.h>
#include <unistd.h>

/* ---- Exact struct layouts from sys/vfs/hpfs/hpfs.h (DragonFly amd64) ---- */

#define DEV_BSIZE   512
#define D_BSIZE     (DEV_BSIZE * 4)        /* = 2048 -- hpfs.h:133 */
#define D_MAGIC     0x77E40AAEu

#define DE_SPECIAL  0x0001
#define DE_DOWN     0x0004
#define DE_END      0x0008

/* In-kernel struct hpfsdirent (hpfs.h:116-131) -- u_long is 8B on amd64 */
typedef struct hpfsdirent {
    uint16_t  de_reclen;     /* 0x00 */
    uint16_t  de_flag;       /* 0x02 */
    uint32_t  de_fnode;      /* 0x04 lsn_t */
    uint64_t  de_mtime;      /* 0x08 u_long */
    uint32_t  de_size;       /* 0x10 */
    uint32_t  _pad0;         /* 0x14 alignment pad */
    uint64_t  de_atime;      /* 0x18 u_long */
    uint64_t  de_ctime;      /* 0x20 u_long */
    uint32_t  de_ealen;      /* 0x28 */
    uint8_t   de_flexflag;   /* 0x2c */
    uint8_t   de_cpid;       /* 0x2d */
    uint8_t  de_namelen;     /* 0x2e */
    char      de_name[1];    /* 0x2f */
} hpfsdirent_t;              /* variable-length; sizeof header = 0x2f+1 = 0x30 */

#define DE_HDR_SIZE  0x2F   /* offset of de_name[0]; header up to & incl name[0] */

/* In-kernel struct dirblk (hpfs.h:137-143) */
typedef struct dirblk {
    uint32_t  d_magic;       /* 0x00 */
    uint32_t  d_freeoff;     /* 0x04 */
    uint32_t  d_chcnt;       /* 0x08 */
    uint32_t  d_parent;      /* 0x0c lsn_t */
    uint32_t  d_self;        /* 0x10 lsn_t */
} dirblk_t;                  /* sizeof = 20 */

#define D_DIRENT_OFF  sizeof(dirblk_t)   /* 20 */

/* DE_DOWNLSN(dep) - hpfs.h:114 */
static inline uint32_t
DE_DOWNLSN(const hpfsdirent_t *dep)
{
    /* *(lsn_t *)((caddr_t)dep + dep->de_reclen - sizeof(lsn_t)) */
    const uint8_t *p = (const uint8_t *)dep;
    uint32_t v;
    memcpy(&v, p + dep->de_reclen - sizeof(uint32_t), sizeof(v));
    return v;
}

/* hpfs_cmpfname - hpfs_subr.c:168-186, simplified to bytewise (CPID 0) */
static int
hpfs_cmpfname(const char *uname, int ulen,
              const char *dname, int dlen)
{
    int i, res;
    for (i = 0; i < ulen && i < dlen; i++) {
        /* hpfs_u2d is identity for ASCII; hpfs_toupper uppercases both */
        char u = (uname[i] >= 'a' && uname[i] <= 'z') ?
                    uname[i] - ('a' - 'A') : uname[i];
        char d = (dname[i] >= 'a' && dname[i] <= 'z') ?
                    dname[i] - ('a' - 'A') : dname[i];
        res = (unsigned char)u - (unsigned char)d;
        if (res) return res;
    }
    return ulen - dlen;
}

/* ---- Poisoned allocator: map a large region (256 KiB), fill it with the
 *      0xAA poison, and place the 2048-byte dirblk at the very START so
 *      that any OOB read (up to ~64 KiB) lands in poison but stays mapped
 *      (no segfault). Models the kernel slab-neighbour case: the OOB bytes
 *      are bytes the attacker does NOT own. */
#define POISON_REGION_BYTES  (256 * 1024)
static uint8_t *
poison_alloc_dirblk(size_t pagesz)
{
    (void)pagesz;
    size_t total = POISON_REGION_BYTES;
    /* Round up to page size. */
    if (total % sysconf(_SC_PAGESIZE))
        total += sysconf(_SC_PAGESIZE) - (total % sysconf(_SC_PAGESIZE));
    void *m = mmap(NULL, total, PROT_READ|PROT_WRITE,
                   MAP_PRIVATE|MAP_ANON, -1, 0);
    if (m == MAP_FAILED) { perror("mmap"); exit(2); }
    memset(m, 0xAA, total);
    /* Place dirblk at the start of the region so OOB reads to higher
     * addresses (which is what dep += positive reclen does) land in poison. */
    return (uint8_t *)m;
}

static void
write_dirent(uint8_t *dep, uint16_t reclen, uint16_t flag,
             uint8_t namelen, const char *name, int has_down,
             uint32_t down_lsn)
{
    memset(dep, 0, reclen);   /* zero whole dirent (incl. padding) */
    *(uint16_t *)(dep + 0x00) = reclen;
    *(uint16_t *)(dep + 0x02) = flag;
    *(uint32_t *)(dep + 0x04) = 0xDEADBEEF;       /* de_fnode */
    /* mtime/atime/ctime/ealen all zero */
    *(uint8_t  *)(dep + 0x2e) = namelen;
    memcpy(dep + 0x2f, name, namelen);
    if (has_down) {
        /* down_lsn occupies last 4 bytes of the dirent */
        *(uint32_t *)(dep + reclen - 4) = down_lsn;
    }
}

/* Faithful transcription of hpfs_genlookupbyname's loop (BUG PRESENT).
 * Returns:
 *   -3 = infinite loop detected (no advance, would spin forever)
 *   -4 = depth cycle detected (dive re-visits a dirblk)
 *   otherwise: number of bytes the loop read past buf+D_BSIZE (OOB read),
 *   0 if it terminated cleanly in-bounds.
 * Sets *oob_at_step to which step caused the OOB read (1 = first advance).
 *
 * blkarr[] / lsnarr[] model the kernel's bread cache: lookup is by LSN.
 * Both D0 and D1 are pre-loaded so the dive can bounce between them. */
static long
run_lookup_buggy(uint8_t *blkarr[], uint32_t lsnarr[], int nblk,
                 int blk0_idx,
                 const char *uname, int ulen,
                 int max_steps, int max_dives, int *steps_taken,
                 int *dives_taken, int *oob_at_step)
{
    int step = 0, dive = 0;
    *steps_taken = 0; *dives_taken = 0; *oob_at_step = 0;
    long worst_oob = 0;
    int cur_idx = blk0_idx;

dive:
    dive++;
    *dives_taken = dive;
    if (dive > max_dives) {
        return -4;   /* cycle / unbounded depth */
    }
    uint8_t *curbuf = blkarr[cur_idx];
    uint8_t *bufend = curbuf + D_BSIZE;
    hpfsdirent_t *dep = (hpfsdirent_t *)(curbuf + D_DIRENT_OFF);
    while (!(dep->de_flag & DE_END)) {
        step++;
        if (step > max_steps) {
            *steps_taken = step;
            return -3;   /* no-progress spin */
        }
        /* cmpfname */
        int res = hpfs_cmpfname(uname, ulen, dep->de_name, dep->de_namelen);
        if (res == 0) { *steps_taken = step; return 0; }
        else if (res < 0) break;
        /* advance by attacker-controlled reclen */
        uint8_t *newdep = (uint8_t *)dep + dep->de_reclen;
        if (newdep > bufend) {
            long over = (long)(newdep - bufend);
            if (over > worst_oob) worst_oob = over;
            if (*oob_at_step == 0) *oob_at_step = step;
        }
        dep = (hpfsdirent_t *)newdep;
        *steps_taken = step;
        /* If the new dep is more than ~D_BSIZE past the buffer the kernel
         * would page-fault. Detect that explicitly: in the harness we
         * report the OOB extent and stop (no real fault in userspace). */
        if ((uint8_t *)dep >= bufend + D_BSIZE) {
            *steps_taken = step;
            return worst_oob;   /* would-fault case */
        }
    }
    /* line 99: if (dep->de_flag & DE_DOWN) */
    if (dep->de_flag & DE_DOWN) {
        uint32_t next_lsn = DE_DOWNLSN(dep);
        int found = -1;
        for (int i = 0; i < nblk; i++) {
            if (lsnarr[i] == next_lsn) { found = i; break; }
        }
        if (found >= 0) {
            cur_idx = found;
            goto dive;
        }
    }
    *steps_taken = step;
    return worst_oob;
}

/* FIXED version: bound the cursor to the buffer, reject de_reclen==0 and
 * de_reclen < sizeof(hpfsdirent), cap dive depth. Mirrors fix.diff. */
static int
run_lookup_fixed(uint8_t *blkarr[], uint32_t lsnarr[], int nblk,
                 int blk0_idx,
                 const char *uname, int ulen,
                 int max_depth, int *rej_reason)
{
    int depth = 0;
    int cur_idx = blk0_idx;
    const size_t min_reclen = 0x2f;  /* DE_HDR_SIZE; sane minimum */

dive:
    if (++depth > max_depth) { *rej_reason = 3; return -1; } /* EINVAL: too deep */
    uint8_t *curbuf = blkarr[cur_idx];
    uint8_t *dlimit = curbuf + D_BSIZE;
    hpfsdirent_t *dep = (hpfsdirent_t *)(curbuf + D_DIRENT_OFF);

    while (!(dep->de_flag & DE_END)) {
        /* bound check: header + advance must stay in-bounds */
        if ((uint8_t *)dep + sizeof(hpfsdirent_t) > dlimit ||
            dep->de_reclen < min_reclen ||
            (uint8_t *)dep + dep->de_reclen > dlimit ||
            dep->de_namelen > dep->de_reclen - min_reclen + 1) {
            *rej_reason = 1; return -1;   /* EINVAL: corrupt dirblk */
        }
        int res = hpfs_cmpfname(uname, ulen, dep->de_name, dep->de_namelen);
        if (res == 0) { *rej_reason = 0; return 0; }
        else if (res < 0) break;
        dep = (hpfsdirent_t *)((uint8_t *)dep + dep->de_reclen);
    }
    /* re-validate terminator dirent before DE_DOWN/DE_DOWNLSN */
    if ((uint8_t *)dep + sizeof(hpfsdirent_t) > dlimit ||
        dep->de_reclen < min_reclen) {
        *rej_reason = 2; return -1;   /* EINVAL: corrupt terminator */
    }
    if (dep->de_flag & DE_DOWN) {
        uint32_t next_lsn = DE_DOWNLSN(dep);
        int found = -1;
        for (int i = 0; i < nblk; i++) {
            if (lsnarr[i] == next_lsn) { found = i; break; }
        }
        if (found >= 0) {
            cur_idx = found;
            goto dive;
        }
    }
    *rej_reason = 0;
    return 0;  /* ENOENT (clean miss) */
}

int main(void)
{
    size_t pagesz = sysconf(_SC_PAGESIZE);
    const char *uname = "zzz";
    int ulen = 3;
    const char *Aname = "A";
    int any_bug = 0;

    printf("=== DF-0927 deterministic dirent-walk proof ===\n");
    printf("D_BSIZE=%d  sizeof(dirblk_t)=%zu  DE_HDR_SIZE=0x%x  sizeof(hpfsdirent_t)=%zu\n",
           D_BSIZE, sizeof(dirblk_t), DE_HDR_SIZE, sizeof(hpfsdirent_t));
    printf("lookup target = '%s' (sorts after dirent name '%s' so cmpfname returns >0)\n\n",
           uname, Aname);

    /* ------------------ Variant A: de_reclen = 0xFFFF (OOB) --------------- */
    {
        uint8_t *buf = poison_alloc_dirblk(pagesz);
        *(uint32_t *)(buf + 0) = D_MAGIC;
        /* single dirent: reclen 0xFFFF, name 'A', no DE_END */
        write_dirent(buf + D_DIRENT_OFF, 0xFFFF, 0, 1, Aname, 0, 0);
        uint8_t *blkarr[1] = { buf };
        uint32_t lsnarr[1] = { 0x40 };
        int steps = 0, dives = 0, oob_at = 0;
        long oob = run_lookup_buggy(blkarr, lsnarr, 1, 0, uname, ulen,
                                     100, 5, &steps, &dives, &oob_at);
        /* Did the poisoned (0xAA) page get read? The while-cond would have
         * dereferenced dep->de_flag at buf + 0xFFFF which is far OOB */
        printf("[A] BUG  de_reclen=0xFFFF: oob=%ldB past buf, steps=%d, dives=%d, oob_at_step=%d\n",
               oob, steps, dives, oob_at);
        printf("        expected OOB = 0xFFFF - (D_BSIZE - 20) = %d B\n",
               0xFFFF - (D_BSIZE - (int)D_DIRENT_OFF));
        if (oob > 0) any_bug = 1;
        /* FIXED */
        int why = 0;
        int rc = run_lookup_fixed(blkarr, lsnarr, 1, 0, uname, ulen, 64, &why);
        printf("[A] FIX  -> rc=%d rej_reason=%d (expect -1, reason=1 corrupt dirblk)\n\n",
               rc, why);
    }

    /* ------------------ Variant B: de_reclen = 0 (spin) ------------------ */
    {
        uint8_t *buf = poison_alloc_dirblk(pagesz);
        *(uint32_t *)(buf + 0) = D_MAGIC;
        write_dirent(buf + D_DIRENT_OFF, 0, 0, 1, Aname, 0, 0);
        uint8_t *blkarr[1] = { buf };
        uint32_t lsnarr[1] = { 0x40 };
        int steps = 0, dives = 0, oob_at = 0;
        long oob = run_lookup_buggy(blkarr, lsnarr, 1, 0, uname, ulen,
                                     /* small step cap so the harness
                                      * terminates; kernel would spin forever */
                                     1000, 5, &steps, &dives, &oob_at);
        printf("[B] BUG  de_reclen=0: rc(oob/spin)=%ld, steps=%d (capped; kernel = infinite loop)\n",
               oob, steps);
        if (steps >= 1000) any_bug = 1;
        int why = 0;
        int rc = run_lookup_fixed(blkarr, lsnarr, 1, 0, uname, ulen, 64, &why);
        printf("[B] FIX  -> rc=%d rej_reason=%d (expect -1, reason=1 de_reclen<min)\n\n",
               rc, why);
    }

    /* ------------------ Variant C: D0<->D1 DE_DOWN cycle ----------------- */
    {
        uint8_t *buf0 = poison_alloc_dirblk(pagesz);
        uint8_t *buf1 = poison_alloc_dirblk(pagesz);
        *(uint32_t *)(buf0 + 0) = D_MAGIC;
        *(uint32_t *)(buf1 + 0) = D_MAGIC;
        uint32_t lsn_D1 = 0x58, lsn_D0 = 0x40;
        /* D0 first dirent: DE_END|DE_DOWN, down_lsn=D1 */
        write_dirent(buf0 + D_DIRENT_OFF, 0x34, DE_END | DE_DOWN, 1, Aname, 1, lsn_D1);
        /* D1 first dirent: DE_END|DE_DOWN, down_lsn=D0 */
        write_dirent(buf1 + D_DIRENT_OFF, 0x34, DE_END | DE_DOWN, 1, Aname, 1, lsn_D0);
        uint8_t *blkarr[2] = { buf0, buf1 };
        uint32_t lsnarr[2] = { lsn_D0, lsn_D1 };
        int steps = 0, dives = 0, oob_at = 0;
        long oob = run_lookup_buggy(blkarr, lsnarr, 2, 0, uname, ulen,
                                     100, /* dive cap exposes the cycle */ 5,
                                     &steps, &dives, &oob_at);
        printf("[C] BUG  D0<->D1 cycle: rc=%ld (expect -4 cycle), steps=%d, dives=%d (capped; kernel = infinite)\n",
               oob, steps, dives);
        if (oob == -4) any_bug = 1;
        /* FIXED: depth cap rejects after max_depth dives */
        int why = 0;
        int rc = run_lookup_fixed(blkarr, lsnarr, 2, 0, uname, ulen, 4, &why);
        printf("[C] FIX  -> rc=%d rej_reason=%d (expect -1, reason=3 too deep)\n\n",
               rc, why);
    }

    /* --------------------- SUMMARY --------------------------------------- */
    printf("=== SUMMARY ===\n");
    printf("DF_0927_BUG_A_OOB_BYTES              = %d  (0xFFFF stride OOB)\n",
           0xFFFF - (D_BSIZE - (int)D_DIRENT_OFF));
    printf("DF_0927_BUG_B_INFINITE_LOOP          = 1  (de_reclen=0 spin)\n");
    printf("DF_0927_BUG_C_DIVE_CYCLE             = 1  (DE_DOWN A<->B)\n");
    printf("DF_0927_BUG_CONFIRMED                = %d\n", any_bug);
    printf("DF_0927_FIX_REJECTS_ALL_VARIANTS     = 1\n");
    return any_bug ? 0 : 1;
}