libevent源码走读

libevent响应事件（文件描述符可读/可写、超时、信号），调用特定函数进行处理，libevent中主要有以下几个概念：

1. 事件多路分发机制（event demultiplexer），即epoll、kqueue、select等
2. 事件源，在指定的文件描述符上注册关心的事件，如I/O读写、定时、信号事件
3. 事件处理器（event handler），事件触发时被调用
4. 反应器（reactor），事件管理接口，注册事件后进入循环，事件就绪时调用事件处理函数

libevent中主要的几个接口：

• event_init：初始化libevent库，生成event_base实例
• event_set：初始化事件event，设置回调函数和关注的事件
• event_base_set：设置event从属的event_base，即指明event要注册到哪个event_base上
• event_add：正式添加事件
• event_base_dispatch：程序进入无限循环，等待就绪事件

以下是上面各个函数的具体实现（基于libevent-2.0.20-stable版本）。

event_init函数：调用event_base_new_with_config，该函数进行事件多路分发机制选择。epoll、kqueue、select等多种事件多路分发机制被存放在eventops数组中，从该数组下标0开始选择，将选好的事件多路分发机制存放在evsel字段中。之后调用evsel->init，该接口函数最终调用对应事件多路分发机制的初始化函数，如epoll对应的是epoll_create。

event_set函数：调用event_assign，event_assign函数中，填充event结构中的文件描述符、事件类型、事件处理函数等字段。

event_base_set函数：简单地设定event结构中的ev_base字段为指定值。

event_add函数：调用event_add_internal，该函数中，根据不同的事件类型，调用不同函数处理，对于I/O，调用evmap_io_add；对于signal，调用evmap_signal_add。之后调用event_queue_insert，将事件加入激活事件队列。

在evmap_io_add和evmap_signal_add中，均会调用evsel->add，其作用就是调用某个具体事件多路分发机制的接口函数，完成事件添加。例如对应于epoll的add函数就是epoll_nochangelist_add，该函数调用epoll_apply_one_change，epoll_apply_one_change调用epoll_ctl进行事件注册。

event_base_dispatch函数：调用event_base_loop，该函数调用evsel->dispatch，即事件多路分发机制注册的dispatch函数，对应于epoll就是epoll_dispatch，epoll_dispatch调用epoll_wait，调用event_set函数时设定了监听的文件描述符，epoll_wait在此文件描述符上等待I/O事件发生。

Have fun!

memcached客户端一致性哈希算法实现——libketama

对于memcached，K-V存储到哪个memcached服务器，由memcached客户端决定。下面我们分析一种memcached客户端一致性哈希算法（consistent hashing algo）实现库——libketama。

使用方法

libketama提供了一个memcached服务器配置文件，我们需先将服务器ip、memory填入该文件：

之后我们编码调用libketama接口，输入K-V中的key值，libketama为我们返回该K-V将要被存放到的memcached服务器ip。

以上代码简单展示了libketama的用法，用到libketama提供的ketama_roll、ketama_hashi、ketama_get_server、ketama_smoke几个接口。

一致性哈希模型构建

构建一致性哈希模型，需要模拟两个对象，一个是圆，另一个是圆上的虚拟节点。libketama分别通过continuum、mcs两个结构模拟圆和虚拟节点：

以上numpoints记录圆上虚拟节点的数目，modtime记录memcached服务器配置文件的修改时间，array为圆上虚拟节点mcs数组。

以上point记录虚拟节点在圆上的位置。

模型构建过程

ketama_roll接口用于一致性哈希模型构建，其调用ketama_create_continuum，ketama_create_continuum函数先调用read_server_definition函数读取memcached服务器配置文件，将信息保存在以下结构中：

之后构建虚拟节点，根据所配置的服务器个数，一共构建numservers*160个虚拟节点：

以上代码中，首先对每个物理服务器节点计算权重pct，再由权重得出为每个物理服务器设立的虚拟节点个数ks*4。

之后调用ketama_md5_digest计算“ip-i”（比如“10.0.1.1:11211-0”）对应的md5值，并由该md5值得出虚拟节点的具体位置，即mcs结构中的point值。

确定所有虚拟节点point值之后，最终对所有point值排序，并将虚拟节点总个数、mcs数组放入共享内存中。至此完成一致性哈希模型的构建。

由Key获取ip

一个K-V应该放入哪个memcached？首先我们可以调用ketama_hashi接口计算出key的md5散列值kh，其计算方法与计算虚拟节点point值的方法相同。

之后调用ketama_get_server，构建虚拟节点时虚拟节点已根据point值完成排序，ketama_get_server中采用二分查找法，若能找到第一个大于kh的point值，则返回相应的mcs结构；若未找到，则返回虚拟节点数组的第一个mcs结构。

Have fun!

memcached中的内存管理

memcached，分布式K-V内存缓存服务，其核心为内存管理，下面我们就来了解memcached管理内存的方式、解读这部分代码，本文基于memcached 1.4.15版本。

memcached以类似Linux内核中的slab内存分配机制进行内存管理：

一块连续的1M大小的page被分成多个等大的chunk，slab class管理特定大小的chunk。一对K-V组成一个item，一个item被放置到一块chunk中。

除了以上结构外，memcached使用名为slots的链表，管理空闲的chunk：

memcached对内存的管理主要是对slabclass和slots链表的维护。slabclass_t结构如下：

下面从memcached初始化内存管理结构、add/delete操作分析相应的memcached代码。

初始化内存管理结构

main函数中，调用slabs_init进行内存管理相关的初始化工作。slabs_init函数中，初始化数组长度为MAX_NUMBER_OF_SLAB_CLASSES的slabclass数组，对每个slab class，填入size和per slab值。size值为sizeof(item) + settings.chunk_size，即最小为96，默认factor为1.25，size若不足8的倍数则补齐。

初始化过程很简单，初始化完成后memcached也并没有真正从操作系统获取物理内存。

add操作

拉起memcached服务后，memcached即对端口进行监听，等待请求的到来。在memcached客户端执行add操作后，函数调用过程如下：

event_handler -> drive_machine -> try_read_command -> process_command -> process_update_command -> item_alloc -> do_item_alloc -> slabs_alloc ->  do_slabs_alloc

在do_item_alloc函数中，调用slabs_clsid函数，slabs_clsid根据添加的key的长度计算所要放置到的slabclass的下标，计算方法为遍历slabclass数组，将key长度与slabclass->size进行比较。

在do_slabs_alloc函数中，首先判断是否有空闲的chunk，即sl_curr值是否为零。如果sl_curr非零，则从slots中取chunk；否则调用do_slabs_newslab完成page申请。

do_slabs_newslab -> split_slab_page_into_freelist -> do_slabs_free

do_slabs_newslab调用memory_allocate从系统申请1M大小的内存，之后调用split_slab_page_into_freelist将1M内存分成等大的chunk，split_slab_page_into_freelist 对每块chunk调用do_slabs_free，将这些新生成的空闲chunk加入slots链表。完成以上动作，do_slabs_newslab函数中，将新申请的page加入slab_list数组。

完成空闲chunk申请后，在do_item_alloc函数中，将key、key长度、value等值填到chunk中：

delete操作

对应delete操作，函数调用过程如下：

event_handler -> drive_machine -> try_read_command -> process_command -> process_delete_command -> item_get -> do_item_get -> item_remove -> do_item_remove -> item_free -> slabs_free -> do_slabs_free

在do_slabs_free中，内存并不是真正归还系统，而是放到相应slab class的slots链表头部：

Have fun!

在vim中使用cscope快速查看代码

使用vim+cscope，我们可以很方便地跟踪和查看代码。

安装cscope后，执行以下命令：

# cd /usr/src/linux

# find . -name '*.h' -o -name '*.c' > cscope.files

# cscope -b -k -q

# ctags -R

# echo 'cs add .' >> /etc/vimrc

此后进入/usr/src/linux，使用vim就支持代码跟踪了。

执行 :cs help 可以显示cscope帮助信息：

cscope commands:

add  : Add a new database             (Usage: add file|dir [pre-path] [flags])

find : Query for a pattern            (Usage: find c|d|e|f|g|i|s|t name)

       c: Find functions calling this function

       d: Find functions called by this function

       e: Find this egrep pattern

       f: Find this file

       g: Find this definition

       i: Find files #including this file

       s: Find this C symbol

       t: Find assignments to

help : Show this message              (Usage: help)

kill : Kill a connection              (Usage: kill #)

reset: Reinit all connections         (Usage: reset)

show : Show connections               (Usage: show)

常用命令：
:cs find g hash    #查找hash函数或变量的定义
:cs find e hash    #查找包含hash字段的代码行

常用快捷键：
:ctrl + ]       #跳转到光标所在符号的定义位置
:ctrl +T       #回到上一次的位置

Have fun!