rwlocks, correctness over speed.

[Alfred Perlstein]

* dima <_pppp at mail.ru> [071122 08:44] wrote:
> > In summary, I am proposing (temporarily) making read-recursion
> > on rwlocks not supported in order to avoid livelock due to writer
> > starvation.
> 
> It's not the matter of recursion, but the implementation itself.
> Comments from the code:
> <quote>
>          * Note that we don't make any attempt to try to block read
>          * locks once a writer has blocked on the lock.  The reason is
>          * that we currently allow for read locks to recurse and we
>          * don't keep track of all the holders of read locks.  Thus, if
>          * we were to block readers once a writer blocked and a reader
>          * tried to recurse on their reader lock after a writer had
>          * blocked we would end up in a deadlock since the reader would
>          * be blocked on the writer, and the writer would be blocked
>          * waiting for the reader to release its original read lock.
> </quote>
> Such a design would provide writer starvation regardless the presence of recursion. If a writer is waiting for the lock, no more readers should be allowed. It's a simple rule to avoid writer starvation in rw-locks. Recursion does need an accurate accounting of all the current readers.
> I've posted a reference implementation of rw-locks to this mailing list about a year ago. My proposal was to use an array to account the current readers (the array can be handled without any additional locking). It limits the maximum read contention, though.

Dima, if you put the list inside the thread (as mentioned in my email)
then it scales to any number of readers.  Although the number of
simultanious discrete readlocks is limited by a constant.

>From talking to Attilio and John, they do not want that as it is "slow".


-Alfred

> 
> > More details:
> > 
> > We currently have a problem with our implementation of rwlocks.
> > 
> > I think this is a key issue for 7.x as what we decide to support
> > will have rammifications for many years to come.
> > 
> > We do not support writer priority or "fair share" usage of rwlocks
> > between readers and writers.
> > 
> > We have several choices to rectify this.
> > 
> > 1. Disallow recursion on rwlocks (witness can be used to enforce this),
> > this simplifies rwlocks such that we can avoid deadlock when a single
> > reader is trying to recurse while a writer is pending.
> > 
> > 2. Track ownership of rwlocks, this can be implemented with a "rwlock
> > stack" in the per-thread control block (struct thread).  Using this
> > ownership information we can determine if someone is recursing and
> > allow them to continue recursing despite a pending write request.
> > 
> > I think the most simple solution currently is to drop support for
> > recursive reads on rwlocks until we have the facility in place
> > to properly support starvation avoidance.
> > 
> > Why is this important?
> > 
> > Simply put, developers that quickly "fix" some portion of code,
> > whether that be a driver or part of the kernel proper who use read
> > recursion will open the system to writer starvation and hence the
> > system will destabilize, particulary for high load situations.
> > 
> > I would like to get this in before 7.0-RELEASE becasue otherwise
> > we're forced to implement something like the above mentioned solution
> > #2, which will degrade performance for most use cases of rwlocks.
> > 
> > Comments?
> > 
> > -- 
> > - Alfred Perlstein
> > _______________________________________________
> > freebsd-arch at freebsd.org mailing list
> > http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> > To unsubscribe, send any mail to "freebsd-arch-unsubscribe at freebsd.org"
> > 

-- 
- Alfred Perlstein