Try upgrades and downgrades for POSIX rwlocks

[Alfred Perlstein]

* John Baldwin <jhb at freebsd.org> [110125 06:21] wrote:
> 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.

Agreed 100%.

> 
> > 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.

They do raise an eyebrow... the way that unlocks are handled are really
nasty.

> 
> > 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.

No idea.  

-- 
- Alfred Perlstein
.- VMOA #5191, 03 vmax, 92 gs500, 85 ch250, 07 zx10
.- FreeBSD committer