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