# 2023q1 Homework3 (quiz3)
contributed by < `Jerejere0808` >

## 測驗 1

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

#define rb_parent(r) ((node_t *) ((r)->color & ~1))
#define rb_color(r) ((color_t) (r)->color & 1)

#define rb_set_parent(r, p)                         \
    do {                                            \
        (r)->color = rb_color(r) | (uintptr_t) (p); \
    } while (0)
#define rb_set_red(r) \
    do {              \
        (r)->color &= ~1;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        (r)->color |= 1;           \
    } while (0)

對照 linux 紅黑樹的實作

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
...

基本上 struct 的結構差異不大，也有利用 ABI 的特性，將父節點的地址儲存在該節點的 color 欄位中，同時使用 color 欄位的 LSB 來表示該節點的顏色，這樣可以省下額外用來儲存 color 的空間。
struct 的差異主要是在，treesort.c 的實作直接 value 放在結構裡，並且多了一個 next pointer。 這個 pointer 應該要指向 rb tree 裡面用 inorder traverse 得到的下一個 node，這部分就要用到 cmap_next(node_t *node)

static node_t *cmap_next(node_t *node)
{
    if (!node)
        return NULL;

    if (node->right) {
        node = node->right;
        while (node->left)
            node = node->left;
        return node;
    }

    node_t *parent;
    while ((parent = rb_parent(node)) && node == parent->right)
        node = parent;

    return parent;
}

如此一來，在 tree_sort() 中，我們把 list 中的節點一個一個放進 map 裡，然後再透過 cmap_next() 一個一個拿出來，這樣就會是排序好的狀態

void tree_sort(node_t **list)
{
    node_t **record = list;
    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
    while (*list) {
        cmap_insert(map, *list, NULL);
        list = &(*list)->next;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = &(*list)->next;
    }
    *list = NULL;
    *record = first;
    free(map);
}

可以了解到 tree sort 就是利用insert 到 rb tree 時候因為其為 binary search tree 的特性再配合 preorder search 就能將以從小到大的順序找到 node 並透過 next pointer 連接成一個 sorted list。所以其實可以用不同 binary search tree 達成依樣目的，但是用 rb tree 有幾個優點如下:

1.rb tree 為 balanced search tree ， 所以 rb_next 找下一個節點就不用一直遍歷到很深。
2.但是若要平衡為何不用 avl treee ， 其甚至比 rb tree 平衡? 這裡參考 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)

因為雖然 rb tree AVL tree 比紅黑樹要平衡（左右子樹的高度不能差超過 2），但會在平衡自身時花費比紅黑樹多的時間。
如果考慮到要更快速地去 search 一個節點，那 AVL tree 會比較適合。
紅黑樹的優點在於雖沒有到完全平衡 (最長路徑 ≤ 2 倍最短路徑)，但是紅黑樹會在平衡自己時達到 O(1)(最多 3 次旋轉) 的複雜度。
而這裡我們其實只需要透過插入資料並遍歷來排序資料，所以不需要 search。若用 rb tree 來實踐 tree sort。

分析時間複雜度，先建立好 rb tree 花費 O(nlogn): 每次插入 n 筆資料每次插入都是O(logn)

cmap_next 找下一個 node 需要 O(logn)，找 n 次，所以也是 O(nlogn)。整體來說這裡的 sort 時間複雜度為 O(nlogn)。
## 測驗 2
## 測驗 3

**解釋 Linear feedback shift register (LFSR) 的運作原理**
LFSR 的運作原理如下：

初始狀態：LFSR 包含一組初始的二進制暫存器，這些暫存器可以是0或1。這些暫存器可以視為一個二進制數字，稱為「狀態」。

位移：其中有幾個 bits 可以透過 xor 產生一個 bit 輸出然後反饋回最左端的位置，這樣就能再產生一個新的狀態。這幾個可以影響輸出的 bits 根據它們位置 可以以2的羃多項式來表示，當 bit = 0 係數就是 0, bit = 1 係數就是 1。像是，這些 bits 的位置若為 16，14，13，11，則可以表示成x^16^+x^14^+x^13^+x^11^+1，期可稱為反饋多項式。

應用:賦給暫存器的初始狀態叫做「種子」，因為LFSR的運算是確定性的，所以，由暫存器所生成的狀態完全決定於暫存器當時或者之前的狀態。而且，由於暫存器的狀態是有限的，它最終肯定會是一個重複的循環。但若反饋多項式 x 的冪為互質，所產生的狀態就能看起來是隨機的且循環周期非常長，如此一來，LFSR就能生成偽隨機數，偽隨機噪聲序列，快速數字計數器，還有擾頻器。

**在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例**

/tools/perf/bench/numa.c

static inline uint32_t lfsr_32(uint32_t lfsr)
{
	const uint32_t taps = BIT(1) | BIT(5) | BIT(6) | BIT(31);
	return (lfsr>>1) ^ ((0x0u - (lfsr & 0x1u)) & taps);
}

static u64 do_work(u8 *__data, long bytes, int nr, int nr_max, int loop, u64 val)
{
	long words = bytes/sizeof(u64);
	u64 *data = (void *)__data;
	long chunk_0, chunk_1;
	u64 *d0, *d, *d1;
	long off;
	long i;

	BUG_ON(!data && words);
	BUG_ON(data && !words);

	if (!data)
		return val;

	/* Very simple memset() work variant: */
	if (g->p.data_zero_memset && !g->p.data_rand_walk) {
		bzero(data, bytes);
		return val;
	}

	/* Spread out by PID/TID nr and by loop nr: */
	chunk_0 = words/nr_max;
	chunk_1 = words/g->p.nr_loops;
	off = nr*chunk_0 + loop*chunk_1;

	while (off >= words)
		off -= words;

	if (g->p.data_rand_walk) {
		u32 lfsr = nr + loop + val;
		int j;

		for (i = 0; i < words/1024; i++) {
			long start, end;

			lfsr = lfsr_32(lfsr);

			start = lfsr % words;
			end = min(start + 1024, words-1);

			if (g->p.data_zero_memset) {
				bzero(data + start, (end-start) * sizeof(u64));
			} else {
				for (j = start; j < end; j++)
					val = access_data(data + j, val);
			}
		}
	} else if (!g->p.data_backwards || (nr + loop) & 1) {
		/* Process data forwards: */

		d0 = data + off;
		d  = data + off + 1;
		d1 = data + words;

		for (;;) {
			if (unlikely(d >= d1))
				d = data;
			if (unlikely(d == d0))
				break;

			val = access_data(d, val);

			d++;
		}
	} else {
		/* Process data backwards: */

		d0 = data + off;
		d  = data + off - 1;
		d1 = data + words;

		for (;;) {
			if (unlikely(d < data))
				d = data + words-1;
			if (unlikely(d == d0))
				break;

			val = access_data(d, val);

			d--;
		}
	}

	return val;
}

主要適用於執行記憶體存取操作以測量記憶體效能，函式首先根據工作執行緒數目、迴圈迭代數目和當前執行緒 ID 和迴圈迭代計算要存取的記憶體塊的大小。然後使用 LFSR 偽隨機數生成器，使用隨機走訪模式或正反向走訪記憶體塊來對指定的記憶體塊進行記憶體存取操作。總體來說 LFSR 可以讓測試程式隨機拜訪某一塊記憶體並測量效能。

**在 Linux 核心原始程式碼中找到 log2(x)的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 log2(x)的應用案例並解說**

在 "/include/linux/log2.h" 中的log2(x)實作。
u16 和 u32 定義在 "/arch/powerpc/boot/types.h" 分別代表 uint16_t 和 uint32_t
fls 函數（find last set bit，找到最高位元的 1 的索引）

typedef u16 uint16_t;
typedef u32 uint32_t;

static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
	return fls(n) - 1;
}

static __always_inline __attribute__((const))
int __ilog2_u64(u64 n)
{
	return fls64(n) - 1;
}

## 測驗 4

這邊 r 在最後加 1 之前，所計算出來的值應該要為 x - 1 的 MSB 位置，其也等於$\lfloor log_2(x-1)\rfloor$
(x > 0xFFFF) << 4
若 x 超過 16 位元，向右位移 16 個位元
(x > 0xFF) << 3
若 x 超過 8 位元，向右位移 8 個位元
(x > 0xF) << 2
若 x 超過 4 位元，向右位移 4 個位元
(x > 0x3) << 1
若 x 超過 2 位元，向右位移 2 個位元
r |= shift;
可以作為 r = r + shift 使用
最後剩兩個位元，記得要做最後一次 r | shift。然後透過 x >> 1 可以確認最左邊的位元是否為 1 ，若為 1 則 r 還要再加 1 ，這樣 r 才會是 $\lfloor log_2(x-1)\rfloor$ 所以

KKKK = r | shift | x >> 1

**改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless**

這邊的做法是想辦法將 x = 0 時，在做完 x- -之後回復成 0 ，這樣 r, shift 最後都是 0 ，答案就是 1。而 x != 0 時，還是維持 x- -，所以需要一個 mask ，當 x = 0，就為 0x00000000，並跟 x- - 的值做 & 操作，使其恢復成 0 ，反之，當 x != 0，mask 必須為 0xFFFFFFFF，保留原本的 x- -。

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;
    
    uint32_t mask;
    mask = !(x) - 1;
    x--;
    x = x & mask;
    
    r = (x > 0xFFFF) << 4;                 
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (KKKK) + 1;       
}