linux-kernel - Re: [rfc] "fair" rw spinlocks

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: <20091201190140.GA5421@Krystal>
Date:	Tue, 1 Dec 2009 14:01:40 -0500
From:	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>
To:	Nick Piggin <npiggin@...e.de>
Cc:	Arnd Bergmann <arnd@...db.de>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [rfc] "fair" rw spinlocks

Nick Piggin <npiggin@...e.de> wrote:
> Anyway, I don't have a patch yet. I'm sure it can be done
> without extra atomics in fastpaths. Comments?

Hi Nick,

I actually have an implementation doing what you are looking for. I did
it last year, but after that had to focus on finishing my Ph.D., so it
went a bit out of focus. You can see this old thread:

http://lwn.net/Articles/297493/
"Priority Sifting Reader-Writer Lock v13"

It's not fair per-se: it's biased to favor writers over readers.
However, writers vs writers are fair.

Disclaimer: there may be some amount of dust accumulated on these
patches over the past year. Also, I did not do any formal proof of
correctness of these algorithms (yet) ;)

The code is in the LTTng tree for the 2.6.32-rc8 kernel, they can be
listed by searching for "psrwlock" commits, e.g.:

http://git.kernel.org/?p=linux%2Fkernel%2Fgit%2Fcompudj%2Flinux-2.6-lttng.git&a=search&h=HEAD&st=commit&s=psrwlock

The main commit is:
http://git.kernel.org/?p=linux/kernel/git/compudj/linux-2.6-lttng.git;a=commit;h=4ae9a3960df1eefb726709ed6b697d739db3380b

Documentation (design explanation, performance tests):
http://git.kernel.org/?p=linux/kernel/git/compudj/linux-2.6-lttng.git;a=blob;f=Documentation/psrwlock.txt;h=5309aeb3d04d645d890b5dd7702982631a81e4c8;hb=18f769c8588a9368254b6c4bffc870f08cee6f97

I currently have to focus on my thesis defense (it's actually this
Friday), but I'll try to catch up with feedback if there happens to be
some. Please feel free to look at the code and clean it up if you think
it's worthwhile. It would be a shame to duplicate that work.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
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/