什么是栈回溯

发布网友

共2个回答

热心网友

一、栈回溯的概念：
栈回溯就是回溯法，是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

热心网友

栈回溯原理浅析创建时间：2010-06-24 文章类别：内核研究文章大小：7104 Bytes 文档名称：Windows NT Stack Trace 文档维护：welfear 创建时间：2009年6月7日更新内容：对StackWalk的分析(2009.6.17) 更新内容：对x栈的分析(2009.6.19) 在系统软件开发中有时会有得到函数调用者的信息的需要，为此WindowsNT专门提供了调用 RtlGetCallerAddress为内核开发者使用，但它并没有公开所以也就不能为驱动开发者使用。然而在兼容过程中又无法避免使用它，所以我们只好探究其原理。 RtlGetCallerAddress可以由两种方法实现，其原型如下： VOID RtlGetCallersAddress( OUT PVOID *CallersAddress, //address to save the first caller. OUT PVOID *CallersCaller //address to save the second caller. ) 第一种方法，它的主要实现是在RtlCaptureStackBackTrace中完成的。而在这个 RtlCaptureStackBaceTrace在各个版本的WindowsNT中都有着重要的作用。这是一个比较通用的获得栈信息的函数。原型如下： USHORT RtlCaptureStackBackTrace( IN ULONG FramesToSkip, IN ULONG FramsToCapture, OUT PVOID *BackTrace, OUT PULONG BackTraceHash); 栈信息的获得是通过另外一个导出函数RtlWalkFrameChain实现的。原型如下： ULONG RtlWalkFrameChain(OUT PVOID *Callers, IN ULONG Count, IN ULONG Flags); 在X86平台上，它的工作原理很简单，就是通过EBP寄存器一步一步得到每个栈的信息。 _asm mov FramePointer, EBP; 在得到EBP内容之后，我们需要计算当前内核栈的范围，这是因为我们在计算数据时不能跑出一个范围，否则会有蓝屏的危险。栈的开始地址就设置为EBP指针指向的地址。而终止范围是比较难确定的。这个地址可以使用KeGetCurrentThread()->StackBase的值，但这并不保险，在DPC环境中，如果栈内存很换出，则还是会蓝屏。有一点是可以肯定的，当前的EBP栈是没有被换出的，如果可能就在当前栈所在页的上一页末作为栈的终止地址。我们知道在函数开始处都有： push ebp mov ebp, esp 作为函数的最开始两句代码。这样根据EBP就可以找到所有的函数地址。 NextFramePointer = *(PULONG_PTR)(FramePointer); ReturnAddress = *(PULONG_PTR)(FramePointer + sizeof(ULONG_PTR)); 这里有两点需要注意： 1、ReturnAddress应该在StackStart和StackEnd之间。 2、ReturnAddress不能小于K（这是由WindowsNT的设计决定的）。在另一种实现中，RtlGetCallerAddress是个精简过的函数，因为RtlCaptureStackBackTrace 太危险了也太复杂了。下面我们分析这个版本的RtlGetCallerAddress是如何工作的，这里面有几处偏移应该先交代一下： 1、fs:124h是KTHREAD的首地址，实际上这句代码就是KeGetCurrentThread()产生的。 2、eax + 18h是KTHREAD的InitialStack的偏移。 3、eax + 1Ch是KTHREAD的StackLimit的偏移。为了方便阅读，代码将会被分段显示如下： .text:0044BAA4 000 push ebp .text:0044BAA5 004 mov ebp, esp .text:0044BAA7 004 push ebx .text:0044BAA8 008 push esi .text:0044BAA9 00C push edi .text:0044BAAA 010 mov eax, large fs:124h .text:0044BAB0 010 push dword ptr [eax+18h] .text:0044BAB3 014 push esp .text:0044BAB4 018 push offset loc_44BB2F .text:0044BAB9 01C push large dword ptr fs:0 .text:0044BAC0 020 mov large fs:0, esp 开头几句是为了当前线程内核栈的相关变量值，这里的loc_44BB2F是异常的处理函数。显然这里用到了VC的异常处理机制。具体细节可以毛老师的项目*。 .text:0044BAC7 020 xor esi, esi ; Logical Exclusive OR .text:0044BAC9 020 xor edi, edi ; Logical Exclusive OR .text:0044BACB 020 mov edx, ebp .text:0044BACD 020 mov edx, [edx] .text:0044BACF 020 cmp edx, ebp ; Compare Two Operands .text:0044BAD1 020 jbe short loc_44BAEE ; Jump if Below or Equal (CF=1 | ZF=1) 这是比较当前栈和上一个栈的地址，当然如果没有问题的情况下自然是当前的地址低。否则就要跳到 loc_44BB0D中退出了。 .text:0044BAD3 020 cmp edx, [ebp+var_10] ; Compare Two Operands .text:0044BAD6 020 jnb short loc_44BB0D ; Jump if Not Below (CF=0) .text:0044BAD8 020 cmp edx, [eax+1Ch] ; Compare Two Operands .text:0044BADB 020 jb short loc_44BB0D ; Jump if Below (CF=1) edx一直保存着调用者的栈指针，它应该是在InitialStack和StackLimit之间。如果不是都要跳入loc_44BB0D 检测Dpc环境下的栈情况。 .text:0044BADD loc_44BADD: ; CODE XREF: RtlGetCallersAddress(x,x)+87j .text:0044BADD 020 mov esi, [edx+4] .text:0044BAE0 020 mov edx, [edx] .text:0044BAE2 020 cmp edx, ebp ; Compare Two Operands .text:0044BAE4 020 jbe short loc_44BAEE ; Jump if Below or Equal (CF=1 | ZF=1) .text:0044BAE9 020 jnb short loc_44BAEE ; Jump if Not Below (CF=0) .text:0044BAEB 020 mov edi, [edx+4] esi保存了调用者函数的地址。edx由于mov edx, [edx]而继续向上找了一个栈，它应该在InitialStack和当前栈指针之间。最后edi保存了调用者的调用者返回地址。这样两个返回参数都已经得到了。 .text:0044BAEE loc_44BAEE: ; CODE XREF: RtlGetCallersAddress(x,x)+2Dj .text:0044BAEE ; RtlGetCallersAddress(x,x)+40j ... .text:0044BAEE 020 mov ecx, [ebp+CallersAddress] .text:0044BAF1 020 jecxz short loc_44BAF5 ; Jump if ECX is 0 .text:0044BAF3 020 mov [ecx], esi .text:0044BAF5 .text:0044BAF5 loc_44BAF5: ; CODE XREF: RtlGetCallersAddress(x,x)+4Dj .text:0044BAF5 020 mov ecx, [ebp+CallersCaller] .text:0044BAF8 020 jecxz short loc_44BAFC ; Jump if ECX is 0 .text:0044BAFA 020 mov [ecx], edi .text:0044BAFC .text:0044BAFC loc_44BAFC: ; CODE XREF: RtlGetCallersAddress(x,x)+54j .text:0044BAFC 020 pop large dword ptr fs:0 .text:0044BB03 01C pop edi .text:0044BB04 018 pop edi .text:0044BB05 014 pop edi .text:0044BB06 010 pop edi .text:0044BB07 00C pop esi .text:0044BB08 008 pop ebx .text:0044BB09 004 pop ebp .text:0044BB0A 000 retn 8 ; Return Near from Procere 这些都是函数的扫尾工作。下面的工作是为了处理异常的，因为这个函数实在是太危险了。 .text:0044BB0D .text:0044BB0D loc_44BB0D: ; CODE XREF: RtlGetCallersAddress(x,x)+32j .text:0044BB0D ; RtlGetCallersAddress(x,x)+37j .text:0044BB0D 020 cmp large dword ptr fs:994h, 0 ; Compare Two Operands .text:0044BB15 020 mov eax, large fs:988h .text:0044BB1B 020 jz short loc_44BAEE ; Jump if Zero (ZF=1) .text:0044BB1D 020 cmp edx, eax ; Compare Two Operands .text:0044BB1F 020 mov [ebp+var_10], eax .text:0044BB22 020 jnb short loc_44BAEE ; Jump if Not Below (CF=0) .text:0044BB24 020 sub eax, 3000h ; Integer Subtraction .text:0044BB29 020 cmp edx, eax ; Compare Two Operands .text:0044BB2B 020 ja short loc_44BADD ; Jump if Above (CF=0 & ZF=0) .text:0044BB2D 020 jmp short loc_44BAEE ; Jump 994是DpcRoutineActive的偏移地址。如果没有当前Dpc函数运行，那一定是出问题了跳到loc_44BAEE准备返回。 988是DpcStack的偏移地址。如果当前是Dpc Stack，那么edx的值应该在DpcStack和DpcStackLimit范围之内。 DpcStackLimit的值是通过DpcStack减掉内核栈大小得到的。普通的内核栈都是3个PAGE_SIZE，每个PAGE_SIZE 在x86中是4KB。所以要减掉3000h那么大。最后有两条路可以走，一是跳到loc_44BADD继续计算，二是跳到loc_44BAEE 准备返回。 .text:0044BB2F .text:0044BB2F loc_44BB2F: ; DATA XREF: RtlGetCallersAddress(x,x)+10o .text:0044BB2F 020 mov eax, [esp+1Ch+var_10] .text:0044BB33 020 mov edi, [eax+9Ch] .text:0044BB39 020 mov esp, [esp+1Ch+var_14] .text:0044BB3D 020 jmp short loc_44BAEE ; Jump 简单处理了一下异常列表。实际上没什么用。在应用程序中，有时需要通过观察栈信息进行调试分析。例如下面的代码就是从VC2003中的atlutil.h文件中摘录的：见评论。针对这段代码有几点需要说明： 1、应用层中一般使用GetThreadContext或通过设置未捕获异常来得到某一时刻的CPU各个寄存器的状态。 2、在出现未捕获异常时，异常过滤函数得到的是出问题的函数出错时的状态，这样可以很好的获得出错信息。 3、GetThreadContext的使用在MSDN中有说明，它不能获得当前线程的上下文信息。使用这个函数需要挂起当前线程。在VC2005中附带的代码来看，它先是另外创建了一个线程，然后在本线程WaitForSingleObject等待新创建的线程退出，然后再继续运行。 4、无论是VC20003还是VC2005，它们的代码都有问题。VC2005中的代码使用下面的方式： while (WaitForSingleObject(hThread, 0) != WAIT_TIMEOUT); 看注释的意思是CE对WaitForSingleObject支持不好而这么做的。而VC2003的代码问题就比较多了，GetThreadContext应该是获得挂起线程的上下文，这在VC2005的注释里也提到了。 5、StackWalk的作用是前面分析Stack Trace。使用它的好处是代码有可移植性。使用之前需要用GetThreadContext的内容初始化。 6、在MSDN中有如下一段对GetThreadContext的描述： You cannot get a valid context for a running thread. Use the SuspendThread function to suspend the thread before calling GetThreadContext. If you call GetThreadContext for the current thread, the function returns successfully; however, the context returned is not valid. 但我直接使用GetCurrentThread来调用GetThreadContext得到的结果是正确的，而且VC自带的代码也这么用，真让人不解。可后来修改的代码和注释表明似乎，这是个问题。现在我的理解是要得到“当前”的CPU状态要先SuspendThread，而想得到进入内核前的CPU状态则可以直接使用GetThreadContext获得，MSDN中的无效是指得到并不是调用者“当时”的CPU状态。 x只支持一种调用方式：fastcall。x调用的前四个参数使用RCX、RDX、R8、R9，然后才使用栈传递。调用者负责维护栈平衡。在x中,VC不支持asm关键字，所以获得EBP要困难一些。但我记得在Linux中有一个获得EBP的巧妙方法。 VOID GetCallerAddress(ULONG_PTR arg) { ULONG_PTR EBP = (&arg)[-1]; } 在应用层中使用Stack Trace技术就不用那么小心了，直接使用循环，然后捕获异常就可以了。

热心网友

全部栏目

什么是栈回溯