Jeffly

相关概念

1. LSN 是一个 64 位逻辑字节偏移量，表示从 WAL 流起始位置的字节偏移
2. TLI（TimeLineID）TLI 是 时间线标识符，用于区分 WAL 历史的不同”分支”。

表现形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
* Pointer to a location in the XLOG. These pointers are 64 bits wide,
* because we don't want them ever to overflow.
*/

typedef uint64 XLogRecPtr;

/*
* Store the LSN as a single 64-bit value, to allow atomic loads/stores.
*
* For historical reasons, the storage of 64-bit LSN values depends on CPU
* endianness; PageXLogRecPtr used to be a struct consisting of two 32-bit
* values. When reading (and writing) the pd_lsn field from page headers, the
* caller must convert from (and convert to) the platform's native endianness.
*/
typedef struct
{
	uint64 lsn;
} PageXLogRecPtr;

相关转换

1
2
3
4
5

#define XLogSegNoOffsetToRecPtr(segno, offset, wal_segsz_bytes, dest) \
(dest) = (segno) * (wal_segsz_bytes) + (offset)

#define XLogSegmentOffset(xlogptr, wal_segsz_bytes) \
((xlogptr) & ((wal_segsz_bytes) - 1))

wal 日志文件

Format

1
00000001 00000000 00000003

Related code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#define XLogSegmentsPerXLogId(wal_segsz_bytes) \
(UINT64CONST(0x100000000) / (wal_segsz_bytes))

/*
* Generate a WAL segment file name. Do not use this function in a helper
* function allocating the result generated.
*/
static inline void
XLogFileName(char *fname, TimeLineID tli, XLogSegNo logSegNo, int wal_segsz_bytes)
{
	snprintf(fname, MAXFNAMELEN, "%08X%08X%08X", tli,
	(uint32) (logSegNo / XLogSegmentsPerXLogId(wal_segsz_bytes)),
	(uint32) (logSegNo % XLogSegmentsPerXLogId(wal_segsz_bytes)));
}

An example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

gujinfei@jeff:~/codes/blink-tree-cpp/build$ pg_controldata $PGDATA | grep "Bytes per WAL segment"
Bytes per WAL segment:                16777216
gujinfei@jeff:~/codes/blink-tree-cpp/build$ 

gujinfei=# SELECT pg_current_wal_lsn();
 pg_current_wal_lsn 
--------------------
 0/0384C598
(1 row)

gujinfei=# SELECT pg_walfile_name('0/0384C598');
     pg_walfile_name      
--------------------------
 000000010000000000000003
(1 row)

1. segno = 0x0384C598 / 0x1000000 = 3
2. offset = 0x0384C598 % 0x1000000 = 0x384C598
3. 文件名解析：
   • TLI（TimeLineID）：00000001
   • 3/256 = 00000000
   • 3%256 = 00000003

1. Richard Yen: pg_stats: How Postgres Internal Stats Work
   https://postgr.es/p/9mG
   2026-06-22

2. warda bibi: MCP For PostgreSQL: Automated Health Checks & Performance Analysis
   https://postgr.es/p/9nf
   2026-06-24

谓词锁：

1. 传统谓词锁：

• 真锁：锁住一个数学条件（如 age > 10）。
• 缺点：
  • 数据库难以判断任意两个条件是否重叠（数学上不可判定）
  • 性能极差

2. postgresql谓词锁：

• 假锁，实际上是标记（SIRead 标记）。
• 目的：支持 SSI（可串行化快照隔离）协议。
• 本质：在内存中不阻塞任何事务，只做“记事本”，记录谁读了什么，谁后来改了什么。

为什么记录 RW（读后写）依赖？

• 写偏斜（Write Skew）最难防。
• 常规锁只能解决 WR 依赖（先写后读）。
• 对 RW 依赖（先读后写），普通锁无法察觉

PostgreSQL 的解决方法

1. 事务 A 读数据 → 默默加 SIRead 标记。
2. 事务 B 修改数据 → 检查 SIRead 标记 → 在后台依赖图上连线（A →rw B）

An Example

让我们创建一个具有跨多个页面的索引的表（可以通过使用较低的填充因子值来实现）：

1
2
3
4

CREATE TABLE pred(n numeric, s text);
INSERT INTO pred(n) SELECT n FROM generate_series(1,10000) n; 
CREATE INDEX ON pred(n) WITH (fillfactor = 10);
ANALYZE pred;

如果查询执行顺序扫描，则会在整个表上获取谓词锁（即使某些行不满足提供的过滤条件）。

Sequential scan 丢失了谓词的精度，PG 只能保守地锁整表。这是一种宁可误判、不能漏判的策略——牺牲并发性，换取正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

mytest=# SELECT pg_backend_pid();
 pg_backend_pid 
----------------
         512701
(1 row)

mytest=# BEGIN ISOLATION LEVEL SERIALIZABLE;
BEGIN
mytest=*# EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM pred WHERE n > 100;
                   QUERY PLAN                   
------------------------------------------------
 Seq Scan on pred (actual rows=9900.00 loops=1)
   Filter: (n > '100'::numeric)
   Rows Removed by Filter: 100
   Buffers: shared hit=45
 Planning:
   Buffers: shared hit=15
(6 rows)

尽管谓词锁（predicate locks）拥有自己独立的底层基础设施，但 pg_locks 视图仍然会将它们与重量级锁（heavyweight locks）放在一起共同显示。所有的谓词锁在获取时，其模式一律为 SIRead 模式，该模式是“可串行化隔离读”（Serializable Isolation Read）的缩写。

1
2
3
4
5

mytest=*# SELECT relation::regclass, locktype, page, tuple FROM pg_locks WHERE mode = 'SIReadLock' AND pid = 512701 ORDER BY 1, 2, 3, 4;
 relation | locktype | page | tuple 
----------+----------+------+-------
 pred     | relation |      |      
(1 row)

需要注意的是，谓词锁的持有时间可能会超过事务本身的持续时间，因为它们被用来追踪事务之间的依赖关系。但无论如何，它们都是自动管理的。

如果查询执行的是索引扫描（index scan），情况就会有所好转。对于 B-tree 索引，只需在读取的堆元组（heap tuples，即实际的数据行）以及索引中被扫描的叶子页面（leaf pages）上设置谓词锁即可。这将“锁定”已被读取的整个范围，而不仅仅是那些精确的数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

mytest=# BEGIN ISOLATION LEVEL SERIALIZABLE;
BEGIN
mytest=*# EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM pred WHERE n BETWEEN 1000 AND 1001;
                            QUERY PLAN                             
-------------------------------------------------------------------
 Index Scan using pred_n_idx on pred (actual rows=2.00 loops=1)
   Index Cond: ((n >= '1000'::numeric) AND (n <= '1001'::numeric))
   Index Searches: 1
   Buffers: shared hit=1 read=2
 Planning:
   Buffers: shared hit=6
(6 rows)

mytest=*# SELECT relation::regclass, locktype, page, tuple FROM pg_locks WHERE mode = 'SIReadLock' AND pid = 512701 ORDER BY 1, 2, 3, 4;
  relation  | locktype | page | tuple 
------------+----------+------+-------
 pred       | tuple    |    4 |    96
 pred       | tuple    |    4 |    97
 pred_n_idx | page     |   28 |      
(3 rows)

已经扫描过的元组（数据行）所对应的索引叶子页面（leaf pages）数量是会发生变化的：例如，当向表中插入新行时，索引页面可能会发生分裂（split）。然而，PostgreSQL 充分考虑到了这种情况，并且也会将新出现的页面锁定

1
2
3
4
5
6
7
8
9
10
11

mytest=*# SELECT relation::regclass, locktype, page, tuple FROM pg_locks WHERE mode = 'SIReadLock' AND pid = 512701 ORDER BY 1, 2, 3, 4;
  relation  | locktype | page | tuple 
------------+----------+------+-------
 pred       | tuple    |    4 |    96
 pred       | tuple    |    4 |    97
 pred_n_idx | page     |   28 |      
 pred_n_idx | page     |  266 |      
 pred_n_idx | page     |  267 |      
 pred_n_idx | page     |  268 |      
 pred_n_idx | page     |  269 |      
(7 rows)

每一个被读取的元组（数据行）都是被单独锁定的，而这类元组的数量可能会相当庞大。谓词锁使用在服务器启动时分配的独立内存池。谓词锁的总数受到 max_pred_locks_per_transaction 参数值乘以 max_connections 参数值的限制（尽管从参数名称来看，谓词锁并不是按每个独立事务分别计算的）

在这里，我们遇到了与行级锁（row-level locks）相同的问题，但解决方式却截然不同：这里应用了“锁升级”（lock escalation）机制。

一旦与单个页面（page）相关的元组锁（tuple locks）数量超过了 max_pred_locks_per_page 参数的值(默认值设为 2)，它们就会被一个单一的页面级锁（page-level lock）所取代

1
2
3
4
5
6
7
8

mytest=*# EXPLAIN (analyze, costs off, timing off, summary off) SELECT * FROM pred WHERE n BETWEEN 1000 AND 1002;
                            QUERY PLAN                             
-------------------------------------------------------------------
 Index Scan using pred_n_idx on pred (actual rows=1002.00 loops=1)
   Index Cond: ((n >= '1000'::numeric) AND (n <= '1002'::numeric))
   Index Searches: 1
   Buffers: shared hit=15
(4 rows)

现在，我们不再拥有三个元组类型的锁，而是拥有了一个页面类型的锁：

1
2
3
4
5
6
7
8
9
10

mytest=*# SELECT relation::regclass, locktype, page, tuple FROM pg_locks WHERE mode = 'SIReadLock' AND pid = 512701 ORDER BY 1, 2, 3, 4;
  relation  | locktype | page | tuple 
------------+----------+------+-------
 pred       | page     |    4 |      
 pred_n_idx | page     |   28 |      
 pred_n_idx | page     |  266 |      
 pred_n_idx | page     |  267 |      
 pred_n_idx | page     |  268 |      
 pred_n_idx | page     |  269 |      
(6 rows)

锁升级肯定会导致误报序列化错误，这会对系统吞吐量产生负面影响。因此，必须在性能和在锁上花费可用资源之间找到适当的平衡。

Predicate locks 支持以下索引类型：

• B-Trees
• hash indexes, GiST, and GIN

如果执行索引扫描，但索引不支持谓词锁，则整个索引将被锁定。可以预见的是，在这种情况下，无故中止的事务数量也会增加。

为了在可串行化（Serializable）级别下实现更高效的运行，通过 READ ONLY 子句将事务显式声明为“只读”是非常有意义的。如果锁管理器（lock manager）发现一个只读事务不会与其他事务发生冲突，它就可以释放已经设置的谓词锁，并且不再获取新的谓词锁。而如果这样的事务同时被声明为 DEFERRABLE（可延迟的），那么只读事务异常（read-only transaction anomaly）也将得以避免。

Memory layout diagram

B-tree 在并发修改时，传统实现通常采用 lock coupling（也叫 crabbing）：从根开始向下加锁，只有确认当前节点是 safe node （即插入时不会触发 split 的节点）后才能释放父节点锁。当发生 split 时，可能需要长时间持有多层节点锁，并发性受到限制。
Lehman-Yao 1981年的论文给出了一个优雅的解法——只需要给每个节点增加两个字段，就能把最大同时持锁数降到3个常数。这篇文章记录我用C++实现这个算法的过程，以及踩过的坑。

B-link tree 是什么

B-link tree 是 b-tree的一个变体：增加了high-key和right-link：

• high-key：当前节点 key 范围的上界（所有 key 都满足 key <= high-key）。
• right-link：平级之间，左结点持有右结点的指针，可以方便的从左边访问到右边（不经过父节点）
  查询不需要加锁:

  Note the simplicity of the search, which behaves just as a nonconcurrent search, treating link pointers in exactly the same manner as any other pointer.

Note also that this procedure does no locking of any kind. This contrasts with conventional database search algorithms (e.g., Bayer and Schkolnick [3]), in which all searches read-lock the nodes they examine.

插入遵循自顶向下找到目标叶子，然后自底向上传播 split。加锁时最多同时持有三个锁:

1. 分裂节点的原始左半部分
2. 分裂节点上一层的两个节点
   与传统方法相比（即只有在确定节点为安全节点时才释放锁），这种做法在 锁粒度和并发性能上都有显著改进。

实现过程中踩的坑

1. 内部节点的 keys 可以为空
   B-tree 内部节点的 key 是相邻 children 之间的分隔符，只有 children >= 2 时才需要。当 max_keys=1 时，split 后右半部分内部节点只有1个 child，不需要任何分隔符，keys 为空是合法状态。开始误以为内部节点必须有 key，导致 max_keys=1 的边界情况一直跑不通。
2. 任意结点的均需要按顺序插入
   开始写代码时，受用例影响，key = 1、2、3、4、5 这样插入，用 push_back 直接追加 key，没有用 lower_bound 找到正确插入位置，导致换用例后节点内 keys 无序，ScanNode 的二分查找全部失效。B-tree 节点内的 keys 必须始终保持有序。
3. 分裂时需要区分叶子结点和中间结点
   分裂时叶子结点和中间结点需要区分处理：
   叶子结点：中间对半分，mid key 是左结点的最大 key，复制到父节点作为分隔符，同时也成为左节点的 high-key
   中间结点：中间对半分，mid key提升到父节点，右边从mid+1开始
   分裂算法以及流程需要很清晰，然后开始写代码，会事半功倍。而我没有想明白的情况下，改了好几版才最终成型
4. 打印树
   每完成一次插入后打印整棵树（或每次插入前先检查树），可以很快定位是哪一次插入开始破坏了树结构，比单纯调试代码效率高得多。
5. 并发插入时，需要考虑根结点的分裂，还有g_root_id的切换
6. 并发分裂时需要重新构建stack
7. 并发调试需要借助tsan工具

当前进度和后续计划

已实现论文中的并发插入流程，并验证最多持有三个锁的性质。

• Search
• Concurrent insert

代码

https://github.com/jeffrey-fly/blink-tree-cpp.git

1. 定义与核心功能

对 DAG（有向无环图）的顶点进行线性排序，使得每条有向边 在序列中满足 在 之前。

• 偏序线性化：解决任务调度、编译依赖等”先修课程”类问题
• 环路检测：若输出序列长度小于节点总数，说明图中存在环

2. 核心数据结构

• inDegree[i]（入度数组）：记录节点 的剩余前置依赖数，inDegree[i] == 0 时节点就绪
• Queue（就绪队列）：存储当前所有入度为 0、可立即处理的节点
• Graph（邻接表）：快速查找节点 的所有后继节点

3. 算法步骤（Kahn’s Algorithm）

1. 初始化

   • 遍历全图，统计每个节点的初始入度
   • 将所有入度为 0 的节点加入队列

2. 迭代处理

   • 取出队头节点 ，加入结果列表
   • 遍历 的所有后继节点 ，执行 inDegree[m]--
   • 若 inDegree[m] 减为 0，将 加入队尾

3. 结果判定

   • 输出节点数等于顶点总数 → 排序成功
   • 否则 → 图中存在环

4. 进阶：逆向填充（DFS 实现）

DFS 实现拓扑排序时，节点在其所有后继节点处理完毕后才被记录，因此天然得到逆序结果。标准做法是维护指针 index = totalNodes - 1，每次将完成的节点放入 result[index]，然后 index--，最终 result 即为正向拓扑序。

5. 复杂度分析

字典序最小的拓扑排序：将 Queue 替换为 Min-Heap（优先队列）即可。

一 内存屏障概念

屏障（fence）的核心作用是两件事：保证指令顺序和跨线程可见性。两者听起来像一回事，但实现层面是分开的。

1. 编译器屏障（compiler fence）：只阻止编译器重排指令，不产生任何 CPU 指令。asm volatile("" ::: "memory") 就是典型例子，零运行时开销。
2. CPU 内存屏障（hardware fence）：实际生成一条 CPU 指令，阻止处理器乱序执行，并确保 store/load 结果对其他核可见。

两者都需要，缺一不可——即使 CPU 不乱序，编译器也可能把你的代码搬到错误位置。

二 CPU 内存模型对比

StoreLoad hazard 是最常见的坑：当前核的 store 还在 store buffer 里没有刷到缓存，后续的 load 却绕过 store buffer 直接从缓存或内存读取，于是读到了旧值。x86 的 TSO 模型里，这是唯一允许的乱序方向；ARM 上四个方向都可能出问题。

解决办法是在写端用 release，读端用 acquire，在两个线程之间建立 happens-before 链。

三 Release / Acquire Fence

配对规则：

release store（写端）：在逻辑上声明”这个 store 之前的所有写都完成了”，对应 ARM 上的 STLR 指令。

acquire load（读端）：在逻辑上声明”读到这个值之后，才能看后面的操作”，对应 ARM 上的 LDAR 指令。

不要靠 x86 的天然 TSO 顺序写无锁代码——否则在 ARM 上会悄悄出错，而且很难复现。

四 示例

下面是一个单生产者单消费者（SPSC）环形队列的最简版本，用来演示 release/acquire 的典型用法。多生产者或多消费者场景需要额外的 CAS，不在本例讨论范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <atomic>
#include <iostream>

// 对齐到缓存行，避免 false sharing
alignas(64) std::atomic<int> tail{0};
alignas(64) int head{0};   // head 只被消费者访问，不需要原子变量
int buffer[1024];

void producer() {
    int t = tail.load(std::memory_order_relaxed);

    buffer[t % 1024] = 42;

    // release：保证 buffer 的写入在 tail 更新之前对其他核可见
    // ARM 上生成 STLR 指令
    tail.store(t + 1, std::memory_order_release);
}

void consumer() {
    // acquire：读到 tail 的新值后，能看到 producer 在 release 之前写的所有内容
    // ARM 上生成 LDAR 指令
    while (tail.load(std::memory_order_acquire) <= head) {
        // 自旋等待时可以加 CPU hint，让流水线让出资源给其他超线程
        // ARM: __builtin_arm_yield()
        // x86: _mm_pause()
    }

    int value = buffer[head % 1024];
    std::cout << "Data: " << value << std::endl;

    head++;  // head 是消费者私有的，直接递增即可
}

注意：

• tail 用 std::atomic，因为生产者写、消费者读，存在跨线程访问
• head 只有消费者自己读写，用普通 int 就够了，不需要原子操作
• tail 的初始 load 用 relaxed，因为这里只是读自己上次写的值，不涉及跨线程同步

五 总结

• x86 TSO：CPU 层面保证了大部分顺序，memory_order_release/acquire 在 x86 上通常不会生成额外的 fence 指令。但编译器屏障依然必要，不能省略——省了之后编译器可能把你的代码重排到完全错误的地方。
• ARM：什么都不帮你保证，每一处需要同步的地方都得显式写出来。好处是性能更可控，坏处是出错了很难调试。

今天工作中遇到一个有意思的事，同事调试程序发现死锁了，但是一打pstack就过去了。分析过去的堆栈，发现线程卡在 write() 上，打 pstack 后就突然继续执行了。
恰好还有一台出现问题的环境留着，等待分析验证

一 堆栈现象

1
2
3

#0 ... write() from libpthread.so.0
#1 ... ?? () from libasan.so.5
#2 ... NetWrite(...)  // 自己封装的写函数

• 卡住现象是在发送端
• 打 pstack 后线程立即恢复，行为类似“虚假唤醒”

二 原因分析

同事反馈，数据量很大。查看代码，发现是阻塞的 TCP write
那么怀疑到了发送端缓冲区：

2.1 阻塞的 TCP write

所以，如果对端不读取数据：

• 发送端 send buffer 满
• write() 阻塞，线程挂起
• 网络层也没有错误，写线程只能等待

2.2 信号打断 (EINTR)

• 阻塞的 write() 可以被 可中断信号打断:返回值：-1, errno=EINTR
• pstack attach 就是触发 signal 的一种情况，所以线程看似“自己醒了”

注意：信号打断不会解决 send buffer 满导致的阻塞，它只是让系统调用提前返回。

2.3 关于接收端

接收端是基于 libevent 的协程处理，观察堆栈没有触发事件 → 没有调用 read()，然后发送端 write() 阻塞

最终确认
杀掉接收端后，发送端 write() 立即返回。 和pstack效果一样

三 解决方式

得排查为什么接收端不收数据，而不是死锁问题。

四 总结

1. TCP write 阻塞的根本原因：对端不读 → send buffer 满
2. 信号（如 pstack attach）可以打断阻塞，返回 EINTR
3. TCP write 短写是常态，循环处理保证数据完整
4. ASan 堆栈出现只是包装函数，不是问题根源
5. 安全的写函数必须循环处理短写 + EINTR，阻塞问题需用非阻塞或专门线程解决

一、栈的基本性质

在 x86_64 架构（Linux / macOS）下：

• 栈从 高地址向低地址增长
• 栈顶由 rsp（stack pointer）指示
• push → rsp -= 8
• pop → rsp += 8

原因：

• 早期内存布局约定（低地址给 code / data）
• 向下增长可以避免与 heap 冲突（heap 通常向上增长）

二、Sample code

1
2
3
4
5
6
7
8
9
10
11
12
13

int add(int a, int b)
{
    int c = a + b;
    return c;
}

int main()
{
    int x = 3;
    int y = 4;
    int z = add(x, y);
    return z;
}

三、Disassem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(lldb) disassem
test`main:
    0x100003f80 <+0>:  pushq  %rbp
    0x100003f81 <+1>:  movq   %rsp, %rbp
    0x100003f84 <+4>:  subq   $0x10, %rsp
    0x100003f88 <+8>:  movl   $0x0, -0x4(%rbp)
    0x100003f8f <+15>: movl   $0x3, -0x8(%rbp)
->  0x100003f96 <+22>: movl   $0x4, -0xc(%rbp)
    0x100003f9d <+29>: movl   -0x8(%rbp), %edi
    0x100003fa0 <+32>: movl   -0xc(%rbp), %esi
    0x100003fa3 <+35>: callq  0x100003f60               ; add(int, int)
    0x100003fa8 <+40>: movl   %eax, -0x10(%rbp)
    0x100003fab <+43>: movl   -0x10(%rbp), %eax
    0x100003fae <+46>: addq   $0x10, %rsp
    0x100003fb2 <+50>: popq   %rbp
    0x100003fb3 <+51>: retq 

1
2
3
4
5
6
7
8
9
10
11
12
13

(lldb) disassemble --name add
test`add:
    0x100003f60 <+0>:  pushq  %rbp
    0x100003f61 <+1>:  movq   %rsp, %rbp
    0x100003f64 <+4>:  movl   %edi, -0x4(%rbp)
    0x100003f67 <+7>:  movl   %esi, -0x8(%rbp)
    0x100003f6a <+10>: movl   -0x4(%rbp), %eax
    0x100003f6d <+13>: addl   -0x8(%rbp), %eax
    0x100003f70 <+16>: movl   %eax, -0xc(%rbp)
    0x100003f73 <+19>: movl   -0xc(%rbp), %eax
    0x100003f76 <+22>: popq   %rbp
    0x100003f77 <+23>: retq   
    0x100003f78 <+24>: nopl   (%rax,%rax)

四、函数栈帧的建立（Prologue）

前3条指令：

1
2
3

pushq %rbp
movq  %rsp, %rbp
subq  $0x10, %rsp

作用：

• 保存上一层函数的 rbp
• 建立当前函数栈帧基址
• 为局部变量分配 16 字节空间

注意：
即便只需要 12 字节（3 个 int），编译器仍分配 16 字节。

原因：

• 栈 16 字节对齐（System V ABI 要求）
• 调用其他函数前必须满足对齐约束

五、System V ABI 参数传递

在 x86_64 下（System V ABI）：

前 6 个整数参数通过寄存器传递：

因此：

1
2

movl -0x8(%rbp), %edi
movl -0xc(%rbp), %esi

并不是通过栈传参。

六、call 指令的真实语义

1

callq 0x100003f60

等价于

1
2
3

rsp -= 8
*(rsp) = rip_after_call
rip = target

即：

返回地址被压入栈中。在本例中：

1

0x100003fa8 被压入栈

七、执行 call 后的栈结构

假设进入 add 之前，main 的栈帧如下：

1
2
3
4
5
6
7
8
9
10
11
12

高地址
-------------------------
return address (to caller of main)
-------------------------
saved rbp
-------------------------  ← rbp (main)
x   (-0x8)
y   (-0xc)
z   (-0x10)
padding
-------------------------  ← rsp
低地址

执行 call 后：

1
2
3
4
5
6
7
8
9
10
11

高地址
-------------------------
return address to main caller
-------------------------
saved rbp (main)
-------------------------  ← rbp(main)
local variables
-------------------------
return address (0x100003fa8)  ← rsp
-------------------------
低地址

八、add 函数栈帧

add 的 prologue：

1
2
3

pushq  %rbp
movq   %rsp, %rbp
movl   %edi, -0x4(%rbp)

这里 没有 sub rsp。

该版本编译器没有显式为 add 分配额外栈空间。

本例中 add 为 leaf function。虽然未显式 sub rsp 分配空间，但由于使用了 push %rbp，局部变量仍然位于当前栈帧中，并未实际使用 red zone。
在 macOS / Linux 的 System V ABI 下：

栈顶以下 128 字节称为 red zone，可在 leaf function 中使用。

所以 add 是一个 leaf function：

• 没有再调用其他函数
• 不需要保持 16-byte 对齐给下一级
• 编译器优化掉 sub rsp

栈变为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

高地址
--------------------------------
main 的局部变量
--------------------------------
saved rbp (main)
--------------------------------
return addr → main caller
--------------------------------
return addr → main  ← 8(%rbp_add)
saved rbp (main)    ← 0(%rbp_add)
--------------------------------  ← rbp(add)
local a copy
local b copy
local c
--------------------------------  ← rsp
低地址

注意：
每次函数调用都会：

• 保存调用者 rbp
• 建立新的栈帧

形成一条链。

本例中 add 为 leaf function，未显式执行 sub rsp。
在 System V ABI 下允许使用 128 字节 red zone，因此编译器可省略栈空间分配。

九、rbp 与 rsp 的角色

局部变量用 rbp - offset 访问。

返回地址在：

1

8(%rbp)

saved rbp 在：

1

0(%rbp)

十、ret 的行为

1

ret

等价于

1
2

rip = *(rsp)
rsp += 8

即：

• 弹出返回地址
• 跳转回调用点

其他

函数调用 =

1. 保存返回地址
2. 建立栈帧
3. 执行函数
4. 恢复栈帧
5. 跳回

栈本质是：

一种严格的 LIFO 调用上下文保存机制

总结

• 栈从高地址向低地址增长
• call 会压入返回地址
• 每个函数建立自己的栈帧
• rbp 固定当前帧
• rsp 始终指向栈顶
• System V ABI 下参数主要走寄存器

addr2line 是 GNU Binutils 提供的一个调试工具，用于将程序地址转换为源代码文件 + 行号。
其底层依赖 ELF 文件中的 DWARF 调试信息。

典型使用场景：

• core dump 分析
• 崩溃栈回溯解析
• 日志中只有地址信息
• 线上二进制与调试符号分离

示例分析

例如某崩溃日志中看到：

1
2

.../your_binary(_ZN19MyTableC1EPS_+0x10d)[0x1f792fd]
......

含义：

• ZN19MyTableC1EPS → C++ mangled 名字
• +0x10d → 相对于函数起始地址的偏移
• [0x1f792fd] → 实际程序地址

1. 如果符号信息在可执行文件上

   1	addr2line -e your_binary -f -C 0x1f792fd

2. use eu-addr2line 加载symbol

   1	eu-addr2line -e ./your_binary --debuginfo-path=./your_binary.debug 0x1f792fd

   or

   1 2	# 基本用法 (记得加上 -f 显示函数名, -C 还原C++符号) addr2line -fCe <path_to_debug_symbols_file> <address>

   output：
   mytable/MyTable.cpp:1070

3. 只有函数名 + 偏移
   例如日志只有： MyTable::insert+0x52
   需要手动计算地址。

   • 查函数起始地址

     1	nm -C your_binary | grep my_func

     如果 binary 已 strip，需要对 debug 文件执行 nm：

     或

     1	objdump -t your_binary | grep MyTable::insert

     假设得到：

     1	0000000000401230 T MyTable::insert

   • 加上偏移

     1	0x401230 + 0x52 = 0x401282

   • 再 addr2line

     1	addr2line -e your_binary -f -C 0x401282

PIE / ASLR 注意事项

如果二进制是 PIE（Position Independent Executable）：

1

readelf -h your_binary | grep Type

如果看到：

1

Type: DYN (Position-Independent Executable file)

说明是 PIE。

这时：

• 崩溃日志中的地址 = load_base + offset

• 必须减去加载基地址

在 core dump 中：

1

info proc mappings

或者

1

cat /proc/<pid>/maps

找到加载基址，例如：

1
2

7f3c2d400000-...
真实地址 = 崩溃地址 - 基址

再传给 addr2line。

否则会解析失败或定位错误。

常用排错检查

1. 是否包含调试信息

   1	readelf --sections your_binary | grep debug

2. 是否被 strip

   1	file your_binary