Mutexes are recursive on windows, but not on unix

[alexcrichton]

This behavioral difference should factor into the stabilization of the methods on sync::Mutex and how we'd like to word the documentation.

For now though, this is a tracking issue as this difference in behavior was not originally intended.

cc @aturon

[pythonesque]

How can this make the semantics of the Mutex API differ substantially? You have a &mut borrow of the value protected by the Mutex, so even if the Mutex is reentrant I don't see how you could expose that through the API. Or I guess the issue is that you could get aliased &muts by clone()ing a Arc<Mutex<T>> on Windows and unlocking both in the same thread?

[alexcrichton]

Unfortunately the &mut borrow is earned from the MutexGuard structure, not the Mutex, which allows you lock it twice. For example, if this code completed, it could exhibit memory unsafety (two &mutreferences):

use std::sync::Mutex;
use std::mem;

fn main() {
    let m = Mutex::new(4u);
    let mut g1 = m.lock();
    let mut g2 = m.lock();

    let p1 = &mut *g1;
    let p2 = &mut *g2;
    mem::swap(p1, p2);
}

On unix that code deadlocks, but on windows it executes just fine.

[pythonesque]

Wait, lock() doesn't take a mutable reference to the Mutex? Weird, isn't that guaranteed to deadlock on Unix?

Anyway, since you could have aliased Mutexs in the same thread even if that were changed, I think Windows mutexes need an additional check for safety (Windows fast mutexes look like they have too many limitations to be a drop in replacement).

[sfackler]

lock can't take &mut self. That'd be a guarantee that the caller has exclusive access to the mutex, which defeats the entire point.

[pythonesque]

Oh right, it has to be shared in the first place. Heh.

[retep998]

What are the limitations of fast mutexes that prevent us from using them?

[pythonesque]

@sivadeilra and I discussed this and he recommends just adding a flag and checking it manually on Windows.

[alexcrichton]

@retep998 I don't think there are any limitations (we're currently using them), this is just a surprising consequence of using them.

@pythonesque yeah I suspect that sys::mutex::Mutex will have specific code on windows for a separate UnsafeCell<uint> which is inspected once the lock is acquired (using GetCurrentThreadId) and if the same thread acquires the mutex twice it just panics.

[retep998]

According to the current code we use Critical Sections for Mutexes on Windows.
https://github.com/rust-lang/rust/blob/master/src/libstd/sys/windows/mutex.rs
Fast/Guarded mutexes are a separate thing entirely and will deadlock if you attempt to lock them twice on the same thread.
http://msdn.microsoft.com/en-us/library/windows/hardware/ff545716%28v=vs.85%29.aspx
The MSVC C++ implementation for std::mutex checks if the locked thread is the current thread before even trying to lock it and throws an exception if it is.

[alexcrichton]

Whoa! I had no idea that "fast mutexes" was a thing. I thought there were only inter-process mutexes and critical sections.

It looks like the "fast mutexes" or "guarded mutexes" are only for drivers, and maybe not for userland code? Or at least I couldn't figure out how to use them. Do you have pointers to the source for MSVC's implementation, or how to use them?

[pythonesque]

Yeah, the bits that made it seem like they were only for drivers was why I said we probably couldn't use them. Apparently critical sections are the fastest userland ones you should use. On a related note, it might be worth clarifying in the Mutex documentation that they aren't intended to be used between processes (maybe it's already there, but I don't recall seeing it).

[retep998]

According to some debugging, on Windows 8.1 x64, MSVC uses SRWLock for std::mutex instead of CriticalSection. I'm going to do some benchmarking to determine their performance difference. As an added bonus, you can sleep a ConditionVariable on an SRWLock in Windows which Rust could provide as a platform specific extension trait.

[retep998]

And this is pretty conclusive. I did a test with two threads constantly locking and unlocking the same mutex. When I used CriticalSection it took about 260ns per lock+unlock. When I used SRWLock it took about 60ns per lock+unlock.
http://puu.sh/dSHEP/c304111d25.txt

[Gankra]

On my beefy Win7 x64 gaming rig, I get a rock-solid 26ns for RW, and a fluctuating 70-80ns for Critical.

Faster and more reliable.

[pythonesque]

Oh wow, and they can't be acquired recursively either, so we wouldn't even need to do anything different from the other platforms. Good find!

[retep998]

@pythonesque - Yep just tried acquiring an SRWLock twice on the same thread and it has deadlocked.

[pythonesque]

Hm, they look like they have other problems though:

There is no guarantee about the order in which threads that request ownership will be granted ownership; SRW locks are neither fair nor FIFO.

Defaulting to an unfair lock doesn't seem like a good idea (unless your only goal is to win benchmarks). But if MSVC++ is doing it...

[retep998]

We already use SRWLock for RWLock in Rust anyway.
https://github.com/rust-lang/rust/blob/master/src/libstd/sys/windows/rwlock.rs

[huonw]

@thestinger, what's the simple solution you have in mind? (Storing an extra flag internally?)

[retep998]

Some quick tests show that CriticalSection is indeed fairer than SRWLock.
CriticalSection:

34171   32087   34549   25067   0       0       0       0       0       0
40418   27530   33882   30486   0       0       0       0       0       0
13877   31742   28593   39065   24009   0       0       0       0       0
30863   26029   29152   26382   25551   0       0       0       0       0
24567   25217   23325   25580   23492   16435   0       0       0       0
19113   21615   23606   18665   28300   27893   0       0       0       0
24753   22568   22606   22561   16146   25420   9746    0       0       0
18139   19727   17637   19984   25940   21281   12959   0       0       0
14938   12694   24798   19116   14594   14405   18209   14920   0       0
16073   23406   14504   23900   15294   13880   17375   13068   0       0
15506   16711   20121   15031   18179   16284   20653   15558   0       0
14872   13808   15967   18741   22169   12231   14982   12377   14076   0
25134   15375   12654   19882   12849   13015   16348   13682   13203   0
13403   13560   14045   15284   18013   16664   16047   19306   13425   0
5448    12843   13179   14318   15326   10203   22727   19956   12746   12418
15951   14074   11454   14648   17843   12552   14109   13494   12543   14056
14332   12718   13949   15113   16568   13259   15926   12378   13147   16045
9892    13519   14725   12129   13071   12111   20561   13575   12737   20391
8007    15212   19330   20983   10905   15684   7332    16555   14948   5042
18892   16922   11213   3885    15867   17002   19348   830     14227   20773
12939   15018   14149   13247   14292   13719   15672   13052   13053   17209
12889   12095   14208   13656   16628   13973   20397   14235   12888   12264
12849   13143   11709   16143   13620   13213   10585   19450   15283   17067
13880   14551   13568   13072   15539   13406   13064   11765   13458   16932
17342   13698   12702   9005    16266   12308   16181   12967   14432   16617
12551   12264   16975   17913   12432   17250   12927   14446   12467   14826
16225   22543   7888    12447   12939   8439    21196   8263    20920   13451
9912    16791   14213   14521   13237   13768   15750   16222   17729   12213
19113   4052    15270   7882    18009   16244   15204   13262   13159   14812
12327   13482   19490   14220   10289   15407   14474   13937   6609    20744
10804   12756   16694   18448   10703   13008   17756   14632   20425   6601
16523   15259   13954   6909    14970   15050   14145   14234   14847   16760
17305   21514   13950   14038   11952   12102   12307   16863   14319   6489
16156   13567   10291   10395   12499   13230   13304   13531   20497   16017
14035   13232   13811   13629   13807   15228   12951   14227   15944   13567
18192   14164   9099    13043   13349   13584   13496   15798   14292   13682
19019   11688   13174   13547   12121   20478   13253   14991   14269   11777
13737   20448   12508   14319   16930   16030   12510   12691   12427   13317
16577   10328   17387   10455   8043    12292   23642   18685   13417   13693
13393   9173    12092   17458   4567    13900   14887   12802   19120   19896

SRWLock:

14950   35673   41991   45097   0       0       0       0       0       0
28474   14421   40287   51305   0       0       0       0       0       0
44944   35323   27909   28776   3682    0       0       0       0       0
24781   28759   16158   34098   37222   0       0       0       0       0
31306   4890    35027   40664   30966   0       0       0       0       0
42811   1266    41404   22654   32755   0       0       0       0       0
8612    36366   42335   17029   37768   0       0       0       0       0
30595   18802   41117   35020   13337   0       0       0       0       0
22939   23370   29415   28797   31042   1       0       0       0       0
21774   27659   27204   29719   29502   0       0       0       0       0
30967   28935   17961   28625   29074   0       0       0       0       0
29716   25411   34458   31635   8904    13450   0       0       0       0
30110   25604   31467   28732   1959    26036   0       0       0       0
43507   25897   6716    21962   14358   31232   0       0       0       0
38802   34657   0       32641   0       36822   0       0       0       0
22617   47039   17330   0       15787   30837   0       0       0       0
12971   1485    52151   27650   25521   11465   6654    0       0       0
12710   24073   16559   25993   12784   13395   34478   0       0       0
26570   19995   13982   22040   11775   18991   27860   0       0       0
39311   18948   20103   18997   624     18489   10668   0       0       0
38075   38007   0       34453   0       29134   0       0       0       0
32527   32189   0       20248   12985   36962   9146    0       0       0
31850   31152   0       0       25346   27119   29781   0       0       0
22822   26172   21435   12707   16757   7626    20010   12587   0       0
15776   20214   21782   14139   23846   0       26534   23167   0       0
2214    26299   24346   3598    18175   27459   18998   15545   0       0
22838   0       13965   21927   23436   17270   25427   20284   0       0
27481   0       26135   21903   2864    0       37421   28664   0       0
15463   26165   15571   9990    10626   13514   12882   36975   0       0
26058   9737    21616   9448    15814   18939   17433   22365   0       0
17786   14293   19036   26162   14943   17528   19337   8553    0       0
26767   16439   12661   22420   15464   23073   13523   14101   0       0
0       28728   0       29137   34603   0       26967   25072   0       0
0       32623   0       30177   30979   0       26777   22745   0       0
0       12298   0       35904   38813   0       25011   29945   1       0
22021   12500   20687   13388   12768   13407   12275   21295   13410   0
15918   20539   4433    12478   13587   17859   20414   16040   24186   0
20186   16709   12291   18128   22137   19764   16334   5697    13276   0
25518   12516   0       25367   21217   12223   12754   21593   12731   0
21410   8873    19218   21208   26954   0       7345    23886   7939    0

Each row is 100ms apart. CPU has 4 cores/threads.

[thestinger]

@huonw: If you write a semaphore on top of it and hard-wire the count at 1, it will deadlock. There is probably a better way to do it. I think the older mutex type is already non-recursive but I think it's missing the syscall free fast path.

[retep998]

As of Windows Server 2003 SP1, CriticalSection doesn't use FIFO, which means it doesn't actually guarantee fairness.
If we're going to provide fair mutexes then we need to provide a solid fairness guarantee otherwise we might as well just use whatever is fastest.

[retep998]

After some clarification on IRC I have realized that fairness means low priority threads won't steal mutex lock time from higher priority threads.

[mzabaluev]

Apparently [Static]RwLock is non-recursive on Linux too, and easy to deadlock:

#![allow(unstable)]

use std::sync::{StaticRwLock, RW_LOCK_INIT};

static LOCK: StaticRwLock = RW_LOCK_INIT;

fn main() {
    let _read = LOCK.read();
    let _write = LOCK.write();
}