Libevent源码分析
作者：余超 E-MAIL:yuchao86@gmail.com
Libevent是一个开源的,跨平台的事件接口封装处理库,Libevent相对于ACE来说轻量多了，ACE用了很多设计模式的思想来封装过，很好地支持C＋＋等面向对象编程的需要，本身ACE就是用C＋＋写成的，不过Libevent里面还是有很多东西值得借鉴的。Libevent是事件响应模型但是具体事件处理还要使用者自己的代码来实现,在一般的C/C++程序中可以直接包含头文件<event.h>就可以使用里面定义好的函数接口，如果你觉得不够好，你自己也可以修改，非常著名的Memcached就是基于libevent设计出来的，Memcached使用libevent来进行网络并发连接的处理，能够保证在很大并发的情况下，仍旧能够保持快速的相应能力，在Memcached的源码包中，你可以在memcache.h中(大约在310－320行左右）看到这样的结构体定义：
typedef struct {
pthread_t thread_id; /*unique ID of this thread */
struct event_base *base; /*libevent handle this thread uses */
struct event notify_event; /*listen event for notify pipe */
int notify_receive_fd; /*receiving end of notify pipe */
int notify_send_fd; /*sending end of notify pipe */
struct thread_stats stats; /*Stats generated by this thread */
struct conn_queue*new_conn_queue; /* queue of new connections to handle */
cache_t *suffix_cache; /*suffix cache */
} LIBEVENT_THREAD;
从这个结构后面的英文注释中己可以大概知道每个结构体成员变量的意义，如果想深入理解可以参考相关头文件，例如要查看pthread_t的定义你可以找到$INCLUDE_PATH文件夹下面的pthreadtypes.h文件，我用的是linux的BackTrack4系统，我的路径是/usr/include/，如果你使用IDE的话，你可以直接按住Ctrl然后鼠标单击你想查看的结构或者类也可以，这里我们要注意的是event_base和event这两个结构体，他们都定义在event.h头文件中，打开可以看到如下定义和很多函数接口，这些接口只要有libevent.so.*库的支持都是可以使用的
struct event_base;
struct event;
struct evkeyval;
struct event_list;
struct evkeyvalq;
struct evbuffer;
struct bufferevent;
struct event_watermark;
下面我们将对这个文件中很重要的两个数据结构进行分析，一个是evbuffer缓冲结构，另一个是min_heap堆排序结构的分析。
evbuffer缓冲结构分析
可以说对于任何网络库(模块)而言，一个缓冲模块都是必不可少的。缓冲模块主要用于缓冲从网络接收到的数据，以及用户提交的数据(用于发送)。很多时候，我们还需要将网络模块层(非TCP层)的这些缓冲数据拷贝到用户层，而这些内存拷贝都会消耗时间。关于libevent的缓冲模块，主要就是围绕evbuffer结构体展开。evbuffer用于缓存逻辑层（即l基于libevent那一层）将要发送的数据，以及缓存从设备（fd)里读取出的数据,先看下evbuffer的定义：
struct evbuffer {
u_char *buffer;
u_char *orig_buffer;
size_t misalign;
size_t totallen;
size_t off;
void (*cb)(struct evbuffer *,size_t, size_t, void *);
void *cbarg;
};
libevent的缓冲是一个连续的内存区域，其处理数据的方式(写数据和读数据)更像一个队列操作方式：从后写入，从前读出。evbuffer分别设置相关指针用于指示读出位置和写入位置。其大致结构如图：
orig_buffer指向由realloc分配的连续内存区域，buffer指向有效数据的内存区域，totallen表示orig_buffer指向的内存
区域的大小，misalign表示buffer相对于orig_buffer的偏移，off表示有效数据的长度。
这里我将结合具体的代码分析libevent是如何操作上面那个队列式的evbuffer的，先看一些辅助函数：
void
evbuffer_drain(struct evbuffer*buf, size_t len)
{
size_t oldoff = buf->off;
if (len >= buf->off) {
buf->off = 0;
buf->buffer =buf->orig_buffer;
buf->misalign = 0;
goto done;
}
buf->buffer += len;
buf->misalign += len;
buf->off -= len;
done:
/* Tell someone about changes inthis buffer */
if (buf->off != oldoff &&buf->cb != NULL)
(*buf->cb)(buf, oldoff,buf->off, buf->cbarg);
}
evbuffer_drain:该函数主要操作一些指标，当每次从evbuffer里读取数据时，libevent便会将buffer指针后移，同时增大misalign，减小off，而该函数正是做这件事的。说白了，该函数就是用于调整缓冲队列的前向指标。
int
evbuffer_expand(struct evbuffer*buf, size_t datlen)
{
size_t need = buf->misalign +buf->off + datlen;
/* If we can fit all the data,then we don't have to do anything */
if (buf->totallen >= need)
return (0);
/*
* If the misalignment fulfillsour data needs, we just force an
* alignment to happen. Afterwards, we have enough space.
*/
if (buf->misalign >=datlen) {
evbuffer_align(buf);
} else {
void *newbuf;
size_t length = buf->totallen;
if (length < 256)
length = 256;
while (length < need)
length <<= 1;
if (buf->orig_buffer !=buf->buffer)
evbuffer_align(buf);
if ((newbuf =realloc(buf->buffer, length)) == NULL)
return (-1);
buf->orig_buffer =buf->buffer = newbuf;
buf->totallen = length;
}
return (0);
}
evbuffer_expand:该函数用于扩充evbuffer的容量。每次向evbuffer写数据时，都是将数据写到buffer+off后，buffer到buffer+off之间已被使用，保存的是有效数据，而orig_buffer和buffer之间则是因为读取数据移动指标而形成的无效区域。evbuffer_expand的扩充策略在于，首先判断如果让出orig_buffer和buffer之间的空闲区域是否可以容纳添加的数据，如果可以，则移动buffer和buffer+off之间的数据到orig_buffer和orig_buffer+off之间(有可能发生内存重叠，所以这里移动调用的是memmove)，然后把新的数据拷贝到orig_buffer+off之后；如果不可以容纳，那么重新分配更大的空间(realloc)，同样会移动数据。扩充内存的策略为：确保新的内存区域最小尺寸为256，且以乘以2的方式逐步扩大(256、512、1024、...)。
int
evbuffer_add(struct evbuffer *buf,const void *data, size_t datlen)
{
size_t need = buf->misalign +buf->off + datlen;
size_t oldoff = buf->off;
if (buf->totallen < need) {
if (evbuffer_expand(buf, datlen)== -1)
return (-1);
}
memcpy(buf->buffer + buf->off,data, datlen);
buf->off += datlen;
if (datlen && buf->cb!= NULL)
(*buf->cb)(buf, oldoff,buf->off, buf->cbarg);
return (0);
}
evbuffer_add:该函数用于添加一段用户数据到evbuffer中。很简单，就是先判断是否有足够的空闲内存，如果没有则调用evbuffer_expand扩充之，然后直接memcpy，更新off指标。
int
evbuffer_remove(struct evbuffer*buf, void *data, size_t datlen)
{
size_t nread = datlen;
if (nread >= buf->off)
nread = buf->off;
memcpy(data, buf->buffer,nread);
evbuffer_drain(buf, nread);
return (nread);
}
evbuffer_remove:该函数用于将evbuffer中的数据复制给用户空间(读数据)。简单地将数据memcpy，然后调用evbuffer_drain移动相关指标。
evbuffer还提供了两个函数：evbuffer_write和evbuffer_read，用于直接在套接字上写/读数据。
int
evbuffer_read(struct evbuffer*buf, int fd, int howmuch)
{
u_char *p;
size_t oldoff = buf->off;
int n = EVBUFFER_MAX_READ;
if (howmuch < 0 || howmuch >n)
howmuch = n;
if (evbuffer_expand(buf, howmuch)== -1)
return (-1);
p = buf->buffer + buf->off;
n = read(fd, p,howmuch);//WIN32使用这个函数n= recv(fd, p, howmuch, 0);
if (n == -1)
return (-1);
if (n == 0)
return (0);
buf->off += n;
if (buf->off != oldoff &&buf->cb != NULL)
(*buf->cb)(buf, oldoff,buf->off, buf->cbarg);
return (n);
}
可以看到evbuffer_read函数一样的简单，这里我们删除了win32下实现的代码和FIONREAD定义。所以你看到的代码比较简洁。下面是evbuffer_write函数的源码，可以看到也是一样调用evbuffer_drain经典的写操作。
int
evbuffer_write(struct evbuffer*buffer, int fd)
{
int n;
n = write(fd, buffer->buffer,buffer->off);//WIN32使用这个函数n= send(fd, buffer->buffer, buffer->off, 0);
if (n == -1)
return (-1);
if (n == 0)
return (0);
evbuffer_drain(buffer, n);
return (n);
}
min_heap的结构定义如下：
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
libevent中的min_heap的节点值是一个时间值。libevent总是保证时间最晚的节点为根节点。libevent用这个数据结构来实现IO事件的超时控制。当某个事件(libevent中的structevent)被添加时(event_add)，libevent将此事件按照其超时时间(由用户设置)保存在min_heap里。然后libevent会定期地去检查这个min_heap，从而实现了超时机制。heap用数组作为其存储结构。这保证数组第一个元素就是heap的根节点，保证我们在取heap的最小元素时，其算法复杂度为O(1)。p指向了一个动态分配的数组，数组元素为event*，这也是heap中的节点类型。这里libevent使用连续空间去保存heap，也就是保存一棵树。因为heap是完成树，所以可以保证其元素在数组中是连续的。n表示目前保存了多少个元素，a表示p指向的内存的尺寸。structevent这个结构体定义了很多东西，但是我们只关注两个成员：min_heap_idx：表示该event保存在min_heap数组中的索引，初始为-1；ev_timeout：该event的超时时间，将被用于heap操作中的节点值比较。
struct event {
TAILQ_ENTRY (event) ev_next;
TAILQ_ENTRY (event)ev_active_next;
TAILQ_ENTRY (event)ev_signal_next;
unsigned int min_heap_idx;/* formanaging timeouts */
struct event_base *ev_base;
int ev_fd;
short ev_events;
short ev_ncalls;
short *ev_pncalls;/* Allowsdeletes in callback */
struct timeval ev_timeout;
......
};
往堆里插入元素相对而言比较简单，每一次插入时都从树的最右最下开始。然后比较即将插入的节点值与该节点的父亲节点的值，如果小于父亲节点的话，那么交换两个节点，将新的父亲节点与其新的父亲节点继续比较。重复这个过程，直到比较到根节点。libevent实现这个过程的函数主要是min_heap_shift_up_。每一次min_heap_push时，首先检查存储空间是否足够，然后直接调用min_heap_shift_up_插入。主要代码如下：
int min_heap_push(min_heap_t* s,struct event* e)
{
if(min_heap_reserve(s, s->n+ 1))
return -1;
min_heap_shift_up_(s, s->n++,e);
return 0;
}
int min_heap_reserve(min_heap_t*s, unsigned n)
{
if(s->a < n)
{
struct event** p;
unsigned a = s->a ?s->a * 2 : 8;
if(a < n)
a = n;
if(!(p = (structevent**)realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
voidmin_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event*e)
{
//获取父节点
unsigned parent = (hole_index- 1) / 2;
//只要父节点还大于子节点就循环
while(hole_index &&min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] =s->p[parent])->min_heap_idx = hole_index;
//交换位置
hole_index = parent;
parent = (hole_index - 1)/ 2;
}
(s->p[hole_index] =e)->min_heap_idx = hole_index;
}
大部分时候，从堆里取元素只局限于取根节点，因为这个节点是最有用的。对于数组存储结构而言，数组第一个元素即为根节点。取完元素后，我们还需要重新调整整棵树以使其依然为一个heap。这需要保证两点：1.依然是完成树；2.父亲节点依然小于孩子节点,实际上libevent中父节点的时间值小于子节点的时间值，时间值的比较通evutil_timercmp实现：
struct event*min_heap_pop(min_heap_t* s)
{
if(s->n)
{
struct event* e = *s->p;
min_heap_shift_down_(s,0u, s->p[--s->n]);
e->min_heap_idx = -1;
return e;
}
return 0;
}
voidmin_heap_shift_down_(min_heap_t* s, unsigned hole_index, structevent* e)
{
unsigned min_child = 2 *(hole_index + 1);
while(min_child <= s->n)
{
min_child -= min_child ==s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child- 1]);
if(!(min_heap_elem_greater(e,s->p[min_child])))
break;
(s->p[hole_index] =s->p[min_child])->min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 *(hole_index + 1);
}
min_heap_shift_up_(s,hole_index, e);
//取出节点后从新建立完全树
}
从以上分析可以看出，min_heap的设计很好地实现了超时机制，不过我们可以使用Quick排序做一些改进，大家都知道heap排序的算法效率是O（nlog2n),Quick排序的算法效率也是O(nlog2n)所以这两个算法的效率是差不多的，唯一不同的地方在于Quick排序算法减少的比较次数，尤其是当排序的数据很大，要进行多次loop时（比如当一个新的cacheevent要加入一个很大的min_heap时尤其明显）。
这次的分析就到这里，希望互联网的广大朋友多多指教，有不正确的地方敬请批评指正。
下一篇文章将是介绍memcached的源码分析。希望大家多多支持。
参考如下：
http://www.cprogramming.com/tutorial/computersciencetheory/heap.html