본문 바로가기
Kernel/Memory Management

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

by hyeyoo 2022. 12. 26.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

Introduction

What is Reverse Mapping?

가상 메모리는 페이지 테이블을 사용해서 가상 주소를 물리 주소로 변환한다. 페이지 테이블은 프로세스별로 존재하며, 각각의 프로세스는 독립적인 가상 주소공간을 갖는다. MMU는 가상 주소를 물리 주소로(forward mapping) 변환하지만, 운영체제는 반대로 어떤 페이지 프레임이 어떤 프로세스의 가상 주소 공간에 매핑되어있는지(reverse mapping)를 알아야 하는 경우가 있다.

구체적으로 어떤 경우에 reverse mapping이 필요한가 하면 swapout/pageout, migration, compaction을 할때 해당 페이지프레임을 사용하고 있는 프로세스의 pte를 빠르게 찾거나 수정하기 위해 필요하다.

예전 (Linux v2.4)에는 어떤 페이지 프레임을 매핑하는 pte를 찾으려면 모든 프로세스의 가상 주소 공간을 탐색했어야했다. 이후 v2.5.27에는 reverse mapping이 구현되어 (메모리 오버헤드는 늘었지만) 탐색을 좀 더 효율적으로 할 수 있게 되었다. 다만 이 글에서 다루는 PTE-based reverse mapping은 메모리 오버헤드가 적지 않아서 오래 가지 않아 object-based reverse mapping으로 대체되었다.

Naive approach: pte chaining (v2.5.27)

이 글은 minimal rmap이 도입된 commit c48c43e6ed41a ("minimal rmap")을 기준으로 코드를 설명한다.

Changelog

rmap의 초기 구현 [Rik02]의 changelog의 일부를 읽어보자.

Basically,
기본적으로,

before: When the page reclaim code decides that is has scanned too many
unreclaimable pages on the LRU it does a scan of process virtual
address spaces for pages to add to swapcache.  ptes pointing at the
page are unmapped as the scan proceeds.  When all ptes referring to a
page have been unmapped and it has been written to swap the page is
reclaimable.

전:
페이지 회수 코드가 너무 많은 LRU 상의 unreclaimable 페이지들을 스캔했다면,
페이지 회수 코드는 swapcache에 추가할 페이지들을 찾기 위해 프로세스
가상 주소 공간을 스캔한다. 페이지를 가리키는 pte들은 스캔이 진행됨에 따라
unmap된다. 모든 pte가 unmap되고 페이지가 스왑 영역에 기록되면 페이지를 회수할 수 있게 된다.

after: When an anonymous page is encountered on the tail of the LRU we
use the rmap to see if it hasn't been referenced lately.  If so then
add it to swapcache.  When the page is again encountered on the LRU, if
it is still unreferenced then try to unmap all ptes which refer to it
in one hit, and if it is clean (ie: on swap) then free it.

후:
(스캔을 하다가) LRU의 끝에서 익명 페이지를 만나면 rmap으로 이 페이지가 최근에
접근되었는지를 확인한다. 만약 접근되지 않았다면 페이지를 swapcache에 추가한다.
만약 LRU를 스캔하다가 페이지를 다시 만났고, 아직도 reference되지 않았다면
모든 pte를 한 번에 unmap한 후, 페이지가 clean한 상태라면 (e.g. swap에 기록되에) 회수한다.

The rest of the VM - list management, the classzone concept, etc
remains unchanged.

그 외의 부분들 - 리스트 관리, classzone 개념, 기타 등등은 바뀌지 않았다.

Data structure

메인라인에 처음 도입된 rmap의 구현은 단순히 pte에 대한 포인터들을 연결 리스트로 연결했다.

pte chain은 새로운 페이지를 프로세스 주소 공간에 추가하거나, 이미 프로세스가 사용 중인데 페이지를 참조하는 페이지 테이블이 늘어난 경우 추가된다. 반대로 페이지를 해제하거나 이 페이지를 참조하는 페이지 테이블의 수가 줄어든 경우 pte chain이 제거된다.

Implementation of minimal rmap

[Rik02]에서 추가한 함수들을 일부 살펴보자.

page_referenced()

/**
 * page_referenced - test if the page was referenced
 * @page: the page to test
 *
 * Quick test_and_clear_referenced for all mappings to a page,
 * returns the number of processes which referenced the page.
 * Caller needs to hold the pte_chain_lock.
 */
int page_referenced(struct page * page)
{
        struct pte_chain * pc;
        int referenced = 0;

        if (TestClearPageReferenced(page))
                referenced++;

        /* Check all the page tables mapping this page. */
        for (pc = page->pte_chain; pc; pc = pc->next) {
                if (ptep_test_and_clear_young(pc->ptep))
                        referenced++;
        }
        return referenced;
}

page_referenced() 함수는 PG_referenced 플래그 체크하고, pte chain을 순회하면서 몇 개의 pte에서 pte_young()이 참을 반환하는지를 센다. (pte_young()을 확인한 후 clear한다.)

pte_chain locking

pte chain에 배타적으로 접근하려면 락이 필요한데, pte chain의 구현에서는 PG_chainlock이라는 page flag를 만든 후, TAS 기반 bit spinlock을 사용했다.

#define PG_chainlock            16      /* lock bit for ->pte_chain */

/*
 * inlines for acquisition and release of PG_chainlock
 */
static inline void pte_chain_lock(struct page *page)
{
        /*
         * Assuming the lock is uncontended, this never enters
         * the body of the outer loop. If it is contended, then
         * within the inner loop a non-atomic test is used to
         * busywait with less bus contention for a good time to
         * attempt to acquire the lock bit.
         */
        preempt_disable();
        while (test_and_set_bit(PG_chainlock, &page->flags)) {
                while (test_bit(PG_chainlock, &page->flags))
                        cpu_relax();
        }
}

static inline void pte_chain_unlock(struct page *page)
{
        clear_bit(PG_chainlock, &page->flags);
        preempt_enable();
}

page_add_rmap(), page_remove_rmap()

page_add_rmap(), page_remove_rmap()은 pte_chain_lock/unlock()을 사용하여 pte chain을 새로 추가한다. 링크드 리스트에 pte chain 삽입/삭제하는 것 외에 특별한 내용은 없으므로 분석은 생략한다.

Changes in page frame reclamation

v2.4.22의 page frame reclamation과 swapout 방식은 아래 글을 참고하길 바란다. 이 글에서는 rmap에 의해 변경된 부분만 다룬다. v2.4.22와 v2.5.27의 PFRA는 그렇게 크게 차이가 나지는 않는다.

 

Page Frame Reclamation and Swapout (v2.4.22)

Introduction 언젠가 swap, PFRA, rmap에 대해서도 글을 써야겠다고 생각하고 있었는데, 모두 복잡하다보니 어디서부터 시작할지가 항상 고민이었다. 결국 가장 문서화가 잘 되어있는 Understanding the Linux

hyeyoo.com

reverse mapping 이전에는 userspace에 매핑된 어떤 페이지 프레임을 회수하려면 모든 프로세스의 주소 공간을 조금씩 차례대로 unmap하면서 모든 매핑이 해제되기를 기다려야했다. 하지만 reverse mapping을 사용하면 어떤 페이지 프레임의 pte들이 어디에 있는지 바로 알 수 있기 때문에, 회수 알고리즘에도 변화가 생긴다.

Don't traverse the whole address space anymore

v2.4.22에서의 swap out function call graph

기존에는 swap_out() 함수에서 아래 그림처럼 swap_mm의 페이지 테이블을 스캔하면서 unmap을 하고, swap_out_add_to_swap_cache()로 페이지 프레임을 스왑 캐시에 추가했다.

프로세스들의 주소 공간을 순서대로 스캔하는 모습

 

하지만 rmap이 추가되면서 swap_out()과 관련된 함수는 아예 사라지고, shrink_cache()에서 익명 페이지 프레임인 경우 add_to_swap()으로 먼저 스왑 캐시에 페이지 프레임을 추가한 후, try_to_unmap()으로 페이지 프레임을 페이지 테이블에서 언매핑을 시도하도록 바뀌었다. rmap 덕분에 이전처럼 모든 프로세스의 페이지 테이블을 전부 스캔할 필요 없이 빠르게 페이지 프레임을 언매핑할 수 있다.

 

Changes in shrink_cache()

코드를 보기 전 우선 v2.4.22부터 v2.5.27까지의 변경 사항을 일부 살펴보자.

- 페이지 프레임의 writeback에서의 locking이 바뀌었다. 원래는 writeout 중에 페이지 프레임은 PageLocked()가 참이었는데, 이제 writeout중인 페이지 프레임은 PG_locked 대신  PG_writeback 플래그가 켜진다. commit a2bcb3a084f4 ("[PATCH] page writeback locking update") - 단, swapout중인 페이지 프레임은 그대로 PG_locked 플래그를 사용한다.

- PG_writeback으로 페이지 프레임이 writeout 중인지를 알 수 있어서 PG_launder 비트가 사라졌다. commit a25364526006 ("[PATCH] remove PG_launder") 

- page->buffers 필드가 page->private으로 추상화되었다. commit 9855b4a17d61 ("[PATCH] page->buffers abstraction") 이제 PagePrivate() or page_has_buffers() 매크로로 확인해야한다.

v2.5.27의 shrink_cache()를 flow chart로 그려보면 다음과 같다.

shrink_cache() 

static int
shrink_cache(int nr_pages, zone_t *classzone,
		unsigned int gfp_mask, int priority, int max_scan)
{
	struct list_head * entry;
	struct address_space *mapping;

	spin_lock(&pagemap_lru_lock);
	while (--max_scan >= 0 &&
			(entry = inactive_list.prev) != &inactive_list) {
		struct page *page;
		int may_enter_fs;

while문에서는 pagemap_lru_lock을 획득한 후, inactive list에서 max_scan개의 페이지 프레임을 스캔하거나 inactive list의 head에 도달하기 전까지 페이지 프레임들을 스캔한다.

		if (need_resched()) {
			spin_unlock(&pagemap_lru_lock);
			__set_current_state(TASK_RUNNING);
			schedule();
			spin_lock(&pagemap_lru_lock);
			continue;
		}

LRU scan에 너무 많은 시간을 쏟는 걸 방지하기 위해 중간에 sleep을 할 필요가 있다면 sleep한 후 다시 스캔한다.

		page = list_entry(entry, struct page, lru);

		if (unlikely(!PageLRU(page)))
			BUG();
		if (unlikely(PageActive(page)))
			BUG();

shrink_cache()는 inactive list를 스캔하기 때문에 LRU 리스트 상의 페이지 프레임에서 켜져있어야할 PG_lru 플래그가 없거나, active list 페이지 프레임에만 켜져있는 PG_active 플래그가 켜져있다면 BUG()를 호출한다.

		list_del(entry);
		list_add(entry, &inactive_list);

우선 entry를 inactive list의 head로 추가해, 회수에 실패하더라도 다음 스캔에서 만날 수 있도록 한다.

		/*
		 * Zero page counts can happen because we unlink the pages
		 * _after_ decrementing the usage count..
		 */
		if (unlikely(!page_count(page)))
			continue;

		if (!memclass(page_zone(page), classzone))
			continue;

페이지 프레임이 해제되고 있는 경우에는 reference count가 0인 페이지 프레임을 만날 수 있기 때문에 이 경우에는 간단하게 스킵해준다. 페이지 프레임의 zone이 회수하려는 zone과 다른 경우에도 스킵한다.

		/*
		 * swap activity never enters the filesystem and is safe
		 * for GFP_NOFS allocations.
		 */
		may_enter_fs = (gfp_mask & __GFP_FS) ||
				(PageSwapCache(page) && (gfp_mask & __GFP_IO));

		/*
		 * IO in progress? Leave it at the back of the list.
		 */
		if (unlikely(PageWriteback(page))) {
			if (may_enter_fs) {
				page_cache_get(page);
				spin_unlock(&pagemap_lru_lock);
				wait_on_page_writeback(page);
				page_cache_release(page);
				spin_lock(&pagemap_lru_lock);
			}
			continue;
		}

페이지 프레임에 대해서 writeout이 진행 중이고, 파일 시스템 연산이 가능한 경우 writeout이 끝날 때까지 기다린다.

		if (TestSetPageLocked(page))
			continue;

		if (PageWriteback(page)) {	/* The non-racy check */
			unlock_page(page);
			continue;
		}

페이지 프레임에 대하여 TestSetPageLocked()로 락을 획득하고, 실패한 경우 다음 페이지로 넘어간다.

앞에서 PageWriteback()으로 writeout이 진행 중인지 확인했지만 race를 피하기 위해, 락을 획득한 후 한번 더 확인해준다.

		/*
		 * The page is in active use or really unfreeable. Move to
		 * the active list.
		 */
		pte_chain_lock(page);
		if (page_referenced(page) && page_mapping_inuse(page)) {
			del_page_from_inactive_list(page);
			add_page_to_active_list(page);
			pte_chain_unlock(page);
			unlock_page(page);
			continue;
		}

page_mapping_inuse()는 페이지 프레임이 사용자 주소 공간에 매핑된 경우를 의미하며, page_referenced()는 PG_referenced 플래그와 페이지 프레임을 매핑하는 pte를 통해 페이지 프레임이 접근되었는지를 확인한다. 따라서 위 코드는 페이지 프레임이 사용자 주소 공간에 매핑되어있고, 최근에 접근된 경우에 페이지 프레임을 active list로 옮긴다.

		/*
		 * Anonymous process memory without backing store. Try to
		 * allocate it some swap space here.
		 *
		 * XXX: implement swap clustering ?
		 */
		if (page->pte_chain && !page->mapping && !PagePrivate(page)) {
			page_cache_get(page);
			pte_chain_unlock(page);
			spin_unlock(&pagemap_lru_lock);
			if (!add_to_swap(page)) {
				activate_page(page);
				unlock_page(page);
				page_cache_release(page);
				spin_lock(&pagemap_lru_lock);
				continue;
			}
			page_cache_release(page);
			spin_lock(&pagemap_lru_lock);
			pte_chain_lock(page);
		}

만약 페이지 프레임의 pte chain이 있는데, mapping이 없고 연관된 버퍼도 없다면 스왑 캐시에 속하지 않은 페이지 프레임을 의미하므로 add_to_swap()으로 스왑 캐시에 넣어준다. 만약 스왑 캐시에 넣을 수 없다면 어차피 회수가 불가능하므로 active list로 옮겨준다. (activate_page())

		/*
		 * The page is mapped into the page tables of one or more
		 * processes. Try to unmap it here.
		 */
		if (page->pte_chain) {
			switch (try_to_unmap(page)) {
				case SWAP_ERROR:
				case SWAP_FAIL:
					goto page_active;
				case SWAP_AGAIN:
					pte_chain_unlock(page);
					unlock_page(page);
					continue;
				case SWAP_SUCCESS:
					; /* try to free the page below */
			}
		}
		pte_chain_unlock(page);

페이지 프레임이 사용자 주소 공간에 매핑되어있다면 try_to_unmap()으로 언매핑을 시도한다. SWAP_ERROR/SWAP_FAIL이 반환된 경우에는 페이지 프레임을 active list로 옮기고, SWAP_AGAIN이 반환되면 다음에 이 페이지 프레임을 만났을 때 다시 시도한다. SWAP_SUCCESS가 반환되면 아래 부분에서 writeout 혹은 회수를 시도한다.

		mapping = page->mapping;

		if (PageDirty(page) && is_page_cache_freeable(page) &&
				page->mapping && may_enter_fs) {
			/*
			 * It is not critical here to write it only if
			 * the page is unmapped beause any direct writer
			 * like O_DIRECT would set the page's dirty bitflag
			 * on the physical page after having successfully
			 * pinned it and after the I/O to the page is finished,
			 * so the direct writes to the page cannot get lost.
			 */
			int (*writeback)(struct page *, int *);
			const int nr_pages = SWAP_CLUSTER_MAX;
			int nr_to_write = nr_pages;

			writeback = mapping->a_ops->vm_writeback;
			if (writeback == NULL)
				writeback = generic_vm_writeback;
			page_cache_get(page);
			spin_unlock(&pagemap_lru_lock);
			(*writeback)(page, &nr_to_write);
			max_scan -= (nr_pages - nr_to_write);
			page_cache_release(page);
			spin_lock(&pagemap_lru_lock);
			continue;
		}

.페이지 프레임에 PG_dirty 플래그가 켜져있는데 (PageDirty()) 사용자 주소 공간에 매핑되지 않았다면 (is_page_cache_freeable(page)) 디스크에 writeout을 해주어야 하므로 mapping->a_ops->vm_writeback()을 호출해준다. (단 filesystem 연산을 하면 안 되는 경우에는 데드락을 피하기 위해 writeout을 하지 않는다.) 이 루틴은 페이지 캐시 상의 페이지 프레임 혹은 스왑 캐시 상의 페이지 프레임에 대해서 수행된다.

		/*
		 * If the page has buffers, try to free the buffer mappings
		 * associated with this page. If we succeed we try to free
		 * the page as well.
		 *
		 * We do this even if the page is PageDirty().
		 * try_to_release_page() does not perform I/O, but it is
		 * possible for a page to have PageDirty set, but it is actually
		 * clean (all its buffers are clean).  This happens if the
		 * buffers were written out directly, with submit_bh(). ext3
		 * will do this, as well as the blockdev mapping. 
		 * try_to_release_page() will discover that cleanness and will
		 * drop the buffers and mark the page clean - it can be freed.
		 */
		if (PagePrivate(page)) {
			spin_unlock(&pagemap_lru_lock);

			/* avoid to free a locked page */
			page_cache_get(page);

			if (try_to_release_page(page, gfp_mask)) {

이 부분에서는 페이지 프레임과 연관된 버퍼가 있는지를 확인하며, 있다면 try_to_release_page()로 해제를 시도한다. 이 함수는 성공한 경우 0이 아닌 수를 반환한다.

				if (!mapping) {
					/*
					 * We must not allow an anon page
					 * with no buffers to be visible on
					 * the LRU, so we unlock the page after
					 * taking the lru lock
					 */
					spin_lock(&pagemap_lru_lock);
					unlock_page(page);
					__lru_cache_del(page);

					/* effectively free the page here */
					page_cache_release(page);

					if (--nr_pages)
						continue;
					break;

페이지 프레임이 페이지 캐시에 속했다면 mapping이 NULL이 아니라 address_space를 가리켜야 한다. try_to_release_page()가 성공했는데 mapping이 NULL이라면, 이전에는 스왑 캐시에 존재했지만 이를 참조하는 pte가 없어서 스왑 캐시에서 제거된 후, 연관된 버퍼만 남았음을 의미한다. try_to_release_page()에서 버퍼를 해제해주었으므로  LRU 리스트에서 제거하고 회수한다.

				} else {
					/*
					 * The page is still in pagecache so undo the stuff
					 * before the try_to_release_page since we've not
					 * finished and we can now try the next step.
					 */
					page_cache_release(page);

					spin_lock(&pagemap_lru_lock);
				}

페이지 프레임이 페이지 캐시에 존재했다면 다음에 이 페이지 프레임을 만날 때 회수를 다시 시도한다.

			} else {
				/* failed to drop the buffers so stop here */
				unlock_page(page);
				page_cache_release(page);

				spin_lock(&pagemap_lru_lock);
				continue;
			}
		}

try_to_release_page()가 실패한 경우에는 다음 페이지 프레임으로 넘어간다.

		/*
		 * This is the non-racy check for busy page.
		 */
		if (mapping) {
			write_lock(&mapping->page_lock);
			if (is_page_cache_freeable(page))
				goto page_freeable;
			write_unlock(&mapping->page_lock);
		}
		unlock_page(page);
		continue;

실행 흐름이 여기까지 도달했다면 적어도 페이지 프레임은 페이지 캐시나 스왑 캐시에 속해야 하며, 연관된 버퍼가 없어야 한다. 따라서 여기서 is_page_cache_freeable()이 참을 반환하면 reference count가 1만 남은 경우이다. (페이지 캐시나 스왑 캐시가 참조) 그런 경우 page_freeable로 가서 회수를 시도한다.

page_freeable:
		/*
		 * It is critical to check PageDirty _after_ we made sure
		 * the page is freeable* so not in use by anybody.
		 */
		if (PageDirty(page)) {
			write_unlock(&mapping->page_lock);
			unlock_page(page);
			continue;
		}

여기까지 왔어도 회수가 불가능 경우가 있는데, 페이지 프레임이 dirty인 경우이다. 이런 경우엔 다음 페이지 프레임으로 이동한다.

		/* point of no return */
		if (likely(!PageSwapCache(page))) {
			__remove_inode_page(page);
			write_unlock(&mapping->page_lock);
		} else {
			swp_entry_t swap;
			swap.val = page->index;
			__delete_from_swap_cache(page);
			write_unlock(&mapping->page_lock);
			swap_free(swap);
		}

실행 흐름이 여기까지 왔다면 이 페이지 프레임은 clean한 상태이며, 사용자 주소 공간에 매핑되어있지 않고, 스왑 캐시나 페이지 캐시에 속한 경우이다. 어떤 캐시에 속했냐에 따라서 페이지 프레임을 캐시에서 제거해준다.

		__lru_cache_del(page);
		unlock_page(page);

		/* effectively free the page here */
		page_cache_release(page);
		if (--nr_pages)
			continue;

그 다음 LRU 리스트에서 페이지 프레임을 제거한 후 회수한다.

		goto out;
page_active:
		/*
		 * OK, we don't know what to do with the page.
		 * It's no use keeping it here, so we move it to
		 * the active list.
		 */
		del_page_from_inactive_list(page);
		add_page_to_active_list(page);
		pte_chain_unlock(page);
		unlock_page(page);
	}
out:	spin_unlock(&pagemap_lru_lock);
	return nr_pages;
}

try_to_unmap()

/**
 * try_to_unmap - try to remove all page table mappings to a page
 * @page: the page to get unmapped
 *
 * Tries to remove all the page table entries which are mapping this
 * page, used in the pageout path.  Caller must hold pagemap_lru_lock
 * and the page lock.  Return values are:
 *
 * SWAP_SUCCESS - we succeeded in removing all mappings
 * SWAP_AGAIN   - we missed a trylock, try again later
 * SWAP_FAIL    - the page is unswappable
 * SWAP_ERROR   - an error occurred
 */

try_to_unmap()은 물리 페이지를 회수하는 함수로, rmap의 구현과 함께 추가되었다. [Rik02]의 changelog에서 말하는 것처럼, 이전에는 pageout을 할 때 프로세스 주소 공간을 순회하면서 하나씩 pte를 unmap했는데, 이제는 페이지 프레임이 어디에 매핑되어있는지를 알기 때문에 페이지 프레임 단위로도 회수를 할 수 있게 되었다.

int try_to_unmap(struct page * page)
{
        struct pte_chain * pc, * next_pc, * prev_pc = NULL;
        int ret = SWAP_SUCCESS;

        /* This page should not be on the pageout lists. */
        if (PageReserved(page))
                BUG();

PG_reserved가 켜져있는 페이지 프레임은 swapout될 수 없으므로 애초에 LRU (pageout) list에 존재해선 안된다. 이 경우는 BUG()를 호출한다.

        if (!PageLocked(page))
                BUG();

PFRA에서 페이지 프레임을 회수하기 전에 TestSetPageLocked()로 락을 하는데, 락이 정상적으로 획득되지 않은 경우도 오류이므로 BUG()를 호출한다.

        /* We need backing store to swap out a page. */
        if (!page->mapping)
                BUG();

페이지가 pageout될 수 없거나 (PageReserved()) ,page->mapping 이 NULL 경우에는 BUG()를 호출한다.

좀 더 부가설명을 하자면, try_to_unmap()이 회수하는 페이지 프레임은 페이지 캐시 상의 페이지거나 (page->mapping이 address_space를 가리킴), swap cache 상의 페이지여야 한다. (page->mapping이 swapper_space를 가리킴). 다시 말해 swap cache에 존재하지 않는 anonymous page는 먼저 swap cache에 추가한 후 try_to_unmap()을 호출해야한다.

        for (pc = page->pte_chain; pc; pc = next_pc) {
                next_pc = pc->next;
                switch (try_to_unmap_one(page, pc->ptep)) {

이 함수는 pte chain을 순회하면서 각각의 pte들에 대하여 try_to_unmap_one()을 호출해서 unmapping을 시도한다.  try_to_unmap_one()은 pte의 unmapping의 성공/실패 여부를 반환한다.

                        case SWAP_SUCCESS:
                                /* Free the pte_chain struct. */
                                pte_chain_free(pc, prev_pc, page);
                                break;

SWAP_SUCCESS는 pte의 unmap에 성공했다는 의미이므로 pte chain을 free하고 다음 chain으로 넘어간다.

                        case SWAP_AGAIN:
                                /* Skip this pte, remembering status. */
                                prev_pc = pc;
                                ret = SWAP_AGAIN;
                                continue;

try_to_unmap_one()에서 mm->page_table_lock의 trylock에 실패한 경우에는 이 pte를 다음에 다시 시도한다.

                        case SWAP_FAIL:
                                return SWAP_FAIL;
                        case SWAP_ERROR:
                                return SWAP_ERROR;
                }
        }

        return ret;
}

SWAP_FAIL의 경우에는 pte가 unmap될 수 없는 경우이며, SWAP_ERROR는 오류가 발생한 경우이다. 두 경우 모두 이 페이지 프레임을 회수할 수 없기 때문에 unmap을 중단하고 함수를 반환한다.

try_to_unmap_one()

try_to_unmap_one()은 페이지 프레임을 가리키는 pte 하나를 unmap하는 함수이다.

static int try_to_unmap_one(struct page * page, pte_t * ptep)
{
        unsigned long address = ptep_to_address(ptep);
        struct mm_struct * mm = ptep_to_mm(ptep);
        struct vm_area_struct * vma;
        pte_t pte;
        int ret;

        if (!mm)
                BUG();

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

누군가 page_table_lock을 사용중이라면 기다리지 않고 다음에 다시 시도한다.

        /* During mremap, it's possible pages are not in a VMA. */
        vma = find_vma(mm, address);
        if (!vma) {
                ret = SWAP_FAIL;
                goto out_unlock;
        }

mremap 도중이라면 페이지 프레임이 VMA에 속하지 않을 수 있으므로 SWAP_FAIL을 반환한다. (왜 SWAP_AGAIN이 아닌지는 잘 모르겠다.)

        /* The page is mlock()d, we cannot swap it out. */
        if (vma->vm_flags & VM_LOCKED) {
                ret = SWAP_FAIL;
                goto out_unlock;
        }

VMA가 mlock()에 의해 메모리에 고정된 상태라면 어차피 회수를 못하므로 SWAP_FAIL을 반환한다.

        /* Nuke the page table entry. */
        pte = ptep_get_and_clear(ptep);
        flush_tlb_page(vma, address);
        flush_cache_page(vma, address);

pte를 clear하고 TLB, dcache를 flush해준다.

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

페이지 프레임이 페이지 캐시에 속한다면 그냥 디스크에 writeout한 이후 회수해도 나중에 page fault가 나면 디스크에서 읽어올 위치를 알 수 있지만, 페이지 프레임이 스왑 캐시에 존재하는 경우에는 그렇지 않으므로 pte를 swap entry로 바꾼 후 swap cache 상의 reference count를 추가해준다.

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

pte상에 dirty 비트가 켜져있는 경우, PG_dirty 플래그를 켜주어 페이지가 회수되기 전에 적절하게 디스크에 쓰여지도록 한다.

        mm->rss--;
        page_cache_release(page);
        ret = SWAP_SUCCESS;

언매핑에 성공했으므로 페이지 프레임의 reference count와 rss를 줄여준다.

out_unlock:
        spin_unlock(&mm->page_table_lock);
        return ret;
}

When to add/remove pte chain

pte chain은 사용자 주소 공간에 페이지 프레임이 매핑될 때 추가되고, 언매핑될 때 제거된다. v2.5.27에서 pte chain을 추가하고 제거하는 경우가 무엇이 있는지 알아보자.

do_no_page() / do_anonymous_page()

do_anonymous_page()와 do_no_page()는 페이지 폴트 핸들러에서 프로세스 주소 공간에 anonymous page가 추가될 때 호출된다. 아주 심플한 케이스로, do_anonymous_page()는 0으로 채워진 페이지 프레임을 할당해서 프로세스 주소 공간에 매핑하고, do_no_page()는 할당된 페이지에 대해서 vm_operations_struct의 nopage callback을 호출한 후 프로세스 주소공간에 매핑한다.

pte chain이 추가되기 전(왼쪽)과 후(오른쪽)

do_swap_page()

do_swap_page()는 swap을 위해 unmap된 페이지에 접근한 경우 호출되며, 스왑 캐시 상의 페이지를 (디스크에만 존재하는 경우는 스왑 캐시로 불러온다.) 페이지 테이블에서 참조해야 하므로 pte chain을 추가해준다. 

put_dirty_page()

대체로 프로세스가 사용하는 페이지들은 페이지 폴트 핸들러에 의해서 추가되지만, 실행 파일을 실행할 때 처음에 페이지를 추가해줄 때가 있다. 그런 경우도 프로세스가 페이지를 참조하므로 pte chain을 추가해줘야한다.

unuse_pte()

sys_swapoff()는 현재 사용 중이던 swap file을 더 이상 사용하지 않도록 하는 swapoff() 시스템 호출의 구현이다. swap file을 더 이상 사용하지 않으려면 swap file의 내용을 읽어서 메모리에 올린 후, swap entry들을 모두 원래대로 되돌려야 한다. v2.5.26에서는 모든 process의 주소 공간을 돌면서 swap entry를 정상적은 entry로 되돌린 후 pte chain을 추가해줘야한다. unuse_pte()는 swap entry를 다시 되돌리는 역할을 하며 sys_swapoff() -> try_to_unuse() -> unuse_process() -> unuse_vma() -> unuse_pgd() -> unuse_pmd() -> unuse_pte() 순서대로 호출된다. swap entry가 원래의 엔트리가 된 경우 페이지 테이블에서 페이지를 참조하게 되므로 pte chain을 추가한다.

fork()

fork()을 하게되면 dup_mmap()으로 부모 프로세스의 주소 공간을 자식 프로세스의 주소 공간에 복제한다.

이때, dup_mmap()에서는 copy_page_range()로 부모 프로세스의 모든 VMA에 대하여 VMA의 시작~끝 범위를 copy_page_range()로 복제한다. fork()를 하면 자식과 부모가 같은 페이지 프레임을 가리키므로 pte chain을 추가해준다. 

fork()에 의해 하나의 페이지 프레임이 두 프로세스 사이에 공유되는 경우

Breaking CoW

copy_page_range()에서 VM_MAYWRITE가 설정된 VMA의 경우에는 부모와 자식 모두의 페이지 테이블에서 read-only로 매핑을 한 후 write에 의한 page fault가 발생하기 전까지는 부모와 자식이 같은 페이지 프레임을 참조한다. 하지만 write에 의한 page fault가 발생해서 copy를 해야하는 경우에는 부모의 페이지를 복사해서 자식의 페이지 테이블에 매핑해야하며, 자식은 더 이상 부모와 같은 페이지를 공유하지 않게 된다.  

따라서 do_wp_page()는 기존에 부모와 자식이 공유하던 페이지 프레임의 reverse mapping을 제거한 후, CoW 이후 복사된 페이지 프레임에 reverse mapping을 추가한다.

fork()에 의해 공유되던 페이지 프레임에 CoW가 발생한 경우

copy_one_pte()

copy_one_pte()는 do_mremap()->move_vma()->move_page_tables()->move_one_page()->copy_one_pte() 순서로 호출되며, VMA의 주소를 옮길 때 사용하므로, 기존의 pte chain을 제거한 후, 새롭게 이동된 주소에 대한 pte chain을 다시 추가한다.

페이지 프레임이 원래의 주소에 매핑되어있었다가

 

언매핑된 후 (왼쪽) 다른 주소에 다시 매핑된 경우(오른쪽)

References

[Rik02] [patch 1/13] minimal rmap, Rik Van Riel, 2002

'Kernel > Memory Management' 카테고리의 다른 글

Object-based reverse mapping (v2.6.7)  (0) 2023.02.17
Physical Memory Model (FLATMEM, SPARSEMEM)  (0) 2023.02.08
Page Frame Reclamation and Swapout (v2.4.22)  (0) 2022.12.24
Process Address Space  (0) 2022.11.05
compound page 정리  (2) 2022.10.05

댓글