Free-Space Management
Free-space management 追蹤哪些 storage blocks 沒被 file / directory 使用。Allocation 要從這裡拿 blocks；delete / truncate 要把 blocks 放回來。
file grows → allocate free blocks
file deleted → return blocks to free-space structureMajor Techniques
| Technique | Good at | Main cost |
|---|---|---|
| D-OS-Ch14ea-Bit_Vector_Free_Space_Management | 找 free / contiguous bits | bitmap 可能大，分散更新多 |
| D-OS-Ch14eb-Free_Space_List_Variants | 簡單取得 free blocks | 找 contiguous ranges 較弱 |
| D-OS-Ch14ec-Space_Map | large pool、range-based free space | implementation 複雜 |
| D-OS-Ch14ed-TRIM | 告知 SSD/NVM 哪些 logical blocks 已不用 | hint batching / command overhead |
Interaction with Allocation
- Contiguous / extent allocation 需要 large contiguous holes。
- Linked allocation 只需要任意 free block。
- Indexed allocation 需要 data blocks，也可能需要 index blocks。
核心 tradeoff：metadata size、allocation speed、deallocation speed、locality、crash recovery。Free-space metadata 本身也需要 journal / COW 保護。