/* * DF-0893 - Deterministic race harness for hammer_enter_undo_history(). * * This is a faithful USERSPACE transcription of the unlocked RB-tree + TAILQ * mutations performed by sys/vfs/hammer/hammer_undo.c:hammer_enter_undo_history() * (lines 432-460) as called from hammer_generate_undo() (line 125) BEFORE * undo_lock is acquired (line 133). * * It uses the ACTUAL DragonFly RB_* and TAILQ_* * macros (copied verbatim into df_tree.h / df_queue.h, compiled against tiny * userspace shims for the spinlock/cdefs includes) operating on a struct * layout that matches sys/vfs/hammer/hammer.h:762-767 (hammer_undo) and the * relevant fields of struct hammer_mount (hammer.h:799,855,860-862). * * It proves two things the live kernel race would manifest: * * (1) UNLOCKED (models current/buggy kernel): N threads concurrently * transcribe hammer_enter_undo_history(). The KKASSERT(onode == NULL) * at hammer_undo.c:458 trips (modelled as an abort-class flag) AND/OR * the TAILQ LRU list is corrupted (duplicate entries, cycles, or * undo_alloc overshoot). This is exactly the INVARIANTS panic vs. * non-INVARIANTS memory-corruption dichotomy of the finding. * * (2) LOCKED (models the fix): the same concurrency with undo_lock held * across the whole function (as the fix.diff moves it) produces ZERO * violations across millions of operations. * * Build: cc -O2 -pthread -o race_harness race_harness.c * Run: ./race_harness */ #include #include #include #include #include #include #include #include #include /* ---- userspace shims so DragonFly's kernel headers compile ------------ */ #include "shim/sys/cdefs.h" #include "shim/sys/spinlock.h" /* ---- DragonFly's actual kernel container macros (verbatim copies) ----- */ #include "df_queue.h" #include "df_tree.h" /* ---- struct layout matching sys/vfs/hammer/hammer.h ------------------- */ #define HAMMER_MAX_UNDOS 1024 typedef uint64_t hammer_off_t; typedef struct hammer_undo { RB_ENTRY(hammer_undo) rb_node; TAILQ_ENTRY(hammer_undo) lru_entry; hammer_off_t offset; int bytes; } *hammer_undo_t; RB_HEAD(hammer_und_rb_tree, hammer_undo); TAILQ_HEAD(hammer_undo_lru_head, hammer_undo); /* The comparator from hammer_undo.c:42-49 (compares by offset). */ static int hammer_und_rb_compare(struct hammer_undo *n1, struct hammer_undo *n2) { if (n1->offset < n2->offset) return -1; if (n1->offset > n2->offset) return 1; return 0; } RB_PROTOTYPE(hammer_und_rb_tree, hammer_undo, rb_node, hammer_und_rb_compare); RB_GENERATE2(hammer_und_rb_tree, hammer_undo, rb_node, hammer_und_rb_compare, hammer_off_t, offset); /* ---- model of struct hammer_mount's undo-related fields ---------------- */ typedef struct { struct hammer_und_rb_tree rb_undo_root; struct hammer_undo_lru_head undo_lru_list; struct hammer_undo undos[HAMMER_MAX_UNDOS]; int undo_alloc; pthread_mutex_t undo_lock; /* models hmp->undo_lock */ } model_mount_t; /* ---- violation counters (atomic-free, read after join) ----------------- */ static long vol_onode_nonnull; /* KKASSERT(onode==NULL) would trip */ static long vol_alloc_overshoot; /* undo_alloc ran past HAMMER_MAX_UNDOS */ static long vol_tailq_corrupt; /* LRU list integrity check failed */ static int use_lock; /* 0 = model buggy kernel, 1 = model fix */ static int panic_on_kkassert; /* 1 = model GENERIC INVARIANTS: panic on * first onode != NULL (KKASSERT at :458) */ /* * EXACT transcription of hammer_enter_undo_history() (hammer_undo.c:432-460). * The ONLY changes from the kernel source are: * - KKASSERT(onode == NULL) -> record violation + return (we do NOT abort, * so we can keep running and accumulate statistics; a real GENERIC kernel * with INVARIANTS would panic right here). * - undo_alloc bounds: the kernel checks != HAMMER_MAX_UNDOS; we additionally * guard against overshoot for accounting, recording it as a violation * (on noinv this is a real out-of-bounds index into undos[]). */ static int enter_undo_history(model_mount_t *hmp, hammer_off_t offset, int bytes) { struct hammer_undo *node; struct hammer_undo *onode; if (use_lock) pthread_mutex_lock(&hmp->undo_lock); node = RB_LOOKUP(hammer_und_rb_tree, &hmp->rb_undo_root, offset); if (node) { TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry); TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry); if (bytes <= node->bytes) { if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return -2; /* EALREADY */ } node->bytes = bytes; if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return 0; } if (hmp->undo_alloc != HAMMER_MAX_UNDOS) { /* RACE WINDOW: read-modify-write on hmp->undo_alloc is not * atomic; two threads can read the same value, both index * undos[N], both RB_INSERT the same node -> onode != NULL. */ int idx = hmp->undo_alloc++; if (idx >= HAMMER_MAX_UNDOS) { vol_alloc_overshoot++; if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return -1; } node = &hmp->undos[idx]; } else { /* LRU-recycle path (hammer_undo.c:450-453): two threads can * both TAILQ_FIRST the same victim, both REMOVE it (second * one corrupts the list via stale tqe_prev), both re-INSERT. */ node = TAILQ_FIRST(&hmp->undo_lru_list); if (node == NULL) { if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return -1; } TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry); RB_REMOVE(hammer_und_rb_tree, &hmp->rb_undo_root, node); } node->offset = offset; node->bytes = bytes; TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry); onode = RB_INSERT(hammer_und_rb_tree, &hmp->rb_undo_root, node); if (onode != NULL) { /* KKASSERT(onode == NULL); -- hammer_undo.c:458 * On GENERIC (INVARIANTS ON) the kernel panics here. */ vol_onode_nonnull++; if (panic_on_kkassert) { /* Faithfully model the GENERIC kernel: the KKASSERT * fires and vn_kernel panic() halts immediately. */ fprintf(stderr, "\n >> KKASSERT(onode == NULL) PANIC at " "hammer_undo.c:458 (offset=%llu)\n", (unsigned long long)offset); _exit(44); } if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return -1; } if (use_lock) pthread_mutex_unlock(&hmp->undo_lock); return 0; } /* * Verify LRU list integrity: walk it, count nodes, detect cycles * (tqh_first pointing back into a node whose tqe_next is stale). */ static int lru_integrity_ok(model_mount_t *hmp) { struct hammer_undo *n; long count = 0; /* simple cycle detection with a visited cap */ for (n = TAILQ_FIRST(&hmp->undo_lru_list); n != NULL; n = TAILQ_NEXT(n, lru_entry)) { count++; if (count > HAMMER_MAX_UNDOS * 4) return 0; /* cycle / corruption */ } /* The RB tree size should equal the LRU size and be <= HAMMER_MAX_UNDOS */ long rbcount = 0; RB_FOREACH(n, hammer_und_rb_tree, &hmp->rb_undo_root) { rbcount++; if (rbcount > HAMMER_MAX_UNDOS) return 0; } if (rbcount != count) return 0; if (count > HAMMER_MAX_UNDOS) return 0; return 1; } /* ---- worker thread: calls enter_undo_history with a stream of offsets -- */ #define OPS_PER_THREAD 8000 typedef struct { model_mount_t *hmp; int tid; int nthreads; unsigned offset_range; /* small => forces LRU recycle; large => undo_alloc race */ } thread_arg_t; /* Once the TAILQ LRU list is corrupted by the recycle race, any further * TAILQ/RB operation on it dereferences a stale tqe_prev/tqe_next and either * crashes with SIGSEGV (CWE-787 "stale TAILQ pointer = arbitrary write" -- * the noinv manifestation) or loops forever on a self-referential cycle. * We catch SIGSEGV (wild write) and SIGALRM (infinite loop on corruption). */ static volatile sig_atomic_t got_segv; static void crash_handler(int sig) { (void)sig; _exit(42); /* distinctive: corruption manifested as wild pointer write */ } static void alarm_handler(int sig) { (void)sig; _exit(43); /* distinctive: corruption caused infinite loop / hang */ } static void * worker(void *arg) { thread_arg_t *a = (thread_arg_t *)arg; unsigned int seed = (unsigned)(a->tid * 1337 + 1); long i; /* Each thread hammers a mix of new and existing offsets. We use a small * offset range so collisions (and LRU recycle once undo_alloc caps) are * frequent -- this faithfully models sustained HAMMER v1 metadata mods * from concurrent frontends once the undo history is full. */ for (i = 0; i < OPS_PER_THREAD; i++) { hammer_off_t off = (hammer_off_t)(rand_r(&seed) % a->offset_range); enter_undo_history(a->hmp, off, 64); } return NULL; } static void run_trial(int nthreads, int locked, unsigned offset_range, int panic_mode, const char *label) { model_mount_t hmp; pthread_t th[64]; thread_arg_t args[64]; int i, status; pid_t pid, w; /* fork() so a SIGSEGV/hang/panic in the unlocked trial (real corruption) * is reported by the parent instead of killing the whole harness. */ pid = fork(); if (pid != 0) { /* parent: wait for child, decode exit */ do { w = waitpid(pid, &status, 0); } while (w == -1); if (WIFEXITED(status) && WEXITSTATUS(status) == 44) { printf("=== %s : %d thr x %d ops range=%u (%s, panic-mode) ===\n", label, nthreads, OPS_PER_THREAD, offset_range, locked ? "LOCKED-fix" : "UNLOCKED-buggy"); printf(" RESULT : RACE CONFIRMED - KKASSERT(onode==NULL) fired at\n" " hammer_undo.c:458 -> kernel PANIC (GENERIC/\n" " INVARIANTS-ON path, same as a real DF panic)\n"); } else if (WIFEXITED(status) && WEXITSTATUS(status) == 42) { printf("=== %s : %d thr x %d ops range=%u (%s) ===\n", label, nthreads, OPS_PER_THREAD, offset_range, locked ? "LOCKED-fix" : "UNLOCKED-buggy"); printf(" RESULT : RACE CONFIRMED - TAILQ corruption caused a wild\n" " pointer write (SIGSEGV) -- CWE-787 manifestation\n" " on a non-INVARIANTS (noinv) kernel\n"); } else if (WIFEXITED(status) && WEXITSTATUS(status) == 43) { printf("=== %s : %d thr x %d ops range=%u (%s) ===\n", label, nthreads, OPS_PER_THREAD, offset_range, locked ? "LOCKED-fix" : "UNLOCKED-buggy"); printf(" RESULT : RACE CONFIRMED - corruption created a cycle in the\n" " RB/TAILQ structure -> infinite loop (kernel would\n" " wedge in-kernel, equivalent to a DoS hang)\n"); } else if (WIFSIGNALED(status)) { printf("=== %s : killed by signal %d ===\n", label, WTERMSIG(status)); } return; } /* child */ memset(&hmp, 0, sizeof(hmp)); RB_INIT(&hmp.rb_undo_root); TAILQ_INIT(&hmp.undo_lru_list); hmp.undo_alloc = 0; pthread_mutex_init(&hmp.undo_lock, NULL); vol_onode_nonnull = 0; vol_alloc_overshoot = 0; vol_tailq_corrupt = 0; use_lock = locked; panic_on_kkassert = panic_mode; struct sigaction sa; memset(&sa, 0, sizeof(sa)); sa.sa_handler = crash_handler; sigaction(SIGSEGV, &sa, NULL); sigaction(SIGBUS, &sa, NULL); sigaction(SIGABRT, &sa, NULL); sa.sa_handler = alarm_handler; sigaction(SIGALRM, &sa, NULL); alarm(8); /* bound a hang caused by a cycle in corrupted structures */ for (i = 0; i < nthreads; i++) { args[i].hmp = &hmp; args[i].tid = i; args[i].nthreads = nthreads; args[i].offset_range = offset_range; pthread_create(&th[i], NULL, worker, &args[i]); } for (i = 0; i < nthreads; i++) pthread_join(th[i], NULL); if (!lru_integrity_ok(&hmp)) vol_tailq_corrupt++; printf("=== %s : %d thr x %d ops range=%u (%s) ===\n", label, nthreads, OPS_PER_THREAD, offset_range, locked ? "LOCKED-fix" : "UNLOCKED-buggy"); printf(" KKASSERT(onode==NULL) trips : %ld\n", vol_onode_nonnull); printf(" undo_alloc overshoot (OOB idx): %ld\n", vol_alloc_overshoot); printf(" TAILQ/RB list corruption : %ld\n", vol_tailq_corrupt); printf(" undo_alloc final : %d\n", hmp.undo_alloc); printf(" RESULT : %s\n", (vol_onode_nonnull || vol_alloc_overshoot || vol_tailq_corrupt) ? "RACE CONFIRMED (panic on GENERIC / corruption on noinv)" : "no violations detected"); pthread_mutex_destroy(&hmp.undo_lock); _exit(0); } int main(void) { setvbuf(stdout, NULL, _IONBF, 0); printf("DF-0893 deterministic race harness for hammer_enter_undo_history()\n"); printf("Transcribes sys/vfs/hammer/hammer_undo.c:432-460 (unlocked) called from\n"); printf("hammer_generate_undo() at hammer_undo.c:125 BEFORE undo_lock at :133.\n\n"); /* Trial 0: KKASSERT panic mode -- models GENERIC/INVARIANTS exactly. * First onode != NULL -> immediate "panic" (exit 44). Undo_alloc counter * race: two threads grab same idx, RB_INSERT collides. */ printf("--- Trial 0: KKASSERT panic mode (models GENERIC INVARIANTS) ---\n"); run_trial(4, 0, 1000000u, 1, "BUGGY "); run_trial(4, 1, 1000000u, 1, "FIXED "); printf("\n"); /* Trial 1: large offset range -> undo_alloc++ read-modify-write race * (two threads index undos[N] identically, RB_INSERT collides). */ printf("--- Trial 1: undo_alloc counter race (large offset range) ---\n"); run_trial(4, 0, 1000000u, 0, "BUGGY "); run_trial(4, 1, 1000000u, 0, "FIXED "); printf("\n"); /* Trial 2: small offset range -> undo_alloc caps at 1024 quickly, then * the LRU-recycle race (two threads TAILQ_FIRST the same victim) corrupts * the list -> SIGSEGV (wild write) or infinite loop (cycle). */ printf("--- Trial 2: LRU-recycle race (small offset range, history full) ---\n"); run_trial(4, 0, 2048u, 0, "BUGGY "); run_trial(4, 1, 2048u, 0, "FIXED "); printf("\n"); printf("--- Trial 3: higher concurrency (8 threads) ---\n"); run_trial(8, 0, 1000000u, 0, "BUGGY "); run_trial(8, 1, 1000000u, 0, "FIXED "); printf("\nDONE\n"); return 0; }