alst_leaf_alloc corrupts bm_bighint hint by mutating start before the bighint-decision comparison

Summary

alst_leaf_alloc executes start &= ALIST_BMAP_RADIX - 1 (:443), converting the absolute allocation-start address into a leaf-relative index (0..31) before it is used to decide whether bm_bighint may be lowered (:451 if (start <= blk) and :509). The subsequent start <= blk comparison then compares a relative offset against an absolute leaf base; for every leaf except the first (blk >= 32), it is always true, so the failure path unconditionally writes scan->bm_bighint = count - 1 (or 0) even when the caller's start was mid-leaf and only bits [start-blk .. 31] were searched. This violates the documented invariant ("bighint will never contain a value that is too low"), can persistently mark a leaf as unable to satisfy an allocation it could, and causes spurious ALIST_BLOCK_NONE returns from the meta recursion.

Root cause

sys/kern/subr_alist.c:443:

start &= ALIST_BMAP_RADIX - 1;          /* absolute -> relative (0..31) */
...
if (orig == 0) {
    if (start <= blk)                    /* :451  relative <= absolute => always true for blk>=32 */
        scan->bm_bighint = 0;
    return(ALIST_BLOCK_NONE);
}
...
if (start <= blk)                        /* :509  same */
    scan->bm_bighint = count - 1;

The intended test is orig_start <= blk (did we search the entire leaf?).

Threat model & preconditions

• Attacker position: indirect only. The sole in-kernel consumer is vm_contig_alist (vm_page.c:435, fixed 65536-block = 256 MB low-DMA reserve); alloc/free params come from physical-page bookkeeping. An unprivileged user can only influence this via allocation patterns (fragmentation), hence AC:H.
• Privileges gained or impact: availability — a corrupted-too-low bighint makes alst_meta_alloc:615 skip a leaf that actually has sufficient contiguous free space, so vm_page_alloc_contig spuriously returns NULL → driver/device probe or transfer failure. No memory corruption, privilege change, or info leak. The condition self-heals on the next alst_leaf_free (:684 resets bighint = ALIST_BMAP_RADIX).
• Confidence: likely (the bug is certain; reachability is kernel-internal / indirect).

Proof of concept (sketch)

Reproducible with the in-tree standalone debug harness (subr_alist.c:993, compiled -DALIST_DEBUG): create an alist of ≥64 blocks, free a range so the leaf at blk=32 has free bits in positions 0..15 but the search start is 48, attempt a 16-block allocation with start=48 — it fails and dumps bm_bighint=15 for that leaf; a subsequent allocation with start=0 that should fit in bits 0..15 of the same leaf is rejected because 16 > bighint(15) at the meta guard (:615).

Impact

Low — availability only (spurious contiguous-DMA allocation failure), no memory corruption. The only consumer is a fixed-size kernel-internal alist.

Recommended fix

Save the absolute start before the mutation and use it for the bighint decisions:

--- a/sys/kern/subr_alist.c
+++ b/sys/kern/subr_alist.c
@@ -437,6 +437,7 @@
    alist_bmap_t orig = scan->bm_bitmap;
+   alist_blk_t orig_start = start;
 ...
@@ -450,7 +451,7 @@
    if (orig == 0) {
-       if (start <= blk)
+       if (orig_start <= blk)
            scan->bm_bighint = 0;
        return(ALIST_BLOCK_NONE);
    }
 ...
@@ -508,7 +509,7 @@
-   if (start <= blk)
+   if (orig_start <= blk)
        scan->bm_bighint = count - 1;
    return(ALIST_BLOCK_NONE);

References

• sys/kern/subr_alist.c:443,451,509 — the start mutation + comparisons.
• sys/sys/alist.h:59-60 — the bm_bighint "never too low" invariant.
• CWE-684 Violation of Invariants; CWE-704 Incorrect Type Conversion.

Timeline

• 2026-06-29 Discovered during automated file-by-file audit of sys/kern/subr_alist.c.
• pending Reported to DragonFlyBSD security contact.