# 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:

```c
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`):

| N    | input   | VULN_depth | FIXED_depth | log2(N) |
|------|---------|-----------|-------------|---------|
| 512  | killer  | **109**   | 5           | 9       |
| 1024 | killer  | **225**   | 5           | 10      |
| 2048 | killer  | **453**   | 6           | 11      |
| 4096 | killer  | **883**   | 7           | 12      |

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:

| Caller | Array | Max size | Attacker-controlled? |
|--------|-------|----------|----------------------|
| `sys/vfs/ext2fs/ext2_htree.c:587` | directory-entry hashes | ~340 / 4 KB block | **only weakly** (filename→half_md4 hash, one-way); **AND the call site is `#if 0`** |
| `sys/netgraph/ppp/ng_ppp.c:1747` | `sortByLatency` | `NG_PPP_MAX_LINKS = 16` | no (link latencies) |
| `sys/dev/raid/vinum/vinumio.c:760` | `drivelist` | vinum drive count (root-set) | no |
| `sys/dev/drm/linux_sort.c:36` | DRM objects | hw-bound (planes/modes) | no |

**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:

```c
#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.