Skip to contentSkip to conversation

Cancellable MCS spinlock rework

RFC In review Jason Low 5 participants 22 messages Jul 2, 2014 – Jul 8, 2014 Locking primitives

lore
Share & tools
lore

Jason Low

author
#0 lore raw

RFC 1/1 Cancellable MCS spinlock rework

The cancellable MCS spinlock is currently used to queue threads that are doing optimistic spinning. It uses per-cpu nodes, where a thread obtaining the lock would access and queue the local node corresponding to the CPU that it's running on. Currently, the cancellable MCS lock is implemented by using pointers to these nodes.

In this RFC patch, instead of operating on pointers to the per-cpu nodes, we store the CPU numbers in which the per-cpu nodes correspond to in atomic_t. A similar concept is used with the qspinlock.

We add 1 to the CPU number to retrive an "encoded value" representing the node of that CPU. By doing this, 0 can represent "no CPU", which allows us to keep the simple "if (CPU)" and "if (!CPU)" checks. In this patch, the next and prev pointers in each node were also modified to store encoded CPU values.

By operating on the CPU # of the nodes using atomic_t instead of pointers to those nodes, this can reduce the overhead of the cancellable MCS spinlock by 32 bits (on 64 bit systems).

It was also found that the current cancellable MCS lock's use of ACCESS_ONCE stores + cmpxchg() on some architectures can result in race conditions. Since this change makes the cancellable MCS lock use atomic operations, this may also be able to address those problems and avoid needing to implement architecture dependant workarounds to avoid such issues with this lock.

---
 include/linux/mutex.h         |    4 +-
 include/linux/osq_lock.h      |    8 ++++
 include/linux/rwsem.h         |    7 ++--
 kernel/locking/mcs_spinlock.c |   81 ++++++++++++++++++++++++++++-------------
 kernel/locking/mcs_spinlock.h |    7 ++--
 kernel/locking/mutex.c        |    2 +-
 kernel/locking/rwsem-xadd.c   |    2 +-
 7 files changed, 74 insertions(+), 37 deletions(-)
 create mode 100644 include/linux/osq_lock.h
include/linux/mutex.h +2 -2
index 11692de..0809dc7 100644
@@ -17,6 +17,7 @@
 #include <linux/lockdep.h>
 #include <linux/atomic.h>
 #include <asm/processor.h>
+#include <linux/osq_lock.h>
 
 /*
  * Simple, straightforward mutexes with strict semantics:
@@ -46,7 +47,6 @@
  * - detects multi-task circular deadlocks and prints out all affected
  *   locks and tasks (and only those tasks)
  */
-struct optimistic_spin_queue;
 struct mutex {
 	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
 	atomic_t		count;
@@ -56,7 +56,7 @@ struct mutex {
 	struct task_struct	*owner;
 #endif
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	struct optimistic_spin_queue	*osq;	/* Spinner MCS lock */
+	struct optimistic_spin_tail osq; /* Spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_MUTEXES
 	const char 		*name;
include/linux/osq_lock.h new file +8 -0
new file mode 100644
index 0000000..582e8ff
@@ -0,0 +1,8 @@
+#ifndef __LINUX_OSQ_LOCK_H
+#define __LINUX_OSQ_LOCK_H
+
+struct optimistic_spin_tail {
+	atomic_t tail;	/* 0 indicates no tail (empty queue) */
+};
+
+#endif
include/linux/rwsem.h +3 -4
index 8d79708..cdefd08 100644
@@ -13,10 +13,9 @@
 #include <linux/kernel.h>
 #include <linux/list.h>
 #include <linux/spinlock.h>
-
 #include <linux/atomic.h>
+#include <linux/osq_lock.h>
 
-struct optimistic_spin_queue;
 struct rw_semaphore;
 
 #ifdef CONFIG_RWSEM_GENERIC_SPINLOCK
@@ -33,7 +32,7 @@ struct rw_semaphore {
 	 * if the owner is running on the cpu.
 	 */
 	struct task_struct *owner;
-	struct optimistic_spin_queue *osq; /* spinner MCS lock */
+	struct optimistic_spin_tail osq; /* spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;
@@ -70,7 +69,7 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 	  __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock),	\
 	  LIST_HEAD_INIT((name).wait_list),		\
 	  NULL, /* owner */				\
-	  NULL /* mcs lock */                           \
+	  { ATOMIC_INIT(0) } /* mcs lock */                           \
 	  __RWSEM_DEP_MAP_INIT(name) }
 #else
 #define __RWSEM_INITIALIZER(name)			\
kernel/locking/mcs_spinlock.c +55 -26

156 lines not on this page · raw message

kernel/locking/mcs_spinlock.h +4 -3
index a2dbac4..c07b5e4 100644
@@ -13,6 +13,7 @@
 #define __LINUX_MCS_SPINLOCK_H
 
 #include <asm/mcs_spinlock.h>
+#include <linux/osq_lock.h>
 
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
@@ -119,11 +120,11 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
  */
 
 struct optimistic_spin_queue {
-	struct optimistic_spin_queue *next, *prev;
+	atomic_t next, prev;
 	int locked; /* 1 if lock acquired */
 };
 
-extern bool osq_lock(struct optimistic_spin_queue **lock);
-extern void osq_unlock(struct optimistic_spin_queue **lock);
+extern bool osq_lock(struct optimistic_spin_tail *lock);
+extern void osq_unlock(struct optimistic_spin_tail *lock);
 
 #endif /* __LINUX_MCS_SPINLOCK_H */
kernel/locking/mutex.c +1 -1
index bc73d33..b668d8d 100644
@@ -60,7 +60,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
 	INIT_LIST_HEAD(&lock->wait_list);
 	mutex_clear_owner(lock);
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	lock->osq = NULL;
+	atomic_set(&lock->osq.tail, 0);
 #endif
 
 	debug_mutex_init(lock, name, key);
kernel/locking/rwsem-xadd.c +1 -1
index dacc321..b346ff2 100644
@@ -84,7 +84,7 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name,
 	INIT_LIST_HEAD(&sem->wait_list);
 #ifdef CONFIG_SMP
 	sem->owner = NULL;
-	sem->osq = NULL;
+	atomic_set(&sem->osq.tail, 0);
 #endif
 }
 
Signature · 1 line
1.7.1
maintainer
#1 lore raw
Quoted 10 lines · Jason Low

The cancellable MCS spinlock is currently used to queue threads that are doing optimistic spinning. It uses per-cpu nodes, where a thread obtaining the lock would access and queue the local node corresponding to the CPU that it's running on. Currently, the cancellable MCS lock is implemented by using pointers to these nodes.

In this RFC patch, instead of operating on pointers to the per-cpu nodes, we store the CPU numbers in which the per-cpu nodes correspond to in atomic_t. A similar concept is used with the qspinlock.

Quoted 8 lines

We add 1 to the CPU number to retrive an "encoded value" representing the node of that CPU. By doing this, 0 can represent "no CPU", which allows us to keep the simple "if (CPU)" and "if (!CPU)" checks. In this patch, the next and prev pointers in each node were also modified to store encoded CPU values.

By operating on the CPU # of the nodes using atomic_t instead of pointers to those nodes, this can reduce the overhead of the cancellable MCS spinlock by 32 bits (on 64 bit systems).

Still struggling to figure out why you did this.

author
#2 lore raw
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Jason Low

The cancellable MCS spinlock is currently used to queue threads that are doing optimistic spinning. It uses per-cpu nodes, where a thread obtaining the lock would access and queue the local node corresponding to the CPU that it's running on. Currently, the cancellable MCS lock is implemented by using pointers to these nodes.

In this RFC patch, instead of operating on pointers to the per-cpu nodes, we store the CPU numbers in which the per-cpu nodes correspond to in atomic_t. A similar concept is used with the qspinlock.

We add 1 to the CPU number to retrive an "encoded value" representing the node of that CPU. By doing this, 0 can represent "no CPU", which allows us to keep the simple "if (CPU)" and "if (!CPU)" checks. In this patch, the next and prev pointers in each node were also modified to store encoded CPU values.

Quoted 5 lines
Quoted 3 lines

By operating on the CPU # of the nodes using atomic_t instead of pointers to those nodes, this can reduce the overhead of the cancellable MCS spinlock by 32 bits (on 64 bit systems).

Still struggling to figure out why you did this.

Why I converted pointers to atomic_t?

This would avoid the potentially racy ACCESS_ONCE stores + cmpxchg while also using less overhead, since atomic_t is often only 32 bits while pointers could be 64 bits.

maintainer
#3 lore raw
Quoted 21 lines · Jason Low
Quoted 20 lines · Peter Zijlstra
Quoted 18 lines · Jason Low

The cancellable MCS spinlock is currently used to queue threads that are doing optimistic spinning. It uses per-cpu nodes, where a thread obtaining the lock would access and queue the local node corresponding to the CPU that it's running on. Currently, the cancellable MCS lock is implemented by using pointers to these nodes.

In this RFC patch, instead of operating on pointers to the per-cpu nodes, we store the CPU numbers in which the per-cpu nodes correspond to in atomic_t. A similar concept is used with the qspinlock.

We add 1 to the CPU number to retrive an "encoded value" representing the node of that CPU. By doing this, 0 can represent "no CPU", which allows us to keep the simple "if (CPU)" and "if (!CPU)" checks. In this patch, the next and prev pointers in each node were also modified to store encoded CPU values.

By operating on the CPU # of the nodes using atomic_t instead of pointers to those nodes, this can reduce the overhead of the cancellable MCS spinlock by 32 bits (on 64 bit systems).

Quoted 7 lines
Quoted 1 line

Still struggling to figure out why you did this.

Why I converted pointers to atomic_t?

This would avoid the potentially racy ACCESS_ONCE stores + cmpxchg while also using less overhead, since atomic_t is often only 32 bits while pointers could be 64 bits.

So no real good reason.. The ACCESS_ONCE stores + cmpxchg stuff is likely broken all over the place, and 'fixing' this one place doesn't cure the problem.

author
#4 lore raw
Quoted 26 lines · Peter Zijlstra
Quoted 25 lines · Jason Low
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Jason Low

The cancellable MCS spinlock is currently used to queue threads that are doing optimistic spinning. It uses per-cpu nodes, where a thread obtaining the lock would access and queue the local node corresponding to the CPU that it's running on. Currently, the cancellable MCS lock is implemented by using pointers to these nodes.

In this RFC patch, instead of operating on pointers to the per-cpu nodes, we store the CPU numbers in which the per-cpu nodes correspond to in atomic_t. A similar concept is used with the qspinlock.

We add 1 to the CPU number to retrive an "encoded value" representing the node of that CPU. By doing this, 0 can represent "no CPU", which allows us to keep the simple "if (CPU)" and "if (!CPU)" checks. In this patch, the next and prev pointers in each node were also modified to store encoded CPU values.

Quoted 5 lines
Quoted 3 lines

By operating on the CPU # of the nodes using atomic_t instead of pointers to those nodes, this can reduce the overhead of the cancellable MCS spinlock by 32 bits (on 64 bit systems).

Still struggling to figure out why you did this.

Why I converted pointers to atomic_t?

Quoted 7 lines
Quoted 3 lines

This would avoid the potentially racy ACCESS_ONCE stores + cmpxchg while also using less overhead, since atomic_t is often only 32 bits while pointers could be 64 bits.

So no real good reason.. The ACCESS_ONCE stores + cmpxchg stuff is likely broken all over the place, and 'fixing' this one place doesn't cure the problem.

Right, fixing the ACCESS_ONCE + cmpxchg and avoiding the architecture workarounds for optimistic spinning was just a nice side effect.

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

author
#5 lore raw
Quoted 13 lines · Jason Low
Quoted 11 lines · Peter Zijlstra
Quoted 6 lines · Jason Low

Why I converted pointers to atomic_t?

This would avoid the potentially racy ACCESS_ONCE stores + cmpxchg while also using less overhead, since atomic_t is often only 32 bits while pointers could be 64 bits.

So no real good reason.. The ACCESS_ONCE stores + cmpxchg stuff is likely broken all over the place, and 'fixing' this one place doesn't cure the problem.

Quoted 6 lines

Right, fixing the ACCESS_ONCE + cmpxchg and avoiding the architecture workarounds for optimistic spinning was just a nice side effect.

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

And due to padding, the additional modification below reduces the size of struct rw_semaphore by 64 bits on my machine :)

struct rw_semaphore {
long count;
- raw_spinlock_t wait_lock;
struct list_head wait_list;
+ raw_spinlock_t wait_lock;
#ifdef CONFIG_SMP
+ struct optimistic_spin_tail osq; /* spinner MCS lock */
/*
* Write owner. Used as a speculative check to see
* if the owner is running on the cpu.
*/
struct task_struct *owner;
- struct optimistic_spin_tail osq; /* spinner MCS lock */
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;

maintainer
#6 lore raw
Quoted 11 lines · Jason Low

And due to padding, the additional modification below reduces the size of struct rw_semaphore by 64 bits on my machine :)

struct rw_semaphore {

(quoted diff) +1 -1
 	long count;
-	raw_spinlock_t wait_lock;
 	struct list_head wait_list;
+	raw_spinlock_t wait_lock;
 #ifdef CONFIG_SMP

Review

Quoted 10 lines
(quoted diff) +1 -1
+	struct optimistic_spin_tail osq; /* spinner MCS lock */
 	/*
 	 * Write owner. Used as a speculative check to see
 	 * if the owner is running on the cpu.
 	 */
 	struct task_struct *owner;
-	struct optimistic_spin_tail osq; /* spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;

Right, that might make sense.

#7 lore raw
In reply to Jason Low
Quoted 3 lines · Jason Low

And due to padding, the additional modification below reduces the size of struct rw_semaphore by 64 bits on my machine :)

Well, I think you could also make 'count' just be 'int' instead of 'long'.

I don't think we'll support 2 _billion_ processes/threads waiting on the same semaphore any time soon, so the 'long' seems a bit of an overkill on 64-bit architectures.

Linus.

#8 lore raw
Quoted 4 lines · Linus Torvalds

I don't think we'll support 2 _billion_ processes/threads waiting on the same semaphore any time soon, so the 'long' seems a bit of an overkill on 64-bit architectures.

Oh, never mind. The 'struct semaphore' uses it as just a plain count, but the rwsem ends up splitting up the bits for readers/writers, so we actually do want the full 64-bit value there.

Linus

author
#9 lore raw
Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

I don't think we'll support 2 _billion_ processes/threads waiting on the same semaphore any time soon, so the 'long' seems a bit of an overkill on 64-bit architectures.

Oh, never mind. The 'struct semaphore' uses it as just a plain count, but the rwsem ends up splitting up the bits for readers/writers, so we actually do want the full 64-bit value there.

Yeah, that was the key to reducing the struct size as the rwsem count can't share a 64 bit chunk with the spinlock, unlike some of the other lock.

Thanks,
Jason

maintainer
#10 lore raw
In reply to Jason Low
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

#11 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

author
#12 lore raw
Quoted 11 lines · Davidlohr Bueso
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Right, especially if it could help things like xfs inode.

#13 lore raw
Quoted 12 lines · Jason Low
Quoted 9 lines · Davidlohr Bueso
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Right, especially if it could help things like xfs inode.

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t. The structure is cacheline aligned and there is no saving in size. Converting them to atomic_t does have a bit of additional overhead of converting the encoded cpu number back to the actual pointer.

So my suggestion is to just change what is stored in the mutex and rwsem structure to atomic_t, but keep the pointers in the optimistic_spin_queue structure.

-Longman

author
#14 lore raw
Quoted 9 lines · Waiman Long
Quoted 8 lines · Jason Low
Quoted 7 lines · Davidlohr Bueso
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Right, especially if it could help things like xfs inode.

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t.

Converting the pointers in the optimistic_spin_queue to atomic_t would mean we're fully operating on atomic operations instead of using the potentially racy cmpxchg + ACCESS_ONCE stores on the pointers.

If we're in the process of using the CPU numbers in atomic_t, I thought we might as well fix that as well since it has actually been shown to result in lockups on some architectures. We can then avoid needing to implement the tricky architecture workarounds for optimistic spinning. Wouldn't that be a "nice-have"?

Jason

#15 lore raw
Quoted 12 lines · Jason Low
Quoted 11 lines · Waiman Long
Quoted 10 lines · Jason Low
Quoted 9 lines · Davidlohr Bueso
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

Right, especially if it could help things like xfs inode.

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t.

Converting the pointers in the optimistic_spin_queue to atomic_t would mean we're fully operating on atomic operations instead of using the potentially racy cmpxchg + ACCESS_ONCE stores on the pointers.

Yes, the ACCESS_ONCE macro for data store does have problem on some architectures. However, I prefer a more holistic solution to solve this problem rather than a workaround by changing the pointers to atomic_t's. It is because even if we make the change, we are still not sure if that will work for those architectures as we have no machine to verify that. Why not let the champions of those architectures to propose changes instead of making some untested changes now and penalize commonly used architectures like x86.

Quoted 8 lines

If we're in the process of using the CPU numbers in atomic_t, I thought we might as well fix that as well since it has actually been shown to result in lockups on some architectures. We can then avoid needing to implement the tricky architecture workarounds for optimistic spinning. Wouldn't that be a "nice-have"?

Jason

I am not aware of any tricky architectural workarounds other than disabling optimistic spinning for those that don't support it.

-Longman

author
#16 lore raw
Quoted 22 lines · Waiman Long
Quoted 12 lines · Jason Low
Quoted 11 lines · Waiman Long
Quoted 10 lines · Jason Low
Quoted 9 lines · Davidlohr Bueso
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

Right, especially if it could help things like xfs inode.

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t.

Converting the pointers in the optimistic_spin_queue to atomic_t would mean we're fully operating on atomic operations instead of using the potentially racy cmpxchg + ACCESS_ONCE stores on the pointers.

Quoted 8 lines

Yes, the ACCESS_ONCE macro for data store does have problem on some architectures. However, I prefer a more holistic solution to solve this problem rather than a workaround by changing the pointers to atomic_t's. It is because even if we make the change, we are still not sure if that will work for those architectures as we have no machine to verify that. Why not let the champions of those architectures to propose changes instead of making some untested changes now and penalize commonly used architectures like x86.

So I initially was thinking that converting to atomic_t would not result in reducing performance on other architecture. However, you do have a point in your first post that converting the encoded cpu number to the pointer may add a little bit of overhead (in the contended cases).

If converting pointers to atomic_t in the optimistic_spin_queue structure does affect performance for commonly used architectures, then I agree that we should avoid that and only convert what's stored in mutex/rwsem.

maintainer
#17 lore raw
In reply to Jason Low
Quoted 23 lines · Jason Low
Quoted 9 lines · Waiman Long
Quoted 8 lines · Jason Low
Quoted 7 lines · Davidlohr Bueso
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Jason Low

Would potentially reducing the size of the rw semaphore structure by 32 bits (for all architectures using optimistic spinning) be a nice benefit?

Possibly, although I had a look at the mutex structure and we didn't have a hole to place it in, unlike what you found with the rwsem.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

Yeah, and currently struct rw_semaphore is the largest lock we have in the kernel. Shaving off space is definitely welcome.

Right, especially if it could help things like xfs inode.

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t.

Converting the pointers in the optimistic_spin_queue to atomic_t would mean we're fully operating on atomic operations instead of using the potentially racy cmpxchg + ACCESS_ONCE stores on the pointers.

Quoted 5 lines

If we're in the process of using the CPU numbers in atomic_t, I thought we might as well fix that as well since it has actually been shown to result in lockups on some architectures. We can then avoid needing to implement the tricky architecture workarounds for optimistic spinning. Wouldn't that be a "nice-have"?

Nah, I think those archs are fundamentally broken at the moment, we should not make code harder to read and or more complex just for them.

author
#18 lore raw
In reply to Waiman Long
Quoted 10 lines · Waiman Long

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t. The structure is cacheline aligned and there is no saving in size. Converting them to atomic_t does have a bit of additional overhead of converting the encoded cpu number back to the actual pointer.

So my suggestion is to just change what is stored in the mutex and rwsem structure to atomic_t, but keep the pointers in the optimistic_spin_queue structure.

Peter, would you prefer going with the above?

If we were to keep the pointers to the next and prev nodes in the struct optimistic_spin_queue instead of converting them to atomic_t to store their cpu #, we'd still need to keep track of the cpu #. In the unqueue phase of osq_lock, we might have to reload prev = node->prev which we then may cmpxchg() it with the lock tail.

The method we can think of so far would be to add a regular int variable to optimistic_spin_queue and initialize it to the CPU #, during the time we also initialize node->locked and node->next at the beginning of osq_lock. The cost wouldn't be much of an issue since optimistic_spin_queue is cache aligned.

maintainer
#19 lore raw
Quoted 21 lines · Jason Low
Quoted 10 lines · Waiman Long

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t. The structure is cacheline aligned and there is no saving in size. Converting them to atomic_t does have a bit of additional overhead of converting the encoded cpu number back to the actual pointer.

So my suggestion is to just change what is stored in the mutex and rwsem structure to atomic_t, but keep the pointers in the optimistic_spin_queue structure.

Peter, would you prefer going with the above?

If we were to keep the pointers to the next and prev nodes in the struct optimistic_spin_queue instead of converting them to atomic_t to store their cpu #, we'd still need to keep track of the cpu #. In the unqueue phase of osq_lock, we might have to reload prev = node->prev which we then may cmpxchg() it with the lock tail.

Quoted 5 lines

The method we can think of so far would be to add a regular int variable to optimistic_spin_queue and initialize it to the CPU #, during the time we also initialize node->locked and node->next at the beginning of osq_lock. The cost wouldn't be much of an issue since optimistic_spin_queue is cache aligned.

Let me try and have an actual look at the patch; I'm in the tail end of a flu and my head isn't quite set for details, but I'll buckle up and go look, gimme a few :-)

author
#20 lore raw
Quoted 22 lines · Peter Zijlstra
Quoted 21 lines · Jason Low
Quoted 10 lines · Waiman Long

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t. The structure is cacheline aligned and there is no saving in size. Converting them to atomic_t does have a bit of additional overhead of converting the encoded cpu number back to the actual pointer.

So my suggestion is to just change what is stored in the mutex and rwsem structure to atomic_t, but keep the pointers in the optimistic_spin_queue structure.

Peter, would you prefer going with the above?

If we were to keep the pointers to the next and prev nodes in the struct optimistic_spin_queue instead of converting them to atomic_t to store their cpu #, we'd still need to keep track of the cpu #. In the unqueue phase of osq_lock, we might have to reload prev = node->prev which we then may cmpxchg() it with the lock tail.

Quoted 7 lines
Quoted 5 lines

The method we can think of so far would be to add a regular int variable to optimistic_spin_queue and initialize it to the CPU #, during the time we also initialize node->locked and node->next at the beginning of osq_lock. The cost wouldn't be much of an issue since optimistic_spin_queue is cache aligned.

Let me try and have an actual look at the patch;

Okay, I will be sending out the patchset I had so that there's something more concrete.

maintainer
#21 lore raw
In reply to Jason Low
Quoted 9 lines · Jason Low
Quoted 7 lines · Waiman Long

I do see a point in reducing the size of the rwsem structure. However, I don't quite understand the point of converting pointers in the optimistic_spin_queue structure to atomic_t. The structure is cacheline aligned and there is no saving in size. Converting them to atomic_t does have a bit of additional overhead of converting the encoded cpu number back to the actual pointer.

Quoted 5 lines
Quoted 3 lines

So my suggestion is to just change what is stored in the mutex and rwsem structure to atomic_t, but keep the pointers in the optimistic_spin_queue structure.

Peter, would you prefer going with the above?

Yeah..

Quoted 11 lines

If we were to keep the pointers to the next and prev nodes in the struct optimistic_spin_queue instead of converting them to atomic_t to store their cpu #, we'd still need to keep track of the cpu #. In the unqueue phase of osq_lock, we might have to reload prev = node->prev which we then may cmpxchg() it with the lock tail.

The method we can think of so far would be to add a regular int variable to optimistic_spin_queue and initialize it to the CPU #, during the time we also initialize node->locked and node->next at the beginning of osq_lock. The cost wouldn't be much of an issue since optimistic_spin_queue is cache aligned.

Right, there's actually a 4 byte hole in there aside from the full cacheline alignment, so yeah, tons of space.