[SW정글] Week 11 개발일지

SW정글/OS

[SW정글] Week 11 개발일지

초혼 2023. 1. 30. 16:46

Week11 PintOS Filesystem

File Allocation Table (FAT)

swift-shame-3ee.notion.site

File Allocation Table (FAT)

sector

각 sector들은 sector number를 통해 접근할 수 있다 → disk에서 주소 역할
disk는 일정한 크기(512bytes)를 가지는 sector로 나누어져있다

cluster

file을 저장하는 단위
1개 혹은 다수의 sector로 구성 → pintos에서는 1 cluster = 1 sector
큰 file의 경우 다수의 cluster에 저장된다
하나의 file을 저장하는 다수의 cluster를 배치하는 방법 여러가지가 있다
- 연속된 space에 배치
  - external fragmentation에 취약
  - file을 저장하는 cluster 수와 시작하는 cluster의 sector number를 저장
- linked list
  - 마지막 cluster는 End Of cluster 값을 저장
  - 무조건 처음 cluster부터 시작해서 원하는 cluster를 찾아야하므로 뒤의 cluster에 접근할 때 overhead가 심함
  - cluster 내부에 자신의 다음 cluster의 sector number를 저장
- multi-level indexing
  - doubly indirect block은 또 다른 indirect block이 있는 주소가 들어있는 table로 구성
  - direct block은 cluster의 주소가 들어있는 table로 구성
  - indirect block은 또 다른 direct block이 있는 주소가 들어있는 table로 구성
  - 크기가 제한된 direct, indirect, doubly indirect block으로 구성
- file allocation table (FAT)

File Allocation Table (Fat)

disk의 시작 부분에 file cluster에 대한 정보가 있는 table을 만들어서 사용
cluster는 자신과 mapping 되는 fat에 다음 cluster의 주소가 있음
자신이 마지막 cluster라면 EOCluster 값이 있음

간단해서 많은 filesystem에서 지원하고 이동식 disk에 많이 사용
안정성이 낮음 → 백업용 fat을 만들어서 2개의 fat을 운용하기도 함

FAT에서 작동하는 filesys

File Growth

Subdirectory

parse_path

subdirectory 구현으로 단순히 file_name이 아닌 path가 입력된다
이를 parsing해서 경로와 최종적인 file_name을 return

struct dir *parse_path(char *path_name, char *file_name)
{
	struct thread *curr = thread_current();
	struct dir *dir;

	char path[512];
	strlcpy(path, path_name, strlen(path_name) + 1);

	if (path == NULL || file_name == NULL)
		return NULL;

	if (strlen(path) == 0)
		return NULL;

	if (path[0] == '/')
		dir = dir_open_root();
	else
		dir = dir_reopen(curr->curr_dir);

	char *token, *next_token, *save_ptr;
	token = strtok_r(path, "/", &save_ptr);
	next_token = strtok_r(NULL, "/", &save_ptr);

	struct inode *inode = NULL;
	while (token != NULL && next_token != NULL)
	{
		if (!dir_lookup(dir, token, &inode))
			goto fail;

		if (inode_is_link(inode))
		{
			char *link_name = inode_get_link_name(inode);
			strlcpy(path, link_name, strlen(link_name) + 1);

			strlcat(path, "/", strlen(path) + 2);
			strlcat(path, next_token, strlen(path) + strlen(next_token) + 1);
			strlcat(path, save_ptr, strlen(path) + strlen(save_ptr) + 1);

			dir_close(dir);

			if (path[0] == '/')
				dir = dir_open_root();
			else
				dir = dir_reopen(curr->curr_dir);

			token = strtok_r(path, "/", &save_ptr);
			next_token = strtok_r(NULL, "/", &save_ptr);

			continue;
		}

		if (inode_is_dir(inode) == INODE_FILE)
			goto fail;

		dir_close(dir);

		dir = dir_open(inode);

		token = next_token;
		next_token = strtok_r(NULL, "/", &save_ptr);
	}

	if (token == NULL)
		strlcpy(file_name, ".", 2);
	else
	{
		if (strlen(token) > NAME_MAX)
			goto fail;

		strlcpy(file_name, token, strlen(token) + 1);
	}

	return dir;

fail:
	dir_close(dir);
	return NULL;
}

chdir

현재 process의 작업 directory를 변경하는 syscall
작업 directory → path가 상대경로일때 base가 되는 directory

bool chdir(const char *name)
{
	struct thread *curr = thread_current();

	/* string copy to avoid race condition */
	char *copy_name = (char *)malloc(strlen(name) + 1);
	if (copy_name == NULL)
		return false;
	strlcpy(copy_name, name, strlen(name) + 1);

	/* input is zero */
	if (strlen(copy_name) == 0)
		return false;

	/* set base directory by path style(absolute or relative) */
	struct dir *dir;
	if (copy_name[0] == '/')
		dir = dir_open_root();
	else
		dir = dir_reopen(curr->curr_dir);

	/* path parsing */
	char *token, *save_ptr;
	token = strtok_r(copy_name, "/", &save_ptr);

	struct inode *inode = NULL;
	while (token != NULL)
	{
		if (!dir_lookup(dir, token, &inode))
			goto fail;

		if (!inode_is_dir(inode))
			goto fail;

		dir_close(dir);
		dir = dir_open(inode);

		token = strtok_r(NULL, "/", &save_ptr);
	}

	/* change current working directory */
	dir_close(curr->curr_dir);
	curr->curr_dir = dir;
	free(copy_name);

	return true;

fail:
	dir_close(dir);
	if (inode)
		inode_close(inode);

	return false;
}

mkdir

새로운 directory를 만드는 syscall

bool mkdir(const char *dir)
{
	/* string copy to avoid race condition */
	char *copy_dir = (char *)malloc(strlen(dir) + 1);
	if (copy_dir == NULL)
		return false;
	strlcpy(copy_dir, dir, strlen(dir) + 1);

	/* filesys_create_dir */
	lock_acquire(&file_lock);
	bool succ = filesys_create_dir(copy_dir);
	lock_release(&file_lock);

	free(copy_dir);

	return succ;
}

bool filesys_create_dir(const char *name)
{
	bool success = false;

	/* parsing path */
	char file_name[NAME_MAX + 1];
	struct dir *dir = parse_path(name, file_name);

	/* allocate sector to new inode_disk */
	cluster_t inode_cluster = fat_create_chain(0);
	disk_sector_t inode_sector = cluster_to_sector(inode_cluster);

	struct inode *sub_dir_inode;
	struct dir *sub_dir = NULL;

	success = (dir != NULL														                        // is success path parsing
			   && dir_create(inode_sector, 16)								                	  // create dir
			   && dir_add(dir, file_name, inode_sector)							              // add new dir to parsing dir
			   && dir_lookup(dir, file_name, &sub_dir_inode)				          	  // find inode of new dir
			   && dir_add(sub_dir = dir_open(sub_dir_inode), ".", inode_sector)	  // add "." to new dir
			   && dir_add(sub_dir, "..", inode_get_inumber(dir_get_inode(dir)))); // add ".." to new dir
	if (!success && inode_cluster != 0)
		fat_remove_chain(inode_cluster, 0);

	dir_close(sub_dir);
	dir_close(dir);

	return success;
}

readdir

open된 directory에 있는 file 혹은 directory를 1개씩 읽어온다

→ 현재 struct dir에 있는 pos에서 struct dir_entry를 1개 읽어오고 pos를 앞으로 이동

→ 다음 호출 때는 변경된 pos에서 읽어오기 때문에 다음 entry가 읽어진다

→ pos을 계속해서 유지시켜야한다 = struct dir를 닫으면 안된다

→ struct dir을 다음 호출 때 어떻게 넘겨줄지가 문제

→ 입력 받은 fd와 연결된 struct file을 활용

bool readdir(int fd, char *name)
{
	if (name == NULL)
		return false;

	struct file *f = process_get_file(fd);
	if (f == NULL)
		return false;

	/* return when fd is file */
	if (inode_is_dir(f->inode) == INODE_FILE)
		return false;

	/* point struct file with struct dir
	   both struct's first and second member is same(inode, pos)
	   use struct file pos for dir */
	struct dir *dir = f;

	bool succ = dir_readdir(dir, name);

	return succ;
}

bool dir_readdir(struct dir *dir, char name[NAME_MAX + 1])
{
	struct dir_entry e;

	while (inode_read_at(dir->inode, &e, sizeof e, dir->pos) == sizeof e)
	{
		/* advace pos */
		dir->pos += sizeof e;

		/* skip ".", ".." */
		if (!strcmp(e.name, ".") || !strcmp(e.name, ".."))
			continue;

		if (e.in_use)
		{
			strlcpy(name, e.name, NAME_MAX + 1);
			return true;
		}
	}
	return false;
}

isdir

fd와 연결된 file이 file인지 directory인지 check

inumber

fd와 연결된 file의 inode의 inumber를 return
inumber는 inode를 구분하는 key값
pintos에서는 inode_disk가 저장되어 있는 sector number를 inumber로 활용

Soft link

soft link file을 만드는 syscall
symlinkhard link는 같은 inode를 포인팅하는 새로운 struct를 만듬(file or dir)
soft link는 parse_path하는 과정에서 기존의 struct를 포인팅하게 만듬