project4_Indexed and Extensible files

이전의 핀토스 파일 시스템은 데이터를 이어진 형태의 연속 할당으로 할당해 디스크 전체에는 빈공간이 file size만큼 남아있더라도 할당받못하는 외부단편화가 발생하기 쉽다. 프로젝트 4에서는 on-disk inode structrue를 수정하여 위 문제를 해결한다.

 

Indexing large files with FAT (File Allocation Table)

위에서 말한대로 이전 프로젝트에서는 파일시스템이 연속할당의 방식으로 데이터를 할당해 여러개의 disk sector에 걸쳐서 이어진 형태로 공간에 저장되어있었다 이를 cluster로 부른다면 클러스터는 한개 혹은 다수의 dis sector를 가질 수 있다. 기존 핀토스 파일시스템에서는 cluster 사이즈를 cluster 안에 저장된 파일의 크기와 같다고 할 수 있다.

 

우리는 기존 파일시스템의 문제인 외부 단편화 현상을 줄여야 한다. 그러기 위해 우선 클러스터 크기를 줄일 수 있다. 이는 skeleton 코드에서 cluster의 sector 를 1로 함으로 써 간단히 해결 가능하다.

 

크기가 작아진 cluster를 사용시 한개의 클러스터는 파일 전체를 담기에 충분하지 않을 수 있다 따라서 multiple cluster가 필요하고 이 클러스터들을 추적할 data structure를 linked-list를 이용하여 구현하고 이를 inode에 담아 주어야 한다. 

 

inode에는 파일의 첫 블럭의 섹터 갯수를 저장하고 첫 block 은 다음 block의 sector를 저장하는 방법을 쓸 수 있지만 이렇게 하면 마니막 block을 읽고 싶은 경우에도 전체 block을 읽어야 하는 부담이 있다.

이 때문에 FAT 시스템은 고정된 크기의 FAT에 데이터가 아닌 블럭들의 connectivity 값만을 넣어 DRAM의 캐쉬에 들어갈 만큼 크기가 작아진다. 따라서 table안의 entry만 읽어 접근이 가능해진다.

 

fat_fs_init

FAT파일 시스템을 초기화하는 함수이다. fat_length와 fat_fs의 data_start filed를 초기화 해야하며 fat_length에는 filesystem안에 얼마나 많은 클러스터들이 있는지에 대한 정보가담겨있다.

data_start는 파일을 보관할 수 있는 첫 sector의 정보가 담겨있다.

sector_to_cluster는 디스크 섹터값을 클러스터 값으로 변환해 주는 함수이다

/* fat.c */

void
fat_fs_init (void) {
	/* TODO: Your code goes here. */
	ASSERT(SECTORS_PER_CLUSTER == 1);

	fat_fs ->data_start = fat_fs->bs.fat_start + fat_fs->bs.fat_sectors;
	fat_fs->fat_length = sector_to_cluster(disk_size(filesys_disk)) - 1;
}

cluster_t 
sector_to_cluster (disk_sector_t sector) {
	ASSERT(sector >= fat_fs->data_start);

	// sector 158 -> clst 1
	return sector - fat_fs->data_start + 1;
}

fat_create_chain

클러스터를 나타내는 index number를 인자(clst)로 받아 다음 빈 클러스터를 추가함으로써 체인을 늘린다. 만약 clst 가 0인경우 chain을 새로 만들고 새로 할당한 클러스터에 cluster number를 반환한다. 

/* fat.c */

cluster_t
fat_create_chain (cluster_t clst) {
	/* TODO: Your code goes here. */
	cluster_t new_clst = get_empty_cluster();
	if(new_clst != 0){
		fat_put(new_clst,EOChain);
		if(clst != 0){
			fat_put(clst,new_clst);
		}
	}
	return new_clst;
}

cluster_t get_empty_cluster(){
	size_t clst = bitmap_scan_and_flip(fat_bitmap,0,1,false) + 1;

	if(clst == BITMAP_ERROR)
		return 0;
	else
		return (cluster_t) clst;
}

클러스터는 현재 비트맵으로 관리되고 있다. get_empty_cluster를 통해 우선 비어있는 클러스터를 받아 fat에 추가하고 bitmap_scan_and_flip을 통해 연속된 사이즈만큼 할당 안된 비트를 찾아 값을 flip시키고 인덱스  번호를 반환한다.

 

fat_remove_chain

주어진 인자 clst부터 cluster들을 chain에서 삭제하고 plcst는 clst의 직전 clst가 되어야 하는데 이 말은 이 함수가 실행되면 pclst는 새로 갱신된 chain의 마지막 elem이 된다는 뜻이다.

만약 clst가 chin의 첫번째 elem  이었다면 pclst는 0이다.

void
fat_remove_chain (cluster_t clst, cluster_t pclst) {
	/* TODO: Your code goes here. */
	while(clst && clst != EOChain){
		bitmap_set(fat_bitmap, clst -1, false);
		clst = fat_get(clst);
	}
    //while 문을 돌며 비트맵의 해당 비트를 false로 설정해준다.
	if(pclst != 0){
		fat_put(pclst, EOChain);
	}
}

fat_put

clst가 가리키는 FAT enrty를 val로 갱신한다. 

FAT entry는 chain 안의 다음 cluster를 가리키기 때문에 주어진 clst 넘저가 담긴곳은 fat[clst-1]이다.

void
fat_put (cluster_t clst, cluster_t val) {
	/* TODO: Your code goes here. */
	ASSERT(clst >= 1);
	if(!bitmap_test(fat_bitmap,clst-1)){
		bitmap_mark(fat_bitmap,clst -1);
	}
	fat_fs->fat[clst -1] = val;
}
fat_put

fat_get

clst가 가르키는 cluster number를 반환해준다.

 

cluster_t
fat_get (cluster_t clst) {
	/* TODO: Your code goes here. */
	ASSERT(clst >= 1);

	if(clst > fat_fs->fat_length || !bitmap_test(fat_bitmap,clst-1)){
		return 0;
	}
	return fat_fs->fat[clst-1];
}

cluster_to_sector

clst를 sector number로 바꾸고 이를 반환한다.

disk_sector_t
cluster_to_sector (cluster_t clst) {
	/* TODO: Your code goes here. */
	ASSERT(clst >=1);

	// clst 1 -> sector 158 (fat_fs->data_start)
	return fat_fs->data_start + (clst - 1) * SECTORS_PER_CLUSTER;
}

File Growth

extensibnle files를 실행한다. 기존 file system에서 파일의 크기는 file이 만들어 질때 결정되었다. 하지만 대부분의  files system에서는 파일은 만들어 질떄 크기가 0이고 EOF로 write가 끝날 때마다 갱신이 되는 방식이다 . 이것을 구현해보자.

 

file system 의 사이즈를 초과하는 file크기가 아니라면, file의 크기에 제한을 두면 안된다.  이건 root directory file에도 적용되며 이 directory file갯수 제한이었던 16은 해제된다.

 

user program이 현 EOF를 넘어서 검색할 수 있도록 해야한다. 이 검색은 file을 확장하지 않고 기존 EOF를 넘어가는 위치에서의 쓰기 작업은 EOF를 쓰기 작업이 끝난 위치로 옮긴다.

기존 EOF와 쓰기의 시작 지점 사이 공간은 0으로 채우고 이전 EOF위치에서부터 시작된 읽기 작업은 byte를 반환하지 않는다.

 

EOF를 넘어선 쓰기 작업은 0으로 채워진 많은 block을 야기한다. 일부 파일 시스템은 0만 있는 블록에 메모리를 할당, 쓰기 작업을 수행하지만 이 블럭에 쓰기 작업이 수행될 때까지 공간을 할당하지 않는 파일 시스템도 있다.