2024q1 Homework2 (quiz1+2)

contributed by < jason50123 >
作業要求

第一次測驗

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

linux kernel Cgroups research

在 linux kernel 的 cgroup.h 中我們可以找到以下的macro是有關 pre-order 的 traversal

#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 存自己的子節點。

接下來就可以從下面的 function 看到會先從 root 開始走，然後接著會去 call css_next_child確認說是否有 child，若有就往子節點去traverse，若沒有的話，就是往當前節點的 sibling 去走．

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。

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 來完成這樣的動作。

/**
 * 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