Re: 請教這篇Secure, Efficient and Easy C programming的原理
推
04/06 10:26,
04/06 10:26
推
04/06 21:54,
04/06 21:54
→
04/06 21:55,
04/06 21:55
→
04/06 21:57,
04/06 21:57
→
04/06 22:02,
04/06 22:02
→
04/06 22:05,
04/06 22:05
推
04/06 23:19,
04/06 23:19
→
04/06 23:20,
04/06 23:20
→
04/06 23:21,
04/06 23:21
→
04/06 23:21,
04/06 23:21
推
04/08 03:12,
04/08 03:12
以上推文是來自 ptt.cc 的這串主題，其他轉信站可能之前沒看到，在此補充。
而我這篇回文是針對 EdisonX 版友的推文，稍微聊聊，可能有些偏離主題了，
標題改成「在記憶體 Heap 區裡，大家都愛用的鏈結串列」也許比較合適...
(其實還是很爛對嗎？ =_=")
To EdisonX 版友：
您這篇我之前沒看過，其內容我不是完全了解，
但我覺得其中對於「Linked List」的使用，大家的理念應該都是很接近的。
在 data-stack.c 裡面使用鏈結串列，是為了將每一次於 Runtime 做 Memory Allcation
所回傳的起始位址記錄下來，比如：
add1 = malloc(10)
add2 = malloc(20)
add3 = malloc(30)
使用鏈結串列記錄下來，最後得到：add1->add2->add3
故執行 t_pop() 函數時，可以達到：free(add1) -> free(add2) -> free(add3)
一次性將已配置記憶體都釋放掉，免除 Memory Leak 的情況。
● data-stack.c 使用鏈結串列目的：使 free() 一次到位，永絕 Memory Leak。
而在 EdisonX 版友文章中，每次 malloc() 時，有兩筆額外的資訊會被記錄：
(1) 觸發該配置的原始碼檔案，比如 1.c, 2.cpp
(2) 該原始碼檔案中，對應此次配置的程式碼行號
將這兩筆額外資訊，合成鏈結串列的 node (節點)。
也就是說，最終得到的鏈結串列，其實跟 data-stack.c 的內容差不多，
都是把連續的記憶體配置動作記錄下來，只是這次記載的資訊更豐富而已。
明顯的差別在於，釋放記憶體區塊的方法。
在 data-stack.c，是使用 t_pop() 一次性查詢鏈結串列，然後釋放全部區塊；
在 EdisonX 版友文章中，還是維持傳統 C 語言的 malloc-free 使用模式，在 malloc()
所多記錄的那個 node，就在相應的 free() 時，多進行移除該 node 的動作，
則最終留下的鏈結串列裡，都是沒被 free 的區塊。
● dbg_malloc (VC) 使用鏈結串列的目的：偵測可能發生 Memory Leak 的記憶體區塊
而在我上方推文中提到：「跟 Heap 管理器一樣，把 Heap block 串起來...」
當初推文空間有限，講得比較含糊，其實我指的是 Windows Heap Manager 的行為，
下面我把這段重新寫詳細一點。(Linux 的狀況，就待強者補充了)
所謂的 Heap Manager 是指 ntdll.dll 裡的程式碼。
一個 Windows 行程 (Process)，其記憶體空間中，有三大類的 Heap：
(1) Default Process Heap (預設 1MB 大)
(2) C Runtime Heap
(3) Application Specific Heap
每個行程都有「Heap-(1)」，使用 GetProcessHeap() 可以取得，不管它。
而「Heap-(2)」就是用 C/C++ 寫好一個程式，不管你的入口函數是 main, wmain,
tmain, WinMain, wWinMain...在進去入口函數前，所謂的 C 標準函式庫，會用
HeapCreate() 函數去建立這個「Heap-(2)」，之後你在原始碼裡面，不管寫 malloc
還是寫 new，其底層都是透過這樣的 Windows API 來達成：
HeapAlloc(CRuntimeHeap, .., 配置大小);
至於「Heap-(3)」就是排除「Heap-(1) 跟 Heap-(2)」之後，在記憶體空間裡，
不知道是誰偷偷用 HeapCreate() 去建立出來的 Heap 區域，也不必管它，
誰建的誰才需要關注它。
我們用 C/C++ 編譯器去建立的 DLL 檔，需要執行 malloc/new 嗎？
有時候需要，有時候不需要，不一定有用到 Heap。
所以 DLL 在進去入口函數 DllMain() 之前，
也會有個「C 標準函式庫」先執行：
HANDLE dllheap = HeapCreate(..);
這也算是一種「Heap-(2)」。
所以在 C/C++ 行程中，執行完 ptr = malloc(8); 然後丟給某個 dll 函數，並且
期待該 dll 函數會幫忙做 free(ptr) 是不智之舉，其底層會變成：
HeapFree(dllheap, .., ptr);
然後 Heap Manager 會發現在 dllheap 對應的這一大塊記憶體裡，
根本就沒有 ptr 可以釋放，抱錯小孩了！
Heap Manager 有四個重點：
I. Heap Manager 的功能、任務為何
II. Heap Block 更具體一點是什麼
III. 為何 free(addr) 之後，就可以釋放當初配置的大小，這筆 Size 記錄在哪
IV. Heap Manager 學別人用 Linked List 幹嘛
其中 II. 跟 III. 是同一件事，而 I. 跟 IV. 也差不多是同一件事。
Heap Manager 即負責 HeapCreate, HeapAlloc, HeapFree, HeapDestroy 這四大任務
的管理者。等於「建立/摧毀 Heap」與「配置/釋放 Heap Block」四大任務。
比如上面說的 dllheap 就是被建立出來的 Heap (堆)；
而 ptr = malloc(8); 所建立出來的東西稱之 Heap Block (堆塊)。
這中間其實還有一個東西叫 Heap Segment (堆段)。
一個 Heap 內，會有好幾個堆段；而每個堆段內，又分成好幾個堆塊。
已知虛擬記憶體位址有三大狀態：Free, Reserved, Committed
而剛建立好的堆可能 4MB 這麼大，但是很長一段時間內，都只用了幾百位元組而已，
為了要節省物理記憶體，一開始只會在 Heap 內建立比較小的堆段，比如 4KB，
之後的 mallc 請求都從此堆段中找尋堆塊來回應，當 4KB 堆段不夠用了，
則 Heap Manager 才會建立新的堆段，每次放大兩倍，也就是接著建立 8KB 堆段。
在這 4MB 中，只要還沒被拿去建立成堆段者，都是 Reserved 狀態，換言之，不佔
實體記憶體空間。堆段的地位主要是用來節省記憶體用的，通常不必管它。
當「C 標準函式庫」在進入 main() 前，就是像 SNG 車記者，要把現場還給棚內主播
(C Programmer) 前，會先用 HeapCreate() 跟一個叫「堆經理」的傢伙，申請在
記憶體空間裡要一個連續的位址空間，將其保留。
假設此位址是 0x5000~0x6FFF 總共 0x2000 大。
之後當 "棚內主播" 寫了像 malloc(7); 這樣的要求後，
就等於跟「堆經理」去要一個大小至少保證有 7+ Bytes 的堆塊。
堆經理就會進行查詢，看要回傳回應哪個堆塊的起始位址給主播用。
這樣的「malloc/free」要求是連綿不絕的，堆經理不能拿張紙，畫 0x2000 個格子，然後
把已配置的用鉛筆打勾，沒配置的保留空白，這樣的資料結構很難用...
比如當有人要求配置 11 Bytes 堆塊時，就要從格子最左邊開始找，一直到至少有
連續 11 個空格出現為止，才有辦法回應申請。
所以 Windows 的「堆經理」，為了能快速解決這些從早煩到晚的申請，找了兩套機器，
叫前堆分配器 (Front-End Allocator) 跟後端分配器 (Back-End Allocator)。
前端分配器，處理申請的速度很快，但不是每個 malloc(..) 請求它都能處理，
當它處理不了的，就交給後端分配器去搞，後端分配器一定能完成任務，但速度比較慢。
後端分配器不管它。
前端分配器在 Windows Vista 之前，使用的型號都叫「Look Aside List」，簡稱 LAL。
到了 Vista 之後，型號則是「LOW Fragmentation」，簡稱 LF。
在 XP 可以用 HeapSetInformation 使分配器變成 LF。
LF (低碎片) 分配器還是不管它。
LAL (對應單) 分配器就是不管堆的總體有多大，都把它區分成 128 大類，
也就是建立 LAL[128] 陣列，其中 LAL[0] 沒在用，所以不管它。
LAL[1] -> 16 Bytes
LAL[2] -> 24 Bytes
LAL[3] -> 32 Bytes
.
.
.
LAL[127] ->1024 Bytes
也就是說，如果中共打過來，政府有 18 套劇本可以對應，
如果有人要求 malloc，那堆經理就有 127 套劇本可以對應，記錄在 LAL 對應單上面。
每個堆塊的組成，都要求至少得在最前方留下 8 Bytes Metadata，裡面會記錄
此堆塊的大小，所以 free(ptr) 這樣跑之所以能成立，是因為 "堆經理" 會到
「(char *) ptr - 8」這個位址去查詢此堆塊的 Metadata，
以得知此次共需釋放多大的空間。
從 LAL 對應清單中得知，最小的堆塊都有 16 Bytes 這麼大，扣掉 Metadata 後，
該次 malloc 的申請者最少也能得到 8 bytes 的空間，所以那些以為申請 malloc(1)
要省記憶體的人，請認清楚：堆塊的大小是 8 Bytes 起跳的
你去自助餐夾一根花椰菜難道還期待老闆算你幾塊錢嗎？
至少都是「5塊/10塊」或「一份/半份」這樣算錢的...
當然老闆講人情的話可以不計較，但 ntdll.dll 是沒有人性的。
※ Windows Internal 的說法，好像「64位元程式」的 Heap Block 最小單位
不是 16 Bytes 而是 24 Bytes？沒有寫得很詳細，但這不影響大局，沒關係。
malloc(1~8) 的申請，都是使用對應單裡的 LAL[1]
malloc(9~16) 的申請，都使使用對應單裡的 LAL[2]
.
.
以此類推。
而 LAL 陣列的每一項，都是一個鏈結串列，記錄所有可以被 malloc() 的堆塊。
假設下面這三個連續位址內，都是等待配置的 16-Byte-Size 堆塊。
0x5000~0x500F
0x5010~0x501F
0x5020~0x502F
則 LAL[1]->0x5000->0x5010->0x5020
當發生 ptr1 = malloc(1) 時，會得到 ptr1 = 0x5008;
且對應單變成 LAL[1]->0x5010->0x5020
同理，若又發生 ptr2 = malloc(8) 時，會得到 ptr2 = 0x5018;
且對應單變成 LAL[1]->0x5020
然後若發生 malloc(8) 將使 LAL[1] 的鏈結串列清空。
接著再一次 malloc(8) 就會使前端分配器束手無策，改用後端分配器去處理。
後端分配器如何解決 16-Bytes 堆塊不足的問題呢？
其實是找比 16 Bytes 大的堆塊，也就是 24, 32, 40... Bytes 這些堆塊，找到
還閒置的就把它拿來分割成小的堆塊，比如把 32 毀掉一個，創造兩個 16 Bytes 堆塊。
● Heap Manager 使用鏈結串列的目的：快速回應 malloc 的請求
回頭檢視「ptr1 = malloc(1) 得到 ptr1 = 0x5008」這筆配置的底層。
如果用 WinDbg 指鹿為馬的 dt 功能的話，那就是透過以下指令：
dt _HEAP_ENTRY 0x5008 - 0x8
就可以解讀此 Heap Block 的 Metadata 內容：
+0x00 Size : 0x0002 (乘以「堆粒度:8」之後才是真實大小)
+0x02 PreviousSize : 不一定
+0x04 SmallTagIndex : 不知道，不管它
+0x05 Flags : 旗標
+0x06 UnusedBytes : 0x07
+0x07 SegmentIndex : 堆段索引，表明它屬於哪個堆段
這個 Heap Block 之前說過是 16 Bytes，其中 malloc 只有請求 1 Byte，
所以共有 7 Bytes 在此堆塊中是 Unused 的。
PreviousSize 假設是 0x0008 好了，表示緊鄰的前一個堆塊大小為 64 Bytes。
因為有這個記錄，所以可以從目前堆塊，去索引到前一個 Heap Block 的起始點；
又因為有自己 Heap Block 的 Size，所以又可以向後索引到下一個 HeapBlock 的起點。
這也是一種鏈結串列的利用，方便任意往前、往後遍歷所有的 Heap Blocks。
至於 Flags 詳細如下：
0x01 - HEAP_ENTRY_BUSY
0x02 - HEAP_ENTRY_EXTRA_PRESENT
0x04 - HEAP_ENTRY_FILL_PATTERN
0x08 - HEAP_ENTRY_VIRTUAL_ALLOC
0x10 - HEAP_ENTRY_LAST_ENTRY
0x20 - HEAP_ENTRY_SETTABLE_FLAG1
0x40 - HEAP_ENTRY_SETTABLE_FLAG2
0x80 - HEAP_ENTRY_SETTABLE_FLAG3
只有黃色的需要關注，這裡的 BUSY 不代表已配置給 "棚內主播" 那種配置，
有兩種可能，一種是被前堆分配器拿去用，另一種是真的配置給 C Programmer 了。
反正使用者不會直接查看 Metadata 來決定堆塊可以不可以拿去用，而是會詢問 LAL，
而 LAL 也不會去看 Metadata，而是查自己的「對應單」，當對應單找不到對應方案時，
才把處理權轉交給後端分配器。
一直到當後端分配器把某個 Heap Block 拿去配置後，才會
去 Set 該堆塊的 HEAP_ENTRY_BUSY 旗標。
當 Flags 值為偶數時，也就是 unset BUSY 時，就代表堆塊才剛被 HeapFree 完而已。
HEAP_ENTRY_VIRTUAL_ALLOC 告訴我們，該堆塊是直接由 VirtualAlloc 所配置而來。
C Programmer 有時候請求的 malloc() 大小是很超過的，隨便就好幾 MB 當基本單位。
而 Metadata 欄位才 2 Bytes 寬，頂天了也就 0xFFFF，就算乘以堆粒度 8 之後，
也只有 511 KiB 可以記錄。
這種過度的要求丟給 Heap Manager 時，Heap Manager 會又丟給上層的
虛擬記憶體管理員，總之就是 VirtualAlloc 系列函數。
(該系列函數的粒度 (granularity) 是 64KB 當基本單位)
就好像酒店客人拿錢給服務生，說要買烤鴨一樣...都是外包的業務。
當一個 malloc(幾MB) 的要求丟給 Heap Manager 時，雖然會轉交給 VirtualAlloc
來配置，該塊配置記憶體還是會被添加 Heap Block 的 Metadata，並標明此
FLAG 來註記：「這是一個不位於 Heap 區域內的記憶體區塊」。
Heap Corruption 最常見的情況，就是寫入 Heap 記憶體時，破壞了 Metadata。
比如你 vadd = malloc(8)，可是卻從 vadd 開始連續寫入遠過八位元組的資料，
使相鄰的下一個 Heap Block 資訊被破壞掉，無法正常使用。
資料來源：
Advanced Windows Debugging
http://advancedwindowsdebugging.com/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.128.253
※ 編輯: purpose 來自: 124.8.128.253 (04/08 14:06)
推
04/08 14:49, , 1F
04/08 14:49, 1F
補充一下 Heap Block 的 Metadata 在 VISTA 之後似乎有變動，我之前是在 XP 觀察的
最精確的解讀方式是使用 WinDbg 的 !Heap 這個 Extension，新的手動解讀方式：
http://advdbg.org/blogs/advdbg_system/articles/5152.aspx
簡單來說，有經過編碼，要先做 XOR 解碼後才是正確的值，防止 shellcoder 用的。
※ 編輯: purpose 來自: 124.8.138.253 (04/08 18:44)
推
04/08 20:29, , 2F
04/08 20:29, 2F
推
04/08 21:49, , 3F
04/08 21:49, 3F
推
08/18 02:52, , 4F
08/18 02:52, 4F
推
08/18 11:00, , 5F
08/18 11:00, 5F
討論串 (同標題文章)