(2022.03.27) Indexed & Extensible 가이드라인 (1)

해당 매뉴얼을 이해하는 데에는 FAT 방식에 대한 이해가 필요하기 때문에 FAT를 먼저 공부하고 왔다.

 

파일 시스템은 파일의 내용을 기본적으로는 섹터에 담아서 저장하며, 관리의 편의성을 위해 이러한 섹터들 중 연달은 섹터를 여러개를 모은 "클러스터" 단위로 관리한다. 파일이 한 클러스터 안에 다 담기지 않을 경우에는 여러 클러스터를 활용해 파일을 저장해야 할 것이다. 이 때, 사용되는 각 클러스터를 어떻게 관리할지가 주요한 문제이다. 버클리 FFS의 경우 이를 inode에서 indirect inode, double indirect inode 등으로 접근할 수 있도록 하였다. FAT는 그보다 훨씬 단순하다. 사용된 클러스터를 연결 리스트 방식으로 관리하는데에서 아이디어를 착안한 것이다.

 

예를 들어 한 파일의 내용이 217번, 618번, 339번 클러스터에 순차적으로 쓰여있다고 하자. 이러한 파일의 내용을 전체 순회할 때 어떻게 217, 618, 339 클러스터가 사용된다는 것을 알 수 있을까? 만약 클러스터의 섹터 내에 연결 정보를 직접 저장한다면, 어떤 클러스터가 파일 내용을 담고 있는지 파악을 할 수 있을 것이다. 그러나 random access, 또는 파일 하단 접근 같은 경우 필요하지도 않는 섹터의 정보를 읽어오느라 파일 접근성이 떨어질 것이다.

 

우리가 필요한 것은 파일의 정보가 아닌 클러스터 연결 정보이므로, 이를 분리해 따로 관리하면 더 빠른 시간 내에 필요한 자원을 찾을 수 있을 것이다. 이를 분리한 구조가 바로 File Allocation Table, 줄여서 FAT이며, 그림과 같이 엔트리가 다음 클러스터의 인덱스를 나타내어 따라가면서 찾을 수 있도록 만들었다. 아래의 그림이 FAT 동작 방식의 핵심이라고 할 수 있다.

 

이제 다시 매뉴얼로 돌아오자. 왜 FAT를 공부할 필요가 있었냐면 이제 핀토스는 효율성을 버리고 우리들의 편의성을 위해 FAT 방식의 작동을 택했기 때문이다.

In practice, this probably means using an index structure with direct, indirect, and doubly indirect blocks. In previous semesters, most students adopted something like what you have learned as Berkeley UNIX FFS with multi-level indexing. However, to make your life easier, we make you implement it in an easier way: FAT. You must implement FAT with given skeleton code. Your code MUST NOT contain any code for multi-level indexing (FFS in the lecture). You will receive 0pts for file growth parts.

 

사실 개인적인 생각으로는 학생들의 편의보다는 indirect inode, double indirect inode를 찾아가는 수많은 코드에서의 유사성을 참다 못해 결국 FFS를 금지시켜 버렸다고 생각한다. 내가 전회차에서 회귀된 것도 이 때문이었거든.... 암튼 그것이 소멸됐다니 속이 후련하다. 때문에 이제 파일 시스템은 FAT로 구현해야 한다.

 

FAT는 각 cluster의 다음에 올 cluster를 알려주는 구조이다. 핀토스에서는 external fragmentation을 최소화하기 위해 cluster의 size를 줄였고, 이에 한 cluster가 하나의 sector로만 구성되어 있다. 실질적으로는 같으나, cluster 차원에서 볼 때와 sector 관점에서 볼 때 이들은 numbering이 달라질 수 있기에 이 점을 염두하면서 구현을 하도록 한다.

 

프로젝트 4부터는 filesys_init을 포함한 여러 함수가 바뀌게 된다. #ifdef EFILESYS로 제약을 걸어두었던 코드들이 활성화되기 때문인데 이들을 살펴보면서 우리가 고쳐야 할 것을 알아보자.

void
filesys_init (bool format) {
	filesys_disk = disk_get (0, 1);
	if (filesys_disk == NULL)
		PANIC ("hd0:1 (hdb) not present, file system initialization failed");

	inode_init ();

	fat_init ();

	if (format)
		do_format ();

	fat_open ();
}

void
filesys_done (void) {
	fat_close ();
}

static void
do_format (void) {
	printf ("Formatting file system...");

	/* Create FAT and save it to the disk. */
	fat_create ();
	fat_close ();

	printf ("done.\n");
}

filesys를 초기화하고 끝내는 부분에서 이제 fat.c에 정의된 함수들이 호출된다. 때문에 fat.c를 이제 열어볼 필요가 있다. fat.c를 열면, FAT의 초기화를 위한 fat_init, fat_create, fat_close 등의 함수가 있는 것을 볼 수 있다. 그럼 대체 구체적으로 FAT는 어떤 방식으로 정의되는가 해서 보니 핀토스에서 제공하는 FAT의 틀로 다음의 구조체가 마련되어 있다.

/* Should be less than DISK_SECTOR_SIZE */
struct fat_boot {
	unsigned int magic;
	unsigned int sectors_per_cluster; /* Fixed to 1 */
	unsigned int total_sectors;
	unsigned int fat_start;
	unsigned int fat_sectors; /* Size of FAT in sectors. */
	unsigned int root_dir_cluster;
};

/* FAT FS */
struct fat_fs {
	struct fat_boot bs;
	unsigned int *fat;
	unsigned int fat_length;
	disk_sector_t data_start;
	cluster_t last_clst;
	struct lock write_lock;
};

static struct fat_fs *fat_fs;

해당 fat_fs는 전역 변수로 fat_init에서 공간이 할당된다. fat_fs 내의 boot 블럭을 파일 시스템에서 읽어오거나 처음 파일 시스템이 가동되는 경우, fat_boot_create에서 새롭게 만들어진다.

void
fat_init (void) {
	fat_fs = calloc (1, sizeof (struct fat_fs));
	if (fat_fs == NULL)
		PANIC ("FAT init failed");

	// Read boot sector from the disk
	unsigned int *bounce = malloc (DISK_SECTOR_SIZE);
	if (bounce == NULL)
		PANIC ("FAT init failed");
	disk_read (filesys_disk, FAT_BOOT_SECTOR, bounce);
	memcpy (&fat_fs->bs, bounce, sizeof (fat_fs->bs));
	free (bounce);

	// Extract FAT info
	if (fat_fs->bs.magic != FAT_MAGIC)
		fat_boot_create ();
	fat_fs_init ();
}

void
fat_boot_create (void) {
	unsigned int fat_sectors =
	    (disk_size (filesys_disk) - 1)
	    / (DISK_SECTOR_SIZE / sizeof (cluster_t) * SECTORS_PER_CLUSTER + 1) + 1;
	fat_fs->bs = (struct fat_boot){
	    .magic = FAT_MAGIC,
	    .sectors_per_cluster = SECTORS_PER_CLUSTER,
	    .total_sectors = disk_size (filesys_disk),
	    .fat_start = 1,
	    .fat_sectors = fat_sectors,
	    .root_dir_cluster = ROOT_DIR_CLUSTER,
	};
}

fat_boot_create에서 fat_sectors를 지정하는 저 식이 어떻게 나온 것인지 생각해보았다. (N - 1)/M + 1의 구조는 N이 M의 배수가 아니어서 잔여가 남더라도 충분한 개수를 지정하기 위한 형태라는 것을 알고 있다. 그런데, 분모의 + 1은 왜 있는것인가를 고민했다. 생각해보니 FAT는 한 "cluster"에서 다음 "cluster"가 어디인지 찾기 위한 구조이다. 이를 풀어 설명함면 FAT에 cluster가 아닌 sector는 굳이 매핑될 필요가 없는 것이다. 따라서 FAT 자체를 저장하기 위해 사용되는 sector는 FAT의 엔트리로서 들어갈 필요가 없기에 512/4 = 128개의 sector를 저장함과 동시에 FAT를 저장하는 한 개의 sector도 같이 포함하여 나눠주는 것이다.

 

도식화하면 디스크에는 아래와 같이 저장되는 것이라고 정리할 수 있다.

 

여기서 N은 disk_size (filesys_disk) 에 해당하는 수이며, 1 ~ f의 섹터의 크기에 해당하는 FAT로 f + 1부터 N - 1에 해당하는 cluster 겸 sector의 연결 상태를 표현하는 것이 가능하다.

 

그 외의 함수들은 할당한 자원을 해제하거나, 필요한 연결을 해 주는 기능성 측면의 함수들로 구성되어 있다. 이 정도면 기존에 있는 FAT 코드는 충분히 살펴본 것 같다. 이제 해야 하는 것이 무엇인지 살펴보자.

cluster_t fat_fs_init (void);

fat_fs의 멤버인 fat_length와 data_start를 초기화하라고 매뉴얼에 나온다. fat_length는 파일 시스템 내에 얼마나 많은 cluster가 있는지를 나타내는 것이며, data_start는 어디서부터 파일 저장이 시작되는 sector인지를 표시하는 값이다. 그외에도 초기화할 것이 있다면 해당 함수에서 해주면 된다고 한다. 

 

다음으로는 FAT를 직접적으로 조작하는 함수인

cluster_t fat_create_chain (cluster_t clst);
void fat_remove_chain (cluster_t clst, cluster_t pclst);
void fat_put (cluster_t clst, cluster_t val);
cluster_t fat_get (cluster_t clst);

를 만드는 것이 목표이다. 자세한 설명은 매뉴얼에 꽤 직관적으로 나와있어서 생략하고, 해당 함수들을 만든 뒤에는 FAT에 해당 함수들로만 접근해야 할 것이다.

 

마지막으로, 아래와 같이 cluster에서 sector로 변환할 수 있는 함수를 만들어야 한다. 

disk_sector_t cluster_to_sector (cluster_t clst);

처음에는 그냥 반환만 하면 되는 것이 아닌가라고 생각했는데, ROOT_DIR_CLUSTER가 1로 정의되었지만 1번 sector는 FAT를 위해 할당되어 있으니, 해당 변환에서 이러한 충돌을 해소할 필요가 있다고 나중에 깨달았다. 아마 fat_fs의 data_start를 운용해서 구현하면 될 것이다.

 

여기까지가 FAT를 운용하는 파트였다. 근데 아직 매뉴얼이 안 끝났네? 또 뭐가 남았나 하고 보니.. File Growth 파트였다. 이건 다음 포스팅 때 따로 가이드라인을 작성하도록 하자.