CSAPP期末複習（更新ing）

CSAPP期末快速複習（更新ing）

本人有關CSAPP的部落格連結：

私人部落格

CSDN

内容基本上差不多

主要内容

1. 概論
2. 資訊的表示
3. 機器級的表示
4. 連結
5. I/O

概論

1. 上下文：上下文是一個狀态，包含運作程序所需的所有狀态資訊，程序切換通過切換上下文完成
2. 編譯過程（連結中會再次提到）：源程式 預處理-> 文本 編譯->彙程式設計式 彙編->可重定位目标檔案 連結->可執行檔案
3. 指令集架構：每條機器代碼的效果。微體系結構：處理器的具體實作
4. 存儲器層次結構：從上至下，通路速度越來越慢，容量越來越大。課本P10圖。
5. 作業系統：是應用程式和硬體之間的一層軟體
6. 作業系統的兩個基本功能：防止硬體被失控的應用程式濫用；向應用程式提供簡單的、一緻的、有效的接口來控制硬體裝置
7. Amdahl定律：P16，了解即可
8. 三個層次的并發：線程級别，指令級别（超标量處理器：在一個時鐘機關内執行多個指令），單指令、多資料并行
9. 三個層次的抽象：檔案，虛拟記憶體，程序

練習：看一下P16練習1.1，不重要，了解即可

資訊的表示

1. 為什麼使用二進制：便于表示、存儲、傳輸
2. 将學習的三種資料類型：有符号整數，無符号整數，浮點數
3. 進制轉換：略（數電裡面學過了）
4. 32位程式與64位程式的不同：32位程式

   long

   類型為4位元組，指針類型為4位元組；64位程式

   long

   類型為8位元組，指針類型為8位元組；尋址空間大小不同：32位程式最多尋址 2 32 2^{32} 232即4G記憶體，64位能尋址 2 64 2^{64} 264記憶體；64位機器向下相容32位機器
5. 大端法、小端法：大端法高位在記憶體低處，小端法低位在記憶體高處。直覺表示為，小端法和平常的數字表示順序是反過來的。
6. 布爾環：

   a ^ a = 0

   ，見課本第38頁練習2.10。
7. 邏輯運算與位運算的不同：邏輯計算隻要得出了結果，就不會繼續計算。例如

   a && b

   ，隻要

   a

   為假，則

   b

   不會執行。
8. 移位運算：特殊的隻有右移。邏輯位移補符号位，算術位移補0。
9. 移位運算切記：移位的大小

   K

   絕對不能大于等于資料類型的位元組數

   M

   ，因為實際的移位大小為

   K mod M

   ，例如

   int << 32

   ，結果是

   32 mod 32 = 0

   ，即不産生操作，應當更正為

   (int << 31) << 1

10. 整數表示隻需要記住：有符号整數與無符号整數僅僅隻有解讀方式不同，它們的位級表示是一樣的，運算過程基本上也是一緻的（乘法在底層使用的機器指令不一樣，但是最終的位級表示是一樣的）。
11. 有符号整數的表示範圍是不對稱的：

    -2^(k-1) ~ 2^(k-1)-1

    ，例如int類型，範圍為

    -2^31~2^31-1

    。
12. 有符号整數的負數形式采用補碼表示。原因：其他的負數表達方式都有存在+0與-0的問題。
13. 有符号整數的最小的負數表達形式的補碼表示是自身。例如

    -INT_MIN=INT_MIN

    。至于為什麼，寫一下它的補碼形式就知道了。是以它特别特殊。
14. 無符号數與有符号數的快速轉化：

    k

    位的整數，

    無符号數=有符号數+2^k

    ，例如，

    [1001]

    有符号數表示為

    -2^3+2^0=-7

    ，無符号數表示為

    2^3+2^0=9

    ，相差

    2^4=16

15. 截斷與擴充：截斷就和取模差不多，擴充要注意是不是有符号數，因為有符号數的擴充要算上符号位。
16. 乘法：P71
17. 除法公式背：P74
18. 加法溢出檢測：如果加數均為正數，得出負數或者0，則說明溢出。不可使用

    c = a + b; c - b == a

    的方法進行判斷：課本第65頁練習題2.31
19. 乘除法溢出檢測：課本第68頁2.35
20. 浮點數的表示：P79
21. 當将浮點數當成整數進行表示時，大小順序不變：課本P81
22. 浮點數所能準确表示的最大正整數：課本P83練習題
23. 必須了解：P82最後一段話
24. 向偶數舍入：若是中間值，向偶數舍入，否則向更近的那一邊舍入。課本P84練習。
25. 浮點運算：加法：可交換、單調性、不可結合（由于舍入，将丢失資訊）；乘法：可交換，單調性（整數乘法不具有單調性（溢出，正數相乘可能得到負數）），不可結合，不具有加法配置設定性（ 1 e 20 ∗ 1 e 20 − l e 20 ∗ 1 e 20 = N a N 1e20*1e20-le20*1e20=NaN 1e20∗1e20−le20∗1e20=NaN（溢出） 1 e 20 ∗ ( 1 e 20 − 1 e 20 ) = 0.0 1e20*(1e20-1e20)=0.0 1e20∗(1e20−1e20)=0.0）

機器級表示

A&T彙編

• 寄存器

  寄存器分為三類（至少）：被調用者儲存寄存器，調用者儲存寄存器，棧指針

  被調用者儲存寄存器，即被調用的函數有義務使得這些寄存器的值在過程結束的時候保持和過程開始時候的值一樣，即有義務儲存這些寄存器的值。調用者儲存寄存器，即調用者有義務自己儲存這些寄存器的值。棧指針，即

  rsp指針

  ，指向棧頂。具體看課本P120圖

• 尋址方式

  看課本P121表格并完成其後的練習

• MOV族

  有MOV、MOVZ、MOVS三種類

  MOVZ：小->大。多出來的空間用0補足

  MOVS：小->大。多出來的空間用符号位補足

  注意：

1. MOV的源和目的不能都是記憶體位址，至少有一個寄存器。

2. movabsq

   是一個很特殊的指令，特殊在于會将寄存器的高位用0補足
3. MOVS有

   movslq

   ，而MOVZ沒有

   movzlq

   ，因為

   movabsq

   已經完成了該功能
4. 特殊的指令：

   cltq

   ，将

   eax

   擴充為

   rax

   ，MOVS的指令

• POP、PUSH

  POP和PUSH可以由其他指令複合完成。使用POP和PUSH指令的唯一目的是減少機器指令位元組數。

  看P127頁表

  注意，棧頂在低位位址。看課本P13圖，注意觀察箭頭方向

  是以，配置設定空間要将rsp指針減去相應的大小。

• 算術操作、邏輯操作

  看課本P129表

  注意，左移的兩個表達式效果是一樣的。

  注意下面一段話，leaq的靈活使用。

• 條件碼

  這個部落格是基本介紹

  這個部落格是詳細一點的介紹

• 跳轉

  比較特殊的是

  jmp

  ，有兩種跳轉方式，直接跳轉和間接跳轉。（在實踐的時候發現，我好像隻能對寄存器進行間接跳轉。）看課本P139表

結構

過程

資料

連結

1. 連結是将各種代碼和資料片段收集并組合成為一個單一檔案的過程
2. 連結可以執行于編譯時，也可以執行于加載時，甚至運作于運作時。詳見課本介紹
3. 一個程式的編譯包括：預處理，編譯，彙編，連結。使用

   cpp

   進行預處理，使用

   cc1

   進行編譯，使用

   as

   進行彙編，使用

   ld

   進行連結

• cc1，第三個字元是阿拉伯字母1，而不是英文字母l

1. shell會調用作業系統中一個叫做加載器的函數，将可執行檔案的代碼和資料複制到記憶體，然後将核心的控制權轉交給該程式。
2. 使用

   gcc -E

   進行預處理，使用

   gcc -S

   進行編譯，使用

   gcc -c

   進行彙編，使用

   gcc -o

   進行可執行檔案的生成
3. 為了構造可執行檔案，連結器必須完成兩個主要任務：符号解析：将每個符号引用和符号定義關聯起來；重定位：将每一個符号定義與記憶體位置關聯起來，進而重定位section
4. 連結器對整個程式一無所知，大部分工作都由産生目标檔案的編譯器與彙編器完成
5. 目标檔案分為：可重定位目标檔案(.o)，可執行目标檔案，共享目标檔案(.so)（關于.so檔案，在gcc手冊中有詳細介紹）
6. 目标檔案的格式為ELF。參考資料1 參考資料2

   

• ELF

1. .text，正文，已經編譯的機器代碼
2. .rodata，read only data
3. .data，已經初始化的全局和靜态變量（不包含局部變量）
4. .bss，未初始化的全局和靜态變量。該節不占據實際空間，僅僅是一個占位符。目标檔案中未初始化的變量不需要占據空間，運作時在記憶體中将其指派為0，也不占據可執行檔案的空間。
5. .symtable，符号表，存放函數、全局變量的資訊。每個可重定位的目标檔案都有一張符号表，除非使用STRIP指令去除。注意，其不包含局部變量
6. .rel.text：一個.texg section中的位置清單。連結器會修改這些位置。任何外部函數或全局變量的位置都需要修改，任何本地函數的指令不需要修改。可執行目标檔案中不需要重定位資訊
7. .rel.data：所有的全局變量與外部定義函數的重定位資訊。
8. .debug：調試符号表，隻有使用

   -g

   參數才會出現。條目中包含局部變量、全局變量、原始C檔案。
9. .line：原始C檔案與機器指令的行号的映射
10. .strtab，字元串表

以上重要的有：1，2，3，4，5

可以使用

readelf

指令讀取ELF檔案

• 符号

  連結器的上下文中有三種符号：

1. 全局符号：能被其他子產品引用的符号。對應于非靜态的C函數與全局變量。在EFL檔案中放在.data、.bss中
2. 外部符号：由其他子產品定義的全局符号
3. 局部符号：不能被其他子產品引用的局部符号，包括static屬性的C函數與全局變量。在該子產品的任何位置可見！與局部變量區分！

連結器的符号和變量不是一個概念。.symtab中不包含任何局部變量（非靜态）。這些局部變量（非靜态）在棧中被管理。

定義為static的局部變量不是在棧中管理的，編譯器在

.data

中為其配置設定空間，并建立一個有唯一名字的符号。

例如在兩個函數中都定義了static變量x，那麼編譯器會建立兩個符号：

x.1

、

x.2

• 符号表

  有三個僞section，沒有對應的條目：

  ABS：不應該被重定位的符号

  UNDEF：未定義符号

  COMMON：未配置設定位置的未初始化的資料（未初始化的全局變量）（.bss：未初始化的靜态變量以及初始化為0的全局或靜态變量）

  （未進行初始化的全局變量在COMMON中，未初始化的靜态變量在.bss中）

  （完成課本P470練習）

• 符号解析

  連結器解析符号引用的方法是将每個引用與它輸入的可重定位目标檔案的符号表中的一個确定的符号定義關聯起來。

  編譯器值允許每個子產品中每個局部符号有一個定義，還要確定靜态局部變量有唯一的名字。

  當編譯器遇到一個不在目前子產品中定義的符号時，會假設該符号時在其他某個子產品中定義的，然後生成一個連結器符号表條目，将其交與連結器處理。

  多個目标檔案可能會定義相同名字的全局符号。連結器要麼标志為錯誤，要麼以某種方式選出一個定義并抛棄其他定義。（C++中的重載）

• 解析全局符号

  隻有全局符号才有強弱的概念

  函數和已初始化的全局變量是強符号，未初始化的全局變量是弱符号

  使用以下規則處理多重定義的符号：

1. 不允許同名的強符号
2. 強符号和弱符号同名，選擇強符号

3. 多個弱符号，随機選擇

   規則2和規則3的連續應用會造成一些運作時錯誤

使用

gcc -fno-common

調用連結器，告訴連結器，在遇到多個全局符号的時候，觸發一個錯誤

• 與靜态庫連結

  标準C函數放在了一個單獨的、可重定位的目标子產品中，優點是可以将編譯器的實作與标準函數的實作分離，缺點是每個可執行檔案都包含着一個标準函數集合的完全副本（極大浪費了磁盤空間），并且每個程式都将自己的函數的副本放在記憶體中（極大地浪費了記憶體空間）。

  靜态庫的概念用于解決上述缺點

  相關函數被編譯為單獨的子產品，然後封裝為單獨的靜态庫檔案。連結時，連結器隻複制被程式引用的目标子產品。

使用

AR

工具建立一個靜态庫：

ar rcs lib.a a.o b.o

• 靜态庫解析引用的流程

  在符号解析階段，連結器從左到右掃描指令行上的可重定位目标檔案與archive檔案

  它維護着一個可重定位目标檔案的集合E，一個未解析符号集合U，以及已定義符号集合D

  解析流程：

解析檔案f
	->目标檔案
		-> add f to E, edit U and D
		-> next file
	->archive file
		-> 如果成員檔案m定義了U中的一個引用
			-> add m to E, edit U and D
			-> next file
           

上述流程的缺點：能否成功解析與出現在指令行上的順序密切相關。

原則：将庫檔案放在後面。

（在An introducuction to GCC一書中有較長的描述）

I/O