Re: [rfc] "fair" rw spinlocks

[Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>]

Nick Piggin <npiggin@suse.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