epoll学习报告

 epoll学习报告

                             kamuszhou 周霄 Jul/26/2013

 

这几天通读了内核中对epoll I/O模型的实现代码,结合网络上很多介绍epoll的文章,对epoll的实现原理已经很熟悉,下面谈谈我的几点体会。下文引用的内核代码来自3.9.6版本的内核,见URL:http://lxr.oss.org.cn/source/fs/eventpoll.c

 

一. epoll的边沿触发(ET)的效率高于电平(LT)触发的效率

    首先简单介绍一个背景:epoll实现中,把已经有事件发生的文件用一个双链表链接一起,这个双链表是在struct eventpoll结构中的rdllist域。用户空间调用epoll_wait(),陷入内核后就会立即检查这个双链表,如果链表中非空,就通过文件的poll()函数询问文件有无事件发生。如果有事件发生且是用户关心的,就会向用户空间报告,否则就睡眠。

    epoll的实现代码中实际上只有两行代码与触发方式有关,如下图所示。

 上图所示的代码运行的上下文情况是:用户加入到epoll中的某个文件,只要支持poll(),(可以是socket,FIFO,裸设备,whatever)有关心的事件到达(或可读,或可写,或报错),内核空间已经把发生的事件复制到了用户空间,但还没有从内核态返回用户空间。在返回用户空间之前代码检查用被epoll监视的这个文件是否是ET触发,如果不是(那就是LT),就把监视的文件重新放回就绪队列,下次epoll_wait()调用的时候会立即重新检查这个文件有否有事件到达。如果这文件的确有事件发生,则epoll_wait()报告给调用者。如果没有,而且其它被监视的文件也没有事件发生,则调用epoll_wait()的task就让出处理器,开始睡觉(TASK_INTERRUPTIBLE)。这段逻辑在static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, int maxevents, long timeout)中,第1494行。

如果监听的文件开启的是边沿触发(默认),则不会执行上图中的list_add_tail()逻辑。这就是边沿触发只会向用户报告一次,直到下一个关心事件发生才向用户空间报告的原因。

那么为什么ET触发效率高于LT触发呢?看一个例子,假如客户端监视一个TCP的Socket,服务端这时发来1M数据,客户端的主机网卡驱动缓存足够大,一次性接收到了所有1M数据。下面看两段客户端的接收伪代码(没有写read调用返回时socket被关闭的情况;另socket描述符fd被设为非阻塞)。

   上图的代码使用了LT触发,这段代码依赖epoll_wait()通知还有数据可供读取。所以共调用了1024次epoll_wait(),1024次read(),共2048次系统调用才读完1M数据。

 

上图使用ET触发,epoll_wait()只报告一次,然后代码循环调用1024次read()读完数据,直到第1025次read()返回-1,出错码为EAGAIN(EAGAIN等于EWOULDBLOCK),于是代码知道已经接收完数据。一共只使用了1026次系统调用就读完了数据。

总结:即使使用电平触发也不要依赖epoll_wait()通知调用者到达事件,需要循环调用IO函数直到被通知EAGAIN,这样就把epoll_wait()的调用次数降到最低,仅管有可能在下次epoll_wait()时会有可能浪费一次文件的poll()调用,但这个很小的开销可以忽略。

 

二. 为什么epoll支持嵌套调用

读epoll的实现代码发现,一个epoll的文件描述符epfd可以嵌套的加入另一个epoll。这样有什么用呢?

epoll的实现中“平等的”对待每个被监视的文件,它们维护在一棵红黑树之中,假如有十万个文件被监视,那么查找某个文件时就要在这十万个文件中查找。即使红黑树的查找效率是log(n),文件非常大时也是比较消耗时间的。

那么假如有这样一种情况,如果这十万个文件中只有1000个是活跃的,或者说这1000个文件优先级最高。那么则有一种优化方案是,创建两个epoll,第一个epoll(epfd0)监控100000 – 1000 个文件,第二个epoll (epfd1) 监控1000个高优先级文件以及epfd0。这样的好处是,大多数情况下epoll实现只在1001个元素的红黑树中查找,自然效率提高了。

总结:epoll的嵌套调用给开发者提供了一个在高并发环境下的优化方案。

 

三. epoll的效率一定比select/poll高吗。

    答案是不一定。

Select的缺点大致有:

1. 内核中写死了最多只能监视1024个文件.

2. 每次调用select都要把关心的文件描述符和关心的文件件从一个用户空间的长长的数组拷贝到内核空间.

3. select若使得caller进程进入睡眠后,某个文件有事件到达此进程被唤醒,那么所有被监视的文件全部会被调用poll()询问“你有没有事件到达”,这是一个线性的时间复杂度。

epoll针对select的三个缺点的改进:

1. 监视的文件数由取决于系统中有多少低端内存(x86_64架构中的所有内存都是低端内存)。3.9.6版本的内核实现中,对于每个登录用户,最多使用系统中低端内存的4%用来创建监视用的数据结构。见第1951行代码。max_user_watches = (((si.totalram – si.totalhigh) / 25) << PAGE_SHIFT) / EP_ITEM_COST;

2. 用户只需要把关心的文件对应的数据结构在调用epoll_wait()前用epoll_ctl()一次性传入内存,以后调用epoll_wait()时不需要像select一样拷贝大量数据。

3. 当调用epoll_wait()的caller进程睡眠时,突然有事件到达,caller进程被唤醒,epoll_wait()返回用户空间,内核并不遍历没有监视的文件,而只报告在一个即短时间内发生的事件。下面更详细的描述这个场景,以监视tcp socket举例,大致是:某进程调用epoll_wait(),此时没有任何它关心的事件发生,于是caller进程进入睡眠。处理器调度了其它进程。数据到达时,当前进程被硬件中断,网卡驱动收到数据包,数据包在中断处理函数中被拷入内核,中断处理函数设置中断下半部(Half Bottom)。下半部被处理器调度,调用epoll实现代码注册的回调函数ep_poll_callback()。ep_poll_callback()函数唤醒之前的caller进程,caller进程重新获得CPU,从epoll实现的ep_poll()函数中恢复执行,在3.9.6内核中的第1564行: if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS))。然后,内核代码开始收集已经就绪的文件和发生的事件,发回用户空间。只有从第一次回调函数ep_poll_callback()被驱动的代码调用(caller进程还在睡眠时执行的ep_poll_callback()算第一次)到epoll实现代码走到第586行关闭中断关闭中断的代码 spin_lock_irqsave(&ep->lock, flags);之间发生的事件才会被收集。

    对于第3点,这是epoll的优点,但在某种情况下却会是epoll的缺点。网上很多比较poll, select, epoll性能的文章,没来得及仔细看,我个人认为结论是可靠的。结论引入了一个概念active-to-total ratio,设所有被监控的文件数是n,活跃的文件数是m,active-to-total比则是m/n,如果这个比非常高,比如大于0.7,则poll或select的性能要高过epoll,反之则epoll胜出。

    对比前文对select的第3个缺点和epoll的改进点3的叙述可以解释这个原因。因为select在返回用户空间前又轮循了所有关心的文件,而这些文件又大部分是有事件发生的,所以select所做的工作并没有浪费,但epoll只收集了一小段时间中发生的事件,于是select较之epoll减少了用户空间和内核空间的频繁切换,从而让select的性能反超epoll。

那么如何改进呢?明白了以上的原因,那么就可以对epoll做出改进,理论上对于active-to-total比较高的应用环境下,可以在epoll的实现中加入与select做法相同逻辑,即退出前询问所有的监控文件,反正active-to-total比很高。或者更好的方案,用一个链表链接活跃的文件,在epoll返回用户空间前遍历这个链表,争取每一个epoll_wait()调用返回尽可能多的事件。

 

附:epoll的主要数据结构简介.

epoll接口的主要数据结构有struct eventpoll,struct epitem,struct eppoll_entry。

    在讲述这三个数据结构前先提一下struct file。Unix设计初期希望它的设计遵从“一切皆文件”的理念。在Linux内核中,每个抽象的文件对应一个内核struct file结构体。Struct file结构体中有一个void *private_data域。不同的文件类型会在private_data域中存放特定的信息。Struct file中另一个域f_op是函数指针的列表,它记录了对应该文件的操作。所有epoll文件的f_op都指向static const struct file_operations eventpoll_fops,因此可以代码判断一个文件是不是epoll如下:

static inline int is_file_epoll(struct file *f)

{

         return f->f_op == &eventpoll_fops;

}

 

    每次成功调用epoll_create时就会创建一个struct file的结构体,和一个struct eventpoll。Struct file中的private_data指向struct eventpoll。eventpoll维护了这个epoll的重要信息。其中比较重要的几个字段有:一个循环列表struct list_head  rdllist链接了该epll中已经可以读写或者有出错的文件描述符。一个红黑树的根结点struct rb_root  rbr,eventpoll维护了一棵红黑树,树中的结点是struct epitem。

每个被加入到epoll中被关注的文件描述符都对应一个struct epitem结构体。所有加入到同一个epoll中对应的所有epitem都挂在红黑树上。该红黑树的根结构保存在struct eventpoll中。epitem中记录了对应的文件的文件描述符和文件指针。

struct eppoll_entry是用来挂接到设备文件中的结构体。设备驱动在得知自己可读或可写或有错误时通过这个结构体通知有事件发生。每个eppoll_entry都指向一个epitem,一个epitem可能对应多个eppoll_entry。eppoll_entry中的域wait_queue_t  wait就是被用来挂接到设备文件中的等待队列。设备文件通过wait可以拿到eppoll_entry,再通过eppoll_entry拿到epitem,再拿到eventpoll。

 

 

dpkg的一些用法

Debian的dpkg的一些用法

 

1. 查看当前系统中的软件信息(dpkg -l)


"dpkg -l"命令用于查看当前系统中所有deb的软件包信息;通过"dpkg -l"命令与less和grep命令配合使用,可以实现更复杂的软件包信息查询功能。





debian:~/Desktop# dpkg -l


期望状态=未知(u)/安装(i)/删除(r )/清除(p)/保持(h)


| 当前状态=未(n)/已安装(i)/仅存配置(c )/仅解压缩(U)/配置失败(F)/不完全安装(H)


|/ 错误?=(无)/保持(?)/须重装(R )/两者兼有(#) (状态,错误:大写=故障)


||/ 名称 版本 简介







2 查询已安装的指定软件包的详细信息(dpkg -s)


使用"dpkg -s"命令查询ssh软件包的详细信息

3 查询系统中已安装的软件包所安装的文件(dpkg -L)





显示"ssh"软件包安装到系统的文件





debian:~# dpkg -L ssh


/.


/usr


/usr/share


/usr/share/doc


/usr/share/doc/openssh-client


/usr/share/doc/ssh






4 查询系统中的某个文件属于哪个软件包(dpkg -S)





debian:~# dpkg -S /etc/init.d/networking


netbase: /etc/init.d/networking



文件"/etc/init.d/networking"属于名为"netbase"的软件包。





debian:~# dpkg -S /etc/passwd


dpkg:没有找到 /etc/passwd。



系统中许多文件不属于任何软件包,它们可能是用户

GCC内联汇编写的memcmp函数 for x86-64

今天写内核代码时要写一个比较两个页框(Page Frame)的函数,想到用内联汇编来写这个功能。下面是代码:

long cmp_x64(void *s1, void *s2, size_t n)
{
    size_t num = n / 8;
    register long res;

    __asm__ __volatile__
    (
     "testq %3,%3\n\t"               ; 测试num是不是0
     "repe  cmpsq\n\t"                ; 不停地比较直到cx寄存器为0或比较到差别
     "je        1f\n\t"              ; 两块内存相等,跳出,返回0.
     "sbbq      %0,%0\n\t"    ; sbb是x86的减法指令,会额外地减去CF(借位)的值,这样%0就会是0或者-1
     "orq       $1,%0\n"         ; 把立即数1或到%0上,这样%0就会是1或者-1.
     "1:"
         : "=&a"(res)          ;  传入变量res放入寄存器ax,且这个变量是输出值(=),不要与其它输入输出共用寄存器(&)
     : "0"(res), "S"(s1), "D"(s2), "c"(num)  ; 输入列表
     : "cc");           // clobber list 告诉gcc在这段内联汇编中哪些寄存器被显式/隐式修改.If our instruction can alter the condition code register, we have to add "cc" to the list of clobbered registers.

    return res;
}

今天用Debian时总遇到locale的错误.

我的debian一般把LC_ALL设成en_US.UTF-8。这次dpkg-reconfigure locales时没有选美国英语,而是用了香港英语。于是就出错了。

解决方法的关键在于  /etc/environment 文件,  dpkg-reconfigure locales 命令用来配置local,以及locale命令列出当前期待的locale,还有 local-gen 命令可以生成local.

debian报得错误类似于:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = "en_US:en",
    LC_ALL = (unset),
    LANG = "en_US"
    are supported and installed on your system.

////////////

另外今天还解决了编译内核后,用新内核启动时报错:

kernel panic – not syncing VFS: unable to mount root fs on unknown block (0, 0)

// 通常这是因为对应文件系统被编译成模块,那么就应该生成initrd加载对应的文件驱动模块。在debian下,用update-initramfs 命令生成对应的initrd. 如: update-initramfs -c -k 3.0.63

 

使用gdb和虚拟机调试内核

调试内核很麻烦,即使是有了虚拟机的帮助。在这里记下一些关键的东西,以备忘 。

#  编译内核后, 用新内核启动系统失败,报错 “unable to mount fs ….” 之类.

需要用 update-initramfs 生成initram。

# 对于grub2,我增加了一个自定义的grub开机启动项用来调试内核,如下:

#!/bin/sh
exec tail -n +3 $0
# This file provides an easy way to add custom menu entries.  Simply type the
# menu entries you want to add after this comment.  Be careful not to change
# the 'exec tail' line above.
echo "Add Debugging entry"
cat << EOF
menuentry "Debian debug 3.7.4"{
set root=(hd0,1)
linux /boot/vmlinuz-3.7.4 root=/dev/vda1 ro quiet kgdboc=ttyS0,115200 kgdbwait
initrd /boot/initrd.img-3.7.4
}
EOF

/////////

the above grub configuration file resides in /etc/grub.d/

# client在虚拟机里启动后在内核调试断点处停下。这时在host机用gdb调试.

# gdb vmlinux

set remotebaud 115200

target remote /dev/pts/0

此时gdb输入continue命令让客户机的系统继续运行。如果想断下正在运行的client内核,在client机中使用magic SysR:  echo "g" > /proc/sysrq-trigger

 

Barebox介绍

从裸机上电开始启动计算机的过程听起来是相当复杂的。在PC的世界里,BIOS统治这个领域已经几十年了。不过,哲学上讲任何世界都是从出生,到繁荣,再后到死亡的过程。BIOS的寿命也即将迎来终结。BIOS的掘墓者即是EFI。对于MAC用户来说,EFI的使用已经有好长一段时间了。而在嵌入式Linux的世界里,u-boot则在长时间里扮演着老大哥的角色。

U-boot,或者来自DENX的das U-boot提供了非常丰富的功能。如:网络,脚本,支持FLASH(这里的flash是存储方面的flash,而不是adobe的那个flash)。一般的嵌入式系统工程序师需要的工具,都提供好了。

还是那句话,对于万事万物,都是生生死死的过程啊。u-boot的功能越来越强大。催生了新的事物的诞生。它的名字就是:Barebox。

Barebox最开始被称之为:u-boot-v2,它是一个像u-boot一样野心勃勃的bootloader。不过Barebox更有Linux的味道一些。它的发展抛弃了u-boot而越来越像Linux。它有文件系统,有基本的shell,甚至还有与Linux近似的驱动模块。

Barebox的另一个创新即是,bootloader可以被构建成一个用户空间的应用程序。这样的好处是显而易近的,你可以更方便的开方和调试Barebox。

说了这么多,看看Barebox是个什么样子呢?

uboot:/

uboot:/ ls
. .. dev env
 

和Linux一样,dev目录夹下面放了系统的设备文件。比如,mem设备文件描述了计算机的内存。

再回到u-boot,它有一个特殊的命令:md。md命令可以查看内存的内容。对于Barebox,提供了同样的工具。不过这个工具是以一种POSIX的方式实现的:打开/dev/mem设备,lseek移动文件指针,read读出文件内容。这样的实现方式不仅仅提升了代码结构,它还使得md命令可以不需修改就应用到其它设备上,比如flash存诸器。

如果你想测试一下Barebox到底如何。你可以有两种方法。

  • 第一:你可以下载Barebox的沙盒功能即把它构建成一个Linux的用户空间的应用。来自Barebox官方的解释是:

Sandbox:
If you develop features for Barebox, you can use the 'sandbox' target which compiles Barebox as a POSIX application in the Linux userspace: it can be started like a normal command and even has network access (tun/tap). Files from the local filesytem can be used to simulate devices.   如果你要为Barebox开发功能,你可以使用'沙盒'。这种方式把Barebox构建成一个Linux的用户空间程序。它像一般的命令一样,而且还有网络功能。来自文件系统的文件可以被用来模拟设备。

  • 第二:不说你也知道,把Barebox安装到真真正正的硬件上吧!对于我,我就尝试过在PC机的一块旧式的主板上安装Barebox。 

最后,Barebox的官方网站是: http://barebox.org/

copyright blog.ykyi.net