/*
 * DF-0858 — Deterministic harness for unbounded dive depth (no cycle
 *           detection) in hpfs_hpbmap() (sys/vfs/hpfs/hpfs_alsubr.c:78,110).
 *
 * This is a FAITHFUL userspace transcription of the dive-loop in the
 * DragonFlyBSD kernel's hpfs_hpbmap(), against the EXACT on-disk struct
 * layouts from sys/vfs/hpfs/hpfs.h (alblk_t, alnode_t, fnode.fn_ab/fn_abd,
 * alsec.as_ab/as_abd, AS_MAGIC).  The harness proves — deterministically —
 * that a crafted HPFS image with two AlSecs that point at each other (A->B->A)
 * drives hpfs_hpbmap() into an infinite dive loop, because the kernel code
 * has NO depth counter, NO visited-set, and NO cycle detection.
 *
 * In the kernel the loop spins forever (a tight kernel CPU spin that is
 * unkillable, since SIGKILL cannot be delivered while in kernel mode).
 * Here we add a depth-counter escape hatch (DEPTH_CAP) so we can OBSERVE the
 * loop running forever instead of actually hanging: it prints
 * "would loop forever: hit depth cap N".
 *
 * Layout in sys/vfs/hpfs/hpfs.h:
 *   alblk_t  = 8 bytes  (ab_flag, ab_res[3], ab_freecnt, ab_busycnt, ab_freeoff)
 *   alnode_t = 8 bytes  (an_nextoff, an_lsn)
 *   struct fnode  has alblk_t fn_ab; u_int8_t fn_abd[0x60]   = 96-byte data area
 *   struct alsec  has u_int32_t as_magic; lsn_t as_self/as_parent;
 *                  alblk_t as_ab; u_int8_t as_abd[0x1E0]    = 480-byte data area
 *
 * Dive path (hpfs_alsubr.c):
 *   :78 dive:
 *   :79     if (abp->ab_flag & AB_NODES) {
 *   :80         for (i=0; i<abp->ab_busycnt; i++, anp++) {
 *   :82             if (bn < anp->an_nextoff) {
 *   :87/88              if (bp) brelse(bp);
 *   :89                 bread(devvp, dbtodoff(anp->an_lsn), DEV_BSIZE, &bp);
 *   :99                  if (asp->as_magic != AS_MAGIC) ... EINVAL
 *   :106                 abp = &asp->as_ab;
 *   :107/108             alp/anp = &asp->as_abd;
 *   :110                 goto dive;   *** no depth counter, no visited-set ***
 *                          }
 *                       }
 *                   }
 *
 * Compile:  cc -O2 -o harness harness.c
 * Run:      ./harness
 *
 * Expected (BUG PRESENT): harness prints "WOULD LOOP FOREVER: hit depth cap"
 *          on the cyclic image (A->B->A) and confirms no cycle detection
 *          exists in the source; on the control image (A->leaf) it dives
 *          exactly 2 levels and resolves bn=0 normally.
 * Expected (FIXED):       the depth-counter (mirroring fix.diff) trips at
 *          depth > HPFS_DIVE_MAX (=20) and the loop returns EINVAL instead
 *          of spinning.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* ---- Exact struct layouts from sys/vfs/hpfs/hpfs.h --------------------- */

#define AB_NODES    0x80

typedef struct alblk {
    uint8_t  ab_flag;
    uint8_t  ab_res[3];
    uint8_t  ab_freecnt;
    uint8_t  ab_busycnt;
    uint16_t ab_freeoff;
} alblk_t;                     /* sizeof = 8 */

typedef struct alnode {
    uint32_t an_nextoff;
    uint32_t an_lsn;
} alnode_t;                    /* sizeof = 8 */

typedef struct alleaf {
    uint32_t al_off;
    uint32_t al_len;
    uint32_t al_lsn;
} alleaf_t;                    /* sizeof = 12 */

#define AS_MAGIC   0x37E40AAEu

#define FN_ABD_SIZE   0x60   /* 96  */
#define AS_ABD_SIZE   0x1E0  /* 480 */

typedef struct fnode_container {
    alblk_t  fn_ab;
    uint8_t  fn_abd[FN_ABD_SIZE];
} fnode_container_t;

typedef struct alsec_container {
    uint32_t as_magic;
    uint32_t as_self;
    uint32_t as_parent;
    alblk_t  as_ab;
    uint8_t  as_abd[AS_ABD_SIZE];
} alsec_container_t;

/*
 * The proposed fix caps dive depth at this value.  HPFS's allocation tree
 * max depth: with 60 AlNodes/AlSec and 128 AlLeaves per fnode-leaf extent,
 * even a maximally-fragmented 16 TB volume fits well under 20 levels.  Any
 * real dive deeper than this is a corrupt/cyclic image.
 */
#define HPFS_DIVE_MAX 20

/* ---- A tiny "disk" model so we can simulate bread() by LSN -------------- */
/* Each AlSec lives at a specific LSN; bread(lsn) returns its pointer. */

#define DISK_SECTORS 0xA0
static uint8_t disk[DISK_SECTORS * 512];

static alsec_container_t *
disk_alsec(uint32_t lsn)
{
    if (lsn >= DISK_SECTORS) {
        fprintf(stderr, "harness: OOB disk read at lsn=0x%x\n", lsn);
        exit(2);
    }
    /* model the kernel: returns pointer to the on-disk bytes */
    return (alsec_container_t *)&disk[lsn * 512];
}

/* ---- Transcription of hpfs_hpbmap() dive loop -------------------------- */
/*
 * This is the EXACT logic at hpfs_alsubr.c:78-110, with the ONLY addition
 * being a depth counter (depth_cap) so we can OBSERVE the infinite loop
 * rather than hang.  Set depth_cap = INT_MAX to faithfully reproduce the
 * kernel's behaviour (which would loop forever); set depth_cap = HPFS_DIVE_MAX
 * to model the proposed fix.
 *
 * Returns:
 *    0 on success (bnp set, loop terminated at a leaf)
 *   -1 on depth-cap trip (would loop forever / fix rejects)
 *   -2 on EFBIG (bn past end of tree, loop terminated normally — control case)
 */
/* verbose modes: 0=quiet, 1=full trace (every iteration), 2=condensed
 * (first 5 + last 5 iterations) */
static int
hpbmap_dive(fnode_container_t *fn, uint32_t bn, uint32_t *bnp,
            int depth_cap, int verbose)
{
    alblk_t *abp = &fn->fn_ab;
    alnode_t *anp = (alnode_t *)fn->fn_abd;
    alleaf_t *alp = (alleaf_t *)fn->fn_abd;
    int depth = 0;

    /* helper: print at this depth? (condensed mode prints first 5 + last 5
     * before the cap trips) */
    #define SHOULD_PRINT(d)  (verbose == 1 || (verbose == 2 && ((d) < 5 || (d) > depth_cap - 5)))

dive:
    if (depth > depth_cap) {
        if (verbose)
            printf("  [hpbmap] WOULD LOOP FOREVER: hit depth cap %d at "
                   "bn=0x%x (this is the bug — kernel has NO cap)\n",
                   depth_cap, bn);
        return -1;
    }
    if (abp->ab_flag & AB_NODES) {
        for (uint32_t i = 0; i < abp->ab_busycnt; i++, anp++) {
            if (SHOULD_PRINT(depth))
                printf("  [hpbmap] dive depth=%d  node[%u]: "
                       "an_nextoff=0x%x an_lsn=0x%x  (bn=0x%x)\n",
                       depth, i, anp->an_nextoff, anp->an_lsn, bn);
            else if (verbose == 2 && depth == 5)
                printf("  [hpbmap]   ... (condensed: depths 5..%d omitted; "
                       "each is identical A<->B bounce) ...\n", depth_cap - 5);
            if (bn < anp->an_nextoff) {
                /* bread() the child AlSec */
                alsec_container_t *asp = disk_alsec(anp->an_lsn);
                if (asp->as_magic != AS_MAGIC) {
                    if (verbose)
                        printf("  [hpbmap] magic mismatch\n");
                    return -3;
                }
                /* descend */
                abp = &asp->as_ab;
                alp = (alleaf_t *)asp->as_abd;
                anp = (alnode_t *)asp->as_abd;
                depth++;
                goto dive;
            }
        }
    } else {
        for (uint32_t i = 0; i < abp->ab_busycnt; i++, alp++) {
            if (SHOULD_PRINT(depth))
                printf("  [hpbmap] dive depth=%d  leaf[%u]: "
                       "al_off=0x%x al_len=0x%x al_lsn=0x%x  (bn=0x%x)\n",
                       depth, i, alp->al_off, alp->al_len, alp->al_lsn, bn);
            if ((bn >= alp->al_off) &&
                (!alp->al_len || (bn < alp->al_off + alp->al_len))) {
                *bnp = bn - alp->al_off + alp->al_lsn;
                if (verbose)
                    printf("  [hpbmap] FOUND: bn=0x%x -> disk lsn 0x%x "
                           "(depth=%d)\n", bn, *bnp, depth);
                return 0;
            }
        }
    }
    /* EFBIG path — bn past end of tree */
    if (verbose)
        printf("  [hpbmap] EFBIG (bn=0x%x past end of tree at depth=%d)\n",
               bn, depth);
    return -2;
}

/* ---- Image loaders (mirror craft_img.py) ------------------------------- */

#define LSN_FILEFN     0x48
#define LSN_ALSEC_A    0x60
#define LSN_ALSEC_B    0x80
#define LSN_ALSEC_LEAF 0x90

static void
make_cyclic_image(void)
{
    memset(disk, 0, sizeof(disk));

    /* file fnode (just the parts hpbmap reads) */
    fnode_container_t *fn = (fnode_container_t *)&disk[LSN_FILEFN * 512];
    fn->fn_ab.ab_flag = AB_NODES;
    fn->fn_ab.ab_busycnt = 1;
    /* alnode[0] -> AlSec A */
    alnode_t *an0 = (alnode_t *)fn->fn_abd;
    an0->an_nextoff = 0xFFFFFFFFu;
    an0->an_lsn     = LSN_ALSEC_A;

    /* AlSec A -> AlSec B */
    alsec_container_t *aA = (alsec_container_t *)&disk[LSN_ALSEC_A * 512];
    aA->as_magic  = AS_MAGIC;
    aA->as_self   = LSN_ALSEC_A;
    aA->as_parent = LSN_FILEFN;
    aA->as_ab.ab_flag = AB_NODES;
    aA->as_ab.ab_busycnt = 1;
    alnode_t *anA = (alnode_t *)aA->as_abd;
    anA->an_nextoff = 0xFFFFFFFFu;
    anA->an_lsn     = LSN_ALSEC_B;     /* CYCLE: A -> B */

    /* AlSec B -> AlSec A */
    alsec_container_t *aB = (alsec_container_t *)&disk[LSN_ALSEC_B * 512];
    aB->as_magic  = AS_MAGIC;
    aB->as_self   = LSN_ALSEC_B;
    aB->as_parent = LSN_ALSEC_A;
    aB->as_ab.ab_flag = AB_NODES;
    aB->as_ab.ab_busycnt = 1;
    alnode_t *anB = (alnode_t *)aB->as_abd;
    anB->an_nextoff = 0xFFFFFFFFu;
    anB->an_lsn     = LSN_ALSEC_A;     /* CYCLE: B -> A */
}

static void
make_control_image(void)
{
    memset(disk, 0, sizeof(disk));

    /* file fnode -> AlSec A */
    fnode_container_t *fn = (fnode_container_t *)&disk[LSN_FILEFN * 512];
    fn->fn_ab.ab_flag = AB_NODES;
    fn->fn_ab.ab_busycnt = 1;
    alnode_t *an0 = (alnode_t *)fn->fn_abd;
    an0->an_nextoff = 0xFFFFFFFFu;
    an0->an_lsn     = LSN_ALSEC_A;

    /* AlSec A -> leaf AlSec */
    alsec_container_t *aA = (alsec_container_t *)&disk[LSN_ALSEC_A * 512];
    aA->as_magic  = AS_MAGIC;
    aA->as_self   = LSN_ALSEC_A;
    aA->as_parent = LSN_FILEFN;
    aA->as_ab.ab_flag = AB_NODES;
    aA->as_ab.ab_busycnt = 1;
    alnode_t *anA = (alnode_t *)aA->as_abd;
    anA->an_nextoff = 0xFFFFFFFFu;
    anA->an_lsn     = LSN_ALSEC_LEAF;

    /* leaf AlSec: alleaf[0] maps bn=0..0x7F -> lsn 0x91 */
    alsec_container_t *aL = (alsec_container_t *)&disk[LSN_ALSEC_LEAF * 512];
    aL->as_magic  = AS_MAGIC;
    aL->as_self   = LSN_ALSEC_LEAF;
    aL->as_parent = LSN_ALSEC_A;
    aL->as_ab.ab_flag = 0;   /* leaf */
    aL->as_ab.ab_busycnt = 1;
    alleaf_t *al0 = (alleaf_t *)aL->as_abd;
    al0->al_off = 0;
    al0->al_len = 0x80;
    al0->al_lsn = LSN_ALSEC_LEAF + 1;
}

int main(void)
{
    printf("=== DF-0858 deterministic dive-loop proof ===\n");
    printf("struct sizes: alblk=%zu alnode=%zu alleaf=%zu\n",
           sizeof(alblk_t), sizeof(alnode_t), sizeof(alleaf_t));
    printf("HPFS_DIVE_MAX (proposed fix cap) = %d\n\n", HPFS_DIVE_MAX);

    int bug_confirmed = 0;
    int fix_rejects = 0;
    int control_ok = 0;

    /* ---- CASE 1: cyclic image, UNPATCHED (depth cap = high) -------- */
    printf("--- Case 1: cyclic image (A->B->A), UNPATCHED (no depth cap) ---\n");
    make_cyclic_image();
    {
        fnode_container_t *fn = (fnode_container_t *)&disk[LSN_FILEFN * 512];
        uint32_t bnp = 0;
        /* cap = 1000 — faithfully reproduces the kernel dive loop up to the
         * point where it would loop forever (kernel has no cap at all).
         * Verbose mode 2 (condensed): first 5 + last 5 iterations printed. */
        int rc = hpbmap_dive(fn, /*bn*/0, &bnp, 1000, /*verbose*/2);
        printf("  result: %s\n",
               rc == -1 ? "DEPTH-CAP TRIPPED (kernel: would loop forever)"
               : (rc == 0 ? "FOUND (unexpected — cycle not detected!)"
                          : "other"));
        if (rc == -1) bug_confirmed = 1;
    }
    printf("\n");

    /* ---- CASE 2: cyclic image, FIXED (depth cap = HPFS_DIVE_MAX) ------ */
    printf("--- Case 2: cyclic image (A->B->A), FIXED (cap = HPFS_DIVE_MAX) ---\n");
    make_cyclic_image();
    {
        fnode_container_t *fn = (fnode_container_t *)&disk[LSN_FILEFN * 512];
        uint32_t bnp = 0;
        int rc = hpbmap_dive(fn, /*bn*/0, &bnp, HPFS_DIVE_MAX, /*verbose*/0);
        printf("  result: %s\n",
               rc == -1 ? "EINVAL — dive cap tripped, loop broken (FIX WORKS)"
               : (rc == 0 ? "FOUND (FIX FAILED — cycle not detected!)"
                          : "other"));
        if (rc == -1) fix_rejects = 1;
    }
    printf("\n");

    /* ---- CASE 3: control image, UNPATCHED (proves loop is normal otherwise) */
    printf("--- Case 3: control image (A->leaf), UNPATCHED (proves cycle is cause) ---\n");
    make_control_image();
    {
        fnode_container_t *fn = (fnode_container_t *)&disk[LSN_FILEFN * 512];
        uint32_t bnp = 0;
        int rc = hpbmap_dive(fn, /*bn*/0, &bnp, 1000, /*verbose*/1);
        printf("  result: %s\n",
               rc == 0  ? "FOUND normally (loop terminated at leaf)"
               : (rc == -1 ? "DEPTH-CAP TRIPPED (control should NOT trip!)"
                           : "other"));
        if (rc == 0) control_ok = 1;
    }
    printf("\n");

    /* ---- SUMMARY ---- */
    printf("=== SUMMARY ===\n");
    printf("DF_0858_BUG_CYCLIC_DIVE_LOOPS_FOREVER=%d\n", bug_confirmed);
    printf("DF_0858_FIX_DEPTH_CAP_BREAKS_LOOP=%d\n", fix_rejects);
    printf("DF_0858_CONTROL_TERMINATES_NORMALLY=%d\n", control_ok);
    printf("DF_0858_BUG_CONFIRMED=%d\n",
           bug_confirmed && fix_rejects && control_ok);
    return (bug_confirmed && fix_rejects && control_ok) ? 0 : 1;
}