Source: Geeks for geeks-Interval Tree

考慮已有一 interval 集合，要對其進行以下操作

• 新增 interval
• 移除 interval
• 查詢 interval x 是否與現存任意 interval 重疊

Interval tree

• 滿足上述操作在 O(log(n)) 內完成
• augment a self-balancing BST (Red Black Tree, AVL Tree)

每個節點儲存

• interval: [low, high]
• max: subtree + 節點自身的最大值

Source: https://www.dgp.toronto.edu/public_user/JamesStewart/378notes/22intervals/

裡面的 Interval Tree 實際上是對應 Segment tree ，不曉得是不是通用稱法。下面以 Segment Tree 稱之。

名詞介紹

• interval: 由兩個整數 a, b 構成的區間[a, b]
• elementary interval: 加入 integer line 而切割出的不同區段

給定 n 個 intervals [ai, bi], for i = 1 … n, 假設這些 intervals 不共享 endpoint，那會得到 2n + 1 個 sub-intervals。

常用 git 指令

1
2
3
4
5
6
7
8
9
10

#define xstr(s) str(s)
#define str(s) #s
#define foo 4

 str (foo)
      ==> "foo"
 xstr (foo)
      ==> xstr (4)
      ==> str (4)
      ==> "4"

str() 會將參數直接字串化，不做展開。
對 xstr(s) 會先展開 s，因此 str() 拿到的是已展開的參數。

Ref: 3.4 Stringification

Load constants

All AArch64 instructions are 32-bits long…

ARM instruction 只有 32 bits 長，需要借助 pseudo instruction: adr, ldr 的輔助，例如載入常數

1
2

ldr rd, =constant # rd=32-bit constant
adr rd, label     # rd=32-bit relative address

ldr 會依據情況轉換成 mov, mvn, ldr [pc, #offset] 等指令，= 用意是從 literal pool 找出該常數，若沒有就放入 literal pool。

binutils-aarch64-linux-gnu 套件缺乏 aarch64-linux-gnu-gdb，於是直接抓 binutils-gdb 下來編譯。

Build gdb

ubuntu 21.10

1
2
3

git clone git://sourceware.org/git/binutils-gdb.git --depth=1 --branch gdb-11.2-release
./configure --target=aarch64-linux-gnu
make -j8

ubuntu 24.04

1
2
3

git clone git://sourceware.org/git/binutils-gdb.git --depth=1 --branch gdb-13.1-release
./configure --target=aarch64-linux-gnu
make -j1

紀錄安裝細節，但因為 wordpress 套件 githuber-md 1.17.0 bug 修復進度緩慢，markdown 顯示上仍有問題，只發一篇文就受不了改用 hexo。

2022 年那一陣子準備面試材料，看到 vDSO 帶來效能提升方式，也就是在 user space 直接調用 vDSO 無需切換至 kernel space，對 process 在 kernel space 和 user space 是如何切換的感到好奇。又看到 osdi lab 有整份作業需求放出來，想說多一份面試材料也不錯，兩個月內零基礎應該可以自幹出來，結果幹了快一年XD（做到 lab3 後面試上後就懶得更新）

1
2

Q: 找不到好用的 VFS 範例
A: 要有檔案 建回檔案系統 就要看救援軟體(testdisk)

不愧是大佬，直接看大型專案，對我而言太 hardcore，還是請示了一下 AI：

Question 1. Without indirect branch, the code might still work fine, why it’s the case and why it’s mandatory to use indirect branch.

讓 PC-relative 的指令如 adr 使用到正確的值(program counter)。

Question 2. For mapping 1GB memory region, how many page frames are used by page tables(PGD, PUD, PMD, and PTE) in four level translation?

(PGD * 1) + (PUD * 1) + (PMD * 1) + (PTE * 512) = 515 page

Question 3. If a page frame is allocated and to be mapped at user space. Is it necessary to initialize it into 0?

當整頁當作 user task .bss 時需要，否則交給 user space 去初始化即可。但在讀取 page table entry 時是以 0 作為是否已使用的判斷(page table 也是存放在 page 上)，因此有對 page 寫 0 的必要。