数组是比较简单的一个结构，如下所示：
core/ngx_array.h
struct ngx_array_s {
void *elts; //数组元素所在的内存地址
ngx_uint_t nelts; //数组中已有的元素个数
size_t size; //数组中每个元素的大小
ngx_uint_t nalloc; //已分配空间中可存放的元素个数
ngx_pool_t *pool; //内存池指针
};
1. 创建数组的操作如下所示：
1. 首先在内存池pool中申请一小片内存，用于ngx_array_s结构
2. 将数组的元素大小size和个数nalloc相乘，计算出数组所需内存，并在内存池pool中申请一片内存，用于存放元素
+-----------------+----------+--------+----+-----------+
| ngx_array_s | elem1 | elem2 | .... | elemn |
+-----------------+----------+--------+----+-----------+
代码见core/ngx_array.c的ngx_array_create函数：
a = ngx_palloc(p, sizeof(ngx_array_t)); 申请数组的数据结构的内存
a->elts = ngx_palloc(p, n * size); 申请数组内的元素的内存
2. 加入元素：
当数组不满的时候，直接将元素放入适当的位置即可。
当数组中已有元素的个数nelts等于数组中可存放元素个数时，若要再添加元素，则需要先扩展元素内存的大小，nginx采取的策略是扩展为原来大小的2倍
扩展方法分两种情况：
1. 元素内存之后的连续的内存尚未使用，则直接将内存池的空闲指针向后移动即可
2. 元素内存之后的连续的内存已被使用，则重新从内存池中空闲内存中申请一块可以存放nalloc*2个元素的内存，并将原来的nalloc个元素复制过去。
2.1 情况1：
ngx_array_s的elts指针指向数组内元素的起始位置，加上数组内元素的大小(元素大小和元素个数的乘积)，即可算出数组元素的结尾位置aend。内存池pool有一个last指针，指向当前空闲内存的位置，如果aend==last，则表示数组后面的空间是空闲的，如果空闲空间的大小足够放下一个元素，则可以直接将pool的free指针向后移动，即可实现ngx_array的扩展。
+-----------------+----------+--------+----+-----------+------------+
| ngx_array_s | elem1 | elem2 | .... | elemn | newelem |
+-----------------+----------+--------+----+-----------+------------+
代码见core/ngx_array.c的ngx_array_push函数
if ((u_char *) a->elts + size == p->last //元素后面的空间是空闲的
&& p->last + a->size <= p->end) //并且空间空间足够
{
p->last += a->size; //内存池的指针向后移动
a->nalloc++; //本数组的可容纳元素个数加1
}
2.2 情况2：
如果数组元素的结尾位置的pool的last指针不等，意味着数组元素后面被其它数据(something)占用了，就去pool的空闲空间中申请一块更大的内存，nginx采用原来大小的2倍，然后将原来的nalloc个元素(elem1-n)复制到新内存中(xelem1-n)，并加入新元素(newelem)。
+-----------------+----------+--------+----+-----------+-------------+----------+--------+----+-----------+-----------+----+---------+
| ngx_array_s | elem1 | elem2 | .... | elemn | something | xelem1 | xelem2| .... | xelemn | newelem | ... | elem2n |
+-----------------+----------+--------+----+-----------+-------------+----------+--------+----+-----------+-----------+----+---------+
代码见core/ngx_array.c的ngx_array_push函数：
else
{
new = ngx_palloc(p, 2 * size); //申请新内存
ngx_memcpy(new, a->elts, size); //拷贝旧元素
a->elts = new; //修改元素内存指针
a->nalloc *= 2; //修改可容纳元素个数
}
3. 释放数组：
nginx 释放数组的方式很简单，和创建数组的方式相似：
如果元素的后面是空闲内存，即元素与空闲内存是连续的，则直接移动pool的last指针，将元素占用的内存加入空闲内存；然后判断数组的数据结构后面是否空闲内存，如果是则移动pool的last指针，将数组的数据结构内存加入空闲内存。
第一步将元素归还pool
+-----------------+----------+--------+----+-----------+
| ngx_array_s | elem1 | elem2 | .... | elemn |
+-----------------+----------+--------+----+-----------+
去除元素后，pool的last指针前移，第二步将结构归还pool
+-----------------+
| ngx_array_s |
+-----------------+
代码见core/ngx_array.c的ngx_array_destroy函数
if ((u_char *) a->elts + a->size * a->nalloc == p->last) {//连续内存
p->last -= a->size * a->nalloc;//释放元素
}
if ((u_char *) a + sizeof(ngx_array_t) == p->last) {//连续内存
p->last = (u_char *) a;//释放数组数据结构
}
问题：
数组的设计很简单，和C++的vector设计基本一致。
特别的地方是：它从已经申请的pool中申请与释放内存，并不需要与操作系统接口调用，因此效率更好。
但是很明显这里没有处理碎片，例如先申请一个2个元素的数组a，再申请一个3个元素的数组b，再往a中加入3个元素，则a的原来两个元素()的内存就没有用了。但是也没有指针指向这块内存，只有等pool失效的时候才会回收。
+-----------+----------+--------+----------+--------+--------+---------+--------+---------+----+---------+
| array a | elem1 | elem2 | array_b | elem1 | elem2 | elem3 | xelem1| xelem2 | ... | elem4 |
+-----------+----------+--------+----------+--------+--------+---------+--------+---------+----+---------+
1. 申请产生空洞
向a中加入第3个元素时，elem2后面已经被array_b占用，所以要申请原来大小的2倍(2*2=4)的新内存(xelem1-4)。
并将array_a的eles指针指向这块新内存。此时黑体的elem1和elem2已经无人管理了，只有等pool失效的时候才能归还。
2. 释放产生空洞
如果此时释放数组b，数组b的结尾元素elem3，而pool的last指向数组a的elem4的尾部，明显二者不同，所以数组b的内存也不能归还pool。
但是由于nginx还有对pool的管理，所以不这个空洞只是暂时的，当pool销毁时，整个pool的内存都会归还，空洞随之消失。
阅读(817) | 评论(0) | 转发(0) |
