/*
 * DF-1120 userspace harness — sym buddy allocator OOB write primitive.
 *
 * The kernel bug:
 *   sys/dev/disk/sym/sym_hipd.c:408  m_pool_s.h[] declared
 *       h[MEMO_CLUSTER_SHIFT - MEMO_SHIFT + 1]   ->   h[9]  on x86_64
 *   (PAGE_SHIFT=12, MEMO_PAGE_ORDER=0, MEMO_SHIFT=4 -> 12-4+1=9 slots, idx 0..8)
 *   sys/dev/disk/sym/sym_hipd.c:476-497  ___sym_mfree merge loop:
 *       while (1) {
 *           b = a ^ s;  q = &h[i];   <-- walks h[] for buddy
 *           if found: a = a&b; s <<= 1; ++i;   <-- i climbs with no bound
 *       }
 *   MEMO_FREE_UNUSED (#ifdef at :477) is wrapped in `#if 0` at :366-368 so it
 *   does NOT compile in -- the early-exit when s==MEMO_CLUSTER_SIZE is absent,
 *   so two buddy-adjacent 4096-byte frees merge at i=7->8, then again at i=8
 *   (s becomes 8192), and the next loop top does `q = &h[9]` -> 8-byte OOB
 *   write into whatever follows m_pool_s in kernel heap.
 *
 * This harness replicates the allocator bookkeeping with the same layout and
 * demonstrates the OOB write into a guard canary placed right after h[].
 * Uses real mmap'd 4096-aligned buddy addresses so linked-list walks are valid.
 *
 * Build:  cc -O2 -o harness harness.c
 * Run:    ./harness
 * Expected: "OOB WRITE at h[9] detected" (canary corrupted).
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

#define PAGE_SHIFT         12
#define MEMO_PAGE_ORDER    0
#define MEMO_SHIFT         4
#define MEMO_CLUSTER_SHIFT (PAGE_SHIFT + MEMO_PAGE_ORDER)   /* 12 */
#define MEMO_CLUSTER_SIZE  (1UL << MEMO_CLUSTER_SHIFT)     /* 4096 */
#define NH                 (MEMO_CLUSTER_SHIFT - MEMO_SHIFT + 1)  /* 9 */

typedef struct m_link { struct m_link *next; } m_link_s;

/* mimic m_pool_s tail layout: h[] immediately followed by a canary */
typedef struct {
    m_link_s h[NH];
    uint64_t canary;
} test_pool;

static test_pool pool;

int main(void) {
    memset(&pool, 0, sizeof(pool));
    pool.canary = 0xDEADBEEFCAFEBABEull;

    printf("Layout: h[%d] (idx 0..%d), canary at &h[%d]\n",
           NH, NH - 1, NH);
    printf("MEMO_CLUSTER_SIZE = %lu\n", MEMO_CLUSTER_SIZE);

    /* Allocate two page-aligned buddy-adjacent 4096-byte regions.
     * A 2-page mmap gives us A at offset 0 and B = A^4096 at offset 4096. */
    void *base = NULL;
    if (posix_memalign(&base, 2 * MEMO_CLUSTER_SIZE, 2 * MEMO_CLUSTER_SIZE) != 0) {
        perror("posix_memalign"); return 1;
    }
    unsigned long A = (unsigned long)base;
    unsigned long B = A + MEMO_CLUSTER_SIZE;  /* buddy: B = A ^ 4096 (A is page-aligned) */
    /* for page-aligned A, A ^ 4096 == A + 4096 iff bit 12 of A is 0.
     * Force it by choosing base appropriately. */
    if (A & MEMO_CLUSTER_SIZE) { A += MEMO_CLUSTER_SIZE; B = A ^ MEMO_CLUSTER_SIZE; }
    assert((A ^ MEMO_CLUSTER_SIZE) == B);
    printf("A=%p  B=%p  (B == A ^ 4096 = buddy pair)\n", (void*)A, (void*)B);

    /* Free A first: walks up to s=4096,i=8; h[8] empty -> push A onto h[8]. */
    {
        int i = 0, s = (1 << MEMO_SHIFT);
        unsigned long a = A;
        while (MEMO_CLUSTER_SIZE > (unsigned)s) { s <<= 1; ++i; }
        ((m_link_s *)a)->next = pool.h[i].next;
        pool.h[i].next = (m_link_s *)a;
        printf("freed A: parked on h[%d] (s=%d)\n", i, s);
    }

    /* Free B: walks up to s=4096,i=8; buddy A IS on h[8] -> MERGE:
     * a = A&B, s=8192, i=9.  Next loop top accesses h[9] -> OOB. */
    {
        int i = 0, s = (1 << MEMO_SHIFT);
        unsigned long a = B;
        while (MEMO_CLUSTER_SIZE > (unsigned)s) { s <<= 1; ++i; }
        printf("freed B: entering merge loop at i=%d, s=%d\n", i, s);

        /* EXACT kernel loop body, NO MEMO_FREE_UNUSED guard */
        while (1) {
            m_link_s *q;
            unsigned long b;
            if (i >= NH) {
                printf("\n*** OOB WRITE at h[%d] -- canary corrupted ***\n", i);
                printf("    (kernel: `q = &h[%d]` then `h[%d].next = (m_link_s*)a`\n", i, i);
                printf("     = 8-byte write past m_pool_s.h[] into adjacent heap)\n");
                pool.h[i].next = (m_link_s *)a; /* the OOB write */
                printf("    canary before = 0x%016lx\n",
                       (unsigned long)0xDEADBEEFCAFEBABEull);
                printf("    canary after  = 0x%016lx  (OVERWRITTEN)\n",
                       (unsigned long)pool.canary);
                free(base);
                return 0;
            }
            b = a ^ s;
            q = &pool.h[i];
            while (q->next && q->next != (m_link_s *)b) q = q->next;
            if (!q->next) {
                ((m_link_s *)a)->next = pool.h[i].next;
                pool.h[i].next = (m_link_s *)a;
                printf("  no buddy at i=%d: parked, break\n", i);
                break;
            }
            q->next = q->next->next;
            a = a & b;
            s <<= 1;
            ++i;
            printf("  merged at i=%d -> new i=%d, s=%d\n", i-1, i, s);
        }
    }
    printf("no OOB -- unexpected.\n");
    free(base);
    return 1;
}