Bug 198014 - Signals can lead to an inconsistency in PI mutex ownership
Summary: Signals can lead to an inconsistency in PI mutex ownership
Status: Closed FIXED
Alias: None
Product: Base System
Classification: Unclassified
Component: kern (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Some People
Assignee: Eric van Gyzen
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-02-24 21:20 UTC by eric
Modified: 2015-07-22 21:26 UTC (History)
4 users (show)

See Also:


Attachments
Proposed patch (2.48 KB, patch)
2015-02-24 21:21 UTC, eric
no flags Details | Diff
Patch to restore owner after umtx_pi_claim fails (1.11 KB, patch)
2015-02-24 21:26 UTC, eric
no flags Details | Diff
Patch to return errors from _thr_umutex_unlock2 (1.82 KB, patch)
2015-02-24 21:27 UTC, eric
no flags Details | Diff
Deterministic test case (8.41 KB, text/x-c)
2015-02-24 22:49 UTC, eric
no flags Details
Randomized, racy test case (6.32 KB, text/x-c)
2015-02-24 22:53 UTC, eric
no flags Details
Test case for r277970 (3.83 KB, text/x-c)
2015-02-24 22:58 UTC, eric
no flags Details
Proposed patch (2.60 KB, patch)
2015-02-25 15:06 UTC, eric
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description eric 2015-02-24 21:20:00 UTC
Signals can lead to an inconsistency in PI mutex ownership.

I have two test cases to reproduce this.  I hope to provide them soon.  For now, here is the description.

Consider three threads--Trun, Tsleep, and Tsig--all contending for one pthread mutex.  Trun owns the mutex and is running in userspace.

Tsleep wants the mutex and calls pthread_mutex_lock...do_lock_pi.  Near the top of do_lock_pi, Tsleep allocates a umtx_pi object.  This object will exist as long as at least one thread is in do_lock_pi for this mutex.  Since Trun owns the mutex, Tsleep sets UMUTEX_CONTESTED and calls umtxq_sleep_pi.  Therein, Tsleep adds itself to the queue of waiters (umtxq_insert) and assigns ownership of the umtx_pi to Trun (umtx_pi_setowner).  It then sleeps in utmxq_sleep.

Tsig wants the mutex and does the same as Tsleep, with a few differences.  Tsig does not allocate a new umtx_pi; instead, it finds the existing umtx_pi and increments its reference count.  Tsig becomes the second thread in the queue of waiters.  Tsig does not set ownership of the umtx_pi, since that's already done.  Tsig then sleeps in umtxq_sleep.

Trun calls pthread_mutex_unlock...do_unlock_pi.  Therein, umtxq_count_pi indicates that Tsleep is the first thread on the queue of waiters.  Trun disowns the umtx_pi, removes Tsleep from the queue of waiters, and makes it runnable.  However, Tsleep does not run immediately, for whatever reason.  Perhaps all CPUs are busy.  Perhaps CPU sets, priorities, and schedling policy allow Trun to keep running while Tsleep sits on the run queue.

Trun calls pthread_mutex_lock...do_lock_pi again.  It acquires the mutex, claims ownership of the umtx_pi (umtx_pi_claim), and returns to userland.

A thread sends a signal to Tsig.  It returns from umtxq_sleep, removes itself from the queue of waiters, and ultimately returns from do_lock_pi.  The queue of waiters is now empty.

Trun calls pthread_mutex_unlock...do_unlock_pi.  Unlike last time, umtxq_count_pi says the queue is empty, so Trun does not disown the umtx_pi.  (Recall that the umtx_pi remains in existence due to the reference by Tsleep.)  Trun sets the mutex to UMUTEX_UNOWNED and returns.

Now, the mutex and umtx_pi disagree on the ownership of the mutex.  From here, there are several possible paths to failure.  For completeness, let's follow through with one.

Any thread--Tany--locks the mutex.  Any other thread--Tother--tries to lock it, sets the contested bit, adds itself to the queue, and sleeps.  Tany unlocks the mutex; since it's contested, Tany calls do_unlock_pi.  Since Tother is in the queue, uq_first is non-NULL.  Recall that Trun still owns the umtx_pi, so pi->pi_owner != curthread, so do_unlock_pi returns EPERM and leaves the umutex owned by Tany.  Before calling do_unlock_pi, Tany had already disowned the pthread_mutex.  The error from _thr_umutex_unlock2 has no effect.

So, nobody owns the pthread_mutex, Tany owns the umutex, and Trun owns the umtx_pi.  Prior to r277970, this broken ownership could have caused a panic.  Now, it just causes operations on this mutex to fail, or possibly causes a deadlock among the contending user threads.

To solve this problem, do_unlock_pi should disown the umtx_pi even if the queue of waiters is empty.
Comment 1 eric 2015-02-24 21:21:30 UTC
Created attachment 153475 [details]
Proposed patch
Comment 2 eric 2015-02-24 21:23:00 UTC
With this patch, all of my tests pass.
Comment 3 eric 2015-02-24 21:26:03 UTC
Created attachment 153476 [details]
Patch to restore owner after umtx_pi_claim fails
Comment 4 eric 2015-02-24 21:27:32 UTC
Created attachment 153477 [details]
Patch to return errors from _thr_umutex_unlock2
Comment 5 eric 2015-02-24 21:28:43 UTC
Here are two more patches to fix minor issues that I found during this bug-hunt.
Comment 6 eric 2015-02-24 22:49:47 UTC
Created attachment 153485 [details]
Deterministic test case
Comment 7 eric 2015-02-24 22:53:17 UTC
Created attachment 153486 [details]
Randomized, racy test case
Comment 8 eric 2015-02-24 22:58:15 UTC
Created attachment 153487 [details]
Test case for r277970

This is a test case for the bug fixed by r277970.  I'm attaching it here just for reference and completeness.  The present bug is the reason that I found the one fixed by r277970.  (There is no Bugzilla bug for it.)
Comment 9 Konstantin Belousov freebsd_committer freebsd_triage 2015-02-25 13:38:03 UTC
I agree with all three patches, with one detail.

In the first patch, which does umtx_pi_disown() for empty queue, shouldn't the case of pi->pi_owner != curthread be handled the same as it is done in the non-empty queue case ?  The 'might' condition from the the comment really means that the umutex and the kernel state are un-synchronized, and the 'userland messed the mutex' situation is applicable in the same way there.
Comment 10 eric 2015-02-25 14:22:40 UTC
I considered this, but I'm indecisive.  The current "userland messed the mutex" error path compounds the problem by leaving the umutex owned by the current thread, while libthr already disowned the pthread_mutex.  I wonder if it should disown the umutex.  This might allow the mutex owner fields to regain consistency.  On the other hand, maybe we should let it stay inconsistent to make the failure more permanent; this might prevent the application from corrupting its state even further.

Regardless, you're right that the empty case should be consistent with the non-empty case when another thread owns the umtx_pi, since I believe this is still an error.  Note that the umtx_pi could legitimately be unowned in the empty case, such as immediately after umtx_pi_alloc.

I'm testing an updated patch now.
Comment 11 Konstantin Belousov freebsd_committer freebsd_triage 2015-02-25 14:27:59 UTC
(In reply to eric from comment #10)
I do not have an opinion which case currently is handled more correctly.  I tend to agree with notion that empty case handling of silent ignore of the foreign owner is probably more appropriate.

Also, it took me some time to understand how pi_owner could be NULL.  Probably, a comment should be added.  I also suggest to split the comment in if (pi != NULL) into two.  The first sentence should go before if (pi != NULL) test, and the second sentence left as is.
Comment 12 eric 2015-02-25 15:04:51 UTC
(In reply to Konstantin Belousov from comment #11)

OK, we can ignore the foreign owner.  I've tested that code quite a bit already.

I'll change the comments, as you suggest.
Comment 13 eric 2015-02-25 15:06:38 UTC
Created attachment 153524 [details]
Proposed patch

Adjust comments based on Konstantin's feedback.
Comment 14 Eric van Gyzen freebsd_committer freebsd_triage 2015-07-22 21:26:44 UTC
These fixes were committed by kib@ as r279282, r279283, and r279284.