// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package sync provides basic synchronization primitives such as mutual
// exclusion locks. Other than the Once and WaitGroup types, most are intended
// for use by low-level library routines. Higher-level synchronization is
// better done via channels and communication.
//
// Values containing the types defined in this package should not be copied.
package sync

import (
    "internal/race"
    "sync/atomic"
    "unsafe"
)

func throw(string) // provided by runtime

// A Mutex is a mutual exclusion lock.
// The zero value for a Mutex is an unlocked mutex.
//
// A Mutex must not be copied after first use.
type Mutex struct {
    state int32
    sema  uint32
}

// A Locker represents an object that can be locked and unlocked.
type Locker interface {
    Lock()
    Unlock()
}

const (
    //0001 = 1
    mutexLocked = 1 << iota // mutex is locked
    //0010 = 2
    mutexWoken
    //0100 = 4
    mutexStarving
    //0011 = 3
    mutexWaiterShift = iota

    // Mutex fairness.
    //
    // Mutex can be in 2 modes of operations: normal and starvation.
    // In normal mode waiters are queued in FIFO order, but a woken up waiter
    // does not own the mutex and competes with new arriving goroutines over
    // the ownership. New arriving goroutines have an advantage -- they are
    // already running on CPU and there can be lots of them, so a woken up
    // waiter has good chances of losing. In such case it is queued at front
    // of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
    // it switches mutex to the starvation mode.
    //
    // In starvation mode ownership of the mutex is directly handed off from
    // the unlocking goroutine to the waiter at the front of the queue.
    // New arriving goroutines don't try to acquire the mutex even if it appears
    // to be unlocked, and don't try to spin. Instead they queue themselves at
    // the tail of the wait queue.
    //
    // If a waiter receives ownership of the mutex and sees that either
    // (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
    // it switches mutex back to normal operation mode.
    //
    // Normal mode has considerably better performance as a goroutine can acquire
    // a mutex several times in a row even if there are blocked waiters.
    // Starvation mode is important to prevent pathological cases of tail latency.
    starvationThresholdNs = 1e6
)

// Lock locks m.
// If the lock is already in use, the calling goroutine
// blocks until the mutex is available.
func (m *Mutex) Lock() {
    // Fast path: grab unlocked mutex.
    //如果 state 是 0， 沒有加鎖驻债，進行加鎖并返回
    //如果 state 不是 0, 已經(jīng)加鎖，執(zhí)行 m.lockSlow() 進行排隊加鎖等待
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        if race.Enabled {
            race.Acquire(unsafe.Pointer(m))
        }
        return
    }
    // Slow path (outlined so that the fast path can be inlined)
    m.lockSlow()
}

func (m *Mutex) lockSlow() {
    var waitStartTime int64
    starving := false
    //進入 lockSlow 說明加鎖失敗, 該鎖已經(jīng)被鎖定，進行掛起等待,
    //但是在這個過程中會進行自旋醉者， awoke 標記在自旋過程中, 加鎖的進行是否要進行鎖釋放
    //如果是峻黍，不用進行釋放躁劣，自旋的協(xié)程直接加鎖
    awoke := false
    iter := 0
    old := m.state
    for {
        // Don't spin in starvation mode, ownership is handed off to waiters
        // so we won't be able to acquire the mutex anyway.
        // old & (mutex | mutexStarving) = mutexLocked ; old 處于 lock 狀態(tài)促煮，但是不處于 mutexStarving 狀態(tài)
        //判斷協(xié)程是否可以自旋, 協(xié)程自旋條件如下
        // 1 互斥鎖只有在普通模式才能進入自旋邮屁；
        // 2 runtime.sync_runtime_canSpin 需要返回 true：
        // 2.1 運行在多 CPU 的機器上胸蛛；
        // 2.2 當(dāng)前 Goroutine 為了獲取該鎖進入自旋的次數(shù)小于四次；
        // 2.3 當(dāng)前機器上至少存在一個正在運行的處理器 P 并且處理的運行隊列為空樱报；
        if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
            // Active spinning makes sense.
            // Try to set mutexWoken flag to inform Unlock
            // to not wake other blocked goroutines.
            //判斷是否可以標記 mutexWoken ，并嘗試進行標識泞当，可以進行標記的條件為
            //1. awoke == false
            //2. old mutexWoken 狀態(tài)為 0
            //3. waitersCount 迹蛤，鎖的等待個數(shù)大于 0
            if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
                atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
                awoke = true
            }
            //進行自旋
            runtime_doSpin()
            iter++
            old = m.state
            continue
        }
        new := old

        // Don't try to acquire starving mutex, new arriving goroutines must queue.
        //當(dāng) old 不是 mutexStarving 狀態(tài)
        if old&mutexStarving == 0 {
            // new = new | mutexLocked; new mutexLocked 位置為1
            new |= mutexLocked
        }

        // old 處于饑餓 或 鎖定狀態(tài)
        if old&(mutexLocked|mutexStarving) != 0 {
            //new 高位計數(shù)器加一
            new += 1 << mutexWaiterShift
        }
        // 當(dāng)前協(xié)程將鎖置為饑餓狀態(tài)，但是如果鎖目前沒有被鎖, 不轉(zhuǎn)換
        // Unlock 方法希望饑餓的鎖有 waiter
        // The current goroutine switches mutex to starvation mode.
        // But if the mutex is currently unlocked, don't do the switch.
        // Unlock expects that starving mutex has waiters, which will not
        // be true in this case.
        // starving 為真襟士，并且 old 處于鎖定狀態(tài)
        // 這種情況是當(dāng)前協(xié)程被喚醒盗飒，并且等待時間挺長了，
        // 但是在嘗試加鎖過程中陋桂，又被別的協(xié)程加鎖了逆趣，切換為饑餓模式，將饑餓狀態(tài)為置為1
        if starving && old&mutexLocked != 0 {
            //new = new | mutexStarving嗜历； new mutexStarving 狀態(tài)置為 1
            new |= mutexStarving
        }
        if awoke {
            // The goroutine has been woken from sleep,
            // so we need to reset the flag in either case.
            if new&mutexWoken == 0 {
                throw("sync: inconsistent mutex state")
            }
            // &^ 清零運算符宣渗，根據(jù)右側(cè)操作數(shù)為 1 的位, 對左側(cè)操作數(shù)進行清零
            // 將 new 的 mutexWoken 位置置為為 0
            new &^= mutexWoken
        }
        if atomic.CompareAndSwapInt32(&m.state, old, new) {
            // old mutexLocked 和 mutexStarving 均為0
            // old 沒有被鎖定，并且沒有饑餓
            if old&(mutexLocked|mutexStarving) == 0 {
                // 通過 CAS 函數(shù)獲取了鎖
                // locked the mutex with CAS
                //加鎖成功梨州，出現(xiàn)這種情況痕囱，說明在進行 atomic.CompareAndSwapInt32 的時候
                //之前別的協(xié)程加的鎖已經(jīng)被釋放, 此協(xié)程可以直接加鎖
                break
            }

            //加鎖失敗，將協(xié)程掛載到鎖的信號量上面
            // If we were already waiting before, queue at the front of the queue.
            // queueLifo 是否將協(xié)程掛載到等待協(xié)程隊列的頭部
            queueLifo := waitStartTime != 0
            if waitStartTime == 0 {
                waitStartTime = runtime_nanotime()
            }

            // 信號量掛載
            runtime_SemacquireMutex(&m.sema, queueLifo, 1)

            // 協(xié)程被喚醒暴匠， 繼續(xù)嘗試加鎖
            starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
            old = m.state

            //old 處于 mutexStarving 狀態(tài)
            if old&mutexStarving != 0 {
                // If this goroutine was woken and mutex is in starvation mode,
                // ownership was handed off to us but mutex is in somewhat
                // inconsistent state: mutexLocked is not set and we are still
                // accounted as waiter. Fix that.
                //old 處于 mutexLocked 或者 mutexWoken 狀態(tài), 但是等待的協(xié)程數(shù)為0鞍恢，出現(xiàn)不一致狀態(tài)
                if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
                    throw("sync: inconsistent mutex state")
                }

                //delta = int32(1 - 8)
                delta := int32(mutexLocked - 1<<mutexWaiterShift)
                if !starving || old>>mutexWaiterShift == 1 {
                    //退出 starving 模式
                    // Exit starvation mode.
                    //關(guān)鍵是在這里做，并考慮等待時間每窖。
                    // Critical to do it here and consider wait time.
                    //饑餓模式的效率非常低帮掉，以至于兩個goroutine一旦將互斥切換到饑餓模式，就可以無限地鎖定步進窒典。
                    // Starvation mode is so inefficient, that two goroutines
                    // can go lock-step infinitely once they switch mutex
                    // to starvation mode.
                    //delta = delta - 4
                    delta -= mutexStarving
                }
                //修改狀態(tài)蟆炊，break 加鎖成功
                atomic.AddInt32(&m.state, delta)
                break
            }
            //協(xié)程被喚醒，重新走循環(huán)瀑志，嘗試加鎖
            awoke = true
            iter = 0
        } else {
            old = m.state
        }
    }

    if race.Enabled {
        race.Acquire(unsafe.Pointer(m))
    }
}

// Unlock unlocks m.
// It is a run-time error if m is not locked on entry to Unlock.
//
// A locked Mutex is not associated with a particular goroutine.
// It is allowed for one goroutine to lock a Mutex and then
// arrange for another goroutine to unlock it.
func (m *Mutex) Unlock() {
    if race.Enabled {
        _ = m.state
        race.Release(unsafe.Pointer(m))
    }

    // Fast path: drop lock bit.
    // 將標志位置為未加鎖
    new := atomic.AddInt32(&m.state, -mutexLocked)
    if new != 0 {
        // Outlined slow path to allow inlining the fast path.
        // To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
        m.unlockSlow(new)
    }
}

func (m *Mutex) unlockSlow(new int32) {
    if (new+mutexLocked)&mutexLocked == 0 {
        throw("sync: unlock of unlocked mutex")
    }
    if new&mutexStarving == 0 { // 正常模式
        old := new
        for {
            // If there are no waiters or a goroutine has already
            // been woken or grabbed the lock, no need to wake anyone.
            // In starvation mode ownership is directly handed off from unlocking
            // goroutine to the next waiter. We are not part of this chain,
            // since we did not observe mutexStarving when we unlocked the mutex above.
            // So get off the way.
            if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
                return
            }
            // Grab the right to wake someone.
            new = (old - 1<<mutexWaiterShift) | mutexWoken
            if atomic.CompareAndSwapInt32(&m.state, old, new) {
                runtime_Semrelease(&m.sema, false, 1)
                return
            }
            old = m.state
        }
    } else { // 饑餓模式
        // Starving mode: handoff mutex ownership to the next waiter, and yield
        // our time slice so that the next waiter can start to run immediately.
        // Note: mutexLocked is not set, the waiter will set it after wakeup.
        // But mutex is still considered locked if mutexStarving is set,
        // so new coming goroutines won't acquire it.
        runtime_Semrelease(&m.sema, true, 1)
    }
}