Nginx source code to learn the basic data structure of ngx_list_t (five)

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

Ngx_list_t introduction

Ngx_list_t is a single linked list container nginx package, its application in nginx is more frequent, such as in the nginx source code in src/http/ngx_http_request.{h, c} HTTP's head is used

Ngx_list_t to store. The linked list structure and our common list is different, the difference is that each node linked list nodes, unlike our common single linked list node (i.e. each

A node can only store one element), ngx_list_t node is actually a fixed size array (or block). In addition, ngx_list_t one-way linked list and a section on the ngx_queue_t bidirectional

The list is different, ngx_queue_t and nginx memory pool, ngx_queue_t is not responsible for the allocation of memory to store the list elements, ngx_queue_t is only responsible for the allocated memory

The elements are connected by two-way linked list. Distribution of ngx_list_t is responsible for the linked list memory (using the nginx memory pool), ngx_list_t using a single linked list to multiple memory blocks connected, each memory block

Multiple elements in contiguous memory (greater than or equal to 1 elements), forms such as "single linked list array +".
Introduction about the nginx memory pool refer to this article, the ngx_queue_t reference this article.


The basic structure of ngx_list_t


Definition in the src/core/ngx_list.{h file, c}:

typedef struct ngx_list_part_s ngx_list_part_t;  
   
struct ngx_list_part_s {  //Each node in the linked list structure
    void          *elts; //Pointing to the node data area (stored nalloc size of size elements can be the data area)  
    ngx_uint_t        nelts;  //The number of stored elements  
    ngx_list_part_t  *next;   //Pointer to the next node list  
};  
   
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;   //Memory pool  
}ngx_list_t;

Chain table structure comprises a first block, and finally a block pointer. Sizeof on 32 bit systems (ngx_list_t) =28, sizeof (ngx_list_part_t) =12. From the above list structure,

For each list node (list part) will be allocated nalloc size size small space, namely the size of (nalloc * size) node data list storage bytes.

The basic operation of ngx_list_t

The basic operation of the ngx_list_t list of a total of 3, were as follows (hypothesis on 32 bit Linux systems):

ngx_list_t* ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size); //Create list

Create a linked list is mainly for the two block of memory, some variable initialization. Elaborate, the first chain of distribution header (28B) share memory, then the distribution of head nodes (including chain header data area (part) n*size size),

The two distribution in the incoming memory pool (pool pointing to the memory pool) in the starting position, finally simple initialization chain headers and return chain header.

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;     //Existing 0 elements  
    list->part.next = NULL;  //There is only one piece
    list->last = &list->part;  //Point to the last piece of
    list->size = size;  //The number of the elements
    list->nalloc = n;  
    list->pool = pool;  
   
    return list;    //The starting position return header  
}
List the logic structure diagram is given below with two nodes:



The ngx_list consists of 2 blocks, a total of n+m elements (i.e. second node elements contained in m<n). Note, only the last block (i.e., last refers to the node) may get a dissatisfied state,

Ngx_list does not define element deletion and chain destruction operation.

static ngx_inlinengx_int_t

ngx_list_init(ngx_list_t*list, ngx_pool_t *pool, ngx_uint_t n, size_t size); //Initialization list

This function is used for objects of type ngx_list_t already exists, but its first node storage elements of the memory space is not distributed, can call this function to give the first node of the list

Allocation of memory space to store the elements. The following code:


static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    list->part.elts = ngx_palloc(pool, n * size); // The application of space from the memory pool, let ELTs to point to the space available
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }
    list->part.nelts = 0; 
    list->part.next = NULL;
    list->last = &list->part; // When last began pointing to the first node
    list->size = size;
    list->nalloc = n;
    list->pool = pool;
    return NGX_OK;
}


void*ngx_list_push(ngx_list_t *l) //Adding elements

The add operation does not finish in the actual 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) memory address, and add the data operation in

Add location after adding elements, according to the ngx_list_t last pointer to the location of the last piece, then the element detection the last piece is finished, the judge

ngx_list_part_t->nelts == ngx_list_t->Nalloc (equal to that is full, otherwise the last piece of memory is not used). If not, will the nelts elements. Finally a return to. If full, application

A new chain block, and the tail interpolation to join the list, then the memory block of zeroth element address new applications for return.

The program flow chart are as follows:



Test examples


In order to better understand the knowledge of the above points, write test code, and principles and design ideas to further understanding of open source code debugging. The combination of nginx and ngx_list_t and memory pool

Nginx data type ngx_str_t for test.

Using the nginx string types to the C language package string type ngx_str_t type (file src/core/ngx_string.{h, c} has defined this type), defined as follows:

typedef struct {
    size_t      len;
    u_char     *data;
} ngx_str_t;

Len said the effective length of string,

Data pointer to the string first address, of course the string not necessarily end with data指针指向字符串首地址, 当然该段字符串未必就一定以\0字符结束, 因此在使用时, 必须结合长度len来使用data指针 characters, so when in use, must be combined with the length of len to use the data pointer.


A simple example is given below to create a memory pool from which assigns a list.

In this example, each node list (part) can be stored for 5 elements, each element of the sizeof (ngx_str_t) bytes in size (32 bit system is 8 bytes), create a linked list, add to the list

The 10 elements of type ngx_str_t, ngx_str_t type stored in the memory for a character from a memory pool, each ngx_str_t is 32 bytes. The following code:


//ngx_list_test.c
#include <stdio.h>
#include <string.h>
#include "ngx_config.h"
#include "nginx.h"
#include "ngx_conf_file.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_list.h"

#define N 5
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 print_list(ngx_list_t *l)
{
	
	ngx_list_part_t *p = &(l->part);
	size_t i, n_part=0;
	while(p)
	{
		i=0;
		printf("------------part %d---------------\n", ++n_part);
		for(; i<p->nelts; ++i)
		{
			printf("%s\n", (char*)(((ngx_str_t*)p->elts + i)->data) );
		}
		p = p->next;
	}
	printf("-------------------------------\n");
}


int main()
{
	ngx_pool_t *pool;
	int i;
	char str[] = "hello NGX!";
	ngx_list_t *l;

	pool = ngx_create_pool(1024, NULL);
	printf("Create pool. pool max is %d\n", pool->max);
	l = ngx_list_create(pool, N, sizeof(ngx_str_t));
	printf("Create list. size=%d nalloc=%d\n", l->size, l->nalloc);
	printf("unused memory size is %d\n", (ngx_uint_t)(pool->d.end - 
					pool->d.last) );
	for(i=0; i<10; ++i)
	{
		ngx_str_t *pstr = ngx_list_push(l);
		char *buf = ngx_palloc(pool, 6*N);
		sprintf(buf, "My Id is %d,%s", i+1, str);

		pstr->len = strlen(buf);
		pstr->data = buf;
	}
	print_list(l);
	printf("unused memory size is %d\n", (ngx_uint_t)(pool->d.end - 
					pool->d.last) );
	ngx_destroy_pool(pool);
	return 0;
}
In the code above, the preparation of the corresponding Makefile (not familiar with make can reference here) the following documents:
CC=gcc
C_FLAGS = -g -Wall -Wextra  
DIR=/home/dane/nginx-1.2.0
TARGETS=ngx_list_test
TARGETS_FILE=$(TARGETS).c

all:$(TARGETS)


clean:
	rm -f $(TARGETS) *.o

CORE_INCS=-I $(DIR)/src/core/ \
		  -I $(DIR)/objs/ \
		  -I $(DIR)/src/event \
		  -I $(DIR)/src/event/modules \
		  -I $(DIR)/src/os/unix \
		  -I $(DIR)/Nginx_Pre/pcre-8.32/

NGX_OBJ = $(DIR)/objs/src/core/ngx_palloc.o \
		  $(DIR)/objs/src/core/ngx_string.o \
		  $(DIR)/objs/src/os/unix/ngx_alloc.o \
		  $(DIR)/objs/src/core/ngx_list.o

$(TARGETS):$(TARGETS_FILE)
	$(CC) $(C_FLAGS) $(TARGETS_FILE) $(CORE_INCS) $(NGX_OBJ) -o $@


The above Makefile compile, directly make can produce the executable file ngx_list_test

./Ngx_list_test can run the executable file.

The results are as follows:


Through the result of running the program, the program, and a list of the logic structure diagram, we can know, at first we create a memory pool is 1024 bytes in size memory pool, pool the head node

The memory size (40B), the max memory pool that is the maximum memory available is 1024 - 40 = 984 bytes, then ngx_list_create create list, the memory pool size is 28 bytes in the head list

And the distribution of head nodes (including chain headers in part)The data area(n*size) 5*8=40 bytes, create such a list of total consumption of memory pool size is 28+40 = 68 bytes, so the memory

The memory pool size is 984 - 68 = 916 bytes. The program then add 10 ngx_str_t types of elements in the list, the list is created only to create a linked list nodes, at this time the only

The linked list nodes can only accommodate 5 ngx_str_t string structure, therefore ngx_list_push adds sixth elements will automatically create a new node list, at this time will have to apply for a ngx_list_part_t

Type of structure, its size is 12 bytes, and apply for the node (part) data area of memory (n*size) size is 40 bytes, in addition to the element stored string of 10 ngx_str_t type (each ngx_str_t

From the memory pool for a 32 byte string which accommodates), so the final memory pool remaining memory size of 916 - 5*32 - 12 - 40 - 5*32 = 544 bytes. Results with the program running results.

Through the analysis and test, we can see that the ngx_list uses the block of memory management, it largely reduces the application memory from memory pool frequency, which are helpful to improve the performance.

Reference resources:

http://code.google.com/p/nginxsrp/wiki/NginxCodeReview

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

Posted by Charles at March 05, 2014 - 3:35 PM