linux-kernel - Re: [RFC PATCH] Writer-biased low-latency rwlock v8

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: <alpine.LFD.1.10.0808211402370.3487@nehalem.linux-foundation.org>
Date:	Thu, 21 Aug 2008 14:15:08 -0700 (PDT)
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>
cc:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	Jeremy Fitzhardinge <jeremy@...p.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...e.hu>, Joe Perches <joe@...ches.com>,
	linux-kernel@...r.kernel.org, Steven Rostedt <rostedt@...dmis.org>
Subject: Re: [RFC PATCH] Writer-biased low-latency rwlock v8

On Thu, 21 Aug 2008, Linus Torvalds wrote:
> 
> That leaves 30 bits for readers. If you still think you need to "limit the 
> number of readers", then you aren't getting it.

Side note: the actual main rwlock thing is designed for a 64-bit word and 
the waiters separately as two 32-bit words, so it doesn't really do what I 
describe, but that's actually because the whole sleeping thing is _harder_ 
than a spinning thing, and has races with wakeups etc.

A spinning thing, in contrast, is pretty trivial.

So here's what I think your code should be like:

 rdlock:
	movl $4,%eax
	lock ; xaddl %eax,(%rdi)
	testl $3,%eax
	jne __rdlock_slowpath
	ret

 rwlock:
	xorl %eax,%eax
	movl $1,%edx
	lock ; cmpxchgl %edx,(%rdi)
	jne __rwlock_slowpath
	ret

 rdunlock:
	lock ; subl $4,(%rdi)
	ret

 rwunlock:
	lock ; andl $~1,(%rdi)
	ret

and I'm pretty damn sure that that should be totally sufficient for a 
spinning rwlock. The non-spinning one is more complex just because the 
unlock paths need to guarantee that something gets woken up, that just 
isn't an issue when you do spinlocks.

Now, in the slow-path:
 - on the rwlock slowpath side, set bit#1 to make sure that readers get 
   caught in the slowpath
 - then do a *separate* count of how many pending readers and writers 
   (ie the ones that got caught into the slowpath) you have (one word 
   each is probably fine), and then the slowpaths can just do the right 
   thing depending on whether there are pending readers/writers.

See? The main lock needs not worry about number of writers AT ALL, because 
it's totally irrelevant. So don't worry about running out of bits. You 
won't. Just put those counts somewhere else! The only thing that matters 
for the main lock word is whether there are active readers (30 bits), and 
whether there is an active writer (there can only ever be one: 1 bit), and 
whether new readers should be trapped (1 bit).

If you worry about overflows, you're doing something wrong.

			Linus
--
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/