[PintOS] Project 2 : User Programs

chohk10·2023년 4월 29일

PintOS

목록 보기

2/8

[PintOS] Project 2 : User Programs

카이스트 자료 간단 번역
Appendix의 내용을 읽고 PintOS의 구조를 파악하는게 구현하는데 있어서 가장 도움이 됐던 것 같다.
일반적인 설명인줄 알고 처음엔 안읽었다가 뒤늦게 알고 읽게되어서 많이 아쉬웠다..

Introduction

userprog 디렉토리에서 주로 작업할 예정이지만, pintOS의 대부분을 살펴보면서 상호작용 해야한다. 프로젝트 1 위에 이어서 작업을 해야하는데, 이는 프로젝트 1의 코드가 프로젝트 2에 영향을 주지는 않지만 과거 테스트 케이스까지 쌓아서 평가를 하기 때문이다. Extra 과제의 경우, 제공되는 skeleton code 는 하나도 없으며, 테스트 케이스만 주어진다. (테스트를 돌리기 위해서는 userprog/Make.vars 파일을 조작해야한다.)

배경

이번 프로젝트에서는, 스레드가 아닌 프로세스를 다룰 예정이고, 각각의 프로세스는 하나의 스레드만 가지고 있도록 한다. 각각의 프로그램은 하나의 기계를 전부 사용하고 있도록 착각하게 된다. (컴퓨터 기계 전체에 대한 abstraction) => memory, scheduling, 그 외 state 들을 정확하게 다루어서 이 환영이 깨지지 않도록 해야한다.

프로젝트 1에서는 테스트 코드를 커널에 직접적으로 컴파일했기 때문에 특정한 함수 인터페이스가 커널 내에서 요구되었다. (어떤 인터페이스를 말하는걸까..?) 프로젝트 2에서는 사용자 프로그램에서 커널을 테스트하도록 한다. 사용자 프로그램은 주어진 조건들에 맞도록 해야하며, 이 조건들을 만족하는 선에서 커널 코드들을 자유롭게 수정해도 된다.
#ifdef VM 으로 감싸진 블록 내에는 코드에는 수정사항이 들어가면 안된다. (이 부분은 프로젝트 3에서 다루게 된다)

다루게될 소스 파일들

process.*, syscall.*, exception.*
그 외 : gdt.*(Global Descriptor Table - table that describes segments in use - 전체 핀토스 프로젝트에서 이파일을 조작할 일은 없음), tss.*(Task-State Segment - ring switching 에서 stack pointer를 찾는 역할 - 프로세스가 인터럽트 핸들러에 들어가면 하드웨어는 커널의 stack pointer를 찾아달라고 이 코드를 호출하게 된다. 전체 프로젝트에서 코드를 수정할 일은 없음)

File System 사용하기

사용자 프로그램은 파일시스템에 로드되며, 앞으로 다둘 시스템 콜의 대부분은 이 파일시스템과 관련되어있다. 하지만 이번 프로젝트의 주요 포인트는 파일 시스템이 아니기 때문에 심플한 시스템을 핀토스에서 제공한다. -> filesys.* 파일의 코드들을 살펴보는 것이 좋다! (어떻게 동작하며 어떤 한계가 있는지 확인)
파일시스템 파일을 조작할 필요 절대 없고, 이번 프로젝트에서 제대로 파일시스템의 루틴을 파악한다면 프로젝트 4 때 삶이 편해질 것이다 (비교적).
한계점들 : 내부 동기화 없음 -> 동기화를 직접 사용해서 하나의 프로세스만 접근하도록 해줘야 함, 생성할 때 파일 사이즈가 결정되며 루트 디렉토리도 마찬가지이므로 생성할 수 있는 파일의 총량도 한정되어있음, allocation extent가 한정되어있어서, 사용할 공간을 늘릴 수가 없음 따라서 외부 단편화가 심각해질 수 있음, subdirectory 없음, 파일명은 14글자로 한정, 시스템 중간에 crash 가 발생하면 저절로 고칠 수 있는 방법이 없음,
filesys_remove() 가 구현되어있어서, 파일이 열려있는 상태에서 제거를 하면, block들이 deallocate되지 않아서 그 파일에 접근하는 코드가 있는 다른 스레드가 언제든지 접근할 수 있다(?)

프로젝트 1에서는 커널 이미지에 테스트 프로그램들이 존재했던 것에 비해 이번 프로젝트에는 사용자 스페이스에서 돌아가는 테스트 프로그램들을 핀토스 VM에 넣어주어야 한다. make check 스크립트가 알아서 해주겠지만, 어떻게 동작하는건지 알아두면 개별 테스트 케이스를 다루는데 도움이 될 것이다. (그 밑에는 어떻게 하는건지에 대한 설명)

사용자 프로그램이 어떻게 동작하는지

메모리 안에 들어가는 사이즈이고, 우리가 만드는 시스템 콜만 사용했을 때, C로 작성된 프로그램이 핀토스에서 잘 돌아간다. 다르게 말하면 이 조건에 맞지 않는다면 돌아가지 않는다는 뜻이다. 예를들어, 이 프로젝트에서 사용되는 시스템 콜들 중에 메모리 할당을 하는 것이 없기 때문에 malloc() 구현이 불가능하다. floating point operation도 불가능하다.
PintOs에서도 userprog/process.c 에서 제공되는 로더를 통해 object file, shared libraried, executables 등에 사용되는 ELF 파일 형식을 로딩할 수 있다. (이하 해당 파일 관련 설명)

가상 메모리 레이아웃

PintOS의 가상 메모리는 사용자 공간과 커널 공간으로 나누어져 있다. (커널 공간 기본 설정에 대한 설명)
사용자 공간은 프로세스 별로 할당되게 된다. 커널이 하나의 프로세스에서 다른 프로세스로 넘어갈 때 가상 주소 공간 역시 바뀐다. (프로세서의 페이지 디렉토리 기반 레지스터 pml4_activate() in thread/mmu.c) 각각의 스레드 구조체는 프로세스의 페이지 테이블에 대한 포인터를 가지고 있다.
커널 가상 공간은 항상 매핑이 같으며, 사용자 프로세스와 커널 스레드가 실행되는 것에 영향을 받지 않는다. PintOS에서 커널공간은 물리 메모리에 1대1 매핑이 되어있다. (이하 자세한 설명)
사용자 프로그램은 자신의 가상 메모ㄹ 공간만 사용할 수 있으며 커널 공간을 접근하려고 하면 page fault가 발생하며, 핸들러에 의해 프로세스가 종료된다.
커널 스레드는 커널 메모리 공간과 사용자 메모리 공간 모두 접근할 수 있다. 그러나 커널도 매핑이 되지 않은 사용자 가상 메모리 공간에 접근하려고 하면 page fault가 발생한다.

일반적인 메모리 레이아웃

(스택, BSS, data segment, code segment 등 일반적인 설명)
프로젝트 2에서는 스택의 크기가 고정되어있지만 프로젝트 3에서는 확장이 가능할 것이다. 일반적으로는 시스템 콜을 통해서 data segment의 사이즈 조정이 가능하지만 PintOS에서는 구현되어있지 않다. (이하 code segment 위치에 대한 설명)
각각의 프로그램 segment의 이름과 위치를 알려주는 "linker script"에 따라서 linker가 사용자 프로그램의 메모리 레이아웃을 설정한다. (자세한 내용을 볼 수 있는 방법에 대한 설명)

사용자 메모리 공간 접근

시스템 콜을 통해 사용자 프로그램이 넘겨주는 포인터를 가지고 커널은 메모리에 자주 접근하게 된다. 사용자 프로그램이 null pointer를 보낼 수도 있고, 매핑되지 않은 메모리 공간에 대한 포인터를 넘겨줄 수도 있고, 커널의 메모리 공간에 대한 포인터를 넘겨줄 수도 있으니 이러한 invalid 포인터를 거부하고 커널과 다른 프로세스에 안좋은 영향을 주지 않도록 잘못된 값을 요청하는 프로세스를 죽이고 그 프로세스의 자원을 free 해주어야 한다.
방법 1 : 받은 포인터를 dereference 해서 값의 유효성을 검증
thread/mmu.c 와 include/threads/vaddr.h 의 함수들을 확인하면 된다. 사용자의 메모리 접근을 관리하는 제일 간단한 방법이다.
방법 2 : 사용자가 넘겨준 포인터가 KERN_BASE 밑으로만 가리키는지 확인한 후 역참조(??)
유효하지 않은 포인터는 page fault를 발생시킬 것이고, page_fault() 함수를 수정해 핸들링 할 수 있다. 프로세서의 MMU의 이점을 잘 사용하기 때문에 보통 속도가 더 빠르다. 따라서 실제 커널 프로그램에서 사용되는 편이다.

어느 방법이든 자원의 leak를 조심해야한다. (이하 자세한 내용)

Overview of Project 2

유저 프로그램은 특권 명령을 실행하기 위해 정해진 포맷과 시스템콜을 통해서, 하고자 하는 행동과 그에 필요한 데이터 등의 인자를 운영체제에게 보내준다. 운영체제는 이 내용을 받아서 적절한 validation을 거친 후 유저 프로그램이 원하는 내용을 처리해준다.
현재 PintOS에는 이러한 시스템콜이 구현되어있지 않은 상태이며, 직접 만들어야 한다.

Functions!

userprog/process.c

process_init : initd 등의 프로세스들을 초기화 해주는 역할
process_create_initd : 사용자 프로그램의 시작 (한번만 호출되어야 함)
- palloc_get_page : 비어있는 페이지를 얻는 함수. (argument에 따라 사용자 풀 또는 커널 풀에서 페이지를 할당받아 가져올 수 있으며, 0으로 데이터를 지워서 가져올 수도 있음)
- 새로 할당받은 비어있는 페이지에 file_name을 복제해 넣음
- 새로운 thread를 생성해서 initd 함수를 실행
- 스레드 생성을 실패하는 경우 할당받은 페이지를 free
- => tid를 return 하고, 이 정보를 바탕으로 run_task에서 해당 프로세스가 끝날 때까지 process_wait에서 기다리고 있음
initd : 사용자 프로세스의 첫 시작에 대한 스레드 함수
- process_init : 초기화
- process_exec : 현재 실행중인 context를 인자로 받는 내용으로 변경
process_exec : 현재 실행을 filename의 프로그램으로 switch
- intr_frame을 사용하지 못함(?)
- process_cleanup : 새로 실행할 내용을 로드하기 전에 현재의 context를 정리
- load : filename에 해당하는 실행파일을 로드
- palloc_free_page : filename을 저장하기 위해 사용했던 페이지를 free
- do_iret : 커널모드를 나감으로서 새로 세팅된 (switch된) 프로세스를 시작
process_wait : 자식 스레드가 끝나서 exit status를 돌려줄 때까지 기다린다.
- 커널에 의해 terminate 되었다면 return -1
- tid가 유효하지 않거나
- tid가 해당 프로세스의 자식 프로세스가 아니거나
- process_wait가 해당 tid에 대해서 이미 성공적으로 불려있다면
- 기다리지 않고 바로 return -1
- TODO : process_wait(initd)를 하는 경우 pintos가 종료되므로 무한루프를 먼저 만든 후 구현하도록 한다.
process_exit : 프로세스 종료. thread_exit 함수에 의해 불려짐
- TODO : 프로세스가 terminate 되었을 때의 메세지 작성
- 프로세스 자원 cleanup을 여기서 구현하는 것을 추천한다고 함
- process_cleanup
process_cleanup : 현재 프로세스의 자원을 free
- 현재 프로세스의 페이지 디렉토리를 파괴, kernel-only 페이지 디렉토리로 switch
process_activate : nest 스레드에서 사용자 코드를 실행할 수 있도록 CPU를 세팅
- 모든 context switch에서 해당 함수가 불린다.
- pml4_activate : 스레드의 페이지 테이블을 활성화
- tss_update : 프로세싱 인터럽트(?)를 위해서 스레드의 커널 스택을 세팅
load : filename의 ELF 실행파일을 현재 스레드로 로드, 실행파일의 엔트리 포인트를 rip에 저장, 초기 스택 포인터는 rsp에 저장
- 페이지 디렉토리를 활성화 하고 할당 (process_activate)
- 실행파일을 열어서 헤더를 읽고 verify (filesys_open, file_read)
- 프로그램 헤더를 읽기 (file_read)
- 스택 세팅 (setup_stack, 인터럽트 프레임 if_)
- 시작 주소 rip에 저장
- TODO : argument passing 구현
validate_segment
load_segment
setup_stack : USER_STACK에서 0으로 초기화한 페이지를 매핑함으로써 최소 스택을 생성
install_page : 사용자 주소공간과 커널 주소공간에 대한 매핑을 페이지 테이블에 추가한다.

userprog/syscall.c

과거에는 시스템콜 관련 서비스들은 인터럽트 핸들러에서 다뤄졌었다. 그러나 x86-64 부터는 시스템콜 instruction으로 시스템콜을 요청하는게 훨씬 효율적이게 되었다.
Model Specific Registe(MSR)의 값을 읽음으로서 실행된다.
syscall_init
syscall_handler : system call interface
- TODO : 세부 내용 작성
- thread_exit() (이걸로 시스템콜 핸들러를 종료하는건가?)

기타 함수

userprog/process.c

process_fork : 현재 프로세스를 복제해서 새로운 이름을 부여
- __do_fork 함수에 대해서 스레드 생성
duplicate_pte : 해당 함수를 pml4_for_each 함수에 넘겨줌으로써 부모의 주소공간을 복제
- 구현해야하는 사항 TODO
  1. 부모 페이지가 커널 페이지라면 return
  2. 부모 페이지 level 4 map(pml4) 에서 va를 가져온다(?)
  3. 자식 프로세스를 위한 새로운 PAL_USER 페이지를 할당하고 결과물을 newpage에 저장
  4. 부모의 페이지를 새로운 페이지로 복제 -> 부모의 페이지에 쓰기가 가능한지 확인 -> 결과에 따라 writable bool 설정
  5. 자식의 페이지 테이블에 새로운 페이지를 추가 (va주소에 writable permission을 가지도록 설정)
__do_fork : 부모의 실행에 대한 context를 복사하는 thread 함수
- parent->tf는 userland context를 가지고 있지 않다고 함 따라서 process_fork의 두번째 인자도 이 함수까지 가지고 와야한다고 함
- TODO : parentif. 를 가져오기 (예를들어, process_fork의 if)
- CPU의 문맥을 읽어서 local stack에 저장한다
- PT 복제(?)
  - pml4_create
  - process_activate
  - duplicate_pte 함수에 대해서 pml4_for_each가 아니면 (?) goto error (thread_exit)
- TODO : file_duplicate 함수를 사용해서 파일 오브젝트를 복제. 이 함수가 모든 자원의 복제를 완수하기 전까지 부모는 fork()에서 return 하면 안됨
- process_init
- do_iret : 새로 생성된 프로세스로 switch

⭐️ Function Flow ⭐️

init.c

main()
read_command_line <- pintos 이하의 argument가 들어옴 (추측)
parse_options <- pintos 프로그램의 option을 확인 (-q 끝나고 전원 끄기, -f 파일시스템 관련 등) + option이 아닌 첫번째 argument에 대한 포인터(argv)를 return
run_actions(argv) : argv에서 수행할 task 단위로 실행 -> 이번 프로젝트에서 해당하는건 'run' task와 관련된 것 뿐
- 'run'은 인자의 개수가 2개이며, 'run'과 이하 실행할 프로그램에 대한 문장 두가지를 run_tasks 함수로 넘김
run_tasks : process_create_initd(task) 를 통해 프로그램을 실행하며, process_wait를 통해서 해당 프로그램이 종료하기를 기다림
TODO: process_wait 구현해야함

process.c

process_create_initd
thread_create(file_name, PRI_DEFAULT, initd, fn_copy) : file_name -> thread->name, initd -> function, fn_copy -> aux (initd 함수에 들어가는 듯)
initd(fn_copy)
process_exec(fn_copy)
load(file_name)
do_iret(interrupt_frame) : interrupt out (get out of kernel) & start user mode!

1. Argument Passing

x86-64 Calling Convention

사용자 레벨의 프로그램은 정수 레지스터를 사용해 %rdi, %rsi, %rdx, %rcx, %r8, %r9 시퀀스를 넘긴다.
호출 함수는 다음 instruction의 주소(return address)를 stack에 push 하며, 호출받은 함수의 첫 instruction으로 jump 한다.
호출받은 함수가 실행된다.
호출받은 함수가 리턴값이 있다면 RAX 레지스터에 그 값을 저장한다.
호출받은 함수는 스택에서 return address를 pop 하여 그 주소로 x86-64 RET instruction 을 사용해 jump 함으로써 return 한다.

Argument Passing for PintOS

command를 단어 단위로 쪼갠다.
단어들을 tack의 가장 위쪽에 위치시킨다. 포인터로 참조할 예정이기 때문에, 스택에 단어가 들어가는 순서는 상관없다.
각 단어의 주소와 null pointer 센티넬을 역순으로(오른쪽에서 왼쪽으로) 스택에 push 한다.
- null pointer 센티넬은 argv[argc] 가 null pointer임을 확인시켜주는 역할을 한다. (C 표준에 따라서)
- 역순으로 스택에 추가함으로써 argv[0]가 가상 주소공간의 가장 낮은 주소에 위치할 수 있도록 해준다.
- Word 단위로 align 되어 있을 때 접근하는 것이 align 되지 않은 것에 비해 속도가 빠르다. 따라서 최고의 성능을 위해서는 스택에 처음 push 하기 전에 stack pointer를 8의 배수로 내림하는 것이 좋다.
%rsi는 argv를 가리키고 %rdi는 argc를 가리키도록 한다.
마지막으로, 가짜 return address를 스택에 push 한다. entry function은 return 할 일이 없긴 하지만, 다른 모든 stack frame과 동일한 구조를 가지도록 해야한다.

⭐️ Argument Passing 구현 ⭐️

Address of arguments in stack

Is it okay to just do this :
*(uintptr_t*) (stack_top + idx * sizeof(uintptr_t)) = arg_addrs[idx];
Or do I have to memcpy like this :
memcpy((void *)stack_top, &arg_addrs[idx], sizeof(uintptr_t));

Both ways are valid for storing the addresses in the reserved space on the stack. However, using a typecast to uintptr_t and direct assignment like (uintptr_t) (stack_top + idx sizeof(uintptr_t)) = arg_addrs[idx]; is a more concise and potentially faster approach than using memcpy.

Using memcpy to copy the address from arg_addrs to the stack involves an extra function call and copying of bytes, which can be slower than direct assignment using a typecast. However, using memcpy can be more robust in certain situations, such as when the types of the source and destination pointers are not the same or when the source data is not aligned properly.

In general, both approaches are valid and can be used depending on the specific requirements and constraints of your application.

Alignment and padding in stack

To determine how much padding to add after pushing the argument values into the stack, you need to calculate the difference between the stack pointer and the next higher multiple of 16.

The reason for aligning the stack on a 16-byte boundary is to comply with the System V AMD64 ABI (Application Binary Interface) specification, which requires that the stack pointer be 16-byte aligned at the time of a function call. This is important for efficient memory access and to ensure that the SSE registers are properly aligned.

일반적인 시스템에서 메모리 사용을 보다 효과적으로 하기 위해서 function call이 발생했을 때 stack pointer가 16byte 정렬이 되어있도록 한다. 따라서 이 조건을 만족하기 위해서 스택에 데이터를 push한 후 각 data의 주소와 return address를 push 하기 전에 8byte 또는 16byte에 정렬되도록 padding을 추가해준다.

In 64-bit architectures, the natural alignment for data types that are 8 bytes or smaller is 8 bytes. However, aligning the stack to a 16-byte boundary can improve performance because it allows for more efficient memory access by the processor. This is because many modern processors have a cache line size of 64 bytes, and aligning the stack to a 16-byte boundary ensures that each cache line contains data from only one stack frame. This can reduce cache misses and improve overall performance. Additionally, some instructions may require 16-byte alignment for proper execution, so aligning the stack to a 16-byte boundary can also prevent issues with instruction execution.

많은 운영체제에서는 8byte가 아닌 16byte 정렬을 사용한다. 그러나 PintOS에서는 8byte로 정렬을 하라고 나와있기 때문에 8byte 정렬로 구현하면 된다. 8byte로 구현하는게 사실 더 간단하다.

The alignment requirement of the return address on the stack depends on the total size of the arguments pushed onto the stack before it. If the total size of the arguments is a multiple of 16 bytes, then the return address can be placed directly on a 16-byte boundary. If not, padding bytes will need to be added to align the return address properly. The padding size is calculated as the difference between the total size of the arguments and the nearest lower multiple of 16 bytes. Once the padding is added, the return address can be placed at the top of the stack on a 16-byte boundary.

스택이 시작하는 지점(주로 return address가 들어가는 부분)을 16byte로 align 시키기 위해서는 argument 주소값을 push 하기 전에 padding을 준다. 이 padding의 크기는 argument의 개수, 데이터의 크기 등에 따라 달라져야할 것이라 생각한다. 8byte로 정렬해주면 되는 PintOS에서는 그저 데이터를 모두 push하고 난 후의 stack top을 8byte로 정렬해주면 그만인데, 16byte로 정렬하기 위해선 앞으로 들어올 내용의 크기에 따라 8byte를 추가로 넣어줘야할지 등을 결정해줘야 할 것이라 생각한다. ChatGPT는 이러한 방법이 실제 운영체제에서 채택되는게 맞다고 닫변해주긴 했지만, 진실인지는 잘 모르겠다.

To execute the system call in the context of the calling process, the kernel needs to set up the user stack with the appropriate arguments. The kernel will typically allocate a block of memory for the user stack and copy the arguments into it, taking care to align the stack pointer (RSP) to a 16-byte boundary before executing the system call.

Once the kernel has finished setting up the user stack with the necessary arguments for the system call, it executes the system call instruction. The system call instruction transfers control from the user program to the kernel, which then executes the corresponding system call.

Function call이 발생하면 위와 같은 사항들을 고려해 8byte 또는 16byte alignment에 맞춰서 stack을 세팅해주며, 스택 세팅이 완료되면 function call에 대한 instruction이 실행된다.

Registers

각각의 역할과 함수 호출에서의 역할

범용 레지스터 (General Purpose Register)
- 상수나 주소를 저장하는 등의 목적
- 64비트가 되면서 레지스터의 크기가 증가했으며, R8, R9, ..., R15 레지스터가 추가되었다.
- 산술 연산 레지스터
  - rax : 산술 논리 연산, 함수의 리턴값을 저장
  - rbx : 간접 주소 저장?, 산수/변수 저장, 호출 받는 함수(callee)가 내용을 저장하는 레지스터
  - rcx : 반복문의 반복 횟수 저장(counter), 문자열 처리, 4번째 argument 전달
  - rdx : rax의 보조적인 역할, 3번째 argument 전달
- 인덱스 레지스터
  - rsi(source index) : 복사나 비교할 때 사용되는 소스 문자, 출발지 주소를 저장, 두번째 argument 전달 (argv를 가리킴)
  - rdi(destination index) : 복사나 비교를 할 때 사용되는 목적지 주소를 저장, 첫번째 argument 전달 (argc를 가리킴)
- 포인터 레지스터
  - rsp(stack pointer) : stack top을 가리킴, 프로그램이 함수를 호출하며 리턴 주소와 argument 등을 스택에 push 하며, 그에따라 rsp 위치는 조정이 된다.
  - rbp(base pointer) : stack base(스택의 제일 바닥 부분, 기준점)을 가리킴, rbp 밑에는 return 값이 있음, 호출 받는 함수(callee)가 내용을 저장하는 레지스터
IP (Instruction Pointer) (= PC, Program Counter)
- CPU가 처리해야하는 다음 명령어의 주소를 가리키는 레지스터
- CPU는 rip가 가리키는 주소의 명령어를 실행하고, 포인터는 크기만큼 이동하여 다음 명령어를 가리키도록 함
- jump, call, ret 등의 분기문을 통해 다른 사이클로 변경할 수 있다.
세그먼트 레지스터 (Segment Register)
- cs(code segment) : 코드 영역을 가리키는 레지스터, 데이터 이동 명령으로 값을 변경할 수 없으며 jump 또는 인터럽트 관련 명령으로만 변경 가능
- ss(stack segment) : 스택 영역을 가리키는 레지스터, sp, bp 등 레지스터를 통해 스택에 접근할 때 암시적으로 사용됨
- ds(data segment) : 데이터 영역을 가리키는 레지스터
- es(extra segment), fs, gs : 데이터 관련 확장 레지스터
컨트롤 레지스터 (Control Register)
- 운영체제의 모드를 변경하고, 현재 운영 중인 모드의 기능을 제어
- cr0, cr1, cr2, cr3, cr4, cr8
- 캐시 기능, 페이징 기능 등
E-flag 레지스터
- extended flag registers
- 시스템 제어용 플래그, 조건처리, 상태 저장 등의 용도

Callee-saved Registers

Callee-saved registers are a subset of registers that are used in some programming languages and calling conventions to preserve the state of the callee (the called function) across a function call. These registers are typically preserved by the callee, meaning that if the callee modifies the register, it is responsible for restoring the original value before returning control to the caller. The caller can therefore assume that the values in these registers will remain unchanged after a function call.

The purpose of callee-saved registers is to prevent the callee from modifying the state of the caller unintentionally. If the caller relies on a particular register to hold a value, and the callee modifies that register without restoring it, the caller's program may behave unexpectedly or even crash.

The specific set of callee-saved registers varies depending on the architecture and calling convention used. Typically, the registers that are considered callee-saved are those that the caller expects to remain unchanged after a function call. In some architectures, the set of callee-saved registers may be fixed, while in others, the programmer may have the option to specify which registers should be preserved across a function call.

In summary, callee-saved registers are a subset of registers that are preserved by the callee to maintain the state of the caller across a function call. They are used to prevent unintended modification of the caller's state and to maintain consistency in the program's behavior.

호출받은 함수는 해당 레지스터의 값을 보존해야하며, 호출한 함수에게 제어권이 넘어가기 전에 값을 원래대로 돌려놓을 의무가 있다. 그럼으로 인해 호출한 함수는 해당 레지스터의 값이 함수 호출에도 변하지 않을 것이라는 것을 보장받는다. callee-saved 레지스터의 목적은 callee가 caller의 상태값을 실수로 바꾸지 않도록 하는 것이며, caller는 바뀌지 않고 사용할 값을 저장하는 용도로 사용한다.

2. User Memory Access

syscall을 구현하기 위해서는 가상 메모리에 데이터를 읽고 쓰는 기능이 제공되어야 한다. Argument을 가져올 때는 이 기능이 필요없지만, 시스템콜의 인자로 제공된 포인터에서 데이터를 읽어올 때에는 이 기능을 통해야 한다(좀 까다로울 수 있다) : 사용자가 유효하지 않은 포인터를 넘겨준다면? 커널 메모리에 대한 포인터라면? 혹은 유효하지 않은 공간이나 커널 메모리 공간을 일부 포함하고 있는 블록을 가리키고 있다면? 이러한 케이스에 대해서 사용자 프로세스를 종료시킴으로서 핸들링을 해야한다.

=> 시스템콜이 발생했을 때 OS는 유저 프로그램이 보낸 포인터가 유효한지 검증을 해야한다. Systemcall handler를 구현하면서 같이 구현하자.

3. System Calls

시스템콜 기반 구조를 구현하기

현재 PintOS에 구현되어있는 시스템콜 핸들러는 시스템콜이 들어오는 경우 프로세스를 죽임으로서 처리를 해주고 있다. 우리는 system call number, argument 등을 얻어서 적절한 행동을 취할 수 있도록 구현을 해야한다.

System Call Details

프로젝트 1에서는 타이머와 I/O 장치와 같이 CPU 외부의 독립적인 장치에 의한 'external' interrupt로 인해 운영체제가 유저 프로그램으로부터 제어권을 넘겨받는 방법을 다뤘다.

운영체제는 프로그램의 코드에서 발생하는 software exception도 다룬다. (예, page fault, division by zero 등) 이러한 exception은 유저 프로그램이 운영체제에게 서비스(system call)를 요청하는 방법이기도 하다. (👉🏻: exception은 두 가지 1. external device 로부터의 hw interrupt = interrupt, 2. user로 부터의 sw exception= fault, trap, abort)

과거에 시스템콜은 software exception과 동일하게 다루어졌는데, 지금은 시스템콜을 위한 instruction이 추가되어 사용되고 있다. PintOS에서도 시스템콜 수행 전에 system call number와 argument를 레지스터에 저장해주면 되는데, 일반적인 방법과는 다르게 rax는 system call number 이며, 4번째 argument는 rcx가 아닌 r10을 사용한다. (rax - rdi, rsi, rdx, r10, r8, r9 순서로 사용)

시스템콜을 호출하는 유저 프로세스에서 레지스터는 커널 스택에 존재하는 interrupt frame을 넘겨받기에 접근이 가능하다. x86-64 관례에 의하면 함수의 리턴값을 rax 레지스터에 저장하는 것이다. 값을 리턴하는 Systemc call도 interrupt frame의 rax 요소의 값을 수정하는 방식으로 이 관례를 따를 수 있다.

System call to implement

각 시스템콜에 대한 system call number는 syscall-nr.h에 정의되어있다.
include/lib/user/syscall.h를 포함하는 유저 프로그램이 볼 수 있는 시스템콜 함수들:
(include/lib/user 디렉토리의 모든 헤드파일에서 정의된 함수들은 오로지 유저 프로그램에 의해서만 사용된다.)

void halt (void);
void exit (int status);
pid_t fork (const char *thread_name);
int exec (const char *cmd_line);
int wait (pid_t pid);
bool create (const char *file, unsigned initial_size);
bool remove (const char *file);
int open (const char *file);
int filesize (int fd);
int read (int fd, void *buffer, unsigned size);
int write (int fd, const void *buffer, unsigned size);
void seek (int fd, unsigned position);
unsigned tell (int fd);
void close (int fd);

4. Process Termination Message

유저 프로세스가 종료될 때 마다 프로세스 이름과 exit 코드를 다음과 같은 형식으로 출력한다.

printf ("%s: exit(%d)\n", ...);

프로세스 이름은 fork()에 전달되는 이름 전체여야 한다. 유저 프로세스가 아닌 커널 스레드가 종료하는 상황이거나, halt 시스템 콜이 호출되는 상황이라면 이 메세지를 출력하지 않는다. 프로세스가 load 되는데 실패하는 경우 메세지 출력여부는 선택적이다. 그 외에, 처음 제공된 상태의 PintOS가 아직 인쇄하지 않는 다른 메세지는 디버깅 시 유용할 수 있으나, 성적 스크립트에 혼란을 줘 낮은 성적을 받을 수 있기 때문에 인쇄하지 않는게 좋다.

5. Deny Write on Executables

실행파일로 사용 중인 파일, 즉 실행중인 파일에 쓰기를 거부하는 코드를 추가. 디스크에서 수정되는 중인 코드를 어떤 프로세스가 실행하려고 한다면 어떤 예측하지 못한 결과가 발생할지 모르기때문에 많은 운영체제들이 이러한 조치를 취하고 있다. 이부분은 프로젝트 3에서 가상 메모리를 구현하면 특히 더 중요해지는데, 지금 한다고 손해는 아니다.

file_deny_write() 함수를 사용해 모든 열려있는 파일에 대해 쓰기를 막을 수 있다. 해당 파일에 대해 해당 함수를 다시 부르게 되면 다시 쓰기 기능을 가능케 할 수 있다(해당 파일을 열고있는 다른 곳에서 쓰기를 막고있는게 아니라면). 또한, 파일을 닫아도 쓰기가 가능해진다. 그러므로, 어떤 프로세스의 실행파일에 대해 쓰기를 막기 위해서는 프로세스가 돌아가는 동안 해당 파일을 계속 열려있어야 한다.

⭐️ Syscall 구현 ⭐️

syscall handler

interrupt frame에 저장된 레지스터 값 중 rax에 system call number가 저장되어 있다. rax의 값을 가져와서 syscall_nr.h에 정의된 enum 값에 따라 상황에 맞는 syscall 함수를 호출하도록 swtich-case문을 사용한다. 각각의 syscall에 따라서 argument를 1개 받는 것도, 3개를 받는 것도, 다양하게 있는데, 레지스터 순서대로 rdi, rsi, rdx, r10, ... 레지스터의 값을 인자의 개수만큼 차례대로 함수에 넘겨준다.

exit

void exit (int status);

Terminates the current user program, returning status to the kernel. If the process's parent waits for it (see below), this is the status that will be returned. Conventionally, a status of 0 indicates success and nonzero values indicate errors.

현재 프로그램을 종료시키며, 커널에게 status를 돌려준다. 부모 프로세스를 해당 프로세스를 기다리고 있다면 여기서 입력되는 status가 부모에게 전달된다. 관례에 따라 0은 성공, 0이 아닌 값은 에러를 의미한다.

해당 status는 exit 함수의 caller가 결정하며, 커널에서 강제 종료시키는 경우 -1, 정상 종료하는 경우 0 등의 값을 넘긴다. 커널에서 강제 종료시킨다면 커널의 프로세스 중에서 exit(-1)과 같이 부를 것이고, 유저 프로그램에 의해 syscall을 통해서 불러진다면 caller는 인터럽트 프레임의 rdi 필드에 exit status 값을 저장해 argument로 넘겨줄 것이다. 그러면 exit 함수는 thread struct에 해당 exit status를 저장해줌으로써 해당 스레드(프로세스)의 부모가 exit status를 확인할 수 있도록 해준다.

thread_exit() 을 사용
-> process_exit()을 호출
-> interrupt disable
-> 현재 스레드는 THREAD_DYING 상태로 변경하며, 다음 스레드로 schedule()

process_exit()
-> process_cleanup()
-> TODO : implement sema, fd

fork

pid_t fork (const char *thread_name);

Create new process which is the clone of current process with the name THREAD_NAME. You don't need to clone the value of the registers except %RBX, %RSP, %RBP, and %R12 - %R15, which are callee-saved registers. Must return pid of the child process, otherwise shouldn't be a valid pid. In child process, the return value should be 0. The child should have DUPLICATED resources including file descriptor and virtual memory space. Parent process should never return from the fork until it knows whether the child process successfully cloned. That is, if the child process fail to duplicate the resource, the fork () call of parent should return the TID_ERROR.

The template utilizes the pml4_for_each() in threads/mmu.c to copy entire user memory space, including corresponding pagetable structures, but you need to fill missing parts of passed pte_for_each_func (See virtual address).

입력되는 thread_name을 이름으로 가진 현재 프로세스의 복제본을 생성한다. callee-saved 레지스터인 %RBX, %RSP, %RBP, and %R12 - %R15 를 제외하고는 레지스터의 값을 복제해올 필요 없다. 생성되는 자식 프로세스의 pid(tid)를 리턴값으로 꼭 돌려줘야 하며, 그렇지 않는 경우 자식의 pid는 유효하지 않아야 한다. 자식 프로세스에서의 리턴값은 0이어야 한다. 자식은 file descriptor와 가상 메모리 공간을 포함한 부모의 자원의 복제본을 가지고 있어야 한다. 부모 프로세스는 자식 프로세스가 성공적으로 복제된 것을 확인하기 전까지는 fork 함수에서 return해서는 안된다. 즉, 자식 프로세스가 부모 자원의 복제를 실패하는 경우 부모의 fork 호출은 tid_error을 return 해야한다.

주어진 템플릿은 threads/mmu.c에서 제공하는 pml4_for_each()를 사용해 사용자 메모리 공간 전체를 복사하고 있다. 해당하는 페이지 테이블 구조를 모두 포함해서. 하지만 여전히 pte_for_each_func의 빠진 부분들을 채워야 한다.

callee-saved 레지스터는 caller 입장에서 값이 유지될 것을 보장받는 레지스터이며, 프로세스를 fork할 때에도 해당 레지스터 값들은 복제가 되어야 한다.
process_fork(thread_name, intr_frame) 을 사용
-> thread_create() : current thread에 대해서 __do_fork

exec

int exec (const char *cmd_line);

Change current process to the executable whose name is given in cmd_line, passing any given arguments. This never returns if successful. Otherwise the process terminates with exit state -1, if the program cannot load or run for any reason. This function does not change the name of the thread that called exec. Please note that file descriptors remain open across an exec call.

현재의 프로세스를 cmd_line을 통해 받은 이름을 가진 실행파일로 변경하며, cmd_line으로 함께 받은 argument는 pass 해준다. 실행에 성공한다면 해당 함수는 절대 return 하지 않는다. 프로그램이 로드되지 않는다거나, 모종의 이유로 실행이 되지 않는 등 실행에 실패한다면 해당 프로세스는 exit state -1 로 종료한다. 이 함수는 이 함수를 부른 thread의 이름을 변경하지 않는다. file descriptor는 exec 호출의 처음부터 끝까지 열린 채로 유지된다는 것을 주의할 것.

wait

int wait (pid_t pid);

Waits for a child process pid and retrieves the child's exit status. If pid is still alive, waits until it terminates. Then, returns the status that pid passed to exit. If pid did not call exit(), but was terminated by the kernel (e.g. killed due to an exception), wait(pid) must return -1. It is perfectly legal for a parent process to wait for child processes that have already terminated by the time the parent calls wait, but the kernel must still allow the parent to retrieve its child’s exit status, or learn that the child was terminated by the kernel.

wait must fail and return -1 immediately if any of the following conditions is true:

pid does not refer to a direct child of the calling process. pid is a direct child of the calling process if and only if the calling process received pid as a return value from a successful call to fork. Note that children are not inherited: if A spawns child B and B spawns child process C, then A cannot wait for C, even if B is dead. A call to wait(C) by process A must fail. Similarly, orphaned processes are not assigned to a new parent if their parent process exits before they do.

The process that calls wait has already called wait on pid. That is, a process may wait for any given child at most once.

자식 프로세스를 기다린 후 자식 프로세스의 exit status를 가져온다. pid의 프로세스가 아직 살아있다면 해당 프로세스가 끝날 때까지 기다린다. 자식 프로세스가 종료되면, 자식 프로세스의 exit status를 return 한다. pid 프로세스가 exit 함수를 부른 것이 아니라 커널이 강제 종료시킨거라면 -1을 return 해야한다. 이미 종료한 자식에 대해서 부모가 wait을 하는 것은 지극히 정상적인 일이며, 이때 커널은 부모가 자식의 exit status를 여전히 가져올 수 있도록 해주거나 자식이 이미 종료했음을 알 수 있도록 해주어야 한다.

wait 함수는 다음의 경우에 즉시 -1을 return 하며 실패해야한다 :

pid 프로세스가 부모 프로세스의 직계 자식이 아닐 때. 부모 프로세스가 성공적인 fork 함수 호출을 통해서 자식 프로세스의 pid를 받은 경우에만 pid 프로세스가 호출 프로세스의 직계 자식이 된다. 자식은 물려받지 않는 다는 것을 주의 : A가 B를 낳고 B가 C를 낳는다면, A는 C를 wait할 수 없으며, B가 죽었다고 해도 wait할 수 없다. A가 C에 대해 wait을 호출한다면 해당 호출은 실패가 뜬다. 이와 유사하게, 부모가 먼저 exit을 해서 부모를 잃어버린 프로세스는 새로운 부모에게 할당되지 않는다.

wait을 호출하는 프로세스가 이미 이전에 pid 에 대해서 wait을 호출한 경우. (중복 호출하는 경우) 즉, 주어진 자식 프로세스에 대해서는 최대 1번까지만 wait할 수 (기다릴 수) 있다.

(같은 부모가 같은 자식에 대해서 동시에 여러번 기다릴 수 없으며, child 프로세스가 종료된 후에는 부모가 기다리지 않고 exit status만 가져오기 때문에 기다리는 것은 오로지 한번만 가능하다.)

process_wait()

Waits for thread TID to die and returns its exit status. If it was terminated by the kernel (i.e. killed due to an exception), returns -1. If TID is invalid or if it was not a child of the calling process, or if process_wait() has already been successfully called for the given TID, returns -1 immediately, without waiting.

입력된 입력된 tid가 유효하지 않거나 직계 자식이 아닌 경우,

create

bool create(const char *file, unsigned initial_size)

=> filesys_create()을 호출
=> inode를 생성하며, disk에 해당 내용을 쓴다.

⭐️ File System in PintOS ⭐️

filesystem

struct disk *filesys_disk;
  
/* Initializes the file system module.
 * If FORMAT is true, reformats the file system. */
void filesys_init(bool format) {
	filesys_disk = disk_get (0, 1);
	if (filesys_disk == NULL)
	PANIC ("hd0:1 (hdb) not present, file system initialization failed");
	  
	inode_init ();
#ifdef EFILESYS
	fat_init ();
	if (format)
		do_format ();
	fat_open ();
#else
	/* Original FS */
	free_map_init ();
	if (format)
		do_format ();
	free_map_open ();
#endif
}

bool filesys_create(const char *name, off_t initial_size) {
	disk_sector_t inode_sector = 0;
	struct dir *dir = dir_open_root ();
	bool success = (dir != NULL
					&& free_map_allocate (1, &inode_sector)
					&& inode_create (inode_sector, initial_size)
					&& dir_add (dir, name, inode_sector));
	if (!success && inode_sector != 0)
		free_map_release (inode_sector, 1);
	dir_close (dir);
	  
	return success;
}

file

/* An open file. */
struct file {
	struct inode *inode; /* File's inode. */
	off_t pos; /* Current position. */
	bool deny_write; /* Has file_deny_write() been called? */
};

inode

파일의 메타데이터를 저장하는 자료구조 (data structure for storing metadata about a file)

/* In-memory inode. */
struct inode {
	struct list_elem elem;   /* Element in inode list. */
	disk_sector_t sector;    /* Sector number of disk location. */
	int open_cnt;            /* Number of openers. */
	bool removed;            /* True if deleted, false otherwise. */
	int deny_write_cnt;      /* 0: writes ok, >0: deny writes. */
	struct inode_disk data;  /* Inode content. */
};

/* On-disk inode.
 * Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk {
	disk_sector_t start;     /* First data sector. */ 
	off_t length;            /* File size in bytes. */
	unsigned magic;          /* Magic number. */
	uint32_t unused[125];    /* Not used. */
};

/* Index of a disk sector within a disk.
 * Good enough for disks up to 2 TB. */
typedef uint32_t disk_sector_t;

/* List of open inodes, so that opening a single inode twice
 * returns the same `struct inode'. */
static struct list open_inodes;

chohk10

이전 포스트

[PintOS] Project 1 : Thread

다음 포스트

[PintOS] Project 2 : User Programs

PintOS

[PintOS] Project 2 : User Programs

Introduction

배경

다루게될 소스 파일들

File System 사용하기

사용자 프로그램이 어떻게 동작하는지

가상 메모리 레이아웃

일반적인 메모리 레이아웃

사용자 메모리 공간 접근

Overview of Project 2

Functions!

기타 함수

⭐️ Function Flow ⭐️

1. Argument Passing

x86-64 Calling Convention

Argument Passing for PintOS

⭐️ Argument Passing 구현 ⭐️

Address of arguments in stack

Alignment and padding in stack

Registers

Callee-saved Registers

2. User Memory Access

3. System Calls

System Call Details

System call to implement

4. Process Termination Message

5. Deny Write on Executables

⭐️ Syscall 구현 ⭐️

syscall handler

exit

fork

exec

wait

create

⭐️ File System in PintOS ⭐️

filesystem

file

inode

[PintOS] Project 1 : Thread

[PintOS] Project 3 : Virtual Memory - Memory Management

0개의 댓글