---
# System prepended metadata

title: 2023q1 Homework3 (quiz3)
tags: [Linux Kernel]

---

---
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 。
![](https://i.imgur.com/17AfP43.png)
![](https://i.imgur.com/r6aGw6e.png)
因此，如果定義個了一個 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)`
