随着64位操作系统的普及，都开始大力进军x64，X64下的调试机制也发生了改变，与x86相比，添加了许多自己的新特性，之前学习了Windows x64的调试机制，这里本着“拿来主义”的原则与大家分享。
本文属于译文，英文原文链接：http://www.codemachine.com/article_x64deepdive.html
翻译原文地址：深入Windows X64 调试
在正式开始这篇译文之前，译者先定义下面两个关于栈帧的翻译：
- frame pointer：栈帧寄存器、栈帧指针，在X86平台上，是EBP所指的位置
- stack pointer：栈顶寄存器、栈顶指针，在X86平台上，是ESP所指的位置
这个教程讨论一些在 X64 CPU 上代码执行的要点，如：编译器优化、异常处理、参数传递和参数恢复，并且介绍这几个topic之间的关联。我们会涉及与上述topic相关的一些重要的调试命令，并且提供必要的背景知识去理解这些命令的输出。同时，也会重点介绍X64平台的调试与X86平台的不同，以及这些不同对调试的影响。最后，我们会活学活用，利用上面介绍的知识来展示如何将这些知识应用于X64平台的基于寄存器存储的参数恢复上，当然，这也是X64平台上调试的难点。
0x00 编译器优化
这一节主要讨论影响X64 code生成的编译器优化，首先从X64寄存器开始，然后，介绍优化细节，如：函数内联处理（function in-lining）,消除尾部调用（tail call elimination）, 栈帧指针优化（frame pointer optimization）和基于栈顶指针的局部变量访问（stack pointer based local variable access）。
- 寄存器的变化
X64平台上的所有寄存器，除了段寄存器和EFlags寄存器，都是64位的，这就意味着在x64平台上所有内存的操作都是按64位宽度进行的。同样，X64指令有能力一次性处理64位的地址和数据。增加了8个新的寄存器，如： r8~r15，与其他的使用字母命名的寄存器不同，这些寄存器都是使用数字命名。下面的调试命令输出了 X64 平台上寄存器的信息：
rax=fffffa60005f1b70 rbx=fffffa60017161b0 rcx=000000000000007f rdx=0000000000000008 rsi=fffffa60017161d0 rdi=0000000000000000 rip=fffff80001ab7350 rsp=fffffa60005f1a68 rbp=fffffa60005f1c30 r8=0000000080050033 r9=00000000000006f8 r10=fffff80001b1876c r11=0000000000000000 r12=000000000000007b r13=0000000000000002 r14=0000000000000006 r15=0000000000000004 iopl=0 nv up ei ng nz na pe nc cs=0010 ss=0018 ds=002b es=002b fs=0053 gs=002b efl=00000282 nt!KeBugCheckEx:
fffff800`01ab7350 48894c2408 mov qword ptr [rsp+8],rcx ss:0018:fffffa60`005f1a70=000000000000007f
相比较X86平台，一些寄存器的用法已经发生变化，这些变化可以按如下分组：
- 不可变寄存器是那些在函数调用过程中，值被保存起来的寄存器。X64平台拥有一个扩展的不可变寄存器集合，在这个集合中，以前x86平台下原有的不可变寄存器也包含在内，新增的寄存器是从R12到R15，这些寄存器对于函数参数的恢复很重要。
- Fastcall寄存器用于传递函数参数。Fastcall是X64平台上默认的调用约定，前4个参数通过RCX, RDX, R8, R9传递。
- RBP不再用作栈帧寄存器。现在RBP和RBX,RCX一样都是通用寄存器，调试前不再使用RBP来回溯调用栈。
- 在X86 CPU中，FS段寄存器用于指向线程环境块（TEB）和处理器控制区（Processor Control Region, KPCR），但是，在X64上，GS段寄存器在用户态是指向TEB，在内核态是指向KPCR。然而，当运行WOW64程序中，FS 寄存器仍然指向32位的TEB。
在X64平台上，trap frame的数据结构(nt!_KTRAP_FRAME)中不包含不可变寄存器的合法内容。如果X64函数会使用到这些不可变寄存器，那么，指令的序言部分会保存不可变寄存器的值。这样，调试器能够一直从栈中取到这些不可变寄存器原先的值，而不是从trap frame中去取。在X64内核模式调试状态下，`.trap`命令的输出会打印一个NOTE，用于告诉用户所有从trap frame中取出的寄存器信息可能不准确，如下所示：
Child-SP RetAddr : Args to Child .
.
.
nt!KiDoubleFaultAbort+0xb8 (TrapFrame @ fffffa60`005f1bb0) .
.
.
1: kd> .trap fffffa60`005f1bb0
NOTE: The trap frame does not contain all registers.
Some register values may be zeroed or incorrect
- 函数内联处理（Function in-lining）
如果满足一定的规则以后，X64编译器会执行内联函数的扩展，这样会将所有内联函数的调用部分用函数体来替换。内联函数的优点是避免函数调用过程中的栈帧创建以及函数退出时的栈平衡，缺点是由于指令的重复对导致可执行程序的大小增大不少，同时，也会导致cache未命中和page fault的增加。内联函数同样也会影响调试，因为当用户尝试在内联函数上设置断点时，调试器是不能找到对应的符号的。源码级别的内联可以通过编译器的/Ob flag 进行控制，并且可以通过__declspec(noinline)禁止一个函数的内联过程。图1显示函数2和函数3被内联到函数1的过程。
Figure 1 : Function In-lining
- 消除尾部调用（Tail Call Elimination）
X64编译器可以使用jump指令替换函数体内最后的call指令，通过这种方式来优化函数的调用过程。这种方法可以避免被调函数的栈帧创建，调用函数与被调函数共享相同的栈帧，并且，被调函数可以直接返回到自己爷爷级别的调用函数，这种优化在调用函数与被调函数拥有相同参数的情况下格外有用，因为如果相应的参数已经被放在指定的寄存器中，并且没有改变，那么，它们就不用被重新加载。图2显示了TCE，我们在函数1的最后调用函数4：
Figure 2 : Tail Call Elimination
- 栈帧指针省略（Frame Pointer Omission, FPO）
在X86平台下，EBP寄存器用于访问栈上的参数与局部变量，而在X64平台下，RBP寄存器不再使用充当同样的作用。取而代之的是，在X64环境下，使用RSP作为栈帧寄存器和栈顶寄存器，具体是如何使用的，我们会在后续的章节中做详细的叙述。（译者注：请区分X86中的FPO与X64中的FPO，有很多相似的地方，也有不同之处。关于 X86上的FPO，请参考《软件调试》中关于栈的描述）所以，在X64环境下，RBP寄存器已经不再担当栈帧寄存器，而是作为一般的通用寄存器使用。但是，有一个例外情况，当使用alloca()动态地在栈上分配空间的时候，这时，会和X86环境一样，使用RBP作为栈帧寄存器。 下面的汇编代码片段展示了X86环境下的KERNELBASE!Sleep函数，可以看到EBP寄存器被用作栈帧寄存器。当调用SleepEx()函数的时候，参数被压到栈上，然后，使用call指令调用SleepEx()。
75ed3511 8bff mov edi,edi
75ed3513 55 push ebp
75ed3514 8bec mov ebp,esp
75ed3516 6a00 push 0
75ed3518 ff7508 push dword ptr [ebp+8]
75ed351b e8cbf6ffff call KERNELBASE!SleepEx (75ed2beb)
75ed3520 5d pop ebp 75ed3521 c20400 ret 4.
下面的代码片段展示的是X64环境下相同的函数，与X86的code比起来有明显的不同。X64版本的看起来非常紧凑，主要是由于不需要保存、恢复RBP寄存器。
一、题目：在O(1)时间删除链表结点
题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
原文采用的是C/C++，这里采用C#，节点定义如下：
{
// 数据域
public T Item { get; set; }
// 指针域
public Node<T> Next { get; set; }
public Node()
{
}
public Node(T item)
{
this.Item = item;
}
}
要实现的DeleteNode方法定义如下：
{
}
二、解题思路
2.1 常规思路
在单向链表中删除一个结点，最常规的做法无疑是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。这种思路由于需要顺序查找，时间复杂度自然就是O(n)。
2.2 正确思路
是不是一定需要得到被删除的结点的前一个结点呢？答案是否定的。
我们可以很方便地得到要删除的结点的一下结点。因此，我们可以把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，就相当于把当前需要删除的结点删除了。
但是，还有两个特殊情况需要进行考虑：
（1）如果要删除的结点位于链表的尾部，那么它就没有下一个结点：
此时我们仍然从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作，这仍然属于O(n)时间的操作。
（2）如果链表中只有一个结点，而我们又要删除链表的头结点（也是尾结点）：
此时我们在删除结点之后，还需要把链表的头结点设置为NULL。
最后，通过综合最坏情况（尾节点需要顺序查找，1次）和最好情况（n-1次），因此平均时间复杂度为：
需要注意的是：受到O(1)时间的限制，我们不得不把确保结点在链表中的责任推给了函数DeleteNode的调用者。
三、解决问题
3.1 代码实现
{
if (headNode == null || deleteNode == null)
{
return;
}
if (deleteNode.Next != null) // 链表有多个节点，要删除的不是尾节点:O(1)时间
{
Node<int> tempNode = deleteNode.Next;
deleteNode.Item = tempNode.Item;
deleteNode.Next = tempNode.Next;
tempNode = null;
}
else if (headNode == deleteNode) // 链表只有一个结点，删除头结点（也是尾结点）:O(1)时间
{
deleteNode = null;
headNode = null;
}
else // 链表有多个节点，要删除的是尾节点:O(n)时间
{
Node<int> tempNode = headNode;
while(tempNode.Next != deleteNode)
{
tempNode = tempNode.Next;
}
tempNode.Next = null;
deleteNode = null;
}
}
3.2 单元测试
（1）封装返回结果
该方法作为单元测试的对比方法，主要用来对比实际值与期望值是否一致：
{
if (headNode == null)
{
return string.Empty;
}
StringBuilder sbNodes = new StringBuilder();
while(headNode != null)
{
sbNodes.Append(headNode.Item);
headNode = headNode.Next;
}
return sbNodes.ToString();
}
（2）测试用例
[TestMethod]
public void DeleteNodeTest1()
{
Node<int> head1 = new Node<int>(1);
Node<int> head2 = new Node<int>(2);
Node<int> head3 = new Node<int>(3);
Node<int> head4 = new Node<int>(4);
Node<int> head5 = new Node<int>(5);
head1.Next = head2;
head2.Next = head3;
head3.Next = head
没有评论:
发表评论