[PintOS] Project 3 : Virtual Memory - Anonymous Page

chohk10·2023년 5월 23일

PintOS

목록 보기

4/8

2. Anonymous Page

Non-disk based image called anonymous page.

An anonymous mapping has no backing file or device. It is anonymous because it does not have any named file source (unlike file-backed pages). Anonymous pages are used in executable, such as for stack and heap.

Anonymous page, struct anon_page anon, is included in its struct page, which contains generic information of a page.

Page Initialization with Lazy Loading

Lazy loading is a design where the loading of memory is deferred until the point at which it is needed.

A page is allocated, meaning there is page struct corresponding to it.
But there is no dedicated physical frame, and the actual content of the page is not yet loaded.
The contents will be loaded only at which it is truly needed, which is signaled by a page fault.

General page initalization flow

vm_alloc_page_with_initializer is invoked when the kernel receives a new page request.
1. Initializer will initialize a new page by allocating a page structure and setting appropriate initializer depending on its page type
2. Return the control back to the user program
As the user program executes, at a point, a page fault occurs because the program is trying to access a page which it believes to possess but the page has no contents yet. (lazy loading)
During the fault handling procedure, uninit_initialize is invoked and calls the initializer set earlier.
- initializer will be anon_initializer for anonymous pages and file_backed_initializer for file-backed pages.

Lazy Loading for Executable

When a process starts it execution, only the memory parts that are immediately needed are loaded onto the main memory. Reduces the overhead compared to eager loading as a result.

To support the lazy loading, a page type called VM_UNINIT is used.
All pages are initially created as VM_UNINIT pages!
Page structure for uninitialized pages - struct uninit_page
Functions for creating, initializing, and destroying uninitialized pages can be found in include/vm/uninit.c.

On page fault, the page fault handler (page_fault in userprog/exception.c) transfers control to vm_try_handle_fault in vm/vm.c
Which first checks if it is a valid page fault
- By valid, we mean the fault that accesses invalid
- There are three cases of bogus page fault:
  1. lazy-loaded,
  2. swaped-out page, and
  3. write-protected page (See Copy-on-Write (Extra)).
- For now, just consider the first case, lazy-loaded page.
If it is a bogus fault, you load some contents into the page and return control to the user program.
- If it is a page fault for lazy loading, the kernel calls one of the initializers previously set in vm_alloc_page_with_initializer to lazy load the segment.

`vm_alloc_page_with_initializer`

bool vm_alloc_page_with_initializer (enum vm_type type, void *va,
        bool writable, vm_initializer *init, void *aux);

Create an uninitialized page with the given type.
The swap_in handler of uninit page automatically initializes the page according to the type, and calls INIT with given AUX. (This fuction sets everything up so that this will be possible in the later on step)
Once you have the page struct, insert the page into the process's supplementary page table.
Using VM_TYPE macro defined in vm.h can be handy.

Things to Implement :

Fetch an appropriate initializer according to the passed vm_type
Create "uninit" page struct by calling uninit_new with the initializer fetched
Modify the field after calling the uninit_new

What this function does :

check if the virtual address is already in the spt table
dtnamically allocate memory for the page structure (if allocation fails, goto error section)
according to the given page type, fetch the appropriate initializer (if type is not among the specified, free memory allocated for page struct and goto error section)
set the page struct as a new uninit page using uninit_new()
modify members of page struct (i.g. writable flag)
insert the page into the spt (if insertion fails, free memory for page struct and goto error section)
return true if ecerything was successful, false if something had failed

👉🏻 lazy loading을 하기 때문에 페이지를 할당받아도, 해당 페이지에 들어갈 contents는 실제로 로딩을 하지는 않는다. 그저 페이지 struct를 만들어서 페이지 테이블에 넣어둘 뿐이다.
👉🏻 load 함수는 load_segment 함수를 부르며, load_segment는 VM_ANON 타입으로 vm_alloc_page_with_initializer를 부른다.
👉🏻 vm_alloc_page_with_initializer는 페이지를 할당받는 함수로, uninitialized type으로 페이지를 초기화 해주며, 해당 페이지에 들어갈 예정인 페이지 타입에 맞게 operation에 사용할 함수들과 init에 사용할 함수(i.g. lazy_load_segment()) 등을 미리 넣어두고 이 페이지를 페이지 테이블에 넣어둔다.
👉🏻 그래서 나중에 페이지 테이블 엔트리에 들어가있는 해당 내용을 참조하고자 할 때 엔트리는 있지만 실제 페이지는 생성이 되어 있지 않으므로 page fault가 발생하며, 이렇게 처음으로 page fault 발생 시 현재 해당 페이지를 uninit 타입이기 때문에 uninit_initialize 함수를 호출하게 된다. (아마도)

`uninit_initialize`

The page fault handler follows its call chain, and finally reaches uninit_intialize when it calls swap_in. We give the complete implementation for it. Although, you may need to modify the uninit_initialize according to your design.

static bool uninit_initialize (struct page *page, void *kva);

Initializes the page on the first fault
template code first fetches vm_initializer and aux
calls the corresponding page_initializer through a function pointer.

What this function does :
1. get uninit_page struct from page struct
2. run the initializer which was set previously according to the page type (VM_ANON in the case of load_segment()) => returns true if successful, else returns false
3. if there is an init function set in the uninit_page struct, run the init function with the aux arguments also passed through uninit_page struct => returns true if successful, else returns false. if there is no init function, pass true so that the results will only depend on the result of the initializer function
4. return true if both initializer and init succeedes, if any fails, return false

`vm_anon_init`, `anon_initializer`

May modify vm_anon_init and anon_initializer in vm/anon.c according to needs.

void vm_anon_init (void);

Initialize for anonymous page subsystem. In this function, you can setup anything related to the anonymous page.

👉🏻 당장은 어떤걸 initiate 해야하는지 모르기 때문에 일단 넘어감! 아마도 anonymous 페이지는 내용이 없는 상태로 시작하기 때문에 zero fill을 해주는 내용이 들어가지 않을까 생각함

bool anon_initializer (struct page *page,enum vm_type type, void *kva);

first sets up the handlers for the anonymous page in page->operations
might need to update some information in anon_page, which is currently an empty struct
used as initializer for anonymous pages (i.e. VM_ANON)

👉🏻 우선은 어떤게 필요할지 모르기 때문에 넘어감

`load_segment`, `lazy_load_segment`

Implement load_segment and lazy_load_segment in userprog/process.c.

Implement segment loading from executables. All of these pages should be loaded lazily, that is, only as the kernel intercepts page faults for them.
You'll need to modify the core of the program loader, which is the loop in load_segment of userprog/process.c. Each time around the loop, it makes a call to vm_alloc_page_with_initializer to create a pending page object. When a page fault occurs, this is when the segment is actually loaded from the file.

static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
        uint32_t read_bytes, uint32_t zero_bytes, bool writable);

Current code calculates the number of bytes to read from a file and the number of bytes to fill with zeros within the main loop. Then, it calls vm_alloc_page_with_initializer to create a pending object. You need to set up the auxiliary values as aux argument that you will provide to vm_alloc_page_with_initializer. You may want to create a structure that contains necessary information for the loading of binary.

Things to implement :

Set up aux to pass information to the lazy_load_segment.

static bool lazy_load_segment (struct page *page, void *aux);

You may have noticed that lazy_load_segment is supplied as the fourth argument of vm_alloc_page_with_initializer in load_segment. This function is the initializer for executable's pages and is invoked in times of page faults. It receives a page struct and aux as arguments. aux is the information you set up in load_segment. Using this information, you have to find the file to read the segment from and eventually read the segment into memory.

This is called when the first page fault occurs on address VA. VA is available when calling this function.

Things to implement :

Load the segment from the file (앞선 프로젝트에서 사용한 load 함수와 비슷하게!)

`setup_stack`

You should adjust the setup_stack in userprog/process.c to fit stack allocation into the new memory management system.

static bool setup_stack (struct intr_frame *if_);

The first stack page need not be allocated lazily.
You can allocate and initialize it with the command line arguments at load time, with no need to wait for it to be faulted in.
You might need to provide the way to identify the stack.
You can use the auxillary markers in vm_type of vm/vm.h (e.g. VM_MARKER_0) to mark the page.

Create a PAGE of stack at the USER_STACK. Return true on success.

Map the stack on stack_bottom and claim the page immediately.
If success, set the rsp accordingly.
You should mark the page as stack.

`vm_try_handle_fault`

Finally, modify vm_try_handle_fault function to resolve the page struct corresponding to the faulted address by consulting to the supplemental page table through spt_find_page.

/* Return true on success */
bool vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt = &thread_current ()->spt;
	struct page *page = NULL;

	page = spt_find_page(spt, pg_round_down(addr));

	if (page == NULL) {
		return false;
	}
  
	return vm_do_claim_page (page);
}

👉🏻 Problem : 커널 주소는 걸러줘야 하나?
Reasoning :
(유저는 당연히 유저 주소만 사용이 가능하고) 커널이 페이지에 접근하려고 할 때, aliasing을 위해 유저 주소만 사용하도록 하는 제약을 사용한다면 커널 주소는 걸러주는게 맞을거라고 생각한다.
다른 커널 함수들에서 유저 주소만 사용하도록 신경써서 구현한다고 하더라도 잘못되는 경우가 있을 수 있기 때문에 커널 주소가 들어온건 아닌지 이 함수에서 확인된다면 좋을 것 같다고 생각했다.
근데 애초에 유저 주소만 취급하는 spt table에 대해서 spt_find_page를 하기 때문에, 이미 커널 주소는 걸러진거라고 볼 수 있지 않을까 싶다.
spt_find_table도 해당 주소에 대해 테이블 엔트리를 찾지 못하면 NULL 값을 리턴하기 때문에 page == NULL에서 모두 걸러질 수 있다.
👉🏻 그런데.. 결국 uaddr는 frame에 접근하기 위해서 kernel address를 사용하는데, 그러면 항상 kernel address를 사용하고 있는 것이 되는거 아닌가? 나중에 유저 프로그램이 주소에서 데이터를 읽을 때 sup talble을 거치나?

After implementing all the requirements, all of the tests in project 2 except fork should be passed.

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
FAIL tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
FAIL tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
FAIL tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
FAIL tests/vm/pt-write-code
FAIL tests/vm/pt-write-code2
FAIL tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
FAIL tests/vm/page-parallel
FAIL tests/vm/page-merge-seq
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
pass tests/vm/page-shuffle
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL tests/vm/mmap-remove
pass tests/vm/mmap-zero
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass tests/vm/mmap-zero-len
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
pass tests/vm/lazy-anon
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL tests/vm/swap-fork
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
53 of 141 tests failed.

Supplemental Page Table - Revisit

Implement supplemental_page_table_copy and supplemental_page_table_kill

결과

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
FAIL tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
FAIL tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
FAIL tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
FAIL tests/vm/pt-write-code
FAIL tests/vm/pt-write-code2
FAIL tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
FAIL tests/vm/page-parallel
FAIL tests/vm/page-merge-seq
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
pass tests/vm/page-shuffle
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL tests/vm/mmap-remove
pass tests/vm/mmap-zero
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass tests/vm/mmap-zero-len
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
pass tests/vm/lazy-anon
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL tests/vm/swap-fork
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
53 of 141 tests failed.

Page Cleanup

Implement uninit_destroy in vm/uninit.c and anon_destroy

👉🏻uninit_destroy 의 경우, 메모리를 할당해주었던 aux를 free.

chohk10

이전 포스트

[PintOS] Project 3 : Virtual Memory - Memory Management

다음 포스트

[PintOS] Project 3 : Virtual Memory - Anonymous Page

PintOS

2. Anonymous Page

Page Initialization with Lazy Loading

Lazy Loading for Executable

`vm_alloc_page_with_initializer`

`uninit_initialize`

`vm_anon_init`, `anon_initializer`

`load_segment`, `lazy_load_segment`

`setup_stack`

`vm_try_handle_fault`

Supplemental Page Table - Revisit

결과

Page Cleanup

[PintOS] Project 3 : Virtual Memory - Memory Management

[PintOS] Project 3 : Virtual Memory - Stack Growth

0개의 댓글

[PintOS] Project 3 : Virtual Memory - Anonymous Page

PintOS

2. Anonymous Page

Page Initialization with Lazy Loading

Lazy Loading for Executable

vm_alloc_page_with_initializer

uninit_initialize

vm_anon_init, anon_initializer

load_segment, lazy_load_segment

setup_stack

vm_try_handle_fault

Supplemental Page Table - Revisit

결과

Page Cleanup

[PintOS] Project 3 : Virtual Memory - Memory Management

[PintOS] Project 3 : Virtual Memory - Stack Growth

0개의 댓글

`vm_alloc_page_with_initializer`

`uninit_initialize`

`vm_anon_init`, `anon_initializer`

`load_segment`, `lazy_load_segment`

`setup_stack`

`vm_try_handle_fault`