# DF-5696 VERDICT — reproduced (userland differential rig on the DragonFly guest)

**Bottom line:** the `int` byte-distance variables `d`/`r` in
`sys/libkern/qsort.c:109` corrupt the sort's internal state whenever a
partition byte-distance exceeds `INT_MAX`. The decisive member is the
signed/unsigned promotion at `qsort.c:173/179` (`(int)r > (size_t)es`), which
turns a *truncated-negative* distance into a *huge unsigned* one, passes the
"iterate right partition" guard, and restarts the outer loop with
`a = pn - r` (2.13 GiB **past** the array end) and `n = r / es` (~2^64) —
from there the sort compares and swaps completely out of bounds. A second
family member (`d = (n/8)*es` at `qsort.c:125`, needs ≥16 GiB) makes med3
hand the comparator pointers ~2 GiB *below* the array. Both are demonstrated
against the verbatim kernel source compiled in userland (the established rig
pattern) on the DragonFly guest. **In-tree kernel reachability today: none** —
all five callers sort ≤ a few KB — so this is a latent primitive
memory-corruption defect, not a live kernel bug. Severity Low, confidence
certain.

## How it was demonstrated

Rig: `qsort_rig.c` + `qsort_v.c` (verbatim `sys/libkern/qsort.c`, sha256
`18620ff1b212…` == guest `/usr/src/sys/libkern/qsort.c`) + `qsort_fixed6.c`
(identical source with `size_t d, r2` and `size_t swapfunc` n). Guest:
DragonFly 6.5-DEVELOPMENT, gcc 8.3, 12 GiB.

### Member 1 — `r` truncation → unsigned promotion → OOB partition state (5.76 GiB)

Input: n = 720,000,000, es = 8; keys `i+1` for elements [0, 270M), constant
`0x100000000` for [270M, 720M). Observed dynamics (comparator arg trace,
`truncate_trace` mode):

1. med3 (11 cmps) picks a medium pivot; `swap(a, pm)` parks it at slot 0
   (swapping a small into slot 719,999,999).
2. First partition while-loop stops immediately (slot 1 > pivot under
   memcmp/LE); the second while marches `pc` over all 720,000,000 elements;
   the 449,999,999 equal comparisons each do `swap(pc, pd); pd -= es`.
3. Loop ends with `pd` at element 270,000,000 and `pc` at 0 →
   **`pd - pc` = 2,160,000,000 bytes** → `(int)` wrap = **−2,134,967,296**.
4. `vecswap` is skipped by its `> 0` guard (harmless), but
   `if ((r = pd - pc) > es)` compares `int r` with `size_t es` → r promotes
   to 18,446,744,073,681,161,720 → guard **passes** →
   `a = pn - r` = `base + 5,760,000,000 + 2,134,967,296` =
   **base + 7,894,967,296**, `n = r / es` = (size_t)(−266,870,912).
5. `goto loop` → n > 40 branch: `d = (n/8)*es` → (int) −266,870,912 →
   first med3 comparison is `cmp(a, a+d)` = `cmp(base+7,894,967,296,
   base+7,628,096,384)` — **both far past the array end**. The guest rig
   observed exactly these two offsets (fatal → confirmed exit 9):

```
TRUNCATION OOB CONFIRMED: comparator called with args past the array end
(x-base=7894967296 y-base=7628096384, n*es=5760000000)
```

The offset arithmetic matches the source model **byte-for-byte**
(7,894,967,296 = 5,760,000,000 + |(int)2,160,000,000|; 7,628,096,384 =
7,894,967,296 + (int)((2^64−266,870,912)/8·8)). In a kernel caller a
dereferencing comparator (e.g. `ext2_htree_cmp_sort_entry`,
ext2_htree.c:500-512) would perform an OOB **read** at both addresses, and
the subsequent `swap(a, pm)` (qsort.c:132) an 8-byte OOB **write** at `a`.

Patched control: `qsort_fixed6.c` on the identical input sorts correctly —
8,795,877,536 comparisons, 222.4 s, `patched: array IS SORTED`.
Small control (n = 720,000, same shape): verbatim output == libc qsort
reference (proves the failure is a ≥2^31-byte threshold, not the layout).

### Member 2 — `d = (n/8)*es` truncation → med3 samples below the array (17.2 GiB VA)

n = 17,200,000,000, es = 1 (MAP_ANONYMOUS, pages untouched): the **first**
med3 call at qsort.c:126 already hands the comparator `pl+d` with
`d = (int)2,150,000,000 = −2,144,967,296`:

```
OOB COMPARATOR ARGS CONFIRMED: x-base=0 y-base=-2144967296 n*es=17200000000
```

Patched control: 0 OOB comparator args in the first 1000 calls.

### Differential/contract evidence (negative result for the other classes)

- `fuzz` (guest 8000 + host 20000 iterations): random n ∈ [0,3000], es ∈
  {1..40 incl. odd/unaligned}, randomized base misalignment, byte canaries
  both sides, comparator asserting arg bounds/alignment — verbatim, patched,
  and `kqsort_r` (thunk-identity checked) all byte-identical to libc qsort,
  0 canary corruption, 0 OOB/unaligned comparator args, worst comparison
  count 2.17 × n·log₂n. Partition invariants, med3 sampling, both insertion
  sorts, the tail-recursion elimination arithmetic — all clean at sane sizes.
- `fuzz_lie` (guest 2000 + host 5000 iterations × 6 inconsistent comparators:
  deterministic noise, always+1, always−1, all-equal, antisymmetric/
  intransitive, PRNG): 0 canary corruption, 0 OOB comparator args — the
  partition loop and insertion sorts stay in-bounds under *any* comparator
  (pb/pc are guarded by `pb <= pc`, pa/pd move in lockstep). The only
  comparator-abuse failure mode left is recursion depth / O(n²) degradation,
  which is the already-filed DF-2245/DF-2254 class and was not re-tested as
  a finding.

## Why not a kernel build for fix validation

The fix is validated A/B on the **same 5.76 GiB input**: verbatim source →
OOB partition state (exit 9); patched source → correct sort. Building a
patched kernel would show no observable delta because **no in-tree caller can
reach the ≥2.16 GiB threshold** (caller census in README). fix_status=fixed
on that basis.

## Guest state

Ran as root on the standard clean-source snapshot (12 GiB RAM for the big
arrays; `vm.sh` restored to 4096 and the guest `reset with-src` afterwards).
No kernel panic occurred (all demos are userland); guest left clean.

## Fix status (batch validation)
Applied with the 36 sibling fix.diffs of this batch in findings/poc/_batch41/all_fixes.patch; single in-guest `make -j6 nativekernel KERNCONF=X86_64_GENERIC` completed RC=0 with zero errors under -Werror (full log: findings/poc/_batch41/fix_build8.log). Behavior A/B intentionally skipped for this Info-tier item.