2021q1 Week1/2/3/4

Uduru0522

/**
 * 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);
}

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: 調整指標至如下形式

digraph G{
    rankdir = LR
    splines=ortho
    
    node[
        style = filled;
        shape = record;
        color = darkolivegreen2;
    ] entry1 entry2
    
    node[color = gray73, shape = box] e1_next e2_next e1_prev e2_prev
    node[color = lightgoldenrod1, shape = cds] pos
    node[style=invis, shape=record] ivs1 ivs2
    
    {rank = same; e1_prev; e2_prev; ivs1;} 
    {rank = same; entry1; entry2;} 
    {rank = same; e1_next; e2_next; ivs2;}
    
    e2_prev -> e2_next;
    e2_prev -> e1_prev -> ivs1 [style=invis];
    e2_next -> e1_next -> ivs2 [style=invis];
    e1_prev -> entry1 -> e1_next;
    e1_prev -> entry2 -> e1_next;
    e1_next -> entry2 -> e1_prev [constraint=false];
    pos -> e2_prev [shape=none];
}

• 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 上的空間。這樣做的原因主要是效能考量，有以下兩點:

1. 分配 heap 空間較直接儲存於 stack 上更費時，因此為短字串分配 heap 空間的時間開銷較大
2. 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) + cn=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(nlogn)\)，演算法需以 list 的中心點切割，使兩個 sub-list 皆盡量等長，再對 sub-list 做 merge sort，故 worst case 的複雜度與 best case 相同，應為：

\[ T(n) = T(\frac{n}{2})+T(\frac{n}{2})=O(nlogn) \]

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

digraph G {

        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 1 | <ref>  }"]
        b [label="{ <data> 3 | <ref>  }"];
        c [label="{ <data> 5 | <ref>  }"];
        g [label="{ <data> 7 | <ref>  }"];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:g -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d [label="{ <data> 2 | <ref>  }"]
        e [label="{ <data> 4 | <ref>  }"];
        f [label="{ <data> 6 | <ref>  }"];
        d:ref:f -> e:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        e:ref:f -> f:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        node [shape=plaintext]
        "sublist B"->a [style=invis]
        "sublist A"->d [style=invis]
}

此時 merge 將需要 m + n - 1 次的 comparison，根據 Wikipedia，此數值最高為 \(n ⌈lg n⌉ − 2⌈lg 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。