nginx是个优秀的web server，然而对nginx源码进行深入分析的文章并不多。末尾的参考文献列表中列出在网上找到的文章，在此补充一些自己的学习心得，与这些文章形成互补。
对于纯C写成的服务器程序，基础数据结构都是必备的。nginx的内存分配都是在自己实现的内存池(在ngx_palloc.c/.h文件中)的基础上, 具体实现原理参见[4]。nginx的内存池是按需分配，统一释放，也就是在一个pool的生命周期内，已分配的内存空间不会释放(大块空间除外,超过一个pagesize为大块空间)，也就是说内存使用量一直在增长，直到pool销毁。因此，小块内存分配后，不需要free操作，减少了内存泄露的机会。
nginx还有很多地方的设计思路都是用空间换时间，牺牲一点内存使用量换取更高的时间效率。
1. ngx_str_t 字符串结构
ngx_string.c/.h中定义了字符串操作函数。
typedef struct {
size_t len;
u_char *data;
} ngx_str_t;
#define ngx_string(str) { sizeof(str) - 1, (u_char *) str } //定义常量字符串
2. ngx_array_t
struct ngx_array_s {
void *elts; //数据块
ngx_uint_t nelts; //有效的项数
size_t size; //单位数据的size
ngx_uint_t nalloc; //已分配的项数
ngx_pool_t *pool; //所属缓冲池
};
void *
ngx_array_push(ngx_array_t *a)
{
void *elt, *new;
size_t size;
ngx_pool_t *p;
if (a->nelts == a->nalloc) {
/* the array is full */
size = a->size * a->nalloc;
p = a->pool;
if ((u_char *) a->elts + size == p->d.last
&& p->d.last + a->size <= p->d.end)
{
/*
* the array allocation is the last in the pool
* and there is space for new allocation
*/
p->d.last += a->size;
a->nalloc++;
} else {
/* allocate a new array */
new = ngx_palloc(p, 2 * size);
if (new == NULL) {
return NULL;
}
ngx_memcpy(new, a->elts, size);
a->elts = new;
a->nalloc *= 2;
}
}
elt = (u_char *) a->elts + a->size * a->nelts;
a->nelts++;
return elt;
}
ngx_array_push返回一个指针指向数组中可插入数据的有效位置，调用者把该指针转成对应的结构体指针，然后赋值便完成插入。nginx的其他数据结构使用都遵循这个方式。记得以前自己实现的动态数组，插入元素是先建立一个临时结构体变量，对结构体赋值，然后push_back到数组中，这样数据就复制了两次，不优雅且低效。
该数组没有实现元素删除的接口。在nginx的模块中一般没有此需要。
PS: nginx的变量名elt, 我猜是element的缩写吧，很多变量都用此命名，表示数据项。
3. ngx_list_t 链表
单链表
struct ngx_list_part_s {
void *elts; //数据
ngx_uint_t nelts; //有效的数据项数
ngx_list_part_t *next; //next指针(next part)
};
typedef struct {
ngx_list_part_t *last; //最后一个part
ngx_list_part_t part;
size_t size; //单位数据项大小
ngx_uint_t nalloc; //已分配的项目
ngx_pool_t *pool;
} ngx_list_t;
该链表也只实现了插入接口，没有实现删除(需在外部自行实现)。nginx每个链表项是一个part(ngx_list_part_t), 每个part可以容纳若干个数据。因此，遍历链表的代码就变成：
/*
*
* the iteration through the list:
*
* part = &list.part;
* data = part->elts;
*
* for (i = 0 ;; i++) {
*
* if (i >= part->nelts) {
* if (part->next == NULL) {
* break;
* }
*
* part = part->next;
* data = part->elts;
* i = 0;
* }
*
* 访问
data[i]
*
* }
*/
4. ngx_buf_t.
buffer的结构参见文献[4]. 有几个指针用于管理buffer, 用于发送/接收缓冲管理。
+----------已分配的内存----------------+
+----已操作-----+---待操作----+--------+
| | | |
start pos last end
5. ngx_queue_t, ngx_rbtree_t
队列和红黑树，都是经典的实现方式，没什么好讲的。红黑树实现参见本博客另一篇文章。
6. ngx_hash_t
hash函数
key = 0;
for (i = 0; i < len; i++) {
key = key*31 + data[i];
}
typedef struct {
void *value;
u_char len; //指定name的长度
u_char name[1]; //配对关键字, 不定长度.
} ngx_hash_elt_t;
typedef struct {
ngx_hash_elt_t **buckets;
ngx_uint_t size;
} ngx_hash_t;
void *
ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
{
ngx_uint_t i;
ngx_hash_elt_t *elt;
elt = hash->buckets[key % hash->size];
if (elt == NULL) {
return NULL;
}
while (elt->value) {
if (len != (size_t) elt->len) {
goto next;
}
for (i = 0; i < len; i++) {
if (name[i] != elt->name[i]) {
goto next;
}
}
return elt->value;
next:
elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
sizeof(void *));
continue;
}
return NULL;
}
参考文献
[1]
啃饼的博客. 对nginx有一系列的分析文章 [2] Joshua Zhu在广州技术沙龙的《nginx源码分析》交流。有PPT和视频. http://blog.zhuzhaoyuan.com/
[3] nginx的分析文章, 锁，内存管理，进程模型等. http://simohayha.javaeye.com/category/101180
[4] nginx的内存管理. http://simohayha.javaeye.com/blog/545192