Process Address Space

이 글에서는 리눅스에서의 프로세스 주소 공간을 관리하는 자료구조를 알아볼 것이다. 이 글에서는 page table isolation / address space isolation은 고려하지 않는다. outdated된 내용이 조금 있을 수 있지만 우선은 프로세스 주소 공간에 대한 큰 그림을 그려보자.

Address Space

주소 공간은 주소의 범위를 의미한다. 주소 공간의 크기는 32비트에서 4G, 64비트에서 16EB이다. 그리고 이 주소 공간을 어떻게 잘 나눠서 사용할지는 아키텍처에서 정한다. 예시) x86_64, aarch64

주소 공간은 크게 user (process) address space와 kernel address space로 나뉜다. kernel과 user의 address space를 어떻게 페이지 테이블로 나타낼지도 아키텍처에 따라 다른데, x86은 기본적으로 하나의 페이지 테이블 안에서 user와 kernel이 주소 범위에 따라서 나눠서 쓰고, arm에서는 user와 kernel의 페이지 테이블이 별도로 있으며, sparc에서는 user와 kernel의 주소 공간 자체가 별도로 분리되어있다.

User Address Space

리눅스는 모놀리식 커널이기 때문에 (모듈도 있긴 하지만) 커널은 하나의 이미지이며 각 기능들이 마이크로 커널마냥 명확하게 분리되어있지는 않다. 그래서 커널의 주소 공간은 유일하다. 다시 말해서 어떤 CPU에서 어떤 프로세스를 실행하든 커널의 주소 공간은 크게 다르지 않다. (vmalloc은 예외로, page fault가 발생했을 때 동기화한다.)

하지만 이와 다르게 프로세스는 저마다의 context가 존재한다. 커널 주소 공간에서는 실행중인 프로세서, 프로세스와 관계 없이 같은 주소에는 모두 같은 데이터가 들어있다. (물론 예외가 있을 수 있다.) 하지만 프로세스(user) 주소 공간에서는 같은 주소라도 실행 중인 프로세스에 따라 가리키는 데이터가 달라지게 된다.

Managing Address Space

리눅스에서 태스크를 관리하는 자료구조가 task_struct라면 어떤 태스크에게 할당된 모든 주소 공간과 페이지 테이블, 할당된 메모리에 대한 정보는 모두 mm_struct가 (task_struct->mm) 관리하며 프로세스마다 독립적으로 존재한다. (스레드 끼리는 공유한다.)

하지만 사용자 주소 공간 내에서도 메모리를 특성에 따라 텍스트, 스택, 힙 등 용도와 특성에 따라서 나누어야 하므로 vm_area_struct (VMA) 라는 자료구조로 나누어 관리한다. 아래 그림은 프로세스마다 mm_struct로 주소 공간과 할당된 메모리에 관련된 정보를 갖고 있으며, 주소 공간이 VMA로 나뉜다는 것을 보여준다. 약간 outdated되긴 했지만 참고용으로 보자.

VMA는 텍스트/데이터 영역과 같이 연관된 파일이 있거나 (file-backed), 스택/힙처럼 파일과 아무 관련이 없을 수도 있다. (anonymous)

mm_struct and vm_area_struct [17]

 

mm_struct

mm_struct는 프로세스의 주소 공간과, 할당된 메모리에 대한 정보를 주로 관리한다. 각 프로세스마다 mm_struct가 존재하며 스레드 간에는 같은 mm_struct를 공유한다. mm_struct도 복잡한 구조체기 때문에 중요한 (주관적임) 필드들만 일부 짚고 넘어가보자. 

struct mm_struct {
	struct {
		struct maple_tree mm_mt;

 

maple_tree는 VMA의 목록을 RCU 기반의, 모던 CPU에 친화적인 B-tree로 관리하는 자료구조로 리눅스 6.1-rc1에 추가되었으며 기존의 링크드 리스트와 red-black tree, mmap_cache는 VMA를 관리하는 데에 더이상 사용하지 않는다. [4], [5], [8]

 

#ifdef CONFIG_MMU
		unsigned long (*get_unmapped_area) (struct file *filp,
				unsigned long addr, unsigned long len,
				unsigned long pgoff, unsigned long flags);
#endif
		unsigned long mmap_base;	/* base of mmap area */
		unsigned long mmap_legacy_base;	/* base of mmap area in bottom-up allocations */
#ifdef CONFIG_HAVE_ARCH_COMPAT_MMAP_BASES
		/* Base addresses for compatible mmap() */
		unsigned long mmap_compat_base;
		unsigned long mmap_compat_legacy_base;
#endif

 

get_unmapped_area()는 mmap()으로 새로운 vma를 만들때, vma가 사용할 주소를 반환하는 함수다. mmap_base와 mmap_legacy_base는 get_unmappped_area()가 주소를 찾기 시작하는 지점이다.

bottom-up and top-down approaches of mmap() [2]

 

원래는 프로세스 주소 공간이 왼쪽 사진과 같이 구성되어서 mmap이 bottom-up으로 자랐지만, 왼쪽의 방식으로 주소 공간을 구성하면 mmap과 heap이 자랄 수 있는 한계가 명확하다. [2] 그래서 2004년 즈음에 오른쪽 사진과 같이  스택이 자랄 수 있는 한계를 제한하고 mmap 영역과 heap 영역이 서로 마주보며 반대 방향으로 자라도록 바뀌었다. [3] 정확하게 말하면 현재는 bottom-up (legacy), top-down (current) 두 가지 방식을 모두 지원한다.

		unsigned long task_size;	/* size of task vm space */
		pgd_t * pgd;

 

task_size는 프로세스 주소 공간의 크기이며 일반적으로 TASK_SIZE라는 값을 갖는다. pgd는 PGD 테이블의 첫 엔트리를 가리킨다.

picture of four level page table - LWN.net

PGD 테이블은 프로세스의 가상 주소가 어느 물리 주소에 매핑되어있는지를 나타내며, x86_64에서는 이 테이블에 커널과 유저 주소 공간이 모두 매핑되어있다. pgd필드는 PGD 테이블의 첫 엔트리를 가리킨다.

		/**
		 * @mm_users: The number of users including userspace.
		 *
		 * Use mmget()/mmget_not_zero()/mmput() to modify. When this
		 * drops to 0 (i.e. when the task exits and there are no other
		 * temporary reference holders), we also release a reference on
		 * @mm_count (which may then free the &struct mm_struct if
		 * @mm_count also drops to 0).
		 */
		atomic_t mm_users;

		/**
		 * @mm_count: The number of references to &struct mm_struct
		 * (@mm_users count as 1).
		 *
		 * Use mmgrab()/mmdrop() to modify. When this drops to 0, the
		 * &struct mm_struct is freed.
		 */
		atomic_t mm_count;

 

mm_users와 mm_count는 모두 이 mm_struct의 사용자 수를 의미한다. 리눅스는 자신의 주소 공간을 사용하는 사용자를 "real users that uses their own address space"와 "anonymous users that steals others' address space"로 나눈다. [6] 

 

mm_users는 사용자 부분의 주소 공간을 필요로 하며, madvise(), /proc 등 사용자 부분에 접근하는 곳에서 mmget()으로 카운트를 증가시킨다. (※주의: CLONE_VM 플래그가 없다면 fork()는 mm을 복사하기 때문에 mm_users를 증가시키지는 않는다. 대신 스레드를 생성할 때는 CLONE_VM 플래그를 명시해서 mm_users를 증가시킨다.)

mm_count는 anonymous user의 수 + 1 (mm_users > 0인 경우)이다. anonymous user는 커널 주소 공간만 접근하며 (e.g. kernel thread), 다른 "real users"의 mm을 task_struct의 active_mm 필드로 빌려와서 사용할 수 있다. (anonymous user는 "real user"가 아니기 때문에 ->mm 필드는 NULL이다.) 이렇게 하면 커널 스레드로 컨텍스트 스위칭을 할 때는 TLB flush를 하지 않아도 된다.

mm_users가 0이더라도, 즉 이 주소 공간을 사용하는 실제 사용자는 모두 사라졌더라도 anonymous user가 이를 빌려서 쓸 수 있기 때문에, mm_count가 0이 되기 전까지는 mm_struct가 해제되지 않는다. 단, mm_users가 0이 되면 mm_struct 자체는 해제되지 않지만  사용자 주소 공간과 관련된 메모리는 모두 해제된다. swap에서는 mm을 순회하는 도중 해제되는 것을 방지하기 위해 mmget()으로 mm_users를 증가시킨다. 

 

#ifdef CONFIG_MMU
		atomic_long_t pgtables_bytes;	/* PTE page table pages */
#endif
		int map_count;			/* number of VMAs */

 

map_count는 VMA의 개수를, pgtables_bytes는 PGD/P4D/PUD/PMD 테이블은 제외하고 PTE 테이블의 크기를 나타낸다. 

 

		spinlock_t page_table_lock; /* Protects page tables and some
					     * counters
					     */
		/*
		 * With some kernel config, the current mmap_lock's offset
		 * inside 'mm_struct' is at 0x120, which is very optimal, as
		 * its two hot fields 'count' and 'owner' sit in 2 different
		 * cachelines,  and when mmap_lock is highly contended, both
		 * of the 2 fields will be accessed frequently, current layout
		 * will help to reduce cache bouncing.
		 *
		 * So please be careful with adding new fields before
		 * mmap_lock, which can easily push the 2 fields into one
		 * cacheline.
		 */
		struct rw_semaphore mmap_lock;

 

*주의*: locking에 관한 내용은 아직 정리를 더 해야할 것 같다. Documentation/vm/locking이라는 문서가 위의 락들에 대해 설명했었는데 너무 outdated되어서 사라졌고 그 외의 문서는 없는 것 같다. 사라진 문서를 참고하되 의존하지는 말자.

우선 page_table_lock은 프로세스의 페이지 테이블을 수정할 때 획득해야한다. 새로운 페이지 프레임을 매핑한다던가, 어떤 페이지의 권한을 read/write에서 read-only로 바꾼다던가 등등. page_table_lock은 페이지 테이블 전체를 보호하지만 경우에 따라서는 좀더 finer-grained lock을 사용하기도 한다.

mmap_lock RW 세마포어는 maple tree를 순회할 때는 mmap_read_lock()으로 read mode로 lock을, mmap() 등으로 maple tree에 삽입/삭제할 때는 mmap_write_lock()으로 write mode로 lock을 획득해야 한다. 단, mmap_read_lock()을 사용하면 maple tree에 새로운 VMA가 추가, 삭제, 병합되지 않음은 보장되지만 VMA 자체가 확장되는 등의 변경으로부터 보호해주지는 않는다.

예를 들어 프로세스 주소 공간에 대해 페이지 폴트가 발생하면 핸들링하는 로직은 read mode의 lock을 획득한 후 폴트가 난 주소에 해당하는 VMA를 찾고, VMA에 VM_GROWSDOWN 플래그가 존재한다면 expand_stack(), 함수로 스택의 VMA를 확장한다. 이 때는 mmap_lock의 read mode의 lock을 획득한 상태에서 VMA expansion을 serialize할 방법이 없으므로 page_table_lock으로 concurrent한 expansion을 방지한다. 다시 한 번 요약하면 mmap_lock의 read mode의 lock을 획득하면 maple tree가 바뀌지 않음은 보장되지만 VMA 자체가 수정되지 않다는 보장은 하지 않으며 그러한 보장이 필요하다면  page_table_lock을 획득해야 한다.

mmap_lock과 page_table_lock은 그 외에도 (문서화되지 않은...) 다양한 용도로 사용되고 있고, 아마 가까운 미래에 많이 바뀔 것 같다. 이 내용은 다음에 따로 글로 정리해야겠다. [8]에 process address space의 locking에 대한 서술이 매우 잘 되어 있으므로 참고하자.

		unsigned long hiwater_rss; /* High-watermark of RSS usage */
		unsigned long hiwater_vm;  /* High-water virtual memory usage */

		unsigned long total_vm;	   /* Total pages mapped */
		unsigned long locked_vm;   /* Pages that have PG_mlocked set */
		atomic64_t    pinned_vm;   /* Refcount permanently increased */
		unsigned long data_vm;	   /* VM_WRITE & ~VM_SHARED & ~VM_STACK */
		unsigned long exec_vm;	   /* VM_EXEC & ~VM_WRITE & ~VM_STACK */
		unsigned long stack_vm;	   /* VM_STACK */
		unsigned long def_flags;

 

total_vm은 프로세스 주소 공간에 실제로 매핑된 페이지의 수를 의미한다.  lock_vm, pinned_vm은 total_vm 중 메모리에 lock되었거나 pin된 페이지의 수를 나타낸다. data, exec, stack은 VMA의 플래그에 따라 데이터, 코드, 스택에 사용된 페이지 수를 나타낸다.

		spinlock_t arg_lock; /* protect the below fields */

		unsigned long start_code, end_code, start_data, end_data;
		unsigned long start_brk, brk, start_stack;
		unsigned long arg_start, arg_end, env_start, env_end;

 

위 필드들은 코드, 데이터, 힙, arg, 환경변수의 주소 공간의 시작과 끝을 나타내며 arg_lock으로 보호된다.

 

		/* Architecture-specific MM context */
		mm_context_t context;

 

context는 아키텍처별로 필요한 내용을 넣는 필드다. (PCB 아님)

		unsigned long flags; /* Must use atomic bitops to access */

 

flags는 mm에 관련된 플래그들을 기록하는 필드이다.

Virtual Memory Area (vm_area_struct)

어떤 VMA는 텍스트, 데이터 섹션과 같이 파일로부터 만들어지거나 (file-backed), 스택이나 힙처럼 파일과 관계 없이 실행 중에 만들어진다. (anonymous)

전자의 경우 vm_area_struct->vm_file->f_dentry->d_inode->i_mapping으로 vma와 관련된 address_space를 얻을 수 있다. 이 경우에는 페이지 캐시 상의 페이지를 가리킨다.

vm_area_struct

vm_area_struct의 필드 중 중요한 필드를 살펴보자.

/*
 * This struct describes a virtual memory area. There is one of these
 * per VM-area/task. A VM area is any part of the process virtual memory
 * space that has a special rule for the page-fault handlers (ie a shared
 * library, the executable area etc).
 */
struct vm_area_struct {
	/* The first cache line has the info for VMA tree walking. */

	unsigned long vm_start;		/* Our start address within vm_mm. */
	unsigned long vm_end;		/* The first byte after our end address
					   within vm_mm. */

	struct mm_struct *vm_mm;	/* The address space we belong to. */

 

vm_start (inclusive), vm_end (exclusive)는 VMA의 주소 범위를 나타내며, vm_mm은 VMA가 속한 mm을 가리킨다.

	/*
	 * Access permissions of this VMA.
	 * See vmf_insert_mixed_prot() for discussion.
	 */
	pgprot_t vm_page_prot;
	unsigned long vm_flags;		/* Flags, see mm.h. */

 

vm_page_prot은 VMA에 속한 페이지들의 protection bit를 저장하며 (읽기/쓰기가 가능한지 등등) vm_flags는 VMA의 특성들을 플래그로 저장한다. 

vm_flags를 몇가지 표로 정래해보았다.

플래그	의미
VM_READ	VMA에 읽기가 가능하다
VM_MAYREAD	VM_READ를 설정할 수 있다 [10]
VM_WRITE	VMA에 쓰기가 가능하다
VM_MAYWRITE	VM_WRITE를 설정할 수 있다
VM_EXEC	VMA를 실행할 수 있다
VM_MAYEXEC	VMA_EXEC를 설정할 수 있다
VM_SHARED	VMA가 여러 프로세스 사이에서 공유될 수 있다
VM_MAYSHARE	VM_SHARED를 설정할 수 있다
VM_LOCKED	VMA가 swap out되지 않고 메모리에 항상 상주해야한다
VM_RAND_READ	접근 패턴이 임의적이다
VM_SEQ_READ	접근 패턴이 순차적이다
VM_DONTCOPY	fork()시에 VMA를 복제하지 않는다

 

	/*
	 * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
	 * list, after a COW of one of the file pages.	A MAP_SHARED vma
	 * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
	 * or brk vma (with NULL file) can only be in an anon_vma list.
	 */
	struct list_head anon_vma_chain; /* Serialized by mmap_lock &
					  * page_table_lock */
	struct anon_vma *anon_vma;	/* Serialized by page_table_lock */

 

이 글에서 자세히는 설명하지 않지만 anon_vma는 object-based reverse mapping에서 anonymous page가 매핑된 VMA의 목록을 관리하는 데에 사용된다. [11], [12]

	/* Function pointers to deal with this struct. */
	const struct vm_operations_struct *vm_ops;

	/* Information about our backing store: */
	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
					   units */
	struct file * vm_file;		/* File we map to (can be NULL). */
	void * vm_private_data;		/* was vm_pte (shared mem) */

} __randomize_layout;

 

vm_file은 file-backed VMA인 경우 파일을 가리키며, vm_pgoff는 PAGE_SIZE단위의 파일 내 오프셋이다. vm_private_data는 파일시스템이나 디바이스 드라이버에서 VMA에 데이터를 저장할 때 사용된다.

vm_operations_struct는 open, close, fault 등 VMA를 생성/삭제, 폴트 등의 연산이 발생할 때 호출될 함수 포인터를 저장한다.

Address Space Operations

새로운 주소 공간을 할당하거나 삭제하는 등 프로세스의 주소 공간을 수정하는 대표적인 연산을 아래 표에 간단하게 정리했다.

시스템 호출	설명
mmap()	프로세스 주소 공간에 새로운 주소 공간을 할당한다. 경우에 따라서 새로운 VMA를 maple tree에 삽입하거나 기존의 VMA를 확장한다.
munmap()	주소 공간을 없앤다. 경우에 따라서 VMA를 2개로 나누거나, 축소하거나, maple tree에서 제거한다.
mremap()	기존의 주소 공간을 새로운 영역으로 옮긴다. 경우에 따라 VMA를 쪼개거나, 합치거나, 확장하거나 새로운 VMA를 maple tree에 삽입한다.
mprotect()	주소 공간의 protection을 수정한다. 경우에 따라 VMA를 쪼갤 수 있다.
madvise()	주소 공간에 대한 힌트를 준다.
fork()	VM_DONTCOPY로 명시된 VMA를 제외한 프로세스 주소 공간을 복사하며, 모든 페이지는 쓰기가 불가능하도록 COW 처리가 된다.
exit()	주소 공간을 포함하여 프로세스의 모든 자원을 회수한다.
shmat()/shmdt()	shared memory를 프로세스 주소 공간에 추가하거나 제거한다.
mlock()/munlock()	주소 공간을 메모리에 lock하거나 해제한다 (VM_LOCKED)

Page Fault

가상 메모리에서는 임의의 가상 주소가 임의의 페이지 프레임을 가리키게 해서 가상 주소로 물리 메모리에 접근할 수 있다. 가상 주소에 대하여 page table walking을 수행해서 물리 주소를 구하는 것은 하드웨어가 수행하는데, 만약 페이지가 존재하지 않는 경우에는 page fault exception이 발생하여 운영체제가 이를 처리한다.

page fault가 발생하는 이유는 여러 가지가 있다. 주소 공간은 있지만 아직 메모리가 할당되지 않았거나, fork()가 수행되어 COW page에 쓰기를 수행하거나, 힙/스택을 확장하거나, swap out된 페이지에 접근하거나, 아니면 그냥 유효하지 않은 주소에 접근했을 수도 있다. 페이지 폴트는 크게 디스크 연산을 동반하는 (swap 같은 경우) major fault와, COW 처럼 디스크 연산을 동반하지 않는 minor fault로 나뉜다. task_struct에서 maj_flt, min_flt가 이러한 폴트의 횟수를 나타낸다.

 페이지 폴트 핸들러는 폴트가 일어난 주소, 실행 모드 (커널/유저), 주소에 해당하는 페이지 테이블 엔트리 등의 맥락을 모두 고려하여 오류를 던지든 새로운 페이지를 할당하든 상황에 맞게 적절한 동작을 취해야한다.

이때, 폴트가 난 주소가 사용자 주소 공간에 해당하는 경우 페이지 폴트 핸들러는 주소에 해당하는 VMA를 찾기 위해서 mmap_lock (reader/writer semaphore)을 read mode로 획득한다.

페이지 폴트 핸들러는 아키텍처에서 정의하며 아키텍처에 독립적인 부분은 handle_mm_fault()부터이다. 페이지 폴트가 나는 경우들을 좀 더 세부적으로 정리해보자.

major/minor	폴트의 원인		해결 방법	관련 함수
major	접근하려는 페이지가 swap out 상태이며 swap cache에도 존재하지 않아 디스크에서 읽어와야 하는 경우		디스크의 스왑 공간에서 페이지 프레임을 찾아서 메모리로 불러온다	do_swap_page()
minor	폴트 주소가 VMA에 포함되고 권한도 있는데 페이지가 present하지 않음		페이지를 할당한다.	do_anonymous_page(), do_fault()
minor	폴트 주소가 VMA에 포함되지는 않지만 스택, 힙처럼 VMA가 확장될 수 있는 경우		VMA를 확장하고 페이지를 할당한다.	expand_upwards(), expand_downwards()
minor	접근하려는 페이지가 present하지만 read-only인 페이지에 쓰기를 하려는 경우		COW 페이지라면 COW를 깨고 그렇지 않다면 오류를 뿜는다.	do_wp_page()
minor	커널 주소 공간에서 폴트가 난 경우		커널 영역에서는 왠만한 경우에서는 폴트가 나면 안되지만 vmalloc 영역이 동기화되지 않은 경우에는 페이지 폴트가 발생할 수 있다.

 

page fault flowchart [17]

 

Summary

프로세스의 주소 공간이 하나의 연속적인 공간이 아니라 각각의 연속적인 주소 공간을 나타내는 VMA들을 maple tree로 관리한다. 페이지 테이블을 수정할 때는 page_table_lock을, maple tree을 수정할 때는 mmap_lock이라는 reader/writer semaphore를 사용한다.

기본적으로 리눅스는 VMA의 할당과 물리 페이지의 할당을 동시에 하지 않으며 (demand allocation), 페이지 폴트가 발생하는 경우에만 물리 페이지를 할당하고 페이지 테이블이 할당한 페이지를 가리키게 한다. 페이지 폴트 핸들러는 그 외에도 swap out된 페이지에 접근하는 등 페이지에 접근할 수 없는 다양한 경우를 처리한다.

Recent Trends

mmap_lock scalability

최근 10년 동안 주소 공간의 확장성을 주제로 한 세션이나 논문이 많아졌다. [8], [14], [18] mmap_lock은 reader/writer semaphore이기 때문에 VMA의 삽입/삭제와 조회가 동시에 수행될 수 없다. 따라서 많은 스레드를 사용하고, address space operation이 intensive한 어플리케이션은 address space operation과 page fault에 병목 현상을 겪게 된다. Speculative Page Fault [15], Per-VMA lock [14], Maple Tree [4], [8] 등은 모두 이러한 문제를 해결하려는 시도의 일환이다.

 

References

[1] How The Kernel Manages Your Memory - Many But Finite ()

[2] Reorganizing the address space - LWN.net

[3] flexible-mmap-2.6.7-D5 by Ingo Molnar, LWN archive    

[4] The Maple Tree, A Modern Data Structure for a Complex Problem, By Liam Howlett, Oracle Linux Blog

[5] commit 763ecb0350 ("mm: remove the vma linked list"), Linus' mainline tree   

[6] active_mm, by Linus Torvalds, on Kernel Documentation

[7] Ch.4, Process Address Space of "gorman book"

[8] Scalable address spaces using RCU balanced trees, 2012, MIT CSAIL

[9] Documentation/vm/locking  

[10] VM_MAYREAD & VM_READ, kernelnewbies mailing list  

[11] The object-based reverse-mapping VM   

[12] Virtual Memory II: the return of objrmap  

[13] Cramming more into struct page   

[14] LWN kernel index # mmap_sem   

[15] Speculative page fault, linux-mm mailing list  

[16] per-VMA lock proposal  

[17] linux gorman book notes, Lorenzo Stoakes  

[18] RadixVM: Scalable address spaces for multithreaded applications