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

1. typedef struct ngx_list_part_s ngx_list_part_t;
3. struct ngx_list_part_s { //Struct node
4. void *elts; //Pointing to the node actual data area (for nalloc size of size elements in the data area)
5. ngx_uint_t nelts; //The actual number of storage elements
6. ngx_list_part_t *next; //Pointer to the next node
7. };
9. typedef struct{ //Chain table structure
10. ngx_list_part_t *last; //To the end of the list of a node(part)
11. ngx_list_part_t part; //The first node contains chain in header(part)
12. size_t size; //Each element size
13. ngx_uint_t nalloc; //A number of space containing the list, namely, the actual distribution of the number of small space
14. ngx_pool_t *pool; //Distribution of the node space in the memory pool
15. }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

1. //Create list
2. ngx_list_t*ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
4. //Initialization list
5. static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
6. ngx_uint_tn, size_t size);
8. //Adding elements
9. 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

1. ngx_list_t *
2. ngx_list_create(ngx_pool_t*pool, ngx_uint_t n, size_t size)
3. {
4. ngx_list_t *list;
6. list = ngx_palloc(pool,sizeof(ngx_list_t)); //Distribution chain headers from the memory pool
7. if (list == NULL) {
8. return NULL;
9. }
11. list->part.elts =ngx_palloc(pool, n * size); //Then n*size distribution size region as a linked list data regions
12. if (list->part.elts == NULL) {
13. return NULL;
14. }
16. list->part.nelts = 0; //Initialization
17. list->part.next = NULL;
18. list->last = &list->part;
19. list->size = size;
20. list->nalloc = n;
21. list->pool = pool;
23. return list; //The starting position return header
24. }

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

1. void *
2. ngx_list_push(ngx_list_t*l)
3. {
4. void *elt;
5. ngx_list_part_t *last;
7. last = l->last;
9. if (last->nelts ==l->nalloc) { //Full list data area
11. /* the last part is full, allocate anew list part */
13. last =ngx_palloc(l->pool, sizeof(ngx_list_part_t)); //Distribution node(list part)
14. if (last == NULL) {
15. return NULL;
16. }
18. last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//The distribution of the node (part) data area
19. if (last->elts == NULL) {
20. return NULL;
21. }
23. last->nelts = 0;
24. last->next = NULL;
26. l->last->next =last; //The distribution of list part into the list
27. l->last = last; //And modify list head last pointer
28. }
30. elt = (char *)last->elts + l->size * last->nelts; //Calculating the position of the next data in the linked list in the data area
31. last->nelts++; //The actual storage data number plus 1
33. return elt; //Returns the position
34. }

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

1. /**
2. * ngx_list_t test, to test ngx_list_create, ngx_list_push
3. */
5. #include <stdio.h>
6. #include "ngx_config.h"
7. #include "ngx_conf_file.h"
8. #include "nginx.h"
9. #include "ngx_core.h"
10. #include "ngx_string.h"
11. #include "ngx_palloc.h"
12. #include "ngx_list.h"
14. volatile ngx_cycle_t *ngx_cycle;
16. void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
17. const char *fmt, ...)
18. {
19. }
21. void dump_pool(ngx_pool_t* pool)
22. {
23. while (pool)
24. {
25. printf("pool = 0x%x\n", pool);
26. printf(" .d\n");
27. printf(" .last = 0x%x\n", pool->d.last);
28. printf(" .end = 0x%x\n", pool->d.end);
29. printf(" .next = 0x%x\n", pool->d.next);
30. printf(" .failed = %d\n", pool->d.failed);
31. printf(" .max = %d\n", pool->max);
32. printf(" .current = 0x%x\n", pool->current);
33. printf(" .chain = 0x%x\n", pool->chain);
34. printf(" .large = 0x%x\n", pool->large);
35. printf(" .cleanup = 0x%x\n", pool->cleanup);
36. printf(" .log = 0x%x\n", pool->log);
37. printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
38. pool = pool->d.next;
39. }
40. }
42. void dump_list_part(ngx_list_t* list, ngx_list_part_t* part)
43. {
44. int *ptr = (int*)(part->elts);
45. int loop = 0;
47. printf(" .part = 0x%x\n", &(list->part));
48. printf(" .elts = 0x%x ", part->elts);
49. printf("(");
50. for (; loop <list->nalloc - 1; loop++)
51. {
52. printf("0x%x, ", ptr[loop]);
53. }
54. printf("0x%x)\n", ptr[loop]);
55. printf(" .nelts = %d\n", part->nelts);
56. printf(" .next = 0x%x", part->next);
57. if (part->next)
58. printf(" -->\n");
59. printf(" \n");
60. }
62. void dump_list(ngx_list_t* list)
63. {
64. if (list == NULL)
65. return;
67. printf("list = 0x%x\n", list);
68. printf(" .last = 0x%x\n", list->last);
69. printf(" .part = 0x%x\n", &(list->part));
70. printf(" .size = %d\n", list->size);
71. printf(" .nalloc = %d\n", list->nalloc);
72. printf(" .pool = 0x%x\n\n", list->pool);
74. printf("elements:\n");
76. ngx_list_part_t *part = &(list->part);
77. while (part)
78. {
79. dump_list_part(list, part);
80. part = part->next;
81. }
82. printf("\n");
83. }
85. int main()
86. {
87. ngx_pool_t *pool;
88. int i;
90. printf("--------------------------------\n");
91. printf("create a new pool:\n");
92. printf("--------------------------------\n");
93. pool = ngx_create_pool(1024, NULL);
94. dump_pool(pool);
96. printf("--------------------------------\n");
97. printf("alloc an list from the pool:\n");
98. printf("--------------------------------\n");
99. ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));
100. dump_pool(pool);
102. for (i = 0; i <15; i++)
103. {
104. int *ptr = ngx_list_push(list);
105. *ptr = i + 1;
106. }
108. printf("--------------------------------\n");
109. printf("the list information:\n");
110. printf("--------------------------------\n");
111. dump_list(list);
113. printf("--------------------------------\n");
114. printf("the pool at the end:\n");
115. printf("--------------------------------\n");
116. dump_pool(pool);
118. ngx_destroy_pool(pool);
119. return 0;
120. }

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

1. CXX = gcc
2. CXXFLAGS +=-g -Wall -Wextra
4. NGX_ROOT =/usr/src/nginx-1.0.4
6. TARGETS =ngx_list_t_test
7. TARGETS_C_FILE= $(TARGETS).c
9. CLEANUP = rm-f $(TARGETS) *.o
11. all:$(TARGETS)
13. clean:
14. $(CLEANUP)
16. CORE_INCS =-I. \
17. -I$(NGX_ROOT)/src/core \
18. -I$(NGX_ROOT)/src/event \
19. -I$(NGX_ROOT)/src/event/modules \
20. -I$(NGX_ROOT)/src/os/unix \
21. -I$(NGX_ROOT)/objs \
23. NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o
24. NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o
25. NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
26. NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o
28. $(TARGETS):$(TARGETS_C_FILE)
29. $(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING)$(NGX_ALLOC) $(NGX_LIST) $^ -o $@

3.3 operating results [plain] view plaincopy

1. # ./ngx_list_t_test
2. -------------------------------- create a new pool:
3. -------------------------------- pool = 0x9208020 .d .last = 0x9208048
4. .end = 0x9208420
5. .next = 0x0
6. .failed = 0 .max = 984
7. .current = 0x9208020
8. .chain = 0x0
9. .large = 0x0
10. .cleanup = 0x0
11. .log = 0x0 available pool memory = 984
12. -------------------------------- alloc an list from the pool:
13. -------------------------------- pool = 0x9208020 .d .last = 0x9208078
14. .end = 0x9208420
15. .next = 0x0
16. .failed = 0 .max = 984
17. .current = 0x9208020
18. .chain = 0x0
19. .large = 0x0
20. .cleanup = 0x0
21. .log = 0x0 available pool memory = 936
22. -------------------------------- the list information:
23. -------------------------------- list = 0x9208048 .last = 0x9208098
24. .part = 0x920804c
25. .size = 4
26. .nalloc = 5
27. .pool = 0x9208020
28. elements: .part = 0x920804c .elts = 0x9208064 (0x1, 0x2, 0x3, 0x4, 0x5)
29. .nelts = 5
30. .next = 0x9208078 -->
31. .part = 0x920804c .elts = 0x9208084 (0x6, 0x7, 0x8, 0x9, 0xa)
32. .nelts = 5
33. .next = 0x9208098 -->
34. .part = 0x920804c .elts = 0x92080a4 (0xb, 0xc, 0xd, 0xe, 0xf)
35. .nelts = 5
36. .next = 0x0
37. -------------------------------- the pool at the end:
38. -------------------------------- pool = 0x9208020 .d .last = 0x92080b8
39. .end = 0x9208420
40. .next = 0x0
41. .failed = 0 .max = 984
42. .current = 0x9208020
43. .chain = 0x0
44. .large = 0x0
45. .cleanup = 0x0
46. .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