原文：https://zhuanlan.zhihu.com/p/509148906
老规矩相信大家已经知道 select 应用的特性，这里主要是介绍 select 的底层原理。
select 底层原理主要分为两部：
- select 语句优化
- selectgo
select 语句优化
编译阶段，编译器会根据 select 中 case 的不同，会对控制语句进行优化。这一过程发生在:
// src/cmd/compile/internal/walk/select.go
func walkSelectCases(cases []*ir.CommClause) []ir.Node {
...
}
需要强调一下的是 default 也算是一个 case。
空 select
即 select{} ，语法下的优化:
if ncas == 0 {
return []ir.Node{mkcallstmt("block")}
}
mkcallstmt("block") 就直接转换成了成了 runtime.block() 函数:
// src/runtime/select.go
func block() {
gopark(nil, nil, waitReasonSelectNoCases, traceEvGoStop, 1) // forever
}
gopark 函数咱们应该很清楚作用了。
(不清楚的，可以回看 GMP调度 那篇文章)
单一case
还有只有一个 case的情况：
select {
case v := <-ch:
}通过 walkSelectCases() 里面这段逻辑
if ncas == 1 {
...
}编译器就会将select去掉，直接改写成接收通道的方式：
v := <- ch非阻塞
还只有一共两个选择， 一个是 case，一个是 default的情况：
if ncas == 2 && dflt != nil {
...
}
编译器优化结果如下：
// select {
// case c <- v:
// ... foo
// default:
// ... bar
// }
//
// as
//
// if selectnbsend(c, v) {
// ... foo
// } else {
// ... bar
// }
//
func selectnbsend(c *hchan, elem unsafe.Pointer) (selected bool) {
return chansend(c, elem, false, getcallerpc())
}
// select {
// case v = <-c:
// ... foo
// default:
// ... bar
// }
//
// as
//
// if selectnbrecv(&v, c) {
// ... foo
// } else {
// ... bar
// }
//
func selectnbrecv(elem unsafe.Pointer, c *hchan) (selected bool) {
selected, _ = chanrecv(c, elem, false)
return
}
// select {
// case v, ok = <-c:
// ... foo
// default:
// ... bar
// }
//
// as
//
// if c != nil && selectnbrecv2(&v, &ok, c) {
// ... foo
// } else {
// ... bar
// }
//
func selectnbrecv2(elem unsafe.Pointer, received *bool, c *hchan) (selected bool) {
// TODO(khr): just return 2 values from this function, now that it is in Go.
selected, *received = chanrecv(c, elem, false)
return
}我们看到 selectnbsend() 或者 selectnbrecv() / selectnbrecv2()，都调用的是 我们在 channel 那一章节的 介绍的 发送/接收函数。但不同的是，走的的是非阻塞 channel 逻辑，即 block 参数为 false。
selectgo
其他情况的写法，就是真正走到 select 的源码逻辑中。从 func walkSelectCases() 中可以看到，selectgo 也放到了语法节点中：
func walkSelectCases(cases []*ir.CommClause) []ir.Node {
...
fn := typecheck.LookupRuntime("selectgo")
var fnInit ir.Nodes
r.Rhs = []ir.Node{mkcall1(fn, fn.Type().Results(), &fnInit, bytePtrToIndex(selv, 0), bytePtrToIndex(order, 0), pc0, ir.NewInt(int64(nsends)), ir.NewInt(int64(nrecvs)), ir.NewBool(dflt == nil))}
...
}
接下来咱们就来拆分 selecgo 函数中的逻辑，先看一开始：
// src/runtime/select.go
// selectgo implements the select statement.
//
// cas0 points to an array of type [ncases]scase, and order0 points to
// an array of type [2*ncases]uint16 where ncases must be <= 65536.
// Both reside on the goroutine's stack (regardless of any escaping in
// selectgo).
//
// For race detector builds, pc0 points to an array of type
// [ncases]uintptr (also on the stack); for other builds, it's set to
// nil.
//
// selectgo returns the index of the chosen scase, which matches the
// ordinal position of its respective select{recv,send,default} call.
// Also, if the chosen scase was a receive operation, it reports whether
// a value was received.
func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends, nrecvs int, block bool) (int, bool) {
...
// NOTE: In order to maintain a lean stack size, the number of scases
// is capped at 65536.
cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))
order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))
ncases := nsends + nrecvs
scases := cas1[:ncases:ncases]
pollorder := order1[:ncases:ncases]
lockorder := order1[ncases:][:ncases:ncases]
...
}
从注释可以看出各个参数的意思，以及 selectgo 返回的是case的索引，即该执行哪个case 下的逻辑。重点关注一下 case0 和 order0。
case0 的结构体就是 scase :
type scase struct {
c *hchan // chan
elem unsafe.Pointer // data element
}
本文使用的是go version: 1.17.9， 该版本下，scase结构体 只有两个字段即一个通道，以及发送/接收的值。
order0 就是我们的 case 数组，会被转化成scases 和 order1，最终会被转换成 pollorder 和 lockorder 。
pollorder 存放的是： case中元素的索引。
lockorder 存放的是：根据chan在堆区的地址顺序排序(大根堆排序)的所有chan。
(由于每个 case 中的 c 都会上锁，又按地址顺序排序，用顺序锁有效避免协程并发带来的死锁问题。)
还有一段注释很重要，就是 case数量不能超过 65536。
然后就是 selectgo() 的执行逻辑。虽然代码很多，但总结起来主要就干4件事：
- 将case乱序后，加入lockerorder中。
- 第一次循环执行 pollorder 中已经乱序了的 case -- 对就绪的channel进行 发送/接收 。
- 第二次循环执行 lockorder，将当前 goroutine 加入到 所有 case 的 channel 发送/接收队列中( sendq/recvq)， 等待被唤醒。
- goroutine 被唤醒之后，找到满足条件的 channel并处理。
case 乱序
我们再来具体看三处逻辑的源码。先看事情1：
pollorder := order1[:ncases:ncases]
lockorder := order1[ncases:][:ncases:ncases]
...
norder := 0
// 第一个for
for i := range scases {
cas := &scases[i]
// Omit cases without channels from the poll and lock orders.
if cas.c == nil {
cas.elem = nil // allow GC
continue
}
j := fastrandn(uint32(norder + 1)) // fastrandn 随机函数
pollorder[norder] = pollorder[j]
pollorder[j] = uint16(i)
norder++
}
pollorder = pollorder[:norder]
lockorder = lockorder[:norder]
...
// 第二个for
for i := range lockorder {
j := i
// Start with the pollorder to permute cases on the same channel.
c := scases[pollorder[i]].c
for j > 0 && scases[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() {
k := (j - 1) / 2
lockorder[j] = lockorder[k]
j = k
}
lockorder[j] = pollorder[i]
}
// 第三个for
for i := len(lockorder) - 1; i >= 0; i-- {
o := lockorder[i]
c := scases[o].c
lockorder[i] = lockorder[0]
j := 0
for {
k := j*2 + 1
if k >= i {
break
}
if k+1 < i && scases[lockorder[k]].c.sortkey() < scases[lockorder[k+1]].c.sortkey() {
k++
}
if c.sortkey() < scases[lockorder[k]].c.sortkey() {
lockorder[j] = lockorder[k]
j = k
continue
}
break
}
lockorder[j] = o
}
...
sellock(scases, lockorder)
其中有三个 for 的逻辑：
- 第一个for:
通过fastrandn()打乱 pollorder的顺序。 - 第二个for:
将pollorder中的 case 复制到 lockorder 中。 - 第三个for:
再将lockorder中的 case 按照其chan在堆区的地址顺序进行排序。
然后将 case 中 channel都上锁。
有就绪channel
事情2 对准备就绪的channel进行接收/发送:
for _, casei := range pollorder {
casi = int(casei)
cas = &scases[casi]
c = cas.c
if casi >= nsends {
sg = c.sendq.dequeue()
if sg != nil {
goto recv
}
if c.qcount > 0 {
goto bufrecv
}
if c.closed != 0 {
goto rclose
}
} else {
if raceenabled {
racereadpc(c.raceaddr(), casePC(casi), chansendpc)
}
if c.closed != 0 {
goto sclose
}
sg = c.recvq.dequeue()
if sg != nil {
goto send
}
if c.qcount < c.dataqsiz {
goto bufsend
}
}
}
我们看到通过 if casi >= nsends 来判断进入接收逻辑，还是发送逻辑。
(我们通过这里casi >= nsends 反推scases 中所有 case 的排序：接收类型的 case 的 idx 排在 发送了类型case 之后)
goto 的逻辑就比较简单了，就是满足条件后的执行。执行逻辑跟 channel 里面源码几乎一样，这里就不详细说明了。
阻塞，加入等待队列
事情3:
gp = getg()
if gp.waiting != nil {
throw("gp.waiting != nil")
}
nextp = &gp.waiting
for _, casei := range lockorder {
casi = int(casei)
cas = &scases[casi]
c = cas.c
sg := acquireSudog()
sg.g = gp
sg.isSelect = true
// No stack splits between assigning elem and enqueuing
// sg on gp.waiting where copystack can find it.
sg.elem = cas.elem
sg.releasetime = 0
if t0 != 0 {
sg.releasetime = -1
}
sg.c = c
// Construct waiting list in lock order.
*nextp = sg
nextp = &sg.waitlink
if casi < nsends {
c.sendq.enqueue(sg)
} else {
c.recvq.enqueue(sg)
}
}
// wait for someone to wake us up
gp.param = nil
// Signal to anyone trying to shrink our stack that we're about
// to park on a channel. The window between when this G's status
// changes and when we set gp.activeStackChans is not safe for
// stack shrinking.
atomic.Store8(&gp.parkingOnChan, 1)
gopark(selparkcommit, nil, waitReasonSelect, traceEvGoBlockSelect, 1)
gp.activeStackChans = false
这里只强调一点 sg.c = c 等待唤醒用的数据(sudog) ，绑定了case 下的channel。
相信看了这篇文章后，这里的逻辑应该很熟悉了。
xiaoxlm：深入golang -- channel1 赞同 · 0 评论文章
唤醒
最后就是被唤醒后：
主要的逻辑就是这一段:
sellock(scases, lockorder)
...
sg = (*sudog)(gp.param)
...
sglist = gp.waiting
...
for _, casei := range lockorder {
k = &scases[casei]
if sg == sglist {
// sg has already been dequeued by the G that woke us up.
casi = int(casei)
cas = k
caseSuccess = sglist.success
if sglist.releasetime > 0 {
caseReleaseTime = sglist.releasetime
}
} else {
c = k.c
if int(casei) < nsends {
c.sendq.dequeueSudoG(sglist)
} else {
c.recvq.dequeueSudoG(sglist)
}
}
sgnext = sglist.waitlink
sglist.waitlink = nil
releaseSudog(sglist) // 释放
sglist = sgnext // 移动 sglist
}
...
selunlock(scases, lockorder)
goto retc
...sg = (*sudog)(gp.param) 这里的sg，事情3中插入的 sudog， 然后对比所有 case 中的 sudog地址 if sg == sglist直到找到，最后解锁所有channel，返回对应的 case 索引。
没有被用到的 sudog 会被释放掉，并移出相应的等待队列。
总结
编译器会根据不同的写法来优化代码。
selectgo 索然代码繁多，但主要干的就两件：
- 顺序锁住全部 channel 防止 goroutine 并发加锁导致死锁问题。
2. 公平地遍历所有通道。
然后就是如果有通道就绪，就执行通道的相关逻辑，最后返回要执行的 case 索引。
最后友情提示一下，select 一般是和 channel 配合使用的，会看到很多调用 channel 的底层函数。所以最好结合 channel 这一章节一起看。
标签：case,--,golang,scases,channel,lockorder,sg,select From： https://www.cnblogs.com/liujiacai/p/17095891.html