본 글은 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
I-1. Segment Heap 개요
I-2. 중요한 구조체
1. _EX_POOL_HEAP_MANAGER_STATE
2. _SEGMENT_HEAP
3. _RTLP_HP_HEAP_GLOBALS
1. nt!ExPoolState (_EX_POOL_HEAP_MANAGER_STATE)
- Kernel Pool Memory Allocator의 core 구조체이다.
- Paged Pool, Non-Paged Pool, etc.들은 이 구조체(_EX_POOL_HEAP_MANAGER_STATE)에 의해 관리된다.
//0x86940 bytes (sizeof)
struct _EX_POOL_HEAP_MANAGER_STATE
{
struct _RTLP_HP_HEAP_MANAGER HeapManager; //0x0
ULONG NumberOfPools; //0x38d0
struct _EX_HEAP_POOL_NODE PoolNode[64]; //0x3900
struct _SEGMENT_HEAP* SpecialHeaps[4]; //0x86900
};
• HeapManager(_RTLP_HP_HEAP_MANAGER): 전역 변수, Metadata들을 저장하고 있다.
• NumberOfPools: Pool node의 개수를 저장하고 있는 변수. 기본값은 1이다
• PoolNode(_EX_HEAP_POOL_NODE): 각 노드들은 Paged/Nonpaged pool과 같이 Segment Heap에 해당하는 네 개의 Heap을 갖고 있다.
2. _SEGMENT_HEAP
- Segment Heap의 core 구조체이다
- 각각의 Pool들은 _SEGMENT_HEAP 구조체를 갖고 있다. Memory를 할당할 때, pool type에 맞는 memory를 _SEGMENT_HEAP을 보고 결정한다.
- ExPoolState 안에 있는 _SEGMENT_HEAP: ExPoolState.PoolNode[0].Heap[0~4]에 해당한다. 이 4개의 Segment Heap들은 시스템이 부팅될 때 생성되고 initialized 된다.
ExPoolState.PoolNode[0].Heap[0] --> NonPagedPool
ExPoolState.PoolNode[0].Heap[1] --> NonPagedPoolNx
ExPoolState.PoolNode[0].Heap[2] --> PagedPool
//0x800 bytes (sizeof)
struct _SEGMENT_HEAP
{
struct RTL_HP_ENV_HANDLE EnvHandle; //0x0
ULONG Signature; //0x10
ULONG GlobalFlags; //0x14
ULONG Interceptor; //0x18
USHORT ProcessHeapListIndex; //0x1c
USHORT AllocatedFromMetadata:1; //0x1e
union
{
struct _RTL_HEAP_MEMORY_LIMIT_DATA CommitLimitData; //0x20
struct
{
ULONGLONG ReservedMustBeZero1; //0x20
VOID* UserContext; //0x28
ULONGLONG ReservedMustBeZero2; //0x30
VOID* Spare; //0x38
};
};
ULONGLONG LargeMetadataLock; //0x40
struct _RTL_RB_TREE LargeAllocMetadata; //0x48
volatile ULONGLONG LargeReservedPages; //0x58
volatile ULONGLONG LargeCommittedPages; //0x60
union _RTL_RUN_ONCE StackTraceInitVar; //0x68
struct _HEAP_RUNTIME_MEMORY_STATS MemStats; //0x80
USHORT GlobalLockCount; //0xd8
ULONG GlobalLockOwner; //0xdc
ULONGLONG ContextExtendLock; //0xe0
UCHAR* AllocatedBase; //0xe8
UCHAR* UncommittedBase; //0xf0
UCHAR* ReservedLimit; //0xf8
struct _HEAP_SEG_CONTEXT SegContexts[2]; //0x100
struct _HEAP_VS_CONTEXT VsContext; //0x280
struct _HEAP_LFH_CONTEXT LfhContext; //0x340
};
• EnvHandle(RTL_HP_ENV_HANDLE): Segment Heap의 environment handle
• Siganature: Segment Heap의 signature. 이 값은 항상 0xddeeddee이다.
• AllocatedBase: _SEGMENT_HEAP 구조체의 끝 부분을 가리키는 포인터이다. LFH Allocator에 의해 요구되는 구조체를 할당하기 위해 사용된다. 할당된 이후에, 할당된 구조체의 끝을 가리킨다.
• SegContexts(_HEAP_SEG_CONTEXT): back-end 관리자의 core 구조체이다. Size에 따라 두 개의 context로 나뉜다.
(1) 0x20000(128KB) < Size <= 0x7f000(508KB)
(2) 0x7f000(508KB) < Size <= 0x7f0000(8128KB)
• VsContext(_HEAP_VS_CONTEXT): front-end에 있는 VS Allocator의 core 구조체
• LfhContext(_HEAP_LFH_CONTEXT): front-end에 있는 LowFragmentationHeap Allocator의 core 구조체
3. nt!RtlpHpHeapGlobals(_RTLP_HP_HEAP_GLOBALS)
- Segment Heap에서 많은 field, 값, 함수들은 대부분 encoding 되어있다.
- 이 구조체(nt!RtlpHpHeapGlobals)는 이런 encoding 되어 있는 값들에 대한 키들과 다른 관련 정보들을 저장하는 데 사용한다.
//0x38 bytes (sizeof)
struct _RTLP_HP_HEAP_GLOBALS
{
ULONGLONG HeapKey; //0x0
ULONGLONG LfhKey; //0x8
struct _HEAP_FAILURE_INFORMATION* FailureInfo; //0x10
struct _RTL_HEAP_MEMORY_LIMIT_DATA CommitLimitData; //0x18
};
• HeapKey: VS Allocator, Segment Allocator에 의해 사용된다.
• LfhKey: LowFragmentationHeap(LFH)에 의해 사용된다
-> HeapKey와 LfhKey는 모두 8byte 크기의 random 값이다.
II. Frontend Allocation
1. Low Fragmentation Heap(LFH)
크기
- Size <= 0x3FF0(16,368 byte)인 경우에 해당된다
- NtHeap과 activate 되는 타이밍이 매우 유사하다. LFH 크기에 해당하는 정확히 같은 크기의 chunk들이 17개 할당 돼야 활성화 된다.
데이터 구조체
LfhContext(_HEAP_LFH_CONTEXT)
- LFH Allocator의 core 구조체이다. LFH에 의해 할당된 메모리를 관리하는 데 사용된다. 그리고 LFH에 의해 할당된 메모리들의 정보와 Heap에 있는 LFH의 정보들을 기록해둔다.
//0x4c0 bytes (sizeof)
struct _HEAP_LFH_CONTEXT
{
VOID* BackendCtx; //0x0
struct _HEAP_SUBALLOCATOR_CALLBACKS Callbacks; //0x8
UCHAR* AffinityModArray; //0x30
UCHAR MaxAffinity; //0x38
UCHAR LockType; //0x39
SHORT MemStatsOffset; //0x3a
struct _RTL_HP_LFH_CONFIG Config; //0x3c
union _HEAP_LFH_SUBSEGMENT_STATS BucketStats; //0x40
ULONGLONG SubsegmentCreationLock; //0x48
struct _HEAP_LFH_BUCKET* Buckets[129]; //0x80
};
• BackendCtx(_HEAP_SEG_CONTEXT): LFH에 의해 사용되는 Backend allocator를 가리킨다.
• 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) LFH Allocator의 속성(attribute)을 나타내기 위해 사용된다. 또한 (2) Allocation size가 LFH Allocator의 범위에 속하는지 결정한다.
//0x4 bytes (sizeof)
struct _RTL_HP_LFH_CONFIG
{
USHORT MaxBlockSize; //0x0
USHORT WitholdPageCrossingBlocks:1; //0x2
USHORT DisableRandomization:1; //0x2
};MaxBlockSize: LFH의 최대 size 값
WitholdPageCrossingBlocks: cross-page block(청크)가 있는지 표시하는 플래그
DisableRandomization: LFH를 randomize 할 건지를 나타내는 플래그
• Buckets(_HEAP_LFH_BUCKET): 버켓 배열. 각 버켓은 LFH의 size range 안에 있는 특정 크기의 블럭에 해당한다.
- LFH가 enable 되면, _HEAP_LFH_BUCKET 구조체를 가리키게 된다.
- LFH가 enable 되지 않았다면, 각 block size에 해당하는 block이 몇 개나 할당 되었는지 나타내기 위해 사용된다. 이때 마지막 2byte는 항상 값이 1로 고정이다. 마지막 2byte 옆에 있는 2byte는 할당된 횟수값이다.. 해당 크기의 블럭이 할당될 때 마다 횟수값은 0x21씩 증가한다. (사진 참고)
Buckets(_HEAP_LFH_BUCKET)
//0x68 bytes (sizeof)
struct _HEAP_LFH_BUCKET
{
struct _HEAP_LFH_SUBSEGMENT_OWNER State; //0x0
ULONGLONG TotalBlockCount; //0x38
ULONGLONG TotalSubsegmentCount; //0x40
ULONG ReciprocalBlockSize; //0x48
UCHAR Shift; //0x4c
UCHAR ContentionCount; //0x4d
ULONGLONG AffinityMappingLock; //0x50
UCHAR* ProcAffinityMapping; //0x58
struct _HEAP_LFH_AFFINITY_SLOT** AffinitySlots; //0x60
};- bucket과 이와 관련된 구조체는 LFH가 enable 됐을 때만 할당된다
- LFH Allocator는 Size에 맞는 블록을 관리하기 위해 해당 구조체를 사용한다
- State(_HEAP_LFH_SUBSEGMENT_OWNER): Bucket의 status를 나타내기 위해 사용된다. 이 구조체는 LFH의 memory pool을 관리하기 위해 사용된다.
//0x38 bytes (sizeof)
struct _HEAP_LFH_SUBSEGMENT_OWNER
{
UCHAR IsBucket:1; //0x0
UCHAR Spare0:7; //0x0
UCHAR BucketIndex; //0x1
union
{
UCHAR SlotCount; //0x2
UCHAR SlotIndex; //0x2
};
UCHAR Spare1; //0x3
ULONGLONG AvailableSubsegmentCount; //0x8
ULONGLONG Lock; //0x10
struct _LIST_ENTRY AvailableSubsegmentList; //0x18
struct _LIST_ENTRY FullSubsegmentList; //0x28
};- BucketIndex: bucket의 index 값이다.
- AvailableSubsegmentCount: available한 subsegment의 개수이다
- AvailableSubsegmentList(_LIST_ENTRY): bucket 안에서 available한 다음 subsegment를 가리킨다
- FullSubsegmentList(_LIST_ENTRY): bucket 안에서 사용된, 다음 subsegment를 가리킨다
- AffinitySlots(_HEAP_LFH_AFFINITY_SLOT): LFH가 사용하고 있는 pool을 manage하기 위해 사용되는 main 구조체이다. 기본적으로 단 하나만 존재한다
//0x40 bytes (sizeof)
struct _HEAP_LFH_AFFINITY_SLOT
{
struct _HEAP_LFH_SUBSEGMENT_OWNER State; //0x0
struct _HEAP_LFH_FAST_REF ActiveSubsegment; //0x38
};- State(_HEAP_LFH_SUBSEGMENT_OWNER): Bucket 구조체 안의 State와 동일한 구조체이다.
다만, AffinitySlots.State는 주로 subsegment를 관리하기 위해서 사용된다
- ActiveSubsegment(_HEAP_LFH_FAST_REF): 사용되고 있는 subsegment를 가리키는 포인터. 하위 12비트는 subsegmen에서 available 블럭의 개수를 나타낸다.
LFH subsegments(_HEAP_LFH_SUBSEGMENT)
- LFH의 memory pool은 NtHeap의 User 청크와 매우 유사하다. 다만 LFH의 경우 각 청크들은 header나 metadata가 존재하지 않는다.
- memory가 충분하지 않다면 (1st) 먼저, Buckets->State.availableSubsegmentList에서 subsegment를 가져온다. (2nd) Buckets->State.availableSubsegmentList에도 subsegment가 충분하지 않다면 backend allocator에서 새로운 subsegmet를 할당받는다
- (주로) buckets->AffinitySlots에 의해 관리된다
//0x38 bytes (sizeof)
struct _HEAP_LFH_SUBSEGMENT
{
struct _LIST_ENTRY ListEntry; //0x0
union
{
struct _HEAP_LFH_SUBSEGMENT_OWNER* Owner; //0x10
union _HEAP_LFH_SUBSEGMENT_DELAY_FREE DelayFree; //0x10
};
ULONGLONG CommitLock; //0x18
union
{
struct
{
USHORT FreeCount; //0x20
USHORT BlockCount; //0x22
};
volatile SHORT InterlockedShort; //0x20
volatile LONG InterlockedLong; //0x20
};
USHORT FreeHint; //0x24
UCHAR Location; //0x26
UCHAR WitheldBlockCount; //0x27
struct _HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETS BlockOffsets; //0x28
UCHAR CommitUnitShift; //0x2c
UCHAR CommitUnitCount; //0x2d
USHORT CommitStateOffset; //0x2e
ULONGLONG BlockBitmap[1]; //0x30
};• ListEntry(_LIST_ENTRY).Flink: 사용 가능한 다음 LFH subsegment를 가리킨다
ListEntry.Blink: 사용 가능한 이전 LFH subsegment를 가리킨다
• Owner(_HEAP_LFH_SUBSEGMENT_OWNER): subsegment를 manage하는 구조체를 가리키고 있다. == 즉, 해당 subsegment에 부합하는 bucket의 AffnitySlots.State를 가리키고 있다.
• FreeCount: 블럭이 free된 횟수. (*주의* subsegment의 freed block 개수를 나타내는 것이 아니다)
• BlockCount: subsegment에 있는 전체 블럭의 개수
• FreeHint: 가장 최근에 할당된 블럭의 인덱스이다. 만약, 가장 최근에 free된 블럭의 인덱스가 FreeHint보다 크다면, 해당 인덱스로 FreeHint가 업데이트 된다. Allocated Algorithm에서 사용된다.
• Location: subsegment의 위치를 나타낸다. 0: AvailableSegmentList, 1: FullSubsegmentList, 2: subsegment 전체가 곧 back-end로 리턴될 예정임을 나타냄
• BlockOffsets(_HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETS): subsegment의 블럭 size를 나타내고 && subsegment의 첫 블럭이 위치한 곳까지의 offset을 나타내는 데 사용됨
//0x4 bytes (sizeof)
struct _HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETS
{
union
{
struct
{
USHORT BlockSize; //0x0
USHORT FirstBlockOffset; //0x2
};
ULONG EncodedData; //0x0
};
};- BlockSize: subsegment에 있는 브럭의 size
- FirstBlockOffset: 첫 블럭까지의 offset. FirstBlock = subsegment + FirstBlockOffset
• BlockOffsets(_HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETS): 이 값은 encoding 되어있다.
EncodedData = RtlHpHeapGlobals.LfhKey ^ BlockOffsets ^ (subsegment >> 12)
• BlockBitmap: subsegment 안에 있는 block의 usage status를 나타냄. bit 0: is_busy를 나타내는 비트, bit 1: unused bytes를 나타내는 비트
• Block: User에게 return되는 할당된 메모리. 만약 블럭이 해당되는 BlockBitmap의 unused bytes 비트 값이 1이라면, 블럭의 마지막 두 바이트는 unused bytes를 나타내기 위해 사용됨. 만약 1바이트만 존재한다면, 0x8000이라는 값이 저장됨
Memory Allocation Mechanism
Allocate
(1) LfhContext->Config.MaxBlockSize보다 작은 크기의 메모리를 할당할 때, 그 크기에 해당하는 bucket이 LFH enabled 돼있는지 확인한다.
- bucket index = RtlpLfhBucketIndexMap[needbytes+0xf] (RtlpLfhBucketIndexMap == .rdata 세그먼트에 있는 전역 const 변수)
- Check: Buckets[index]->State & 1 == 1
- 만약 LFH가 enable 돼있지 않다면, RtlpHpLfhBucketUpdateStats() 함수를 통해 해당 bucket의 usage 횟수을 update 한다
- buckets[idx]는 enable 되기 전까지는 사용 횟수를 저장한다.
- chunk를 할당 했을 때: 해당 bucket[idx] += 0x210000
- ( (buckets[idx] >> 16) & 0x1f) > 0x10 이거나 (buckets[idx] >> 16) > 0xff00이면 RtlpHpLfhBucketActivate() 함수를 통해 LFH가 활성화된다.
(2) LFH 활성화에 대해..( RtlpHpLfhBucketActivate() 함수 )
- 시작 부분에, RtlpHpHeapExtendContext() 함수를 통해 필요한 bucket의 구조체들을 할당한다. (필요한 구조체: Bucket, owner, affinityslot 등등...)
- 할당 메소드는 _SEGMENT_HEAP->AllocatedBase를 통해 할당된다. ( _SEGMENT_HEAP->AllocatedBase는 주로 _SEGMENT_HEAP 구조체의 끝 부분을 가리키고 있다)
- 할당한 후에, bucket 관련 구조체들은 RtlpHpLfhBucketInitialize() 함수를 통해 initialized 된다.
(3) LFH가 활성화 된 후, LFH는 LFH에 해당하는 크기의 블럭을 할당할 때마다 사용된다.
해당 함수는 nt!RtlpHpLfhSlotAllocate() 이다.
- 그 후, 해당 함수는 ActiveSubsegment에 available 블럭이 있는지 체크한다. check logic은 다음과 같다
-> ActiveSubsegment의 하위 12비트(ActiveSubsegment의 하위 12비트는 available 블럭의 개수를 나타낸다)를 검사하고, available 블럭이 있다면, subsegment에서 블럭을 할당한다.
-> 만약 ActiveSubsegment 값에 available 블럭이 없다면, subsegment에 정말 할당 가능한 블럭이 없는 건지 재차 확한다.
(4) Which block will be taken?
a. 만약 subsegment에 available block이 있다면, NTHeap의 LFH 블럭 동작과 유사하다. 이는 먼저, RtlpLowFragHeapRandomData[x]의 값을 가져간다.
b. 그 후에는 RtlpLowFragHeapRandomData[x+1]의 값을 가져간다. x는 1byte 크기이며 256round 후에 x = rand() % 256이다.
c. RtlpLowFragHeapRandomData는 랜덤한 값들로 채워져있는 uint64[32] 배열이다. 이 랜덤값의 범위는 0x0 ~ 0x7f까지이다.
d. 그 후, subsegment->FreeHint의 값을 통해 Bitmap[index] 값을 가져온다. 이때 index = (2*FreeHint) >> 6이다.
e. Bitmap의 값을 가져온 후, 처음 할당된 블럭의 비트를 본다.
f. 그 후 random index를 더하면, 그 블럭이 바로 할당될 블럭이다. 이때 그 블럭이 이미 할당된 상태라면, next 방향에서 그와 가장 가까운 블럭을 할당한다.
g. 그 후, subsegment의 bitmap과 unused byte를 update 하고난 다음, memory block을 return 해준다.
(자세한 그림 및 단계 자료 p. 67~p. 70 사진 참고)
ㄱ. ActiveSubsegment의 하위 12비트 값이 0이라면, SubSegment->FreeCount가 1보다 큰지 확인한다. 만약 값이 1보다 크다면 subsegment가 아직 할당 가능한 블럭을 갖고있다는 뜻이므로 ActiveSubsegment의 하위 12비트를 update 한다.
ㄴ. subsegment가 할당될 수 있는 블럭을 갖고있지 않다면, Buckets[idx]->State.AvailableSubsegmentList에서 할당한다.
p. 만약 어느 subsegment도 available하지 않다면, back-end allocator로부터 새로운 subsegment를 할당 받은 후, 할당 받은 subsegment를 initialize 한다. (새로운 subsegment 할당 && initialize -> RtlpHpLfhSubsegmentCreate() 함수를 통해)
q. 할당 받은 subsegment의 initialization이 끝나면. AffinitySlots->State.AvailableSubsegmentList에 새롭게 할당받은 subsegment를 추가한다. 그리고, 새롭게 할당된 subsegment->Owner가 AffinitySlots->State를 가리키게 하고, AffinitySlots->ActiveSubsegment에 해당 subsegment를 추가한 뒤, 하위 12bit를 initialize 해준다.
Free
- free를 구현한 핵심적인 함수는 nt!RtlpHpLfhSubsegmentFreeBlock() 함수이다
nt!RtlpHpLfhSubsegmentFreeBlock()
1. 함수의 시작 부분에서, SubSegment.BlockOffsets를 가져와 decode 한다.
2. BlockOffsets 구조체의 BlockSize와 FirstBlockOffset을 가져온다
3. (2)의 정보에 따라 블럭의 index를 계산하고
4. 계산한 index에 해당하는 bitmap을 clear 한 후, FreeCount += 1을 해준다.
5. 만약 FreeCount == BlockCount-1이면, subsegment의 모든 블럭이 free 되었다는 뜻이므로, subsegment는 AvailableSubsegmentList에서 삭제된다.
( FreeCount == subsegment의 블럭이 free된 횟수 && BlockCount == subsegment에 있는 전체 블럭 개수)
5-1. subsegment가 제거될 때, double-linked-list check들이 존재한다
5-2. subsegment는 Backend Allocator에게 release된다.
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
