From owner-freebsd-arch@FreeBSD.ORG Thu Nov 22 19:12:42 2007 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 13BF516A41B for ; Thu, 22 Nov 2007 19:12:42 +0000 (UTC) (envelope-from _pppp@mail.ru) Received: from mx28.mail.ru (mx28.mail.ru [194.67.23.67]) by mx1.freebsd.org (Postfix) with ESMTP id 9BA0F13C461 for ; Thu, 22 Nov 2007 19:12:41 +0000 (UTC) (envelope-from _pppp@mail.ru) Received: from f106.mail.ru (f106.mail.ru [194.67.57.205]) by mx28.mail.ru (mPOP.Fallback_MX) with ESMTP id CADBE757C33 for ; Thu, 22 Nov 2007 19:44:48 +0300 (MSK) Received: from mail by f106.mail.ru with local id 1IvFAP-000BFB-00; Thu, 22 Nov 2007 19:44:41 +0300 Received: from [89.208.20.114] by koi.mail.ru with HTTP; Thu, 22 Nov 2007 19:44:41 +0300 From: dima <_pppp@mail.ru> To: Alfred Perlstein Mime-Version: 1.0 X-Mailer: mPOP Web-Mail 2.19 X-Originating-IP: [89.208.20.114] Date: Thu, 22 Nov 2007 19:44:41 +0300 In-Reply-To: <20071121222319.GX44563@elvis.mu.org> References: <20071121222319.GX44563@elvis.mu.org> Content-Type: text/plain; charset=koi8-r Content-Transfer-Encoding: 8bit Message-Id: Cc: arch@freebsd.org Subject: Re: rwlocks, correctness over speed. X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: dima <_pppp@mail.ru> List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Nov 2007 19:12:42 -0000 > 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: * 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. 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" >