栈回溯

2024-09-04 07:48
文章标签 回溯

本文主要是介绍栈回溯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先必须明确一点也是非常重要的一点,栈是向下生长的,所谓向下生长是指从内存高地址->低地址的路径延伸,那么就很明显了,栈有栈底和栈顶,那么栈顶的地址要比栈底低。对x86体系的CPU而言,其中:

---> 寄存器ebp(base pointer )可称为“帧指针”或“基址指针”,其实语意是相同的。

---> 寄存器esp(stack pointer)可称为“ 栈指针”。

要知道的是:

--->ebp 在未受改变之前始终指向栈帧的开始,也就是栈底,所以ebp的用途是在堆栈中寻址用的。

—>esp是会随着数据的入栈和出栈移动的,也就是说,esp始终指向栈顶。

寄存器ebp指向当前的栈帧的底部(高地址),寄存器esp指向当前的栈帧的顶部(地地址)

这是来自apue里一张经典的c程序内存分布图:

 

基于多核异构处理器B4860平台的实例,对栈回溯功能做如下描述,仅供参考。假设函数A调用函数B,我们称A函数为"调用者",B函数为“被调用者”则函数调用过程:

(1)先将调用者(A)的堆栈的基址(ebp)入栈,以保存之前任务的信息;

(2)然后将调用者(A)的栈顶指针(esp)的值赋给ebp,作为新的基址(即被调用者B的栈底);

(3)然后在这个基址(被调用者B的栈底)上开辟(一般用sub指令)相应的空间用作被调用者B的栈空间;

(4)函数B返回后,从当前栈帧的ebp即恢复为调用者A的栈顶(esp),使栈顶恢复函数B被调用前的位置;然后调用者A再从恢复后的栈顶可弹出之前的ebp值(可以这么做是因为这个值在函数调用前一步被压入堆栈)。这样,ebp和esp就都恢复了调用函数B前的位置,也就是栈恢复函数B调用前的状态。

以DSP侧异常为例说明,如下所示:

1.Task创建时,会为每个Task分配好Task的栈,并指定当前Task栈的size。

其中,栈是向下生长(高地址 -> 低地址),因此文中所描述的“top_of_stack”实则为栈的底(EBP)。

2.DSP出现异常时,会记录当前函数的上下文信息,如PC,SP,os_context_info,top_of_stack,etc.可结合这些关键信息及Map文件进行栈回溯,找到出现异常函数的上下文。

3.PC指针,通常是用来指向当前运行指令的下一条指令的指针。计算机取指令也就是根据PC指针所指向的那条指令来进行取指的,接着就是译码等操作。异常时的PC,归属于当前栈帧,要想获取到异常函数的多级调用关系,就需要知道当前栈帧的栈顶(根据函数的入栈会动态变化)和栈底。

4.得到完全任务栈的栈帧,以及当前错误的PC,以及Map文件,就可以获取到函数调用的上下文,描述如下:

(1)错误的PC不一定指向当前出现异常时函数,但一定会指向出现异常函数的栈帧内。PC缺省是uint32_t类型,这里我们对PC截断处理,PC的高16bit+offset就会指向出现异常时的函数,offset表示当函数压栈时的偏移地址。

(2)函数的压栈操作是从高地址到低地址方向的一个生长,换句话说,函数的调用关系是从高地址往低地址方向调入的一个过程,因此,为了找到出现异常时函数调用的上下文,就要从低地址往高地址方向反推。

注:在一体机SC3900中,函数的压栈是从低地址到高地址。其中,嵌汇编操作描述如下:

以CPU侧异常为例说明,结合coredump文件即核心转储,进行GDB调试即可,本文不过多描述。

这篇关于栈回溯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135423

相关文章

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

风控系统之指标回溯,历史数据重跑

个人博客:无奈何杨(wnhyang) 个人语雀:wnhyang 共享语雀:在线知识共享 Github:wnhyang - Overview 回顾 默认你已经看过之前那篇风控系统指标计算/特征提取分析与实现01,Redis、Zset、模版方法。 其中已经介绍了如何利用redis的zset结构完成指标计算,为了方便这篇文章的介绍,还是在正式开始本篇之前回顾一下。 时间窗口 zset

165-Stamps【回溯】

回溯 给h和k的意思是在k种邮票中选h个邮票 基本的连续邮资问题 15226160 165 Stamps Accepted C++ 0.062 2015-03-27 07:21:37 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2

回溯——8.递增子序列

力扣题目链接 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。 示例: 输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中

【代码随想录|回溯part04】

代码随想录|回溯part04 1、46.全排列2、47.全排列 II3.问题 总结 python 1、46.全排列 46.全排列 class Solution:def permute(self, nums):result = []self.backtracking

代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

今日内容 回溯的理论基础leetcode. 77 组合leetcode. 216 组合总和Ⅲleetcode. 17 电话号码的字母组合 回溯理论基础 回溯法也叫回溯搜索法,它是一种搜索的方式,而且只要有递归就会有回溯,回溯就是递归的副产品。 回溯说到底并不是什么非常高深的搜索方式,本质上仍然是穷举,穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点,但改变不了回溯本质就是穷举

算法打卡 Day28(回溯算法)-组合总数 + 组合总数 Ⅱ+ 电话号码的字母组合

文章目录 Leetcode 17-电话号码的字母组合题目描述解题思路 Leetcode 39-组合总数题目描述解题思路 Leetcode 216-组合总数 Ⅲ题目描述解题思路 Leetcode 17-电话号码的字母组合 题目描述 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/descrip

【递归、回溯专题(三)】记忆化搜索题集

文章目录 1. 斐波那契数2. 不同路径2. 不同路径3. 最长递增子序列4. 猜数字大小II 1. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给定 n

@金华银行,“双录+可回溯”齐护航,让金融服务更安心

菊风中标金华银行临柜双录及可视化回溯系统建设项目 三大核心应用 临柜双录体验:为理财、基金、保险、对公开户、个人信贷面签等业务场景设计,支持销售经理通过PC或Pad进行业务操作 远程双录服务:预约制流程,客户可远程进行理财、基金等业务的录音录像,提高效率 可视化回溯系统:多渠道接入,操作轨迹采集,实现销售交易行为全过程的可视化 技术亮点 音视频能力:视频呼入、多方通话、智能路由

回溯法-图的m着色问题

图的 m 着色问题 问题描述 给定一个无向连通图 ( G = (V, E) ) 和 ( m ) 种颜色,我们的任务是为图 ( G ) 的每个顶点着色,使得相邻的顶点颜色不同。如果存在这样的着色方案,我们称之为图 ( G ) 的 ( m ) 可着色问题。 算法思路 初始化:创建一个二维数组 colors 来记录每个顶点的颜色。选择起始点:从图中任选一个顶点作为起始点,并为其着色。相邻顶点着色