Try upgrades and downgrades for POSIX rwlocks

[John Baldwin]

On Monday, January 24, 2011 8:18:39 pm Alfred Perlstein wrote:
> * John Baldwin <jhb at freebsd.org> [110124 13:05] wrote:
> > Does anyone know if there is a de facto or proposed standard for supporting 
> > upgrades and downgrades in POSIX rwlocks?  IBM seems to support something 
> > rather gross where a wrlock() will succeed if the only shared lock is held by 
> > the current thread.  But then the thread holds both a read and write lock, and 
> > it has to call unlock twice, the first to drop the write lock, the second to 
> > drop the read lock.  If we were to add support for upgrades and downgrades I 
> > would prefer something more along the lines of our in-kernel APIs where there 
> > are try_upgrade() and downgrade() operations that convert a given lock between 
> > states.
> 
> There may a be a tricky problem here.
> 
> In order to avoid writer starvation (in the kernel) we give writers
> preference over readers so that many concurrent readers can't keep
> the lock in a shared-only state forever.  (Or at least that's how I
> left it when I touched it last. :D )
> 
> There is a problem here.
> 
> To conserve that behavior we need to look at the situation of an upgrade:
> 1) we have to put the upgrader to the front of the writer queue,
> this can starve other threads looking for only a writer lock by
> giving an unfair advantage to those that take a share lock first.
> 
> 2) we don't even look at this issue and we wind up with some deadlock.
> 
> At a glance, I think we have to have some kind of "try_upgrade"
> that doesn't give preference to the thread already holding the lock.

Err, I generally think try_upgrades (which by nature give preference to the
current thread since they only succeed if the only shared lock held is that
of the current thread) are the only "sane" upgrade operation.  If you have
any sort of blocking upgrade then you have to handle the problem of two
concurrent upgrades in which case at least one upgrade would only be able
to succeed after another thread has obtained a write lock and modified the
state, and I suspect most programmers don't realize that after a blocking
lock upgrade they cannot trust any of the state that they checked under
the read lock and instead need to recheck all of that.  Having a try_upgrade
forces them to handle this since it can fail and in the failure case it is
more obvious that you have to reexamine state if you fall back to doing a
read lock followed by a blocking write lock.

> We should probably strongly encourage try_upgrades to have some sort
> of fault injection so that a potentially infrequently "missed upgrade"
> path can be exercised easily.  Perhaps with a kernel config option or
> that fault injection stuff?
> 
> just some ideas.
> 
> Maybe there's someone that can explain how IBM does the rwlocks.

IBM's method is documented online:

http://publib.boulder.ibm.com/infocenter/iseries/v5r4/index.jsp?topic=%2Fapis%2Fconcep26.htm

However, I think these semantics are horrible.  Others may disagree.

> Why do we want to have our own method.  And if our methods are different,
> does it break the semantics that may become standard across the board?  Does it
> help us to diverge?  What about OS X and Solaris?

I am mostly asking to see if anyone else knows of alternate semantics to that
of IBM's.  I would rather not do the IBM semantics if possible because as I
stated above, I think they are non-obvious and non-intuitive.  I was not able
to find any references online to any other pthread implementations that
support upgrades or downgrades on rwlocks however.

-- 
John Baldwin