浪費時間紀錄

作業 5 浪費的時間

其實這裡都是我誤解了 n-th set bit，他與陣列位置的概念一樣。第 0 個位置在現實生活中其實是第一個。因此第 0-th set bit 是指 first set bit。不過都花了 2 天在寫和找問題，刪掉也可惜，因此把這裡當作警惕和紀錄。

1. 第 2 周測驗 3
   考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)
   在改進過程中，我發現測試函式會檢查到輸出位置錯誤的問題，如下:

...
idx wrong: must in 799669-th bit, but you find in 799670-th bit
Time taken to find 400000-th bit: 0.000455 seconds
CPU cycles taken to find 400000-th bit: 1636266 cycles

idx right: in 400127-th bit
Time taken to find 200000-th bit: 0.000246 seconds
CPU cycles taken to find 200000-th bit: 881650 cycles

idx right: in 599309-th bit
Time taken to find 300000-th bit: 0.000378 seconds
CPU cycles taken to find 300000-th bit: 1492544 cycles

idx wrong: must in 798529-th bit, but you find in 798531-th bit
Time taken to find 400000-th bit: 0.000467 seconds
CPU cycles taken to find 400000-th bit: 1742514 cycles

不過當時認為 find_nth_bit 不可能出錯，因此一直花時間在檢查測試函式是否有問題，最後先放棄，做改進後比對的測試，大致上就是將改進前與改進後的程式碼取不同名稱並輸入相同測試數據比對輸出結果，而突然想到我的改寫原先應會出錯，卻不管怎麼修改測試數據皆與 find_nth_bit 輸出結果相同，因此開始尋找問題，並發現 linux/include/linux/bitops.h 內的函式 fns 計算方法有誤，如下:

/**
 * fns - find N'th set bit in a word
 * @word: The word to search
 * @n: Bit to find
 */
static inline unsigned long fns(unsigned long word, unsigned int n)
{
	unsigned int bit;

	while (word) {
		bit = __ffs(word);
		if (n-- == 0)
			return bit;
		__clear_bit(bit, &word);
	}

	return BITS_PER_LONG;
}

fns 函式錯誤

函式定義:
find N'th set bit in a word ，即在一 word 長度中的記憶體尋找第 n 個 set bits
函式作法:

1. 利用 __ffs 尋找低位開始第一個 set bit 之位置
2. 若此時的 n 不為 0 ，則利用 __clear_bit 清除該位 (設為 0) ，再回到 1.

那麼假設傳入函式參數為 word = 10000000110010111, n = 4
那麼流程將為

1. bit = __ffs(10000000110010111) = 0, n--(4) != 0, __clear_bit(0, &word)
2. bit = __ffs(10000000110010110) = 1, n--(3) != 0, __clear_bit(1, &word)
3. bit = __ffs(10000000110010100) = 2, n--(2) != 0, __clear_bit(2, &word)
4. bit = __ffs(10000000110010000) = 4, n--(1) != 0, __clear_bit(4, &word)
因為是 n-- ，此時 1 != 0 ，需要等到該段結束才會減 1
5. bit = __ffs(10000000110000000) = 7, n--(0) == 0 回傳 7
但是第 4 位 set bits 在第 4 位才對。

MRE (Minimal reproducible example)

輸入 fns(1, 1)
輸出:64
正解:0

因為 n-- 尚不等於 0 ，因此會去尋找第二個 set bit。
因此應改成 --n 的動作，如此可得正確位置
修改 linux/include/linux/bitops.h 內的 fns 函式:

/**
 * fns - find N'th set bit in a word
 * @word: The word to search
 * @n: Bit to find
 */
static inline unsigned long fns(unsigned long word, unsigned int n)
{
	unsigned int bit;

	while (word) {
		bit = __ffs(word);
		if (--n == 0)
			return bit;
		__clear_bit(bit, &word);
	}

	return BITS_PER_LONG;
}

更改後再做測試，測試筆數: 10000 次，每一次皆尋找第 200000、300000 及第 400000個 set bit

修改前: idx wrong: 15004 time
修改後: idx wrong: 946 time

FIND_NTH_BIT 函式錯誤

可以看到仍有錯誤，不過我認為是其他函式出錯了，因為我檢查輸出結果與事實只要是錯誤的皆 >=64，但 fns 只負責一個 64 bits 的範圍，而 FIND_NTH_BIT 內寫到

w = hweight_long(tmp);                              \
if (w > nr)                                         \
    goto found; 

假設 nr 剛好為 64 ，即代表距離還需要尋找 64 個 set bits ，而 hweight_long(tmp) 剛好也回傳 64 ，那麼不會進入判斷式 if (w > nr) ，這說明了 fns 不可能會處理到 nr 為 >=64 的情況，因此不可能會差到 >=64，所以並非函式 fns 的問題。

那麼如果 w == nr 卻不進入判斷式 if (w > nr) 會怎樣呢 ?

for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
    if (idx * BITS_PER_LONG + nr >= sz)                 \
        goto out;                                       \
                                                        \
    tmp = (FETCH);                                      \
    w = hweight_long(tmp);                              \
    if (w > nr)                                         \
        goto found;                                     \
                                                        \
    nr -= w;                                            \
} 
found:                                                      \
    sz = min((idx << logBPL) + fns(tmp, nr), sz);           \
out:                                                        \
    sz;  

與上述同樣情況，那麼 nr 等於 0 ，會再找一段 word 去加長長度，數值說明:

現在情況: w = 15, nr = 15, idx = 3
1. w == nr : 不進入判斷式 if (w > nr)
2. nr -= w, nr = 0
3. idx++
4. w = 3
5. w > nr : 進入判斷式 if (w > nr)
6. goto found
7. idx << logBPL : 這裡因 idx++ ，使最後輸出多了 64
8. fns(tmp, nr) : 因 nr = 0 ，因此回傳 0

那麼為什麼誤差會 >= 64 呢?
因為原先目標位置 n 在上一個 idx 的 word 內，而現在被以 64 計算，因此多計算了 leadind zero 的數量 (因為加上此 word 的 set bits 要剛好等於 nr)

假設 addr[idx]=...00001011010...
                     ^
                  目標位置 n

因此最後誤差為 128 - n ，其中 n 為前一個 word 的最後一個 set bit

MRE (Minimal reproducible example)
只要首個 word = 1, n(set bit) = 1 ，即可重現

修改 linux/lib/find_bit.c 內的 FIND_NTH_BIT 函式:

for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
    if (idx * BITS_PER_LONG + nr >= sz)                 \
        goto out;                                       \
                                                        \
    tmp = (FETCH);                                      \
    w = hweight_long(tmp);                              \
    if (w >= nr)                                         \
        goto found;                                     \
                                                        \
    nr -= w;                                            \
} 

第 3 周 測驗 4 所浪費的時間

KSM (Kernel Samepage Merging)

參考 Kernel Samepage Merging

目的:

KSM is a memory-saving de-duplication feature

目的就是節省記憶體使用

概述:

KSM 起初與 KVM (Kernel-based Virtual Machine) 一同開發 (也被稱為 Kernel Shared Memory)，透過共享含有相同資料的記憶體，將更多虛擬機器放入實體記憶體內。
而方法為週期性的掃描使用者記憶體有註冊 (有向 MMU (記憶體管理單元（Memory management unit）) 中註冊相關 page 對應的實體位址) 之位置，並尋找 pages 中可被單一寫入保護的 page 取代的完全相同的內容 (若後續想要更新該內容，則會自動複製一份) ，而 KSM 常駐程式每一次掃描的 pages 數量及掃描的間隔時間由 sysfs interface 設置。
KSM 僅合併匿名 (private) pages ，而非 pagecache (file) pages。

• Anonymous (Private) Pages:
  • 定義：Anonymous pages 是為了存儲程序的私有數據而分配的記憶體 pages 。這些 pages 通常包含程序的佇列、堆疊和未初始化的數據等。
  • 存取控制：只有擁有該 page 的程序可以訪問它。
  • 內容：通常存儲程序運行時的動態數據，如變數、函數調用的返回地址等。
  • 生命周期：當程序終止時，相關的 anonymous pages 會被釋放並返回給系統。
• Pagecache (File) Pages:
  • 定義：Pagecache pages 用於存儲文件系統的 pagecache 。當文件被讀取到記憶體中時，它的 page 會被放入 pagecache 中，以加速後續的讀取操作。
  • 存取控制：多個程序可以共享 pagecache 中的 page ，只要他們有相應文件的讀取權限。
  • 內容：存儲文件的數據，如文本、圖片、音頻等。
  • 生命周期：文件的 page 在不再需要時會被從 pagecache 中移除。
    因原本 Pagecache (File) Pages 就有共享之機制，無須再去合併。

KSM 合併的 pages 原本被鎖定於 kernel 記憶體內，但現在可以被置換入硬碟成其他使用者的 pages 以釋放實體記憶體 (不過共享在當他們被置換入記憶體時會被破壞，因為在置換入硬碟時合併的資訊同時會失去，因此 ksmd 需重新探索 pages 是否一致並重新合併)

實作方法:

為了降低過多的掃瞄， KSM 透過一 pointers 指向 pages 之位置的資料結構儲存透過內容排序的 pages 。

因為 pages 內的內容隨時都會改變， KSM 不能僅插入 pages 進入一般排序的樹並期待他能找到所有內容。因此 KSM 使用兩種資料結構 – 穩定及不穩定樹。

穩定樹保有指向所有合併 pages (KSM pages) 的 pointers ，並透過其內容進行排序。由於每一個 page 皆為寫入保護，在此樹尋找是完全可以被保證是有作用的 (除非 pages 為非映射)，因此此樹被稱為穩定樹。

穩定樹的節點包含了從 KSM page 反向映射到有定位到此頁面之虛擬位址的資訊。因此給定一個 KSM page，系統可以查詢穩定樹，以找到所有映射到這個頁面的虛擬地址，如下:

/**
 * struct ksm_stable_node - node of the stable rbtree
 * @node: rb node of this ksm page in the stable tree
 * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
 * @hlist_dup: linked into the stable_node->hlist with a stable_node chain
 * @list: linked into migrate_nodes, pending placement in the proper node tree
 * @hlist: hlist head of rmap_items using this ksm page
 * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)
 * @chain_prune_time: time of the last full garbage collection
 * @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN
 * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
 */
struct ksm_stable_node {
	union {
		struct rb_node node;	/* when node of stable tree */
		struct {		/* when listed for migration */
			struct list_head *head;
			struct {
				struct hlist_node hlist_dup;
				struct list_head list;
			};
		};
	};
	struct hlist_head hlist;
	union {
		unsigned long kpfn;
		unsigned long chain_prune_time;
	};
	/*
	 * STABLE_NODE_CHAIN can be any negative number in
	 * rmap_hlist_len negative range, but better not -1 to be able
	 * to reliably detect underflows.
	 */
#define STABLE_NODE_CHAIN -1024
	int rmap_hlist_len;
#ifdef CONFIG_NUMA
	int nid;
#endif
};

/**
 * struct ksm_rmap_item - reverse mapping item for virtual addresses
 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list
 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
 * @nid: NUMA node id of unstable tree in which linked (may not match page)
 * @mm: the memory structure this rmap_item is pointing into
 * @address: the virtual address this rmap_item tracks (+ flags in low bits)
 * @oldchecksum: previous checksum of the page at that virtual address
 * @node: rb node of this rmap_item in the unstable tree
 * @head: pointer to stable_node heading this list in the stable tree
 * @hlist: link into hlist of rmap_items hanging off that stable_node
 * @age: number of scan iterations since creation
 * @remaining_skips: how many scans to skip
 */
struct ksm_rmap_item {
	struct ksm_rmap_item *rmap_list;
	union {
		struct anon_vma *anon_vma;	/* when stable */
#ifdef CONFIG_NUMA
		int nid;		/* when node of unstable tree */
#endif
	};
	struct mm_struct *mm;
	unsigned long address;		/* + low bits used for flags below */
	unsigned int oldchecksum;	/* when unstable */
	rmap_age_t age;
	rmap_age_t remaining_skips;
	union {
		struct rb_node node;	/* when node of unstable tree */
		struct {		/* when listed from stable tree */
			struct ksm_stable_node *head;
			struct hlist_node hlist;
		};
	};
};

為了避免在 KSM 分頁反向映射造成的巨大的延遲， KSM 在穩定樹中維持兩種節點:

• 鏈結串列中保存反向映射結構的常規節點
• 鏈結代表相同寫入保護記憶體內容節點 ("dup") 之 "chains" ，但每一個 "dup" 對應到一個複製該內容不同的 KSM page。

於內部，常規節點 "dups" 和 "chains" 代表使用相同 struct ksm_stable_node 的結構。

除了穩定樹， KSM 使用第二個資料結構稱為不穩定樹，此樹保有指向在一段時間未被改變 pages 的 pointers 。不穩定樹透過其 pages 內容進行排序，不過由於其並非為寫入保護， KSM 無法依賴不穩定樹能正常工作，因為不穩定樹容易因內容被修改而被破壞，因此才稱為不穩定。

KSM 利用以下技術解決此問題:

• 不穩定樹在每次 KSM 掃描完記憶體區域後會被清除，而在 KSM 掃描起始時該樹才會被重建。
• KSM 只會將雜湊值在先前掃描整輪記憶體區域後未被改變的 pages 插進穩定樹。
• 不穩定樹為紅黑樹，因此平衡性取決於節點的顏色而非其內容，以確保即使樹被破壞也不會不平衡 (因為一定會改變內容) ，因此掃描時間也會維持相同 (此外，搜尋及插入節點進入紅黑樹皆使用相同演算法，因此在清除其重建時無須開銷)。
• KSM 永遠不會清除穩定樹，意味著即使需要嘗試 10 次在不穩定樹中去尋找一 page ，一但找到，他會被安全的保護在穩定樹中 (當在掃描一新的 page 時，首先會與穩定樹比較，再與不穩定樹比較)。

當可調整的 merge_across_nodes 未被設置， KSM 將會維持多個穩定樹及多個不穩定樹，每個 NUMA 節點各一個。

NUMA, Non-Uniform Memory Access ，是一種可以在多處理系統中設定微處理器叢集的方法，因此他們可以在 local 共享記憶體
參考 non-uniform memory access (NUMA)

Trace code:

/*
 * The scan time advisor is based on the current scan rate and the target
 * scan rate.
 *
 *      new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)
 *
 * To avoid perturbations it calculates a change factor of previous changes.
 * A new change factor is calculated for each iteration and it uses an
 * exponentially weighted moving average. The new pages_to_scan value is
 * multiplied with that change factor:
 *
 *      new_pages_to_scan *= change facor
 *
 * The new_pages_to_scan value is limited by the cpu min and max values. It
 * calculates the cpu percent for the last scan and calculates the new
 * estimated cpu percent cost for the next scan. That value is capped by the
 * cpu min and max setting.
 *
 * In addition the new pages_to_scan value is capped by the max and min
 * limits.
 */
static void scan_time_advisor(void)
{
	unsigned int cpu_percent;
	unsigned long cpu_time;
	unsigned long cpu_time_diff;
	unsigned long cpu_time_diff_ms;
	unsigned long pages;
	unsigned long per_page_cost;
	unsigned long factor;
	unsigned long change;
	unsigned long last_scan_time;
	unsigned long scan_time;

	/* Convert scan time to seconds */
	scan_time = div_s64(ktime_ms_delta(ktime_get(), advisor_ctx.start_scan),
			    MSEC_PER_SEC);
	scan_time = scan_time ? scan_time : 1;

	/* Calculate CPU consumption of ksmd background thread */
	cpu_time = task_sched_runtime(current);
	cpu_time_diff = cpu_time - advisor_ctx.cpu_time;
	cpu_time_diff_ms = cpu_time_diff / 1000 / 1000;

	cpu_percent = (cpu_time_diff_ms * 100) / (scan_time * 1000);
	cpu_percent = cpu_percent ? cpu_percent : 1;
	last_scan_time = prev_scan_time(&advisor_ctx, scan_time);

	/* Calculate scan time as percentage of target scan time */
	factor = ksm_advisor_target_scan_time * 100 / scan_time;
	factor = factor ? factor : 1;

	/*
	 * Calculate scan time as percentage of last scan time and use
	 * exponentially weighted average to smooth it
	 */
	change = scan_time * 100 / last_scan_time;
	change = change ? change : 1;
	change = ewma(advisor_ctx.change, change);

	/* Calculate new scan rate based on target scan rate. */
	pages = ksm_thread_pages_to_scan * 100 / factor;
	/* Update pages_to_scan by weighted change percentage. */
	pages = pages * change / 100;

	/* Cap new pages_to_scan value */
	per_page_cost = ksm_thread_pages_to_scan / cpu_percent;
	per_page_cost = per_page_cost ? per_page_cost : 1;

	pages = min(pages, per_page_cost * ksm_advisor_max_cpu);
	pages = max(pages, per_page_cost * KSM_ADVISOR_MIN_CPU);
	pages = min(pages, ksm_advisor_max_pages_to_scan);

	/* Update advisor context */
	advisor_ctx.change = change;
	advisor_ctx.scan_time = scan_time;
	advisor_ctx.cpu_time = cpu_time;

	ksm_thread_pages_to_scan = pages;
	trace_ksm_advisor(scan_time, pages, cpu_percent);
}

目的為探究並分析程式碼對於名稱 exponential weighted moving average 的精確度。
避免有額外的計算在函式 ewma 外，因此將相關會影響函式同時列出:

change = ewma(advisor_ctx.change, change);

傳入參數為 advisor_ctx.change 及 change ，而從第 574 行可以看到

advisor_ctx.change = change;

而 advisor_ctx.change 之初始化我目前只能在第 341 行看到

#ifdef CONFIG_SYSFS
/*
 * Only called through the sysfs control interface:
 */

/* At least scan this many pages per batch. */
static unsigned long ksm_advisor_min_pages_to_scan = 500;

static void set_advisor_defaults(void)
{
	if (ksm_advisor == KSM_ADVISOR_NONE) {
		ksm_thread_pages_to_scan = DEFAULT_PAGES_TO_SCAN;
	} else if (ksm_advisor == KSM_ADVISOR_SCAN_TIME) {
		advisor_ctx = (const struct advisor_ctx){ 0 };
		ksm_thread_pages_to_scan = ksm_advisor_min_pages_to_scan;
	}
}
#endif /* CONFIG_SYSFS */

雖然在 trace 會呼叫到此函式的 code 時會發現 唯一呼叫到此函式的函式為

static ssize_t advisor_mode_store(struct kobject *kobj,
				  struct kobj_attribute *attr, const char *buf,
				  size_t count)

( 不過在 linux 中就不會再有任何函式呼叫到此函式。)
因此我將 advisor_ctx.change 暫時視為僅與 change 有關。
而與change 有關為

scan_time = div_s64(ktime_ms_delta(ktime_get(), advisor_ctx.start_scan),
			    MSEC_PER_SEC);
scan_time = scan_time ? scan_time : 1;
...
last_scan_time = prev_scan_time(&advisor_ctx, scan_time);
...
change = scan_time * 100 / last_scan_time;
change = change ? change : 1;

第一部分僅為獲取現在 kernel 時間並與 advisor_ctx.start_scan 相減再轉換為秒，因此不會作額外計算，而 last_scan_time 使用的函式 prev_scan_time 也僅為使用可用的 scan_time 。

/*
 * Use previous scan time if available, otherwise use current scan time as an
 * approximation for the previous scan time.
 */
static inline unsigned long prev_scan_time(struct advisor_ctx *ctx,
					   unsigned long scan_time)
{
	return ctx->scan_time ? ctx->scan_time : scan_time;
}

因此可看出 change 為 scan_time 之變化量百分比。

change = scan_time * 100 / last_scan_time;

送給滑到這裡的人

/*
 * The scan time advisor is based on the current scan rate and the target
 * scan rate.
 *
 *      new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)
 *
 * To avoid perturbations it calculates a change factor of previous changes.
 * A new change factor is calculated for each iteration and it uses an
 * exponentially weighted moving average. The new pages_to_scan value is
 * multiplied with that change factor:
 *
 *      new_pages_to_scan *= change facor
 *
 * The new_pages_to_scan value is limited by the cpu min and max values. It
 * calculates the cpu percent for the last scan and calculates the new
 * estimated cpu percent cost for the next scan. That value is capped by the
 * cpu min and max setting.
 *
 * In addition the new pages_to_scan value is capped by the max and min
 * limits.
 */

這裡他第 393 行的 facor 應該為 factor ，是一個貢獻 Linux 的機會。