...
Run Format

Source file src/sync/mutex.go

Documentation: sync

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package sync provides basic synchronization primitives such as mutual
     6  // exclusion locks. Other than the Once and WaitGroup types, most are intended
     7  // for use by low-level library routines. Higher-level synchronization is
     8  // better done via channels and communication.
     9  //
    10  // Values containing the types defined in this package should not be copied.
    11  package sync
    12  
    13  import (
    14  	"internal/race"
    15  	"sync/atomic"
    16  	"unsafe"
    17  )
    18  
    19  func throw(string) // provided by runtime
    20  
    21  // A Mutex is a mutual exclusion lock.
    22  // The zero value for a Mutex is an unlocked mutex.
    23  //
    24  // A Mutex must not be copied after first use.
    25  type Mutex struct {
    26  	state int32
    27  	sema  uint32
    28  }
    29  
    30  // A Locker represents an object that can be locked and unlocked.
    31  type Locker interface {
    32  	Lock()
    33  	Unlock()
    34  }
    35  
    36  const (
    37  	mutexLocked = 1 << iota // mutex is locked
    38  	mutexWoken
    39  	mutexStarving
    40  	mutexWaiterShift = iota
    41  
    42  	// Mutex fairness.
    43  	//
    44  	// Mutex can be in 2 modes of operations: normal and starvation.
    45  	// In normal mode waiters are queued in FIFO order, but a woken up waiter
    46  	// does not own the mutex and competes with new arriving goroutines over
    47  	// the ownership. New arriving goroutines have an advantage -- they are
    48  	// already running on CPU and there can be lots of them, so a woken up
    49  	// waiter has good chances of losing. In such case it is queued at front
    50  	// of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
    51  	// it switches mutex to the starvation mode.
    52  	//
    53  	// In starvation mode ownership of the mutex is directly handed off from
    54  	// the unlocking goroutine to the waiter at the front of the queue.
    55  	// New arriving goroutines don't try to acquire the mutex even if it appears
    56  	// to be unlocked, and don't try to spin. Instead they queue themselves at
    57  	// the tail of the wait queue.
    58  	//
    59  	// If a waiter receives ownership of the mutex and sees that either
    60  	// (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
    61  	// it switches mutex back to normal operation mode.
    62  	//
    63  	// Normal mode has considerably better performance as a goroutine can acquire
    64  	// a mutex several times in a row even if there are blocked waiters.
    65  	// Starvation mode is important to prevent pathological cases of tail latency.
    66  	starvationThresholdNs = 1e6
    67  )
    68  
    69  // Lock locks m.
    70  // If the lock is already in use, the calling goroutine
    71  // blocks until the mutex is available.
    72  func (m *Mutex) Lock() {
    73  	// Fast path: grab unlocked mutex.
    74  	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
    75  		if race.Enabled {
    76  			race.Acquire(unsafe.Pointer(m))
    77  		}
    78  		return
    79  	}
    80  
    81  	var waitStartTime int64
    82  	starving := false
    83  	awoke := false
    84  	iter := 0
    85  	old := m.state
    86  	for {
    87  		// Don't spin in starvation mode, ownership is handed off to waiters
    88  		// so we won't be able to acquire the mutex anyway.
    89  		if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
    90  			// Active spinning makes sense.
    91  			// Try to set mutexWoken flag to inform Unlock
    92  			// to not wake other blocked goroutines.
    93  			if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
    94  				atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
    95  				awoke = true
    96  			}
    97  			runtime_doSpin()
    98  			iter++
    99  			old = m.state
   100  			continue
   101  		}
   102  		new := old
   103  		// Don't try to acquire starving mutex, new arriving goroutines must queue.
   104  		if old&mutexStarving == 0 {
   105  			new |= mutexLocked
   106  		}
   107  		if old&(mutexLocked|mutexStarving) != 0 {
   108  			new += 1 << mutexWaiterShift
   109  		}
   110  		// The current goroutine switches mutex to starvation mode.
   111  		// But if the mutex is currently unlocked, don't do the switch.
   112  		// Unlock expects that starving mutex has waiters, which will not
   113  		// be true in this case.
   114  		if starving && old&mutexLocked != 0 {
   115  			new |= mutexStarving
   116  		}
   117  		if awoke {
   118  			// The goroutine has been woken from sleep,
   119  			// so we need to reset the flag in either case.
   120  			if new&mutexWoken == 0 {
   121  				throw("sync: inconsistent mutex state")
   122  			}
   123  			new &^= mutexWoken
   124  		}
   125  		if atomic.CompareAndSwapInt32(&m.state, old, new) {
   126  			if old&(mutexLocked|mutexStarving) == 0 {
   127  				break // locked the mutex with CAS
   128  			}
   129  			// If we were already waiting before, queue at the front of the queue.
   130  			queueLifo := waitStartTime != 0
   131  			if waitStartTime == 0 {
   132  				waitStartTime = runtime_nanotime()
   133  			}
   134  			runtime_SemacquireMutex(&m.sema, queueLifo)
   135  			starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
   136  			old = m.state
   137  			if old&mutexStarving != 0 {
   138  				// If this goroutine was woken and mutex is in starvation mode,
   139  				// ownership was handed off to us but mutex is in somewhat
   140  				// inconsistent state: mutexLocked is not set and we are still
   141  				// accounted as waiter. Fix that.
   142  				if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
   143  					throw("sync: inconsistent mutex state")
   144  				}
   145  				delta := int32(mutexLocked - 1<<mutexWaiterShift)
   146  				if !starving || old>>mutexWaiterShift == 1 {
   147  					// Exit starvation mode.
   148  					// Critical to do it here and consider wait time.
   149  					// Starvation mode is so inefficient, that two goroutines
   150  					// can go lock-step infinitely once they switch mutex
   151  					// to starvation mode.
   152  					delta -= mutexStarving
   153  				}
   154  				atomic.AddInt32(&m.state, delta)
   155  				break
   156  			}
   157  			awoke = true
   158  			iter = 0
   159  		} else {
   160  			old = m.state
   161  		}
   162  	}
   163  
   164  	if race.Enabled {
   165  		race.Acquire(unsafe.Pointer(m))
   166  	}
   167  }
   168  
   169  // Unlock unlocks m.
   170  // It is a run-time error if m is not locked on entry to Unlock.
   171  //
   172  // A locked Mutex is not associated with a particular goroutine.
   173  // It is allowed for one goroutine to lock a Mutex and then
   174  // arrange for another goroutine to unlock it.
   175  func (m *Mutex) Unlock() {
   176  	if race.Enabled {
   177  		_ = m.state
   178  		race.Release(unsafe.Pointer(m))
   179  	}
   180  
   181  	// Fast path: drop lock bit.
   182  	new := atomic.AddInt32(&m.state, -mutexLocked)
   183  	if (new+mutexLocked)&mutexLocked == 0 {
   184  		throw("sync: unlock of unlocked mutex")
   185  	}
   186  	if new&mutexStarving == 0 {
   187  		old := new
   188  		for {
   189  			// If there are no waiters or a goroutine has already
   190  			// been woken or grabbed the lock, no need to wake anyone.
   191  			// In starvation mode ownership is directly handed off from unlocking
   192  			// goroutine to the next waiter. We are not part of this chain,
   193  			// since we did not observe mutexStarving when we unlocked the mutex above.
   194  			// So get off the way.
   195  			if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
   196  				return
   197  			}
   198  			// Grab the right to wake someone.
   199  			new = (old - 1<<mutexWaiterShift) | mutexWoken
   200  			if atomic.CompareAndSwapInt32(&m.state, old, new) {
   201  				runtime_Semrelease(&m.sema, false)
   202  				return
   203  			}
   204  			old = m.state
   205  		}
   206  	} else {
   207  		// Starving mode: handoff mutex ownership to the next waiter.
   208  		// Note: mutexLocked is not set, the waiter will set it after wakeup.
   209  		// But mutex is still considered locked if mutexStarving is set,
   210  		// so new coming goroutines won't acquire it.
   211  		runtime_Semrelease(&m.sema, true)
   212  	}
   213  }
   214  

View as plain text