Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 22 Nov 2007 19:44:41 +0300
From:      dima <_pppp@mail.ru>
To:        Alfred Perlstein <alfred@freebsd.org>
Cc:        arch@freebsd.org
Subject:   Re: rwlocks, correctness over speed.
Message-ID:  <E1IvFAP-000BFB-00._pppp-mail-ru@f106.mail.ru>
In-Reply-To: <20071121222319.GX44563@elvis.mu.org>
References:  <20071121222319.GX44563@elvis.mu.org>

next in thread | previous in thread | raw e-mail | index | archive | help
> 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.

> 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@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"
> 



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?E1IvFAP-000BFB-00._pppp-mail-ru>