Fixing the Krieger read-write lock

Using Hardware Transactional Memory to Correct and Simplify a Readers-Writer Lock Algorithm will appear in PPoPP 2013.

Comments:

We ran into the KSUH bug back in 2005 when implementing TBB's tbb::queuing_rw_mutex (which is based on KSUH). The TBB interface uses stack-allocated nodes as part of a RAII scheme. After intermittent failures, we tracked down the issue to freeing of nodes before their last access. Now paranoid, we looked around for a checker and discovered the Spin model checker was what we needed. Spin confirmed the problem and we became big fans of Spin. Our fix in the tbb::queueing_rw_mutex seems to be different than the fix described in the PPoPP 2013 paper.

Posted by Arch Robison on February 06, 2013 at 03:58 PM EST #

Hi Arch, do you have a concise description of the work-around you used in TBB? Regards, -Dave

Posted by guest on February 06, 2013 at 11:30 PM EST #

We fixed the write issue by changing "spin" to a three-state variable. The extra state is like "spin=0", but warns of a pending write to "pred". We write the special spin value, do the pending write, and then write "spin=0". After a reader or writer performs an unlock, it waits until spin is not in the extra state. I like your fix better since it adds code only on the path for unlocking readers, and your fix is non-blocking.

Here are more notes if someone wants to look over the TBB sources, which are downloadable from http://threadingbuildingblocks.org/download . The relevant file is src/tbb/queuing_rw_mutex.cpp. In addition to fixing the late-write bug, we also made improvements to fix a situation where readers block readers, fit the mutex in a single word, and added upgrade/downgrade. We flipped the polarity of "spin" (it's called "going" in our sources) for naming consistency with our queuing_mutex. The RAII-style "scoped_lock" object acts as the node.

So it's a little tricky to match up with the original KSUH. Nonetheless the KSUH algorithm is there. The sequence that warns about late writes looks like:

__TBB_store_relaxed(n->my_going, 2); // protect next queue node from being destroyed too early
if( n->my_state==STATE_UPGRADE_WAITING ) {
...
} else {
... some assertions...
__TBB_store_relaxed(n->my_prev, (scoped_lock*)0);
__TBB_store_with_release(n->my_going,1);
}

and the waiting is done by:

spin_wait_while_eq( my_going, 2 );

Posted by Arch Robison on February 07, 2013 at 04:16 PM EST #

Hi Arch, thanks for the description of your fix -- that looks like a good approach. As an aside, I found the bug when some sanity and lightweight integrity checks would fail when benchmarking RW lock algorithms for my other PPoPP 2013 paper. Initially, it'd fail about once every 2-3 days on very large system, but with judicious insertion of random delays I could get it down to under 1 second.

Regards, -Dave

Posted by guest on February 11, 2013 at 12:50 PM EST #

Hi Dave, I see you work about JVM related subjects, can you please inform how to have access to an oracle hotspot 1.6 VM that prints java frames in hs_err files ?

The detailed description is in the following forum post. Sorry to bother here, but I asked there and stackoverflow and nobody stepped in.

https://forums.oracle.com/forums/thread.jspa?threadID=2503763&tstart=0

Thanks

Claudio

Posted by Claudio Miranda on March 05, 2013 at 02:33 PM EST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Dave

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today