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 進行對調,用這樣的圖來看就比較好懂了:

終於到了最後一組,來跑看看
```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) 論文一開頭的描述來看:

足以知道位元反轉 (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 內建的版本說明如下:

<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)

* 全加器:將兩個一位二進位數相加 (input: A, B, Cin) (output: S, Cout)

* 波紋進位加法器:使用多個一位全加器構成 N 位加法器

* 半加器可用以下 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 -> 該段記憶體尚未被使用

<a id="orgc49ca9f"></a>
### 實作 1 - 最簡單的 malloc
從上面的想法,可以想到每次進行 malloc 的時候,其實我們是這樣佔用記憶體的 (payload 為實際存放資料的區塊)

為了方便理解,我們首先定義自己的記憶體區塊來製作我們的記憶體管理程式,其中 `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()` 的描述是這樣的

所以我們可以這樣實作他
```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` 實作。

```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,用圖片表達的話就是這樣。

當我們的 `printf()` 有把透過 `fflush()` 把緩衝區清乾淨的狀況下,就會像上圖一樣,最終印出 14 個 `-` 。
那緩衝區沒弄乾淨的情況呢? 就會變成這樣了,在 `fork()` 下面的 `-` 就是被複製走而多出來的傢伙。

<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)