476536 - Assertions need to be able to check the state of particular locks

Status: RESOLVED FIXED

(NSPR :: NSPR, enhancement, P2)

Description

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It would be really really useful for building more robust code if we had some kind of helper function like PR_CurrentThreadHoldsLock(PRLock*), even if it's only available in debug builds. Same for monitors. Seems like this would be easy to implement by adding a debug-only field to PRLock, even if there's no direct way to implement it.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

For monitors, there is already such a function.  PR_InMonitor(m)

NSSRWLocks have function NSSRWLock_HaveWriteLock, which is essentially
return (PRBool)(PR_GetCurrentThread() == rwlock->rw_owner);

These functions work in both debug and non-debug builds, IIRC.

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Oh, are we allowed to #include "private/pprthred.h"?

Comment 3

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Wan-Teh --- is it OK for me to take this bug?

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

Chris, Feel free to attach a patch to any open NSPR bug!
If the NSPR module owners like it, they'll give the bug to you.

Comment 5

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: Add CurrentThreadOwns* functions for Lock, Monitor, and CMonitor

Notes:

1. Also included is a bugfix for the bthreads implementation of PR_GetMonitorEntryCount
2. Only the pthread implementation has been tested (or compiled :( ), sorry.  Is there an easy way for me to test the changes across all platforms nspr supports?
3. The pthreads implementation of PR_CurrentThreadOwnsLock is fairly subtle, so please review it especially carefully
4. The lock.c test has been expanded to use the new querying functions liberally, and has passed several runs on my Linux machine.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 367342 [details] [diff] [review]
Add CurrentThreadOwns* functions for Lock, Monitor, and CMonitor

There are two separate issues that must be reviewed here.
1) Is the new API presented here the right/desirable API, and
2) Is the implementation of it satisfactory?

I expect Wan-Teh will have strong opinions on the former,
so I want him to also weigh in here on that question.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

Wan-Teh, 
if you're satisfied with the API, I'm satisfied with the implementation.

Comment 8

[Wan-Teh Chang]

Comment on attachment 367342 [details] [diff] [review]
Add CurrentThreadOwns* functions for Lock, Monitor, and CMonitor

Chris, thanks for the patch.  I took a quick look at it.
Here are some preliminary comments.

1. Don't bother changing prcmon.h.  The cached monitors
came from NSPR's early days as the underpinning of Netscape's
port of Sun Java VM.  Cached monitors are used to implement
Java's "synchronized" keyword.  We should discourage the
use of cached monitors in new code.

2. It's important to note that the OwnsLock function only
works correctly when the current thread owns the lock.
If the current thread doesn't own the lock, it will be
reading the 'locked' and 'owner' fields without holding
the lock, so there's no memory consistency to speak of.
We can only provide this guarantee, and you need to read
this as a mathematical statement (P => Q):

  If the current thread owns the lock, OwnsLock() returns true.

So, we can't guarantee this:

  If the current thread doesn't own the lock, OwnsLock() returns
  false.

Your changes to the test programs should not contain assertions
that assert OwnsLock() returns false.

3. Therefore, it's fine to reorder the assignments of 'locked'
and 'owner' to increase the likelihood of getting the desired
result when the current thread doesn't own the lock, but we
need to realize that no guarantee can be made in that condition.
Even the compiler is allowed the reorder the two assignment
statements.

4. You may want to consider designing an API so that OwnsLock()
can't be misused.  Perhaps we should provide only an
AssertOwnsLock() function (or macro) that returns void, so
that people can't assert !OwnsLock() by mistake.

Comment 9

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Thanks for this great review.

> 1. Don't bother changing prcmon.h.  The cached monitors
> came from NSPR's early days as the underpinning of Netscape's
> port of Sun Java VM.  Cached monitors are used to implement
> Java's "synchronized" keyword.  We should discourage the
> use of cached monitors in new code.
> 

Will do!

> 2. It's important to note that the OwnsLock function only
> works correctly when the current thread owns the lock.
> If the current thread doesn't own the lock, it will be
> reading the 'locked' and 'owner' fields without holding
> the lock, so there's no memory consistency to speak of.
> We can only provide this guarantee, and you need to read
> this as a mathematical statement (P => Q):
> 
>   If the current thread owns the lock, OwnsLock() returns true.
> 
> So, we can't guarantee this:
> 
>   If the current thread doesn't own the lock, OwnsLock() returns
>   false.
> 
> Your changes to the test programs should not contain assertions
> that assert OwnsLock() returns false.
> 
> 3. Therefore, it's fine to reorder the assignments of 'locked'
> and 'owner' to increase the likelihood of getting the desired
> result when the current thread doesn't own the lock, but we
> need to realize that no guarantee can be made in that condition.
> Even the compiler is allowed the reorder the two assignment
> statements.
> 
> 4. You may want to consider designing an API so that OwnsLock()
> can't be misused.  Perhaps we should provide only an
> AssertOwnsLock() function (or macro) that returns void, so
> that people can't assert !OwnsLock() by mistake.
> 

The crux of all these points is whether or not to guarantee the inverse (!OwnsLock()).  So I'll address them all together.  Assuming that we decide NOT to guarantee the inverse, I agree with all your objections/suggestions.  My argument is that we can provide both OwnsLock() and !OwnsLock() given appropriate memory consistency, and that we can achieve this appropriate consistency.  "Sequential consistency" is close enough for intuition, but technically "linearizability" is what we want.

There are two issues I need to address.  First, is the implementation correct assuming consistent memory?  I'm very comfortable that this is true.  The pthreads implementation is the only somewhat sneaky one, and it has been validated by the 'spin' model checker for up to 5 threads doing 10e6 concurrent lock/unlock, and 7 threads doing 1e5.  I can post the model if desired.

Second, can nspr rely on or provide consistent memory?  This depends on both the compiler and architecture.  For all the modern compilers and architectures I'm familiar with, (1) I seriously doubt the accesses will be reordered; and (2) even so, memory fence instructions are available to enforce the guarantee at the architecture level.  These make !OwnsLock() linearizable.

HOWEVER, if worrying about memory fences etc. is a maintenance burden beyond nspr's scope, then I completely agree with not guaranteeing !OwnsLock().

Comment 10

[Wan-Teh Chang]

PR_Lock and PR_Unlock already provide memory fences.
If the new OwnsLock function adds more memory fences
so that we can assert !OwnsLock() correctly, the cost
is too high.  (Memory fence instructions can be
expensive.)  Also, we can't assume that pthread_t
(the return value of pthread_self) can be read or
written atomically.

I believe that you don't need to assert !OwnsLock().
So the requirement to only assert OwnsLock() isn't
really a limitation.

Comment 11

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Suits me.

Comment 12

[Shawn Wilsher :sdwilsh]

(In reply to comment #10)
> PR_Lock and PR_Unlock already provide memory fences.
> If the new OwnsLock function adds more memory fences
> so that we can assert !OwnsLock() correctly, the cost
> is too high.  (Memory fence instructions can be
> expensive.)  Also, we can't assume that pthread_t
> (the return value of pthread_self) can be read or
> written atomically.
Is it really that bad of a cost that we cannot ensure this correctness for debug builds at least (assuming NSPR has debug only builds)?  There are places in code where I want to ensure that we don't hold a lock, and in other places where I'd want to assert that we hold it.

Comment 13

[Wan-Teh Chang]

I'm not qualified to review patches that use memory
fences.  I'm not embarassed to admit that I find
relaxed memory consistency models hard to understand.
There should be some Mozilla developers who can
answer your question.  I try to stay within the
comfort zone of using locks.

Comment 14

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

>> PR_Lock and PR_Unlock already provide memory fences.
>> If the new OwnsLock function adds more memory fences
>> so that we can assert !OwnsLock() correctly, the cost
>> is too high.  (Memory fence instructions can be
>> expensive.)  Also, we can't assume that pthread_t
>> (the return value of pthread_self) can be read or
>> written atomically.
> Is it really that bad of a cost that we cannot ensure this correctness for
> debug builds at least (assuming NSPR has debug only builds)?  There are places
> in code where I want to ensure that we don't hold a lock, and in other places
> where I'd want to assert that we hold it.
> 

I think (but didn't verify) that we would need one additional memory fence to ensure correctness of !OwnsLock().  100 cycles is usually quoted as the cost of a memory fence for the executing thread, although it can be worse than that considering secondary effects like invalidated cache entries etc.  Still, I don't think this a prohibitive overhead in DEBUG builds.

The reason I came over to Wan-Teh's side is threefold.  First, I think that he's right that asserting OwnsLock() is much more important than asserting !OwnsLock().  The only use I can think of for the latter is catching errors such as improper Unlock()ing, but these kinds of errors usually result in deadlock (which is already caught).  Also, it's easy to catch these errors in destructors (assert !lock->locked).  Second, memory fences require architecture-specific support, not just platform-specific support.  This greatly increases the implementation complexity.  And third, the original implementation of !OwnsLock() is going to work on most architectures probably 99.9999...% of the time; if desired, it can be exposed through a "discouraged" API (like "#include "nspr/private.h").

But if you can provide very compelling uses of !OwnsLock(), I'm willing to reconsider my position.

Comment 15

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: Patch v2, with updated API

Comment 16

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

I should add, once again, that only the pthreads implementation has been compiled and tested.

Comment 17

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I agree asserting OwnsLock is much more useful than !OwnsLock, but !OwnsLock is still quite useful IMHO. It's not necessarily for improper unlocking per se, but for example ensuring that certain locks are not held across callbacks to other modules. In those cases a deadlock might not actually occur even though invariants are being violated. We might not even trigger potential-deadlock warnings if the callback paths tested happen to not take any other locks. Even if we do trigger potential-deadlock warnings, asserting !OwnsLock gives an earlier warning. It's also useful documentation that we can be sure stays consistent with the code.

One option would be to have an NS_ASSERT_LOCK_HELD macro and an NS_ASSERT_LOCK_NOT_HELD macro. The latter could simply be defined to nothing on architectures that we care less about. If the assertion is only checked on memory-consistent x86 machines running Mac OS, Windows and Linux then I think that's definitely worth having.

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Having said that, we shouldn't let discussions about a !OwnsLock feature hold up the OwnsLock feature, so we should spin the former out to a separate bug if it remains an issue.

Comment 19

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

I think that in the long term, XPCOM should bypass PR_Lock for other reasons like being able to put locks on the stack.  It's probably better to forestall !OwnsLock until after we make that change.  I like the LOCK_HELD/NOT_HELD indirection, and will add it as part of bug 58904.

In the meantime, in case anyone wants to tackle the memory fence problem for !OwnsLock, this is the right tool for the job: http://checkfence.sourceforge.net/.

Comment 20

[Wan-Teh Chang]

I now maintain NSPR in my spare time, often on weekends.  (Last
weekend was an exception as I was working on my tax return.)  I'm
having a little trouble keeping up with the comments in this bug.

To ensure that your work gets prompt review, could you nominate
a Mozilla developer familiar with system programming to be an
NSPR module owner or peer?  I don't want to be the bottleneck
of your progress, and I welcome new blood who wants to tackle
challenging multithreading problems.

roc filed bug 476540 about being able to allocate PRLock on
the stack.  It's certainly doable.  I'll comment in that bug.

Comment 21

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Wan-Teh: no problem at all.  It appears that Ted is already an NSPR peer.  I should have asked him first, my fault.

Comment 22

[(not currently active) Ted Mielczarek]

Despite being an NSPR peer, I'm not comfortable reviewing code at this level. roc: would you like to take a look at this patch?

Comment 23

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 367653 [details] [diff] [review]
Patch v2, with updated API

OK

Comment 24

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Comment on attachment 367653 [details] [diff] [review]
Patch v2, with updated API

Ted: no problem, thanks.

Comment 25

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 367653 [details] [diff] [review]
Patch v2, with updated API

I have reviewed this patch, and I would give it an r+, but I believe 
that these new PR_Assert calls should be macro invocations, and the 
macros should be defined so that in non-DEBUG builds, they expand to 
nothing.  This way, in non-debug builds, we do not have a bunch of 
code calling functions that do nothing.  

I have no problem with the functions that exist in this patch, but
code outside of NSPR should invoke them all through a macro. 
e.g. something like

#if defined(DEBUG)
#define PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mon) \
        PR_AssertCurrentThreadInMonitor(mon)
#else
#define PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mon) 
#endif

Comment 26

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Fine with me.

One issue: I don't know of a way to keep PR_AssertCurrentThreadInMonitor() out of NSPR's API.  The only thing I know how to do is something like assert.h:

  /* You'll be tossed into a special ring of hell if you use this directly. */
  NSPR_API(void) __pr_assertcurrentthreadinmonitor(PR_Monitor* mon);

  #ifdef DEBUG
  #  define PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mon) \
         __pr_assertcurrentthreadinmonitor(PR_Monitor* mon)
  #else
  #  define PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mon)
  #endif

Is this OK?

Comment 27

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: v3

Comment 28

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 367944 [details] [diff] [review]
v3

Perhaps this will seem terribly nit-picky, but NSPR's convention 
for labeling private symbols uses a single leading underscore.
Compare the outputs of these MXR searches:

http://mxr.mozilla.org/nspr/search?string=_pr_&case=on&find=%5C.h%24&filter=%5Cb_pr_&tree=nspr

http://mxr.mozilla.org/nspr/search?string=__pr_&case=on&find=%5C.h%24&filter=%5Cb__pr_&tree=nspr

So, please make one more revision of this patch, which uses a single
leading underscore, and I think it will get r+.

Comment 29

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: v4

Removed leading underscore and switched to camel case, to conform to other nspr code.

Comment 30

[Wan-Teh Chang]

Comment on attachment 368080 [details] [diff] [review]
v4

Chris,

You need to add the new functions to nspr.def:
http://mxr.mozilla.org/nspr/source/nsprpub/pr/src/nspr.def

Right now nspr.def is only used on Solaris.  It controls
functions exported from libnspr4.so.  You can imitate the
existing code and add a NSPR_4.8 section for the new functions
at the end.

Since these functions are exported, they should have the
PR_ prefix like the PR_Assert function used by the PR_ASSERT
macro and the PR_LogPrint function used by the PR_LOG macro.

The ifdef around PR_ASSERT_CURRENT_THREAD_xxx should match
the ifdef around PR_ASSERT:
http://mxr.mozilla.org/nspr/ident?i=PR_ASSERT

So you need to test defined(DEBUG) || defined(FORCE_PR_ASSERT).

I like the shorter NS_ASSERT_LOCK_HELD macro name that roc
suggested in comment 17.  The current thread is implied, so
how about renaming the function and macro PR_AssertLockHeld
and PR_ASSERT_LOCK_HELD?  (Or PR_AssertOwnsLock and
PR_ASSERT_OWNS_LOCK)

Comment 31

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Thanks for the review.  I'm not sure whether I should be requesting them from you --- does this indicate that I should be?

> You need to add the new functions to nspr.def:
> http://mxr.mozilla.org/nspr/source/nsprpub/pr/src/nspr.def
> 
> Right now nspr.def is only used on Solaris.  It controls
> functions exported from libnspr4.so.  You can imitate the
> existing code and add a NSPR_4.8 section for the new functions
> at the end.
> 

I saw this, but it didn't seem used anymore so I ignored it.  Will do.

> I like the shorter NS_ASSERT_LOCK_HELD macro name that roc
> suggested in comment 17.  The current thread is implied, so
> how about renaming the function and macro PR_AssertLockHeld
> and PR_ASSERT_LOCK_HELD?  (Or PR_AssertOwnsLock and
> PR_ASSERT_OWNS_LOCK)
> 

I actually disagree with this --- to my ears, "AssertLockHeld" is too different from "AssertCurrentThreadOwnsLock" for the "CurrentThread" part to be implied.  There might even be esoteric uses for a separate "AssertLockHeld" function (concurrent GC?), though I see no reason to provide it at the moment.  I'd rather be precise about this macro name at the expense of its brevity.

Is the name of this macro important enough to get a patch rejected?  If not, I'll post v5 without waiting for this discussion to be resolved.

Comment 32

[Wan-Teh Chang]

Chris, please consider me as a "drive-by reviewer".
Make as many suggested changes as you agree with.
Don't worry about nits such as shorter names.  Thanks!

Comment 33

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: v5

Updated based on Wan-Teh's and Nelson's comments, except for the shorter macro name.

Comment 34

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 368095 [details] [diff] [review]
v5

Committed on CVS trunk.

include/prlock.h;       new revision: 3.9; previous revision: 3.8
include/prmon.h;        new revision: 3.7; previous revision: 3.6
src/nspr.def;           new revision: 1.15; previous revision: 1.14
src/bthreads/btlocks.c; new revision: 3.8; previous revision: 3.7
src/bthreads/btmon.c;   new revision: 3.7; previous revision: 3.6
src/pthreads/ptsynch.c; new revision: 3.32; previous revision: 3.31
src/threads/prmon.c;    new revision: 3.7; previous revision: 3.6
src/threads/combined/prulock.c; new revision: 3.13; previous revision: 3.12
tests/lock.c;           new revision: 3.9; previous revision: 3.8

Comment 35

[Nelson Bolyard (seldom reads bugmail)]

I'm resolving this, but you can reopen it if there's more to be done.