论select的实现

常用 Linux C/C++ 做网络开发的, 可能对于 select/poll/epoll 的使用并不陌生。三个都是 IO 复用机制, select/poll 一直被大家说效率不高, 那是为什么呢? 这篇主要从 linux-2.6.24 的内核实现来看下,它是怎么实现的,什么导致慢的。

1) 实现

下面是 select 函数的调用链

image

1. sys_select

sys_select 函数的实现很简单, 从用户进程拷贝超时时间, 调用 core_sys_select 函数。内核里面的时间是通过 clock 来计算, 所以会先把用户时间转化为 clock 数。

2. core_sys_select

select 是否有数据到来,是根据文件描述符对应的读写位是否设置为 1 来确定。这个查询结果是放到一个 bitmap 上来实现,core_sys_select 主要工作:

  1. 初始化读写还有异常的bitmap
  2. 调用 do_select 实现核心的轮询工作。
  3. 把结果拷贝会用户空间

core_sys_select 有一个小技巧, 在内核代码里面使用比较多。分配 bitmap空间的时候, 如果需要空间比较小,直接从栈区分配,需要空间超过栈区大小,直接从内核堆分配内存。可以避免一些内存碎片。

3. do_select

下面分片段来看下 do_select 的完整实现:

rcu_read_lock();
retval = max_select_fd(n, fds);
rcu_read_unlock();

根据用户传进来的 n 和当前文件系统里面的信息,获取当前需要监听的最大文件描述符编号。

poll_initwait(&table);

void poll_initwait(struct poll_wqueues *pwq)
{
    // 设置回调函数 __pollwait
    init_poll_funcptr(&pwq->pt, __pollwait);
    pwq->error = 0;
    pwq->table = NULL;
    pwq->inline_index = 0;
}

static inline void init_poll_funcptr(poll_table *pt, poll_queue_proc qproc)
{
    pt->qproc = qproc;
}

这个函数实现很关键,这里 init_poll_funcptr 初始化回调函数为 __pollwait, 后面轮询会回调这个函数,然后通过这个函数把进程添加到对应的监听文件等待队列,当有事件到来时,就会唤醒这个进程。

wait = &table.pt;
if (!*timeout)
   wait = NULL;

这里把 wait 设置为这个回调函数的指针,还有当 timeout=0 的时候把这个设置为 0,这个可以实现非阻塞的功能,后面来说为什么。

接下来是 select 实现最核心部分,轮询监听的文件描述符

for (;;) {
    ...
    for (j = 0; j < __NFDBITS; ++j, ++i, bit <<= 1) {
            int fput_needed;
            if (i >= n)
                break;
            if (!(bit & all_bits))
                continue;
            file = fget_light(i, &fput_needed);
            if (file) {
                f_op = file->f_op;
                mask = DEFAULT_POLLMASK;
                // 这里会调用 struct file*实现的poll函数进行轮询
                if (f_op && f_op->poll)
                    mask = (*f_op->poll)(file, retval ? NULL : wait);
                fput_light(file, fput_needed);
                // 根据查询返回掩码确定是否有可读数据
                if ((mask & POLLIN_SET) && (in & bit)) {
                    res_in |= bit;
                    retval++;
                }
                // 根据查询返回掩码确定是否可写
                if ((mask & POLLOUT_SET) && (out & bit)) {
                    res_out |= bit;
                    retval++;
                }
                // 根据查询返回掩码确定是否有异常
                if ((mask & POLLEX_SET) && (ex & bit)) {
                    res_ex |= bit;
                    retval++;
                }
    }
    cond_resched();
   }
}

上面的实现看起来一上来就是轮询,假设所有的文件描述符都没有数据可以读写,会怎么样呢? 理论上应该需要监听所有的文件描述符,当有其中一个有数据到来时就唤醒进程。那么哪个地方把进程添加到文件描述符对应的监听列表呢?

对于 tcp 的文件描述符, 他的 poll 函数实现(跟我们上面的poll不是一个东西),调用了sock_poll, 里面又调用了 tcp_poll, tcp_poll 里面会执行下面步骤:

  1. 调用 poll_wait
  2. 查询当前文件描述符的状态,是否可读写。
unsigned int tcp_poll(struct file *file, struct socket *sock, poll_table *wait)
{
    ...
    poll_wait(file, sk->sk_sleep, wait);
    ...
}

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);
}

回到上面的问题,就是通过 poll_wait 函数把当前进程挂到 sk->sk_sleep 这个队列里面来,当有读写事件到来时,就会唤醒这个队列里面的进程,让他们重新运行,来轮询读写数据。

而这个 qproc 函数就是上面 poll_initwait 函数初始化的回调函数 __pollwait

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);
}

这个函数实现就是把当前进程挂到 sk->sleep 队列。 上面还可以看到调用回调函数的条件必须是 wait_address 和 p 不为空,也就是说如果不想把文件描述挂到监听列表,只需要把 p 这个参数设置为 NULL.

因为进程挂到某一个文件的监听列表,只要挂一次即可。所以第一次循环之后把所有的文件描述符挂一遍之后就会把这个参数设置为 NULL。

还有两种情况也会把这个参数设置为 NULL:

  • 已经有文件描述符有读写事件,不需要再挂,因为一遍轮询就会退出,取消所有监听。
if (f_op && f_op->poll)
    mask = (*f_op->poll)(file, retval ? NULL : wait);
  • 最上面提到的, timeout = 0, 会把 wait 参数为 NULL, 即不会有挂载行为,轮询一遍立即返回,不等待事件到来,类似 non-blocking 的效果。

2) 为什么 select 慢

  1. 从上面看,在第一次所有监听都没有事件时,调用 select 都需要把进程挂到所有监听的文件描述符一次。
  2. 有事件到来时,不知道是哪些文件描述符有数据可以读写,需要把所有的文件描述符都轮询一遍才能知道。
  3. 通知事件到来给用户进程,需要把整个 bitmap 拷到用户空间,让用户空间去查询。

上面的两种情况在监听的文件描述符较少的时候,性能损耗不太明显,但在百万连接的场景下,这种实现的缺点就会很明显。

3) 为什么epoll 快

这个会在下一篇博客来介绍一下,它是怎么规避这些问题的。

主要是几点:

  1. 进程挂载到监听的文件描述符只会挂一次
  2. 用专门的链表来存储有事件到来的文件描述符,返回给用户进程,只需要拷贝这个链表。
  3. 使用红黑树来管理文件描述符,可以做到快速添加监听的文件描述符。