1. // Go 语言中暴露的 semaphore 实现 
2. // 具体的用法是提供 sleep 和 wakeup 原语 
3. // 以使其能够在其它同步原语中的竞争情况下使用 
4. // 因此这里的 semaphore 和 Linux 中的 futex 目标是一致的 
5. // 只不过语义上更简单一些 
6. // 
7. // 也就是说，不要认为这些是信号量 
8. // 把这里的东西看作 sleep 和 wakeup 实现的一种方式 
9. // 每一个 sleep 都会和一个 wakeup 配对 
10. // 即使在发生 race 时，wakeup 在 sleep 之前时也是如此 
11. // 
12. // See Mullender and Cox, “Semaphores in Plan 9,'' 
13. // http://swtch.com/semaphore.pdf 
14.  
15. // 为 sync.Mutex 准备的异步信号量 
16.  
17. // semaRoot 持有一棵 地址各不相同的 sudog(s.elem) 的平衡树 
18. // 每一个 sudog 都反过来指向(通过 s.waitlink)一个在同一个地址上等待的其它 sudog 们 
19. // 同一地址的 sudog 的内部列表上的操作时间复杂度都是 O(1)。顶层 semaRoot 列表的扫描 
20. // 的时间复杂度是 O(log n)，n 是被哈希到同一个 semaRoot 的不同地址的总数，每一个地址上都会有一些 goroutine 被阻塞。 
21. // 访问 golang.org/issue/17953 来查看一个在引入二级列表之前性能较差的程序样例，test/locklinear.go 
22. // 中有一个复现这个样例的测试 
23. type semaRoot struct { 
24.     lock  mutex 
25.     treap *sudog // root of balanced tree of unique waiters. 
26.     nwait uint32 // Number of waiters. Read w/o the lock. 
27. } 
28.  
29. // Prime to not correlate with any user patterns. 
30. const semTabSize = 251 
31.  
32. var semtable [semTabSize]struct { 
33.     root semaRoot 
34.     pad  [sys.CacheLineSize – unsafe.Sizeof(semaRoot{})]byte 
35. } 
36.  
37. func semroot(addr *uint32) *semaRoot { 
38.     return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root 
39. } 

1. ┌─────┬─────┬─────┬─────┬─────┬────────────────────────┬─────┐                  
2. │  0  │  1  │  2  │  3  │  4  │         …..          │ 250 │                  
3. └─────┴─────┴─────┴─────┴─────┴────────────────────────┴─────┘                  
4.    │                                                      │                     
5.    │                                                      │                     
6.    └──┐                                                   └─┐                   
7.       │                                                     │                   
8.       │                                                     │                   
9.       ▼                                                     ▼                   
10.  ┌─────────┐                                           ┌─────────┐              
11.  │ struct  │                                           │ struct  │              
12.  ├─────────┴─────────┐                                 ├─────────┴─────────┐    
13.  │   root semaRoot   │──┐                              │   root semaRoot   │──┐ 
14.  ├───────────────────┤  │                              ├───────────────────┤  │ 
15.  │        pad        │  │                              │        pad        │  │ 
16.  └───────────────────┘  │                              └───────────────────┘  │ 
17.                         │                                                     │ 
18.        ┌────────────────┘                                    ┌────────────────┘ 
19.        │                                                     │                  
20.        │                                                     │                  
21.        ▼                                                     ▼                  
22.  ┌──────────┐                                          ┌──────────┐             
23.  │ semaRoot │                                          │ semaRoot │             
24.  ├──────────┴────────┐                                 ├──────────┴────────┐    
25.  │    lock mutex     │                                 │    lock mutex     │    
26.  ├───────────────────┤                                 ├───────────────────┤    
27.  │   treap *sudog    │                                 │   treap *sudog    │    
28.  ├───────────────────┤                                 ├───────────────────┤    
29.  │   nwait uint32    │                                 │   nwait uint32    │    
30.  └───────────────────┘                                 └───────────────────┘ 

treap 结构:

1.                                  ┌──────────┐                                     
2.                             ┌─┬─▶│  sudog   │                                     
3.                             │ │  ├──────────┴────────────┐                        
4.       ┌─────────────────────┼─┼──│      prev *sudog      │                        
5.       │                     │ │  ├───────────────────────┤                        
6.       │                     │ │  │      next *sudog      │────┐                   
7.       │                     │ │  ├───────────────────────┤    │                   
8.       │                     │ │  │     parent *sudog     │    │                   
9.       │                     │ │  ├───────────────────────┤    │                   
10.       │                     │ │  │  elem unsafe.Pointer  │    │                   
11.       │                     │ │  ├───────────────────────┤    │                   
12.       │                     │ │  │     ticket uint32     │    │                   
13.       │                     │ │  └───────────────────────┘    │                   
14.       │                     │ │                               │                   
15.       │                     │ │                               │                   
16.       │                     │ │                               │                   
17.       │                     │ │                               │                   
18.       │                     │ │                               │                   
19.       │                     │ │                               │                   
20.       ▼                     │ │                               ▼                   
21. ┌──────────┐                │ │                         ┌──────────┐              
22. │  sudog   │                │ │                         │  sudog   │              
23. ├──────────┴────────────┐   │ │                         ├──────────┴────────────┐ 
24. │      prev *sudog      │   │ │                         │      prev *sudog      │ 
25. ├───────────────────────┤   │ │                         ├───────────────────────┤ 
26. │      next *sudog      │   │ │                         │      next *sudog      │ 
27. ├───────────────────────┤   │ │                         ├───────────────────────┤ 
28. │     parent *sudog     │───┘ └─────────────────────────│     parent *sudog     │ 
29. ├───────────────────────┤                               ├───────────────────────┤ 
30. │  elem unsafe.Pointer  │                               │  elem unsafe.Pointer  │ 
31. ├───────────────────────┤                               ├───────────────────────┤ 
32. │     ticket uint32     │                               │     ticket uint32     │ 
33. └───────────────────────┘                               └───────────────────────┘ 

在这个 treap 结构里，从 elem 的视角(其实就是 lock 的 addr)来看，这个结构是个二叉搜索树。从 ticket 的角度来看，整个结构就是一个小顶堆。

所以才叫树堆(treap)。

相同 addr，即对同一个 mutex 上锁的 g，会阻塞在同一个地址上。这些阻塞在同一个地址上的 goroutine 会被打包成 sudog，组成一个链表。用 sudog 的 waitlink 相连:

1. ┌──────────┐                         ┌──────────┐                          ┌──────────┐              
2. │  sudog   │                  ┌─────▶│  sudog   │                   ┌─────▶│  sudog   │              
3. ├──────────┴────────────┐     │      ├──────────┴────────────┐      │      ├──────────┴────────────┐ 
4. │    waitlink *sudog    │─────┘      │    waitlink *sudog    │──────┘      │    waitlink *sudog    │ 
5. ├───────────────────────┤            ├───────────────────────┤             ├───────────────────────┤ 
6. │    waittail *sudog    │            │    waittail *sudog    │             │    waittail *sudog    │ 
7. └───────────────────────┘            └───────────────────────┘             └───────────────────────┘ 

中间的元素的 waittail 都会指向最后一个元素:

1. ┌──────────┐                                                                                            
2. │  sudog   │                                                                                            
3. ├──────────┴────────────┐                                                                               
4. │    waitlink *sudog    │                                                                               
5. ├───────────────────────┤                                                                               
6. │    waittail *sudog    │───────────────────────────────────────────────────────────┐                   
7. └───────────────────────┘                                                           │                   
8.                                   ┌──────────┐                                      │                   
9.                                   │  sudog   │                                      │                   
10.                                   ├──────────┴────────────┐                         │                   
11.                                   │    waitlink *sudog    │                         │                   
12.                                   ├───────────────────────┤                         │                   
13.                                   │    waittail *sudog    │─────────────────────────┤                   
14.                                   └───────────────────────┘                         ▼                   
15.                                                                               ┌──────────┐              
16.                                                                               │  sudog   │              
17.                                                                               ├──────────┴────────────┐ 
18.                                                                               │    waitlink *sudog    │ 
19.                                                                               ├───────────────────────┤ 
20.                                                                               │    waittail *sudog    │ 
21.                                                                               └───────────────────────┘ 

对外封装

在 sema.go 里实现的内容，用 go:linkname 导出给 sync、poll 库来使用，也是在链接期做了些手脚:

1. //go:linkname sync_runtime_Semacquire sync.runtime_Semacquire 
2. func sync_runtime_Semacquire(addr *uint32) { 
3.     semacquire1(addr, false, semaBlockProfile) 
4. } 
5.  
6. //go:linkname poll_runtime_Semacquire internal/poll.runtime_Semacquire 
7. func poll_runtime_Semacquire(addr *uint32) { 
8.     semacquire1(addr, false, semaBlockProfile) 
9. } 
10.  
11. //go:linkname sync_runtime_Semrelease sync.runtime_Semrelease 
12. func sync_runtime_Semrelease(addr *uint32, handoff bool) { 
13.     semrelease1(addr, handoff) 
14. } 
15.  
16. //go:linkname sync_runtime_SemacquireMutex sync.runtime_SemacquireMutex 
17. func sync_runtime_SemacquireMutex(addr *uint32, lifo bool) { 
18.     semacquire1(addr, lifo, semaBlockProfile|semaMutexProfile) 
19. } 
20.  
21. //go:linkname poll_runtime_Semrelease internal/poll.runtime_Semrelease 
22. func poll_runtime_Semrelease(addr *uint32) { 
23.     semrelease(addr) 
24. }