2025-04-10 08:00:00

如何进行条件分支预测器实验¶

背景¶

最近针对各种条件分支预测器（Conditional Branch Predictor）做了在各种 benchmark 上的实验，在此记录一下做这个实验的流程。

流程¶

说到做条件分支预测器实验，到底是做什么呢？其实就是针对未来的处理器中的条件分支预测器的设计，在提前准备好的一些 benchmark 上进行模拟，观察它的预测准确性。既然是未来的处理器，那么硬件肯定是没有的，如果直接用 RTL 去实现新的预测器，再用 RTL 仿真，结果固然准确，但这还是太复杂并且太慢了。所以在前期的时候，首先会构建一个单独的条件分支预测器的实验环境，在只考虑条件分支指令、不考虑其他指令的情况下，单纯来观察预测的效果，从而可以实现比较快速的设计迭代。

为了达成这个目的，需要：

1. 提前准备好一些 benchmark，提取出这个 benchmark 中所涉及到的条件分支 trace，以及条件分支预测器所需要的其他信息
2. 为了进一步缩短模拟的时间和 trace 的大小，利用 SimPoint 等技术来减少要模拟的指令条数
3. 搭建一个条件分支预测器模拟器，在上一步提取出来的 trace 中模拟条件分支预测器的执行，从而得到结果

下面按照这个顺序，分别来讨论一下这个流程。

benchmark 准备¶

比较常见的 benchmark 就是 SPEC INT 2017，当然现在很多论文也会自己去寻找一些其他的 benchmark，不同的 benchmark 它的程序的特性也是不一样的，未来也可能会有新的 benchmark 出来，所以有必要了解从 benchmark 到 trace 的过程。选好了 benchmark 以后，我们需要思考怎么去生成一个 trace：为了减少后续模拟的负担，我们需要从 benchmark 中提取条件分支的执行历史，作为 groundtruth，喂给条件分支预测器，这样才能知道每次预测是否准确。当然了，网上已经有很多现成的 trace，比如 CBP Championship 比赛也都有提供自己的 benchmark trace（P.S. 2025 年的 CBP Championship 正在火热进行中），但读完本文，你应该可以尝试自己完成这个从 benchmark 到 trace 的过程。

那么第一个问题就是，怎么获取 benchmark 中分支指令执行的信息呢？首先来看一组数据，在 amd64 上，用 -O3 编译 SPEC INT 2017 的 benchmark，一共 10 个子 benchmark，加起来运行的指令数大约是 1.6e13 条，其中有大约 2.9e12 条分支指令（包括了有条件和无条件），这个数量是非常巨大的，无论是保存这些执行信息的性能开销，还是需要的存储空间，都是比较巨大的。

考虑到条件分支预测器只需要分支指令的信息，所以只考虑 2.9e12 条分支指令的部分，而不去考虑完整的 1.6e13 条指令，首先可以减少一个数量级。接着，考虑每个分支指令需要记录哪些信息：

1. 知道每一条分支指令的地址、每一条直接分支指令的目的地址
2. 对于执行的每一条条件分支指令，要记录它跳转与否
3. 对于执行的每一条间接分支指令，需要记录它跳转的目的地址

其中第一点，由于条件分支指令本身是不变的（不考虑 JIT），所以只需要存一份就行。而 SPEC INT 2017 所有程序的分支指令加起来大概只有 5e4 的量级，相比 2.9e12 的执行的分支指令数可以忽略不计。第三点，由于间接分支指令通常也是比较少的，而且同一条间接分支指令的目的地址通常来说不会特别多，也有压缩的空间。那么最主要的空间来自于：

1. 虽然条件分支指令数量不多，但是执行的条件分支指令次数很多，每一次执行的可能是不同的条件分支指令，如果要记录当前这次执行的是哪一条条件分支指令，那么这个指令的地址或者一个 id 所占用的空间会很大；如果不记录当前执行的是哪一条分支分支指令，就需要在后续处理的时候，结合可执行程序的汇编来推断，当前执行的是哪一条条件分支指令
2. 其次就是要记录条件分支跳转与否，这一个的开销相对会小一些，只需要一个 bit

由此可以推导出不同的 trace 记录方式：

第一种方式是，遇到条件分支指令时，只记录跳转（Taken）还是不跳转（Not Taken），这种方式保存的数据量最小（平均每个分支只需要比 1 bit 略多的空间），但是后续需要结合汇编，恢复出执行的过程，更进一步还可以压缩那些 return 的目的地址等于对应的 call 指令的下一条指令的地址的情况（Indirect Transfer Compression for Returns）。Intel PT 采用的是这种方法。

第二种方式是，遇到条件分支指令时，不仅记录跳转与否，还记录它执行的是哪一条分支指令。这种方式保存的数据量稍多，假如要支持 5e4 条不同的条件分支指令，为了保存这个 id，就需要 16 位。类似地，也可以只记录跳转了的条件分支指令，那么那些没有跳转的条件分支指令，就需要后续结合汇编或者完整的条件分支指令表来恢复出来。CBP Championship 的 trace 采用的是这种方法。

第一种方法明显空间会更小，以 2.9e12 条执行的分支指令数，大概需要 300GB 的磁盘空间；第二种方法，同样的分支指令数，就需要大概 5.8TB 的磁盘空间。当然了，第二种方法存的数据可以经过无损压缩进一步缩小空间，实测压缩后大概是每分支 0.16 字节（这个数字与所跑的 benchmark 有关系，分支容易被预测的 benchmark 对应更好的压缩率，因为某种意义来说分支预测也是一种无损压缩），只比第一种方法大概每分支 0.14 字节略大。同理，第一种方法存的数据也可以经过无损压缩进一步缩小空间，达到每分支大约 0.018 字节的程度（压缩率也和分支预测准确率有关）。

在评估条件分支预测器的时候，除了知道分支本身，还需要知道执行的指令数，用于计算 MPKI 等，这个可以通过 PMU 单独统计出来，或者直接根据控制流推算出执行的指令数，例如在等长指令的 ISA 上直接用地址差除以指令长度来计算指令数，在变长指令的 ISA 上 Parse ELF 去解析控制流经过的指令：

1. 解析 ELF，用反汇编器得到每条指令的地址，从小到大排序放到数组中
2. 对于每个分支地址和目的地址，查询它对应的指令在指令数组中的下标，记录下来
3. 统计指令数时，每遇到一个跳转的分支，就用当前跳转的分支的分支地址在指令数组中的下标，减去上一个跳转的分支的目的地址在指令数组中的下标，加上一，累加到指令数中

当然了，这里有一些细节，例如如果程序是 PIE，那么需要知道它加载的基地址，从而把运行时的指令地址和 ELF 对应起来；类似地，如果程序加载了 libc 等动态库，也需要知道它们的加载地址。这些信息可以在抓取指令 trace 的同时，顺带记录下来。如果想规避这个麻烦，可以使用静态编译，不过 vdso 依然会动态加载，但 vdso 内指令很少，通常可以忽略不计，可以特判忽略掉。

此外，如果分支预测器需要知道分支指令的 fallthrough 地址（例如 Path History Register），且使用的是变长指令集，还需要记录分支指令的长度。这些需求实现起来都并不复杂，也只需要占用很小的空间。

TB 级别的规模，无论是保存这些数据，还是生成这些数据，或者更进一步在这些数据上模拟条件分支预测器，都会带来很大的负担。因此，需要一个办法来减少要模拟的 trace 长度。

SimPoint¶

SimPoint 是解决这个问题的一个很重要的方法：它观察到了一个很重要的现象，就是这些 benchmark 其实大多数时候是在重复做相同的事情，只不过涉及到的数据不同。这也很好理解，因为很多程序里面都是循环，而循环是很有规律的，我们可以预期程序的行为在时间尺度上也会有一定的周期性。下面是 SimPoint 论文中的一个图，它记录了 gzip-graphic benchmark 的 IPC（每周期指令数，图中的实线）和 L1 数据缓存缺失率（图中的虚线）随着执行过程的变化：

可以看到比较明显的周期性，而涉及到周期性，就会想到利用周期的性质：如果在一个周期上评估它的 IPC 或者分支预测器的准确率，然后外推到其他的周期，是不是大大缩小了执行时间？SimPoint 利用这个思想，设计了如下的步骤：

1. 首先把整个执行过程按照执行的指令数切分成很多个 slice
2. 接着对 slice 进行聚类，使得每一个类内的 slice 的行为类似，这个类就叫做一个 phase
3. 之后做实验的时候，只需要对每个 phase 内的一个 slice 进行实验，评估出它的 IPC 或者其他性能指标，再按照 phase 内的 slice 数量加权平均，就可以得到完整执行过程的性能指标了

这里比较核心的步骤，就是怎么对 slice 聚类？SimPoint 论文采用了机器学习的方法：针对每个 slice，统计它在不同 Basic Block 内执行的时间的比例，把这个统计数据记为 Basic Block Vector；那么聚类，就是针对那些 Basic Block Vector 相近的 Slice，进行 K-Means 算法。

由于 K-Means 算法执行的时候，需要首先知道聚出来多少个类，所以 SimPoint 枚举了若干个不同的类的个数，对每个 K-Means 聚类结果进行打分：BIC（Bayesian Information Criterion），根据打分找到一个聚类效果足够好，但是类又不是特别多的结果。

进一步为了提升聚类的性能，SimPoint 还进行了一次降维操作，把很长的 Basic Block Vector 线性映射到一个比较小的 15 维的向量上。

SimPoint 论文中展示了聚类的效果，还是很可观的：

完成聚类以后，SimPoint 的输出就是若干个 phase，每一个类对应一个 phase，每个 phase 包括：

1. 权重：权重就是这个类中 slice 的个数
2. 代表这个 phase 的一个 slice 的信息，例如它是从第几条指令开始到第几条指令

完成 SimPoint 算法后，得到的 trace 长度大大减小，例如一段原始的长为 1e10 条指令的 trace，以 3e7 条指令为一个 slice，聚类以后，只剩下 10 个 phase，那么需要模拟和保存的 trace 长度只剩下了 3e8 条指令。SimPoint 聚类整个流程的性能大概在每秒 2e8 条分支指令的量级。

回顾前面提到的完整的 SPEC INT 2017 的量级：2.9e12 条执行的分支指令数，经过 SimPoint 处理后，假如每个子 benchmark 拆分成 15 个长度为 1e8 条指令的 phase，那么最终可能只需要 3e10 条指令，这就是一个比较好处理的大小了，以单核每秒模拟 1e7 条分支指令的速度，完整跑一次条件分支预测器实验，可能只需要几十分钟的时间，再加上多核，可以进一步缩短到几分钟。

trace 抓取¶

刚才讨论了很多 trace 的大小以及如何用 SimPoint 压缩空间，那么这个 trace 到底怎么抓取呢？主要有两种方法：

1. 基于硬件已有的 trace，比如 Intel PT，但需要注意，Intel PT 是可能丢失历史的，虽然比例比较小；为了避免丢失历史，建议设置 sysctl kernel.perf_event_paranoid=-1（或者用 root 权限来运行 perf record，即绕过 mlock limit after perf_event_mlock_kb 的限制）来扩大 Intel PT 使用的 buffer 大小，从 32KB 扩大到 1MB（参考 pt_perf），在大小核机器上还要绑定到一个大核上
2. 基于软件的 Binary Instrumentation，即针对分支指令插桩，比如 Pin、DynamoRIO 甚至 QEMU

第一种方法性能是最好的，运行开销比较小，耗费 1.4x 的时间，但是后续处理也比较费劲一些，此外比较依赖平台，ARM 上虽然也有 SPE，但是支持的平台比较少。其他平台就不好说了。

第二种方法性能会差一些，大概会有 30-50x 的性能开销，但是一天一夜也能够把 SPEC INT 2017 跑完。实现的时候，需要注意在遇到分支的时候，首先把信息保存在内存的 buffer 中，buffer 满了再写盘；此外，为了减少磁盘空间以及写盘所耗费的 I/O 时间，可以在内存中一边生成数据一边压缩，直接把压缩好的数据写入到文件中。

实践中，可以先用 Intel PT 抓取 trace，再把 trace 转换为第二种格式，最终的抓取 + 转换的性能开销大概是 15x。大致算法如下：

1. 遍历程序中所有的分支，按照地址从小到大保存起来在数组当中，针对那些直接分支，提前计算好从它的目的地址开始遇到的第一个分支在数组的下标
2. 解析 perf.data 中的 Intel PT packet，提取出其中的 TNT 和 TIP packet，从程序的 entrypoint 开始，沿着 Intel PT 的 trace 重建控制流：条件分支从 TNT packet 获取方向，间接分支从 TIP packet 获取目的地址，
3. 如果分支跳转了，就根据目的地址找到从目的地址开始遇到的下一个分支（二分查找）；如果没有跳转，就直接访问数组的下一个分支
4. 注意 RET compression 的处理：维护 call stack，如果遇到 return 的时候刚好在 TNT packet 中，且对应的 bit 是 Taken，则从 call stack 取出目的地址；一个优化是 call stack 不仅记录地址，还记录从这个地址开始遇到的下一个分支在数组的下标
5. 重建控制流的同时，输出第二种格式的 trace，在内存中完成流式压缩

以上的这些性能开销只是在一个程序上测得的结果，不同的程序上，其性能开销也有很大的不同。

对于动态链接，perf.data 会记录 mmap event；Pin 和 DynamoRIO 都可以对 module load 事件进行插桩。动态库可以从文件系统中访问，vdso 可以从内存中导出。

条件分支预测器模拟¶

在完成了前面的大部分步骤以后，最终就是搭建一个条件分支预测器的模拟器了。其实这一点倒是并不复杂，例如 CBP Championship 或者 ChampSim 都有现成的框架，它们也都提供了一些经典的分支预测器的实现代码，例如 TAGE-SC-L。在它们的基础上进行开发，就可以评估各种条件分支预测器的预测效果了。

实际上，除了条件分支预测器，还有很多其他的实验也可以用类似的方法构建 trace 然后运行。但条件分支预测器有个比较好的特点：它需要的状态比较简单，通常拿之前一段指令做预热即可，不需要 checkpoint；而如果要完整模拟整个处理器的执行，通常需要得到系统的整个状态，比如内存和寄存器，才能继续执行，这时候就可能需要提前把 slice 开始的状态保存下来（checkpoint），或者用一个简单的不精确的模拟器快速计算出 slice 开始的状态（fast forwarding）。

实验数据¶

Trace 抓取¶

在这里列出最终使用的 trace 格式和实验数据：

1. trace 格式：使用第二种 trace 记录方法，每次执行 branch 记录 4 字节的信息，包括 branch id 和是否跳转，使用 zstd 进行无损压缩
2. trace 大小和运行时间统计（GCC 12.2.0，-O3 -static 编译，在 Intel i9-14900K 上实验）：

每分支的空间开销和在 i9-14900K 上测得的 MPKI（Mispredictions Per Kilo Instructions）有比较明显的正相关性：

由于 LTO 对分支数量的影响较大，额外对比了 -O3 和 -O3 -flto 的区别：

LTO 去掉了 9% 的分支指令，对整体性能的影响还是蛮大的，MPKI 的数值也有明显的变化。

时间开销¶

各个步骤需要耗费的时间（单线程）：

1. 抓取 trace：约 20 小时
2. 运行 SimPoint: 约 4 小时
3. 模拟分支预测：约 1 小时

SimPoint¶

考虑到（子）benchmark 之间没有依赖关系，可以同时进行多个 trace/simpoint/simulate 操作，不过考虑到内存占用和硬盘 I/O 压力，实际的并行性也没有那么高。

跑出来的 SimPoint 聚类可视化中效果比较好的，图中横轴是按执行顺序的 SimPoint slice，纵轴每一个 y 值对应一个 SimPoint phase，图中的点代表哪个 slice 被归到了哪个 phase 上：

500.perlbench_r diffmail:

520.omnetpp_r:

557.xz_r input:

以 1e8 条指令的粒度切分 SimPoint，把 241 GB 的 trace 缩减到 415 MB 的规模。

分支预测器模拟¶

使用 CBP 2016 的 Andre Seznec TAGE-SC-L 8KB/64KB 的分支预测器在 SimPoint 上模拟 SPEC INT 2017 Rate-1，只需要 9-10 分钟。

使用 CBP 2016 的 Andre Seznec TAGE-SC-L 8KB/64KB 的分支预测器在 SimPoint 上模拟的 CMPKI（只考虑了方向分支），和 Intel i9-14900K 的 MPKI（考虑了所有分支）在 SPEC INT 2017 Rate-1（AMD64，-O3）的比较：

不同编译器、编译选项和指令集下 SPEC INT 2017 的指令数和分支指令数规模¶

基于 Pin 开发 branch trace 工具¶

下面给出如何用 Pin 实现一个 branch trace 工具的过程：

1. 参考 Pin 的样例代码，Instrument 每一条指令，如果它是分支指令，就记录它的指令地址、目的地址、指令长度、分支类型以及是否跳转的信息：

   VOID Instruction(INS ins, VOID *v) { if (INS_IsControlFlow(ins)) { UINT32 size = INS_Size(ins); enum branch_type type = /* omitted */; INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)RecordBranch, IARG_INST_PTR, IARG_BRANCH_TARGET_ADDR, IARG_UINT32, size, IARG_UINT32, type, IARG_BRANCH_TAKEN, IARG_END); }}int main(int argc, char *argv[]) { if (PIN_Init(argc, argv)) return Usage(); INS_AddInstrumentFunction(Instruction, 0); PIN_StartProgram(); return 0;}

2. 记录分支的时候，分别维护分支的数组和分支执行事件的数组，然后对于每次执行的分支，记录分支的 id 以及是否跳转的信息，到分支执行事件的数组当中：

   VOID RecordBranch(VOID *inst_addr, VOID *targ_addr, UINT32 inst_length, UINT32 type, BOOL taken) { struct branch br; br.inst_addr = (uint64_t)inst_addr; br.targ_addr = (uint64_t)targ_addr; br.inst_length = inst_length; br.type = (branch_type)type; struct entry e; e.taken = taken; // insert branch if not exists auto it = br_map.find(br); if (it == br_map.end()) { assert(num_brs < MAX_BRS); br_map[br] = num_brs; e.br_index = num_brs; brs[num_brs++] = br; } else { e.br_index = it->second; } if (buffer_size == BUFFER_SIZE) { // omitted } write_buffer[buffer_size++] = e; num_entries++;}

3. 为了减少磁盘空间，当缓冲区满的时候，首先经过 zstd 的流压缩，再把压缩后的内容写入到文件中：

   // https://github.com/facebook/zstd/blob/dev/examples/streaming_compression.cZSTD_EndDirective mode = ZSTD_e_continue;ZSTD_inBuffer input = {write_buffer, sizeof(write_buffer), 0};int finished;do { ZSTD_outBuffer output = {zstd_output_buffer, zstd_output_buffer_size, 0}; size_t remaining = ZSTD_compressStream2(zstd_cctx, &output, &input, mode); assert(!ZSTD_isError(remaining)); assert(fwrite(zstd_output_buffer, 1, output.pos, trace) == output.pos); finished = input.pos == input.size;} while (!finished);

4. 最后在程序结束时，把分支数组写入到文件并记录元数据：

   VOID Fini(INT32 code, VOID *v) { // 1. compress the remaining data in write buffer and write to file // 2. save metadata, including: // 1. number of branch executions // 2. number of branches // 3. branches array}int main(int argc, char *argv[]) { // omitted PIN_AddFiniFunction(Fini, 0); PIN_StartProgram(); // omitted}

5. 针对动态链接，可以利用 Pin 已有的 API IMG_AddInstrumentFunction 来跟踪，方便后续找到 trace 中各个地址对应的指令

这样就完成了 Branch Trace 的抓取。

2025-04-07 08:00:00

Thread Local Storage (TLS) 实现探究¶

背景¶

TLS 是 thread local storage 的缩写，可以很方便地存储一些 per-thread 的数据，但它内部是怎么实现的呢？本文对 glibc 2.31 版本的 TLS 实现进行探究。

__thread¶

首先来看 TLS 在 C 中是怎么使用的：用 __thread 标记一个全局变量（注：进入 C11/C++11 标准的用法是用 thread_local 来标记），那么它就会保存在 TLS 当中，每个线程都有一份：

__thread int data;

那么编译器在生成访问这个 TLS 全局变量时，生成的指令也不同。以下面的代码为例：

int global_data;__thread int tls_data;void global(int val) { global_data = val; }void tls(int val) { tls_data = val; }

生成的 amd64 汇编如下：

 .textglobal: movl %edi, global_data(%rip) rettls: movl %edi, %fs:tls_data@tpoff ret .section .tbss,"awT",@nobitstls_data: .zero 4 .bssglobal_data: .zero 4

访问全局变量的时候，采用的是典型的 PC-relative 方式来找到全局变量 global_data 的地址；访问 thread local 变量的时候，可以看到它采用了一个比较少见的写法：%fs:tls_data@tpoff，它的意思是由链接器计算出 tls_data 相对 %fs 段寄存器的偏移，然后直接写到指令的偏移里。链接以上程序，可以看到最终的二进制是：

0000000000001140 <global>: 1140: 89 3d ce 2e 00 00 mov %edi,0x2ece(%rip) # 4014 <global_data> 1146: c3 ret 1147: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1) 114e: 00 000000000000001150 <tls>: 1150: 64 89 3c 25 fc ff ff mov %edi,%fs:0xfffffffffffffffc 1157: ff 1158: c3 ret

可见最终 global_data 被放到了相对二进制开头 0x4014 的地方，而 tls_data 被放到了 %fs:-0x4 的位置。那么这个 %fs 是怎么得到的，-0x4 的偏移又是怎么计算的呢？下面来进一步研究背后的实现。

TLS 的组织方式¶

首先 TLS 是 per-thread 的存储，意味着每个新线程，都有一个 buffer 需要保存 TLS 的数据。那么这个数据所在的位置，也需要一些 per-thread 的高效方式来访问，在 amd64 上，它是通过 %fs 段寄存器来维护的。那么 TLS 可能有哪些来源呢？首先可执行程序自己可能会用一些，它通过 DT_NEEDED 由动态链接器在启动时加载的动态库也有一些（比如 glibc 的 tcache），此外运行时 dlopen 了一些动态库也会有 TLS 的需求。为了满足这些需求，需要设计一个 TLS 的结构，既能满足这些在启动时已知的可执行程序和动态库的需求，又能满足运行时动态加载的新动态库的需求。

这里面可执行程序和启动时加载的动态库的需求是明确的，不会变的，因此可以由动态链接器在加载的时候，直接给可执行程序和动态库分配 TLS 空间：

1. 比如可执行程序本身需要 0x10 字节的 TLS 空间，它启动时加载两个动态库 libc.so.6 和 libstdc++.so.6，期中 libc.so.6 需要 0x20 字节的 TLS 空间，libstdc++.so.6 需要 0x30 字节的 TLS 空间
2. 加起来一共需要 0x60 字节的 TLS 空间，那么在创建线程的时候，创建好 0x60 字节的 TLS 空间，按照顺序进行分配：
   1. 0x00-0x10: 属于可执行程序
   2. 0x10-0x30: 属于 libc.so.6
   3. 0x30-0x60: 属于 libstdc++.so.6
3. 分配好这个空间以后，因为 libc.so.6 无法提前预知它会被分配到哪个位置，所以需要一次重定位，把 libc.so.6 里的 TLS 空间的使用重定位到分配后的位置，例如 libc.so.6 的 0x20 的 TLS 空间内的开头 8 字节，现在在整个 TLS 空间内的偏移就是 0x20 + 8 = 0x28

但是 dlopen 动态加载进来的动态库怎么办呢？这些动态库的数量可以动态变化，可以加载也可以卸载，再这么线性分配就不合适了，这时候就需要给每个 dlopen 得到的动态库分配独立的 TLS 空间。既然是动态分配的空间，那么这些独立的 TLS 空间的地址，不同线程不同，不能通过一个基地址加固定偏移的方式来计算，就需要提供一个机制来找到各个动态库的 TLS 空间的地址。

glibc 的实现中，它把各个动态库的 TLS 空间的起始地址记录在一个 dtv 数组中，并且提供一个 __tls_get_addr 函数来查询动态库的 TLS 空间内指定 offset 的实际地址：

typedef struct dl_tls_index{ uint64_t ti_module; uint64_t ti_offset;} tls_index;void *__tls_get_addr (tls_index *ti){ dtv_t *dtv = THREAD_DTV (); /* omitted */ void *p = dtv[ti->ti_module].pointer.val; /* omitted */ return (char *) p + ti->ti_offset;}

其中 dtv 数组的指针保存在 struct pthread（即 Thread Control Block (TCB)）中，而这个 struct pthread 就保存在 %fs 段寄存器指向的地址上：

struct pthread{ tcbhead_t header; /* omitted */};typedef struct{ /* omitted */ dtv_t *dtv; /* omitted */ uintptr_t stack_guard; /* omitted */} tcbhead_t;# define THREAD_DTV() \ ({ struct pthread *__pd; \ THREAD_GETMEM (__pd, header.dtv); })

P.S. stack protector 所使用的 canary 的值就保存在 pthread.header.stack_guard 字段中，也就是在 %fs:40 位置。

而之前提到的可执行程序本身的 TLS 空间以及程序启动时加载的动态库的 TLS 空间，实际上是保存在 struct thread 也就是 TCB 前面的部分，从高地址往低地址分配（图片来源：ELF Handling For Thread-Local Storage）：

图中 \(tp_t\) 在 amd64 下就是 %fs 段寄存器，它直接指向的就是 struct thread 也就是 TCB；从 %fs 开始往低地址，先分配可执行程序本身的 TLS 空间（图中 \(tlsoffset_1\) 到 \(tp_t\) 的范围），后分配程序启动时加载的动态库的 TLS 空间（图中 \(tlsoffset_1\) 到 \(tlsoffset_2\) 以及 \(tlsoffset_3\) 到 \(tlsoffset_2\) 的范围）。注意这些偏移对于每个线程都是相同的，只是不同线程的 %fs 寄存器不同。

而对于 dlopen 动态加载的动态库，则 TLS 空间需要动态分配，然后通过 dtv 数组来索引（图中 \(dtv_{t,4}\) 和 \(dtv_{t,5}\)），因此无法通过重定位修正，而是要在运行时通过 __tls_get_addr 函数获取地址。为了让 __tls_get_addr 更具有通用性，dtv 数组也记录了分配在 %fs 指向的 TCB 更低地址的可执行程序和程序启动时加载的动态库的 TLS 空间，此时 __tls_get_addr 可以查到所有 TLS 变量的地址。每个动态库在 dtv 数组中都记录了信息，那么这个动态库在 dtv 数组中的下标，记为这个动态库的编号（module id），后面会多次出现这个概念。

知道了 TLS 的组织方式后，接下来观察编译器、链接器和动态链接器是如何配合着让代码可以找到正确的 TLS 变量的地址。

可执行程序¶

首先来看一个简单的场景：可执行程序直接访问自己定义的 TLS 变量。前面提到，可执行程序的 TLS 空间直接保存到 %fs 往下的地址，因此可执行程序的 TLS 变量相对 %fs 的偏移，是可以提前计算得到的。下面看一个例子：

__thread int tls_data1;__thread int tls_data2;int read_tls_data1() { return tls_data1; }int read_tls_data2() { return tls_data2; }int main() {}

编译得到的汇编：

read_tls_data1: movl %fs:tls_data1@tpoff, %eax retread_tls_data2: movl %fs:tls_data2@tpoff, %eax ret

这就是在本文一开头就看到的语法：%fs:symbol@tpoff，它会对应一个 R_X86_64_TPOFF32 类型的重定位，告诉链接器，这是一个 TLS 变量，并且它的偏移在静态链接的时候就可以计算出来，并且这个偏移会直接写到 mov 指令的立即数内：

$ gcc -O2 -c tls.c -o tls.o$ objdump -S -r tls.o# omitted0000000000000000 <read_tls_data1>: 0: 64 8b 04 25 00 00 00 mov %fs:0x0,%eax 7: 00 4: R_X86_64_TPOFF32 tls_data1 8: c3 ret 9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)0000000000000010 <read_tls_data2>: 10: 64 8b 04 25 00 00 00 mov %fs:0x0,%eax 17: 00 14: R_X86_64_TPOFF32 tls_data2 18: c3 ret$ gcc tls.o -o tls$ objdump -S tls# omitted0000000000001140 <read_tls_data1>: 1140: 64 8b 04 25 fc ff ff mov %fs:0xfffffffffffffffc,%eax 1147: ff 1148: c3 ret 1149: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)0000000000001150 <read_tls_data2>: 1150: 64 8b 04 25 f8 ff ff mov %fs:0xfffffffffffffff8,%eax 1157: ff 1158: c3 ret$ objdump -t tls# omitted0000000000000000 g .tbss 0000000000000004 tls_data20000000000000004 g .tbss 0000000000000004 tls_data1

根据以上输出可以看到，可执行程序自己使用了 8 字节的 TLS 空间，其中低 4 字节对应 tls_data2，高 4 字节对应 tls_data1；根据这个信息，链接器就可以推断出 tls_data2 保存在 %fs-0x8 的位置，tls_data1 保存在 %fs-0x4 的位置，直接把这个偏移编码到 mov 指令内。这样，运行时开销是最小的。

这一种访问 TLS 的情况，也叫做 local exec TLS model：它只用于可执行程序访问可执行程序自己的 TLS 变量的场景。可执行程序的 TLS 空间总是紧贴着 %fs 分配，不会受到动态库的影响，因此可以提前计算出它自己的 TLS 变量的偏移。

动态库¶

接下来观察另一种情况：动态库使用动态库自己的 TLS 变量。按照前面的分析，有两种情况：

1. 第一种情况是，动态库是在程序启动时被动态链接器加载，那么它会被分配在 %fs 往低地址的空间。虽然相对 %fs 的偏移无法在链接阶段就提前得知，但是动态链接器会给它分配连续的 TLS 空间，从而可以计算出它的 TLS 空间相对 %fs 的偏移，于是动态链接器可以帮助完成剩下的重定位。
2. 第二种情况是，动态库是由 dlopen 被加载，那么它被分配的 TLS 空间的地址就无法从 %fs 直接计算得出，此时就需要借助 __tls_get_addr 函数的帮助。

initial exec TLS model¶

首先来看第一种情况，它也被叫做 initial exec TLS model。还是从例子开始看起：

__thread int tls_data1;__thread int tls_data2;int read_tls_data1() { return tls_data1; }int read_tls_data2() { return tls_data2; }

首先观察编译出来的汇编：

$ gcc -ftls-model=initial-exec -fPIC -O2 -S tls.c$ cat tls.sread_tls_data1: movq tls_data1@gottpoff(%rip), %rax movl %fs:(%rax), %eax retread_tls_data2: movq tls_data2@gottpoff(%rip), %rax movl %fs:(%rax), %eax ret

可以看到，这次生成的汇编不同了：它首先从 symbol@gottpoff(%rip) 读取一个 offset 到 %rax 寄存器，再从 %fs:(%rax) 地址读取 TLS 变量的值。上面提到，在 initial exec TLS model 下，TLS 空间是可以相对 %fs 寻址的，但是 offset 无法提前得知，需要由动态链接器完成重定位。

回忆之前在《开发一个链接器（4）》一文中，当动态库想要获得某个只有动态链接器才知道的地址，就会把它预留好位置放到 .got 表当中，并且输出一个 dynamic relocation，告诉动态链接器如何把地址计算出来并填进去。在这里，原理也是类似的，只不过是在 .got 表中预留了一个空间来保存 TLS 变量相对 %fs 的偏移。下面观察对象文件内是怎么记录这个信息的：

$ as tls.s -o tls.o$ objdump -S -r tls.o# omitted0000000000000000 <read_tls_data1>: 0: 48 8b 05 00 00 00 00 mov 0x0(%rip),%rax # 7 <read_tls_data1+0x7> 3: R_X86_64_GOTTPOFF tls_data1-0x4 7: 64 8b 00 mov %fs:(%rax),%eax a: c3 ret b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000000010 <read_tls_data2>: 10: 48 8b 05 00 00 00 00 mov 0x0(%rip),%rax # 17 <read_tls_data2+0x7> 13: R_X86_64_GOTTPOFF tls_data2-0x4 17: 64 8b 00 mov %fs:(%rax),%eax 1a: c3 ret

可以看到，这时候它在 mov 指令的立即数位置创建了一个 R_X86_64_GOTTPOFF 类型的重定位，这是告诉链接器：创建一个 .got entry，里面由动态链接器填写对应 symbol 在运行时相对 %fs 的偏移，然后链接器把 .got entry 相对 mov 指令的偏移写到 mov 指令的立即数内。

至于为啥是 symbol-0x4 而不是 symbol，原因在之前《开发一个链接器（2）》 已经出现过：x86 指令的立即数偏移是基于指令结尾的，而 relocation 指向的是立即数的起始地址，也就是指令结尾地址减去 4，那么立即数也要做相应的修正。

最后，观察链接器做的事情：

$ gcc -shared tls.o -o libtls.so$ objdump -D -S -R libtls.so# omittedDisassembly of section .text:0000000000001100 <read_tls_data1>: 1100: 48 8b 05 d1 2e 00 00 mov 0x2ed1(%rip),%rax # 3fd8 <tls_data1+0x3fd4> 1107: 64 8b 00 mov %fs:(%rax),%eax 110a: c3 ret 110b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000001110 <read_tls_data2>: 1110: 48 8b 05 a9 2e 00 00 mov 0x2ea9(%rip),%rax # 3fc0 <tls_data2+0x3fc0> 1117: 64 8b 00 mov %fs:(%rax),%eax 111a: c3 retDisassembly of section .got:0000000000003fb8 <.got>: ... 3fc0: R_X86_64_TPOFF64 tls_data2 3fd8: R_X86_64_TPOFF64 tls_data1

可以看到：

1. 链接器为两个 TLS 变量分别创建了一个 .got entry，tls_data1 对应 0x3fd8，tls_data2 对应 0x3fc0
2. 链接器在这两个 .got entry 处创建了 dynamic relocation R_X86_64_TPOFF64，告诉动态链接器：给动态库分配空间后，把 tls_data1 和 tls_data2 相对 %fs 的偏移写入到这两个 .got entry 内

3. 链接器计算出了 mov 指令和 .got entry 的相对偏移，直接写到了 mov 指令的立即数当中：

   0000000000001100 <read_tls_data1>: 1100: 48 8b 05 d1 2e 00 00 mov 0x2ed1(%rip),%rax # 3fd8 <tls_data1+0x3fd4> 1107: 64 8b 00 mov %fs:(%rax),%eax 110a: c3 ret 110b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000001110 <read_tls_data2>: 1110: 48 8b 05 a9 2e 00 00 mov 0x2ea9(%rip),%rax # 3fc0 <tls_data2+0x3fc0> 1117: 64 8b 00 mov %fs:(%rax),%eax 111a: c3 ret

   4. 那么在运行时，为了读取 TLS 变量，首先从 .got 表读取 TLS 变量相对 %fs 的偏移写到 %rax 寄存器，再通过 %fs:(%rax) 访问 TLS 变量即可

那么这就是 initial exec TLS model 的实现方法了：它利用了动态库会在程序启动时加载的性质，保证 TLS 变量都保存在相对 %fs 的运行时可知且不变的偏移上，把偏移记录在 .got 表中，由动态链接器去计算，那么访问的时候就很简单了，直接读取 offset 从 %fs 访问即可。

local/global dynamic TLS model¶

接下来看动态库的第二种情况：它可能由 dlopen 加载，因此 TLS 变量相对 %fs 的位置可能会变化，此时需要通过 __tls_get_addr 函数来得到 TLS 变量的地址。回顾前面提到的 __tls_get_addr 的声明：

typedef struct dl_tls_index{ uint64_t ti_module; uint64_t ti_offset;} tls_index;void *__tls_get_addr (tls_index *ti);

即它需要两个信息，一个是 TLS 变量所在的动态库的编号（这个编号是动态生成的一个 id，实际上是这个动态库在 dtv 数组中的下标），另外是这个 TLS 变量在动态库内的偏移。这时候，又分为两种情况：

1. 第一种情况是，这个 TLS 变量就在这个动态库本身内部定义，此时 TLS 变量在动态库内的偏移在链接期间已知，只是不知道 TLS 空间的起始地址，需要通过 __tls_get_addr 函数获取，这种情景叫做 local dynamic TLS model
2. 第二种情况是，这个 TLS 变量不知道在哪个动态库定义，此时只知道这个 TLS 变量的名字，不知道它属于哪个动态库，也不知道它在动态库内的偏移，这种情况叫做 global dynamic TLS model，是最通用的情况，对 TLS 变量所在的位置没有任何假设

local dynamic TLS model¶

接下来分析 local dynamic TLS model，它面向的场景是一个可能被 dlopen 加载的动态库，需要访问自己的 TLS 变量，此时需要用 __tls_get_addr 读取自己的 TLS 空间的起始地址，根据链接时已知的偏移，计算出 TLS 变量在运行时的地址。由于 __tls_get_addr 需要知道动态库的编号，而这个编号只有动态链接器才知道，因此需要生成一个 dynamic relocation，让动态链接器把这个动态库自己的编号写入到 .got entry 中，之后才能拿这个 .got entry 的值调用 __tls_get_addr，进而得到 TLS 变量的地址。下面来观察这个过程，源码和之前一样：

__thread int tls_data1;__thread int tls_data2;int read_tls_data1() { return tls_data1; }int read_tls_data2() { return tls_data2; }

首先查看生成的汇编：

$ gcc -ftls-model=local-dynamic -fPIC -O2 -S tls.c$ cat tls.sread_tls_data1:.LFB0: subq $8, %rsp leaq tls_data1@tlsld(%rip), %rdi call __tls_get_addr@PLT movl tls_data1@dtpoff(%rax), %eax addq $8, %rsp retread_tls_data2: subq $8, %rsp leaq tls_data2@tlsld(%rip), %rdi call __tls_get_addr@PLT movl tls_data2@dtpoff(%rax), %eax addq $8, %rsp ret

首先可以看到的是一个新的语法：symbol@tlsld(%rip)，生成一个 R_X86_64_TLSLD 类型的 relocation，它的意思是在 .got 表中生成一个 entry，这个 entry 会保存当前动态库对应的编号，然后在这里通过 lea 指令把这个 .got entry 的地址作为 tls_index * 类型的参数传给 __tls_get_addr，那么它就会去寻找这个动态库的 TLS 空间的起始地址，把结果写入到 %rax 寄存器内。

得到 TLS 空间的起始地址后，再利用 symbol@dtpoff(%rax) 的语法，生成 R_X86_64_DTPOFF32 类型的 relocation，在链接的时候直接把 symbol 相对自己的 TLS 空间的起始地址的偏移写到 movl 指令内，从而实现了 TLS 变量的访问。

下面观察生成的对象文件：

$ as tls.s -o tls.o$ objdump -D -r tls.oDisassembly of section .text:0000000000000000 <read_tls_data1>: 0: 48 83 ec 08 sub $0x8,%rsp 4: 48 8d 3d 00 00 00 00 lea 0x0(%rip),%rdi # b <read_tls_data1+0xb> 7: R_X86_64_TLSLD tls_data1-0x4 b: e8 00 00 00 00 call 10 <read_tls_data1+0x10> c: R_X86_64_PLT32 __tls_get_addr-0x4 10: 8b 80 00 00 00 00 mov 0x0(%rax),%eax 12: R_X86_64_DTPOFF32 tls_data1 16: 48 83 c4 08 add $0x8,%rsp 1a: c3 ret 1b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000000020 <read_tls_data2>: 20: 48 83 ec 08 sub $0x8,%rsp 24: 48 8d 3d 00 00 00 00 lea 0x0(%rip),%rdi # 2b <read_tls_data2+0xb> 27: R_X86_64_TLSLD tls_data2-0x4 2b: e8 00 00 00 00 call 30 <read_tls_data2+0x10> 2c: R_X86_64_PLT32 __tls_get_addr-0x4 30: 8b 80 00 00 00 00 mov 0x0(%rax),%eax 32: R_X86_64_DTPOFF32 tls_data2 36: 48 83 c4 08 add $0x8,%rsp 3a: c3 ret

可以看到，由于 __tls_get_addr 的运行时地址也是不知道的，所以就和调用其他动态库的函数一样，用已有的 PLT 机制去重定位。

接下来看最后的动态库：

$ gcc -shared tls.o -o libtls.so$ objdump -D -R libtls.so# omittedDisassembly of section .text:0000000000001110 <read_tls_data1>: 1110: 48 83 ec 08 sub $0x8,%rsp 1114: 48 8d 3d 9d 2e 00 00 lea 0x2e9d(%rip),%rdi # 3fb8 <_DYNAMIC+0x1c0> 111b: e8 10 ff ff ff call 1030 <__tls_get_addr@plt> 1120: 8b 80 04 00 00 00 mov 0x4(%rax),%eax 1126: 48 83 c4 08 add $0x8,%rsp 112a: c3 ret 112b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000001130 <read_tls_data2>: 1130: 48 83 ec 08 sub $0x8,%rsp 1134: 48 8d 3d 7d 2e 00 00 lea 0x2e7d(%rip),%rdi # 3fb8 <_DYNAMIC+0x1c0> 113b: e8 f0 fe ff ff call 1030 <__tls_get_addr@plt> 1140: 8b 80 00 00 00 00 mov 0x0(%rax),%eax 1146: 48 83 c4 08 add $0x8,%rsp 114a: c3 retDisassembly of section .got:0000000000003fb8 <.got>: ... 3fb8: R_X86_64_DTPMOD64 *ABS*

可以看到，无论是访问 tls_data1 还是 tls_data2，在调用 __tls_get_addr 时，使用的参数都是一样的 0x3fb8，也就是动态链接器把当前动态库的编号写进去的 .got entry。返回值就是当前动态库的 TLS 空间的基地址，把返回值加上对应的 offset（tls_data1 的偏移是 4，tls_data2 的偏移是 0，这个 offset 直接写到了 movl 指令的立即数里），就得到了 TLS 变量的地址。

特别地，如果在一个函数里访问多个当前动态库的 TLS 变量，那么 __tls_get_addr 调用是可以合并的：

__thread int tls_data1;__thread int tls_data2;int read_tls_data() { return tls_data1 + tls_data2; }

会生成如下的汇编：

$ gcc -ftls-model=local-dynamic -fPIC -O2 -S tls.c$ cat tls.sread_tls_data:.LFB0: subq $8, %rsp leaq tls_data1@tlsld(%rip), %rdi call __tls_get_addr@PLT movl tls_data1@dtpoff(%rax), %edx addl tls_data2@dtpoff(%rax), %edx addq $8, %rsp movl %edx, %eax ret

这样就减少了一次 __tls_get_addr 的调用。

global dynamic TLS model¶

再来介绍最后一种情况：对于一个 dlopen 的动态库，如果它要访问的 TLS 变量，只知道名字，不知道来自哪一个动态库，不知道偏移是多少。这时候，只能把全部工作交给动态链接器去做：让动态链接器根据符号，去查找符号表，找到对应的动态库和偏移，记录下来；由于涉及到动态库的编号和偏移，所以需要两个连续的 .got entry，正好对应 tls_index 结构体的两项成员：

typedef struct dl_tls_index{ uint64_t ti_module; uint64_t ti_offset;} tls_index;

继续上面的例子，这次采用 global dynamic TLS model 进行编译：

$ cat tls.c__thread int tls_data1;__thread int tls_data2;int read_tls_data1() { return tls_data1; }int read_tls_data2() { return tls_data2; }$ gcc -ftls-model=global-dynamic -fPIC -O2 -S tls.c$ cat tls.sread_tls_data1: subq $8, %rsp data16 leaq tls_data1@tlsgd(%rip), %rdi .value 0x6666 rex64 call __tls_get_addr@PLT movl (%rax), %eax addq $8, %rsp retread_tls_data2: subq $8, %rsp data16 leaq tls_data2@tlsgd(%rip), %rdi .value 0x6666 rex64 call __tls_get_addr@PLT movl (%rax), %eax addq $8, %rsp ret

这次出现了一些不一样的内容：data16、.value 0x6666 和 rex64；实际上，这些是无用的指令前缀，不影响指令的语义，但是保证了这段代码有足够的长度，方便后续链接器进行优化。除了这些奇怪的前缀，核心就是 symbol@tlsgd(%rip) 语法，它会创建 R_X86_64_TLSGD relocation，它的意思是：创建一对 .got entry，第一个 entry 对应 symbol 所在动态库的编号，第二个 entry 对应 symbol 在动态库的 TLS 空间内的偏移，这两个 entry 组成一个 tls_index 结构体；通过 leaq 指令得到这个结构体的指针，调用 __tls_get_addr，就得到了这个 TLS 变量的地址。

接下来看生成的对象文件：

$ as tls.s -o tls.o$ objdump -D -r tls.oDisassembly of section .text:0000000000000000 <read_tls_data1>: 0: 48 83 ec 08 sub $0x8,%rsp 4: 66 48 8d 3d 00 00 00 data16 lea 0x0(%rip),%rdi # c <read_tls_data1+0xc> b: 00 8: R_X86_64_TLSGD tls_data1-0x4 c: 66 66 48 e8 00 00 00 data16 data16 rex.W call 14 <read_tls_data1+0x14> 13: 00 10: R_X86_64_PLT32 __tls_get_addr-0x4 14: 8b 00 mov (%rax),%eax 16: 48 83 c4 08 add $0x8,%rsp 1a: c3 ret 1b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000000020 <read_tls_data2>: 20: 48 83 ec 08 sub $0x8,%rsp 24: 66 48 8d 3d 00 00 00 data16 lea 0x0(%rip),%rdi # 2c <read_tls_data2+0xc> 2b: 00 28: R_X86_64_TLSGD tls_data2-0x4 2c: 66 66 48 e8 00 00 00 data16 data16 rex.W call 34 <read_tls_data2+0x14> 33: 00 30: R_X86_64_PLT32 __tls_get_addr-0x4 34: 8b 00 mov (%rax),%eax 36: 48 83 c4 08 add $0x8,%rsp 3a: c3 ret

基本符合预期，通过 R_X86_64_TLSGD relocation 来表示意图，通过反汇编也可以看到，多余的那些修饰符是没有用的，语义上就是一条 leaq 加一条 call 指令。和之前 local dynamic TLS model 类似，__tls_get_addr 也是用已有的 PLT 机制来寻址。

最后来看生成的动态库：

$ gcc -shared tls.o -o libtls.so$ objdump -D -R libtls.so# omittedDisassembly of section .text:0000000000001110 <read_tls_data1>: 1110: 48 83 ec 08 sub $0x8,%rsp 1114: 66 48 8d 3d b4 2e 00 data16 lea 0x2eb4(%rip),%rdi # 3fd0 <tls_data1@@Base+0x3fcc> 111b: 00 111c: 66 66 48 e8 0c ff ff data16 data16 rex.W call 1030 <__tls_get_addr@plt> 1123: ff 1124: 8b 00 mov (%rax),%eax 1126: 48 83 c4 08 add $0x8,%rsp 112a: c3 ret 112b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)0000000000001130 <read_tls_data2>: 1130: 48 83 ec 08 sub $0x8,%rsp 1134: 66 48 8d 3d 74 2e 00 data16 lea 0x2e74(%rip),%rdi # 3fb0 <tls_data2@@Base+0x3fb0> 113b: 00 113c: 66 66 48 e8 ec fe ff data16 data16 rex.W call 1030 <__tls_get_addr@plt> 1143: ff 1144: 8b 00 mov (%rax),%eax 1146: 48 83 c4 08 add $0x8,%rsp 114a: c3 retDisassembly of section .got:0000000000003fa8 <.got>: ... 3fb0: R_X86_64_DTPMOD64 tls_data2@@Base 3fb8: R_X86_64_DTPOFF64 tls_data2@@Base 3fd0: R_X86_64_DTPMOD64 tls_data1@@Base 3fd8: R_X86_64_DTPOFF64 tls_data1@@Base

观察 .got，可以看到对于每个 TLS 变量，都生成了两个 entry：tls_data2 占用了 0x3fb0 和 0x3fb8 两个 entry，第一个对应动态库的下标（MOD 表示 Module），第二个对应偏移（OFF 表示 Offset）；tls_data1 也是类似的，占用了 0x3fd0 和 0x3fd8。当动态链接器在 .got 表中准备好 tls_index 结构体后，在访问 TLS 变量时，只需要 lea + call 就可以找到 TLS 变量的地址了。

四种 TLS model 的对比¶

接下来进行四种 TLS model 的对比：

1. local exec TLS model: 用于可执行程序访问自身的 TLS 变量，由于可执行程序的 TLS 空间总是紧挨着 %fs，所以自身的 TLS 变量相对 %fs 的偏移在链接时已知，可以直接计算出来，运行时开销最小
2. initial exec TLS model: 用于在程序启动时由动态链接器自动加载的动态库访问自身的 TLS 变量，由于它的 TLS 空间相对 %fs 的偏移在加载后就是固定的，所以由动态链接器计算出各个 TLS 变量相对 %fs 的偏移，写到 .got 表中，运行时只需要读取 .got 表中记录的 offset，和 %fs 做加法就得到了变量的地址
3. local dynamic TLS model: 用于可能被 dlopen 的动态库访问自身的 TLS 变量，由于它的 TLS 空间相对 %fs 的偏移是不确定的，所以需要用 __tls_get_addr 调用来获取自身的 TLS 空间的起始地址；为了给 __tls_get_addr 传递正确的参数，告诉这个函数自己的动态库编号是多少，在 .got 表中预留了一个 entry 让动态链接器把该动态库的编号写进去；那么运行时只需要读取 .got 表中记录的动态库编号，调用 __tls_get_addr，再和链接时已知的 offset 做加法就得到了变量的地址
4. global dynamic TLS model: 用于通用情况下，不知道 TLS 变量属于哪个动态库，也不知道 TLS 变量在 TLS 空间内的偏移是多少，所以需要动态链接器去查询 TLS 变量属于哪个动态库，放在哪个偏移上，并且动态链接器要把这两个信息写到 .got 表中；那么运行时就要用 __tls_get_addr 调用来根据 .got 表中记录的动态库编号以及偏移来找到变量的地址

下面是一个对比表格：

特别地，local dynamic TLS model 的 leaq + call 是可以复用的，所以整体来说，还是越通用的 TLS model，运行时的开销越大。

实际编程中的 TLS model¶

看到这里，你可能会疑惑：在编程的时候，大多数时候并没有去管 TLS model 的事情，也就是说在编译的时候并没有指定，那么这个时候会采用什么 TLS model 呢？

答案是取决于编译器和链接器会根据所能了解到的情况，选择一个最优的实现方法。在前面的例子中，都是直接定义了一个全局的 __thread 变量然后去访问它，但如果它是 static 的，会发生什么呢？如果编译的时候，没有开 -fPIC，也就是说生成的代码不会出现在动态库中，又会发生什么呢？

首先来看从编译器到汇编的这一个阶段，会采用什么样的 TLS model：

1. 如果在编译源码的时候，没有开 -fPIC，那么生成的代码只出现在可执行程序中，这个时候编译器会直接使用 local exec TLS model，即生成 movl %fs:symbol@tpoff, %rax 的指令
2. 如果在编译源码的时候，开了 -fPIC，那么生成的代码既可能出现在可执行程序中，也可能出现在动态库中，这时会首先默认为 global dynamic TLS model，即生成 data16 leaq symbol@tlsgd(%rip), %rdi; .value 0x6666; rex64; call __tls_get_addr@PLT; movl (%rax), %eax 指令
3. 但如果 __thread 变量设置了 static，即使打开了 -fPIC，也保证了这个 TLS 变量一定是访问自己 TLS 空间中的，不会访问别人的，那么编译器会自动选择 local dynamic TLS model，即生成 leaq symbol@tlsld(%rip), %rdi; call__tls_get_addr@PLT; movl %symbol@dtpoff(%rax), %eax 指令

接下来观察链接的时候，会发生什么事情：

1. 如果编译源码的时候，打开了 -fPIC 且没有用 static，如前所述，编译器会使用 global dynamic TLS model；但如果这个对象文件最后被链接到了可执行程序当中，那么链接器知道这个时候用 local exec TLS model 是性能更好的，那么它会对指令进行改写，此时之前预留的无用的指令前缀 data 16; .value 0x6666; rex64 起了作用，保证改写前后的指令序列的长度不变：

   # before linker optimizations: global dynamicdata16 leaq symbol@tlsgd(%rip), %rdi.value 0x6666rex64call __tls_get_addr@PLT# after linker optimizations: local exec# the symbol@tpoff(%rax) relocation is resolved by the linker immediatelymovq %fs:0, %raxleaq symbol@tpoff(%rax), %rax

2. 类似地，如果编译源码的时候，打开了 -fPIC 且用了 static，如前所述，编译器会使用 local dynamic TLS model；但如果这个对象文件最后被链接到了可执行程序当中，那么链接器知道这个时候用 local exec TLS model 是性能更好的，那么它会对指令进行改写，为了保证改写前后的指令序列的长度不变，这次是在生成的汇编里加入无用的指令前缀：

   # before linker optimizations: local dynamicleaq symbol@tlsld(%rip), %rdicall __tls_get_addr@PLTmovl symbol@dtpoff(%rax), %eax# after linker optimizations: local exec# the symbol@tpoff(%rax) relocation is resolved by the linker immediately.word 0x6666.byte 0x66movq %fs:0, %raxmovl symbol@tpoff(%rax), %eax

3. 如果编译源码的时候，打开了 -fPIC 且用了 extern 来标记 TLS 变量，由于编译器不知道这个 TLS 变量属于谁，所以编译器会使用 global dynamic TLS model；但如果这个对象文件最后被链接到了可执行程序当中，并且编译器发现这个 TLS 变量属于一个动态库，这意味着这个 TLS 变量在程序启动时会随着动态库加载而变得可用，适用 initial exec TLS model，于是链接器也会进行改写：

   # before linker optimizations: global dynamicdata16 leaq symbol@tlsgd(%rip), %rdi.value 0x6666rex64call __tls_get_addr@PLT# after linker optimizations: initial execmovq %fs:0, %raxaddq symbol@gottpoff(%rip), %rax

4. 如果编译源码的时候，没有打开 -fPIC 且用了 extern 来标记 TLS 变量，那么编译器知道，这个对象文件最后只能出现在可执行程序中，那么这个 TLS 变量要么来自于可执行程序自己，要么来自于程序启动时加载的动态库，所以编译器会使用 initial exec TLS model；但如果这个对象文件最后被链接到了可执行程序当中，并且编译器发现这个 TLS 变量属于可执行程序自己，适用 local exec TLS model，于是链接器也会进行改写：

   # before linker optimizations: initial execmovq %fs:0, %raxaddq symbol@gottpoff(%rip), %rax# after linker optimizations: local exec# the symbol@tpoff(%rax) relocation is resolved by the linker immediatelymovq %fs:0, %raxleaq symbol@tpoff(%rax), %rax

可见通过两阶段的处理，在编译器和链接器的协同下，尝试优化到一个开销更小的 TLS model，转化的几种情况如下：

1. global dynamic -> initial exec：编译的时候开了 -fPIC 和 extern，然后链接到可执行程序内，TLS 变量来自动态库
2. global dynamic -> local exec：编译的时候开了 -fPIC，然后链接到可执行程序内，TLS 变量来自程序自己
3. local dynamic -> local exec：编译的时候开了 -fPIC 和 -static，然后链接到可执行程序内，TLS 变量来自程序自己
4. initial exec -> local exec：编译的时候没开 -fPIC，然后链接到可执行程序内，TLS 变量来自程序自己

TLSDESC¶

前面提到，在 global dynamic 和 local dynamic 两种 TLS model 下，要访问 TLS 变量的时候，需要调用 __tls_get_addr 函数，这是比较慢的。为了优化它，让人想到了 PLT 机制：

1. 初始情况下，PLT 会生成一个 stub，从 .got 读取一个函数指针并跳转，这个函数指针初始情况下是执行了 stub 的下一条指令
2. 对于第一次执行这个 stub，它会把这个函数的编号 push 到栈上，然后调用动态链接器提供的 _dl_runtime_resolve 函数来寻找这个函数的实际地址；此时 _dl_runtime_resolve 会把找到的函数地址写回到 .got 的函数指针
3. 此后再次执行 stub 的时候，就会从 .got 读取计算好的的函数指针，直接跳转到实际的函数地址

由此可以类比得到一个针对 TLS 的类似机制，称为 TLSDESC：

1. TLSDESC 占用 16 字节空间，前面 8 字节是一个函数指针，后面 8 字节用来保存 offset，保存在 .got 表中
2. 把原来 local/global dynamic TLS model 对 __tls_get_addr 的调用，改成调用 TLSDESC 中的函数指针，调用时 %rax 寄存器指向了 TLSDESC 的地址，它的返回结果是 TLS 变量相对 %fs 的偏移，后续指令根据这个偏移计算出实际的地址
3. 动态链接器在加载的时候，它会去判断目标 TLS 变量相对 %fs 的偏移是否是常量：对于可执行程序以及随着程序启动而自动加载的动态库，它们的 TLS 变量相对 %fs 的偏移是常量

4. 如果目标 TLS 变量相对 %fs 的偏移是常量，则把这个常量写入到 .got 表中 TLSDESC 变量的 offset 的位置，然后把函数指针改写成 _dl_tlsdesc_return，它是一个很简单的实现，因为在调用这个函数时，%rax 寄存器指向了 TLSDESC 的地址，所以直接从 %rax+8 地址把 offset 读出来然后返回就可以：

   _dl_tlsdesc_return: movq 8(%rax), %rax ret

5. 如果目标 TLS 变量相对 %fs 的偏移不是常量，则把函数指针改写成 _dl_tlsdesc_dynamic 函数，再走和之前的 __tls_get_addr 类似的逻辑，完成剩下的查找；由于返回值是 TLS 变量相对 %fs 的偏移，所以返回之前还要减去 %fs 的地址：

   /* %rax points to the TLS descriptor, such that 0(%rax) points to _dl_tlsdesc_dynamic itself, and 8(%rax) points to a struct tlsdesc_dynamic_arg object. It must return in %rax the offset between the thread pointer and the object denoted by the argument, without clobbering any registers. The assembly code that follows is a rendition of the following C code, hand-optimized a little bit.ptrdiff_t_dl_tlsdesc_dynamic (register struct tlsdesc *tdp asm ("%rax")){struct tlsdesc_dynamic_arg *td = tdp->arg;dtv_t *dtv = *(dtv_t **)((char *)__thread_pointer + DTV_OFFSET);if (__builtin_expect (td->gen_count <= dtv[0].counter && (dtv[td->tlsinfo.ti_module].pointer.val != TLS_DTV_UNALLOCATED), 1)) return dtv[td->tlsinfo.ti_module].pointer.val + td->tlsinfo.ti_offset - __thread_pointer;return __tls_get_addr_internal (&td->tlsinfo) - __thread_pointer;}*/

它利用的也是在内存中保存函数指针，通过运行时替换函数指针的方式，实现 slow path 到 fast path 的动态替换。

dtv 维护¶

最后再来深入分析一下 dtv 的维护方式。前面提到，dtv 的指针是保存在 struct pthread 内的，而 struct pthread 又是保存在 %fs 寄存器指向的位置：

struct pthread{ tcbhead_t header; /* omitted */};typedef struct{ /* omitted */ dtv_t *dtv; /* omitted */} tcbhead_t;

所以要访问 dtv 也很简单，直接从 %fs 加它在 struct pthread 结构体内的偏移即可。

前面提到，在调用 __tls_get_addr 时，需要提供一个动态库的 ID 来查询得到这个动态库的 TLS 空间的起始地址，再加上在这个 TLS 空间内的偏移。而这个动态库的 ID，正好就是 dtv 数组的下标，所以 __tls_get_addr 做的事情大概是：

1. 找到 dtv 的地址：mov %fs:DTV_OFFSET, %RDX_LP
2. 从 __tls_get_addr 函数的参数里读取 ti_module 字段：mov TI_MODULE_OFFSET(%rdi), %RAX_LP

3. 读取 dtv[ti->ti_module].val，也就是这个模块的 TLS 空间的起始地址：salq $4, %rax; movq (%rdx, %rax), %rax，这里左移 4 位是因为 dtv 数组的每个元素的类型是 dtv_t，其定义如下：

   struct dtv_pointer{ void *val; /* Pointer to data, or TLS_DTV_UNALLOCATED. */ void *to_free; /* Unaligned pointer, for deallocation. */};/* Type for the dtv. */typedef union dtv{ size_t counter; struct dtv_pointer pointer;} dtv_t;

   4. 把起始地址加上偏移，然后返回：add TI_OFFSET_OFFSET(%rdi), %RAX_LP; ret

但实际情况会比这个更复杂：dlopen 可能会动态引入新的动态库，此时 dtv 数组可能需要扩张；此外，如果一个动态库有 TLS 变量但是从来不用，也可以 lazy 分配它的 TLS 空间，只有在第一次访问的时候，才去分配。

首先来考虑第一个需求，处理 dlopen 导致 dtv 元素个数变化，它的实现方法是这样的：

1. dtv[0] 不用来保存 TLS 空间的信息，而是记录一个 counter，这个 counter 记录的是当前 dtv 的版本号（generation），另外在全局变量 dl_tls_generation 中记录当前最新的版本号；当 dlopen 导致 dtv 结构发生变化时，更新 dl_tls_generation 版本，然后在 __tls_get_addr 里检查版本号，不一致则进入 slow path：

   ENTRY (__tls_get_addr) mov %fs:DTV_OFFSET, %RDX_LP mov GL_TLS_GENERATION_OFFSET+_rtld_local(%rip), %RAX_LP /* GL(dl_tls_generation) == dtv[0].counter */ cmp %RAX_LP, (%rdx) jne 1f mov TI_MODULE_OFFSET(%rdi), %RAX_LP /* dtv[ti->ti_module] */ salq $4, %rax movq (%rdx,%rax), %rax /* omitted */ add TI_OFFSET_OFFSET(%rdi), %RAX_LP ret1: /* slow path, stack alignment omitted */ call __tls_get_addr_slow ret

   2. 在 __tls_get_addr_slow 中，如果发现当前 dtv 的版本号和最新的版本号 dl_tls_generation 不一致，就调用 update_get_addr 来重新分配内存：

   void *__tls_get_addr_slow (tls_index *ti){ dtv_t *dtv = THREAD_DTV (); if (__glibc_unlikely (dtv[0].counter != GL(dl_tls_generation))) return update_get_addr (ti); return tls_get_addr_tail (ti, dtv, NULL);}

具体的 dtv 更新逻辑比较复杂，有兴趣的读者可以翻阅 glibc 的源码中 update_get_addr 函数的实现。

接下来考虑第二个需求，也就是 lazy 分配，只有在第一次访问 TLS 空间的时候，才给 dlopen 的动态库分配 TLS 空间。为了区分已分配和未分配的 TLS 空间，未分配的 TLS 空间的 val 字段的值是 TLS_DTV_UNALLOCATED，当 __tls_get_addr 检测到 TLS 空间尚未分配时，也会进入 slow path：

ENTRY (__tls_get_addr) mov %fs:DTV_OFFSET, %RDX_LP mov GL_TLS_GENERATION_OFFSET+_rtld_local(%rip), %RAX_LP /* GL(dl_tls_generation) == dtv[0].counter */ cmp %RAX_LP, (%rdx) jne 1f mov TI_MODULE_OFFSET(%rdi), %RAX_LP /* dtv[ti->ti_module] */ salq $4, %rax movq (%rdx,%rax), %rax /* branch if val == TLS_DTV_UNALLOCATED */ cmp $-1, %RAX_LP je 1f add TI_OFFSET_OFFSET(%rdi), %RAX_LP ret1: /* slow path, stack alignment omitted */ call __tls_get_addr_slow ret

在 slow path 中，最终由 allocate_dtv_entry 函数来分配这片空间，注意到 TLS 空间可能有对齐的要求，所以它实际上记录了两个地址，一个是 malloc 得到的地址（用于后续的 free 调用），一个是经过对齐后的地址：

/* Allocate one DTV entry. */static struct dtv_pointerallocate_dtv_entry (size_t alignment, size_t size){ if (powerof2 (alignment) && alignment <= _Alignof (max_align_t)) { /* The alignment is supported by malloc. */ void *ptr = malloc (size); return (struct dtv_pointer) { ptr, ptr }; } /* Emulate memalign to by manually aligning a pointer returned by malloc. First compute the size with an overflow check. */ size_t alloc_size = size + alignment; if (alloc_size < size) return (struct dtv_pointer) {}; /* Perform the allocation. This is the pointer we need to free later. */ void *start = malloc (alloc_size); if (start == NULL) return (struct dtv_pointer) {}; /* Find the aligned position within the larger allocation. */ void *aligned = (void *) roundup ((uintptr_t) start, alignment); return (struct dtv_pointer) { .val = aligned, .to_free = start };}

可见这些 lazy 分配的 TLS 空间都是放在堆上的，由 malloc 进行动态分配。而可执行程序和随着程序启动而自动加载的动态库的 TLS 空间，是随着 TCB 也就是 struct pthread 一起分配的。对于新创建的线程来说，TCB 放置在栈的顶部，而不是在堆上，所以要求大小不能动态变化，只有 dtv 数组的指针保存在 struct pthread 中，dtv 数组本身是放在堆上的，根据需要进行 malloc/realloc（见 _dl_resize_dtv 函数）。对于初始线程来说，TCB 是通过 malloc 或者 sbrk 动态分配的。

参考¶

• ELF Handling For Thread-Local Storage
• All about thread-local storage
• What system data is stored on the stack

2025-03-30 08:00:00

glibc 内存分配器实现探究¶

背景¶

malloc 和 free 日常用的很多，但它内部是怎么实现的呢？本文对 glibc 2.31 版本的内存分配器的实现进行探究。

本文的完整版内容已经整合到知识库中。

malloc¶

glibc 2.31 是 ubuntu 20.04 所使用的 libc 版本，首先来分析它的实现，源码可以从 glibc-2.31 tag 中找到。

首先来看 malloc 函数，它实现在 malloc/malloc.c 的 __libc_malloc 函数当中，忽略 __malloc_hook 和一些检查，首先可以看到它有一段代码，使用了一个叫做 tcache 的数据结构：

/* int_free also calls request2size, be careful to not pad twice. */size_t tbytes;if (!checked_request2size (bytes, &tbytes)) { __set_errno (ENOMEM); return NULL; }size_t tc_idx = csize2tidx (tbytes);MAYBE_INIT_TCACHE ();DIAG_PUSH_NEEDS_COMMENT;if (tc_idx < mp_.tcache_bins && tcache && tcache->counts[tc_idx] > 0) { return tcache_get (tc_idx); }DIAG_POP_NEEDS_COMMENT;

tcache (Thread Local Cache)¶

接下来仔细地研究 tcache 的结构。首先，它是一个 per-thread 的数据结构，意味着每个线程都有自己的一份 tcache，不需要上锁就可以访问：

static __thread tcache_perthread_struct *tcache = NULL;

接下来看它具体保存了什么：

/* We overlay this structure on the user-data portion of a chunk when the chunk is stored in the per-thread cache. */typedef struct tcache_entry{ struct tcache_entry *next; /* This field exists to detect double frees. */ struct tcache_perthread_struct *key;} tcache_entry;/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct"). Keeping overall size low is mildly important. Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons. */typedef struct tcache_perthread_struct{ uint16_t counts[TCACHE_MAX_BINS]; tcache_entry *entries[TCACHE_MAX_BINS];} tcache_perthread_struct;/* Caller must ensure that we know tc_idx is valid and there's room for more chunks. */static __always_inline voidtcache_put (mchunkptr chunk, size_t tc_idx){ tcache_entry *e = (tcache_entry *) chunk2mem (chunk); /* Mark this chunk as "in the tcache" so the test in _int_free will detect a double free. */ e->key = tcache; e->next = tcache->entries[tc_idx]; tcache->entries[tc_idx] = e; ++(tcache->counts[tc_idx]);}/* Caller must ensure that we know tc_idx is valid and there's available chunks to remove. */static __always_inline void *tcache_get (size_t tc_idx){ tcache_entry *e = tcache->entries[tc_idx]; tcache->entries[tc_idx] = e->next; --(tcache->counts[tc_idx]); e->key = NULL; return (void *) e;}

可以看到它有两个成员，把 tcache 分为 TCACHE_MAX_BINS 这么多个 bin，每个 bin 分别有一个：

1. counts[bin]：记录了这个 bin 中空闲块的数量，tcache_put 的时候加一，tcache_get 的时候减一
2. entries[bin]: 每个 bin 用一个链表保存了空闲块，链表的节点类型是 tcache_entry，那么 entries[bin] 保存了链表头的指针

bin 是内存分配器的一个常见做法，把要分配的块的大小分 bin，从而保证拿到的空闲块足够大。接下来看 tcache_put 是如何把空闲块放到 tcache 中的：

1. 把空闲块强制转换为 tcache_entry 结构体类型
2. 把它的 key 字段指向 tcache，用来表示这个空闲块当前在 tcache 当中，后续用它来检测 double free
3. 以新的 tcache_entry 作为链表头，插入到 tcache 的对应的 bin 当中：entries[tc_idx]
4. 更新这个 bin 的空闲块个数到 count[tc_idx] 当中

反过来，tcache_get 则是从 tcache 中拿出一个空闲块：

1. 从链表头 entries[tc_idx] 取出一个空闲块，把它从链表中删除：entries[tc_idx] = e->next
2. 更新这个 bin 的空闲块个数到 count[tc_idx] 当中
3. 把它的 key 字段指向 NULL，用来表示这个空闲块当前不在 tcache 当中
4. 返回这个空闲块的地址

malloc¶

接下来回到 malloc 的实现，它首先根据用户要分配的空间大小（bytes），计算出实际需要分配的大小（tbytes），和对应的 bin（tc_idx）：

/* int_free also calls request2size, be careful to not pad twice. */size_t tbytes;if (!checked_request2size (bytes, &tbytes)) { __set_errno (ENOMEM); return NULL; }size_t tc_idx = csize2tidx (tbytes);

其中 checked_request2size 实现如下：

#define request2size(req) \ (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \ MINSIZE : \ ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)/* Check if REQ overflows when padded and aligned and if the resulting value is less than PTRDIFF_T. Returns TRUE and the requested size or MINSIZE in case the value is less than MINSIZE on SZ or false if any of the previous check fail. */static inline boolchecked_request2size (size_t req, size_t *sz) __nonnull (1){ if (__glibc_unlikely (req > PTRDIFF_MAX)) return false; *sz = request2size (req); return true;}

它实现的实际上是把用户请求的内存大小，加上 SIZE_SZ（即 sizeof(size_t)），向上取整到 MALLOC_ALIGN_MASK 对应的 alignment（MALLOC_ALIGNMENT，通常是 2 * SIZE_SZ）的整数倍数，再和 MINSIZE 取 max。这里要加 SIZE_SZ，是因为 malloc 会维护被分配的块的一些信息，包括块的大小和一些 flag，后续会详细讨论，简单来说就是分配的实际空间会比用户请求的空间要更大。

接着，看它是如何计算出 tcache index 的：

/* When "x" is from chunksize(). */# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)

可以看到，从 MINSIZE 开始，以 MALLOC_ALIGNMENT 为单位，每个 bin 对应一个经过 align 以后的可能的内存块大小。得到 tcache index 后，检查对应的 bin 是否有空闲块，如果有，则直接分配：

if (tc_idx < mp_.tcache_bins && tcache && tcache->counts[tc_idx] > 0) { return tcache_get (tc_idx); }

可以看到，tcache 相当于是一个 per thread 的小缓存，记录了最近释放的内存块，可供 malloc 使用。由于 bin 的数量有限，所以比较大的内存分配不会经过 tcache。

P.S. calloc 不会使用 tcache，而是用后面提到的 _int_malloc 进行各种分配。

free¶

既然 malloc 用到了 tcache，自然 free 就要往里面放空闲块了，相关的代码在 _int_free 函数当中：

size_t tc_idx = csize2tidx (size);if (tcache != NULL && tc_idx < mp_.tcache_bins) { /* Check to see if it's already in the tcache. */ tcache_entry *e = (tcache_entry *) chunk2mem (p); /* This test succeeds on double free. However, we don't 100% trust it (it also matches random payload data at a 1 in 2^<size_t> chance), so verify it's not an unlikely coincidence before aborting. */ if (__glibc_unlikely (e->key == tcache)) { tcache_entry *tmp; LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx); for (tmp = tcache->entries[tc_idx]; tmp; tmp = tmp->next) if (tmp == e) malloc_printerr ("free(): double free detected in tcache 2"); /* If we get here, it was a coincidence. We've wasted a few cycles, but don't abort. */ } if (tcache->counts[tc_idx] < mp_.tcache_count) { tcache_put (p, tc_idx); return; } }

它的逻辑也不复杂：

1. 计算 tcache index，找到对应的 bin
2. 检查它是不是已经被 free 过了，即 double free：free 过的指针，它的 key 字段应当指向 tcache，如果实际检测到是这样，那就去 tcache 里遍历链表，检查是不是真的在里面，如果是，说明 double free 了，报错
3. 如果对应的 bin 的链表长度不是很长（阈值是 mp_.tcache_count，取值见后），则添加到链表头部，完成 free 的过程

那么 tcache 默认情况下有多大呢：

/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */# define TCACHE_MAX_BINS 64/* This is another arbitrary limit, which tunables can change. Each tcache bin will hold at most this number of chunks. */# define TCACHE_FILL_COUNT 7

也就是说，它有 64 个 bin，每个 bin 的链表最多 7 个空闲块。

在 64 位下，这 64 个 bin 对应的块大小是从 32 字节到 1040 字节，每 16 字节一个 bin（(1040 - 32) / 16 + 1 = 64）。那么，malloc(1032) 或更小的分配会经过 tcache，而 malloc(1033) 或更大的分配则不会。

实验¶

下面来写一段程序来观察 tcache 的行为，考虑到从链表头部插入和删除是后进先出（LIFO），相当于是一个栈，所以分配两个大小相同的块，释放后再分配相同大小的块，得到的指针的顺序应该是反过来的：

#include <stdio.h>#include <stdlib.h>int main() { void *p1 = malloc(32); void *p2 = malloc(32); free(p1); free(p2); void *p3 = malloc(32); void *p4 = malloc(32); printf("p1=%p p2=%p p3=%p p4=%p\n", p1, p2, p3, p4);}

输出如下：

p1=0x55fb2f9732a0 p2=0x55fb2f9732d0 p3=0x55fb2f9732d0 p4=0x55fb2f9732a0

结果符合预期，tcache 的内部状态变化过程如下：

1. free(p1)：p1 变成链表的头部
2. free(p2)：p2 变成链表的头部，next 指针指向 p1
3. p3 = malloc(32): p2 是链表的头部，所以被分配给 p3，之后 p1 成为链表的头部
4. p4 = malloc(32): p1 是链表的头部，所以被分配给 p4

如果修改分配的大小，让它们被放到不同的 bin，就不会出现顺序颠倒的情况：

#include <stdio.h>#include <stdlib.h>int main() { void *p1 = malloc(32); void *p2 = malloc(48); free(p1); free(p2); void *p3 = malloc(32); void *p4 = malloc(48); printf("p1=%p p2=%p p3=%p p4=%p\n", p1, p2, p3, p4);}

输出如下：

p1=0x5638e68db2a0 p2=0x5638e68db2d0 p3=0x5638e68db2a0 p4=0x5638e68db2d0

可以看到 p3 等于 p1，p4 等于 p2。此时 p1 和 p3 属于同一个 bin，而 p2 和 p4 属于另一个 bin。

既然我们知道了 tcache 的内部构造，我们可以写一个程序，首先得到 tcache 的地址，再打印出每次 malloc/free 之后的状态：

#include <stdint.h>#include <stdio.h>#include <stdlib.h>#define TCACHE_MAX_BINS 64typedef struct tcache_entry { struct tcache_entry *next; struct tcache_perthread_struct *key;} tcache_entry;typedef struct tcache_perthread_struct { uint16_t counts[TCACHE_MAX_BINS]; tcache_entry *entries[TCACHE_MAX_BINS];} tcache_perthread_struct;void dump_tcache(tcache_perthread_struct *tcache) { for (int i = 0; i < TCACHE_MAX_BINS; i++) { if (tcache->counts[i]) { tcache_entry *p = tcache->entries[i]; printf("tcache bin #%d: %p", i, p); p = p->next; while (p) { printf(" -> %p", p); p = p->next; } printf("\n"); } }}int main() { // leak tcache address void *p0 = malloc(128); free(p0); tcache_entry *entry = p0; tcache_perthread_struct *tcache = entry->key; printf("tcache is at %p\n", tcache); // clear tcache p0 = malloc(128); void *p1 = malloc(32); void *p2 = malloc(32); free(p1); printf("after free(p1):\n"); dump_tcache(tcache); free(p2); printf("after free(p2):\n"); dump_tcache(tcache); void *p3 = malloc(32); printf("after malloc(p3):\n"); dump_tcache(tcache); void *p4 = malloc(32); printf("after malloc(p4):\n"); dump_tcache(tcache); printf("p1=%p p2=%p p3=%p p4=%p\n", p1, p2, p3, p4);}

运行结果如下：

tcache is at 0x558f39310010after free(p1):tcache bin #1: 0x558f39310740after free(p2):tcache bin #1: 0x558f39310770 -> 0x558f39310740after malloc(p3):tcache bin #1: 0x558f39310740after malloc(p4):p1=0x558f39310740 p2=0x558f39310770 p3=0x558f39310770 p4=0x558f39310740

打印出来的结果和预期一致。

接下来继续分析 malloc 的后续代码。

回到 __libc_malloc¶

如果 malloc 没有命中 tcache，或者 free 没有把空闲块放到 tcache 当中，会发生什么事情呢？接下来往后看，首先是 __libc_malloc 的后续实现：

if (SINGLE_THREAD_P) { victim = _int_malloc (&main_arena, bytes); // omitted return victim; }arena_get (ar_ptr, bytes);victim = _int_malloc (ar_ptr, bytes);