Source/WTF/wtf/Lock.cpp

   1 /*
   2  * Copyright (C) 2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "Lock.h"
  28
  29 #include "DataLog.h"
  30 #include "ParkingLot.h"
  31 #include "StringPrintStream.h"
  32 #include "ThreadingPrimitives.h"
  33 #include <thread>
  34
  35 namespace WTF {
  36
  37 static const bool verbose = false;
  38
  39 NEVER_INLINE void LockBase::lockSlow()
  40 {
  41     unsigned spinCount = 0;
  42
  43     // This magic number turns out to be optimal based on past JikesRVM experiments.
  44     const unsigned spinLimit = 40;
  45
  46     for (;;) {
  47         uint8_t currentByteValue = m_byte.load();
  48         if (verbose)
  49             dataLog(toString(currentThread(), ": locking with ", currentByteValue, "\n"));
  50
  51         // We allow ourselves to barge in.
  52         if (!(currentByteValue & isHeldBit)
  53             && m_byte.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
  54             return;
  55
  56         // If there is nobody parked and we haven't spun too much, we can just try to spin around.
  57         if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
  58             spinCount++;
  59             std::this_thread::yield();
  60             continue;
  61         }
  62
  63         // Need to park. We do this by setting the parked bit first, and then parking. We spin around
  64         // if the parked bit wasn't set and we failed at setting it.
  65         if (!(currentByteValue & hasParkedBit)
  66             && !m_byte.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
  67             continue;
  68
  69         // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
  70         ParkingLot::compareAndPark(&m_byte, isHeldBit | hasParkedBit);
  71
  72         // We have awoken, or we never parked because the byte value changed. Either way, we loop
  73         // around and try again.
  74     }
  75 }
  76
  77 NEVER_INLINE void LockBase::unlockSlow()
  78 {
  79     // We could get here because the weak CAS in unlock() failed spuriously, or because there is
  80     // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
  81     // be held and parked if someone attempts to lock just as we are unlocking.
  82     for (;;) {
  83         uint8_t oldByteValue = m_byte.load();
  84         RELEASE_ASSERT(oldByteValue == isHeldBit || oldByteValue == (isHeldBit | hasParkedBit));
  85
  86         if (oldByteValue == isHeldBit) {
  87             if (m_byte.compareExchangeWeak(isHeldBit, 0))
  88                 return;
  89             continue;
  90         }
  91
  92         // Someone is parked. Unpark exactly one thread, possibly leaving the parked bit set if
  93         // there is a chance that there are still other threads parked.
  94         ASSERT(oldByteValue == (isHeldBit | hasParkedBit));
  95         ParkingLot::unparkOne(
  96             &m_byte,
  97             [this] (ParkingLot::UnparkResult result) {
  98                 // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
  99                 // so we should still see both bits set right now.
 100                 ASSERT(m_byte.load() == (isHeldBit | hasParkedBit));
 101
 102                 if (result.mayHaveMoreThreads)
 103                     m_byte.store(hasParkedBit);
 104                 else
 105                     m_byte.store(0);
 106             });
 107         return;
 108     }
 109 }
 110
 111 } // namespace WTF
 112