本帖最后由 ajguthahbzzb 于 2025-3-20 19:24 编辑
0x0 前言 pwn方向的C++题经常会涉及到许多STL的数据结构,本文对vector、map两种数据结构进行探讨和分析。其余数据结构在pwn方向中并不常用所以暂时不在本文讨论(在reverse方向常用的结构体我会放到后面的文章里探讨,主要是对无符号表的STL源码进行逆向)。
(由于文章确实不是很详细,所以后面做了一次修改)
vector的底层是三个指针指向堆内存里动态分配的结构体数组,而map底层是红黑树实现的。
0x1 演示代码
[C++] 纯文本查看 复制代码 #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++] 纯文本查看 复制代码 #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;
}
|