libco协程思想

libco在解决cpu利用率与IO利用率不平衡的同时，又避免了异步调用和回调分离导致的代码结构破碎。

libco是微信后台大规模使用的C++协程库，2013年至今稳定运行在微信后台的数万台机器上，并在2013年已开源。
libco首先能解决CPU利用率与IO利用率不平衡，比用多线程解决IO阻塞CPU问题更高效。因为用户态协程切换比线程切换性能高：线程切换保存恢复的数据更多，需要用户态和内核态切换。其次libco又避免了异步调用和回调分离导致的代码结构破碎。
libco采用epoll多路复用使得一个线程处理多个socket连接，采用钩子函数hook住socket族函数，采用时间轮盘处理等待超时事件，采用协程栈保存、恢复每个协程上下文环境。

函数调用过程：
两个寄存器：
ebp:栈帧基地址
esp:栈顶的内存地址
栈帧：两个寄存器之间的内存块，用来存放函数的临时变量，参数和返回地址。保护和恢复栈帧就是保存和恢复寄存器esp和ebp的值

调用函数执行时：
ebp esp是上一个函数的栈帧

把ebp的值压入栈顶（保护前一个函数的栈帧）
参数从右到左入栈，返回地址入栈，函数内变量入栈，执行函数
esp回到原点，pop ebp值，ebp回到上一个函数的栈帧基地址

esp可以通过ebp+4恢复（栈是高地址向下增长）

函数栈：函数执行过程
首先复习下进程的地址空间，如图所示，与本文相关的有代码段、堆、栈。代码段包含应用程序的汇编代码，指令寄存器eip存的是代码段中某一条汇编指令地址，cpu从eip中取出汇编指令的地址，并在代码段中找到对应汇编指令开始执行。CPU执行指令时在栈里存参数、局部变量等数据。代码通过malloc、new在堆上申请内存空间。

协程栈：每个非主协程有自己的栈，而该栈是在堆上分配的，并不是系统栈，但主协程的栈仍然是系统栈，每两个协程的栈地址不相邻。

线程切换VS 协程切换
IO密集时也可以使用多个线程。但线程有两个不足：一，切换代价大（保存恢复上下文、线程调度）；二，占用资源多。

线程往往需要对公共数据加锁，锁会导致线程调度。因为用户的线程是在用户态执行，而线程调度和管理是在内核态实现，所以线程调度需要从用户态转到内核态，再从内核态转到用户态。切到内核态时需要保存用户态上下文，再切到用户态时，需要恢复用户态上下文，而线程的用户态上下文比协程上下文大得多。另外线程调度也需要耗时。

线程栈默认为1M大于协程栈128K，另外线程还需要各种struct存一些状态，实测每个pthread_create创建的线程大约占8M左右内存，因此线程占用资源也远比协程多。

协程控制：epoll多路复用IO模型

文件描述符

文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。
文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

什么是IO多路复用？

IO 多路复用是一种同步IO模型，实现一个线程可以监视多个文件句柄；
一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作；
没有文件句柄就绪就会阻塞应用程序，交出CPU。

多路是指网络连接，复用指的是同一个线程

为什么有IO多路复用？

没有IO多路复用机制时，有BIO、NIO两种实现方式，但它们都有一些问题
BIO

服务端采用单线程，当 accept 一个请求后，在 recv 或 send 调用阻塞时，将无法 accept 其他请求（必须等上一个请求处理 recv 或 send 完）（无法处理并发）
服务端采用多线程，当 accept 一个请求后，开启线程进行 recv，可以完成并发处理，但随着请求数增加需要增加系统线程，大量的线程占用很大的内存空间，并且线程切换会带来很大的开销，10000个线程真正发生读写实际的线程数不会超过20%，每次accept都开一个线程也是一种资源浪费。

IO多路复用的三种实现（select/poll/epoll）

select

它仅仅知道了，有I/O事件发生了，却并不知道是哪那几个流（可能有一个，多个，甚至全部），我们只能无差别轮询所有流，找出能读出数据，或者写入数据的流，对他们进行操作。所以select具有O(n)的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。

int main() {
  /*
   * 这里进行一些初始化的设置，
   * 包括socket建立，地址的设置等,
   */

  fd_set read_fs, write_fs;
  struct timeval timeout;
  int max = 0;  // 用于记录最大的fd，在轮询中时刻更新即可

  // 初始化比特位
  FD_ZERO(&read_fs);
  FD_ZERO(&write_fs);

  int nfds = 0; // 记录就绪的事件，可以减少遍历的次数
  while (1) {
    // 阻塞获取
    // 每次需要把fd从用户态拷贝到内核态
    nfds = select(max + 1, &read_fd, &write_fd, NULL, &timeout);
    // 每次需要遍历所有fd，判断有无读写事件发生
    for (int i = 0; i <= max && nfds; ++i) {
      if (i == listenfd) {
         --nfds;
         // 这里处理accept事件
         FD_SET(i, &read_fd);//将客户端socket加入到集合中,利用bitmap来存储的
      }
      if (FD_ISSET(i, &read_fd)) {
        --nfds;
        // 这里处理read事件
      }
      if (FD_ISSET(i, &write_fd)) {
         --nfds;
        // 这里处理write事件
      }
    }
  }

select 缺点
select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理。这样所带来的缺点是：

单个进程所打开的FD是有限制的，通过 FD_SETSIZE 设置，默认1024 ;
每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大；
对 socket 扫描时是线性扫描，采用轮询的方法，效率较低（高并发）

poll

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，但是它没有最大连接数的限制，原因是它是基于链表来存储的.

epoll

epoll可以理解为event poll，不同于忙轮询和无差别轮询，epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd)的，此时我们对这些流的操作都是有意义的。（复杂度降低到了O(1)）

epoll的实现很简单，就是通过三个函数实现：

#include <sys/epoll.h>

// 数据结构
// 每一个epoll对象都有一个独立的eventpoll结构体
// 用于存放通过epoll_ctl方法向epoll对象中添加进来的事件
// epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可
struct eventpoll {
    /*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/
    struct rb_root  rbr;
    /*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/
    struct list_head rdlist;
};

// API
int epoll_create(int size); // 内核中间加一个 ep 对象，把所有需要监听的 socket 都放到 ep 对象中
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); // epoll_ctl 负责把 socket 增加、删除到内核红黑树
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);// epoll_wait 负责检测可读队列，没有可读 socket 则阻塞进程

每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间效率是lgn，其中n为红黑树元素个数)。

而所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中。

在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：

struct epitem{
    struct rb_node  rbn;//红黑树节点
    struct list_head    rdllink;//双向链表节点
    struct epoll_filefd  ffd;  //事件句柄信息
    struct eventpoll *ep;    //指向其所属的eventpoll对象
    struct epoll_event event; //期待发生的事件类型
}

当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。

树和双链表数据结构，并结合回调机制，造就了epoll的高效。
讲解完了Epoll的机理，我们便能很容易掌握epoll的用法了。一句话描述就是：三步曲。

第一步：epoll_create()系统调用。此调用返回一个句柄，之后所有的使用都依靠这个句柄来标识。
第二步：epoll_ctl()系统调用。通过此调用向epoll对象中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。
第三部：epoll_wait()系统调用。通过此调用收集收集在epoll监控中已经发生的事件。

epoll的优点

没有最大并发连接的限制，能打开的FD的上限远大于1024（1G的内存上能监听约10万个端口）；
效率提升，不是轮询的方式，不会随着FD数目的增加效率下降。只有活跃可用的FD才会调用callback函数；即Epoll最大的优点就在于它只管你“活跃”的连接，而跟连接总数无关，因此在实际的网络环境中，Epoll的效率就会远远高于select和poll；
内存拷贝，利用mmap()文件映射内存加速与内核空间的消息传递；即epoll使用mmap减少复制开销。