(2022.02.16) Extend File Descriptor 가이드라인

오늘 글 참 많이 쓰네 ㅋㅋㅋ

 

이제 이것만 하면 프로젝트 2도 끝이다. 가기 전에 프로젝트 3 가이드라인까진 작성할 수 있을 것 같다. 매뉴얼에는 살벌한 멘트가 우리를 반겨준다.

YOU SHOULD PASS ALL TESTCASES FOR EXTRA TO GET THE CREDIT. TAKE ALL OR NOTHING.

 

와우... 테케 개수가 몇 개이길래? 두 개네? 심지어 multi-oom까지 쳐도 3개다. 이것만 통과하면 끝이다. 물론 프로젝트 3부터는 이런 얍삽이 방지를 위해 히든 테케가 존재한다고 한다. (모르지 프로젝트 2에도 있을지) 그래서 현재 정해둔 목표는 프로젝트 3까지는 추가 플젝을 해 보고 프로젝트 4는 되도록 손절하는 것이다. 내용도 무시무시하던데 시간이 정말 썩어나면 하는 것으로 하자.

 

어쨌든 이번 추가 플젝의 목표는 stdin / stdout을 닫는 것을 허용하고, dup2 system call을 구현하는 것이다. 예전 pintos를 아는 사람은 이걸 고려해서 stdin / stdout을 닫으면 실패하도록 해야 하는 기존의 테케가 전부 없어졌다는 것을 알 수 있을 것이다. 아무튼 현재까지 내가 구현한 방식은 이것을 전부 포섭하도록 구현했다. _close syscall을 보면 stdin / stdout을 닫더라도 아무런 문제가 없다.

void _close(int fd)
{
	filesys_enter();

	struct fildes *fd_entry = fd_search(fd);
	struct free_fildes *ffd;
	struct file *fp;

	if (fd_entry == NULL) // not valid fd
		goto close_done;

	list_remove (&fd_entry->fd_elem);
	fp = fd_entry->fp;
	free (fd_entry); // always free what you malloc-ed;

	ffd = (struct free_fildes *)malloc (sizeof(struct free_fildes));
	if (ffd != NULL)
	{
		ffd->fd = fd;
		list_insert_ordered(&thread_current()->free_fd_list, &ffd->ffd_elem, cmp_fd, NULL);
	}
	
	if (fp != 0 && fp != 1)
		file_close (fp);

close_done:
	filesys_exit();
}

미리 고려해서 구현하니 역시 편하다. 이제 dup2를 살펴본다.

 

---

 

나에게는 dup2는 자주 쓸 일이 없어 다소 생소한 syscall이다. 예-전 해킹 문제에서나 몇 번 봤지, 실제로 쓴 적은 거의 없을 것이다. 매뉴얼을 읽어보면 dup2는 oldfd, newfd 인자 두 개를 받아 oldfd의 복사본인 newfd를 만드는 것이라고 한다. 성공할 경우 newfd를 반환, newfd가 기존에 열려있는 fd일 경우 기존에 연결된 파일을 닫고 oldfd의 복사본이 된다.

 

대체 dup2가 하는 "fd의 복사본"을 만든다는 것이 무엇일까? 이는 같은 file 포인터를 공유한다는 것을 의미한다. 단순히 fork처럼 file_duplicate로 복사하는 것이 아니다. file_duplicate의 경우 한 쪽에서 seek를 쓴다고 할지라도 다른 쪽에서 파일 read/write offset이 변경되지는 않는다. 그러나 dup2로 복사된 fd의 경우는 다르다. 한 쪽에서 seek를 써서 파일의 read/write offset이 변했다면 다른 fd에서 tell을 하더라도 변경된 offset이 반환되어야 한다.

 

우선 이러한 특징을 알아둔 뒤 주어진 입력에 따른 fd의 행동 양상을 살펴보자. 어떤 fd가 주어질 경우 그 fd는 아무 파일과도 연결되어 있지 않은 신규 fd이거나 파일과 연결된 기존 fd일 것이다. 이에 따라 dup2에 주어진 입력이 4가지로 나뉜다.

 

1. oldfd 기존, newfd 기존
2. oldfd 기존, newfd 신규
3. oldfd 신규, newfd 기존
4. oldfd 신규, newfd 신규

매뉴얼에 따라 해당 경우들에 dup2가 해야 하는 행동을 살펴보면 아래와 같다.

 

1. oldfd 기존, newfd 기존 : newfd와 연결된 파일을 닫고 newfd는 oldfd의 복사본이 된다. 성공했으면 newfd 반환
2. oldfd 기존, newfd 신규 : newfd는 oldfd의 복사본이 된다. 성공했으면 newfd 반환
3. oldfd 신규, newfd 기존 : dup2는 실패하며 -1을 반환한다. newfd에 연결된 파일은 닫지 않는다.
4. oldfd 신규, newfd 신규 : dup2는 실패하며 -1을 반환한다.

매뉴얼에서는 특수 케이스로 oldfd = newfd인 경우까지 설명하고 있다. 아무것도 하지 않고 newfd를 반환하면 된다고 한다.

 

일단 해당 함수를 구현하려면 수정해야 하는 주요 사항이 있다. 현재까지 file descriptor의 배정은 전적으로 커널에게 맡겨져 있었다. 때문에 last_allocate 이전의 fd는 모두 배정되어 있거나 free_fd_list에 들어가 있다고 장담할 수 있었다. 그러나 dup2로 fd를 인위적으로 만들어 낼 수 있게 되면서 last_allocate를 잡는 기준이 변경되어야 할 것이다. (최악의 경우 구조를 뜯어고쳐야 할듯...)

 

위와 같은 수정사항은 옆으로 치워놓고 여기까지 봤을 때, 핵심적인 사항은 한 fd에서 취한 행동을 다른 fd와 동기화시키는 것이다. 다음과 같은 해결책 등을 생각해볼 수 있다.

 

• 복사된 fd를 가진 fildes 구조체는 file 구조체를 공유한다.
• 복사된 fd를 가진 fildes 구조체는 fildes 구조체 내에 같은 파일을 가리키는 fd를 모두 저장한다.
  변동이 있을 경우 해당 fd를 가진 fildes 구조체에 통보한다.
• 새로운 구조체를 만드는 것
• ...

두 번째 경우는 너-무 수정할 것이 많다. 간단한 read/write의 경우에도 모든 리스트를 순회하면서 tell과 seek를 호출해야 한다. 가장 현실적인 것은 첫 번째 경우인데 이 것도 간단하지는 않다. 한 fd가 파일을 닫을 경우 file_close는 해당 file 포인터를 완전히 free시키기 때문이다. 나머지 fd와 연관된 fp가 dangling 포인터가 되지 않도록 대비가 필요하다.

 

이런 저런 고민을 하다가 모든 안을 적절히 합치면 어떨까라는 생각이 들었다. 그냥 이것 저것 끄적이다가 든 생각이라 아직 날것이라 정리가 조금 더 필요하다. 동작 방법은 대략 다음의 그림과 같다.

 

가장 처음 상황

dup2(3, 4)가 실행된 이후

close(5)가 된 이후

그림에 대한 설명을 하자면

 

• dup2가 호출될 때 마다 해당 fd들을 리스트로 가지고 있는 구조체를 만든다.
• dup2의 대상이 된 fd들은 위에서 생성된 구조체의 주소를 들고 있다.
• dup2의 대상이 된 fd들은 동일한 file 구조체를 공유한다.
• 만약 dup2의 대상이었던 fd 중 하나가 close될 경우 dup2_union에서 해당 fd를 제거한다. dup2_union이 NULL이 아니라면 복제된 다른 fd가 있다고 판단한다.
• dup2_union에서 close 대상인 fd를 제거했더라도 fd가 2개 이상 남아있을 경우 dup2_union은 유지한다. 1개뿐이라면 dup2_union도 해제한다.
• close가 되려는 파일 구조체가 공유되고 있을 때의 문제를 해결하기 위해 file_duplicate를 활용해 close될 파일 구조체의 복사본을 만든다. (마지막 그림에서는 A') 기존 파일 구조체(A)는 정상적으로 file_close로 해제시키고 dup2_union을 참조해 각 fildes 구조체의 file 포인터를 새로운 파일 구조체를 가리키도록 update한다.

으어어어.. 이제 이걸 또 fork에서는 복사도 해줘야 한다. ㅋㅋㅋㅋㅋㅋ 대충 이 정도면 아마 dup2 구현하는 데에는 문제 없을 것이다.

 

이제 다시 지금의 fd 할당 문제를 살펴보자. 우선 last_allocated 기준으로 fd를 배정할 때 인위적으로 배정된 fd로 인해 충돌이 날 가능성이 있다는 것이다. 예를 들어 fd가 5까지 할당된 시점에 (last_allocated = 5) dup2(2, 6)을 호출해 성공하고 다시 open을 한다면 last_allocated + 1을 반환하는 현 코드의 특성상 충돌이 일어난다.

 

free_fd_list에서 fd를 배정하는 것 또한 문제가 생긴다. 현재 free_fd_list의 모든 엔트리는 last_allocated보다 작다는 전제가 들어가 있다. 허나 dup2로 큰 수를 fd로 배정한 뒤, 해당 fd를 close하면 free_fd_list에 큰 수가 들어가서 "작은 fd 우선 배정 원칙"에 어긋나게 된다. 따라서 코드를 다음과 같이 수정한다.

 

• free_fd_list에 원소가 존재한다면 가장 앞의 엔트리의 fd가 last_allocated보다 작은지 검사한다. 만약 작다면 해당 fd를 반환하고, 크다면 인위적으로 배정된 fd일 것이므로 나머지 엔트리들도 모두 없애버린다.
• 만약 free_fd_list에서 fd를 반환받지 못했다면 (처음부터 비어있었거나 모두 부적절 fd), 현재 fd_list는 적어도 last_allocated까지는 전부 fd가 배정되어 있다는 것이다. 따라서 last_allocated + 1 부터 시작해 비어있는 fd를 발견할 때까지 탐색한다.

문제는 가장 마지막의 탐색 부분. 이건 리스트로 구현한 이상 이제 O(n)의 시간복잡도를 피할 수는 없게 되었다. 만약 해당 사항을 수정했는데, multi-oom가 시간 초과에 걸리게 될 경우, pintos에서 제공하는 다른 자료구조인 hash를 써먹을 방도를 연구해보자.