Windows Cache

오랜만에 책 공부를 해보았습니다;;

예전에 File System Filter Driver에 대해 쫌 공부를 하던 도중 Cache라는 아주 막강한 놈이 있어서 쫌 애를 먹었던 기억이 있었습니다. 그래서 Cache에 관련 내용이 잘 기억이 않나서 .. 정리를 해보았습니다.
================================

Cache는  프로그램이 수행될 때 나타나는 지역성을 이용하여 메모리나 디스크에서 사용되었떤 내용을 특별히 빠르게 접근할 수 있는 곳에 보관하고 관리함으로써 이 내용을 다시 필요로 할 때 보다 빠르게 참조하도록 하는 제어장치입니다.

현재 CPU의 성능을 보면 아주 상상을 초월합니다. 예전엔 메모리보다 사이클 시간이 느려서 메모리 -> CPU 로 이동하는 시간에 대해서 큰 신경을 안썼지만 지금은 메모리 사이클 시간보다 수십배 빠르기 때문에 CPU에서 해당 명령어나 데이터 처리하는 속도도 중요하지만 그런 명령어나 데이터를 처리하기 위해 메모리에서 CPU로 명령어나 데이터를 가져오는 시간 또한 컴퓨터 성능에 엄청난 차이를 발생시킵니다.

그래서 Cache라는 것을 만들게 된 것입니다.

한번 참조된 데이터의 근처 메모리에는 또 다시 참조될 수 있다는 지역성의 특성을 사용해 CPU의 클럭 사이클 만큼 빠르게 접근할 수 있는 Cache Memory를 둔 것입니다.

다들 컴퓨터를 사보셨으니 아실탠데 Cache라는 메모리는 메인 메모리로 불리우는 RAM보다 훨씬 작은 용량을 가지고 있습니다. 아래 그림을 보시겠습니다.

 

그저그런 Intel CPU?!!!!?!?! 입니다...Cache라고 나와서 용량이 12MB이군요. 

4G, 8G, 16G 하는 RAM보다 훨씬 용량이 적은 것을 보실 수 있습니다. 

그렇기 때문에 Cache가 존재한다고 무조건 똑같은 효율을 낼 수 있는 것이 아닌 Cache 메모리에 CPU가 이후에 참조할 쓸모 있는 정보가 얼마나 들어있는냐.. 가 중요한 것입니다.

CPU가 참조하고자 하는 메모리가 Cache에 존재하고 있으면 Cache Hit 이라고 하며,
CPU가 참조하고자 하는 메모리가 Cache에 존재하고 있지 않으면 Cache Miss 라고 합니다.

이 때 메인 메모리로부터 일정한 블록 사이즈의 데이터를 가져와서 Cache에 저장한 후 그 데이터에서 특정 원드 크기의 데이터만 CPU에 전달하게 됩니다.

이 때 메인 메모리로부터 일정한 블록 사이즈를 Cache에 가져올 때 블록 사이즈는 매우 중요합니다.

블록이 크면 클수록 Cache Hit율을 높힐 순 있지만 그만큼 새로운 블록이 들어왔을 때 Cache 데이터 교체 작업이 빈번히 발생되므로 많은 오버헤드가 발생할 수도 있습니다. 

이러한 Cache와 메모리간 어떻게 맵핑이 되어 있는지 알아보겠습니다.
총 3가지 방식
1. Direct Mapping
2. Associative Mapping
3. Set Associative Mapping 
이 있는데 이중에 많은 프로세서들이 채택하고 있는 방식인 Set Associative Mapping 방식에 대해서만 설명하겠습니다.
1,2 번은 스스로 찾아보세요 ^^;
 
Set Associative Mapping 방식도 프로세서가 발전해 가므로서
2-Way Set Associative Mapping, 4-Way Set Associative Mapping...

점점 형태가 바뀌어 가고 있습니다.

Set Associative Mapping 방식의 기본 틀은 만약 64KByte의 Cache를 2-Way면 2개로 4-Way면 4개로 나누게 됩니다.
나눠진 각각의 Cache를 세트라고 하는데 각각의 세트는 Direct Mapping방식 처럼 메인 메모리를 매핑하고 저장된 데이터에 대해서는 Associative Mapping 방식에 의해 비교함으로써 검색되어 집니다.

이제 Cache가 꽉 찼을 경우에 CPU에서 Cache에 없는 메모리를 요구로 할 때 Cache는 현재 있는 데이터의 일부를 새로운 데이터와 교체를 해주어야 합니다.

이렇게 교체를 할 때 어떠한 블록을 빼줘야하는지에 대한 알고리즘이 있는데 대부분 LRU 방식을 많이 사용합니다.
LRU(Least Recently Used) 방식은 메모리와 디스크간 페이징 교체 작업 시에도 나오는 알고리즘 방식입니다.
LRU는 Cache에서 가장 오랫동안 사용되지 않은 블록을 교체하는 방식으로 지역성의 원리에 의하여 일반적으로 자주 참조되지 않는 블록은 가까운 미래에 가장 오랫동안 참조되지 않을 것이라는 사실이 기인한 것입니다.

이번엔 Cache에 쓰는 방법입니다.
우리가 시스템 프로그래밍을 할 때 WriteProcessMemory와 같은 함수를 사용해 특정 메모리에 있는 값을 바꿔버릴 수가 있습니다. 혹은 그냥 프로그램이 실행되면서 mov, lea 이러한 assembly 명령어에 의해서도 메모리에 있는 내용이 바뀌기도 합니다. 이 때 바뀜을 당하는 메모리가 Cache되어 있다면 어떻할 것인가.. 이에 대한 정책이 2개 있습니다.

1. Write Throught
CPU에서 메모리에 쓰기 요청을 할 때마다 Cache의 내용과 메인 메모리의 내용을 같이 바꾸는 형식입니다.
구조는 단순하지만 데이터에 대한 쓰기 요청을 할 때마다 항상 메인 메모리에 접근해야 하므로 Cache에 의한 접근 시간의 개선이 없어지게 됩니다. 하지만 실제로 프로그램에서 메모리 참조 시 쓰기에 대한 작업은 통계적으로 10~15%정도여서 이 방식을 사용해도 성능상 향상은 있습니다. 구조도 단순하기 때문에 많이 사용되어지는 방식입니다.

2. Write Back
CPU에서 메모리에 대한 쓰기 작업 요청 시 Cache에서만 쓰기 작업과 그 변경 사실을 확인할 수 있는 표시를 해 놓고 Cache로부터 해당 블록이 제거될 때 그 블록을 메인 메모리에 복사함으로써 메인 메모리와 Cache의 내용을 동일하게 유지하는 방식입니다. 이 방식은 동일한 블록 내에서 여러번 쓰기를 실행하는 경우 Cache에만 여러 번 쓰기를 하고 메인 메모리에는 한 번만게 되므로 매우 효율적인 방식입니다.

여기서 잠깐 Cache Level을 알아보겠습니다.
L1, L2 Cache라고 하는 것은 들어보셨을 것입니다. 메인 메모리와 CPU 사이에 여러개의 Cache를 둠으로써 병목현상을 제거하는 것입니다. 요새 나오는 CPU들은 L1, L2 Cache는 아에 내장을 하고 있습니다. 그리고 마더보드에 L3, L4 Cache를 두고 있습니다. 하지만 보통 컴퓨터를 사면 L2 Cache정도까지 있는 L3, L4는 좀 더 고성능 컴퓨터에 들어가는거 같습니다.
그리고 L1 -> L2 -> L3 -> L4로 갈수록 Cache Memory용량과 해당 Cache에 접근하는데 걸리는 사이클 시간은 비례하게 증가합니다.

참고로 CPU에는 TLB( Translation Lookaside Buffer ) 라는 버퍼를 가지고 있는데 이것도 Cache와 같다고 생각하시면됩니다. 어떤한 Cache이냐.. CPU에서 메모리에서 접근할 때 가상메모리 -> 물리메모리로 바뀌는 과정에서 세그멘테이션 페이징 작업이 이뤄지게 됩니다. 하지만 매번 주소에 접근할 때마다 이러한 작업이 일어나게 되면 CPU는 본연의 일을 하는데 있어서 방해를 받게 됩니다. 그렇기 때문에 내부에 TLB라는 버퍼를 두고 해당 버퍼에는 가상 주소와 물리 주소를 담아둡니다.
그리고 CPU에서 Page Table을 참조하기전 TLB라는 버퍼를 먼저 뒤져보고 거기에 접근하고자 하는 가상 주소가 있다면 가상 주소를 물리 메모리주소로 변경해주는 작업을 전부 건너뛰로 바로 물리 메모리 주소를 가져오는 것입니다.

자세한 정보 : http://en.wikipedia.org/wiki/Translation_lookaside_buffer

일반적인 TLB일 경우입니다.

• Size: 8 - 4,096 entries
• Hit time: 0.5 - 1 clock cycle
• Miss penalty: 10 - 100 clock cycles
• Miss rate: 0.01 - 1%

이제 디스크에 있는 파일 읽기에서의 Cache사용을 알아보겠습니다.
위에서 설명한 내용은 Cache의 개념과 CPU에서의 Cache내용을 다뤘는데 이러한 Cache의 개념은 CPU에만 있는게 아니라 메모리 관리자에서도 사용됩니다. 아래 그림을 보시겠습니다.

< 출처 : Windows 구조와 원리 - 윈도우즈에서의 캐시 관리 >

1. 애플리케이션이 파일 읽기 관련 API를 사용하여 파일에 대한 읽기 요청을 하게 되면 일단 이 요청에 대하여 Windows의 I/O Manager가 받게 된다.

2. I/O Manager는 해당 파일과 관련된 File System 을 찾은 후 해당 Device Driver에 IRP를 만들어 읽기 요청을 하게 된다.

3. File System에서 받은 읽기 요청이 해당 파일에 대한 최초의 읽기 요청이었을 경우 Cache Manager가 관리하기 위한 Section Object를 만든 후 Cache Manager에게 읽기에 대한 요청을 하게 된다. 

4. Cache Manager는 요청한 파일 영역이 시스템 메모리 영역에 매핑되어졌는지 확인한 후 만약 매핑되어 있지 않다면 읽기를 요청한 영역을 Cache Manager에 의해 관리되어지는 시스템 메모리 영역에 매핑하여 놓는다. 

5. 그후 그 메모리 영역에 대해 읽기가 시도될 것이고 이 영역은 아직 데이터는 들어 있지 않고 매핑만 되어 있는 상태이므로 페이지 폴트가 발생하게 된다.

6. 메모리 관리자는 이 page fault를 처리하기 위해 해당 시스템 메모리와 매핑되어 있는 파일에 대해 Noncached Paging 플래그를 포함한 읽기 IRP를 다시 파일 시스템에 전달하게 된다. File System은 Noncached Paging 플래그를 포함한 읽기 IRP에 대하여 물리적 디스크 드라이버로 데이터 읽기 요청을 하게 된다.

7. 실제 장치로부터 파일에 대한 읽어오기 과정이 이루어진다.

8,9. 디스크로부터 읽기 작업이 완료되면 page fault가 발생한 메모리에 정상적인 데이터가 기록된다.

10. Cache Manager는 읽어들여 온 메모리의 내용을 읽기를 요청한 메모리 부분에 복사하여 놓게 된다.

11,12. 읽기 요청이 완료되고 요청한 애플리케이션으로 읽기 과정을 마무리하게 된다.

이제부터는 실제로 내부 Windows System Cache 실제 내부 구조를 봐보고 직접 WinDbg로 따라가보도록 하겠습니다.

Cache Manager에서는 액세스되어진 파일에 대하여 특정한 시스템 메모리 영역을 View로 지정하고 파일을 매핑하게 되며, 어떤 파일이 어떠한 시스템 메모리에 매핑되어 있는지는 VACB(Virtual Address Control Blocks) 라는 구조체에 저장하여 놓게 됩니다. VACB는 시스템 초기화 시 페이지 아웃이 되지 않는 메모리인 Non-Paged Pool 영역에 배열 형태로 생성되어진 공간에 할당 이 배열의 주소는 Windows의 내부 변수 CcVacbs에 의해 지시되어집니다.

실제로 해당 메모리 부분을 따라가 보도록 하겠습니다.
제가 테스트에 사용한 코드입니다.

현재 C:\Cache_test.txt 파일을 열고 핸들을 얻어와 특정 버퍼로 값을 가져오는 것입니다.
프로세스 명은 Cache.exe 입니다.

처음에 CreateFile만 하고 본 다음 ReadFile까지 하고 또 보도록 하겠습니다.

kd> !process 0 0

**** NT ACTIVE PROCESS DUMP ****

...

PROCESS 81fe73d8  SessionId: 0  Cid: 0518    Peb: 7ffd8000  ParentCid: 066c

    DirBase: 09dc0240  ObjectTable: e1900330  HandleCount:   8.

    Image: Cache.exe

...

kd> .process /i 81fe73d8

You need to continue execution (press 'g' <enter>) for the context

to be switched. When the debugger breaks in again, you will be in

the new process context.

kd> g

Break instruction exception - code 80000003 (first chance)

nt!RtlpBreakWithStatusInstruction:

80529bdc cc              int     3

kd> !process

PROCESS 81fe73d8  SessionId: 0  Cid: 0518    Peb: 7ffd8000  ParentCid: 066c

    DirBase: 09dc0240  ObjectTable: e1900330  HandleCount:   8.

    Image: Cache.exe

    VadRoot 82045130 Vads 22 Clone 0 Private 35. Modified 0. Locked 0.

    DeviceMap e1c12210

    Token                             e1937d48

    ElapsedTime                       00:02:00.828

    UserTime                          00:00:00.093

    KernelTime                        00:00:00.218

    QuotaPoolUsage[PagedPool]         12396

    QuotaPoolUsage[NonPagedPool]      880

    Working Set Sizes (now,min,max)  (168, 50, 345) (672KB, 200KB, 1380KB)

    PeakWorkingSetSize                168

    VirtualSize                       6 Mb

    PeakVirtualSize                   6 Mb

    PageFaultCount                    161

    MemoryPriority                    BACKGROUND

    BasePriority                      8

    CommitCharge                      44

        THREAD 81d0fda8  Cid 0518.070c  Teb: 7ffdf000 Win32Thread: 00000000 WAIT: (WrLpcReply) UserMode Non-Alertable

            81d0ff9c  Semaphore Limit 0x1

kd> !handle

PROCESS 81fe73d8  SessionId: 0  Cid: 0518    Peb: 7ffd8000  ParentCid: 066c

    DirBase: 09dc0240  ObjectTable: e1900330  HandleCount:   8.

    Image: Cache.exe

Handle table at e1e85000 with 8 entries in use

...

001c: Object: 81bfe128  GrantedAccess: 00120089 Entry: e1e85038

Object: 81bfe128  Type: (821eb040) File

    ObjectHeader: 81bfe110 (old version)

        HandleCount: 1  PointerCount: 1

        Directory Object: 00000000  Name: \Cache_test.txt {HarddiskVolume1}

...

kd> dt _FILE_OBJECT 81bfe128

ntdll!_FILE_OBJECT

   +0x000 Type             : 0n5

   +0x002 Size             : 0n112

   +0x004 DeviceObject     : 0x8212d900 _DEVICE_OBJECT

   +0x008 Vpb              : 0x8218b1d8 _VPB

   +0x00c FsContext        : 0xe10a4d90 Void

   +0x010 FsContext2       : 0xe1d5e478 Void

   +0x014 SectionObjectPointer : 0x81d0c18c _SECTION_OBJECT_POINTERS

   +0x018 PrivateCacheMap  : (null) 

   +0x01c FinalStatus      : 0n0

   +0x020 RelatedFileObject : (null) 

   +0x024 LockOperation    : 0 ''

   +0x025 DeletePending    : 0 ''

   +0x026 ReadAccess       : 0x1 ''

   +0x027 WriteAccess      : 0 ''

   +0x028 DeleteAccess     : 0 ''

   +0x029 SharedRead       : 0 ''

   +0x02a SharedWrite      : 0 ''

   +0x02b SharedDelete     : 0 ''

   +0x02c Flags            : 0x40042

   +0x030 FileName         : _UNICODE_STRING "\Cache_test.txt"

   +0x038 CurrentByteOffset : _LARGE_INTEGER 0x0

   +0x040 Waiters          : 0

   +0x044 Busy             : 0

   +0x048 LastLock         : (null) 

   +0x04c Lock             : _KEVENT

   +0x05c Event            : _KEVENT

   +0x06c CompletionContext : (null) 

kd> dt _SECTION_OBJECT_POINTERS 0x81d0c18c

ntdll!_SECTION_OBJECT_POINTERS

   +0x000 DataSectionObject : 0x82060560 Void

   +0x004 SharedCacheMap   : (null) 

   +0x008 ImageSectionObject : (null) 

현재 Cache.exe프로세스가 가지고 있는 핸들 값을 보니 Cache_test.txt가 있습니다.
그리고 해당 Cache_test.txt 의 파일 오브젝트를 봐보았습니다. 
내부에 SECTION_OBJECT_POINTERS 구조체가 있는데 
해당 구조체는 파일 시스템 또는 리다이렉터 드라이버에 의해 생성이 되며 메모리 관리자 그리고 캐시 관리자가 파일 맵핑 그리고 파일 스트림을 위한 캐시 정보를 저장하기 위해 사용됩니다.

내부에는 3개의 멤버 변수가 있는데

그 중에 두번째 멤버 변수가 우리가 관심있게 봐야할 변수입니다.
SharedCacheMap에는 Shared Cache Map 구조체의 포인터가 저장되어 있으며, 이 구조체에는 Cache Manager가 VACB를 관리하기 위한 정보들이 저장되어 있습니다.

하지만 현재 NULL이라고 나오는데 한번도 파일을 읽어들인적이 없기 때문에 NULL로 나오는 것입니다.

이제 ReadFile을 하고 다시 저 부분을 봐보도록 하겠습니다.

kd> dt _SECTION_OBJECT_POINTERS 0x81d0c18c

ntdll!_SECTION_OBJECT_POINTERS

   +0x000 DataSectionObject : 0x82060560 Void

   +0x004 SharedCacheMap   : 0x81bf4360 Void

   +0x008 ImageSectionObject : (null) 

kd> dt _SHARED_CACHE_MAP 0x81bf4360 

nt!_SHARED_CACHE_MAP

   +0x000 NodeTypeCode     : 0n767

   +0x002 NodeByteSize     : 0n304

   +0x004 OpenCount        : 1

   +0x008 FileSize         : _LARGE_INTEGER 0x5a3e2

   +0x010 BcbList          : _LIST_ENTRY [ 0x81bf4370 - 0x81bf4370 ]

   +0x018 SectionSize      : _LARGE_INTEGER 0x80000

   +0x020 ValidDataLength  : _LARGE_INTEGER 0x5a3e2

   +0x028 ValidDataGoal    : _LARGE_INTEGER 0x5a3e2

   +0x030 InitialVacbs     : [4] 0x821a7c98 _VACB

   +0x040 Vacbs            : 0x81bf4390  -> 0x821a7c98 _VACB

   +0x044 FileObject       : 0x81bfe128 _FILE_OBJECT

   +0x048 ActiveVacb       : 0x821a7c98 _VACB

   +0x04c NeedToZero       : (null) 

   +0x050 ActivePage       : 0

   +0x054 NeedToZeroPage   : 0

   +0x058 ActiveVacbSpinLock : 0

   +0x05c VacbActiveCount  : 1

   +0x060 DirtyPages       : 0

   +0x064 SharedCacheMapLinks : _LIST_ENTRY [ 0x80552150 - 0x81cebde4 ]

   +0x06c Flags            : 0

   +0x070 Status           : 0n0

   +0x074 Mbcb             : (null) 

   +0x078 Section          : 0xe1dd5200 Void

   +0x07c CreateEvent      : (null) 

   +0x080 WaitOnActiveCount : (null) 

   +0x084 PagesToWrite     : 0

   +0x088 BeyondLastFlush  : 0n0

   +0x090 Callbacks        : 0xf842f22c _CACHE_MANAGER_CALLBACKS

   +0x094 LazyWriteContext : 0xe10a4d90 Void

   +0x098 PrivateList      : _LIST_ENTRY [ 0x81bf4484 - 0x81bf4484 ]

   +0x0a0 LogHandle        : (null) 

   +0x0a4 FlushToLsnRoutine : (null) 

   +0x0a8 DirtyPageThreshold : 0

   +0x0ac LazyWritePassCount : 0

   +0x0b0 UninitializeEvent : (null) 

   +0x0b4 NeedToZeroVacb   : (null) 

   +0x0b8 BcbSpinLock      : 0

   +0x0bc Reserved         : (null) 

   +0x0c0 Event            : _KEVENT

   +0x0d0 VacbPushLock     : _EX_PUSH_LOCK

   +0x0d8 PrivateCacheMap  : _PRIVATE_CACHE_MAP

kd> dd 0x821a7c98 

821a7c98  d3e80000 81bf4360 00000001 00000000

821a7ca8  821a7600 821a6340 c3e00000 8200e498

821a7cb8  00480000 00000000 821a7930 821a8068

821a7cc8  ce3c0000 81e4c5e0 00000000 00000000

821a7cd8  821a7750 821a67d8 d7d80000 8200e498

821a7ce8  00e80000 00000000 821a7840 821a76d8

821a7cf8  d0640000 81e30cf0 003c0000 00000000

821a7d08  821a81a0 821a7780 dccc0000 8208e628

kd> dt _VACB 0x821a7c98

nt!_VACB

   +0x000 BaseAddress      : 0xd3e80000 Void

   +0x004 SharedCacheMap   : 0x81bf4360 _SHARED_CACHE_MAP

   +0x008 Overlay          : __unnamed

   +0x010 LruList          : _LIST_ENTRY [ 0x821a7600 - 0x821a6340 ]

 

kd> db d3e80000

d3e80000  65 7a 62 65 61 74 2e 74-69 73 74 6f 72 79 2e 63  ezbeat.tistory.c

d3e80010  6f 6d 0d 0a 43 61 63 68-65 20 74 65 73 74 21 21  om..Cache test!!

d3e80020  0d 0a 41 41 41 41 41 41-41 41 41 41 41 41 41 41  ..AAAAAAAAAAAAAA

d3e80030  41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41  AAAAAAAAAAAAAAAA

d3e80040  41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41  AAAAAAAAAAAAAAAA

d3e80050  41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41  AAAAAAAAAAAAAAAA

d3e80060  41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41  AAAAAAAAAAAAAAAA

d3e80070  41 41 41 41 41 41 41 41-41 41 41 41 41 41 41 41  AAAAAAAAAAAAAAAA

SharedCacheMap 변수는 SHARED_CACHE_MAP 라는 구조체 변수이며 내부에 offset +0x30을 보시면 VACB구조체 변수 4개가 배열 형태로 있는 것을 보실 수 있습니다.

첫번째 VACB 구조체를 출력해 BaseAddress로 가보니 ReadFile 해왔던 내용이 캐시에 그대로 담겨 있는 것을 확인할 수 있습니다.