linux-kernel - Re: [RFC PATCH] Fair rwlock

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.0808161422290.3324@nehalem.linux-foundation.org>
Date:	Sat, 16 Aug 2008 14:33:01 -0700 (PDT)
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>
cc:	"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
Subject: Re: [RFC PATCH] Fair rwlock

On Sat, 16 Aug 2008, Mathieu Desnoyers wrote:
> 
> Tweakable contention behavior seems interesting, but I don't think it
> deals with the fact that on a mainline kernel, when an interrupt handler
> comes in and asks for a read lock, it has to get it on the spot.

Right. Which is exactly why I'd suggest using the extra space for saying 
"this CPU is busy-looping waiting for a write lock", and then the 
read-lock contention case can say

 - ok, there's a pending write lock holder on _my_ CPU, so I need to just 
   succeed right away despite the fact that there is contention.

In other words, there are a few cases:

 - you actually *got* the write lock

   interrupts obviously have to be disabled here, because any reader can 
   simply not get the lock.

 - you are waiting to get the write lock.

   Mark this CPU as "pending" in the rwlock (by making the extended thing 
   be a queue, or by simply only ever allowing a single pendign CPU), and 
   re-enable interrupts while you wait for it. An interrupt that comes in 
   and wants a read-lock sees that it's pending, so it should then ignore 
   the contention bit, and only wait for the write bit to go away.

See? This way you only need to actually disable interrupts while holding 
literally the lock, not while waiting for it. While still giving priority 
to writers (except for the _one_ CPU, where new readers will have to get 
through).

So this way you can be fair, and not allow readers to starve a writer. The 
only reader that is allowed past a waiting writer is the reader on that 
same CPU.

And notice how the fast-path needs no spinlock or anything else - it's 
still just a single locked instruction. In comparison, if I read your 
example code right, it is absolutely horrid and has an extra spinlock 
access for the fair_write_lock case.

			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/