欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

------- Tor 源码分析第三部分—— 日志设施与智能链表 --------

程序员文章站 2022-07-27 20:36:34
———————————————————————————————————————————————————————————————————————————————————— init_logging()(\tor-0.3.1.8\src\common\log.c)内部逻辑如下图所示: 它的任务是初始化 ......

————————————————————————————————————————————————————————————————————————————————————

init_logging()(\tor-0.3.1.8\src\common\log.c)内部逻辑如下图所示:

 

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


它的任务是初始化 tor 使用的全局日志设施;它首先检测并初始化用于保护日志信息和日志文件的互斥锁(log_mutex),它是一个 tor_mutex_t 对象

—— 请复习前一篇的相关讨论——具体方式为:

 判断相同源文件内的全局变量 log_mutex_initialized 的值—— 0 代表日志互斥锁尚未初始化,那么它就调用 tor_mutex_init()

;显然,实际负责初始化 log_mutex 的是 pthread 库例程 pthread_mutex_init() 、并且把状态标记 log_mutex_initialized 置 1 。

涉及到的全局变量如下图:

 ------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

接下来,它检查一枚全局的 smartlist_t 指针—— pending_cb_messages(基于 CallBack 的日志消息队列)——若该指针为 NULL 则

调用 smartlist_new()(\tor-0.3.1.8\src\common\container.c)来初始化它。

然后检查传入的实参——若为 1,表明禁用启动消息队列,它就把全局变量 queue_startup_messages 修改为 0,意味着在等待配置日志的过程中不保

存消息;事实上,tor_main() 中为该实参传入 0 指示消息应该在早期就记录下来,如下图

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

这种情况下,它再次调用 smartlist_new()来分配构建一个 smartlist_t 结构指针并赋给全局变量 pending_startup_messages,用于

 

处理启动时刻日志消息队列。pending_startup_messages 指向的各类启动消息(待输出)会在日志系统初始化完毕后重新播放出来。

涉及到的全局变量如下图:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

如果你已经头晕了,那么我们就梳理一下目前为止讨论到全局变量和用途吧:

log_mutex—— 保护日志文件和消息的互斥锁;

log_mutex_initialized—— log_mutex 是否初始化;

pending_cb_messages—— 一枚 smartlist_t 指针(smartlist_t*),存储基于 CallBack 的日志消息队列,可用 smartlist_new() 初始化它;

pending_startup_messages—— 一枚 smartlist_t 指针,存储启动时刻日志消息队列,可用 smartlist_new() 初始化它;

queue_startup_messages—— 启动时刻是否记录日志消息;

disable_startup_queue—— init_logging() 的形参,调用者借助它来开启或关闭启动时刻消息队列功能

init_logging() 内部逻辑如下图所示:

 ------- Tor 源码分析第三部分——  日志设施与智能链表 --------

tor 实现了一种容量可调整、可存储任意数据类型的智能链表——smartlist,它由结构体 smartlist_t 

 

(\tor-0.3.1.8\src\common\container.h)来表示。“container”亦即容器,该模块抽象了许多数据结构来当成容器,

smartlist 只是其中之一。

smartlist_t 内有一个指针数组(list),每个元素(void*)可以指向任意类型的数据,且元素数量可调整,这就是它叫智能链表的原因

,如下图:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

注释里写得很清楚:list 数组的大小可调整,调整后需要更新 capacity 字段(当前容量上限);

num_used 字段记录当前元素数,这些元素(void*)指向有效的数据。你需要意识到一点—— 在 num_used 小于等于 capacity 时,

list 的大小不变;num_used 大于 capacity 时,list 就会动态扩展,同时更新 num_used 和 capacity。

对 smartlist_t 的操作由一些精心编写的例程实施,它们都以 smartlist_ 为前缀,其它模块函数无需知晓智能链表的内部细节,

只需调用这些例程来保证安全、正确地使用智能链表即可,这再次体现出数据抽象和封装、以及接口暴露。。。等高级 C 编程技巧!

这些 smartlist 例程原型如下图所示,分析它们的内部逻辑有助于深入理解智能链表的设计思想:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


smartlist_new() 在堆中分配一块内存用于 smartlist_t 结构,然后返回一枚指向该内存块的指针,如下图所示:

 

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

可以看到,实际的分配函数是 tor_malloc(),后者封装了系统库函数 malloc(),并实现 tor 自己的安全分配算法;分配的内存大小

亦即结构体 smartlist_t 的大小(应该是 12 字节),该值在编译阶段计算出来。在返回一枚 smartlist_t 指针前,它还会将 num_used 字段设置为零,

表示尚未加入元素;将 capacity 字段设置为 SMARTLIST_DEFAULT_CAPACITY 宏定义的常量值(16)表示初始的容量上限为 16 枚

void 指针(总大小为 16 * 4 = 64 字节);接下来它就会调用 tor_calloc() 实际分配另一块 64 字节大小的堆内存,用于

存储那些 void 指针,并让 list 字段持有该内存块的地址。smartlist_new() 返回后的堆内存布局如下图所示:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


我在后面分析其它 smartlist_*() 辅助例程时,会将此图扩展以解释它们的作用。

smartlist_free() 销毁一个智能链表,但它并未实际释放堆中分配的 smartlist_t 结构与 void* 数组占据的内存,如下图:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


smartlist_free() 通过调用 tor_free() -> raw_free() -> free() 把传入的 smartlist_t 指针置 NULL 后返回,因此它不会回收

相关的堆内存,如下图所示:

 ------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

smartlist_add() 往智能链表(void* 数组)内加入新元素。

它首先调用 smartlist_ensure_capacity(),检查当前的容量上限是否允许加入,否则会先动态调大这个 void* 数组的容量后再把新元素

追加到尾部。如下图所示:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

注意,它在调用 smartlist_ensure_capacity() 的同时就会通过一枚 smartlist_t 指针递增 num_used 字段值(寓意追加后的

元素数),然后在 smartlist_ensure_capacity() 内部会检查追加后的元素数是否超出当前容量上限,并采取相应措施!

smartlist_ensure_capacity() 处理完毕后,就可以确保作为数组下标的表达式 sl->list[sl->num_used++] 访问到的目标元素在

许可范围内,它被初始化为一枚新的 void 指针,语法解析如下图所示:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

假设当前元素数已达初始上限(num_used = capacity = 16),相关的堆内存智能链表布局如下图:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


执行 smartlist_add() 调用后的堆内存智能链表布局如下图:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


由此可见,smartlist_ensure_capacity() 会按照 2 次幂来扩展 void* 数组的当前容量上限,而 smartlist_add() 在扩展部分

的起始地址处追加元素,扩展部分的其余元素为 NULL,留待后续使用。


现在让我们深入 smartlist_ensure_capacity() 内部研究它的堆内存分配算法,这种每次以 2 的幂扩展的机制在某种程度上类似于

OS 的内核内存分配算法简化版!如下图所示:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------


smartlist_ensure_capacity() 逻辑要点:

① 它是一个内联(inline)例程,这意味着在编译阶段,编译器会直接将其插入到调用者函数的内部,换言之,当我们反汇编

smartlist_add() 时,不会看到类似“call smartlist_ensure_capacity”这种指令,因为后者的逻辑已经被硬编码至前者内部,

这能够减少函数调用、返回时的栈帧创建、销毁等性能开销!

 

② 它的第二个参数类型为 size_t(亦即 unsigned int),这是一种安全表示长度、大小的类型(无负值),如前所述,

smartlist_add() 会为该参数传入递增 1 后的值,而 smartlist_ensure_capacity() 会判断这个更新的值是否超出了 void* 数组

的当前上限;

 

③ 开头部分的一些条件编译块计算 OS/硬件平台支持的 void* 数组最大上限—— SIZE_MAX 定义在平台相关的 limits.h 头文件内,

如下图所示,该头文件位于 Visual Studio 安装目录的 include 子路径下,它的值取决于编译器,比如这里的 0xFFFFFFFF,

就是十进制的 4,294,967,295 ;同理,INT_MAX 的值计算为 2,147,483,647 ;

SIZEOF_VOID_P 的值在 32 位平台上为 4。

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

经过一系列的预计算,最终得出 MAX_CAPACITY(表示 void* 数组的最大上限,以“元素数”为单位)的值为

1,073,741,823 个元素(SIZE_MAX / (sizeof(void*)),也就是说,void* 数组最大到 4 GB

 

④ 用到了 tor_assert() 检查追加后的元素数,当超过最大容量上限时,调用库函数 abort() 终止程序运行;

tor_assert() 在前一篇讲过了。

 

⑤ 如果追加后的元素数在当前容量上限许可内,smartlist_ensure_capacity() 直接返回,不做任何事,它的调用者

可以安心执行后续操作;如果追加后的元素数超出当前上限,则每次按照 2 的幂为倍数增大当前上限,直到能够容纳

追加后的元素数,并且将扩展部分的内存初始化为零,以供后续使用、还要更新 capacity 字段为新的上限。


在分析源码的算法时,往往言词描述显得苍白无力,还是看看下面这张我绘制的 smartlist_ensure_capacity() 内部逻辑吧,

是不是有点 OS 内核内存分配器的影子?

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

我们最后再分析一下 smartlist_ensure_capacity() 内部实际负责扩展内存的 tor_reallocarray(),

以及负责清零内存的 memset() 函数调用,作为对本篇的收场,如下图所示:

------- Tor 源码分析第三部分——  日志设施与智能链表 --------

 

由此我们推测出 init_logging() 以及相关的组件使用 smartlist 来集中管理日志消息。

下一篇将分析第二个条件编译块前的函数调用——monotime_init()。

——————————————————————————————————————————————————————