2017年暑期系統軟體課程:台北場次 - coldnew's 筆記 ===== ###### tags: `sysprog2017` ( 返回 [2017年暑期系統軟體課程:台北場次](https://hackmd.io/s/BJRtkreHW) ) ( 返回 [2017年暑期系統軟體課程:台北場次 - coldnew's 筆記 GitHub 版](https://coldnew.github.io/embedded-summer-2017/) ) <a id="orgb8806a2"></a> # 課前測驗題 從下方至少選 3 題來作答,不僅要提供程式碼,也該描述思路。作答方式為建立「新的」HackMD 頁面,在「標題」提及自己的姓名或可資識別的代號,內文則應標註原題號,如 Q1:,隨後將新建的 HackMD 連結貼入報名表格,課程工作人員會逐一通知。 參考: [HackMD 教學和作業原則](https://hackmd.io/s/Bk-1zqIte) 示範: [coldnew](https://github.com/coldnew/2015-embedded-summber-note) <a id="orgd702368"></a> ## [ X ] Q1 考慮以下 C99 程式,解釋其具體作用,並用 for/while 迴圈改寫,隨後提供 uint16\_t 的版本。在什麼場合會用到下方的程式碼? ```C #include <stdint.h> uint32_t func(uint32_t x) { uint32_t n = x; n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } ``` <a id="orge264303"></a> ### 想法 & 思考 一開始看到這樣的題目可能不知道怎樣解,所以我們可以套用個數值 `0x12345678` 進去一行一行的測試: ```C uint32_t n = 0x12345678; n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); printf("0x%x\n", n); // => 0x56781234 ``` 可以發現到第一行是前後 2byte 進行對換的動作,即 `0xAABBCCDD => 0xCCDDAABB` 。 接下來讓我們看第二組: ```C uint32_t n = 0x56781234; n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); printf("0x%x\n", n); // => 0x78563412 ``` 可以注意到這一組命令,會做出 `0xAABBCCDD` => `0xBBAADDCC` 這樣的運作,也就是對兩個兩個 byte 進行 swap。 接下來看第三組,這一組則是將 4 位元 (半個 byte, 英文為 `nibble` ) 進行了 swap。 ```C uint32_t n = 0x78563412; n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); printf("0x%x\n", n); // => 0x87654321 ``` 到此,我們已經將原本的 `0x12345678` 轉換成 `0x87654321` 了。 接下來這一組直接看看不懂 ```C uint32_t n = 0x87654321; n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); printf("0x%x\n", n); // => 0x2d951c84 ``` 因為看不懂,所以我們用二進制來觀察 ``` 從: 0x87654321 => 1000 0111 0110 0101 0100 0011 0010 0001 到: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100 ``` 可以看到是對續的兩個 bit 進行對調,用這樣的圖來看就比較好懂了: ![](https://i.imgur.com/5mhKJbA.png) 終於到了最後一組,來跑看看 ```C uint32_t n = 0x2d951c84; n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); printf("0x%x\n", n); // => 0x1e6a2c48 ``` 因為看不懂,所以我們一樣用二進制來觀察 ``` ?: 0xaaaaaaaa => 1010 1010 1010 1010 1010 1010 1010 1010 ?: 0x55555555 => 0101 0101 0101 0101 0101 0101 0101 0101 從: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100 到: 0x1e6a2c48 => 0001 1110 0110 1010 0010 1100 0100 1000 原: 0x12345678 => 0001 0010 0011 0100 0101 0110 0111 1000 ``` 在這邊,我們可以透過 `0xaaaaaaaa` 和 `0x55555555` 發現到這邊的運算是對奇數/偶數的位元進行 swap 的動作。 此外,如果仔細看可以看出,原本的 `0x12345678` 經過這一系列的運作,變成了 `0x1e6a2c48` ,而從 2 進制來看, `0x12345678` 將所有的 bit 進行反轉,就會得到 `0x1e6a2c48` 。 於是我們知道了這個函式用途是作位元的反轉,我們可以整理前面的分析並將註解加回原始題目去: ```C #include <stdint.h> uint32_t reverse_bits_32 (uint32_t n) { /* swap 2-byte long pairs 0xAABBCCDD => 0xCCDDAABB */ n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); /* swap bytes 0xAABBCCDD => 0xBBAADDCC */ n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); /* swap nibbles 0x12345678 => 0x21436587*/ n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); /* swap consecutive pairs */ n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); /* swap odd/even bits */ n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } ``` <a id="orgd6d8041"></a> ### for/while 迴圈版本 先建立函式原型 ```C uint32_t reverse_bits_32(uint32_t x) { /* FIXME: return the reverse_bits result */ } ``` 接下來需要一個暫存用的變數,我命名為 `reverse_x` (輸入到這函式的變數為 x) ```C uint32_t reverse_x = 0; ``` 那要怎樣處理我們的迴圈呢? 我們知道要進行反轉的目標字元數是 `32` , 因此這個迴圈要跑 `32` 次, 所以作個簡單的雛形如下: ```C for (int i = 0; i < 32; i++) { /* FIXME: How to do ? */ } ``` 在這個迴圈裡面,我們檢查每一次要被處理的位元,假設他是 `1` 的話,再去更新 `reverse_x` 的內容。(reverse\_x 預設是 0) 更新的方法很簡單,透過 `or` 運算子 `|` 來進行處理,由於我們要做的是字元反轉,因此假如我們 bit[3] 是 1 的話,則 ``` 從: 0000 0000 0000 0000 0000 0000 0000 1000 <- bit[3] = 1 到: 0001 0000 0000 0000 0000 0000 0000 0000 <- bit[28] = 1, bit[32 - 1 - 3] 從: 0000 0000 0000 0000 0000 1000 0000 0000 <- bit[11] = 1 到: 0000 0000 0001 0000 0000 0000 0000 0000 <- bit[20] = 1, bit[32 - 1 - 11] ``` 所以可以知道,當要被處理的位元為 `1` 的時候,我們要這樣處理: ```C for (int i = 0; i < 32; i++) { if((x & (1 << i))) reverse_x |= 1 << ((32 - 1) - i); } ``` 因此最後的程式如下: ```C #include <stdint.h> uint32_t reverse_bits_32(uint32_t x) { uint32_t reverse_x = 0; for (int i = 0; i < 32; i++) { if((x & (1 << i))) reverse_x |= 1 << ((32 - 1) - i); } return reverse_x; } int main(int argc, char *argv[]) { uint32_t reverse1 = reverse_bits_32( 0x12345678 ); uint32_t reverse2 = reverse_bits_32( reverse1 ); printf("0x12345678 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } ``` 而這程式其實可以再簡化,省掉 `if` 的判斷: ```C #include <stdint.h> uint32_t reverse_bits_32(uint32_t x) { uint32_t reverse_x = 0; for (int i = 0; i < 32; i++){ reverse_x |= ( x >> ( ( 32 - 1 ) - i ) & 1 ) << i; } return reverse_x; } ``` <a id="orgc187eb9"></a> ### uint16\_t 版本: 目標為 32-bit 系統或是以上 假如目標平台本身就是 32-bit 系統或是更高位元 (64-bit, 128-bit ... etc),則我們可以直接使用題目的版本作點 shift 就可以得到 `uint16_t` 的版本: ```C #include <stdint.h> uint32_t reverse_bits_32(uint32_t n) { n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } uint16_t reverse_bits_16(uint16_t x) { return (uint16_t) (reverse_bits_32(x) >> 16); } ``` 這樣子的程式,一樣是可以順利運作的: ``` 從: 0x1234 => 0001 0010 0011 0100 到: 0x3c48 => 0010 1100 0100 1000 ``` <a id="org299c11e"></a> ### uint16\_t 版本: 目標為 16-bit 系統 假設今天的目標為 16-bit 系統,我們就不能用 `uint32_t` 的版本,因為系統最大的位元數是 `16-bit` ,如果要用軟體先做到模擬 32-bit 系統,在將其轉換回來這中間的損耗是划不來的。 因此我們要考慮自己改寫 `uint32_t` 的版本成 `uint16_t`, 其結果如下: (其實大部分都可以直接套用 32-bit 版本的算法) ```C #include <stdint.h> uint16_t reverse_bits_16(uint16_t n) { /* swap bytes */ n = ((n & 0xff00) >> 8) | ((n & 0x00ff) << 8); /* swap nibbles */ n = ((n & 0xf0f0) >> 4) | ((n & 0x0f0f) << 4); /* swap bit pairs */ n = ((n & 0xcccc) >> 2) | ((n & 0x3333) << 2); /* swap odd/even bits */ n = ((n & 0xaaaa) >> 1) | ((n & 0x5555) << 1); return n; } int main(int argc, char *argv[]) { uint16_t reverse1 = reverse_bits_16( 0x1234 ); uint16_t reverse2 = reverse_bits_16( reverse1 ); printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } // => 0x1234 -> 0x2c48 -> 0x1234 ``` <a id="org94f27b4"></a> ### uint16\_t 版本: 目標為 16-bit 系統 (迴圈) 承上,目標一樣是 16-bit 的系統,這時候我們的迴圈版本就變成這樣了 (其實和 [for/while 迴圈版本](#orgd6d8041) 差不多): ```C #include <stdint.h> uint16_t reverse_bits_16(uint16_t x) { uint16_t reverse_x = 0; for (int i = 0; i < 16; i++) { reverse_x |= ( x >> ( ( 16 - 1 ) - i) & 1 ) << i; } return reverse_x; } int main(int argc, char *argv[]) { uint16_t reverse1 = reverse_bits_16( 0x1234 ); uint16_t reverse2 = reverse_bits_16( reverse1 ); printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } // => 0x1234 -> 0x2c48 -> 0x1234 ``` <a id="org15beed3"></a> ### 使用到的場合: 加解密運算 透過本題的程式,可以將 `0x12345678` 轉變成 `0x1e6a2c48` ,而這動作是可以反向的, 我們一樣可以將此函式套用在 `0x1e6a2c48` 從而得到 `0x12345678` 這樣的答案,也就是說將東西丟給這個函式,再把結果丟給這函式,可以得到原本的輸入: ```C 0x12345678 == reverse_bits( reverse_bits(0x12345678) ) /* 兩者相等 */ ``` 利用這種特性,我們可以實作簡單的加解密程式 `rcf.c` ,如下: ```C #include <stdio.h> #include <stdlib.h> #include <stdint.h> uint32_t reverse_bit(uint32_t x) { x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); return x; } int main(int argc, char *argv[]) { if (argc < 3) { printf( "\nUsage:" "\t %s input.txt output.txt\n\n" "This is a simple encrypt/decrypt app " "based on reverse_bit algorithm.\n\n" , argv[0]); return 0; } const char *input_path = argv[1]; FILE *fin = fopen(input_path, "rb"); if (!fin) { fprintf(stderr, "ERROR: failed to open input file %s\n", input_path); exit(-1); } const char *output_path = argv[2]; FILE *fout = fopen(output_path, "wb"); if (!fout) { fclose(fin); fprintf(stderr, "ERROR: failed to open output file %s\n", output_path); exit(-1); } uint32_t ch; int nread; while((nread = fread(&ch, 1, sizeof(uint32_t), fin)) > 0) { /* if read size less than sizeof(uint32_t), just write it */ if (nread < sizeof(uint32_t)) { fwrite(&ch, 1, nread, fout); } else { uint32_t chn = reverse_bit(ch); fwrite(&chn, 1, nread, fout); } } fclose(fin); fclose(fout); return 0; } ``` 這個程式可以使用以下命令進行編譯: ``` gcc rcf.c -o rcf ``` 那要如何使用呢? 我們可以建立一個名為 `hello.txt` 的文字檔,有以下內容: ``` hello, this is a test ``` 接下來使用這隻加密程式產生新的檔案叫做 `hello_enc.txt` ``` ./rcf hello.txt hello_enc.txt ``` 打開可以看到內容如下: (是不是成功加密了!) ``` 66¦^V.^D4ö^DÎ<96>^V<86>^DÎ<96>Φ.^Dt ``` 而這個檔案我們一樣可以透過這隻程式進行解密成 `hello_dec.txt` ``` ./rcf hello_enc.txt hello_dec.txt ``` 打開 `hello_dec.txt` 看看,內容是不是和原來的一樣 ? ``` hello, this is a test ``` <a id="orgff56bb8"></a> ### 使用到的場合: CRC-32 運算 從 [使用到的場合: 加解密運算](#org15beed3) 這邊可以知道僅僅只是反轉一下位元就可以製作加解密程式,[循環冗餘校驗 (CRC)](https://zh.wikipedia.org/zh-tw/循環冗餘校驗) 的實作也可以用到 位元反轉 (bit reverse) 的部分。 具體實作可以參考: - [Hacker's Delight - crc.c](http://www.hackersdelight.org/hdcodetxt/crc.c.txt) <a id="org4e4a0d8"></a> ### 使用到的場合: Linux Kernel Linux kernel 裡面有實作 `bitrev32` 等位元反轉的命令,可以在 [bitrev.h](http://elixir.free-electrons.com/linux/v4.12/source/include/linux/bitrev.h) 看到,最常用到的用途,則是在 `ether_crc()` 這個函式上: ```C /* * Helpers for hash table generation of ethernet nics: * * Ethernet sends the least significant bit of a byte first, thus crc32_le * is used. The output of crc32_le is bit reversed [most significant bit * is in bit nr 0], thus it must be reversed before use. Except for * nics that bit swap the result internally... */ #define ether_crc(length, data) bitrev32(crc32_le(~0, data, length)) #define ether_crc_le(length, data) crc32_le(~0, data, length) ``` <a id="org5847fdf"></a> ### 使用到的場合: 快速傅利葉轉換 在進行快速傅利葉轉換(Fast Fourier Transform, FFT)之前,我們會需要進行位元反轉 (bit reverse),從 [FAST BIT-REVERSAL ALGORITHM](http://www.idi.ntnu.no/~elster/pubs/elster-bit-rev-1989.pdf) 論文一開頭的描述來看: ![](https://i.imgur.com/HkEzXe7.png) 足以知道位元反轉 (bit reverse) 對於快速傅利葉轉換(FFT)的重要性。 (註: [Unscrambling for fast DFT algorithms](http://ieeexplore.ieee.org/document/1631/?denied) 我沒找到電子檔) 此外,在 [Bit Reversal on Uniprocessors](http://www.hpl.hp.com/techreports/93/HPL-93-89.pdf) 這篇文章也列舉了 30 種用來作位元反轉(bit reverse)的演算法,用來測試在不同硬體上面的效能比較。 <a id="org29b8d29"></a> ### 開源專案與位元反轉 以下列出有使用 reverse bits 函式的知名開源專案以及程式碼位置 (點擊可以找到 GitHub 上的原始碼): - [linux kernel](http://elixir.free-electrons.com/linux/v4.12/source/include/linux/bitrev.h) - [redis](https://github.com/antirez/redis/blob/3.0/src/dict.c#L755) <a id="orgefe8780"></a> ### 補充: Clang 與 GCC 支援 Clang 是有內建 [字元反轉](http://clang.llvm.org/docs/LanguageExtensions.html#builtin-bitreverse) 的函式的,然而根據 [BUG 50481](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50481) 來看 GCC 是尚未支援內建這功能。 以下為 Clang 內建的版本說明如下: ![](https://i.imgur.com/1tqbwFE.png) <a id="org486d8c7"></a> ### 補充: C 語言實作 2 進制的 print 函式 在撰寫這一題的時候,順手寫了一個可以將 `uint32_t` 型別的輸入,以二進制的形式顯示出來的函式,這樣也可以比較方便的測試這一個題目: ```C #include <stdint.h> void print_binary(uint32_t x) { unsigned char *p = (unsigned char *) &x; unsigned char byte; for (int i = sizeof(uint32_t) -1; i >= 0; i--) { for (int j = 7; j >= 0; j--) { byte = (p[i] >> j) & 1; printf("%u", byte); if (0 == (j % 4)) printf(" "); } } printf("\n"); } int main(int argc, char *argv[]) { print_binary(0x12345678); return 0; } // => 0001 0010 0011 0100 0101 0110 0111 1000 ``` <a id="org482b8bd"></a> ### 延伸閱讀 - [Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C - Stack Overflow](https://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c) - [In C/C++ what's the simplest way to reverse the order of bits in a byte? - Stack Overflow](https://stackoverflow.com/questions/2602823/in-c-c-whats-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte) - [Bit Twiddling Hacks - Reverse an N-bit quantity in parallel in 5 \* lg(N) operations](http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious) - [The Aggregate Magic Algorithms - Bit Reversal](http://aggregate.org/MAGIC/#Bit%2520Reversal) - [Reversing Bits and Bytes](http://bsmartt13.github.io/blog/2012/01/05/reversing-bits-and-bytes/) - [Bit Reversal on Uniprocessors](http://www.hpl.hp.com/techreports/93/HPL-93-89.pdf) - [演算法筆記 - Bitwise Operation](http://acm.nudt.edu.cn/~twcourse/BitwiseOperation.html) - [Re: 什麼是快速傅立葉轉換 - 看板 C\_and\_CPP - 批踢踢實業坊](https://www.ptt.cc/bbs/C_and_CPP/M.1221326572.A.43C.html) - [一般信號處理,常用快速傅立葉轉換(FFT)來求得信所對應的頻譜](http://eshare.stust.edu.tw/EshareFile/2010_6/2010_6_a78298c9.pdf) - [快速傅立葉轉換 | 線代啟示錄](https://ccjou.wordpress.com/2012/05/25/%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E8%91%89%E8%BD%89%E6%8F%9B/) <a id="org83da906"></a> ## [ ] Q2 在 C 程式中,使用遞迴和 bit-wise operator 來實作乘法運算,請參考以下提示: * 加法器是用於執行加法的電路元件,通常由 AND 閘、OR 閘 和 XOR 閘構成 - 也可用加法器實作減法,只要將減數轉成二補數,並注意溢位即可 * 半加器:將兩個一位二進位數相加 (input: A, B) (output: S, C) ![](https://i.imgur.com/HRN0c1D.png) * 全加器:將兩個一位二進位數相加 (input: A, B, Cin) (output: S, Cout) ![](https://i.imgur.com/cypKq1H.png) * 波紋進位加法器:使用多個一位全加器構成 N 位加法器 ![](https://i.imgur.com/X5fQcYn.png) * 半加器可用以下 C 程式來實作: ```c uint32_t half_add(uint32_t a, uint32_t b) { if (b == 0) return a; uint32_t sum = a ^ b; /* 相加但不進位 */ uint32_t carry = (a & b) << 1; /* 進位但不相加 */ return half_add(sum, carry); } ``` --- <a id="orgdd5c09f"></a> ## [ X ] Q3 思考以下 C 程式的用途,以及在什麼場合用得到 (提示: 記憶體管理常式),探討應用場合時,需要一併列出最小可編譯和運作的 C 程式碼。 ```C void *p; // ... *p = (*p) & ~1; ``` <a id="org906a7ea"></a> ### 思考 & 想法 要看這一題,先把 `~1` 轉換成 `0xfffffffe` 這樣會比較好想,一般來說這種的用途是用在設定某個 bit (flag) 用的,也就是題目其實在問在記憶體管理函式中,怎樣的狀況會用到下面這個: ```C *p &= 0xfffffffe; // 0xfffffffe => // 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110 ``` 從上面可以看出,執行這行程式時會將 bit[0] 歸零。 那這樣的東西要怎樣和記憶體管理常式扯到邊呢? 前面提到了這種作法是在設定某個 bit (flag) 用的,也就是說我們可以這樣想: - 設定為 1 -> 該段記憶體使用中 - 設定為 0 -> 該段記憶體尚未被使用 ![](https://i.imgur.com/q13l6qb.png) <a id="orgc49ca9f"></a> ### 實作 1 - 最簡單的 malloc 從上面的想法,可以想到每次進行 malloc 的時候,其實我們是這樣佔用記憶體的 (payload 為實際存放資料的區塊) ![](https://i.imgur.com/xItGW5o.png) 為了方便理解,我們首先定義自己的記憶體區塊來製作我們的記憶體管理程式,其中 `MY_MEMORY_SIZE` 決定了我們可以索取的記憶體大小。 在主程式開始之前,則需要呼叫 `my_init()` 來確保這個記憶體管理方式是有正確初始化的。 ```C #define MY_MEMORY_SIZE 37 static uint32_t memory[MY_MEMORY_SIZE] = { NULL }; static uint32_t *brkp; static uint32_t *endp; void my_init() { brkp = memory; endp = brkp + MY_MEMORY_SIZE; } ``` 接著定義我們的 `sbrk()` 函式,可以從 `manpage` 看到 `sbrk()` 的描述是這樣的 ![](https://i.imgur.com/MocVlU9.png) 所以我們可以這樣實作他 ```C void *my_sbrk(const size_t size) { if (0 == size) return (void *) memory; void *free = (void *) brkp; brkp += size; if (brkp >= endp) return (void *) -1; return free; } ``` 有了 `sbrk()` 後,就可以透過他製作最簡單的 `malloc()` 了,在這邊我們對要到的記憶體標頭進行設定,將 flag 設定為 1 代表該區塊記憶體正在使用中。 ```C void *my_malloc(const size_t size) { // blk_size = header + payload + footer size_t blk_size = 1 * sizeof(int) + size + 1 * sizeof(int); size_t *header = my_sbrk(blk_size); if ((int)header == -1) return NULL; *header = (blk_size << 1) | 1; // mark allocated bit return header + 1; // return payload address } ``` 相對於 `my_malloc()` 會將 header 的尾巴設定 `1` 來代表該區塊被使用,當要進行 `free()` 的動作的時候,我們就把 header 的尾巴設定回 `0` 。 ```C void my_free(const void *ptr) { size_t *header = ((size_t *) ptr) - 1 * sizeof(int); *header &= ~1; // unmark allocated bit } ``` 最後在搭配一個簡單的測試程式,假如上面的 `MY_MEMORY_SIZE` 設定小於 `36` 就會遇到 `assertion failed` 的錯誤,代表已經用滿了可以用的記憶體了。 (因為每一次 malloc 佔用了 sizeof(int) \*3 的大小,即 `12 bytes`, 因此 my\_malloc() 呼叫 3 次,會用掉 36 bytes 空間,此時 `my_sbrk()` 會失敗) ```C int main(int argc, char *argv[]) { my_init(); int *a1 = my_malloc( 1 * sizeof(int)); assert(a1); *a1 = 1; printf("a1: %p, *a1 = %d\n", a1, *a1); int *a2 = my_malloc( 1 * sizeof(int)); assert(a2); *a2 = 2; printf("a2: %p, *a2 = %d\n", a2, *a2); my_free(a2); // try to free a2 int *a3 = my_malloc( 1 * sizeof(int)); assert(a3); *a3= 3; printf("a3: %p, *a3 = %d\n", a3, *a3); return 0; } ``` 正常情況會得到這樣的結果: ``` a1: 0x10b6d9028, *a1 = 1 a2: 0x10b6d9058, *a2 = 2 a3: 0x10b6d9088, *a3 = 3 ``` 假如 `MY_MEMORY_SIZE` 設定為 `30` 的話,則會變成這樣,代表可用的記憶體已經用完了,無法進行配置。 (沒用 `assert()` 的話就會遇到 `segmentfault`) ``` a1: 0x10acf4028, *a1 = 1 a2: 0x10acf4058, *a2 = 2 Assertion failed: (a3), function main, file b.c, line 69. Abort trap: 6 ``` 這是一個非常簡單的 `malloc()` 實作,從這實作可以發現到我們並沒有作真的 `free()` 的動作,也因此如果一直呼叫 `my_malloc()` 會遇到記憶體爆掉的狀況。 接下來就講講如何透過 header 的尾巴那個 flag 來作閒置記憶體區塊的判斷。 <a id="orgc80909c"></a> ### 實作 2 - 實作 1 改良版 在 [實作 1 - 最簡單的 malloc](#orgc49ca9f) 裡面,雖然我們有對使用中/不使用的記憶體區塊設定好了 flag, 然而我們並沒有使用他,也因此當呼叫 `my_free()` 的時候會發現其實他並沒有實質的作用。 這個實作將沿用 [實作 1 - 最簡單的 malloc](#orgc49ca9f) 的想法,製作出一個實際上可以用的 `my_free()` 函式。 (當然這個東西會有問題,比如記憶體碎片化的狀況) 因為是沿用前面的程式,基本的部分都差不多,差別在這次 `MY_MEMORY_SIZE` 設定為 `30`, 在前面的例子中這個數值在執行 `a3 = my_malloc()` 的時候就會爆掉了。 ```C #define MY_MEMORY_SIZE 30 static uint32_t memory[MY_MEMORY_SIZE] = { NULL }; static uint32_t *brkp; static uint32_t *endp; void my_init() { brkp = memory; endp = brkp + MY_MEMORY_SIZE; } void *my_sbrk(const size_t size) { if (0 == size) return (void *) memory; void *free = (void *) brkp; brkp += size; if (brkp >= endp) return (void *) -1; return free; } ``` 這次我們的 `my_malloc()` 則長得有點不一樣,他會透過 `find_free_block()` 去找尋可以使用的區塊位址。 ```C void *my_malloc(const size_t size) { // blk_size = header + payload + footer size_t blk_size = 1 * sizeof(int) + size + 1 * sizeof(int); size_t *header = find_free_block(size); if ((int)header == -1) return NULL; *header = (blk_size << 1) | 1; // mark allocated bit return header + 1; // return payload address } ``` 那要怎樣尋找可以使用的區塊位址呢? 我們可以先透過 `my_sbrk(0)` 檢查當前的位址,如果和 `brkp` 相同的話,則直接透過 `my_sbrk()` 進行配置。 反之,透過每一個記憶體區塊的大小找尋下一組可以使用的記憶體區塊,並返回位址。 ```C void *find_free_block(size_t size) { /* check if we are at top of heap */ if (my_sbrk(0) == brkp) return my_sbrk(size); int *ptr = my_sbrk(0); /* find free block which also has enough size */ while (1) { /* if memory is in used, skip it */ if ( *ptr & 1 ) { ptr += 1 * sizeof(int) + (*ptr >> 1) + 1 *sizeof(int); continue; } /* if size is enough, use this block */ if ((( *ptr >> 1 ) >= size) || *ptr == NULL) break; /* oops, we search to end of the memory */ if (ptr >= endp) { return (int) -1; } } return ptr; } ``` `my_free()` 則維持和原本的一樣,當需要 free 的時候,設定好 flag 就行了。 ```C void my_free(const void *ptr) { size_t *header = ((size_t *) ptr) - 1; *header &= ~1; // unmark allocated bit } ``` 最後就是我們的測試,透過記憶體位置可以看到基本的 `my_free()` 有作用了。 ```C int main(int argc, char *argv[]) { my_init(); int *a1 = my_malloc( 1 * sizeof(int)); assert(a1); *a1 = 1; printf("a1: %p, *a1 = %d\n", a1, *a1); int *a2 = my_malloc( 1 * sizeof(int)); assert(a2); *a2 = 2; printf("a2: %p, *a2 = %d\n", a2, *a2); my_free(a2); // try to free a2 int *a3 = my_malloc( 1 * sizeof(int)); assert(a3); *a3= 3; printf("a3: %p, *a3 = %d\n", a3, *a3); my_free(a3); // try to free a3 my_free(a1); // try to free a1 int *a4 = my_malloc( 1 * sizeof(int)); assert(a4); *a4 = 4; printf("a4: %p, *a4 = %d\n", a4, *a4); return 0; } // => // => a1: 0x10644f028 *a1 = 1 // => a2: 0x10644f078 *a2 = 2 // => a3: 0x10644f078 *a3 = 3 // => a4: 0x10644f028 *a4 = 4 ``` <a id="org20a7534"></a> ### [ ] TODO: 實作 3 - 實作 2 改良版 **TODO: 避免碎片化** 需要實作碎片合併 <a id="org1c79e71"></a> ### 使用情境 實作記憶體管理常式的方法有很多,在 [A Malloc Tutorial](http://www.inf.udec.cl/~leo/Malloc_tutorial.pdfo) 裡面有講解到更完整的資訊。 此題目的應用場合應該是在有限的程式空間 (flash size 很小)的情況下,需要簡單的記憶體管理機制,使用這種方式來管理記憶體雖然性能不好,但是也可能夠用。 舉例: FreeRTOS 的記憶體管理機制中, [heap\_1.c](https://github.com/coldnew/FreeRTOS-mirror/blob/master/FreeRTOS/Source/portable/MemMang/heap_1.c) 就是一種很簡單的記憶體管理方式,他描述是這樣的: ``` The simplest possible implementation of pvPortMalloc(). Note that this implementation does NOT allow allocated memory to be freed again. See heap_2.c, heap_3.c and heap_4.c for alternative implementations, and the memory management pages of http://www.FreeRTOS.org for more information. ``` 而和此題實作比較接近的,則是 FreeRTOS 的 [heap\_2.c](https://github.com/coldnew/FreeRTOS-mirror/blob/master/FreeRTOS/Source/portable/MemMang/heap_2.c) ``` A sample implementation of pvPortMalloc() and vPortFree() that permits allocated blocks to be freed, but does not combine adjacent free blocks into a single larger block (and so will fragment memory). See heap_4.c for an equivalent that does combine adjacent blocks into single larger blocks. See heap_1.c, heap_3.c and heap_4.c for alternative implementations, and the memory management pages of http://www.FreeRTOS.org for more information. ``` <a id="org5158a47"></a> ### 延伸閱讀 - [Dynamic memory Management](http://arcs.skku.edu/pmwiki/uploads/Courses/ProgrammingLanguages/p2.memManage.pdf) - [Lecture 08 - Dynamic memory Allocation](https://www.cs.cmu.edu/~guna/15-123S11/Lectures/Lecture08.pdf) - [08-MemoryMalloc](https://courses.engr.illinois.edu/cs241/fa2012/lectures/08-MemoryMalloc.pdf) - [A Malloc Tutorial](http://www.inf.udec.cl/~leo/Malloc_tutorial.pdfo) - [Project 3: A Custom malloc() and free()](https://s3.amazonaws.com/iedu-attachments-question/38edd7d5a7535016c8f914a7a871ad0d_feb9cc6ba00f1fc42cbe607593cf02c1.pdf) - [A quick tutorial on implementing and debugging malloc, free, calloc, and realloc](https://danluu.com/malloc-tutorial/) - [My mallock using mmap](https://people.kth.se/~johanmon/courses/id2206/assignments/maplloc.pdf) - [What does brk( ) system call do?](https://stackoverflow.com/questions/6988487/what-does-brk-system-call-do) - [SystemProgramming - Memory, Part 2: Implementing a Memory Allocator](https://github.com/angrave/SystemProgramming/wiki/Memory%252C-Part-2%253A-Implementing-a-Memory-Allocator) - [Implementing malloc](http://moss.cs.iit.edu/cs351/slides/slides-malloc.pdf) - [Memory Allocation](https://hackmd.io/s/B1SRlfeee) - [Understanding glibc malloc](https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/) - [Optimizing Dynamic Memory Management](https://www.cs.princeton.edu/courses/archive/spr11/cos217/lectures/20DynamicMemory2.pdf): 這份講解了 k&r 的 Heap Manager <a id="org355dfe3"></a> ## [ ] Q4 考慮以下 C 程式在 GNU/Linux 中,透過 linked list 來實作動態記憶體管理 (malloc 和 free),虛擬記憶體的使用如下圖,初步的程式如下方,要注意到程式碼並不完整,也不能在多執行緒環境安全運用。 請改寫 `malloc` 程式碼使其正確運作,並提供對應的 `free` 實作。 ![](https://i.imgur.com/NC8J0Hv.png) ```C #include <stddef.h> #include <unistd.h> #include <pthread.h> struct header_t { size_t size; unsigned is_free; struct header_t *next; } *head, *tail; static struct header_t * get_free_block(size_t size) { struct header_t *curr = head; while (curr) { if (curr->is_free && curr->size >= size) return curr; curr = curr->next; } return NULL; } pthread_mutex_t global_malloc_lock; void *malloc(size_t size) { size_t total_size; void *block; struct header_t *header; if (!size) return NULL; if ((header = get_free_block(size))) { header->is_free = 0; return ? /* FIXME: */ } total_size = sizeof(struct header_t) + size; if ((block = sbrk(total_size)) == (void *) -1) return NULL; header = block; header->size = size; header->is_free = 0; header->next = NULL; // ... /* FIXME: */ return ? /* FIXME: */ } ``` <a id="orgce6c870"></a> ## [X] Q5 假設下方 C 程式檔名為 `fork.c` ,在 GNU/Linux 上編譯得到名為 `fork` 的執行檔,我們可用 `./fork | wc -c` 計算輸出的 `-` 字元,請解釋程式行為和輸出的 `-` 字元數量的關聯。 ```C #include <stdio.h> #include <sys/types.h> #include <sys/wait.h> #include <unistd.h> int main() { for (int i = 0; i < 3; i++) { fork(); printf("-"); } wait(NULL); wait(NULL); wait(NULL); return 0; } ``` <a id="org9a2d7f0"></a> ### 思考 & 想法 這題乍看之下應該是要產生出 `14` 個 `-` 符號,然而實際執行卻是生出了 `24` 個,從 [C 语言的谜题](http://coolshell.cn/articles/945.html) 可以注意到, `printf()` 呼叫的時候,並不會馬上把資料寫入到 `stdout` 去,而是會先暫存到一個緩衝區中,也許問題就在這邊。 讓我們加入 `fflush()` 強迫 `printf()` 將資料從緩衝區寫到 `stdout` 看看。 ```C for (int i = 0; i < 3; i++) { pid_t pid = fork(); printf("-"); fflush(stdout); } wait(NULL); wait(NULL); wait(NULL); ``` 這樣的執行結果,就是我們想要的 `14 個 -` ,可見問題的確出在 `printf()` 沒有立即將緩衝區的資料寫入到 `stdout` 而導致 fork 的時候連緩衝區的資料一起 fork 一份了。 要了解整個程式的 fork 流程,我們可以把原本程式稍微改成下面這樣,再透過 `pstree` 去顯示 ```C #include <stdio.h> #include <sys/types.h> #include <sys/wait.h> #include <unistd.h> int main() { for (int i = 0; i < 3; i++) { fork(); printf("-"); } wait(NULL); wait(NULL); wait(NULL); sleep(10); return 0; } ``` 將檔案編譯成 `fork.out` 並透過 `pstree` 去觀察 fork 的狀況 (n 個迴圈總共會出現 2^n - 1 個 process, 此例來看就是有 8 個 process) ./fork.out & pstree -p | grep fork.out |-fork.out(14759)-+-fork.out(14762)-+-fork.out(14766)---fork.out(+ | | `-fork.out(14767) | |-fork.out(14763)---fork.out(14765) | `-fork.out(14764) 可以看到此題迴圈跑 3 次的狀況,共出現了 8 個 process,用圖片表達的話就是這樣。 ![](https://i.imgur.com/EBSCVxs.png) 當我們的 `printf()` 有把透過 `fflush()` 把緩衝區清乾淨的狀況下,就會像上圖一樣,最終印出 14 個 `-` 。 那緩衝區沒弄乾淨的情況呢? 就會變成這樣了,在 `fork()` 下面的 `-` 就是被複製走而多出來的傢伙。 ![](https://i.imgur.com/5tHXFVO.png) <a id="org761c0f9"></a> ### 延伸閱讀 - [For (int i=0;i<10;i++) fork(); how many process will be created?](https://www.quora.com/For-int-i-0-i-10-i++-fork-how-many-process-will-be-created) - [Visually what happens to fork() in a For Loop](https://stackoverflow.com/questions/26793402/visually-what-happens-to-fork-in-a-for-loop) - [一個 fork 的面試題](http://www.cnblogs.com/ittinybird/p/4492098.html) - [C 语言的谜题](http://coolshell.cn/articles/945.html) - [请问下面的程序一共输出多少个“-”?](https://www.nowcoder.com/questionTerminal/1f6cc9c0ef354f86b1727c6c030a1a19) - [Does fork() immediately copy the entire process heap in Linux?](https://unix.stackexchange.com/questions/155017/does-fork-immediately-copy-the-entire-process-heap-in-linux)