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>