注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

epoll比select高效的原因及一些实现问题  

2016-11-01 20:28:31|  分类: Linux内核 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、select面临的问题
关于select和epoll的比较应该是一个老生常谈的问题,地球人兜知道,epoll代表一种更高的逼格,代表一种更先进的生产力,通常知道这些就已经足够。但是如果考虑到select面临的问题,可以推测epoll高效的实现应该付出了更多的努力,并且可以理解为什么epoll的实现看起来有一些"绕"。以select系统调用为例,在执行select的时候,这些被select的fd可能有就绪态,也可能没有。对于有就绪态描述符来说,皆大欢喜,立马从系统调用返回;如果没有,此时select就需要阻塞系统调用(如果超时非零的话)。
由于select的每次系统调用没有状态,比方说,在第一次系统调用返回之后,用户处理这些就绪fd,然后再次进入系统调用,在用户处理就绪文件的这个期间,可能又有fd到达就绪状态,所以select进入系统之后不管三七二十一再次对所有fd进行一次轮训。更糟糕的事,在select系统调用返回之后,用户可能并没有处理这些就绪文件就再次select。对于这些情况,select一无所知,所以它采用最为保守的做法,就是对于所有的描述符一股脑再poll一遍,这样不会丢失任何就绪态,这是政治正确的低效行为。
我们看下这样实现面临的问题:
1、暴力全量poll
在进入系统调用之后,select对于所有指定的fd逐个调用它们的poll接口来获得就绪状态。由于被poll的文件可能现在未就绪,所以就需要在进行poll的时候传入一个回调结构,从而在指定的fd状态变化的时候通知到select的调用进程(也就是唤醒可能阻塞等待的select系统调用)。这个结构在对fd状态没有任何认识的状态下同样是必定需要分配的,这个结构就是poll_table_entry结构。在sys_select===>>>core_sys_select===>>>do_select
if (!*timeout)
wait = NULL;
……
for (j = 0; j < __NFDBITS; ++j, ++i, bit <<= 1) {
……
mask = DEFAULT_POLLMASK;
if (f_op && f_op->poll)
mask = (*f_op->poll)(file, retval ? NULL : wait);
……
}
从这里可以看到,select对于poll作了一些优化,这个优化体现在(*f_op->poll)(file, retval ? NULL : wait)函数的调用:在select对于所有的指定文件进行poll的时候,如果遇到某个(任意一个)文件处于就绪态,那么之后的poll就不需要挂载poll_entry到指定的fd上了,因为只要有一个就绪那么这个系统调用就可以马上返回,而poll的第二个参数struct poll_table_struct *非零的时候目的fd会调用poll_table.qproc(struct file *, wait_queue_head_t *, struct poll_table_struct *),这样poll的调用放可以在这个回调中将自己挂载到回调函数参数中指定的wait_queue_head_t等待队列中。
还有,如果select传入的timeout指针中的内容为零则wait被设置为空指针,从而不会被回调加入等待队列,这也是非阻塞select的实现方法。
2、select的等待队列入队操作qproc函数
select的qproc指针通过poll_initwait函数的init_poll_funcptr(&pwq->pt, __pollwait)初始化,所以入队的回调函数是
/* Add a new entry */
static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,
poll_table *p)
{
struct poll_table_entry *entry = poll_get_entry(p);
if (!entry)
return;
get_file(filp);
entry->filp = filp;
entry->wait_address = wait_address;
init_waitqueue_entry(&entry->wait, current);
add_wait_queue(wait_address,&entry->wait);
}
在这个函数中,select相当于是动态为这个fd创建一个poll_table_entry。
3、tcpsocket poll函数的例子
选择tcp作为例子主要是tcp的应用场景通常更为典型
static inline void poll_wait(struct file * filp, wait_queue_head_t * wait_address, poll_table *p)
{
if (p && wait_address)
p->qproc(filp, wait_address, p);
}

unsigned int tcp_poll(struct file *file, struct socket *sock, poll_table *wait)
{
unsigned int mask;
struct sock *sk = sock->sk;
struct tcp_sock *tp = tcp_sk(sk);

poll_wait(file, sk->sk_sleep, wait);
……
return mask;
}
可以看到,在对tcp socket进行poll的时候,会首先将非空的poll_table结构的p->qproc函数来回调可能的等待队列入队操作。
4、文件就绪时的唤醒
对于tcp socket来说,当接收到一个报文时,其调用流程为tcp_v4_rcv===>>>tcp_v4_do_rcv===>>>tcp_rcv_state_process===>>>tcp_data_queue
else if (!sock_flag(sk, SOCK_DEAD))
sk->sk_data_ready(sk, 0);
这个函数指针sk_data_ready在inet_create===>>>sock_init_data
sk->sk_state_change = sock_def_wakeup;
sk->sk_data_ready = sock_def_readable;
sk->sk_write_space = sock_def_write_space;
sk->sk_error_report = sock_def_error_report;
sk->sk_destruct = sock_def_destruct;
函数执行的功能为
static void sock_def_readable(struct sock *sk, int len)
{
read_lock(&sk->sk_callback_lock);
if (sk->sk_sleep && waitqueue_active(sk->sk_sleep))
wake_up_interruptible(sk->sk_sleep);
sk_wake_async(sk,1,POLL_IN);
read_unlock(&sk->sk_callback_lock);
}
这里唤醒的队列sk->sk_sleep就是tcp_poll中操作的等待队列。
5、select对于poll_table_entry的释放
int do_select(int n, fd_set_bits *fds, s64 *timeout)
{
……
poll_freewait(&table);

return retval;
}

6、总结下select的问题
主要的问题就是没有状态的这样两眼一抹黑的全量poll,这个poll包括了大量的结构分配、释放、poll接口调用等。考虑一个场景,select传入100个fd,只有最后一个fd就绪,那么每次系统调用的时候,select都要把前99个徒劳的分配、挂载、删除,每次系统调用都这么来一波,前99个fd就这么无辜的被不断的调用。
二、epoll的解决方法
1、内核持久容器的创建
为了解决select的问题,直观的想法就是要让epoll系统调用可以有状态,避免暴力poll所有fd。要有状态就需要在内核中创建一个容器(或者说是一个代理),这个容器使用的就是内核中的struct eventpoll结构,其中包含了所有epoll_ctrl添加的fd栖身的红黑树根节点rb_root rbr,还有所有的就绪fd所在的rdllist节点。有了这个节点,epoll的回调就不依赖于用户是否正在执行epoll调用(作为对比,select是要求回调发生时select一定在系统态)。
static int ep_alloc(struct eventpoll **pep)
{
struct eventpoll *ep = kzalloc(sizeof(*ep), GFP_KERNEL);

if (!ep)
return -ENOMEM;

rwlock_init(&ep->lock);
init_rwsem(&ep->sem);
init_waitqueue_head(&ep->wq);
init_waitqueue_head(&ep->poll_wait);
INIT_LIST_HEAD(&ep->rdllist);
ep->rbr = RB_ROOT;

*pep = ep;

DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_alloc() ep=%p\n",
    current, ep));
return 0;
}
2、容器的操作
有了内核容器,接下来的操作就比较简单了,就是在容器中添加、删除、修改元素,而这些就是通过sys_epoll_ctl系统调用来实现的。当有内核的红黑树之后,这个操作就比较简单了,所谓”栽下梧桐树、引来金凤凰”就是这个过程。这里和用户态用stl的map来操作数据一样一样的,只是这个map是在内核态中。这里有一个小细节,就是不允许插入相同的fd,这个细节几乎没什么用,通常只是用来回答"what if"类的问题。
asmlinkage long
sys_epoll_ctl(int epfd, int op, int fd, struct epoll_event __user *event)
{
……
/* Try to lookup the file inside our hash table */
epi = ep_find(ep, tfile, fd);
switch (op) {
case EPOLL_CTL_ADD:
if (!epi) {
……
} else
error = -EEXIST;
break;
case EPOLL_CTL_DEL:
if (epi)
error = ep_remove(ep, epi);
else
error = -ENOENT;
break;
case EPOLL_CTL_MOD:
if (epi) {
……
} else
error = -ENOENT;
break;
}
3、epoll定制的回调函数
回调函数注册为ep_ptable_queue_proc,这个函数将在fd的waitqueue_head中添加一个等待元素,其中注册的回调当fdready时回调函数为ep_poll_callback。
static int ep_poll_callback(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
……
/* If this file is already in the ready list we exit soon */
if (ep_is_linked(&epi->rdllink))
goto is_linked;

list_add_tail(&epi->rdllink, &ep->rdllist);

is_linked:
/*
* Wake up ( if active ) both the eventpoll wait list and the ->poll()
* wait list.
*/
if (waitqueue_active(&ep->wq))
__wake_up_locked(&ep->wq, TASK_UNINTERRUPTIBLE |
TASK_INTERRUPTIBLE);
if (waitqueue_active(&ep->poll_wait))
pwake++;

is_disabled:
write_unlock_irqrestore(&ep->lock, flags);

/* We have to call this outside the lock */
if (pwake)
ep_poll_safewake(&psw, &ep->poll_wait);
……
ep_poll_callback会将就绪的fd添加到readylist中,当然首先会判断该节点是否已经在readylist,这种情况发生的场景也比较场景。以前面看到的tcp socket为例,只要它收到数据就会调用ready,进而回调到这里。如果说一个socket就绪之后,用户态一直不处理,那么这个fd就一致在readylist上,所以这个判断还是有必要的。
4、开始epollwait
从前面的实现可以看到,因为有了内核容器,所以文件fd的就绪态不依赖于用户态行为,也就是说,通过ctl添加了fd之后,用户可以隔任意长时间来进行epoll_wait并且就绪的文件状态不会丢失,以为回调需要的数据和逻辑都已经在内核,用户执行epoll_wait的时候首先看到的是eventpoll的rdllist而不是像select一样临时抱佛脚去各处poll。但是这样也有一个问题:在epoll_wait返回之后,用户可能会对就绪的fd进行操作从而让fd变为未就绪状态。例如对于一个tcp socket的数据,用户可能通过read消耗掉这个socket中的数据从而使其变为未就绪态,这个是期望的大部分情况。但是更加棘手的是用户在epoll_wait之后并没有读取这个数据,那么此时fd应该依然保持为就绪状态。此时epoll应该如何处理这些已经放到就绪队列rdllist中的数据呢?这里补充说明下:socket数据被读光之后并不会回调poll注册的回调函数,也就是从可读变为不可读并没有回调通知。
这个地方就是sys_epoll_wait代码看起来有些繁琐的原因,主要就是为了处理这种状态问题:
static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
  int maxevents, long timeout)
{
……
res = 0;
if (list_empty(&ep->rdllist)) {
……
set_current_state(TASK_RUNNING);
}
……
if (!res && eavail &&
   !(res = ep_events_transfer(ep, events, maxevents)) && jtimeout)
goto retry;

return res;
}

static int ep_events_transfer(struct eventpoll *ep,
     struct epoll_event __user *events, int maxevents)
{
……
/* Collect/extract ready items */
if (ep_collect_ready_items(ep, &txlist, maxevents) > 0) {
/* Build result set in userspace */
eventcnt = ep_send_events(ep, &txlist, events);

/* Reinject ready items into the ready list */
ep_reinject_items(ep, &txlist);
}

up_read(&ep->sem);

return eventcnt;
}

这里的实现思路是:在rdlist中的fd"很可能"是就绪的,如果fd就绪则一定在rdlist中。或者说 就绪 是 在rdlist的充分非必要条件。rdlist中的fd是否真的就绪还要再次检测验证,这个功能就是ep_send_events函数的主要逻辑,它验证的方法也非常直观就是直接去现场poll一把revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL);。
那么如何处理readyfd在用户态没有处理的情况呢?比方说epoll_wait返回一些就绪的fd,但是用户并不处理,下次epoll它们应该还是就绪态,所以如果在ep_send_events之后就把它们从rdlist删除就无法处理这种情况,这就需要ep_reinject_items函数来实现将EPOLLET触发的fd重放到rdlist,这样对于用户未处理的情况,下次epoll_wait的时候它们依然在rdlist中,从而不会丢失就绪态。
三、引申的一些问题
1、为什么epoll比select高效
select是一个无状态的系统调用,步子跨得大,容易扯着蛋,为了避免丢失就绪态,每次select系统调用时,内核都需要实时无条件poll所有指定的fd。而epoll的实现更加的精细,其实也更加直观,就是通过创建容器、添加元素、注册回调这些步骤,把就绪态保存在内核中,从而让这一组系统调用是有状态的,当然这也是为了高效付出的代价,就是系统调用更多,结构比select更复杂。
2、多进程epoll/select会唤醒多少个?
ep_ptable_queue_proc===>>>add_wait_queue(whead, &pwq->wait)
void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;

wait->flags &= ~WQ_FLAG_EXCLUSIVE;
spin_lock_irqsave(&q->lock, flags);
__add_wait_queue(q, wait);
spin_unlock_irqrestore(&q->lock, flags);
}
在tcp socket唤醒队列唤醒的时候,执行的ready函数为
static void sock_def_readable(struct sock *sk, int len)
{
read_lock(&sk->sk_callback_lock);
if (sk->sk_sleep && waitqueue_active(sk->sk_sleep))
wake_up_interruptible(sk->sk_sleep);
sk_wake_async(sk,1,POLL_IN);
read_unlock(&sk->sk_callback_lock);
}

#define wake_up_interruptible(x) __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
    int nr_exclusive, int sync, void *key)
{
struct list_head *tmp, *next;

list_for_each_safe(tmp, next, &q->task_list) {
wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
unsigned flags = curr->flags;

if (curr->func(curr, mode, sync, key) &&
(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
break;
}
}

所以通常都只会唤醒一个等待队列中的元素。也就是说,假设多个进程同时select/epoll一个文件(通常是fork出来的子进程继承过来的fd),当文件就绪之后,所有的select/epoll进程都会被同时唤醒。
3、和accept的对比
那么是不是当进程就绪之后所有的阻塞等待者都会被唤醒呢?也不是,我又想起之前看fastcgi在执行多进程accept同一个listen socket可能被唤醒的问题。在inet_csk_accept===>>>inet_csk_wait_for_connect
for (;;) {
prepare_to_wait_exclusive(sk->sk_sleep, &wait,
 TASK_INTERRUPTIBLE);
……
prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
unsigned long flags;

wait->flags |= WQ_FLAG_EXCLUSIVE;
……
4、简单验证下这个问题
tsecer@harry: cat selectandaccept.cpp 
#include <netinet/in.h>
#include <sys/socket.h>
#include <unistd.h>
#include <stdio.h>

#define LOG(format, arg...) printf(format"\n", ##arg);

void listenandaccept(int ilistenfd)
{
int ipid = getpid();
fd_set readset;
struct sockaddr_in stPeer;
socklen_t iaddrlen = sizeof(stPeer);
FD_ZERO (&readset);
FD_SET (ilistenfd, &readset);
int iret = select(ilistenfd + 1, &readset, NULL, NULL, NULL);
LOG("pid %d select ret %d", ipid, iret);
if (iret < 0)
{
return;
}
sleep(1);
iret = accept(ilistenfd, (sockaddr*)&stPeer, &iaddrlen);
LOG("pid %d accept ret %d", ipid, iret);
if (iret < 0)
{
perror("accept fail");
return;
}
LOG("pid %d exit", ipid);
}

int main()
{
struct sockaddr_in stAddr = {AF_INET, htons(1234), {INADDR_ANY}, };
int ilistenfd = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
LOG("socket ret %d", ilistenfd);
if (ilistenfd < 0)
{
perror("socket failed");
return -1;
}
int iret = bind(ilistenfd, (sockaddr*)&stAddr, sizeof(stAddr));
LOG("bind ret %d", iret);
if (iret < 0)
{
return -2;
}
iret = listen(ilistenfd, 0);
LOG("listen ret %d", iret);
if (iret)
{
return -3;
}
int pid = fork();
if (pid >= 0)
{
listenandaccept(ilistenfd);
}
else
{
LOG("fork fail");
}
}

tsecer@harry: g++ -o selectandaccept selectandaccept.cpp -g
tsecer@harry: ./selectandaccept 
socket ret 3
bind ret 0
listen ret 0
pid 3095 select ret 1
pid 3094 select ret 1
pid 3095 accept ret 4
pid 3095 exit

另一个端口执行telent连接侦听的1234端口:
tsecer@harry: telnet 127.0.0.1 1234
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
Connection closed by foreign host.
tsecer@harry: 
从上面的输出可以看到,select调用被同时唤醒后执行accept系统调用,但是只有一个进程可以成功返回。那么这个特性有什么卵用吗?并不一定有,如果硬要说个意义的话,那么非阻塞环境下不要依赖select的返回值,select说明一个socket可用,也可能被其它进程先消耗掉。
四、最开始为什么会想到这些问题
其实很容易理解epoll将就绪fd放在内核中从而避免对于用户态调用必须进入内核的做法,但是这些就绪列表放入内核中遇到的一个问题就是何时把就绪队列中的元素删除。而且还有一个微妙的问题就是代码中ep_poll_safewake试图避免的问题:内核态的回调是不可控的,可能和用户操作产生锁冲突。
最后补充下epoll man手册中的说明
       An application that employs the EPOLLET flag should use nonblocking
       file descriptors to avoid having a blocking read or write starve a
       task that is handling multiple file descriptors.  The suggested way
       to use epoll as an edge-triggered (EPOLLET) interface is as follows:

              i   with nonblocking file descriptors; and

              ii  by waiting for an event only after read(2) or write(2)
                  return EAGAIN.

       By contrast, when used as a level-triggered interface (the default,
       when EPOLLET is not specified), epoll is simply a faster poll(2), and
       can be used wherever the latter is used since it shares the same
       semantics.
其实手册中明确说明了,如果未设置EPOLLET触发模式,那么此时epoll相当于一个高效的poll函数,它和poll共享相同语义,对于这个函数的使用来说,知道这个差不多已经可以开始板砖了。
  评论这张
 
阅读(67)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017