From owner-freebsd-arch@FreeBSD.ORG Fri Nov 23 00:55:53 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 3ACBA16A419 for ; Fri, 23 Nov 2007 00:55:53 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: from nf-out-0910.google.com (nf-out-0910.google.com [64.233.182.186]) by mx1.freebsd.org (Postfix) with ESMTP id CD5AE13C459 for ; Fri, 23 Nov 2007 00:55:52 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: by nf-out-0910.google.com with SMTP id b2so2682852nfb for ; Thu, 22 Nov 2007 16:55:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=IDd3MX0XNR8zqvq71/8rwbjkmj2xPsqsJ8utixyw87U=; b=VieLECbMTsASdmotB5733QdrbWvyFYOM0brZcLJSPFdTGOfVda/n8vZxxEC4C7UwFYFrZOKvnjRf0FgqqWevcdnjRoYjqToQVn821VU+sN7E5LYY4kv5y8rl559XQmBLCBzOdMlZm3KFU0kpQOXYw/WlVhJcW/8eQIZVy+fh+Qk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=uTr+04QS/ZbYugNFH8gM+E5c9CsCzf15uNmplcIyTpLH4HIkhW1JNE/8gdU/CSHTx2Zkjf89e4qDARhIpfjiroNTHO06668hvTn5FO90UdWa05gh7iW0QRN35xLE6/rKZuO9ZQSM3/zMQMenvwjyFq+4zRqSa0gHJeWPQRrOHb4= Received: by 10.86.91.12 with SMTP id o12mr8969826fgb.1195779346322; Thu, 22 Nov 2007 16:55:46 -0800 (PST) Received: by 10.86.28.19 with HTTP; Thu, 22 Nov 2007 16:55:46 -0800 (PST) Message-ID: <3bbf2fe10711221655n33d4d0c7mbeece529a3d08642@mail.gmail.com> Date: Fri, 23 Nov 2007 01:55:46 +0100 From: "Attilio Rao" Sender: asmrookie@gmail.com To: dima <_pppp@mail.ru> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20071121222319.GX44563@elvis.mu.org> X-Google-Sender-Auth: fb23b2f05dabc45f Cc: arch@freebsd.org, Alfred Perlstein Subject: Re: rwlocks, correctness over speed. X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 Nov 2007 00:55:53 -0000 2007/11/22, dima <_pppp@mail.ru>: > > 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. The real problem with this is that currently we have a fast path which is only an atomic add. What you propose will make the fast path too slow (not mentioning the limitation), and this is somethign we should avoid if possible. Attilio -- Peace can only be achieved by understanding - A. Einstein