用户工具

站点工具


about_ngx_3

Nginx主要数据结构分析

1.ngx_str_t

ngx的字符串主要加上了长度的描述:

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

我们看一下ngx_string宏的定义就一目了然:

#define ngx_string(str)     { sizeof(str) - 1, (u_char *) str }

2.ngx_queue_t

ngx_queue_t作为一个双向链表,本身比较容易理解:

typedef struct ngx_queue_s  ngx_queue_t;
 
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

比较容易费解的是ngx_queue_t只保存指针,那么数据如何保存呢?我们来看一下数据获取的方法:

#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

这样便可以理解了。prev指针和next指针可以指向任何结构体,不过结构体中需要保存ngx_queue_t数据结构来保存聊表的指针。我们可以参考:

struct ngx_connection_s {
    void               *data;
    ngx_event_t        *read;
    ngx_event_t        *write;
 
    ngx_socket_t        fd;
 
    ngx_recv_pt         recv;
    ngx_send_pt         send;
    ngx_recv_chain_pt   recv_chain;
    ngx_send_chain_pt   send_chain;
 
    ngx_listening_t    *listening;
 
    off_t               sent;
 
    ngx_log_t          *log;
 
    ngx_pool_t         *pool;
 
    struct sockaddr    *sockaddr;
    socklen_t           socklen;
    ngx_str_t           addr_text;
 
    ngx_str_t           proxy_protocol_addr;
 
#if (NGX_SSL)
    ngx_ssl_connection_t  *ssl;
#endif
 
    struct sockaddr    *local_sockaddr;
    socklen_t           local_socklen;
 
    ngx_buf_t          *buffer;
 
    ngx_queue_t         queue;
 
    ngx_atomic_uint_t   number;
 
    ngx_uint_t          requests;
 
    unsigned            buffered:8;
 
    unsigned            log_error:3;     /* ngx_connection_log_error_e */
 
    unsigned            unexpected_eof:1;
    unsigned            timedout:1;
    unsigned            error:1;
    unsigned            destroyed:1;
 
    unsigned            idle:1;
    unsigned            reusable:1;
    unsigned            close:1;
 
    unsigned            sendfile:1;
    unsigned            sndlowat:1;
    unsigned            tcp_nodelay:2;   /* ngx_connection_tcp_nodelay_e */
    unsigned            tcp_nopush:2;    /* ngx_connection_tcp_nopush_e */
 
    unsigned            need_last_buf:1;
 
#if (NGX_HAVE_IOCP)
    unsigned            accept_context_updated:1;
#endif
 
#if (NGX_HAVE_AIO_SENDFILE)
    unsigned            aio_sendfile:1;
    unsigned            busy_count:2;
    ngx_buf_t          *busy_sendfile;
#endif
 
#if (NGX_THREADS)
    ngx_atomic_t        lock;
#endif
};

在ngx_connection_s中保存了链表的指针:ngx_queue_t queue

3.ngx_array_t

数组的结构如下:

typedef struct {
    void        *elts; //数组首地址
    ngx_uint_t   nelts;//已经使用的元素数量
    size_t       size;//每个元素占用的空间大小
    ngx_uint_t   nalloc;//数组分配的元素数量
    ngx_pool_t  *pool;内存池指针
} ngx_array_t;

可见数组是结合内存池来使用的,我们可以看下数组创建的方法:

ngx_array_t *
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size)
{
    ngx_array_t *a;
 
    a = ngx_palloc(p, sizeof(ngx_array_t));
    if (a == NULL) {
        return NULL;
    }
 
    if (ngx_array_init(a, p, n, size) != NGX_OK) {
        return NULL;
    }
 
    return a;
}

4.ngx_list_t

list其实是一个数组加链表的结合体:

typedef struct ngx_list_part_s  ngx_list_part_t;
 
struct ngx_list_part_s {
    void             *elts;//元素数据指针
    ngx_uint_t        nelts;//第几号元素
    ngx_list_part_t  *next;//下一个元素指针
};
 
 
typedef struct {
    ngx_list_part_t  *last;//链表尾指针
    ngx_list_part_t   part;//链表首个元素
    size_t            size;//每个元素大小
    ngx_uint_t        nalloc;//分配list元素个数
    ngx_pool_t       *pool;
} ngx_list_t;

5.ngx_table_elt_t

ngx_table_elt_t代表hash表中的一个元素,结构如下:

typedef struct {
    void             *value;
    u_short           len;//元素关键字长度
    u_char            name[1];//元素关键字首地址
} ngx_hash_elt_t;

6.ngx_hash_t

ngx的hash表没有链表,如果找不到则往右继续查找空闲的bucket.

void *
ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
{
    ngx_uint_t       i;
    ngx_hash_elt_t  *elt;
 
#if 0
    ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
#endif
 
    elt = hash->buckets[key % hash->size];
 
    if (elt == NULL) {
        return NULL;
    }
 
    while (elt->value) {
        if (len != (size_t) elt->len) {
            goto next;
        }
 
        for (i = 0; i < len; i++) {
            if (name[i] != elt->name[i]) {
                goto next;
            }
        }
 
        return elt->value;
 
    next:
 
        elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
                                               sizeof(void *));
        continue;
    }
 
    return NULL;
}

初始化的结构为:

typedef struct {
        ngx_hash_t       *hash;            //指向普通的完全匹配哈希表
        ngx_hash_key_pt   key;             //哈希方法
 
        ngx_uint_t        max_size;        //哈希表中槽的最大个数
        ngx_uint_t        bucket_size;     //哈希表中一个槽的空间大小,不是sizeof(ngx_hash_elt_t)
 
        char             *name;            //哈希表的名称
        ngx_pool_t       *pool;            //内存池,它负责分配基本哈希列表、前置通配哈希列表、后置哈希列表中所有槽
       ngx_pool_t       *temp_pool;       //临时内存池,它仅存在初始化哈希表之前。用于分配一些临时的动态数组,带通配符的元素初始化时需要用到临时动态数组
} ngx_hash_init_t;

接着我们分析一下初始化方法:

ngx_int_t
ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
{
    u_char          *elts;
    size_t           len;
    u_short         *test;
    ngx_uint_t       i, n, key, size, start, bucket_size;
    ngx_hash_elt_t  *elt, **buckets;
 
    for (n = 0; n < nelts; n++) {
        if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
        {
            ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
                          "could not build the %s, you should "
                          "increase %s_bucket_size: %i",
                          hinit->name, hinit->name, hinit->bucket_size);
            return NGX_ERROR;
        }
    }
 
    test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
    if (test == NULL) {
        return NGX_ERROR;
    }
 
    bucket_size = hinit->bucket_size - sizeof(void *);
 
    start = nelts / (bucket_size / (2 * sizeof(void *)));
    start = start ? start : 1;
 
    if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
        start = hinit->max_size - 1000;
    }
 
    for (size = start; size <= hinit->max_size; size++) {
 
        ngx_memzero(test, size * sizeof(u_short));
 
        for (n = 0; n < nelts; n++) {
            if (names[n].key.data == NULL) {
                continue;
            }
 
            key = names[n].key_hash % size;
            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
 
#if 0
            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: %ui %ui \"%V\"",
                          size, key, test[key], &names[n].key);
#endif
 
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }
 
        goto found;
 
    next:
 
        continue;
    }
 
    ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
                  "could not build optimal %s, you should increase "
                  "either %s_max_size: %i or %s_bucket_size: %i; "
                  "ignoring %s_bucket_size",
                  hinit->name, hinit->name, hinit->max_size,
                  hinit->name, hinit->bucket_size, hinit->name);
 
found:
 
    for (i = 0; i < size; i++) {
        test[i] = sizeof(void *);
    }
 
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }
 
        key = names[n].key_hash % size;
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }
 
    len = 0;
 
    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
            continue;
        }
 
        test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
 
        len += test[i];
    }
 
    if (hinit->hash == NULL) {
        hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
                                             + size * sizeof(ngx_hash_elt_t *));
        if (hinit->hash == NULL) {
            ngx_free(test);
            return NGX_ERROR;
        }
 
        buckets = (ngx_hash_elt_t **)
                      ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
 
    } else {
        buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
        if (buckets == NULL) {
            ngx_free(test);
            return NGX_ERROR;
        }
    }
 
    elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
    if (elts == NULL) {
        ngx_free(test);
        return NGX_ERROR;
    }
 
    elts = ngx_align_ptr(elts, ngx_cacheline_size);
 
    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
            continue;
        }
 
        buckets[i] = (ngx_hash_elt_t *) elts;
        elts += test[i];
 
    }
 
    for (i = 0; i < size; i++) {
        test[i] = 0;
    }
 
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }
 
        key = names[n].key_hash % size;
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
 
        elt->value = names[n].value;
        elt->len = (u_short) names[n].key.len;
 
        ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
 
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }
 
    for (i = 0; i < size; i++) {
        if (buckets[i] == NULL) {
            continue;
        }
 
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
 
        elt->value = NULL; //设置每个桶的结尾为NULL。
    }
 
    ngx_free(test);
 
    hinit->hash->buckets = buckets;
    hinit->hash->size = size;
 
#if 0
 
    for (i = 0; i < size; i++) {
        ngx_str_t   val;
        ngx_uint_t  key;
 
        elt = buckets[i];
 
        if (elt == NULL) {
            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: NULL", i);
            continue;
        }
 
        while (elt->value) {
            val.len = elt->len;
            val.data = &elt->name[0];
 
            key = hinit->key(val.data, val.len);
 
            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: %p \"%V\" %ui", i, elt, &val, key);
 
            elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
                                                   sizeof(void *));
        }
    }
 
#endif
 
    return NGX_OK;
}

总的流程即为: 1.预估需要的桶数量 2.搜索需要的桶数量 3.分配桶内存 4.初始化每一个ngx_hash_elt_t

7.ngx_rbtree_t

ngx_rbtree_t为典型的红黑树结构:

typedef struct ngx_rbtree_node_s  ngx_rbtree_node_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;
};
 
 
typedef struct ngx_rbtree_s  ngx_rbtree_t;
 
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
 
struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};

8.ngx_radix_tree_t

9.ngx_buf_t

10.ngx_chain_t

about_ngx_3.txt · 最后更改: 2018/10/14 15:31 (外部编辑)