umtx: use a distribution-fair multiplier for the chain hash

[nick_spun.io]

Summary

umtxq_hash() multiplies the key by 0x9E370001 and keeps the high bits.  That
constant is 0x9E37 * 2^16 + 1, so it degenerates for keys whose spacing carries
trailing zero bits: at a 64 KiB stride it puts 128 of 512 parked waiters onto a
single chain mutex, and at 16 KiB and up it uses only a handful of the 512
chains.  Base-system consumers never hit this because libthr places its own wait
words 128 bytes apart, but a Linux-ABI runtime waiting on addresses it allocates
itself lands squarely on the floor.  Switch to 0x61C88647, which leaves at most 3
waiters per chain at the same stride; Linux made this exact change in 2016, after
judging the sparse constants "actively bad for hashing".

[adrian]

I think it'll be worthwhile putting a comment in here explaining the behavioural differences between the two values. Eg, referencing the linux commit, explanation about sparse alloc'ed arenas and waits, etc.
Maybe like three or four lines tops?

[kib]

I do not see how this could be an option. Either there is no (bad) impact on the native umtxes, and then we should just change the constant, perhaps adding a comment explaining its origin and reasoning behind. Or there is the impact, but then you could check that the curproc ABI is linux, and use the proposed constant for Linux processes.

[nick_spun.io]

gate on abi

[nick_spun.io]

In D58337#1344794, @kib wrote:

I do not see how this could be an option. Either there is no (bad) impact on the native umtxes, and then we should just change the constant, perhaps adding a comment explaining its origin and reasoning behind. Or there is the impact, but then you could check that the curproc ABI is linux, and use the proposed constant for Linux processes.

I switched to the ABI-based check and it makes more sense, however after further testing I have only been able to demonstrate measurable impact in synthetic benchmarks that end up doing millions of umtx calls against a single chain under the sparse hash, and I don't think we're likely to ever need to guard against that under real-world conditions

That said, any impact from changing to the fair multiplier for _native_ workloads is minimal enough to blend in with background noise even if the the most common scenario gives slightly less contention under similarly-unlikely conditions under our current sparse multiplier.

Extremely unlikely but significant upside, and a virtually unmeasurable downside. Probably not worth losing sleep over either way.

[kib]

So again, why not change the multiplier unconditionally?

If there is evidence that we should not change it for native binaries, then I suggest to implement this differently. Add sv_umtx_hash_mult member to struct sysent, and set it accordingly for native vs linuxolators sysents. Then you do not need if() in umtxq_hash(), the p_sysent is de-referenced there anyway.

[emaste]

If there is evidence that we should not change it for native binaries

I agree with @kib - I would change it unconditionally, unless we can demonstrate that doing so somehow pessimizes native binaries.

[nick_spun.io]

just change the const

[adrian]

So hm, yay or nay on this?

[kib]

In D58337#1355750, @adrian wrote:

So hm, yay or nay on this?

Apparently I missed the submit button for one more review note.

sys/kern/kern_umtx.c

117

I do not think the comment is appropriate. History of the code needs to go into the commit message. The comment should explain the current state.

[nick_spun.io]

In D58337#1355810, @kib wrote:

In D58337#1355750, @adrian wrote:

So hm, yay or nay on this?

Apparently I missed the submit button for one more review note.

I'll cut it out

[nick_spun.io]

remove comment

[adrian]

oh, before I remove it - go update the comments - they need to be a bits horter and there's no longer a kernel config option for it.

[emaste]

Change looks fine to me. Agree w/ Adrian that the commit message can be shortened significantly.