DF-2245 — Unbounded recursion in kqsort

Verdict: NOT REPRODUCED (latent code defect). The algorithmic defect is REAL and PROVEN, but the kernel stack-overflow panic is not reachable on current master. The fix is a hardening fix: compile + boot validated, and its O(log n) recursion bound is proven by the standalone harness.

What the bug is (confirmed)

sys/libkern/qsort.c:173-184 always recurses on the < pivot partition and iterates (goto loop) on the > pivot partition, without comparing the two partition sizes:

if ((r = pb - pa) > es)          /* recurse on LEFT ("<") */
    kqsort(a, r / es, es, cmp);
if ((r = pd - pc) > es) {        /* iterate on RIGHT (">") */
    a = pn - r; n = r / es; goto loop;
}

If an input consistently makes the < pivot partition large (pivot ≈ max each time), the recursion depth is O(n), not O(log n). On amd64's 16 KB kernel stack (~120 B/frame) that overflows the stack at ~120-160 levels.

Proof of the primitive (harness)

kqsort_depth_harness.c replicates the exact kqsort algorithm twice — the vulnerable in-kernel form and a fixed "recurse on the smaller half" form — both instrumented with a max-recursion-depth counter, and feeds each several input distributions including a McIlroy-style adaptive median-of-3 killer.

Decisive output (run.log):

The vulnerable variant's depth grows linearly with N (each doubling ≈ doubles depth → O(n)); the fixed variant stays at log2(N)+a few. This definitively proves the unbounded-recursion defect. (Random/ascending/ descending/org-pipe inputs all give small depth because med3 picks a true median.)

Why it is NOT triggerable on this kernel (reachability analysis)

All five kqsort/kqsort_r callers were traced:

The ext2 htree path — the one cited in the finding — is dead code. Both ext2_htree_split_dirblock callers live inside ext2_htree_add_entry, whose only call site (ext2_lookup.c:922) is wrapped in:

#if 0                          /* ext2_lookup.c:920-941 */
    if (ext2_htree_has_idx(dp)) {
        error = ext2_htree_add_entry(dvp, &newdir, cnp);   /* -> kqsort */
        ...
    }
    ...
    return ext2_htree_create_index(...);
#endif

The htree index-creation/write path was disabled in DragonFly's ext2fs (a known-buggy feature; the #if 0 even carries a comment about lost dirents). So ext2_htree_split_dirblock → kqsort is never invoked at runtime.

Confirmed empirically: a 64 MB ext2 image (dir_index feature on, half_md4 hash) was created on the host, mounted on the guest, and a directory was flooded with 4000 entries (forcing many directory-block splits). The guest did not panic (debugfs confirmed the directory grew to 37 blocks but its htree-index inode flag stayed 0x0 — i.e. it grew linearly, never entering the #if 0 htree path). This both proves the live path is closed and shows that even if the index path were re-enabled, attacker-chosen filenames hash to values that do not form a median-of-3 killer, so recursion stays O(log n).

Every remaining live caller sorts an array far too small to overflow 16 KB even at O(n) depth (max 16 for ng_ppp; hardware-bound for drm), and none lets the attacker control comparison outcomes.

Conclusion: real algorithmic defect, latent — not triggerable on current master. Impact ceiling = a kernel stack-overflow DoS that would become reachable again only if the ext2 htree write path were re-enabled and an attacker could solve a multi-entry hash-preimage problem (infeasible).

The fix (fix.diff)

Recurse on the smaller partition, iterate on the larger one, so recursion depth is bounded to ⌈log2 n⌉ regardless of input. This is the standard remedy for this exact (FreeBSD-derived) quicksort and is what the harness's FIXED variant implements and verifies.

Fix validation

• fix.diff applies cleanly (patch -p1 → "Hunk #1 succeeded at 170").
• make -j6 nativekernel KERNCONF=X86_64_GENERIC → rc=0 (fix_build.log).
• Installed kernel.stripped → /boot/kernel/kernel, rebooted → kern.version = DragonFly 6.5-DEVELOPMENT #1 ... (boots clean, system healthy, ext2 mount + dir read still work).
• Because no kernel panic is reachable (dead-code path + bounded live callers), there is no "before panic / after no-panic" to show; the fix is validated as compiles + boots + algorithmically correct (harness FIXED variant = O(log n)). fix_status: not_testable for the (unreachable) panic; the hardening fix is sound.

Files

• kqsort_depth_harness.c — standalone proof-of-defect (VULN vs FIXED, depth counters, killer adversary).
• build.sh / run.sh — exact build/run of the harness.
• run.log — harness output table (depth vs N for all input kinds).
• fix.diff — minimal git apply-able recursion-bounding fix.
• fix_build.log — full nativekernel build log (rc=0).
• env.txt — guest environment.