PintOS Project 4 - File Systems (1) Indexed and Extensible Files(정글사관학교 88일차 TIL)

 

Gitbook 정리는 요기!

Indexed and Extensible Files

 

 

0. 과제 개요

이번 과제에서는 FAT 파일 시스템을 구현하는 것이 목표이다. Gitbook 설명을 보면 현재 파일 시스템 구조는 연속 할당 방식이라는 것을 알 수 있다. 이전 글에서도 설명했듯, 연속 할당 방식은 하나의 파일이 디스크 상에 연속적으로 저장되는 방식을 뜻하며 이는 외부 단편화에 취약한 구조이다.

 

이를 FAT file system으로 변환하면, FAT에 파일 위치 정보를 저장하고 이를 메모리에 올림으로써 문제를 해결한다. 일종의 indexed allocation 방식인데, 인덱스 할당에서는 인덱스 블록이라고 하는 하나의 디스크 블록에 파일 내 각 블록의 위치를 저장해두는 방식으로 구현했다. 이를 FAT에 저장해두고 부팅 시 바로 메모리에 올리면 훨씬 빠른 접근과 동시에 직접 접근 문제와 hole 문제를 모두 해결 가능하다. 아래 이미지처럼 디스크의 섹터(정확히는 클러스터에 해당)와 FAT 테이블의 인덱스가 매핑되어있다고 생각하면 된다.

 

FAT의 index: Disk 내 sector의 index

FAT의 value:

• 해당 섹터가 비어있으면: 0 (ex - idx 14번: 0)
• 해당 섹터에 파일이 차 있다면(ex - File A)
  • 해당 섹터가 파일의 끝이라면: -1 (8번 인덱스: 파일의 끝이므로 -1)
  • 해당 섹터가 끝이 아니면: 파일이 저장되는 다음 섹터 번호가 들어있음(5, 6, 7번 인덱스: 각각 다음 섹터가 6, 7, 8번에 해당)

 

 

 

FAT 테이블과 별개로, 테이블 내 각 인덱스에 클러스터가 매핑되어있는지를 체크하기 위해 본 과제에서는 비트맵 테이블을 하나 더 만들어준다. 비트맵 사이즈는 FAT 테이블과 동일하며, FAT에 value가 들어있으면 1, 없으면 0을 매핑해준다.

 

 

참고: 클러스터와 섹터 개념

https://gusdnd852.tistory.com/89

 

1. 과제 구현 (FAT Table)

 

Make.vars 수정

 

먼저 Make.vars를 수정해준다. 아래처럼 #을 제거한다.

# -*- makefile -*-

os.dsk: DEFINES = -DUSERPROG -DFILESYS -DEFILESYS
KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys
KERNEL_SUBDIRS += tests/threads tests/threads/mlfqs
TEST_SUBDIRS = tests/threads tests/userprog tests/filesys/base tests/filesys/extended tests/filesys/mount
GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm

# Uncomment the lines below to enable VM.
os.dsk: DEFINES += -DVM
KERNEL_SUBDIRS += vm
TEST_SUBDIRS += tests/vm tests/filesys/buffer-cache
GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm

 

본격적으로 구현하기 전에, fat.c 파일에 들어있는 구조체를 살펴본다.

 

struct fat_fs: FAT 파일 시스템 정보를 담고 있는 구조체이다. FAT의 메타데이터를 담고 있는데 하나하나 보면

• fat_boot bs: 부팅 시 FAT 정보를 담는 구조체이다.
• unsigned int * fat: FAT  

/* 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;
};

 

/* 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_init(): FAT 테이블 초기화하는 함수

 

FAT 비트맵을 생성하기 위해 bitmap_create()를 추가한다. 

/* FAT 테이블 초기화하는 함수 */
void
fat_init (void) {
	// FAT 담을 공간을 힙에 할당 -> 구조체 자체는 위에 선언해둠.
	fat_fs = calloc (1, sizeof (struct fat_fs));
	if (fat_fs == NULL)
		PANIC ("FAT init failed");

	// Read boot sector from the disk: 디스크에서 FAT 읽어서 calloc담은 공간에 저장
	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 ();

	/* Project 4-1: FAT */
	fat_bitmap = bitmap_create(fat_fs->fat_length); // 
}

 

 

 

fat_fs_init() 구현

 

Gitbook 내용을 보면 fat_length, data_start를 초기화하라고 나와있다. 이때, fat_fs->bs 필드값을 이용하라고 나와있는데, fat_length는 파일 시스템에 얼마나 클러스터가 많은지 그 개수를 저장하는 멤버이므로 전체 섹터 수 * 섹터당 클러스터 수로 값을 계산한다(바이트 크기가 아님을 주의). 이 fat_length를 이용해 fat_create()에서 length 길이만큼의 FAT 테이블을 만든다.

 

FAT 테이블의 시작 위치에서부터 fat 테이블 크기(fat_sector)를 더하면 fat 테이블 다음으로 오는 데이터 블록의 시작 위치에 도달한다. (아래 이미지에서 Data Area가 시작하는 지점) data_start는 이 데이터 블록이 시작하는 위치값을 저장한다.

 

 

void
fat_fs_init (void) {
	/* TODO: Your code goes here. */

	/*fat_length: 파일 시스템에 얼마나 클러스터가 많은 지를 저장*/
	fat_fs->fat_length = fat_fs->bs.total_sectors /SECTORS_PER_CLUSTER;
	/*data_start: 파일 저장 시작할 수 있는 섹터 위치 저장 => DATA Sector 시작 지점*/
	fat_fs->data_start = fat_fs->bs.fat_start + fat_fs->bs.fat_sectors;
	
}

 

 

 

 

 

get_empty_cluster()

 

FAT 비트맵에서 빈 클러스터를 가져오는 함수.

// 빈 클러스터를 가져온다.
cluster_t get_empty_cluster () {
	// fat_bitmap을 
	size_t clst = bitmap_scan_and_flip(fat_bitmap, 0, 1, false) + 1; // 인덱스는 0부터 시작하나 cluster는 1부터 시작
	if (clst == BITMAP_ERROR)
		return 0;
	else
		return (cluster_t) clst;
}

 

 

bitmap_scan_and_flip()

 

비트맵을 스캔해 해당 인덱스를 찾는다. 그 뒤,  value값을 !value로 바꾼다(flip). false였다면 true로, true였다면 false로 바꾼다.

/* Finds the first group of CNT consecutive bits in B at or after
   START that are all set to VALUE, flips them all to !VALU E,
   and returns the index of the first bit in the group.
   If there is no such group, returns BITMAP_ERROR.
   If CNT is zero, returns 0.
   Bits are set atomically, but testing bits is not atomic with
   setting them. */
size_t
bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value) {
	size_t idx = bitmap_scan (b, start, cnt, value);
	if (idx != BITMAP_ERROR)
		bitmap_set_multiple (b, idx, cnt, !value); // !value로 비트맵 세팅
	return idx;
}

 

이제 과제에서 구현하라고 하는 fat 관련 함수를 보자.

 

fat_create_chain()

 

위에서 구현한 get_empty_cluster로 비어있는 새 클러스터 번호를 FAT에서 받아온다.

cluster_t
fat_create_chain (cluster_t clst) {
	/* TODO: Your code goes here. */
	/* Project 4-1: FAT */
	cluster_t new_clst = get_empty_cluster(); // 빈 클러스터를 bitmap에서 가져온다.
	if (new_clst != 0) {
		fat_put(new_clst, EOChain);
		if (clst != 0) {
			fat_put(clst, new_clst);
		}
	}
	return new_clst;

 

 

fat_remove_chain()

 

FAT 테이블에서 해당 클러스터 번호에 해당하는 애를 지운다.

/* Remove the chain of clusters starting from CLST.
 * If PCLST is 0, assume CLST as the start of the chain. */
void
fat_remove_chain (cluster_t clst, cluster_t pclst) {
	/* TODO: Your code goes here. */
	/* Project 4-1: FAT */
	while (clst != EOChain) { // EOChain: End of cluster chain
		bitmap_set(fat_bitmap, clst-1, false);
		clst = fat_get(clst);
	}
	if (pclst != 0) {
		fat_put(pclst, EOChain);
	}
}

 

 

fat_put()

 

fat 테이블에서 인자로 받은 클러스터 번호에 인자값을 넣는다.

/* 
Update a value in the FAT table. 
fat 테이블에 해당 인덱스 값을 업데이트
*/
void
fat_put (cluster_t clst, cluster_t val) {
	/* TODO: Your code goes here. */
	ASSERT(clst >= 1);
	if(!bitmap_test(fat_bitmap, clst-1)) { // 클러스터 값은 1부터 시작. 해당 인덱스가 fat_bitmap에 들어있는지 체크.
		bitmap_mark(fat_bitmap, clst-1); // 인덱스가 없다면 비트맵에서 해당 인덱스에 true로 변경
	}
	fat_fs->fat[clst-1] = val-1; // fat
}

 

 

fat_get()

 

fat 테이블에서 인덱스 값을 가져온다. 

/* Fetch a value in the FAT table. */
cluster_t
fat_get (cluster_t clst) {
	/* TODO: Your code goes here. */
	ASSERT(clst >=1);
	/* 만약 클러스터 번호가 fat_length를 넘어가거나 fat 테이블에 들어있지 않다면 */
	if (clst > fat_fs->fat_length || !bitmap_test(fat_bitmap, clst-1))
		return 0;
	/* fat 테이블에서 해당 인덱스에 들어있는 값을 반환*/
	return fat_fs->fat[clst-1];
}

 

 

/* Covert a cluster # to a sector number. */
disk_sector_t
cluster_to_sector (cluster_t clst) {
	/* TODO: Your code goes here. */
	ASSERT(clst >= 1);

	return fat_fs->data_start + (clst-1) * SECTORS_PER_CLUSTER; // 데이터 시작 위치부터 클러스터당 섹터 수 * 인자로 받은 클러스터 번호를 곱한다.
}

 

 

여기까지 구현했을 때 첫번째 과제인 alarm 파트는 모두 통과하는 것을 확인할 수 있다.