[SW정글] Week 11 개발일지

Week11 PintOS Filesystem

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를 포인팅하게 만듬