-
-
[原创]浅谈STL容器的识别
-
发表于: 2021-12-1 15:44
-
在逆向由C++编写的产品时，最头疼的莫过于两个问题：虚函数和STL，前者会生成一些间接CALL，导致IDA在分析时无法进一步交叉引用，后者采用了大量模板技术，再加上编译器优化，导致比较难提取到固定的签名来识别这些函数。因此，本文打算结合源码、静态分析和动态调试，谈一谈常用的STL容器的基本原理和识别方法。
vs2019（v142）+ x86 + Release + MT
首先简单浏览一下string在源码中的内存布局，有一个大致印象。
估计对C++不熟悉的朋友看到上面这堆代码已经懵逼了，我在这里只根据源码简单的解释一下string中的内存布局，因此看不懂的也没有关系，并不影响。
string中只有一个类成员变量_Mypair并且类型是pair（对_Compressed_pair感兴趣可以自行深入看一下，关键技术：Empty base optimization），绝大多数情况下，_Mypair在Release下的内存布局与_Scary_val（_Mypair的第二个类型）一致，_Scary_val是一个根据Alloc类型来推导出来的，具体细节不在赘述，最终找到了如下代码：
现在代码已经非常清晰了，可以简单的理解为string由三个类成员变量组成：Union类型的_Bx、size_type类型的_Mysize和_Myres。现在必须要说一下string的短字符串优化（SSO）技术，string为了减少对内存的申请次数，如果字符串过短（小于16字节）则直接将字符串拷贝到自身的buffer中，如果字符串长度超过自身buffer预设的大小，则会申请一块内存来存储该字符串，自身则只记录申请的内存地址。基于源码的讲解就到这里，接下来，编译成二进制进行分析。
原始C++代码：
IDA反编译代码：
关于string的识别：
在IDA中，可以根据字符串"string too long"来进行识别，例如上面这个例子，在函数sub_401260中，有一个关于Size的判断：
在OD/X64DBG中，可以根据内存布局来快速判断，基本有两种形式：
根据分析string的经验，可以很容易看出来_Vector_val的内存布局即是vector的内存布局
vector的实现还是非常简单的，只有三个类成员变量：_Myfirst、_Mylast和_Myend，分别指向数组的开始、有效元素的结尾和数组的结尾。vector中没有记录size，而是通过_Mylast-_Myfirst计算而来的，同理，capacity是通过_Myend-_Myfirst计算而来的。下面，我们直接看代码。
原始C++代码：
IDA反编译代码：
关于vector的识别：
在IDA中，可以采用和string相同的方式来识别vector，使用vector后编译会产生"vector too long"的字符串
在OD/X64DBG中，可以根据内存布局来快速判断，vector只有一种形式：
在最后，顺便说一下vector的内存分配策略，直接上源码：
代码也非常清晰，通过这句代码可以看出const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;，一般情况下，增长后的内存大小是原内存大小的1.5倍。
list是一个双向循环链表，整体的设计与前两个容器非常相似，直接看代码。
list的内存布局在Release下可以基本看成和_List_val一致，_List_val是由两个类成员函数_Myhead和_Mysize组成的，前者指向list的头节点，后者用于统计list的当前size（在c++11以前，list::size()的算法时间复杂度可能是O(n)，c++11后保证了时间复杂度是O(1)，因此可以放心用list::size()获取链表的元素个数了）。根据刚才的介绍，应该很容易能算出list本身所占的内存大小了（在32位下是8，64位下是16）。
然后我们再看一下_List_node的声明，刚才已经说过stl的list是双向循环链表，因此肯定包含Next和Prev，在这里可以记一下Next和Prev的顺序，以后在用动态调试器分析时可以快速遍历整个list，紧接着是list的Value类型，也就是list<T>当中T的类型。至此，list的全部类成员变量都已经分析完毕，接下来，编译成二进制进行分析。
原始C++代码：
IDA反编译代码：
关于list的识别：
在IDA中的识别方式与string和vector相同，不再具体说明，在OD/X64DBG中，可以根据内存布局来快速判断，list只有一种形式：
简单容器类型到这里就结束了，下面将介绍较复杂的容器类型map和unordered_map(hash_map)。
stl中的map是基于红黑树实现的，本文不涉及红黑树的具体原理，仅站在内存布局的角度说明msvc版本红黑树的实现。
map和set的实现区别：
map和set底层都是红黑树实现的，在msvc版本的stl中，它们均继承自_Tree class，唯一的区别就是map是由key和value组成的，而set只有key而没有value。multimap和multiset除了允许重复key以外其它和非multi版本一致。
根据前几个容器的分析经验，直接找到_Scary_val对应的类型即可，最终代码如下：
相比普通的红黑树，stl中的红黑树多了一个head节点，并且有以下几个特点：
节点的left或者right为null的情况没有在图中表现出来，实际在stl中，它们被指向head，例如：most left节点的left节点本来应该是null，但在stl的实现中，它被指向head，可通过_Isnil判断。
介绍完了和普通红黑树的基本区别，接下来我们看一下_Tree的内存布局，_Tree本身是由_Myhead和_Mysize组成的，在32位下_Tree总共占用8字节空间，而_Tree_node的内存大小要根据实际Value的类型来计算，在下面的例子中，_Tree_node总共占用24字节空间（_Left(4)+_Parent(4)+_Right(4)+_Color(1)+_Isnil(1)+2字节填充+_Myval(8)）。
原始C++代码：
IDA反编译代码：
对遍历过程有疑问的可以对照下面的C++源码：
最后看一下在内存中的布局：
最后一个使用率比较高的容器莫过于unordered_map了，它内部是由Hash Table实现的，它与hash_map基本一致，但是unordered_map已经被纳入到C++标准当中的，因此在日常使用上，也更推荐使用unordered_map而不是hash_map。
与之前一样，先看一下源码：
Hash Table有两种常见的实现方式：开放定址法和链地址法。stl中的unordered_map中使用的便是链地址法，正如其名，unordered_map中所有Value都是存储在_List当中的，方便顺序遍历所有节点，_Vec记录Hash(Key)对应的List Node位置，用于快速索引到对应的List Node。
我们来先分析下_Hash的内存布局，_Traitsobj是一个模板类型，不是很直观，经过我的搜索，内部最主要记录了load factor，是一个float类型，占用4个字节，默认情况是1，_List和_Vec和标准stl的List和Vector类型的内存布局一致，_Mask和_Maxidx在32位下个占用4个字节，一般情况下_Mask=_Maxidx-1，这点在后面的反编译代码中也能体现出来。最终计算得出_Hash总共占用32字节（_Traitsobj(4)+_List(8)+_Vec(12)+_Mask(4)+_Maxidx(4)）。
下面看一段测试代码：
原始C++代码：
IDA反编译代码：
最后看一下在内存中的布局：
在实际逆向的过程中，通过IDA生成的反编译代码可能要比本文展示的更加复杂，通常都是结构体加上stl容器嵌套造成的，因此并没有一种可以识别出任意stl容器的方案。对于这类代码的还原，我更倾向于动态静态相结合，根据内存布局初步判断容器类型，然后结合初始化代码进一步验证我们的猜想。
template <class _Elem, class _Traits = char_traits<_Elem>, class _Alloc = allocator<_Elem>>
class basic_string {
private: using _Alty = _Rebind_alloc_t<_Alloc, _Elem>;
using _Alty_traits = allocator_traits<_Alty>;
using _Scary_val = _String_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Elem>,
_String_iter_types<_Elem, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Elem&, const _Elem&>>>;
// 省略若干代码
private: _Compressed_pair<_Alty, _Scary_val> _Mypair;
};template <class _Elem, class _Traits = char_traits<_Elem>, class _Alloc = allocator<_Elem>>
class basic_string {
private: using _Alty = _Rebind_alloc_t<_Alloc, _Elem>;
using _Alty_traits = allocator_traits<_Alty>;
using _Scary_val = _String_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Elem>,
_String_iter_types<_Elem, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Elem&, const _Elem&>>>;
// 省略若干代码
private: _Compressed_pair<_Alty, _Scary_val> _Mypair;
};template <class _Val_types>
class _String_val : public _Container_base {
public: using value_type = typename _Val_types::value_type;
using pointer = typename _Val_types::pointer;
using size_type = typename _Val_types::size_type;
// 对于string的情况下_BUF_SIZE == 16
static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);
// 省略若干代码
union _Bxty { // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // TRANSITION, ABI: _Alias is preserved for binary compatibility (especially /clr)
} _Bx;
// 在x86下size_type = uint32_t
size_type _Mysize; // current length of string
size_type _Myres; // current storage reserved for string
};template <class _Val_types>
class _String_val : public _Container_base {
public: using value_type = typename _Val_types::value_type;
using pointer = typename _Val_types::pointer;
using size_type = typename _Val_types::size_type;
// 对于string的情况下_BUF_SIZE == 16
static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);
// 省略若干代码
union _Bxty { // storage for small buffer or pointer to larger one
value_type _Buf[_BUF_SIZE];
pointer _Ptr;
char _Alias[_BUF_SIZE]; // TRANSITION, ABI: _Alias is preserved for binary compatibility (especially /clr)
} _Bx;
// 在x86下size_type = uint32_t
size_type _Mysize; // current length of string
size_type _Myres; // current storage reserved for string
};int main(int argc, char* argv[]) {
std::string v1 = argv[0];
printf("%s\n", v1.c_str());
return 0;
}int main(int argc, char* argv[]) {
std::string v1 = argv[0];
printf("%s\n", v1.c_str());
return 0;
}// 代码从IDA中提取，为了方便解释，结构和变量名有所调整
int __cdecl main(int argc, const char **argv, const char **envp)
{ char *v3; // edx
const char *v4; // ecx
void **v5; // eax
void *v6; // ecx
// string的内存大小为sizeof(void*) * 6
void *str[6]; // [esp+4h] [ebp-1Ch] BYREF
// 1. 初始化string
// 将_Mysize设置成0
str[4] = 0;
// 将_Myres设置成15
str[5] = (void *)15;
// 由于C风格字符串由0结尾，因此初始化阶段将_Buf的首个字节设置成0
LOBYTE(str[0]) = 0;
// 2. 将argv[0]赋值给string
v3 = (char *)*argv;
v4 = *argv;
// 具体的赋值函数
sub_401260(str, v3, strlen(v4));
// 3. 获取string的字符串首地址
v5 = str; // 通过_Buf获取字符串首地址
// 判断_Myres是否大于等于16
if ( str[5] >= (void *)0x10 )
v5 = (void **)str[0]; // 通过_Ptr获取字符串首地址
// 打印结果
printf("%s\n", (const char *)v5);
// 4. 释放string的内存
// 如果_Myres大于16则需要释放字符串的内存
if ( str[5] >= (void *)0x10 )
{
v6 = str[0];
// 与BigAllocation有关，本文不过多介绍
if ( (unsigned int)str[5] + 1 >= 0x1000 )
{
v6 = (void *)*((_DWORD *)str[0] - 1);
if ( (unsigned int)(str[0] - v6 - 4) > 0x1F )
_invalid_parameter_noinfo_noreturn();
}
sub_4014BC(v6); // j_free的间接调用
}
return 0;
}// 代码从IDA中提取，为了方便解释，结构和变量名有所调整
int __cdecl main(int argc, const char **argv, const char **envp)
{ char *v3; // edx
const char *v4; // ecx
void **v5; // eax
void *v6; // ecx
// string的内存大小为sizeof(void*) * 6
void *str[6]; // [esp+4h] [ebp-1Ch] BYREF
// 1. 初始化string
// 将_Mysize设置成0
str[4] = 0;
// 将_Myres设置成15
str[5] = (void *)15;
// 由于C风格字符串由0结尾，因此初始化阶段将_Buf的首个字节设置成0
LOBYTE(str[0]) = 0;
// 2. 将argv[0]赋值给string
v3 = (char *)*argv;
v4 = *argv;
// 具体的赋值函数
sub_401260(str, v3, strlen(v4));
// 3. 获取string的字符串首地址
v5 = str; // 通过_Buf获取字符串首地址
// 判断_Myres是否大于等于16
if ( str[5] >= (void *)0x10 )
v5 = (void **)str[0]; // 通过_Ptr获取字符串首地址
// 打印结果
printf("%s\n", (const char *)v5);
// 4. 释放string的内存
// 如果_Myres大于16则需要释放字符串的内存
if ( str[5] >= (void *)0x10 )
{
v6 = str[0];
// 与BigAllocation有关，本文不过多介绍
if ( (unsigned int)str[5] + 1 >= 0x1000 )
{
v6 = (void *)*((_DWORD *)str[0] - 1);
if ( (unsigned int)(str[0] - v6 - 4) > 0x1F )
_invalid_parameter_noinfo_noreturn();
}
sub_4014BC(v6); // j_free的间接调用
}
return 0;
}void *__thiscall sub_401260(void *this, void *Src, size_t Size)
{ // ...
if ( Size > 0x7FFFFFFF )
sub_4011A0();
// ...
}void __noreturn sub_4011A0(){ sub_40145B("string too long");
}void *__thiscall sub_401260(void *this, void *Src, size_t Size)
{ // ...
if ( Size > 0x7FFFFFFF )
sub_4011A0();
// ...
}void __noreturn sub_4011A0(){ sub_40145B("string too long");
}// 第一种，小于16字节的字符串
// _Buf[16]
012FF9AC 6C6C6548 Hell
012FF9B0 726F576F oWor
012FF9B4 0000646C ld..
012FF9B8 00855054 TP..
012FF9BC 0000000A .... // _Mysize=0000000A
012FF9C0 0000000F .... // _Myres=0000000F
// 第二种，大于等于16字节的字符串
// _Ptr
0133F844 013F7E88 .~?. &"C:\\Users\\Administrator\\Desktop\\stl_reverse\\test\\Release\\test.exe"
// 12个字节的未使用空间
0133F848 008515B0 °...
0133F84C 00000000 ....
0133F850 00855054 TP..
0133F854 00000040 @... // _Mysize=00000040
0133F858 0000004F O... // _Myres=0000004F
// 第一种，小于16字节的字符串
// _Buf[16]
012FF9AC 6C6C6548 Hell
012FF9B0 726F576F oWor
012FF9B4 0000646C ld..
012FF9B8 00855054 TP..
012FF9BC 0000000A .... // _Mysize=0000000A
012FF9C0 0000000F .... // _Myres=0000000F
// 第二种，大于等于16字节的字符串
// _Ptr
0133F844 013F7E88 .~?. &"C:\\Users\\Administrator\\Desktop\\stl_reverse\\test\\Release\\test.exe"
// 12个字节的未使用空间
0133F848 008515B0 °...
0133F84C 00000000 ....
0133F850 00855054 TP..
0133F854 00000040 @... // _Mysize=00000040
0133F858 0000004F O... // _Myres=0000004F
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
using _Alty_traits = allocator_traits<_Alty>;
using _Scary_val = _Vector_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Ty>,
_Vec_iter_types<_Ty, size_type, difference_type, pointer, const_pointer, _Ty&, const _Ty&>>>;
// 省略若干代码
_Compressed_pair<_Alty, _Scary_val> _Mypair;
};template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
using _Alty_traits = allocator_traits<_Alty>;
using _Scary_val = _Vector_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Ty>,
_Vec_iter_types<_Ty, size_type, difference_type, pointer, const_pointer, _Ty&, const _Ty&>>>;
// 省略若干代码
_Compressed_pair<_Alty, _Scary_val> _Mypair;
};template <class _Val_types>
class _Vector_val : public _Container_base {
public: using pointer = typename _Val_types::pointer;
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
};template <class _Val_types>
class _Vector_val : public _Container_base {
public: using pointer = typename _Val_types::pointer;
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
};int main(int argc, char* argv[]) {
struct Value {
int a;
int b;
};
std::vector<Value> v;
for (int i = 0; i < argc; ++i) {
v.push_back(Value{ i, i + 1 });
}
for (auto& i : v) {
printf("%d, %d\n", i.a, i.b);
}
return 0;
}int main(int argc, char* argv[]) {
struct Value {
int a;
int b;
};
std::vector<Value> v;
for (int i = 0; i < argc; ++i) {
v.push_back(Value{ i, i + 1 });
}
for (auto& i : v) {
printf("%d, %d\n", i.a, i.b);
}
return 0;
}int __cdecl main(int argc, const char **argv, const char **envp)
{ _DWORD *v3; // ecx
DWORD v4; // esi
DWORD v5; // ebx
int v6; // edi
int v7; // eax
_DWORD *v8; // edi
char *v9; // eax
int v11; // [esp+10h] [ebp-24h] BYREF
DWORD v12; // [esp+14h] [ebp-20h]
DWORD v13[3]; // [esp+18h] [ebp-1Ch] BYREF
int v14; // [esp+30h] [ebp-4h]
v3 = 0;
v4 = 0;
v12 = 0;
v5 = 0;
// 1. 初始化vector
v13[0] = 0; // _Myfirst
v13[1] = 0; // _Mylast
v13[2] = 0; // _Myend
v6 = 0;
v14 = 0;
// 2. for (int i = 0; i < argc; ++i)
if ( argc > 0 )
{
do
{
v7 = v6++;
v11 = v7;
v12 = v6;
// v4代表_Mylast
// v5代表_Myend
if ( v4 == v5 ) // 判断一下是否有足够的空间
{
// 没有足够的空间容纳新的Value，调用sub_401300分配新的内存并将Value push到最后
// sub_401300对应vector源码中的_Emplace_reallocate
sub_401300((const void **)v13, (_BYTE *)v4, &v11);
v5 = v13[2];
v4 = v13[1];
}
else
{
// 有足够的空间容纳新的Value，不需要重新分配内存
*(_DWORD *)v4 = v7; // 设置Value::a
*(_DWORD *)(v4 + 4) = v6; // 设置Value::b
v4 += 8;
v13[1] = v4; // _Mylast++
}
}
while ( v6 < argc );
v3 = (_DWORD *)v13[0];
v12 = v13[0];
}
v8 = v3;
// 3. for (auto& i : v)
// 具体遍历过程比较直观，就是对线性数组的遍历，不再给出详细解释
if ( v3 != (_DWORD *)v4 )
{
do
{
// v8代表_Myfirst
sub_401010("%d, %d\n", *v8, v8[1]);
v8 += 2;
}
while ( v8 != (_DWORD *)v4 );
v3 = (_DWORD *)v12;
}
// 4. 释放vector的内存
if ( v3 )
{
v9 = (char *)v3;
if ( ((v5 - (_DWORD)v3) & 0xFFFFFFF8) >= 0x1000 )
{
v3 = (_DWORD *)*(v3 - 1);
if ( (unsigned int)(v9 - (char *)v3 - 4) > 0x1F )
_invalid_parameter_noinfo_noreturn();
}
sub_40159B(v3);
}
return 0;
}int __cdecl main(int argc, const char **argv, const char **envp)
{ _DWORD *v3; // ecx
DWORD v4; // esi
DWORD v5; // ebx
int v6; // edi
int v7; // eax
_DWORD *v8; // edi
char *v9; // eax
int v11; // [esp+10h] [ebp-24h] BYREF
DWORD v12; // [esp+14h] [ebp-20h]
DWORD v13[3]; // [esp+18h] [ebp-1Ch] BYREF
int v14; // [esp+30h] [ebp-4h]
v3 = 0;
v4 = 0;
v12 = 0;
v5 = 0;
// 1. 初始化vector
v13[0] = 0; // _Myfirst
v13[1] = 0; // _Mylast
v13[2] = 0; // _Myend
v6 = 0;
v14 = 0;
// 2. for (int i = 0; i < argc; ++i)
if ( argc > 0 )
{
do
{
v7 = v6++;
v11 = v7;
v12 = v6;
// v4代表_Mylast
// v5代表_Myend
if ( v4 == v5 ) // 判断一下是否有足够的空间
{
// 没有足够的空间容纳新的Value，调用sub_401300分配新的内存并将Value push到最后
// sub_401300对应vector源码中的_Emplace_reallocate
sub_401300((const void **)v13, (_BYTE *)v4, &v11);
v5 = v13[2];
v4 = v13[1];
}
else
{
// 有足够的空间容纳新的Value，不需要重新分配内存
*(_DWORD *)v4 = v7; // 设置Value::a
*(_DWORD *)(v4 + 4) = v6; // 设置Value::b
v4 += 8;
v13[1] = v4; // _Mylast++
}
}
while ( v6 < argc );
v3 = (_DWORD *)v13[0];
v12 = v13[0];
}
v8 = v3;
// 3. for (auto& i : v)
// 具体遍历过程比较直观，就是对线性数组的遍历，不再给出详细解释
if ( v3 != (_DWORD *)v4 )
{
do
{
// v8代表_Myfirst
sub_401010("%d, %d\n", *v8, v8[1]);
v8 += 2;
}
while ( v8 != (_DWORD *)v4 );
v3 = (_DWORD *)v12;
}
// 4. 释放vector的内存
if ( v3 )
{
v9 = (char *)v3;
if ( ((v5 - (_DWORD)v3) & 0xFFFFFFF8) >= 0x1000 )
{
v3 = (_DWORD *)*(v3 - 1);
if ( (unsigned int)(v9 - (char *)v3 - 4) > 0x1F )
_invalid_parameter_noinfo_noreturn();
}
sub_40159B(v3);
}
return 0;
}_DWORD *__thiscall sub_401300(const void **this, _BYTE *a2, _DWORD *a3)
{ // ...
// 通过2^32 / 0x1FFFFFFF计算得出8即是该vector的元素大小
if ( v4 == 0x1FFFFFFF )
sub_401460();
// ...
}void __noreturn sub_401460(){ sub_40153A("vector too long");
}_DWORD *__thiscall sub_401300(const void **this, _BYTE *a2, _DWORD *a3)
{ // ...
// 通过2^32 / 0x1FFFFFFF计算得出8即是该vector的元素大小
if ( v4 == 0x1FFFFFFF )
sub_401460();
// ...
}void __noreturn sub_401460(){ sub_40153A("vector too long");
}// vector内存布局
005EFB2C 00878470 p... // _Myfirst
005EFB30 00878478 x... // _Mylast
005EFB34 00878478 x... // _Myend
// vector指向的数组内存
00878470 00000000 ....
00878474 00000001 ....
// vector内存布局
005EFB2C 00878470 p... // _Myfirst
005EFB30 00878478 x... // _Mylast
005EFB34 00878478 x... // _Myend
// vector指向的数组内存
00878470 00000000 ....
00878474 00000001 ....
size_type _Calculate_growth(const size_type _Newsize) const { // given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max; // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize; // geometric growth would be insufficient
}
return _Geometric; // geometric growth is sufficient
}size_type _Calculate_growth(const size_type _Newsize) const { // given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max; // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize; // geometric growth would be insufficient
}
return _Geometric; // geometric growth is sufficient
}template <class _Ty, class _Alloc = allocator<_Ty>>
class list { // bidirectional linked list
private: using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
using _Alty_traits = allocator_traits<_Alty>;
using _Node = _List_node<_Ty, typename allocator_traits<_Alloc>::void_pointer>;
using _Alnode = _Rebind_alloc_t<_Alloc, _Node>;
using _Alnode_traits = allocator_traits<_Alnode>;
using _Nodeptr = typename _Alnode_traits::pointer;
using _Val_types = conditional_t<_Is_simple_alloc_v<_Alnode>, _List_simple_types<_Ty>,
_List_iter_types<_Ty, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Ty&, const _Ty&, _Nodeptr>>;
using _Scary_val = _List_val<_Val_types>;
// 省略若干代码
private: _Compressed_pair<_Alnode, _Scary_val> _Mypair;
};template <class _Value_type, class _Voidptr>
struct _List_node { // list node
using value_type = _Value_type;
using _Nodeptr = _Rebind_pointer_t<_Voidptr, _List_node>;
_Nodeptr _Next; // successor node, or first element if head
_Nodeptr _Prev; // predecessor node, or last element if head
_Value_type _Myval; // the stored value, unused if head
// 省略若干代码
};template <class _Val_types>
class _List_val : public _Container_base {
public: using _Nodeptr = typename _Val_types::_Nodeptr;
using size_type = typename _Val_types::size_type;
// 省略若干代码
private: _Nodeptr _Myhead; // pointer to head node
size_type _Mysize; // number of elements
};template <class _Ty, class _Alloc = allocator<_Ty>>
class list { // bidirectional linked list
private: using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
using _Alty_traits = allocator_traits<_Alty>;
using _Node = _List_node<_Ty, typename allocator_traits<_Alloc>::void_pointer>;
using _Alnode = _Rebind_alloc_t<_Alloc, _Node>;
using _Alnode_traits = allocator_traits<_Alnode>;
using _Nodeptr = typename _Alnode_traits::pointer;
using _Val_types = conditional_t<_Is_simple_alloc_v<_Alnode>, _List_simple_types<_Ty>,
_List_iter_types<_Ty, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Ty&, const _Ty&, _Nodeptr>>;
using _Scary_val = _List_val<_Val_types>;
// 省略若干代码
private: _Compressed_pair<_Alnode, _Scary_val> _Mypair;
};template <class _Value_type, class _Voidptr>
struct _List_node { // list node
using value_type = _Value_type;
using _Nodeptr = _Rebind_pointer_t<_Voidptr, _List_node>;
_Nodeptr _Next; // successor node, or first element if head
_Nodeptr _Prev; // predecessor node, or last element if head
_Value_type _Myval; // the stored value, unused if head
// 省略若干代码
};template <class _Val_types>
class _List_val : public _Container_base {
public: using _Nodeptr = typename _Val_types::_Nodeptr;
using size_type = typename _Val_types::size_type;
// 省略若干代码
private: _Nodeptr _Myhead; // pointer to head node
size_type _Mysize; // number of elements
};int main(int argc, char* argv[]) {
struct Value {
int a;
int b;
};
std::list<Value> v;
for (int i = 0; i < argc; ++i) {
v.push_back(Value{ i, i + 1 });
}
for (auto& i : v) {
printf("%d, %d\n", i.a, i.b);
}
return 0;
}int main(int argc, char* argv[]) {
struct Value {
int a;
int b;
};
std::list<Value> v;
for (int i = 0; i < argc; ++i) {
v.push_back(Value{ i, i + 1 });
}
for (auto& i : v) {
printf("%d, %d\n", i.a, i.b);
}
return 0;
}int __cdecl main(int argc, const char **argv, const char **envp)
{ _DWORD *v3; // edi
int i; // esi
int v5; // ebx
_DWORD *v6; // eax
_DWORD *v7; // ecx
_DWORD *v8; // esi
_DWORD *v9; // eax
_DWORD *v10; // esi
DWORD Block[2]; // [esp+18h] [ebp-18h]
// 1. 初始化list
// 设置list的_Mysize为0
Block[1] = 0;
// 申请一个_List_node作为头节点
v3 = operator new(0x10u);
// 双向链表初始化
*v3 = v3; // v3->_Next = head;
v3[1] = v3; // v3->_Prev = head;
// 将初始化后的node赋值给list的_Myhead
Block[0] = (DWORD)v3;
// 2. for (int i = 0; i < argc; ++i)
for ( i = 0; i < argc; v3 = (_DWORD *)Block[0] )
{
// 这里list::push_back的代码全部被inline进来了
v5 = i++;
if ( Block[1] == 0xFFFFFFF )
sub_4013D2("list too long");
v6 = operator new(0x10u); // 申请一个新的_List_node
// 设置Value
v6[2] = v5;
v6[3] = i;
++Block[1]; // 递增list的_Mysize
// 串链表操作
v7 = (_DWORD *)v3[1]; // v7 = v3->Prev; // v7是临时变量
*v6 = v3; // v6->_Next = v3; // v6是新节点
v6[1] = v7; // v6->_Prev = v7; // v3是head节点
v3[1] = v6; // v3->_Prev = v6;
*v7 = v6; // v7->_Next = v6;
}
// 3. for (auto& i : v)
v8 = (_DWORD *)*v3;
if ( (_DWORD *)*v3 != v3 ) // 先判断一下链表是否是空的
{
// 循环打印链表的每一个节点
do
{
sub_401010("%d, %d\n", v8[2], v8[3]);
v8 = (_DWORD *)*v8; // v8 = v8->_Next;
}
while ( v8 != v3 );
v3 = (_DWORD *)Block[0];
}
// 4. 释放list的内存
// 对应list::_Tidy的代码
*(_DWORD *)v3[1] = 0; // 将最后一个节点的_Next置为NULL，循环时判断到NULL了就结束循环
v9 = (_DWORD *)*v3;
if ( *v3 )
{
// 循环释放链表中的每一个节点
do
{
v10 = (_DWORD *)*v9;
sub_401433(v9); // jmp to free
v9 = v10;
}
while ( v10 );
}
// 释放链表的头节点
sub_401433((void *)Block[0]); // jmp to free
return 0;
}int __cdecl main(int argc, const char **argv, const char **envp)
{ _DWORD *v3; // edi
int i; // esi
int v5; // ebx
_DWORD *v6; // eax
_DWORD *v7; // ecx
_DWORD *v8; // esi
_DWORD *v9; // eax
_DWORD *v10; // esi
DWORD Block[2]; // [esp+18h] [ebp-18h]
// 1. 初始化list
// 设置list的_Mysize为0
Block[1] = 0;
// 申请一个_List_node作为头节点
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
