以上推文是来自 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) 补充一下 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)