FreeBSD / _umtx_op / hashing

The Chain Hash

reference: how a wait word picks its chain lock, and where the picking degenerates the fair-hash fix landed distribution collapse proven; effect is tail latency, not throughput numbers measured from a bit-exact model of umtxq_hash

umtxq_hash() maps a wait word to one of 512 chain locks with a multiplicative hash: multiply the key by an odd constant, then keep the top nine bits. The multiplier is the whole story. A bit-sparse one mixes poorly, and for keys spaced a power-of-two apart - what aligned allocation produces - it piles most waiters onto a handful of chains.

The base system never saw this: libthr places one lock object per mutex, 128 bytes apart, and that stride happens to saturate the table exactly. A Linux-ABI runtime that parks its futex words a power-of-two stride apart lands squarely on the floor. Every figure below comes from a bit-exact model of the hash, not a live kernel.

One multiply, keep the top nine bits

The map from a wait word to a chain lock key n = a + b base a + in-object offset b n * mult mod 2^32 >> UMTX_SHIFTS __WORD_BIT - 9 = 23 % UMTX_CHAINS one of 512 chains Only nine bits survive; the multiply exists to carry key bits into them bits 31..23 kept bits 22..0 discarded by the >> 23 Nine kept bits index 512 chains. Since the shifted product is already below 512, the % UMTX_CHAINS is a no-op at this table size. Why the sparse constant collapses 0x9E370001 = 0x9E37 * 2^16 + 1 -> n * 0x9E370001 = n + (n * 0x9E37 << 16) A key stride with s trailing zeros pushes the shifted copy s bits higher. At s = 16 it leaves the 32-bit word: the product == n, and the hash is just the top bits of the raw address - which a strided sample barely moves, so a few chains carry everyone. sparse 0x9E370001 -> avalanche 26.9% fair 0x61C88647 -> avalanche 45.4% (ideal 50%)
The multiplier is the only free parameter. The key is a high-entropy base plus a strided offset; the shift throws away everything but the top nine bits, so the hash is only as good as the multiply's ability to mix low and middle key bits upward. The sparse constant is 0x9E37 * 2^16 + 1, chosen historically so the multiply reduces to shifts and adds; that same structure is what fails on aligned keys. Avalanche - the mean fraction of output bits that flip per input-bit flip - is 26.9% for it against 45.4% for the fair constant.

Stride versus peak chain occupancy

0 32 64 96 128 peak chain occupancy (deepest of 512) 64 Bs=6 128 Bs=7 512 Bs=9 4 KiBs=12 16 KiBs=14 64 KiBs=16 1 MiBs=20 8 MiBs=23 allocation stride, power-of-two aligned (log2) fair 0x61C88647 sparse 0x9E370001 sparse: 128 of 512 waiters on one chain product == n; the hash is the raw top bits a 64 B step changes s and the pile is gone s >= 22: sparse spreads again
The collapse is a bounded window, not a slope. The fair curve is flat: its deepest chain is 2 across the whole range. The sparse curve is quiet at small strides, spikes to a plateau of 128 across the 16 to 64 KiB window, then returns to baseline. At the 64 KiB peak the sparse hash touches only about 5 of the 512 chains while the fair hash touches about 475 - a ~95x spread - and its deepest chain holds 128 of the 512 parked waiters against the fair hash's 2. The window is bounded on both sides: a 64-byte offset changes the trailing-zero count and erases it, and above a 4 MiB stride (s >= 22) both multipliers are perfect again. Peak is measured from the model.

The same waiters, dealt to chains

sparse 0x9E370001, 64 KiB stride fair 0x61C88647, 64 KiB stride 128 ~5 of 512 chains carry everyone; deepest chain 128 ~475 of 512 chains used; deepest chain 2 Schematic: 512 parked waiters over 512 chains, one bar per chain. Each chain is a mutex; a deeper chain is a longer walk and more contention on that one lock.
Same 512 waiters, same 512 chains, two multipliers. The sparse hash concentrates them; the fair hash spreads them. The table is the model output that the drawings summarise.
stridetrailing zeros ssparse: chains used / deepestfair: chains used / deepest
64 B6317 / 2457 / 2
128 B (libthr per-lock stride)7512 / 1468 / 2
512 B9128 / 4485 / 2
4 KiB1216 / 32228 / 4
16 KiB148 / 96305 / 2
64 KiB (peak)165 / 128475 / 2
1 MiB2065 / 8447 / 2
8 MiB23512 / 1512 / 1
Measured from the model: 512 keys into 512 chains, median over 2000 random bases standing in for the object or vmspace pointer. At 128 B - libthr's stride - the sparse hash saturates the table exactly (all 512 chains, depth 1), which is why the base system never suffered. Deepest chain reaches 128 in the worst case at 16 KiB as well as 64 KiB.

The fix: one constant, swapped for every key

One multiplier, swapped for every key was 0x9E370001 (sparse) now 0x61C88647 = GOLDEN_RATIO_32 (fair) key->hash = ((n * GOLDEN_RATIO_32) >> UMTX_SHIFTS) % UMTX_CHAINS; one unconditional constant - no branch on the calling ABI, so a waiter and a waker always agree one multiplier: 0x61C88647 native _umtx_op(2) keys mutex, cv, sem, ... - now fair too, fine at the 128 B stride Linux futex(2) keys TYPE_FUTEX / TYPE_PI_FUTEX, via linux_futex.c Latent: UMTX_SHIFTS = __WORD_BIT - 9 = 23 against a 32-bit product, so (n * mult) >> 23 is always < 512. The % UMTX_CHAINS is a no-op at 512, and any UMTX_CHAINS > 512 is unreachable - enlarging the table would be a silent no-op.
The shipped change is a single unconditional swap. umtxq_hash multiplies every key - native umtx and Linux futex alike - by the fair 0x61C88647 (GOLDEN_RATIO_32) in place of the sparse 0x9E370001; there is no per-ABI branch. It is safe for the base system because native consumers never exercised the pathology: libthr's 128 B stride already saturates the table, and the fair constant handles that stride too. A Linux-only variant was considered, but the change that shipped is this simpler global swap. The latent point is separate and unfixed: the shift is hardwired for a 512-entry table, so the "just enlarge the table" remedy cannot take effect here.

What the drawings commit to

  • The multiplier is the only lever. The shift keeps nine bits and the reduction is a no-op at this table size, so distribution quality is entirely how well the multiply mixes key bits into the top nine.
  • The collapse is real and bounded. At a 64 KiB stride the sparse constant piles 128 of 512 waiters onto one chain and touches about 5 chains against the fair constant's 475; a 64-byte offset erases it, and a stride at or above 4 MiB restores it.
  • It is a distribution fact, not a throughput claim. Block rate is low, so almost every operation is an uncontended fast path. Where the collapse shows up is tail latency - a crowded chain lock spins, then sleeps - not operations per second.
  • The base system was never exposed. libthr's 128-byte per-lock stride saturates the sparse table exactly, which is why this went unremarked for two decades.
  • The exposed consumers place their own wait words. A Linux-ABI runtime that parks futex words a 32 to 64 KiB stride apart lands on the floor; the shipped fix swaps the single umtxq_hash multiplier to the fair constant for every key, native and Linux alike.