# 2024q1 Homework2 (quiz1+2) contributed by < [jason50123](https://github.com/jason50123) > [作業要求](https://hackmd.io/@sysprog/BkmmEQCn6) ## 第一次測驗 ### Test 1: ### Test 2:Tim sort ## 第二次測驗 ### Test 1: Construct Binary Tree from Preorder and Inorder Traversal 在實作過程中，嘗試寫出 `hlist_add_head` function 的過程中發現，自己對於`**pprev` 存的東西不是很了解，經過思考後終於理解裡面是存放 `前一個點的 next poineter 的 address`。 以及在理解程式碼中，對於為何要使用 `hash function` 來完成感到很疑惑，但後來才發現，如果我不用 `hash function` 的話，在 `dfs` 呼叫 `find node` 的時候，會需要花 *O(n)* 的時間去 traverse 整條 array ，但如果今天用 hash 的話就只需花 *O(1)* 的時間就可以完成 [build tree practice](https://github.com/jason50123/build_tree_testing.git) ### linux kernel Cgroups research 在 linux kernel 的 `cgroup.h` 中我們可以找到以下的macro是有關 pre-order 的 traversal ```c #define css_for_each_descendant_pre(pos, css) \ for ((pos) = css_next_descendant_pre(NULL, (css)); (pos); \ (pos) = css_next_descendant_pre((pos), (css))) ``` 由最一開始的 macro 我們可以看到他會去呼叫 `css_next_descendant_pre()` 這個 function 為了 trace `cgroups` 中的 `css_next_descendant_pre()` function 要先簡單看一下 `cgroup_subsys_state` 這個 structure，裡面包含重要的`list_head *sibling` 會存 parent node 的 children，以及`list_head *children` 存自己的子節點。 ```graphviz digraph structs { rankdir=LR; node [shape=record]; subgraph cluster1{ label="cgroup_subsys_state"; struct1[label= "parent"]; struct2[label="sibling |{prev|next}"]; struct3[label="children |{prev|next}"]; } } ``` 接下來就可以從下面的 function 看到會先從 root 開始走，然後接著會去 call `css_next_child`確認說是否有 child，若有就往子節點去traverse，若沒有的話，就是往當前節點的 sibling 去走． ```c struct cgroup_subsys_state * css_next_descendant_pre(struct cgroup_subsys_state *pos, struct cgroup_subsys_state *root) { struct cgroup_subsys_state *next; cgroup_assert_mutex_or_rcu_locked(); /* if first iteration, visit @root */ if (!pos) return root; /* visit the first child if exists */ next = css_next_child(NULL, pos); if (next) return next; /* no child, visit my or the closest ancestor's next sibling */ while (pos != root) { next = css_next_child(pos, pos->parent); if (next) return next; pos = pos->parent; } return NULL; } ``` 節錄`css_next_child`中的片段，其中的`likely(!(pos->flags & CSS_RELEASED)` 是拿來看說 pos 這個點是不是已經從 list 中被移除了，如果是的話就會`CSS_RELEASED` 就會被設為 true ， 而此時我們就會直接跳過該點，並直接去 traverse 該點的 sibling。 ```c struct cgroup_subsys_state *css_next_child(struct cgroup_subsys_state *pos, struct cgroup_subsys_state *parent) { ... } else if (likely(!(pos->flags & CSS_RELEASED))) { next = list_entry_rcu(pos->sibling.next, struct cgroup_subsys_state, sibling); } ... return NULL; } ``` ### Test2 在 `linux/mmzone.h` 下我們可以找到有關 LRU 的應用。當系統中的`physical page` 低於設定的 `page_min` 、 `page_low` 的值，就會將某些 deactivate 的 page 進行回收。 舊版的 linux kernel 會透過 `__pagevec_lru_add` 一路呼叫到`add_page_to_lru_list` 來把 page 加到相對的lru_list中，但在最新的linux kernel版本，則是透過 folio 來把原本的 struct page 包起來，並透過`lruvec_add_folio` 來完成這樣的動作。 ```c /** * folio_add_lru - Add a folio to an LRU list. * @folio: The folio to be added to the LRU. * * Queue the folio for addition to the LRU. The decision on whether * to add the page to the [in]active [file|anon] list is deferred until the * folio_batch is drained. This gives a chance for the caller of folio_add_lru() * have the folio added to the active list using folio_mark_accessed(). */ void folio_add_lru(struct folio *folio) { struct folio_batch *fbatch; VM_BUG_ON_FOLIO(folio_test_active(folio) && folio_test_unevictable(folio), folio); VM_BUG_ON_FOLIO(folio_test_lru(folio), folio); /* see the comment in lru_gen_add_folio() */ if (lru_gen_enabled() && !folio_test_unevictable(folio) && lru_gen_in_fault() && !(current->flags & PF_MEMALLOC)) folio_set_active(folio); folio_get(folio); local_lock(&cpu_fbatches.lock); fbatch = this_cpu_ptr(&cpu_fbatches.lru_add); folio_batch_add_and_move(fbatch, folio, lru_add_fn); local_unlock(&cpu_fbatches.lock); } ``` ### Test3