# 栈扫描与pclntab
# 栈扫描的流程
本小节主要讲扫描栈中对象和指针的过程，扫描其他的细节忽略（其他包括一些与go 特性相关的结构，如defer和panic，还包括扫描调度保留下来的上下文 gp.sched.ctxt ）
扫描栈和扫描堆一样，需要有类似heap pointer bitmap的结构来指示哪些地方有指针，这个结构叫做stack map 。精准的垃圾回收算法，stack map 不止一个，虽然在编译阶段，就能确定所有栈中变量的位置，也能准确的知道哪些位置有指针，但是在运行过程中，那些位置并不一定真的有，比如指针变量还未被赋值，对象还未初始化。理想情况下，任意一个PC，都应该有一个相对应的stack map，但是这样会造成程序体积非常的庞大。编译器只会生成一些stack map，如果要扫描一个go routine的栈的时候，go routine 必须停在有stack map 的地方（GC-safe point）才行 。
stack map 中包含编译阶段对代码静态分析的结果，包含了在哪些位置（PC）哪些指针和栈对象（stack allocated object）是存活的。有了这些信息，在扫描栈的时候只需要扫描这些标记存活的对象和指针即可。但是有些情况静态分析不能分析出，比如下图 的情况，只有在运行的时候，才能做出判断，如果 if 条件成立， p 会被重新赋值，t 就不再存活（如果p是t的唯一引用）。
解决上述这个问题的方式如下，首先扫描每个栈帧中存活的指针，如果指针指向堆对象，就按扫描堆对象的方式处理，如果指针指向的是栈，就先记录下这个指针。对于每个栈帧中的对象，先不进行扫描，先把对象记录下来，当整个栈的所有栈帧都这么处理完成以后，再根据地址构建一颗栈对象的二叉搜索树，然后逐个取出扫描栈帧记录下来的指向栈对象的指针，在二叉树中搜索指针指向的对象，并扫描这个对象（如果找到的话）。最终，所有被引用的对象都被扫描了，那些没有被引用的对象就免去了扫描。
这个方法的确省去了不必要的扫描，不过带来了额外的空间开销。如果不采用这个方法，每次扫描的时候可以以栈帧为单位，直接扫描。但是如果采用了这个方法，必须保存下所有栈帧中stack map 标记存活的对象的相关信息（类型、栈内偏移等等）。
# stack traceback
栈扫描的时候，需要从栈顶到栈底挨个扫描栈帧，栈帧的详细描述信息是在traceback的过程中生成的，下图中的stackframe是描述栈帧的结构。一个go routine 暂停运行时的PC和SP都保存在g结构体中，traceback就从这个PC开始。golang使用了pclntab储存了许多元数据，包括stack map，同样也包括了从PC 到 函数的信息的映射。通过查询pclntab ，可以通过一个PC定位到这个PC所在的函数的信息（stackframe.fn）。stackframe.fp 也可以通过查询pclntab获得，pclntab中还记录了执行到某pc时SP与FP的偏移。stackframe.lr (opens new window) 存的是函数的返回地址，argp是args from caller的起始地址，在fp已知的情况下，这俩可以计算出来，计算的方式x86与arm不同，具体看 calling convention。arglen 可以通过 funcInfo 获取，至于argmap 是为了几个函数特地设置的，不深究。
从一个栈帧向上回溯，上一个栈帧（更靠近栈底的）的SP就是当前栈帧的FP，而上一个栈帧的PC就是当前栈帧的lr。当通过PC找不到一个合法的funcInfo的时候，回溯终止。
# pclntab
pclntab开头8个字节，function table 尾随其后。前边的8个字节中，分成4部分，起头的4字节大小的magic number 中间两个字节的0x00没有实际意义，尾随两个字节分别代表minimum lenght of an instruction code 和 size of pointer 。8字节后边就是function table (上图中的ftab)
function table 中是函数entry和offset的连续排列，entry表示的是函数的起始PC，offset表示函数相关详细信息在pclntab中的偏移。函数相关的详细信息位于上图的左侧，这个信息对应的结构下图所示
_func 结构体只展示了图1中绘制出来的function information的一部分，图1中的nfuncdata后边还有数据，但是那些数据都没有在 _func 中体现。nameoff 记录的是函数名称的偏移，函数的名称会记录在图1中的 content of name ，可以看到content of name 是一个虚线框（因为如果名字有重复的话，就不需要浪费这个空间了，nameoff直接记录已经存在的名字字符串的偏移）。
pcsp存储的是pc-value of pcsp的偏移，pc-value of pcsp 的内容是pc到 sp 与 fp 偏移的 映射，同理pcfile 存储的也是 pc-value of pcfile 的偏移，pc-value of pcfile 存储的是 pc 到 文件名的映射，pcfile可能会有些令人疑惑，因为一个函数都在一个文件里，直观感受每个pc对应的文件名都是相同的，但是如果这个函数调用了其他文件的函数，并且编译器做了内联，pcfile 就不只有单一的文件了。pcln是PC到行的映射。
npcdata 存的是这个函数pcdata的数量，每个pcdata的offset 都存在图1中的offset of pcdata部分，实际的内容则存在 图1中的 pc-value of pcdata 中。图1展示了pcdata的种类，pcdata 存的信息包括stackmap相关信息，还有内联相关的信息、UnsafePoint
address of funcdata 存的是funcdata 的地址（而不是偏移），funcdata的数量存在nfuncdata中，种类如上图所示。
pcdata记录的是偏移，funcdata记录的是内容，拿stackmap为例子，funcdata中记录的是所有位置的stackmap，而要找到具体某一位置的stackmap，需要pcdata记录的信息，pc-value记录了PC与对应stackmap在fundata中全部stackmap中的位置。
# pc-value
pc-value 的存储的顺序正好和名字相反，读和先都是先value 后 pc 。pc-value存储的信息是压缩过的，记录的都是偏移量。golang的文档中有一个例子，使用pc-value存储pcsp。
以上图为例，上图是main函数的反汇编代码，函数的起始地址是2000，如果要存储所有PC对应 SP指针到FP的偏移值（pcsp），只需要在每次SP变化的时候存储一下 SP偏移 (value) 和 PC值 (pc)就行，如下图 的原始值所示。这种表示方式已经可以减少很多空间了，整个函数87个PC压缩后只有7行记录。
再看上图的偏移值，偏移值这种表示方式相对于原始值这种表示的区别是，每个pc-value对都是基于前一个计算而来的（规定第0对pc-value的value是-1，PC是函数的起始地址），这样就进一步节省了空间，不过在解析pc-value的时候就要更多的计算。存储的时候每个数字占用的空间不是定长的，否则使用偏移值也没有意义，比如存储一个1只需要一个字节，而存储一个257需要2个字节。并且还要有一种方式来确定一个数到底有多少字节表示。源码实现中使用每个字节的最高位来表示这个数是否还要表示的字节，如果最高位是1，则表示还需要再读一个字节，如果下一个字节的最高位还是1，还要再读一个字节，直到读到一个字节的最高位不是1为止。读和写一律按照小端序，无论是什么架构下，下图是源码中读和写的具体实现。这种表示方式对于正数来说是没有问题的，但是负数会有问题，pc-value中只有value可能是负数，因为PC都是递增的，计算出来的偏移都是正数。value 还需要使用zig-zag进行编码才行，zig-zag编码就是用0、1、2、3、4... 分别表示 0、-1、1、-2、2...
