Nginx source code analysis - linked list structure ngx_list_t

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

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;
  2. struct ngx_list_part_s { //Struct node
  3. void *elts; //Pointing to the node actual data area (for nalloc size of size elements in the data area)
  4. ngx_uint_t nelts; //The actual number of storage elements
  5. ngx_list_part_t *next; //Pointer to the next node
  6. };
  7. typedef struct{ //Chain table structure
  8. ngx_list_part_t *last; //To the end of the list of a node(part)
  9. ngx_list_part_t part; //The first node contains chain in header(part)
  10. size_t size; //Each element size
  11. ngx_uint_t nalloc; //A number of space containing the list, namely, the actual distribution of the number of small space
  12. ngx_pool_t *pool; //Distribution of the node space in the memory pool
  13. }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);
  3. //Initialization list
  4. static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
  5. ngx_uint_tn, size_t size);
  6. //Adding elements
  7. 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;
  5. list = ngx_palloc(pool,sizeof(ngx_list_t)); //Distribution chain headers from the memory pool
  6. if (list == NULL) {
  7. return NULL;
  8. }
  9. list->part.elts =ngx_palloc(pool, n * size); //Then n*size distribution size region as a linked list data regions
  10. if (list->part.elts == NULL) {
  11. return NULL;
  12. }
  13. list->part.nelts = 0; //Initialization
  14. list->part.next = NULL;
  15. list->last = &list->part;
  16. list->size = size;
  17. list->nalloc = n;
  18. list->pool = pool;
  19. return list; //The starting position return header
  20. }

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;
  6. last = l->last;
  7. if (last->nelts ==l->nalloc) { //Full list data area
  8. /* the last part is full, allocate anew list part */
  9. last =ngx_palloc(l->pool, sizeof(ngx_list_part_t)); //Distribution node(list part)
  10. if (last == NULL) {
  11. return NULL;
  12. }
  13. last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//The distribution of the node (part) data area
  14. if (last->elts == NULL) {
  15. return NULL;
  16. }
  17. last->nelts = 0;
  18. last->next = NULL;
  19. l->last->next =last; //The distribution of list part into the list
  20. l->last = last; //And modify list head last pointer
  21. }
  22. elt = (char *)last->elts + l->size * last->nelts; //Calculating the position of the next data in the linked list in the data area
  23. last->nelts++; //The actual storage data number plus 1
  24. return elt; //Returns the position
  25. }


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


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
  3. NGX_ROOT =/usr/src/nginx-1.0.4
  4. TARGETS =ngx_list_t_test
  5. TARGETS_C_FILE= $(TARGETS).c
  6. CLEANUP = rm-f $(TARGETS) *.o
  7. all:$(TARGETS)
  8. clean:
  9. $(CLEANUP)
  10. CORE_INCS =-I. \
  11. -I$(NGX_ROOT)/src/core \
  12. -I$(NGX_ROOT)/src/event \
  13. -I$(NGX_ROOT)/src/event/modules \
  14. -I$(NGX_ROOT)/src/os/unix \
  15. -I$(NGX_ROOT)/objs \
  16. NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o
  17. NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o
  18. NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
  19. NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o
  20. $(TARGETS):$(TARGETS_C_FILE)
  21. $(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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Primo at March 13, 2014 - 6:58 PM