• Thomas Hellstrom's avatar
    locking: Implement an algorithm choice for Wound-Wait mutexes · 08295b3b
    Thomas Hellstrom authored
    The current Wound-Wait mutex algorithm is actually not Wound-Wait but
    Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait
    is, contrary to Wait-Die a preemptive algorithm and is known to generate
    fewer backoffs. Testing reveals that this is true if the
    number of simultaneous contending transactions is small.
    As the number of simultaneous contending threads increases, Wait-Wound
    becomes inferior to Wait-Die in terms of elapsed time.
    Possibly due to the larger number of held locks of sleeping transactions.
    
    Update documentation and callers.
    
    Timings using git://people.freedesktop.org/~thomash/ww_mutex_test
    tag patch-18-06-15
    
    Each thread runs 100000 batches of lock / unlock 800 ww mutexes randomly
    chosen out of 100000. Four core Intel x86_64:
    
    Algorithm    #threads       Rollbacks  time
    Wound-Wait   4              ~100       ~17s.
    Wait-Die     4              ~150000    ~19s.
    Wound-Wait   16             ~360000    ~109s.
    Wait-Die     16             ~450000    ~82s.
    
    Cc: Ingo Molnar <mingo@redhat.com>
    Cc: Jonathan Corbet <corbet@lwn.net>
    Cc: Gustavo Padovan <gustavo@padovan.org>
    Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com>
    Cc: Sean Paul <seanpaul@chromium.org>
    Cc: David Airlie <airlied@linux.ie>
    Cc: Davidlohr Bueso <dave@stgolabs.net>
    Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
    Cc: Josh Triplett <josh@joshtriplett.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: Kate Stewart <kstewart@linuxfoundation.org>
    Cc: Philippe Ombredanne <pombredanne@nexb.com>
    Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
    Cc: linux-doc@vger.kernel.org
    Cc: linux-media@vger.kernel.org
    Cc: linaro-mm-sig@lists.linaro.org
    Co-authored-by: default avatarPeter Zijlstra <peterz@infradead.org>
    Signed-off-by: default avatarThomas Hellstrom <thellstrom@vmware.com>
    Acked-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Acked-by: default avatarIngo Molnar <mingo@kernel.org>
    08295b3b
ww-mutex-design.txt 14.8 KB