[PintOS] Project4: Indexed and Extensible Files

Indexed and Extensible Files

현재의 PintOS file system 구조

• 하나의 파일이 디스크 상에 연속적으로 저장되는 방식
• 단점
  • 외부 단편화 발생
  • 파일 확장이 어려움
• 장점
  • 디스크 헤더의 이동 최소화
  • 순서적으로 읽을 수도 있고(순차접근) 특정 부분을 바로 읽을 수 있음(직접접근)

FAT (File Allocation Table)

• FAT은 빈 Sector들을 찾아 데이터를 기록한 뒤, 파일들이 연결된 정보를 File Allocation Table(FAT)에 기록해 놓는 방식

• FAT 방식은 File Allocation Table이라는 표를 만들어서, 파일이 기록된 섹터들의 정보를 Chain 형태로 저장

fat.c 구현

void fat_fs_init(void) {
    /* TODO: Your code goes here. */
    fat_fs->fat_length = disk_size(filesys_disk) - fat_fs->bs.fat_sectors - 1;
    fat_fs->data_start = (disk_sector_t)(fat_fs->bs.fat_start + fat_fs->bs.fat_sectors);
}

• 해당 FAT 테이블의 데이터 영역 시작 섹터를 알려주고 FAT 테이블의 총 인덱스 길이를 정함으로써 FAT 테이블을 만들 수 있는 발판을 마련

• fat_length : FAT 테이블의 인덱스 개수 = 파일 시스템 내 데이터 영역의 클러스터의 개수

• data_start : 파일 시스템 내에서 데이터 블록 영역의 시작 클러스터 번호
  
  
  

struct bitmap* fat_bitmap;

• FAT 테이블의 각 클러스터가 할당되었는지 여부를 관리하는 fat_bitmap 비트맵을 만들어준다.
  
  
  

cluster_t get_empty_cluster(void){
	size_t clst = bitmap_scan_and_flip(fat_bitmap, 0, 1, false);
	
	if (clst == BITMAP_ERROR)
		return 0;  // 실패
	
	return (cluster_t) clst;
}

• fat_bitmap에서 칸 하나가 false인 인덱스를 true로 바꿔주고 인덱스를 리턴한다. 비트맵 맨 처음부터 찾아나간다.
  
  
  

cluster_t fat_get (cluster_t clst) {
	ASSERT(clst >= 1);

	if(clst > fat_fs->fat_length || !bitmap_test(fat_bitmap, clst-1))
		return 0;

	return fat_fs->fat[clst - 1];
}

• 클러스터 번호 clst에 해당하는 FAT 테이블 값을 리턴한다. 즉, 클러스터 체인에서 clst 다음 클러스터의 번호를 리턴한다.

• fat_fs->fat[clst - 1] 클러스터 번호는 1부터 시작하지만 FAT 인덱스는 0부터 시작한다.
  
  
  

void fat_put (cluster_t clst, cluster_t val) {
	ASSERT(clst >= 1);

	if (!bitmap_test(fat_bitmap, clst - 1))
		bitmap_mark(fat_bitmap, clst - 1);

	fat_fs->fat[clst - 1] = val; 
}

• FAT테이블의 각 인덱스(클러스터 번호)에 다음 클러스터 번호를 넣는다.
  
  
  

cluster_t fat_create_chain (cluster_t clst) {
	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;  
}

• 해당 클러스터가 파일의 마지막 클러스터이면 FAT 테이블의 값에 EOChain(0x0FFFFFF)을 넣어 클러스터 체인이 끝난다는 것을 알려준다.

• 만약 대상 클러스터 clst가 0이라면 현재 FAT 상에 저장된 클러스터가 하나도 없다는 뜻이므로 새로 생성된 클러스터 new_clst를 시작으로 하는 클러스터 체인을 만든다.
  
  
  

void fat_remove_chain (cluster_t clst, cluster_t pclst) {
	while(clst && clst != EOChain) {
		bitmap_set(fat_bitmap, clst - 1, false);
		clst = fat_get(clst); 
	}

	if (pclst != 0){ 
		fat_put(pclst, EOChain);
	}
}

• clst에서부터 시작해서 클러스터들을 클러스터 체인에서 지운다.

• clst : 제거될 클러스터의 번호.

• pclst : clst의 바로 앞 클러스터를 나타낸다. 즉, 이 함수가 다 끝나면 업데이트 된 클러스터 체인의 맨 마지막 클러스터가 pclst가 된다.
  
  
  

disk_sector_t cluster_to_sector (cluster_t clst) {
	ASSERT(clst >= 1);

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

• 클러스터 인덱스 번호를 섹터 번호로 치환해준다. 즉, N번 클러스터가 디스크 상의 몇 번째 섹터인지를 계산해준다.
  
  
  

inode.c 구현

bool inode_create (disk_sector_t sector, off_t length, bool isdir) {
	struct inode_disk *disk_inode = NULL;
	bool success = false;

	ASSERT (length >= 0);

	/* If this assertion fails, the inode structure is not exactly
	 * one sector in size, and you should fix that. */
	ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);

	disk_inode = calloc (1, sizeof *disk_inode);
	if (disk_inode != NULL) {
		size_t sectors = bytes_to_sectors (length);  
		disk_inode->length = length;
		disk_inode->magic = INODE_MAGIC;
        
		disk_inode->isdir = isdir;
		#ifdef EFILESYS
		cluster_t clst = sector_to_cluster(sector); 
		cluster_t new_clst = clst;

		if (sectors == 0)
			disk_inode->start = cluster_to_sector(fat_create_chain(new_clst));

		int i;
		for (int i = 0; i < sectors; i++){
			new_clst = fat_create_chain(new_clst);
			if (new_clst == 0){  
				fat_remove_chain(clst, 0);
				free(disk_inode);
				return false;
			}
			if (i == 0){
				clst = new_clst;
				disk_inode->start = cluster_to_sector(new_clst);
			}
		}

		disk_write(filesys_disk, sector, disk_inode);
		if (sectors > 0){
			static char zeros[DISK_SECTOR_SIZE];
			for(i = 0; i < sectors; i++){
				ASSERT(clst != 0 || clst != EOChain);
				disk_write(filesys_disk, cluster_to_sector(clst), zeros);
				clst = fat_get(clst);
			}
		}
		success = true;
		#else
		if (free_map_allocate (sectors, &disk_inode->start)) {
			disk_write (filesys_disk, sector, disk_inode);
			if (sectors > 0) {
				static char zeros[DISK_SECTOR_SIZE];
				size_t i;

				for (i = 0; i < sectors; i++) 
					disk_write (filesys_disk, disk_inode->start + i, zeros); 
			}
			success = true; 
		} 
		#endif
		free (disk_inode);
	}
	return success;
}

• 기존 핀토스에서는 아이노드들의 리스트를 비트맵 FREE MAP으로 관리하고 있었다. 이 free map은 디스크 내의 아이노드 영역의 클러스터의 할당 여부를 저장해 놓은 비트맵 자료구조이다. 게다가 FAT 테이블이나 클러스터 체인도 없었다.

• 해당 함수는 disk inode 구조체를 만들고 이 필드들을 초기화하며, FAT 테이블을 업데이트하고 이 disk inode에 대한 새로운 클러스터 체인을 만든다. 그 후 디스크에 해당 아이노드 구조체를 저장하고, 앞으로 파일의 내용이 들어갈 디스크 공간을 할당하고 0으로 초기화해준다.
  
  
  

void inode_close (struct inode *inode) {
	if (inode == NULL)
		return;

	if (--inode->open_cnt == 0) {    
		list_remove (&inode->elem);  

		if (inode->removed) {  
			#ifdef EFILESYS
			fat_remove_chain(sector_to_cluster(inode->sector), 0);
			#else
			free_map_release (inode->sector, 1);
			free_map_release (inode->data.start, bytes_to_sectors (inode->data.length)); 
		}

		free (inode); 
	}
}

• inode를 닫고 해당정보를 디스크에 써 준다.

• 만약 이 참조가 이 아이노드의 마지막 참조였다면 아이노드를 메모리에서 반환한다.

• 만약 이 아이노드가 지워진 파일에 대한 아이노드였다면 디스크 섹터 또한 반환한다.