---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)

---

# 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
