epoll设计实现

epoll设计实现

没有epoll之前，Linux只能做嵌入式

数据结构设计 fd总集：以查找为主，为啥以查找为主（往下看） 哈希表：初始化内存占用太大，比如只有100个fd，也得初始化一个1k长的哈希数组，造成空间浪费（现在有那种可扩展的哈希，也许能套用）B树和B+树：查找速度较慢，采用划分分区的思想就行搜索，虽然树矮，但key比较次数较多 一般根据上个节点查找下个节点的这种功能用B树一般用在磁盘查找上修改一个节点时只用刷新局部 红黑树：维护难度较高，修改一个节点可能需要修改整棵树，但综合查找速度和存储开销，是一个较优选择 就绪fd集合：不涉及查找，只用来存储，就队列就好 双向链表：链表用双向的，删除一个节点方便 协议栈如何与epoll模块通信

借助linux文件系统vfs：

协议栈会通过API回调epoll，epoll才知道哪些fd就绪了：

三次握手后，内核协议栈accept()通知epoll：epollin接收到数据与确认包后，recv()通知：epollin内核协议栈tcb sendbuff发送数据后，收到ack将清空sendbuff，这时send()通知epoll：epollout接收到fin包，close() 也会通知：epollin接收到rst包：通知epollerr epoll如何加锁

就绪队列和红黑树的节点是一个节点：

struct epitem { RB_ENTRY(epitem) rbn; LIST_ENTRY(epitem) rdlink; int rdy; //exist in list int sockfd; struct epoll_event event; }; // epoll_create struct eventpoll { ep_rb_tree rbr; int rbcnt; LIST_HEAD( ,epitem) rdlist; int rdnum; int waiting; pthread_mutex_t mtx; //rbtree update pthread_spinlock_t lock; //rdlist update pthread_cond_t cond; //block for event pthread_mutex_t cdmtx; //mutex for cond #if ENABLE_MUL_EPOLL struct eventpoll *prev; struct eventpoll *next; #endif };

多个线程操作epoll：

epoll_ctrl：对红黑树加锁 锁整棵树锁子树锁类型：互斥锁 =》没有获取到锁，让出cpu资源 epoll_wait：对就绪队列加锁 是协议栈回调后操作就绪队列，用户态只是读队列，这个锁是为协议栈设置的锁类型：自旋锁 =》没有获取到锁，cpu资源不让出，就等着有资源释放锁队列为啥用自旋锁：因为队列操作简单，占着cpu资源并等待的开销，小于让出cpu资源再重新获取cpu资源的还得设置条件等待：因为队列可能为空0，抢到锁了还要等到队列不为空才能取数据（线程池同理） epoll_create:不加锁 锁是epoll的一部分，锁也需要通过epoll_create进行初始化（也就是初始化eventpoll），即使多个线程创建多个epoll，那也不会造成数据错误 et与lt如何实现

比如客户端发4k的数据，服务器只接收1k，recv先读1k，调用回调，如果是边缘触发，后面的3k是不会触发的（如果客户端再发1k，这次也是会触发的），但水平触发还会触发3次

只要没读完，就会一直recv，每次调用recv都会触发

et：接收数据，调用一次回调，就是一次要把缓存区的数据全部读完

lt: recvbuffer里面有数据，就回调（如果节点已经在就绪队列里了，就不用管）

在接收缓冲区数据的时候，协议栈如果一次接收完就循环接收，接收一次就回调一次epoll：

// 可以这么理解 for(length = 0;Pay_loadLen != 0;length += recvlen){ recvlen = recv(remote_fd, ReceiveBuff, Pay_loadLen, 0); Pay_loadLen = Pay_loadLen - recvlen; memcpy(RxBuffer+length, ReceiveBuff, recvlen); memset(ReceiveBuff, 0, sizeof(ReceiveBuff)); // epoll_cb(); // 在这里回调是水平触发 } // 在这里回调是边缘触发

tip:

epoll中并没用mmap（磁盘与内存的映射），有的文章说会将就绪队列映射到用户态，使得就绪队列也无需从内核态拷贝到用户态，但代码中并没有。aio并不是适合做网络IO（网络IO最高效的还是reactor模型），更适合做磁盘IO内核协议栈本身也是支持mba实现共享内存的，只是有些网卡不支持共享内存： 一般用来做进程间通信(IPC)，是一块物理内存，多进程通过页表将各自的虚拟地址映射到这块物理内存，实现内存共享，但共享内存没有做进程间同步和互斥机制，需要结合信号量使用这里主要是用来实现零拷贝，将磁盘映射到内存。（严格来说应该都不叫共享内存。只是进行了内存映射） 用户态协议栈也得设计用户态epoll，因为用户态协议栈中的 fd 是用户态的，没法调内核态的epoll