对Nginx队列源码ngx_queue_t的一次分析

[AlexiaChen]

---

title: 对Nginx队列源码ngx_queue_t的一次分析
date: 2017-11-18 13:30:00
tags:
- 数据结构与算法
- 双向链表

前言

前几天公司的群里讨论了Nginx内部实现的一个数据结构，ngx_queue_t。 实质上是一个双向链表，但是当时讨论没有讨论出结果来，原因我自己也被绕晕了，今天本着从问题本身出发，不被别人的想法思路所左右，不看网络上任何文章的分析，好好写测试用例来证明自己的想法，其实那天的问题是围绕着两个C语言的宏展开的，那么这篇文章也会重点讲解这两个宏的意义：offsetof 和 ngx_queue_data。所以这篇文章不会涉及到链表插入,删除等细节。

正文

首先，Nginx源码实现这个数据结构，用了大量的宏，我们先用我们的思路，把关键信息抽取出来:

#define u_char unsigned char  
typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;   //前一个  
    ngx_queue_t  *next;   //下一个  
};

以上代码就是这个链表的关键，ngx_queue_s 和 ngx_queue_t都是链表的节点类型，结构体中有链表的前驱（prev）和后驱（next），以实现正反向遍历。唉？ 等等，如果大学的时候，上过数据结构这门课的人会有点奇怪，会这样想：链表的节点应该有相关的数据啊，不然链表有什么意义？ 是的，链表的节点必须有数据，但是上面这个结构体却没有，这是怎么回事？如果在当时，我想大部分人会写成以下这样:

struct ngx_queue_s {
    int data;             // 数据
    ngx_queue_t  *prev;   //前一个  
    ngx_queue_t  *next;   //下一个  
};

这样每访问一个节点的时候，就可以通过节点的指针指向数据了。但是，你有没有想过，万一这个链表的数据是人名呢？不是int型，又或是其他复杂点的类型怎么办？ 是不是又要重新定一个新的链表节点类型？ 这样就麻烦了不少，软件工程里面奉行了一个原则，这个原则就是DRY原则。所以为了让不同类型采用同一个数据结构实现，就需要类型与数据结构实现分离，让这个数据结构的实现适配不同的类型，当然C++中有STL已经帮你做好了，Java也是。但是C语言就不支持泛型，Nginx由于是C语言实现的，所以采用了一种叫寄宿链表的思想，这种思想就是分离数据类型与数据结构实现的。

看到这里，就有人会想，这种思想跟文章要分析的两个宏有什么关系呢？ 现在我可以先放结论，它们之间有莫大的关系，正因为采用了寄宿链表的思想，才会间接产生了那两个宏，这种变形掩盖了一些实质。所以其实宏不是关键，是寄宿链表的思想才是关键！我们需要知道Why，而不是How，不然会深入无限的细节当中去。

话说回来，下面我们来看那两个宏的实现:

// 取struct_type类型的成员相对于struct_type基地址的偏移量（字节数） 一定要是POD 类型
#define offsetof(struct_type, member)   ((size_t) &((struct_type *) 0)->member)   

#define ngx_queue_data(node_addr,struct_type,member)  (struct_type *)((u_char*)node_addr - offsetof(struct_type, member))

我们发现ngx_queue_data这个宏复用了offsetof这个宏，那么首先分析offsetof这个宏:

这个宏根据名字可以很容易就看出来，就是字面意思，取某个结构体成员相对于结构体基址的偏移量（字节）。我们写一段代码测试来验证我们的想法:

typedef struct _SFamily{
    int id;
    char addr[256];
    int nums;
}Family;

//编译时断言，所谓的静态断言, 所以offsetof这个宏在编译时就计算出了结构体成员的偏移
static_assert(offsetof(Family, nums) == 260,"nums offset is 260");
static_assert(offsetof(Family, id) == 0, "id offset is 0");
static_assert(offsetof(Family, addr) == 4, "addr offset is 4");

根据代码结果，轻而易举的验证了我们的想法，而且这个求偏移是静态编译时就能得出的。不然以上代码直接不能通过编译。

好了，之后我们先别着急研究ngx_queue_data这个宏是怎么回事。先来看看怎么使用这个数据结构，怎样来用操作数据结构的一些方法，Nginx中已经定义好了，但是这些方法，是大量的宏定义的，这些宏不是关键，我把它们都改成了C/C++的函数形式：

#define u_char unsigned char  

// 取struct_type类型的成员相对于struct_type基地址的偏移量（字节数） 一定要是POD 类型
#define offsetof(struct_type, member)   ((size_t) &((struct_type *) 0)->member)   

typedef struct ngx_queue_s  ngx_queue_t;


struct ngx_queue_s {
    ngx_queue_t  *prev;   //前一个  
    ngx_queue_t  *next;   //下一个  
};

void ngx_queue_init(ngx_queue_s* q){
    (q)->prev = q;                                                          
    (q)->next = q;
}

bool ngx_queue_empty(ngx_queue_s* head){
    return head == head->prev;
}

void ngx_queue_insert_head(ngx_queue_s* head, ngx_queue_s* node){
    
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
    node->prev = head;

}

void ngx_queue_insert_after(ngx_queue_s* pos, ngx_queue_s* node){
    ngx_queue_insert_head(pos, node);
}

void ngx_queue_insert_tail(ngx_queue_s* tail, ngx_queue_s* node){

    node->prev = tail->prev;
    tail->prev->next = node;
    tail->prev = node;
    node->next = tail;
}

// 头节点和尾节点都是哑节点(dummy node)，并不存储实际数据
ngx_queue_s* ngx_queue_head(ngx_queue_s* head){
    return head->next;
}

ngx_queue_s* ngx_queue_last(ngx_queue_s* tail){
    return tail->prev;
}

//直接取 head dummy node
ngx_queue_s* ngx_queue_sentinel(ngx_queue_s* head){
    return head;
}

//当前节点的下一个节点
ngx_queue_s* ngx_queue_next(ngx_queue_s* cur){
    return cur->next;
}

//当前节点的上一个节点
ngx_queue_s* ngx_queue_prev(ngx_queue_s* cur){
    return cur->prev;
}

//删除节点
void ngx_queue_remove(ngx_queue_s* node){
    node->prev->next = node->next;
    node->next->prev = node->prev;
    
}

#define ngx_queue_data(node_addr,struct_type,member)  (struct_type *)((u_char*)node_addr - offsetof(struct_type, member))

这些函数的用法官方都提供了，我们根据用法，自己实现些测试用例,我们打算实现两个链表，一个是存放书籍信息的，一个是存放人员信息的，写入数据，然后遍历打印它们，看看接口是否正确：

typedef struct _Book{
    ngx_queue_t link;
    int type;
    char name[256];
}Book;

typedef struct _Person{
   
    int sex;
    char name[256];
    ngx_queue_t link;
}Person;

 Book book1, book2, book3;
    Person person1, person2, person3;

    static_assert(offsetof(Book, link) == 0, "link offset is 0");
    static_assert(offsetof(Person, link) == 260, "link offset is 260");

    book1.type = 1;
    book2.type = 2;
    book3.type = 3;

    person1.sex = 1;
    person2.sex = 0;
    person3.sex = 1;

    strcpy(book1.name, "Harry Potter");
    strcpy(book2.name, "the lord of ring");
    strcpy(book3.name, "Jame");

    strcpy(person1.name, "Fan BingBing");
    strcpy(person2.name, "Wu YanZu");
    strcpy(person3.name, "ShuQi");

    //初始化队列
    ngx_queue_t bookQueue;
    ngx_queue_init(&bookQueue);
    ngx_queue_insert_head(&bookQueue, &book1.link);
    ngx_queue_insert_tail(&bookQueue, &book2.link);
    ngx_queue_insert_tail(&bookQueue, &book3.link);

    ngx_queue_t personQueue;
    ngx_queue_init(&personQueue);
    ngx_queue_insert_head(&personQueue, &person1.link);
    ngx_queue_insert_tail(&personQueue, &person2.link);
    ngx_queue_insert_tail(&personQueue, &person3.link);

   
    for (auto iter = ngx_queue_head(&bookQueue); iter != ngx_queue_sentinel(&bookQueue); iter = ngx_queue_next(iter))
    {
        Book* bookPtr = (Book*)ngx_queue_data(iter, Book, link);

        printf("Book name is: %s . type is %d \n", bookPtr->name, bookPtr->type);
    }

    for (auto iter = ngx_queue_head(&personQueue); iter != ngx_queue_sentinel(&personQueue); iter = ngx_queue_next(iter))
    {
        Person* personPtr = (Person*)ngx_queue_data(iter, Person, link);

        printf("Person name is: %s . sex is %s\n", personPtr->name, personPtr->sex == 1 ? "Female" : "Male");
    }

以上代码的打印结果如我们所想，是正确的。注意了，我们遍历访问链表单个节点的时候用了ngx_queue_data这个宏，正是我们需要了解的宏。看来跟C语言数组，C++ vector的遍历访问差不多嘛，访问一个节点元素需要的就是节点的下标（或者说地址）。

接下来我们再看链表节点的真正的数据是定义在哪？

typedef struct _Book{
    ngx_queue_t link;
    int type;
    char name[256];
}Book;

typedef struct _Person{
   
    int sex;
    char name[256];
    ngx_queue_t link;
}Person;

注意了，以上两个结构体里面都有链表节点类型ngx_queue_t，变量名link，想想，是不是数据类型与数据结构就分离了？
不同的数据类型复用了相同类型的数据结构？ 这样访问节点就可以通过它们的link成员来正反向迭代了，所以之前的代码iter变量实际就是link成员的地址，我们可以访问每个结构体里面的link成员变量了，那么怎么知道结构体其他数据呢？没有地址，不知道在哪啊？ 其实关键就是通过link成员的地址来计算出结构体的地址的,下面举个例子:

// iter为链表节点的地址，而链表节点又在Book和Person结构体中
Book* bookPtr = (Book*)ngx_queue_data(iter, Book, link);

Person* personPtr = (Person*)ngx_queue_data(iter, Person, link);

看到上面代码并且联系ngx_queue_data宏的实现，是不是就明白了？

链表节点成员的地址 ➖ 链表节点成员相对于结构体基址的偏移 = 结构体的基址

那么是不是就可以通过结构体基址的地址强制转换为结构体的指针，访问结构体其他数据成员了？还不明白？ 那么再看下面:

typedef struct _Book{
    ngx_queue_t link; // 这个link变量的地址知道了，是不是就可以知道Book结构体基址了？  link的地址假如为123，link的偏移为0，那么123 - 0 = 123。123为数据的结构体地址
    int type;
    char name[256];
}Book;

typedef struct _Person{
   
    int sex;
    char name[256];
    ngx_queue_t link;// 这个link变量的地址知道了，是不是就可以知道Person结构体基址了？  link的地址假如为300，link的偏移为260，那么300 - 260 = 40。40为数据的结构体地址
}Person;

EOF