1. ngx_pool_t

1.1 概述

ngx_pool_t提供内存分配接口。

ngx_pool_t对大块内存和小块内存的分配使用不同的策略。

对于大块内存（超过指定阈值，一般是内存的页大小4096），调用malloc()动态分配。

• ngx_pool_t把大块内存保存在一个ngx_pool_large_t中，这是一个单项链表。ngx_pool_t的成员large指向这个链表。

对于小块内存，则是先预分配大的内存块，然后根据需要从中动态分配小块的。

• ngx_pool_data_t用于保存每块预分配内存的信息。它是ngx_pool_t的第一个成员，位于ngx_pool_t的起始位置。
• 所有ngx_pool_data_t实例链接成一个单向链表，保存所有预分配内存。ngx_pool_t的成员current指向当前的预分配内存。如下图中展示了这个链表的两个元素。

• ngx_pool_data_t的成员last和end，分别指向可分配内存的开始和结束位置。成员next指向下一个ngx_pool_data_t实例，也就是下一块预分配内存。

1.2 分配内存

ngx_create_pool()创建这个单向链表的第一个元素。

• 调用ngx_memalign()分配参数size指定大小的内存，作为小块内存的预分配内存。 预分配内存时，指定按16字节对齐。
• 在内存的开始位置保存ngx_pool_t结构，之后的部分真正用于分配小块内存。让ngx_pool_t的成员current指向ngx_pool_t/ngx_pool_data_t结构。

ngx_palloc()从指定的ngx_pool_t实例中分配内存。如果要求大块内存，则调用ngx_palloc_large()，否则调用ngx_palloc_small()。

对于ngx_palloc_small()，

• 从指定的预分配内存块中分配内存。 如前所说，ngx_pool_t的current指定了当前的ngx_pool_data_t元素，而ngx_pool_data_t的成员last又指定可分配内存的位置。
  • 如果要求的内存大小超过可用的内存，则调用ngx_palloc_block()分配更多的预分配内存。ngx_palloc_block()调用ngx_memalign()。分配内存的大小跟第一次分配的大小一样。
  • 设置第一个ngx_pool_data_t的成员next，指向这里创建的第二个ngx_pool_data_t，这样链表中就有了两个元素。
  • 从ngx_pool_data_t.last分配要求的内存。因为是第一次分配，所以一定会成功。
  • 多次分配后，预分配的空间会耗尽。如果每个分配失败超过指定次数，则设置ngx_pool_t的成员current指向链表中的下一个元素。

对于ngx_palloc_large()，

• 调用ngx_alloc()分配指定大小的内存。
• 分配ngx_pool_large_t结构（它是调用ngx_palloc_small()从预分配内存分配的）。设置它的成员指向刚分配的内存。将ngx_pool_large_t链接到ngx_pool_t的ngx_pool_large_t链表，也就是成员ngx_pool_t.large。

1.3 释放内存

ngx_free()负责释放内存。它只是调用free()释放大块内存。实际上小块内存是不能一个一个释放的，nginx的策略是释放就释放全部。

ngx_reset_pool()释放所有大块内存，将ngx_pool_t链表置于未使用状态。

ngx_destroy_pool()释放所有大块内存，也释放ngx_pool_t链表自身占用的内存。

2. ngx_pool_cleanup_t

nginx_pool_t还用于保存“待清理的任务”，这个任务保存在ngx_pool_cleanup_t结构中，从预分配内存中分配。这也是一个单向链表，保存在ngx_pool_t的成员cleanup中。

ngx_pool_cleanup_t的成员handler是任务的处理函数，成员data是处理函数的参数。

3. ngx_array_t

ngx_array_t实现了数组。

• 成员size是元素大小，nalloc是数组长度（元素个数）。
• 成员elts是指向的数据块的起始位置，nelts是当前保存的元素个数。

ngx_array_create()创建数组。

• 调用ngx_palloc()从ngx_pool_t中分配ngx_array_t结构。
• 调用ngx_array_init()初始化这个结构。其中调用ngx_palloc()从ngx_pool_t中分配数据块内存，并将ngx_array_t的成员elts指向它。

ngx_array_push()从数组中得到一个可用的元素。

• 如果数组中还有没用的元素，则返回它。
• 如果没有，则分两种情况。
  • 如果ngx_array_t所在预分配内存能放得更多元素，则扩展ngx_array_t。
  • 如果预分配内存放不下，则调用ngx_palloc()为数据块重新分配内存。这里不释放ngx_array_t的内存，这是预分配内存的策略。

4. ngx_list_t

ngx_list_create()实现单向链表。与一般链表不同的是，它的链表中每一个元素中保存的是一个数组。下图是包含两个ngx_list_part_t元素的链表。

• ngx_list_part_t的成员elts指向一个数组。
• ngx_list_part_t的成员指向下一个链表元素，而ngx_list_t的成员last指向链表的当前元素。

ngx_list_create()创建一个链表。

• 调用ngx_palloc()分配ngx_list_t结构。ngx_list_part_t是ngx_list_t的一部分，所以同时也分配了ngx_list_part_t结构。将ngx_list_t的成员last指向ngx_list_part_t。
• 给ngx_list_part_t的成员elts分配一个数组。

ngx_list_push()从链表中得到一个可用的位置。

• ngx_list_t的成员last指向当前的ngx_list_part_t。
  • 如果它的数组中还有可用位置，则返回当前位置。
  • 如果没有可用位置，则从调用ngx_palloc()分配一个ngx_list_part_t结构，将它链入ngx_list_t的ngx_list_part_t链表，也就是成员last。

5. ngx_queue_t

ngx_queue_t是一个双向链表。

• 成员prev指向前一个元素，成员next指向后一个元素。
• ngx_queue_insert_after()、ngx_queue_add()、ngx_queue_remove()分别向ngx_queue_t中添加元素。

使用ngx_queue_t的方式是，在结构中包含ngx_queue_t，就可以把结构串联起来。如下面的示意图。

ngx_queue_data()可以根据ngx_queue_t成员在结构中的位置偏移，从成员地址计算结构地址。

6. ngx_rbtree_t

ngx_rbtree_t实现红黑树，ngx_rbtree_node_t是树上的节点。

对于ngx_rbtree_node_t，

• 成员key是键值，data是数据。color是红黑节点标志。
• 成员left和right分别是左右子节点，parent是父节点。

对于ngx_rbtree_t，

• 成员root是树根。
• 成员sentinel是“哨兵”节点。如果一个节点没有子节点，就将该子节点设置为“哨兵”节点。所以访问“哨兵”节点就意味着访问到数的叶子节点了。
• 使用ngx_rbtree的方式，一是定义自己的叶子节点，其中包括ngx_rbtree_node_t结构。二是重新实现ngx_rbtree_t的虚拟函数ngx_rbtree_insert_pt()，根据节点的数据大小，将它插入树的正确位置。
• ngx_rbtree_insert()向红黑树中插入新节点，它调用虚拟函数ngx_rbtree_insert_p()插入新节点，然后如果需要，调整红黑树，使它重新符合红黑树规范。
• ngx_rbtree_delete()从树中删除节点。
• ngx_rbtree_min()得到树的最小节点，ngx_rbtree_next()得到下一个节点。这样就可以遍历树了。