anon_vma chaining (v2.6.34)

Previously on rmap

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

Object-based reverse mapping (v2.6.7)

앞선 글에서 pte chaining 기반 rmap과 object-based rmap이 무엇인지 알아보았다. anonymous memory의 objrmap은  VMA 단위로 reverse mapping을 관리하며, 서로 연관된 VMA들은 같은 anon_vma의 연결 리스트 상에 존재한다. anonymous page의 struct page는 anon_vma에 관한 포인터를 저장하며, 페이지 프레임을 회수할 때는 anon_vma상에 연결된 모든 VMA를 순회하며 (페이지 프레임이 매핑된 경우) 매핑을 해제한다.

Scalability issues of original anon_vma implementation

anon_vma는 fork()로 연관된 VMA들을 anon_vma의 연결 리스트로 연결한다. 이는 Copy-On-Write로 인해 CoW break을 하기 전까지 페이지 프레임이 부모와 자식 모두의 주소 공간에 매핑되어있기 때문이다.

위 그림에서는 페이지 프레임이 프로세스 A, B, C 모두의 주소 공간에 매핑된 경우를 보여준다. 이 경우에는 그림의 페이지 프레임을 회수하려면 프로세스 A, B, C 모두의 주소 공간에서 언매핑을 해야한다.

그런데 프로세스 C가 페이지에 쓰기를 하면서 copy가 발생했다면 어떨까? 프로세스 A와 B는 여전히 페이지 프레임을 공유하겠지만, 프로세스 C는 새로 할당된 페이지 프레임을 사용할 것이다. 이 때 더 이상 다른 프로세스와 공유되지 않는 페이지 프레임을 회수할 때도, anon_vma 상의 모든 VMA를 순회해야 한다는 점이 효율적이지 못하다.

anon_vma chaining을 도입한 패치의 changelog를 보면 실제로 AIM7 벤치마크를 돌리면서 이러한 불필요한 rmap walking으로 인해 anon_vma lock의 contention이 심해서 실행 시간의 99%가 시스템 시간으로 나왔다고 한다.

여기서 anon_vma chaining의 핵심 아이디어가 나온다. 바로 프로세스마다 별도의 anon_vma를 만든 다음, 페이지 프레임이 CoW break에 의해 더 이상 공유되지 않을 때 폴트가 발생한 프로세스의 anon_vma를 가리키도록 하는 것이다.

How to maintain anon_vma per process and chain them

이제 어떻게 해야 프로세스별로 anon_vma를 관리할 수 있을지 상상해보자. 다음 그림처럼 page 1과 page 2가 모두 A, B, C 사이에 공유된다고 하자. (A는 B와 C의 부모이고, B와 C는 형제 관계이다.)

그리고 프로세스 B, C에도 별도의 anon_vma가 존재한다. 아직 copy가 일어나지 않아서 B와 C의 anon_vma를 가리키는 page는 없다. 구현상 AVC 없이 VMA가 2개 이상의 리스트에 존재할 수는 없지만 지금은 너무 깊게 생각하지 말자.

이 상태에서 프로세스 C가 page 2에 쓰기를 해서 copy가 발생한다.

새로 할당된 page 3은 이제 프로세스 C에서만 사용하므로, C의 anon_vma를 가리키게 하며, page 3을 회수할 때는 프로세스 C의 anon_vma만 순회하면 된다. 여기까지 정리해보면 anon_vma chaining에서는

1. 프로세스마다 별도로 anon_vma가 존재한다.

2. CoW가 발생하기 전에는 page가 부모의 anon_vma를 가리키지만, CoW 이후에는 페이지 폴트를 발생시킨 프로세스의 anon_vma를 가리키게 된다.

3. 나중에 페이지 프레임을 회수하려면 anon_vma마다 연관된 VMA들을 연결 리스트로 연결한 후 나중에 순회할 수 있어야 한다. 이 때, 하나의 VMA가 여러 anon_vma의 리스트에 중복해서 존재할 수 있다.

4. fork()로 VMA를 복제하거나, VMA를 split할 때는 복사/split의 대상이 되는 VMA를 참조하는 모든 anon_vma에 새로운 VMA를 추가해야 한다. 다시 말해, 3번에서 말한 것처럼 anon_vma와 연관된 모든 VMA를 순회하는 것 뿐만 아니라, VMA와 연관된 모든 anon_vma도 순회할 수 있어야 한다.

3번과 4번에 유의하여 anon_vma를 어떻게 chaining하는지 알아보자.

Step-by-step explanation

이 섹션에서는 anon_vma_chain을 처음 도입한 패치 [2]를 그림으로 설명한다. anon_vma_chain는 3번과 4번을 만족하기 위해 도입된 자료구조이다.

struct anon_vma_chain

/*
 * The copy-on-write semantics of fork mean that an anon_vma
 * can become associated with multiple processes. Furthermore,
 * each child process will have its own anon_vma, where new
 * pages for that process are instantiated.
 *
 * This structure allows us to find the anon_vmas associated
 * with a VMA, or the VMAs associated with an anon_vma.
 * The "same_vma" list contains the anon_vma_chains linking
 * all the anon_vmas associated with this VMA.
 * The "same_anon_vma" list contains the anon_vma_chains
 * which link all the VMAs associated with this anon_vma.
 */
struct anon_vma_chain {
	struct vm_area_struct *vma;
	struct anon_vma *anon_vma;
	struct list_head same_vma;   /* locked by mmap_sem & page_table_lock */
	struct list_head same_anon_vma;	/* locked by anon_vma->lock */
};

AVC는 vma와 anon_vma를 가리키며, same_vma는 이 AVC가 가리키는 VMA와 연관된 모든 anon_vma를 연결하는 AVC의 리스트이며, same_anon_vma는 이 AVC가 가리키는 anon_vma와 연관된 모든 VMA를 연결하는 AVC의 리스트이다. AVC가 어떻게 사용되는지 예시를 통해 살펴보자.

Before page fault

이전과 마찬가지로 페이지 폴트가 발생하기 전까지는 anon_vma가 없으며, 따라서 anon_vma_chain도 존재하지 않는다.

After anon_vma[_chain] populated

.

헷갈리겠지만 이 그림 부터는 양방향 연결 리스트를 양방향 화살표로 표현했다.

페이지 폴트가 발생하면 anon_vma가 생성되고, AVC가 VMA와 anon_vma를 연결한다. 이 때, 그림의 빨간색 화살표는 "VMA와 연관된 모든 anon_vma를 가리키는 AVC"의 리스트이고 (same_vma), 파란색 화살표는 "anon_vma와 연관된 모든 VMA를 가리키는 AVC"의 리스트 (same_anon_vma)이다.

anon_vma는 페이지 폴트가 발생할 때 anon_vma_prepare()에서 생성된다. anon_vma는 아예 새로 생성하거나, 인접한 VMA의 anon_vma를 사용하기도 한다. 참고로 anon_vma가 서로 다르면 VMA를 머지할 수 없기 때문에 커널은 인접한 VMA의 anon_vma를 사용할 수 있는지 먼저 확인한다.

fork()

fork()를 하면 dup_mmap()으로 부모의 VMA를 하나씩 복제하여 자식의 VMA를 만들게 된다. 이때  anon_vma_fork()를 호출해서 두 가지를 처리한다. 하나는 새로운 VMA를 기존의 VMA와 연관된 모든 anon_vma와 연결하는 것이고, 나머지 하나는 새로운 VMA를 자식의 anon_vma와 연결하는 것이다. 천천히 살펴보자.

anon_vma_fork()

/*
 * Attach vma to its own anon_vma, as well as to the anon_vmas that
 * the corresponding VMA in the parent process is attached to.
 * Returns 0 on success, non-zero on failure.
 */
int anon_vma_fork(struct vm_area_struct *vma, struct vm_area_struct *pvma)
{
	struct anon_vma_chain *avc;
	struct anon_vma *anon_vma;

	/* Don't bother if the parent process has no anon_vma here. */
	if (!pvma->anon_vma)
		return 0;

우선 부모의 VMA에 anon_vma가 아직 없다면 페이지 폴트가 나지 않은 것이므로 부모와 자식이 페이지 프레임을 공유할 일이 없다. 따라서 아무것도 하지 않는다.

	/*
	 * First, attach the new VMA to the parent VMA's anon_vmas,
	 * so rmap can find non-COWed pages in child processes.
	 */
	if (anon_vma_clone(vma, pvma))
		return -ENOMEM;

부모의 VMA가 가리키는 anon_vma가 존재한다면  부모의 VMA와 자식의 VMA 사이에 페이지 프레임을 공유할 수 있기 때문에, same_vma 리스트를 사용해서 부모의 VMA와 연관된 포함된 모든 anon_vma를 순회하면서 새로운 VMA와 연결해주어야 한다. 왜냐하면 부모의 VMA와 자식의 VMA가 공유하는 페이지 프레임을 언매핑할 때, 부모와 자식 모두의 주소 공간에서 언매핑해야 하기 때문이다. anon_vma_clone() 함수는 부모의 VMA와 연관된 모든 anon_vma에 새로운 VMA를 연결한다.

	/* Then add our own anon_vma. */
	anon_vma = anon_vma_alloc();
	if (!anon_vma)
		goto out_error;
	avc = anon_vma_chain_alloc();
	if (!avc)
		goto out_error_free_anon_vma;
	anon_vma_chain_link(vma, avc, anon_vma);
	/* Mark this anon_vma as the one where our new (COWed) pages go. */
	vma->anon_vma = anon_vma;

	return 0;

 out_error_free_anon_vma:
	anon_vma_free(anon_vma);
 out_error:
	return -ENOMEM;
}

그 다음 자식의 VMA와 자식의 anon_vma를 연결한다. 4번을 설명할 때 이야기 했듯 anon_vma가 여러 개인 상황에서는, VMA를 쪼개거나 복제할 때 기존 VMA와 연관된 모든 anon_vma에 새로운 VMA를 추가해야 한다. 이 말은, VMA와 연관된 모든 anon_vma를 순회할 수 있는 방법이 필요함을 의미한다. anon_vma_clone()에서 기존의 VMA와 연관된 모든 anon_vma를 새로운 VMA와 연결해주었기 때문에, 자식의 anon_vma만 연결해주면 된다.두 가지 예시에서 알 수 있듯, AVC는 anon_vma와 연관된 VMA를 새로 연결하거나, VMA와 연관된  anon_vma를 새로 연결할 때 사용된다.

anon_vma_clone()

/*
 * Attach the anon_vmas from src to dst.
 * Returns 0 on success, -ENOMEM on failure.
 */
int anon_vma_clone(struct vm_area_struct *dst, struct vm_area_struct *src)
{
	struct anon_vma_chain *avc, *pavc;

	list_for_each_entry(pavc, &src->anon_vma_chain, same_vma) {
		avc = anon_vma_chain_alloc();
		if (!avc)
			goto enomem_failure;
		anon_vma_chain_link(dst, avc, pavc->anon_vma);
	}
	return 0;

 enomem_failure:
	unlink_anon_vmas(dst);
	return -ENOMEM;
}

이 함수는 src의 same_vma 리스트를 순회하면서, 리스트 상의 각각의 anon_vma를 AVC를 사용해 dst와 연결한다. 이 때, anon_vma_chain_link()에 의해 anon_vma의 same_anon_vma 리스트에 새로운 VMA가 연결되고, 새로운 VMA의 same_vma 리스트에 기존 VMA와 연관된 모든 anon_vma가 연결된다.

anon_vma_chain_link()

static void anon_vma_chain_link(struct vm_area_struct *vma,
				struct anon_vma_chain *avc,
				struct anon_vma *anon_vma)
{
	avc->vma = vma;
	avc->anon_vma = anon_vma;
	list_add(&avc->same_vma, &vma->anon_vma_chain);

	spin_lock(&anon_vma->lock);
	list_add_tail(&avc->same_anon_vma, &anon_vma->head);
	spin_unlock(&anon_vma->lock);
}

anon_vma_chain_link() 함수는 AVC를 사용해 vma와 anon_vma를 연결한다. 이렇게 연결하면 same_vma 리스트를 통해 VMA와 연관된 anon_vma들을 순회할 수 있으며, same_anon_vma 리스트를 통해 anon_vma와 연관된 VMA들을 순회할 수 있다.

VMA split

약간의 이해를 돕기 위해 여기서 자식의 VMA를 쪼개보자. 어떤 VMA를 쪼갤 때는, 쪼개면서 새로 삽입되는 VMA를  기존 VMA와 연관된 모든 anon_vma (same_vma)에 연결해야 한다.

따라서 먼저 자식의 anon_vma에 새로운 VMA를 연결한다.

그 다음 부모의 anon_vma에 새로운 VMA를 연결한다. 이 과정에서 자연스럽게 새로운 VMA와 연관된 anon_vma들도 같이 연결된다.

Exclusive ownership of pages

anon_vma chaining의 목적은 프로세스 별로 anon_vma를 나누고, page가 더 이상 공유되지 않을 때 해당 프로세스를 배타적으로 소유하는 프로세스의 anon_vma로 옮겨서 불필요한 rmap walking cost를 줄이는 것이다.

 

https://lwn.net/Articles/383162

다만 이 때, 정말로 페이지를  프로세스가 배타적으로 소유하는지를 주의깊게 판단해야 한다. 실제로 이 글에서 살펴본 패치에 이로 인한 버그가 발생했었다. 예를 들어서 위 그림처럼 부모와 자식 프로세스가 어떤 페이지 프레임을 공유하고 있었다고 해보자. 그 다음 이 페이지 프레임이 swap cache에 추가된 후 부모와 자식 모두에서 언매핑이 되었다.

 

https://lwn.net/Articles/383162

그 상태에서 다시 자식과 부모가 순서대로 페이지 프레임을 매핑했다고 해보자. 자식이 먼저 매핑했으므로 __page_set_anon_rmap()에 의해 page->mapping이 자식의 anon_vma를 가리키게 된다.

 

https://lwn.net/Articles/383162

 

하지만 이 상태에서 자식 프로세스가 종료하는 경우, 아직 부모 프로세스가 페이지 프레임을 사용함에도 불구하고 page->mapping은 더 이상 존재하지 않는 anon_vma를 가리키게 된다. 이 상태에서 rmap walking을 하면 크래시가 나게 된다.

이후에 [3]과 [4]에 의해 프로세스가 확실하게 페이지 프레임을 배타적으로 소유하는 경우에만 폴트가 발생한 프로세스의 anon_vma를 사용하고, 불확실한 경우에는 가장 오래된 프로세스의 anon_vma를 사용한다.

The End

공부하면서 정신 나갈 것 같아서 만든 짤

이번 글에서는 단순하게 연관된 VMA들을 연결하는 리스트에 불과했던 anon_vma가 왜, 어떻게 프로세스별로 나뉘고 VMA와 anon_vma가 AVC에 의해 어떻게 연결 되는지를 정리했다. 이후에 same_anon_vma 리스트가 interval tree로 바뀌었는데 [5] 그것 말고는 현재까지 드라마틱한 변화는 없었던 것 같다.

References

[1] The case of the overly anonymous anon_vma 

[2] mm: change anon_vma linking to fix multi-process server scalability issue   

[3] anonvma: when setting up page->mapping, we need to pick the _oldest_ anonvma

[4] rmap: add exclusively owned pages to the newest anon_vma  

[5] [PATCH 0/7] use interval trees for anon rmap