본 글은 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
III-1. Pool Header(_POOL_HEADER)
- 'Allocation Size <= 0xfe0(4064byte)'라면 LFH와 VS 모두 0x10byte 크기의 Pool Header를 할당한다.
- 19H1 버전 이후로 Pool Header는 Pool Allocator에 의해 사용된다.
- 현재는 CacheAligned, PoolQuota, PoolTrack과 같은 몇몇 경우에만 사용된다.
- Pool Header는 Size, Previous Size, Pool type. PoolIndex와 같은 정보를 담고있다
//0x10 bytes (sizeof)
struct _POOL_HEADER
{
union
{
struct
{
USHORT PreviousSize:8; //0x0
USHORT PoolIndex:8; //0x0
USHORT BlockSize:8; //0x2
USHORT PoolType:8; //0x2
};
ULONG Ulong1; //0x0
};
ULONG PoolTag; //0x4
union
{
struct _EPROCESS* ProcessBilled; //0x8
struct
{
USHORT AllocatorBackTraceIndex; //0x8
USHORT PoolTagHash; //0xa
};
};
};• PreviousSize: CacheAligned일 때 사용된다. 'Previous Pool Header <--> Header' 사이 offset을 나타낸다
• PoolIndex: Segment Heap에서는 사용되지 않는다.
• PoolType: 해당 블럭의 pool type을 나타낸다
• PoolTag: 블럭이 할당될 때 tag string이 들어가게 된다. ExAllocatePoolWithTag()를 사용하면 PoolTag를 지정해 줄 수 있다.
• ProcessBilled: PoolQuota와 CacheAligned를 위해 사용된다.
III-2. Dynamic Lookaside(_RTL_DYNAMIC_LOOKASIDE)
- '0x201 < Size < 0xfe0'이라면, 해당 블럭이 free 되었을 때 바로 free 되는 것이 아니라, Dynamic Lookaside에 추가된다.
- 블럭의 size에 따라, 서로 다른 linked list에 추가된다. 이때 블럭의 size는 Pool Header에서 가져온다.
- 블럭을 할당할 때, 가장 먼저 Dynamic Lookaside에서 블럭을 가져온다. 만약 Dynamic Lookaside에서 마땅한 블럭을 찾지 못한다면, normal allocation이 수행된다.
- _SEGMENT_HEAP->UserContext(_RTL_DYNAMIC_LOOKASIDE)가 Dynamic Lookaside의 core 구조체이다.
//0x1040 bytes (sizeof)
struct _RTL_DYNAMIC_LOOKASIDE
{
ULONGLONG EnabledBucketBitmap; //0x0
ULONG BucketCount; //0x8
ULONG ActiveBucketCount; //0xc
struct _RTL_LOOKASIDE Buckets[64]; //0x40
};• EnabledBucketBitmap: 어느 bucket이 enable lookaside를 갖고 있는지 나타내기 위해 사용되는 bitmap
• BucketCount: lookaside 안에 있는 버켓의 전체 개수
• ActiveBucketCount: Lookaside가 enable된 bucket의 개수
• Buckets(_RTL_LOOKASIDE): 서로 다른 크기의 lookaside 구조체들을 관리하기 위해 사용된다.
//0x40 bytes (sizeof)
struct _RTL_LOOKASIDE
{
union _SLIST_HEADER ListHead; //0x0
USHORT Depth; //0x10
USHORT MaximumDepth; //0x12
ULONG TotalAllocates; //0x14
ULONG AllocateMisses; //0x18
ULONG TotalFrees; //0x1c
ULONG FreeMisses; //0x20
ULONG LastTotalAllocates; //0x24
ULONG LastAllocateMisses; //0x28
ULONG LastTotalFrees; //0x2c
};• ListHead(_SLIST_HEADER): Singly-linked list의 헤더의 구조체. Linked list의 길이, linked list 자기 자신을 포함하고 있다.
• Depth: Bucket 안에 저장될 수 있는 chunk의 개수
//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 안에 들어있는 노드의 개수
• NextEntry: 다음 node를 가리키는 포인터. Dynamic Lookaside에서는 Pool Header 바로 뒤에 위치한 User data의 시작 부분을 가리킨다.
IV. Backend Allocation
Segment Allocation
Size(in the kernel)
- Size가 page의 배수일 때: Size <= 0x7f0000(8,128KB)
- Size가 page의 배수가 아닐 때: 0x20000(128KB) < Size <= 0x7f0000(8,128KB)
- 0x20000(128KB) < Size <= 0x7f000(508KB)일 때, block의 기본 단위는 0x1000이다.
- 0x7f000(508KB) < Size <= 0x7f0000(8,128KB)일 때, block의 기본 단위는 0x10000이다.
- 두 기본 단위(0x1000 and 0x10000) 모두 page라고 부른다
데이터 구조체
- Page: Segment Allocation의 할당 기본 단위. (1) Size <= 0x7f000(508KB)라면 page의 기본 단위 == 0x1000.
(2) 0x7f000(508KB) < Size <= 0x7f0000(8,128KB)라면 page의 기본 단위는 0x10000이다. 예를 들어, 0x1450byte를 allocate 한다면 페이지 2개가 할당된다.
- Block(Chunk): 하나 또는 여러 개의 page들로 이루어져 있다. Segment Allocator로부터 할당 받은 memory block을 칭한다.
- Page Segment(_HEAP_PAGE_SEGMENT): (1) Segment Allocation의 memory pool. (2) 할당 가능한 Page Segment
가 존재하지 않는다면, 새로운 Page Segment가 System으로부터 MmAllocatePoolMemory() 함수를 통해 할당된다. Beginning에는 필요한 구조체만이 할당된다. (3) 각 Page Segment들은 doubly-linked list 안에 삽입된다
//0x2000 bytes (sizeof)
union _HEAP_PAGE_SEGMENT
{
struct
{
struct _LIST_ENTRY ListEntry; //0x0
ULONGLONG Signature; //0x10
};
struct
{
union _HEAP_SEGMENT_MGR_COMMIT_STATE* SegmentCommitState; //0x18
UCHAR UnusedWatermark; //0x20
};
struct _HEAP_PAGE_RANGE_DESCRIPTOR DescArray[256]; //0x0
};• ListEntry(_LIST_ENTRY): (1) Flink: Linked list 안에 있는 다음(next) Page Segment를 가리키는 포인터이다.
(2) Blink: Linked list 안에 있는 이전(previous) Page Segment를 가리키는 포인터이다.
• Signature: Page segment를 verify하기 위해 사용되는 시그니쳐. Signature 값은 (1) Page segment의 주소, (2) SegContext의 주소, (3) RtlpHpHeapGlobals, (4) 0xA2E64EADA2E64EAD 와 XOR 된다.
• DescArray(_HEAP_PAGE_RANGE_DESCRIPTOR): Page range descriptor 배열. 배열의 각 원소는 각각의 page에 1대1로 대응된다.
• Pages: Segment Allocator의 memory pool
- Page range descriptor(_HEAP_PAGE_RANGE_DESCRIPTOR): Page를 위한 descriptor이다. Page Segment 안에 있는 각 페이지의 상태(Allocated or Free'd) && Page Segment 안에 있는 각 페이지에 대한 정보(page가 block 안의 첫 page인지, block의 size, 등등...)를 담고 있다.
Page range descriptor는 Allocated 또는 Free'd로 나뉠 수 있는데, free'd 상태인 page range descriptor는 rbtree 구조체인 FreePageRanges에 저장되게 된다.
//0x20 bytes (sizeof)
struct _HEAP_PAGE_RANGE_DESCRIPTOR
{
union
{
struct _RTL_BALANCED_NODE TreeNode; //0x0
struct
{
ULONG TreeSignature; //0x0
ULONG UnusedBytes; //0x4
USHORT ExtraPresent:1; //0x8
USHORT Spare0:15; //0x8
};
};
volatile UCHAR RangeFlags; //0x18
UCHAR CommittedPageCount; //0x19
USHORT Spare; //0x1a
union
{
struct _HEAP_DESCRIPTOR_KEY Key; //0x1c
struct
{
UCHAR Align[3]; //0x1c
union
{
UCHAR UnitOffset; //0x1f
UCHAR UnitSize; //0x1f
};
};
};
};• TreeSignature: Page range descriptor의 signature. 이 값은 항상 0xccddccdd이다. Block의 시작 부분에만 있다.
• UnusedBytes: Allocated된 block에 있는 사용되지 않는 byte들의 크기를 나타낸다.
• RangeFlags: Page의 상태를 나타내기 위해 쓰인다.
(1) bit 1: Allocated bit
(2) bit 2: Block header bit
(3) bit 3: Commited. 'LFH: RangeFlag & 0xc = 0x8', 'VS: RangeFlag & 0xc = 0xc'
• CommittedPageCount: 대응되는 page 안에 committed된 pages의 개수를 나타낸다.
• Key(_HEAP_DESCRIPTOR_KEY): Page descriptor에 대응되는 page의 size && committed pages의 개수를 저장하고 있다.
//0x4 bytes (sizeof)
struct _HEAP_DESCRIPTOR_KEY
{
union
{
ULONG Key; //0x0
struct
{
ULONG EncodedCommittedPageCount:16; //0x0
ULONG LargePageCost:8; //0x0
ULONG UnitCount:8; //0x0
};
};
};
- EncodedCommittedPageCount: '~EncodedCommittedPageCount'는 block 안에서 committed된 pages의 개수이다. Block Header에서만 사용된다.
- UnitCount: Block 안에 있는 Page의 개수를 저장하고 있다. 이를 통해서 Block의 크기를 구할 수 있다.
• UnitOffset: 만약 대응되는 page가 block header 페이지가 아니라면, Key의 UnitCount 필드가 UnitOffset으로 불린다. Block 안에서 해당 페이지의 offset 값이다.
• TreeNode(_RTL_BALANCED_NODE): FreePageRanges 안에 있는 node이다.
• TreeNode(_RTL_BALANCED_NODE)
//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
};
};- Left: 해당 Block의 size보다 작은 size를 가진 block을 가리키는 포인터
- Right: 해당 Block의 size보다 큰 size를 가진 block을 가리키는 포인터
- ParentValue: Parent node를 가리키는 포인터. LSB는 Parent를 encode 할 건지를 나타낸다
SegContexts(_HEAP_SEG_CONTEXT)
- Segment allocation의 core 구조체
- Segment allocator에 의해 할당된 메모리를 관리하고 && Heap에 존재하는 Segment allocator의 모든 '정보와 구조체'들을 기록해둔다.
- 각 Heap에는 두 SegContext가 존재한다.
(1) Size <= 0x7f000(508KB)
(2) 0x7f000(508KB) < Size <= 0x7f0000(8,128KB)
//0xc0 bytes (sizeof)
struct _HEAP_SEG_CONTEXT
{
ULONGLONG SegmentMask; //0x0
UCHAR UnitShift; //0x8
UCHAR PagesPerUnitShift; //0x9
UCHAR FirstDescriptorIndex; //0xa
UCHAR CachedCommitSoftShift; //0xb
UCHAR CachedCommitHighShift; //0xc
union
{
UCHAR LargePagePolicy:3; //0xd
UCHAR FullDecommit:1; //0xd
UCHAR ReleaseEmptySegments:1; //0xd
UCHAR AllFlags; //0xd
} Flags; //0xd
ULONG MaxAllocationSize; //0x10
SHORT OlpStatsOffset; //0x14
SHORT MemStatsOffset; //0x16
VOID* LfhContext; //0x18
VOID* VsContext; //0x20
struct RTL_HP_ENV_HANDLE EnvHandle; //0x28
VOID* Heap; //0x38
ULONGLONG SegmentLock; //0x40
struct _LIST_ENTRY SegmentListHead; //0x48
ULONGLONG SegmentCount; //0x58
struct _RTL_RB_TREE FreePageRanges; //0x60
ULONGLONG FreeSegmentListLock; //0x70
struct _SINGLE_LIST_ENTRY FreeSegmentList[2]; //0x78
};• SegmentMask: Page Segment를 찾기 위해 사용되는 mask. Page Segment = block_ptr & SegmentMask
• UnitShift: Page descriptor의 index를 계산하기 위해 사용된다. Index = block_ptr >> UnitShift
• PagesPerUnitShift: "0x1 << PagesPerUnitShift"는 SegContext 안에 있는 page의 크기를 나타낸다.
- Page 기본 단위 Size = (0x1 << PagesPerUnitShift) ^ 0x1000 (-> 이 값이 0이면 Page 기본 단위 크기는 0x1000이다)
• FirstDescriptorIndex: SegContext 안에 있는 첫 번째 Page Descriptor의 index
• LfhContext(_HEAP_LFH_CONTEXT): Segment heap 안에 있는 LFH allocator를 가리키는 포인터
• VsContext(_HEAP_VS_CONTEXT): Segment heap 안에 있는 VS allocator를 가리키는 포인터
• Heap(_SEGMENT_HEAP): 해당 SegContext가 속해있는 Segment heap을 가리키는 포인터
• SegmentListHead(_LIST_ENTRY): Segment Allocator 안에 있는 Page Segment를 가리키는 포인터. 이 Linked list는 integrity check가 존재하는 doubly-linked list이다
FreePageRanges(_RTL_RB_TREE)
- Segment Allocation에서는 block을 release 하면, block의 page descriptor가 SegContext의 FreePageRanges로 Size에 맞게 삽입된다. 만약 block size가 node보다 크다면 right subtree에, node보다 작다면 left subtree에 삽입된다.
- 만약 해당 block보다 큰 size의 node가 존재하지 않는다면 page descriptor의 right subtree와 left subtree는 NULL이다.
- FreePageRanges에서 node를 꺼내올 때 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 되어있는지 나타낸다. 기본값은 disabled이다.
(Encoding 되어있다면, EncodedRoot = Root ^ FreeChunkTree이다)
Memory Allocation Mechanism
Allocation
- Allocation은 페이지를 기준으로 이루어진다.
(1) Size <= 7f000(508KB): Page는 0x1000byte를 기본 단위로 사용한다
(2) 0x7f000(508KB) < Size <= 0x7f0000(8128KB): Page는 0x10000byte를 기본 단위로 사용한다
(e.g.) 예를 들어, 만약 0x1337byte를 할당하면, Segment Allocator는 먼저 0x2000(기본 페이지 2개 단위)을 할당한다. 그 후 잉여 메모리(0x2000-0x1337)은 unused byte에 기록된다.
- Main implementation 함수는 nt!RtlpHpSegAlloc()이다. nt!RtlpHpSegAlloc()은 free'd page descriptor를 가져오기 위해 RtlpHpSegPageRangeAllocate() 함수를 이용하거나 새로운 page descriptor를 생성한다.
(1) 먼저, FreePageRanges를 탐색한다. root에서부터 요청 받은 block의 size에 따라 right subtree나 left subtree를 타고 내려가며 알맞은 node를 탐색한다.
(2) 만약 알맞은 page descriptor를 찾지 못하면, 새로운 page segment를 할당 받고, page segment의 첫 번째 page descriptor를 initialize 시킨다. 그 후, 할당 할 때 할당 받은 이 page descriptor를 사용한다. 이때 page segment는 SegmentListHead에 삽입된다.
(2-a) 이때, 사실은 page segment에게 필요한 memory와 page descriptor 구조체만 할당했을 뿐, 할당 받은 처음에 block 부분은 할당되지 않는다.
- RtlpHpSegSegmentAllocate(): page segment를 할당한다.
- RtlpHpSegSegmentInitialize(): 첫 page descriptor를 initialize한다.
- RtlpHpSegHeapAddSegment(): SegmentListHead에 삽입한다.
(3) 만약 FreePageRanges에서 알맞은 page descriptor를 찾았거나, 새로운 descriptor를 생성했다면, page descriptor는 FreePageRanges에서 제거된다. 이때 만약 요청 받은 page 개수가 block보다 작다면, 이를 split한다. split 하고 남은 block의 page descriptor는 다시 FreePageRanges로 삽입된다.
↓ ↓ Segment Allocation 그림 ↓ ↓
(a) 3개의 page가 하나의 block으로 묶여있는 모습이다. Block Header page descriptor는 UnitSize로 0x3을 갖고 있고, 나머지 두 page descriptor는 UnitSize 대신 UnitOffset에 Block Header로부터 자기 페이지까지의 offset 값을 갖고있다.
또한, Block Header page descriptor를 제외한 나머지 두 page descriptor에서는 TreeNode가 쓰이지 않는다.
(c) Block Header page descriptor의 TreeNode를 NULL로 설정함으로서, 해당 node를 FreePageRanges tree에서 제거한다.
(d) 할당 요청받은 0x1337은 두 페이지 크기이므로, 세 페이지로 구성돼있던 block을 2개 페이지와 1개 페이지로 split한다. 그 후 header page descriptor의 UnitSize값을 split된 것에 맞게 0x2로 수정해주고, Block에서 떨어져나간 page descriptor의 RangeFlag를 block header bit를 나타내는 0x2로 수정해준다. 그 후, 떨어져나간 page descriptor의 UnitOffset을 0x0으로 수정해준다
(e) 떨어져나간 page descriptor의 사용되지 않던 TreeNode 부분을 update하여 FreePageRanges tree에 해당 node를 삽입한다.
(f) 할당된 블럭의 page descriptor를 update 해준다. 먼저 block header page descriptor의 TreeNode 부분을 Allocated 되었을 때 쓰이는 TreeSignature로 바꿔준다. 그 후, block header page descriptor의 RangeFlag를 Allocated(0x1) | Header bit(0x2) 해준 값인 0x3으로 update 해준다. 그리고 block header page descriptor의 UnitSize를 split 된 것에 맞게 0x2로 update 해준다.
그리고 마지막으로, Allocated된 block의 header page가 아닌 page descriptor의 RangeFlag도 Allocated(0x1)로 update 해준다.
(4) Page descriptor를 세팅해준 뒤, block 안에 있는 page들이 모두 'committed' 되었는지 체크한다.
(4-a) 이때, Block 안에 있는 모든 page descriptor의 CommittedPageCount를 증가시킨다
(4-b) 만약 block이 committed 돼야 한다면, Virtual Address에 맞게 memory를 commit 한다.
(4-c) 이때, RtlpHpSegMgrCommit() -> RtlpHpAllocVA() -> MmAllocatePoolMemory()순으로 호출한다
(4-d) block이 Committed 됐으면, 해당 block 안에 있는 모든 page descriptor의 CommittedPageCount를 update 한다.
(5) 마지막으로, 해당 page descriptor에 해당하는 block을 return 해주며 allocate 과정이 끝이 난다.
(5-a) Block = (Page descriptor & SegmentMask) + ( (Page descriptor의 인덱스) << SegContext->UnitShift )이다.
Free
(1) 우선 ptr가 위치한 page segment가 올바른지 RtlpHpSegDescriptorValidate() 함수를 통해 체크한다.
(1-a) Check: Page segment->signature: 0xA2E64EADA2E64EAD == Page segment^SegContext^ RtlpHpHeapGlobals^signature
(1-b) Page의 page descriptor가 Allocated 돼있는 게 맞는지 확인한다.(Double Free check)
(2) Page descriptor = page_segment + 0x20 * ( (free pointer - page segment) >> SegContext->UnitShift )
(3) _HEAP_SEG_CONTEXT = page segment ^ page segment->Signature ^ 0xA2E64EaDA2E64EAD ^ RtlpHpHeapGlobals.HeapKey
(4) 그 후, free pointer가 block의 시작 부분에 위치하는지 본다.
(4-a) 만약 free pointer가 block의 시작 부분에 있지 않다면, memory를 release 할 때 VS Allocator를 사용할지 Lfh Allocator를 사용할지 결정하기 위해 Page descriptor의 RangeFlag를 체크한다.
(4-b) 만약 free pointer가 block의 시작 부분에 있지 않다면, 이는 free pointer가 segment allocation에 의해 관리된다는 뜻이므로 RtlpHpSegPageRangeShrink() 함수가 사용된다.
(5) Block에 대응되는 page descriptor의 Allocated bit를 clear 해준다. 그리고 previous block과 next block이 free'd 상태인지 확인하고, free'd 상태라면 그 block과 병합한다. ( RtlpHpSegPageRangeCoalesce() 함수)
(5-a) previous block을 찾기 위해 previous 페이지의 page descriptor가 block의 header인지 확인한다. 만약 아니라면, previous 페이지의 page descriptor의 UnitOffset을 이용하여 previous block의 page descriptor를 계산해낸다.
(5-b) next block은 현재 page descriptor의 UnitCount를 이용하여 계산해낸다.
(5-c) block의 첫 부분에 있는 page descriptor의 RangeFlag를 통해 block이 allocated 돼있는지 결정한다.
(6) 만약 previous block이 free'd 상태라면
(6-a) FreePageRanges에서 previous block의 page descriptor 제거
(6-b) 우리가 free 하려고 하는 현재 block의 page descriptor의 RangeFlag에서 first bit(Allocated bit) clear
(6-c) previous block의 page descriptor에서 UnitCount update
(6-d) 병합 이후 block의 마지막 page에 대응하는 page descriptor에서 UnitOffset update
(7) 만약 next block도 free'd 상태라면
(7-a) next block을 FreePageRanges에서 제거
(7-b) next block의 page descriptor의 RangeFlag에서 first bit(Allocated bit) clear
(7-c) 우리가 free 하려고 하는 block의 page descriptor에서 UnitCount update
(7-d) 병합 이후 block의 마지막 page에 해당하는 page descriptor의 UnitOffset update
(8) 마지막으로, 병합 이후 block의 size에 맞게 FreePageRanges에 삽입한다.
↓ ↓ Block Free and Merge with Previous Block 그림 ↓ ↓
(처음) 0x4000에 있는 Block을 Free 하려한다
(a) Free 하려는 block이 위치한 Page segment의 Signature를 check 한다
(b) Free 하려는 block의 page descriptor의 RangeFlag에서 Allocated bit가 set 돼있는지 check한다.(Double Free check)
(c) Previous page의 RangeFlage의 Allocated bit를 확인해, previous page가 free'd 상태인지 확인한다.
(d) Previous page descriptor의 UnitOffset을 통해 Previous block header page descriptor의 위치를 구한다
(e) Previous block의 header page descriptor의 RangeFlag의 Allocated bit를 확인하여 previous block이 free'd 상태인지 확인한다
(f), (g) 해당 경우엔 Free 하려는 block의 previous block이 free'd 상태이므로, previous block을 FreePageRanges tree에서 제거한다.
(h) Previous block header page descriptor의 UnitSize를 병합한 것에 맞게 update 해준다
(i) Free 하려는 block의 page descriptor에서 RangeFlag의 Allocated bit를 clear 해줘, Free'd 상태로 바꾼다
(j) 마지막 단계이다. 병합된 block의 header page descriptor에 TreeNode를 추가해줌으로서, 병함된 block을 FreePageRanges tree에 삽입해준다.
Large Block Allocation
- Size > 0x7f0000(8,128KB)
- 해당 Allocation은 관리를 위해 오직 rbtree만을 사용한다. Large block은 사실 system으로부터 직접 할당 받아 rbtree에 저장한다.
- Release 과정도 rbtree에서 해당 large block을 제거한 뒤, system으로 직접 반환된다
데이터 구조체
_SEGMENT_HEAP.LargeAllocMetadata(_RTL_RB_TREE)
//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
};• LargeAllocMetadata(_RTL_RB_TREE): Large Allocation을 통해 Allocated된 memory를 관리하기 위해 사용된다. rbtree 구조체이며, allocated된 memory의 주소가 KEY로 사용된다
• LargeReservedPages: Large Block Allocation을 위해 reserved된 page의 개수
• LargeCommittedPages: Large Allocation을 위해 committed된 page의 개수
_HEAP_LARGE_ALLOC_DATA
//0x28 bytes (sizeof)
struct _HEAP_LARGE_ALLOC_DATA
{
struct _RTL_BALANCED_NODE TreeNode; //0x0
union
{
ULONGLONG VirtualAddress; //0x18
ULONGLONG UnusedBytes:16; //0x18
};
ULONGLONG ExtraPresent:1; //0x20
ULONGLONG GuardPageCount:1; //0x20
ULONGLONG GuardPageAlignment:6; //0x20
ULONGLONG Spare:4; //0x20
ULONGLONG AllocatedPages:52; //0x20
};• TreeNode(_RTL_BALANCED_NODE)
- Left: 해당 node보다 VirtualAddress가 작은 node를 가리키는 포인터
- Right: 해당 node보다 VirtualAddress가 큰 node를 가리키는 포인터
- ParentValue: parent node를 가리키는 포인터. LSB는 Parent node를 encode 할지를 결정한다.
• VirtualAddress: Large block의 주소를 나타내는 값이다. Lowest 16bit는 Unused bytes를 표시하기 위해 사용된다.
• AllocatedPages: Allocate된 page의 개수를 나타낸다
Memory Allocation Mechanism
Allocate
- Allocation은 page를 기본 단위로 사용하여, page를 기준으로 이루어진다
- Main implementation 함수는 nt!RtlpHpMetadataAlloc()이다.
(1) 시작 부분에, Large block Metadata(_HEAP_LARGE_ALLOC_DATA)를 저장하기 위한 memory를 할당받는다.
이는 RtlpHpMetadataHeapCtxGet() 함수와 RtlpHpMetadataHeapStart() 함수를 통해 이뤄진다.
(a) Segment heap->EnvHandle 값에 따라 어느 heap에서 메모리를 할당할 건지 결정한다.
(b) ExPoolState->HeapManager.MetadataHeaps[idx]
(2) 그 후 RtlpHpAllocVA()를 사용하여 memory를 할당 받고, VirtualAddress를 Metadata에 저장한다.
(3) 마지막으로, Metadata를 Segment heap->LargeAllocMetadata에 삽입한다.
Free
- Main implementation 함수는 RtlpHpLargeFree()이다.
(1) 첫 번째로, Segment heap->LargeAllocMetadata에서 free ptr에 대응하는 node를 찾는다. 그 후 찾은 node를 제거한다.
(2) 그 후, memory를 release하기 위해 RtlpHpFreeVA()를 사용한다.
(3) 마지막으로, RtlpHpMetadataFree()를 사용하여, release된 memory의 metadata를 저장하고 있던 memory를 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
'Windows Internals > Kernel Pool Internals' 카테고리의 다른 글
| Windows Kernel Pool Internals Part 2(VS) (0) | 2024.01.31 |
|---|---|
| Windows Kernel Pool Internals Part 1 (Segment Heap 개요, 주요 구조체, LFH) (0) | 2024.01.30 |
