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".
Details
Details
Diff Detail
Diff Detail
- Repository
- rG FreeBSD src repository
- Lint
Lint Skipped - Unit
Tests Skipped - Build Status
Buildable 75404 Build 72287: arc lint + arc unit
Event Timeline
Comment Actions
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?
Comment Actions
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.
Comment Actions
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.
Comment Actions
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.
Comment Actions
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.
Comment Actions
Apparently I missed the submit button for one more review note.
| sys/kern/kern_umtx.c | ||
|---|---|---|
| 118 | 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. | |
Comment Actions
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.
Comment Actions
Change looks fine to me. Agree w/ Adrian that the commit message can be shortened significantly.