역(거꾸로) 매핑이 무엇일까요?
우선 가상 주소로 부터 물리 주소로 변환하는 ( Page Directory -> ... -> PTE -> PFN) "(포워드) 매핑"을 반대로 하는 것이에요! 즉, 역 매핑은 물리 주소(PFN)로 부터 가상 주소(각 태스크 마다 각자 매핑한)로 변환(Translation)하는 것을 말해요.
잠깐, 매핑을 추가로 더 한다면, 메모리 상용 공간 절약의 측면에서도 오버헤드가 생기는 도입한 이유는 무엇일까요?
역 매핑은 모든 페이지 테이블 엔트리를 찾아 매핑을 제거할 때(이런 동작을 LWN 에서는 page out 작업이라고 합니다.) 빠르게 하기 위해서 사용해요. 메모리 관리 측면에서 신속하게 페이지를 해제하고, 해당 사용했던 페이지 프레임을 다른 용도 재활용하기 위해서에요. 필요한 물리 주소 영역을 빠른 응답으로 양도 할 수 있도록 절충한거죠!
자 그럼 이제 역 매핑이 어떠한 자료 구조들에 의해서 수행할 수 있게 되는지 알아볼까요?
페이지 디스크립터에 역 매핑을 알려주는 멤버가 있어요! 역 매핑 방식에는 익명 페이지, 파일에 대한 매핑, KSM 매핑 등이 있어요. mapping 방식을 알려주는 페이지 디스크립터의 멤버를 확인해볼께요.
이번 시간은 우선 익명 페이지를 중점적으로 살펴보고, 매핑된 파일은 간략하게, 스왑 캐시의 경우에는 나중에 스왑 시스템을 살펴볼 때 집중해서 보기로 해요!
우선 익명 페이지가 무엇이었는지 상기해보면, 익명 페이지는 프로세스가 힙, 스택, 파일에 변경된 내용, 공유 메모리 등에 사용하는 가상메모리가 매핑된 페이지를 말하죠.
우선 v2.6.16 익명 페이지;역 매핑에대해서 살펴보아요!
익명 페이지를 위한 역 매핑
Figure 17-1. Object-based reverse mapping for anonymous pages
객체 기반 역 매핑은 역 매핑을 할 페이지 프레임과 관계된 메모리를 구역 별로 관리하는 자료구조(VMA)로 구성해요.
page out 을 할 때에 각자의 모든 태스크의 VM 이 공유하여 사용하고 있는 익명 페이지가 있고, 각자 페이지 테이블 엔트리로 매핑하고 있을 때, 해당하는 매핑한 페이지 테이블 엔트리를 찾아 빠르게 매핑을 언 매핑할 때 사용할 수 있어요.
페이지 프레임을 포함하는 익명 메모리 구역(VMA)들을 이중 연결 원형 리스트에 모으구요. 주의할 것은 익명 메모리 구역이 다른 페이지를 포함하더라도 구역에는 모든 페이지 프레임을 위한 하나의 역 매핑 리스트(anon_vma)만이 존재해요.
<관련 함수>
try_to_unmap_anon()
메모리 구역의 anon_vma 리스트에서 발견된 각 vma 메모리 구역에 대해 try_to_unmap_one( ) 함수를 호출해요.
try_to_unmap_one()
자 이번에는 이제 파일 v2.4.x 기준의 매핑한 페이지의 역매핑의 그림을 우선 보구요. 양방향 리스트에서 PST 로 바뀐 자료 구조까지 살펴보도록 할께요.
매핑한 페이지를 위한 역 매핑
Figure 4.2: Data Structures related to the Address Space
매핑한 페이지는 “우선순위 탐색 트리(Priority Search Trees)” 라는 특별한 탐색 트리에 의존하여, 같은 페이지 프레임을 참조하는 모든 메모리 구역들을 신속히 찾을 수 있어요!
VMA(PST) <- i_mmap <- address_space <- page
<관련 함수>
try_to_unmap_file()
여기서 공유하는 페이지들을 예를 들면, 시스템의 대부분의 프로세스는 #inlcude<stdio.h> 에 정의되어 있는 코드(glibc.so와 같은 shared object 파일)를 포함하는 페이지 등이 있겠죠.
Figure. PST
메모리 구역을 나타낼 때, 시작 인덱스는 라딕스 인덱스, 끝 인덱스는 힙 인덱스를 사용해요. 범위 중복인 경우 때문에 크기 인덱스를 넣는 거구요. 일반적인 트리가 그러하듯이 검색 속도를 높혀요. 다만 각 노드가 담당하는 특정 범위가 있는거죠!
여기서 트리의 노드가 의미하는게 여러 프로세스가 매핑한 페이지의 범위를 의미해요. 만약에 여러 노드의 매핑된 페이지가 특정 범위 페이지면 우선순위 탐색 트리로 겹쳐져 있는 영역 안 페이지를 빠르게 찾은 다음 역 매핑을 통해서 해당 VM 영역을 언 매핑하고 page out 하는 전략인거죠. 위에서 보았던 익명페이지 역 매핑에서 page out 할 때에 여러 프로세스에서 공유한 매핑을 해지한거랑 같은 맥락이에요. 자료구조만 원형 양방향 리스트에서 우선순위트리로 바뀌었죠. 전체적인 흐름은 비슷합니다. 다만 익명페이지 (프로세스, 스레드의 힙 & 스택) 비해서 공유되는 경우가 더 많은거니깐 익명페이지 언맵할 때 비해서 좀 더 효율적인 자료구조(PST)를 사용했었죠.
최신 버전에서는 PST가 사용되지 않고 RB tree로 변경되었어요.
여기까지 v2.6.x 기준은 정리했구요. 최신 버전 v5.x.x 에서 성능을 많이 개선해나가면서 점점 복잡해지게 됐어요. 일단 LWN 의 조나단 콜뱃씨 칼럼을 기준으로 객체 기반 역 매핑의 v2.6.7 구현 아이디어 구현 이후 사용하면서 어떤 문제가 있었는지 차근차근 살펴볼까요?
- By Corbet Posted March 10, 2004
주어진 페이지를 참조 할 수 있는 모든 VMA 의 연결 목록을 표시하는 anon_vma 구조를 도입 했어요.
일단 anon_vma 로 해결 된 문제를 살펴볼께요. Rmap 을 사용하면서 주어진 익명 (힙 또는 스택 메모리) 페이지를 참조하는 모든 vm_area_struct (VMA) 구조를 찾는 문제가 해결되었죠. 익명 페이지는 일반적으로 프로세스 간에 공유되지 않지만 fork ()를 호출 할 때마다 이러한 모든 페이지가 부모와 새 자식 간에 공유되요.
Figure. VMA - n page : 1 page table
따라서 fork() 는 익명 페이지를 포함하는 자식 프로세스의 모든 VMA가 부모의 anon_vma 구조에 유지되는 목록에 추가되도록합니다. struct 페이지 의 매핑 포인터 는 anon_vma 구조를 가리키므로 커널이 목록을 탐색하고 모든 관련 VMA 구조를 찾을 수 있습니다.
페이지 공유는 프로세스 중 하나가 페이지에 쓸 때만 중단되어 COW (기록 중 복사) 작업이 발생합니다. 거의 대다수의 많은 페이지가 변경하여 작성되지 않는 경우가 많기 때문에, 커널은 주어진 익명 페이지를 참조하는 여러 VMA를 찾을 수 있어야 하죠. 페이지 교체할 경우에는 이런 VMA 를 모두 찾아야하고, 그렇지 않으면 페이지 매핑을 해제 할 수 없습니다. 즉, 페이지를 교체 할 수 없게 되는거죠!
Figure. VMA - 1 page : n page table
- By Jonathan Corbet April 13, 2010
anonumous 는 보통 사전적으로 사용할 때, "스스로의 정체성을 숨기려고 자신을 감추는 경우" 즉, 남에게 안 보이려 감추려는 의도가 있습니다.
제목을 직역해보면 "너무나 많은 걸 감추고 싶어하는 anon_vma 구조체가 있을 경우"에요.
위에 설명한 알고리즘은 결국 페이지 교체할 경우에 모든 VMA 를 찾는 Rmap 구현은 AV 에 대한 잠금 처리, 탐색 비용이 비싸서 다시 작성해야 하는 것으로 판명 했구요.
Rik van Riel 씨의 설명을 들어볼까요.
1000 개의 하위 프로세스가있는 워크로드와 프로세스 당 1000 개의 익명 페이지가있는 VMA에서 COW가 발생하면 동일한 anon_vma에 백만 개의 익명 페이지가있는 시스템이 생성되며 각 페이지는 1000 개의 프로세스 중 하나만 매핑됩니다. 그러나 현재 rmap 코드는 모든 VMA 에 대해서 Walk 해야하므로 각 페이지에 대해 O (N) 스캔 복잡성이 발생합니다.
본질적으로 동일한 anon_vma 구조 아래에서 동일한 부모에서 시작된 모든 익명 페이지를 구성함으로써 커널은 페이지를 역 매핑해야 할 때마다 탐색 해야하는 괴물같은 자료 구조를 생성했습니다. 이로 인해 커널은 잠금을 유지하면서 페이지를 참조 할 수 없는 많은 수의 VMA를 스캔하게 되었습니다. 그 결과 AIM 벤치 마크를 실행할 때 "재앙"이 발생합니다.
Rik 의 솔루션은 각 프로세스에 대해 anon_vma 구조 를 만들고 VMA 구조 대신 이들을 함께 연결하자는 것이었어요. 이 연결은 anon_vma_chain 이라는 새로운 구조로 수행되죠.
struct anon_vma_chain {
struct vm_area_struct * vma;
struct anon_vma * anon_vma;
struct list_head same_vma;
struct list_head same_anon_vma;
};각 anon_vma_chain 항목 (AVC) 은 주어진 vma ( same_vma )와 관련된 모든 anon_vma 구조와 주어진 anon_vma 구조 ( same_anon_vma )가 다루는 영역에 속하는 모든 VMA의 두 목록을 유지해요. 구조가 복잡해지니 다이어그램ㅡㅇㄹ 보도록 하죠.
Figure. 처음에는 하나의 익명 VMA 가 있는 단일 프로세스가 있어요.
여기서 "AV"는 anon_vma 구조이고 "AVC"는 위에서 본 anon_vma_chain 구조입니다. AVC는 직접 포인터를 통해 anon_vma 및 VMA 구조 모두에 연결되요. (파란색) 연결 목록 포인터는 same_anon_vma 목록이고 (빨간색) 포인터는 same_vma 목록이구요.
이제 해당 프로세스가 분기되어 VMA가 자식에 복사된다고 상상해볼까요? 처음에는 다음과 같이 외로운 새 VMA가 있어요.
Figure, 처음에는 다음과 같이 외로운 새 VMA가 있어요.
커널은 해당 VMA를 부모의 anon_vma 구조 에 연결해야 되요! 즉, 새로운 anon_vma_chain 추가하게 되요.
Figure. 새로운 AVC가 주어진 anon_vma 구조를 참조하는 모든 VMA의 파란색 목록에 추가되었네요.
새 VMA에는 자체 anon_vma 도 필요합니다.
Figure. 새 VMA에는 자체 anon_vma 도 필요합니다.
이제 계층 구조의 다른 프로세스를 스캔 할 필요 없이 해당 페이지를 역 매핑 할 수 있습니다.
따라서 잠금 경합이 사라지고 벤치 마크를 할 때 행복하게 웃을 수 있습니다.
TODO: AVC 에 대한 이해를 쉽게 정리하자
do fork() 부터 살펴보는 Reverse Mapping Init 과정
아래는 fork 할 때 rmap 이 초기화되는 코드를 간략하게 정리해봤어요.
47: 자식 프로세스에 해당하는 VMA 를 생성해요.
57 ~ 63: fork 를 실행할 때, 결국 root 로 시작하는 AV 를 새로 생성하는지, 아니면 parent 를 따르는 하위의 AV 를 생성하는 지에 따라서 anon_vma_prepare(new VMA) 아니면 anon_vma_fork(new VMA, parent VMA) 으로 처리해요.