乱谈服务器编程
第一部分 编程模型
关于server编程模型,大师stevens在他的《UNP》一书中已经做了详细论述,这里不再重复,这里主要讲一下我的一些理解。
从线程的角度,可以分为两类,一是单线程,一是多线程。先来看单线程模型。
1.1、单线程模型
整个进程只有一个线程,由于只有一个线程,所以要实现高性能,必须与“non-blocking IO + IO multiplexing”相结合。程序基本模型如下:
该模型的代表主要有haproxy、nginx等,另外libevent本身也是单线程的。相对于多线程,单线程server没有线程切换以及加锁的开销,劣势是不能充分利用CPU的多核优势,不过,这可以通过多个进程来解决。
另外,这种模型编程也很简单,因为简单,所以是编写高性能server的首选。公司内部的网络框架Srvframework、GNP都属于这类范畴。 Alan Cox曾说:“线程是为不懂状态机的人准备的”[9]。的确,单线程+状态机可以做很多事情。
1.2、多线程模型
进程有多个线程,一般来说,可以将server的线程分成两类:I/O线程和工作线程。由此又可以将多线程模型大体分成两类:单一I/O线程+多个工作线程、多个I/O线程(工作线程)。另外,不论是单线程,还是多线程,non-blocking IO + IO multiplexing都是必选的。
(1)单一I/O线程+多个工作线程
这种模型下,I/O线程负责event loop、I/O操作,工作线程负责实际的业务逻辑处理,I/O线程与工作线程可以通过阻塞队列/共享内存等方式进行数据交换,队列/共享内存的访问需要加锁。实际上,这种模型本质上与1.2中单线程是类似的,只不过这里的业务逻辑交由单独的工作处理,它有大家都很熟悉的名字——半同步/半异步模型(HS/HA)。Taf属于这类。
(2)多个I/O线程(工作线程)
这种模型下,每个I/O线程都有一个event loop,另外,这里的工作线程可有可无,而且通常是没有,即I/O线程既处理I/O,又进行业务逻辑计算。大家熟悉的leader/follower(L/F)以及muti-reactor(M-R)模型都属于这类,这方面的资料很多,见参考文献,不再讨论。Memcached使用的M-R,ICE使用的L/F。
1.3、小结
个人认为:(1)单线程模型实现简单,如果业务逻辑不复杂,是实现高性能server的首选,比如proxy之类的server。(2)HS/HA很清晰,如果业务逻辑很复杂,比如database,可以考虑这种模型。(3)如果你想充分利用多CPU,当然可以考虑L/F或者M-R。但是值得一提的是,L/F中会有锁的开销,而M-R中没有锁的开销,但M-R的线程切换的开销要高于L/F。根据同事的一些测试,对于短连接L/F的结果好于M-R,而对于长连接,M-R要好于L/F。
2.1、核心数据结构
当用系统调用函数epoll_create创建一个epoll环境时,用户态得到epoll fd,内核态创建一个eventpoll:
理解这个结构是理解epoll的开始,所以这里有必要解释一下。
我们知道在Unix/Linux中,一切都是文件,对于epoll实例的fd,eventpoll通常保存在file. private_data字段中。
lock:自旋锁,用于保护该数据结构。
mtx:互斥量,主要用于多个epoll_ctl之间的并发,epoll以红黑树组织关注的fd,epoll_ctl会修改红黑树,参见epoll_ctl的实现。
为什么有了一个自旋锁,还要搞一个互斥量?见最后一小结。
wq:epoll_wait使用的等待队列,在多线程程序中,我们可以在多个线程中对同一个epoll实例调用epoll_wait。
poll_wait:这个域是比较让人费解的。这里说说我的理解:对于socket fd,会将fd对应的epitem加入到sock的等待队列,但是,对于epfd,没有sock对象,用poll_wait做等待队列,参见ep_eventpoll_poll。
ovflist: 主要是解决当内核在传输数据给用户空间(ep_send_events_proc)时的锁(eventpoll->mtx),此时epoll就是将这个时候传递上来的事件保存到ovflist中。
在epoll内部,每个关注的fd都对应一个epitem:
这个结构比较简单,没什么好说的。
2.2、核心函数
当我们调用epoll_create创建一个epoll实例后,就可以调用epoll_ctl向epoll添加关注的fd了。
SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd,
struct epoll_event __user *, event)
{
…
ep = file->private_data;
//对互斥量加锁
mutex_lock(&ep->mtx);
/*
* Try to lookup the file inside our RB tree, Since we grabbed "mtx"
* above, we can be sure to be able to use the item looked up by
* ep_find() till we release the mutex.
*/
epi = ep_find(ep, tfile, fd);
error = -EINVAL;
switch (op) {
case EPOLL_CTL_ADD:
if (!epi) {
epds.events |= POLLERR | POLLHUP;
error = ep_insert(ep, &epds, tfile, fd);
} 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) {
epds.events |= POLLERR | POLLHUP;
error = ep_modify(ep, epi, &epds);
} else
error = -ENOENT;
break;
}
mutex_unlock(&ep->mtx);
…
}
ep_insert:
ep_insert主要将fd添加到红黑树,然后在具体协议的poll,比如tcp_poll中,调用回调函数ep_ptable_queue_proc,最后检查fd是否ready,如果ready,则将fd加入到就绪队列,并唤醒等待进程。另外,值得一提的是在epoll_ctl和epoll_wait中,对epoll的就绪队列的访问都是由自旋锁lock保护。
ep_ptable_queue_proc主要将epoll_ctl传进来的fd封装成的epitem添加到target file对应的sock的等待队列。
当socket收到数据时,内核协议栈会将其放到sock的接收队列sk_receive_queue,并调用sk_data_ready回调函数(如果用标准函数sock_init_data来初始化sock实例,通常是sock_def_readable),唤醒等待队列,内核唤醒原语最终会调用这里注册的回调函数ep_poll_callback。
下面来看看ep_poll_callback:
该函数将fd加到epoll实例的ready list,然后唤醒epoll实例的等待进程队列。注意红色部分,后面讨论epoll线程安全性的时候会再提到。
当我们把关注的fd添加到epoll环境后,就可以调用epoll_wait等待fd上的事件发生了。
很简单,主要逻辑由ep_poll完成:
static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
int maxevents, long timeout)
{
…
fetch_events:
spin_lock_irqsave(&ep->lock, flags);
if (!ep_events_available(ep)) { ///没有ready event, sleep current process
/*
* We don't have any available event to return to the caller.
* We need to sleep here, and we will be wake up by
* ep_poll_callback() when events will become available.
*/
init_waitqueue_entry(&wait, current);
///将进程加入到epoll环境的等待队列
__add_wait_queue_exclusive(&ep->wq, &wait);
for (;;) {
/*
* We don't want to sleep if the ep_poll_callback() sends us
* a wakeup in between. That's why we set the task state
* to TASK_INTERRUPTIBLE before doing the checks.
*/
set_current_state(TASK_INTERRUPTIBLE);
if (ep_events_available(ep) || timed_out) ///timeout==0, timed_out==1,则break
break;
if (signal_pending(current)) {
res = -EINTR;
break;
}
spin_unlock_irqrestore(&ep->lock, flags);
if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS)) ///schedule
timed_out = 1;
spin_lock_irqsave(&ep->lock, flags);
}
__remove_wait_queue(&ep->wq, &wait);
set_current_state(TASK_RUNNING);
}
check_events:
/* Is it worth to try to dig for events ? */
eavail = ep_events_available(ep);
spin_unlock_irqrestore(&ep->lock, flags);
/*
* Try to transfer events to user space. In case we get 0 events and
* there's still timeout left over, we go trying again in search of
* more luck.
*/
if (!res && eavail && ///将事件拷贝到用户空间
!(res = ep_send_events(ep, events, maxevents)) && !timed_out)
goto fetch_events;
…
}
ep_poll的逻辑也非常简单,就是不断检查epoll的ready list,如果有ready fd,则将其拷贝到用户空间。
注意ep_poll是调用__add_wait_queue_exclusive将当前进程加入到epoll的等待队列的,所以,即使多个线程对同一个epoll调用epoll_wait,也不会出现thundering herd问题。
主要逻辑是在回调函数ep_send_events_proc中完成的。
LT:Level Triggered,水平触发是epoll的默认工作模式,当fd上有事件发生,内核除了把事件上报给用户,还把fd重新加到就绪队列中,所以直到收集事件时没有事件发生,该fd才从epoll的就绪队列中移除。
例如:socket fd可读,如果数据并没有读完,则接下来每次epoll_wait都会返回该fd可读,直到有一次收集事件失败,即socket不可读。
ET: Edge Triggered,边缘触发,相比LT,ET收集完事件后不会把fd重新加入就绪队列。
如果fd可读,epoll上报有事件发生,该fd也从就绪队列中移除了,无论数据有没有读完。该fd只有在下次事件发生并在回调函数ep_poll_callback中被加入就绪队列。
ONESHOT: 顾名思义,如果fd有事件发生,只会触发一次。从ep_send_events_pro的实现可以看到,对于EPOLLONESHOT,会将其它事件位全部清掉。这样,以后ep_poll_callback(参见其实现)将不会将该fd加入ready list,即使有事件发生,直到用户再一次通过EPOLL_CTL_MOD重新设置fd。所以,对于ONESHOT的fd,如果有事件发生,每次EPOLL_CTL_MOD只会上报一次。
第三部分 问题
先看看poll的实现:
主要逻辑在do_sys_poll完成:
int do_sys_poll(struct pollfd __user *ufds, unsigned int nfds,
struct timespec *end_time)
{
struct poll_wqueues table;
int err = -EFAULT, fdcount, len, size;
/* Allocate small arguments on the stack to save memory and be
faster - use long to make sure the buffer is aligned properly
on 64 bit archs to avoid unaligned access */
long stack_pps[POLL_STACK_ALLOC/sizeof(long)];
struct poll_list *const head = (struct poll_list *)stack_pps; ///先使用栈上的空间
struct poll_list *walk = head;
unsigned long todo = nfds;
if (nfds > rlimit(RLIMIT_NOFILE))
return -EINVAL;
len = min_t(unsigned int, nfds, N_STACK_PPS);
for (;;) {
walk->next = NULL;
walk->len = len;
if (!len)
break;
///1.将用户空间的描述符拷贝到内核
if (copy_from_user(walk->entries, ufds + nfds-todo,
sizeof(struct pollfd) * walk->len))
goto out_fds;
todo -= walk->len;
if (!todo)
break;
///如果栈上空间不够,则调用kmalloc分配空间存储描述符信息
len = min(todo, POLLFD_PER_PAGE);
size = sizeof(struct poll_list) + sizeof(struct pollfd) * len;
walk = walk->next = kmalloc(size, GFP_KERNEL);
if (!walk) {
err = -ENOMEM;
goto out_fds;
}
}
///设置poll的回调函数,与epoll类似
poll_initwait(&table);
///2.poll所有描述符,是否有事件发生
fdcount = do_poll(nfds, head, &table, end_time);
poll_freewait(&table);
for (walk = head; walk; walk = walk->next) {
struct pollfd *fds = walk->entries;
int j;
///3.设置相应文件描述发生的事件
for (j = 0; j < walk->len; j++, ufds++)
if (__put_user(fds[j].revents, &ufds->revents))
goto out_fds;
}
…
}
从上面的代码可以看出,poll至少有三个原因导致它比epoll效率低:
(1)每次调用都要将用户空间的所有描述符信息拷贝到内核;
(2)与epoll不同,poll内部没一个ready list,所以,每次都需要检查所有的描述符;
(3)遍历所有的描述符,设置发生的事件。
当fd数量较多时,比如支持上万连接的高并发的server,这些遍历操作会成为性能的致命杀手。
考虑两种情况:一是两个线程对同一个epoll调用epoll_ctl;二是A线程对epoll调用epoll_wait,同时线程B调用epoll_ctl。
(1) 从第2节的epoll实现可以看到,epoll_ctl会修改内部红黑树,而且同时涉及到内存分配,所以它们之间通过互斥量保证线程性安全性。
(2) 另外,epoll_wait与epoll_wait,或者epoll_wait与epoll_ctl之间,涉及到对epoll内部ready list的访问,而且时间很短,没有其它复杂逻辑。所以用自旋锁保护。
综上,epoll是线程安全的。
在Memcached中,每个线程都有一个epoll loop,主线程(处理accept)收到一个连接,会丢到工作线程的epoll loop中,它先将连接对象CQ_ITEM加入工作线程的队列,然后通过管道来通知工作线程。但是,由于两个线程需要访问连接对象队列,所以,使用了锁来保护。实际上,如果在主线程中直接对工作线程调用epoll_ctl,是没有问题的,这样,我们就可以做一些工作(比如利用epoll_event数据结构),从而做到多个线程间无锁编程(这里的无锁是指用户态无锁,但内核仍然会有锁)。注意,这里只针对epoll,不适用于其它模型。
主要参考
1. Kernel 3.0 sourcode
2. Libevent 1.4.13 sourcecode
3. Memcached 1.4.5 sourcecode
4. Haproxy 1.4.8 sourcecode
5. Nginx 0.8.28 sourcecode
6. 《Half Sync/Half Async》
7. 《Leader/Followers:A Design Pattern for Efficient Multi-threaded I/O Demultiplexing and Dispatching》
8. 《Understanding Linux Network Internals》
9. http://lkml.indiana.edu/hypermail/linux/kernel/0106.2/0405.html
原文链接:https://www.cnblogs.com/hustcat/archive/2012/01/11/2319249.html
- 海报