lkml.org 
[lkml]   [2013]   [Nov]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Subject[PATCH v7 0/4] qrwlock: Introducing a queue read/write lock implementation
    Date
    v6->v7:
    - Remove support for unfair lock, so only fair qrwlock will be provided.
    - Move qrwlock.c to the kernel/locking directory.

    v5->v6:
    - Modify queue_read_can_lock() to avoid false positive result.
    - Move the two slowpath functions' performance tuning change from
    patch 4 to patch 1.
    - Add a new optional patch to use the new smp_store_release() function
    if that is merged.

    v4->v5:
    - Fix wrong definitions for QW_MASK_FAIR & QW_MASK_UNFAIR macros.
    - Add an optional patch 4 which should only be applied after the
    mcs_spinlock.h header file is merged.

    v3->v4:
    - Optimize the fast path with better cold cache behavior and
    performance.
    - Removing some testing code.
    - Make x86 use queue rwlock with no user configuration.

    v2->v3:
    - Make read lock stealing the default and fair rwlock an option with
    a different initializer.
    - In queue_read_lock_slowpath(), check irq_count() and force spinning
    and lock stealing in interrupt context.
    - Unify the fair and classic read-side code path, and make write-side
    to use cmpxchg with 2 different writer states. This slows down the
    write lock fastpath to make the read side more efficient, but is
    still slightly faster than a spinlock.

    v1->v2:
    - Improve lock fastpath performance.
    - Optionally provide classic read/write lock behavior for backward
    compatibility.
    - Use xadd instead of cmpxchg for fair reader code path to make it
    immute to reader contention.
    - Run more performance testing.

    As mentioned in the LWN article http://lwn.net/Articles/364583/,
    the read/write lock suffer from an unfairness problem that it is
    possible for a stream of incoming readers to block a waiting writer
    from getting the lock for a long time. Also, a waiting reader/writer
    contending a rwlock in local memory will have a higher chance of
    acquiring the lock than a reader/writer in remote node.

    This patch set introduces a queue-based read/write lock implementation
    that can largely solve this unfairness problem.

    The read lock slowpath will check if the reader is in an interrupt
    context. If so, it will force lock spinning and stealing without
    waiting in a queue. This is to ensure the read lock will be granted
    as soon as possible.

    The queue write lock can also be used as a replacement for ticket
    spinlocks that are highly contended if lock size increase is not
    an issue.

    This patch set currently provides queue read/write lock support on
    x86 architecture only. Support for other architectures can be added
    later on once architecture specific support infrastructure is added
    and proper testing is done.

    The optional patch 3 has a dependency on the the mcs_spinlock.h
    header file which has not been merged yet. So this patch should only
    be applied after the mcs_spinlock.h header file is merged.

    The optional patch 4 use the new smp_store_release() and
    smp_load_acquire() functions which are being reviewed & not merged yet.

    Waiman Long (4):
    qrwlock: A queue read/write lock implementation
    qrwlock x86: Enable x86 to use queue read/write lock
    qrwlock: Use the mcs_spinlock helper functions for MCS queuing
    qrwlock: Use smp_store_release() in write_unlock()

    arch/x86/Kconfig | 1 +
    arch/x86/include/asm/spinlock.h | 2 +
    arch/x86/include/asm/spinlock_types.h | 4 +
    include/asm-generic/qrwlock.h | 200 +++++++++++++++++++++++++++++++++
    kernel/Kconfig.locks | 7 +
    kernel/locking/Makefile | 1 +
    kernel/locking/qrwlock.c | 196 ++++++++++++++++++++++++++++++++
    7 files changed, 411 insertions(+), 0 deletions(-)
    create mode 100644 include/asm-generic/qrwlock.h
    create mode 100644 kernel/locking/qrwlock.c



    \
     
     \ /
      Last update: 2013-11-22 20:41    [W:3.947 / U:0.612 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site