主要參考: CSAPP
數據
眾所周知計算機內使用二進制儲存數字, 所以最小單位為一個 \(0\) 和 \(1\), 稱為一個比特.
事實上計算機內最常見的是將 \(8\) 個比特放在一起當成一個 \(8\) 位二進制數處理, 稱為一個字節. 一個字節正好可以用一個 \(2\) 位十六進制數表示, 所以經常寫成類似於 0xAB 的形式 (0x 前綴在 C 語言中表示十六進制數, 大小寫無所謂)
內存裏的每個位置都被標號, 這個號叫做地址, 每個地址都儲存着一個字節. 因為地址經常有必須為某個特定的 \(2^m\)
一個變量常常會佔用多個字節, 存儲這些字節需要佔有多個地址, 於是有兩種方法: 低位在低地址和高位在低地址. 前者被稱為小端序, 後者被稱為大端序. 一般使用佔用的最低地址表示這個變量的地址.
大端和小端沒有任何區別, 統一使用一種就不會出問題, 而且都被封裝在底層所以平時基本看不到. 但是由於歷史原因, 現代操作系統在本地大部分都是小端序, 但是網絡傳輸大部分協議都是大端序, 所以基本只有在實現網絡協議時要處理這個神奇的史山.
C 語言基本數據
C 語言中 char 一般用 ASCII 碼儲存, 佔用一個字節 (將鍵盤上的字符或者説可見字符和一些控制符號雙射到 \([0,256)\cap\mathbb N\) 上, 其中可見字符區間為 \([32,126]\cap\mathbb N\)).
冷知識, C 語言沒有任何標準規定必須用 ASCII 碼.
C 語言中 (或者這本書中), 整數最常見的有 short, int, long 三種類型, 分別是 \(2,4,8\) 字節 (大部分 \(64\) 位 Linux 系統下). 有符號數直接儲存二進制低位, 無符號數用補碼儲存 (負數加上 \(2^b\) 再儲存, 均截留低位). 這兩個映射都是 \(\mathbb Z\to\mathbb F_2[X]/(X^b)\)
有兩個操作, 截取和擴展. 事實上環同態 \(\mathbb F_2[X]/(X^b)\to\mathbb F_2[X]/(X^c)\) 在 \(b\ge c\) 時是平凡的, 對應截取操作. 但在 \(b<c\) 是不是良定義的. 於是有兩種擴展: 零擴展和符號擴展. 有符號數直接在高位填 0, 無符號數需要在高位填符號位, 才能保證數值一致.
無符號數的截取低位是標準規定的, 可以放心用. 但是有符號數的截取低位是 UB, 最好不要利用這一點, 否則編譯器會給你一巴掌.
C 語言中浮點數使用 IEEE754 標準, 從高位到低位分為 \(3\)
|
類型
|
\(s\)
|
\(m\)
|
\(e\)
|
|
|
\(1\)
|
\(8\)
|
\(23\)
|
|
|
\(1\)
|
\(11\)
|
\(52\)
|
將 \(\mathbb F_2^s\times\mathbb F_2^m\times\mathbb F_2^e\) 映射到 \(\mathbb R\cup\{-\infty,+\infty,\mathrm{NaN}\}\):
|
區域
|
條件
|
值
|
|
非規格化
|
\(M=0\)
|
\((-1)^S\times2^{-2^{m-1}+2}\times E\times2^{-e}\)
|
|
規格化
|
\(M\in(0,2^m-1)\)
|
\((-1)^S\times2^{M-2^{m-1}+1}\times(1+E\times2^{-e})\)
|
|
無窮大
|
\(M=2^m-1,E=0\)
|
\(+\infty(S=0),-\infty(S=0)\)
|
|
非數
|
\(M=2^m-1,E\neq0\)
|
|
注意這不是單射, \(\mathrm{NaN},0\) 都有多個表示方法, 所以有 +0, -0, +nan, -nan.
只考慮正數, 記 \(\mathrm{eps}=2^{-2^{m-1}+2-e}\), 這是能表示的最小正數. 非規格化數在 \([+0,(2^e-1)\mathrm{eps}]\) 上線性分佈. 而 \(M=1\) 時表示的數在 \([2^e\mathrm{eps},(2^{e+1}-1)\mathrm{eps}]\) 上線性分佈. 換句話説, 在 \([+0,(2^{e+1}-1)\mathrm{eps})\) 的數上加減一個 \(\mathrm{eps}\) 就是在二進制上直接加減 \(1\). 這個範圍外最小的正數用 \(S=0,M=2,E=0\) 表示, 等於 \(2^{e+1}\mathrm{eps}\), 説明上面那個加減的區間能取閉區間, 而再下一個數就要加 \(2\mathrm{eps}\)
總結就是, 在 \(S=0\) 時在二進制上加 \(1\), 就相當於加 \(2^{\max(M-1,0)}\mathrm{eps}\). 而 \(S=1\)
浮點數的計算非常複雜 (一般有專門硬件支持), 要做舍入. 具體規定為向數值上更近的數舍入, 如果在中間則舍入到最低的 \(1\) 更高的那個. 比較時, 若兩個操作數存在 NaN 則恆為 false, 否則因為二進制完美保持了偏序關係, 所以可以看成反碼直接比較. 注意在這個意義下 \(+0=-0\).
現在有很多人在研究 AI 計算時減小位數犧牲精度來提速的.
冷知識, ISO 標準在 C23 才開始規定必須用補碼和 IEEE754, 在此之前編譯器用原碼和反碼都是可以的. 而字符更是沒有任何標準規定使用 ASCII 碼.
C 語言複雜數據
數組連續而無間隙地儲存在內存的一段空間內, 多維數組就是低維數組的數組.
數組名就是指向首個元素的指針, 所以函數傳參傳一個數組就是傳了一個指針. 如果是多維數組, 那麼你需要想辦法讓編譯器知道它的大小, 否則沒辦法定位.
(更清晰而數學的定義見 CCSP2023 T4 題目描述部分)
數組要強調無間隙是因為結構體有間隙. 具體而言, 每個類型有兩個屬性: 大小和對齊. 對齊的意思是, 為了提高處理效率, 需要保證數據的地址為特定的 \(2^m\) 的倍數, 這個 \(2^m\)
每個分項互不重疊地存放在結構體之中, 分項地址相對於結構體地址有一個偏移. 標準規定, 結構體所有分項的偏移順序就是定義順序, 而編譯器會為了滿足對齊要求在其中加入空白填充. 最後結構體的對齊為分項的最大對齊, 還需要在最後填充空白使其恰好為對齊的倍數.
有例外, 叫做位域成員.
聯合體所有分項地址相同, 即沒有偏移重疊地儲存. 對齊就是分項的最大對齊, 大小需要不小於分項的最大大小, 也可能需要在最後填充空白使其恰好為對齊的倍數.
指針儲存的就是地址, 大小看系統位數, 對齊和大小相同.
x64 彙編地址
(細節見 cheetsheet)
數據一般從近到遠被儲存在四個地方: 寄存器, 內存, 硬盤 (設備) 和網絡. 訪問所需的時間開銷依次成倍增加, 但可用的內存大小也依次變多 (一般情況下, 比如你 xp 是內存條, 就有可能內存比硬盤空間大).
x64 彙編能直接使用前兩者, 設備一般要通過操作調用, 網絡更是要操作系統跑五層協議.
寄存器有 \(16\) 個, 每個寄存器有 \(8\) 字節, \(8\) 字節本身和它們的低 \(4,2,1\) 位都有一個名稱, 均由 % 開頭. \(16\) 個寄存器中有 \(8\) 個有歷史遺留的特殊命名, 還有 \(8\)
後綴 q, d/l, s/w, b 分別表示四字 (quad word), 雙字/長字 (double/long word), 單字/字 (single word/word), 字節 (byte), 這個要記住, 後面有大用. (特例是 \(8\) 位寄存器 l 表示低位 (low))
除此之外還有一個特殊的程序計數器 %rip, 儲存當前運行的指令地址; 以及四個 \(1\) 比特的條件碼 ZF,SF,OF,CF, 它們不能直接顯式設置與使用.
內存地址的完全體格式為 Imm(rb,ri,s), 其中 Imm 為一個立即數, rb,ri 為寄存器, s 為 1, 2, 4 或 8, 表示地址 Imm+rb+ri*s. 可以適當省略, rb 和 Imm 可以留空, 第二個逗號和後面的 s 可以一起刪掉, 甚至後面整個括號都可以刪掉, 但是括號內只有一個寄存器時就不用寫逗號了. 注意訪存用的寄存器位數要和系統位數匹配.
除此之外還能用 $ 開頭接立即數, 立即數, 相當於數據直接和指令一起被髮送和處理, 在某種意義上是直接儲存將數據在導線上, 比寄存器訪存開銷還低.
x64 彙編指令
指令也是用二進制編碼的數據, 下面介紹具體指令.
mov(b/w) S,D: 將S的數據傳送到D, 後綴b,w指示位數.movl S,D: 將S的低 \(32\) 位數據傳送到D, 如果終點是寄存器則用0覆蓋高 \(32\)movq S,D: 將S的全 \(64\) 位數據傳送到D, 如果S為立即數則只能為 \(32\) 位數, 只能傳送後高位置 \(0\).movabsq I,R: 將 \(64\) 位立即數傳送到寄存器R. 這幾乎是唯一能直接用 \(64\)mov(z/s)(bw/bl/wl/bq/wq/lq) S,D: 將S的低若干位數據傳送到D, 高位補0. 後綴bw,bl,wl,bq,wq,lq分別指示位數,z和s指示零還是符號擴展. 以l目標時同樣會把高 \(4\) 位清零, 特例是沒有movzlq, 因為它就是movl.cltq:movslq %eax,%rax的縮寫.leaq S,R: 將內存地址S的地址存儲到寄存器R.
注意不能直接從內存移動到內存.
(inc/dec/neg/not)(b/w/l/q) D: 單操作數運算.(add/sub/imul/xor/or/and)(b/w/l/q) D: 多操作數運算, 乘法不能用立即數作為源操作數.(sal/shl/sar/shr)(b/w/l/q) k,D: 位移運算,h和a分別為邏輯和算術 (arithmetic) 位移, 區別在於右移時是符號填充 (高位填充, high) 還是零填充,k只能為%cl或者 \([0,256)\) 的立即數, 為$1時可省.
條件碼會被上面的所有算術運算設置, 具體説來:
ZF: 結果是否為0.SF: 結果的最高位.OF:add,sub,inc,dec在視作有符號加減時是否溢出,sal,shl,sar,shr最高位是否改變,not不影響, 其他置0.CF:add,sub在視作無符號加減時是否溢出,sal,shl,sar,shr為移出的位,inc,dec,not不影響, 其他置0.
還有兩條專門設置而不改變寄存器的指令:
cmp(b/w/l/q) S1,S2: 根據S2-S1的結果設置條件碼.test(b/w/l/q) S1,S2: 根據S2&S1的結果設置條件碼.
注意順序是反的.
set(e/z) D: 結果為零/比較等於.set(ne/nz) D: 結果非零/比較不等於.sets D: 結果負數.setns D: 結果非負數.set(g/nle) D: 有符號比較大於.set(ge/nl) D: 有符號比較大於等於.set(l/nge) D: 有符號比較小於.set(le/ng) D: 有符號比較小於等於.set(a/nbe) D: 無符號比較大於.set(ae/nb) D: 無符號比較大於等於.set(b/nae) D: 無符號比較小於.set(be/na) D: 無符號比較小於等於.
D 為 \(8\) 位寄存器, 被設置為 0x00 或 0x01.
g, l, a, b 分別為 greater, lower, above, below 的縮寫. 前四條絕對可信, 後面的一般是先 cmp 再用的.
跳轉指令:
jmp L/*O/D: 將%rip設置為標籤L指向的指令地址/O指向的數據/立即數D.
同樣也有 O 為立即數時只能是 \(32\) 位的限制, 如果真想跳則需要中轉. 標籤 L 通過彙編代碼指定.
很多情況下要先判斷再跳轉, 所以有條件跳轉指令, 格式為:
j(..) L/*O: 條件滿足時將%rip設置為標籤L指向的指令地址/O指向的數據.
條件跳轉事實上對 CPU/GPU 等很不友好, 因為它們往往要在前面的指令沒執行完時提前處理一些指令, 但是條件跳轉會導致不能絕對確定應該提前處理哪條指令, 所以這麼幹有風險. 不過有些時候條件跳轉只是為了傳一個數, 這是非常友好的, 就有條件傳送指令:
cmov(..) S,R: 條件滿足時將寄存器R設置為非立即數S.
(..) 同 set 的那一套後綴.
內存裏有個系統棧, 用來管理函數的調用. 地址最低處儲存着棧頂的數據, %rsp 專門用來表示這個棧頂的地址.
pushq S: 將 \(8\) 位的S壓棧.popq D: 將 \(8\) 位的棧頂彈到D中.call L/*O/D: 將下一條指令的位置壓棧, 再將%rip設置為標籤L指向的指令地址/O指向的數據/立即數D.ret: 將 \(8\) 位的棧頂彈到%rip中.
q 是因為系統是 \(64\)
這個棧一般在函數調用時有 \(16\)
deepseek 説如果你想
pushq\(64\) 位立即數, 會被彙編器拆成一個movabsq和一個pushq.
事實上還有浮點擴展, 向量擴展等等, 它們甚至還會引入新的寄存器. 不過學了這些差不多了.
進程
一個非常重要的概念是進程. 它的核心概念是, 為每個程序構造了一個整個計算機只有它一個程序在運行的環境. 它擁有一個或多個獨立的邏輯控制流和一個私有的地址空間, 但事實上並不需要把整個內存都清空.
而且系統中會有多個進程"同時"運行的假象. 具體實現方法是每個進程都會被執行一段時間, 然後被掛起去執行另一個進程.
函數調用
C 語言中的函數內的局部變量都存放在一個棧中, 這個棧就是上面的系統棧. 系統棧被當前正在調用的函數瓜分, 函數按被調用的從早到晚的順序從棧底到棧頂分別佔有一個叫棧幀的部分, 當函數被調用時它的棧幀便被創建, 當函數返回時它的棧幀被彈棧.
每個函數都可以隨意改寫它的棧幀, 而不用擔心破壞其他函數的狀態, 這樣大大簡化了程序的編寫. 每個棧幀 (棧頂的棧幀可能不完整) 一般從底到頂分為這些部分:
- 被保存的寄存器
- 局部變量
- 實際參數
- 返回地址
調用函數顯式的指令只有一句 call, 它僅僅把返回地址壓棧, 實際上在此之前需要把參數準備好. 參數按照順序依次由 %rdi, %rsi, %rdx, %rcx, %r8, %r9 負責傳遞, 多餘的參數放入棧幀中的實際參數區, 規定順序為從頂到底.
同樣, 函數返回只有一句 ret, 它僅僅把返回地址彈棧並跳轉到該處. 所以要提前把棧幀釋放掉 (實際上只需要把棧頂指針歸位), 並且把返回值存入 %rax.
因為被調用者需要使用寄存器, 所以可能函數調用再返回時寄存器內的值已經被改變, 但調用者需要在後面使用寄存器原來的值. 這個時候有兩種方法, 一種是調用者把寄存器保存到棧中, 被調用者返回後再復原; 另一種是被調用者在進入時就將需要修改的寄存器保存到棧中, 返回前就復原.
具體使用哪種由使用哪個寄存器決定, 具體規定可以查 cheetsheet.
內核
每個進程有兩種狀態, 用户態和內核態, 具體哪個狀態由 CPU 上一個控制寄存器控制. 內核態有使用內存和指令的完整權限, 而用户態對這些資源的使用有限制.
\(64\) 位的 Linux 下, 高於 \(2^{48}\) 位的內存將對用户態不可見, 只能被內核態使用. 不過有 /proc 文件系統可以供用户態讀取內核態所允許的數據.
進程的切換就是由內核態來完成的. 具體過程為, 先保存當前進程上下文 (寄存器, 程序計數器, 用户棧, 內核棧等等數據), 並恢復被切換進程的上下文.
異常
進程運行時總會發生意外, 這樣需要內核中的異常處理程序進行處理, 並且選擇是否在處理完之後將控制交還給用户. 異常也可能是外部設備主動觸發的, 讓 CPU 停止手頭工作處理外部設備的信息. 當然這是切換到內核態的幾乎唯一機會, 可以由用户態主動觸發異常來調用內核程序:
- 故障: 可能恢復的錯誤, 故障處理程序處理後自行選擇是否交還控制.
- 終止: 無法恢復的錯誤, 終止處理程序處理後終止進程.
- 中斷: 外部設備向 CPU 引腳發了一個信號, 並把異常號放在總線上. CPU 在處理完當前指令後, 檢測到了這個信號, 就會把控制交給中斷處理程序, 處理完後交還控制. 還有可能是進程被運行了足夠長時間, 系統產生週期性中斷信號強制切換到內核態進行上下文切換.
- 陷阱: 進程通過指令觸發異常, 最主要的功能就是系統調用, 內核中相應程序會過來處理調用, 並在執行完後返回控制. 當然系統調用也可能發生上下文切換.
Linux 中每個異常有一個異常號.
不同進程的用户態之間以及內核和用户態之間可能有一些通信需求, 比如最典型的是按 CTRL+C 希望某個進程似一似. 但通過簡單的文件傳輸肯定無法讓用户態得到這個消息, 因為它大概率沒有專門處理的操作, 所以需要內核用信號機制施壓.
Linux 中有至少 \(30\)
當進程從內核切換到用户態時, 內核會從低到高檢查所有未被阻塞但被掛起的信號, 若有信號則會強制用户接受. 接受信號後將會執行由信號類型決定的默認行為中的一種:
- 進程終止
- 進程終止, 轉儲內存
- 進程掛起, 直到信號 SIGCONT 喚醒
- 忽略
也可以通過 signal 函數修改行為, 這個函數可以將行為修改為忽略, 恢復默認或者改成執行自定義的信號處理程序. 信號處理程序和主程序併發執行. 不過不能修改 SIGKILL 和 SIGSTOP 的默認行為, 也就是不能賴着不死.
信號處理程序執行時也可能會因為捕獲到新的信號執行另外的信號處理程序, 但是執行時其對應的信號會被阻塞, 所以此時收到同樣的信號不會馬上重新執行, 而是執行完後再執行一次.
虛存
(這一節有一堆縮寫, 自己猜英文全稱)
整個電腦的內存被視作一個大小為 \(M\) 的數組, 被稱為物理內存 PM, 每個字節擁有一個物理地址空間 PAS \([0,M)\cap\mathbb N\) 的中的編號, 被稱為物理地址 PA. 但是彙編使用的地址並非直接使用 PA, 而是虛擬地址空間 VAS \([0,N)\cap\mathbb N\)
一般有 \(N=2^n\), 此時稱 VAS 為 \(n\) 位虛擬地址空間 VAS, 一般為 \(32\) 位或 \(64\) 位. 但 \(M\)
眾所周知 \(K=2^{10},M=2^{20},G=2^{30},T=2^{40},P=2^{50},E=2^{60}\), 這本書裏似乎沒有 \(10^3\)
VM 和 PM 都被分為大小為 \(P=2^p\)
PP 和 VP 之間的映射由 CPU 上的專門的內存管理單元 MMU 和物理內存上的頁表管理. 每個進程有一個單獨的頁表, 頁表是一個由頁表條目 PTE 組成的數組, 大小是 VP 的數量 \(2^{n-p}\), 於是每個 PTE 就成為了一個 VP 的物理實體.
PTE 首位為有效位 \(0\) 和 \(1\), 表示是否緩存到物理內存: 如果是的話後面就指向 PP; 否則如果在硬盤上分配了空間就指向硬盤地址; 否則該 VP 未分配, 後面為空. PTE 上還會添加一些額外的許可位, 比如可以設置 SUP, READ, WRITE, 表示是否需要內核態訪問, 是否可讀, 是否可寫.
CPU 有一個頁表基址寄存器 PTBR 指向當前進程的頁表. CPU 訪問 VP 時, 會將 VA 給 MMU. MMU 先通過 PTBR 找到目前的頁表. 一個 \(n\) 位的 VA 由高 \(n-p\) 位的虛擬頁號 VPN 和低 \(p\)
於是 MMU 找到了對應的 PTE. 如果違反了許可條件則會發生段錯誤 Segmentation Fault; 如果已緩存, 那麼後面會存放物理頁號 PPN; 否則發生缺頁錯誤 Page Fault, 此時有異常處理程序來處理.
如果沒有缺頁, 那麼現在 MMU 就有了 PPN. 而物理頁面偏移 PPO=VPO, 所以可以將 PPN 和 PPO 組合成 PA, 這樣就可以直接訪問物理內存了.
否則缺頁異常處理程序會來處理缺頁. 它會選擇一個犧牲 PP, 如果被修改過則將其寫回磁盤, 再把當前訪問的 VP 從硬盤緩存到該 PP 或者直接分配, 並相應修改 PTE, 最後回到原進程重新執行命令.
不同進程之間可以有 PTE 指向相同的 PP 或硬盤地址, 也可以讓一個 PP 或硬盤地址被一個進程獨享.
但是這樣每次找 PTE 又要訪問一次內存, 不是很划算, 所以 MMU 中有一個翻譯後備緩衝器 TLB.
TLB 中的條目分為 \(T=2^t\) 個組, 每個組裏有 \(c\) 條緩存, 稱做 \(c\) 路組相聯. 每條緩存有標記位, PPN 和有效位 \(0\) 或 \(1\)
這樣又把 VPN 分成了高 \(n-p-t\) 的 TLB 標記 TLBT 和低 \(t\) 位的 TLBI. TLBI 指示了緩存所在組, 於是找到對應組, 看其中 \(c\) 條緩存中有沒有有效位為 \(1\)
當然 64 位系統的頁表可能太大了, 需要多級頁表來壓縮, 高級頁表每個 PTE 都再指向一個次級頁表, 如果沒有該頁表的有效 VP 就置空. 這樣 VPN 還能被切成多個 PTEA.
Core i7 這一節不管了, 課件不教.
Linux 中, 內核 VM 中有一部分通過映射到同一 PP 從而被所有進程共享, 裏面存着內核代碼和數據; 還有一部分是每個進程不同的, 裏面存着頁表, 內核棧, 還有一個接下來要介紹的 task_struct 和 mm_struct.
VM 被組織成一些區域的集合. 內核為每個進程都維護了一個結構體 task_struct 的變量, 儲存了進程的重要信息. 其中一個條目指向結構體 mm_struct 的變量, 儲存了虛擬內存的狀態. 其中一個條目 pgd 指向最高級頁表, 另一個條目 mmap 指向結構體 vm_area_struct 的鏈表. 每個 vm_area_struct 變量儲存一個 VM 區域的信息:
vm_start: 起始地址vm_end: 結束地址vm_prot: 讀寫權限vm_flags: 是否共享等等
MMU 觸發缺頁後, 缺頁異常處理程序會遍歷這個鏈表 (實際上為了加速是一棵樹). 如果不在任何區域內則會觸發段錯誤, 如果訪問不符合權限要求則會觸發保護異常, 否則開始選犧牲 PP...
一個區域在最開始時被映射到硬盤上的連續地址, 可能在普通文件內也可能在匿名文件內. 對於前者, 文件內存儲的是初始值. 對於後者, 相當於區域內初始值均為二進制 \(0\).
每個區域的 vm_area_struct 中儲存了是否是共享區域, 説明在改寫該區域的 VM 時, 它的修改是否需要被其他進程看到.
創建映射時內核會識別被映射的文件, 是否已經被其他進程映射到 PM 中, 如果是則會將 VM 映射到該 PM. 如果是共享文件, 則該進程寫入 VP 時會直接修改對應 PP, 這樣任何修改也會被看到. 否則該 PM 區域是隻讀的, 會引發故障處理程序. 故障處理程序會在 PM 中的其他地方創建一個副本, 並將 VP 重新映射到副本中的 PP.
實踐: 進程控制
ELF
目標文件有三種形式:
- 可重定位目標文件
- 可執行目標文件
- 共享目標文件
在 Linux 中它們同一使用可執行可鏈接格式 ELF.
gcc 編譯分為幾個階段:
cpp預處理:.c源代碼文件 \(\to\).i中間文件ccl編譯:.i中間文件 \(\to\).s彙編語言文件as彙編:.s彙編語言文件 \(\to\).o可重定位目標文件ld鏈接:.o可重定位目標文件 \(\to\)
事實上
ccl已經被掃入歷史的垃圾堆了, 手動操作的時候前兩個可以直接用gcc的-E和-S, 最後一個用不加選項gcc.
格式
ELF 格式頭部總有一個 ELF 頭, 尾部總有一個節頭部表, 中間由若干節組成.
