Pintos project-2-userprog-argument passing

#TODO

가장 먼저, Arguments passing을 구현해야 한다. 그 전에, 다음 문서를 읽어 보도록 하자.

Arguments passing

Argument Passing Setup the argument for user program in process_exec()

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:

User-level applications use as integer registers for passing the sequence %rdi, %rsi, %rdx, %rcx, %r8 and %r9. 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. The callee executes. If the callee has a return value, it stores it into register RAX. The callee returns by popping the return address from the stack and jumping to the location it specifies, using the x86-64 RET instruction. 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:

                             +----------------+
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:

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.

Point %rsi to argv (the address of argv[0]) and set %rdi to 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.

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.

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 (*) ()
RDI: 4	RSI: 0x4747ffc0

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.

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

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.

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.)

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).

번역

이 섹션은 x86-64 아키텍처에서 사용되는 일반적인 함수 호출에 관련한 중요한 규약 (convetion)에 대해 설명하고 있다. 몇몇 자세한 사항은 간단함을 위해 생략되었다. 더욱더 자세한 사항은 System V AMD64 ABI 문서를 참고하면 된다.

Calling Convention (함수 호출 규약)은 다음과 같이 동작한다. : 유저-레벨 프로그램이 정수 배열을 전달하기 위해 %rdi, %rsi, %rdx, %rcx, %r8 and %r9 레지스터를 사용한다.

1. 호출자 (Caller)는 다음 실행할 명령어의 주소를 (return address) 스택에 push한 뒤, 피호출자 (callee)의 첫번째 명령어의 위치로 jump 한다. 이 행동은
2. 하나의 x86-64 인스트럭션인 (명령어) CALL로 앞서 두 개의 일을 동시에 실행할 수 있다.
3. 만약 callee가 반환해야 할 값이 있다면, callee는 %rax 레지스터에 이 값을 저장한다.
4. callee는 스택에서 돌아가야할 주소 (return address)를 스택에서 pop 하여 이 주소가 지정하는 위치로 x86-64 인스트럭션 RET을 사용하여 jump 한다.

어떤 함수, f()가 세 개의 정수 인자를 받는다고 하자. 아래의 텍스트 다이어그램은 앞서 설명한 4가지 단계가 시작하기 전에, callee가 보는 간단한 예제 스택 프레임과 레지스터 상태를 나타낸 것이다. 함수 f가 f(1,2,3)으로 호출되었다고 해 보자. 처음 스택의 주소는 임의로 설정한 것이다.

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

program starup details

유저프로그램을 위한 Pintos C 라이브러리는 _start() 함수가 선언되어 있다. 이 함수는 lib/user/entry.c 소스 코드에 작성되어 있다. 이 함수는 유저 프로그램의 진입지점 (entry point)로써, main() 함수의 wrapper 함수이고, main()이 종료하면 exit()을 호출한다.

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

커널(운영체제)은 반드시 유저 프로그램이 실행되기 전에 함수가 필요로 하는 인자들을 레지스터에 저장해 놓아야 한다. 이러한 인자들은 위에서 설명했던 Calling convention에 의해 동작한다.

/bin/ls -l foo bar

와 같은 쉘 명령어의 인자가 어떻게 처리되는지 과정을 살펴보자.

1. 커맨드를 단어 단위로 쪼갠다 —> /bin/ls, -l, foo, bar
2. 단어들을 스택에 차례로 push 한다. 순서는 크게 중요하지 않다. 어차피 pointer로 레퍼런싱 될 것이기 때문이다. (이 때, 항상 문자열에 끝에는 ‘\0’을 넣어 주어야 함을 잊지 말자.)
3. 방금 전에 스택에 넣었던 단어들의 주소를 명령어와 인자들의 오른쪽부터 왼쪽으로 가면서 넣어준다. 이들은 argv의 각각의 원소이다. C 표준에 의해 argv[argc]는 항상 널 포인터야 한다. 이러한 순서는 argv[0]이 가장 낮은 주소 (가상 메모리 주소)를 가짐을 보장한다. (스택은 높은 주소에서 낮은 주소로 자란다.) 중간에 0x4747ffe8에 word-align이라 1바이트 데이터가 보이는데, 이는 word-align이라 한다. cpu는 항상 8의 배수 단위로 메모리에 접근하기 때문에, 성능 향상을 위해 임의로 padding을 집어넣은 것으로 생각하면 된다.
4. %rsi 레지스터에 argv[0]의 주소를 넣고, %rdi 레지스터에 argc 값을 넣는다. (인자의 개수)
5. 마지막으로, 스택에 가짜 return address 값을 넣는다. 지금 이 함수는 값을 반환하지 않으나, 스택 프레임은 여느 함수와 다르지 않다.

아래 테이블은 위의 5단계를 거친 후 레지스터의 값, 가상 메모리 주소 (주소)와 이름, 데이터, 타입을 나타내었다.

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 (*) ()
RDI: 4	RSI: 0x4747ffc0

Real Code

일단 과제를 수행하기 전에, 반드시 공식 가이드 gitbook의 모든 내용을 알아보도록 하자. 그렇지 않으면, 의미없는 일을 많이 하게 된다. 먼저, userprog/ 디렉토리에서 process.c 파일에 대부분 프로세스 관련된 함수들이 많이 있다. 공식 gitbook은 process_exec() 함수의 구현을 수정하라고 지시하였다. process_exec()의 스켈레톤 구현은 다음과 같다.

f_name 으로 무언가 들어오고, load() 함수에 인터럽트 프레임과 file_name을 전달하여 무언가를 로딩하고 있다. 그럼 먼저, f_name이 무엇인지 확인할 필요가 있다.

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


/* 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.
 *
 * This function will be implemented in problem 2-2.  For now, it
 * does nothing. */

유저 프로그램이 실행되기까지

run_task()

/* Runs the task specified in ARGV[1]. */
static void
run_task (char **argv) {
	const char *task = argv[1];

	printf ("Executing '%s':\n", task);
#ifdef USERPROG
	if (thread_tests){
		run_test (task);
	} else {
		process_wait (process_create_initd (task));
	}
#else
	run_test (task);
#endif
	printf ("Execution of '%s' complete.\n", task);
}

우리가 pintos 커널에 어떤 명령어를 전달할 경우, 즉, 프로그램이나 테스트를 실행할 경우 초기화와 필수적인 연산을 제외하고는 가장 먼저 run_task()가 실행된다. 만약, pintos -v -k -T 60 -m 20 --fs-disk=10 -p tests/userprog/args-many:args-many -- -q -f run 'args-many a b c d e f g h i j ' 와 같은 커맨드 라인으로 pintos를 실행하면, task 변수에는 argv[1]이 저장되기 때문에, args-many a b c d e f g h i j이 된다. 직접 확인해 볼 수도 있다. 다음은 실행 결과의 일부이다.

hd0:0: detected 313 sector (156 kB) disk, model "QEMU HARDDISK", serial "QM00001"
hd0:1: detected 20,160 sector (9 MB) disk, model "QEMU HARDDISK", serial "QM00002"
hd1: unexpected interrupt
hd1:0: detected 109 sector (54 kB) disk, model "QEMU HARDDISK", serial "QM00003"
Formatting file system...done.
Boot complete.
Putting 'args-many' into the file system...
Executing 'args-many a b c d e f g h i j k':

Executing ‘args-many a b c d e f g h i j k’:에 주목하면, task에 인자가 오는 것을 확인할 수 있다. run_task() 는 바로 process_create_initd(task) 를 호출하게 된다.

process_create_initd()

이 함수의 구현을 살펴보면, 다음과 같다.

/* Starts the first userland program, called "initd", loaded from FILE_NAME.
 * The new thread may be scheduled (and may even exit)
 * before process_create_initd() returns. Returns the initd's
 * thread id, or TID_ERROR if the thread cannot be created.
 * Notice that THIS SHOULD BE CALLED ONCE. */
tid_t
process_create_initd (const char *file_name) {
	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);

	/* Create a new thread to execute FILE_NAME. */
	tid = thread_create (file_name, PRI_DEFAULT, initd, fn_copy);
	if (tid == TID_ERROR)
		palloc_free_page (fn_copy);
	return tid;
}

/* A thread function that launches first user process. */
static void
initd (void *f_name) {
#ifdef VM
	supplemental_page_table_init (&thread_current ()->spt);
#endif

	process_init ();

	if (process_exec (f_name) < 0)
		PANIC("Fail to launch initd\n");
	NOT_REACHED ();
}

주석의 내용을 확인하면,

Starts the first userland program, called "initd", loaded from FILE_NAME.
The new thread may be scheduled (and may even exit)
before process_create_initd() returns.
Returns the initd's thread id,
or TID_ERROR if the thread cannot be created.
Notice that THIS SHOULD BE CALLED ONCE.

가장 먼저 실행되는 user-space의 프로그램이고, initd 프로세스이다. 이 프로세스가 process_create_initd()가 리턴되기 전에 스케줄되고, initd의 tid를 반환하거나, 이 스레드가 제대로 생성되지 않았을 경우, TID_ERROR를 반환하게 된다고 설명되어 있다.

우리가 인자로 넘겨준 file_name 에는 ` ‘args-many a b c d e f g h i j ‘ 가 들어가게 되고, 이 string을 새롭게 복사한 뒤, (그렇지 않다면 caller와 load() 함수간의 경쟁 상태가 발생할 수 있기 때문이라고 나와 있다.) 새로운 프로세스를 생성한다. 이 프로세스의 thread function은 initd 이다. initd`의 구현은 위를 참고하면 된다.

일종의 macOS의 launchd 프로세스나, Ubuntu의 initd와 비슷한 역할이고, 모든 우리의 유저스페이스 프로그램은 initd가 process_exec()을 호출하여 실행되게 된다. 이제, process_exec()을 확인하여 보자.

process_exec()

함수의 세부 구현은 다음과 같다.

/* 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. */

	/* SEL_UDESG, SEL_UCSEG ...
	 * GDT selectors defined by loader.
  	 * More selectors are defined by userprog/gdt.h. */
	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 ();
}

파일 이름 복사

	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. */

	/* SEL_UDESG, SEL_UCSEG ...
	 * GDT selectors defined by loader.
  	 * More selectors are defined by userprog/gdt.h. */
	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 ();

방금전에 인자로 넘겨주었던, argv[1]인 args-many a b c d e f g h i j가 f_name이 된다. 주석에 보면, thread 구조체에 있는 intr_frame을 사용할 수 없다고 나와 있다.

스레드 구조체를 확인하면 다음과 같은데,

struct thread {
	/* Owned by thread.c. */

    ....
    struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
};

이 인터럽트 프레임은 현재 스레드가 다시 스케줄될 때, 현재 스레드의 정보를 저장하기 때문에, 새로운 인터럽트 프레임을 생성하는 것으로 보인다. 계속 코드를 분석해 보자.

process_cleanup()

/* Free the current process's resources. */
static void
process_cleanup (void) {
	struct thread *curr = thread_current ();

#ifdef VM
	supplemental_page_table_kill (&curr->spt);
#endif

	uint64_t *pml4;
	/* Destroy the current process's page directory and switch back
	 * to the kernel-only page directory. */
	pml4 = curr->pml4;
	if (pml4 != NULL) {
		/* Correct ordering here is crucial.  We must set
		 * cur->pagedir to NULL before switching page directories,
		 * so that a timer interrupt can't switch back to the
		 * process page directory.  We must activate the base page
		 * directory before destroying the process's page
		 * directory, or our active page directory will be one
		 * that's been freed (and cleared). */
		curr->pml4 = NULL;
		pml4_activate (NULL);
		pml4_destroy (pml4);
	}
}

이 함수는 현재 실행되고 있는 스레드의 자원을 반환한다. initd 프로세스가 아닌, 새로운 프로세스 (우리의 userland process) binary를 로드하기 전에, 기존 자원을 해제하는 것으로 보인다.

load() & do_iret()

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

우리의 userland process binary가 저장되어 있는 simulated disk에서 필요한 binary를 로드하게 된다. 필요한 정보를 방금 전에 새롭게 생성한 인터럽트 프레임 _if에 저장하고, 이 프로세스로 전환한다. (do_iret)

load()

/* Loads an ELF executable from FILE_NAME into the current thread.
 * Stores the executable's entry point into *RIP
 * and its initial stack pointer into *RSP.
 * Returns true if successful, false otherwise. */
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);
	if (file == NULL) {
		printf ("load: %s: open failed\n", file_name);
		goto done;
	}

	/* Read and verify executable header. */
	...

	/* Read program headers. */
	...

	/* 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). */

	success = true;

done:
	/* We arrive here whether the load is successful or not. */
	file_close (file);
	return success;
}

함수가 매우 길어 필요한 부분만 적었다. …은 생략된 부분이다. 참고하여라.

먼저, process_activate()로 현재 프로세스를 스케줄링 한 뒤, 우리의 simulated disk에서 필요한 binary를 로드한다. 이제, 우리가 코드를 수정할 차례이다.

parsing arguments

일단, 먼저 load() 함수에서 인자로 넘어오는 file_name에 대한 파싱이 필요하다. 최소한 명령어 이름과 명령어의 인자를 구별해 줘야 하는 것이다. 예를 들어, 우리가 일반적인 OS에서 /bin/ls -a -l을 실행한다면, /bin/ls는 명령어 이름이 될 것이고, (Command) -a,-l은 인자들이 될 것이다. 현재 load() 함수로 넘어오는 file_name은 전혀 파싱 처리가 되어있지 않고 있다.

strtok_r

그럼 우리가 이런 인자를 파싱하는 것을 구현해야 할까? 다행히도, 지금은 알고리즘 수업 시간이나, 컴파일러 시간이 아니다. 우리가 직접 구현할 필요는 없고, lib/ 디렉토리 안에 있는 유용한 라이브러리 함수를 사용하면 된다! string.h에 보면, 사용할 수 있는 함수들이 나와 있다.

#ifndef __LIB_STRING_H
#define __LIB_STRING_H

#include <stddef.h>

/* Standard. */
void *memcpy (void *, const void *, size_t);
void *memmove (void *, const void *, size_t);
char *strncat (char *, const char *, size_t);
int memcmp (const void *, const void *, size_t);
int strcmp (const char *, const char *);
void *memchr (const void *, int, size_t);
char *strchr (const char *, int);
size_t strcspn (const char *, const char *);
char *strpbrk (const char *, const char *);
char *strrchr (const char *, int);
size_t strspn (const char *, const char *);
char *strstr (const char *, const char *);
void *memset (void *, int, size_t);
size_t strlen (const char *);

/* Extensions. */
size_t strlcpy (char *, const char *, size_t);
size_t strlcat (char *, const char *, size_t);
char *strtok_r (char *, const char *, char **);
size_t strnlen (const char *, size_t);

/* Try to be helpful. */
#define strcpy dont_use_strcpy_use_strlcpy
#define strncpy dont_use_strncpy_use_strlcpy
#define strcat dont_use_strcat_use_strlcat
#define strncat dont_use_strncat_use_strlcat
#define strtok dont_use_strtok_use_strtok_r

#endif /* lib/string.h */

strtok_r 설명 (번역됨)

Prototype

char * strtok_r (char *s, const char *delimiters, char **save_ptr) 

설명

문자열을 DELIMITERS (구분자) 을 기준으로, 토큰 단위로 분리한다. 처음 이 함수가 호출될 때, 인자 s는 토큰으로 분리할 문자열이 되어야 하고, 그 이후에 반복문으로 호출할 경우에는 NULL pointer가 되어야 한다. SAVE_PTR은 현재 처리하는 tokenizer의 위치 주소 (char *)를 기억하기 위한 포인터이다. 이 함수를 호출할 때마다의 반환값은 문자열의 다음 토큰이며, 더이상 남은 토큰이 없을 경우 NULL을 반환한다.

이 함수는 인접한 다수의 구분자를 하나의 구분자로 처리한다. 구분자는 단일 문자열 내에서 한 번의 호출에서 다음 호출로 변경될 수 있다. strtok_r()은 구분 기호를 null 바이트로 변경하여 문자열 S를 수정하게 된다. 따라서 S는 수정 가능한 문자열이어야 한다. 특히 문자열 리터럴은 이전 버전과의 호환성을 위해 ‘const’가 아니더라도 C에서 수정할 수 없다.

Breaks a string into tokens separated by DELIMITERS. The first time this function is called, S should be the string to tokenize, and in subsequent calls it must be a null pointer. SAVE_PTR is the address of a `char *’ variable used to keep track of the tokenizer’s position. The return value each time is the next token in the string, or a null pointer if no tokens remain.

This function treats multiple adjacent delimiters as a single delimiter. The returned tokens will never be length 0. DELIMITERS may change from one call to the next within a single string.

strtok_r() modifies the string S, changing delimiters to null bytes. Thus, S must be a modifiable string. String literals, in particular, are not modifiable in C, even though for backward compatibility they are not `const’.

example

char s[] = " String to tokenize. ";
char *token, *save_ptr;
for (token = strtok_r (s, " ", &save_ptr); token != NULL;
	token = strtok_r (NULL, " ", &save_ptr))
	printf ("'%s'\n", token);

사실, 위의 예시처럼 써 주면 되고, 주의할 점으로는 문자열이 수정 가능해야 한다. (문자열 리터럴이면 안됨) 이것만 기억하면 된다.

tokenize file_name

file_name을 먼저 공백을 기준으로 나눠 배열에 나누어 담아 주도록 하자. 이 배열을 인자 배열, args[]라 하자.

for (token = strtok_r ((char *)file_name, " ", &save_ptr); token != NULL;
    token = strtok_r (NULL, " ", &save_ptr)){
		if (args_num >= MAX_ARG_SIZE){
			success = false;
			goto done;
		}
		args[args_num] = token;
		args_num ++;
	}

	args[args_num] = 0; //Null-sentinel

예시와 같은 코드를 작성하기 위해, 먼저 필요한 변수들을 맨 앞에 선언해 주었다.

int i;
char *token;
char *save_ptr;
int args_num = 0;
int nums;
int args_size;
char* args[MAX_ARG_SIZE];
char* args_address[MAX_ARG_SIZE];

이러한 코드로, 다음과 같은 배열에 명령어 이름, 인자들이 담기게 된다.

file_name : args-many a b c d e
	*	args_num = 6
	*	args[args_num] --> [*args-many][*a][*b][*c][*d][*e][NULL]

miscellaneous..

	/* Allocate and activate page directory. */
	/* Open executable file. */
	/* Read and verify executable header. */
	/* Read program headers. */
	/* Set up stack. */

나머지 부분들의 코드는 Allocate and activate page directory -> Open executable file -> Read and verify executable header -> Read program header -> setup stack 순으로 진행된다. 현재 프로젝트에서는 확인할 필요가 없지만, 더 알아보고 싶다면 ELF 파일 형식에 대해 더 탐구하도록 하자.

Calling Convention

위의 내용에서 설명했던 Convention 대로 코드를 작성해 주면 된다.

start address

	/* Start address. */
	if_->rip = ehdr.e_entry;

먼저 인터럽트 프레임의 rip 레지스터의 값을 저장하는 부분을 프로그램의 시작 주소로 맞춘다. 인터럽트 이후에 우리의 유저 프로그램이 실행될 수 있도록 한다.

make arguments stack

위에서 말했던 순서대로, “그대로” 구현하면 된다.

1. 커맨드를 단어 단위로 쪼갠다 —> /bin/ls, -l, foo, bar
2. 단어들을 스택에 차례로 push 한다.
3. 방금 전에 스택에 넣었던 단어들의 주소를 오른쪽부터 왼쪽으로 가면서 넣어준다. (bar, foo, -l, /bin/ls의 주소들을..) 이들은 argv의 각각의 원소이다. C 표준에 의해 argv[argc]는 항상 널 포인터야 한다.
4. Word-align을 넣어준다.
5. %rsi 레지스터에 argv[0]의 주소를 넣고, %rdi 레지스터에 argc 값을 넣는다. (인자의 개수)
6. 마지막으로, 스택에 가짜 return address 값을 넣는다. 지금 이 함수는 값을 반환하지 않으나, 스택 프레임은 여느 함수와 다르지 않다.

1.은 우리가 이미 했다. 2.부터 진행하면 된다.

nums = args_num - 1;

while (nums >= 0){
	args_size = strlen(args[nums]) + 1;
	if_ -> rsp -= args_size;
	memcpy((void *) if_ -> rsp, args[nums], args_size);
	args_address[nums] = (char *)if_ -> rsp;
	nums --;
}

nums 변수는 우리가 파싱했던 인자와 명령어 배열의 인덱스를 가르킨다. 다음의 순서로 인자들을 스택에 쌓는다.

1. 맨 뒤 인자 배열부터 각 문자열의 크기를 계산하고,
2. rsp 포인터를 (스택 포인터) 감소시킨다. (스택은 아래로 자라기 때문이다.)
3. 스택에 인자 배열을 복사한다.
4. rsp의 값을 args_address[nums]에 저장한다. (인자들의 메모리 주소를 저장하기 위해)

만약 ‘args-many a b c d e’가 file_name 이었다면, 메모리의 상태는 다음과 같다. (지금까지는)

** USER_STACK의 시작점은 0x0000000047480000으로 설정되어 있다. vaddr.h를 참고하여라.

Address	Name	Data	Type
0x000000004747fffe	argv[5][…]	‘e\0’	char[2]
0x000000004747fffc	argv[4][…]	‘d\0’	char[2]
0x000000004747fffa	argv[3][…]	‘c\0’	char[2]
0x000000004747fff8	argv[2][…]	‘b\0’	char[2]
0x000000004747fff6	argv[1][…]	‘a\0’	char[2]
0x000000004747ffe4	argv[0][…]	‘args-many\0’	char[10]

word-align

가상 주소를 8의 배수 단위에 정렬해 준다. 다음 코드로 나는 rsp의 값을 8의 배수로 만들었다.

/* Word - align */
	if_ -> rsp &= ~(7ULL);

rsp는 uint64_t 이기 때문에, (64비트 부호 없는 정수) 8의 배수를 만드려면, 마지막 3비트를 0으로 만들어야 한다. 세부적인 구현은 사실 크게 상관은 없는것 같다.

if_ -> rsp -= if_ -> rsp % 8; 

과 같이 스택 포인터를 내려도 되지만, 뭔가 메모리 주소에 나눗셈을 하는게 되게 어색해 보여서 비트 연산자로 구현하였다. 여기까지 왔다면, 메모리의 상태는 다음과 같다.

Address	Name	Data	Type
0x000000004747fffe	argv[5][…]	‘e\0’	char[2]
0x000000004747fffc	argv[4][…]	‘d\0’	char[2]
0x000000004747fffa	argv[3][…]	‘c\0’	char[2]
0x000000004747fff8	argv[2][…]	‘b\0’	char[2]
0x000000004747fff6	argv[1][…]	‘a\0’	char[2]
0x000000004747ffe4	argv[0][…]	‘args-many\0’	char[10]
0x000000004747ffe0	word-align	0	uint8_t[]

address push

방금 전에 위에서 memcpy로 복사해 넣었던 문자열들의 args 배열의 역순으로 각각의 원소들의 주소를 차례로 스택에 push 한다. (즉, args_address[] 배열에 있던 원소들) 주의할 점은, 반드시 NULL sentinel을 잊어서는 안 된다.

nums = args_num - 1;

if_ -> rsp -= 8;
*(uint64_t *)(if_->rsp) = (uint64_t) 0; /*NULL-sentinel*/


while (nums >= 0){
	if_ -> rsp -= 8;
	*(uint64_t *)(if_->rsp) = (uint64_t) args_address[nums];
	nums --;
}

이제 메모리의 상태는 다음과 같다.

Address	Name	Data	Type
0x000000004747fffe	argv[5][…]	‘e\0’	char[2]
0x000000004747fffc	argv[4][…]	‘d\0’	char[2]
0x000000004747fffa	argv[3][…]	‘c\0’	char[2]
0x000000004747fff8	argv[2][…]	‘b\0’	char[2]
0x000000004747fff6	argv[1][…]	‘a\0’	char[2]
0x000000004747ffe4	argv[0][…]	‘args-many\0’	char[10]
0x000000004747ffe0	word-align	0	uint8_t[]
0x000000004747ffd8	argv[6]	0	char*
0x000000004747ffd0	&argv[5][0]	0x000000004747fffc	char*
0x000000004747ffc8	&argv[4][0]	0x000000004747fffa	char*
0x000000004747ffc0	&argv[3][0]	0x000000004747fff8	char*
0x000000004747ffb8	&argv[2][0]	0x000000004747fff6	char*
0x000000004747ffb0	&argv[1][0]	0x000000004747fff4	char*
0x000000004747ffa8	&argv[0][0]	0x000000004747ffea	char*

fake-return address and argc, argv

/* fake return address */
	if_ -> rsp -= 8;
	*(uint64_t *)if_ -> rsp = 0;

마지막으로 스택에 fake-return address를 추가한다. 그 다음,

	/* argc and argv*/
	if_->R.rdi  = args_num;
	if_->R.rsi = if_-> rsp + 8;

	success = true;

calling convention 대로 레지스터를 설정해 주고, 커널은 do_iret()을 실행하여 인터럽트 (시스템 콜)을 처리하게 된다! 최종적인 메모리 상태는 다음과 같다.

Address	Name	Data	Type
0x000000004747fffe	argv[5][…]	‘e\0’	char[2]
0x000000004747fffc	argv[4][…]	‘d\0’	char[2]
0x000000004747fffa	argv[3][…]	‘c\0’	char[2]
0x000000004747fff8	argv[2][…]	‘b\0’	char[2]
0x000000004747fff6	argv[1][…]	‘a\0’	char[2]
0x000000004747ffe4	argv[0][…]	‘args-many\0’	char[10]
0x000000004747ffe0	word-align	0	uint8_t[]
0x000000004747ffd8	argv[6]	0	char*
0x000000004747ffd0	&argv[5][0]	0x000000004747fffc	char*
0x000000004747ffc8	&argv[4][0]	0x000000004747fffa	char*
0x000000004747ffc0	&argv[3][0]	0x000000004747fff8	char*
0x000000004747ffb8	&argv[2][0]	0x000000004747fff6	char*
0x000000004747ffb0	&argv[1][0]	0x000000004747fff4	char*
0x000000004747ffa8	&argv[0][0]	0x000000004747ffea	char*
0x000000004747ffa0	fake return address	0	(uint64_t *)

check

hex_dump() 라는 비표준 함수로 메모리의 상태를 확인해 볼 수 있다.

hex_dump(if_ -> rsp, (void *) if_ -> rsp, (size_t) USER_STACK - if_ -> rsp, true);

결과는 다음과 같으면 성공이다. 현재 커널에 PIE(위치 독립 실행)이나 ASLR 기능이 없기 때문에, 메모리 주소가 언제나 같다.

000000004747ffa0                          00 00 00 00 00 00 00 00 |        ........|
000000004747ffb0  ec ff 47 47 00 00 00 00-f6 ff 47 47 00 00 00 00 |..GG......GG....|
000000004747ffc0  f8 ff 47 47 00 00 00 00-fa ff 47 47 00 00 00 00 |..GG......GG....|
000000004747ffd0  fc ff 47 47 00 00 00 00-fe ff 47 47 00 00 00 00 |..GG......GG....|
000000004747ffe0  00 00 00 00 00 00 00 00-00 00 00 00 61 72 67 73 |............args|
000000004747fff0  2d 6d 61 6e 79 00 61 00-62 00 63 00 64 00 65 00 |-many.a.b.c.d.e.|

마무리

아직까지 세부적인 system call이 구현되어 있지 않아 테스트를 시행하기에는 무리가 있다. 하지만, 우리의 유저 프로그램에게 충분히 매개변수와 매개변수의 개수 (argc, argv)를 전달하기에는 무리가 없다. 여기까지 성공적으로 수행했다면, 시스템 콜을 모두 구현하지 않아도

System Call!

이라는 문구를 콘솔에서 확인할 수 있을 것이다.