什么事软件堆栈？什么是硬件堆栈？

ggfhkl45

栈是一种具有先入后出特性的数据结构，前面说过，这种特性常常用来帮住我们“原理返回”或者“保持原样”。试想，当我们第一次来到一个陌生的城市，走在陌生的街道上，寻找一个陌生的目标，最令我们有安全感的莫过于仔细记录走过的每一个街道、穿过的每一个路口--这种安全感来源于潜意识里“万一找不到目的地就原路返回”的想法。记得20世纪90年代，有一首家喻户晓的流行歌曲《星星点灯》中曾这样唱到“星星点灯...为迷失的孩子，照亮来时的路”。  \, v( E# z* z" J4 g- Z
, I3 ^, B. f) F9 i
$ A9 w) E9 M2 S+ \# Z  y4 O! d
/ K& W1 j/ B; x+ v( L2 A/ M“找到来时的路”这种想法是人们基本的求生本能，对有人类编写的C语言编译器来说，也是这样--面对一层一层复杂嵌套关系的函数调用，编译器总是试图记录下我们调用的过程，以便“找回回去的路”。栈就在这种场合中，得到了广泛的应用。

; X" J$ ^, n; b+ x
4 J/ @/ b" K7 k; }, m) n0 J, ]C语言支持函数的调用，这完全得益于栈式分配策略的使用。所谓栈式分配，抛去复杂的技术细节，简单说来，就是将函数内部使用的种种信息(例如，局部变量)在发生函数嵌套调用时，压入栈中“记录下所走过的路”。这样，当调用的函数运行结束需要返回时，编译器就能很容易从栈中找到“来时的路”。使用模拟的方法，我们来具体看看这一过程。$ i+ m8 D$ H) a
0 C: l/ s# C5 J6 ~& c  K: [7 f: u0 ~
# E- Y* y2 q, E# A: M4 P( \$ |# j8 [
我们假设：一个函数中所有牵涉到的局部信息都被包含在一个与函数同名的接节点中。当我们在某一个函数中发生了对另外一个函数的调用，就将本函数的局部信息压入栈中--也就是将以该函数命名的结点压入栈中：当我们从某一函数中返回，就从栈中弹出一个结点。观察一段代码的函数调用情况，了解编译器如何借助来实现函数的嵌套调用。
; v, h, {9 {2 G  I% l0 I* e* l0 e1 A# K% L+ D9 S
# g6 f% F* R; f6 q' A9 u
9 e& ~; e0 j( f# ~2 n//这是一段演示用的伪代码，包含了一些函数并设置了一些断点便于观察& k+ W  u+ |1 ~  ^* J
7 ?- J# U8 F8 f8 w2 T//函数的细节已经省略，只保留了对其他函数的调用关系
//函数A2 b: O* c& |5 y& S7 @
void FuncA(void)1 s! q( J) d& S4 Q1 x. M
* J* X$ q6 z* S/ |, U{; B  }& M- L# {1 [% r( n8 k/ t9 E
' _8 g) e/ D+ z- s: s1 P+ d& y+ h//没有任何针对其他函数的嵌套调用
% S$ J9 W! H$ ^  @; `$ H( Y/*断点A1*/
" {) f1 G! e  D$ w9 i& B. S) J}
$ S: h' w5 X2 O2 I9 s" F  b6 W//函数B
void FuncB(void)
{
: V1 G2 R( {% t2 D' u...; K0 S; O5 _- R: A8 _! B
FuncA();//调用了函数A
/*断点B1*/
$ \3 E6 Y9 X) p: P- m...5 e" F4 w; s' E, Y
}0 A: v( u; H0 c  j
//函数C
& _  k1 Y4 U! ]* L: v, mvoid FuncC(void)5 e7 }! f# l% I3 V2 F
0 t/ }; h! G$ i# F{7 N, p( f3 z" t; h! y8 }! T$ B, V
6 w; m' A6 h, i& V...- b" g& T" |* l# p  g7 E, W4 _+ \
; j0 _0 |  Z+ LFuncB();//调用了函数B
/*断点C1*/
: j1 t3 _/ @; L4 AFuncA();//调用了函数A  X; J' U; ?  r9 K6 ^
/*断点C2*/
..." o+ t. _, c& u
9 m1 q% o' F# a! W}7 E5 F7 l* k; d* r9 A' W+ O% B
1 \- q6 G& S& r3 P  j//主函数
void main(void)
5 Q; \! b# J  U8 s{$ K' M" k) J0 H% E. ^
3 N1 J& y  p. @( `1 P...
/*在这里，我们设置一个程序断点，称为断点1*/% r$ l! `, b+ _- H
FuncA();( L+ F2 C9 \+ c! P& E) v% B5 _
/*断点2*/
FuncB();5 ^: m" P. e4 Y* v
/*断点3*/$ Z% u$ w% [& W
FuncC()
+ F3 |' R1 p6 o, ~0 [) w3 N+ d/*断点4*/8 Z* u: v* J4 N5 S0 B5 |% V) @; k
...
+ E3 c( m8 ?" I}- z- F/ ^3 @8 n5 U
当程序运行到断点1时，因为还没有发生任何函数调用(我们假设测试环境中没有使用到操作系统，因此不存在操作系统调用main函数的问题，也就是不存在将操作系统相关的内容压入栈中的问题)，此时，栈是空的，如图13-10(a)所示。' f2 l% v6 l7 Z) e
, S, E  F! |# \, ]) W7 s2 |# U, m) }2 o/ l& G0 P
! o* W% u% W* N1 n5 m; ~/ v$ J
- y, B+ H6 |2 C: u8 x1 W程序继续运行，发生函数调用--FuncA(),并在其中遇到了断点A1。因为此时发生了函数的调用，结点main被压入栈中。此时只是一个结点，如图13-10(b)所示。程序运行到断点2，系统从函数FuncA()返回，因此，将结点main弹出，如图13-10(c)所示。: W! G6 ^' L+ ^9 D
0 P4 h. `+ y$ M' k  A, t" S" o/ _

( ^, ~1 ]3 s! D继续运行程序，直到再次遇到断点A1。此时，栈中有两个元素，从栈顶向下分别是FuncB、main。这说明，在此之前，发生了两次调用：首先是main调用了FuncB，紧接着在FuncB中调用了FuncA，如图13-11(a)所示。当我们遇到断点B1时，程序已经从FuncA中返回，因此弹出了栈顶元素FuncA,如图13-11(b)所示。经过断点3时，结点main也被弹出，栈再次成为空栈，如图13-11(c)所示。
: _0 ~2 x1 ^6 s% a0 p- i: M4 F6 y, ]4 q3 o+ D
& J+ q$ Q% ^% [. t# q& _8 \. [; {* i& d' N9 T  o# ^  k; X0 b
, A  }7 t+ r9 c  W  D当程序第三次执行到断点A1时，由于发生了三次函数调用，因此，栈中有三个结点FuncB,FuncA和main，如图13-11(d)所示。再次经过断点B1时，程序从函数FuncA中返回，因此弹出了栈顶元素FuncB,如图13-11(e)所示。程序继续执行，从函数FuncB中返回遇到断点C1时，结点FuncC被弹出，如图13-11(f)所示。$ G% U, g2 I, p  T' z3 B% T1 R  ^' z
6 T/ I6 N. _1 E' f  N0 s$ t4 ^" \  a- P6 `  I
/ j3 @2 f( L: g( p
从断点C1向后执行，调用函数FuncA第四次遇到断点A1，结点FuncA再次被压入栈中，如图13-12(a)所示。程序从函数FuncA返回，经过断点C2 时，弹出栈顶指针FuncA,如图13-12(b)所示。当我们遇到断点4时，程序已经回归到主函数main()，栈中最后一个结点被弹出，称为空栈，如图13-12(c)所示。( r* O2 Z+ I0 I7 r3 S
& |/ _- x5 Z. F6 v' \/ S

通过上面的模拟，我们展示了C编译器利用栈实现函数嵌套条用的原理。详细情形大家可以参考编译原理的相关内容，这里就不再深入。前面，我们知道，没当发生一次函数调用，编译器都要保存当前的相关信息。这一信息至少包括两大部分：其一，用于描述程序从函数调用中返回时，返回到哪个函数位置;另一部分，用于描述与当前函数有关的一些局部信息(比方说局部变量)。在ICC中，编译器将两个独立开来，分别使用两个栈来保存。保存函数返回地址(也就是第一部分)的栈被称为硬件栈(Hardware Stack 或者 Resturn Stack)。保存当前函数局部相关信息的栈，我们称之为软件堆栈(Software Stack)。( ~; _- \* t: W6 P' B
$ Z  r" A* i8 Z5 Y' q5 Q: c

将原来完整的结点信息一分为二，究竟是出于怎样的考虑呢?我们知道，单片机的内存容量有限(ATMeag48的SRAM仅有512个字节)，不可能允许无限制的函数嵌套，必须对栈的尺寸加以限定。在正常情况下，一个结点中包含的信息总是包含定长和不定长两个部分。其中，表示函数返回地址的部分由于指针长度固定为2个字节，因此属于定长部分。将其单独作为一个结点保存在硬件堆栈中，便于规定函数允许嵌套的最大深度(例如，当我们设定HW Stack的最大尺寸是16时，就表示所允许的函数嵌套深度最大为8层)。出去函数返回地址，我们将其余的变长信息统一放在软件堆栈中，而这一部分的尺寸我们是无法预计的--栈究竟需要多大空间，完全取决于用户在函数中定义了多少局部信息(比方说局部变量)及函数嵌套了多少层，因此，我们总希望能给HW Stack提供尽可能大的空间。" R3 i+ }4 a- v% D
% F& G) W, C8 m+ F' C% b
9 p' q$ B2 `' C( L  o& @0 }" h" H7 h9 G" `: P
出于以上考虑，ICC系统采用硬件栈和软件栈分开存储的方式。编译器要求硬件栈的大小必须在程序编译器前由用户给定(在ICC集成开发环境中，有Compile Option--Target选项卡的Return Stack Size选项卡来设定)，如图13-13所示。硬件栈位于SRAM的高地址，采用向上生长的方式，大小直接受到从栈底地址开始至存储器顶端所剩余的空间限制。这一空间大小恰好等于Return Stack所设置的数值。软件栈与硬件栈背靠背存放，采取向下生长的方式，虽然其大小受到诸多因素的共同影响，但最大尺寸在编译完成后也是确定的，如图13-14所示。

/ i( o2 [  _% f/ J7 C6 {* a
! l( ^: p# U/ b& e' D) Q6 @7 E考虑到存储器的大小的限制，我们在编写单片机的程序时，一定要精打细算。一个程序，当系统中使用了大量的中断资源，并且允许了中断嵌套的存在，那么在极端的情况下，中断处理程序就很容易发生嵌套现象。此时适当扩大硬件堆栈的大小，支持较大的函数嵌套深度，往往能解决很多莫名其妙的跑飞问题。与拥有丰富存储器资源时的状况不同，由于局部变量在函数发生嵌套时，都要占用软件堆栈空间，因此大量使用使用局部变量或者使用了占用空间颇为可观的局部数组(也包括体积巨大的结构体)，在嵌套深度较大时，都有可能造成向下生长的软件堆栈侵入其他存储区域(详细情形阅读ICC的帮助文档)，导致某些变量意外修改、程序跑飞等现象。解决这一问题的方法其实很简单，在某些局部变量占用空间较大的情况下，将其通过关键static声明为静态变量--这样即保证了变量的局限性，又避免了将这些内容压入软件栈中(静态局部变量在存储时和全局变量没有本质区别，采用的都是 静态分配)，只不过每次使用这些变量之前都要记得补充必要的初始化代码。
9 S+ c, f0 L  ~8 Z