# linux2023: nosba0957
## 測驗 α−1 解釋程式碼運作原理
`__treeint_dump()` 是使用中序 (in-order) 方式印出節點。

__treeint_dump(st_left(n), depth + 1);

struct treeint *v = treeint_entry(n);
printf("%d\n", v->value);

__treeint_dump(st_right(n), depth + 1);	

`treeint_remove()` 中先使用 `treeint_find()` 找到目標節點，再使用 `st_remove()` 刪除節點。`st_remove()` 透過 `st_replace_right()` 和 `st_replace_left()` 來刪除節點。若要刪除的節點有右子樹，則用右子樹的最小值取代。
用節點 `del` 擁有右子樹為例，要刪除 `del`，先找到其右子樹中最小值 `least`節點，再使用 `st_replace_right()` 把 `del` 節點換為 `least`，最後更新。

void st_remove(struct st_node **root, struct st_node *del)
{
    if (st_right(del)) {
        struct st_node *least = st_first(st_right(del));
        if (del == *root)
            *root = least;

        st_replace_right(del, least);
        st_update(root, least);
        return;
    }

    if (st_left(del)) {
        struct st_node *most = st_last(st_left(del));
        if (del == *root)
            *root = most;

        st_replace_left(del, most);
        st_update(root, most);
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct st_node *parent = st_parent(del);

    if (st_left(parent) == del)
        st_left(parent) = 0;
    else
        st_right(parent) = 0;

    st_update(root, parent);
}

`st_update()` 的最後會比對更新後和更新前的 hint，若兩者不一樣則會往親代節點遞迴 `st_update()`。

if (n->hint == 0 || n->hint != prev_hint)
    st_update(root, p);

## 測驗 β-1 說明上述程式碼的運作原理
`alignment` 要為 2 的冪，所以 `mask` 是 2 進位中 0 到 n-1 位的遮罩。例如： alignment = 8，mask = 7 (0111 1111)。
`(sz + mask) & ~mask` 先加上 `mask`，可以讓沒有對齊的數往前到下一個區塊。
用老師的例子舉例，`sz` 可能的值為 120 ~ 123，`alignment` 為 4，`mask` 為 3。可以知道 121 ~ 123 沒有對齊，所以先加上 `mask`，值會變為 124 ~ 126，此時再和 `~mask` 做 bitwise and，即可將 2 進位中最高第 3 位以下的 bits 忽略。

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return (sz + mask) & ~mask;       
    }
    return (((sz + mask) / alignment) * alignment);
}

## 測驗 β-2 在 Linux 核心原始程式碼找出類似 align_up 的程式碼
在 [linux/tools/include/linux/mm.h](https://github.com/torvalds/linux/blob/374a7f47bf401441edff0a64465e61326bf70a82/tools/include/linux/mm.h#L15) 中找到類似的程式碼。舉例：[linux/mm/percpu.c](https://github.com/torvalds/linux/blob/374a7f47bf401441edff0a64465e61326bf70a82/mm/percpu.c#L1174)。
當 `index` 取得值後，使用 `__ALIGN_MASK(index, align_mask)` 來對齊，最後確認是否符合要求大小。

static unsigned long pcpu_find_zero_area(unsigned long *map,
					 unsigned long size,
					 unsigned long start,
					 unsigned long nr,
					 unsigned long align_mask,
					 unsigned long *largest_off,
					 unsigned long *largest_bits)
{
	unsigned long index, end, i, area_off, area_bits;
again:
	index = find_next_zero_bit(map, size, start);

	/* Align allocation */
	index = __ALIGN_MASK(index, align_mask);
	area_off = index;

	end = index + nr;
	if (end > size)
		return end;
	i = find_next_bit(map, end, index);
	if (i < end) {
		area_bits = i - area_off;
		/* remember largest unused area with best alignment */
		if (area_bits > *largest_bits ||
		    (area_bits == *largest_bits && *largest_off &&
		     (!area_off || __ffs(area_off) > __ffs(*largest_off)))) {
			*largest_off = area_off;
			*largest_bits = area_bits;
		}

		start = i + 1;
		goto again;
	}
	return index;
}

## 測驗 γ-1 解釋上述程式碼運作原理
`qsort_thread()` 是讓 thread 執行的 function。在程式剛開始時，每個 thread 的狀態 `qs->st` 都會是 `ts_idle`，這裡先讓每個 thread 停在自己的 cond。

again:
      /* Wait for work to be allocated. */
      verify(pthread_mutex_lock(&qs->mtx_st));
      while (qs->st == ts_idle)
          verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st));
      verify(pthread_mutex_unlock(&qs->mtx_st));
      if (qs->st == ts_term) {
          return NULL;
      }
      assert(qs->st == ts_work);

最後只會剩一個 thread 在 `qsort_mt()`，他會用 signal 方式叫醒`pool[0]`。

	/* Hand out the first work batch. */
    qs = &c.pool[0];
    verify(pthread_mutex_lock(&qs->mtx_st));
    qs->a = a;
    qs->n = n;
    qs->st = ts_work;
    c.idlethreads--;
    verify(pthread_cond_signal(&qs->cond_st));
    verify(pthread_mutex_unlock(&qs->mtx_st));

當 `pool[0]` 的 thread 做完後，會再用 signal 的方式叫下一個停在 cond 上 thread 起來。

	verify(pthread_mutex_lock(&c->mtx_al));
	qs->st = ts_idle;
	c->idlethreads++;
	if (c->idlethreads == c->nthreads) {
		for (i = 0; i < c->nthreads; i++) {
			qs2 = &c->pool[i];
			if (qs2 == qs)
				continue;
			verify(pthread_mutex_lock(&qs2->mtx_st));
			qs2->st = ts_term;
			verify(pthread_cond_signal(&qs2->cond_st));
			verify(pthread_mutex_unlock(&qs2->mtx_st));
		}
		verify(pthread_mutex_unlock(&c->mtx_al));
		return NULL;
	}
	verify(pthread_mutex_unlock(&c->mtx_al));