type Locker interface {
    Lock()
    Unlock()
}

func(m *Mutex)Lock()
func(m *Mutex)Unlock()

import (
    "fmt"
    "sync"
)
    
func main() {
    var count = 0
    // 使用WaitGroup等待10个goroutine完成
    var wg sync.WaitGroup
    wg.Add(10)
    for i := 0; i < 10; i++ {
        go func() {
            defer wg.Done()
            // 对变量count执行10次加1
            for j := 0; j < 100000; j++ {
                count++
            }
        }()
    }
    // 等待10个goroutine完成
    wg.Wait()
    fmt.Println(count)
}

$ go run counter.go
855347
$ go run counter.go
802752
$ go run counter.go
789473

$ go run -race counter.go 
==================
WARNING: DATA RACE
Read at 0x00c00009a078 by goroutine 14:
  main.main.func1()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:19 +0x99

Previous write at 0x00c00009a078 by goroutine 7:
  main.main.func1()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:19 +0xab

Goroutine 14 (running) created at:
  main.main()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:15 +0x84

Goroutine 7 (running) created at:
  main.main()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:15 +0x84
==================
==================
WARNING: DATA RACE
Write at 0x00c00009a078 by goroutine 14:
  main.main.func1()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:19 +0xab

Previous write at 0x00c00009a078 by goroutine 7:
  main.main.func1()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:19 +0xab

Goroutine 14 (running) created at:
  main.main()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:15 +0x84

Goroutine 7 (running) created at:
  main.main()
      /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.1counter/counter.go:15 +0x84
==================
850860
Found 2 data race(s)
exit status 66

package main

import (
        "fmt"
        "sync"
)

func main() {
        var mu sync.Mutex
        count := 0
        // 使用 WaitGroup 等待 10 个 goroutine 完成.
        var wg sync.WaitGroup
        wg.Add(10)

        for i := 0; i < 10; i++ {
                go func() {
                        defer wg.Done()
                        // 对变量进行执行 100000 次加 1.
                        for j := 0; j < 100000; j++ {
                                mu.Lock()
                                count++
                                mu.Unlock()
                        }
                }()
        }

        // 等待 10 个 goroutine 完成.
        wg.Wait()
        fmt.Println(count)
}

type Counter struct {
    mu    sync.Mutex
    Count uint64
}

type Counter struct {
    sync.Mutex
    Count uint64
}

func main() {
    var counter Counter
    var wg sync.WaitGroup
    wg.Add(10)
    for i := 0; i < 10; i++ {
        go func() {
            defer wg.Done()
            for j := 0; j < 100000; j++ {
                counter.Lock()
                counter.Count++
                counter.Unlock()
            }
        }()
    }
    wg.Wait()
    fmt.Println(counter.Count)
}

func main() {
    // 封装好的计数器
    var counter Counter

    var wg sync.WaitGroup
    wg.Add(10)

    // 启动10个goroutine
    for i := 0; i < 10; i++ {
        go func() {
            defer wg.Done()
            // 执行10万次累加
            for j := 0; j < 100000; j++ {
                counter.Incr() // 受到锁保护的方法
            }
        }()
    }
    wg.Wait()
    fmt.Println(counter.Count())
}

// 线程安全的计数器类型
type Counter struct {
    CounterType int
    Name        string

    mu    sync.Mutex
    count uint64
}

// 加1的方法，内部使用互斥锁保护
func (c *Counter) Incr() {
    c.mu.Lock()
    c.count++
    c.mu.Unlock()
}

// 得到计数器的值，也需要锁保护
func (c *Counter) Count() uint64 {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.count
}

// CAS操作，当时还没有抽象出atomic包
func cas(val *int32, old, new int32) bool
func semacquire(*int32)
func semrelease(*int32)
// 互斥锁的结构，包含两个字段
type Mutex struct {
	key  int32 // 锁是否被持有的标识
	sema int32 // 信号量专用，用以阻塞/唤醒goroutine
}

// 保证成功在 val 上增加 delta 的值
func xadd(val *int32, delta int32) (new int32) {
	for {
		v := *val
		if cas(val, v, v+delta) {
			return v + delta
		}
	}
	panic("unreached")
}

// 请求锁
func (m *Mutex) Lock() {
	if xadd(&m.key, 1) == 1 { // 标识加1，如果等于1，成功获取到锁
		return
	}
	semacquire(&m.sema) // 否则阻塞等待
}

func (m *Mutex) Unlock() {
	if xadd(&m.key, -1) == 0 { // 将标识减去1，如果等于0，则没有其它等待者
		return
	}
	semrelease(&m.sema) // 唤醒其它阻塞的goroutine
}

func (f *Foo) Bar() {
    f.mu.Lock()
    defer f.mu.Unlock()


    if f.count < 1000 {
        f.count += 3
        return
    }


    f.count++
    return
}

type Mutex struct {
	state int32
	sema  uint32
}

const (
	mutexLocked = 1 << iota // mutex is locked
	mutexWoken
	mutexWaiterShift = iota
)

func (m *Mutex) Lock() {
	// Fast path: 幸运 case，能够直接获取到锁
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}

	awoke := false // 每个 goroutine 的局部变量
	for {
		old := m.state
		new := old | mutexLocked // 新状态加锁，默认都设置「想要持有锁」标志
		if old&mutexLocked != 0 {
			new = old + 1<<mutexWaiterShift // 等待者数量加一
		}
		if awoke {
			// 如果是从 runtime.Semacquire 被唤醒的 goroutine（awoke == true）
            // 就要去掉 mutexWoken，让下一个等待者可以被唤醒。
			new &^= mutexWoken
		}
		if atomic.CompareAndSwapInt32(&m.state, old, new) { // 设置新状态，这里成功设置，不代表抢到了锁
			if old & mutexLocked == 0 { // 锁原状态未加锁，说明抢到了锁
				break
			}
			runtime.Semacquire(&m.sema) // 锁仍被占用，自己要阻塞在信号量上
			awoke = true
		}
	}
}

func (m *Mutex) Unlock() {
	// Fast path: drop lock bit.
	new := atomic.AddInt32(&m.state, -mutexLocked) // 去掉锁标志
	if (new+mutexLocked)&mutexLocked == 0 {        // 本来就没有加锁
		panic("sync: unlock of unlocked mutex")
	}

	old := new
	for {
		if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken) != 0 { // 没有等待者，或者有唤醒的waiter，或者锁原来已加锁
			return
		}
		new = (old - 1<<mutexWaiterShift) | mutexWoken // 新状态，准备唤醒goroutine，并设置唤醒标志
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			runtime.Semrelease(&m.sema)
			return
		}
		old = m.state
	}
}

func (m *Mutex) Lock() {
	// Fast path: 幸运之路，正好获取到锁
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}

	awoke := false
	iter := 0
	for { // 不管是新来的请求锁的goroutine, 还是被唤醒的goroutine，都不断尝试请求锁
		old := m.state            // 先保存当前锁的状态
		new := old | mutexLocked  // 新状态设置加锁标志
		if old&mutexLocked != 0 { // 锁还没被释放
			if runtime_canSpin(iter) { // 还可以自旋
				if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
					atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
					awoke = true
				}
				runtime_doSpin()
				iter++
				continue // 自旋，再次尝试请求锁
			}
			new = old + 1<<mutexWaiterShift
		}
		if awoke { // 唤醒状态
			if new&mutexWoken == 0 {
				panic("sync: inconsistent mutex state")
			}
			new &^= mutexWoken // 新状态清除唤醒标记
		}
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			if old&mutexLocked == 0 { // 旧状态锁已释放，新状态成功持有了锁，直接返回
				break
			}
			runtime_Semacquire(&m.sema) // 阻塞等待
			awoke = true                // 被唤醒
			iter = 0
		}
	}
}

if runtime_canSpin(iter) { // 还可以自旋
    if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
    atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
        awoke = true
    }
    runtime_doSpin()
    iter++
    continue // 自旋，再次尝试请求锁
}

if new&mutexWoken == 0 {
    panic("sync: inconsistent mutex state")
}

type Mutex struct {
	state int32
	sema  uint32
}

const (
	mutexLocked = 1 << iota // mutex is locked
	mutexWoken
	mutexStarving    // 从 state 字段中分出一个饥饿标记
	mutexWaiterShift = iota

	starvationThresholdNs = 1e6
)

func (m *Mutex) Lock() {
	// Fast path: 幸运之路，一下就获取到了锁
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}
	// Slow path：缓慢之路，尝试自旋竞争或饥饿状态下饥饿goroutine竞争
	m.lockSlow()
}

func (m *Mutex) lockSlow() {
	var waitStartTime int64
	starving := false // 此goroutine的饥饿标记
	awoke := false    // 唤醒标记
	iter := 0         // 自旋次数
	old := m.state    // 当前的锁的状态
	for {
		// 锁是非饥饿状态，锁还没被释放，尝试自旋
		if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
			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
		if old&mutexStarving == 0 {
			new |= mutexLocked // 非饥饿状态，加锁
		}
		if old&(mutexLocked|mutexStarving) != 0 {
			new += 1 << mutexWaiterShift // waiter数量加1
		}
		if starving && old&mutexLocked != 0 {
			new |= mutexStarving // 设置饥饿状态
		}
		if awoke {
			if new&mutexWoken == 0 {
				throw("sync: inconsistent mutex state")
			}
			new &^= mutexWoken // 新状态清除唤醒标记
		}
		// 成功设置新状态
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			// 原来锁的状态已释放，并且不是饥饿状态，正常请求到了锁，返回
			if old&(mutexLocked|mutexStarving) == 0 {
				break // locked the mutex with CAS
			}
			// 处理饥饿状态

			// 如果以前就在队列里面，加入到队列头
			queueLifo := waitStartTime != 0
			if waitStartTime == 0 {
				waitStartTime = runtime_nanotime()
			}
			// 阻塞等待
			runtime_SemacquireMutex(&m.sema, queueLifo, 1)
			// 唤醒之后检查锁是否应该处于饥饿状态
			starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
			old = m.state
			// 如果锁已经处于饥饿状态，直接抢到锁，返回
			if old&mutexStarving != 0 {
				if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
					throw("sync: inconsistent mutex state")
				}
				// 有点绕，加锁并且将waiter数减1
				delta := int32(mutexLocked - 1<<mutexWaiterShift)
				if !starving || old>>mutexWaiterShift == 1 {
					delta -= mutexStarving // 最后一个waiter或者已经不饥饿了，清除饥饿标记
				}
				atomic.AddInt32(&m.state, delta)
				break
			}
			awoke = true
			iter = 0
		} else {
			old = m.state
		}
	}
}

func (m *Mutex) Unlock() {
	// Fast path: drop lock bit.
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if new != 0 {
		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 old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
				return
			}
			new = (old - 1<<mutexWaiterShift) | mutexWoken
			if atomic.CompareAndSwapInt32(&m.state, old, new) {
				runtime_Semrelease(&m.sema, false, 1)
				return
			}
			old = m.state
		}
	} else {
		runtime_Semrelease(&m.sema, true, 1)
	}
}

if old&(mutexLocked|mutexStarving) == mutexLocked ...

old & mutexLocked == mutexLocked // 锁被占用
&&
old & mutexStarving == mutexLocked // 处于饥饿

if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
    throw("sync: inconsistent mutex state")
}

delta := int32(mutexLocked - 1<<mutexWaiterShift)

if !starving || old>>mutexWaiterShift == 1 {
    delta -= mutexStarving // 最后一个waiter或者已经不饥饿了，清除饥饿标记
}

atomic.AddInt32(&m.state, delta)
break

func foo() {
    var mu sync.Mutex
    mu.Lock()
    defer mu.Unlock()
    fmt.Println("hello world!")
}

package main

import (
	"fmt"
	"sync"
)

type Counter struct {
	sync.Mutex
	Count int
}

func main() {
	var c Counter
	c.Lock()
	defer c.Unlock()
	c.Count++
	foo(c)
}

// 这里 Counter 的参数是通过复制的方式传入的.
func foo(c Counter) {
	c.Lock()
	defer c.Unlock()
	fmt.Println("in foo")
}

$ go vet copy.go 
# command-line-arguments
# [command-line-arguments]
./copy.go:18:6: call of foo copies lock value: command-line-arguments.Counter
./copy.go:22:12: foo passes lock by value: command-line-arguments.Counter

var lockerType *types.Interface

// Construct a sync.Locker interface type.
func init() {
	nullary := types.NewSignature(nil, nil, nil, false) // func()
	methods := []*types.Func{
		types.NewFunc(token.NoPos, nil, "Lock", nullary),
		types.NewFunc(token.NoPos, nil, "Unlock", nullary),
	}
	lockerType = types.NewInterface(methods, nil).Complete()
}

package main

import (
        "fmt"
        "sync"
)

func foo(l sync.Locker) {
        fmt.Println("in foo")
        l.Lock()
        bar(l)
        l.Unlock()
}

func bar(l sync.Locker) {
        l.Lock()
        fmt.Println("in bar")
        l.Unlock()
}

func main() {
        l := &sync.Mutex{}
        foo(l)
}

$ go run ReentrantLock.go 
in foo
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [sync.Mutex.Lock]:
internal/sync.runtime_SemacquireMutex(0xc000078e60?, 0xa?, 0x559660?)
        /home/going/go/go1.24.0/src/runtime/sema.go:95 +0x25
internal/sync.(*Mutex).lockSlow(0xc0000100f0)
        /home/going/go/go1.24.0/src/internal/sync/mutex.go:149 +0x15d
internal/sync.(*Mutex).Lock(...)
        /home/going/go/go1.24.0/src/internal/sync/mutex.go:70
sync.(*Mutex).Lock(0xc0000100f8?)
        /home/going/go/go1.24.0/src/sync/mutex.go:46 +0x2c
main.bar({0x4da100, 0xc0000100f0})
        /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.3mutex3/ReentrantLock.go:16 +0x22
main.foo({0x4da100, 0xc0000100f0})
        /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.3mutex3/ReentrantLock.go:11 +0x73
main.main()
        /home/going/golang/src/github.com/LiangNing7/conc/mutex/1.3mutex3/ReentrantLock.go:23 +0x29
exit status 2

goroutine 1 [running]:
main.main()
        ....../main.go:19 +0xb1

func GoID() int {
	var buf [64]byte
	n := runtime.Stack(buf[:], false)
	// 得到id字符串
	idField := strings.Fields(strings.TrimPrefix(string(buf[:n]), "goroutine "))[0]
	id, err := strconv.Atoi(idField)
	if err != nil {
		panic(fmt.Sprintf("cannot get goroutine id: %v", err))
	}
	return id
}

$ go get github.com/petermattis/goid

package mutex

import (
	"fmt"
	"sync"
	"sync/atomic"

	"github.com/petermattis/goid"
)

// RecursiveMutex 包装了一个 Mutex，实现可重入.
type RecursiveMutex struct {
	sync.Mutex
	owner     int64 // 当前持有锁的 goroutine id.
	recursion int32 // 这个 goroutine 重入次数.
}

func (m *RecursiveMutex) Lock() {
	gid := goid.Get()
	// 如果当前持有锁的 goroutine 就是这次调用的 goroutine,说明是重入.
	if atomic.LoadInt64(&m.owner) == gid {
		m.recursion++
		return
	}

	m.Mutex.Lock()
	// 获得锁的 goroutine 第一次调用，记录下它的 goroutine id,
	// 调用次数加 1.
	atomic.StoreInt64(&m.owner, gid)
	m.recursion = 1
}

func (m *RecursiveMutex) Unlock() {
	gid := goid.Get()
	// 非持有锁的 goroutine 尝试释放锁，错误的使用.
	if atomic.LoadInt64(&m.owner) != gid {
		panic(fmt.Sprintf("wrong the owner(%d): %d!", m.owner, gid))
	}
	// 调用次数减 1.
	m.recursion--
	if m.recursion != 0 { // 如果这个 goroutine 还没完全释放，则直接返回.
		return
	}
	// 此时 goroutine 的最后一次调用，需要释放锁.
	atomic.StoreInt64(&m.owner, -1)
	m.Mutex.Unlock()
}

package mutex

import (
	"fmt"
	"sync"
	"sync/atomic"
)

// Token 方式的递归锁.
type TokenRecursiveMutex struct {
	sync.Mutex
	token     int64
	recursion int32
}

// 请求锁，需要传入 token.
func (m *TokenRecursiveMutex) Lock(token int64) {
	// 如果传入的token和持有锁的token一致，说明是递归调用
	if atomic.LoadInt64(&m.token) == token {
		m.recursion++
		return
	}
	m.Mutex.Lock() // 传入的 token 不一致
	// 抢到锁之后记录这个 token.
	atomic.StoreInt64(&m.token, token)
	m.recursion = 1
}

// 释放锁.
func (m *TokenRecursiveMutex) Unlock(token int64) {
	// 释放其他 token 持有的锁
	if atomic.LoadInt64(&m.token) != token {
		panic(fmt.Sprintf("wrong the owner(%d): %d!)", m.token, token))
	}
	// 当前持有这个锁的 token 释放锁.
	m.recursion--
	if m.recursion != 0 {
		return
	}
	// 没有递归调用了，释放锁.
	atomic.StoreInt64(&m.token, 0)
	m.Mutex.Unlock()
}

package mutex

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

// 复制 Mutex 定义的常量.
const (
	mutexLocked      = 1 << iota // 1, 加锁标志位置
	mutexWoken                   // 2, 唤醒标志位置.
	mutexStarving                // 4, 锁饥饿标识位置.
	mutexWaiterShift = iota      // 标识 waiter 的起始 bit 位置。
)

// 扩展一个 Mutex 结构.
type Mutex struct {
	sync.Mutex
}

// TryLock() 尝试获取锁.
func (m *Mutex) TryLock() bool {
	// 如果能成功抢到锁.
	if atomic.CompareAndSwapInt32((*int32)(unsafe.Pointer(&m.Mutex)), 0, mutexLocked) {
		return true
	}

	// 如果处于唤醒、加锁或者饥饿状态，这次请求就不参与了，返回 false.
	old := atomic.LoadInt32((*int32)(unsafe.Pointer(&m.Mutex)))
	if old&(mutexLocked|mutexStarving|mutexWoken) != 0 {
		return false
	}

	// 尝试在竞争状态加锁.
	new := old | mutexLocked
	return atomic.CompareAndSwapInt32((*int32)(unsafe.Pointer(&m.Mutex)), old, new)
}

package mutex

import (
	"fmt"
	"math/rand"
	"testing"
	"time"
)

func TestTryLock(t *testing.T) {
	var mu Mutex

	go func() {
		mu.Lock()
		time.Sleep(time.Duration(rand.Intn(2)) * time.Second)
		mu.Unlock()
	}()

	time.Sleep(time.Second)

	ok := mu.TryLock()
	if ok {
		fmt.Println("got the lock")
		// do something.
		mu.Unlock()
		return
	}

	// 没有获取到
	fmt.Println("can't get the lock")
}

type Mutex struct {
    state int32
    sema  uint32
}

package mutex

import (
	"sync/atomic"
	"unsafe"
)

// Count 持有和等待这把锁的 goroutine 的总数
func (m *Mutex) Count() int {
	// 获取 state 字段的值.
	v := atomic.LoadInt32((*int32)(unsafe.Pointer(&m.Mutex)))
	v = v>>mutexWaiterShift + (v & mutexLocked)
	return int(v)
}

// IsLocked 锁是否被持有.
func (m *Mutex) IsLocked() bool {
	state := atomic.LoadInt32((*int32)(unsafe.Pointer(&m.Mutex)))
	return state&mutexLocked == mutexLocked
}

// IsWoken 是否有等待者被唤醒.
func (m *Mutex) IsWoken() bool {
	state := atomic.LoadInt32((*int32)(unsafe.Pointer(&m.Mutex)))
	return state&mutexLocked == mutexWoken
}

// IsStarving 锁是否饥饿.
func (m *Mutex) IsStarving() bool {
	state := atomic.LoadInt32((*int32)(unsafe.Pointer(&m.Mutex)))
	return state&mutexStarving == mutexStarving
}

package mutex

import (
	"sync"
)

type SliceQueue struct {
	data []any
	mu   sync.Mutex
}

func NewSlcieQueue(n int) (q *SliceQueue) {
	return &SliceQueue{data: make([]any, 0, n)}
}

// Enqueue 把值放在队尾.
func (q *SliceQueue) Enqueue(v any) {
	q.mu.Lock()
	defer q.mu.Unlock()
	q.data = append(q.data, v)
}

// Dequeue 去掉对头并返回.
func (q *SliceQueue) Dequeue() any {
	q.mu.Lock()
	defer q.mu.Unlock()

	if len(q.data) == 0 {
		q.mu.Unlock()
		return nil
	}
	v := q.data[0]
	q.data = q.data[1:]
	return v
}