# 2021q1 Homework4 (refinement)
###### tags: `linux2021`
---
* 30 min - 兩個完整問題
* 完整問題
> 1. 問題情況鬆散、有一段歷史根源
---
## 03/18 - 一對一討論

### quiz 1 - sort
* [B[16] tree - sort](https://arxiv.org/pdf/1907.01631.pdf) / 實務上改進需注意
* 改寫時要看當下的特性，例如
* 記憶體使用率
* WCET
* real-time
* percpu - list_sort
* 符不符合更改目標環境所提出的限制
* 是不是 MT-safe
* 例如 [Timsort](https://en.wikipedia.org/wiki/Timsort) 可能因為較複雜的實作，不符合 Linux 核心精簡的原則，特別是驗證的難度，可見 [Timsort : formal verification](https://en.wikipedia.org/wiki/Timsort#Formal_verification)
* [simd sort](https://github.com/WojciechMula/simd-sort) - percpu
*

### quiz 2 - string interning
* GCC `__sync` : deprecated 過時還可以用
* 取決於 OS 或 hardware, 有些架構實做不完全、是系統呼叫、或是根本沒有
* memory barrier mode switch/transition
> can use transfer mode to suspend user mode extension
* 設計實驗時要考慮好所有情境，例如在 string interning 裡要考慮到 ref 的次數
> obsolete 過時不會用

* [intro LFP - ABA problem](https://preshing.com/20120612/an-introduction-to-lock-free-programming/) <-> [wikipedia](https://en.wikipedia.org/wiki/ABA_problem)
* 與 race condition 不同，ABA 注重過程
* [CAS](https://en.wikipedia.org/wiki/Compare-and-swap) - Linux 長使用，比 TAS 少一個指令
* risk file

:::info
**TODO**
* Linux 核心設計: 檔案系統概念及實作手法 (上)
* [Alignment in C - Seminar “Effiziente Programmierung in C”](https://hps.vi4io.org/_media/teaching/wintersemester_2013_2014/epc-14-haase-svenhendrik-alignmentinc-paper.pdf?fbclid=IwAR3nOWRxBJHbzdHix0_Z-_2sfxHyJaQol3zn_GabhUtelOlVVQM9Odwx7X4)
:::

:::danger
ASK
* Alignment why 4
* [assambly - SetPageReserved()](https://hackmd.io/@linD026/2021q1_quiz2#%E9%A1%8D%E5%A4%96)
* ```cpp
#define xs_tmp(x) \
((void)((struct { \
_Static_assert(sizeof(x) <= MAX_STR_LEN, "it is too big"); \
int dummy; \
}){1}), \
xs_new(&xs_literal_empty(), x))

:::

---

## 03/23 - code review
* [GitHub - SystemProgramming](https://github.com/angrave/SystemProgramming/wiki)
### quiz 2 - string interning
> [linD026](https://hackmd.io/@linD026/2021q1_quiz2#2-string-interning-in-%E5%A4%9A%E5%9F%B7%E8%A1%8C%E7%B7%92)
* `atomic` and `__sync`
    * `__sync` 的實作在某些硬體上根本沒有，官方也推薦新的程式碼該用別的
    * [gcc - 6.54 Legacy __sync Built-in Functions for Atomic Memory Access
](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html#g_t_005f_005fsync-Builtins)
        > These functions are implemented in terms of the ‘__atomic’ builtins (see __atomic Builtins). They should not be used for new code which should use the ‘__atomic’ builtins instead.
    * [gcc.gnu.org wiki atomic GCCMM](https://gcc.gnu.org/wiki/Atomic/GCCMM)

#### 字串處理
* `cstring cstr_cat(cstr_buffer sb, const char *str)`
    * 只對 hash 操作有 lock 處理
    * 細部處理，因涉及到有可能呼叫到其他函式，因此選擇包起來
        * 範圍太大、效率不高

* 原先測試沒辦法進入到 hash 操作

static void test_cstr(void *buf) {
cstr_buffer *a = (cstr_buffer *)buf;
cstr_cat((*a), "a");
cstr_cat((*a), "a");
}

    * 後來修改成先對 cstr_buffer a 做處理在進入到測試函式
* 最後，每個對字串操作的都包起來。

#### reference count
* [wikipedia - 參照計數](https://zh.wikipedia.org/wiki/%E5%BC%95%E7%94%A8%E8%AE%A1%E6%95%B0)
    > 參照計數是電腦程式語言中的一種記憶體管理技術，是指將資源（可以是物件、記憶體或磁碟空間等等）的被參照次數儲存起來，當被參照次數變為零時就將其釋放的過程。使用參照計數技術可以實現自動資源管理的目的。同時參照計數還可以指使用參照計數技術回收未使用資源的垃圾回收演算法。
    >
    > 當建立一個物件的實例並在堆上申請記憶體時，物件的參照計數就為1，在其他物件中需要持有這個物件時，就需要把該物件的參照計數加1，需要釋放一個物件時，就將該物件的參照計數減1，直至物件的參照計數為0，物件的記憶體會被立刻釋放。
* [wikipedia - Reference_counting](https://en.wikipedia.org/wiki/Reference_counting)
    > Reference counts are also useful information to use as input to other runtime optimizations.
    >
    > For example,**systems that depend heavily on immutable objects such as many functional programming languages can suffer an efficiency penalty due to frequent copies.** However, if the compiler (or runtime system) knows that a particular object has only one reference (as most do in many systems), and that the reference is lost at the same time that a similar new object is created (as in the string append statement str ← str + "a"), it can replace the operation with a mutation on the original object.
* 對增減值的單一操作保證
    * 只要 lock 就好
* 對增減值最後的結果保證 (結果最後要符合特定值)
    * `sleep() `
    * `reader and writer`
        * [wikipedia](https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem)
        * [GitHub System Programming](https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-7%3A-The-Reader-Writer-Problem) 
    * 總而言之，想辦法把兩個操作分開
* 執行順序很重要
    * [並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-ordering#%E6%9C%80%E7%9B%B4%E8%A6%BA%E7%9A%84%E7%B4%84%E5%AE%9A-Sequential-Consistency)
* [hash table](https://en.wikipedia.org/wiki/Hash_table)
    * [碰撞處理](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution)：Separate chaining 和 Open addressing
    * [concurrent hash table](https://en.wikipedia.org/wiki/Concurrent_hash_table)
### quiz 3 - xs reference counting
> [linD026](https://hackmd.io/@linD026/linux2021-quiz3)
#### reference counting
* 基本定義
    * 有多少個人用他的資料，他就要記錄
* `xs_cow_lazy_copy`
    * 不太符合 lazy copy

#### 多執行緒
* [cppreference - atomic library](https://en.cppreference.com/w/c/atomic)
    * [cppreference - atomic explanation](https://en.cppreference.com/w/c/language/atomic)
    * [cppreference - atomic memory order](https://en.cppreference.com/w/c/atomic/memory_order)
        * [並行程式設計: 執行順序 - Happens-Before](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-ordering#Happens-Before)
* 在多執行緒下，保持資料正確性的調整
    * 執行順序
    * 函式結構
    * 資料儲存結構

#### 空間效率
* 在 xs_new 裡的記憶體配置是以 2 的冪來估算 (capacity)
    * 空間兩倍
    * reclaim
        * 一般性的分配完後，重新分配或直接分配剛好的記憶體
        * 要另設 flag 來標示， capacity 的值也要考慮到(是要大於還是小於)
            * flag <= source
* [wikipedia - Copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write)

:::warning
> [wikipedia - Copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write)
> The string class provided by the C++ standard library was specifically designed to allow copy-on-write implementations in the initial C++98 standard,[5] but not in the newer C++11 standard:[6]

> [wikipedia - 寫入時複製](https://zh.wikipedia.org/wiki/%E5%AF%AB%E5%85%A5%E6%99%82%E8%A4%87%E8%A3%BD)
> `C++` 標準程式庫中的 `std::string` 類，在 `C++98/C++03` 標準中是允許寫時複製策略。但在 `C++11` 標準中為了提高並列性取消了這一策略。`GCC` 從版本 5 開始，`std::string` 不再採用 `COW` 策略。
:::

:::danger
**TODO**
* [hash table](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution)
* [concurrent hash table](https://en.wikipedia.org/wiki/Concurrent_hash_table)
* [string interning](https://en.wikipedia.org/wiki/String_interning)

**NOTE**
* 在多執行緒下，資源要進行分類才能夠作效率高的LOCK、資料結構或函式操作也須調整
:::

---

## 第一週至第四週問題整理
> 此標題與其它標題不同，僅整理。
> > 其它標題為當下筆記
### 第一週
:::info
**TODO**
* [lab-0](https://hackmd.io/@sysprog/linux2021-lab0)
* [quiz1](https://hackmd.io/@linD026/2021q1_quiz1)
    * TCO
    * random - 數學式提供
:::

#### quiz1
* [Lagged Fibonacci generators](https://hackmd.io/@linD026/2021q1_quiz1#%E5%8C%85%E8%A3%9D-random---LFG) 
    * 在數學上的意義
    * 第三週作業 - [fibdrv](https://hackmd.io/@sysprog/linux2021-fibdrv)
* [ASLR ( Address Space Layout Randomization )](https://hackmd.io/@linD026/2021q1_quiz1#ASLR--Address-Space-Layout-Randomization-)
    * 運作原理
* [linux-list 的 list_qsort](https://hackmd.io/@linD026/2021q1_quiz1#2-linux-list-%E7%9A%84-list_qsort)
    * 初次使用 `list_for_each_entry_safe` , `container_of` 等包裝過得 API
* [A Comparative Study Of Linked List Sorting Algorithms](https://hackmd.io/@linD026/2021q1_quiz1#4-%E6%80%9D%E8%80%83%E9%AB%98%E6%95%88%E7%8E%87%E7%9A%84-linked-list-%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95)
    * 演算法計算
    * sort 的比較
    * tree-sort 效能最好
        * 與 qsort 的比較
    * [實作層面的問題](https://hackmd.io/@linD026/2021q1_quiz1#tree_sort-and-list_sort)
* [rbtree](https://hackmd.io/@linD026/2021q1_quiz1#Tree-sort) 和 [c_map](https://hackmd.io/@linD026/2021q1_quiz1#5-c_map)
    * `__attribute__((aligned(sizeof(long))));` 的 bits 應用

### 第二週

#### quiz2
:::info
**TODO**
* string interning
    * [Makefile 提供](https://hackmd.io/@linD026/2021q1_quiz2#cstr_cat---%E5%AD%97%E4%B8%B2%E5%AE%8C%E6%95%B4%E6%80%A7)
    * chriso/intern
:::
* [list_sort 的運作原理](https://hackmd.io/@linD026/2021q1_quiz2#%E8%AA%AA%E6%98%8E-liblist_sortc-%E6%9C%80%E4%BD%B3%E5%8C%96%E6%89%8B%E6%B3%95)
    * 符合 cache friendly 的改變
* [效能檢測](https://hackmd.io/@linD026/2021q1_quiz2#3-%E6%95%88%E8%83%BD%E6%AF%94%E8%BC%83) - 記憶體使用量
    * gcc 
        * -fstack-usage
    * valgrind
        * -v --leak-check=full
        * valgrind --tool=massif 
    * <sys/resource.h>
        * struct rusage
* [規格書規範](https://hackmd.io/@linD026/2021q1_quiz2#C11-63-Conversions)
    * 運算時型態的轉換有規定
* [is_power_of_2](https://hackmd.io/@linD026/2021q1_quiz2#2-is_power_of_2)
    * fls64 的硬體舉例 - Alpha 
        > 舉例解說的微處理器架構用 x86, x86_64, arm, aarch64, risc-v 等架構為主，你可以忽略 Alpha
* [string interning](https://hackmd.io/@linD026/2021q1_quiz2#2-is_power_of_2)
    * reference count
    * threads

### 第三週
:::info
**TODO**
* [fibdrv](https://hackmd.io/@sysprog/linux2021-fibdrv)
* 檔案系統 - page
* [btrfs](https://hackmd.io/@linD026/linux2021-quiz3#btrfs)
:::
#### quiz3
* stack / heap 效能與成本
* [5 Linux 核心 內部實例](https://hackmd.io/@linD026/linux2021-quiz3#5-Linux-%E6%A0%B8%E5%BF%83-%E5%85%A7%E9%83%A8%E5%AF%A6%E4%BE%8B)
    * [fork](https://hackmd.io/@linD026/linux2021-quiz3#fork)
        * [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
        * MMU
        * uclinux
    * [page](https://hackmd.io/@linD026/linux2021-quiz3#page)
        * CoW
### 第四週
#### quiz4
* thread pool
    * [並行程式設計: POSIX Thread - Thread Pool](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads#Thread-Pool)
        * [並行和多執行緒程式設計 (5)](https://www.youtube.com/watch?v=8BidMHVGeBE)
* pthread cancel
    * cancel point
        * pthread_cond_timedwait
    * resource release
* [pthread - rwlock](https://pubs.opengroup.org/onlinepubs/009604599/functions/pthread_rwlock_rdlock.html)
---

## CS:APP 相關資料整理
> 主要相關對象為
> 『 [Linux 核心設計 (Spring 2021) 課程進度表暨線上資源](http://wiki.csie.ncku.edu.tw/linux/schedule) 』
> 『 [CS:APP - international Edition - Second Edition](https://www.amazon.com/Computer-Systems-Programmers-Perspective-International/dp/0137133367/ref=sr_1_5?dchild=1&keywords=computer+systems+a+programmer%27s+perspective+randal+e.&qid=1617036234&s=books&sr=1-5) 』

### week 1
* [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)
    - [ ] CS:APP - Chapter 2

### week 3
* locality of reference 
    - [x] CS:APP - Chapter 6 - page 620
        * 跟程式碼避免產生 page fault 的情景很像
            > 恐龍書的舉例
        * stride-k reference pattern
    :::info
    延伸閱讀
    * CS:APP - Chapter 6 - 6.3 The Memory Hierachy - Page 625
    :::

* Page 
    - [ ] CS:APP - Chapter 9 - page 813, 814

---

## Week 7 quiz
> [GitHub - sysprog21 - concurrent-programs](https://github.com/sysprog21/concurrent-programs)

### mbus
* problem
    * unregister => need refcnt = 0 

---

## 05/12 - 一對一討論

### COSCUP
> [COSCUP 社群守則](https://hackmd.io/@coscup/cococo-zh?type=view)
* [topic note](https://blog.coscup.org/2021/04/coscup-2021-cfp.html)


### COW
[COW - note](https://hackmd.io/@linD026/Linux-kernel-CoW-content/https%3A%2F%2Fhackmd.io%2F%40linD026%2FLinux-kernel-CoW-Note)

### LaTeX
[A quick guide to LATEX](https://assets.ctfassets.net/nrgyaltdicpt/4e825etqMUW8vTF8drfRbw/d4f3d9adcb2980b80818f788e36316b2/A_quick_guide_to_LaTeX__Overleaf_version.pdf)