# 2024q1 Homework5 (assessment) contributed by < [`hungyuhang`](https://github.com/hungyuhang) > ## 前 4 週測驗題改進 ## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發與課程心得 閱讀完**因為自動飲料機而延畢的那一年**這一系列文章，我感觸良多。在文章前面的部分作者提到了一個現象，那就是在學校學到的東西往往不能在業界實際應用，學校教了許多理論基礎，但多數學生卻無法將他們學到的知識拿來做實際應用，還是需要到職場上才有辦法開始學習如何實際的去實作一些東西。 而作者對於堅持完成一件事物的精神，也令我深深感到敬佩。作者一開始覺得製作一台飲料機應該沒有什麼難的，但是當實際開始製作時，才發現原來問題比想像中的多，許多從來沒有想過會發生的問題，全部都成為阻礙，擋住完成自動飲料機的去路。而這時候就作者開始懷疑自己是不是該繼續做下去，開始會認真考慮著該不該放棄。 而在修這堂課的這六個禮拜以來，當我在閱讀課程教材，以及做作業時，我也常常陷入相同的處境。在實際去閱讀教材時，才發現以我自身的能力，要完成指定的作業以及教材進度可以說是難如登天，要讀完一篇教材少說要專注地投入三四個小時以上，要完成作業的一個子題目可能要花上至少一整天才能完成。在期初選這堂課的時候，我曾經告訴自己一定要全心投入這個課程的每個作業，但是在實際投入心力之後，才發現現實往往跟想像中的不一樣，如果我專注在做作業的其中一個子題目，盡量做到最好，那麼我勢必會無法空出多餘的時間去閱讀教材，甚至完成作業的其他子題目。 現實與理想的差距令我感到不知所措，抱著無限的迷惘，我開始下意識的用囫圇吞棗的心態面對每一次作業：有沒有真正的理解不重要，只要產出的內容「看起來」不要太混，好像有在努力那就好了。 但直到上次現場的 code review ，看著老師把學生一一問倒，我才意識到這種囫圇吞棗的心態是毫無意義的。用這種心態做事可能可以省下許多鑽研的時間，讓我得以勉強完成作業的所有子小題，但我卻連一個小題都無法融會貫通。今天如果別人丟了一個類似的題目請我解決的話，我還是只能用最笨最不安全的方式，而無法利用這堂課想給予我們的知識去解決。那如果是這樣的話，那我還比較應該全心投入某個子小題，即使最後作業可能會寫不完，但是至少還能夠學到一些東西。 ## 課程教材心得記錄 ### 你所不知道的 C 語言 - **[你所不知道的 C 語言: 開發工具和規格標準](https://hackmd.io/@sysprog/c-standards)** - 如何正確解釋 C 語言的宣告 在 [c99 draft](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 裡面的 6.7.6 有提供一些簡單的範例： ![Screenshot_20240322_103855](https://hackmd.io/_uploads/BJIZTjueC.png) 在 6.7.5.1 裡面，這段有關 const 的範例也很清楚： ![Screenshot_20240322_104502](https://hackmd.io/_uploads/H1S8pjOg0.png) - 當 `const` 在 `*` 左邊時，它修飾的是指標指向的值 - 當 `const` 在 `*` 右邊時，它修飾的是指標本身 > 關於如何正確解釋 C 的宣告我有查到這篇 [StackOverflow 的貼文](https://stackoverflow.com/questions/34548762/c-isnt-that-hard-void-f/34560439#34560439)，但裡面教的方式比較像是一個通則，實際的細節尚需參考 C99 的 6.7.5 章節。 - **[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)** - 手動清除記憶體快取（感覺用的到） ```bash sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' ``` - 上面命令做的事情就是把一個控制碼（比如說 3 ）寫到 `drop_caches` 這個 file 裡面，寫入之後對應的快取就會被清理 - Address Alignment in C Struct C99 的規格中 6.7.2.1 提到： > Each non-bit-field member of a structure or union object is aligned in an implementation- defined manner appropriate to its type. > 所以關於 struct 如何做 Alignment 是各個 compiler 去各自實作的，而不是 C 語言自己定義的。 - **[你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function)** - Parameter vs Argument - A **parameter** is a variable in a function definition. It is a placeholder and hence does not have a concrete value. - An **argument** is a value passed during function invocation. - **[你所不知道的C語言: 未定義/未指定行為篇](https://hackmd.io/@sysprog/c-undefined-behavior)** - ABI (Application Binary Interface) 以 C 來說，函式通常都會需要接收參數。在編譯成組合語言後的 C 函式裡面，函式的接收方式通常就是： 1. 呼叫函式的人把參數放到特定的 register 裡面（或是放到特定的 stack 位置） 2. 函式本人從特定的 register 去拿值（或是到特定的 stack 位置去拿值） 而「放到哪個 register 」「放到 stack 的哪個位置」這些事情其實就是所謂的 ABI (Application Binary Interface) ，這裡的介面 (interface) 指的就是 caller 跟 callee 之間的介面。 - 如果對 C 語言不熟悉的話，未定義行為往往會讓程式出現難以抓到的錯誤，但如果能夠善加利用的話，未定義行為反而可以讓程式碼運行的更有效率。 ### CS: APP - CH1 #### 1.9 - Concurrency and Parallelism - Thread Level Concurrency - 同時讓多個 process 在 Processor 上面運行 - 在這裡， Processor system 大致上分三種： - uniprocessor system - 透過不停地 context switch 來製造多個 process 同時在一個 processor 上面跑的假象 - Multiprocessor system (Multi-core) - 一個 processor 裡面有好幾個 core - Multiprocessor system (Hyper-threaded) - 一個 processor 裡面有部分元件有很多個 (比如說 PC register) - 但是有些元件只有一個 (比如說浮點數運算元件) - 所以 context switch 的時間跟 uniprocessor 比起來會短很多 - Instruction-Level Parallelism - 同時執行多條 **指令** - Single-Instruction Multiple-Data (SIMD) Parallelism - 1.9.3 ： Abstraction 很重要，舉 ISA 為例， Abstraction 可以讓軟體端的開發者不需要過度深入地去研究 CPU 實作的一些細節，只須遵循 ISA 的規格就可以寫出能夠正確運行的程式。同時，只要不同的處理器可以遵循 ISA 的規格的話，即使實際的硬體設計不一樣， Abstraction 的特性也依然能讓同一份程式在不同的處理器上運行。 ### CS: APP - CH2 - 幾個重要的二元運算性質 - 結合律 (associativity) - 在一個包含有二個以上的可結合運算子的表示式，只要運算數的位置**沒有改變**，其運算的順序就不會對運算出來的值有影響。 - 重新排列表示式中的括號並不會改變其值。例如：(5 + 2) + 1 = 5 + (2 + 1) = 8 - 交換律 (commutativity) - 意指能改變運算子左右兩個運算元的順序而不改變其最終結果。 - 例如：4 + 5 = 5 + 4 - 分配律 (distributivity) - a * (b + c) = a * b + a * c - (b + c) * a = b * a + c * a - integer representations can encode a comparatively small range of values, but do so precisely, while floating-point representations can encode a wide range of values, but only approximately. :::info > Whereas the C standards are designed to allow a wide range of implementations, the Java standard is quite specific on the formats and encodings of data. > 課文提到，相對於 C ， Java 對於 data 的 formats and encodings 是有許多規定的，背後的原因是為什麼呢？ ::: #### 2.1 Information Storage - gcc 可以指定要用哪一個 c 標準來編譯程式碼，比如說 `-std=c99` 或是 `-std=c11` 之類的，但是也可以使用 `-std=gnu11` 這種標準來做編譯，這邊的 gnu11 ，以他[文件](https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html#index-std-1)的說法，其實是 C11 的 GNU dialect ，兩者差異如下： - 如果是標準的話， compiler 會把一些跟 C 標準相衝的 gcc feature 關掉 (但其他 feature 還是打開的) - 如果是 GNU dialect 的話， compiler 會把所有 gcc feature 打開，就算有些 feature 會蓋掉原來 C 標準所定義的東西。 - C data type 所佔的 byte 長度跟程式是編譯成 32 bit 還是 64 bit 有關，比如說 `long` 在 32 bit 的程式，典型的長度是 4 bytes ， 但是在 64 bit 的程式，典型的長度卻是 8 bytes 。 - endianness - Little endian: Least significand byte comes first (因為 comes first, 所以放在低的記憶體位置) - Big endian: Most significand byte comes first (因為 comes first, 所以放在低的記憶體位置) - bit vector 可以拿來表示 finite set ，比如說： - `01101001` 可以拿來表示集合 {0, 3, 5, 6} - `01010101` 可以拿來表示集合 {0, 2, 4, 6} 這時候 `|` 跟 `&` 這兩個運算元就可以類比為集合運算中的 union 跟 intersection 。 - inplace swap ```c void inplace_swap(int *x, int *y) { *y = *x ^ *y; *x = *x ^ *y; *y = *x ^ *y; } ``` 這個程式運用了 a ^ a = 0 的性質來達成 inplace swap 的目的，非常優美。(`^` 在 C 代表 XOR) - 但是如果 x 跟 y 指向同一個記憶體位址時，這個程式會出錯。 - XOR 的性質 (假設 a 的長度為 8 bit) - a ^ 0x00 = a - a ^ 0xFF = !a - Logical operations in C - 包含 `||` 、 `&&` 跟 `!` - 這些 Logical operation 把所有非零的數字視為 True ，並且把零視為 False - 回傳的值是 0 或是 1 。 - The logical operators do not evaluate their second argument if the result of the expression can be determined by evaluating the first argument. - 所以 `a && 5/a` 永遠不會觸發 division by 0 error - `p && *p++` 永遠不會觸發 dereferencing a null pointer error - Shift operations in C - C 標準沒有明定 signed 的數字要用 arithmetic right shift 還是 logical right shift ，所以當寫程式時，我們無法確定 `>>` 運算元會用哪種方式進行 right shift 。但實務上，目前幾乎所有編譯器都是用 arithmetic right shift 。 - 但 unsigned 的數字就是用 logical right shift 。 - 相對於 C ， Java 明定 `>>` 是 arithmetic 的， `>>>` 是 logical 的。 - 當 shift amount 大於 data width 的時候，這在 C 裡面是 undefined behavoir 。 但是在 java 裡面有明定： > 實際的 shift amount = (shift amount) % (data width) 所以在 Java 裡面， a << 36 會等於 a << 4 。(36 % 32 = 4) #### 2.2 Integer Representations - C 標準對各種 data type (`short`, `int`, …) 的值域有最小的規定，在 C99 是記錄在 6.2.5 第五段： > A ”plain” `int` object has the natural size suggested by the architecture of the execution environment (large enough to contain anyvalue in the range `INT_MIN` to `INT_MAX` as defined in the header `<limits.h>`). > 以及 7.18.3 (第七章是 Library 的章節，紀錄 `<limits.h>` 裡面宏的數值)。 - 同一個 bit vector 可以用不同的 interpretation 來解譯 - Unsigned - Two’s-Complement - Two’s Complement Encodings - 定義 $B2T_w$ 為將 binary 轉換成 two’s complement 的函式 - 定義 $x$ 為 $[x_{w-1}, x_{w-2}, …, x_{0}]$ 的 bit vector ，則 $$ B2T_w(\vec{x}) \doteq -x_{w-1}2^{w-1} + \sum^{w-2}_{i=0}x_i2^i $$ 這裡可以觀察到，我們其實可以把第 $i$ 個 bit 的數值 ( 1 或是 0 ) 當作 $2^i$ 的權重來看。 而在 Two’s Complement Encodings 的例子裡，可以發現 MSB 的權重是負的。除了 MSB 以外的所有 bit ，其規律都跟 unsigned 的算法是一樣的。 在這裡可以用數線的方式去思考： ![twos_complement_encoding](https://hackmd.io/_uploads/SykuvdkzC.png) 將 binary 轉換成 two’s complement 時，如果 MSB 為 0 ，只要不停的把數字往右累加上去即可。 但如果 MSB 為 1 ，那就需要先把數字往左邊移動 $2^{w-1}$ ，然後再開始把數字往右累加。而因為 $2^{w-1}$ 必定大於 $\sum^{w-2}_{i=0}x_i2^i$ ，所以在這個情況底下算出來的數字也必定小於 0 。 - 雖然大多數機器都是用 Two’s Complement Encodings 來表示有號數，但是 C standard 並沒有硬性規定一定要用這種方式來表示有號數。所以如果我們希望寫的程式有比較好的可移植性 (Portability) 的話，那就不應該預設 C 裡面的有號數一定都是用 Two’s Complement Encodings 來表示的。 - Two’s Complement 跟 One’s complement 的命名由來 - Two’s complement 對每個非負的 $x$ ，我們可以用 $2^w - x$ 的 bit representation 來代表 $-x$ (那個 2 就是 two’s complement 裡面的 2)。 - 假設 w = 4，則 -2 = [10000] - [0010] = [1110] - One’s complement 對每個非負的 $x$ ，我們可以用 $[111...1] - x$ 的 bit representation 來代表 $-x$ (那堆 1 就是 one’s complement 裡面的 1)。 - 假設 w = 4，則 -2 = [1111] - [0010] = [1110] - Signed / Unsigned Integer 之間的轉換 如果要轉換的變數裡面的數字同時可以被 signed 跟 unsigned 所表示，那轉換過的值就不會變。但如果要轉換的變數裡面的值無法同時被 signed 跟 unsigned 所表示，則多數 C implementation 所採用的方式是保持 bit pattern 不變。 - 舉例： int x = -1 cast 到 unsigned 之後，值會變成 15 這裡一樣可以用數線的方式去思考，可以注意到 cast 之前跟之後的數字彼此差的值是固定的。 為什麼呢？因為 cast 之前跟之後唯一的差別就是對 MSB 的定義不同 (從 $+2^w$ 變成 $-2^w$ ，或是相反) ，而從數線來看的話，就是那條灰色的線會從往右指變成往左指 (或是相反)： ![signed_unsigned](https://hackmd.io/_uploads/r1oFdu1fC.png) - 在 C 裡面，當宣告一個常數時 (比如說 `12345` )， C 會把這些數字預設為 signed 的型態。 但如果在數字後面加上 `U` 或是 `u` 的話， C 就會把他們視為 unsigned 的，比如說 `12345U` 。 - 當運算元同時含有 Signed / Unsigned 的變數時， C 就會對其中一方做型態轉換。關於轉換的規則詳細可以看 C99 的 6.3.1.8 Usual arithmetic conversion 這一個章節。但大致上的規則就是： - 當其中一個運算元是 w bit signed 但是另一個是 w bit unsigned ，則將 signed 轉換成 unsigned 。 但這就會造成一些不太直觀的行為出現，比如說 `-1 < 0U` 的結果會是 `false` ，因為 C 會先把 `-1` cast 成 unsigned 的，當 `-1` 被 cast 成 unsigned 之後他的值就會變成 `UINT_MAX` 。 - 為什麼當我們把負數的 bit representation 做擴展時，前面要補一？ 以下圖舉例： ![expand_bit_representation](https://hackmd.io/_uploads/rJJlKuJMA.png) 當我們把 bit representation 的寬度從 3 變成 4 的時候，原來 MSB 代表的值就從 -4 變成 -8 (也就是淺灰那條線)，為了保持數字一致，bit 3 的數字就一定得是 1 (也就是讓深灰那條線變成 +4 ) 才能中和 MSB 所帶來的改變。 - 在很多情況下，「區分 signed 跟 unsigned 」這件事情會讓程式容易出現一些難以發現的錯誤，比如說 implicit conversion of signed to unsigned 。因為這些原因，現今大多數的程式語言都只有 signed 的型態，比如說 Java 。 但是在某些情況下， unsigned 也是有它的優勢，比如說當我們只想要單純用 bits 的方法來看待記憶體內所處存的資料時，或是當我們拿這些變數來儲存 flag 的時候。 #### 2.3 Integer Arithmetic ## 想投入的專案 - **[Trusted Firmware-A 及 Linux 啟動流程分析](https://hackmd.io/@sysprog/linux2023-projects#Trusted-Firmware-A-%E5%8F%8A-Linux-%E5%95%9F%E5%8B%95%E6%B5%81%E7%A8%8B%E5%88%86%E6%9E%90)** 在智慧裝置，物聯網日漸興盛的今日，人們越來越常把許多個人資料，密碼都儲存在 3C 上(例如手機)，或是使用這些 3C 產品直接作為鑰匙。這時如果所使用的裝置沒有保護機制來防止有心人士竊取個資或是侵入，那麼這對人們的生活會造成極大的困擾。 [參考文章](https://www.cool3c.com/article/130319) 以下是如果我投入這個專案，我想達成的目標： - 透過 [Trusted Firmware-A](https://github.com/ARM-software/arm-trusted-firmware) 這個專案來了解並熟悉安全晶片的整體架構與韌體實作 - 熟悉 JTAG probe 這類偵錯工具的使用方式 - **[打造 Linux 虛擬攝影機裝置驅動程式](https://hackmd.io/@sysprog/linux2023-projects#%E6%89%93%E9%80%A0-Linux-%E8%99%9B%E6%93%AC%E6%94%9D%E5%BD%B1%E6%A9%9F%E8%A3%9D%E7%BD%AE%E9%A9%85%E5%8B%95%E7%A8%8B%E5%BC%8F)** 我認為如果能夠去實際接觸並理解 Linux driver 的話，對於理解 OS 如何運作是很有幫助的，而且這也可以增加撰寫 OS 程式碼的實務經驗。 以下是如果我投入這個專案，我想達成的目標： - 透過實際操作，去理解 Linux driver 的實作方式 - 了解 v4l2 驅動程式框架的細節 ## 一對一討論 (5/9) C99: `uint32_t` (恰好 32-bit) vs `uint_fast32_t` (不保證 32-bit，可能是 64-bit) vs `uint_least32_t` (至少 32-bit) standard vs. implementation ### 白板題 IEEE 754 ```c // Assume float is 32-bit width float float_mul2(float x) { // using bitwise; no mul x = (float)((((unsigned)x & 0x7FC00000) << 1) | ((unsigned)x & 0x801FFFFF)); return x; } ``` > TODO: 修正並解釋, 擴充為 lshift (mul power of 2) 在修正錯誤之前，首先要知道在 IEEE 754 32 bit 的浮點數中，各個 bit 代表的意義： ![IEEE-754-ENGLISH](https://hackmd.io/_uploads/SyijZ-0fR.jpg) 從上圖可以看到： - bit 0 到 bit 22 用來記錄 fraction (fraction 等同於 mantissa) - bit 23 到 bit 30 用來記錄 exponent - 最左邊的 bit 則是用來記錄 sign 接下來就可以來看上面程式碼的錯誤： - 遮罩應該是 `0x7F800000` 跟 `0x807FFFFF` ，而不是 `0x7FC00000` 跟 `0x801FFFFF` 。 - 在這個函式中，我想做的是對 `x` 的 binary representation 做操作，但是 `(unsigned)x` 會直接把 `x` 的 binary representation 從 `float` 直接轉型成 `unsigned` 的形式，這麼一來自然就無法正確的操作了。 - 如果要將浮點數乘以二，只要對 exponent 項做 +1 的動作即可，因為 $2 * ((-1)^{sign} * 2^{exponent-bias} * (1 + fraction)) = (-1)^{sign} * 2^{exponent-bias+1} * (1 + fraction)$ 。但我在程式碼中卻為了對 exponent 項做乘以二而使用 left shift 的操作(但是因為有 bias 的原因，所以如果想要將 exponent 最後的值乘二的話也不能單純將 exponent 項往左移) ，這會導致程式碼的行為不如預期。 將以上錯誤修正之後可以得到下面的程式碼： ```c // Assume float is 32-bit width float float_mul2(float x) { // using bitwise; no mul unsigned *p = (unsigned *)&x; *p = (((*p & 0x7F800000) + 0x800000) | (*p & 0x807FFFFF)); return x; } ``` 進一步簡化可以得到： ```c // Assume float is 32-bit width float float_mul2(float x) { // using bitwise; no mul *(unsigned *) &x += 1U << 23; return x; } ``` 那 `1U << 23` 在這裡所代表的意義是什麼呢？ 在這裡我們想做的事情就是把 x 這個浮點數的 exponent 項給加 1 。依照前面 IEEE 754 32 bit 浮點數各個 bit 的定義，當我們把 1 往左移 23 位的時候，這個 1 就會剛好被移到 exponent 項最右邊的位置： ``` /* 1U */ |0 00000000 00000000000000000000001| |s exponent -------fraction--------| /* 1U << 23 */ |0 00000001 00000000000000000000000| |s exponent -------fraction--------| ``` 接下來只要把這個左移 23 位的 1 加到 x 的 binary representation 後，就可以對 x 的 exponent 項做加 1 的動作。 ### 白板題-延伸 為什麼將一個 unsigned 變數的 binary representation 往左移可以得到該數字的二的冪的乘積？ 假設 $x$ 為 $[x_{w-1}, x_{w-2}, …, x_{0}]$ 的 bit vector ，如果我們想要用 unsigned 的方式去對 $x$ 做解譯，則可以用下面的方式去做轉換： $$ u = \sum^{w-1}_{i=0}x_i2^i $$ 其中 $u$ 是解譯後的數值。 暫不考慮 overflow ，今天如果我們把 $x$ 向左移 $n$ 位，則上述的式子會變成： $$ u_{shifted} = \sum^{w-1}_{i=0}x_i2^{i+n} $$ 將 $2^n$ 從 $\sum$ 符號中提取出來，可以得到： $$ u_{shifted} = 2^n * \sum^{w-1}_{i=0}x_i2^{i} = 2^n * u $$ 所以當我們將一個 unsigned 數字的 binary representation 往左移一位，我們可以將該數字乘以 $2$ ；將數字的 binary representation 往左移兩位，可以將該數字乘以 $2^2 = 4$ ，以此類推。 這裡舉一個簡單的例子： 假設 $x$ 為一個 bit vector ，而他的值是 $[0101]$ 。用 unsigned 的方式去解譯 $x$ 會得到： $$ u = 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 5 $$ 這時候如果我們將 $x$ 往左移 1 ，得到 $x_{shifted}=[1010]$ 。用 unsigned 的方式去解譯會得到： $$ u_{shifted} = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 10 $$ 可以看到 $u_{shifted}$ 的值剛好是 $u$ 的 $2^1=2$ 倍。 比較 $u$ 跟 $u_{shifted}$ 的組成，可以發現當我們把 $x$ 的每一個 1 向左移 1 位的時候，他所配對到的 $2^i$ 也會變成兩倍，也就是 $2^{i+1}$ ，在這個例子的話就是： - $x$ 的第一個 1 配對的 $2^i$ 從 $2^0$ 變成 $2^1$ - $x$ 的第二個 1 配對的 $2^i$ 從 $2^2$ 變成 $2^3$ ### 期末專案 TODO: vcam 紀錄問題 (真的執行程式) vcam 筆記（目前還在整理當中） https://hackmd.io/@hungyuhang/linux2024-final