DF-5146 — DRM hash tables collapse to a single bucket on 64-bit (local DoS)

What

sys/dev/drm/include/linux/hash.h:hash_64() misuses DragonFly's hash32_buf() (sys/sys/hash.h:44): its third argument is a djb2 initval, not a bit-width, and it returns a full 32-bit hash. hash_64() casts that to u64 and shifts right by (64 - bits) — which is identically 0 for every bits <= 32. On amd64 (hash_long == hash_64), every key hashed by sys/dev/drm/drm_hashtab.c (drm_ht_find_key:80, drm_ht_find_key_rcu:98, drm_ht_insert_item:117, drm_ht_just_insert_please:148) lands in bucket 0; the other 4095 buckets of the in-tree order-12 tables (drm_drv.c:603 dev->map_hash, drm_gem.c:148 mm->offset_hash) stay empty forever. All operations degrade to a linear walk of one sorted hlist: inserts O(n) (append-to-tail for the sequential alloc_unr keys used at drm_gem.c:576), lookups O(n) — and every GEM mmap lookup runs under the global DRM_LOCK (drm_gem.c:1089). Not memory corruption: the index is always in-bounds (0); correctness of find/dup-reject/remove is preserved (proven below).

Reproduce (on the DragonFly guest)

# pack copied to /root/df5146 on the guest
cd /root/df5146
sh build.sh     # builds userspace proof + kld twice: baseline + FIX=1
sh run.sh       # runs all three proofs, prints everything

Expected (baseline, stock kernel code):

RESULT: hash_long(key,bits)==0 for ALL 6400000 inputs ...
HTCOLLAPSE: per-1024-insert wall time (us): 581 1978 3689 ... 11403   <- grows linearly
HTCOLLAPSE: nonempty_buckets=1/4096 max_chain=8192 ...
HTCOLLAPSE: VERDICT ... hash_long collapse CONFIRMED in-kernel

Expected (fixed header, fixinc/linux/hash.h):

HTCOLLAPSE: per-1024-insert wall time (us): 19 18 18 17 18 17 17 18   <- flat
HTCOLLAPSE: nonempty_buckets=4096/4096 max_chain=2 ...
HTCOLLAPSE: VERDICT ... hash distributed normally (fixed header in effect)

Files

• hash64_collapse.c — userspace arithmetic proof (verbatim replication of sys/sys/hash.h + sys/dev/drm/include/linux/hash.h)
• htcollapse.c — kernel module harness; Makefile .PATHs the REAL unmodified /usr/src/sys/dev/drm/drm_hashtab.c into the module
• fixinc/linux/hash.h — fixed header used by make FIX=1 (the fix under test, byte-identical logic to fix.diff)
• build.sh, run.sh — exact commands
• build.log, run.log, run.2.log, env.txt — full untrimmed logs
• fix.diff — git-apply-able fix against sys/dev/drm/include/linux/hash.h
• manifest.json, verdict.json — machine-readable results

DF-5146 VERDICT — REPRODUCED (impact: local DoS; not memory corruption)

The bug

sys/dev/drm/include/linux/hash.h:32-39:

static inline u64 hash_64(u64 val, unsigned int bits)
{
    u64 ret;
    ret = (uint64_t)hash32_buf(&val, sizeof(val), bits);
    return ret >> (64 - bits);
}

hash32_buf() (sys/sys/hash.h:44-53) is a djb2 hash: hash = hash*33 + byte, third argument = initval (seed), returning a full 32-bit value. The Linux-compat port treated that argument as a bit-width and expected a pre-reduced result. It is not: the value is always < 2^32, so ret >> (64 - bits) is 0 for every bits in [1,32] (shift by >= 32 of a value that fits in 32 bits). bits == 0 would even be UB (>> 64).

On amd64 BITS_PER_LONG == 64, so hash_long == hash_64 (hash.h:50-54). Every hash_long() call in the DRM tree therefore returns 0:

• sys/dev/drm/drm_hashtab.c:80 (drm_ht_find_key)
• sys/dev/drm/drm_hashtab.c:98 (drm_ht_find_key_rcu)
• sys/dev/drm/drm_hashtab.c:117 (drm_ht_insert_item)
• sys/dev/drm/drm_hashtab.c:148 (drm_ht_just_insert_please)
• also sys/dev/drm/amd/lib/chash.c:398,433 (amdgpu concurrent hash, same root cause — out of scope for this finding, same fix).

Consequence for struct drm_open_hash (drm_hashtab.h:47): all items land in table[0] as one sorted hlist; buckets 1..4095 unused. The tables in tree are both created with order 12 (4096 buckets): sys/dev/drm/drm_drv.c:603 (dev->map_hash) and sys/dev/drm/drm_gem.c:148 (mm->offset_hash).

On i386, hash_long == hash_32 and ret >> (32 - bits) genuinely yields a bits-wide value — the bug is 64-bit-only.

Why it matters (threat)

• Keys for mm->offset_hash come from alloc_unr() (drm_gem.c:576) — sequential 1,2,3,... Insert of an increasing key walks to the tail of the single chain (drm_hashtab.c:120-126 keeps chains sorted, no early exit for the append case) → O(n) per insert, O(n^2) cumulative.
• Every GEM mmap does drm_ht_find_item(&mm->offset_hash, ...) under the global DRM_LOCK (drm_gem.c:1074, drm_gem.c:1089-1090); every legacy map mmap similarly (drm_vm.c:89-91). Lookups are O(n) with early-break, but held under the device-global lock.
• Reachability: an unprivileged user with /dev/dri/card0 access drives insertions via DRM_IOCTL_MODE_CREATE_DUMB + DRM_IOCTL_MODE_MAP_DUMB (drm_gem_dumb_map_offset, drm_gem.c:381-406, no master/auth required). Each object costs the attacker real memory (>= 1 page), so the quadratic CPU burn is bounded by that cost — a sustained CPU/stall vector (GPU subsystem lock contention), not an unbounded one. Hence severity Low/DoS, not higher.
• NOT memory corruption: hashed_key is always 0 → table[0] is always in-bounds (proven in kernel below: errors=0 across find/dup/remove cycles; the bucket index can never exceed the table size when it is constant 0). There is no uid=0 route through this bug.

Proof (guest: DragonFly 6.5-DEVELOPMENT x86_64, cc 8.3)

Three layers, all in run.log (stable across run.2.log):

1. Userspace arithmetic (hash64_collapse.c, verbatim replication of both headers): 6,400,000 key/bits combinations — hash_64 returned 0 for all of them (bits 1..32); i386-path hash_32 spreads.
2. In-kernel, real code (htcollapse.ko compiles the unmodified /usr/src/sys/dev/drm/drm_hashtab.c via the Makefile .PATH, same include flags as the drm module): 8192 sequential-key inserts into a real drm_ht_create(&ht, 12) table: - baseline: nonempty_buckets=1/4096 max_chain=8192, per-1024-insert time 581→11403 us (linear growth per chunk = O(n^2) total); - fixed header (make FIX=1, fixinc/linux/hash.h identical to fix.diff): nonempty_buckets=4096/4096 max_chain=2, flat 17-19 us chunks (~450-600x faster at the tail). - correctness identical in both builds: find(present)=0, find(absent)=-22, dup-insert=-EINVAL, remove/double-remove/reinsert=0, errors=0.
3. Fix validated: same real kernel code, only the header differs — the collapse is gone and behavior is normal, i.e. the fix is both sufficient and minimal. (Full drm.ko rebuild not needed: the kld compiled the real drm_hashtab.c with the same flags the drm module uses, drm/Makefile:121-124.)

What I checked and killed on drm_hashtab.c itself (pass 2)

• No open-addressing probe/wrap: this is hlist chaining with sorted chains (drm_hashtab.c:120-131), not linear probing — the "probe wraps forever on full table" class does not exist here. There is no sentinel/tombstone machinery at all (removal is a guarded unlink).
• No infinite loop in drm_ht_just_insert_please: bits is the constant 17 (drm_bufs.c:126: 32 - PAGE_SHIFT - 3), mask nonzero; the do-while exits when unshifted_key wraps to first (drm_hashtab.c:150-155).
• order is caller-constant 12 everywhere (drm_drv.c:603, drm_gem.c:148) — the 1 << order UB for order>=32 (drm_hashtab.c:43) and the u8 truncation of order (drm_hashtab.h:49) are latent hardening gaps only, unreachable from any in-tree path.
• Double-remove / remove-of-unhashed: hlist_del_init_rcu maps to hlist_del_init which is hlist_unhashed-guarded (list.h:341-348) — proven idempotent in the kld run (double drm_ht_remove_item + reinsert OK).
• drm_ht_remove double-call: NULL-guarded, sets table=NULL (drm_hashtab.c:200-206); items are embedded in caller objects, the table never owns/frees them — no double-free surface.
• Info leak: none; no copyout of table internals; keys are kernel offsets.
• Cross-file observation for the drm_gem.c audit (NOT this finding): drm_gem.c:397's insert path shows no obvious lock; the hashtab contract (drm_hashtab.h:64-72) requires external serialization — flag it there.

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.