nginx源碼分析—連結清單結構ngx_list_t

本部落格（http://blog.csdn.net/livelylittlefish ）貼出作者（阿波）相關研究、學習内容所做的筆記，歡迎廣大朋友指正！

Content

1.連結清單結構

1.2 ngx_list_t的邏輯結構

2.1建立連結清單

3.一個例子

3.2如何編譯

4.小結

0. 序

本文繼續介紹nginx的容器——連結清單。

連結清單實作檔案：檔案：./src/core/ngx_list.h/.c。.表示nginx-1.0.4代碼目錄，本文為/usr/src/nginx-1.0.4。

1. 連結清單結構

1.1 ngx_list_t結構

nginx的連結清單(頭)結構為ngx_list_t，連結清單節點結構為ngx_list_part_t，定義如下。

typedef struct ngx_list_part_s ngx_list_part_t;
 
struct ngx_list_part_s {      //連結清單節點結構
    void             *elts;   //指向該節點實際的資料區(該資料區中可以存放nalloc個大小為size的元素)
    ngx_uint_t        nelts;  //實際存放的元素個數
    ngx_list_part_t  *next;   //指向下一個節點
};
 
typedef struct{              //連結清單頭結構
    ngx_list_part_t  *last;   //指向連結清單最後一個節點(part)
    ngx_list_part_t   part;   //連結清單頭中包含的第一個節點(part)
    size_t            size;   //每個元素大小
    ngx_uint_t        nalloc; //連結清單所含空間個數，即實際配置設定的小空間的個數
    ngx_pool_t       *pool;   //該連結清單節點空間在此記憶體池中配置設定
}ngx_list_t;

其中，sizeof(ngx_list_t)=28，sizeof(ngx_list_part_t)=12。

由此可見，nginx的連結清單也要從記憶體池中配置設定。對于每一個節點(list part)将配置設定nalloc個大小為size的小空間，實際配置設定的大小為(nalloc * size)。詳見下文的分析。

1.2 ngx_list_t的邏輯結構

ngx_list_t結構引用了ngx_pool_t結構，是以本文參考nginx-1.0.4源碼分析—記憶體池結構ngx_pool_t及記憶體管理一文畫出相關結構的邏輯圖，如下。注：本文采用UML的方式畫出該圖。

nginx源碼分析—連結清單結構ngx_list_t

2. 連結清單操作

連結清單操作共3個，如下。

//建立連結清單
ngx_list_t*ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
 
//初始化連結清單
static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
    ngx_uint_tn, size_t size);
 
//添加元素
void*ngx_list_push(ngx_list_t *l)

他們的實作都很簡單，本文隻分析建立連結清單和添加元素操作。

2.1建立連結清單

建立連結清單的操作實作如下，首先配置設定連結清單頭(28B)，然後配置設定頭節點(即連結清單頭中包含的part)資料區，兩次配置設定均在傳入的記憶體池(pool指向的記憶體池)中進行。然後簡單初始化連結清單頭并傳回連結清單頭的起始位置。

ngx_list_t *
ngx_list_create(ngx_pool_t*pool, ngx_uint_t n, size_t size)
{
    ngx_list_t *list;
 
    list = ngx_palloc(pool,sizeof(ngx_list_t));  //從記憶體池中配置設定連結清單頭
    if (list == NULL) {
        return NULL;
    }
 
    list->part.elts =ngx_palloc(pool, n * size); //接着配置設定n*size大小的區域作為連結清單資料區
    if (list->part.elts == NULL) {
        return NULL;
    }
 
    list->part.nelts = 0;     //初始化
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;
 
    return list;    //傳回連結清單頭的起始位置
}

建立連結清單後記憶體池的實體結構圖如下。

nginx源碼分析—連結清單結構ngx_list_t

2.2添加元素

添加元素操作實作如下，同nginx數組實作類似，其實際的添加操作并不在該函數中完成。函數ngx_list_push傳回可以在該連結清單資料區中放置元素(元素可以是1個或多個)的位置，而添加操作即在獲得添加位置之後進行，如後文的例子。

void *
ngx_list_push(ngx_list_t*l)
{
    void             *elt;
    ngx_list_part_t  *last;
 
    last = l->last;
 
    if (last->nelts ==l->nalloc) {  //連結清單資料區滿
 
        /* the last part is full, allocate anew list part */
 
        last =ngx_palloc(l->pool, sizeof(ngx_list_part_t));  //配置設定節點(list part)
        if (last == NULL) {
            return NULL;
        }
 
        last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//配置設定該節點(part)的資料區
        if (last->elts == NULL) {
            return NULL;
        }
 
        last->nelts = 0;
        last->next = NULL;
 
        l->last->next =last;  //将配置設定的list part插傳入連結表
        l->last = last;        //并修改list頭的last指針
    }
 
    elt = (char *)last->elts + l->size * last->nelts; //計算下一個資料在連結清單資料區中的位置
    last->nelts++;  //實際存放的資料個數加1
 
    return elt;  //傳回該位置
}

由此可見，向連結清單中添加元素實際上就是從記憶體池中配置設定連結清單節點(part)及其該節點的實際資料區，并修改連結清單節點(part)資訊。

注1：與數組的差別，數組資料區滿時要擴充資料區空間；而連結清單每次要配置設定節點及其資料區。

注2：連結清單的每個節點(part)的資料區中可以放置1個或多個元素，這裡的元素可以是一個整數，也可以是一個結構。

下圖是一個有3個節點的連結清單的邏輯結構圖。

nginx源碼分析—連結清單結構ngx_list_t

圖中的線太多，容易眼暈，下面這個圖可能好一些。

nginx源碼分析—連結清單結構ngx_list_t

3. 一個例子

了解并掌握開源軟體的最好方式莫過于自己寫一些測試代碼，或者改寫軟體本身，并進行調試來進一步了解開源軟體的原理和設計方法。本節給出一個建立記憶體池并從中配置設定一個連結清單的簡單例子。在該例中，連結清單的每個節點(part)可存放5個元素，每個元素4位元組大小，建立連結清單後，要向連結清單添加15個整型元素。

3.1代碼

/**
 * ngx_list_t test, to test ngx_list_create, ngx_list_push
 */

#include <stdio.h>
#include "ngx_config.h"
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_list.h"

volatile ngx_cycle_t  *ngx_cycle;

void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
            const char *fmt, ...)
{
}

void dump_pool(ngx_pool_t* pool)
{
    while (pool)
    {
        printf("pool = 0x%x\n", pool);
        printf("  .d\n");
        printf("    .last = 0x%x\n", pool->d.last);
        printf("    .end = 0x%x\n", pool->d.end);
        printf("    .next = 0x%x\n", pool->d.next);
        printf("    .failed = %d\n", pool->d.failed);
        printf("  .max = %d\n", pool->max);
        printf("  .current = 0x%x\n", pool->current);
        printf("  .chain = 0x%x\n", pool->chain);
        printf("  .large = 0x%x\n", pool->large);
        printf("  .cleanup = 0x%x\n", pool->cleanup);
        printf("  .log = 0x%x\n", pool->log);
        printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
        pool = pool->d.next;
    }
}

void dump_list_part(ngx_list_t* list, ngx_list_part_t* part)
{
    int *ptr = (int*)(part->elts);
    int loop = 0;

    printf("  .part = 0x%x\n", &(list->part));
    printf("    .elts = 0x%x  ", part->elts);
    printf("(");
    for (; loop < list->nalloc - 1; loop++)
    {
        printf("0x%x, ", ptr[loop]);
    }
    printf("0x%x)\n", ptr[loop]);
    printf("    .nelts = %d\n", part->nelts);
    printf("    .next = 0x%x", part->next);
    if (part->next)
        printf(" -->\n");
    printf(" \n");
}

void dump_list(ngx_list_t* list)
{
    if (list == NULL)
        return;

    printf("list = 0x%x\n", list);
    printf("  .last = 0x%x\n", list->last);
    printf("  .part = 0x%x\n", &(list->part));
    printf("  .size = %d\n", list->size);
    printf("  .nalloc = %d\n", list->nalloc);
    printf("  .pool = 0x%x\n\n", list->pool);

    printf("elements:\n");

    ngx_list_part_t *part = &(list->part);
    while (part)
    {
        dump_list_part(list, part);
        part = part->next;
    }
    printf("\n");
}

int main()
{
    ngx_pool_t *pool;
    int i;

    printf("--------------------------------\n");
    printf("create a new pool:\n");
    printf("--------------------------------\n");
    pool = ngx_create_pool(1024, NULL);
    dump_pool(pool);

    printf("--------------------------------\n");
    printf("alloc an list from the pool:\n");
    printf("--------------------------------\n");
    ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));
    dump_pool(pool);

    for (i = 0; i < 15; i++)
    {
        int *ptr = ngx_list_push(list);
        *ptr = i + 1;
    }

    printf("--------------------------------\n");
    printf("the list information:\n");
    printf("--------------------------------\n");
    dump_list(list);

    printf("--------------------------------\n");
    printf("the pool at the end:\n");
    printf("--------------------------------\n");
    dump_pool(pool);

    ngx_destroy_pool(pool);
    return 0;
}

3.2如何編譯

請參考nginx-1.0.4源碼分析—記憶體池結構ngx_pool_t及記憶體管理一文。本文編寫的makefile檔案如下。

CXX = gcc
CXXFLAGS +=-g -Wall -Wextra
 
NGX_ROOT =/usr/src/nginx-1.0.4
 
TARGETS =ngx_list_t_test
TARGETS_C_FILE= $(TARGETS).c
 
CLEANUP = rm-f $(TARGETS) *.o
 
all:$(TARGETS)
 
clean:
$(CLEANUP)
 
CORE_INCS =-I. \
-I$(NGX_ROOT)/src/core \
-I$(NGX_ROOT)/src/event \
-I$(NGX_ROOT)/src/event/modules \
-I$(NGX_ROOT)/src/os/unix \
-I$(NGX_ROOT)/objs \
 
NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o
NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o
NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o
 
$(TARGETS):$(TARGETS_C_FILE)
$(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING)$(NGX_ALLOC) $(NGX_LIST) $^ -o [email protected]

3.3運作結果

# ./ngx_list_t_test
-------------------------------- create a new pool:
-------------------------------- pool = 0x9208020 .d .last = 0x9208048
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 984
-------------------------------- alloc an list from the pool:
-------------------------------- pool = 0x9208020 .d .last = 0x9208078
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 936
-------------------------------- the list information:
-------------------------------- list = 0x9208048 .last = 0x9208098
  .part = 0x920804c
  .size = 4
  .nalloc = 5
  .pool = 0x9208020
elements: .part = 0x920804c .elts = 0x9208064  (0x1, 0x2, 0x3, 0x4, 0x5)
    .nelts = 5
    .next = 0x9208078 -->
  .part = 0x920804c .elts = 0x9208084  (0x6, 0x7, 0x8, 0x9, 0xa)
    .nelts = 5
    .next = 0x9208098 -->
  .part = 0x920804c .elts = 0x92080a4  (0xb, 0xc, 0xd, 0xe, 0xf)
    .nelts = 5
    .next = 0x0 
-------------------------------- the pool at the end:
-------------------------------- pool = 0x9208020 .d .last = 0x92080b8
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 872

該例子中記憶體池和數組的(記憶體)實體結構可參考2.3節的圖。

4. 小結

本文針對nginx-1.0.4的容器——連結清單結構進行了較為全面的分析，包括連結清單相關資料結構，連結清單建立和向連結清單中添加元素等。最後通過一個簡單例子向讀者展示nginx連結清單建立和添加元素操作，同時借此向讀者展示編譯測試代碼的方法。

敬請關注後續的分析。謝謝！

Reference

Nginx代碼研究計劃 (RainX1982)

nginx-1.0.4源碼分析—記憶體池結構ngx_pool_t及記憶體管理 (阿波)

nginx源碼分析—連結清單結構ngx_list_t

繼續閱讀

【資料結構】醫院選址

Puppet自動化Nginx+Mongrel負載均衡配置

[轉]ISUP信令的IAM消息詳細内容

Ubuntu修改nginx将多個域名分别配置到伺服器不同端口

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

筆試面試題目：滑動視窗(二)

修改or隐藏nginx版本号

Nginx安全改動：隐藏Nginx版本号背景解決serve_tokens指令參考

版本号隐藏

Nginx服務優化（版本隐藏、版本号僞裝、逾時管理、程序管理、日志分割）Nginx服務優化未完待續

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器