Provide protection against starvation of the ll/sc loops when accessing userpace.

[kib]

Summary

Casueword(9) on ll/sc architectures must be prepared for userspace constantly modifying the same cache line as containing the CAS word, and not loop infinitely. Otherwise, rogue userspace livelock kernel.

To fix the issue, change casueword(9) interface to return new value 1 indicating that either comparision or store failed, instead of relying on the oldval == *oldvalp comparison. The primitive no longer retries the operation if it failed spuriously. Modify callers of casueword(9) (all in kern_umtx.c) to handle retries, and react to stops and requests to terminate between retries.

On x86, despite cmpxchg should not return spurious failures, we can take advantage of new interface and just return PSL.ZF.

Sponsored by: The FreeBSD Foundation
Reported by: https://xenbits.xen.org/xsa/advisory-295.txt

Test Plan

I only booted on x86 and did some sanity checks like running libthr kyua tests.

[kib]

Update ppc inline asm comment.

[andrew]

I'm happy with the arm and arm64 changes.

sys/arm64/arm64/support.S

71

Extra newline

[kib]

Remove extra empty line.

[pho]

I ran all of the threaded tests I have, twice. I also did a buildworld / installworld. This on amd64.
I'll run some i386 tests once my test box is available.

[markj]

share/man/man9/casuword.9

110

Typo in "comparison."

sys/kern/kern_umtx.c

1074

How can we have rv != 1 at this point?

1104

I think this block is dead code now. Previously, casueword32 would return 0 even if the comparison failed. Now it returns 1 in that case, but here we know that rv == 0, so it must be that owner == UMUTEX_UNOWNED. Am I missing something?

[kib]

sys/kern/kern_umtx.c

1104

Sure, this is the bug. The block must not be dead, I moved the checks for rv == 1 further. We must handle UMUTEX_CONTESTED there.

[kib]

Hopefully fix two bugs.

One pointed out by Mark and related to missed handling of contended mutexes. Another reported by Peter where I restarted inner loop of sem2_wait with unbusied chain, while loop expects it busy.

[emaste]

FWIW I have sent links to this change to OpenBSD, NetBSD and DragonFly BSD developers.

[brooks]

mips64 (with CHERI) boots with this patch applied.

sys/kern/kern_umtx.c

2719

unrelated style change should probably be a separate commit (also the only conflict against CheriBSD)

[markj]

sys/i386/i386/copyout.c

440–441

Isn't this inverted? atomic_(f)cmpset returns 1 on success, 0 on failure.

[kib]

sys/i386/i386/copyout.c

440–441

Yes it is, it was reported by Peter earlier. I fixed it in my branch, will upload new patch after pho finishes.

[markj]

sys/kern/kern_umtx.c

1176

Why not just continue?

1185–1186

This condition is always true.

1227–1228

It is guaranteed that old == owner here.

1263–1270

It is guaranteed that old == owner here.

1328–1331

If error == 0 then we must have owner == UMUTEX_CONTESTED, so (owner & ~UMUTEX_CONTESTED) == 0 is always true.

1397–1398

If error == 0 we know that old == owner.

1910–1911

What if rv == 1?

[kib]

sys/kern/kern_umtx.c

1328–1331

error == 0 case can happen when count > 1, in which case we did not executed casueword32() at all. And then either owner == UMUTEX_CONTESTED or this is a dying robust mutex.

I think it would be cleaner just to move the part after second '&&' into MPASS().

[kib]

Fix i386 casueword.
Handle Mark' notes.
Committed style change.

[pho]

On i386 I ran a buildworld / installworld + random stress2 tests for a total of 10H30.
On amd64 I ran random stress2 test for 10H30.
No problems seen.

[danfe]

Observations like "this condition is always true" and "it is guaranteed that old == owner here" should ideally be verified by static code analysis. I'd try to apply the patch and run PVS-Studio over it.

[kib]

In D20772#450488, @danfe wrote:

Observations like "this condition is always true" and "it is guaranteed that old == owner here" should ideally be verified by static code analysis. I'd try to apply the patch and run PVS-Studio over it.

In theory it can be, but in reality it would not work by itself. You must provide casueword(9) model to the tool, explaining how oldval/*oldvalp/newval and the return values are related (see patched man page). I know that Coverity has a way to augment semantic of the analyzed program this way, but I do not know how. No idea about PVS.

[markj]

sys/kern/kern_umtx.c

1945–1946

This code is unreachable.

2003–2004

This condition must be true.

2933

The line wraps could be committed separately.

2946

It seems inconsistent that we sleep here.

3128

If oldstate != state and rv != -1, then rv == 1.

3148

Same here.

3343

This test is redundant.

3419

This should be an else if.

[kib]

Handle reported issues, except the sleep in umtxq_check_susp.
Rebase after style changes were committed.

[kib]

Original idea of the sleepable vs. non-sleepable umtxq_check_susp() was that existing (pre-patch) calls should be left non-sleepable, while new cases where rv == 1 are sleepable. Apparently this is too strict (wrong) and cases where we loop or own a busy ref on a key should be non-sleepable as well.

I will do the pass over the patch to adjust it according to the stated rules later.

[jilles]

sys/arm64/arm64/support.S

69

Hmm, is the value in w5 overwritten by SET_FAULT_HANDLER?

sys/riscv/riscv/support.S

71

Hmm, a5 seems to have been overwritten twice with temporary addresses (in EXIT_USER_ACCESS and SET_FAULT_HANDLER).

[kib]

Fix arm64 and riscv asms.
Add a long comment explaining the sleep argument to umtxq_check_susp().
Do pass over the sleep arguments used aligning them with the explanation.

[markj]

sys/riscv/riscv/support.S

64

Suppose we follow the branch. Aren't we going to return the uninitialized contents of a5?

66

Why not use beqz?

[kib]

Fix issues with risc-v casueword.

[markj]

sys/arm64/arm64/support.S

69

I think w5's contents are uninitialized if we follow the branch to label 2.

90

Same here.

sys/kern/kern_umtx.c

695

s/operations/operation/

2162

The key is busied here, so we cannot sleep.

2238–2240

Whitespace looks wrong here.

2239

If rv == 0 we must have owner == UMUTEX_CONTESTED.

[kib]

sys/kern/kern_umtx.c

2239

I re-wrote the logic for rv == 1 completely.

[kib]

do_lock_pp and arm64 casueword fixes.

[kib]

Thank you, Mark.

Peter, could you, please, run the tests one more time, hopefully this is the last.

[pho]

In D20772#452692, @kib wrote:

Thank you, Mark.

Peter, could you, please, run the tests one more time, hopefully this is the last.

Sure, happy to.
A full test on both amd64 and i386, right?

[kib]

Bugfixes after Peter' testing.

[markj]

sys/kern/kern_umtx.c

1927

Typo: signal