[PintOS] Project2-1 Passing the arguments and creating a thread

목표

PinOS에서 인자를 전달하고 쓰레드를 생성하는 매커니즘을 구현해야한다. 현재 핀토스는 명령줄을 토큰화하는 매커니즘이 존재하지 않아 명령줄 전체를 전달한다.

---

명령어 "echo x y z"를 실행

• 현재 PintOS
  • 쓰레드의 이름이 "echo x y z"이다.
  • 파일이름이 "echo x y z"이름을 가진 프로그램을 찾는다.
  • 명령줄 "echo", "x", "y", "z" 인수를 전달하지 못한다.
• 수정한 PintOS
  • 쓰레드 이름이 "ehco"이다.
  • 파일이름이 "echo"이름을 가진 프로그램을 찾는다.
  • 유저스택에 인주들을 푸시한다.
• 스레드 이름과, file_name을 식별하고 인수들을 user stack에 push한다.

---

수정해아할 함수

• pintos-kaist/userprog/process.*

유저프로그램 실행 순서

process_create_initd

• process_create_initd함수는 전체 명령줄을 받는다.
• 파일 이름의 문자열을 파싱한 다음
• 첫번째 토큰(파일이름: argv[0])을 thread_create에서 실행할 새 프로세스의 이름으로 전달한다.

---

process_exec

• file_name을 파싱한다.
• 개별인수들을 토큰화한다.
• 새로 생성된 프로세스의 사용자 스택에 파라미터로 전달한다.
• PintOS에선 process_exec함수내의 load() 함수에서 해당 기능들을 구현한다.
• 문자를 파싱하려면 string 라이브러리에서 제공하는 strtok_r을 사용한다.

---

유저모드와 커널모드간의 컨텍스트 스위칭

유저 쓰레드에서 커널 쓰레드로 전환 되거나 커널 쓰레드에서 유저 쓰레드로 전환되는것은 흐름(context)를 전환(context switching)하는 것이다. 컨텍스트 스위칭(context switching)이 일어나려면 이전 상태를 저장해 놓아야한다.

• 프로세스간 컨텍스트 스위칭은 이전상태를 PCB에 저장한다.
• 쓰레드간 컨텍스트 스위칭은 이전 상태를 TCB에 저장한다.
• 흐름(context) 중간 인터럽트로인해 발생하는 컨텍스트 스위칭은 인터럽트 프레임(interrupt frame)에 저장된다.

유저/커널 모드간 인터럽트를 발생시켜 컨텍스트 스위칭

---

struct intr_frame

• 범용 레지스터
• 12바이트의 어떤 공간
• 5개의 레지스터 필드로 구성되어있다

인터럼트 프레임의 데이터 구조는 운영체제와 CPU에의해 정의된다.

인터럽트 프레임은 커널 스택에 상주하며 사용자 프로세스 레지스터에 저장된다.

커널이 사용자 레지스터를 저장하는데 사용한 데이터 구조가 인터럽트 프레임이다

인터럽트 명령어를 실행하면 사용자 모드에서 커널 모드로 전환되고 커널 공간에 있는 인터럽트 프레임으로 레지스터의 상태들을 push한다

struct intr_frame {
	/* 	intr-stubs.S의 intr_entry에 의해 푸시됨.
		이는 인터럽트된 작업의 저장된 레지스터입니다. */
	
	/* 	grp_registers 필드에는 유저 공간에서 사용하던 
		일반 목적 레지스터들이 저장됩니다. 
		이 레지스터들은 인터럽트 발생 시 CPU에 의해 
		자동으로 저장되지 않기 때문에, 
		소프트웨어적으로 저장해두는 것입니다. */
	struct gp_registers R;
	uint16_t es;	// 유저 공간의 데이터 세그먼트 레지스터 값을 저장합니다.
	uint16_t __pad1;
	uint32_t __pad2;
	uint16_t ds;	// 유저 공간의 데이터 세그먼트 레지스터 값을 저장합니다.
	uint16_t __pad3;
	uint32_t __pad4;
	
	/* 	발생한 인터럽트의 종류를 식별하기 위해 사용됩니다.
		예를 들어, 페이지 폴트, 시스템 호출 등의 
		인터럽트 종류가 있습니다. */
	uint64_t vec_no; /* 인터럽트 벡터 번호. */

	/* 	때때로 CPU에 의해 푸시되며,
	    그렇지 않으면 일관성을 위해 intrNN_stub에 의해 0으로 푸시됩니다.
	    CPU는 이를 `eip' 바로 아래에 놓지만, 우리는 이것을 여기로 이동시킵니다. */	
	/* 	특정 인터럽트(예: 페이지 폴트)와 
		관련된 오류 코드를 저장합니다. 
		이 코드도 유저 공간의 정보를 
		포함하고 있을 수 있습니다. */
        
	uint64_t error_code;
    
/* 	CPU에 의해 푸시됨.
	이는 인터럽트된 작업의 저장된 레지스터입니다. */	

/* 여기 5개의 값들은 User Space에서 호출한 인터럽트
	명령어 내부에서 이 5개의 레지스터를 Push하고
	이 것들을 제외한 나머지 값들은 
	interrupt handler내부에서 값을 Push해줌 */
	uintptr_t rip; 	//유저 공간에서 인터럽트가 발생한 명령어의 주소를 저장합니다. 이는 유저 프로그램이 실행 중이던 위치를 나타냅니다.
	uint16_t cs;	//코드 세그먼트 레지스터. 유저 공간에서의 세그먼트 값을 나타냅니다.
	uint16_t __pad5;//정렬을 위한 패딩값
	uint32_t __pad6;//정렬을 위한 패딩값
	uint64_t eflags;//플래그 레지스터. 인터럽트 발생 시점의 CPU 플래그 상태를 나타냅니다.
	uintptr_t rsp;	//스택 포인터. 유저 공간에서의 스택 위치를 나타냅니다.
	uint16_t ss;	//스택 세그먼트 레지스터. 유저 공간에서의 스택 세그먼트를 나타냅니다.
	uint16_t __pad7;//정렬을 위한 패딩값
	uint32_t __pad8;//정렬을 위한 패딩값
} __attribute__((packed));

---

int N

인터럽트 핸들러나 시스템 콜 같은 커널 함수를 실행할 때 OS는 현재 실행중인 프로세스와 레지스터를 인터럽트 프레임에 저장한다.

인터럽트 프레임은 커널스택에 저장된다.

rsp를 사용자 스택에서 커널 스택 상단으로 전환하고 커널 스택에 있는 레지스터를 전달한다.

• 우리는 PintOS 커널을 수정해 유저프로그램이 실행될 수 있게하는거지 유저 프로그램을 만들고 있는게 아니다.
• 유저 프로그램에서 int를 발생하는거다. 이 점을 유의해라!

1. int 명령어는 유저 스택에서 커널 스택으로 전환함
2. int 명령어를 실행하게되면 rsp는 커널 스택 상단을 가리키게됨
3. 인터럽트 명령어 내부에서 다섯개의 레지스터를 커널스택에 푸시한다.
4. 인터럽트 인스트럭션이 씉나면 인터럽트 핸들러를 실행한다.
5. 인터럽트 핸들러 내부에서 OS에 의해 정의되는 16바이트?의 레지스터와 범용 레지스터 값을 커널 스택에 푸시한다.

---

iret

커널 모드에서 유저모드로 전환하려면 iret명령어를 호출해 커널모드를 탈출하고 인터럽트 프레임을 이용해 이전 상태를 복원한다.

• moveq에서는 rsp 포인터가 인터럽트 프레임의 현재 스택 상단을 가리키도록 설정한다.
• iret을 호출해 cpu는 다섯개의 레지스터를 가져와 user모드에 복원한다.

void do_iret (struct intr_frame *tf) {
	__asm __volatile(
			"movq %0, %%rsp\n"
			"movq 0(%%rsp),%%r15\n"
			"movq 8(%%rsp),%%r14\n"
			"movq 16(%%rsp),%%r13\n"
			"movq 24(%%rsp),%%r12\n"
			"movq 32(%%rsp),%%r11\n"
			"movq 40(%%rsp),%%r10\n"
			"movq 48(%%rsp),%%r9\n"
			"movq 56(%%rsp),%%r8\n"
			"movq 64(%%rsp),%%rsi\n"
			"movq 72(%%rsp),%%rdi\n"
			"movq 80(%%rsp),%%rbp\n"
			"movq 88(%%rsp),%%rdx\n"
			"movq 96(%%rsp),%%rcx\n"
			"movq 104(%%rsp),%%rbx\n"
			"movq 112(%%rsp),%%rax\n"
			"addq $120,%%rsp\n"
			"movw 8(%%rsp),%%ds\n"
			"movw (%%rsp),%%es\n"
			"addq $32, %%rsp\n"
			"iretq"
			: : "g" ((uint64_t) tf) : "memory");
}

---

process_exec

인터럽트 프레임을 할당한다.

프로그램을 로드하고 인터럽트 프레임과 인터럽트프레임을 이용해 유저스택에 초기화한다.

• 인터럽트 프레임을 커널 스택에 푸시한다
• 인자들을 유저 스택에 설정한다.

하지만 우리는 위 과정을 load함수에서 구현한다.

 

int process_exec (void *f_name) {
	char *file_name = f_name;
	bool success;

	/* We cannot use the intr_frame in the thread structure.
	 * This is because when current thread rescheduled,
	 * it stores the execution information to the member. */
	struct intr_frame _if;
	_if.ds = _if.es = _if.ss = SEL_UDSEG;
	_if.cs = SEL_UCSEG;
	_if.eflags = FLAG_IF | FLAG_MBS;

	/* We first kill the current context */
	process_cleanup ();

	/* 바이너리 파일을 로드 
	 * 사용자 스택을 초기화 */
	success = load (file_name, &_if);

	/* 로드에 실패하면 종료 */
	palloc_free_page (file_name);
	if (!success)
		return -1;

	/* Start switched process. */
	/* 전환된 프로세스를 시작합니다. */
	/* 유저 프로그램으로 전환함 */
	do_iret (&_if);
    
	NOT_REACHED ();
}

---

load

• load함수에 실행할 커맨드라인인 file_name을 전달한다
• load는 인수를 파싱하고 실행할 파일을 메모리에 로드한다
• load는 인터럽트 프레임을 이용해 유저스택에 푸시한다

1. 파일을 메모리에 로드하고 사용자 스택을 초기화한다
2. 유저모드 프로그램을 실행할 때 일련의 인수들을 유저 스택에 푸시해야한다(누락된 부분)

static bool load (const char *file_name, struct intr_frame *if_) {
	struct thread *t = thread_current ();
	struct ELF ehdr;
	struct file *file = NULL;
	off_t file_ofs;
	bool success = false;
	int i;

	/* Allocate and activate page directory. */
	/* 페이지 디렉토리를 할당하고 활성화합니다. */
	t->pml4 = pml4_create ();
	if (t->pml4 == NULL)
		goto done;
	process_activate (thread_current ());

	/* Open executable file. */
	/* 실행 파일을 엽니다. */
	file = filesys_open (file_name);
    
	...

	/* Read and verify executable header. */
	/* 실행 파일 헤더를 메모리로 읽고 검증합니다. */
	if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
			|| memcmp (ehdr.e_ident, "\177ELF\2\1\1", 7)
			|| ehdr.e_type != 2
			|| ehdr.e_machine != 0x3E // amd64
			|| ehdr.e_version != 1
			|| ehdr.e_phentsize != sizeof (struct Phdr)
			|| ehdr.e_phnum > 1024) {
		printf ("load: %s: error loading executable\n", file_name);
		goto done;
	}

	/* Read program headers. */
	/* 프로그램 헤더를 읽습니다. 
	 * ELF 헤더에는 이 파일이 어떻게 구성되어있는지에 대한 정보가 들어있음
	 */
	file_ofs = ehdr.e_phoff;
    
	...

	/* Set up stack. */
	/* 사용자 스택을 초기화 */
	if (!setup_stack (if_))
		goto done;

	/* Start address. */
	/* 시작 주소 */
	if_->rip = ehdr.e_entry;

	/* TODO: Your code goes here.
	 * TODO: Implement argument passing (see project2/argument_passing.html). */
	 /* TODO: 여기에 코드를 작성하세요. 
	  * TODO: 인자 전달을 구현합니다 (project2/argument_passing.html 참조). */
	success = true;

done:
	/* 로드가 성공했든 실패했든 여기에 도착합니다. */
	file_close (file);
	return success;
}

---

setup_stack

처음 프로세스를 실행 시키면 인터럽트 프레임은 비어있다 프로세스가 커널에 진입할 때 인터럽트 프레임에 값을 채워야한다.

/* USER_STACK에 0으로 채워진 페이지를 매핑하여 최소한의 스택을 생성합니다. */
static bool
setup_stack (struct intr_frame *if_) {
	uint8_t *kpage;
	bool success = false;

	kpage = palloc_get_page (PAL_USER | PAL_ZERO);
	if (kpage != NULL) {
		success = install_page (((uint8_t *) USER_STACK) - PGSIZE, kpage, true);
		if (success)
			if_->rsp = USER_STACK;
		else
			palloc_free_page (kpage);
	}
	return success;
}

• 현재 스택의 top: &if_.rsp
• Start_from &if_.rsq - 8

---

Passing the argument into user stack

커널에들어가면 인터럽트를 사용해 레지스터 값을 전달한다.

커널에서 빠져 나올때는 iret을 사용해 탈출한다.

프로세스가 생성되고 인수들이 커널에서 유저공간으로 전달되기 위해선 유저스택에 올바른 값으로 push해야한다.

인터럽트 프레임에는 유저스택 상단을 가리키는 rsp필드가 저장되어있다.

파라미터를 스택 탑에서 하나씩 푸시해야한다. 이때 사용되는 규칙이 x86-64 Calling Convention이다.

---

x86-64 Calling Convention

 

예시

1. Push arguments
   1. 인수들을 오른쪽에서 왼쪽순서로 유저  스택에 push한다.
   2. 64비트 환경에선 8byte정렬을 통해 패딩을 채워야한다.
   3. 문자열을 모두 전달한 다음, 첫번째 인수 시작주소를 유저스택에 push한다.
2. argc and argv
   1. argv의 주소를 rsi에 저장한다.
   2. argc의 주소를 rdi에 저장한다.
3. Push the address of the next instruction (return address)

Address	Name	Data	Type
0x4747fffc	argv[3][...]	'bar\0'	char[4]
0x4747fff8	argv[2][...]	'foo\0'	char[4]
0x4747fff5	argv[1][...]	'-l\0'	char[3]
0x4747ffed	argv[0][...]	'/bin/ls\0'	char[8]
0x4747ffe8	word-align	0	uint8_t[]
0x4747ffe0	argv[4]	0	char *
0x4747ffd8	argv[3]	0x4747fffc	char *
0x4747ffd0	argv[2]	0x4747fff8	char *
0x4747ffc8	argv[1]	0x4747fff5	char *
0x4747ffc0	argv[0]	0x4747ffed	char *
0x4747ffb8	return address	0	void (*) ()

 

---

구현

process_create_initd

tid_t process_create_initd (const char *file_name) { // process_execute()
	char *fn_copy;
	tid_t tid;

	/* Make a copy of FILE_NAME.
	 * Otherwise there's a race between the caller and load(). */
	fn_copy = palloc_get_page (0);
	if (fn_copy == NULL)
		return TID_ERROR;
	strlcpy (fn_copy, file_name, PGSIZE);

	char *save_ptr; // strtok_r 함수 실행을 위한 잠깐의 임시 포인터 변수
	strtok_r(file_name, " ", &save_ptr); // file_name을 공백문자마다" "을 "\0" 삽입

	/* Create a new thread to execute FILE_NAME. */
    /* 널 종단자가 공백마다 삽입됐으니까 file_name으로 접근하면 첫번째 단어만 입력됨 */
	tid = thread_create (file_name, PRI_DEFAULT, initd, fn_copy);
	if (tid == TID_ERROR)
		palloc_free_page (fn_copy);
	return tid;
}

load

static bool load (const char *file_name, struct intr_frame *if_) {
	struct thread *t = thread_current ();
	struct ELF ehdr;
	struct file *file = NULL;
	off_t file_ofs;
	bool success = false;
	int i;

	/* Allocate and activate page directory. */
	/* 페이지 디렉토리를 할당하고 활성화합니다. */
	t->pml4 = pml4_create ();
	if (t->pml4 == NULL)
		goto done;
	process_activate (thread_current ());

	char *argv[128]; // 한페이지가 4KB 대충 이정도까지는 들어갈수 있는정도? 
	int argc = 0; // 인자의 갯수

	// file_name에서 인자들을 parsing
	parsing_file_name(file_name, &argc, argv);

	...

	/* Set up stack. */
	/* 사용자 스택 초기화 */
	if (!setup_stack (if_))
		goto done;

	/* Start address. */
	/* 시작 주소 */
	if_->rip = ehdr.e_entry;

	/* TODO: Your code goes here.
	 * TODO: Implement argument passing (see project2/argument_passing.html). */
	 /* TODO: 여기에 코드를 작성하세요. 
	  * TODO: 인자 전달을 구현합니다 (project2/argument_passing.html 참조). */
      
	argument_passing_user_stack(argc, argv, if_);

	success = true;

done:
	/* We arrive here whether the load is successful or not. */
	/* 로드가 성공했든 실패했든 여기에 도착합니다. */
	file_close (file);
	return success;
}

parsing_file_name

void parsing_file_name(char *file_name, int *argc,char *argv[]) {
	char *token, *save_ptr;

	for(token = strtok_r (file_name, " ", &save_ptr); token != NULL; token = strtok_r(NULL, " ", &save_ptr)){
		argv[(*argc)++] = token;
	}
}

argument_passing_user_stack

/* 정렬요건을 8로 설정 */
#define ALIGNMENT 8

/* 가장 가까운 정렬요건으로 올림한다 */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

void argument_passing_user_stack(int argc,char *argv[],struct intr_frame *if_){
	uintptr_t push_rsp = 0; //유저스택에 push할때 사용하는 변수 rsp - push_rsp
	size_t args_size = 0; // 인수들을 push하고 8바이트 정렬을할때 사용할 변수

	/* argv[i][...] 
	 * 인수들 자체(string)를 스택에 push */
	for(int i = argc-1; i >= 0; i--){
		size_t size = strlen(argv[i])+1; // 널종단자 "\0"를 포함한 인수의 사이즈 +1
		push_rsp += size; // size 만큼 유저 스택에 push
		args_size += size; // 정렬할 떄 사용할 args_size
		/* argv[i]가 가리키는 주소에서 size만큼 유저스택 rsp - push_rsp위치에 push */
		memcpy(if_->rsp - push_rsp, argv[i], size);
		/* argv[i]의 포인터 값에 방금 유저 스택에 push한 값 시작주소로 초기화 */
		argv[i] = (char *)(if_->rsp - push_rsp);
	}

	/* word-align 
	 * arg_size를 8바이트 정렬을 해야함*/
	push_rsp = ALIGN(args_size);
	memset(if_->rsp - push_rsp, 0, (push_rsp - args_size)); // 8바이트 정렬을 위해 패딩(0)값을 넣음

	/* argv[argc] 
	 * argv[argc] 인수의 끝배열 주소에 0을 집어넣어서 배열을 끊음*/
	push_rsp += 8; //포인터주소니까 8만큼 rsp를 땡김
	memset(if_->rsp - push_rsp, 0, 8); // 주소값을 0으로 세팅

	/* argv[i] 
	 * argv[i]의 주소를 유저스택에 push*/
	for(int i = 0 ;i < argc; i++){
		push_rsp += 8; // 주소니까 8바이트
		memcpy(if_->rsp - push_rsp, &argv[i], 8); //유저스택에 argv[i]의 각 인수들의 시작 주소값을 넣음
	}
	/* return 주소를 집어넣음 */
	push_rsp += 8; // 주소니까 8바이트
	memset(if_->rsp - push_rsp, 0, 8); //처믐 실행시키는 거니까 일단 fake주소 0

	if_->rsp -= push_rsp; // 유저모드로 전환될떄 레지스터값을 복원할때 사용할 인터럽트프레임의 rsp의 값을 업데이트
	if_->R.rdi = argc; // 첫번째 인자 레지스터 rdi에 argc값 저장
	if_->R.rsi = &argv; // 두번째 인자 레지스터 rsi에 argv값 저장
	return;
}

---

hex_dump 실행결과

---

참고

https://www.youtube.com/watch?v=RbsE0EQ9_dY
https://casys-kaist.github.io/pintos-kaist/project2/argument_passing.html

---

GitHub - hyunS00/pintos-kaist: 크래프톤 정글 5기 Pint OS