---
# System prepended metadata

title: 'linux2023: yeeecheng'

---

# linux2023: yeeecheng

## 測驗α-1
## 測驗α-2

由於```BBBB```小題答錯，因此重新思考這個部分。
```AAAA```小題的答案是```st_replace_right(del, least)```，功能是將欲刪除節點使用其右子樹最小值的節點取代，而因為有改變樹的高度，因此需要 ```st_update```這棵樹，問題是要從哪個節點開始 update ，設想以下情況：

1. 欲刪除 val=4 的節點，須從其右子樹找到最小值節點 val=5，刪除前的高度如圖所示。 
```c
struct st_node *least = st_first(st_right(del));
```
![](https://hackmd.io/_uploads/B16nCGqnh.jpg)

2. val=5 的節點會取代 val=4 的節點，並將 val=5 的右節點 val=7 遞補上來。
```c
/* 對應的程式碼 */
st_replace_right(del, least);
```
![](https://hackmd.io/_uploads/ByFNSzj22.jpg)

3. 最後，需要將右子樹的高度更新，更新位置從 val = 7 的節點開始，但程式碼提供的變數無法找到最下面的節點，因為 ``` st_replace_right(del, least)```已經將least的右節點改為 val = 10 的節點，因此若使用```st_update(root, st_right(least))```找到會是 val=10 的節點，並非 val=7 的節點。因此應該將程式碼變更為以下：
```c
oid st_remove(struct st_node **root, struct st_node *del)
{
    if (st_right(del)) {
        struct st_node *least = st_first(st_right(del)), *least_parent = st_parent(least);
        if (del == *root)
            *root = least;

        st_replace_right(del,least); //AAAA
        
        /* BBBB */
        if (st_left(least_parent)) && least_parent != del)
            st_update(root, st_left(least_parent)); 
        else
            st_update(root, least_parent);
        return;
    }

    if (st_left(del)) {
        struct st_node *most = st_last(st_left(del)), *least_parent = st_parent(least);;
        if (del == *root)
            *root = most;

        st_replace_left(del, most);//CCCC
        /* DDDD */
        if (st_right(least_parent)) && least_parent != del)
            st_update(root, st_right(least_parent)); 
        else
            st_update(root, least_parent);
        return;
    }
    // ...
}
```
如此以來才能夠實現從更新高度的功能。




## 測驗α-3

## 測驗β-1
```c
#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return (sz + mask << 1) & ~mask;   
    }
    return (((sz + mask) / alignment) * alignment);
}
```
根據記憶體對齊的規則，sz 需為 aligment 的倍數。因此，若 sz 不能被 aligment 整除的話，則需要將 sz padding 至下一個能被 aligment 整除的數。而此 padding 值的範圍是 ```1 ~ aligment-1```，因此在函式 align_up 中，定義mask(即 aligment-1) 作為 padding 的值，並得到```((((sz + mask) / alignment) * alignment)```，照理來說，使用此式子可以處理任意的 sz  與 aligment，但函式中多判斷了```(alignment & mask) == 0```，用意是想利用 power of 2 在bitwise 的特性，即 aligment 為2的指數時， ```aligment-1``` 的二進位會是0111...的形式，則```& ~mask```便能夠實現如同先除 aligment 再乘 aligment 的運算，兩者的差異在於運算的執行效率，因為使用```*```,``` / ```編譯成組合語言所需的行數比使用```&```,```|```多，因此在計算完```sz+mask```後，使用```& ~mask```能夠更快得到結果。

## 測驗β-2
在``` linux/include/linux/kernel.h ```找到以下 macro
```c
/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask)	__ALIGN_KERNEL_MASK((x), (mask))
#define PTR_ALIGN(p, a)		((typeof(p))ALIGN((unsigned long)(p), (a)))
#define IS_ALIGNED(x, a)		(((x) & ((typeof(x))(a) - 1)) == 0)
```
其中的 ```__ALGIN_KERNEL```與```__ALGIN_KERNEL_MASK```在``` linux/include/uapi/linux/kernel.h```中
```
#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))
```
macro ```__ALIGN_KERNEL_MASK(x, mask)```的定義與題目中 ```MMMM```的方法相同，而```__ALIGN_KERNEL(x, a)```則對應到 ```mask = aligement -1```

## 測驗γ-1

## 測驗γ-2

## 測驗γ-3