作業描述

測驗 \(\alpha\)

1.解釋上述程式碼運作原理

S-Tree 提供了 treeint_init,tree_destroy,treeint_insert, treeint_remove treeint_dump 的操作

• treeint_insert
  由於 S-Tree 為 Binary Search Tree (BST)，

2.指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作

3.設計效能評比程式，探討上述程式碼和 red-black tree 效能落差

測驗 \(\beta\)

1.說明上述程式碼的運作原理

#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 MMMM;       
    }
    return (((sz + mask) / alignment) * alignment);
}

首先考慮 alignment 非 2 的冪的情形，
align_up 最終會返回 alignment 的倍數，對於 sz 而言，
如果僅僅 return ((sz / alignment) * alignment) 只會得到一個 align_down(sz, alignment)。
所以必須 shift 一個值，如果直接 shift alignment ，如果 sz 已經 是 alignment 的倍數的話，結果會是 sz + alignment 不符合要求，所以才取 mask 當作 shift 的值。

再來考慮alignment 是 2 的冪的情形，
如果 alignment 是 2 的冪，寫成 2 進位形式將會是 0b100..0，而 mask 將會恰好是 0b011..1， mask 跟 alignment 做 & operation 後就會剛好為 0 。
而其實 MMMM 可以跟非 2 的冪一樣 return (((sz + mask) / alignment) * alignment) 答案也會是對的。
但這裡可以用 sz & (~mask) 的後半部的位元全部清除，就可以不用經過除法運算得到 aligment 的倍數，但因為剛剛做 shift 的理由及方法，最終 MMMM 應為 sz + mask & ~mask

2.在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法

從 const.h 可以看到類似的 Macro

#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (__typeof__(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

可以看到其有被封裝在 mm.h ，且在註解裡也表明 a 為 2 的冪

* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))

我們可以直接在 mm.h 看到 PAGE_ALIGN 的 macro 會幫我們拿到 align 的 PAGE address

/* to align the pointer to the (next) page boundary */
#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)

測驗 \(\gamma\)

1.解釋上述程式碼運作原理

從 qsort_mt 開始觀察

2.以 Thread Sanitizer 找出上述程式碼的 data race 並著手修正

3.研讀 專題: lib/sort.c，提出上述程式碼效能改進之規劃並予以實作