About

libevent是一个开源的跨平台网络库,属于事件驱动机制,支持多种I/O多路复用技术,从其主页 http://www.monkey.org/~provos/libevent/ 可以看到libevent使用者众多,其中甚至包括 Memcached.

本文参照的版本是主版本号为1的最后一个版本1.4.14(没办法,2.0.1版本代码量都在4W+行以上了, :-(

File Tree

先看一下libevent的文件组织, 源文件数目是:

源代码总行数是:

Structure Call Graph

先送上一张高清无码大图:

[虚线表示包含关系,其label表示是通过哪个成员变量来包含另一个结构体的.]

从上图的虚线指向可以看出, event_base 是绝对的核心,它包含了定时器事件最小堆结构 min_heap ,信号事件队列结构 evsignal_info 和I/O事件队列结构 eventqueue ,也就是说,libevent把定时器,I/O,信号这些事件都统一到event_base管理.另外,既然libevent是事件驱动的,那么事件属性也很自然的自成一个结构体了,就是 event .

最后,结构体 eventop 是拿来封装多种I/O多路复用技术的,主要是起隐藏底层系统机制的作用.

Tail Queue

evsignal_info 和 eventqueue 都是tail queue结构,其定义如下:

A tail queue is headed by a pair of pointers, one to the head of the list and the other to the tail of the list. The elements are doubly linked so that an arbitrary element can be removed without a need to traverse the list. New elements can be added to the list before or after an existing element, at the head of the list, or at the end of the list. A tail queue may be traversed in either direction.

tail queue有两个指针,分别指向头部和尾部.它的元素是双向链接的,所以无须遍历整个序列就可以删除任意一个元素,而且,新的元素也可以在任意位置插入,不管是在一个已存在元素的前后,还是在队列头部,还是尾部.一个tail queue可以双向遍历.

很自然的,一个tail queue有多种实现方式,在libevent中,使用的是linux下的/usr/include/sys/queue.h,我们看看linux的实现(这个纯宏实现了4种数据结构,任何一行除了注释就是宏,非常牛逼.):

#define TAILQ_HEAD(name, type)						\
struct name {								\
	struct type *tqh_first;	/* first element */			\
	struct type **tqh_last;	/* addr of last next element */		\
}

#define TAILQ_ENTRY(type)						\
struct {								\
	struct type *tqe_next;	/* next element */			\
	struct type **tqe_prev;	/* address of previous next element */	\
}

使用方式如下:

struct QUEUE_ITEM //定义节点的结构体
{
	int value; //在这里可以定义一系列的数据
	TAILQ_ENTRY(QUEUE_ITEM) entries; //作为队列入口
};   

//定义一个匿名队列的头部,这个队列的节点结构为 QUEUE_ITEM
TAILQ_HEAD(,TAILQ_ITEM) queue_head; 

从上面对这些宏的使用可以看出,节点的数据结构是自由定义的(废话),但是一定得包含有这个节点相应于队列的入口.当然,我们很容易就可以将一个节点扩展为对应多个队列,只要在这个节点的定义中有多个队列入口成员就可以了.下文将会讲到,事件结构体event就做了这种扩展.

这篇文章 对tail queue有比较详细的介绍,强烈建议仔细看完,因为Tail Queue在libevent中几乎是无处不在的.

event

首先看看event的成员:

//event提供了函数接口,供Reactor在事件发生时调用,以执行相应的事件处理,
//通常它会绑定一个有效的句柄(ev_fd)做为回调函数的参数.
struct event {

	//已注册事件队列入口
	TAILQ_ENTRY (event) ev_next;

	//已激活事件队列入口
	TAILQ_ENTRY (event) ev_active_next;

	//信号事件队列入口
	TAILQ_ENTRY (event) ev_signal_next;

	//表示该event在定时器事件最小堆min_heap的索引
	unsigned int min_heap_idx;	/* for managing timeouts */

	//该事件所属的反应堆实例
	struct event_base *ev_base;

	//对于I/O事件,是绑定的文件描述符; 对于signal事件,是绑定的信号.
	int ev_fd;

	//表示事件类型: I/O,定时器或者信号
	short ev_events;

	//事件就绪执行时,将要调用ev_callback 的次数,通常为1
	short ev_ncalls;

	//该事件的超时时间,在定时器最小堆min_heap操作中作为节点值进行比较.
	struct timeval ev_timeout;

	//该事件的优先级,越小越优先.
	int ev_pri;		/* smaller numbers are higher priority */

	//该事件被激活时的回调函数
	void (*ev_callback)(int, short, void *arg);

	//该事件的标记信息,表示其当前的状态,即它在哪个链表中
	int ev_flags;

	... //其他成员.
};

可以看到,一个事件是可以插入到多个队列的,当它与一个反应堆实例(event_base)关联时,这个事件被插入到反应堆实例下的已注册事件队列 event_base -> eventqueue ,当它处于就绪状态时,会被插入到反应堆实例下的已激活事件队列 event_base -> activequeues[id], id = event -> ev_pri .同时,如果此事件是信号事件,那么它会被插入到反应堆结构体下的信号事件结构体下的信号队列 event_base -> evsignal_info -> evsigevents[id], id = event -> ev_fd .

需要指出的,每个事件都保持了一个成员 struct event_base *ev_base; ,它表示该事件属于哪个反应堆实例.

还有一个成员需要注意, short ev_events; ,它表明此事件的事件类型,libevent正是基于此实现对I/O,信号,定时 3种事件的封装的.

min_heap

min_heap是存储定时事件的最小堆,它应该是libevent里最简单的结构体了:

typedef struct min_heap
{
    struct event** p; //p指向一个动态分配的数组,数组元素是event指针.
    unsigned n, a; // n表示目前保存了多少元素,a表示p指向的内存能够存储event指针的个数.
} min_heap_t;

之所以会有这个结构体,是因为I/O多路复用机制,比如说select,往往要求一个最大等待时间,而最小堆的根节点表示的就是最小超时时间,所以把根节点时间值传给select作为其最大等待时间就可以了.而在堆中取出根节点复杂度为O(1).

btw,从min_heap的成员p可以看出,libevent使用的是开辟一块连续存储区(即数组)来实现堆的策略.这很容易就可以办到,无非就是shift_up和shift_down操作罢了,但是libevent做了小小的优化,这导致了算法的不清晰,有点得不偿失的感觉,不提为妙.

eventop

eventop实现了对系统I/O多路复用机制的封装,这些机制包括 select poll epoll evport kqueue devpoll (别忘了libevent是跨平台的).

看看eventop的成员吧:

struct eventop {
	const char *name; //表示哪种I/O多路复用机制
	void *(*init)(struct event_base *); //初始化
	int (*add)(void *, struct event *); //注册事件
	int (*del)(void *, struct event *); //删除事件
	int (*dispatch)(struct event_base *, void *, struct timeval *); //事件分发
	void (*dealloc)(struct event_base *, void *); //注销,释放资源

	//是否需要重新初始化
	int need_reinit;
};

可以看到,eventop里面包含了5中操作的函数指针,libevent就是通过这一点来实现封装的.不同的机制定义不同的操作,但这些操作的接口却是保持一致的,以select接口为例:

const struct eventop selectops =
{
    "select",
    select_init,
    select_add,
    select_del,
    select_dispatch,
    select_dealloc,
    0
};

其中,5个select_* 成员都是函数指针,不同机制的函数以static形势封装在不同的文件下 ,举个例子, static void *
select_init(struct event_base *base) 函数的声明和定义在select.c文件下,而epoll机制的初始化函数 static void *
epoll_init(struct event_base *base) 声明和定义在epoll.c文件下.

好了,做好了这些准备,各机制的信息已经隐藏起来了,那么到底该怎样封装呢? libevent借助了一个static数组来保存这些I/O复用机制的结构体指针,代码如下:

#ifdef HAVE_EVENT_PORTS
extern const struct eventop evportops;
#endif
#ifdef HAVE_SELECT
extern const struct eventop selectops;
#endif
...
#ifdef WIN32
extern const struct eventop win32ops;
#endif

static const struct eventop *eventops[] =
{
#ifdef HAVE_EVENT_PORTS
    &evportops,
#endif
#ifdef HAVE_SELECT
    &selectops, //在select.c中
#endif
...
#ifdef WIN32
    &win32ops,
#endif
    NULL
};

其中, HAVE_* 宏是在configure时保存在config.h中的.注意在声明 evportops selectops 等变量时使用的是extern,由此使编译器知道这是外部变量,在别处寻找,或者在链接时寻找其符号名.(在libevent中,是在链接时才寻找到symbol的,封装嘛..)

封装已经ok了,那么程序运行时应该选择哪种I/O多路复用机制呢? libevent很不人性化的一点就在这里,它没有用配置文件或者config.h信息来保证用户可以灵活的选择,而是写死在代码里了(当然,手动修改代码重编译就是唯一的方法了.说到这里,还有一点要吐槽的是,libevent用的autoconf,configure文件和makefile文件难懂异常,在这方面完败于手工编写makefile的nginx.). 代码正是上面的 struct eventop *eventops[] 数组,此数组最后一个有效的元素就是libevent选择的机制.选择代码如下:

//初始化一个反应堆实例
struct event_base *event_base_new(void)
{
    ...
    for (i = 0; eventops[i] && !base->evbase; i++)
    {
        //选定I/O多路复用机制
        base->evsel = eventops[i];
    }
    ...
}

evsignal_info

evsignal_info 是用来管理信号事件的,代码如下:

struct evsignal_info {

	//是否有信号发生的标记
	volatile sig_atomic_t evsignal_caught;

	//evsigevents[signo]表示注册到信号 signo 的事件链表
	struct event_list evsigevents[NSIG];

	//具体记录每个信号触发的次数,evsigcaught[signo]是记录信号signo被触发的次数
	sig_atomic_t evsigcaught[NSIG];

	... //其他成员
};

其中, struct event_list evsigevents[NSIG]; 成员是一个数组,它的元素 evsigevents[id] 表示注册到信号id的事件链表.

关于evsignal_info 还有很多很多要说的,这留给下篇文章,本文对其描述到此为止.

event_base

终于到了最最核心的 event_base 了.秒杀之,代码如下:

struct event_base {

	//保存I/O机制
	const struct eventop *evsel; 

	//有多少个event
	int event_count;		/* counts number of total events */ 

	//有多少个活动的event
	int event_count_active;	/* counts number of active events */ 

	//存储已就绪事件队列的数组
	struct event_list **activequeues;

        //已就绪事件队列数组的元素个数
	int nactivequeues;

	//保存信号事件队列的结构体
	struct evsignal_info sig;

	//已注册事件队列
	struct event_list eventqueue; 

	//这是定时器事件最小堆
	struct min_heap timeheap;

	...//其他成员
};

重要的数据成员的说明已经在注释中给出了.相信我,回头看看前面event的描述吧.

Conclusion and next steps

本文介绍了libevent主要的结构体,接下来会分析事件处理框架或者是信号/定时器如何集成到I/O处理中的.我还没决定呢.