nginx_advanced_structure

Posted on Edited on In ,

Overview

nginx provides advanced data structure like array, list, queue, rb tree which are specific to nginx, like array, it can grow dynamically, but not support free element back to array, list actually is list of several arrays.

array

array will increase dynamically if no more space for use. but it’s better to allocate enough element at initialization.
as when increase array size, move original data from old array to new array, so that new array has whole data, can iterate it to get all elements. but the new address may be not equal old(a->elts), the original array is not freed at all, because user still points to old part and access the element that get from old array as user has that pointer, new element is created from the new array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
+-----+     +------+               +--------+    +---------+
|     |     |      |               |        |    |         |
|  e1 |     | e2   |               |  e3    |    |  e4     |
+--+--+     +--+---+               +--------++   +------+--+
   |           |                             |          |
   |           |   +------+        +-------+ |          |
   |           |   |      |        |       | |          |
   |           +-->+  12  |        |  12   | |          |
   |               |      |        |       | |          |
   |               +------+        +-------+ |          |
   |               |      |        |       | |          |
   +-------------> |  13  |        |  13   | |          |
                   +------+        |       | |          |
                                   +-------+ |          |
                                   |       | |          |
                                   |  14   +<+          |
                                   |       |            |
                                   +-------+            |
                                   |       |            |
                                   |  15   +<-----------+
                                   |       |
                                   +-------+

e1 and e2 still point to old array after double array
e3 and e4 point to new array, but the first two elements still have the same info with old array

limitation

  • NOT support decrease array size
  • NOT support free element back to array
  • Only support free the whole array

data structure

1
2
3
4
5
6
7
8
typedef struct {
    void        *elts;      /* address of nalloc * size */
    ngx_uint_t   nelts;     /* in use counter */
    size_t       size;      /* size of the element */
    ngx_uint_t   nalloc;    /* total elements can be used */
    ngx_pool_t  *pool;
} ngx_array_t;

API

1
2
3
4
5
6
7
8
9
/* example to use: */
typedef struct {
    ngx_int_t id;
} my_element_t;

/* initialization size: 4 my_element_t */
ngx_array_t *my_array = ngx_array_create(pool, 4, sizeof(my_element_t));
my_node = ngx_array_push(my_array);
my_node->id = 1;

list

nginx list is a list of array(fixed size, nalloc * size) each list part is an array(fixed size), list stores the header part and last part.

when request an element from the list, it checks if the last array is used up or not, if not, gets it, otherwise creates a new array, get one element from it.

Note

  • list is good for dynamic element size, but not good for free ops
  • The array in the list is used once only when it’s last
    later on even you free elements back to the array, if it’s not last anymore, never use it anymore.
  • Never delete element of list as it’s dangerous as it related data movement

data structure

1
2
3
4
5
6
7
8
9
10
11
12
13
struct ngx_list_part_s {
    void             *elts;     /* header of the continuos memory */
    ngx_uint_t        nelts;    /* used counter of this part */
    ngx_list_part_t  *next;     /* next part of the list */
};

typedef struct {
    ngx_list_part_t  *last;     /* the last part */
    ngx_list_part_t   part;     /* the first part */
    size_t            size;     /* size of each element */
    ngx_uint_t        nalloc;   /* a list can have several parts, each part can take nalloc continuous memory */
    ngx_pool_t       *pool;
} ngx_list_t;

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct {
    ngx_int_t id;
} my_element_t;

/* 4 elements for each array in the list */
ngx_list_t *mylist = ngx_list_create(pool, 4, sizeof(my_element_t));
my_element_t *node = ngx_list_push(mylist);
node->id = 2;

/* the iteration through the list: */
part = &mylist.part;
data = part->elts;

for (i = 0 ;; i++) {
    if (i >= part->nelts) {
        if (part->next == NULL) {
            break;
        }
        part = part->next;
        data = part->elts;
        i = 0;
    }
    ...data[i] ...
}

queue

ngx_queue_t is just for linking, data area must be allocated /freed by user, ngx_queue is bidirectional list.

it supports:

  • insert node at head/tail
  • get head/tail node
  • empty check
  • remove a node
  • get prev/next node of the given one
  • sort
  • join/split list

data structure

1
2
3
4
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* example to use: */
typedef struct my_node {
    ngx_queue_t q_node;
    xxx;
    yyy;
} my_node_t;

ngx_queue_t head;
my_node_t node;

ngx_queue_init(&head)
ngx_queue_insert_head(&head, &node.q_node)

ngx_queue_empty(&head);
ngx_queue_head(&head);
ngx_queue_last(&head);
ngx_queue_remove(&node);

rb tree

red/back tree is balanced binary search tree.

nginx rb tree

balance:

  • when delete/insert a node, the tree may be rotated to make the depth small,hence quick search

binary:

  • each node have at most two child left/right

search:

  • the left node is smaller than its parent
  • the right node is large than it’s parent
  • as it’s sorted, so each node must have a key(integer)

Note
By default, key must be unique, if insert a node with same key the previous one will be replaced, BUT you can define custom ‘insert’ method to overwrite the default, hence allow two nodes can have the same key in the tree.

data structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct ngx_rbtree_s {
    /* root can be change after insert or delete as it may rotate
    ngx_rbtree_node_t     *root;
    /* sentinel is a node with black color, if node has no left/right child, set
     * its left/right child with sentinel to meet rb tree required
     */
    ngx_rbtree_node_t     *sentinel;
    /* 'insert' method, how to insert a node in the tree
     * you can define your own to allow same key
     * actually nginx provides such way to us
     */
    ngx_rbtree_insert_pt   insert;
};

typedef ngx_uint_t  ngx_rbtree_key_t;
typedef ngx_int_t   ngx_rbtree_key_int_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* example to use */
typedef struct my_node {
  xxx
  ngx_rbtree_node_t rb_node;
} my_node_t;

my_node_t node;
ngx_rbtree_t rbtree;
ngx_rbtree_node_t sentinel;

ngx_rbtree_init(&rbtree, &sentinel, ngx_rbtree_insert_value);

node.rb_node.key = 1;
ngx_rbtree_insert(&rbtree, &node.rb_node);

hash

Hash is for quick searching, elements are distributed at different buckets based on hash_value % bucket_count, inside each bucket, it’s an array, compared one by one, so for hash, the important are hash function and bucket counter to distribute element evenly to reduce conflict. nginx has built-in hash function and bucket count calculated by nginx itself.

hash layout

data structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
typedef struct {
    /* each element is <key, value> pair
     * key: name
     * value: any value
     */
    void             *value;
    /* as you can see each element is not fixed!!
     * each element size = sizeof(void*) + sizeof(u_short) + 1 + len
     */
    u_short           len;
    u_char            name[1];
} ngx_hash_elt_t;

typedef struct {
    /* bucket address */
    ngx_hash_elt_t  **buckets;
    /* the bucket counts */
    ngx_uint_t        size;
} ngx_hash_t;

typedef struct {
    /* passed in parameter -->converted to ngx_hash_elt_t */
    ngx_str_t         key;
    ngx_uint_t        key_hash;
    void             *value;
} ngx_hash_key_t;

/* Above are three must structures for hash */



typedef struct {
    ngx_hash_t        hash;
    void             *value;
} ngx_hash_wildcard_t;

/* ngx_hash_combined_t is not a must for hash, but a helper for nginx to use for some case
 * to create different hashes for different types, like this
 * server_name abc.com *.example.com test.com.*;
 */
typedef struct {
    ngx_hash_t            hash;    /* abc.com */
    ngx_hash_wildcard_t  *wc_head; /* *.example.com */
    ngx_hash_wildcard_t  *wc_tail; /* test.com.* */
} ngx_hash_combined_t;

typedef struct {
    ngx_hash_t       *hash;     /* passed in if NULL, created inside init function */
    ngx_hash_key_pt   key;
    ngx_uint_t        max_size; /* max bucket count, how many buckets */
                                /* the real bucket count is calculated based on hash keys */
    ngx_uint_t        bucket_size; /* how many bytes used by each bucket */

    char             *name;
    ngx_pool_t       *pool;
    ngx_pool_t       *temp_pool; /* used for wildcard hash_init to allocate memory for checking conflict */
} ngx_hash_init_t;

/* helper structure to add keys to the keys_arrays
 * it supports key conflict checking
 * then pass each key array to hash_init
 */
typedef struct {
    ngx_uint_t        hsize; /* bucket number */
    ngx_pool_t       *pool;
    ngx_pool_t       *temp_pool;

    /* key array of exact match like abc.com*/
    ngx_array_t       keys; /* key array, each of ngx_hash_key_t */
    ngx_array_t      *keys_hash; /* bucket array, each bucket is array of ngx_str_t temporary used for checking conflict when creating ngx_hash_key_t */
   
    /* key array of wc_head like *.test.com */
    ngx_array_t       dns_wc_head;
    ngx_array_t      *dns_wc_head_hash;

    /* key array of wc_tail like abc.test.* */
    ngx_array_t       dns_wc_tail;
    ngx_array_t      *dns_wc_tail_hash;
} ngx_hash_keys_arrays_t;

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* without helper function for hash keys */
ngx_hash_init_t  hash;
ngx_array_t      keys_array;
ngx_hash_key_t  *hk;

/* add temporary hash key, no key conflicting check */
ngx_array_init(&keys_array, cf->temp_pool, 32, sizeof(ngx_hash_key_t));
hk = ngx_array_push(&keys_array);
hk->key = "test";
hk->key_hash = ngx_hash_key_lc("test", 4);
hk->value = XX; //anything you want

hash.hash = NULL;
hash.key = ngx_hash_key_lc;
hash.max_size = 2048;
hash.bucket_size = 64;
hash.name = "test_hash";
hash.pool = cf->pool;
hash.temp_pool = NULL;

/* add hash keys to hash buckets */
ngx_hash_init(&hash, keys_array.elts, keys_array.nelts);

/* finding */
ngx_uint_t hash_value;
hash_value = ngx_hash_key_lc("test", 4);
ngx_hash_find(hash.hash, hash_value, "test", 4);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// with helper function
ngx_hash_init_t  hash;
ngx_hash_keys_arrays_t keys_array;
// few keys
ngx_hash_keys_array_init(&keys_array, NGX_HASH_SMALL);

//add keys to helper array(wildard support and conflict checking!!!)
ngx_hash_add_key(&keys_array, "test", XXX, NGX_HASH_WILDCARD_KEY);
ngx_hash_add_key(&keys_array, "*.test", YYY, NGX_HASH_WILDCARD_KEY);
ngx_hash_add_key(&keys_array, "test.*", ZZZ, NGX_HASH_WILDCARD_KEY);

hash.hash = NULL;
hash.key = ngx_hash_key_lc;
hash.max_size = 2048;
hash.bucket_size = 64;
hash.name = "test_hash_helper";
hash.pool = cf->pool;

if (keys_array.keys.nelts) {
    ngx_hash_init(&hash, keys_array.keys.elts, keys_array.keys.nelts);
    hash.temp_pool = NULL;

    ngx_hash_t *hash_normal = hash.hash; // save hash
}

if (keys_array.dns_wc_head.nelts) {
    ngx_qsort(keys_array.dns_wc_head.elts,
              (size_t) keys_array.dns_wc_head.nelts,
              sizeof(ngx_hash_key_t), xx_compare_helper);

    hash.temp_pool = XXX; //must set
    ngx_hash_wildcard_init(&hash, keys_array.dns_wc_head.elts, keys_array.dns_wc_head.nelts);
    ngx_hash_t *hash_head = hash.hash; //save
}

if (keys_array.dns_wc_tail.nelts) {
    ngx_qsort(keys_array.dns_wc_tail.elts,
              (size_t) keys_array.dns_wc_tail.nelts,
              sizeof(ngx_hash_key_t), xx_compare_helper);

    hash.temp_pool = XXX; // must set
    ngx_hash_wildcard_init(&hash, keys_array.dns_wc_tail.elts, keys_array.dns_wc_tail.nelts);
    ngx_hash_t *hash_tail = hash.hash; //save
}