big reader semaphore take#2
RFC PATCH 1/1 big reader semaphore take#2
Hello guys,
This is the second take of brsem (big reader semaphore).
Nick, unfortunately, simple array of rwsem's does not work as lock holders are not pinned down to cpus and may release locks on other cpus.
This is a compeletely new implementation and much simpler than the first one. Each brsem is consisted of shared part and two per-cpu counters. Read fast path involves only one atomic_add_return and following conditional jump just as in rwsem.
The patch is against 2.6.14-rc4 and only implements brsem. It does not apply it to anywhere. My simple concurrent dd benchmark shows clear improvement over regular rwsem but it seems that there are too many factors affecting the bench. I'll soon create another micro bench which concentrates only on synchronization and post the result.
I've written a document to describe how brsem works. The document seems a bit too long for direct posting. It can be accessed at the following page.
http://home-tj.org/wiki/index.php/Brsem
Any comments are welcomed.
Thanks.
include/asm-i386/atomic.h +5 -0
@@ -178,6 +178,11 @@ static __inline__ int atomic_add_negativreturn c; } +static __inline__int atomic_xchg (atomic_t *v,int i) +{ +return xchg (&v->counter, i); +} +/** * atomic_add_return - add and return * @v: pointer of type atomic_t
include/asm-x86_64/atomic.h +6 -0
@@ -2,6 +2,7 @@#define __ARCH_X86_64_ATOMIC__#include <linux/config.h> +#include <asm/system.h> /* xchg */ /* atomic_t should be 32 bit signed type */
@@ -178,6 +179,11 @@ static __inline__ int atomic_add_negativreturn c; } +static __inline__int atomic_xchg (atomic_t *v,int i) +{ +return xchg (&v->counter, i); +} +/* An 64bit atomic type */ typedef struct {volatile long counter; }atomic64_t ;
include/linux/brsem-generic.h new file +56 -0
56 lines not on this page · raw message
include/linux/brsem.h new file +62 -0
62 lines not on this page · raw message
kernel/Makefile +1 -1
@@ -7,7 +7,7 @@ obj-y = sched.o fork.o exec_domain.o sysctl.o capability.o ptrace.o timer.o user.o \ signal.o sys.o kmod.o workqueue.o pid.o \ rcupdate.o intermodule.o extable.o params.o posix-timers.o \ - kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o + kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o brsem.o obj-$(CONFIG_FUTEX) += futex.o obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
kernel/brsem.c new file +318 -0
318 lines not on this page · raw message
Quoted 8 lines · Tejun Heo
Hello guys,
This is the second take of brsem (big reader semaphore).
Nick, unfortunately, simple array of rwsem's does not work as lock holders are not pinned down to cpus and may release locks on other cpus.
That's right. It would require down_read to return the index or a pointer to the lock that it took, and to pass that into up_read. So it wouldn't be a completely drop-in replacement for a regular semaphore if that's what you had in mind?
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 19 lines · Tejun Heo
Hello guys,
This is the second take of brsem (big reader semaphore).
Nick, unfortunately, simple array of rwsem's does not work as lock holders are not pinned down to cpus and may release locks on other cpus.
This is a compeletely new implementation and much simpler than the first one. Each brsem is consisted of shared part and two per-cpu counters. Read fast path involves only one
atomic_add_returnand following conditional jump just as in rwsem.The patch is against 2.6.14-rc4 and only implements brsem. It does not apply it to anywhere. My simple concurrent dd benchmark shows clear improvement over regular rwsem but it seems that there are too many factors affecting the bench. I'll soon create another micro bench which concentrates only on synchronization and post the result.
Quoted 8 lines
I've written a document to describe how brsem works. The document seems a bit too long for direct posting. It can be accessed at the following page.
http://home-tj.org/wiki/index.php/Brsem
Any comments are welcomed.
brsem is updated to use custom wait mechanism as rwsem does such that it isn't affected by wakeup's from other sources. Also there are some minor fixes like exporting interface functions to modules.
Also, a module named test-brsem is written to perform simple micro-benchmarking with correctness verification. I did reader performance test and the result is appended to brsem.txt.
The test is basically.... (taken from brsem.txt)
Quoted 12 lines
For each of NOSYNC, RWSEM and BRSEM cases, the following test is repeated with 1, 2, 4 and 8 concurrent readers.
- there are 32768 16-byte blocks allocated using vmalloc.
- the following actions are repeated 10000000 times.
- reader performs the following action 0-2 times.
- select a random block and calculate SHA1 of the block.
- reader does nothing ordown_readrwsem ordown_readbrsem
- reader performs the following action 0-2 times.
- select a random block and calculate SHA1 of the block.
- reader does nothing orup_readrwsem orup_readbrsem
Quoted 2 lines
Used system times are collected from all readers. Each test is run 6 times and averaged. All results are in milliseconds.
And the result and conclusion is... (taken from brsem.txt)
Quoted 9 lines
RATIO AGAINST NOSYNC each #thr
NOSYNC RWSEM BRSEM
#thr | /thr ratio /thr ratio /thr ratio
--------------------------------------------------------1 | 12356 1.0000 12478 1.0098 12654 1.0241 2 | 12423 1.0000 13747 1.1065 12710 1.0231 4 | 12471 1.0000 14364 1.1517 12759 1.0230 8 | 12483 1.0000 14344 1.1490 12772 1.0231
Quoted 6 lines
The last table shows how much more cpu cycles each thread has used in RWSEM and BRSEM cases compared against NOSYNC case of the same concurrency. RWSEM's ratio against NOSYNC increases as concurrency increases (upto four) but BRSEM's ratio stays virtually constant. i.e. BRSEM's overhead stays constant regardless of the number of processors participating in synchronization.
Please visit the following URL for further information and sources.
http://home-tj.org/wiki/index.php/Brsem
Thanks.
(Nick, what do you think about the new implementation?)
Signature · 1 line
tejun
Quoted 10 lines · Tejun Heo
Quoted 8 lines · Tejun Heo
Hello guys,
This is the second take of brsem (big reader semaphore).
Nick, unfortunately, simple array of rwsem's does not work as lock holders are not pinned down to cpus and may release locks on other cpus.
[...]
Quoted 3 lines
(Nick, what do you think about the new implementation?)
As I said, I think I'd prefer to see an implementation that returns a token from down_read to be used in up_read (ie. the slot # of the counter which has been downed).
This obviously no longer makes it a drop in replacement for an rwsem. But could such a beast ever be considered so? Would that make your VFS patches really ugly?
The upshot of that would be that you could build the whole thing from rwsem infrastructure and have basically zero other locking mechanisms or complexity that you don't want in a synchronisation primitive.
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 16 lines · Nick Piggin
Quoted 10 lines · Tejun Heo
Quoted 8 lines · Tejun Heo
Hello guys,
This is the second take of brsem (big reader semaphore).
Nick, unfortunately, simple array of rwsem's does not work as lock holders are not pinned down to cpus and may release locks on other cpus.
[...]
Quoted 1 line
Quoted 7 lines
Quoted 2 lines
(Nick, what do you think about the new implementation?)
As I said, I think I'd prefer to see an implementation that returns a token from
down_readto be used inup_read(ie. the slot # of the counter which has been downed).
Oh... I read your response but thought that was only response to 'that wouldn't work' part.
Quoted 3 lines
This obviously no longer makes it a drop in replacement for an rwsem. But could such a beast ever be considered so? Would that make your VFS patches really ugly?
I think Al Viro is on that now.
Quoted 5 lines
The upshot of that would be that you could build the whole thing from rwsem infrastructure and have basically zero other locking mechanisms or complexity that you don't want in a synchronisation primitive.
To certain extent, I do agree with you - it's safer/simpler..., but on the other hand, new brsem isn't that more complex and would perform almost identically without extra semantical baggage. So, I thought it might be worth a bit more effort.
Hmm... So, array of rwsem's, it should be.
Thanks.
Signature · 1 line
tejun
Quoted 10 lines · Tejun Heo
Quoted 5 lines · Nick Piggin
The upshot of that would be that you could build the whole thing from rwsem infrastructure and have basically zero other locking mechanisms or complexity that you don't want in a synchronisation primitive.
To certain extent, I do agree with you - it's safer/simpler..., but on the other hand, new brsem isn't that more complex and would perform almost identically without extra semantical baggage. So, I thought it might be worth a bit more effort.
I would do it thisway if possible, yes.
Quoted 2 lines
Hmm... So, array of rwsem's, it should be.
First implementation would be per-cpu just rwsems. A second patch to make it just an array rwsem->count's plus a shared queue may be in order - OTOH everyone does their own rwsems, so this will be a bit of a headache.
I forget - are you just planning to use one global brsem? In this case the size issue wouldn't be a pressing one.
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com