Skip to contentSkip to conversation

rwsem: Implement writer lock-stealing

PATCH In review Michel Lespinasse 4 participants 15 messages Feb 9, 2013 – Feb 20, 2013

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

cover rwsem: Implement writer lock-stealing

This proposal implements writer lock stealing in lib/rwsem.c, just as Alex Shi's earlier proposal did for the simpler lib/rwsem-spinlock.c

Patches 1 and 2 are small cleanups that I thought I should separate from the bulk of the changes; Patch 3 is the generic support for write lock stealing; Patch 4 is the x86 support (optional, only required for higher performance).

I am not in an ideal position to push this as I will be out of town starting from the middle of next week. However, I hope that this proposal will at least get the ball rolling. I did run some basic testing including David Howell's synchro-test module (as found in Andrew's -mm tree).

Michel Lespinasse (4):
rwsem: make the waiter type an enumeration rather than a bitmask
rwsem: shorter spinlocked section in rwsem_down_failed_common()
rwsem: implement write lock stealing
x86 rwsem: avoid taking slow path when stealing write lock

 arch/x86/include/asm/rwsem.h |  28 +++--
 include/linux/rwsem.h        |   2 +
 lib/rwsem.c                  | 252 ++++++++++++++++++++-----------------------
 3 files changed, 139 insertions(+), 143 deletions(-)
Signature · 1 line
1.8.1
#1 lore raw

PATCH 1/4 rwsem: make the waiter type an enumeration rather than a bitmask

We are not planning to add some new waiter flags, so we can convert the waiter type into an enumeration.

Background: David Howells suggested I do this back when I tried adding a new waiter type for unfair readers. However, I believe the cleanup applies regardless of that use case.

---
 lib/rwsem.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)
lib/rwsem.c +11 -8
index 8337e1b9bb8d..4a6ff093a433 100644
@@ -28,12 +28,15 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name,
 
 EXPORT_SYMBOL(__init_rwsem);
 
+enum rwsem_waiter_type {
+	RWSEM_WAITING_FOR_WRITE,
+	RWSEM_WAITING_FOR_READ
+};
+
 struct rwsem_waiter {
 	struct list_head list;
 	struct task_struct *task;
-	unsigned int flags;
-#define RWSEM_WAITING_FOR_READ	0x00000001
-#define RWSEM_WAITING_FOR_WRITE	0x00000002
+	enum rwsem_waiter_type type;
 };
 
 /* Wake types for __rwsem_do_wake().  Note that RWSEM_WAKE_NO_ACTIVE and
@@ -63,7 +66,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type)
 	signed long oldcount, woken, loop, adjustment;
 
 	waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
-	if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
+	if (waiter->type != RWSEM_WAITING_FOR_WRITE)
 		goto readers_only;
 
 	if (wake_type == RWSEM_WAKE_READ_OWNED)
@@ -132,10 +135,10 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type)
 		waiter = list_entry(waiter->list.next,
 					struct rwsem_waiter, list);
 
-	} while (waiter->flags & RWSEM_WAITING_FOR_READ);
+	} while (waiter->type != RWSEM_WAITING_FOR_WRITE);
 
 	adjustment = woken * RWSEM_ACTIVE_READ_BIAS;
-	if (waiter->flags & RWSEM_WAITING_FOR_READ)
+	if (waiter->type != RWSEM_WAITING_FOR_WRITE)
 		/* hit end of list above */
 		adjustment -= RWSEM_WAITING_BIAS;
 
@@ -171,7 +174,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type)
  */
 static struct rw_semaphore __sched *
 rwsem_down_failed_common(struct rw_semaphore *sem,
-			 unsigned int flags, signed long adjustment)
+			 enum rwsem_waiter_type type, signed long adjustment)
 {
 	struct rwsem_waiter waiter;
 	struct task_struct *tsk = current;
@@ -182,7 +185,7 @@ rwsem_down_failed_common(struct rw_semaphore *sem,
 	/* set up my own style of waitqueue */
 	raw_spin_lock_irq(&sem->wait_lock);
 	waiter.task = tsk;
-	waiter.flags = flags;
+	waiter.type = type;
 	get_task_struct(tsk);
 
 	if (list_empty(&sem->wait_list))
Signature · 1 line
1.8.1
#2 lore raw

PATCH 2/4 rwsem: shorter spinlocked section in rwsem_down_failed_common()

In reply to Michel Lespinasse

This change reduces the size of the spinlocked and TASK_UNINTERRUPTIBLE sections in rwsem_down_failed_common():

- We only need the sem->wait_lock to insert ourselves on the wait_list; the waiter node can be prepared outside of the wait_lock.

- The task state only needs to be set to TASK_UNINTERRUPTIBLE immediately before testing waiter.task to see if someone woke us; it doesn't need to protect the entire function.

---
 lib/rwsem.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
lib/rwsem.c +3 -5
index 4a6ff093a433..cd2d803cbbe4 100644
@@ -180,14 +180,12 @@ rwsem_down_failed_common(struct rw_semaphore *sem,
 	struct task_struct *tsk = current;
 	signed long count;
 
-	set_task_state(tsk, TASK_UNINTERRUPTIBLE);
-
 	/* set up my own style of waitqueue */
-	raw_spin_lock_irq(&sem->wait_lock);
 	waiter.task = tsk;
 	waiter.type = type;
 	get_task_struct(tsk);
 
+	raw_spin_lock_irq(&sem->wait_lock);
 	if (list_empty(&sem->wait_list))
 		adjustment += RWSEM_WAITING_BIAS;
 	list_add_tail(&waiter.list, &sem->wait_list);
@@ -210,11 +208,11 @@ rwsem_down_failed_common(struct rw_semaphore *sem,
 	raw_spin_unlock_irq(&sem->wait_lock);
 
 	/* wait to be given the lock */
-	for (;;) {
+	while (true) {
+		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 		if (!waiter.task)
 			break;
 		schedule();
-		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}
 
 	tsk->state = TASK_RUNNING;
Signature · 1 line
1.8.1
#3 lore raw

PATCH 3/4 rwsem: implement write lock stealing

In reply to Michel Lespinasse

Add support for write lock stealing in the generic rwsem code.

rwsem_down_write_failed() is similar to rwsem_down_read_failed(), with a few significant differences:

- The waiter doesn't try waking blocked threads if there are no active lockers - it just steals the lock in that case.

- The waiter doesn't get removed from the wait_list upon wakeup, and doesn't get a lock grant either. Therefore, it has to attempt stealing the lock before sleeping (if it fails, then it is safe to sleep as the active locker will be responsible of waking it up) and it has to dequeue itself after successfully acquiring the lock. For simplicity, I moved the attempt at stealing the lock within the sem wait_lock, so that we can know at that time if we are the last waiter.

- There is no need to get a reference on the task structure, since the task is responsible for removing itself from the wait_list. There is no risk, like in the rwsem_down_read_failed() case, that a task would wake up and exit (thus destroying its task structure) while __rwsem_do_wake() is still running - wait_lock protects against that.

The __rwsem_do_wake() funciton is also largely rewritten to account for the new requirements:

- The code to wake writers is simplified, as it doesn't need to grant them the lock (and deal with the possible case where another active locker might have appeared)

- The code to wake readers can't just check that there are no writers at the start of the operation and assume that this will still be true later, since writers might steal the lock until the first reader lock is granted. One option could be to grant the first reader lock, then count additional readers at the head of the queue, grant them extra readers locks if any, and finally wake all these readers. However, this gets a bit complex. Instead, I implemented a simpler alternative where we maintain a count of queued readers. This allows us to grant as many reader locks as necessary at the start of the operation, and then wake all these readers (regardless of their position in the queue).

---
 include/linux/rwsem.h |   2 +
 lib/rwsem.c           | 235 +++++++++++++++++++++++---------------------------
 2 files changed, 109 insertions(+), 128 deletions(-)
include/linux/rwsem.h +2 -0
index 8da67d625e13..be6f9649512d 100644
@@ -25,6 +25,7 @@ struct rw_semaphore;
 struct rw_semaphore {
 	long			count;
 	raw_spinlock_t		wait_lock;
+	unsigned int		wait_readers;
 	struct list_head	wait_list;
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map	dep_map;
@@ -58,6 +59,7 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 #define __RWSEM_INITIALIZER(name)			\
 	{ RWSEM_UNLOCKED_VALUE,				\
 	  __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock),	\
+	  0,						\
 	  LIST_HEAD_INIT((name).wait_list)		\
 	  __RWSEM_DEP_MAP_INIT(name) }
 
lib/rwsem.c +107 -128

295 lines not on this page · raw message

Signature · 1 line
1.8.1
#4 lore raw

Re: [PATCH 3/4] rwsem: implement write lock stealing

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) · line 106

Quoted 11 lines · Michel Lespinasse
lib/rwsem.c +11 -0
+               if (waiter->type != RWSEM_WAITING_FOR_WRITE) {
+                       list_del(&waiter->list);
+
+                       /* Set RWSEM_WAITING_BIAS before waking the last reader
+                        * so we know there will be a remaining active locker.
+                        */
+                       if (!(--readers) && !list_empty(&sem->wait_list))
+                               rwsem_atomic_add(RWSEM_WAITING_BIAS, sem);
+
+                       tsk = waiter->task;
+                       smp_mb();

For what with mb?

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int wake_type)

Quoted 9 lines
lib/rwsem.c +7 -0
+                       waiter->task = NULL;
+                       wake_up_process(tsk);
+                       put_task_struct(tsk);
+               }
+       } while (readers);
+       sem->wait_readers = 0;
 
 
+       /* If there are no active locks, wake the front queued process(es). */

s/locks/lockers/

Quoted 2 lines
lib/rwsem.c +2 -0
+       if (!(count & RWSEM_ACTIVE_MASK))
+               sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
#5 lore raw

Re: [PATCH 3/4] rwsem: implement write lock stealing

Quoted 14 lines · Hillf Danton

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) · line 106

Quoted 11 lines · Michel Lespinasse
lib/rwsem.c +11 -0
+               if (waiter->type != RWSEM_WAITING_FOR_WRITE) {
+                       list_del(&waiter->list);
+
+                       /* Set RWSEM_WAITING_BIAS before waking the last reader
+                        * so we know there will be a remaining active locker.
+                        */
+                       if (!(--readers) && !list_empty(&sem->wait_list))
+                               rwsem_atomic_add(RWSEM_WAITING_BIAS, sem);
+
+                       tsk = waiter->task;
+                       smp_mb();

For what with mb?

This is the same mb that used to be before the readers_only label before this change.
The intention is that the write to waiter->task must be the last access to waiter - after that, the reader is granted the lock so it could do anything, including deallocating the waiter structure as it gets out of rwsem_down_read_failed() and possibly deallocating the task structure if it exits

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#6 lore raw

Re: [PATCH 3/4] rwsem: implement write lock stealing

Quoted 16 lines · Michel Lespinasse
Quoted 14 lines · Hillf Danton

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) · line 106

Quoted 11 lines · Michel Lespinasse
lib/rwsem.c +11 -0
+               if (waiter->type != RWSEM_WAITING_FOR_WRITE) {
+                       list_del(&waiter->list);
+
+                       /* Set RWSEM_WAITING_BIAS before waking the last reader
+                        * so we know there will be a remaining active locker.
+                        */
+                       if (!(--readers) && !list_empty(&sem->wait_list))
+                               rwsem_atomic_add(RWSEM_WAITING_BIAS, sem);
+
+                       tsk = waiter->task;
+                       smp_mb();

For what with mb?

Quoted 8 lines

This is the same mb that used to be before the readers_only label before this change.
The intention is that the write to waiter->task must be the last access to waiter - after that, the reader is granted the lock so it could do anything, including deallocating the waiter structure as it gets out of rwsem_down_read_failed() and possibly deallocating the task structure if it exits

Perhaps the waiting process needs to see if no more wait needed,

	/* wait to be given the lock */
	for (;;) {
		if (!waiter.task)
			break;
		schedule();
		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
	}

and another mb do exist at the beginning of try_to_wake_up().

And I want to change
+ /* Block until there are no active lockers. */
+ do {
+ schedule();
+ set_task_state(tsk, TASK_UNINTERRUPTIBLE);
+ } while (sem->count & RWSEM_ACTIVE_MASK);

to

	/* Block until there are no active lockers. */
	while (sem->count & RWSEM_ACTIVE_MASK) {
		schedule();
		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
	}

for sure that we have to wait.

#7 lore raw

PATCH 4/4 x86 rwsem: avoid taking slow path when stealing write lock

In reply to Michel Lespinasse

modify __down_write[_nested] and __down_write_trylock to grab the write lock whenever the active count is 0, even if there are queued waiters (they must be writers pending wakeup, since the active count is 0).

Note that this is an optimization only; architectures without this optimization will still work fine:

- __down_write() would take the slow path which would take the wait_lock and then try stealing the lock (as in the spinlocked rwsem implementation)

- __down_write_trylock() would fail, but callers must be ready to deal with that - since there are some writers pending wakeup, they could have raced with us and obtained the lock before we steal it.

---
 arch/x86/include/asm/rwsem.h | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)
arch/x86/include/asm/rwsem.h +21 -7
index 2dbe4a721ce5..cad82c9c2fde 100644
@@ -105,8 +105,8 @@ static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
 	asm volatile("# beginning down_write\n\t"
 		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
 		     /* adds 0xffff0001, returns the old value */
-		     "  test      %1,%1\n\t"
-		     /* was the count 0 before? */
+		     "  test " __ASM_SEL(%w1,%k1) "," __ASM_SEL(%w1,%k1) "\n\t"
+		     /* was the active mask 0 before? */
 		     "  jz        1f\n"
 		     "  call call_rwsem_down_write_failed\n"
 		     "1:\n"
@@ -126,11 +126,25 @@ static inline void __down_write(struct rw_semaphore *sem)
  */
 static inline int __down_write_trylock(struct rw_semaphore *sem)
 {
-	long ret = cmpxchg(&sem->count, RWSEM_UNLOCKED_VALUE,
-			   RWSEM_ACTIVE_WRITE_BIAS);
-	if (ret == RWSEM_UNLOCKED_VALUE)
-		return 1;
-	return 0;
+	long result, tmp;
+	asm volatile("# beginning __down_write_trylock\n\t"
+		     "  mov          %0,%1\n\t"
+		     "1:\n\t"
+		     "  test " __ASM_SEL(%w1,%k1) "," __ASM_SEL(%w1,%k1) "\n\t"
+		     /* was the active mask 0 before? */
+		     "  jnz          2f\n\t"
+		     "  mov          %1,%2\n\t"
+		     "  add          %3,%2\n\t"
+		     LOCK_PREFIX "  cmpxchg  %2,%0\n\t"
+		     "  jnz	     1b\n\t"
+		     "2:\n\t"
+		     "  sete         %b1\n\t"
+		     "  movzbl       %b1, %k1\n\t"
+		     "# ending __down_write_trylock\n\t"
+		     : "+m" (sem->count), "=&a" (result), "=&r" (tmp)
+		     : "er" (RWSEM_ACTIVE_WRITE_BIAS)
+		     : "memory", "cc");
+	return result;
 }
 
 /*
Signature · 1 line
1.8.1
#8 lore raw
In reply to Michel Lespinasse
Quoted 2 lines · Michel Lespinasse

This proposal implements writer lock stealing in lib/rwsem.c, just as Alex Shi's earlier proposal did for the simpler lib/rwsem-spinlock.c

Ops, my patch in tip/urgent is for rwsem. Yuanhan's patch is for rwsem-spinlock.

Thanks
Alex

#9 lore raw
Quoted 6 lines · Alex Shi
Quoted 2 lines · Michel Lespinasse

This proposal implements writer lock stealing in lib/rwsem.c, just as Alex Shi's earlier proposal did for the simpler lib/rwsem-spinlock.c

Ops, my patch in tip/urgent is for rwsem. Yuanhan's patch is for rwsem-spinlock.

Your rwsem patch is queued up for v3.9, in the tip:core/locking tree:

3a15e0e0cdda rwsem: Implement writer lock-stealing for better scalability

Michel, mind having a look at that and possibly generate a delta patch, if your patch has changes we should apply?

Thanks,

Ingo

#10 lore raw
Quoted 9 lines · Ingo Molnar
Quoted 6 lines · Alex Shi
Quoted 2 lines · Michel Lespinasse

This proposal implements writer lock stealing in lib/rwsem.c, just as Alex Shi's earlier proposal did for the simpler lib/rwsem-spinlock.c

Ops, my patch in tip/urgent is for rwsem. Yuanhan's patch is for rwsem-spinlock.

Sorry, my bad. Looks like an email snafu on my side - when I wanted to save your patch to look through it with more context, I ended up saving Yuanhan's instead.

Quoted 7 lines

Your rwsem patch is queued up for v3.9, in the tip:core/locking tree:

3a15e0e0cdda rwsem: Implement writer lock-stealing for better scalability

Michel, mind having a look at that and possibly generate a delta patch, if your patch has changes we should apply?

The main difference I can see is that my approach makes it possible to steal the rwsem in a fast path, without going through the lib/rwsem.c slow path. A few things fall out from that; most notably I had to change the readers_only side of __rwsem_do_wake() to account with the possibility of write lock stealing on the fast path, while Alex doesn't since he forces write lock stealing to use the slow path. Overall, my changes are more extensive but they also reduce the total line count, while Alex's proposal goes the other way.

For these reasons, I think I still prefer my approach. However as mentioned, this is not the best time for me to push it as I'll be away for a little while. I should be able to get back to this in a couple weeks, though.

Alex, could you go through my patch and see if there is anything you find objectionable ? (if not about the details, at least about the general approach of enabling writer lock stealing on the fast path)

Thanks,

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#11 lore raw
Quoted 3 lines · Michel Lespinasse

Alex, could you go through my patch and see if there is anything you find objectionable ? (if not about the details, at least about the general approach of enabling writer lock stealing on the fast path)

I am still in my lunar new year vacation. I may do a aim7 test for you after back to office.
But as to fast path stealing, I didn't see extra benefit on fast path.

Signature · 2 lines
Thanks
    Alex
#12 lore raw
In reply to Michel Lespinasse
Quoted 6 lines

Alex, could you go through my patch and see if there is anything you find objectionable ? (if not about the details, at least about the general approach of enabling writer lock stealing on the fast path)

I did a quick review on the patchset and tested the patches 1~3, and 1~3 plus 4th, my patch plus 4th.

The patch looks much complicated, and also goes writing slow path to steal locking. My patch looks quite straight and simple.

This 1~3 patch has very very similar performance effect with mine.

The highlight patch is the 4th, seems it can provide about ~2% aim7 performance gain(base on both of mine or patches 1~3) on my 4S NHM EX machine.

Signature · 1 line
Thanks Alex
#13 lore raw
Quoted 12 lines · Alex Shi
Quoted 4 lines

Alex, could you go through my patch and see if there is anything you find objectionable ? (if not about the details, at least about the general approach of enabling writer lock stealing on the fast path)

I did a quick review on the patchset and tested the patches 1~3, and 1~3 plus 4th, my patch plus 4th.

The patch looks much complicated, and also goes writing slow path to steal locking. My patch looks quite straight and simple.

Quoted 6 lines

This 1~3 patch has very very similar performance effect with mine.

The highlight patch is the 4th, seems it can provide about ~2% aim7 performance gain(base on both of mine or patches 1~3) on my 4S NHM EX machine.

That speedup would be nice to have.

Thanks,

Ingo

#14 lore raw
In reply to Alex Shi
Quoted 11 lines · Alex Shi

I did a quick review on the patchset and tested the patches 1~3, and 1~3 plus 4th, my patch plus 4th.

The patch looks much complicated, and also goes writing slow path to steal locking. My patch looks quite straight and simple.

This 1~3 patch has very very similar performance effect with mine.

The highlight patch is the 4th, seems it can provide about ~2% aim7 performance gain(base on both of mine or patches 1~3) on my 4S NHM EX machine.

Thanks for doing these measurements.

I think we can keep patches 1-2 out of this discussion as they don't have much complexity and don't have much to do with write stealing either.

Patch 4 is where fast path write stealing is implemented; however there are some parts of patch 3 that I think are required - the one I have in mind right now is when waking readers, the existing code assumes that writers can't get the lock while it counts how many reader locks need to be granted. There are several solutions to that - for example you could grant the first reader lock before counting how many more you need, but that would result in longer code than in my proposal. Either way, I believe if you go into fixing lib/rwsem.c to account for the possibility of fast path lock stealing you'll end up with something very similar to my proposed patch 3...

(This is kinda how I proceeded with this series, I wrote the fastpath lock stealing first, then I thought about what's required to support it in the slow path)

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.