linux-kernel - Re: [PATCH RFC 1/2] qrwlock: A queue read/write lock implementation

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]

Date:	Fri, 19 Jul 2013 11:43:27 -0400
From:	Waiman Long <waiman.long@...com>
To:	George Spelvin <linux@...izon.com>
CC:	JBeulich@...ell.com, linux-arch@...r.kernel.org,
	linux-kernel@...r.kernel.org, mingo@...nel.org, tglx@...utronix.de
Subject: Re: [PATCH RFC 1/2] qrwlock: A queue read/write lock implementation

On 07/18/2013 02:46 PM, George Spelvin wrote:
>> Thank for the revision, I will make such a change in the next version of
>> my patch.
> I'm relying on you to correct any technical errors in my description.
> I just meant "something more like this", not impose that exact wording.
>
>> As I said in my response to Ingo, that change will make the lock more
>> unfair to the writers. However, I can run some tests to find out the
>> performance impact of such a way on the benchmarks that I used.
> You can do a lot with the basic structure if you're willing to
> go to XADD in the _lock_failed handlers.
>
> Adding writer priority is possible, but at least some call sites have
> to be reader-priority because they're recursive or are in interrupts,
> and readers don't disable interrupts.
>
> The basic solution is for writers to first detect if they're the *first*
> writer.  If a write lock fails, look and see if it's>  -RW_LOCK_BIAS.
>
> If not, drop it and spin reading until it's>= 0, then try again.
> (Possibly with XADD this time to combine the acquire and add.)
>
> But when we *are* the first writer, subtract an additional -RW_LOCK_BIAS/2.
> This tells pending readers "writer wating, back off!".
>
>
> What readers do when they see that bit set in rwlock->lock-1 depends on
> whether they're fair or unfair:
>
> - Fair readers re-increment the lock and spin waiting for it to become>
>    -RW_LOCK_BIAS/2, at which point they try to reacquire.
> - Unfair readers say "ah, that means I can go ahead, thank you!".
>
>
> A waiting writer waits for the lock to equal -RW_LOCK_BIAS/2, meaning
> all readers have left.  Then it adds -RW_LOCK_BIAS/2, meaning "write
> lock taken" and goes ahead.
>
> At this point, there is a thundering horde while the held-off readers
> get back in line.  But hopefully it overlaps with the writer's lock tenure.
>
> When the writer drops its lock, the waiting readers go ahead, and the
> spinning writers advance in a thundering horde to contend for first place.
> (Again, the latency for this is hopefully covered by the readers'
> lock tenure.)

Thank for the suggestion. What you have proposed will be somewhat 
similar to what my new code is doing with readers/writers spinning on 
the cacheline without the waiting queue. I need to run some tests to see 
if it can really help.

> I count 531 calls to read_lock in the kernel (10 of them are in
> lib/locking-selftest.c, called RL).  I don't have any idea how difficult
> it would be to divide them into read_lock_fair and read_lock_unfair.

What I have in mind is to have 2 separate rwlock initializers - one for 
fair and one for reader-bias behavior. So the lock owners can decide 
what behavior do they want with a one line change.

Regards,
Longman
--
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/