From: David Howells <dhowells@redhat.com>
In-Reply-To: <20060108000021.588c6f5f.akpm@osdl.org> 
References: <20060108000021.588c6f5f.akpm@osdl.org>  <20060104144151.GA27646@elte.hu> <43BC5E15.207@austin.ibm.com> <20060105143502.GA16816@elte.hu> <43BD4C66.60001@austin.ibm.com> <20060105222106.GA26474@elte.hu> <43BDA672.4090704@austin.ibm.com> <20060106002919.GA29190@pb15.lixom.net> <43BFFF1D.7030007@austin.ibm.com> <20060107143722.25afd85d.akpm@osdl.org> <20060108074356.GM26499@krispykreme> 
To: Andrew Morton <akpm@osdl.org>
Cc: Anton Blanchard <anton@samba.org>, jes@trained-monkey.org,
       rmk+lkml@arm.linux.org.uk, ak@suse.de, linux-kernel@vger.kernel.org,
       hch@infradead.org, torvalds@osdl.org, viro@ftp.linux.org.uk,
       linuxppc64-dev@ozlabs.org, mingo@elte.hu, nico@cam.org, oleg@tv-sign.ru,
       alan@lxorguk.ukuu.org.uk, arjan@infradead.org
Subject: Re: PowerPC fastpaths for mutex subsystem 
Date: Mon, 09 Jan 2006 11:13:52 +0000
Message-ID: <923.1136805232@warthog.cambridge.redhat.com>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1675
Lines: 35

Andrew Morton <akpm@osdl.org> wrote:

> > Wasnt most of the x86 mutex gain a result of going from fair to unfair
> > operation? The current ppc64 semaphores are unfair.
> > 
> 
> What's "unfair"?  Mutexes are FIFO, as are x86 semaphores.

No, strictly Ingo's mutexes are neither completely fair nor completely FIFO.
It's possible for a process to jump the queue because unlock() always sets the
counter back to 1 before waking up the process at the front of the queue. This
means that the lock() fastpath in another process may steal the mutex out of
sequence before the wakee has a chance to grab it.

I'm not 100% convinced that x86 counting semaphores are completely fair or
completely FIFO. It's possible that they are because up() never arbitrarily
sets the count back to >0.

R/W semaphores are completely fair, but only as completely FIFO as the unfair
spinlocks permit. This is because it's much easier to guarantee their behaviour
(writer-starvation is a real problem with unfair rwsems). I have a simple
implementation of totally fair spinlocks for x86 which would also work on
anything that can emulate XADD, but I don't think it's worth the trouble.

However, for Ingo's mutexes, I suspect this queue-jumping feature is
sufficiently low probability that we can ignore it. It is theoretically
possible to induce livelock, but in reality I think it extremely unlikely to
happen for any significant length of time.

David
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/