Merge branch 'rwsem-optimizations'

Merge rwsem optimizations from Michel Lespinasse:
 "These patches extend Alex Shi's work (which added write lock stealing
  on the rwsem slow path) in order to provide rwsem write lock stealing
  on the fast path (that is, without taking the rwsem's wait_lock).

  I have unfortunately been unable to push this through -next before due
  to Ingo Molnar / David Howells / Peter Zijlstra being busy with other
  things.  However, this has gotten some attention from Rik van Riel and
  Davidlohr Bueso who both commented that they felt this was ready for
  v3.10, and Ingo Molnar has said that he was OK with me pushing
  directly to you.  So, here goes :)

  Davidlohr got the following test results from pgbench running on a
  quad-core laptop:

    | db_size | clients  |  tps-vanilla   |   tps-rwsem  |
    +---------+----------+----------------+--------------+
    | 160 MB   |       1 |           5803 |         6906 | + 19.0%
    | 160 MB   |       2 |          13092 |        15931 |
    | 160 MB   |       4 |          29412 |        33021 |
    | 160 MB   |       8 |          32448 |        34626 |
    | 160 MB   |      16 |          32758 |        33098 |
    | 160 MB   |      20 |          26940 |        31343 | + 16.3%
    | 160 MB   |      30 |          25147 |        28961 |
    | 160 MB   |      40 |          25484 |        26902 |
    | 160 MB   |      50 |          24528 |        25760 |
    ------------------------------------------------------
    | 1.6 GB   |       1 |           5733 |         7729 | + 34.8%
    | 1.6 GB   |       2 |           9411 |        19009 | + 101.9%
    | 1.6 GB   |       4 |          31818 |        33185 |
    | 1.6 GB   |       8 |          33700 |        34550 |
    | 1.6 GB   |      16 |          32751 |        33079 |
    | 1.6 GB   |      20 |          30919 |        31494 |
    | 1.6 GB   |      30 |          28540 |        28535 |
    | 1.6 GB   |      40 |          26380 |        27054 |
    | 1.6 GB   |      50 |          25241 |        25591 |
    ------------------------------------------------------
    | 7.6 GB   |       1 |           5779 |         6224 |
    | 7.6 GB   |       2 |          10897 |        13611 | + 24.9%
    | 7.6 GB   |       4 |          32683 |        33108 |
    | 7.6 GB   |       8 |          33968 |        34712 |
    | 7.6 GB   |      16 |          32287 |        32895 |
    | 7.6 GB   |      20 |          27770 |        31689 | + 14.1%
    | 7.6 GB   |      30 |          26739 |        29003 |
    | 7.6 GB   |      40 |          24901 |        26683 |
    | 7.6 GB   |      50 |          17115 |        25925 | + 51.5%
    ------------------------------------------------------

  (Davidlohr also has one additional patch which further improves
  throughput, though I will ask him to send it directly to you as I have
  suggested some minor changes)."

* emailed patches from Michel Lespinasse <walken@google.com>:
  rwsem: no need for explicit signed longs
  x86 rwsem: avoid taking slow path when stealing write lock
  rwsem: do not block readers at head of queue if other readers are active
  rwsem: implement support for write lock stealing on the fastpath
  rwsem: simplify __rwsem_do_wake
  rwsem: skip initial trylock in rwsem_down_write_failed
  rwsem: avoid taking wait_lock in rwsem_down_write_failed
  rwsem: use cmpxchg for trying to steal write lock
  rwsem: more agressive lock stealing in rwsem_down_write_failed
  rwsem: simplify rwsem_down_write_failed
  rwsem: simplify rwsem_down_read_failed
  rwsem: move rwsem_down_failed_common code into rwsem_down_{read,write}_failed
  rwsem: shorter spinlocked section in rwsem_down_failed_common()
  rwsem: make the waiter type an enumeration rather than a bitmask

2 files changed, 132 insertions, 146 deletions

diff --git a/lib/rwsem-spinlock.c b/lib/rwsem-spinlock.c
index 7542afbb22b3..9be8a9144978 100644
--- a/lib/rwsem-spinlock.c
+++ b/lib/rwsem-spinlock.c
@@ -9,12 +9,15 @@
 #include <linux/sched.h>
 #include <linux/export.h>
 
+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;
 };
 
 int rwsem_is_locked(struct rw_semaphore *sem)
@@ -67,26 +70,17 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
 
         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 
-        if (!wakewrite) {
-                if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
-                        goto out;
-                goto dont_wake_writers;
-        }
-
-        /*
-         * 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) {
-                wake_up_process(waiter->task);
+        if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
+                if (wakewrite)
+                        /* Wake up a writer. Note that we do not grant it the
+                         * lock - it will have to acquire it when it runs. */
+                        wake_up_process(waiter->task);
                 goto out;
         }
 
         /* grant an infinite number of read locks to the front of the queue */
- dont_wake_writers:
         woken = 0;
-        while (waiter->flags & RWSEM_WAITING_FOR_READ) {
+        do {
                 struct list_head *next = waiter->list.next;
 
                 list_del(&waiter->list);
@@ -96,10 +90,10 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
                 wake_up_process(tsk);
                 put_task_struct(tsk);
                 woken++;
-                if (list_empty(&sem->wait_list))
+                if (next == &sem->wait_list)
                         break;
                 waiter = list_entry(next, struct rwsem_waiter, list);
-        }
+        } while (waiter->type != RWSEM_WAITING_FOR_WRITE);
 
         sem->activity += woken;
 
@@ -144,7 +138,7 @@ void __sched __down_read(struct rw_semaphore *sem)
 
         /* set up my own style of waitqueue */
         waiter.task = tsk;
-        waiter.flags = RWSEM_WAITING_FOR_READ;
+        waiter.type = RWSEM_WAITING_FOR_READ;
         get_task_struct(tsk);
 
         list_add_tail(&waiter.list, &sem->wait_list);
@@ -201,7 +195,7 @@ void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
         /* set up my own style of waitqueue */
         tsk = current;
         waiter.task = tsk;
-        waiter.flags = RWSEM_WAITING_FOR_WRITE;
+        waiter.type = RWSEM_WAITING_FOR_WRITE;
         list_add_tail(&waiter.list, &sem->wait_list);
 
         /* wait for someone to release the lock */
diff --git a/lib/rwsem.c b/lib/rwsem.c
index ad5e0df16ab4..cf0ad2ad19f5 100644
--- a/lib/rwsem.c
+++ b/lib/rwsem.c
@@ -4,6 +4,7 @@
  * Derived from arch/i386/kernel/semaphore.c
  *
  * Writer lock-stealing by Alex Shi <alex.shi@intel.com>
+ * and Michel Lespinasse <walken@google.com>
  */
 #include <linux/rwsem.h>
 #include <linux/sched.h>
@@ -30,21 +31,22 @@ 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
- * RWSEM_WAKE_READ_OWNED imply that the spinlock must have been kept held
- * since the rwsem value was observed.
- */
-#define RWSEM_WAKE_ANY        0 /* Wake whatever's at head of wait list */
-#define RWSEM_WAKE_NO_ACTIVE  1 /* rwsem was observed with no active thread */
-#define RWSEM_WAKE_READ_OWNED 2 /* rwsem was observed to be read owned */
+enum rwsem_wake_type {
+        RWSEM_WAKE_ANY,         /* Wake whatever's at head of wait list */
+        RWSEM_WAKE_READERS,     /* Wake readers only */
+        RWSEM_WAKE_READ_OWNED   /* Waker thread holds the read lock */
+};
 
 /*
  * handle the lock release when processes blocked on it that can now run
@@ -57,46 +59,43 @@ struct rwsem_waiter {
  * - writers are only woken if downgrading is false
  */
 static struct rw_semaphore *
-__rwsem_do_wake(struct rw_semaphore *sem, int wake_type)
+__rwsem_do_wake(struct rw_semaphore *sem, enum rwsem_wake_type wake_type)
 {
         struct rwsem_waiter *waiter;
         struct task_struct *tsk;
         struct list_head *next;
-        signed long woken, loop, adjustment;
+        long oldcount, woken, loop, adjustment;
 
         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
-        if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
-                goto readers_only;
-
-        if (wake_type == RWSEM_WAKE_READ_OWNED)
-                /* Another active reader was observed, so wakeup is not
-                 * likely to succeed. Save the atomic op.
-                 */
+        if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
+                if (wake_type == RWSEM_WAKE_ANY)
+                        /* Wake writer at the front of the queue, but do not
+                         * grant it the lock yet as we want other writers
+                         * to be able to steal it.  Readers, on the other hand,
+                         * will block as they will notice the queued writer.
+                         */
+                        wake_up_process(waiter->task);
                 goto out;
+        }
 
-        /* Wake up the writing waiter and let the task grab the sem: */
-        wake_up_process(waiter->task);
-        goto out;
+        /* Writers might steal the lock before we grant it to the next reader.
+         * We prefer to do the first reader grant before counting readers
+         * so we can bail out early if a writer stole the lock.