• Kernel Pool Allocator • From 19H1 ~ Now • Segment heap • Note • Segment heap in kernel is very similar to segment heap in userland • Some size and config are difference • We will focus on kernel in this slide • Windows 10 20H2
it will be allocated from BackEnd to FrontEnd first ntoskrnl.exe ExAllocatePool WithTag ntoskrnl.exe ExAllocateHeap Pool LFH RtlpHpLfh ContextAllocate VS Allocation RtlpHpVsContext AllocateInternal Segment Allocation RtlpHpSegAlloc Block Allocation RtlpHpLarge Alloc FrontEnd allocator Backend Allocator
) • Store some Global variables, some Metadata, etc. • NumberOfPool • Number of Pool Node • Default 1 NumberOfPool (8bytes) HeapManager (0x38d0bytes) PoolNode[64] (0x20c0*64) … 0x0 0x38d0 0x3900 0x86900
• Each node will have four Heaps corresponding to different segment heaps, such as Paged/ Nonpaged pool, etc. NumberOfPool (8bytes) HeapManager (0x38d0bytes) PoolNode[64] (0x20c0*64) … 0x0 0x38d0 0x3900 0x86900
in the segment heap • Each Pool will have a _SEGMENT_HEAP structure. When allocating memory, it will decide which HEAP to allocate according to the pool type. • In ExPoolState • These are four segment heap will be created and initialized when the system is turned on • ExPoolState.PoolNode[0].Heap[0-4]
environment handle of segment heap • Signature • Signature of segment heap • It always 0xddeeddee • AllocatedBase • Point to the end of the entire structure of _SEGMENT_HEAP, used to allocate the structure required by LFH Allocator, after allocation, it will point to the end of the allocated structure … … Signature (4bytes) LargeAllocMetadata (10bytes) _SEGMENT_HEAP LargeReservedPages (8bytes) LargeCommittedPages (8bytes) … AllocatedBase (8bytes) SegContexts (0x180bytes) VsContext (0xc0bytes) LfhContext (0x4c0bytes) 0x10 0x48 0x58 0x60 0xe8 0x100 0x280 0x340 0x0 EnvHandle (10bytes) … UserContext (8bytes) … … 0x28
Used for VS Allocator, Segment Allocator • LfhKey • Used for LowFragmentationHeap • Both are 8 byte random value HeapKey (8bytes) LfhKey (8bytes) _RTLP_HP_HEAP_GLOBALS … 0x0 0x8
• Size <= 0x200 and LFH is enabled for this size • The activation timing is very similar to that of NtHeap. It will be activated after 18 consecutive allocations of the same size block
to the Backend allocator used by the LFH … BackendCtx (8bytes) Callbacks (0x28bytes) Config (4bytes) _HEAP_LFH_CONTEXT 0x0 0x8 0x3c … 0x80 … Buckets[129]
pointer 會被 encode 過 • The value of callbacks will be xored by • RtlpHpHeapGlobals.HeapKey • Address of LfhContext • Function pointer … BackendCtx (8bytes) Callbacks (0x28bytes) Config (4bytes) _HEAP_LFH_CONTEXT 0x0 0x8 0x3c … 0x80 … Buckets[129]
to indicate the attributes of the LFH Allocator • It will be used to determine whether the size of allocation is within the scope of LFH allocator … BackendCtx (8bytes) Callbacks (0x28bytes) Config (4bytes) _HEAP_LFH_CONTEXT 0x0 0x8 0x3c … 0x80 … Buckets[129]
• The size of the max block in LFH • WitholdPageCrossingBlocks • Are there any cross-page blocks • DisableRandomization • Whether to disable randomization of LFH MaxBlockSize (2bytes) WitholdPageCrossingBlocks (1bit) _RTL_HP_LFH_CONFIG 0x0 0x2 DisableRandomization (1bit) 0x2
array, each buckets corresponds to blocks in a specific size range • When LFH is enabled, it will point to the _HEAP_LFH_BUCKET structure … BackendCtx (8bytes) Callbacks (0x28bytes) Config (4bytes) _HEAP_LFH_CONTEXT 0x0 0x8 0x3c … 0x80 … Buckets[129]
it is not enabled, it will be used to indicate the number of times the block of the size is allocated. • The last 2 bytes are always 1 • The next 2 byte is the number of allocations • Each allocation will add 0x21 … BackendCtx (8bytes) Callbacks (0x28bytes) Config (4bytes) _HEAP_LFH_CONTEXT 0x0 0x8 0x3c … 0x80 … Buckets[0] … 0x0021 0x0001 Buckets[0]
Used to indicate the status of the Buckets • This structure is used to manage the memory pool of LFH … State (0x38bytes) TotalBlockCount (8bytes) _HEAP_LFH_BUCKET 0x0 0x38 0x40 TotalSubsegmentCount (8bytes) ReciprocalBlockSize (8bytes) … AffinitySlots[] 0x48 0x60
(_LIST_ENTRY) • Point to the next available subsegment in the bucket • FullSubsegmentList (_LIST_ENTRY) • Point to the next used up subsegment in the bucket IsBuckets (1bit) _HEAP_LFH_SUBSEGMENT_OWNER 0x0 0x1 BucketIndex (1byte) … 0x8 0x18 … AvailableSubsegmentCount (8B) AvailableSubsegmentList (8B) FullSubsegmentList (8bytes) 0x20
main structure used to manage the memory pool using by LFH • There is only one by default … State (0x38bytes) TotalBlockCount (8bytes) _HEAP_LFH_BUCKET 0x0 0x38 0x40 TotalSubsegmentCount (8bytes) ReciprocalBlockSize (8bytes) … *AffinitySlots[] 0x48 0x60
(_HEAP_LFH_SUBSEGMENT_O WNER) • Same structure as State in Bucket, but this one is mainly used to manage subsegment State (0x38bytes) ActiveSubsegment (8bytes) _HEAP_LFH_AFFINITY_SLOT 0x0 0x38
(_HEAP_LFH_FAST_REF) • Point to the subsegment being used • The lowest 12 bits indicate how many blocks are available in the subsegment State (0x38bytes) ActiveSubsegment (8bytes) _HEAP_LFH_AFFINITY_SLOT 0x0 0x38
of LFH is very similar in structure to UserBlock in NtHeap, but each block does not have header and other metadata. • Once there is not enough memory, it will take subsegment from Buckets->State.availableSubsegmentList first, if it has no available subsegment , it will allocate from backend allocator for a new subsegment • Mainly managed by buckets->AffinitySlots
• Point to the structure that manages the subsegment • Point back to the AffinitySlots.State of the bucket to which it belongs ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
number of times the block is released • Not the number of freed blocks of the subsegment ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
total number of block in the subsegment • FreeHint • The index of block that the last allocated • If the index of block that the last freed larger than freehint. It will be updated to the index • Used in allocated algorithm ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
• Used to indicate the block size of the subsegment and the offset of the first block in the subsegment ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
size of block in the subsegment • The size is the original size • FirstBlockOffset • The offset of the first block • FirstBlock = subsegment + FirstBlockOffset BlockSize (2bytes) _HEAP_LFH_SUBSEGMENT_ENCODED_OFFSETS 0x0 FirstBlockOffset (2bytes) 0x2
the usage status of the block in the subsegment, and every two bits corresponds to a block • bit 0 : is_busy bit • bit 1 : unused bytes ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
allocated memory return to user. • If the unused byte in the corresponding BlockBitmap is 1, then the last two bytes of the block are used to represent unused bytes • If there is only 1 byte, it will be recorded as 0x8000 ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) _HEAP_LFH_SUBSEGMENT 0x0 0x10 0x20 Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[] Block … 0x22 0x24 0x26 0x28 0x30
LfhContext- >Config.MaxBlockSize, it will first check whether the corresponding bucket is LFH enabled • bucket index = RtlpLfhBucketIndexMap[needbytes+0xf] • Check : Buckets[index]->State & 1 == 1 (disable） • If it’s not enabled, it will update(RtlpHpLfhBucketUpdateStats) the usage times corresponding bucket.
LfhContext->Config.MaxBlockSize, it will first check whether the corresponding bucket is LFH enabled • The buckets[idx] will record the number of times when it is not enabled • When we allocated a chunk : the corresponding buckets[idx] += 0x210000 • Once (buckets[idx] >> 16) & 0x1f> 0x10 or (buckets[idx] >> 16)> 0xff00 it will enable LFH (RtlpHpLfhBucketActivate)
At the beginning, it will allocate the required structure of the bucket (RtlpHpHeapExtendContext) • Bucket, owner, affinityslot … • The allocation method is directly allocated from _SEGMENG_HEAP- >AllocatedBase (usually pointing to the end of the segment heap structure) • After allocation, the bucket related structure will be initialized by RtlpHpLfhBucketInitialize
will be used as long as the block of the size is allocated • Implementation function is nt!RtlpHpLfhSlotAllocate • Next, it will check if there is an available block in ActiveSubsegment • The check is to take the lowest 12 bits of ActiveSubsegment (representing the number of blocks that can be allocated), and if there are available block, it will allocate from the subsegment • If not, it will confirm whether the subsegment really has no block that can be allocated
the case that the subsegment have available blocks, it will be similar to the LFH block in NtHeap, it would take the value of RtlpLowFragHeapRandomData[x] first. • Next time it will retrieve the value from RtlpLowFragHeapRandomData[x+1] • x is 1 byte ，x = rand() % 256 after 256 rounds • RtlpLowFragHeapRandomData is a 256-bytes array filled with random value • The range of random value is 0x0 - 0x7f Low FragmentationHeap
of Bitmap[Index] according to the value of subsegment->FreeHint • Index = (2*freehint) >> 6 • After retrieving the value of the Bitmap, it will look for the bit corresponding first allocated block • Then adding the random index, it is the block to be allocated
is 0 • If it is not zero, it will take the next nearest block • If it is zero, it will set the corresponding BlockBitmap, and confirm whether there is unused byte _HEAP_LFH_SUBSEGMENT ListEntry (10bytes) Owner (8bytes) FreeCount (2bytes) BlockCount (2bytes) FreeHint (2bytes) Location (1byte) … BlockOffsets (4bytes) … … BlockBitmap[0] Block Block … BlockBitmap[1]
of the ActiveSubsegment is 0, it would check whether subsegment->FreeCount is greater than 1 • if the value is greater than 1 (indicating that the subsegment still have allocatable blocks), it will update the lowest 12 bit at the ActiveSubsegment • If the subsegment has no block that can be allocated, it will be filled from Buckets[idx]->State.AvailableSubsegmentList
would allocate a new subsegment from the back-end allocator and initialize the subsegment (RtlpHpLfhSubsegmentCreate) • It will initialize BlockOffsets, BitMap, etc. • After initialization, it will add to AffinitySlots->State.AvailableSubsegmentList, and point subsegment->Owner back to AffinitySlots->State • AffinitySlots->ActiveSubsegment is also set to this subsegment and the lowest 12 bit is initialized
• At the beginning, it will take subsegment.BlockOffsets first and decode it • According to the content of BlockOffsets, it will retrieve block size and firstblockoffset • According to the previous info, the index of block can be calculated • Clear the corresponding bitmap and set FreeCount = FreeCount + 1
that all the blocks of the subsegment are released, the subsegment will be removed from the AvaliableSubsegmentList • There will also be double linked list checks when removing here • It will release subsegment to backend Allocator
memory allocator • In front of the chunk in VS allocation, there are some related metadata that record information of the chunk • _HEAP_VS_CHUNK_HEADER • _HEAP_VS_CHUNK_FREE_HEADER • Similar to back-end allocator in NtHeap
of chunk • The value is right shift by 4 bits • UnasfePrevSize • The size of previous chunk • The value is right shift by 4 bits User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) EncodedSegmentPageOffset (1byte) Inused UnusedBytes (1bit) SkipDuringWalk (1bit) Spare (22 bit)
the chunk is allocated • The value is 1, if it is allocated User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) EncodedSegmentPageOffset (1byte) Inused UnusedBytes (1bit) SkipDuringWalk (1bit) Spare (22 bit)
index of pages of the chunk in the VS subsegment • It is used to find the VS subsegment • It will also be encoded. User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) EncodedSegmentPageOffset (1byte) Inused UnusedBytes (1bit) SkipDuringWalk (1bit) Spare (22 bit)
many pages of memory need to be committed when the chunk is allocated User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) Freed Node (18byte)
in the same as allocated chunk • Node (_RTL_BALANCED_NODE) • Node of rbtree and Freed chunk will be stored in a rbtree structure User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) Freed Node (18byte)
• Left/Right • The left and right subtrees of the Node • ParentValue • Parent node of this node User Data MemoryCost (2byte) UnsafeSize (2byte) UnsafePrevSize (2byte) Allocated (1byte) Padding (1byte) Freed Left (8byte) Right (8byte) ParentValue (8byte)
for lock • LockType (_RTLP_HP_LOCK_TYPE) • The type of Lock can be divided into • Paged/NonPaged/TypeMax LockType VsContext Lock FreeChunkTree SubsegmentList … DelayFreeContext … BackendCtx Callbacks Config 0x0 0x8 0x10 0x20 0x40 0x80 0x88 0xb0
after free a chunk, the chunk will be placed in the FreeChunkTree of the heap, and the chunk will be inserted in the FreeChunkTree according to the size. • If the size of chunk is larger than the node, it will be placed in right subtree otherwise, will be placed in left subtree • If there is no larger chunk than the chunk, the right subtree is NULL, and the other side is also • There will be a node check when taken out of the tree
to the root of the rbtree • Encoded • Indicates whether the root has been encoded (default disable) • About encode : • EncodedRoot = Root ^ FreeChunkTree Encoded Root FreeChunkTree 0x0 0x8
free (default in kernel but disable in usermode) and size of chunk < 0x1000, after Free a chunk, it will not be free immediately, but will be added to a singly linked list called DelayFreeContext, until the number of chunks in the linked list exceeds 0x20, the chunks in the linked list will be freed at one time • Next pointer will be put at the beginning of user data • FILO • If you want to check whether delay free is enable, you can check VsContext- >Config
number of chunks in the Linked list • NextEntry • Point to next chunk • At this time chunk is still Allocated Depth (2byte) NextEntry (8byte) Sequence (6byte) DelayFreeContext Listhead
pool of VS allocation • Once there is not enough for allocation, it will allocated from the backend allocator for a new subsegment • Each subsegment will be linked in a linked list
The value would be encoded • Flink/Blink will xor with following value • Address of ListEntry • Address of next/prev subsegment … ListEntry CommitBitmap CommitLock Size (2byte) VS Subsegment Signature (15bit) FullCommit (1bit) 0x0 0x10 0x18 0x20 0x22 Chunk header 0x30 Chunk header Chunk header
Indicates the status of page commit in the subsegment, and the page starts from the beginning of the subsegment • CommitLock • Lock used when Commit … ListEntry CommitBitmap CommitLock Size (2byte) VS Subsegment Signature (15bit) FullCommit (1bit) 0x0 0x10 0x18 0x20 0x22 Chunk header 0x30 Chunk header Chunk header
Size of VS subsegment • The value is right shift by 4 bits • Signature • Signature for verification, make sure that the subsegment is found when free … ListEntry CommitBitmap CommitLock Size (2byte) VS Subsegment Signature (15bit) FullCommit (1bit) 0x0 0x10 0x18 0x20 0x22 Chunk header 0x30 Chunk header Chunk header
VS subsegment header is the memory pool of VS Allocator. At the beginning, the memory pool of subsegment is a large chunk • Split when allocated • Coalesce to-be-freed block with neighbors … ListEntry CommitBitmap CommitLock Size (2byte) VS Subsegment Signature (15bit) FullCommit (1bit) 0x0 0x10 0x18 0x20 0x22 Chunk header 0x30 Chunk header Chunk header
to the Backend allocator (_HEAP_SEG_CONTEXT) structure used by the VS Allocator LockType VsContext Lock FreeChunkTree SubsegmentList … DelayFreeContext … BackendCtx Callbacks Config 0x0 0x8 0x10 0x20 0x40 0x80 0x88 0xb0
Function pointer will be encoded • Callbacks will xor with following value • RtlpHpHeapGlobals.HeapKey • VsContext address • Function pointer LockType VsContext Lock FreeChunkTree SubsegmentList … DelayFreeContext … BackendCtx Callbacks Config 0x0 0x8 0x10 0x20 0x40 0x80 0x88 0xb0
Used to represent the attributes of the Vs Allocator • PageAlignLargeAllocs (default 0 in user mode) • FullDecommit • EnableDelayFree (default 0 in usermode) LockType VsContext Lock FreeChunkTree SubsegmentList … DelayFreeContext … BackendCtx Callbacks Config 0x0 0x8 0x10 0x20 0x40 0x80 0x88 0xb0
nt!RtlpHpVsContextAllocateInternal • It will calculate the required chunk size at the beginning • Then it will find a suitable chunk from FreeChunkTree in VsContext • Start searching from the root, when the required chunk is larger than the node, continue searching from the right subtree until it is found or is NULL
can be allocated is not found, a subsegment will be allocated and the subsegment will be added to the VsContext, and then start searching from FreeChunkTree again • It will create a large chunk when it initialize the subsegment. • RtlpHpVsSubsegmentCreate • Request memory (RtlpHpSegVsAllocate) from backend, and create a new subsegment, the minimum size is (0x10000)
to VsContext • It will determinate how to split the subsegment according to whether to enable PageAlignLargeAllocs • If PageAlignLargeAllocs is set, the subsegment will be split into two chunks, one is the first chunk behind the subsegment structure, and the second is the page alignment, the user data of the chunk is aligned, and both chunks are added to FreeChunkTree • If not, the entire subsegment will be treated as a large chunk and added to FreeChunkTree
of chunk size larger then request size, the chunk will be split, and the remaining chunks will be re-added to FreeChunkTree • RtlpHpVsChunkSplit • It will remove the chunk out of FreeChunkTree, and split the chunk, and re-added re-added FreeChunkTree as a new Freed chunk. • This will also be split according to whether the page alignment is or not. If the size of the chunk to be split exceeds 1 page, it split remainder chunk into two pieces according to the page • If request size < chunk size, unused byte will be recorded at the last 2 bytes of chunk
nt!RtlpHpVsContextFree • The signature and Allocated bytes of the subsegment will be verified at first • Subsegment->Size ^ Subsegment->Signature ^ 0x2BED == 0 • BSOD if verification fails
if the number of chunks in VsContext- >DelayFreeContext is greater than 0x20 • VsContext->DelayFreeContext.Depth > 0x20 • If it is less than 0x20, the chunk will be inserted at the beginning of the linked list and then return • VsContext->DelayFreeContext.NextEntry
the chunks in the linked list will be freed one by one • When it free a chunk, EncodedSegmentPageOffset will be used to find the VS subsegment of the chunk, and verify the Allocated byte and segment signature
whether the front and next chunks can be merged. If VsContext->Config.flag has enable PageAlignLargeAllocs, then one more chunk will be check. The merged chunk will be moved out of FreeChunkTree first. There is a tree structure check. After the merge, update prev_size and Size • RtlpHpVsChunkCoalesce • After merging, if address of chunk+0x20 is the beginning of page, the chunk will be page aligned and split into two pieces
(0x420) Parent Left Right Chunk header (0x210) Parent Left Right Chunk header (0x510) Parent Ｐ Ｌ Ｒ R->Parent->Right == R L->Parent->Left == L P->Left->Parent == P P->Right->Parent == P
the merged chunk is exactly equal to the size of the subsegment, the entire subsegment will be moved out of the linked list. • There is also a double linked list check here and it will release the subsegment to the backend allocator • If it is not equal, it will calculate MemoryCost and Segmentpageoffset of the chunk and then encode it. • Finally, look for a suitable position in FreeChunkTree to insert
• Both LFH and VS Allocator will allocate additional 0x10 byte (64bit) • It is used to store the Pool Header. Pool Header is used for Pool Allocator before 19H1 . • Now it is basically used in a few cases such as CacheAligned, PoolQuota and PoolTrack • The header contains • Size • PreviousSize • Pool type • PoolIndex
in the CacheAligned case, indicating the offset between the previous Pool header and the header • Pool Index • Useless in Segment Heap PoolIndex (1byte) PreviousSize (1byte) PoolType (1byte) BlockSize (1byte) PoolTag (4 bytes) ProcessBilled (8 bytes) 0x0 0x1 0x2 0x3 0x4 0x8 Pool header
size of the block • The value is right shift by 4 bits • PoolType • The pooltype of the block PoolIndex (1byte) PreviousSize (1byte) PoolType (1byte) BlockSize (1byte) PoolTag (4 bytes) ProcessBilled (8 bytes) 0x0 0x1 0x2 0x3 0x4 0x8 Pool header
tag string is filled in when the block is allocated • When you use ExAllocatePoolWithTag, you can specify the pooltag • ProcessBilled • Used for PoolQuota and CacheAligned PoolIndex (1byte) PreviousSize (1byte) PoolType (1byte) BlockSize (1byte) PoolTag (4 bytes) ProcessBilled (8 bytes) 0x0 0x1 0x2 0x3 0x4 0x8 Pool header
<0xfe0. • It will not be freed immediately after free. The block will be added to a Dynamic Lookaside • Depending on the size of the block, it will be added to different linked lists • The size is taken from Pool Header • When it allocate, it will first take block from Dynamic Lookaside first • It will enter the normal allocation if it is not found
is used to indicate which buckets have enable lookaside • BucketCount • The total number of buckets in lookaside EnabledBucketBitmap (8bytes) BucketCount (4bytes) ActiveBucketCount (4bytes) Buckets[64] (0x40bytes) 0x0 0x8 0xc 0x40 _RTL_DYNAMIC_LOOKASIDE
of buckets with enable lookaside • Buckets (_RTL_LOOKASIDE) • Used to manage the structure of different sizes of lookaside, which is where the lookaside are EnabledBucketBitmap (8bytes) BucketCount (4bytes) ActiveBucketCount (4bytes) Buckets[64] (0x40bytes) 0x0 0x8 0xc 0x40 _RTL_DYNAMIC_LOOKASIDE
structure of the head of the Singly linked list contains the length of the linked list, and the linked list itself, which is common in windows kernel • Depth • The number of chunks that can be stored in the bucket ListHead (16bytes) Depth (2bytes) … 0x0 0x10 _RTL_LOOKASIDE
nodes in the linked list • NextEntry • Point to next node • In the Dynamic Lookaside, it points to the Userdata of the freed chunk, behind the pool header Depth (2bytes) … NextEntry (8 byte) 0x0 0x8 _SLIST_HEADER
The difference between the two is that the block units are different. • 0x20000 < Size <= 0x7f000 • 0x1000 as the unit of block • 0x7f000 < Size <= 0x7f0000 • 0x10000 as the unit of block • Both unit are called page here
<= 0x7f000, the allocation unit of Segment Allocation • For example, if you allocate 0x1450 bytes, it would allocate 2 page • 0x7f000 < Size <= 0x7f0000 • It will use 0x10000 as the allocation unit • In the following slides, I will use 0x1000 as an example Page Page Page Page 0x1000 0x10000 Pages
multiple pages • The memory block allocated by Segment Allocatior • As shown in the figure, the block is composed of 3 pages Page Page Page Page 0x1000 Block
segment allocation • Once there is no available page segment, a new page segment will be allocated from the system(MmAllocatePoolMemory) , but only the required structure will be allocated at the beginning • Each page segment will be inserted into a double linked list
Point to the next page segment in the Linked list • Blink • Point to the previous page segment in the Linked list … ListEntry Signature _HEAP_PAGE_SEGMENT … … DescArray[256] 0x0 0x10 0x40 Pages 0x2000 0x10000
the page segment is used to verify the page segment • Signature will xor with following value • Address of page segment • Address of Segcontext • RtlpHpHeapGlobals • 0xA2E64EADA2E64EAD … ListEntry Signature _HEAP_PAGE_SEGMENT … … DescArray[256] 0x0 0x10 0x40 Pages 0x2000 0xA2E64EADA2E64EAD
• Each element corresponds to each page one by one • Pages • Ｍemory pool of segment allocator Segment Allocation … ListEntry Signature _HEAP_PAGE_SEGMENT … … DescArray[256] 0x0 0x10 0x40 Pages 0x2000 0xA2E64EADA2E64EAD
page • Indicates the status (Allocated or Freed) and information of each page in the page segment (whether the page is the beginning of a block, size of block, etc.) • It can be divided into allocated and freed • The page range descriptor in the freed state will be stored in FreePageRanges which is a rbtree structure
pages committed in the block • Only used in block header • UniCount • The size of Block • Value is page count Segment Allocation EncodedCommittedPageCount (2bytes) _HEAP_DESCRIPTOR_KEY 0x0 0xA2E64EADA2E64EAD LargePageCost (1bytes) 0x2 UnitCount (1bytes) 0x3
header • The UnitCount field will be called UnitOffset • Indicates the offset of the page in the block Segment Allocation TreeSignature UnusedBytes Allocated and not header … RangeFlag (1byte) 0x0 0x4 0xA2E64EADA2E64EAD 0x18 CommittedPageCount (1byte) 0x19 … 0x1c … … UnitOffset (1byte) 0x1f
a page descriptor that block size is smaller than its. • Right • Point to a page descriptor that block size is greater than its. • ParentValue • Point to parent node • The lowest 1 bit will determine whether to encode Parent Segment Allocation TreeNode Freed RangeFlag (1byte) 0x0 0xA2E64EADA2E64EAD 0x18 CommittedPageCount (1byte) 0x19 … Left Right ParentValue 0x8 0x10 Key (4 bytes)
header • The UnitCount field will be called UnitOffset • Indicates the offset of the page in the block Segment Allocation TreeNode (0x18 bytes) Freed and not header RangeFlag (1byte) 0x0 0xA2E64EADA2E64EAD 0x18 CommittedPageCount (1byte) 0x19 … … 0x1c … UnitOffset (1byte) 0x1f
the Segment allocation • Used to manage the memory allocated by segment allocator, and record all the information and structure of segment allocator in the heap • There are two SegContexts in each Heap • Size <= 0x7f000 • 0x7f000 < Size < 0x7f0000
the size of a page in the SegContext • The size of page unit is (0x1 << PagePerUnitShift)*0x1000 • If the value is zero • Page unit is 0x1000 • FirstDescriptorIndex • The index of the first Page Descriptor in the SegContext Segment Allocation SegmentMask (8bytes) UnitShift (1bytes) SegContext PagesPerUnitShift (1byte) FirstDescriptorIndex (1byte) 0x0 0x8 0xA2E64EADA2E64EAD 0x9 … 0xa VsContext (8bytes) 0x18 LfhContext (8bytes) … Heap (8bytes) 0x38 0x20 SegmentListHead (10bytes) … 0x48 … FreePageRanges (10bytes) 0x60
heap to which it belongs • SegmentListHead (_LIST_ENTRY) • Point to the page segment in the segment allocator • The linked list is a double linked list with integrity check Segment Allocation SegmentMask (8bytes) UnitShift (1bytes) SegContext PagesPerUnitShift (1byte) FirstDescriptorIndex (1byte) 0x0 0x8 0xA2E64EADA2E64EAD 0x9 … 0xa VsContext (8bytes) 0x18 LfhContext (8bytes) … Heap (8bytes) 0x38 0x20 SegmentListHead (10bytes) … 0x48 … FreePageRanges (10bytes) 0x60
releasing a block, the page descriptor of the block will be inserted into the FreePageRanges of the SegContext according to the size • If the block size is greater than the node, the page descriptor will be inserted into the right subtree, otherwise will be will be inserted into left subtree. • If there is no greater than the page descriptor, the right subtree is NULL and the other side is also • There will be a node check when the node is taken out of the tree
to the root of the rbtree • Encoded • Indicates whether the root has been encoded (default disable) • About encode • EncodedRoot = Root ^ FreeChunkTree Segment Allocation 0xA2E64EADA2E64EAD Encoded Root FreePageRanges 0x0 0x8
page as the unit to allocate, and divided into • Size <= 0x7f000 • Page uses 0x1000 bytes as a unit • 0x7f000 < Size < 0x7f0000 • Page uses 0x10000 bytes as a unit
page as the unit to allocate • For example, if it allocate 0x1337 bytes, segment allocation will allocate 0x2000, which is 2 page units, and the extra memory 0x2000-0x1337 will be recorded in unused byte
• It will use RtlpHpSegPageRangeAllocate to get freed page descriptor or create a new page descriptor • First, it will search from FreePageRanges. • Start searching from the root, when the required block is larger than the node, continue searching from the right subtree until it is found or is NULL
is found, a new page segment will be allocated and the first page descriptor of the page segment will be initialized, and then this page descriptor will be used for allocated. The page segment will be inserted into the SegmentListHead. • In fact, it only allocated the memory required for the page segment and page descriptor structure, and the block part is not allocated at first • RtlpHpSegSegmentAllocate : Allocate page segment • RtlpHpSegSegmentInitialize : Initialize the first page descriptor • RtlpHpSegHeapAddSegment : insert into SegmentListHead
or created a page descriptor, the page descriptor will be removed from FreePageRanges • When the required number of pages is smaller than the block, splitting will be done. • The page descriptor corresponding to the remainder block will be inserted into FreePageRanges
it will check whether all pages in the block are committed • It will add up the CommittedPageCount of all page descriptors in the block • If the block needs committed, it will commit memory to the specified VA • RtlpHpSegMgrCommit ->RtlpHpAllocVA->MmAllocatePoolMemory • Then update the CommittedPagecount of all page descriptors corresponding to the block
verify whether the page segment where the ptr is located is legal • RtlpHpSegDescriptorValidate • Verify: Page segment->signature • 0xA2E64EADA2E64EAD == Page segment^SegContext^ RtlpHpHeapGlobals^signature • Verify that the page descriptor of the page where the ptr is located is Allocated • Double Free check
the free pointer is at the beginning of block • If free pointer is not at the beginning of the block, it will check the RangeFlag of the Page descriptor to determine whether to use VS Allocator or Lfh Allocator to release the memory • If free pointer is not at the beginning of the block, it means that the free pointer is managed by segment allocation, and RtlpHpSegPageRangeShrink will be used
page descriptor correspond to block will be cleared, and it will check whether the previous and following blocks are Freed. If it is Freed, it will be merged • RtlpHpSegPageRangeCoalesce • The way to find the previous block is to check whether the page descriptor of previous page is at the beginning of the block. If it is not the beginning, it will use the UnitOffset of the page descriptor of previous page to calculate the page descriptor of the previous block. • The following is calculated using the UnitCount of the current page descriptor • Determine whether the RangeFlag of the Page descriptor at the beginning of the block is Allocated • It use page descriptor of the block at the beginning to check whether the block is allocated.
Free • Remove the Page descriptor of the previous block from FreePageRanges • Clear the first bit of the RangeFlag of the Page descriptor of the Block which we want to free • Update the UnitCount of the Page descriptor of the previous block • Update UnitOffset of the last page descriptor of Block after merge
Free • Remove the page descriptor of following block from FreePageRanges • Clear the first bit of the RangeFlag of the Page descriptor of the following block • Update the UnitCount of the Page descriptor of the block which we want to free • Update UnitOffset of the last page descriptor of Block after merge
to other Allocations, it is much simpler. In fact, it almost directly allocate for a large block of memory from the system and stores it with rbtree. • Release is also removed from rbtree and returned to the system directly.
to manage the allocated memory by Large Allocation • It is also a rbree structure, and the address of allocated memory is used as KEY … … Dfa … Signature (4bytes) LargeAllocMetadata (10bytes) _SEGMENT_HEAP … LargeReservedPages (8bytes) LargeCommittedPages (8bytes) … AllocatedBase (8bytes) SegContexts (0x180bytes) … VsContext (0xc0bytes) LfhContext (0x4c0bytes) 0x10 0x48 0x58 0x60 0xe8 0x100 0x280 0x340 EnvHandle (10bytes) 0x0
• Point to a node whose VirtualAddress is smaller than the node • Right • Point to a Node whose VirtualAddress is greater than the Node • ParentValue is pointed to parent node • The lowest 1 bit will determine whether to encode Parent node VirtualAddress (8 bytes) … _HEAP_LARGE_ALLOC_DATA 0x0 0x18 AllocatedPages (52 bit) 0x20:12 Left Right ParentValue
on page as the unit. • Main implementation function is nt!RtlpHpMetadataAlloc • At the beginning, it will allocate memory for storing Large block Metadata (_HEAP_LARGE_ALLOC_DATA) • RtlpHpMetadataHeapCtxGet & RtlpHpMetadataHeapStart • It will determine which Heap to allocate from according to the value of Segment heap->EnvHandle • ExPoolState->HeapManager.MetadataHeaps[idx]
on page as the unit. • Main implementation function is nt!RtlpHpMetadataAlloc • Next, it will use RtlpHpAllocVA to allocated memory, and then store the VirtualAddress in Metadata • Finally, insert the Metadtata into Segment heap->LargeAllocMetadata
(RtlpHpLargeFree) • First find the node correspond to the free ptr from Segment heap- >LargeAllocMetadata, and remove the node • Use RtlpHpFreeVA to release memory • Finally release the memory storing Metadata (RtlpHpMetadataFree) of the released memory
yuukit
masatoto
de9uch1
ryou0634
asonas
monochromegane
sosk
0325
upura
takase
chemical_tree
addyosmani
speakerdeck
thoeni
jonrohan
csswizardry
jlugia
lara
gr2m
moore
iamctodd
mojombo
pedronauck
![Memory Allocator in kernel • _SEGMENT_HEAP • ExPoolState.PoolNode[0].Heap[0] -> NonPagedPool](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_17.jpg){kind=link}
![Low FragmentationHeap • Get an index • Searchwidth = RtlpSearchWidth[Bucketindex];](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_66.jpg){kind=link}
![Segment Allocation … ListEntry Signature _HEAP_PAGE_SEGMENT … … DescArray[0x02] 0x0](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_148.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT 0x0 0x40 Block 0x2000 DescArray[0x02] DescArray[0x03]](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_168.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_175.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_176.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_177.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_178.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_179.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_180.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_181.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_182.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_183.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_193.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_194.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_195.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_196.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_197.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_198.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_199.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_200.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_201.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_202.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_203.jpg){kind=link}
![Segment Allocation … _HEAP_PAGE_SEGMENT DescArray[0x02] DescArray[0x03] … Page 2 Page](https://files.speakerdeck.com/presentations/c2b43337944f44b7a1a4a4396d14ec13/slide_204.jpg){kind=link}
