Skip to contentSkip to conversation

x86, mutex: non-atomic unlock (and a rant)

RFC PATCH In review Nick Piggin 3 participants 5 messages Nov 2, 2009

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

RFC PATCH 1/1 x86, mutex: non-atomic unlock (and a rant)

Hi,

Chasing performance regressions, as usual (and not of the nice patch X caused a n% slowdown type, but n% slowdown between a couple of years of kernel releases, with few or no patches causing something above the noise).

Unfortunately, our biggest competitors are our previous kernels, and we (were?) really good at writing really fast kernels. And most of our users who are running the competition are completely satisfied with all the features it has[*], so an "upgrade" that causes a slowdown does not go down well. A feature that 0.01% of people might use but causes a 0.1% slowdown for everyone else... may not actually be a good idea. Performance is a feature too, and every time we do this, we trade off a little bit of that for things most people don't need.

[*] modulo hardware support perhaps

Anyway, end rant. Not much gets achieved by ranting, and seeing as I can't just magic away overhead-causing features, then I've just been looking for places to cut costs. So...

Non-atomic unlock for mutexs maybe? I do this by relying on cache coherence on a cacheline basis for ordering rather than the memory consistency of the x86. Linus I know you've told me this is an incorrect assumption in the past, but I'm not so sure. If it is worthwhile, then maybe we can ask the HW guys if we're allowed to do this? There are actually other places where we could do similar tricks to avoid heavy barriers...

In lmbench style syscall microbenchmarks I'm running, it is hard to see much significant difference on a core2 with single threaded tests. I'd say it could be very slightly favourable.

I also got rid of the more clever calling sequence when I was tinkering with this patch which maybe could be added back in, although I didn't like how it generated a short forward cond jump on success (to jump over the fail_fn call).

---
 arch/x86/include/asm/mutex.h    |  105 ++++++++++++++++++++++++++++++++-
 arch/x86/include/asm/mutex_32.h |  125 ----------------------------------------
 arch/x86/include/asm/mutex_64.h |  100 --------------------------------
 include/linux/mutex.h           |    4 -
 kernel/mutex.c                  |   76 ++++++++----------------
 5 files changed, 132 insertions(+), 278 deletions(-)
arch/x86/include/asm/mutex.h +102 -3
Index: linux-2.6/arch/x86/include/asm/mutex.h
===================================================================
@@ -1,5 +1,104 @@
-#ifdef CONFIG_X86_32
-# include "mutex_32.h"
+/*
+ * Assembly implementation of the mutex fastpath, based on atomic
+ * decrement/increment.
+ *
+ * started by Ingo Molnar:
+ *
+ *  Copyright (C) 2004, 2005, 2006 Red Hat, Inc., Ingo Molnar <[email protected]>
+ */
+#ifndef _ASM_X86_MUTEX_H
+#define _ASM_X86_MUTEX_H
+
+/**
+ *  __mutex_fastpath_lock - try to take the lock by moving the count
+ *                          from 1 to a 0 value
+ *  @count: pointer of type atomic_t
+ *  @fn: function to call if the original value was not 1
+ *
+ * Change the count from 1 to a value lower than 1, and call <fn> if it
+ * wasn't 1 originally. This function MUST leave the value lower than 1
+ * even when the "1" assertion wasn't true.
+ */
+static inline void __mutex_fastpath_lock(struct mutex *lock,
+					       void (*fail_fn)(struct mutex *))
+{
+	if (unlikely(atomic_dec_return(&lock->count) < 0))
+		fail_fn(lock);
+}
+
+/**
+ *  __mutex_fastpath_lock_retval - try to take the lock by moving the count
+ *                                 from 1 to a 0 value
+ *  @count: pointer of type atomic_t
+ *  @fail_fn: function to call if the original value was not 1
+ *
+ * Change the count from 1 to a value lower than 1, and call <fail_fn> if it
+ * wasn't 1 originally. This function returns 0 if the fastpath succeeds,
+ * or anything the slow path function returns
+ */
+static inline int __mutex_fastpath_lock_retval(struct mutex *lock,
+					       int (*fail_fn)(struct mutex *))
+{
+	if (unlikely(atomic_dec_return(&lock->count) < 0))
+		return fail_fn(lock);
+	else
+		return 0;
+}
+
+/**
+ *  __mutex_fastpath_unlock - try to promote the mutex from 0 to 1
+ *  @count: pointer of type atomic_t
+ *  @fail_fn: function to call if the original value was not 0
+ *
+ * try to promote the mutex from 0 to 1. if it wasn't 0, call <fail_fn>.
+ * In the failure case, this function is allowed to either set the value
+ * to 1, or to set it to a value lower than 1.
+ *
+ * If the implementation sets it to a value of lower than 1, the
+ * __mutex_slowpath_needs_to_unlock() macro needs to return 1, it needs
+ * to return 0 otherwise.
+ */
+static inline void __mutex_fastpath_unlock(struct mutex *lock,
+					       void (*fail_fn)(struct mutex *))
+{
+	atomic_set(&lock->count, 1);
+	barrier();
+	if (unlikely(lock->waiters))
+		fail_fn(lock);
+}
+
+/**
+ * __mutex_fastpath_trylock - try to acquire the mutex, without waiting
+ *
+ *  @count: pointer of type atomic_t
+ *  @fail_fn: fallback function
+ *
+ * Change the count from 1 to a value lower than 1, and return 0 (failure)
+ * if it wasn't 1 originally, or return 1 (success) otherwise. This function
+ * MUST leave the value lower than 1 even when the "1" assertion wasn't true.
+ * Additionally, if the value was < 0 originally, this function must not leave
+ * it to 0 on failure.
+ */
+static inline int __mutex_fastpath_trylock(struct mutex *lock,
+					   int (*fail_fn)(struct mutex *))
+{
+	/*
+	 * We have two variants here. The cmpxchg based one is the best one
+	 * because it never induce a false contention state.  It is included
+	 * here because architectures using the inc/dec algorithms over the
+	 * xchg ones are much more likely to support cmpxchg natively.
+	 *
+	 * If not we fall back to the spinlock based variant - that is
+	 * just as efficient (and simpler) as a 'destructive' probing of
+	 * the mutex state would be.
+	 */
+#ifdef __HAVE_ARCH_CMPXCHG
+	if (likely(atomic_cmpxchg(&lock->count, 1, 0) == 1))
+		return 1;
+	return 0;
 #else
-# include "mutex_64.h"
+	return fail_fn(&lock->count);
 #endif
+}
+
+#endif /* _ASM_X86_MUTEX_H */
arch/x86/include/asm/mutex_32.h deleted +0 -125

125 lines not on this page · raw message

include/linux/mutex.h +3 -1
Index: linux-2.6/include/linux/mutex.h
===================================================================
@@ -48,6 +48,7 @@
 struct mutex {
 	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
 	atomic_t		count;
+	unsigned int		waiters;
 	spinlock_t		wait_lock;
 	struct list_head	wait_list;
 #if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_SMP)
@@ -60,7 +61,8 @@ struct mutex {
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;
 #endif
-};
+} __attribute__((aligned(sizeof(atomic_t)+sizeof(unsigned int))));
+  /* first 2 atomics must be in the same cacheline */
 
 /*
  * This is the control structure for tasks blocked on mutex,
kernel/mutex.c +27 -49

222 lines not on this page · raw message

arch/x86/include/asm/mutex_64.h deleted +0 -100

100 lines not on this page · raw message

#1 lore raw
Quoted 5 lines · Nick Piggin

Non-atomic unlock for mutexs maybe? I do this by relying on cache coherence on a cacheline basis for ordering rather than the memory consistency of the x86. Linus I know you've told me this is an incorrect assumption in the past, but I'm not so sure.

I'm sure.

This is simply buggy:

arch/x86/include/asm/mutex.h line 67

Quoted 4 lines
arch/x86/include/asm/mutex.h +4 -0
+	atomic_set(&lock->count, 1);
+	barrier();
+	if (unlikely(lock->waiters))
+		fail_fn(lock);

because it doesn't matter one whit whether 'lock->count' and 'lock->waiters' are in the same cacheline or not.

The cache coherency deals in cachelines, but the instruction re-ordering logic does not. It's entirely possible that the CPU will turn this into

	tmp = lock->waiters;
	...
	atomic_set(&lock->count, 1);
	if (tmp)
		fail_fn(lock);

and your "barrier()" did absolutely nothing.

The fact that it may _work_ in almost all circumstances (and perhaps even "always" on some microarchitectures) is irrelevant. It's simply not guaranteed to work. Yes, you need just the right timings, and yes, it's probably hard to hit. And yes, I can well imagine that some micro- architecture will even guarantee the write->read ordering, and that it would _always_ work on that micro-architecture.

But I can see your thing failing even on an in-order CPU. It literally doesn't even need OoO to fail, all it needs is a sufficiently deep write buffer on an in-order core. And to fail in practice, maybe there needs to be lots of writes in that buffer, and some bad luck, but the thing is, write buffers are not coherent between cores - so the write may have happened as far as the core that does it is concerned, but other cores (or even HT) may not see the new value until after the read has taken effect.

Linus

#2 lore raw
Quoted 39 lines · Linus Torvalds
Quoted 5 lines · Nick Piggin

Non-atomic unlock for mutexs maybe? I do this by relying on cache coherence on a cacheline basis for ordering rather than the memory consistency of the x86. Linus I know you've told me this is an incorrect assumption in the past, but I'm not so sure.

I'm sure.

This is simply buggy:

arch/x86/include/asm/mutex.h line 67

Quoted 4 lines
arch/x86/include/asm/mutex.h +4 -0
+	atomic_set(&lock->count, 1);
+	barrier();
+	if (unlikely(lock->waiters))
+		fail_fn(lock);

because it doesn't matter one whit whether 'lock->count' and 'lock->waiters' are in the same cacheline or not.

The cache coherency deals in cachelines, but the instruction re-ordering logic does not. It's entirely possible that the CPU will turn this into

	tmp = lock->waiters;
	...
	atomic_set(&lock->count, 1);
	if (tmp)
		fail_fn(lock);

and your "barrier()" did absolutely nothing.

The fact that it may _work_ in almost all circumstances (and perhaps even "always" on some microarchitectures) is irrelevant. It's simply not guaranteed to work. Yes, you need just the right timings, and yes, it's probably hard to hit. And yes, I can well imagine that some micro- architecture will even guarantee the write->read ordering, and that it would _always_ work on that micro-architecture.

Quoted 8 lines

But I can see your thing failing even on an in-order CPU. It literally doesn't even need OoO to fail, all it needs is a sufficiently deep write buffer on an in-order core. And to fail in practice, maybe there needs to be lots of writes in that buffer, and some bad luck, but the thing is, write buffers are not coherent between cores - so the write may have happened as far as the core that does it is concerned, but other cores (or even HT) may not see the new value until after the read has taken effect.

Hm OK I see you must be right there. The trick will only be guaranteed to work if you operate on exactly the same memory location I guess (or for store/store vs load/load sequences). In which case, atomic ops can't be avoided for the unlock case :(

Well, it can use a barrier instead of atomic for unlock, which might help on some architectures but on x86 I don't think it does much.

#3 lore raw
In reply to Linus Torvalds

[Linus Torvalds - Mon, Nov 02, 2009 at 07:20:08AM -0800]

| 
| On Mon, 2 Nov 2009, Nick Piggin wrote:
| > 
| > Non-atomic unlock for mutexs maybe? I do this by relying on cache
| > coherence on a cacheline basis for ordering rather than the memory
| > consistency of the x86. Linus I know you've told me this is an incorrect
| > assumption in the past, but I'm not so sure.
| 
| I'm sure.
| 
| This is simply buggy:
| 
| > +	atomic_set(&lock->count, 1);
| > +	barrier();
| > +	if (unlikely(lock->waiters))
| > +		fail_fn(lock);
| 
| because it doesn't matter one whit whether 'lock->count' and 
| 'lock->waiters' are in the same cacheline or not.
| 
| The cache coherency deals in cachelines, but the instruction re-ordering 
| logic does not. It's entirely possible that the CPU will turn this into
| 
| 	tmp = lock->waiters;
| 	...
| 	atomic_set(&lock->count, 1);
| 	if (tmp)
| 		fail_fn(lock);
| 
| and your "barrier()" did absolutely nothing.

...

If we write it as

	atomic_set(&lock->count, 1);
	some-serializing-op(); /* say cpuid() */
	if (unlikely(lock->waiters))
		fail_fn(lock);

This should do the trick, though this serializing operation is always cost too much.

The other option could be that we put two mem-write operations like

	int tmp;
	atomic_set(&lock->count, 1);
	tmp = lock->waiters;
	rmb();
	lock->waiters = tmp;
	if (unlikely(lock->waiters))
		fail_fn(lock);

Which should work faster then cpuid (and we have to be sure somehow that gcc doesn't suppress this redundant operations).

-- Cyrill

#4 lore raw

[Cyrill Gorcunov - Mon, Nov 02, 2009 at 07:46:26PM +0300]

| 
| The other option could be that we put two mem-write operations
| like
| 	int tmp;
| 	atomic_set(&lock->count, 1);
| 	tmp = lock->waiters;
| 	rmb();
| 	lock->waiters = tmp;
| 	if (unlikely(lock->waiters))
| 		fail_fn(lock);
| 
| Which should work faster then cpuid (and we have to be sure somehow
| that gcc doesn't suppress this redundant operations).
|

And which has nothing to do with OoO mem-read, and wouldn't work. Sorry for noise.

-- Cyrill