linux-kernel - Re: queued spinlock code and results

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20070711020638.GB27475@wotan.suse.de>
Date:	Wed, 11 Jul 2007 04:06:38 +0200
From:	Nick Piggin <npiggin@...e.de>
To:	Christoph Lameter <clameter@....com>
Cc:	Andi Kleen <andi@...stfloor.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: queued spinlock code and results

On Tue, Jul 10, 2007 at 01:52:47PM -0700, Christoph Lameter wrote:
> On Sun, 8 Jul 2007, Andi Kleen wrote:
> 
> > I would say the main drawback of switchable and queued locks 
> > would be also that they require a larger spinlock_t thus increasing
> > cache usage
> 
> Right. Zoran Radovic has shown that queued locks are inferior 
> to other approaches. The best approach that he found in his research were 
> the HBO locks that are somewhat more intelligent form of spinlocks.
> 
> http://user.it.uu.se/~zoranr/
> http://www.it.uu.se/research/group/uart/projects/nucasynch/
> 
> Paper on the issue with measurements:
> http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf


OK, maybe I do have my terminology wrong -- we'll call them FIFO locks
or ticket locks. The point is not to improve performance of the contended
case (although they may have slightly better contended case characteristicds),
but to improve worst case latency and improve fairness.

BTW. some advanced congestion algorithms like HBO may find these ticket
locks useful because you can see immediately how many CPUs are contending
the lock, and spinners know how many CPUs are in front of them. That info
could be fed into the spin backoff scheme.

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