[CSAPP] 9.7 Case Study: The Intel Core i7 / Linux Memory System

9.7 Case Study: The Intel Core i7 / Linux Memory System

• Linux 실행하는 Intel Core i7에 대해서 case study하면서 virtual memory mechanisms에 대해서 보자.
• Haswell microarchitecture는 64bit virtual, physical address space를 허용한다.
• 하지만 현재 Core i7은 48bit virtual address space와 52bit physical address space를 지원한다.
• 그리고 compatibility mode는 32bit virtual, physical address space를 지원한다.
• 아래 그림은 Core i7 memory system을 보여준다.



• 가장 바깥에 점선으로 processor package (chip)을 표현했다.
• processor package에는 4개의 core가 있다.
• 그리고 큰 L3 cache와 DDR3 memory controller는 모든 core가 공유한다.

• 각 core는 TLB의 계층 구조를 가진다. 이 계층 구조는 data와 instruction caches의 계층 구조다.
• 그리고 QuickPath 기술 기반의 fast point-to-point links의 세트를 가지고 있다.
• 이것은 다른 core와 외부 IO bridge와 직접 통신하기 위해서 있는 것이다.
• TLB들은 가상으로 주소가 지정되고 (=가상 주소 가진다는 의미 같다.) 4 way set associative다.

• L1~L3 caches는 물리 주소를 가지고 있고 block size는 64 바이트이다.
• L1~L2 caches는 8 way associative이고 L3는 16 way set associative이다.
• page size는 시작할 때 4KB 또는 4MB로 구성될 수 있다.
• Linux는 4KB page를 사용한다.

9.7.1 Core i7 Address Translation

• 아래 그림은 Core i7 address translation process를 요약한 것이다.
• translation process는 CPU가 virtual address를 생성했을 때부터 data word가 memory에 도착할 때까지 과정이다.
• 단순화를 위해 i-캐시, i-TLB 및 L2 통합 TLB는 표시되지 않는다.



• Core i7은 4단계 page table 계층 구조 사용한다. (VPN4까지 있기 때문에)
• 각 process에는 각 process를 위한 page table 계층 구조 있다. (계층 구조 가진다는 뜻)
• Linux process가 실행중일 때 할당된 page와 연결된 page table들은 메모리에 있다.
• 하지만 Core i7 아키텍처에서는 이런 page table들을 swapped in and out 할 수 있다.
• CR3 control register는 L1 page table의 시작 물리 주소를 가지고 있다.
• CR3의 값은 각 process context의 일부이며 각 context switch할 때 복구된다.
• 아래 그림은 level 1~3 page table의 entry의 format을 보여준다.
• 각 항목은 4KB child page table을 참조한다. (level 2, 3 page table 크기가 각각 4KB이다.)



• P=1일 때 (Linux의 경우 항상 해당) address field는 40 bit physical page number (PPN)을 포함한다.
• 이 PPN은 적절한 child page table의 시작을 가리키는 것이다. (PPN으로 다음 레벨 page table 주소 사용)
• 이것은 page table에 4KB alignment requirement를 부과한다.
• (4KB alignment requirement의 의미는 page table의 시작의 physical address는 40 bit PPN과 더해지는 12 bit의 0에 의해 얻어진다고 한다. 그래서 52 bit physical address 얻어진다. 12bit의 0이 더해져서 physical address는 $2^{12}=4096$ 부터 시작하는 것이다. 그래서 4KB의 배수로 정렬된다는 의미다.)
• 아래 그림은 level 4 page table의 entry format을 보여준다.
• 역시 각 항목은 4KB child page table을 참조한다.



• P=1일 때 address field는 40 bit PPN을 포함한다.
• 이것은 physical memory에 있는 어떤 page의 base를 가리킨다.
• 역시 이것은 physical page에 4KB alignment requirement를 부과한다.
• (4KB 크기의 page 단위로 건너 뛸 수 있게 하는 의미 같다.)
• PTE는 page에 대한 access를 제어하는 3개의 permission bit가 있다.
• R/W bit는 page의 content가 read, write 가능인지, read-only인지 결정하는 것이다.
• U/S bit는 user mode에서 page를 access할 수 있는지를 결정한다. 이것은 OS kernel에 있는 code와 data를 user program으로부터 보호한다.
• XD bit는 64bit 시스템부터 도입되었다. 이것은 각 memory page에서 명령어 fetch를 비활성화하는데 사용이 된다. 이것은 중요한 새로운 특징이다. 왜냐하면 read only code segment로 실행을 제한해서 OS kernel이 buffer overflow 공격의 위험을 줄일 수 있게 했기 때문이다.
• MMU가 각 virtual address를 변환할 때 MMU는 2개의 다른 bit도 업데이트 한다.
• 이 2개의 다른 bit는 kernel의 page fault handler가 사용할 수 있다.
• MMU는 reference bit라고 알려진 A bit를 page에 access할 때마다 설정한다.
• kernel은 reference bit을 kernel의 page replacement 알고리즘을 구현할 때 사용한다.
• 그리고 MMU는 D bit를 page가 write 될 때마다 설정한다.
• 변경된 page를 dirty page라고 부른다.
• dirty bit는 kernel에게 victim page가 replacement page로 복사되기 전에 write back해야 하는지 아닌지를 알려주는 것이다.
• kernel은 special kernel mode 명령어를 호출해서 reference 또는 dirty bit을 clear할 수 있다.
• 아래 그림은 Core i7 MMU가 virtual address를 physical address로 변환할 때 어떻게 4 level page table을 사용하는지 보여준다.

• PT: page table;
• PTE: page table entry;
• VPN: virtual page number;
• VPO: virtual page offset;
• PPN: physical page number;
• PPO: physical page offset.
• 4 level page table에 대한 Linux 이름도 표시되어 있다.
• 36 bit VPN는 4개의 9 bit chunck로 나뉜다. (virtual address가 48bit인데 VPO가 12 bit이니 남은 36 bit의 VPN이 있다.)
• 각 chunck는 각 level의 page table의 offset으로 사용된다.
• CR3 레지스터는 L1 page table의 physical address를 가지고 있다.
• VPN 1은 L1 PTE offset을 제공한다. L1 PTE는 L2 page table의 base address를 가지고 있다.
• VPN 2는 L2 PTE offset을 제공한다. 이렇게 계속 진행되는 것이다.

9.7.2 Linux Virtual Memory System

• virtual memory system은 HW와 kernel과 긴밀한 협력이 필요하다.
• 세부 사항은 버전마다 다르고 완벽한 설명은 범위를 벗어난다.
• 그래도 이 섹션의 목표는 Linux virtual memory system에 대해 충분히 설명하는 것이다.
• 왜냐하면 어떻게 실제 OS가 virtual memory를 구성하는지와 어떻게 page fault를 다루는지에 대해서 조금이라도 알려주기 위해서다.
• Linux는 각 process마다 아래 그림에 표시된 형식으로 별도의 virtual address space를 가지고 있다.

• 이 그림은 여러번 봤던 것이다.
• 보면 code, data, heap, shared library, stack segment 등 친숙한 것들이 보인다.
• 이제 address translation을 이해했으니 user stack 위에 있는 kernel virtual memory에 대한 세부 정보를 채울 수 있다.
• kernel virtual memory는 kernel의 code와 data structure를 포함한다.
• kernel virtual memory의 어떤 영역은 모든 프로세스에게 공유되는 physical page와 매핑된다.
• (프로세스의 virtual page table들이 하나의 physical memory의 page를 공유하는 경우다.)
• 예를 들어 모든 프로세스는 kernel의 code와 전역 data structure를 공유한다.
• Linux 또한 연속 virtual page set를 해당되는 연속 physical page set와 매핑한다.
• (physical memory에 막 할당해 놓는 것이 아니라 연속적으로 한다는 의미 같다.)
• 이렇게 해서 kernel은 physical memory의 특정 위치에 쉽게 access할 수 있다.
• 예를 들어 page table에 access해야 하거나 특정 physical memory 위치에 매핑된 디바이스에 memory-mapped IO operations을 수행해야 할 때 쉽게 access할 수 있는 것이다.
• kernel virtual memory의 다른 영역에는 각 프로세스마다 다른 data를 포함한다.

각 프로세스마다 다른 data에는 다음과 같은 것들이 있다.

1. page table
2. kernel이 process의 context에서 code를 실행할 때 사용하는 stack
3. virtual address space의 현재 구성을 추적하는 다양한 데이터 구조

Linux Virtual Memory Areas

• Linux는 virtual memory를 area=segment의 모음으로 구성한다.
• area는 page가 어떤 식으로든 연관이 있는 할당된 virtual memory의 연속 chunck다.
• 예를 들어 code segment, data segment, heap, shared library segment, user stack 이런 것들은 모두 별개의 area이다.
• 각 할당된 virtual page는 어떤 area에 포함되고 있다.
• 그리고 어떤 area에도 포함되지 않는 virtual page는 존재할 수 없으면 process가 참조할 수 없다.
• 이런 area의 개념은 매우 중요하다. 왜냐하면 area가 virtual address space가 gap 가질 수 있게 하기 때문이다.
• kernel은 존재하지 않는 virtual page를 계속 추적하지 않는다. 그리고 이런 page는 메모리, 디스크 또는 kernel에서 추가 리소스를 소비하지 않는다.
• 아래 그림은 프로세스에서 virtual memory area를 추적하는 kernel data structure를 보여준다.

• kernel은 시스템에 있는 각 프로세스에 대해 고유한 task structure를 가지고 있다.
• task structure의 element는 kernel이 프로세스를 실행하는데 필요한 모든 정보 포함하거나 가리킨다.
• kernel이 프로세스 실행하는데 필요한 정보로는 PID, user stack에 대한 포인터, PC, executable object file의 이름 등이 있다.
• task structure에 한 entry는 mm_struct를 가리킨다.
• mm_struct는 virtual memory의 현재 상태를 나타낸다.
• mm_struct에서 2개의 field를 보자. pgd와 mmap이다.
• pgd는 level 1 table = page global directory를 가리키는 것이다.
• mmap은 vm_area_structs의 리스트를 가리킨다. vm_area_structs는 현재 virtual address space의 area를 나타내는 것이다.
• kernel이 이 프로세스를 실행할 때 kernel은 pgd를 CR3 control register에 저장한다.
• 특정 area에 대한 vm_area_structs는 아래의 fields들을 가지고 있다.
• fvm_start : area의 시작 부분을 가리킨다. vm_end : area의 끝을 가리킨다. vm_prot : area에 포함된 모든 페이지에 대한 읽기/쓰기 권한을 나타낸다. vm_flags : area의 페이지가 다른 프로세스와 공유되는지 또는 이 프로세스에 대해 비공개인지를 나타낸다. vm_next : list에 있는 다음 area_structs를 가리킨다.

Linux Page Fault Exception Handling

• MMU가 virtual address A를 변환하려고 하는 동안 page fault 났다고 가정해보자.
• 이 exception은 kernel의 page fault handler에게 control을 넘긴다.
• 그리고 아래의 단계를 거쳐 일을 수행한다.

1. virtual address A가 합법적인가? 체크한다.
   1. 즉 이 A가 area struct에 정의된 area 안에 있는지 확인하는 것이다.
   2. 이 질문에 답하기 위해서 fault handler는 area struct list를 뒤진다.
   3. 뒤지면서 A와 각 area struct의 vm_start와 vm_end와 비교한다.
   4. 만약에 주소가 합법적이지 않으면 fault handler는 segmentation fault를 발생시킨다. 그러면 프로세스는 종료된다.
   5. 이런 상황은 아래 그림에서 1로 표시된 것이다.
   6. 프로세스가 임의의 개수의 새로운 virtual memory area를 생성할 수 있기 때문에 area struct list를 순차적으로 뒤지는 것은 비용이 많이든다.
   7. 따라서 실제 Linux에서는 표시되지 않은 field를 사용해서 list에 tree를 중첩하고(list를 tree로 바꾼다는 의미??) tree에서 search를 진행한다.
2. 시도된 memory access가 합법적인가? 체크한다.
   1. 즉 프로세스가 이 area에서 page를 read or write or execute 할 수 있는 권한이 있는지 확인하는 것이다.
   2. 예를 들어 store 명령어가 read only page에 write를 시도해서 page fault가 발생한 상황이 있을 수 있다.
   3. 아니면 user mode에서 실행중인 프로세스가 kernel virtual memory에서 word를 읽으려고 시도해서 page fault가 발생한 상황이 있을 수 있다.
   4. 만약에 access가 합법적이지 않다면 fault handler는 protection exception을 발생시킨다. 그러면 프로세스는 종료된다.
   5. 이런 상황은 아래 그림에서 2로 표시된 것이다.
3. 여기까지 오면 kernel은 합법적인 virtual address에서 합법적인 operation으로 인해서 page fault가 발생했음을 알고 있다.
   1. kernel은 fault를 victim page를 선택해서 해결한다.
   2. victim page가 dirty page 였으면 swapping out하고 새로운 page를 swapping in하고 page table을 업데이트한다.
   3. page fault handler가 반환되었을 때 CPU는 fault가 발생한 명령어를 다시 실행한다. 즉 A를 MMU에 다시 보내는 것이다.
   4. 이번에는 MMU가 page fault 없이 A를 정상적으로 변환한다.

1. 1.