https://www.cs.cmu.edu/~213/lectures/05-machine-basics.pdf

從 8086 到 Core i7

1978 年，Intel 發(fā)布了第一款 x86 指令集的微處理器——Intel 8086[1]，以此拉開了 Intel x86 系列發(fā)展的序幕。8086 是 16 位微處理器，主要為 IBM PC 和 DOS 設(shè)計(jì)，有 1MB 的地址空間。八年后的 1985，第一個(gè) 32 位 Intel 處理器(IA32) 386 誕生。2004 年，奔騰(Pentium) 4E 成為了第一個(gè) 64 位處理器(x86-64)。后來隨著摩爾定律在單個(gè)核心上達(dá)到極限，2006 年 Core 2 成為了第一個(gè)多核 Intel 處理器。

多核心的處理器大概長這樣：

image

隨著時(shí)代和科技的發(fā)展，處理器除了支持最基本的運(yùn)算指令集外，還增加了支持多媒體操作處理和更高效執(zhí)行條件操作的指令，這部分內(nèi)容涉及到分支預(yù)測[2]（又是一個(gè)很有意思但是沒時(shí)間寫的話題），因?yàn)槠P(guān)系不再贅述，簡單來說就是研究人員為了讓處理器效率提升采用了各種各樣的方法，可能只是為了 1% 的提升。

除了增加處理器本身的功能外，另外的趨勢是集成，比如說 2015 年的 Core i7 Broadwell，可以從下圖看到處理器芯片中加入了原來主板才有的許多部件，如 PCIe, SATA, DDR3 等等。

image

順帶說一下千年老二 AMD，主打性價(jià)比，研發(fā)的 Opteron 系列是 Pentium 4 的強(qiáng)勁對手，并且開發(fā)了自己的 64 位拓展 x86-64。

Intel 在 64 位處理器的發(fā)展并不算順風(fēng)順?biāo)?001 年本打算使用全新的架構(gòu)快速從 IA32 轉(zhuǎn)換到 IA64，但是糟糕的性能反倒給了 AMD 機(jī)會(huì)。后者在 2003 年發(fā)布的 x86-64(現(xiàn)在叫 AMD64) 架構(gòu)明顯更厲害，搞得 Intel 疲于應(yīng)戰(zhàn)，最后在 2004 年搞出來一個(gè)叫 EM64T 的東西，其實(shí)幾乎和 AMD64 一樣?，F(xiàn)在除了某些低端的處理器，幾乎都支持 x86-64，也是這一講主要介紹的內(nèi)容。

從 C 到機(jī)器代碼

機(jī)器代碼就是處理器能夠直接執(zhí)行的字節(jié)層面上的程序，但是對于人類來說基本上是不可讀的，所以把字節(jié)按照具體含義進(jìn)行『翻譯』，就成了人類可讀的匯編代碼。注意這里的用詞是『翻譯』而不是『編譯』，可以認(rèn)為匯編代碼就是機(jī)器代碼的可讀形式。

機(jī)器代碼和 C 代碼應(yīng)用兩套完全不同的邏輯，機(jī)器代碼是純粹從『執(zhí)行』的方式來進(jìn)行思考的，而 C 的話則因?yàn)檩^多的抽象有了『程序設(shè)計(jì)』這個(gè)概念。相信讀完這一節(jié)之后，你就會(huì)意識(shí)到為什么 C 語言的出現(xiàn)，可以稱得上計(jì)算機(jī)學(xué)科的『第二次工業(yè)革命』。

一門新語言絕非只是一套語法規(guī)則，而是一系列配套的工具加上語法規(guī)則。C 語言代碼最終成為機(jī)器可執(zhí)行的程序，會(huì)像流水線上的產(chǎn)品一樣接受各項(xiàng)處理：

• C 語言代碼(da.c, wang.c)經(jīng)過編譯器的處理(gcc -0g -S)成為匯編代碼(da.s, wang.s)
• 匯編代碼(da.s, wang.s)經(jīng)過匯編器的處理(gcc 或 as)成為對象程序(da.o, wang.o)
• 對象程序(da.o, wang.o)以及所需靜態(tài)庫(lib.a)經(jīng)過鏈接器的處理(gcc 或 ld)最終成為計(jì)算機(jī)可執(zhí)行的程序

我們直接來看一段代碼及其經(jīng)過編譯生成的匯編代碼，可能會(huì)有些難以理解，這是正常的，因?yàn)檫€沒有介紹處理器具體執(zhí)行指令的機(jī)制。這里我們先有一個(gè)感性的認(rèn)識(shí)即可。

// 代碼文件: sum.c



long plus(long x, long y);



void sumstore(long x, long y, long *dest)

{

long t = plus(x, y);

    *dest = t;

}

對應(yīng)的匯編代碼

sumstore:

    pushq   %rbx

    movq    %rbx, %rbx

    call    plus

    movq    %rax, (%rbx)

    popq    %rbx

    ret

比較一下我們就發(fā)現(xiàn)，C 語言代碼被處理成了有統(tǒng)一格式的匯編代碼，在匯編代碼中，第一個(gè)字符串叫做操作符，后面可能跟著 1/2/3 個(gè)以逗號(hào)分隔的操作數(shù)，為什么是以這樣的形式呢？這就要從處理器的運(yùn)算方式講起了，先來看看處理器是如何配合內(nèi)存進(jìn)行計(jì)算的：
：

image

• 程序計(jì)數(shù)器(PC, Program counter) - 存著下一條指令的地址，在 x86-64 中稱為 RIP
• 寄存器(Register) - 用來存儲(chǔ)數(shù)據(jù)以便操作
• 條件代碼(Codition codes) - 通常保存最近的算術(shù)或邏輯操作的信息，用來做條件跳轉(zhuǎn)

這里需要注意，處理器能夠執(zhí)行的操作其實(shí)是非常有限的，簡單來說只有三種：存取數(shù)據(jù)、計(jì)算和傳輸控制。存取數(shù)據(jù)是在內(nèi)存和寄存器之間傳輸數(shù)據(jù)，進(jìn)行計(jì)算則是對寄存器或者內(nèi)存中的數(shù)據(jù)執(zhí)行算術(shù)運(yùn)算，傳輸控制主要指非條件跳轉(zhuǎn)和條件分支。這也就是為什么匯編代碼有固定的 指令 操作數(shù)1 (,操作數(shù)2 ,操作數(shù)3) 這樣的形式了。

我們拿前面程序中的兩條指令來具體說明一下從 C 到匯編再到機(jī)器代碼的變化：

// C 代碼

*dest = t;



// 對應(yīng)的匯編代碼

movq    %rax, (%rbx)



// 對應(yīng)的對象代碼

0x40059e:   46 89 03

C 代碼的意思很簡單，就是把值 t 存儲(chǔ)到指針 dest 指向的內(nèi)存中。對應(yīng)到匯編代碼，就是把 8字節(jié)（也就是四個(gè)字, Quad words）移動(dòng)到內(nèi)存中（這也就是為什叫做 movq）。t 的值保存在寄存器 %rax 中，dest 指向的地址保存在 %rbx 中，而 *dest 是取地址操作，對應(yīng)于在內(nèi)存中找到對應(yīng)的值，也就是 M[%rbx]，在匯編代碼中用小括號(hào)表示取地址，即 (%rbx)。最后轉(zhuǎn)換成 3 個(gè)字節(jié)的指令，并保存在 0x40059e 這個(gè)地址中。

匯編入門

前面我們簡要了解了一下程序執(zhí)行的基本過程，也對匯編有了一點(diǎn)點(diǎn)認(rèn)識(shí)，這一節(jié)我們從寄存器的相關(guān)知識(shí)講起，介紹匯編的基本知識(shí)。這部分內(nèi)容雖然在實(shí)際編程中幾乎用不到，但是對于后面內(nèi)容的理解非常重要。

x86-64 架構(gòu)中的整型寄存器如下圖所示（暫時(shí)不考慮浮點(diǎn)數(shù)的部分）

image

仔細(xì)看看寄存器的分布，我們可以發(fā)現(xiàn)有不同的顏色以及不同的寄存器名稱，黃色部分是 16 位寄存器，也就是 16 位處理器 8086 的設(shè)計(jì)，然后綠色部分是 32 位寄存器（這里我是按照比例畫的），給 32 位處理器使用，而藍(lán)色部分是為 64 位處理器設(shè)計(jì)的。這樣的設(shè)計(jì)保證了令人震驚的向下兼容性，幾十年前的 x86 代碼現(xiàn)在仍然可以運(yùn)行！

前六個(gè)寄存器(%rax, %rbx, %rcx, %rdx, %rsi, %rdi)稱為通用寄存器，有其『特定』的用途：

• %rax(%eax) 用于做累加
• %rcx(%ecx) 用于計(jì)數(shù)
• %rdx(%edx) 用于保存數(shù)據(jù)
• %rbx(%ebx) 用于做內(nèi)存查找的基礎(chǔ)地址
• %rsi(%esi) 用于保存源索引值
• %rdi(%edi) 用于保存目標(biāo)索引值

而 %rsp(%esp) 和 %rbp(%ebp) 則是作為棧指針和基指針來使用的。下面我們通過 movq 這個(gè)指令來了解操作數(shù)的三種基本類型：立即數(shù)(Imm)、寄存器值(Reg)和內(nèi)存值(Mem)。

對于 movq 指令來說，需要源操作數(shù)和目標(biāo)操作數(shù)，源操作數(shù)可以是立即數(shù)、寄存器值或內(nèi)存值的任意一種，但目標(biāo)操作數(shù)只能是寄存器值或內(nèi)存值。指令的具體格式可以這樣寫 movq [Imm|Reg|Mem], [Reg|Mem]，第一個(gè)是源操作數(shù)，第二個(gè)是目標(biāo)操作數(shù)，例如：

• movq Imm, Reg -> mov $0x5, %rax -> temp = 0x5;
• movq Imm, Mem -> mov $0x5, (%rax) -> *p = 0x5;
• movq Reg, Reg -> mov %rax, %rdx -> temp2 = temp1;
• movq Reg, Mem -> mov %rax, (%rdx) -> *p = temp;
• movq Mem, Reg -> mov (%rax), %rdx -> temp = *p;

這里有一種情況是不存在的，沒有 movq Mem, Mem 這個(gè)方式，也就是說，我們沒有辦法用一條指令完成內(nèi)存間的數(shù)據(jù)交換。

上面的例子中有些操作數(shù)是帶括號(hào)的，括號(hào)的意思就是尋址，這也分兩種情況：

• 普通模式，(R)，相當(dāng)于 Mem[Reg[R]]，也就是說寄存器 R 指定內(nèi)存地址，類似于 C 語言中的指針，語法為：movq (%rcx), %rax 也就是說以 %rcx 寄存器中存儲(chǔ)的地址去內(nèi)存里找對應(yīng)的數(shù)據(jù)，存到寄存器 %rax 中
• 移位模式，D(R)，相當(dāng)于 Mem[Reg[R]+D]，寄存器 R 給出起始的內(nèi)存地址，然后 D 是偏移量，語法為：movq 8(%rbp),%rdx 也就是說以 %rbp 寄存器中存儲(chǔ)的地址再加上 8 個(gè)偏移量去內(nèi)存里找對應(yīng)的數(shù)據(jù)，存到寄存器 %rdx 中

因?yàn)閷ぶ愤@個(gè)內(nèi)容比較重要，所以多說兩句，不然之后接觸指針會(huì)比較吃力。對于尋址來說，比較通用的格式是 D(Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]+D]，其中：

• D - 常數(shù)偏移量
• Rb - 基寄存器
• Ri - 索引寄存器，不能是 %rsp
• S - 系數(shù)

除此之外，還有如下三種特殊情況

• (Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]]
• D(Rb, Ri) -> Mem[Reg[Rb]+Reg[Ri]+D]
• (Rb, Ri, S) -> Mem[Reg[Rb]+S*Reg[Ri]]

我們通過具體的例子來鞏固一下，這里假設(shè) %rdx 中的存著 0xf000，%rcx 中存著 0x0100，那么

• 0x8(%rdx) = 0xf000 + 0x8 = 0xf008
• (%rdx, %rcx) = 0xf000 + 0x100 = 0xf100
• (%rdx, %rcx, 4) = 0xf000 + 4*0x100 = 0xf400
• 0x80(, %rdx, 2) = 2*0xf000 + 0x80 = 0x1e080

了解了尋址之后，我們來看看運(yùn)算指令，這里以 leaq 指令為例子。具體格式為 leaq Src, Dst，其中 Src 是地址的表達(dá)式，然后把計(jì)算的值存入 Dst 指定的寄存器，也就是說，無須內(nèi)存引用就可以計(jì)算，類似于 p = &x[i];。我們來看一個(gè)具體的例子，假設(shè)一個(gè) C 函數(shù)是：

long m12(long x)

{

return x * 12;

}

對應(yīng)的匯編代碼為：

leaq (%rdi, %rdi, 2), %rax # t <- x+x*2

salq $2, %rax              # return t << 2

可以看到是直接對 %rdi 寄存器中存的數(shù)據(jù)（地址）進(jìn)行運(yùn)算，然后賦值給 %rax。最后給出一些常見的算術(shù)運(yùn)算指令，注意參數(shù)的順序，而且對于有符號(hào)和無符號(hào)數(shù)都是一樣的，更多的信息可以參考 Intel 官方文檔[3]。

需要兩個(gè)操作數(shù)的指令

• addq Src, Dest -> Dest = Dest + Src
• subq Src, Dest -> Dest = Dest - Src
• imulq Src, Dest -> Dest = Dest * Src
• salq Src, Dest -> Dest = Dest << Src
• sarq Src, Dest -> Dest = Dest >> Src
• shrq Src, Dest -> Dest = Dest >> Src
• xorq Src, Dest -> Dest = Dest ^ Src
• andq Src, Dest -> Dest = Dest & Src
• orq Src, Dest -> Dest = Dest | Src

需要一個(gè)操作數(shù)的指令

• incq Dest -> Dest = Dest + 1
• decq Dest -> Dest = Dest - 1
• negq Dest -> Dest = -Dest
• notq Dest -> Dest = ~Dest

流程控制

https://www.cs.cmu.edu/~213/lectures/06-machine-control.pdf
我們先來回顧一下 x86-64 處理器中不同的寄存器，這一部分很重要，務(wù)必要弄明白

image

首先要理解的是，寄存器中存儲(chǔ)著當(dāng)前正在執(zhí)行的程序的相關(guān)信息：

• 臨時(shí)數(shù)據(jù)存放在 (%rax, …)
• 運(yùn)行時(shí)棧的地址存儲(chǔ)在 (%rsp) 中
• 目前的代碼控制點(diǎn)存儲(chǔ)在 (%rip, …) 中
• 目前測試的狀態(tài)放在 CF, ZF, SF, OF 中

條件代碼與跳轉(zhuǎn)

最后的四個(gè)標(biāo)識(shí)位（CF, ZF, SF, OF）就是用來輔助程序的流程控制的，意思是：

• CF: Carry Flag (針對無符號(hào)數(shù))
• ZF: Zero Flag
• SF: Sign Flag (針對有符號(hào)數(shù))
• OF: Overflow Flag (針對有符號(hào)數(shù))

可以看到以上這四個(gè)標(biāo)識(shí)位，表示四種不同的狀態(tài)，舉個(gè)例子，假如我們有一條諸如 t = a + b 的語句，匯編之后假設(shè)用的是 addq Src, Dest，那么根據(jù)這個(gè)操作結(jié)果的不同，會(huì)相應(yīng)設(shè)置上面提到的四個(gè)標(biāo)識(shí)位，而因?yàn)檫@個(gè)是執(zhí)行類似操作時(shí)順帶盡心設(shè)置的，稱為隱式設(shè)置，例如：

• 如果兩個(gè)數(shù)相加，在最高位還需要進(jìn)位（也就是溢出了），那么 CF 標(biāo)識(shí)位就會(huì)被設(shè)置
• 如果 t 等于 0，那么 ZF 標(biāo)識(shí)位會(huì)被設(shè)置
• 如果 t 小于 0，那么 SF 標(biāo)識(shí)位會(huì)被設(shè)置
• 如果 2’s complement 溢出，那么 OF 標(biāo)識(shí)位會(huì)被設(shè)置為 1（溢出的情況是 (a>0 && b > 0 && t <0) || (a<0 && b<0 && t>=0)）

這就發(fā)現(xiàn)了，其實(shí)這四個(gè)條件代碼，是用來標(biāo)記上一條命令的結(jié)果的各種可能的，是自動(dòng)會(huì)進(jìn)行設(shè)置的。注意，使用 leaq 指令的話不會(huì)進(jìn)行設(shè)置。

除了隱形設(shè)置，還可以顯式進(jìn)行設(shè)置，具體的方法是使用 cmpq 指令，這里的 q 指的是 64 位的地址。具體來說 cmpq Src2(b), Src1(a) 等同于計(jì)算 a-b（注意 a b 順序是顛倒的），然后利用 a-b 的結(jié)果來對應(yīng)進(jìn)行條件代碼的設(shè)置：

• 如果在最高位還需要進(jìn)位（也就是溢出了），那么 CF 標(biāo)識(shí)位就會(huì)被設(shè)置
• a 和 b 相等時(shí)，也就是 a-b 等于零時(shí)，ZF 標(biāo)識(shí)位會(huì)被設(shè)置
• 如果 a < b，也就是 (a-b)<0 時(shí)，那么 SF 標(biāo)識(shí)位會(huì)被設(shè)置
• 如果 2’s complement 溢出，那么 OF 標(biāo)識(shí)位會(huì)被設(shè)置（溢出的情況是 (a>0 && b > 0 && t <0) || (a<0 && b<0 && t>=0)）

另一種進(jìn)行顯式設(shè)置的方法是使用 testq 指令，具體來說 testq Src2(b), Src1(a) 等同于計(jì)算 a&b（注意 a b 順序是顛倒的），然后利用 a-b 的結(jié)果來對應(yīng)進(jìn)行條件代碼的設(shè)置，通常來說會(huì)把其中一個(gè)操作數(shù)作為 mask：

• 當(dāng) a&b == 0 時(shí)，ZF 標(biāo)識(shí)位會(huì)被設(shè)置
• 當(dāng) a&b < 0 時(shí)，SF 標(biāo)識(shí)位會(huì)被設(shè)置

有了這四個(gè)條件碼，就可以通過不同的組合方式，來產(chǎn)生不同的條件判斷。

介紹完了條件代碼，就可以來看看具體的跳轉(zhuǎn)了，跳轉(zhuǎn)實(shí)際上就是根據(jù)條件代碼的不同來進(jìn)行不同的操作。我們先來看一個(gè)比較原始的例子（編譯器沒有進(jìn)行優(yōu)化）：

long absdiff(long x, long y)

{

long result;

if (x > y)

        result = x-y;

else

        result = y-x;

return result;

}

對應(yīng)的匯編代碼如下，這里 %rdi 中保存了參數(shù) x，%rsi 中保存了參數(shù) y，而 %rax 一般用來存儲(chǔ)返回值：

absdiff:

    cmpq    %rsi, %rdi

    jle     .L4

    movq    %rdi, %rax

    subq    %rsi, %rax

    ret

.L4:    # x <= y

    movq    %rsi, %rax

    subq    %rdi, %rax

    ret

這里我們是要給出兩個(gè)數(shù)的絕對值的差，所以需要判斷誰大誰小。考慮到匯編不算特別直觀，這里我們用 goto 語句重寫一次，基本上就和匯編出來的代碼邏輯類似了，方便之后的講解：

long absdiff_goto(long x, long y)

{

long result;

int ntest = x <= y;

if (ntest) goto Else;

    result = x-y;

goto Done;

Else:

    result = y-x;

Done:

return result;

}

我們再看另一種條件語句要如何翻譯，比如 val = Test ? Then_Expr : Else_Expr;，重寫上面的函數(shù)就是：val = x>y ? x-y : y-x;

轉(zhuǎn)換成 goto 形式就是：

    ntest = !Test;

if (ntest) goto Else;

    value = Then_Expr;

goto Done;

Else:

    val = Else_Expr;

Done:

    ...

但是實(shí)際上匯編出來的代碼，并不是這樣的，會(huì)采用另一種方法來加速分支語句的執(zhí)行?，F(xiàn)在我們先來說一說，為什么分支語句會(huì)對性能造成很大的影響。

我們知道現(xiàn)在的 CPU 都是依靠流水線工作的，比方說執(zhí)行一系列操作需要 ABCDE 五個(gè)步驟，那么在執(zhí)行 A 的時(shí)候，實(shí)際上執(zhí)行 B 所需的數(shù)據(jù)會(huì)在執(zhí)行 A 的同時(shí)加載到寄存器中，這樣運(yùn)算器執(zhí)行外 A，就可以立刻執(zhí)行 B 而無須等待數(shù)據(jù)載入。如果程序一直是順序的，那么這個(gè)過程就可以一直進(jìn)行下去，效率會(huì)很高。但是一旦遇到分支，那么可能執(zhí)行完 A 下一步要執(zhí)行的是 C，但是載入的數(shù)據(jù)是 B，這時(shí)候就要把流水線清空（因?yàn)楹竺孑d入的東西都錯(cuò)了），然后重新載入 C 所需要的數(shù)據(jù)，這就帶來了很大的性能影響。為此人們常常用『分支預(yù)測』這一技術(shù)來解決（分支預(yù)測是另一個(gè)話題這里不展開），但是對于這類只需要判斷一次的條件語句來說，其實(shí)有更好的方法。

處理器有一條指令支持 if(Test) Dest <- Src 的操作，也就是說可以不用跳轉(zhuǎn)，利用條件代碼來進(jìn)行賦值，于是編譯器在可能的時(shí)候會(huì)把上面的 goto 程序改成如下：

result = Then_Expr;

eval = Else_Expr;

nt = !Test;

if (nt) result = eval;

return result;

具體的做法是：反正一共就兩個(gè)分支，我都算出行不行，然后利用上面的條件指令來進(jìn)行賦值，這樣就完美避免了因?yàn)榉种Э赡軒淼男阅軉栴}（需要清空流水線），像下面這樣，同樣 %rdi 中保存了參數(shù) x，%rsi 中保存了參數(shù) y，而 %rax 一般用來存儲(chǔ)返回值：

absdiff:

    movq    %rdi, %rax  # x

    subq    %rsi, %rax  # result = x-y

    movq    %rsi, %rdx

    subq    %rdi, %rdx  # eval = y-x

    cmpq    %rsi, %rdi  # x:y

    cmovle  %rdx, %rax  # if <=, result = eval

    ret

這個(gè)方法好是好，但是也有一些情況并不適用于：

• 因?yàn)闀?huì)把兩個(gè)分支的運(yùn)算都提前算出來，如果這兩個(gè)值都需要大量計(jì)算的話，就得不償失了，所以需要分支中的計(jì)算盡量簡單。
• 另外在涉及指針操作的時(shí)候，如 val = p ? *p : 0;，因?yàn)閮蓚€(gè)分支都會(huì)被計(jì)算，所以可能導(dǎo)致奇怪問題出現(xiàn)
• 最后一種就是如果分支中的計(jì)算是有副作用的，那么就不能這樣弄 val = x > 0 ? x*= 7 : x+= 3;，這種情況下，因?yàn)槎加?jì)算了，那么 x 的值肯定就不是我們想要的了。

循環(huán)

先來看看并不那么常用的 Do-While 語句以及對應(yīng)使用 goto 語句進(jìn)行跳轉(zhuǎn)的版本：

// Do While 的 C 語言代碼

long pcount_do(unsigned long x)

{

long result = 0;

do {

        result += x & 0x1;

        x >>= 1;

    } while (x);

return result;

}



// Goto 版本

long pcount_goto(unsigned long x)

{

long result = 0;

loop:

    result += x & 0x1;

    x >>= 1;

if (x) goto loop;

return result;

}

這個(gè)函數(shù)計(jì)算參數(shù) x 中有多少位是 1，翻譯成匯編如下：

    movl    $0, %eax    # result = 0

.L2:                    # loop:

    movq    %rdi, %rdx

    andl    $1, %edx    # t = x & 0x1

    addq    %rdx, %rax  # result += t

    shrq    %rdi        # x >>= 1

    jne     .L2         # if (x) goto loop

    rep; ret

其中 %rdi 中存儲(chǔ)的是參數(shù) x，%rax 存儲(chǔ)的是返回值。換成更通用的形式如下：

// C Code

do

    Body

while (Test);



// Goto Version

loop:

Body

if (Test)

goto loop

而對于 While 語句的轉(zhuǎn)換，會(huì)直接跳到中間，如：

// C While version

while (Test)

    Body



// Goto Version

goto test;

loop:

    Body

test:

if (Test)

goto loop;

done:

如果在編譯器中開啟 -O1 優(yōu)化，那么會(huì)把 While 先翻譯成 Do-While，然后再轉(zhuǎn)換成對應(yīng)的 Goto 版本，因?yàn)?Do-While 語句執(zhí)行起來更快，更符合 CPU 的運(yùn)算模型。

接著來看看最常用的 For 循環(huán)，也可以一步一步轉(zhuǎn)換成 While 的形式，如下

// For

for (Init; Test; Update)

    Body



// While Version

Init;

while (Test) {

    Body

    Update;

}

Switch 語句

最后我們來看看最復(fù)雜的 switch 語句，這種類型的語句一次判斷會(huì)有多種可能的跳轉(zhuǎn)路徑（知道 CPU 的分支預(yù)測會(huì)多抓狂嗎）。這里用一個(gè)具體的例子來進(jìn)行講解：

long switch_eg (long x, long y, long z){

long w = 1;

switch (x) {

case 1:

            w = y*z;

break;

case 2:

            w = y/z;

// fall through

case 3:

            w += z;

break;

case 5:

case 6:

            w -= z;

break;

default:

            w = 2;

    }

return w;

}

這個(gè)例子中包含了大部分比較特殊的情況：

• 共享的條件：5 和 6
• fall through：2 也會(huì)執(zhí)行 3 的部分（這個(gè)要小心，一般來說不這么搞，如果確定要用，務(wù)必寫上注釋）
• 缺失的條件：4

具體怎么辦呢？簡單來說，使用跳轉(zhuǎn)表（你會(huì)發(fā)現(xiàn)表的解決方式在很多地方都有用：虛函數(shù)，繼承甚至動(dòng)態(tài)規(guī)劃），可能會(huì)類似如下匯編代碼，這里 %rdi 是參數(shù) x，%rsi 是參數(shù) y，%rdx 是參數(shù) z, %rax 是返回值

switch_eg:

    movq    %rdx, %rcx

    cmpq    $6, %rdi    # x:6

    ja      .L8

    jmp     *.L4(, %rdi, 8)

跳轉(zhuǎn)表為

.section    .rodata

    .align 8

.L4:

    .quad   .L8 # x = 0

    .quad   .L3 # x = 1

    .quad   .L5 # x = 2

    .quad   .L9 # x = 3

    .quad   .L8 # x = 4

    .quad   .L7 # x = 5

    .quad   .L7 # x = 6

這里需要注意，我們先跟 6 進(jìn)行比較（因?yàn)?6 是最大的），然后利用 ja 指令進(jìn)行跳轉(zhuǎn)，為什么，因?yàn)槿绻秦?fù)數(shù)的話，ja 是處理無符號(hào)數(shù)的，所以負(fù)數(shù)情況肯定大于 6，于是直接利用 ja 跳轉(zhuǎn)到 default 的分支。

然后下一句 jmp *.L4(,%rdi, 8) # goto *JTab[x]，是一個(gè)間接跳轉(zhuǎn)，通過看上面的跳轉(zhuǎn)列表來進(jìn)行跳轉(zhuǎn)。

比如說，直接跳轉(zhuǎn) jmp .L8，就直接跳到 .L8 所在的標(biāo)簽，也就是 x = 0

如果是 jmp *.L4(,%rdi,8) 那么就先找到 .L4 然后往后找 8 個(gè)字節(jié)（或 8 的倍數(shù)），于是就是 0~6 的范圍。

通過上面的例子，我們可以大概了解處理 switch 語句的方式：大的 switch 語句會(huì)用跳轉(zhuǎn)表，具體跳轉(zhuǎn)時(shí)可能會(huì)用到?jīng)Q策樹（if-elseif-elseif-else）

過程調(diào)用

https://www.cs.cmu.edu/~213/lectures/07-machine-procedures.pdf

上一節(jié)中我們學(xué)習(xí)了機(jī)器是如何利用跳轉(zhuǎn)實(shí)現(xiàn)流程控制的，這一節(jié)我們來看一個(gè)更加復(fù)雜的機(jī)制：過程調(diào)用（也就是調(diào)用函數(shù)）具體在 CPU 和內(nèi)存中是怎么實(shí)現(xiàn)的。理解之后，對于遞歸會(huì)有更加清晰的認(rèn)識(shí)。

在過程調(diào)用中主要涉及三個(gè)重要的方面：

1. 傳遞控制：包括如何開始執(zhí)行過程代碼，以及如何返回到開始的地方
2. 傳遞數(shù)據(jù)：包括過程需要的參數(shù)以及過程的返回值
3. 內(nèi)存管理：如何在過程執(zhí)行的時(shí)候分配內(nèi)存，以及在返回之后釋放內(nèi)存

以上這三點(diǎn)，都是憑借機(jī)器指令實(shí)現(xiàn)的

棧結(jié)構(gòu)

在 x86-64 中，所謂的棧，實(shí)際上一塊內(nèi)存區(qū)域，這個(gè)區(qū)域的數(shù)據(jù)進(jìn)出滿足先進(jìn)后出的原則。越新入棧的數(shù)據(jù)，地址越低，所以棧頂?shù)牡刂肥亲钚〉?。下圖中箭頭所指的就是寄存器 %rsp 的值，這個(gè)寄存器是棧指針，用來記錄棧頂?shù)奈恢谩?/p>

image.png

我們假設(shè)一開始 %rsp 為紅色，對于 push 操作，對應(yīng)的是 pushq Src 指令，具體會(huì)完成下面三個(gè)步驟：

1. 從地址 Src 中取出操作數(shù)
2. 把 %rsp 中的地址減去 8（也就是到下一個(gè)位置）
3. 把操作數(shù)寫入到 %rsp 的新地址中

這個(gè)時(shí)候 %rsp 就對應(yīng)藍(lán)色。

重來一次，假設(shè)一開始 %rsp 為紅色，對于 pop 操作，對應(yīng)的是 popq Dest 指令，具體會(huì)完成下面三個(gè)步驟：

1. 從 %rsp 中存儲(chǔ)的地址中讀入數(shù)據(jù)
2. 把 %rsp 中的地址增加 8（回到上一個(gè)位置）
3. 把剛才取出來的值放到 Dest 中（這里必須是一個(gè)寄存器）

這時(shí)候 %rsp 就對應(yīng)黃色。

調(diào)用方式

了解了棧的結(jié)構(gòu)之后，我們先通過一個(gè)函數(shù)調(diào)用的例子來具體探索一下過程調(diào)用中的一些細(xì)節(jié)。

// multstore 函數(shù)

void multstore (long x, long, y, long \*dest)

{

long t = mult2(x, y);

    *dest = t;

}



// mult2 函數(shù)

long mult2(long a, long b)

{

long s = a * b;

return s;

}

image.png

對應(yīng)的匯編代碼為：

0000000000400540 <multstore>:

    \# x 在 %rdi 中，y 在 %rsi 中，dest 在 %rdx 中

    400540: push    %rbx            # 通過壓棧保存 %rbx

    400541: mov     %rdx, %rbx      # 保存 dest

    400544: callq   400550 <mult2>  # 調(diào)用 mult2(x, y)

    \# t 在 %rax 中

    400549: mov     %rax, (%rbx)    # 結(jié)果保存到 dest 中

    40054c: pop     %rbx            # 通過出?；謴?fù)原來的 %rbx

    40054d: retq                    # 返回



0000000000400550 <mult2>:

    \# a 在 %rdi 中，b 在 %rsi 中

    400550: mov     %rdi, %rax      # 得到 a 的值

    400553: imul    %rsi, %rax      # a * b

    \# s 在 %rax 中

    400557: retq                    # 返回

可以看到，過程調(diào)用是利用棧來進(jìn)行的，通過 call label 來進(jìn)行調(diào)用（先把返回地址入棧，然后跳轉(zhuǎn)到對應(yīng)的 label），返回的地址，將是下一條指令的地址，通過 ret 來進(jìn)行返回（把地址從棧中彈出，然后跳轉(zhuǎn)到對應(yīng)地址）

我們『單步調(diào)試』來看看具體調(diào)用的過程

image

1. 在執(zhí)行到 400544 那一行的時(shí)候 %rsp 指向棧頂（存儲(chǔ)著棧頂?shù)牡刂罚?rip 指向當(dāng)前要執(zhí)行的指令（也就是 400544）
2. 在上一步操作完成之后，因?yàn)樘D(zhuǎn)的關(guān)系，%rip 指向 mult2 函數(shù)開始的地方（也就是 400550），之前的壓棧操作也使得棧頂改變（返回值的位置），于是 %rsp 對應(yīng)進(jìn)行改變
3. 接著執(zhí)行到了 retq 那句，這個(gè)時(shí)候要做的就是從棧中取出棧頂位置（這樣就可以從跳轉(zhuǎn)處繼續(xù)了），然后對寄存器做對應(yīng)的修改
4. 最后恢復(fù)到原來的 multstore 函數(shù)中繼續(xù)執(zhí)行

我們可以發(fā)現(xiàn)，函數(shù)調(diào)用中會(huì)利用 %rax 來保存過程調(diào)用的返回值，以便程序繼續(xù)運(yùn)行的。這就是基本的過程調(diào)用的控制流程。

那么過程調(diào)用的參數(shù)會(huì)放在哪里呢？如果參數(shù)沒有超過六個(gè)，那么會(huì)放在：%rdi, %rsi, %rdx, %rcx, %r8, %r9 中。如果超過了，會(huì)另外放在一個(gè)棧中。而返回值會(huì)放在 %rax 中。

既然是利用棧來進(jìn)行函數(shù)調(diào)用，自然而然就可以推廣到遞歸的情況，而對于每個(gè)過程調(diào)用來說，都會(huì)在棧中分配一個(gè)幀 Frames。每一幀里需要包含：

• 返回信息
• 本地存儲(chǔ)（如果需要）
• 臨時(shí)空間（如果需要）

整一幀會(huì)在過程調(diào)用的時(shí)候進(jìn)行空間分配，然后在返回時(shí)進(jìn)行回收，在 x86-64/Linux 中，棧幀的結(jié)構(gòu)是固定的，當(dāng)前的要執(zhí)行的棧中包括：

• Argument Build: 需要使用的參數(shù)
• 如果不能保存在寄存器中，會(huì)把一些本地變量放在這里
• 已保存的寄存器上下文
• 老的棧幀的指針（可選）

而調(diào)用者的棧幀則包括：

• 返回地址（因?yàn)?call 指令被壓入棧的）
• 調(diào)用所需的參數(shù)

具體如下圖所示：

image

ABI

image.png

image.png

image.png

image.png

遞歸

有了前面的的基礎(chǔ)，要理解遞歸就簡單很多了，直接上例子

long pcount_r(unsigned long x) {

if (x == 0)

return 0;

else

return (x & 1) + pcount_r(x >> 1);

}

對應(yīng)的匯編代碼為：

pcount_r:

    mov     $0, %eax

    testq   %rdi, %rdi

    je      .L6

    push    %rbx

    movq    %rdi, %rbx

    andl    $1, %ebx

    shrq    %rdi

    call    pcount_r

    addq    %rbx, %rax

    popq    %rbx

.L6:

    rep; ret

實(shí)際執(zhí)行的過程中，會(huì)不停進(jìn)行壓棧，直到最后返回，所以遞歸本身就是一個(gè)隱式的棧實(shí)現(xiàn)，但是系統(tǒng)一般對于棧的深度有限制（每次一都需要保存當(dāng)前棧幀的各種數(shù)據(jù)），所以一般來說會(huì)把遞歸轉(zhuǎn)換成顯式棧來進(jìn)行處理以防溢出。

數(shù)據(jù)存儲(chǔ)

https://www.cs.cmu.edu/~213/lectures/08-machine-data.pdf

上一節(jié)我們了解了過程調(diào)用是如何用機(jī)器代碼實(shí)現(xiàn)的，這一節(jié)我們來看看基本的數(shù)據(jù)是如何存儲(chǔ)在計(jì)算機(jī)中。

第一講中我們已經(jīng)學(xué)到，不同的數(shù)據(jù)類型所需要的字節(jié)數(shù)是不同的，我們先來回顧一下這個(gè)表格：

我們舉幾個(gè)具體的例子就一目了然了：

image

既然是連續(xù)的地址空間，就有很多不同的訪問方式，比方對于 int val[5] 來說

多維數(shù)組

對于多維的數(shù)組，基本形式是 T A[R][C]，R 是行，C 是列，如果類型 T 占 K 個(gè)字節(jié)的話，那么數(shù)組所需要的內(nèi)存是 R*C*K 字節(jié)。具體在內(nèi)存里的排列方式如下：

[圖片上傳失敗...(image-a50067-1553428110617)]

具體訪問的方式如下：

int get_a_digit(int index, int dig)

{

return A[index][dig];

}

對應(yīng)的匯編代碼為，這里假設(shè) C = 5

leaq    (%rdi, %rdi, 4), %rax   # 5 * index

addl    %rax, %rsi              # 5 * index + dig

movl    A(, %rsi, 4), %eax      # M[A + 4*(5*index+dig)]

還有另外一種組合數(shù)組的方式，不是連續(xù)分配，而是存儲(chǔ)每個(gè)數(shù)組的起始地址。與之前連續(xù)分配唯一不同之處在于計(jì)算元素位置時(shí)候不同行對應(yīng)不連續(xù)的起始地址（可能分散在內(nèi)存的不同部分）。這兩種方式在 C 語言中看起來差不多，但對應(yīng)的匯編代碼則完全不同。

結(jié)構(gòu)體

結(jié)構(gòu)體是 C 語言中非常常用的一種機(jī)制，具體在內(nèi)存中是如何存放的呢？我們通過具體的例子來進(jìn)行學(xué)習(xí)。比如我們有這樣一個(gè)結(jié)構(gòu)體：

struct rec 

{

int a[4];

size_t i;       

struct rect *next;

};

那么在內(nèi)存中的排列是

image

如果我們換一下結(jié)構(gòu)體元素的排列順序，可能就會(huì)出現(xiàn)和我們預(yù)想不一樣的結(jié)果，比如

struct S1

{

char c;

int i[2];

double v;

} *p;

因?yàn)樾枰獙R的緣故，所以具體的排列是這樣的：

image

具體對齊的原則是，如果數(shù)據(jù)類型需要 K 個(gè)字節(jié)，那么地址都必須是 K 的倍數(shù)，比方說這里 int 數(shù)組 i 需要是 4 的倍數(shù)，而 v 則需要是 8 的倍數(shù)。

感謝網(wǎng)友『光河』的補(bǔ)充：文中講“具體對齊的原則是，如果數(shù)據(jù)類型需要 K 個(gè)字節(jié)，那么地址都必須是 K 的倍數(shù)”——這只是windows的原則，而Linux中的對齊策略是“2字節(jié)數(shù)據(jù)類型的地址必須為2的倍數(shù)，較大的數(shù)據(jù)類型（int,double,float）的地址必須是4的倍數(shù)”

為什么要這樣呢，因?yàn)閮?nèi)存訪問通常來說是 4 或者 8 個(gè)字節(jié)位單位的，不對齊的話訪問起來效率不高。具體來看的話，是這樣：

• 1 字節(jié)：char, …
  • 沒有地址的限制
• 2 字節(jié)：short, …
  • 地址最低的 1 比特必須是 0
• 4 字節(jié)：int, float, …
  • 地址最低的 2 比特必須是 00
• 8 字節(jié)：double, long, char *, …
  • 地址最低的 3 比特必須是 000
• 16 字節(jié)：long double (GCC on Linux)
  • 地址最低的 4 比特必須是 0000

對于一個(gè)結(jié)構(gòu)體來說，所占據(jù)的內(nèi)存空間必須是最大的類型所需字節(jié)的倍數(shù)，所以可能需要占據(jù)更多的空間，比如：

struct S2 {

double v;

int i[2];

char c;

} *p;

image

根據(jù)這種特點(diǎn)，在設(shè)計(jì)結(jié)構(gòu)體的時(shí)候可以采用一些技巧。例如，要把大的數(shù)據(jù)類型放到前面，加入我們有兩個(gè)結(jié)構(gòu)體：

struct S4 {

char c;

int i;

char d;

} *p;



struct S5 {

int i;

char c;

char d;

} *p;

對應(yīng)的排列是：

image

這樣我們就通過不同的排列，節(jié)約了 4 個(gè)字節(jié)空間，如果這個(gè)結(jié)構(gòu)體要被復(fù)制很多次，這也是很可觀的內(nèi)存優(yōu)化。

緩沖區(qū)溢出

https://www.cs.cmu.edu/~213/lectures/09-machine-advanced.pdf

這一節(jié)是機(jī)器代碼的最后一部分，主要說說由緩沖區(qū)溢出引起的攻防大戰(zhàn)。我們先來看看程序在內(nèi)存中是如何組織的（x86-64 Linux）

image

最上面是運(yùn)行時(shí)棧，有 8MB 的大小限制，一般用來保存局部變量。然后是堆，動(dòng)態(tài)的內(nèi)存分配會(huì)在這里處理，例如 malloc(), calloc(), new() 等。然后是數(shù)據(jù)，指的是靜態(tài)分配的數(shù)據(jù)，比如說全局變量，靜態(tài)變量，常量字符串。最后是共享庫等可執(zhí)行的機(jī)器指令，這一部分是只讀的。

可以見到，棧在最上面，也就是說，棧再往上就是另一個(gè)程序的內(nèi)存范圍了，這種時(shí)候我們就可以通過這種方式修改內(nèi)存的其他部分了。

舉個(gè)例子

typedef struct 

{

    int a[2];

    double d;

} struct_t;

double fun(int i)

{

    volatile struct_t s;

    s.d = 3.14;

    s.a[i] = 1073741824; // 可能會(huì)越界

    return s.d;

}

不同的 i 可能的執(zhí)行結(jié)果是：

• fun(0) -> 3.14
• fun(1) -> 3.14
• fun(2) -> 3.1399998664856
• fun(3) -> 2.00000061035156
• fun(4) -> 3.14
• fun(6) -> Segmentation fault

之所以會(huì)產(chǎn)生這種錯(cuò)誤，是因?yàn)樵L問內(nèi)存的時(shí)候跨過了數(shù)組本身的界限修改了 d 的值。你沒看錯(cuò)，這是個(gè)大問題！如果不檢查輸入字符串的長度，就很容易出現(xiàn)這種問題，尤其是針對在棧上有界限的字符數(shù)組。

在 Unix 中，gets() 函數(shù)的實(shí)現(xiàn)是這樣的：

// 從 stdin 中獲取輸入

char *gets(char *dest)

{

    int c = getchar();

    char *p = dest;

    while (c != EOF && c != '\n')

    {

        *p++ = c;

        c = getchar();

    }

    *p = '\0';

    return dest;

}

可以看到并沒有去檢測最多能讀入多少字符（于是很容易出問題），類似的情況還在 strcpy, strcat, scanf, fscanf, sscanf 中出現(xiàn)。比如說

void echo() {

    char buf[4]; // 太小

    gets(buf);

    puts(buf);

}

void call_echo() {

    echo();

}

我們來測試一下這個(gè)函數(shù)，可能的結(jié)果是：

unix> ./echodemo

 Input: 012345678901234567890123

Output: 012345678901234567890123

unix> ./echodemo

 Input: 0123456789012345678901234

Segmentation Fault

為什么明明在 echo() 中聲明 buf 為 4 個(gè) char，居然一開始輸入這么多都沒問題？我們到匯編代碼里去看看：

00000000004006cf <echo>:

    4006cf: 48 83 ec 18         sub   $0x18, %rsp

    4006d3: 48 89 e7            mov   %rsp, %rdi

    4006d6: e8 a5 ff ff ff      callq 400680 <gets>

    4006db: 48 89 e7            mov   %rsp, %rdi

    4006de: e8 3d fe ff ff      callq 400520 <puts@plt>

    4006e3: 48 83 c4 18         add   $0x18, %rsp

    4006e7: c3                  retq

# call_echo 部分

    4006e8: 48 83 ec 08         sub   $0x8, %rsp

    4006ec: b8 00 00 00 00      mov   $0x0, %eax

    4006f1: e8 d9 ff ff ff      callq 4006cf <echo>

    4006f6: 48 83 c4 08         add   $0x8, %rsp

    4006fa: c3                  retq

我們看 4006cf 這一行，可以發(fā)現(xiàn)實(shí)際上給 %rsp 分配了 0x18 的空間，所以可以容納不止 4 個(gè) char。

在調(diào)用 gets 函數(shù)之前（第 4006d6 行），內(nèi)存中棧幀示意圖為：

image

結(jié)合上面代碼可以看到，call_echo 棧幀中保存著調(diào)用之前執(zhí)行指令的地址 4006f6，用于返回之后繼續(xù)執(zhí)行。我們輸入字符串 01234567890123456789012 之后，棧幀中緩沖區(qū)被填充，如下：

image

雖然緩沖區(qū)溢出了，但是并沒有損害當(dāng)前的狀態(tài)，程序還是可以繼續(xù)運(yùn)行（也就是沒有出現(xiàn)段錯(cuò)誤），但是如果再多一點(diǎn)的話，也就是輸入 0123456789012345678901234，內(nèi)存中的情況是這樣的：

image

就把返回地址給覆蓋掉了，當(dāng) echo 執(zhí)行完成要回到 call_echo 函數(shù)時(shí)，就跳轉(zhuǎn)到 0x400034 這個(gè)內(nèi)容未知的地址中了。也就是說，通過緩沖區(qū)溢出，我們可以在程序返回時(shí)跳轉(zhuǎn)到任何我們想要跳轉(zhuǎn)到的地方！攻擊者可以利用這種方式來執(zhí)行惡意代碼！

image.png

那么我們現(xiàn)在來看看，怎么處理緩沖區(qū)溢出攻擊，有幾種方式：

• 好好寫代碼，盡量不讓緩沖區(qū)異常
• 程序容易出問題，那么提供系統(tǒng)層級的保護(hù)
• 編譯器也可以來個(gè)認(rèn)證(stack canaries)

第一種，避免緩沖區(qū)溢出，我們用更安全的方法，如：fgets, strncpy 等等。

image.png

第二種，棧的位置不確定，讓緩沖區(qū)溢出沒辦法影響到，并且每次位置都不一樣，就不怕被暴力破解。并且也可以把一段內(nèi)存標(biāo)記為只讀，那么就避免因?yàn)榫彌_區(qū)溢出而導(dǎo)致的重寫。

image.png

image.png

第三種，使用認(rèn)證機(jī)制(Stack Canaries)。簡單來說，就是在超出緩沖區(qū)的位置加一個(gè)特殊的值，如果發(fā)現(xiàn)這個(gè)值變化了，那么就知道出問題了。

image.png

image.png

但是，除了緩沖區(qū)溢出，還有另一種攻擊的方式，稱為返回導(dǎo)向編程[4]?？梢岳眯薷囊延械拇a，來繞過系統(tǒng)和編譯器的保護(hù)機(jī)制，攻擊者控制堆棧調(diào)用以劫持程序控制流并執(zhí)行針對性的機(jī)器語言指令序列（稱為Gadgets）。每一段 gadget 通常結(jié)束于 return 指令，并位于共享庫代碼中的子程序。系列調(diào)用這些代碼，攻擊者可以在擁有更簡單攻擊防范的程序內(nèi)執(zhí)行任意操作。