CHAPTER 3. 페이지 테이블

Chapter 3. 페이지 테이블

페이지 테이블은 운영체제가 각 프로세스에 자기만의 독립적인 주소 공간과 메모리를 제공하는 데 사용하는 가장 널리 쓰이는 메커니즘이다. 페이지 테이블은 메모리 주소가 무엇을 의미하는지, 그리고 어떤 물리 메모리의 어느 영역에 접근할 수 있는지를 결정한다. 페이지 테이블은 xv6가 서로 다른 프로세스들의 주소 공간을 격리하고, 그것들을 하나의 물리 메모리 위에 다중화할 수 있게 해준다. 페이지 테이블은 운영체제가 여러 유용한 기법을 수행할 수 있게 해주는 간접 계층을 제공한다.

xv6는 그중 몇 가지를 수행한다. 같은 메모리, 즉 트램펄린 페이지를 여러 주소 공간에 매핑하고, 매핑되지 않은 페이지로 커널 스택과 사용자 스택을 보호하며, 사용자 힙 메모리를 지연 할당한다. 이 장의 나머지 부분은 RISC-V 하드웨어가 제공하는 페이지 테이블과 xv6가 그것을 어떻게 사용하는지를 설명한다.

3.1 페이징 하드웨어

다시 상기하자면, RISC-V 명령어는 사용자 명령어든 커널 명령어든 가상 주소를 조작한다. 기계의 RAM, 즉 물리 메모리는 물리 주소로 인덱싱된다. RISC-V 페이지 테이블 하드웨어는 각 가상 주소를 물리 주소에 매핑함으로써 이 두 종류의 주소를 연결한다.

xv6는 RISC-V의 Sv39 모드를 사용한다. 이는 64비트 가상 주소 중 하위 39비트만 사용되고, 상위 25비트는 사용되지 않는다는 뜻이다. 이 Sv39 구성에서 RISC-V 페이지 테이블은 논리적으로 2²⁷개, 즉 134,217,728개의 페이지 테이블 엔트리(PTE)로 이루어진 배열이다. 각 PTE는 44비트 물리 페이지 번호(PPN)와 몇 개의 플래그를 포함한다. 페이징 하드웨어는 39비트 중 상위 27비트를 사용해 페이지 테이블을 인덱싱하여 PTE를 찾고, 물리 주소의 상위 44비트는 PTE의 PPN에서 가져오고, 하위 12비트는 원래 가상 주소에서 그대로 복사한다.

그림 3.1은 PTE들의 단순 배열로서 페이지 테이블을 논리적으로 보았을 때 이 과정이 어떻게 이루어지는지 보여준다. 실제 RISC-V 페이지 테이블은 트리 구조이며, 더 완전한 설명은 그림 3.2를 보라. 페이지 테이블은 운영체제가 정렬된 4096바이트, 즉 2¹²바이트 단위로 가상 주소에서 물리 주소로의 변환을 제어할 수 있게 한다. 이런 덩어리를 페이지라고 부른다.

RISC-V의 설계는 가상 주소와 물리 주소 모두 확장될 여지를 남겨두었다. 더 많은 가상 주소 공간이 필요하다면 RISC-V는 48비트 가상 주소를 사용하는 Sv48 모드를 지원한다. 물리 주소 역시 성장 여지가 있다. PTE 형식에는 물리 페이지 번호가 추가로 10비트 더 커질 수 있는 공간이 있다. RISC-V 설계자들은 기술 예측을 바탕으로 주소 크기를 선택했다. 2⁴⁸바이트는 262,144GB로, 오늘날 어떤 애플리케이션도 사용할 가능성이 낮은 훨씬 큰 사용자 가상 주소 공간이다. 2⁵⁶바이트의 물리 주소 공간은 65,536테라바이트이며, 현재 어떤 컴퓨터도 장착할 수 있는 RAM보다 훨씬 많다.

그림 3.2가 보여주듯, RISC-V CPU 페이지 테이블은 물리 메모리 안에 3단계 트리로 저장된다. 트리의 루트는 4096바이트짜리 페이지 테이블 페이지이며, 512개의 PTE를 포함한다. 이 PTE들은 트리의 다음 단계에 있는 페이지 테이블 페이지들의 물리 주소를 담고 있다. 그 각각의 페이지도 최종 단계 트리를 위한 512개의 PTE를 포함한다. 페이징 하드웨어는 27비트 중 상위 9비트를 사용해 루트 페이지 테이블 페이지 안의 PTE를 선택하고, 가운데 9비트를 사용해 다음 단계 페이지 테이블 페이지 안의 PTE를 선택하며, 하위 9비트를 사용해 최종 PTE를 선택한다. Sv48 RISC-V에서는 페이지 테이블이 4단계이고, 가상 주소의 39번부터 47번 비트가 최상위 단계를 인덱싱한다.

주소를 변환하는 데 필요한 세 PTE 중 하나라도 존재하지 않으면, 페이징 하드웨어는 페이지 폴트 예외를 발생시킨다. 이후 페이지 폴트를 처리하는 일은 커널에게 맡겨진다. 이는 4장과 5장에서 다룬다.

그림 3.2의 3단계 구조는 그림 3.1의 단일 단계 설계와 비교했을 때 PTE를 메모리 효율적으로 기록할 수 있게 해준다. 넓은 범위의 가상 주소가 매핑을 갖지 않는 일반적인 경우, 3단계 구조는 하위 page-table page 전체를 생략할 수 있다. 예를 들어 애플리케이션이 주소 0에서 시작하는 몇 개의 페이지만 사용한다면, 최상위 페이지 테이블의 1번부터 511번 엔트리는 무효이며, 커널은 그 511개의 중간 레벨 page-table page을 위한 페이지를 할당할 필요가 없다. 게다가 커널은 그 511개의 중간 레벨 page-table page 각각에 대응하는 최하위 page-table page도 할당할 필요가 없다. 따라서 이 예에서 3단계 설계는 중간 레벨 page-table page 511페이지와 최하위 page-table page 511 × 512페이지를 절약한다.

CPU는 load 또는 store 명령어를 실행하는 과정에서 3단계 구조를 하드웨어적으로 순회하지만, 3단계 구조의 잠재적 단점은 CPU가 load/store 명령어 안의 가상 주소를 물리 주소로 변환하기 위해 메모리에서 세 개의 PTE를 읽어야 한다는 점이다. 물리 메모리에서 PTE를 읽는 비용을 피하기 위해 RISC-V CPU는 PTE를 TLB(Translation Lookaside Buffer)에 캐시한다.

각 PTE는 연결된 가상 주소가 어떻게 사용될 수 있는지를 페이징 하드웨어에 알려주는 플래그 비트를 포함한다. PTE_V는 PTE가 존재하는지를 나타낸다. 이 비트가 설정되어 있지 않으면 해당 페이지에 대한 참조는 페이지 폴트 예외를 발생시킨다. 즉 허용되지 않는다. PTE_R은 명령어가 그 페이지를 읽을 수 있는지를 제어한다. PTE_W는 명령어가 그 페이지에 쓸 수 있는지를 제어한다. PTE_X는 CPU가 그 페이지의 내용을 명령어로 해석하고 실행할 수 있는지를 제어한다. PTE_U는 사용자 모드의 명령어가 그 페이지에 접근할 수 있는지를 제어한다. PTE_U가 설정되어 있지 않으면 해당 PTE는 Supervisor 모드에서만 사용할 수 있다. 그림 3.2는 플래그 비트들이 PTE 안에서 어디에 위치하는지 보여준다. 플래그와 그 밖의 모든 페이지 하드웨어 관련 구조는 0500에 정의되어 있다.

CPU가 어떤 페이지 테이블을 사용하게 하려면, 커널은 루트 페이지 테이블 페이지의 물리 주소를 satp 레지스터에 써야 한다. CPU는 이후 명령어들이 생성하는 모든 주소를 satp가 가리키는 페이지 테이블을 사용해 변환한다. 각 CPU는 자기 자신의 satp를 갖는다. 따라서 서로 다른 CPU들은 서로 다른 프로세스를 실행할 수 있고, 각 프로세스는 자기 자신의 페이지 테이블로 표현되는 독립적인 주소 공간을 가진다.

커널의 관점에서 페이지 테이블은 메모리에 저장된 데이터이며, 커널은 일반적인 트리 형태 자료구조를 다루는 코드와 매우 비슷한 코드로 페이지 테이블을 생성하고 수정한다.

이 책에서 사용하는 용어에 대해 몇 가지 주의할 점이 있다. 물리 메모리는 RAM 안의 저장 셀을 가리킨다. 물리 메모리의 한 바이트는 주소를 가지며, 이를 물리 주소라고 부른다. 메모리를 참조하는 명령어들, 예를 들어 load, store, jump, 함수 호출은 오직 가상 주소만 사용한다. 페이징 하드웨어는 이 가상 주소를 물리 주소로 변환하고, 그다음 메모리 시스템에 보내 저장소를 읽거나 쓴다. 주소 공간은 어떤 페이지 테이블에서 유효한 가상 주소들의 집합이다. 각 xv6 프로세스는 별도의 사용자 주소 공간을 가지며, xv6 커널도 자기 자신의 주소 공간을 가진다. 사용자 주소 공간의 메모리는 프로세스의 사용자 주소 공간과, 그 페이지 테이블이 프로세스가 접근하도록 허용하는 물리 메모리를 함께 가리킨다. 가상 메모리는 페이지 테이블을 관리하고 이를 사용해 격리 같은 목표를 달성하는 데 관련된 아이디어와 기법을 가리킨다.

3.2 커널 주소 공간

시작할 때 xv6는 커널의 주소 공간을 설명하는 하나의 페이지 테이블을 만든다. 커널은 자기 주소 공간의 배치를 설정하여, 물리 메모리와 다양한 하드웨어 자원에 예측 가능한 가상 주소로 접근할 수 있게 한다. 그림 3.3은 이 배치가 커널 가상 주소를 물리 주소에 어떻게 매핑하는지 보여준다. 0200 파일은 xv6의 커널 메모리 배치에 대한 상수들을 선언한다.

QEMU는 물리 주소 0x80000000에서 시작하여 최소한 0x88000000까지 이어지는 RAM, 즉 물리 메모리를 포함한 컴퓨터를 시뮬레이션한다. xv6는 이 끝 주소를 PHYSTOP이라고 부른다. QEMU 시뮬레이션은 디스크 인터페이스 같은 I/O 장치도 포함한다. QEMU는 장치 인터페이스를 물리 주소 공간의 0x80000000 아래에 위치한 메모리 매핑 제어 레지스터로 소프트웨어에 노출한다. 커널은 이 특수한 물리 주소들을 읽고 씀으로써 장치와 상호작용할 수 있다. 이런 읽기와 쓰기는 RAM이 아니라 장치 하드웨어와 통신한다. 4장은 xv6가 장치와 어떻게 상호작용하는지 설명한다.

커널은 모든 물리 RAM과 장치 레지스터를 물리 주소와 같은 값의 가상 주소에 매핑한다. 이것을 직접 매핑(direct mapping)이라고 하며, 커널이 가상 주소 x에 load 또는 store를 수행하는 것만으로 물리 주소 x를 읽거나 쓸 수 있게 한다. 커널 코드 자체는 가상 주소 공간과 물리 메모리 양쪽 모두에서 KERNBASE=0x80000000에 위치한다. kfork(2373)가 자식 프로세스를 위한 사용자 주소 공간의 메모리를 할당할 때, 할당자는 그 메모리의 물리 주소를 반환한다. kfork는 부모의 사용자 주소 공간의 메모리를 자식에게 복사할 때 그 주소를 가상 주소로 직접 사용한다.

직접 매핑되지 않는 커널 가상 주소도 몇 가지 있다.

첫째, 트램펄린 페이지다. 이는 가상 주소 공간의 맨 위에 매핑된다. 사용자 페이지 테이블도 같은 매핑을 갖는다. 4장은 트램펄린 페이지의 역할을 논의하지만, 여기서 우리는 페이지 테이블의 흥미로운 사용 사례를 볼 수 있다. trampoline 코드를 담고 있는 하나의 물리 페이지가 커널의 가상 주소 공간 안에 두 번 매핑된다. 한 번은 가상 주소 공간의 맨 위에, 또 한 번은 직접 매핑으로 매핑된다.

둘째, 커널 스택 페이지다. 각 프로세스는 자기 자신의 커널 스택을 가지며, 이는 높은 커널 가상 주소에 매핑된다. xv6는 그 아래에 매핑되지 않은 가드 페이지를 남겨둘 수 있다. 가드 페이지의 PTE는 무효다. 즉 PTE_V가 설정되어 있지 않다. 따라서 커널이 커널 스택을 넘치게 사용하면 페이지 폴트가 발생할 가능성이 높고, 커널은 panic을 일으킨다. 가드 페이지가 없다면 넘친 스택은 다른 커널 메모리를 덮어써서 잘못된 동작을 일으킬 것이다. panic으로 크래시되는 편이 더 낫다.

커널은 높은 커널 가상 주소 영역의 매핑을 통해 스택을 사용하지만, 각 스택은 직접 매핑된 주소를 통해서도 커널에서 접근할 수 있다. 다른 설계는 직접 매핑만 두고 스택도 직접 매핑된 주소에서 사용할 수 있다. 그러나 그런 구성에서는 가드 페이지를 제공하려면 원래 물리 메모리를 가리켜야 할 가상 주소의 매핑을 해제해야 한다. 그러면 그 물리 메모리를 사용하기 어려워진다.

커널은 trampoline과 커널 텍스트 영역(kernel text)를 위한 페이지를 PTE_R 및 PTE_X 권한으로 매핑하지만 PTE_W로는 매핑하지 않는다. 커널은 다른 페이지들을 PTE_R 및 PTE_W 권한으로 매핑하지만 PTE_X로는 매핑하지 않는다. 가드 페이지의 매핑은 무효다. 이러한 제한된 권한의 목적은 커널 버그가 예상치 못한 방식으로 페이지에 접근할 때 이를 잡아내는 것이다. 예를 들어 커널 코드가 실수로 커널 명령어를 덮어쓰려고 하는 경우가 그렇다.

커널은 하나의 커널 페이지 테이블을 만들며, 모든 CPU는 커널에서 실행될 때 이 페이지 테이블을 사용한다. xv6는 커널 페이지 테이블을 처음 만든 이후에는 수정하지 않는다.

3.3 코드: 주소 공간 만들기

계속 진행하기 전에 kernel/vm.c에서 mappages() 함수 끝까지 읽어라.

xv6에서 주소 공간과 페이지 테이블을 조작하는 코드 대부분은 vm.c(1400)에 있다. 중심 자료구조는 pagetable_t이며, 실제로는 RISC-V 루트 페이지 테이블 페이지를 가리키는 포인터다. pagetable_t는 커널 페이지 테이블일 수도 있고, 프로세스별 페이지 테이블 중 하나일 수도 있다. 중심 함수는 walk와 mappages다. walk는 어떤 가상 주소에 대한 PTE를 찾고, mappages는 새 매핑을 위한 PTE를 설치한다. kvm으로 시작하는 함수들은 커널 페이지 테이블을 조작한다. uvm으로 시작하는 함수들은 사용자 페이지 테이블을 조작한다. 다른 함수들은 양쪽 모두에 사용된다. copyout과 copyin은 시스템 콜 인자로 제공된 사용자 가상 주소로 데이터를 복사하거나 그 주소에서 데이터를 복사한다. 이 함수들이 vm.c에 있는 이유는 해당 주소에 대응하는 물리 메모리를 찾기 위해 주소를 명시적으로 변환해야 하기 때문이다.

부팅 시퀀스 초기에 main은 kvminit(1465)을 호출해 kvmmake(1421)를 사용하여 커널의 페이지 테이블을 만든다. 이 호출은 xv6가 RISC-V에서 페이징을 활성화하기 전에 일어나므로, 주소는 직접 물리 메모리를 가리킨다. kvmmake는 먼저 루트 페이지 테이블 페이지를 담을 물리 메모리 한 페이지를 할당한다. 그런 다음 kvmmap을 호출해 커널이 필요로 하는 변환을 설치한다. 이 변환에는 커널의 명령어와 데이터, PHYSTOP까지의 물리 메모리, 실제로는 장치인 메모리 범위가 포함된다. proc_mapstacks(2132)는 각 프로세스마다 커널 스택을 할당한다. 이 함수는 kvmmap을 호출해 각 스택을 KSTACK이 생성한 가상 주소에 매핑하며, 이 주소 배치는 무효한 스택 가드 페이지를 위한 공간을 남겨둔다.

kvmmap(1457)은 mappages(1556)를 호출한다. mappages는 어떤 가상 주소 범위를 그에 대응하는 물리 주소 범위에 매핑하는 항목들을 페이지 테이블에 설치한다. 이는 범위 안의 각 가상 주소에 대해 페이지 간격으로 따로 수행된다. 매핑할 각 가상 주소에 대해 mappages는 walk를 호출하여 그 주소에 대한 PTE의 주소를 찾는다. 그런 다음 PTE를 초기화하여 관련 물리 페이지 번호, 원하는 권한(PTE_W, PTE_X, 그리고/또는 PTE_R), 그리고 PTE를 유효하다고 표시하기 위한 PTE_V를 담게 한다(1577).

walk(1497)는 RISC-V 페이징 하드웨어가 가상 주소에 대한 PTE를 찾는 방식을 모방한다. 그림 3.2를 보라. walk는 페이지 테이블 트리를 한 단계씩 내려가며, 각 단계에서 가상 주소의 9비트를 사용해 관련 페이지 테이블 페이지를 인덱싱한다. 각 단계에서 다음 단계 페이지 테이블 페이지의 PTE를 찾거나, 최종 페이지의 PTE를 찾는다(1503). 1단계 또는 2단계 페이지 테이블 페이지의 PTE가 유효하지 않다면, 필요한 page-table page가 아직 할당되지 않았다는 뜻이다. alloc 인자가 설정되어 있다면 walk는 새 페이지 테이블 페이지를 할당하고 그 물리 주소를 PTE에 넣는다. walk는 트리의 가장 낮은 계층에 있는 PTE의 주소를 반환한다(1513).

위 코드는 물리 메모리가 커널 가상 주소 공간에 직접 매핑되어 있다는 사실에 의존한다. 예를 들어 walk가 페이지 테이블의 여러 단계를 내려갈 때, PTE에서 다음 하위 단계 페이지 테이블의 물리 주소를 꺼낸다(1505). 그리고 그 주소를 가상 주소로 사용해 다음 하위 단계의 PTE를 가져온다(1503).

각 CPU에서 main은 kvminithart(1473)를 호출해 커널 페이지 테이블을 설치한다. 이 함수는 루트 페이지 테이블 페이지의 물리 주소를 CPU의 satp 레지스터에 넣는다. 이후 CPU는 커널 페이지 테이블을 사용해 주소를 변환한다. 커널 페이지 테이블은 직접 매핑되어 있기 때문에 커널은 계속 올바르게 실행된다. 즉 이 변경 전후로 주소는 RAM 안의 같은 위치를 가리킨다.

각 RISC-V CPU는 PTE를 TLB에 캐시한다. xv6가 페이지 테이블을 변경하면, CPU에게 해당 캐시된 TLB 엔트리를 무효화하라고 알려야 한다. 그렇게 하지 않으면 나중에 어느 시점에 TLB가 오래된 캐시 매핑을 사용할 수 있다. 그 매핑은 그사이에 다른 프로세스에 할당된 물리 페이지를 가리킬 수 있고, 그 결과 한 프로세스가 다른 프로세스의 메모리를 마구 써버릴 수 있다. RISC-V에는 현재 CPU의 TLB를 flush하는 sfence.vma 명령어가 있다. xv6는 satp 레지스터를 다시 로드한 후 kvminithart에서 sfence.vma를 실행하고, uservec과 userret을 위한 trampoline 코드에서도 실행한다.

satp를 변경하기 전에도 sfence.vma 명령어를 실행해야 한다. 이는 아직 완료되지 않은 모든 load와 store가 끝나기를 기다리기 위해서다. 이 대기는 앞선 페이지 테이블 갱신이 완료되었음을 보장하고, 앞선 load와 store가 새 페이지 테이블이 아니라 기존 페이지 테이블을 사용하도록 보장한다.

3.4 물리 메모리 할당

커널은 실행 시간에 페이지 테이블, 사용자 주소 공간의 메모리, 커널 스택, 파이프 버퍼를 위해 물리 메모리를 할당하고 해제해야 한다.

xv6는 커널의 끝과 PHYSTOP 사이의 물리 메모리를 실행 시간 할당에 사용한다. xv6는 한 번에 4096바이트짜리 전체 페이지를 할당하고 해제한다. 어떤 페이지가 비어 있는지는 페이지들 자체를 통과하는 연결 리스트를 엮어 추적한다. 할당은 연결 리스트에서 페이지 하나를 제거하는 것이다. 해제는 해제된 페이지를 리스트에 추가하는 것이다.

kernel/kalloc.c를 읽어라.

3.5 코드: 물리 메모리 할당자

할당자는 kalloc.c(2950)에 있다. 할당자의 자료구조는 할당 가능한 물리 메모리 페이지들의 free list다. 각 사용 가능한 페이지(free page)의 “next” 포인터는 struct run(2966) 안에 있다. 할당자는 각 사용 가능한 페이지(free page)의 run 구조체를 그 사용 가능한 페이지(free page) 자체 안에 저장한다. 페이지가 free 상태일 때는 그 안에 다른 것이 저장되어 있지 않기 때문이다. free list는 spin lock으로 보호된다(2970-2973). 리스트와 락은 하나의 struct로 감싸져 있는데, 이는 락이 struct 안의 필드들을 보호한다는 점을 분명히 하기 위해서다. 지금은 락과 acquire, release 호출을 무시하라. 7장에서 락을 자세히 살펴볼 것이다.

main 함수는 kinit을 호출해 할당자를 초기화한다(2976). kinit은 커널의 끝과 PHYSTOP 사이에 있는 물리 RAM의 모든 페이지를 담도록 free list를 초기화한다. xv6는 하드웨어가 제공하는 설정 정보를 파싱해서 사용 가능한 물리 메모리 양을 알아내야 할 것이다. 그러나 xv6는 기계가 128메가바이트의 RAM을 가지고 있다고 가정한다. kinit은 freerange를 호출해 각 페이지마다 kfree를 호출하는 방식으로 free list에 반환한다. PTE는 4096바이트 경계에 정렬된, 즉 4096의 배수인 물리 주소만 가리킬 수 있으므로, freerange는 PGROUNDUP을 사용해 정렬된 물리 주소만 해제하도록 한다. 할당자는 처음에는 어떤 메모리도 갖고 있지 않다. kfree에 대한 이 호출들이 할당자에게 관리할 메모리를 제공한다.

할당자는 주소에 대한 산술을 수행하기 위해 주소를 정수처럼 취급하기도 하고, 메모리를 읽고 쓰기 위해 주소를 포인터처럼 사용하기도 한다. 예를 들어 freerange에서 모든 페이지를 순회할 때는 주소를 정수처럼 다루고, 각 페이지 안에 저장된 run 구조체를 조작할 때는 포인터처럼 다룬다. 주소의 이런 이중 사용이 할당자 코드에 C 타입 캐스트가 가득한 주된 이유다.

kfree(3005) 함수는 해제되는 메모리의 모든 바이트를 값 1로 설정하는 것으로 시작한다. 이렇게 하면 메모리를 해제한 뒤에도 그것을 사용하는 코드, 즉 댕글링 참조(dangling reference)를 사용하는 코드는 예전의 유효한 내용을 읽는 대신 junk 값을 읽게 된다. 바라건대 이는 그런 코드가 더 빨리 깨지게 만들 것이다. 그런 다음 kfree는 그 페이지를 free list의 앞에 붙인다. pa를 struct run에 대한 포인터로 캐스트하고, free list의 기존 시작점을 r->next에 기록한 뒤, free list를 r로 설정한다. kalloc은 free list의 첫 번째 요소를 제거하고 반환한다.

3.6 프로세스 주소 공간

각 프로세스는 자기 자신의 페이지 테이블을 가지며, xv6가 프로세스 사이를 전환할 때 페이지 테이블도 함께 변경된다. 그림 3.4는 그림 2.3보다 더 자세하게 프로세스의 주소 공간을 보여준다. 프로세스의 사용자 주소 공간은 0에서 시작하며 원칙적으로 MAXVA, 즉 0x4000000000에서 끝난다(0896). 하지만 실제로는 그중 아주 작은 일부만 물리 메모리에 매핑된다.

프로세스의 주소 공간은 프로그램의 text를 담는 페이지들, 프로그램의 미리 초기화된 데이터를 담는 페이지들, 스택을 위한 페이지 하나, 그리고 힙을 위한 페이지들로 이루어진다. xv6는 text를 담는 페이지를 PTE_R, PTE_X, PTE_U 권한으로 매핑한다. xv6는 데이터, 스택, 힙을 PTE_R, PTE_W, PTE_U 권한으로 매핑한다.

사용자 주소 공간 안에서 권한을 사용하는 것은 사용자 프로세스를 강화하는 일반적인 기법이다. text가 PTE_W로 매핑되어 있다면, 프로세스가 실수로 자기 자신의 코드를 수정할 수 있다. 예를 들어 프로그래밍 오류로 프로그램이 널 포인터(NULL 포인터)에 쓰기를 수행하면 주소 0의 명령어를 수정하고, 이후 계속 실행되어 더 큰 혼란을 만들 수 있다. 이런 오류를 즉시 감지하기 위해 xv6는 text를 PTE_W 없이 매핑한다. 프로그램이 실수로 주소 0에 store를 시도하면 하드웨어는 store 실행을 거부하고 페이지 폴트를 발생시킨다. 4장을 보라. 그러면 커널은 그 프로세스를 죽이고, 개발자가 문제를 추적할 수 있도록 유용한 메시지를 출력한다.

마찬가지로 데이터를 PTE_X 없이 매핑하면, 사용자 프로그램은 실수로 프로그램 데이터 안의 주소로 jump하여 그 주소에서 실행을 시작할 수 없다.

실제 운영체제에서 권한을 신중하게 설정해 프로세스를 강화하는 것은 보안 공격 방어에도 도움이 된다. 공격자는 프로그램, 예를 들어 웹 서버에 정교하게 구성된 입력을 제공하여 프로그램 안의 버그를 유발하고, 그 버그를 exploit으로 바꾸기를 기대할 수 있다. 권한을 신중하게 설정하는 것과 사용자 주소 공간의 배치를 무작위화하는 것 같은 다른 기법들은 이런 공격을 더 어렵게 만든다.

스택은 단일 페이지이며, 그림에는 exec 시스템 콜이 만든 초기 내용이 표시되어 있다. 명령행 인자를 담은 문자열들과 그 문자열들을 가리키는 포인터 배열이 스택의 맨 위에 있다. 그 바로 아래에는 프로그램이 마치 main(argc, argv) 함수가 방금 호출된 것처럼 main에서 시작할 수 있게 해주는 값들이 있다.

사용자 스택이 할당된 스택 메모리가 넘치는 것을 감지하기 위해, xv6는 스택 바로 아래에 접근 불가능한 가드 페이지를 둔다. 이는 PTE_U 플래그를 지움으로써 이루어진다. 사용자 스택이 넘쳐서 프로세스가 스택 아래의 주소를 사용하려 하면, 가드 페이지는 사용자 모드에서 실행 중인 프로그램에 접근 불가능하므로 하드웨어는 페이지 폴트 예외를 생성한다. 현실 세계의 운영체제라면 스택이 넘칠 때 사용자 스택을 위한 메모리를 자동으로 더 할당할 수도 있다.

여기서 페이지 테이블 사용의 몇 가지 좋은 예를 볼 수 있다. 첫째, 서로 다른 프로세스의 페이지 테이블은 사용자 주소를 서로 다른 물리 메모리 페이지로 변환한다. 따라서 각 프로세스는 독립적인 사용자 주소 공간의 메모리를 가진다. 둘째, 각 프로세스는 자기 메모리가 0에서 시작하는 연속적인 가상 주소를 가진 것처럼 보지만, 프로세스의 물리 메모리는 불연속적일 수 있다. 셋째, 커널은 사용자 주소 공간의 맨 위에 trampoline 코드를 담은 페이지를 매핑한다. 이때 PTE_U는 설정하지 않는다. 따라서 하나의 물리 메모리 페이지가 모든 주소 공간에 나타나지만, 오직 커널만 사용할 수 있다.

3.7 코드: exec

kernel/exec.c와 kernel/vm.c의 uvmcreate()부터 읽어라.

exec는 프로세스의 사용자 주소 공간을 파일에서 읽은 데이터로 교체하는 시스템 콜이다. 이 파일은 바이너리 또는 executable file이라고 부른다. 바이너리는 일반적으로 컴파일러와 링커의 출력물이며, 기계어 명령어와 프로그램 데이터를 담고 있다. kexec(6426), 즉 exec의 커널 내부 구현은 namei(6440)를 사용해 이름이 지정된 바이너리 경로를 연다. namei는 10장에서 설명한다. 그런 다음 ELF header를 읽는다. xv6 바이너리는 널리 사용되는 ELF 형식으로 구성되며, 이는 0950에 정의되어 있다. ELF 바이너리는 ELF header인 struct elfhdr(0955)와 그 뒤에 이어지는 Program Header들의 시퀀스인 struct proghdr(0974)로 이루어진다. 각 Program Header는 메모리에 적재될 하나의 세그먼트를 설명한다. xv6 프로그램은 두 개의 Program Header를 가진다. 하나는 명령어용이고, 하나는 데이터용이다.

첫 번째 단계는 파일이 아마도 ELF 바이너리를 포함하는지 빠르게 검사하는 것이다. ELF 바이너리는 네 바이트짜리 “magic number” 0x7F, ‘E’, ‘L’, ‘F’, 즉 ELF_MAGIC(0952)으로 시작한다. ELF header가 올바른 magic number를 가지고 있다면, kexec는 바이너리가 잘 형성되어 있다고 가정한다.

kexec는 proc_pagetable(6454)을 사용해 사용자 매핑이 없는 새 페이지 테이블을 할당하고, uvmalloc(6470)을 사용해 각 ELF 세그먼트(segment)를 위한 메모리를 할당하며, loadseg(6409)를 사용해 각 segment를 메모리에 적재한다. loadseg는 walkaddr을 사용해 ELF 세그먼트(segment)의 각 페이지를 쓸 할당된 메모리의 물리 주소를 찾고, readi를 사용해 파일에서 읽는다.

exec로 생성되는 첫 번째 사용자 프로그램인 /init의 Program Header는 다음과 같다.

# objdump -p user/_init

user/_init:         file format elf64-little

Program Header:
0x70000003 off    0x0000000000006bb0 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**0
         filesz 0x000000000000004a memsz 0x0000000000000000 flags r--
    LOAD off    0x0000000000001000 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**12
         filesz 0x0000000000001000 memsz 0x0000000000001000 flags r-x
    LOAD off    0x0000000000002000 vaddr 0x0000000000001000
                                       paddr 0x0000000000001000 align 2**12
         filesz 0x0000000000000010 memsz 0x0000000000000030 flags rw-
   STACK off    0x0000000000000000 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**4
         filesz 0x0000000000000000 memsz 0x0000000000000000 flags rw-

여기서 텍스트 세그먼트는 메모리의 가상 주소 0x0에 적재되어야 하며, 쓰기 권한 없이 파일의 offset 0x1000에 있는 내용에서 적재된다는 것을 볼 수 있다. 또한 데이터 세그먼트는 주소 0x1000에 적재되어야 하며, 이 주소는 페이지 경계에 있고 실행 권한은 없다는 것도 볼 수 있다.

Program Header의 filesz는 memsz보다 작을 수 있다. 이는 그 둘 사이의 빈 공간을 파일에서 읽는 대신 0으로 채워야 한다는 뜻이다. 이는 C 전역 변수에 사용된다. /init의 경우 데이터 세그먼트 filesz는 0x10바이트이고 memsz는 0x30바이트다. 따라서 uvmalloc은 0x30바이트를 담기에 충분한 물리 메모리를 할당하지만, 파일 /init에서는 0x10바이트만 읽는다.

이제 kexec는 사용자 스택을 할당하고 초기화한다. 스택 페이지는 하나만 할당한다. kexec는 인자 문자열들을 하나씩 스택의 맨 위로 복사하고, 그 문자열들을 가리키는 포인터를 ustack에 기록한다. main에 전달될 argv 리스트의 끝에는 널 포인터(NULL 포인터)를 둔다. argc와 argv의 값은 시스템 콜 반환 경로를 통해 main으로 전달된다. argc는 시스템 콜 반환값을 통해 전달되며, 이는 a0에 들어간다. argv는 프로세스 trapframe의 a1 엔트리를 통해 전달된다.

kexec는 스택 페이지 바로 아래에 접근 불가 페이지(guard page)를 둔다. 따라서 프로그램이 한 페이지보다 많은 스택을 사용하려 하면 fault가 발생한다. 이 접근 불가 페이지(guard page)는 kexec가 너무 큰 인자를 처리하는 데도 도움이 된다. 그런 상황에서는 kexec가 인자를 스택으로 복사하기 위해 사용하는 copyout(1754) 함수가 목적지 페이지에 접근할 수 없다는 것을 알아차리고 -1을 반환한다.

새 메모리 이미지를 준비하는 동안 kexec가 잘못된 프로그램 segment 같은 오류를 감지하면 bad 라벨로 점프하고, 새 이미지를 해제한 뒤 -1을 반환한다. kexec는 시스템 콜이 성공할 것이라고 확신할 때까지 기존 이미지를 해제하면 안 된다. 기존 이미지가 사라지면 시스템 콜은 거기로 -1을 반환할 수 없기 때문이다. kexec의 유일한 오류 경우들은 이미지를 생성하는 동안 발생한다. 이미지가 완성되면 kexec는 새 페이지 테이블로 전환을 확정하고(6531), 기존 페이지 테이블을 해제할 수 있다(6535).

exec 시스템 콜은 ELF 파일에서 바이트를 읽어 ELF 파일이 지정한 주소의 메모리에 적재한다. 사용자나 프로세스는 ELF 파일 안에 원하는 어떤 주소든 넣을 수 있다. 따라서 exec는 위험하다. ELF 파일 안의 주소가 실수로든 의도적으로든 커널을 가리킬 수 있기 때문이다. 부주의한 커널에서 그 결과는 크래시부터 커널의 격리 메커니즘을 악의적으로 우회하는 것, 즉 보안 exploit까지 다양할 수 있다. xv6는 이런 위험을 피하기 위해 여러 검사를 수행한다. 예를 들어 if(ph.vaddr + ph.memsz < ph.vaddr)는 합이 64비트 정수에서 overflow되는지를 검사한다. 위험은 사용자가 ph.vaddr에는 사용자가 선택한 가상 주소가 들어갈 수 있고, ph.memsz는 충분히 커서 합이 overflow되어 0x1000이 되도록 ELF 바이너리를 만들 수 있다는 점이다. 그러면 이 값은 유효한 값처럼 보인다. 예전 xv6 버전에서는 사용자 주소 공간 안에 커널도 포함되어 있었다. 다만 사용자 모드에서는 읽기/쓰기가 불가능했다. 이 경우 사용자는 커널 메모리에 해당하는 주소를 선택할 수 있었고, 그러면 ELF 바이너리의 데이터가 커널로 복사될 수 있었다. RISC-V 버전의 xv6에서는 이런 일이 일어날 수 없다. 커널은 자기 자신의 별도 페이지 테이블을 가지기 때문이다. loadseg는 커널의 페이지 테이블이 아니라 프로세스의 페이지 테이블로 적재한다.

커널 개발자가 중요한 검사를 빠뜨리는 것은 쉽다. 실제 운영체제의 커널들은 빠진 검사가 사용자 프로그램에 의해 악용되어 커널 권한을 얻는 데 사용된 긴 역사를 가지고 있다. xv6가 커널에 제공되는 사용자 수준 데이터를 완전히 검증한다고 보기는 어렵다. 악의적인 사용자 프로그램은 이를 악용해 xv6의 격리를 우회할 수 있을지도 모른다.

3.8 현실 세계

대부분의 운영체제처럼 xv6는 메모리 보호와 매핑을 위해 페이징 하드웨어를 사용한다. 대부분의 운영체제는 xv6보다 훨씬 더 정교하게 페이징을 사용한다. 특히 페이징과 페이지 폴트 예외를 결합하여 사용하며, 이는 4장에서 논의한다.

xv6는 커널이 가상 주소와 물리 주소 사이의 직접 매핑을 사용하고, 커널이 적재될 것으로 기대하는 주소인 0x80000000에 물리 RAM이 있다고 가정하기 때문에 단순해진다. 이는 QEMU에서는 동작하지만, 실제 하드웨어에서는 좋지 않은 생각이다. 실제 하드웨어는 RAM과 장치를 예측 불가능한 물리 주소에 배치한다. 예를 들어 xv6가 커널을 저장할 수 있다고 기대하는 0x80000000에 RAM이 없을 수도 있다. 더 진지한 커널 설계는 페이지 테이블을 활용해 임의의 하드웨어 물리 메모리 배치를 예측 가능한 커널 가상 주소 배치로 바꾼다.

RISC-V는 물리 주소 수준의 보호를 지원하지만, xv6는 그 기능을 사용하지 않는다.

메모리가 많은 기계에서는 RISC-V의 “슈퍼페이지(superpage)” 지원을 사용하는 것이 합리적일 수 있다. 물리 메모리가 작을 때는 작은 페이지가 적절하다. 세밀한 단위로 할당하고 디스크로 페이지 아웃(page out)할 수 있기 때문이다. 예를 들어 프로그램이 8킬로바이트의 메모리만 사용한다면, 그 프로그램에게 4메가바이트짜리 super-page 전체를 물리 메모리로 주는 것은 낭비다. 큰 페이지는 RAM이 많은 기계에서 적절하며, 페이지 테이블 조작의 오버헤드를 줄일 수 있다.

페이지 테이블을 변경할 때 전체 TLB를 flush하지 않기 위해 RISC-V CPU는 ASID, 즉 주소 공간 식별자(address space identifier)를 지원할 수 있다. 그러면 커널은 특정 주소 공간에 대한 TLB 엔트리만 flush할 수 있다. xv6는 이 기능을 사용하지 않는다.

xv6 커널에는 작은 객체를 위한 메모리를 제공할 수 있는 malloc 같은 할당자가 없다. 이 때문에 커널은 동적 할당이 필요한 정교한 자료구조를 사용할 수 없다. 더 정교한 커널이라면 xv6처럼 4096바이트 블록만 할당하는 대신, 다양한 크기의 작은 블록들을 많이 할당할 것이다. 실제 커널 할당자는 큰 할당뿐만 아니라 작은 할당도 처리해야 한다.

메모리 할당은 오래도록 뜨거운 주제다. 기본 문제는 제한된 메모리를 효율적으로 사용하고, 알 수 없는 미래의 요청에 대비하는 것이다. 오늘날 사람들은 공간 효율성보다 속도에 더 관심을 둔다.

3.9 연습문제

1. RISC-V의 device tree를 파싱하여 컴퓨터가 가진 물리 메모리의 양을 찾아라.

2. copyin과 copyinstr 함수는 소프트웨어적으로 사용자 페이지 테이블을 순회한다. 커널이 사용자 프로그램을 매핑하도록 커널 페이지 테이블을 설정하고, copyin과 copyinstr이 시스템 콜 인자를 커널 공간으로 복사할 때 memcpy를 사용할 수 있게 하라. 이때 페이지 테이블 순회는 하드웨어에 의존한다.

3. xv6를 수정하여 커널에 슈퍼페이지(superpage)를 사용하라.

4. Unix의 exec 구현은 전통적으로 shell script에 대한 특별 처리를 포함한다. 실행할 파일이 #! 텍스트로 시작하면 첫 번째 줄은 그 파일을 해석하기 위해 실행할 프로그램으로 간주된다. 예를 들어 exec가 myprog arg1을 실행하도록 호출되었고, myprog의 첫 줄이 #!/interp라면, exec는 /interp를 명령행 /interp myprog arg1로 실행한다. xv6에서 이 관례를 지원하도록 구현하라.

5. 커널에 대해 address space layout randomization을 구현하라.