[Pintos] Project 4 - File System(FAT)

 

이번 주는 핀토스의 마지막 주차인 파일 시스템이다. 보통 핀토스는 프로젝트 2와 3이 가장 어려운 편이고, 마지막 프로젝트 4가 쉬운 편이라고 하는데 그렇다고 만만할 정도는 아니었다... 그래도 핀토스에 대한 흐름이 어느 정도 잡혀있어서 그런지 초반에 개념을 잡고 나니 구현은 생각보다 빠르게 진행됐다. 

 

초반에 개념 잡는 게 어려우니 오늘 포스팅은 파일 시스템의 기본 개념에 대해서 다뤄보려고 한다! 

 

Inode

먼저 핀토스가 제공하는 기본 코드에 대해서 살펴보자. 커널에서 파일이나 directory에 접근할 때 항상 inode라는 구조체를 거쳐서 접근하게 된다. inode 구조체를 살펴보자! 

/* In-memory inode. */
struct inode
{
	struct list_elem elem;	/* Element in inode list. */
	disk_sector_t sector;	/* Sector number of disk location. */
	int open_cnt;			/* Number of openers. */
	bool removed;			/* True if deleted, false otherwise. */
	int deny_write_cnt;		/* 0: writes ok, >0: deny writes. */
	struct inode_disk data; /* Inode content. */
};

/* On-disk inode.
 * Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk
{
	disk_sector_t start; /* First data sector. */
	off_t length;		 /* File size in bytes. */
	int is_dir;
	unsigned magic;		  /* Magic number. */
	uint32_t unused[124]; /* Not used. */
};

핀토스에서 사용하는 inode 구조체에는 inode_disk라는 구조체를 멤버 변수로 사용하고 있다. 간략하게 설명하자면 inode는 메모리 공간 상에서만 존재하는 데이터이고, inode_disk는 실제로 하드 디스크에 저장되어 있는 정보이다. 각각의 멤버 변수에 대해 조금 더 자세하게 알아보자. 

 

inode

• elem : inode가 open 되었을 때 open 된 inode들을 관리하는 리스트에 삽입하기 위해 있는 변수이다. 
• sector : inode_disk에 대한 데이터가 저장되어 있는 sector를 의미한다. 
• open_cnt : 현재 inode를 open 한 프로세스의 개수를 의미한다. 
• removed : inode가 가리키고 있는 파일의 삭제 유무를 나타낸다. 만약 removed가 true로 설정되면, inode를 참조하고 있는 마지막 프로세스가 inode를 close 할 때 파일 삭제를 진행한다. 
• deny_write_cnt : 파일의 write를 deny 설정한 횟수를 의미한다. 
• data : 실제 디스크에 저장되어 있는 inode의 내용이다. 

 

inode_disk

• start : 실제 데이터가 저장되어 있는 sector의 시작점을 의미한다. 
• length : 파일의 길이를 의미한다. 
• is_dir : 구현 과정에서 추가한 변수로, 현재 inode가 directory인지를 나타내는 변수이다. 
• unused : inode_disk의 크기를 하드디스크의 한 sector와 맞추기 위한 변수이다. 실제로 사용되지는 않는다. 

 

모든 파일이나 directory는 이 inode를 통해 관리된다. directory 또한 파일처럼 취급하고 따라서 directory에도 파일과 마찬가지로 inode 구조체가 붙는다. 모든 파일이나 directory는 고유한 inode를 가지며, inode가 저장되어 있는 sector를 inumber라고 한다. 

 

위와 같이 ls -i 옵션을 통해 파일의 inumber를 확인해 볼 수 있다. inode_disk는 아주 간략한 정보만 담고 있지만, 실제로 inode는 파일의 권한이나 마지막 수정 시간 등 더 많은 메타데이터를 담고 있다. 

위와 같이 stat 명령어를 통해 파일이나 directory의 더욱 자세한 정보를 확인할 수 있다. 

 

 

How to access File/Directory

이제 이 inode에 담겨있는 정보를 통해 실제 directory나 파일에 접근하는 방법을 알아보자. 하드 디스크가 위의 그림과 같이 있다고 해보자. 아주 간단하게 표현하긴 했지만 위의 그림과 같이 디스크의 맨 앞부분은 예약된 영역으로 사용한다. 이후 우리가 사용할 FAT가 위치하고, 그 뒷부분이 모두 data region이다. 

보통 root directory cluster는 그림과 같이 FAT의 바로 뒤에 위치한다. root directory cluster의 안을 조금 더 자세히 들여다보자.

그림과 같이 root directory cluster에는 여러 파일 또는 directory의 directory entry들이 담겨있다. 구조체를 확인하고 넘어가자.

/* A single directory entry. */
struct dir_entry
{
	disk_sector_t inode_sector; /* Sector number of header. */
	char name[NAME_MAX + 1];	/* Null terminated file name. */
	bool in_use;				/* In use or free? */
};

위와 같이 세 개의 변수가 있는 것을 확인할 수 있다. 

• inode_sector : 파일 또는 directory에 대한 inode가 위치한 sector를 의미한다. 
• name : 파일 또는 directory의 이름을 의미한다. 
• in_use : directory 내에서 실제로 사용되고 있는지를 확인하는 flag이다. 만약 false로 설정되어 있다면, 존재하지 않거나 삭제된 파일을 의미한다. 

directory 내의 entry들은 모두 크기가 동일하기 때문에, 파일이나 directory를 찾을 때에는 directory entry들을 검사하며 name을 비교하여 찾을 수 있다. 

directory entry에 들어있는 내용들을 나타내면 위의 그림과 같다. 각각의 entry들이 모두 파일의 inode 위치와 이름을 가지고 있는 것을 볼 수 있다. 여기서 만약 jungle이라는 이름의 directory로 접근한다고 생각해 보자. 그림에서는 dir1이다. 

 

dir1에 대한 entry를 읽어 들여 inode_sector가 45번인 것을 알아냈다! 이제 디스크의 45번 sector로 접근해 정보를 불러온다. 여기에서 우리는 jungle directory에 대한 data가 56번 sector에 저장되어 있으며, 길이는 58475byte인 것을 알 수 있다. 

 

우리는 이제 위와 같이 jungle directory에 대한 data에 접근할 수 있게 되었다! 현재 접근한 파일은 directory이기 때문에, dir1 data에는 위에서 root directory를 살펴본 것과 같이 directory entry들이 담겨있을 것이다. 파일에 대한 접근 또한 이와 동일하며, 단지 읽어 들일 데이터의 형태만 다를 뿐이다. 

 

 

 

FAT(File Allocation Table)

이번에는 위의 그림에서 나와있는 FAT에 대해 알아보자. 기본적으로 핀토스에서는 디스크 sector의 할당 여부를 free_map을 활용하여 나타내고 있다. free_map은 bitmap 자료구조로 구현되어 있으며, sector 할당 요청이 들어왔을 때 bitmap_scan_and_flip 함수를 통해 연속적으로 할당 가능한 sector들을 찾고 bitmap의 bit들을 1로 뒤집는다. 이러한 방식 때문에, 기존의 free_map을 활용한 방식에서는 파일을 만들기 위해서 파일 크기만큼의 연속적인 sector가 비어있어야 했다. 이를 FAT 방식으로 바꾸어 파일을 흩어진 sector들에 나누어 저장하는 방식을 구현하는 것이 프로젝트 4의 과제이다! 

FAT에서는 sector들을 관리하기 위해 디스크의 sector를 cluster 단위로 나누어 관리한다. 

그림으로 나타내면 대략 위와 같다! 여기에서 우리가 만약 어떤 파일을 만드는데, 총 세 개의 cluster가 필요하다고 해보자. 원래의 free_map 방식이었으면 위의 그림에서 CLUSTER2에서 CLUSTER4 까지를 할당했을 것이다. 

그렇다면 같은 상황에서 위와 같이 CLUSTER2와 CLUSTER4가 이미 할당된 상태라면 어떻게 될까? free_map 방식에서는 CLUSTER3은 연속적으로 할당이 불가능하기 때문에 사용할 수 없게 된다. 하지만 FAT 방식에서는 CLUSTER3도 사용할 수 있다! 

위와 같이 세 개의 cluster를 요청했을 때, CLUSTER 3, 4, 11을 할당해 준다고 하자. 이때 FAT는 다음과 같이 설정된다. 

테이블에서 왼쪽은 테이블의 인덱스, 오른쪽은 해당 인덱스의 value를 나타낸 것이다. 이렇게 다음 내용이 저장되어 있는 cluster를 FAT에 저장함으로써 서로 다른 부분에 데이터가 저장되어 있어도 파일을 연속적으로 읽는 것이 가능해진다. 이때 마지막 cluster는 EOChain 값을 설정하여 파일의 끝을 의미하게 한다.