[WEEK 09] PintOS - Project 2: User Programs (Argument Passing)

신호정 벨로그·2021년 10월 5일
pintos
0

Today I Learned

목록 보기
47/89

PintOS - Project 2: User Programs (Argument Passing)

Goal

Setup the argument for user program in process_exec()

Argument Passing 과제의 목표는 process_exec() 함수의 유저 프로그램 인자를 설정하는 것이다.

Instructions

x86-64 Calling Convention

This section summarizes important points of the convention used for normal function calls on 64-bit x86-64 implementations of Unix. Some details are omitted for brevity. For more detail, you can refer System V AMD64 ABI.

호출 규칙 일반 함수

The calling convention works like this:

  1. User-level applications use as integer registers for passing the sequence %rdi, %rsi, %rdx, %rcx, %r8 and %r9.
  2. The caller pushes the address of its next instruction (the return address) on the stack and jumps to the first instruction of the callee. A single x86-64 instruction, CALL, does both.
  3. The callee executes.
  4. If the callee has a return value, it stores it into register RAX.
  5. The callee returns by popping the return address from the stack and jumping to the location it specifies, using the x86-64 RET instruction.

일반적인 x86-64 호출 규칙은 다음과 같다.

  1. 유저 수준 응용 프로그램은 정수형 레지스터를 사용한다.
  2. 호출자는 다음 인스트럭션의 주소값을 스택에 삽입하고 피호출자의 첫 번째 인스트럭션으로 이동한다.
  3. 피호출자는 실행한다.
  4. 피호출자가 리턴 밸류를 가지면 그 값은 레지스터 RAX에 저장된다.
  5. 피호출자는 스택에서 주소값을 꺼내어 리턴하고 주소값이 가리키는 위치로 이동하여 x86-64 RET 인스트럭션을 사용한다.

Consider a function f() that takes three int arguments. This diagram shows a sample stack frame and register state as seen by the callee at the beginning of step 3 above, supposing that f() is invoked as f(1, 2, 3). The initial stack address is arbitrary:

f() 함수는 세 개의 정수형 인자로 입력한다. 아래의 그림은 함수 f()가 f(1, 2, 3)이라는 입력을 호출한 경우 위의 3단계에서 피호출자에게 보여지는 스택 프레임과 레지스터 상태를 나타낸다. 초기 스택 주소값은 임의의 값이다.

                             +----------------+
stack pointer --> 0x4747fe70 | return address |
                             +----------------+
RDI: 0x0000000000000001 | RSI: 0x0000000000000002 | RDX: 0x0000000000000003

Program Startup Details

The Pintos C library for user programs designates _start(), in lib/user/entry.c, as the entry point for user programs. This function is a wrapper around main() that calls exit() if main() returns:

유저 프로그램에서 사용되는 핀토스 C 라이브러리는 _start()를 유저 프로그램의 entry point로 지정한다. 이 함수는 main() 함수가 리턴하면 exit()를 호출하는 래퍼 함수이다.

void _start (int argc, char *argv[]) {
    exit (main (argc, argv));
}

The kernel must put the arguments for the initial function on the register before it allows the user program to begin executing. The arguments are passed in the same way as the normal calling convention.

커널은 레지스터에 위치한 초기 함수가 유저 프로그램의 실행을 허락하기 전에 함수에 인자를 입력해야 한다. 인자들은 일반적인 호출 규칙에 따라 전달되어야 한다.

Consider how to handle arguments for the following example command: /bin/ls -l foo bar.

인자들을 다루는 방법은 다음과 같다.

Break the command into words: /bin/ls, -l, foo, bar.

Place the words at the top of the stack. Order doesn't matter, because they will be referenced through pointers.

단어들을 스택의 상단에 위치한다. 단어들은 포인터를 통해 참조될 것이기 때문에 단어들의 순서는 상관 없다.

Push the address of each string plus a null pointer sentinel, on the stack, in right-to-left order. These are the elements of argv. The null pointer sentinel ensures that argv[argc] is a null pointer, as required by the C standard. The order ensures that argv[0] is at the lowest virtual address. Word-aligned accesses are faster than unaligned accesses, so for best performance round the stack pointer down to a multiple of 8 before the first push.

각 문자열의 주소값에 null pointer sentinel을 더하여 스택에 오른쪽에서 왼쪽 순서로 삽입한다. argv 인자의 구성 요소들이다. null pointer sentinel은 C 표준 규칙에 따라 argv[argv] 인자가 null pointer임을 확인한다. argv[0] 인자가 가장 낮은 가상 주소임을 확인한다. 단어순으로 정렬된 접근은 정렬되지 않은 접근보다 빠르기 때문에 이상적인 성능을 발휘하기 위해 추가하기 이전에 스택 포인터 8의 배수로 올림한다.

Point %rsi to argv (the address of argv[0]) and set %rdi to argc.

%rsi가 argv(argv[0]의 주소값) 가리리고 %rdi를 argc로 설정한다.

Finally, push a fake "return address": although the entry function will never return, its stack frame must have the same structure as any other.

마지막으로 가짜 "return address"를 추가한다: 입력 함수가 리턴하지 않을 것이지만 스택 프레임은 같은 구조를 가져야만 한다.

The table below shows the state of the stack and the relevant registers right before the beginning of the user program. Note that the stack grows down.

주어진 표는 스택과 관련된 레지스터가 유저 프로그램을 실행하기 직전의 상태를 나타낸다. 스택이 아래 방향으로 증가하는 것을 유의한다.

In this example, the stack pointer would be initialized to 0x4747ffb8. As shown above, your code should start the stack at the USER_STACK, which is defined in include/threads/vaddr.h.

해당 예시에서 스택 포인터는 0x4747ffb8로 초기화된다. 코드는 include/threads/vaddr.h 파일에서 정의된 USER_STACK에서 스택이 시작되어야 한다.

You may find the non-standard hex_dump() function, declared in <stdio.h>, useful for debugging your argument passing code.

<stdio.h>에서 선언되 hex_dump() 함수는 인자를 전달하는 디버깅 과정에서 유용하다.

Implement the argument passing.

Currently, process_exec() does not support passing arguments to new processes. Implement this functionality, by extending process_exec() so that instead of simply taking a program file name as its argument, it divides it into words at spaces. The first word is the program name, the second word is the first argument, and so on. That is, process_exec("grep foo bar") should run grep passing two arguments foo and bar.

process_exec() 함수는 인자를 새로운 프로세스로 전달하는 것을 제공하지 않는다. 프로그램 파일명을 인자명으로 변경하는 것이 아니라 기존의 process_exec() 함수를 추가하여 인자를 전달하는 기능을 구현해야 한다. 프로그램 이름의 첫 번째 단어는 프로그램의 이름, 두 번째 단어는 첫 번째 인자이어야 한다. 예를 들면 process_exec("grep foo bar")을 입력하면 grep 프로그램을 실행하고 두 개의 인자 foo와 bar을 전달해야 한다.

Within a command line, multiple spaces are equivalent to a single space, so that process_exec("grep foo bar") is equivalent to our original example. You can impose a reasonable limit on the length of the command line arguments. For example, you could limit the arguments to those that will fit in a single page (4 kB). (There is an unrelated limit of 128 bytes on command-line arguments that the pintos utility can pass to the kernel.)

커맨드 라인에서 여러 스페이스는 한 번의 스페이스와 같다. process_exec("grep foo bar")은 주어진 예시와 결과가 같다. 사용자는 커맨드 라인의 길이에 합리적인 제한을 두어야 한다. 예를 들면, 사용자는 싱글 페이지(4kb)에 알맞게 하기 위해 인자들에 제한을 둔다. (이것과 별개로 커맨드 라인 인자에는 핀토스 유틸리티가 커널에 전달하게 하기 위한 128 바이트 크기의 제한이 존재한다.)

You can parse argument strings any way you like. If you're lost, look at strtok_r(), prototyped in include/lib/string.h and implemented with thorough comments in lib/string.c. You can find more about it by looking at the man page (run man strtok_r at the prompt).

Implementations

process_exec()

유저 프로그램이 실행하기 전에 커널은 레지스터에 첫 함수의 인자를 저장해야 한다.

process_exec() 함수는 유저가 입력한 명령어를 수행할 수 있도록 프로그램을 메모리에 적재하고 실행하는 함수이다.

해당 프로그램은 f_name에 문자열로 이름이 저장되어 있으나 파일 이름 뿐만 아니라 (rm -rf의 -rf와 같은) 옵션도 포함되어 있기 때문에 이를 분리해야 한다.

/* Switch the current execution context to the f_name.
 * Returns -1 on fail. */
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();

	/* And then load the binary */
	success = load(file_name, &_if);

	/* If load failed, quit. */
	palloc_free_page(file_name);
	
	if (!success)
		return -1;

	/* Start switched process. */
	do_iret(&_if);
	NOT_REACHED();

process_exec() 함수는 문자열을 f_name이라는 인자로 입력 받는다.

char filename = f_name; f_name은 문자열이지만 void 로 넘겨 받았다. 이를 문자열로 인식하기 위해 자료형을 char *로 변환해야 한다.

struct intr_frame: intr_frame 구조체는 유저 프로그램을 실행할 때 필요한 정보를 포함한다.

process_cleanup(); process_cleanup() 함수는 새로운 실행 파일을 현재 쓰레드에 담기 전에 현재 프로세스에 담긴 컨텍스트를 지운다. 즉 현재 프로세스에 할당된 page directory를 지운다.

success = load(file_name, &_if); _if와 file_name을 현재 프로세스에 로드한다. 로드가 성공하면 1을 반환하고 그렇지 않으면 0을 반환한다.

palloc_free_page(file_name); file_name은 프로그램 파일 이름을 입력하기 위해 생성한 임시 변수이기 때문에 load를 끝내면 해당 메모리를 반환해야 한다.

if (!success) return -1; load를 실패하면 -1을 반환한다.

do_iret(&_if); NOT_REACHED(); load가 실행되면 context switching을 실행한다.

Argument Parsing 기능

쓰레드의 이름을 실행 파일 명으로 저장할 것이고 f_name은 유저가 입력한 커맨드 라인이기 때문에 실행 파일 이름 뿐만 아니라 다른 인자들을 포함하게 된다. 따라서 커맨드 라인으로부터 실행 파일 이름명을 분리해야 한다.

f_name을 사용하는 경우를 고려하여 원본 파일명을 수정하는 대신 file_name_copy라는 이름의 사본을 생성하고 memcpy()를 이용하여 file_name의 메모리를 복사하여 이를 수정한다.

memcpy(a, b, size); b에서 size만큼을 읽어서 a에 복사한다.

strlen(file_name) + 1만큼의 크기를 사용하는 이유는 strlen() 함수는 '\n'이 나올 때까지 1바이트 씩 읽고 '\n'이 나오면 종료하기 때문이다.

'\n'도 포함될 수 있도록 파일 크기에 1을 더해준다. char *이기 때문에 8바이트를 늘려 한 글자를 더 읽을 수 있다.

파일명을 추출해야 하지만 다른 인자들 또한 프로세스를 실행하는 데에 필요하므로 user stack에 저장한다.

arg_list라는 리스트를 생성하여 각 인자의 char *를 저장한다. 프로그램 명은 arg_list[0]에 저장되며, arg_list[1]부터 다른 인자들이 저장된다.

char strtok(char str, char* delimiters); 첫 번째 매개변수 문자열을 두 번째 매개변수 구분자를 기준으로 문자열을 분할하여 각 문자열의 포인터를 반환한다.

token = strtok_r(NULL, " ", &last); 여백 ' '을 기준으로 문자열을 분할하여, 각 인자에 sentinel '\n'을 추가하여 저장한다.

예를 들어, cmd line이 rm -rf 인 경우 arg_list에는 [rm\0, -rf\0, \0]의 형태로 저장된다.

token_count에는 파일명을 제외한 인자의 갯수가 저장된다.

load를 마치면 argument_stack() 함수를 이용하여 user stack에 인자들을 저장한다.

/* Switch the current execution context to the f_name.
 * Returns -1 on fail. */
int process_exec(void *f_name) {
	char *file_name = f_name;
	char *file_name_copy[48];
	bool success;

	memcpy(file_name_copy, file_name, strlen(file_name) + 1);

	/* 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();

	int token_count = 0;
	char *token, *last;
	char *arg_list[64];
	char *tmp_save = token;

	token = strtok_r(file_name_copy, " ", &last);
	arg_list[token_count] = token;

	while (token != NULL) {
		token = strtok_r(NULL, " ", &last);
		token_count++;
		arg_list[token_count] = token;
	}

	/* And then load the binary */
	success = load(file_name, &_if);

	/* If load failed, quit. */
	palloc_free_page(file_name);
	
	if (!success)
		return -1;
	
	argument_stack(arg_list, token_count, &_if);
	
	/* Start switched process. */
	do_iret(&_if);
	NOT_REACHED();
}

argument_stack()

void argument_stack(int argc, char **argv, struct intr_frame *if_) {
	char *arg_address[128];

	/* Insert arguments' addresses */
	for (int i = argc - 1; i >= 0; i--) {
		int argv_len = strlen(argv[i]);
		if_ -> rsp = if_ -> rsp - (argv_len + 1);
		memcpy(if_ -> rsp, argv[i], argv_len + 1);
		arg_address[i] = if_ -> rsp;
	}

	/* Insert padding for word-align */
	while (if_ -> rsp % 8 != 0) {
		if_ -> rsp--;
		*(uint8_t *)(if_ -> rsp) = 0;
	}

	/* Insert addresses of strings including sentinel */
	for (int i = argc; i >= 0; i--) {
		if_ -> rsp = if_ -> rsp - 8;

		if (i == argv)
			memset(if_ -> rsp, 0, sizeof(char **));
		
		else
			memcpy(if_ -> rsp, &arg_address[i], sizeof(char **));
	}

	/* Fake return address */
	if_ -> rsp = if_ -> rsp - 8;
	memset(if_ -> rsp, 0, sizeof(void *));

	if_ -> R.rdi = argc;
	if_ -> R.rsi = if_ -> rsp + 8; 
}
/* Insert arguments' addresses */
for (int i = argc - 1; i >= 0; i--) {
	int argv_len = strlen(argv[i]);
	if_ -> rsp = if_ -> rsp - (argv_len + 1);
	memcpy(if_ -> rsp, argv[i], argv_len + 1);
	arg_address[i] = if_ -> rsp;
}

먼저 user stack의 최상단부터 각 배열의 문자열의 크기만큼 담는다.

if_ -> rsp는 user stack에서 현재 위치를 가리키는 stack pointer이다.

각 인자에서 인자의 크기를 읽고 (각 인자에는 sentinel이 포함되어 있기 때문에 strlen()에 1을 더한다.), 그 크기만큼 rsp를 내린다.

memcpy() 함수를 통해 현재 위치를 가리키는 스택 포인터 rsp에 인자를 복사한다.

/* Insert padding for word-align */
while (if_ -> rsp % 8 != 0) {
	if_ -> rsp--;
	*(uint8_t *)(if_ -> rsp) = 0;
}

word-align을 실행한다. 64비트 환경이기 때문에 8바이트 단위로 정렬한다 rsp를 8의 배수에 맞추기 위해 값을 내린다.

다시 읽고 이해하기

다시 읽고 이해하기

다시 읽고 이해하기

/* Insert addresses of strings including sentinel */
for (int i = argc; i >= 0; i--) {
	if_ -> rsp = if_ -> rsp - 8;

	if (i == argv)
		memset(if_ -> rsp, 0, sizeof(char **));

	else
		memcpy(if_ -> rsp, &arg_address[i], sizeof(char **));
}

if 조건문에서 memset()을 사용하면 3개의 인자를 입력 받았을 때, 밑에서부터 3개의 주소를 새기고 마지막에 0을 추가한다.

if (i == argv) 조건을 만족하지 않는 경우 arg_address에 저장한 주소를 입력한다. memcpy()의 인자로 포인터를 입력하기 때문에 arg_address[i]를 입력한다.

다시 읽고 이해하기

다시 읽고 이해하기

다시 읽고 이해하기

/* Fake return address */
if_ -> rsp = if_ -> rsp - 8;
memset(if_ -> rsp, 0, sizeof(void *));

인자의 주소값을 입력하고 그 밑에는 거짓 return address(함수를 호출하는 부분의 다음 수행 명령어 주소)를 입력한다. return address는 프로세스가 함수를 호출하면 해당 함수는 독자적인 stack을 가지고 함수가 종료되면 다시 프로세스로 돌아가기 위한 코드 영역 주소를 입력하지만, 유저 프로그램을 실행하기 위한 준비 단계이므로 돌아올 표기를 할 필요가 없다. 그렇기 때문에 0으로만 구성된 거짓 return address를 입력한다.

profile
신호정 벨로그
hello world
이전 포스트

[WEEK 09] PintOS - Project 2: User Programs (Introduction)

0개의 댓글