Object-based reverse mapping (v2.6.7)

Previously on rmap

rmap (v2.5.26): pte chaining & page frame reclamation

이전 글에서는 v2.5.27에 도입된 minimal rmap을 살펴봤다. pte chain 기반 rmap은 메모리 오버헤드와 fork/exit, page mapping/unmapping의 긴 실행 시간 때문에 머지 않아 object 기반 rmap에 의해 대체되었다. [4], [5]

Some changes in pte chaining

pte chain부터 objrmap의 도입 이전까지 변화가 좀 있었는데, 자세히 다루지는 않고 커밋들을 일부 링크하겠다.

[PATCH] avoid allocating pte_chains for unshared pages  

하나의 pte만 페이지 프레임을 참조하는 경우 pte_chain을 할당하지 않도록 하는 패치 (PG_direct 플래그로 두 가지 케이스를 구분)

[PATCH] rmap pte_chain speedup and space saving  

pte_chain 한 개당 pte를 여러 개씩 저장해서 탐색 속도를 높이고 메모리를 절약하는 패치

[PATCH] speed up rmap searching

pte_chain의 next 필드에 non-null entry의 index를 저장해서 탐색 속도를 빠르게 하는 패치

from PTE-based rmap to Object-based rmap

"Object-based rmap"이란, page frame을 매핑하는 모든 pte들에 대해서 reverse mapping을 관리하지 않고, page frame이 속한 객체 (Object) 단위로 reverse mapping을 관리한다는 의미이다. 

pte chaining in minimal rmap implementation

.

objrmap for file pages

file page는 디스크 상의 파일 (inode)라는 객체와 연관되어있다. 따라서 page frame에 대한 pte들이 아니라, page->mapping이 가리키는 address_space가 이 address_space를 참조하는 모든 VMA들을 알고 있으므로 pte chain을 사용하지 않아도 reverse mapping을 알아낼 수 있다. [1] address_space는 이 파일을 매핑하는 VMA들을 i_mmap 리스트(for private mapping)와 i_mmap_shared (for shared mapping) 리스트로 관리한다.

Object-based reverse mapping은 page frame마다 매핑된 모든 pte에 대한 reverse mapping을 관리하지 않기 때문에 메모리 오버헤드가 비교적 적다는 장점이 있다.

다만 그림처럼 linked list에서 얼마 지나지 않아 i_mmap_shared와 i_mmap 필드는 linked list가 아닌 radix priority search tree로 변경되어 [6] [9] VMA의 시작과 끝을 범위로 하는 interval에 대하여 해당 interval에 속하는 VMA들을 O(log2(N)) 안에 찾을 수 있게 되었다.

objrmap for anon pages

file page는 inode라는 객체와 연관되어있다. 그렇다면 anon page는 어떤 객체와 연관지어야할까? 프로세스의 주소 공간에 VMA가 속하고, 그 VMA가 나타내는 가상 주소 공간에 페이지 프레임이 매핑되므로 프로세스 주소 공간과 메모리를 나타내는 mm_struct 혹은 주소 공간 중 일부인 VMA를 나타내는 vm_area_struct와 연관지을 수 있겠다.

실제로 각각 mm_struct와 vm_area_struct를 anon page와 연관된 객체로 취급하는 anonmm과 anon_vma가 서로 경쟁을 하다가  anon_vma로 굳어지게 되었다. [3]

anonmm

Hugh의 anonmm은 fork()로 연관된 mm_struct들을 연결 리스트로 묶어서 어떤 page가 매핑되었을 수 있는 mm_struct들을 탐색할 수 있도록 한다. 이 방식은 page와 연관된 객체를 mm_struct로 간주하는 Object-based rmap이라고 할 수 있다.

/*
 * struct anonmm: to track a bundle of anonymous memory mappings.
 *
 * Could be embedded in mm_struct, but mm_struct is rather heavyweight,
 * and we may need the anonmm to stay around long after the mm_struct
 * and its pgd have been freed: because pages originally faulted into
 * that mm have been duped into forked mms, and still need tracking.
 */
struct anonmm {
	atomic_t	 count;	/* ref count, including 1 per page */
	spinlock_t	 lock;	/* head's locks list; others unused */
	struct mm_struct *mm;	/* assoc mm_struct, NULL when gone */
	struct anonmm	 *head;	/* exec starts new chain from head */
	struct list_head list;	/* chain of associated anonmms */
};

anonmm의 역할은 사실상 fork()로 연관되는 mm_struct를 연결 리스트로 이어주는 것이 전부다.

위 다이어그램은 fork()로 복제된 mm_struct가 기존의 mm_struct와 anonmm에 의해 연결되는 것을 그림으로 보여준다. 처음 exec()를 호출했을 때는 하나의 프로세스만 존재하지만, fork()를 하게 되면서 새로운 프로세스의 anonmm이 연결 리스트에 추가된다. anonmm->head는 처음 exec()를 한 프로세스를 가리킨다.

프로세스가 할당한 page는 page->mapping 필드가 해당 프로세스의 anonmm을 가리킨다. 어떤 페이지 프레임이 매핑된 mm_struct는 anonmm 연결 리스트를 순회하면서 탐색할 수 있다. 다만, anonmm 리스트로 연결된 모든 mm_struct가 페이지 프레임을 매핑하고 있지는 않을 수 있다. fork() 이후에 페이지 프레임을 할당했냐, 이전에 할당했냐에 따라서 달라진다.

또한 한 가지 참고할 점은, 프로세스가 중간에 사라지더라도 anonmm은 그대로 남는다는 것이다. 왜냐하면 페이지 프레임을 할당한 프로세스가 종료된 이후에도 다른 프로세스가 페이지 프레임을 사용할 수 있기 때문이다. 따라서 anonmm의 count 필드가 page->mapping 필드로 anonmm을 참조하는 횟수를 관리하고, 이 count가 0이 된 경우에만 anonmm을 제거한다.

페이지 프레임이 매핑된 pte들을 찾으려면 mm_struct의 페이지 테이블을 탐색해서 이 mm_struct가 페이지 프레임을 매핑하는지 확인해봐야 한다. 그러려면 페이지 프레임이 매핑된 가상 주소가 무엇인지 알아야 하는데, page->index 필드에 페이지 프레임이 매핑된 가상 주소가 저장된다. 자, 여기서 anonmm의 단점이 드러난다. 어떤 페이지 프레임이 2개 이상의 프로세스의 주소 공간에 매핑되어있고, 둘 중 하나의 프로세스에서 mremap() 등의 시스템 호출로 매핑된 가상 주소를 변경하면 page->index에 저장된 가상 주소에 페이지 프레임이 매핑되어있지 않을 수 있다. 다시 말해 anonmm의 설계는 어떤 페이지 프레임은 fork()로 연관된 프로세스들에 대하여 모두 같은 가상 주소로 매핑되어있다는 가정 하에서만 의미가 있다.

anonmm은 이 문제를 해결하기 위해 일반적으로 fork()로 인해 공유된 페이지 프레임에 대해 쓰기가 발생했을 때 Copy-On-Write가 발생하는 것과 달리 mremap()을 할 때 일찍 copy를 수행한다.

anon_vma

anon_vma는 anonmm과는 달리 VMA를 page와 연관된 객체로 본다. anonmm에서와 비슷하게 page->mapping 필드가anon_vma라는 자료구조를 가리킨다. 다만 anon_vma는 anonmm에서와 다르게 VMA마다 하나씩 존재하는 것이 아니며, VMA를 연결하는 이중 연결 리스트를 관리한다.

anon_vma는 anonmm과 유사하게 page->index 필드에 페이지 프레임이 매핑된 절대적인 가상 주소를 페이지 단위로 기록하지만, mremap으로 VMA의 시작 주소가 바뀌더라도 VMA들이 링크드 리스트로 연결되어 있으므로 찾는데 문제가 없으며, VMA가 이동하더라도 페이지 프레임이 어느 가상 주소에 매핑되는지 알 수 있다.

한 가지 특이한 점은 anon_vma가 도입되면서 anonymous VMA의 vm_pgoff 필드에 (vma->vm_start) >> PAGE_SHIFT를 저장하게 되었다는 것이다. 원래 vm_pgoff 필드는 file VMA의 앞 또는 뒤에 다른 file VMA를 머지할 때, VMA의 파일 내 오프셋이 연속적인 두 VMA를 머지하려고 확인하는 필드였는데, 이제 두 anonymous VMA의 가상 주소가 연속적인 경우를 확인하는 데에도 쓰이게 되었다.

anon_vma allocation

페이지 프레임은 프로세스 주소 공간에 매핑될 때 항상 연관된 anon_vma가 존재해야 한다. 따라서 일반적으로 새로 할당된 페이지 프레임은 기존의 VMA가 참조하던 anon_vma를 사용하거나 새로운 anon_vma를 할당하며, 페이지 프레임과 anon_vma를 연결짓는다. VMA가 처음 만들어질 때는 anon_vma가 없을 수 있는데, anonymous page에 대해 page fault가 날 때는 anon_vma를 할당하거나 기존의 anon_vma를 재사용하게 된다. 첫 페이지 폴트가 일어나기 전까지 anon_vma를 할당하지 않는 건 미리 anon_vma를 할당해서 나중에 VMA merging을 하기 어려워지는 경우를 위한 것 같다. 왜냐하면 서로 다른 anon_vma를 가리키는 VMA를 머지할 수는 없기 때문이다.

Sharing page frames via fork()

VMA는 fork() 혹은 split/merge를 통해 연관지어진다. fork()를 해서 부모의 VMA로부터 자식의 VMA가 복사될 때는, 자식의 VMA가 부모의 VMA와 같은 anon_vma를 가리켜서 하나의 페이지 프레임이 여러 프로세스의 VMA에 매핑된 경우를 rmap walking으로 탐색할 수 있다.

VMA splitting & merging

fork() 말고도 VMA를 쪼개거나 병합할 때, VMA들은 같은 anon_vma를 사용하도록 연관지어진다.

VMA splitting

VMA를 split할 때는, split으로 인해 새로 생성되는 VMA가 기존의 anon_vma를 사용하도록 한다. 예를 들어 아래 그림에서 VMA A와 B에 모두 포함된 페이지 프레임들에 대하여 rmap walking을 할 때, VMA B가 split된 이후에도 VMA A와 같은 anon_vma 상의 리스트에 존재해야 rmap walking으로 찾을 수가 있다.

 

VMA merging

반대로 VMA를 merging할 때는 머지가 되는 두 VMA가 같은 anon_vma를 가리키거나, 둘다 anon_vma가 없거나, 둘 중 하나가 anon_vma가 없어야 한다.

예를 들어 위 그림에서 A, B, C가 같은 anon_vma를 가리키고, D, E가 같은 anon_vma를 가리킨다고 해보자. (A와 D가 같은 anon_vma를 가리키는지는 아직 모른다.)

A와 D를 머지한다면, E에 포함된 페이지 프레임에 대해서 rmap walking을 할 때 D를 찾을 수 있어야 하고, B나 C에 포함된 페이지 프레임을 rmap walking을 할 때 A를 찾을 수 있어야 한다. 따라서 A와 D를 머지하려면 적어도 둘 중 하나가 어떤 anon_vma도 가리키지 않거나, 같은 anon_vma를 가리켜야 한다. 서로 다른 anon_vma를 가리키는 두 VMA는 머지할 수 없다.

rmap walking in anon_vma

rmap walking은 try_to_unmap_anon()이나 try_to_unmap_file()이 페이지 프레임을 프로세스 주소 공간에서 언매핑할 때 수행된다.

vma_address()

/*
 * At what user virtual address is page expected in vma?
 */
static inline unsigned long
vma_address(struct page *page, struct vm_area_struct *vma)
{
	pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
	unsigned long address;

	address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
	if (unlikely(address < vma->vm_start || address >= vma->vm_end)) {
		/* page should be within any vma from prio_tree_next */
		BUG_ON(!PageAnon(page));
		return -EFAULT;
	}
	return address;
}

anon_vma 방식에서는 page->index에 페이지 프레임이 매핑된 가상 주소가 페이지 단위로 저장되며, vma->vm_pgoff에 VMA의 시작 주소를 페이지 단위로 저장한다.

어떤 page frame이 VMA에 매핑된 주소는 vma_address()로 함수로 구할 수 있는데, anon_vma를 head로 하는 연결 리스트의 모든 VMA에 대하여 (vma->vm_start + ((page->index - vma->vm_pgoff)) << PAGE_SHIFT)가 VMA의 가상 주소 범위에 포함되는지 확인한다. 위 식을 사용하면 VMA가 이동한 경우에도 이동한 VMA 상에 페이지 프레임이 매핑된 주소를 구할 수 있다. vma_address()로 가상 주소를 구했다면, page table walking을 통해 해당 가상 주소가 매핑된 pte를 찾아서 해당 주소가 커널이 언매핑하려는 페이지 프레임을 매핑하는지 확인한다.

try_to_unmap_one()

try_to_unmap_one()은 VMA가 나타내는 가상 주소 공간에 페이지 프레임이 매핑된 경우 언매핑을 시도한다.

/*
 * Subfunctions of try_to_unmap: try_to_unmap_one called
 * repeatedly from either try_to_unmap_anon or try_to_unmap_file.
 */
static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma)
{
	struct mm_struct *mm = vma->vm_mm;
	unsigned long address;
	pgd_t *pgd;
	pmd_t *pmd;
	pte_t *pte;
	pte_t pteval;
	int ret = SWAP_AGAIN;

	if (!mm->rss)
		goto out;
	address = vma_address(page, vma);
	if (address == -EFAULT)
		goto out;

우선 페이지 프레임이 매핑된 가상 주소가 이 VMA가 나타내는 가상 주소 공간에 포함되는지를 먼저 확인한다. 만약 포함되지 않는다면 SWAP_AGAIN을 반환해 다음 VMA를 스캔하도록 한다.

	/*
	 * We need the page_table_lock to protect us from page faults,
	 * munmap, fork, etc...
	 */
	if (!spin_trylock(&mm->page_table_lock))
		goto out;

	pgd = pgd_offset(mm, address);
	if (!pgd_present(*pgd))
		goto out_unlock;

	pmd = pmd_offset(pgd, address);
	if (!pmd_present(*pmd))
		goto out_unlock;

	pte = pte_offset_map(pmd, address);
	if (!pte_present(*pte))
		goto out_unmap;

	if (page_to_pfn(page) != pte_pfn(*pte))
		goto out_unmap;

page table walking을 한 다음 pte가 가리키는 pfn이 우리가 unmap하려는 페이지 프레임과 일치하는지도 확인한다. 일치하지 않는다면 SWAP_AGAIN을 반환해 다음 VMA를 스캔하도록 한다.

	/*
	 * If the page is mlock()d, we cannot swap it out.
	 * If it's recently referenced (perhaps page_referenced
	 * skipped over this mm) then we should reactivate it.
	 */
	if ((vma->vm_flags & (VM_LOCKED|VM_RESERVED)) ||
			ptep_test_and_clear_young(pte)) {
		ret = SWAP_FAIL;
		goto out_unmap;
	}

페이지 프레임이 이 VMA에 매핑된 것이 맞는다면, 언매핑을 해야할지 판단한다. VMA가 mlock()된 경우나 pte를 확인해봤는데 최근에 접근된 경우, SWAP_FAIL을 반환해 이 페이지 프레임에 대한 rmap walking을 중단하도록 한다.

	/* Nuke the page table entry. */
	flush_cache_page(vma, address);
	pteval = ptep_clear_flush(vma, address, pte);

	/* Move the dirty bit to the physical page now the pte is gone. */
	if (pte_dirty(pteval))
		set_page_dirty(page);

언매핑을 할 수 있다면 캐시와 TLB를 flush하고, 디스크에 writeback 된 후에 회수될 수 있도록 PG_dirty 비트를 설정한다.

	if (PageAnon(page)) {
		swp_entry_t entry = { .val = page->private };
		/*
		 * Store the swap location in the pte.
		 * See handle_pte_fault() ...
		 */
		BUG_ON(!PageSwapCache(page));
		swap_duplicate(entry);
		set_pte(pte, swp_entry_to_pte(entry));
		BUG_ON(pte_file(*pte));
	}

anon page인 경우 swap space에서 해당하는 페이지의 reference를 증가시킨 후, pte에 swap space 상의 위치를 기록한다.

	mm->rss--;
	BUG_ON(!page->mapcount);
	page->mapcount--;
	page_cache_release(page);

out_unmap:
	pte_unmap(pte);
out_unlock:
	spin_unlock(&mm->page_table_lock);
out:
	return ret;
}

그 다음 mapcount, rss를 갱신한 후 함수를 반환한다.

try_to_unmap_anon()

try_to_unmap_anon()은 anon_vma의 링크드 리스트를 순회하며 각각의 VMA에 대하여 try_to_unmap_one()으로 언매핑을 시도한다.

static inline int try_to_unmap_anon(struct page *page)
{
	struct anon_vma *anon_vma = (struct anon_vma *) page->mapping;
	struct vm_area_struct *vma;
	int ret = SWAP_AGAIN;

	spin_lock(&anon_vma->lock);
	BUG_ON(list_empty(&anon_vma->head));
	list_for_each_entry(vma, &anon_vma->head, anon_vma_node) {
		ret = try_to_unmap_one(page, vma);
		if (ret == SWAP_FAIL || !page->mapcount)
			break;
	}
	spin_unlock(&anon_vma->lock);
	return ret;
}

try_to_unmap_file()

try_to_unmap_file()은 파일이 매핑된 i_mmap 상의 모든 VMA에 대하여 try_to_unmap_one()으로 페이지 프레임의 언매핑을 시도한 후, 페이지 프레임이 nonlinear mapping에 포함된 경우도 처리한다. nonlinar mapping은 여기서 자세히 다루지는 않고 마지막에 간략하게 설명한다.

/**
 * try_to_unmap_file - unmap file page using the object-based rmap method
 * @page: the page to unmap
 *
 * Find all the mappings of a page using the mapping pointer and the vma chains
 * contained in the address_space struct it points to.
 *
 * This function is only called from try_to_unmap for object-based pages.
 *
 * The spinlock address_space->i_mmap_lock is tried.  If it can't be gotten,
 * return a temporary error.
 */
static inline int try_to_unmap_file(struct page *page)
{
	struct address_space *mapping = page->mapping;
	pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
	struct vm_area_struct *vma = NULL;
	struct prio_tree_iter iter;
	int ret = SWAP_AGAIN;
	unsigned long cursor;
	unsigned long max_nl_cursor = 0;
	unsigned long max_nl_size = 0;
	unsigned int mapcount;

	if (!spin_trylock(&mapping->i_mmap_lock))
		return ret;

	while ((vma = vma_prio_tree_next(vma, &mapping->i_mmap,
					&iter, pgoff, pgoff)) != NULL) {
		ret = try_to_unmap_one(page, vma);
		if (ret == SWAP_FAIL || !page->mapcount)
			goto out;
	}
	/* ... nonlinear mapping unmap하는 부분 생략됨 ... */
out:
	spin_unlock(&mapping->i_mmap_lock);
	return ret;
}

nonlinear file mappings

이제는 중요한 내용은 아니지만 기록을 위해 적어본다.

예전에 32비트에서는 주소 공간이 크지 않아서 아주 큰 파일을 mmap()으로 매핑하기가 쉽지 않았다. 파일 전체를 가상 주소 공간에 매핑하자니 주소 공간이 너무 작고, 필요한 곳만 띄엄띄엄 매핑하자니 VMA의 수가 너무 많아진다.

그래서 원래는 file VMA에 포함된 모든 페이지 프레임들은 파일 상에서 연속적이어야 했지만, 오프셋이 연속적이지 않은 페이지 프레임들을 연속적인 가상 주소에 매핑할 수 있는 remap_file_pages() system call이 추가되었다.

다만 nonlinear mapping은 큰 단점이 있는데, VMA 내에서의 페이지 프레임의 오프셋이 VMA와 페이지 프레임이 매핑된 가상 주소와 연관되어있다는 가정이 틀리기 때문이다. 따라서 일반적인 방법으로 rmap walking을 할 수 없으며 모든 nonlinear mapping을 탐색하지 않는 한 어떤 페이지 프레임이 어떤 VMA에 속하는지 알기 어렵다.

64비트로 넘어가면서 거대한 파일을 매핑해야 하는 32비트 환경이 덜 중요해졌기 때문에, 2014년에 remap_file_pages()는 nonlinear mapping을 새로운 VMA를 삽입하는 방식으로 emulation 하도록 바뀌었으며 이 시스템 호출은 deprecated 되었다. [7] [8]

References

[1] Full updated partial object-based rmap

Dave McCraken의 file page에 대한 object -based rmap 패치. 이 상태로 메인라인으로 바로 가지는 않았지만 이후에 2.6.6-mm4에 포함되었다.

[2] The object-based reverse-mapping VM, Jonathan Corbet, 2003 

Dave McCraken의 file page에 대한 object-based rmap을 다룬 글

[3] The status of object-based reverse mapping, 2004  

anonymous page에 대한 object-based rmap을 다룬 LWN.net 글

[4] 2.6.6-mm4, Andrew Morton, 2004 

anonymous page에 object-based rmap이 머지된 버전이다. Hugh Dickins의 object-based rmap 시리즈는 40여개의 패치들로 이루어진 시리즈였고, 그 중 대부분이 머지되었다. (이 시리즈에 대한 메일링 리스트 아카이브는 못 찾았다.)

[5] Object-based Reverse Mapping, Dave McCraken, 2004  

anon / file page에 대하여 pte chain에서 object-based rmap으로 넘어가기까지의 과정을 정리한다.

[6] [Linux] priority search tree (1)

[7] [PATCHv2 0/2] remap_file_pages() decommission

[8] [PATCH 00/38] mm: remove non-linear mess 

[9] [PATCH] rmap 17: real prio_tree