2019q1 Homework1 (list)

contributed by < flawless0714 >

Linux source code version: 4.20.13

執行環境

OS: Lubuntu 18.04.1 LTS (Bionic Beaver)
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping:            9
CPU MHz:             700.030
CPU max MHz:         3500.0000
CPU min MHz:         400.0000
BogoMIPS:            5808.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            4096K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d

自我檢查清單

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

使用 macro 實作 linked list 可增加可讀性。考慮以下 linked list 走訪程式(已省略 list 建立、新增節點之實作。iterator為用來走訪 list 的指標)，看到 macro 名稱就可以直覺知道其功用，相較之下，看到 for 迴圈後還需要思考其中初始值、條件式及遞增式的操作。

struct num {
    struct list_head node;
    int number;
};

/*---- Implement directly ----*/
for (iterator = head->next; iterator != head; iterator = iterator->next) {
    printf("%d\n", iterator->number);
}
/*----------------------------*/

/*---- Implement with macro ----*/    
list_for_each(iterator, &head) {  
    printf("%d\n", list_entry(iterator, struct num, node)->number);
}    
/*------------------------------*/

一般 function call 會有 stack 儲存/回復的開銷。

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

NetLabel
此為 kernel 中用於為通訊封包(network, IPC…)附加標籤(security label)用的 framework。

以下為 NetLabel 內其中一個使用到 list_head 的資料結構

struct netlbl_af4list {
    __be32 addr;
    __be32 mask;
    
    u32 valid;
    struct list_head list;
}

以下程式碼用途為在 address list 內尋找對應的 ipv4 節點。其中可以發現到走訪 list 時使用的是 RCU 版本的走訪 macro,由此可得知這個 address list 被讀取的頻率大於更新頻率。

/**
 * netlbl_af4list_search - Search for a matching IPv4 address entry
 * @addr: IPv4 address
 * @head: the list head
 *
 * Description:
 * Searches the IPv4 address list given by @head.  If a matching address entry
 * is found it is returned, otherwise NULL is returned.  The caller is
 * responsible for calling the rcu_read_[un]lock() functions.
 *
 */
struct netlbl_af4list *netlbl_af4list_search(__be32 addr,
                                             struct list_head *head)
{
    struct netlbl_af4list *iter;

    list_for_each_entry_rcu(iter, head, list)
        if (iter->valid && (addr & iter->mask) == iter->addr)
            return iter;

    return NULL;
}

__list_add_rcu
此 macro 用於將新節點插入 list 中。考慮以下程式碼，雖然只是簡單的節點插入，但其中為什麼要用 rcu_assign_pointer() 來 assign 節點呢？這是為了保證在這之前的 assigments 一定會在執行此 assignment (rcu_assign_pointer())之前完成，還有避免編譯器最佳化造成過早完成 assignment (此舉可能會造成 reader 拿到更新到一半的資料，從程式碼中可以看到13、14行正在初始化新節點，假如 assign 在這兩行之前完成，則 reader 就有可能拿到空指標)。

















/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add_rcu(struct list_head *new,
        struct list_head *prev, struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

    new->next = next;
    new->prev = prev;
    rcu_assign_pointer(list_next_rcu(prev), new);
    next->prev = new;
}

Scheduler
以下程式碼(僅擷取部份)為功用為進行排程器的初始化(為相關 struct 分配記憶體、初始化 root_task_group、初始化每個 CPU 的 rq queue、將 init_task 行程轉變為 idle 行程)。其中 list_add 這個 macro 把 root_task_group.list (系統中所有 task 都屬於此 group)這個鏈結插入 task_groups (插入後 task_groups 會從原本的 task_groups.next = task_groups (LIST_HEAD_INIT 這個 macro 做的，它會把新建立的節點的 prev 及 next 指標指向自己)變成 task_groups.next = root_task_group.list。這邊我們就可以聯想到 container_of 這個 macro 的用途，因為 list_head 在 Linux kernel 中都只被當作結構體的成員，所以我們才會需要這個 macro 來做 offset，找到現在 linked list 所指到的成員的本體，例如本文中的 root_task_group。
```
#ifdef CONFIG_CGROUP_SCHED
task_group_cache = KMEM_CACHE(task_group, 0);

list_add(&root_task_group.list, &task_groups);
INIT_LIST_HEAD(&root_task_group.children);
INIT_LIST_HEAD(&root_task_group.siblings);
autogroup_init(&init_task);
#endif /* CONFIG_CGROUP_SCHED */
```

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
- typeof 功用為取得給定變數的資料型態
- typeof 在程式碼中可以作為靜態分析的工具，假如給定的變數的資料型態不如預期，編譯器會有警告訊息。考慮以下程式碼，其用途為檢查傳入之參數是否為傳入之資料型態，假如資料型態不同，則會跳出此警告 warning: comparison of distinct pointer types lacks a cast，此段警告為當比較兩個不同型態的指標時未使用 cast 轉型。如此就可以發現程式碼中的 typo 等問題了。此段程式碼原理為先以參數 type 宣告一變數 a，再以令個參數 x 宣告一變數 b，之後再對兩個變數做 address of 的比較(此處假如兩者資料型態不同，編譯器就會跳警告了)，然後把結果轉為 void 型態，以使得此段程式在編譯器最佳化時就被刪除，以免在執行時期遭到濫用。
```
#define typecheck(type,x) \
({  type a; \
    typeof(x) b; \
    (void)(&a == &b); \
    1; \
})
```
解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
LIST_POISONING 這樣的設計有何意義？
linked list 採用環狀是基於哪些考量？
什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
什麼情境會需要需要找到第 k 大/小元素呢？又，你打算如何實作？
list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
for_each 風格的開發方式對程式開發者的影響為何？
- 提示：對照其他程式語言，如 Perl 和 Python
程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
- 提示: 對照看 Doxygen
tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
tests/ 目錄的 unit test 可如何持續精進和改善呢？

筆記

RCU
- 在 grace period 期間若有新的 reader，則其拿到的資料為更新後的資料 (writer運作流程為更新指標–>grace period–>回收記憶體)
- __READ_ONCE_SIZE
  某些情況下處理器對記憶體的讀寫不是一次完成的，如此可能會有 data race 發生，而此 macro 可以保證讀寫一次完成。
- 多個 writer
  當 writer 不只一個時，會需要
__builtin_memcpy
一個由編譯器實做的 memcpy，不需要引用任何標頭檔。編譯時期此段程式會直接以組合語言的形式展開，類似 macro。
Con Kolivas
一位職業麻醉師，同時也是 Linux kernel 開發者之一。在 scheduler 上有不小的貢獻 (CFS 前身)。據 Kolivas 本人表示，剛接觸 Linux kernel 時，甚至沒學過 C 語言
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 →
CFS (Complete Fair Scheduler)
- Priority 較低的 task 有比較高被執行的機率，以避免其被拖延較久才被執行，可以說是名符其實。
- Scheduling Tick
  每次觸發時，排程器會計算每個正在執行的 task 的執行時間，藉此決定是否進行 task 的 context-switch。觸發頻率為編譯核心時的設定參數，常見有100hz、1000hz 。

2019q1 Homework1 (list)

執行環境

自我檢查清單

筆記

參考資料

tags: `linux2019`

2019q1 Homework1 (list)

執行環境

自我檢查清單

筆記

參考資料

tags: linux2019

Read more

BORE (Burst-Oriented Response Enhancer) CPU Scheduler

[jitterdebugger](https://github.com/igaw/jitterdebugger) 介紹

[Scheduler BPF](https://lore.kernel.org/bpf/YUKhCHarl+Ng1xxR@carbon.dhcp.thefacebook.com/T/#mcd3ce3ed88a21ac23daa96417d3c9934cafbb585)

2019q1 Homework4 (smallsys)

tags: `linux2019`