selectgo
select为golang提供了多路IO复用机制，和其他IO复用一样，用于检测是否有读写事件是否ready。
本文将介绍一下golang的select的用法和实现原理。
实现原理
golang实现select的时候，实际上为每一个case语句定义了一个数据结构，select语句块执行的时候，实际上可以类比成对一个case数组处理的代码块（或者函数），然后程序流程转到选中的case块。
case数据结构
源码包src/runtime/select.go:scase定义了表示case语句的数据结构：
1
2
3
4
5
type scase struct {
c *hchan // chan
kind uint16
elem unsafe.Pointer // data element
}
scase.c表示当前case语句操作的chan指针，这也表明一个case只能监听一个chan。
scase.kind表示当前的chan是可读还是可写channel或者是default。三种类型分别由常量定义：
caseRecv：case语句中尝试读取scase.c中的数据；
caseSend：case语句中尝试向scase.c中写入数据；
caseDefault： default语句
scase.elem表示缓冲区地址，跟据scase.kind不同，有不同的用途：
scase.kind == caseRecv ： scase.elem表示读出channel的数据存放地址；
scase.kind == caseSend ： scase.elem表示将要写入channel的数据存放地址；
select实现逻辑
源码包src/runtime/select.go:selectgo()定义了select选择case的函数：
1
2
3
4
5
6
7
8
9
// selectgo implements the select statement.
//
// *sel is on the current goroutine’s stack (regardless of any
// escaping in selectgo).
//
// selectgo returns the index of the chosen scase, which matches the
// ordinal position of its respective select{recv,send,default} call.
func selectgo(sel *hselect) int {
}
其中数据结构hselect如下：
1
2
3
4
5
6
7
8
9
10
// Select statement header.
// Known to compiler.
// Changes here must also be made in src/cmd/internal/gc/select.go’s selecttype.
type hselect struct {
tcase uint16 // total count of scase[]
ncase uint16 // currently filled scase[]
pollorder *uint16 // case poll order
lockorder *uint16 // channel lock order
scase [1]scase // one per case (in order of appearance)
}
hselect.tcase存的是scase总数。
hselect.pollorder是保存scase的随机后的序列。以达到随机检测case的目的。
hselect.lockorder是保存的channel地址。所有case语句中channel序列，以达到去重防止对channel加锁时重复加锁的目的。
selectgo返回int，表示选中的scase，也就是ready的channel index。
该函数执行逻辑大致如下：
锁定scase语句中所有的channel
按照随机顺序检测scase中的channel是否ready
2.1 如果case可读，则读取channel中数据，解锁所有的channel，然后返回(case index)
2.2 如果case可写，则将数据写入channel，解锁所有的channel，然后返回(case index)
2.3 所有case都未ready，则解锁所有的channel，然后返回（default index）
- 所有case都未ready，且没有default语句
3.1 将当前协程加入到所有channel的等待队列
3.2 当将协程转入阻塞，等待被唤醒
- 唤醒后返回channel对应的case index
4.1 如果是读操作，解锁所有的channel，然后返回(case index)
4.2 如果是写操作，解锁所有的channel，然后返回(case index)
select可以用来管理多个channel的读写，以及实现channel读写timeout等。select并不是以库的形式提供，而是语言级支持的语法特性，因此select的实现主要由编译器和runtime共同完成，本文将重点关注runtime部分。
select语句的执行主要由4个阶段组成，依次是创建select对象，注册所有的case条件，执行select语句，最后释放select对象。这里提到的select对象是底层runtime维护的一个Select结构，这个对象对Go程序来说基本是透明的。后面的内容中，我将称这个select对象为选择器。
选择器内存模型(Select)
这里内存模型主要是描述的选择器在内存是如何布局的，是什么样的数据结构来维护的。源码位于runtime/chan.c中，描述内存模型的函数主要是newselect。newselect就是在内存上创建一个选择器。
描述选择器内存模型最重要的两个结构体定义如下：
struct Scase
{
SudoG sg; // must be first member (cast to Scase)
Hchan* chan; // chan
byte* pc; // return pc
uint16 kind;
uint16 so; // vararg of selected bool
bool* receivedp; // pointer to received bool (recv2)
};
struct Select
{
uint16 tcase; // total count of scase[]
uint16 ncase; // currently filled scase[]
uint16* pollorder; // case poll order
Hchan** lockorder; // channel lock order
Scase scase[1]; // one per case (in order of appearance)
};
Scase描述Go程序select语句中定义的case条件，也就是说Go程序中的一个case在runtime中就是用Scase这个结构来维护的。可以看到Scase中有一个Hchan *chan字段，这个显然就是每个case条件上操作的channel了。
Select就是定义“选择器”的核心结构了，每个字段当然都很重要，不过可以重点关注pollorder、lockorder、scase三个字段。这里先看一下Scase scase[1]这个字段的定义，可以猜到scase字段就是用来存储所有case条件的，但这里却只是定义了一个只有一个元素的数组，这怎么够存储多余1个case的情况呢？？？
此图就是整个选择器的内存模型了，这一整块内存结构其实也是由头部结构+数据结构组成，头部就是Select那一部分，对应上面提到的struct Select，数据结构部分都是由数组构成。
scase就是一个数组，数组元素为Scase类型，存储每个case条件。
lockorder指针指向的也是一个数组，元素为Hchan *类型，存储每个case条件中操作channel。
pollorder是一个uint16的数组.
从头部开始这一整块内存是由一次类malloc（为什么是类malloc，因为Go有自己的内存管理接口，不是采用的普通malloc）调用分配的，然后再将Select头部结构中的lockorder和pollorder两个指针分别指向正确的位置即可。当然，在一口气分配这块内存前，是事先算好了所有需要的内存的大小的。这里特别强调一次malloc分配所有需要的内存，就是想表达除了C/C++外还有哪门语言有这么强的内存控制能力？其他语言（包括Go）在处理这种情况，手法应该差不多都是先New一个主要的对象，然后New这个主要对象字段中需要的对象。当然，你可能会告诉我，这门语言有很好的内存管理系统，不在乎这样的对象创建…呵呵。拥有内存的完全控制能力，也是系统软件大量采用C/C++编写的原因，也是其他语言的实现基本采用C/C++的原因吧。这个问题不能继续扯下去了。
scase字段被定义为1个元素的数组的问题还没有解决。上图展示的是一个有6个case条件的选择器内存模型，可以看到lockorder、pollorder以及scase(黑色部分)都是6个单元的数组。注意，黑色部分的scase的第一个单元位于Select头部结构内存空间中，这个单元就是struct Select中定义的那个只有一个元素的scase数组了，在malloc分配这块内存的时候，scase就只需要少分配一个单元就可以了，所以上图中可以看出只是多加了5个scase的存储单元。这样一来，scase字段和lockorder、pollorder就没有什么两样了，殊途同归。其实，Scase scase[1]字段完全可以定义为Scase *scase嘛，但这样要多浪费一个指针的内存空间。我还是很倾向这种扣字节式的实现方式。
在newselect函数中创建好这块内存空间后，就再也找不到填充scase、lockorder和pollorder三个数组的过程了，也就是创建好内存模型就结束了，还没填数据呢，这是怎么回事？填充选择器其实就是注册case的过程。
到这里，选择器就被创建好了，剩下的就是选择器如何工作了。
注册case条件
了解了选择器的内存布局，也就是创建好了一个选择器，再看如何把所有case条件数据注册到选择器中，重点看一下两个函数吧:
static void
selectsend(Select *sel, Hchan *c, void *pc, void *elem, int32 so)
{
i = sel->ncase;
……………..
sel->ncase = i+1;
cas = &sel->scase[i];
cas->pc = pc;
cas->chan = c;
cas->so = so;
cas->kind = CaseSend;
cas->sg.elem = elem; } 这个selectsend函数就是在碰到case条件是写数据到channel的时候会调用。它会将Go程序中此case上的数据以及channel等信息传给选择器，填充在具体的Scase结构中，完成写channel的case注册。
static void
selectrecv(Select *sel, Hchan *c, void *pc, void *elem, bool *received, int32 so)
{
i = sel->ncase;
sel->ncase = i+1;
cas = &sel->scase[i];
cas->pc = pc;
cas->chan = c;
cas->so = so;
cas->kind = CaseRecv;
cas->sg.elem = elem;
cas->receivedp = received; } selectrecv和selectsend很像，它是在碰到case条件是从一个channel读取数据的时候会被调用，以完成对读channel的case注册。同样，也是事先将channel以及存放数据的内存传递给选择器，填充在一个Scase中。这里由于是等待读取数据，所以是把存储数据的内存地址交给选择器，然后选择器在从channel取到数据后，将数据拷贝到这个内存里。
case条件的注册过程特别简单，没什么复杂的内容，但这部分其实和编译器很相关，比如只有一个case的select可以优化成直接操作channel等。
执行选择器
这部分是select的核心，主要包含选择器是如何管理case条件，如何读写对应的channel。
选择器和channel的交互是由selectgo()这个函数实现的，这个函数有一点小长，不过过程其实很简单的。下面贴一个此函数的代码骨架。
static void*
selectgo(Select **selp)
{
sel = *selp;
// 这里是一个很重要的地方，pollorder数组依次填上每个case的编号[0, n]，然后第二个for就
// 是一个洗牌操作了，将pollorder数组中的编号给随机打乱。目的当然就是为了case条件执行的
// 随机性。
for(i=0; incase; i++)
sel->pollorder[i] = i;
for(i=1; incase; i++) {
……….
}
// 这里又来两个遍历所有case的循环，好蛋疼啊。这次做的事情就是将lockorder中的元素给排序
// 一下。注意，lockorder数组中的元素是每个case对应的channel的地址。
for(i=0; incase; i++) {
…………..
}
for(i=sel->ncase; i-->0; ) {
………
}
// sellock就是遍历lockorder数组，然后将数组中的每个channel给加上锁，因为后面不知道将
// 操作哪个channel，干脆就全部给加上好了？？？真暴力啊。上面对lockorder排序的目的也出来
// 了，就是方便此处加锁的时候，对lockorder中的channel去重。因为两个case完全可能同时操
// 作同一个channel，所以lockorder中可能存储重复的channel了。
sellock(sel);
// 走到这里，总算把准备工作给干完了，将开始真正干活了。 loop:
// 这个for循环就是按pollorder的顺序去遍历所有case，碰到一个可以执行的case后就中断循
// 环。pollorder中的编号在初始化阶段就已经被洗牌了，所以是随机挑了一个可以执行的case。
for(i=0; incase; i++) {
o = sel->pollorder[i];
cas = &sel->scase[o];
…..
switch(cas->kind) {
case CaseRecv:
……..
case CaseSend:
…….
case CaseDefault:
……
}
}
// 没有找到可以执行的case，但有default条件，这个if里就会直接退出了。
if(dfl != nil) {
…..
}
// 到这里，就是没有找到可以执行的case，也没有default条件的情况了。
// 把当前goroutine给入队到每个case对应的channel的等待队列中去。channel的等待队列在
// channel实现中已经详细介绍了。
for(i=0; incase; i++) {
………..
switch(cas->kind) {
case CaseRecv:
enqueue(&c->recvq, sg);
break;
case CaseSend:
enqueue(&c->sendq, sg);
break;
}
}
// 入队完后，就把当前goroutine给挂起等待发生一个可以执行的case为止。这里同时也把所有
// channel上的加锁给解开了。
runtime·park((void(*)(Lock*))selunlock, (Lock*)sel, "select");
// 当前goroutine被唤醒开始执行了，再次把所有channel加锁。还是暴力。
sellock(sel);
// 这一个遍历case的for循环，很有意思。这里就是本次select不会执行的那些case对应的
// channel给出队当前goroutine。就是不管它们了，已经找到了一个执行的目标case了。
for(i=0; incase; i++) {
cas = &sel->scase[i];
if(cas != (Scase*)sg) {
c = cas->chan;
if(cas->kind == CaseSend)
dequeueg(&c->sendq);
else
dequeueg(&c->recvq);
}
}
// 还是没找到case，重新循环执行一遍。这种情况应该是goroutine被其他一些因素给唤醒了。
if(sg == nil)
goto loop;
………..
// 解锁退出，完成了select的执行了。
selunlock(sel);
goto retc;
// 这些goto的tag，都是针对每个case具体操作channel的过程。和channel的实现中介绍的差不多。
asyncrecv:
………
goto retc;
asyncsend:
…………….
goto retc;
syncrecv:
………………..
goto retc;
syncsend:
……………..
// select执行完退出的时候，不光是释放选择器对象，还会返回pc。这个pc就是本次select执行的case
// 的地址。只有把这个栈地址返回，才能继续执行case条件中的语句。
retc:
pc = cas->pc;
runtime·free(sel);
return pc;
}
虽然只是一个代码骨架，也挺长的，估计也只有对照源码才能更好的理解了。总之，select的执行逻辑还是有一点小复杂的。初看的时候，不是特别好理解。再总结一下我认为的几个应该知道的地方：
select语句的执行将会对涉及的所有channel加锁，并不是只加锁需要操作的channel。
对所有channel加锁之前，存在一个对涉及到的所有channel进行堆排序的过程，目的就是为了去重。
select并不是直接随机选择一个可执行的case，而是事先将所有case洗牌，再从头到尾选择第一个可执行的case。
如果select语句是放置在for循环中，长期执行，会不会每次循环都经历选择器的创建到释放的4个阶段？？？我可以明确的告诉你，目前必然是这样子的，所以select的使用是有代价的，还不低。
select的实现核心部分其实就完了，优化的空间应该还是挺多的。
编译器优化
虽然不懂编译器，但还是大概扫了一眼编译器中对select的实现部分。大概看一下cmd/gc/select.c代码中的注释，就可以了解到，编译器其实对select有一定的优化。比如你写的select没有任何的case条件，那还创建选择器干嘛呢；再或者你只有一个case条件，这显然可以不用select嘛；即使有一个case+default，也是可以优化为非阻塞的直接操作channel啊。
这部分编译器相关的优化可以详细看walkselect()函数。
