Nginx source code analysis - linked list structure ngx_list_t
Content
The 1 chain structure
The logical structure of the 1.2 ngx_list_t
2.1 create a linked list
3 an example
3.2 how to compile
4 Summary
0 sequence
This paper continues to introduce the nginx -- the list container.
The linked list implementation file: File:./src/core/ngx_list.h/.c. Nginx-1.0.4 code directory. Said, this is/usr/src/nginx-1.0.4.
The 1 chain structure
1.1 ngx_list_t structure
Nginx list (head) structure is ngx_list_t, struct node is ngx_list_part_t, defined as follows.
[cpp] view plaincopy- typedef struct ngx_list_part_s ngx_list_part_t;
- struct ngx_list_part_s { //Struct node
- void *elts; //Pointing to the node actual data area (for nalloc size of size elements in the data area)
- ngx_uint_t nelts; //The actual number of storage elements
- ngx_list_part_t *next; //Pointer to the next node
- };
- typedef struct{ //Chain table structure
- ngx_list_part_t *last; //To the end of the list of a node(part)
- ngx_list_part_t part; //The first node contains chain in header(part)
- size_t size; //Each element size
- ngx_uint_t nalloc; //A number of space containing the list, namely, the actual distribution of the number of small space
- ngx_pool_t *pool; //Distribution of the node space in the memory pool
- }ngx_list_t;
Among them, sizeof(ngx_list_t)=28, sizeof(ngx_list_part_t)=12.
Thus, the nginx list must also allocated from the memory pool. For each node (list part) will assign the nalloc size is size little space, the actual distribution of size (nalloc * size). Analysis for the following.
The logical structure of the 1.2 ngx_list_t
Ngx_list_t cited the ngx_pool_t structure, this paper refer to the nginx-1.0.4 source code analysis - memory pool structure of ngx_pool_t and memory management in drawing logic diagram structure, as follows. Note: This article is to draw the graph using UML approach.
2 the list operations
List operation a total of 3, are as follows.
[cpp] view plaincopy- //Create list
- ngx_list_t*ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
- //Initialization list
- static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
- ngx_uint_tn, size_t size);
- //Adding elements
- void*ngx_list_push(ngx_list_t *l)
Their implementation is very simple, this paper analyses create list and add elements.
2.1 create a linked list
Create list of the operation to achieve the following, first distribution chain header (28B), and then assign the head node (which includes chain header data area part), two distribution in the incoming memory pool (pool pointing to the memory pool) in. The starting position and then simple initialization chain headers and return chain header.
[cpp] view plaincopy- 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)); //Distribution chain headers from the memory pool
- if (list == NULL) {
- return NULL;
- }
- list->part.elts =ngx_palloc(pool, n * size); //Then n*size distribution size region as a linked list data regions
- if (list->part.elts == NULL) {
- return NULL;
- }
- list->part.nelts = 0; //Initialization
- list->part.next = NULL;
- list->last = &list->part;
- list->size = size;
- list->nalloc = n;
- list->pool = pool;
- return list; //The starting position return header
- }
Physical structure create list after the memory pool.
2.2 add elements
Add elements to achieve the following, with the nginx arrays to achieve similar, the add operation does not finish in the function. The ngx_list_push function returns the element in the list can be placed in the data area (the elements can be of 1 or more) position, and add operation is in after obtaining add location, such as the following examples.
[cpp] view plaincopy- void *
- ngx_list_push(ngx_list_t*l)
- {
- void *elt;
- ngx_list_part_t *last;
- last = l->last;
- if (last->nelts ==l->nalloc) { //Full list data area
- /* the last part is full, allocate anew list part */
- last =ngx_palloc(l->pool, sizeof(ngx_list_part_t)); //Distribution node(list part)
- if (last == NULL) {
- return NULL;
- }
- last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//The distribution of the node (part) data area
- if (last->elts == NULL) {
- return NULL;
- }
- last->nelts = 0;
- last->next = NULL;
- l->last->next =last; //The distribution of list part into the list
- l->last = last; //And modify list head last pointer
- }
- elt = (char *)last->elts + l->size * last->nelts; //Calculating the position of the next data in the linked list in the data area
- last->nelts++; //The actual storage data number plus 1
- return elt; //Returns the position
- }
Thus, adding elements is actually from the memory pool allocation list node to a list (part) and the actual data area of the node, and modify the linked list node (part) information.
Note 1: with an array of distinction, array data area is full to extend the data space; and the distribution list to each node and data area.
Note 2: each node list (part) data area can be arranged in 1 or more of the elements, the elements can be an integer, it can also be a structure.
Below is a list of 3 node logic structure diagram.
The lines too much, easy to feel dizzy, this figure may be better.
3 an example
The best way to understand and master the open source software than to write some test code, or rewrite the software itself, and the principle and design method of open source software understanding further debugging. This section gives a simple example creates a memory pool from which assigns a list. In this example, each node list (part) can be stored for 5 elements, each element is 4 bytes in size, create a linked list, to add 15 integer elements to the list.
The 3.1 code
[cpp] view plaincopy- /**
- * 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 how to compile
Please refer to the nginx-1.0.4 source code analysis - memory pool structure and memory management in ngx_pool_t. In this paper, a makefile file written as follows.
[cpp] view plaincopy- 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 $@
3.3 operating results [plain] view plaincopy
- # ./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
Memory pool and an array of the examples in (memory) physical structure can refer to Section 2.3 of the map.
4 Summary
-- the list structure makes a comprehensive analysis of the container according to the nginx-1.0.4, including the list data structure, create and add elements to the list. Finally, a simple example to show the reader nginx list to create and add elements to display operation, at the same time a method for compiling the test code to readers.
Posted by Primo at March 13, 2014 - 6:58 PM