---
tags: Linux Kernel
---
# 2023q1 Homework3 (quiz3)
contributed by < [`chun61205`](https://github.com/chun61205) >
> [2023q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗一
### 研讀 data alignment
#### Data Alignment
data alignment 的意思是， data 的 address 可以公平的被 $1,2,4,8$ ，這些數字整除，也就是 $2$ 的 $n$ 次方 ($n\in N$)。換句話說，這些 data object 可以用 $1,2,4,8$ byte 去 alignment 。
#### CPU 資料存取
CPU 會根據電腦系統架構決定一次要存取的 byte 數，32 位元的 cpu 一次可以讀取 32 bit 的資料，64 位元一次可以讀取 64 bit 。
因此，如果定義個了一個 struct ：
```c
struct s1 {
char c;
int a;
}
```
原本推論 char 為 $1$ byte，而 int 為 $4$ byte ，兩個加起來應該為 $5$ byte，然而實際上為 $8$ byte，由於 int 為 $4$ byte ，所以 char 為了要能 alignment $4$ byte 就多加了 $3$ byte 進去 ，使得 cpu 存取速度不會因 address 不是在 $4$ 的倍數上，存取變慢。
### 研讀 [`treesort.c`](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)
#### 節點
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
* 該資料結構 `node_t` 紀錄了紅黑數的節點，包括了 `color` 、左右節點 `left` 和 `right` ，在原本陣列中的下一個節點 `next` ，和其值 `value` 。
* 其中顏色的定義如下：
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
```
紅色是 `0` ，黑色則是 `1` 。
* 值得注意的是，這裡的 `color` 同時拿來儲存 parent 的位置和當前節點的 color。因為指標的 alignment 方式是 $8$ bytes ，也就是指標的地址必須是 $8$ 的倍數，換句話說 `node_t` 的指標的最後 $3$ 個 bit 必定是 $0$ ($3$ bits 最高能表示到 $7$ ，因此最後 $3$ 個 bit 必定用不到)。
因此可以判斷：
* 最後一個 bit 可以拿來儲存 color ，且只要把最後 $3$ bit 設成 `0` ，剩下的就是 parent 的位置。
```c
#define rb_parent(r) ((node_t *) (((r)->color & ~7)))
#define rb_color(r) ((color_t) (r)->color & 1)
```
* 設定位置的話則需要考慮到當前節點的顏色
```c
#define rb_set_parent(r, p) \
do { \
(r)->color = rb_color(r) | (uintptr_t) (p); \
} while (0)
```
* 設定顏色只要針對 `color` 的最後一個 bit 操作就好。
```c
#define rb_set_red(r) \
do { \
(r)->color &= ~1; \
} while (0)
#define rb_set_black(r) \
do { \
(r)->color |= 1; \
} while (0)
```
#### `cmap_internal`
```c
struct cmap_internal {
node_t *head;
/* Properties */
size_t key_size, element_size, size;
cmap_iter_t it_end, it_most, it_least;
int (*comparator)(void *, void *);
};
```
該資料結構 `cmap_internal` 用以紀錄 `map` 的資料。
#### `tree_sort`
:::spoiler 完整程式碼
```c
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = &(*list)->next;
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = &(*list)->next;
}
*list = NULL;
*record = first;
free(map);
}
```
:::
這裡的 `tree_sort` 從 `list` 一個一個讀取節點，並插入到紅黑樹，隨後再利用 `cmp_next` 將排序好的節點一個一個接在 `list` 。
---
## 測驗二
### 解釋程式碼原理
#### 資料結構
```c
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) node->parent_balance & ~3;
}
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)node->parent_balance & 3;
}
```
從以上程式碼可以觀察到， avl tree 有三種狀態，標為 `AVL_NEUTRAL`, `AVL_LEFT`, `AVL_RIGHT` 。此外，這段程式碼也有利用 data alignment 的原理，將 `parent_balence` 的最後兩位元當作該節點的狀態。
---
## 測驗三
## 測驗四
### 解釋程式碼原理
```c
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
shift = (x > 0xF) << 2;
x >>= shift;
shift = (x > 0x3) << 1;
x >>= shift;
```
這幾段程式碼原理是，若是 `x` 的前 $16, 24, 28, 30$ 個 bits 不全為 `0` 則分別向右移 $16, 8, 4, 2$。換句話說就是利用 binary search 來找到 MSB。
這些總共 shift 的位數會全部被累加到 `r` ，用來表示 $log(x)$ 的整數部份。
```c
r |= shift;
```
之所以能夠使用 `|=` 是因為這些 shift 的位數全部都是 2 的冪。
最後在執行這段程式碼時
```c
return (KKKK) + 1;
```
1. `r` 必須先加上 `shift` (`r | shift`) 。
2. `x` 最高會有兩位數因此需要做和上面一樣的操作 (`x >> 1`) 。
3. 最後，考慮到 `x = 0b01` 的情況，必須再加上 `1` 。
因此 `KKKK` 為 `(r | shift | x >> 1)`
Sign in with Wallet
Connect another wallet