Go 語言 再論函數

原文鏈接：https://chai2010.cn/advanced-go-programming-book/ch3-asm/ch3-06-func-again.html

3.6 再論函數

在前面的章節(jié)中我們已經簡單討論過 Go 的匯編函數，但是那些主要是葉子函數。葉子函數的最大特點是不會調用其他函數，也就是棧的大小是可以預期的，葉子函數也就是可以基本忽略爆棧的問題（如果已經爆了，那也是上級函數的問題）。如果沒有爆棧問題，那么也就是不會有棧的分裂問題；如果沒有棧的分裂也就不需要移動棧上的指針，也就不會有棧上指針管理的問題。但是是現實中 Go 語言的函數是可以任意深度調用的，永遠不用擔心爆棧的風險。那么這些近似黑科技的特性是如何通過低級的匯編語言實現的呢？這些都是本節(jié)嘗試討論的問題。

3.6.1 函數調用規(guī)范

在 Go 匯編語言中 CALL 指令用于調用函數，RET 指令用于從調用函數返回。但是 CALL 和 RET 指令并沒有處理函數調用時輸入參數和返回值的問題。CALL 指令類似 PUSH IP 和 JMP somefunc 兩個指令的組合，首先將當前的 IP 指令寄存器的值壓入棧中，然后通過 JMP 指令將要調用函數的地址寫入到 IP 寄存器實現跳轉。而 RET 指令則是和 CALL 相反的操作，基本和 POP IP 指令等價，也就是將執(zhí)行 CALL 指令時保存在 SP 中的返回地址重新載入到 IP 寄存器，實現函數的返回。

和 C 語言函數不同，Go 語言函數的參數和返回值完全通過棧傳遞。下面是 Go 函數調用時棧的布局圖：

圖 3-13 函數調用參數布局

首先是調用函數前準備的輸入參數和返回值空間。然后 CALL 指令將首先觸發(fā)返回地址入棧操作。在進入到被調用函數內之后，匯編器自動插入了 BP 寄存器相關的指令，因此 BP 寄存器和返回地址是緊挨著的。再下面就是當前函數的局部變量的空間，包含再次調用其它函數需要準備的調用參數空間。被調用的函數執(zhí)行 RET 返回指令時，先從?；謴?BP 和 SP 寄存器，接著取出的返回地址跳轉到對應的指令執(zhí)行。

3.6.2 高級匯編語言

Go 匯編語言其實是一種高級的匯編語言。在這里高級一詞并沒有任何褒義或貶義的色彩，而是要強調 Go 匯編代碼和最終真實執(zhí)行的代碼并不完全等價。Go 匯編語言中一個指令在最終的目標代碼中可能會被編譯為其它等價的機器指令。Go 匯編實現的函數或調用函數的指令在最終代碼中也會被插入額外的指令。要徹底理解 Go 匯編語言就需要徹底了解匯編器到底插入了哪些指令。

為了便于分析，我們先構造一個禁止棧分裂的 printnl 函數。printnl 函數內部都通過調用 runtime.printnl 函數輸出換行：

TEXT ·printnl_nosplit(SB), NOSPLIT, $8
    CALL runtime·printnl(SB)
    RET

然后通過 go tool asm -S main_amd64.s 指令查看編譯后的目標代碼：

"".printnl_nosplit STEXT nosplit size=29 args=0xffffffff80000000 locals=0x10
0x0000 00000 (main_amd64.s:5) TEXT "".printnl_nosplit(SB), NOSPLIT	$16
0x0000 00000 (main_amd64.s:5) SUBQ $16, SP

0x0004 00004 (main_amd64.s:5) MOVQ BP, 8(SP)
0x0009 00009 (main_amd64.s:5) LEAQ 8(SP), BP

0x000e 00014 (main_amd64.s:6) CALL runtime.printnl(SB)

0x0013 00019 (main_amd64.s:7) MOVQ 8(SP), BP
0x0018 00024 (main_amd64.s:7) ADDQ $16, SP
0x001c 00028 (main_amd64.s:7) RET

輸出代碼中我們刪除了非指令的部分。為了便于講述，我們將上述代碼重新排版，并根據縮進表示相關的功能：

TEXT "".printnl(SB), NOSPLIT, $16
    SUBQ $16, SP
        MOVQ BP, 8(SP)
        LEAQ 8(SP), BP
            CALL runtime.printnl(SB)
        MOVQ 8(SP), BP
    ADDQ $16, SP
RET

第一層是 TEXT 指令表示函數開始，到 RET 指令表示函數返回。第二層是 SUBQ $16, SP 指令為當前函數幀分配 16 字節(jié)的空間，在函數返回前通過 ADDQ $16, SP 指令回收 16 字節(jié)的棧空間。我們謹慎猜測在第二層是為函數多分配了 8 個字節(jié)的空間。那么為何要多分配 8 個字節(jié)的空間呢？再繼續(xù)查看第三層的指令：開始部分有兩個指令 MOVQ BP, 8(SP) 和 LEAQ 8(SP), BP，首先是將 BP 寄存器保持到多分配的 8 字節(jié)棧空間，然后將 8(SP) 地址重新保持到了 BP 寄存器中；結束部分是 MOVQ 8(SP), BP 指令則是從棧中恢復之前備份的前 BP 寄存器的值。最里面第四次層才是我們寫的代碼，調用 runtime.printnl 函數輸出換行。

如果去掉 NOSPLIT 標志，再重新查看生成的目標代碼，會發(fā)現在函數的開頭和結尾的地方又增加了新的指令。下面是經過縮進格式化的結果：

TEXT "".printnl_nosplit(SB), $16
L_BEGIN:
    MOVQ (TLS), CX
    CMPQ SP, 16(CX)
    JLS  L_MORE_STK

        SUBQ $16, SP
            MOVQ BP, 8(SP)
            LEAQ 8(SP), BP
                CALL runtime.printnl(SB)
            MOVQ 8(SP), BP
        ADDQ $16, SP

L_MORE_STK:
    CALL runtime.morestack_noctxt(SB)
    JMP  L_BEGIN
RET

其中開頭有三個新指令，MOVQ (TLS), CX 用于加載 g 結構體指針，然后第二個指令 CMPQ SP, 16(CX)SP 棧指針和 g 結構體中 stackguard0 成員比較，如果比較的結果小于 0 則跳轉到結尾的 L_MORE_STK 部分。當獲取到更多?？臻g之后，通過 JMP L_BEGIN 指令跳轉到函數的開始位置重新進行?？臻g的檢測。

g 結構體在 $GOROOT/src/runtime/runtime2.go 文件定義，開頭的結構成員如下：

type g struct {
    // Stack parameters.
    stack       stack   // offset known to runtime/cgo
    stackguard0 uintptr // offset known to liblink
    stackguard1 uintptr // offset known to liblink

    ...
}

第一個成員是 stack 類型，表示當前棧的開始和結束地址。stack 的定義如下：

// Stack describes a Go execution stack.
// The bounds of the stack are exactly [lo, hi),
// with no implicit data structures on either side.
type stack struct {
    lo uintptr
    hi uintptr
}

在 g 結構體中的 stackguard0 成員是出現爆棧前的警戒線。stackguard0 的偏移量是 16 個字節(jié)，因此上述代碼中的 CMPQ SP, 16(AX) 表示將當前的真實 SP 和爆棧警戒線比較，如果超出警戒線則表示需要進行棧擴容，也就是跳轉到 L_MORE_STK。在 L_MORE_STK 標號處，先調用 runtime·morestack_noctxt 進行棧擴容，然后又跳回到函數的開始位置，此時此刻函數的棧已經調整了。然后再進行一次棧大小的檢測，如果依然不足則繼續(xù)擴容，直到棧足夠大為止。

以上是棧的擴容，但是棧的收縮是在何時處理的呢？我們知道 Go 運行時會定期進行垃圾回收操作，這其中包含棧的回收工作。如果棧使用到比例小于一定到閾值，則分配一個較小到?？臻g，然后將棧上面到數據移動到新的棧中，棧移動的過程和棧擴容的過程類似。

3.6.3 PCDATA 和 FUNCDATA

Go 語言中有個 runtime.Caller 函數可以獲取當前函數的調用者列表。我們可以非常容易在運行時定位每個函數的調用位置，以及函數的調用鏈。因此在 panic 異?；蛴?log 輸出信息時，可以精確定位代碼的位置。

比如以下代碼可以打印程序的啟動流程：

func main() {
    for skip := 0; ; skip++ {
        pc, file, line, ok := runtime.Caller(skip)
        if !ok {
            break
        }

        p := runtime.FuncForPC(pc)
        fnfile, fnline := p.FileLine(0)

        fmt.Printf("skip = %d, pc = 0x%08X\n", skip, pc)
        fmt.Printf("func: file = %s, line = L%03d, name = %s, entry = 0x%08X\n", fnfile, fnline, p.Name(), p.Entry())
        fmt.Printf("call: file = %s, line = L%03d\n", file, line)
    }
}

其中 runtime.Caller 先獲取當時的 PC 寄存器值，以及文件和行號。然后根據 PC 寄存器表示的指令位置，通過 runtime.FuncForPC 函數獲取函數的基本信息。Go 語言是如何實現這種特性的呢？

Go 語言作為一門靜態(tài)編譯型語言，在執(zhí)行時每個函數的地址都是固定的，函數的每條指令也是固定的。如果針對每個函數和函數的每個指令生成一個地址表格（也叫 PC 表格），那么在運行時我們就可以根據 PC 寄存器的值輕松查詢到指令當時對應的函數和位置信息。而 Go 語言也是采用類似的策略，只不過地址表格經過裁剪，舍棄了不必要的信息。因為要在運行時獲取任意一個地址的位置，必然是要有一個函數調用，因此我們只需要為函數的開始和結束位置，以及每個函數調用位置生成地址表格就可以了。同時地址是有大小順序的，在排序后可以通過只記錄增量來減少數據的大小；在查詢時可以通過二分法加快查找的速度。

在匯編中有個 PCDATA 用于生成 PC 表格，PCDATA 的指令用法為：PCDATA tableid, tableoffset。PCDATA 有個兩個參數，第一個參數為表格的類型，第二個是表格的地址。在目前的實現中，有 PCDATA_StackMapIndex 和 PCDATA_InlTreeIndex 兩種表格類型。兩種表格的數據是類似的，應該包含了代碼所在的文件路徑、行號和函數的信息，只不過 PCDATA_InlTreeIndex 用于內聯函數的表格。

此外對于匯編函數中返回值包含指針的類型，在返回值指針被初始化之后需要執(zhí)行一個 GO_RESULTS_INITIALIZED 指令：

#define GO_RESULTS_INITIALIZED	PCDATA $PCDATA_StackMapIndex, $1

GO_RESULTS_INITIALIZED 記錄的也是 PC 表格的信息，表示 PC 指針越過某個地址之后返回值才完成被初始化的狀態(tài)。

Go 語言二進制文件中除了有 PC 表格，還有 FUNC 表格用于記錄函數的參數、局部變量的指針信息。FUNCDATA 指令和 PCDATA 的格式類似：FUNCDATA tableid, tableoffset，第一個參數為表格的類型，第二個是表格的地址。目前的實現中定義了三種 FUNC 表格類型：FUNCDATA_ArgsPointerMaps 表示函數參數的指針信息表，FUNCDATA_LocalsPointerMaps 表示局部指針信息表，FUNCDATA_InlTree 表示被內聯展開的指針信息表。通過 FUNC 表格，Go 語言的垃圾回收器可以跟蹤全部指針的生命周期，同時根據指針指向的地址是否在被移動的棧范圍來確定是否要進行指針移動。

在前面遞歸函數的例子中，我們遇到一個 NO_LOCAL_POINTERS 宏。它的定義如下：

#define FUNCDATA_ArgsPointerMaps 0 /* garbage collector blocks */
#define FUNCDATA_LocalsPointerMaps 1
#define FUNCDATA_InlTree 2

#define NO_LOCAL_POINTERS FUNCDATA $FUNCDATA_LocalsPointerMaps, runtime·no_pointers_stackmap(SB)

因此 NO_LOCAL_POINTERS 宏表示的是 FUNCDATA_LocalsPointerMaps 對應的局部指針表格，而 runtime·no_pointers_stackmap 是一個空的指針表格，也就是表示函數沒有指針類型的局部變量。

PCDATA 和 FUNCDATA 的數據一般是由編譯器自動生成的，手工編寫并不現實。如果函數已經有 Go 語言聲明，那么編譯器可以自動輸出參數和返回值的指針表格。同時所有的函數調用一般是對應 CALL 指令，編譯器也是可以輔助生成 PCDATA 表格的。編譯器唯一無法自動生成是函數局部變量的表格，因此我們一般要在匯編函數的局部變量中謹慎使用指針類型。

對于 PCDATA 和 FUNCDATA 細節(jié)感興趣的同學可以嘗試從 debug/gosym 包入手，參考包的實現和測試代碼。

3.6.4 方法函數

Go 語言中方法函數和全局函數非常相似，比如有以下的方法：

package main

type MyInt int

func (v MyInt) Twice() int {
    return int(v)*2
}

func MyInt_Twice(v MyInt) int {
    return int(v)*2
}

其中 MyInt 類型的 Twice 方法和 MyInt_Twice 函數的類型是完全一樣的，只不過 Twice 在目標文件中被修飾為 main.MyInt.Twice 名稱。我們可以用匯編實現該方法函數：

// func (v MyInt) Twice() int
TEXT ·MyInt·Twice(SB), NOSPLIT, $0-16
    MOVQ a+0(FP), AX   // v
    ADDQ AX, AX        // AX *= 2
    MOVQ AX, ret+8(FP) // return v
    RET

不過這只是接收非指針類型的方法函數?，F在增加一個接收參數是指針類型的 Ptr 方法，函數返回傳入的指針：

func (p *MyInt) Ptr() *MyInt {
    return p
}

在目標文件中，Ptr 方法名被修飾為 main.(*MyInt).Ptr，也就是對應匯編中的 ·(*MyInt)·Ptr。不過在 Go 匯編語言中，星號和小括弧都無法用作函數名字，也就是無法用匯編直接實現接收參數是指針類型的方法。

在最終的目標文件中的標識符名字中還有很多 Go 匯編語言不支持的特殊符號（比如 type.string."hello" 中的雙引號），這導致了無法通過手寫的匯編代碼實現全部的特性。或許是 Go 語言官方故意限制了匯編語言的特性。

3.6.5 遞歸函數: 1 到 n 求和

遞歸函數是比較特殊的函數，遞歸函數通過調用自身并且在棧上保存狀態(tài)，這可以簡化很多問題的處理。Go 語言中遞歸函數的強大之處是不用擔心爆棧問題，因為?？梢愿鶕枰M行擴容和收縮。

首先通過 Go 遞歸函數實現一個 1 到 n 的求和函數：

// sum = 1+2+...+n
// sum(100) = 5050
func sum(n int) int {
    if n > 0 {return n+sum(n-1) } else { return 0 }
}

然后通過 if/goto 重構上面的遞歸函數，以便于轉義為匯編版本：

func sum(n int) (result int) {
    var AX = n
    var BX int

    if n > 0 {goto L_STEP_TO_END}
    goto L_END

L_STEP_TO_END:
    AX -= 1
    BX = sum(AX)

    AX = n // 調用函數后, AX 重新恢復為 n
    BX += AX

    return BX

L_END:
    return 0
}

在改寫之后，遞歸調用的參數需要引入局部變量，保存中間結果也需要引入局部變量。而通過棧來保存中間的調用狀態(tài)正是遞歸函數的核心。因為輸入參數也在棧上，所以我們可以通過輸入參數來保存少量的狀態(tài)。同時我們模擬定義了 AX 和 BX 寄存器，寄存器在使用前需要初始化，并且在函數調用后也需要重新初始化。

下面繼續(xù)改造為匯編語言版本：

// func sum(n int) (result int)
TEXT ·sum(SB), NOSPLIT, $16-16
    MOVQ n+0(FP), AX       // n
    MOVQ result+8(FP), BX  // result

    CMPQ AX, $0            // test n - 0
    JG   L_STEP_TO_END     // if > 0: goto L_STEP_TO_END
    JMP  L_END             // goto L_STEP_TO_END

L_STEP_TO_END:
    SUBQ $1, AX            // AX -= 1
    MOVQ AX, 0(SP)         // arg: n-1
    CALL ·sum(SB)          // call sum(n-1)
    MOVQ 8(SP), BX         // BX = sum(n-1)

    MOVQ n+0(FP), AX       // AX = n
    ADDQ AX, BX            // BX += AX
    MOVQ BX, result+8(FP)  // return BX
    RET

L_END:
    MOVQ $0, result+8(FP) // return 0
    RET

在匯編版本函數中并沒有定義局部變量，只有用于調用自身的臨時棧空間。因為函數本身的參數和返回值有 16 個字節(jié)，因此棧幀的大小也為 16 字節(jié)。L_STEP_TO_END 標號部分用于處理遞歸調用，是函數比較復雜的部分。L_END 用于處理遞歸終結的部分。

調用 sum 函數的參數在 0(SP) 位置，調用結束后的返回值在 8(SP) 位置。在函數調用之后要需要重新為需要的寄存器注入值，因為被調用的函數內部很可能會破壞了寄存器的狀態(tài)。同時調用函數的參數值也是不可信任的，輸入參數值也可能在被調用函數內部被修改了。

總得來說用匯編實現遞歸函數和普通函數并沒有什么區(qū)別，當然是在沒有考慮爆棧的前提下。我們的函數應該可以對較小的 n 進行求和，但是當 n 大到一定程度，也就是棧達到一定的深度，必然會出現爆棧的問題。爆棧是 C 語言的特性，不應該在哪怕是 Go 匯編語言中出現。

Go 語言的編譯器在生成函數的機器代碼時，會在開頭插入一小段代碼。因為 sum 函數也需要深度遞歸調用，因此我們刪除了 NOSPLIT 標志，讓匯編器為我們自動生成一個棧擴容的代碼：

#include "funcdata.h"

// func sum(n int) int
TEXT ·sum(SB), $16-16
    NO_LOCAL_POINTERS

    // 原來的代碼

除了去掉了 NOSPLIT 標志，我們還在函數開頭增加了一個 NO_LOCAL_POINTERS 語句，該語句表示函數沒有局部指針變量。棧的擴容必然要涉及函數參數和局部編指針的調整，如果缺少局部指針信息將導致擴容工作無法進行。不僅僅是棧的擴容需要函數的參數和局部指針標記表格，在 GC 進行垃圾回收時也將需要。函數的參數和返回值的指針狀態(tài)可以通過在 Go 語言中的函數聲明中獲取，函數的局部變量則需要手工指定。因為手工指定指針表格是一個非常繁瑣的工作，因此一般要避免在手寫匯編中出現局部指針。

喜歡深究的讀者可能會有一個問題：如果進行垃圾回收或棧調整時，寄存器中的指針是如何維護的？前文說過，Go 語言的函數調用是通過棧進行傳遞參數的，并沒有使用寄存器傳遞參數。同時函數調用之后所有的寄存器視為失效。因此在調整和維護指針時，只需要掃描內存中的指針數據，寄存器中的數據在垃圾回收器函數返回后都需要重新加載，因此寄存器是不需要掃描的。

3.6.6 閉包函數

閉包函數是最強大的函數，因為閉包函數可以捕獲外層局部作用域的局部變量，因此閉包函數本身就具有了狀態(tài)。從理論上來說，全局的函數也是閉包函數的子集，只不過全局函數并沒有捕獲外層變量而已。

為了理解閉包函數如何工作，我們先構造如下的例子：

package main

func NewTwiceFunClosure(x int) func() int {
    return func() int {
        x *= 2
        return x
    }
}

func main() {
    fnTwice := NewTwiceFunClosure(1)

    println(fnTwice()) // 1*2 => 2
    println(fnTwice()) // 2*2 => 4
    println(fnTwice()) // 4*2 => 8
}

其中 NewTwiceFunClosure 函數返回一個閉包函數對象，返回的閉包函數對象捕獲了外層的 x 參數。返回的閉包函數對象在執(zhí)行時，每次將捕獲的外層變量乘以 2 之后再返回。在 main 函數中，首先以 1 作為參數調用 NewTwiceFunClosure 函數構造一個閉包函數，返回的閉包函數保存在 fnTwice 閉包函數類型的變量中。然后每次調用 fnTwice 閉包函數將返回翻倍后的結果，也就是：2，4，8。

上述的代碼，從 Go 語言層面是非常容易理解的。但是閉包函數在匯編語言層面是如何工作的呢？下面我們嘗試手工構造閉包函數來展示閉包的工作原理。首先是構造 FunTwiceClosure 結構體類型，用來表示閉包對象：

type FunTwiceClosure struct {
    F uintptr
    X int
}

func NewTwiceFunClosure(x int) func() int {
    var p = &FunTwiceClosure{
        F: asmFunTwiceClosureAddr(),
        X: x,
    }
    return ptrToFunc(unsafe.Pointer(p))
}

FunTwiceClosure 結構體包含兩個成員，第一個成員 F 表示閉包函數的函數指令的地址，第二個成員 X 表示閉包捕獲的外部變量。如果閉包函數捕獲了多個外部變量，那么 FunTwiceClosure 結構體也要做相應的調整。然后構造 FunTwiceClosure 結構體對象，其實也就是閉包函數對象。其中 asmFunTwiceClosureAddr 函數用于輔助獲取閉包函數的函數指令的地址，采用匯編語言實現。最后通過 ptrToFunc 輔助函數將結構體指針轉為閉包函數對象返回，該函數也是通過匯編語言實現。

匯編語言實現了以下三個輔助函數：

func ptrToFunc(p unsafe.Pointer) func() int

func asmFunTwiceClosureAddr() uintptr
func asmFunTwiceClosureBody() int

其中 ptrToFunc 用于將指針轉化為 func() int 類型的閉包函數，asmFunTwiceClosureAddr 用于返回閉包函數機器指令的開始地址（類似全局函數的地址），asmFunTwiceClosureBody 是閉包函數對應的全局函數的實現。

然后用 Go 匯編語言實現以上三個輔助函數：

#include "textflag.h"

TEXT ·ptrToFunc(SB), NOSPLIT, $0-16
    MOVQ ptr+0(FP), AX // AX = ptr
    MOVQ AX, ret+8(FP) // return AX
    RET

TEXT ·asmFunTwiceClosureAddr(SB), NOSPLIT, $0-8
    LEAQ ·asmFunTwiceClosureBody(SB), AX // AX = ·asmFunTwiceClosureBody(SB)
    MOVQ AX, ret+0(FP)                   // return AX
    RET

TEXT ·asmFunTwiceClosureBody(SB), NOSPLIT|NEEDCTXT, $0-8
    MOVQ 8(DX), AX
    ADDQ AX   , AX        // AX *= 2
    MOVQ AX   , 8(DX)     // ctx.X = AX
    MOVQ AX   , ret+0(FP) // return AX
    RET

其中 ·ptrToFunc 和 ·asmFunTwiceClosureAddr 函數的實現比較簡單，我們不再詳細描述。最重要的是 ·asmFunTwiceClosureBody 函數的實現：它有一個 NEEDCTXT 標志。采用 NEEDCTXT 標志定義的匯編函數表示需要一個上下文環(huán)境，在 AMD64 環(huán)境下是通過 DX 寄存器來傳遞這個上下文環(huán)境指針，也就是對應 FunTwiceClosure 結構體的指針。函數首先從 FunTwiceClosure 結構體對象取出之前捕獲的 X，將 X 乘以 2 之后寫回內存，最后返回修改之后的 X 的值。

如果是在匯編語言中調用閉包函數，也需要遵循同樣的流程：首先為構造閉包對象，其中保存捕獲的外層變量；在調用閉包函數時首先要拿到閉包對象，用閉包對象初始化 DX，然后從閉包對象中取出函數地址并用通過 CALL 指令調用。