Skip to content
GitLab
  1. Jun 06, 2014
    • Waiman Long's avatar
      x86, locking/rwlocks: Enable qrwlocks on x86 · bd01ec1a
      Waiman Long authored 
      

Make x86 use the fair rwlock_t.

Implement the custom queue_write_unlock() for best performance.

Signed-off-by: default avatarWaiman Long <Waiman.Long@hp.com>
[peterz: near complete rewrite]
Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
Cc: Dave Jones <davej@redhat.com>
Cc: Jeremy Fitzhardinge <jeremy@goop.org>
Cc: Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Raghavendra K T <raghavendra.kt@linux.vnet.ibm.com>
Cc: "Paul E.McKenney" <paulmck@linux.vnet.ibm.com>
Cc: linux-kernel@vger.kernel.org
Cc: x86@kernel.org
Link: http://lkml.kernel.org/n/tip-r1xuzmdysvuhl3h86n5fbxi7@git.kernel.org


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      bd01ec1a
    • Waiman Long's avatar
      locking/rwlocks: Introduce 'qrwlocks' - fair, queued rwlocks · 70af2f8a
      Waiman Long authored 
      This rwlock uses the arch_spin_lock_t as a waitqueue, and assuming the
arch_spin_lock_t is a fair lock (ticket,mcs etc..) the resulting
rwlock is a fair lock.

It fits in the same 8 bytes as the regular rwlock_t by folding the
reader and writer count into a single integer, using the remaining 4
bytes for the arch_spinlock_t.

Architectures that can single-copy adress bytes can optimize
queue_write_unlock() with a 0 write to the LSB (the write count).

Performance as measured by Davidlohr Bueso (rwlock_t -> qrwlock_t):

 +--------------+-------------+---------------+
 |   Workload   |   #users    |     delta     |
 +--------------+-------------+---------------+
 | alltests     | > 1400      | -4.83%        |
 | custom       | 0-100,> 100 | +1.43%,-1.57% |
 | high_systime | > 1000      | -2.61         |
 | shared       | all         | +0.32         |
 +--------------+-------------+---------------+

http://www.stgolabs.net/qrwlock-stuff/aim7-result...
      70af2f8a
  3. Jun 05, 2014
    • Davidlohr Bueso's avatar
      locking/mutexes: Documentation update/rewrite · 9161f540
      Davidlohr Bueso authored 
      

Our mutexes have gone a long ways since the original
implementation back in 2005/2006. However, the mutex-design.txt
document is still stuck in the past, to the point where most of
the information there is practically useless and, more
important, simply incorrect. This patch pretty much rewrites it
to resemble what we have nowadays.

Since regular semaphores are almost much extinct in the kernel
(most users now rely on mutexes or rwsems), it no longer makes
sense to have such a close comparison, which was copied from
most of the cover letter when Ingo introduced the generic mutex
subsystem.

Note that ww_mutexes are intentionally left out, leaving things
as generic as possible.

Signed-off-by: default avatarDavidlohr Bueso <davidlohr@hp.com>
Cc: tim.c.chen@linux.intel.com
Cc: paulmck@linux.vnet.ibm.com
Cc: waiman.long@hp.com
Cc: jason.low2@hp.com
Cc: aswin@hp.com
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1401338203.2618.11.camel@buesod1.americas.hpqcorp.net


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      9161f540
    • Andrew Morton's avatar
      locking/rwsem: Fix checkpatch.pl warnings · 0cc3d011
      Andrew Morton authored 
      

WARNING: line over 80 characters
#205: FILE: kernel/locking/rwsem-xadd.c:275:
+		old = cmpxchg(&sem->count, count, count + RWSEM_ACTIVE_WRITE_BIAS);

WARNING: line over 80 characters
#376: FILE: kernel/locking/rwsem-xadd.c:434:
+		 * If there were already threads queued before us and there are no

WARNING: line over 80 characters
#377: FILE: kernel/locking/rwsem-xadd.c:435:
+		 * active writers, the lock must be read owned; so we try to wake

total: 0 errors, 3 warnings, 417 lines checked

Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: Davidlohr Bueso <davidlohr@hp.com>
Cc: Tim Chen <tim.c.chen@linux.intel.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Link: http://lkml.kernel.org/n/tip-pn6pslaplw031lykweojsn8c@git.kernel.org


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      0cc3d011
    • Davidlohr Bueso's avatar
      locking/rwsem: Fix warnings for CONFIG_RWSEM_GENERIC_SPINLOCK · dbb5eafa
      Davidlohr Bueso authored 
      

Optimistic spinning is only used by the xadd variant
of rw-semaphores. Make sure that we use the old version
of the __RWSEM_INITIALIZER macro for systems that rely
on the spinlock one, otherwise warnings can be triggered,
such as the following reported on an arm box:

  ipc/ipcns_notifier.c:22:8: warning: excess elements in struct initializer [enabled by default]
  ipc/ipcns_notifier.c:22:8: warning: (near initialization for 'ipcns_chain.rwsem') [enabled by default]
  ipc/ipcns_notifier.c:22:8: warning: excess elements in struct initializer [enabled by default]
  ipc/ipcns_notifier.c:22:8: warning: (near initialization for 'ipcns_chain.rwsem') [enabled by default]

Signed-off-by: default avatarDavidlohr Bueso <davidlohr@hp.com>
Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
Cc: Tim Chen <tim.c.chen@linux.intel.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Peter Hurley <peter@hurleysoftware.com>
Cc: Alex Shi <alex.shi@linaro.org>
Cc: Rik van Riel <riel@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: Jason Low <jason.low2@hp.com>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Chris Mason <clm@fb.com>
Cc: Josef Bacik <jbacik@fusionio.com>
Link: http://lkml.kernel.org/r/1400545677.6399.10.camel@buesod1.americas.hpqcorp.net


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      dbb5eafa
    • Davidlohr Bueso's avatar
      locking/rwsem: Support optimistic spinning · 4fc828e2
      Davidlohr Bueso authored 
      We have reached the point where our mutexes are quite fine tuned
for a number of situations. This includes the use of heuristics
and optimistic spinning, based on MCS locking techniques.

Exclusive ownership of read-write semaphores are, conceptually,
just about the same as mutexes, making them close cousins. To
this end we need to make them both perform similarly, and
right now, rwsems are simply not up to it. This was discovered
by both reverting commit 4fc3f1d6

 (mm/rmap, migration: Make
rmap_walk_anon() and try_to_unmap_anon() more scalable) and
similarly, converting some other mutexes (ie: i_mmap_mutex) to
rwsems. This creates a situation where users have to choose
between a rwsem and mutex taking into account this important
performance difference. Specifically, biggest difference between
both locks is when we fail to acquire a mutex in the fastpath,
optimistic spinning comes in to play and we can avoid a large
amount of unnecessary sleeping and overhead of moving tasks in
and out of wait queue. Rwsems do not have such logic.

This patch, based on the work from Tim Chen and I, adds support
for write-side optimistic spinning when the lock is contended.
It also includes support for the recently added cancelable MCS
locking for adaptive spinning. Note that is is only applicable
to the xadd method, and the spinlock rwsem variant remains intact.

Allowing optimistic spinning before putting the writer on the wait
queue reduces wait queue contention and provided greater chance
for the rwsem to get acquired. With these changes, rwsem is on par
with mutex. The performance benefits can be seen on a number of
workloads. For instance, on a 8 socket, 80 core 64bit Westmere box,
aim7 shows the following improvements in throughput:

 +--------------+---------------------+-----------------+
 |   Workload   | throughput-increase | number of users |
 +--------------+---------------------+-----------------+
 | alltests     | 20%                 | >1000           |
 | custom       | 27%, 60%            | 10-100, >1000   |
 | high_systime | 36%, 30%            | >100, >1000     |
 | shared       | 58%, 29%            | 10-100, >1000   |
 +--------------+---------------------+-----------------+

There was also improvement on smaller systems, such as a quad-core
x86-64 laptop running a 30Gb PostgreSQL (pgbench) workload for up
to +60% in throughput for over 50 clients. Additionally, benefits
were also noticed in exim (mail server) workloads. Furthermore, no
performance regression have been seen at all.

Based-on-work-from: Tim Chen <tim.c.chen@linux.intel.com>
Signed-off-by: default avatarDavidlohr Bueso <davidlohr@hp.com>
[peterz: rej fixup due to comment patches, sched/rt.h header]
Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
Cc: Alex Shi <alex.shi@linaro.org>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Hurley <peter@hurleysoftware.com>
Cc: "Paul E.McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Jason Low <jason.low2@hp.com>
Cc: Aswin Chandramouleeswaran <aswin@hp.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: "Scott J Norton" <scott.norton@hp.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Chris Mason <clm@fb.com>
Cc: Josef Bacik <jbacik@fusionio.com>
Link: http://lkml.kernel.org/r/1399055055.6275.15.camel@buesod1.americas.hpqcorp.net


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      4fc828e2
  5. May 05, 2014
    • Tim Chen's avatar
      rwsem: Add comments to explain the meaning of the rwsem's count field · 3cf2f34e
      Tim Chen authored 
      

It took me quite a while to understand how rwsem's count field
mainifested itself in different scenarios.

Add comments to provide a quick reference to the the rwsem's count
field for each scenario where readers and writers are contending
for the lock.

Hopefully it will be useful for future maintenance of the code and
for people to get up to speed on how the logic in the code works.

Signed-off-by: default avatarTim Chen <tim.c.chen@linux.intel.com>
Cc: Davidlohr Bueso <davidlohr@hp.com>
Cc: Alex Shi <alex.shi@linaro.org>
Cc: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Hurley <peter@hurleysoftware.com>
Cc: Paul E.McKenney <paulmck@linux.vnet.ibm.com>
Cc: Jason Low <jason.low2@hp.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Link: http://lkml.kernel.org/r/1399060437.2970.146.camel@schen9-DESK


Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
      3cf2f34e
  7. Apr 18, 2014