Skip to contentSkip to conversation

mutex subsystem, -V11

PATCH In review Ingo Molnar 4 participants 8 messages Jan 3, 2006 – Jan 5, 2006

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

cover mutex subsystem, -V11

this is version -V11 of the generic mutex subsystem, against v2.6.15. It consists of the following 19 patches:

add-atomic-xchg.patch
add-function-typecheck.patch

mutex-generic-asm-implementations.patch
mutex-asm-mutex.h-i386.patch
mutex-asm-mutex.h-x86_64.patch
mutex-asm-mutex.h-arm.patch
mutex-arch-mutex-h.patch
mutex-core.patch

mutex-docs.patch
mutex-debug.patch
mutex-debug-more.patch

sem2mutex-xfs.patch
sem2mutex-vfs-i-sem.patch
sem2mutex-vfs-i-sem-more.patch
sem2mutex-simple-ones.patch

sem2completion-sx8.patch
sem2completion-cpu5wdt.patch
sem2completion-ide-gendev.patch
sem2completion-loop.patch

the patches should work fine on every Linux architecture. They can also be downloaded from:

http://redhat.com/~mingo/generic-mutex-subsystem/

Changes since -V10:

  38 files changed, 99 insertions(+), 94 deletions(-)

- export mutex_trylock() too (reported by Antti Salmela)

- fixed attribution From: lines

- finished the i_sem -> i_mutex conversion: fixed up all affected documentation as well, and rarely used code. It builds fine under allyesconfig.

- DECLARE_MUTEX -> DEFINE_MUTEX in cpufreq

- small cleanups

Ingo

#1 lore raw
Quoted 1 line · Ingo Molnar

this is version -V11 of the generic mutex subsystem, against v2.6.15.

When compiling for x86 with no mutex debugging, I see:

	(gdb) disas mutex_lock
	Dump of assembler code for function mutex_lock:
	0xc02950d0 <mutex_lock+0>:      lock decl (%eax)
	0xc02950d3 <mutex_lock+3>:      js     0xc02950ef <.text.lock.mutex>
	0xc02950d5 <mutex_lock+5>:      ret    
	End of assembler dump.
	(gdb) disas 0xc02950ef
	Dump of assembler code for function .text.lock.mutex:
	0xc02950ef <.text.lock.mutex+0>:        call   0xc0294ffb <__mutex_lock_noinline>
	0xc02950f4 <.text.lock.mutex+5>:        jmp    0xc02950d5 <mutex_lock+5>
	0xc02950f6 <.text.lock.mutex+7>:        call   0xc029509f <__mutex_unlock_noinline>
	0xc02950fb <.text.lock.mutex+12>:       jmp    0xc02950db <mutex_unlock+5>
	End of assembler dump.

Can you arrange .text.lock.mutex+0 here to just jump directly to __mutex_lock_noinline? Otherwise we have an unnecessarily extended return path.

You may not want to make the JS go directly there, but you could have that go to a JMP to __mutex_lock_noinline rather than having a CALL followed by a JMP back to a return instruction.

Admittedly, this may not be possible, as you're mixing up C and ASM, but it would speed things up a little.

David

#2 lore raw
Quoted 20 lines · David Howells
Quoted 1 line · Ingo Molnar

this is version -V11 of the generic mutex subsystem, against v2.6.15.

When compiling for x86 with no mutex debugging, I see:

	(gdb) disas mutex_lock
	Dump of assembler code for function mutex_lock:
	0xc02950d0 <mutex_lock+0>:      lock decl (%eax)
	0xc02950d3 <mutex_lock+3>:      js     0xc02950ef <.text.lock.mutex>
	0xc02950d5 <mutex_lock+5>:      ret    
	End of assembler dump.
	(gdb) disas 0xc02950ef
	Dump of assembler code for function .text.lock.mutex:
	0xc02950ef <.text.lock.mutex+0>:        call   0xc0294ffb <__mutex_lock_noinline>
	0xc02950f4 <.text.lock.mutex+5>:        jmp    0xc02950d5 <mutex_lock+5>
	0xc02950f6 <.text.lock.mutex+7>:        call   0xc029509f <__mutex_unlock_noinline>
	0xc02950fb <.text.lock.mutex+12>:       jmp    0xc02950db <mutex_unlock+5>
	End of assembler dump.
Quoted 3 lines

Can you arrange .text.lock.mutex+0 here to just jump directly to __mutex_lock_noinline? Otherwise we have an unnecessarily extended return path.

jmp is free on x86. eg zero cycles. Any trickery is more likely to cost because of doing unexpected things.

Quoted 4 lines

You may not want to make the JS go directly there, but you could have that go to a JMP to __mutex_lock_noinline rather than having a CALL followed by a JMP back to a return instruction.

unbalanced call/ret pairs are REALLY expensive on x86. The current x86 processors all do branch prediction on the ret based on a special internal call stack, breaking the symmetry is thus a branch prediction miss, eg 40+ cycles

#3 lore raw
Quoted 6 lines · Arjan van de Ven
Quoted 3 lines

Can you arrange .text.lock.mutex+0 here to just jump directly to __mutex_lock_noinline? Otherwise we have an unnecessarily extended return path.

jmp is free on x86. eg zero cycles. Any trickery is more likely to cost because of doing unexpected things.

I'm talking about replacing:

	<caller>:		call
	mutex_lock:		 lock decl
	mutex_lock:		 js
	.text.lock.mutex:	  call
	__mutex_lock:		   ret
	.text.lock.mutex:	  jmp
	mutex_lock:		 ret
	<caller>:		...

With:

	<caller>:		call
	mutex_lock:		 lock decl
	mutex_lock:		 js
	.text.lock.mutex:	  jmp
	__mutex_lock:		   ret
	<caller>:		...

Or:

	<caller>:		call
	mutex_lock:		 lock decl
	mutex_lock:		 js
	__mutex_lock:		  ret
	<caller>:		...

This sort of thing is done by the compiler when it does tail-calling.

Quoted 8 lines
Quoted 3 lines

You may not want to make the JS go directly there, but you could have that go to a JMP to __mutex_lock_noinline rather than having a CALL followed by a JMP back to a return instruction.

unbalanced call/ret pairs are REALLY expensive on x86. The current x86 processors all do branch prediction on the ret based on a special internal call stack, breaking the symmetry is thus a branch prediction miss, eg 40+ cycles

In what way would this be unbalanced? You end up with one fewer CALL and one fewer RET instruction. And why would the CPU think this is any different from a function with a conditional branch in it? Eg:

	<caller>:		call
	mutex_lock:		 lock decl
	mutex_lock:		 js
	mutex_lock:		 ret
	<caller>:		...

The only route to __mutex_lock would be through mutex_lock...

Are there docs on this feature of the x86 anywhere?

David

#4 lore raw
Quoted 2 lines · David Howells

This sort of thing is done by the compiler when it does tail-calling.

Yes. And it's nice even when unconditional branches are effectively free, because it can avoid an unnecessary cache miss just to fetch the unnecessary branch (which very much _can_ happen, since the failure function will sleep).

Of course, the thing to look out for is to never get the call-return stack messed up, but this kind of regular tail-call doesn't have that issue.

Linus

#5 lore raw
In reply to Ingo Molnar

The attached patch adds a module for testing and benchmarking mutexes, semaphores and R/W semaphores.

Using it is simple:

insmod synchro-test.ko <args>

It will exit with error ENOANO after running the tests and printing the results to the kernel console log.

The available arguments are:

(*) mx=N

Start up to N mutex thrashing threads, where N is at most 20. All will try and thrash the same mutex.

(*) sm=N

Start up to N counting semaphore thrashing threads, where N is at most
20. All will try and thrash the same semaphore.

(*) ism=M

Initialise the counting semaphore with M, where M is any positive integer greater than zero. The default is 4.

(*) rd=N
(*) wr=O
(*) dg=P

Start up to N reader thrashing threads, O writer thrashing threads and P downgrader thrashing threads, where N, O and P are at most 20 apiece. All will try and thrash the same read/write semaphore.

(*) elapse=N

Run the tests for N seconds. The default is 5.

(*) load=N

Each thread delays for N uS whilst holding the lock. The dfault is 0.

(*) do_sched=1

Each thread will call schedule if required after each iteration.

(*) v=1

Print more verbose information, including a thread iteration distribution list.

The module should be enabled by turning on CONFIG_DEBUG_SYNCHRO_TEST to "m".

---
warthog>diffstat -p1 mutex-debug-module-2615rc7.diff

 Documentation/synchro-test.txt |   51 ++++
 kernel/Makefile                |    1 
 kernel/synchro-test.c          |  486 +++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig.debug              |   14 +
 4 files changed, 552 insertions(+)
Documentation/synchro-test.txt +51 -0
diff -uNrp linux-2.6.15-rc7-mutex/Documentation/synchro-test.txt linux-2.6.15-rc7-mutex-slowopt/Documentation/synchro-test.txt
@@ -0,0 +1,51 @@
+The synchro-test.ko module can be used for testing and benchmarking mutexes,
+semaphores and R/W semaphores.
+
+Using it is simple:
+
+	insmod synchro-test.ko <args>
+
+It will exit with error ENOANO after running the tests and printing the
+results to the kernel console log.
+
+The available arguments are:
+
+ (*) mx=N
+
+	Start up to N mutex thrashing threads, where N is at most 20. All will
+	try and thrash the same mutex.
+
+ (*) sm=N
+
+	Start up to N counting semaphore thrashing threads, where N is at most
+	20. All will try and thrash the same semaphore.
+
+ (*) ism=M
+
+	Initialise the counting semaphore with M, where M is any positive
+	integer greater than zero. The default is 4.
+
+ (*) rd=N
+ (*) wr=O
+ (*) dg=P
+
+	Start up to N reader thrashing threads, O writer thrashing threads and
+	P downgrader thrashing threads, where N, O and P are at most 20
+	apiece. All will try and thrash the same read/write semaphore.
+
+ (*) elapse=N
+
+	Run the tests for N seconds. The default is 5.
+
+ (*) load=N
+
+	Each thread delays for N uS whilst holding the lock. The dfault is 0.
+
+ (*) do_sched=1
+
+	Each thread will call schedule if required after each iteration.
+
+ (*) v=1
+
+	Print more verbose information, including a thread iteration
+	distribution list.
kernel/Makefile +1 -0
diff -uNrp linux-2.6.15-rc7-mutex/kernel/Makefile linux-2.6.15-rc7-mutex-slowopt/kernel/Makefile
@@ -33,6 +33,7 @@ obj-$(CONFIG_GENERIC_HARDIRQS) += irq/
 obj-$(CONFIG_CRASH_DUMP) += crash_dump.o
 obj-$(CONFIG_SECCOMP) += seccomp.o
 obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
+obj-$(CONFIG_DEBUG_SYNCHRO_TEST) += synchro-test.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/synchro-test.c +486 -0

486 lines not on this page · raw message

lib/Kconfig.debug +14 -0
diff -uNrp linux-2.6.15-rc7-mutex/lib/Kconfig.debug linux-2.6.15-rc7-mutex-slowopt/lib/Kconfig.debug
@@ -207,3 +207,17 @@ config RCU_TORTURE_TEST
 	  at boot time (you probably don't).
 	  Say M if you want the RCU torture tests to build as a module.
 	  Say N if you are unsure.
+
+config DEBUG_SYNCHRO_TEST
+	tristate "Synchronisation primitive testing module"
+	depends on DEBUG_KERNEL
+	default n
+	help
+	  This option provides a kernel module that can thrash the sleepable
+	  synchronisation primitives (mutexes and semaphores). 
+
+	  You should say N or M here. Whilst the module can be built in, it's
+	  not recommended as it requires module parameters supplying to get it
+	  to do anything.
+
+	  See Documentation/synchro-test.txt.
#6 lore raw
Quoted 2 lines · David Howells

The attached patch adds a module for testing and benchmarking mutexes, semaphores and R/W semaphores.

thanks!

Quoted 3 lines

(*) load=N

Each thread delays for N uS whilst holding the lock. The dfault is 0.

could you possibly also add an option that delays a thread while _not_ holding the lock? The time spent not holding the lock is an important parameter of mutex workloads too.

Ingo

#7 lore raw

PATCH 1/1 Add synchronisation primitive testing module

The attached patch adds a module for testing and benchmarking mutexes, semaphores and R/W semaphores.

Using it is simple:

insmod synchro-test.ko <args>

It will exit with error ENOANO after running the tests and printing the results to the kernel console log.

The available arguments are:

(*) mx=N

Start up to N mutex thrashing threads, where N is at most 20. All will try and thrash the same mutex.

(*) sm=N

Start up to N counting semaphore thrashing threads, where N is at most
20. All will try and thrash the same semaphore.

(*) ism=M

Initialise the counting semaphore with M, where M is any positive integer greater than zero. The default is 4.

(*) rd=N
(*) wr=O
(*) dg=P

Start up to N reader thrashing threads, O writer thrashing threads and P downgrader thrashing threads, where N, O and P are at most 20 apiece. All will try and thrash the same read/write semaphore.

(*) elapse=N

Run the tests for N seconds. The default is 5.

(*) load=N

Each thread delays for N uS whilst holding the lock. The dfault is 0.

(*) interval=N

	Each thread delays for N uS whilst not holding the lock. The default
	is 0.

(*) do_sched=1

Each thread will call schedule if required after each iteration.

(*) v=1

Print more verbose information, including a thread iteration distribution list.

The module should be enabled by turning on CONFIG_DEBUG_SYNCHRO_TEST to "m".

---
warthog>diffstat -p1 mutex-debug-module-2615rc7-2.diff

 Documentation/synchro-test.txt |   59 ++++
 kernel/Makefile                |    1 
 kernel/synchro-test.c          |  503 +++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig.debug              |   14 +
 4 files changed, 577 insertions(+)
Documentation/synchro-test.txt +59 -0
diff -uNrp linux-2.6.15-rc7-mutex/Documentation/synchro-test.txt linux-2.6.15-rc7-mutex-slowopt/Documentation/synchro-test.txt
@@ -0,0 +1,59 @@
+The synchro-test.ko module can be used for testing and benchmarking mutexes,
+semaphores and R/W semaphores.
+
+The module is compiled by setting CONFIG_DEBUG_SYNCHRO_TEST to "m" when
+configuring the kernel.
+
+Using it is simple:
+
+	insmod synchro-test.ko <args>
+
+It will exit with error ENOANO after running the tests and printing the
+results to the kernel console log.
+
+The available arguments are:
+
+ (*) mx=N
+
+	Start up to N mutex thrashing threads, where N is at most 20. All will
+	try and thrash the same mutex.
+
+ (*) sm=N
+
+	Start up to N counting semaphore thrashing threads, where N is at most
+	20. All will try and thrash the same semaphore.
+
+ (*) ism=M
+
+	Initialise the counting semaphore with M, where M is any positive
+	integer greater than zero. The default is 4.
+
+ (*) rd=N
+ (*) wr=O
+ (*) dg=P
+
+	Start up to N reader thrashing threads, O writer thrashing threads and
+	P downgrader thrashing threads, where N, O and P are at most 20
+	apiece. All will try and thrash the same read/write semaphore.
+
+ (*) elapse=N
+
+	Run the tests for N seconds. The default is 5.
+
+ (*) load=N
+
+	Each thread delays for N uS whilst holding the lock. The default is 0.
+
+ (*) interval=N
+
+	Each thread delays for N uS whilst not holding the lock. The default
+	is 0.
+
+ (*) do_sched=1
+
+	Each thread will call schedule if required after each iteration.
+
+ (*) v=1
+
+	Print more verbose information, including a thread iteration
+	distribution list.
kernel/Makefile +1 -0
diff -uNrp linux-2.6.15-rc7-mutex/kernel/Makefile linux-2.6.15-rc7-mutex-slowopt/kernel/Makefile
@@ -33,6 +33,7 @@ obj-$(CONFIG_GENERIC_HARDIRQS) += irq/
 obj-$(CONFIG_CRASH_DUMP) += crash_dump.o
 obj-$(CONFIG_SECCOMP) += seccomp.o
 obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
+obj-$(CONFIG_DEBUG_SYNCHRO_TEST) += synchro-test.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/synchro-test.c +503 -0

503 lines not on this page · raw message

lib/Kconfig.debug +14 -0
diff -uNrp linux-2.6.15-rc7-mutex/lib/Kconfig.debug linux-2.6.15-rc7-mutex-slowopt/lib/Kconfig.debug
@@ -207,3 +207,17 @@ config RCU_TORTURE_TEST
 	  at boot time (you probably don't).
 	  Say M if you want the RCU torture tests to build as a module.
 	  Say N if you are unsure.
+
+config DEBUG_SYNCHRO_TEST
+	tristate "Synchronisation primitive testing module"
+	depends on DEBUG_KERNEL
+	default n
+	help
+	  This option provides a kernel module that can thrash the sleepable
+	  synchronisation primitives (mutexes and semaphores). 
+
+	  You should say N or M here. Whilst the module can be built in, it's
+	  not recommended as it requires module parameters supplying to get it
+	  to do anything.
+
+	  See Documentation/synchro-test.txt.