Skip to contentSkip to conversation

rwsem-spinlock: let rwsem write lock stealable

PATCH Superseded Yuanhan Liu 3 participants 12 messages Jan 30, 2013 – Feb 1, 2013 Library code

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 rwsem-spinlock: let rwsem write lock stealable

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

With this patch, we got a double performance increase in one test box with following aim7 workfile:
FILESIZE: 1M
POOLSIZE: 10M
10 fork_test

some /usr/bin/time output w/o patch some /usr/bin/time_output with patch
----------------------------------------------------------------------------
Percent of CPU this job got: 369% Percent of CPU this job got: 537%
Voluntary context switches: 640595016 Voluntary context switches: 157915561
----------------------------------------------------------------------------
You will see we got a 45% increase of CPU usage and saves about 3/4 voluntary context switches.

Here is the .nr_running filed for all CPUs from /proc/sched_debug.

output w/o this patch:
----------------------

cpu 00:   0   0   ...   0   0   0   0   0   0   0   1   0   1 .... 0   0
cpu 01:   0   0   ...   1   0   0   0   0   0   1   1   0   1 .... 0   0
cpu 02:   0   0   ...   1   1   0   0   0   1   0   0   1   0 .... 1   1
cpu 03:   0   0   ...   0   1   0   0   0   1   1   0   1   1 .... 0   0
cpu 04:   0   1   ...   0   0   2   1   1   2   1   0   1   0 .... 1   0
cpu 05:   0   1   ...   0   0   2   1   1   2   1   1   1   1 .... 0   0
cpu 06:   0   0   ...   2   0   0   1   0   0   1   0   0   0 .... 0   0
cpu 07:   0   0   ...   2   0   0   0   1   0   1   1   0   0 .... 1   0
cpu 08:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 09:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 10:   0   0   ...   0   0   0   2   0   0   1   0   1   1 .... 1   2
cpu 11:   0   0   ...   0   0   0   2   2   0   1   0   1   0 .... 1   2
cpu 12:   0   0   ...   2   0   0   0   1   1   3   1   1   1 .... 1   0
cpu 13:   0   0   ...   2   0   0   0   1   1   3   1   1   0 .... 1   1
cpu 14:   0   0   ...   0   0   0   2   0   0   1   1   0   0 .... 1   0
cpu 15:   0   0   ...   1   0   0   2   0   0   1   1   0   0 .... 0   0

output with this patch:
-----------------------

cpu 00:   0   0   ...   1   1   2   1   1   1   2   1   1   1 .... 1   3
cpu 01:   0   0   ...   1   1   1   1   1   1   2   1   1   1 .... 1   3
cpu 02:   0   0   ...   2   2   3   2   0   2   1   2   1   1 .... 1   1
cpu 03:   0   0   ...   2   2   3   2   1   2   1   2   1   1 .... 1   1
cpu 04:   0   1   ...   2   0   0   1   0   1   3   1   1   1 .... 1   1
cpu 05:   0   1   ...   2   0   1   1   0   1   2   1   1   1 .... 1   1
cpu 06:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 07:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 08:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 09:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 10:   0   0   ...   1   1   1   0   0   1   1   1   1   1 .... 0   0
cpu 11:   0   0   ...   1   1   1   0   0   1   1   1   1   2 .... 1   0
cpu 12:   0   0   ...   1   1   1   0   1   1   0   0   0   1 .... 2   1
cpu 13:   0   0   ...   1   1   1   0   1   1   1   0   1   2 .... 2   0
cpu 14:   0   0   ...   2   0   0   0   0   1   1   1   1   1 .... 2   2
cpu 15:   0   0   ...   2   0   0   1   0   1   1   1   1   1 .... 2   2

------------------------------------------------------------------------
Where you can see that CPU is much busier with this patch.

---
 lib/rwsem-spinlock.c |   65 +++++++++++++++++---------------------------------
 1 files changed, 22 insertions(+), 43 deletions(-)
lib/rwsem-spinlock.c +22 -43
index 7e0d6a5..a32b85e 100644
@@ -73,20 +73,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
 		goto dont_wake_writers;
 	}
 
-	/* if we are allowed to wake writers try to grant a single write lock
-	 * if there's a writer at the front of the queue
-	 * - we leave the 'waiting count' incremented to signify potential
-	 *   contention
+	/*
+	 * as we support write lock stealing, we can't set sem->activity
+	 * to -1 here to indicate we get the lock. Instead, we wake it up
+	 * to let it go get it again.
 	 */
 	if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
-		sem->activity = -1;
-		list_del(&waiter->list);
-		tsk = waiter->task;
-		/* Don't touch waiter after ->task has been NULLed */
-		smp_mb();
-		waiter->task = NULL;
-		wake_up_process(tsk);
-		put_task_struct(tsk);
+		wake_up_process(waiter->task);
 		goto out;
 	}
 
@@ -121,18 +114,10 @@ static inline struct rw_semaphore *
 __rwsem_wake_one_writer(struct rw_semaphore *sem)
 {
 	struct rwsem_waiter *waiter;
-	struct task_struct *tsk;
-
-	sem->activity = -1;
 
 	waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
-	list_del(&waiter->list);
+	wake_up_process(waiter->task);
 
-	tsk = waiter->task;
-	smp_mb();
-	waiter->task = NULL;
-	wake_up_process(tsk);
-	put_task_struct(tsk);
 	return sem;
 }
 
@@ -204,7 +189,6 @@ int __down_read_trylock(struct rw_semaphore *sem)
 
 /*
  * get a write lock on the semaphore
- * - we increment the waiting count anyway to indicate an exclusive lock
  */
 void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
 {
@@ -214,37 +198,32 @@ void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
 
 	raw_spin_lock_irqsave(&sem->wait_lock, flags);
 
-	if (sem->activity == 0 && list_empty(&sem->wait_list)) {
-		/* granted */
-		sem->activity = -1;
-		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
-		goto out;
-	}
-
-	tsk = current;
-	set_task_state(tsk, TASK_UNINTERRUPTIBLE);
-
 	/* set up my own style of waitqueue */
+	tsk = current;
 	waiter.task = tsk;
 	waiter.flags = RWSEM_WAITING_FOR_WRITE;
-	get_task_struct(tsk);
-
 	list_add_tail(&waiter.list, &sem->wait_list);
 
-	/* we don't need to touch the semaphore struct anymore */
-	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
-
-	/* wait to be given the lock */
+	/* wait for someone to release the lock */
 	for (;;) {
-		if (!waiter.task)
+		/*
+		 * That is the key to support write lock stealing: allows the
+		 * task already on CPU to get the lock soon rather than put
+		 * itself into sleep and waiting for system woke it or someone
+		 * else in the head of the wait list up.
+		 */
+		if (sem->activity == 0)
 			break;
-		schedule();
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
+		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
+		schedule();
+		raw_spin_lock_irqsave(&sem->wait_lock, flags);
 	}
+	/* got the lock */
+	sem->activity = -1;
+	list_del(&waiter.list);
 
-	tsk->state = TASK_RUNNING;
- out:
-	;
+	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 }
 
 void __sched __down_write(struct rw_semaphore *sem)
Signature · 1 line
1.7.7.6
#1 lore raw
Quoted 71 lines · Yuanhan Liu

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

With this patch, we got a double performance increase in one test box with following aim7 workfile:
FILESIZE: 1M
POOLSIZE: 10M
10 fork_test

some /usr/bin/time output w/o patch some /usr/bin/time_output with patch
----------------------------------------------------------------------------
Percent of CPU this job got: 369% Percent of CPU this job got: 537%
Voluntary context switches: 640595016 Voluntary context switches: 157915561
----------------------------------------------------------------------------
You will see we got a 45% increase of CPU usage and saves about 3/4 voluntary context switches.

Here is the .nr_running filed for all CPUs from /proc/sched_debug.

output w/o this patch:
----------------------

cpu 00:   0   0   ...   0   0   0   0   0   0   0   1   0   1 .... 0   0
cpu 01:   0   0   ...   1   0   0   0   0   0   1   1   0   1 .... 0   0
cpu 02:   0   0   ...   1   1   0   0   0   1   0   0   1   0 .... 1   1
cpu 03:   0   0   ...   0   1   0   0   0   1   1   0   1   1 .... 0   0
cpu 04:   0   1   ...   0   0   2   1   1   2   1   0   1   0 .... 1   0
cpu 05:   0   1   ...   0   0   2   1   1   2   1   1   1   1 .... 0   0
cpu 06:   0   0   ...   2   0   0   1   0   0   1   0   0   0 .... 0   0
cpu 07:   0   0   ...   2   0   0   0   1   0   1   1   0   0 .... 1   0
cpu 08:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 09:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 10:   0   0   ...   0   0   0   2   0   0   1   0   1   1 .... 1   2
cpu 11:   0   0   ...   0   0   0   2   2   0   1   0   1   0 .... 1   2
cpu 12:   0   0   ...   2   0   0   0   1   1   3   1   1   1 .... 1   0
cpu 13:   0   0   ...   2   0   0   0   1   1   3   1   1   0 .... 1   1
cpu 14:   0   0   ...   0   0   0   2   0   0   1   1   0   0 .... 1   0
cpu 15:   0   0   ...   1   0   0   2   0   0   1   1   0   0 .... 0   0

output with this patch:
-----------------------

cpu 00:   0   0   ...   1   1   2   1   1   1   2   1   1   1 .... 1   3
cpu 01:   0   0   ...   1   1   1   1   1   1   2   1   1   1 .... 1   3
cpu 02:   0   0   ...   2   2   3   2   0   2   1   2   1   1 .... 1   1
cpu 03:   0   0   ...   2   2   3   2   1   2   1   2   1   1 .... 1   1
cpu 04:   0   1   ...   2   0   0   1   0   1   3   1   1   1 .... 1   1
cpu 05:   0   1   ...   2   0   1   1   0   1   2   1   1   1 .... 1   1
cpu 06:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 07:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 08:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 09:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 10:   0   0   ...   1   1   1   0   0   1   1   1   1   1 .... 0   0
cpu 11:   0   0   ...   1   1   1   0   0   1   1   1   1   2 .... 1   0
cpu 12:   0   0   ...   1   1   1   0   1   1   0   0   0   1 .... 2   1
cpu 13:   0   0   ...   1   1   1   0   1   1   1   0   1   2 .... 2   0
cpu 14:   0   0   ...   2   0   0   0   0   1   1   1   1   1 .... 2   2
cpu 15:   0   0   ...   2   0   0   1   0   1   1   1   1   1 .... 2   2
Quoted 2 lines

------------------------------------------------------------------------
Where you can see that CPU is much busier with this patch.

That looks really good - quite similar to how it behaved with mutexes, right?

Does this recover most of the performance regression?

Thanks,

Ingo

#2 lore raw
Quoted 77 lines · Ingo Molnar
Quoted 71 lines · Yuanhan Liu

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

With this patch, we got a double performance increase in one test box with following aim7 workfile:
FILESIZE: 1M
POOLSIZE: 10M
10 fork_test

some /usr/bin/time output w/o patch some /usr/bin/time_output with patch
----------------------------------------------------------------------------
Percent of CPU this job got: 369% Percent of CPU this job got: 537%
Voluntary context switches: 640595016 Voluntary context switches: 157915561
----------------------------------------------------------------------------
You will see we got a 45% increase of CPU usage and saves about 3/4 voluntary context switches.

Here is the .nr_running filed for all CPUs from /proc/sched_debug.

output w/o this patch:
----------------------

cpu 00:   0   0   ...   0   0   0   0   0   0   0   1   0   1 .... 0   0
cpu 01:   0   0   ...   1   0   0   0   0   0   1   1   0   1 .... 0   0
cpu 02:   0   0   ...   1   1   0   0   0   1   0   0   1   0 .... 1   1
cpu 03:   0   0   ...   0   1   0   0   0   1   1   0   1   1 .... 0   0
cpu 04:   0   1   ...   0   0   2   1   1   2   1   0   1   0 .... 1   0
cpu 05:   0   1   ...   0   0   2   1   1   2   1   1   1   1 .... 0   0
cpu 06:   0   0   ...   2   0   0   1   0   0   1   0   0   0 .... 0   0
cpu 07:   0   0   ...   2   0   0   0   1   0   1   1   0   0 .... 1   0
cpu 08:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 09:   0   0   ...   1   0   0   0   1   0   0   1   0   0 .... 0   1
cpu 10:   0   0   ...   0   0   0   2   0   0   1   0   1   1 .... 1   2
cpu 11:   0   0   ...   0   0   0   2   2   0   1   0   1   0 .... 1   2
cpu 12:   0   0   ...   2   0   0   0   1   1   3   1   1   1 .... 1   0
cpu 13:   0   0   ...   2   0   0   0   1   1   3   1   1   0 .... 1   1
cpu 14:   0   0   ...   0   0   0   2   0   0   1   1   0   0 .... 1   0
cpu 15:   0   0   ...   1   0   0   2   0   0   1   1   0   0 .... 0   0

output with this patch:
-----------------------

cpu 00:   0   0   ...   1   1   2   1   1   1   2   1   1   1 .... 1   3
cpu 01:   0   0   ...   1   1   1   1   1   1   2   1   1   1 .... 1   3
cpu 02:   0   0   ...   2   2   3   2   0   2   1   2   1   1 .... 1   1
cpu 03:   0   0   ...   2   2   3   2   1   2   1   2   1   1 .... 1   1
cpu 04:   0   1   ...   2   0   0   1   0   1   3   1   1   1 .... 1   1
cpu 05:   0   1   ...   2   0   1   1   0   1   2   1   1   1 .... 1   1
cpu 06:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 07:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 08:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 09:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 10:   0   0   ...   1   1   1   0   0   1   1   1   1   1 .... 0   0
cpu 11:   0   0   ...   1   1   1   0   0   1   1   1   1   2 .... 1   0
cpu 12:   0   0   ...   1   1   1   0   1   1   0   0   0   1 .... 2   1
cpu 13:   0   0   ...   1   1   1   0   1   1   1   0   1   2 .... 2   0
cpu 14:   0   0   ...   2   0   0   0   0   1   1   1   1   1 .... 2   2
cpu 15:   0   0   ...   2   0   0   1   0   1   1   1   1   1 .... 2   2
Quoted 2 lines

------------------------------------------------------------------------
Where you can see that CPU is much busier with this patch.

Quoted 2 lines

That looks really good - quite similar to how it behaved with mutexes, right?

Yes :)

And the result is almost same with mutex lock when MUTEX_SPIN_ON_OWNER is disabled, and that's the reason you will see massive processes(about
100) queued on each CPU in my last report:

    https://lkml.org/lkml/2013/1/29/84
Quoted 2 lines

Does this recover most of the performance regression?

Yes, there is only a 10% gap here then. I guess that's because I used the general rwsem lock implementation(lib/rwsem-spinlock.c), but not the XADD one(lib/rwsem.c). I guess the gap may be a little smaller if we do the same thing to lib/rwsem.c.

Thanks.

	--yliu
#3 lore raw
Quoted 24 lines · Yuanhan Liu
Quoted 21 lines
Quoted 18 lines

output with this patch:
-----------------------

cpu 00:   0   0   ...   1   1   2   1   1   1   2   1   1   1 .... 1   3
cpu 01:   0   0   ...   1   1   1   1   1   1   2   1   1   1 .... 1   3
cpu 02:   0   0   ...   2   2   3   2   0   2   1   2   1   1 .... 1   1
cpu 03:   0   0   ...   2   2   3   2   1   2   1   2   1   1 .... 1   1
cpu 04:   0   1   ...   2   0   0   1   0   1   3   1   1   1 .... 1   1
cpu 05:   0   1   ...   2   0   1   1   0   1   2   1   1   1 .... 1   1
cpu 06:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 07:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 08:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 09:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 10:   0   0   ...   1   1   1   0   0   1   1   1   1   1 .... 0   0
cpu 11:   0   0   ...   1   1   1   0   0   1   1   1   1   2 .... 1   0
cpu 12:   0   0   ...   1   1   1   0   1   1   0   0   0   1 .... 2   1
cpu 13:   0   0   ...   1   1   1   0   1   1   1   0   1   2 .... 2   0
cpu 14:   0   0   ...   2   0   0   0   0   1   1   1   1   1 .... 2   2
cpu 15:   0   0   ...   2   0   0   1   0   1   1   1   1   1 .... 2   2
Quoted 2 lines

------------------------------------------------------------------------
Where you can see that CPU is much busier with this patch.

Quoted 2 lines

That looks really good - quite similar to how it behaved with mutexes, right?

Quoted 6 lines

Yes :)

And the result is almost same with mutex lock when MUTEX_SPIN_ON_OWNER is disabled, and that's the reason you will see massive processes(about
100) queued on each CPU in my last report:

    https://lkml.org/lkml/2013/1/29/84

Just curious: how does MUTEX_SPIN_ON_OWNER versus !MUTEX_SPIN_ON_OWNER compare, for this particular, massively-contended anon-vma locks benchmark?

Quoted 7 lines
Quoted 1 line

Does this recover most of the performance regression?

Yes, there is only a 10% gap here then. I guess that's because I used the general rwsem lock implementation(lib/rwsem-spinlock.c), but not the XADD one(lib/rwsem.c). I guess the gap may be a little smaller if we do the same thing to lib/rwsem.c.

Is part of the gap due to MUTEX_SPIN_ON_OWNER perhaps?

I'm surprised that rwsem-spinlock versus rwsem.c would show a 10% performance difference - assuming you have lock debugging/tracing disabled in the .config.

( Once the performance regression is fixed, another thing to
check would be to reduce anon-vma lock contention. )

Thanks,

Ingo

#4 lore raw
Quoted 29 lines · Ingo Molnar
Quoted 26 lines · Yuanhan Liu
Quoted 21 lines
Quoted 18 lines

output with this patch:
-----------------------

cpu 00:   0   0   ...   1   1   2   1   1   1   2   1   1   1 .... 1   3
cpu 01:   0   0   ...   1   1   1   1   1   1   2   1   1   1 .... 1   3
cpu 02:   0   0   ...   2   2   3   2   0   2   1   2   1   1 .... 1   1
cpu 03:   0   0   ...   2   2   3   2   1   2   1   2   1   1 .... 1   1
cpu 04:   0   1   ...   2   0   0   1   0   1   3   1   1   1 .... 1   1
cpu 05:   0   1   ...   2   0   1   1   0   1   2   1   1   1 .... 1   1
cpu 06:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 07:   0   0   ...   2   1   1   2   0   1   2   1   1   1 .... 2   1
cpu 08:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 09:   0   0   ...   1   1   1   1   1   1   1   1   1   1 .... 0   0
cpu 10:   0   0   ...   1   1   1   0   0   1   1   1   1   1 .... 0   0
cpu 11:   0   0   ...   1   1   1   0   0   1   1   1   1   2 .... 1   0
cpu 12:   0   0   ...   1   1   1   0   1   1   0   0   0   1 .... 2   1
cpu 13:   0   0   ...   1   1   1   0   1   1   1   0   1   2 .... 2   0
cpu 14:   0   0   ...   2   0   0   0   0   1   1   1   1   1 .... 2   2
cpu 15:   0   0   ...   2   0   0   1   0   1   1   1   1   1 .... 2   2
Quoted 2 lines

------------------------------------------------------------------------
Where you can see that CPU is much busier with this patch.

Quoted 2 lines

That looks really good - quite similar to how it behaved with mutexes, right?

Yes :)

Quoted 8 lines
Quoted 4 lines

And the result is almost same with mutex lock when MUTEX_SPIN_ON_OWNER is disabled, and that's the reason you will see massive processes(about
100) queued on each CPU in my last report:

    https://lkml.org/lkml/2013/1/29/84

Just curious: how does MUTEX_SPIN_ON_OWNER versus !MUTEX_SPIN_ON_OWNER compare, for this particular, massively-contended anon-vma locks benchmark?

In above testcase, MUTEX_SPIN_ON_OWNER is slightly doing better job(like 3% ~ 4%) than !MUTEX_SPIN_ON_OWNER.

Quoted 4 lines
Quoted 4 lines
Quoted 2 lines

Does this recover most of the performance regression?

Yes, there is only a 10% gap here then. I guess that's because

Sorry, to be accurate, it's about 14% gap; when MUTEX_SPIN_ON_OWNER is enabled.

Quoted 6 lines
Quoted 4 lines

I used the general rwsem lock implementation(lib/rwsem-spinlock.c), but not the XADD one(lib/rwsem.c). I guess the gap may be a little smaller if we do the same thing to lib/rwsem.c.

Is part of the gap due to MUTEX_SPIN_ON_OWNER perhaps?

Nope, !MUTEX_SPIN_ON_OWNER does introduce a little performance drop just as above stated.

So, to make it clear, here is the list:

lock case performance drop compared to mutex lock
----------------------------------------------------------------------------

mutex lock w/o MUTEX_SPIN_ON_OWNER   3.x%
rwsem-spinlock with write stealing   14.x%
rwsem-spinlock                       >100%
Quoted 3 lines

I'm surprised that rwsem-spinlock versus rwsem.c would show a 10% performance difference -

Yes, it may not. And there is only about 0.9% performance difference in above test between rwsem-spinlock and XADD rwsem. The difference maybe enlarged when both has write lock stealing enabled, which will be known only after we do same thing to lib/rwsem.c.

Thanks.

	--yliu
Quoted 9 lines

assuming you have lock
debugging/tracing disabled in the .config.

( Once the performance regression is fixed, another thing to
check would be to reduce anon-vma lock contention. )

Thanks,

Ingo

#5 lore raw
In reply to Yuanhan Liu
Quoted 12 lines · Yuanhan Liu

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

Quoted 4 lines

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

I noticed that you haven't modified __down_write_trylock() - for consistency with __down_write() you should replace

        if (sem->activity == 0 && list_empty(&sem->wait_list)) {
with
        if (sem->activity == 0) {

Other than that, I like the idea. I was originally uncomfortable with doing lock stealing for the rwsem, but I think doing it for writers only as you propose should be fine. Readers wait for any queued writers, and in exchange they are guaranteed to get the lock once they've blocked. You *still* want to check for regressions that this change might cause - not with anon_vma as this was a mutex not long ago, but possibly with mmap_sem - but I'm crossing my fingers and thinking that it'll most likely turn out fine.

I may be able to help with the non-spinlock version of this as I still remember how this works.

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

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

Quoted 4 lines

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

Quoted 5 lines

I noticed that you haven't modified __down_write_trylock() - for consistency with __down_write() you should replace

        if (sem->activity == 0 && list_empty(&sem->wait_list)) {
with
        if (sem->activity == 0) {

Yes, my bad for missing that. Thanks a lot for pointing it out. Will fix it.

Quoted 10 lines

Other than that, I like the idea. I was originally uncomfortable with doing lock stealing for the rwsem, but I think doing it for writers only as you propose should be fine. Readers wait for any queued writers, and in exchange they are guaranteed to get the lock once they've blocked.

You *still* want to check for regressions that this change might cause - not with anon_vma as this was a mutex not long ago, but possibly with mmap_sem

Yes. Well, at least it passed Fengguang's 0-DAY test, which did lots of tests on almost all ARCHs. Well, you reminds me that I just enabled RWSEM_GENERIC_SPINLOCK for x86 ARCH, thus I need to enable RWSEM_GENERIC_SPINLOCK to all ARCHs and do test again.

BTW, mind to tell a nice test case for mmap_sem?

Quoted 2 lines

- but I'm crossing my fingers and
thinking that it'll most likely turn out fine.

Thanks!

Quoted 3 lines

I may be able to help with the non-spinlock version of this as I still remember how this works.

That would be great! Especially I will have vacation soon for Chinese New Year.

	--yliu
#8 lore raw
Quoted 9 lines · Ingo Molnar
Quoted 1 line · Yuanhan Liu

BTW, mind to tell a nice test case for mmap_sem?

this one was write-hitting on mmap_sem pretty hard, last I checked:

http://people.redhat.com/mingo/threaded-mmap-stresstest/

Thanks!

Is there any pass condition? I tested a while, at least I found no oops or any noisy from dmesg output. Is that OK?

Well, sometimes, it will quit peacefully. Sometimes it will not. ps -eo 'pid, state,wchan,comm' shows that it is sleeping at futex_wait_queue_me().

NOTE: this happens both with or w/o this patch. Thus it may not an issue introduced by this patch?

Thanks.

	--yliu
#9 lore raw
Quoted 9 lines · Yuanhan Liu
Quoted 8 lines · Ingo Molnar
Quoted 1 line · Yuanhan Liu

BTW, mind to tell a nice test case for mmap_sem?

this one was write-hitting on mmap_sem pretty hard, last I checked:

Quoted 6 lines
Quoted 1 line

http://people.redhat.com/mingo/threaded-mmap-stresstest/

Thanks!

Is there any pass condition? I tested a while, at least I found no oops or any noisy from dmesg output. Is that OK?

Yeah, not crashing and not hanging is the expected behavior.

Quoted 6 lines

Well, sometimes, it will quit peacefully. Sometimes it will not. ps -eo 'pid, state,wchan,comm' shows that it is sleeping at futex_wait_queue_me().

NOTE: this happens both with or w/o this patch. Thus it may not an issue introduced by this patch?

hm, that's unexpected - it's expected to loop infinitely. I have a newer version (attached) - is that exiting too?

Maybe this triggers spuriously:

if (!info->si_addr)
raise(SIGABRT); /* Allow GDB backtrace */

although then you should see the SIGABRT as an irregular exit IIRC.

Thanks,

Ingo

#10 lore raw
Quoted 12 lines · Ingo Molnar
Quoted 9 lines · Yuanhan Liu
Quoted 8 lines · Ingo Molnar
Quoted 1 line · Yuanhan Liu

BTW, mind to tell a nice test case for mmap_sem?

this one was write-hitting on mmap_sem pretty hard, last I checked:

Quoted 8 lines
Quoted 6 lines
Quoted 1 line

http://people.redhat.com/mingo/threaded-mmap-stresstest/

Thanks!

Is there any pass condition? I tested a while, at least I found no oops or any noisy from dmesg output. Is that OK?

Yeah, not crashing and not hanging is the expected behavior.

Good to know.

Quoted 9 lines
Quoted 7 lines

Well, sometimes, it will quit peacefully. Sometimes it will not. ps -eo 'pid, state,wchan,comm' shows that it is sleeping at futex_wait_queue_me().

NOTE: this happens both with or w/o this patch. Thus it may not an issue introduced by this patch?

hm, that's unexpected - it's expected to loop infinitely.

Reall sorry about that. My bad. I modify the code a bit: removed the two //, so that thread will exit after count > 1000000.

Sorry again :(

	--yliu
Quoted 14 lines

I have
a newer version (attached) - is that exiting too?

Maybe this triggers spuriously:

if (!info->si_addr)
raise(SIGABRT); /* Allow GDB backtrace */

although then you should see the SIGABRT as an irregular exit IIRC.

Thanks,

Ingo

#11 lore raw
In reply to Michel Lespinasse
Quoted 25 lines · Michel Lespinasse
Quoted 12 lines · Yuanhan Liu

We(Linux Kernel Performance project) found a regression introduced by commit 5a50508, which just convert all mutex lock to rwsem write lock. The semantics is same, but the results is quite huge in some cases. After investigation, we found the root cause: mutex support lock stealing. Here is the link for the detailed regression report:

    https://lkml.org/lkml/2013/1/29/84

Ingo suggests to add write lock stealing to rwsem as well:
"I think we should allow lock-steal between rwsem writers - that
will not hurt fairness as most rwsem fairness concerns relate to reader vs. writer fairness"

Quoted 4 lines

I then tried it with rwsem-spinlock first as I found it much easier to implement it than lib/rwsem.c. And here I sent out this patch first for comments. I'd try lib/rwsem.c later once the change to rwsem-spinlock is OK to you guys.

I noticed that you haven't modified __down_write_trylock() - for consistency with __down_write() you should replace

        if (sem->activity == 0 && list_empty(&sem->wait_list)) {
with
        if (sem->activity == 0) {
Quoted 9 lines

Other than that, I like the idea. I was originally uncomfortable with doing lock stealing for the rwsem, but I think doing it for writers only as you propose should be fine. Readers wait for any queued writers, and in exchange they are guaranteed to get the lock once they've blocked. You *still* want to check for regressions that this change might cause - not with anon_vma as this was a mutex not long ago, but possibly with mmap_sem - but I'm crossing my fingers and thinking that it'll most likely turn out fine.

My gut feeling, from having implemented lock stealing in a number of locking primitives in the past, is that writer lock-stealing will be a measurable win for mmap_sem as well.

Thanks,

Ingo