C++ 逆向之顺序容器内存结构

此处对c++的stl顺序容器的内存结构进行总结,以便在逆向过程中更好的识别。如有不妥之处,请指出。
编译器使用g++ 7.5。

array

array 用法如下

1
2
3
4
5
6
7
8
#include <iostream>
#include <array>

using namespace std;
array<int, 30> a;
int main(){
cin >> c[0] >> c[1];
}

array的用法和普通数组相同。在头文件array中可以找到定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _Tp, std::size_t _Nm>
struct __array_traits
{
typedef _Tp _Type[_Nm];
typedef __is_swappable<_Tp> _Is_swappable;
typedef __is_nothrow_swappable<_Tp> _Is_nothrow_swappable;

static constexpr _Tp&
_S_ref(const _Type& __t, std::size_t __n) noexcept
{ return const_cast<_Tp&>(__t[__n]); }

static constexpr _Tp*
_S_ptr(const _Type& __t) noexcept
{ return const_cast<_Tp*>(__t); }
};
template<typename _Tp, std::size_t _Nm>
struct array
{
typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
typename _AT_Type::_Type _M_elems;
}

以上代码省略了大部分无关代码
typename _AT_Type::_Type _M_elems;定义了储存的空间,等价于_Tp[_Nm] _M_elems;。所以array定义了之后就不能改变大小。
array容器和普通的数组在内存中没有任何区别,函数内定义的array仍然储存在栈上,只是在普通的数组上封装了迭代器等操作。有区别的一点是sizeof(array<_Tp, _Nm>) = sizeof(_Tp) * _Nm

vector

vector与array不同的一点是在定义之后可以动态改变大小。
在头文件vector可以找到定义。
vector继承_Vector_base
_Vector_base内有一个结构体,_Vector_impl
_Vector_impl内定义了三个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _Tp, typename _Alloc>
struct _Vector_base
{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Tp>::other _Tp_alloc_type;
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
pointer;

struct _Vector_impl
: public _Tp_alloc_type
{
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
}
public:
_Vector_impl _M_impl;
}

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>{...}

vector内定义了三个指针,_M_start, _M_finish, _M_end_of_storage,分别指向在堆上申请内存的开始,当前,结束。所以sizeof(vector<_tp>)的大小是固定的等于sizeof(pointer) * 3。
另外vector的成员函数size() = (_M_finish - _M_start) / sizeof(_Tp),而vector的capacity() = (_M_end_of_storage - _M_start) / sizeof(_Tp)。使用一下代码可以验证猜测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
struct T{
int * _M_start;
int * _M_finish;
int * _M_end_of_storage;
void print(){
printf("%lx\n",this->_M_start);
printf("%lx\n",this->_M_finish);
printf("%lx\n",this->_M_end_of_storage);
}
};
int main(){
vector<int> b;
T *t = reinterpret_cast<T *>(&b);
b.push_back(1);
b.push_back(2);
b.push_back(3);
t->print();
int *a = t->_M_start;
for(;a!=t->_M_finish;a++)
printf("%d\n", *a);
}

输出

1
2
3
4
5
6
560454460e70
560454460e7c
560454460e80
1
2
3

在vector内只存储了三个指针,所以vector无论定义在函数内部还是外部,都只占用3*sizeof(pointer)的大小。所以在逆向中遇到了连续存储的三个指针,第一个指针指向开始,第二个指针指向第二个要存储的位置,第三个指针指向结尾。就可以推断是vector。

list

list继承_List_base
_List_base内有一个结构体,_List_impl;
_List_impl内定义了一个_List_node;
_List_node结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
}
template<typename _Tp>
struct _List_node : public __detail::_List_node_base
{
#if __cplusplus >= 201103L
__gnu_cxx::__aligned_membuf<_Tp> _M_storage;
_Tp* _M_valptr() { return _M_storage._M_ptr(); }
_Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
#else
_Tp _M_data;
_Tp* _M_valptr() { return std::__addressof(_M_data); }
_Tp const* _M_valptr() const { return std::__addressof(_M_data); }
#endif
};

所以sizeof(list<_tp>)的大小等于sizeof(pointer) * 2 + sizeof(size_t)

1
2
3
4
5
list<long> d;
d.push_back(1);
d.push_back(5);
d.push_back(3);
d.push_back(3);

使用gdb的x命令查看内存可以得到如下内容

1
2
3
4
5
0x00005555557570e00x000055555576ae80	0x000055555576aee0       0x0000000000000004
0x000055555576ae800x000055555576aea0 0x00005555557570e0 0x0000000000000001
0x000055555576aea00x000055555576aec0 0x000055555576ae80 0x0000000000000005
0x000055555576aec00x000055555576aee0 0x000055555576aea0 0x0000000000000003
0x000055555576aee00x00005555557570e0 0x000055555576aec0 0x0000000000000003

如图list<_tp>内有一个_list_node_base节点,该节点的next指向存储数据的开始,prev指向数据的结束,data储存list的大小。list容器实现了一个双向循环链表,而list存储的是指向储存这个链表大小的特殊节点。

deque

deque比较复杂,可以看做vector和array(使用array存储每个vector的起始地址)的组合。在头文件stl_deque.h中可以找到deque的定义。
deque继承_Deque_base
_Deque_base中定义了结构体_Deque_impl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator
{
typedef __ptr_to<_Tp> _Elt_pointer;
typedef __ptr_to<_Elt_pointer> _Map_pointer;
_Elt_pointer _M_cur;
_Elt_pointer _M_first;
_Elt_pointer _M_last;
_Map_pointer _M_node;
}
typedef _Deque_iterator<_Tp, _Tp&, _Ptr> iterator;
typedef typename iterator::_Map_pointer _Map_pointer;
struct _Deque_impl : public _Tp_alloc_type
{
_Map_pointer _M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
}

可以看出deque的迭代器(_Deque_iterator)相比vector就多了一个指向mapTable(_M_node)的指针。
故,sizeof(deque<_Tp>) = sizeof(pointer) + sizeof(size_t) + 2 * sizeof(iterator) = 9 * sizeof(pointer) + sizeof(size_t)

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <deque>
using namespace std;

deque<int> a;
int main(){
for(int i=1;i<=10;i++)
a.push_back(i);
return 0;
}

假设每次malloc的大小是4(实际情况比这大得多),则此时的内存分布如下图

mapTable实际就是一个array,而它的每个元素分别指向一个vector。所以deque可以看做vector和array的组合。

文章目录
  1. 1. array
  2. 2. vector
  3. 3. list
  4. 4. deque