# DF-5696 — kqsort byte-distance `int` truncation + signed/unsigned promotion corrupts the partition state (OOB reads/writes) for ≥2.16 GiB partitions

`sys/libkern/qsort.c` (DragonFly `kqsort`/`kqsort_r`, Bentley–McIlroy) keeps all
partition **byte distances** in `int` variables `d` and `r`
(sys/libkern/qsort.c:109) even though `n`, `es` and all pointer deltas are
64-bit (`size_t`/`ptrdiff_t`). Two family members, both demonstrated:

1. **`r` truncation + unsigned promotion (the strong one — OOB read/write):**
   when a partition byte-distance exceeds `INT_MAX`, `(int)` wraps negative;
   the guard `if ((r = pd - pc) > es)` (qsort.c:179, and :173) compares the
   `int` `r` against `size_t es`, so the negative `r` is promoted to a huge
   unsigned value, the guard **passes**, and `a = pn - r; n = r / es; goto loop`
   (qsort.c:181-183) restarts the sort with the array pointer **2.13 GiB past
   the end** and `n ≈ 2^64`. The next med3/partition pass then hands the
   comparator (and then `swap(a, pm)`'s swapfunc) wild pointers — an OOB read
   in the comparator and an 8-byte OOB write at `swap(a, pm)`.
   Demonstrated on the guest at n=720,000,000 × es=8 (5.76 GiB): comparator
   args at `base+7,894,967,296` and `base+7,628,096,384` — exactly
   `pn + 2,134,967,296` and `a + (int)((n/8)*es)` (see VERDICT.md trace math).

2. **`d = (n/8)*es` truncation (med3 sampling):** at n·es ≥ 2^34 (16 GiB),
   `d` wraps negative and `med3(pl, pl+d, pl+2*d)` (qsort.c:125-128) feeds the
   comparator pointers ~2 GiB / ~4 GiB **below** the array. Demonstrated on
   the guest at n=17,200,000,000 × es=1: `y-base = -2,144,967,296`.

**Reachability (why severity is Low, not High):** every in-tree caller was
censused — `ext2_htree.c:587` (n = directory-block entries ≤ ~512, es = 8),
`linux_sort.c:36` (drm `sort()`, n = in-memory object counts, es = constants),
`vinumio.c:760` (n ≤ drives, es = 4), `ng_ppp.c:1747` / `ng_ppp7:2292` (n ≤
NG_PPP_MAX_LINKS, es = sizeof(int)). None sorts more than a few KB; the
≥2.16 GiB threshold is unreachable in the tree today. The finding is a
**latent primitive memory-corruption defect** (the same class of size-type bug
that becomes exploitable the day a caller passes a large/counted array — e.g.
a future drm/hash sort driven by untrusted counts).

## Evidence (this pack)

Userland differential rig compiling the **audited source verbatim**
(`qsort_v.c`, sha256 `18620ff1…`, identity-pinned == guest `/usr/src` copy) plus
the patched variant `qsort_fixed6.c` (same source, `size_t d, r2` +
`size_t swapfunc` n) — the established rig pattern. Big-array modes ran **on
the DragonFly guest** (12 GiB; guest cc 8.3); small modes also ran on the host.

- `build.log` — host build (zig cc 18.1.6), shows the exact verbatim→patched delta
- `guest_build.log` — guest build from `/usr/src`, sha pin verified
- `run.log` — guest full matrix: **ALL_EXPECTATIONS_MET**
  (truncate rc=9: verbatim OOB args, patched sorts the same 5.76 GiB input
  correctly in 8,795,877,536 comparisons / 222 s)
- `run_host.log` — host: fuzz 20000 + fuzz_lie 5000 + es0 modes
- `run_es0.log` — guest es0 runs (shared with DF-5697)
- `env.txt` — guest uname/compiler/RAM/swap + pinned sha256 of both files
- `fix.diff` — git-apply-able one-file fix (also fixes `kqsort_r` via the
  shared body; `sys/libkern/qsort_r.c:9` includes this file)

## Reproduce

Guest (as root, `/usr/src` present, ≥8 GiB RAM):
```
sh guest_build.sh && sh guest_run.sh
```
Host (any cc; big-array modes need ≥8 GiB + permissive mmap):
```
sh build.sh && sh run.sh
```
Expected decisive lines:
```
TRUNCATION OOB CONFIRMED: comparator called with args past the array end (x-base=7894967296 …)
OOB COMPARATOR ARGS CONFIRMED: … y-base=-2144967296 … n*es=17200000000
PATCHED(f6): … patched: array IS SORTED
OVERALL: ALL_EXPECTATIONS_MET
```