contributed by < Korin777 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian

contributed by < Korin777 > 測驗題目 測驗一 運作原理 pool_malloc 透過 get_loc_to_place 從 memory pool 的 free block 中配置記憶體給使用者 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up

contributed by < Korin777 > 測驗題目 測驗三 RB_LOG2_MAX_NODES node_t 的大小為 sizeof(void*) * 4 所以 node 最多有 $$\frac{1 << (sizeof(void ) << 3)} {(sizeof(void) * 4)}$$ 取 log2 可以得到 RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1，若 sizeof(void*) == 8 就會是 RB_LOG2_MAX_MEM_BYTES - 4 - 1 tree_insert 這裡透過 path 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

contributed by < Korin777 > 測驗四 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r;

contributed by < Korin777 > 測驗三 size_t swar_count_utf8(const char *buf, size_t len) { const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len >> 3; size_t count = 0; for (; qword != end; qword++) {

contributed by < Korin777 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian

2022q1 第 18 週測驗題 rbtree-minimal node->__rb_parent_color 紀錄 node 的 parent 及 node 的 color 程式碼註解中小寫為 red node 大寫為 black node 帶有括號則兩種都有可能 e.g n N (n) 以 kernel-scheduler Figure 3.3: data structure: red-black tree 的圖來看 假如 __rb_erase 的 node 是 2 的話會進到 case1 , 移除掉的節點是紅色 , 所以 rebalance 會是 NULL 不會進行 __rb_erase_color ; 反之 __rb_erase 移除的 node 是 31 的話 , 因為移除的 node 是黑色的 , 所以 rebalance 會是 node 34 , __rb_erase_color 會進到 if 的 case 4 並 break 出來 [ ] __rb_erase

Goal Check how to use SDL systemcall in rv32emu Learn the transplant process of quake by quakembd which run quake in ARM ISA run quake on rv32emu whitch is an instruction set architecture (ISA) emulator implementing the 32 bit RISC-V processor model Step of this project 1. Compile C code to riscv 32bits elf file which can run on rv32emu Get riscv64-unknown-elf(Newlib multilib)

contributed by < Korin777 > GitHub 以第 11 週測驗題第二題的程式碼為基礎，實作有效的並行鏈結串列，並搭配第 13 週測驗題第一題的記憶體管理 (以 mmap 系統呼叫實作) 程式，儘量降低 lock contention。 論文研讀: 〈Lock-Free Linked Lists and Skip Lists〉 撰寫測試程式: 設計實驗量化分析 scability，參考 concurrent-ll glibc malloc、free 會用到 mutex -> 設計更有效率的 malloc、free 來降低 lock contention memory barrier: fence(防止 instruction reorder)

contributed by < Korin777 > 測驗二 程式研讀 程式運作 reader 會透過 load 函式 來讀 shared_config 並透過 list_insert_or_append 函式 將正在使用的 config 插入 config_dom->pointer(即為 hazard pointer) ， reader 印出 config 後在透過 drop 函式 將 config 從 hazard pointer 移除 writer 透過 swap 函式 更新 shared_config ， 並將舊的 config 透過 cleanup_ptr 函式 釋放 只有一個 writer 時 ， updating config 到 updated config 中間 ， read config 會印出兩種不同的 config ， 一個是舊的一個新的 config ， 等到 updated config 後 read config 所印出的 config 才會一致

測驗 1 void *memchr_opt(const void *src_void, int c, size_t length) { const unsigned char *src = (const unsigned char *) src_void; unsigned char d = c; while (UNALIGNED(src)) { if (!length--) return NULL; if (*src == d)

contribute by < Korin777 > 測驗一 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r;

contributed by < Korin777 > Linux 效能分析 限定 CPU 給特定的程式使用 在 /etc/default/grub 中新增 isolcpus 參數GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1" 更新 /boot/grub/grub.cfg$ sudo update-grub 重新開機

contribute by < Korin777 > 測驗一 在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如: GENMASK(6, 4) 產生 $01110000_{2}$ GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元) 已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義: #define GENMASK(h, l) \

contributed by < Korin777 > 測驗一 延伸問題一 考慮以下對二個無號整數取平均值的程式碼: #include <stdint.h> uint32_t average(uint32_t a, uint32_t b) { return (a + b) / 2;

contributed by < Korin777 > Q1 延伸題目一 函式功能: map_init 用來建立 hash table map_t 的各個 hlist_head , ht 的數量為2的冪 digraph structs {

contributed by < Korin777 > 開發環境 $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian