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/

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ