15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Copyright (c) 2006, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Author: Sanjay Ghemawat 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <config.h> 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock.h" 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/synchronization_profiling.h" 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock_internal.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/cycleclock.h" 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/sysinfo.h" /* for NumCPUs() */ 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// NOTE on the Lock-state values: 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kSpinLockFree represents the unlocked state 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kSpinLockHeld represents the locked state with no waiters 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Values greater than kSpinLockHeld represent the locked state with waiters, 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// where the value is the time the current lock holder had to 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// wait before obtaining the lock. The kSpinLockSleeper state is a special 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "locked with waiters" state that indicates that a sleeper needs to 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// be woken, but the thread that just released the lock didn't wait. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int adaptive_spin_count = 0; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const base::LinkerInitialized SpinLock::LINKER_INITIALIZED = 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::LINKER_INITIALIZED; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct SpinLock_InitHelper { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLock_InitHelper() { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // On multi-cpu machines, spin for longer before yielding 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the processor or sleeping. Reduces idle time significantly. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (NumCPUs() > 1) { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) adaptive_spin_count = 1000; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Hook into global constructor execution: 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We do not do adaptive spinning before that, 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but nothing lock-intensive should be going on at that time. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SpinLock_InitHelper init_helper; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // unnamed namespace 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Monitor the lock to see if its value changes within some time period 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (adaptive_spin_count loop iterations). A timestamp indicating 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// when the thread initially started waiting for the lock is passed in via 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the initial_wait_timestamp value. The total wait time in cycles for the 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// lock is returned in the wait_cycles parameter. The last value read 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// from the lock is returned from the method. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Atomic32 SpinLock::SpinLoop(int64 initial_wait_timestamp, 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Atomic32* wait_cycles) { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int c = adaptive_spin_count; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (base::subtle::NoBarrier_Load(&lockword_) != kSpinLockFree && --c > 0) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Atomic32 spin_loop_wait_cycles = CalculateWaitCycles(initial_wait_timestamp); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Atomic32 lock_value = 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::subtle::Acquire_CompareAndSwap(&lockword_, kSpinLockFree, 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) spin_loop_wait_cycles); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *wait_cycles = spin_loop_wait_cycles; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return lock_value; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SpinLock::SlowLock() { 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The lock was not obtained initially, so this thread needs to wait for 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it. Record the current timestamp in the local variable wait_start_time 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // so the total wait time can be stored in the lockword once this thread 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // obtains the lock. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 wait_start_time = CycleClock::Now(); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Atomic32 wait_cycles; 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Atomic32 lock_value = SpinLoop(wait_start_time, &wait_cycles); 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lock_wait_call_count = 0; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (lock_value != kSpinLockFree) { 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the lock is currently held, but not marked as having a sleeper, mark 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it as having a sleeper. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lock_value == kSpinLockHeld) { 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Here, just "mark" that the thread is going to sleep. Don't store the 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // lock wait time in the lock as that will cause the current lock 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // owner to think it experienced contention. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_value = base::subtle::Acquire_CompareAndSwap(&lockword_, 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kSpinLockHeld, 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kSpinLockSleeper); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lock_value == kSpinLockHeld) { 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Successfully transitioned to kSpinLockSleeper. Pass 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kSpinLockSleeper to the SpinLockWait routine to properly indicate 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the last lock_value observed. 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_value = kSpinLockSleeper; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (lock_value == kSpinLockFree) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Lock is free again, so try and aquire it before sleeping. The 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // new lock state will be the number of cycles this thread waited if 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this thread obtains the lock. 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_value = base::subtle::Acquire_CompareAndSwap(&lockword_, 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kSpinLockFree, 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) wait_cycles); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; // skip the delay at the end of the loop 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Wait for an OS specific delay. 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::internal::SpinLockDelay(&lockword_, lock_value, 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++lock_wait_call_count); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Spin again after returning from the wait routine to give this thread 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // some chance of obtaining the lock. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_value = SpinLoop(wait_start_time, &wait_cycles); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The wait time for contentionz lock profiling must fit into 32 bits. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// However, the lower 32-bits of the cycle counter wrap around too quickly 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// with high frequency processors, so a right-shift by 7 is performed to 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// quickly divide the cycles by 128. Using these 32 bits, reduces the 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// granularity of time measurement to 128 cycles, and loses track 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of wait time for waits greater than 109 seconds on a 5 GHz machine 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// [(2^32 cycles/5 Ghz)*128 = 109.95 seconds]. Waits this long should be 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// very rare and the reduced granularity should not be an issue given 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// processors in the Google fleet operate at a minimum of one billion 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// cycles/sec. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum { PROFILE_TIMESTAMP_SHIFT = 7 }; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SpinLock::SlowUnlock(uint64 wait_cycles) { 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::internal::SpinLockWake(&lockword_, false); // wake waiter if necessary 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Collect contentionz profile info, expanding the wait_cycles back out to 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the full value. If wait_cycles is <= kSpinLockSleeper, then no wait 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // was actually performed, so don't record the wait time. Note, that the 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // CalculateWaitCycles method adds in kSpinLockSleeper cycles 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // unconditionally to guarantee the wait time is not kSpinLockFree or 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kSpinLockHeld. The adding in of these small number of cycles may 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // overestimate the contention by a slight amount 50% of the time. However, 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if this code tried to correct for that addition by subtracting out the 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kSpinLockSleeper amount that would underestimate the contention slightly 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 50% of the time. Both ways get the wrong answer, so the code 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // overestimates to be more conservative. Overestimating also makes the code 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a little simpler. 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (wait_cycles > kSpinLockSleeper) { 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::SubmitSpinLockProfileData(this, 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) wait_cycles << PROFILE_TIMESTAMP_SHIFT); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int32 SpinLock::CalculateWaitCycles(int64 wait_start_time) { 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 wait_cycles = ((CycleClock::Now() - wait_start_time) >> 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PROFILE_TIMESTAMP_SHIFT); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The number of cycles waiting for the lock is used as both the 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // wait_cycles and lock value, so it can't be kSpinLockFree or 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kSpinLockHeld. Make sure the value returned is at least 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kSpinLockSleeper. 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) wait_cycles |= kSpinLockSleeper; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return wait_cycles; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 183