Allocate Kernel Memory, Free

1. Windows Kernel Pool

windows 버전이 바뀔 때마다 memory design NUMA를 더 최적화시켜 memory 관리의 효율이 올라가게 된다. 그 결과로 Kernel의 KNODE 구조체에 의해 정의된 node라고 하는 작은 단위로 memory가 관리된다.

System을 시작하게 되면 memory 관리자는 Pool Descriptor에 의해 관리되는 Memory Pool을 형성하게 된다.

  • Paged Pool: 실제 memory에 상주하지 않고 paging file에 기록될 수도 있고 반대로 paging file에서 실제 memory로 load될 수 있는 가상 memory이다.
  • Non-paged Pool: 항상 실제 memory에 있어야 하며 찾고자 하는 data가 memory상에 없을 때 page fault를 반환하게 되는데 이를 처리할 수 없을 때 접근 가능한 정보들을 저장한다.

 

2. Pool Descriptor

Heap과 마찬가지로 할당한 memory에 대한 관리가 필요하다. Pool memory를 할당하게 되면 고유한 Descriptor가 하나씩 할당이 되는데 사용 중인 page 및 pool 사용과 관련된 기타 정보들을 나타내 준다.

kd> dt _POOL_DESCRIPTOR
nt!_POOL_DESCRIPTOR
 +0x000 PoolType : _POOL_TYPE
 +0x004 PagedLock : _KGUARDED_MUTEX
 +0x004 NonPagedLock : Uint4B
 +0x040 RunningAllocs : Int4B
 +0x044 RunningDeAllocs : Int4B
 +0x048 TotalBigPages : Int4B
 +0x04c ThreadsProcessingDeferrals : Int4B
 +0x050 TotalBytes : Uint4B
 +0x080 PoolIndex : Uint4B
 +0x0c0 TotalPages : Int4B
 +0x100 PendingFrees : Ptr32 Ptr32 Void
 +0x104 PendingFreeDepth : Int4B
 +0x140 ListHeads : [512] _LIST_ENTRY

Delayed freelist는 free되기를 기다리는 Pool chunk의 단일 연결 목록이다. 그리고 ListHeads는 동일한 크기의 Free pool chunk의 Double linked list이고 해제되어 언제든지 할당 가능한 chunk가 있다.

 

3. ListHeads (Free list)

ListHeads 목은 8bytes 단위로 정렬하고 최대 4080bytes 할당에 사용된다. Pool Descriptor의 구조를 보면 마지막에 ListHeads가 있는데 이는 free가 된 chunk가 LIST_ENTRY 구조로 배열이 들어가게 된다.

그리고 free chunk의 POOL_HEADER 뒤쪽에 LIST_ENTRY에 대한 데이터가 담기게 된다.

kd> !pool 85198988
Pool page 85198988 region is Nonpaged pool
...
 85198780 size: 40 previous size: 200 (Allocated) Even (Protected)
 851987c0 size: 40 previous size: 40 (Allocated) Even (Protected)
 85198800 size: 40 previous size: 40 (Allocated) Even (Protected)
 85198840 size: 40 previous size: 40 (Allocated) Even (Protected)
 85198880 size: 40 previous size: 40 (Allocated) Even (Protected)
 851988c0 size: 40 previous size: 40 (Allocated) Even (Protected)
 85198900 size: 40 previous size: 40 (Allocated) Even (Protected)
 85198940 size: 40 previous size: 40 (Allocated) Even (Protected)
*85198980 size: 200 previous size: 40 (Free) *Even

특정 Object가 할당이 되어있는 Pool 상태이다.

kd> dc 85198980
85198980 00400008 ee657645 85198588 8519ad88 ..@.Eve.........
85198990 00000000 00000000 00000000 00000000 ................
...

windbg로 POOL_HEADER의 주소로부터 살펴보면 위와 같이 Flink 값과 Blink에 대한 값이 담겨져 있다.

8519ad80 size: 200 previous size: 40 (Free) *Even
 Pooltag Even : Event objects
8519af80 size: 40 previous size: 200 (Allocated) Even (Protected)
8519afc0 size: 40 previous size: 40 (Allocated) Even (Protected)

kd> dd 8519ad80
8519ad80 00400008 ee657645 85198988 85199188
8519ad90 00000000 00000000 00000000 00000000
8519ada0 00000000 00080001 00000000 00000000

붉은 색 주소에 대한 정보를 보면 free chunk라는 것을 알 수 있고 Flink data에 0x85198988 주소의 chunk가 나타나 있다.

 

4. Lookaside List

kernel은 작은 크기의 pool chunk들의 빠른 할당 및 해제를 위해서 singly-linked lookaside list를 사용한다. Lookaside list는 system이 처음 동작할 경우 크기별로 block을 나누고 할당 요청이 들어오면 block을 제거해 반환해준다. 할당할 block이 부족할 경우 memory pool에서 할당해주게 된다.

CPU 캐싱의 효율을 높이기 위해서 lookaside 목록은 KPRCB의 프로세서 별로 정의된다.

kd> !prcb
PRCB for Processor 0 at 82f2fd20:
Current IRQL -- 0
Threads-- Current 84f4d690 Next 00000000 Idle 82f39380
Processor Index 0 Number (0, 0) GroupSetMember 1
Interrupt Count -- 00064bef
Times -- Dpc 0000018c Interrupt 000000e9 
 Kernel 00050e78 User 00001172 
kd> dt _KPRCB 82f2fd20
ntdll!_KPRCB
 +0x000 MinorVersion : 1
 +0x002 MajorVersion : 1
 +0x004 CurrentThread : 0x84f4d690 _KTHREAD
 +0x008 NextThread : (null) 
 +0x00c IdleThread : 0x82f39380 _KTHREAD
 +0x010 LegacyNumber : 0 ''
 +0x011 NestingLevel : 0 ''
 +0x012 BuildType : 0
 +0x014 CpuType : 6 ''
 +0x015 CpuID : 1 ''
 +0x016 CpuStep : 0x5e03
...
 +0x598 PrcbPad22 : [2] 0
 +0x5a0 PPLookasideList : [16] _PP_LOOKASIDE_LIST
 +0x620 PPNPagedLookasideList : [32] _GENERAL_LOOKASIDE_POOL
 +0xf20 PPPagedLookasideList : [32] _GENERAL_LOOKASIDE_POOL

Non-paged 할당 함수 PPNPagedLookasideList, paged 할당 함수 PPPagedLookasideList 부분을 보면 각 32개의 고유한 목록이 있고 이는 GENERAL_LOOKASIDE_POOL 구조체에 의해서 정의된다.

Lookaside list는 system이 처음 동작할 경우 크기별로 block을 나누고 할당 요청이 들어오면 하나의block을 제거해 memory를 반환한다. block이 부족하면 memory pool에서 할당해주게 된다.

 

5. Large Pool

Pool Descriptor Listheads는 page의 크기 (4080bytes)보다 작은 chunk를 유지 및 관리한다.

Page 크기 이상의 Pool Memory 할당은 nt!ExpAllocateBigPool()에 의해서 처리된다.

 

6. Allocation Algorithm

PVOID ExAllocatePoolWithTag( POOL_TYPE PoolType, SIZE_T NumberOfBytes, ULONG Tag)
// call pool page allocator if size is above 4080 bytes

if (NumberOfBytes > 0xff0) { 
// call nt!ExpAllocateBigPool
}

// attempt to use lookaside lists

if (PoolType & PagedPool) {
 if (PoolType & SessionPool && BlockSize <= 0x19) {
 // try the session paged lookaside list
 // return on success
 }

else if (BlockSize <= 0x20) { 
 // try the per-processor paged lookaside list
 // return on success
 }
 // lock paged pool descriptor (round robin or local node)
}
else { // NonPagedPool
 if (BlockSize <= 0x20) 
 // try the per-processor non-paged lookaside list
 // return on success
 }
 // lock non-paged pool descriptor (local node)
}

// attempt to use listheads lists
for(n = BlockSize – 1; n < 512; n++){
 if(ListHeads[n].Flink == &ListHeads[n]){ // empty
 continue;
 } // try nex block size

// safe unlink ListHeads[n].Flink
// split if larger than needed
// return chunk
}

ExAllocatePoolWithTag()는 Pool memory를 할당하기 위해 사용하는 함수이다. 할당 요청한 size가 0xff0보다 클 경우 Large Pool Memory를 할당해준다.

그리고 Non-paged Pool 할당시에는 Listheads lists의 chunk를 우선적으로 사용하게 된다.

 

7. Free Algorithm

ExFreePoolWithTag()함수는 할당해준 Pool memory를 해제시켜줄 때 사용하는 함수이다. 해제된 chunk는 단편화를 줄이기 위해서 인접한 다른 free chunk들과 합병된다.

VOID ExFreePoolWithTag(PVOID Entry, ULONG Tag){
 if(PAGE_ALIGNED(Entry)){
 // call nt!MiFreePoolPages
 // return on success
 }

if (Entry -> BlockSize != NextEntry -> PreviousSize) {
 BugCheckEx(BAD_POOL_HEADER);
 }

if (Entry -> PoolType & SessionPagedPool && Entry -> BlockSize <= 0x19){
 // put in session pool lookaside list
 // return on success
 }

else if (Entry -> BlockSize <= 0x20){
 if (Entry -> PoolType & PagedPool){
 // put in per-processor paged lookaside list
 // return on success
 }
 else{ // Non-paged pool
 // put in per-processor non-paged lookaside list
 // return on success
 }
 }
}

if(ExpPoolFlags & DELAY_FREE) { // 0x200
 if (PendingFreeDepth >= 0x20){
 // call nt!ExDeferredFreePool
 }
 if (IS_FREE(PreviousEntry)){
 // safe unlink previous entry
 // merge previous with current chunk
 }
 if (IS_FULL_PAGE(Entry)){
 //call nt!MiFreePoolPages
 }
 else{
 //insert Entry to ListHeads[BlockSize – 1]
 }
}

Free된 chunk의 entry를 따라서 전, 후에 있는 chunk들의 상태를 확인하고 만약 free가 되었을 시 그 chunk와 합병하게 된다.

 

문서: Kenel memory Allocation, Free