C++ STL（vector、map）内存结构

ajguthahbzzb

0x0 前言

---

pwn方向的C++题经常会涉及到许多STL的数据结构，本文对vector、map两种数据结构进行探讨和分析。其余数据结构在pwn方向中并不常用所以暂时不在本文讨论（在reverse方向常用的结构体我会放到后面的文章里探讨，主要是对无符号表的STL源码进行逆向）。
（由于文章确实不是很详细，所以后面做了一次修改）
vector的底层是三个指针指向堆内存里动态分配的结构体数组，而map底层是红黑树实现的。

0x1 演示代码

---

[C++] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <iostream> #include <vector> #include <map>   using namespace std;   int main() {     map<string, string> mp;     vector<string> vec;     for (int i = 0; i < 10; i++)     {         mp["k" + to_string(i)] = "v" + to_string(i);         vec.push_back("a" + to_string(i));     }       for (auto &e : mp) {         cout << e.first << " " << e.second << endl;     }     for (auto &e : vec) {         cout << e << endl;     }       return 0; }

linux环境下，将文件保存为main.cpp，执行g++ main.cpp -g -o main生成可执行文件。

0x2 gdb调试分析

---

运行完第一个for循环后，查看mp和vec的数据结构：


0x3 vec内存结构分析

---

直接执行p mp或p vec不能看到结构体各字段的信息，所以先找到其内部字段然后再显示其结构体信息。根据源码去查找其内部字段。下面的图片展示了vec内部各字段及内存结构。

可以看到其有三个字段，_M_start表示数组起始地址，_M_finish表示数组最后一个元素后面的元素的地址，_M_end_of_storage表示当前数组最大容量可到达的地址的下一个地址。
下面的图片展示了堆内数组的内存结构。


可以看到vector底层的结构体数组是线性存储在堆内的。上图存储了10个std::string结构体。

0x4 map内存结构分析

---

下面的图片展示了map内部各字段及内存结构。

总共6个字段，_M_key_compare，_M_header（_M_color，_M_parent，_M_left，_M_right），_M_node_count。
_M_key_compare在底层没有字段，仅占位。由于map底层是红黑树，所以用_M_color字段表示红或黑。_M_parent，_M_left，_M_right分别表示父节点、左右子节点。_M_node_count表示整棵树的大小。注意，_M_header的类型是std::_Rb_tree_node_base，与堆内节点的类型一致。
下面的图片展示了堆内节点的内存结构（以(k6, v6)为例）。

可以看到每个节点由std::_Rb_tree_node_base、键结构体、值结构体拼接而成。


0x5 vector扩容验证

---

vector大小从0x10开始，每超出容量便扩容为原来两倍。扩容时先把原来的数组free掉，然后和正常的malloc申请内存顺序一样先从tcache里取，如果没有则从其他bin里面取，且申请后不会将内存全设为0。
验证代码：

[C++] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <vector> #include <map> #include <malloc.h> #include <string.h>   using namespace std;     int main() {     vector<string> vec;       void *p[5];     for (int size = 0x10, i = 0; i < 5; size *= 2, i++)     {         p[i] = malloc(size);         memset(p[i], 'a', size);         malloc(0x10);     }     for (int i = 0; i < 5; i++)     {         free(p[i]);     }       for (int i = 0; i < 10; i++)     {         vec.push_back("a" + to_string(i));     }       for (auto &e : vec) {         cout << e << endl;     }       return 0; }

scz

这篇可以看看

STL容器逆向与实战 - [2023-02-07]
https://mp.weixin.qq.com/s/bfzeGbieYWaPS3_iB-gSeg

感觉不到风

取址就可以了

hah924

学习了，感觉也就那样

508916

感觉说的不是很详细

xixicoco

这块内容是最容易迷糊的

geekcode

学习到了谢谢

HypernovaG

对pwn不是很了解，看上去很直观，谢谢分享

Jerryiii

学到了一个新的 gdb 工具，谢谢分享

leipf

学习到了