본 글은 Windows 10 20H2 버전을 기준으로 설명된 자료를 토대로 작성됐다(해당 자료 정보는 Reference 참고)
Windows Kernel Pool Allocator
- Windows 10 19H1(1903) 버전 이후로 Windows는 Kernel Pool Allocator로 Segment Heap을 사용하고 있다.
글의 목차
I-1. Segment Heap 개요
I-2. 중요한 구조체
II. Frontend Allocation
1. Low Fragmentation Heap(LFH)
2. Variable Size(VS) Allocation
III-1. Pool Header
III-2. Dynamic Lookaside
IV. Backend Allocation
1. Segment Allocation
2. Large Block Allocation
II. Frontend Allocation
2. Variable Size(VS) Allocation
Size
(1) Size <= 0x200 && LFH not enabled
(2) 0x200(512byte) < Size <= 0xfe0(4064byte)
(3) ( 0xfe0 < Size <= 0x20000(128KB) ) && (Size & 0xfff) != 0
데이터 구조체
Chunk
- memory allocator의 기본 구조체
- VS allocation의 chunk 앞에는, 청크의 정보를 담고있는 metadata가 존재한다. (-> _HEAP_VS_CHUNK_HEADER && _HEAP_VS_CHUNK_FREE_HEADER)
- NtHeap의 back-end allocator와 유사하다
_HEAP_VS_CHUNK_HEADER
//0x10 bytes (sizeof)
struct _HEAP_VS_CHUNK_HEADER
{
union _HEAP_VS_CHUNK_HEADER_SIZE Sizes; //0x0
union
{
struct
{
ULONG EncodedSegmentPageOffset:8; //0x8
ULONG UnusedBytes:1; //0x8
ULONG SkipDuringWalk:1; //0x8
ULONG Spare:22; //0x8
};
ULONG AllocatedChunkBits; //0x8
};
};//0x8 bytes (sizeof)
union _HEAP_VS_CHUNK_HEADER_SIZE
{
ULONG MemoryCost:16; //0x0
struct
{
ULONG UnsafeSize:16; //0x0
ULONG UnsafePrevSize:16; //0x4
ULONG Allocated:8; //0x4
};
USHORT KeyUShort; //0x0
ULONG KeyULong; //0x0
ULONGLONG HeaderBits; //0x0
};• MemoryCost: Free'd일 때만 사용된다
• UnsafeSize: Chunk의 size. 청크의 진짜 size를 오른쪽으로 4bit만큼 shift한 값이 저장돼 있다(== 진짜 Size을 16으로 나눈 값)
• UnsafePrevSize: Previous chunk의 size. UnsafeSize와 동일하게 진짜 Size를 16으로 나눈 값이 저장돼 있다.
• Allocated: Chunk가 allocated 되었는지를 나타내는 값. Allocated 돼있다면 값은 1이다.
• Sizes 구조체의 멤버에는 값들이 Encoding 되어 저장된다. ( Encoding -> Chunk 헤더 ^ Chunk 주소 ^ RtlpHpHeapGlobals.HeapKey )
• EncodedSegmentPageOffset: VS subsegment 안에 있는 청크의 페이지의 인덱스를 나타낸다. VS subsegment를 찾을 때 사용되며, 이 값 또한 encode 되어 저장된다. (encoding -> (int8)Chunk 주소 ^ (int8)RtlpHpHeapGlobals.HeapKey ^ SegmentPageOffset)
• UnusedBytes: 할당된 청크가 unused memory를 갖고 있는지 나타냄
_HEAP_VS_CHUNK_FREE_HEADER
//0x20 bytes (sizeof)
struct _HEAP_VS_CHUNK_FREE_HEADER
{
union
{
struct _HEAP_VS_CHUNK_HEADER Header; //0x0
struct
{
ULONGLONG OverlapsHeader; //0x0
struct _RTL_BALANCED_NODE Node; //0x8
};
};
};• MemoryCost: 청크가 할당될 때 몇 개의 page가 필요한지 나타낸다.
• 위의 8byte는 allocated chunk와 동일하다
• Node(_RTL_BALANCED_NODE): rbtree의 노드 && Free'd chunk는 rbtree 구조체에 저장된다.
//0x18 bytes (sizeof)
struct _RTL_BALANCED_NODE
{
union
{
struct _RTL_BALANCED_NODE* Children[2]; //0x0
struct
{
struct _RTL_BALANCED_NODE* Left; //0x0
struct _RTL_BALANCED_NODE* Right; //0x8
};
};
union
{
struct
{
UCHAR Red:1; //0x10
UCHAR Balance:2; //0x10
};
ULONGLONG ParentValue; //0x10
};
};- Children
-> Left/Right: node의 왼쪽과 오른쪽 subtree
- ParentValue: 해당 node의 parent node
VsContext(_HEAP_VS_CONTEXT)
- VS Allocator의 core 구조체
- VS allocator에 의해 할당된 memory를 manage 하기 위해 사용된다. 또한, VS allocator의 모든 정보와 구조체를 heap에 저장한다.
//0xc0 bytes (sizeof)
struct _HEAP_VS_CONTEXT
{
ULONGLONG Lock; //0x0
enum _RTLP_HP_LOCK_TYPE LockType; //0x8
struct _RTL_RB_TREE FreeChunkTree; //0x10
struct _LIST_ENTRY SubsegmentList; //0x20
ULONGLONG TotalCommittedUnits; //0x30
ULONGLONG FreeCommittedUnits; //0x38
struct _HEAP_VS_DELAY_FREE_CONTEXT DelayFreeContext; //0x40
VOID* BackendCtx; //0x80
struct _HEAP_SUBALLOCATOR_CALLBACKS Callbacks; //0x88
struct _RTL_HP_VS_CONFIG Config; //0xb0
ULONG Flags; //0xb4
};• Lock: Lock을 위해 존재함
• LockType(_RTLP_HP_LOCK_TYPE): Lock type으로는 Paged, NonPaged, TypeMax가 존재한다.
• FreeChunkTree(_RTL_RB_TREE): VS Allocation에서는 chunk를 free 하면, 그 청크는 heap에 존재하는 FreeChunkTree로 자신의 Size에 맞게 삽입되게 된다.
- 만약, chunk의 size가 node보다 크다면 오른쪽 subtree에, 그렇지 않다면 왼쪽 subtree에 위차하게 된다.
- 만약, 해제된 chunk보다 Size가 큰 chunk가 없다면, 오른쪽과 왼쪽 subtree는 모두 NULL이다.
* tree로부터 꺼내질 때, node check를 수행한다.
//0x10 bytes (sizeof)
struct _RTL_RB_TREE
{
struct _RTL_BALANCED_NODE* Root; //0x0
union
{
UCHAR Encoded:1; //0x8
struct _RTL_BALANCED_NODE* Min; //0x8
};
};- Root: rbtree의 root를 가리키는 포인터
- Encoded: root가 encode 되어있는지 나타낸다. 기본값은 disable이다.(EncodedRoot = Root ^ FreeChunkTree)
• SubsegmentList(_LIST_ENTRY): subsegment들 doubly-linked list로 관리한다.
• DelayFreeContext(_HEAP_VS_DELAY_FREE_CONTEXT): Delay Free가 enable 돼있고(kernel의 기본값: enabled <-> User mode 기본값: disabled) && chunk size < 0x1000이라면, chunk를 free 했을 때 바로 free가 되는 것이 아니라 DelayFreeContext라는 singly-linked-list에 들어가게 된다. 그리고 DelayFreeContext에 들어있는 chunk의 개수가 0x20을 넘어가면 DelayFreeContext 안에 있는 chunk들은 한꺼번에 free 되게 된다.
- "NextEntry 포인터"가 user data의 시작 부분에 삽입된다
- FILO 방식으로 동작한다
- Delay Free가 enable 돼있는지 확인하려면, VsContext->Config를 확인하면 된다.
//0x10 bytes (sizeof)
struct _HEAP_VS_DELAY_FREE_CONTEXT
{
union _SLIST_HEADER ListHead; //0x0
};//0x10 bytes (sizeof)
union _SLIST_HEADER
{
struct
{
ULONGLONG Alignment; //0x0
ULONGLONG Region; //0x8
};
struct
{
ULONGLONG Depth:16; //0x0
ULONGLONG Sequence:48; //0x0
ULONGLONG Reserved:4; //0x8
ULONGLONG NextEntry:60; //0x8
} HeaderX64; //0x0
};- Depth: Linked list에 들어있는 chunk의 개수
- NextEntry: 다음 청크를 가리키는 포인터. Chunk가 할당되어 있을 때도 user data의 시작 부분에 삽입돼있다.
• BackendCtx: VS에 의해 사용되는 Backend allocator (_HEAP_SEG_CONTEXT)를 가리킨다.
• Callbacks(_HEAP_SUBALLOCATOR_CALLBACKS): subsegment를 할당 또는 release하기 위해 사용되는 Call back function 테이블. Allocate, Free, Commit, Decommit, ExtendContext 등.
-> 이러한 Callbacks의 함수 포인터들은 (1) RtlpHpHeapGlobals.Heapkey, (2) LfhContext의 주소, (3) Function pointer와 xor 한 뒤 encoding하여 저장된다.
• Config(_RTL_HP_LFH_CONFIG): (1) VS Allocator의 속성(attribute)을 나타내기 위해 사용된다.
//0x4 bytes (sizeof)
struct _RTL_HP_VS_CONFIG
{
struct
{
ULONG PageAlignLargeAllocs:1; //0x0
ULONG FullDecommit:1; //0x0
ULONG EnableDelayFree:1; //0x0
} Flags; //0x0
};- PageAlignLargeAllocs (kernel 기본값: 1 && user mode 기본값: 0)
- FullDecommit
- EnableDelayFree(kernel 기본값: 1 && user mode 기본값: 0 )
VS Subsegment(_HEAP_VS_SUBSEGMENT)
- VS allocation의 memory pool
- Allocation을 위한 충분한 subsegment가 존재하지 않는다면, Backend allocator를 통해 새로운 subsegment를 할당받는다.
- 각 subsegment들은 linked list로 연결된다
//0x28 bytes (sizeof)
struct _HEAP_VS_SUBSEGMENT
{
struct _LIST_ENTRY ListEntry; //0x0
ULONGLONG CommitBitmap; //0x10
ULONGLONG CommitLock; //0x18
USHORT Size; //0x20
USHORT Signature:15; //0x22
USHORT FullCommit:1; //0x22
};• ListEntry(_LIST_ENTRY): (1) Flink: 다음 subsegment를 가리킨다, Blink: Previous subsegment를 가리킨다. (2) 이때 ListEntry 안의 Flink와 Blink 값들은 encoding 되어 저장된다.(Encoded value == Flink(Blink) ^ ListEntry의 주소 ^ next(prev) subsegment의 주소). (3) doubly-linked list check가 존재한다.
• CommitBitmap: subsegment 안에 있는 page commit의 상태를 나타낸다. 또한, 페이지는 subsegment의 시작 부분에서 시작한다.
• CommitLock: Commit 시에 사용되는 Lock
• Size: VS subsegment의 Size(16으로 나눠진 값이 저장돼있다. 원래 값 == Size멤버 값 x 16)
• Signature: Verification을 위해 존재한다. Make sure that subsegment is found when free
• VS Subsegment 헤더의 뒤에는 VS Allocator의 memory pool이 존재한다. 처음엔 Subsegment의 memory pool은 large chunk이다. 이 large chunk가 Allocate 시에 쪼개지게 된다. 또한, to-be-freed 블럭을 병합한다.
Memory Allocation Mechanism
Allocate
- Main implementation 함수는 nt!RtlpHpVsContextAllocateInternal()이다.
(1) 이 함수는 시작 부분에 할당 요청 받은 chunk size를 계산한다
(2) 그 후, VsContext 안의 FreeChunkTree에서 적합한 청크가 있는지 탐색한다. FreeChunkTree에서 chunk를 탐색할 때, root에서부터 요청 받은 chunk의 크기가 현재 노드보다 더 크다면 NULL을 만날 때까지 right subtree를 타고 가며 찾는다.
(3) 만약 FreeChunkTree에서 적합한 청크를 찾는 데 실패했다면, Subsegment를 Backend allocator로부터 할당 받고, 할당 받은 Subsegment를 VsContext에 추가한다. 그 후, FreeChunkTree를 다시 탐색한다.
(3-a) Subsegment를 initialize 할 때 large chunk를 생성한다
(3-b) nt!RtlpHpVsSubsegmentCreate(): Backend에게 RtlpHpSegVsAllocate() 함수를 통해 memory를 요창한다. 그 후, 새로운 subsegment를 생성한다. 이때 minimum size는 0x10000이다.
(4) ntoskrnl!RtlpHpVsContextAddSubsegment(): VsContext에 Subsegment를 추가해주는 함수. Config의 PageAlignLargeAllocs를 enable 할지에 따라 어떻게 subsegment를 split 할지 결정한다.
(4-a) 만약 PageAlignLargeAllocs가 enable 돼있으면, Subsegment는 두 개의 청크로 split 된다. 청크 하나는 Subsegment 구조체 바로 뒤에 오는 첫 번째 청크이고, 또다른 청크는 페이지 alignment이다. 이 청크의 user data는 aligned 되어있다. 그 후, 두 청크는 FreeChunkTree에 추가된다.
(4-b) PageAlignLargeAllocs가 disable 돼있으면, subsegment 전체는 하나의 large chunk로 간주되어 FreeChunkTree에 추가된다.
(5) 만약 FreeChunkTree에서 찾은 chunk의 size가 할당 요청 받은 size보다 크다면, 그 청크는 split 된다. 그 후 split된 남은 청크는 다시 FreeChunkTree에 추가한다.
(5-a) RtlpHpVsChunkSplit(): FreeChunkTree에서 청크를 꺼낸 뒤, 청크를 split 하고, FreeChunkTree로 청크를 new freed 청크로 다시 추가한다.
(5-b) 또한 page alignment가 활성화 돼있는지 아닌지에 따라 chunk를 split한다. 만약 chunk size가 한 페이지를 초과한다면, page align에 따라 split하고 남은 청크를 다시 split한다.
(5-c) 만약 request size < chunk size라면, 청크의 마지막 2byte에 unused byte를 기록해둔다. (몇 개의 바이트가 안 쓰이고 있는지)
Free
- Main implementation 함수는 nt!RtlpHpVsContextFree()이다.
(1) 가장 먼저 Subsegment의 Signature와 할단된 바이트를 검사한다. (Check: Subsegment->Size ^ Subsegment->Signature ^ 0x2BED == 0. Check가 실패하면 BSOD가 발생한다)
(2) 그 후, VsContext->DelayFreeContext에 있는 chunk의 개수가 0x20보다 큰지 확인한다. (VsContext->DelayFreeContext.Depth > 0x20). 만약 0x20보다 적게 들어있다면, DelayFreeContext(singly-linked list)의 처음에 해당 청크를 삽입한 뒤, ret 한다.
(3) 만약 'DelayFreeContext > 0x20'이라면, DelayFreeContext(singly-linked list)안에 있는 청크를 하나하나씩 free 한다. 이때, chunk를 free 할 때, chunk가 위치하고 있는 VS Subsegment를 찾기 위해 EncodedSegmentPageOffset이 사용된다. 그 후, 할당된 바이트와 Segment signature를 검사한다.
(4) 그 후, 앞 청크와 바로 그 뒤 청크가 병합될 수 있는지 체크한다. 만약 VsContext->Config에 PageAlignLargeAllocs가 enable 돼있다면 병합 체크를 할 때 세 개의 청크를 체크한다. 병합된 청크는 우선 FreeChunkTree에서 제거된 후 tree structure check를 수행한다. 병합 후엔 앞 청크의 prev_size와 병합된 청크의 size를 업데이트 해준다.
(4=a) 청크들을 병합할 때는 RtlpHpVsChunkCoalesce() 함수가 사용된다.
(5) 병합 후, 'chunk 주소+0x20'이 page의 시작이라면, chunk는 page align 되고 두 개로 split 된다.
(6) 만약 병합된 청크의 size가 Subsegment의 size와 정확히 똑같다면, subsegment 전체는 linked list에서 제거된다.
(7) 이때, doubly linked list check가 존재한다. Check를 수행한 후 subsegment는 Backend allocator에게 release 된다.
(!6) 병합된 청크의 size가 Subsegment의 size와 똑같지 않다면, 청크의 MemoryCost와 SegmentPageOffset을 계산한 뒤 encode 한다. 그 후 마지막으로 FreeChunkTree에 삽입하기 위해 FreeChunkTree에서 청크가 들어가기에 적합한 위치를 찾는다.
Reference
https://speakerdeck.com/scwuaptx/windows-kernel-heap-segment-heap-in-windows-kernel-part-1
Windows Kernel Heap: Segment heap in windows kernel Part 1
Windows Kernel Heap: Segment heap in windows kernel Part 1 Segment heap internals
speakerdeck.com
