2021q1 Week1/2/3/4

課堂問答簡記
請填入你的 GitHub 帳號名稱

Uduru0522

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

linux/list.h 的 list_swap() 實做原理？

/**
 * list_swap - replace entry1 with entry2 
 *             and re-add entry1 at entry2's position
 * @entry1: the location to place entry2
 * @entry2: the location to place entry1
 */
static inline void list_swap(struct list_head *entry1,
			     struct list_head *entry2)
{
	struct list_head *pos = entry2->prev;

	list_del(entry2);
	list_replace(entry1, entry2);
	if (pos == entry1)
		pos = entry2;
	list_add(entry1, pos);
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

先試著把一些函式展開：






































static inline void list_swap(struct list_head *entry1,
			      struct list_head *entry2)
{
    struct list_head *pos = entry2->prev;

    /* list_del(entry2); */{
        /* __list_del_entry(entry2); */{
            if (!__list_del_entry_valid(entry2))
		        return;
            /* __list_del(entry2->prev, entry2->next); */{
                entry2->next->prev = entry2->prev;
                WRITE_ONCE(entry2->prev->next, entry2->next);
            }
        }
        entry2->next = LIST_POISON1;
        entry2->prev = LIST_POISON2;
    }
    
    /* list_replace(entry1, entry2); */{
        entry2->next = entry1->next;
        entry2->next->prev = entry2;
        entry2->prev = entry1->prev;
        entry2->prev->next = entry2;
    }
    
    if (pos == entry1)
        pos = entry2;
        
    /* list_add(entry1, pos); */
        /* __list_add(entry1, pos, pos->next) */{
            if (!__list_add_valid(entry1, pos, pos->next))
                return;
            pos->next->prev = entry1;
            entry1->next = pos->next;
            entry1->prev = pos;
            WRITE_ONCE(pos->next, entry1);
        }
}

Line 11,12: 將 entry2 的前後接上，其中 WRITE_ONCE() 可以防止賦值的指令被拆分成多個小指令，或是在多執行緒被其他函式調用時時造成錯誤。

#define WRITE_ONCE(var, val) (*((volatile typeof(val) *)(&(var))) = (val))

Line 15,16: 將 entry2 自 list 之中分離出來，經過 __list_del_entry_valid() 確認資料可用之後, 把當下 entry2 的 prev 以及 next 設為預設的 dead pointer (LIST_POISON1 以及 LIST_POISON1)，當調用 LIST_POISON 時會導致 Page Fault。
Line 20-23: 調整指標至如下形式

Line 31-36: 利用 list_add(new, prev, next) 將新節點插入 prev 及 next 之間的行為，將 entry1 加入至原先 entry2 所在地點。
Line 26,27 用以對應傳入的兩個 node 是 XXX -> entry1 -> entry2 -> YYY 的情況。

Nahemah1022

1. 在 lab0 作業中的 merge_sort 有什麼可以改進的地方

merge sort 本身
- 程式中的註解太過簡短，可以針對 if 與 else 兩個區段分別註解會更加清晰
- 變數的命名也不夠直覺，indirect 的目的無法直接望文生義
其他做法
- 有嘗試過使用 quick sort 算法，但因為測試資料中含有 quick sort 的 worst case，造成效能下降無法通過 qtest
TODO：弄清楚 qtest 如何檢驗效能

2. 在 qtest 中 Address Sanitize 的問題與解決方

存取到超出 bool 本身一個 byte 大小的空間造成錯誤
- 可以將所有 bool 都改成 int，但會需要連帶修改其他東西，不好維護
- 我的方法是直接分成兩個不同參數的 function，可以解決問題但可能會讓兩個 fucniton 的內容過於相似，應有更好的辦法

RZHuangJeff

1. 在quiz3中`xs_trim`如何比對欲移除的字元

問題
由於xs_trim支援讓呼叫者自訂欲剪除的字元，因此若欲排除的字元太多使用逐一比對的話將造成執行效能低落，因此引入另外的方法。
解決方法
透過查表的方式直接確認是否欲移除該字元。

在程式碼中，可以看到一個長度為32的mask陣列，mask陣列的初始值為0，並且可透過兩個macro: set_bit及check_bit進行建表及查詢。在通常的執行環境中，單一個位元所站的空間為1個byte，而程式碼中mask中元素的型態為uint8_t，因此可以將所有不同的字元對應到mask中的不同個bit，而這個工作由set_bit完成，具體的內容如下:

#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

可以發現到set_bit將給定的byte分成上5位元及下3位元，分別成為存取mask的索引及其中的第幾個位元。以byte = 'A'為例: A的ascii碼為0x41，則存取mask的索引為8，並且其對應到的是mask[8]中的第2個字元(1 << 1 是2)。找到對應的位元後則透過or將該位元設成1。
表建好後，透過check_bit在常數時間內查詢該表，便可得知該字元是否為欲刪除之字元，check_bit的具體內容為:

#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)

由上可知，只要透過與set_bit相同之方式找到mask中對應的位元，並且確認該位元是否為1。

2. 為何`xs_new`要分兩種方式儲存短字串及長字串

在xs_new中是將長度小於 16 的字串放在 stack，並為長度大於 16 的字串分配 heap 上的空間。這樣做的原因主要是效能考量，有以下兩點:

分配 heap 空間較直接儲存於 stack 上更費時，因此為短字串分配 heap 空間的時間開銷較大
stack 的較 heap 接近先前已使用過的位址，如此可善用 cache 的 spatial locality

hankluo6

https://hackmd.io/@hankluo6/2021q1quiz1

1. quiz2 的 get_middle 方式遇到的 worst case

上課時將 merge sort 想成 quick sort，merge sort 的 worst case 不應該為不平衡的切割，如果為不平衡切割的話，複雜度應為：

T (n) = T (n - 1) + c n = T (1) + \frac{(n - 1)}{n} - \frac{(n - 1) (n - 2)}{2} = O (n^{2})

這樣就與 quick sort 一樣為

O (n^{2})

，但 merge sort 的概念為 divide and conquer，worst case 應為

O (n l o g n)

，演算法需以 list 的中心點切割，使兩個 sub-list 皆盡量等長，再對 sub-list 做 merge sort，故 worst case 的複雜度與 best case 相同，應為：

T (n) = T (\frac{n}{2}) + T (\frac{n}{2}) = O (n l o g n)

而會造成 merge sort 產生 worst case 的為 merge 時 compare 的次數，當兩個 sub-list 間的大小排序為互相交叉時會發生：

此時 merge 將需要 m + n - 1 次的 comparison，根據 Wikipedia，此數值最高為

n ⌈ l g n ⌉ - 2 ⌈ l g n ⌉ + 1

。

2. Linux 核心的 `list_sort.c` 的切割方式

實現 botton-up 方式的 merge sort，以每兩個元素為單位切割，當合併後產生兩個

2^{k}

數量的 list 時，便會合併成

2^{k + 1}

，並保證

2^{k - 1}, . . ., 2^{1}

數量的 linked list 皆存在，這樣就能維持每次 merge （包含最後一次 merge_final）皆最高只會有 2:1 的數量比例，所以只要

3 \times 2^{k}

數量的元素都可以容納在 cache 中，便能減少 cache miss。