Daly的游戏人生

Nginx源码学习(1) ---- 基础数据结构

   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;