nginx高级数据类型(1) - 内存池、动态数组、单向列表、双向链表

2018-07-22 17:54:28

内存池

结构定义

// 描述内存池的信息
typedef struct {
    // 可用内存的起始位置
    // 小块内存每次都从这里分配
    u_char               *last;

    // 可用内存的结束位置
    u_char               *end;

    // 下一个内存池节点
    ngx_pool_t           *next;

    // 本节点分配失败次数
    // 失败超过4次则本节点认为满,不再参与分配
    ngx_uint_t            failed;
} ngx_pool_data_t;


// nginx内存池结构体
// 实际是由多个节点串成的单向链表
// 每个节点分配小块内存
// 但max、current、大块内存链表只在头节点
struct ngx_pool_s {
    // 描述本内存池节点的信息
    ngx_pool_data_t       d;

    // 可分配的最大块
    // 不能超过NGX_MAX_ALLOC_FROM_POOL,即4k
    size_t                max;

    // 当前使用的内存池节点
    ngx_pool_t           *current;

    // 为chain做的优化,空闲缓冲区链表
    ngx_chain_t          *chain;

    // 大块的内存
    ngx_pool_large_t     *large;

    //销毁内存池时会遍历调用
    ngx_pool_cleanup_t   *cleanup;

    ngx_log_t            *log;
};

// 大块内存节点
typedef struct ngx_pool_large_s  ngx_pool_large_t;

// 大块内存节点, 大于4k
// 保存成链表方便回收利用
struct ngx_pool_large_s {
    ngx_pool_large_t     *next;
    void                 *alloc;
};
// 创建内存池
ngx_pool_t *ngx_create_pool(size_t size, ngx_log_t *log);

// 销毁内存池
void ngx_destroy_pool(ngx_pool_t *pool);

// 重置内存池,释放内存
void ngx_reset_pool(ngx_pool_t *pool);

// 分配8字节对齐的内存,速度快,可能有少量浪费
// 分配大块内存(>4k),直接调用malloc
void *ngx_palloc(ngx_pool_t *pool, size_t size);

// 分配未对齐的内存
// 分配大块内存(>4k),直接调用malloc
void *ngx_pnalloc(ngx_pool_t *pool, size_t size);

// 使用ngx_palloc分配内存,并将内存块清零
// 分配大块内存(>4k),直接调用malloc
void *ngx_pcalloc(ngx_pool_t *pool, size_t size);

// 把内存归还给内存池,通常无需调用
// 实际上只释放大块内存
ngx_int_t ngx_pfree(ngx_pool_t *pool, void *p);

创建内存池函数为 ngx_create_pool()。

// 字节对齐分配一个size - sizeof(ngx_pool_t)内存
// 内存池的大小可以超过4k
// 一开始只有一个内存池节点
ngx_pool_t *
ngx_create_pool(size_t size, ngx_log_t *log)
{
    ngx_pool_t  *p;

    // 字节对齐分配内存,16字节的倍数
    // os/unix/ngx_alloc.c
    p = ngx_memalign(NGX_POOL_ALIGNMENT, size, log);
    if (p == NULL) {
        return NULL;
    }

    // 设置可用的内存,减去了自身的大小
    p->d.last = (u_char *) p + sizeof(ngx_pool_t);
    p->d.end = (u_char *) p + size;

    // 一开始只有一个内存池节点
    p->d.next = NULL;
    p->d.failed = 0;

    // 池内可用的内存空间
    size = size - sizeof(ngx_pool_t);

    // 不能超过NGX_MAX_ALLOC_FROM_POOL,即4k
    p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;

    // 刚创建,就使用自己
    p->current = p;

    // 未开始分配,链表都是空
    p->chain = NULL;
    p->large = NULL;

    p->cleanup = NULL;
    p->log = log;

    return p;
}

销毁内存池

销毁内存池为真正的释放所有内存,为 ngx_destroy_pool(),这个函数能帮助我们理解内存池几个核心字段的意思。

// 销毁内存池
void
ngx_destroy_pool(ngx_pool_t *pool)
{
    ngx_pool_t          *p, *n;
    ngx_pool_large_t    *l;
    ngx_pool_cleanup_t  *c;

    // 调用清理函数链表
    for (c = pool->cleanup; c; c = c->next) {
        if (c->handler) {
            c->handler(c->data);
        }
    }

    // 遍历直接释放大块内存块
    // #define ngx_free          free
    for (l = pool->large; l; l = l->next) {
        if (l->alloc) {
            ngx_free(l->alloc);
        }
    }

    // 遍历内存池节点,逐个free
    for (p = pool, n = pool->d.next; /* void */; p = n, n = n->d.next) {
        ngx_free(p);

        if (n == NULL) {
            break;
        }
    }
}

重置内存池

重置内存池会真的释放大块内存,而小块内存并没有释放。

// 重置内存池,释放内存
void
ngx_reset_pool(ngx_pool_t *pool)
{
    ngx_pool_t        *p;
    ngx_pool_large_t  *l;

    // 检查大块内存链表,直接free
    for (l = pool->large; l; l = l->next) {
        if (l->alloc) {
            ngx_free(l->alloc);
        }
    }

    // 遍历内存池节点,逐个重置空闲指针位置
    // 相当于释放了已经分配的内存
    for (p = pool; p; p = p->d.next) {
        p->d.last = (u_char *) p + sizeof(ngx_pool_t);
        p->d.failed = 0;
    }

    // 当前内存池指针
    pool->current = pool;

    // 指针置空,之前的内存都已经释放了
    pool->chain = NULL;
    pool->large = NULL;
}

创建后的内存池内存分配图如下:

内存池销毁后的清理工作可以通过如下函数加入。

// size可以为0,用户需要自己设置ngx_pool_cleanup_t::data指针
ngx_pool_cleanup_t *
ngx_pool_cleanup_add(ngx_pool_t *p, size_t size)
{
    ngx_pool_cleanup_t  *c;

    // 内存池拿一块内存
    c = ngx_palloc(p, sizeof(ngx_pool_cleanup_t));
    if (c == NULL) {
        return NULL;
    }

    // 如果要求额外数据就再分配一块
    // 注意都是对齐的
    if (size) {
        c->data = ngx_palloc(p, size);
        if (c->data == NULL) {
            return NULL;
        }

    } else {
        c->data = NULL;
    }

    // handler清空,之后用户自己设置
    c->handler = NULL;

    // 挂到内存池的清理链表里
    c->next = p->cleanup;
    p->cleanup = c;

    return c;
}

比如我们可以通过如下来在内存池销毁时关闭打开文件描述符

//注册清理文件句柄
    ngx_pool_cleanup_t * cln = ngx_pool_cleanup_add(r->pool, sizeof(ngx_pool_cleanup_file_t));
    cln->handler = ngx_pool_cleanup_file;

    ngx_pool_cleanup_file_t *clnf = cln->data;
    clnf->fd = b->file->fd;
    clnf->name = (u_char *)f_name;
    clnf->log = r->pool->log;
void ngx_pool_cleanup_file(void *data){
    ngx_pool_cleanup_file_t  *c = data;

    ngx_close_file(c->fd);
}


动态数组

typedef struct {
    void        *elts;      //数组的内存位置,即数组首地址
    ngx_uint_t   nelts;     //数组当前的元素数量
    size_t       size;      //数组元素的大小
    ngx_uint_t   nalloc;    //数组可容纳的最多元素数量
    ngx_pool_t  *pool;      //数组使用的内存池
} ngx_array_t;
// 使用内存池创建一个可容纳n个大小为size元素的数组,即分配了一块n*size大小的内存块
// size参数通常要使用sizeof(T)
ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size);

// “销毁”动态数组,不一定归还分配的内存
// 数组创建后如果又使用了内存池则不会回收内存
// 因为内存池不允许空洞
void ngx_array_destroy(ngx_array_t *a);

// 向数组添加元素,用法比较特别,它们返回的是一个void*指针,用户必须把它转换为真正的元素类型再操作
// 不直接使用ngx_array_t.elts操作的原因是防止数组越界,函数内部会检查当前数组容量自动扩容
void *ngx_array_push(ngx_array_t *a);
void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);


// 重新分配数组的内存空间,相当于resize
static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    // 重新初始化数组属性
    array->nelts = 0;
    array->size = size;
    array->nalloc = n;
    array->pool = pool;

    // 重新分配内存,原内存不释放
    array->elts = ngx_palloc(pool, n * size);
    if (array->elts == NULL) {
        return NGX_ERROR;
    }

    return NGX_OK;
}


单向列表

ngx_list_t 相当于一个数组容器,ngx_list_part_t 才是真正存储数据的地方,ngx_list_part_t 通过 next 指针相连。

// 链表的节点
typedef struct ngx_list_part_s  ngx_list_part_t;

// 类似ngx_array_t,是一个简单的数组,也可以“泛型”存储数据
// next指针指向链表里的下一个节点
// 可用于存储http头信息
struct ngx_list_part_s {
    void             *elts;     //数组元素指针
    ngx_uint_t        nelts;    //数组里的元素数量
    ngx_list_part_t  *next;     //下一个节点的指针
};
// 定义链表(实际上是头节点+元信息)
// 成员size、nalloc和pool与ngx_array_t含义是相同的,确定了节点里数组的元信息
typedef struct {
    ngx_list_part_t  *last;     //链表的尾节点
    ngx_list_part_t   part;     //链表的头节点
    size_t            size;     //链表存储元素的大小
    ngx_uint_t        nalloc;   //每个节点能够存储元素的数量
    ngx_pool_t       *pool;     //链表使用的内存池
} ngx_list_t;

// 使用内存池创建链表,每个节点可容纳n个大小为size的元素
ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);

//初始化
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);
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }

    list->part.nelts = 0;
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return NGX_OK;
}

ngx_list_t 中包含了第一个  ngx_list_part_t,也就是第一个 ngx_list_part_t 内存在创建 ngx_list_t 结构体时就已经分配了,后面的 ngx_list_part_t 在调用 ngx_list_init 初始化的时候分配,关系大致如下图。

 

双向链表

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};
// 初始化头节点,把两个指针都指向自身
#define ngx_queue_init(q)                          /
    (q)->prev = q;                                 /
    (q)->next = q

// 检查头节点的前驱指针,判断是否是空队列
#define ngx_queue_empty(h)                         /
    (h == (h)->prev)

// 向队列的头插入数据节点
#define ngx_queue_insert_head(h, x)                /
    (x)->next = (h)->next;                         /
    (x)->next->prev = x;                           /
    (x)->prev = h;                                 /
    (h)->next = x


// 在节点的后面插入数据
#define ngx_queue_insert_after   ngx_queue_insert_head


// 向队列的尾插入数据节点
// 在节点前插入数据
#define ngx_queue_insert_tail(h, x)                /
    (x)->prev = (h)->prev;                         /
    (x)->prev->next = x;                           /
    (x)->next = h;                                 /
    (h)->prev = x


// 获取队列的头尾指针,可以用它们来实现队列的正向或反向遍历
// 直到遇到头节点(ngx_queue_sentinel)停止
#define ngx_queue_head(h)                          /
    (h)->next


// 获取队列的头尾指针,可以用它们来实现队列的正向或反向遍历
// 直到遇到头节点(ngx_queue_sentinel)停止
#define ngx_queue_last(h)                          /
    (h)->prev


// 返回节点自身,对于头节点来说就相当于“哨兵”的作用
#define ngx_queue_sentinel(h)                      /
    (h)


// 节点的后继指针
#define ngx_queue_next(q)                          /
    (q)->next


// 节点的前驱指针
#define ngx_queue_prev(q)                          /
    (q)->prev


// “删除”当前节点,实际上它只是调整了节点的指针
// 把节点从队列里摘除,并没有真正从内存里删除数据
#if (NGX_DEBUG)

#define ngx_queue_remove(x)                        /
    (x)->next->prev = (x)->prev;                   /
    (x)->prev->next = (x)->next;                   /
    (x)->prev = NULL;                              /
    (x)->next = NULL

#else

#define ngx_queue_remove(x)                        /
    (x)->next->prev = (x)->prev;                   /
    (x)->prev->next = (x)->next

#endif


// 拆分队列
#define ngx_queue_split(h, q, n)                   /
    (n)->prev = (h)->prev;                         /
    (n)->prev->next = n;                           /
    (n)->next = q;                                 /
    (h)->prev = (q)->prev;                         /
    (h)->prev->next = h;                           /
    (q)->prev = n;


// 合并两个队列
#define ngx_queue_add(h, n)                        /
    (h)->prev->next = (n)->next;                   /
    (n)->next->prev = (h)->prev;                   /
    (h)->prev = (n)->prev;                         /
    (h)->prev->next = h;


// 从作为数据成员的ngx_queue_t结构访问到完整的数据节点
#define ngx_queue_data(q, type, link)              /
    (type *) ((u_char *) q - offsetof(type, link))


ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);

// 使用一个比较函数指针对队列元素排序,但效率不是很高
void ngx_queue_sort(ngx_queue_t *queue,
    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));

用法

#include <stdio.h>
#include <stddef.h>
#include "queue.h"

typedef struct tmp tmp_t;

struct tmp{
	char *name;
	int age;
	ngx_queue_t q;
};

int main(){
    tmp_t tmp1;
    tmp_t tmp2;
    tmp_t tmp3;
    
    //其实就是 ngx_queue_t sen;
    ngx_queue_t ngx_queue_sentinel(sen);  //声明哨兵
    
    tmp_t *ttt;
    
    tmp1.name = "tmp1";
    tmp1.age = 22;
    
    tmp2.name = "tmp2";
    tmp2.age = 23;
    
    tmp3.name = "tmp3";
    tmp3.age = 24;
    
    
    ngx_queue_init(&sen);
    ngx_queue_insert_tail(&sen, &tmp2.q);
    ngx_queue_insert_tail(&sen, &tmp3.q);
    
	ttt = ngx_queue_data(sen.next, tmp_t, q);
	printf("%d %s\n", ttt->age, ttt->name);
	
	ttt = ngx_queue_data(sen.next->next, tmp_t, q);
	printf("%d %s\n", ttt->age, ttt->name);
}
[root@192 c]# gcc main.c 
[root@192 c]# ./a.out 
23 tmp2
24 tmp3


备注

1.nginx版本为 1.14.0。
2..原文地址http://www.freecls.com/a/2712/d4


©著作权归作者所有
收藏
推荐阅读
简介
天降大任于斯人也,必先苦其心志。