# 2019q3 Homework1 (review)
contributed by < `ArielWu0203` >
###### tags: `linux_2019`
* [作業要求](https://hackmd.io/@sysprog/rJM4SPw8S)
## 第一周測驗題 Q1
:::info
在 Linux 核心原始程式碼找出類似的 alignment 巨集並解釋其作用
:::
* Data alignment macro : [tools/testing/scatterlist/linux/mm.h](https://elixir.bootlin.com/linux/latest/source/tools/testing/scatterlist/linux/mm.h#L33)
```cpp
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
```
### 作用
* a 為 2 的倍數時，可以做對齊 (alignment) 。例如 :
* x = 0x1011 , a = 4 時，會輸出 0x1014。
* x = 0x1014 , a = 4 時，會輸出 0x1014。
* x = 0x1016 , a = 4 時，會輸出 0x1018。
* ***(typeof(x))(a) - 1)***
是為了得到需要對齊的位數。
* ***((x) + (mask)) & ~(mask)***
*x + mask* 要讓 x 可以加到下個可以對齊的地方。
再用 *&(~mask)* 就可以將多餘的位數歸為 0，即可對齊。
* 因為對齊是以位元 (bit) 為基準，所以 a 必須為 2 的倍數(1,2,4,8...)。
### 目的
* cpu 不會一次抓取 1 byte 的資料，因為這樣太慢了，所以 cpu 會一次抓取 4 bytes (根據電腦規格而定)，而且是按照==順序==去取，例如 : 第一次存取 0~3 ，第二次存取 4~7。
因此，若在存取資料的分布在 1~4，cpu 就需要存取兩次(0~3 , 4~7)，會造成存取速度降低。
* [reference : 課程資料--記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7?type=view)
## 第一周測驗題 Q2
:::info
解釋程式運作原理並在 GitHub 找出實際應用的程式碼
:::
```cpp
#include <stdint.h>
#define INT_SIZE_OF(n) \
((sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1))
```
* 和 Q1 類似，也是 data alignment。
**(sizeof(int) - 1)** 為需要對齊的位數。
**sizeof(n) + sizeof(int) - 1** 讓 n 可以加到下個可以對齊的地方，在用 *&(~(sizeof(int) - 1))* 將多餘的位數歸為 0，即可對齊。
### 運作原理
* 假設 m 為一整數， 且 n 不為 4 的倍數， n 的範圍為
$4m<n<4(m+1)$
* 為了要讓 n 可以到下個對齊的地方，加上 *sizeof(int) - 1* ，則 n 的範圍為 $4(m+1)\leq n<4(m+2)$
* 若 n 為 4 的倍數， n 加上 *sizeof(int) - 1* 不會到下一個單位(4 bytes)，所以對齊後，仍然為 n
### GitHub 實際應用的程式碼
* [link](https://github.com/weolar/miniblink49/blob/master/vc6/include/crt/stdarg.h)
```cpp=
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
#define va_start(ap,v) ( ap = (va_list)_ADDRESSOF(v) + _INTSIZEOF(v) )
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
```
## 課程簡介和注意須知 : C語言可不是只有語法
:::info
思考下方程式碼的作用，以及如何應用
:::
```cpp=
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;
}
```
### 作用
若有 1 byte 要反轉。
> n = ++1001++ ++1011++
> 先反轉以 4 bits 為單位 -> n = ++1011++ ++1001++
> 再反轉以 2 bits 為單位 -> n = ++11++ ++10++ ++01++ ++10++
> 再反轉以 1 bits 為單位 -> n = ++1++ ++1++ ++0++ ++1++ ++1++ ++0++ ++0++ ++1++
### 目的
由於用迴圈對一個個位元做反轉，效率太低了，所以以 n bits 當作單位，來做反轉。
### 實驗測試
[github : reverse_test](https://github.com/ArielWu0203/reverse_test)
* reverse with loop
一個個 bit 做反轉。
```cpp=
int32_t reverse(int32_t x){
int32_t val = 0; int32_t i = 0;
for (i = 0; i < 32; i++) {
val = (val << 1) | (x & 0x1);
x >>= 1;
}
return val;
}
```
* Reverse integer bitwise without using loop
以 n bits 當作單位，來做反轉。
```cpp=
int32_t reverse(int32_t new){
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
return new;
}
```
* 測試結果
==reverse without loop== 程式的完成時間比較短。
### 應用
* crc 校驗 : [ linux/bitrev.h](https://elixir.bootlin.com/linux/v4.12/source/include/linux/bitrev.h)
* [linux/crc32.h](https://elixir.bootlin.com/linux/v4.12/source/include/linux/crc32.h#L76)
```cpp=
#define ether_crc(length, data) bitrev32(crc32_le(~0, data, length))
#define ether_crc_le(length, data) crc32_le(~0, data, length)
```
## 第一週課程進度
### Windows / Ubuntu 雙系統安裝
1. 建立磁碟分割區
* 按住Win + X，選擇`磁碟管理`。
* 選擇剩餘空間較大的可分配磁碟，右鍵並選擇*壓縮磁碟區*，這裡我選了 300GB 。
2. 關閉快速啟動
* 按住Win + X，選擇`電源選項` `其他電源選項` `選擇按下電源按鈕時的行為` `關閉快速啟動`。
3. 關閉 Secure Boot
* 重啟進入 BIOS ，我的電腦是 ASUS ，按 F2
* `Security` `Secure Boot` `Disabled`
4. USB 開機
* [UNetbootin](https://justhodl.blogspot.com/2018/01/unetbootin-ubuntu-linux-usb-windows.html)
5. 安裝
* 插 USB ，重啟進入 BIOS ， 選擇 `Save&Exit` `USB_NAME(選沒有 UEFI 的)`
* 分割硬碟
* `\` 15GB
* `swap` 8GB
* `\home` 剩餘的空間
6. [Grub Customizer](https://www.jianshu.com/p/e8fbf2aef5f2)
* 為了要讓 Windows 為預設。
#### Reference
* [Windows10+Ubuntu雙系統安裝](https://www.itread01.com/content/1546486745.html)
* [輕鬆學會 Windows / Ubuntu 雙系統安裝 (簡易教學)](https://www.youtube.com/watch?v=rjpBTT6AmeU)
* [完全看懂：灌 Linux 前該怎麼分配硬碟？](https://www.techbang.com/posts/6153-fully-understand-linux-distribution-before-irrigation-how-to-drive)
### [記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7?type=view)
#### Memory
* 為什麼無法對 `void *` 做數值操作?
因為 `void` *沒有明確大小*，所以需要強制轉型(or 顯示轉型)。
* Overcommiting
* 配置還不能使用的記憶體。
* 為什麼要 Overcommiting?
VMA(The virtual memory allocator) 會使用 overcommiting ，先配置，等可以用的時候再用，因為若等到有充足的記憶體時再配置，新的要求會卡在外面處理不完。
* 為什麼使用 malloc 時要看記憶體是否可用?
因為可能 OOM killer 會因記憶體不足，而根據使用率將配置過的記憶體刪除。
* VLA (varialble-length arrays)
* 在執行的過程中，才能確定 array 所配置的大小。
* 為什麼 linux kernel 不允許 VLA?
因為有安全的疑慮。
* slab allocator
* 善用 cache memory ，增加效能。
* mmap
* 將檔案映射到記憶體上，可多對一。
* Copy-on-write
* 改過的檔案不要再放回原本的記憶體，放入新的記憶體中。
:::danger
避免只談記憶體，應該精確地提及 virtual/physical pages
:notes: jserv
:::
#### data alignmaent
* cpu 不會一次抓取 1 byte 的資料，因為這樣太慢了，所以 cpu 會一次抓取 4 bytes (根據系統而定)。
因此，若在存取資料的分布在 1~4，cpu 就需要存取兩次( 0~3 , 4~7 )，會造成存取速度降低。
### [數值系統](https://hackmd.io/@sysprog/BkRKhQGae?type=view)
* `a` 為正數時，`~a+1` 為 a 的負數。
* `x & (x - 1) == 0` 的數學意義
若 x = 12 , x-1 = 11，用 4 bits 表示。
```
x 1100
x-1 1011 (&
------------
1000
```
消除了最右邊的 1 。
而 `x & (x - 1) == 0` 表示 x 的位元中，只有一個 1，表示 x 為 $2^n,n=1,2,3...$
#### xorSwap
```cpp
void xorSwap(int *x, int *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
```
$proof$
$x = x \oplus y,\ y=y$
$y = y \oplus (x \oplus y) = (y \oplus y) \oplus x=0 \oplus x = x$
$x = (x \oplus y) \oplus x = y$
#### Detect NULL
```cpp
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
```
先看一個 byte 的大小 `((X) - 0x01) & ~(X) & 0x80`
```
~( ~(X-0x01) | X ) & 0x80
```
`~(X-0x01)` 為 `X*(-1)` ， 為 X 的負數。
`負數 | 正數` 的數學意義: X 是有正負的，及 X 為**非零數**。
所以
`~( ~(X-0x01) | X ) & 0x80 == 1` ，則表示 X 為 0。
`~( ~(X-0x01) | X ) & 0x80 == 0` ，則表示 X 不為 0。
#### Reverse integer bitwise without using loop
```cpp
new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);
```
若有 1 byte 要反轉。
> n = ++1001++ ++1011++
> 先反轉以 4 bits 為單位 -> n = ++1011++ ++1001++
> 再反轉以 2 bits 為單位 -> n = ++11++ ++10++ ++01++ ++10++
> 再反轉以 1 bits 為單位 -> n = ++1++ ++1++ ++0++ ++1++ ++1++ ++0++ ++0++ ++1++
### [C語言 : 指標](https://hackmd.io/@sysprog/HyBPr9WGl?type=view)
* `&` : the address of
* `*` : the value of
#### Funciton Pointer
* 儲存某一個涵是起始的 memory address
* Example :
```clike=
#include <stdio.h>
int Mul(int a, int b){
return a*b;
}
int FuncA(int x, int y, int (*Opt)(int, int)){
return Opt(x, y);
}
int main(){
int result = FuncA(5, 10, Mul);
printf("%d\n",result);
}
```
**typedef**
```clike=
typedef int (*MathMethod)(int, int);
int Mul(int a, int b) { return a*b; }
int Divide(int a, int b) { return a/b; }
int Calc(int x, int y, MathMethod Opt){
return Opt(x, y);
}
int main(){
int a = 8, b = 7;
printf("a x b = %d\n", Calc(a, b, Mul));
printf("a / b = %d\n", Calc(a, b, Divide));
}
```
#### C99 type
* 「陣列」、「函式」，以及「指標」都稱為 ==derived declarator types==
* Practice
> Q : 設定絕對地址為 0x67a9 的 32-bit 整數變數的值為 0xaa6，該如何寫？
> Ans :
```clike=
*(int32_t * const) (0x67a9) = 0xaa6;
// 位址需要為 const
```
#### A pointer to a pointer
##### linked list
* pointers to objects
```cpp
void remove_list_node(List *list, Node *target)
{
Node *prev = NULL;
Node *current = list->head;
// Walk the list
while (current != target) {
prev = current;
current = current->next;
}
// Remove the target by updating the head or the previous node.
if (!prev)
list->head = target->next;
else
prev->next = target->next;
}
```
* indirect pointer
```cpp
void remove_list_node(List *list, Node *target)
{
// The "indirect" pointer points to the *address*
// of the thing we'll update.
Node **indirect = &list->head;
// Walk the list, looking for the thing that
// points to the node we want to remove.
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
```
原本的 head 的 lifetime 限制在 function 內，但用 a pointer a pointer 可以增加 lifetime
Sign in with Wallet
Connect another wallet