情人节在家很无聊,很随便地就找了这么一个号称 安全 的web服务器:thttpd,闲的蛋疼,于是看了下代码.

主要数据结构

thttpd代码量很小,wc -l看了一下,11,000行左右,除去1k行左右的几个cgi演示性质的代码,大概有15个源文件,主要的数据结构如下:

各结构体的作用简单描述如下: TimerStruct(typedef成Timer)主要作为一个定时器,它包含了一个TimerProc*元素作为它到时之后的处理函数.结构体httpd_server表示一个绑定到某网址的server,而结构体httpd_conn就是一个从客户端(浏览器)到服务器(thttpd)的连接信息,这些连接信息也就是客户端看到的HTTP协议下指定的GET查询,POST更改操作对应的HTTP请求信息和响应信息,以及服务器看到的accept()返回的connfd信息,显然,结构体connecttab表示的就是被定时器绑定的连接信息和对应.

下面,分别介绍一下这些结构体对应的数据结构和算法:

Timer

由上图可知,Timer有两个指针,分别是prev和next,这样设计,就可以像timers.c下的 static Timer* free_timers; 一样,创建一个双向链表,元素的个数可以用一个int元素表示.这是低阶的实现,更高级的应用在这一行代码: Timer *timers[HASH_SIZE]; ,这里定义了一个数组,每个数组元素却是由多个Timer元素组成的双向链表,数组的下标根据Timer元素值的hash指定.

这么设计有什么作用呢? 实际上,在thttpd的实现中,timers不外乎就是拿来插入和删除一个Timer元素的,稍微有点不一样的是,作者对这个数组的每一个元素(也就是链表)做了排序.对双向链表排序看起来有点无厘头,因为它是顺序取值的,又不是数组那样可以随机读写.实际上,这是作者对Timer应用的思考: 不管用什么数据结构来组织,既然Timer是一个计时器,那么就总是需要从一堆Timer里面找出离某个时间最近的那个Timer的. 在thttp的实现中,因为与客户端的连接有很多,也就是accept()返回的connfd数量有很多,根据这个最近的Timer,就可以从这一堆connfd中select出已经ready(可读可写或异常)的那个connfd,然后对此connfd操作(写或读).好吧,既然关键点出来了,那么将链表排序也就是可以理解了的: 要找出最小的那个Timer,只要从times[]数组里面找出头元素最小的那个链表的下标,然后在此下标对应的链表中顺序比较找出最小的那个就可以了,这么一来,就省去了所有元素都比较一遍的麻烦.转化成代码如下:

Timer* tmr_mstimeout( )
{
    register Timer* min = timers[0];

    for ( h = 1; h < HASH_SIZE; ++h )
    {
        //timers在插入或删除元素时自然是要用心维护好顺序的,这里不打出来
        if ( timers[h] < min )
            min = timers[h];
    }
    return min;
}

至于为什么不直接设计成一个由很多Timer组成的数组呢(即: 元素是Timer而不是由Timer组成的链表,也就是 Timer timers[HASH_SIZE]) ,这么设计就可以直接用二分查找了.我觉得,这应该是因为作者认为哈希后每个链表的元素很少的缘故.

至于前面提到的 static Timer* free_timers; ,它实际上起的是类似于内存池的作用,当需要一个Timer元素时,从free_timers分配,当timers里需要cancel一个Timer时,由free_timers接收,省去了分配内存和释放内存的时间(C语言还好,C++的话分配是需要三步骤的,明显的吃力不讨好.).分配操作转换成代码如下:

Timer* tmr_create( )
{
    Timer* t;

    //free_timers相当于内存池
    if ( free_timers != (Timer*) 0 )
    {
        t = free_timers;
        free_timers = t->next;
        --free_count;
    }
    else
    {
        t = (Timer*) malloc( sizeof(Timer) );
        if ( t == (Timer*) 0 )
            return (Timer*) 0;
        ++alloc_count;
    }

    t->hash = hash( t );
    //将新分配的元素插入timers
    l_add( t );
    ++active_count;

    return t;
}

文件mmc.c下结构体MapStruct还有thttpd.c下结构体connecttab实现思想上和Timer都差不多,不加赘述.

fdwatch.c

fdwatch.c下select poll devpoll kqueue操作维护了各自的数据结构(保存文件描述符fd)和几种操作(add_fd,del_fd等),作者把这些操作封装成界面通用的宏,成功的隐藏了内部细节.比如说,fdwatch.c的用户(主要是thttp.c文件)只要用一句DEL_FD宏就可以实现添加fd的功能,而无需考虑背后fd是添加到select poll devpoll kqueue对应的哪个数据结构中,这里不多说.

下面看看select,很明显,它需要维护一个数据结构,用来存储一堆文件描述符fd,这个数据结构需要支持add和del操作.第一选择是一维数组,add时就是push(),del时也不过排序后二分查找即可.作者采用的是另外一种思路,开两个数组,维持 a[i]=j, b[j]=i 的关系.这样,要在a[]数组中找到j,可以很简单先到辅助数组b[]中找出j在a[]数组中的下标,省去了排序和二分查找.这是小技巧,直接看一下add和del的代码:

//nselect_fds维持为数组select_fds最后那个元素的下标
static void select_add_fd (int fd)
{
    select_fds[nselect_fds] = fd;
    select_fdidx[fd] = nselect_fds;

    ++nselect_fds;
}

static void select_del_fd (int fd)
{
    int idx = select_fdidx[fd];

    --nselect_fds;
    select_fds[idx] = select_fds[nselect_fds];
    select_fdidx[select_fds[idx]] = idx;
    select_fds[nselect_fds] = -1;
    select_fdidx[fd] = -1;
}

thttpd.c

这个没什么好说的,看一下main()函数流程就是了:

int main(int argc, char * argv[])
{
	...
	//很无聊的初始化各种数据结构(timer,connecttab,httpd_server等等),读配置,转daemon,注册信号处理函数等操作

	...

    //真正开始干活了.
    while(...)
    {

	//看一下有多少个文件描述符是ready了的.
        num_ready = fdwatch( tmr_mstimeout( &tv ) );

	//找到需要处理的connection
        while ( c = (connecttab*) fdwatch_get_next_client_data() )
        {
			switch ( c->conn_state )
			{
			case CNST_READING:
				handle_read( c, &tv );
				break;
			case CNST_SENDING:
				handle_send( c, &tv );
				break;
			case CNST_LINGERING:
				handle_linger( c, &tv );
				break;
			}
        }

		//所有计时器都跑的很欢快.
		tmr_run(...);
    }

    //主循环结束
    exit(0);
}

唉,人家都是分析架构的,我只看得懂一点点代码.杯具.