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

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.