이 글은 핀토스 파일 시스템에 관한 글입니다.

• Why FAT?
  * Data Structure
  • File indexing
  • Bitmap
• Subdirectories
  • 계층구조
  • cd, mkdir 실제 구현

---

FAT (file allocation table)

핀토스 FAT 파일 시스템 구현

• 기존 핀토스는 파일을 생성하면 크기를 수정할 수 없었으나 (연속적인 디스크 할당)
• FAT는 비연속적으로 파일 조각들을 저장할 수 있어 파일 크기를 동적으로 증가 가능

FAT 히스토리

• MS-DOS 및 Windows 9x 운영 체제의 기본 파일 시스템. 디스크 용량이 증가함에 따라 FAT12, FAT16, FAT32로 변형 (each FAT entry is 12/16/32 bits in length).
• Windows XP부터는 Microsoft 운영체제 기본 파일시스템이 FAT에서 NTFS로 대체되었지만, FAT는 호환성과 구현 용이성으로 인해 SSD 및 많은 휴대용 임베디드 장치에서 계속 사용 중.

FAT spec 변화

• FAT가 12, 16, 32 bit 시스템으로 진화한 이유는 인덱스 값의 한계 때문.
• 각 bit가 다음 클러스터를 나타내려면 인덱스를 봐야하는데, CD시절 이후 사이즈가 만배 이상 커진만큼 기존 비트 수로는 표현의 한계가 있음.

클러스터 사이즈와 내부단편화

• FAT가 관리할 수 있는 클러스터 개수에 제한이 있는데- 파일은 커지다보니
  2000년대 중반 클러스터 사이즈를 키운 적.
• 그러나 클러스터 하나가 몇백KB까지 커지면 내부단편화가 심화됨. 몇글자만 써도 그 파일이 차지하는 사이즈는 몇백KB가 되어버리는 것.

왜 블록으로 나누는가?

파일시스템은 데이터를 일정 크기 블록으로 나누어 저장.
가장 큰 이유 중 하나는 외부단편화 방지.
외부단편화란 디스크에 남는 작은 공간들이 연속적으로 나열되지 않고 분산되어 발생하는 현상.
파일시스템은 공간을 할당하고 해제하는 작업(freemap)이 반복되면서 외부 단편화가 발생할 수.
블록 단위로 할당하면 비어있는 만큼을 다 활용함으로써 외부단편화를 줄일 수.

그러나 byte 단위로 나누지 않고 블록 단위로 나누는 이유는 '관리해야 할 개수' 문제 때문. 바이트 단위로 할당하면 매우 작은 크기의, 수많은 공간을 따로 추적하고 관리해야 하므로 블록 단위로 나누는 것이 효율적.

클러스터와 FAT

클러스터(cluster)는 파일시스템에서 데이터를 저장하는 최소 단위.
클러스터는 여러개의 섹터로 구성되는데, 클러스터 개념 없이 디스크의 한 조각을 섹터(512Byte) 단위로 매핑하여 저장하면 너무 잘게 쪼개게 되어 FAT 테이블 크기가 너무 커짐. 따라서 파일을 찾을 때나 추적할 때 속도나 용이성을 고려해 클러스터 사용

FAT Data Structure

1. 연결 리스트
2. 비트맵

연결리스트

FAT는 연속된 클러스터의 'Linked list'로 작동. 클러스터 넘버로서 데이터 영역을 정의하며, 비연속적인 데이터 공간도 {entry : value}가 {cluster number : next cluster}로서 다음 파일조각을 찾아갈 수 있음.

비트맵

disk usage 트래킹

• 핀토스 파일시스템은 8MB
• 디스크 섹터사이즈가 512byte 이므로 파일시스템을 구성하는 전체 블록 개수는 16,384개
• FAT는 4개의 디스크 섹터를 차지하는 비트맵으로,
  4 x 512 x 8bit = 16,384 bit
• 즉 FAT의 each bit는 파일시스템내 모든 disk sector의 사용여부를 추적할 수 있음
• 핀토스에서 FAT block bitmap 또한 'file'로 나타냄

FAT 비트맵의 value는 기본적으로 next cluster number 나타내지만, 0 또는 -1은 각각 empty, EOF라는 특별한 의미를 지님

• 0x000: 클러스터가 비어있음
• 0x002~MAX: 클러스터가 할당되었음
• 0xFFF: 할당되었으나 end-of-file(EOF)를 나타냄

Microsoft 사의 FAT spec 공식문서를 참조하면 다음과 같음.

 

WHY FAT ?

• 컴퓨터가 디스크에 파일을 저장할 때 파일들이 실제로는 쭉 연결되어서 저장되는 것이 아니라 여기저기 쪼개져서 저장됨
• 사용자가 파일 접근을 시도하면 쪼개진 각각의 조각들이 어디에 저장되어있는지 알아야
• 쪼개진 조각들의 위치를 저장하고 있는 자료구조가 'FAT(File Allocation Table)'
• 아래 그림과 같이 directory entry 구조체 내 파일명과 cluster number로 디스크 섹터를 찾아가면 인덱싱으로 전체 파일을 구성할 수 있음.

Directory entry, Cluster, FAT 관계

byte_to_sector()

파일내 오프셋을 디스크 섹터 넘버로 변환.
원래 파일은 { start, length }만 알면 온전히 읽어들일 수 있으나
이번 과제는 비연속적인 파일 저장을 감안해야 하므로
오프셋(pos)을 DIS_SECTOR_SIZE로 나눈 디스크 개수만큼
FAT를 인덱싱으로 다음 클러스터를 찾아가며 전체 파일크기를 구성해야 함.

byte_to_sector()

static disk_sector_t
byte_to_sector (const struct inode *inode, off_t pos) {
	ASSERT (inode != NULL);
	if (pos < inode->data.length) {
		#ifdef EFILESYS
        	/* 실제 디스크내 data가 시작되는 sector를 clst로 */
			cluster_t clst = sector_to_cluster(inode->data.start);	
			for (unsigned i = 0; i < (pos / DISK_SECTOR_SIZE); i++) {
				clst = fat_get(clst); 		    // next clst로 이동
				if (clst == 0) return -1;		// end of chain
			}
			return cluster_to_sector(clst);
		#else
			return inode->data.start + pos / DISK_SECTOR_SIZE;
		#endif
	}
	else
		return -1;
}

fat_get()

cluster_t
fat_get (cluster_t clst) {
	return fat_fs->fat[clst - 1];
}

 

FAT create chain

FAT 파일시스템에 클러스터를 추가하는 함수

• 비트맵 스캔으로 빈 클러스터를 찾아 new_clst로 지정
  • 파라미터 clst가 0이면 바로 new_clst를 리턴해 해당 지점부터 inode->data가 시작될 수 있도록 함
  • clst가 0이 아니면 빈 슬롯 앞 칸의 value에 new_clst를 넣음으로써 체인을 한 칸 늘림
    

fat_create_chain()

cluster_t
fat_create_chain (cluster_t clst) 
{
	cluster_t new_clst = get_empty_cluster();
	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;	// type casting
}

 

Write data to disk using FAT

inode_write_at()

FAT 파일시스템에 데이터를 쓸 때 고려해야 할 두 가지 사항

1. File Growth

• 기존 파일 사이즈를 넘어서면 마지막 클러스터 기준으로 FAT chain 확장

2. Zero Padding

• 유저 프로그램은 현재 EOF(파일 끝)을 넘어 탐색(seek)할 수 있는데,
  EOF를 넘어선 위치에서 쓰면 해당 위치로 파일이 확장되며,
  이전 EOF와 쓰고있는 위치 사이 간격을 0으로 채워야 함
• 그 이유는 malloc으로 메모리 블록을 할당받았을 때, 그 안에 뭐가 들어있을 지 알 수 없기 때문.
  데이터가 꼭 랜덤이라는 법도 없고, OS의 중요한 정보 또는 다른 프로세스 정보가 들어가있을 수도 있음.
• 그게 파일로 그대로 저장이 되면 절대 안되므로, 빈 공간도 꽉꽉 채워서 저장하는 게 맞음

Zero Padding 로직 흐름
1. memset(0, 0, DISK_SECTOR_SIZE): 제로 버퍼를 0으로 초기화
2. endclst: 파일을 확장하는 과정에서 파일의 마지막 클러스터를 식별
3. 마지막 클러스터가 0으로 완전히 채워지지 않은 경우, 클러스터를 zero 버퍼로 읽고 나머지 부분을 0으로 덮어쓴 다음 디스크에 다시 씀

여기서 실제 디스트에 쓰는 disk_write()은 네 번 등장
1. 디스크에 쓸 chunck_size가 섹터 크기(512 byte)로 나눠떨어질 때 섹터를 온전히 채워 저장하는 부분
2. 맞아떨어지지 않을 때 섹터내 오프셋을 쓰는 부분
3. 제로 패딩을 써주는 부분
4. 늘어난 파일 크기를 디스크에 반영해주는 부분

/* 4번 - File growth */
if (inode_length(inode) < origin_offset + bytes_written) {
	inode->data.length = origin_offset + bytes_written;
	disk_write(filesys_disk, inode->sector, &inode->data);
}

inode_write_at()

off_t
inode_write_at (struct inode *inode, const void *buffer_, off_t size, off_t offset) {
	const uint8_t *buffer = buffer_;
	off_t bytes_written = 0;
	off_t origin_offset = offset;
	uint8_t zero[DISK_SECTOR_SIZE];  // buffer for zero padding

	while (size > 0) {
		/* Sector to write, starting byte offset within sector. */
		disk_sector_t sector_idx = byte_to_sector (inode, offset);
		int sector_ofs = offset % DISK_SECTOR_SIZE;		
		/* 생략 */

		/* Write full sector directly to disk. */
		disk_write (filesys_disk, sector_idx, buffer + bytes_written); 
		/* Advance. */
		size -= chunk_size;
		offset += chunk_size;
		bytes_written += chunk_size;
	}
	/* File growth */
	if (inode_length(inode) < origin_offset + bytes_written) 
	{
		off_t inode_len = inode_length (inode);
		cluster_t endclst = sector_to_cluster (byte_to_sector(inode, inode_len -1));
		cluster_t newclst = inode_len == 0? endclst : fat_create_chain (endclst);

		/* Zero-padding */
		memset (zero, 0, DISK_SECTOR_SIZE);
		disk_write(filesys_disk, cluster_to_sector(newclst), zero);

		off_t inode_ofs = inode_len % DISK_SECTOR_SIZE;						// zero padding offset
		if (inode_ofs != 0) {
			inode->data.length += DISK_SECTOR_SIZE - inode_ofs;				// update length
			disk_read (filesys_disk, cluster_to_sector(endclst), zero); 	// read from zero
			memset (zero + inode_ofs + 1, 0, DISK_SECTOR_SIZE - inode_ofs);
			disk_write (filesys_disk, cluster_to_sector(endclst), zero);    // write zero 
		}
		disk_write(filesys_disk, inode->sector, &inode->data);				// save updated inode->data to disk
	}
	return bytes_written;
}

 

 

Subdirectories

핀토스 구현 과제

루트 디렉토리가 모든 파일을 소유하던 구조를,
루트 산하 여러 폴더가 계층구조를 이룰 수 있게 함.

 

폴더를 만든다는 것

• 컴퓨터 입장에선 파일과 폴더 모두 '파일'임.
  • 그것을 구분할 수 있는 방법은 flag 뿐.
  • inode_disk 구조체에 is_dir 플래그를 추가하는 것만으로도 서브디렉토리 구조를 수용할 수 있도록 변경하는 셈
• 파일 생성 시 우리가 해야 할 것은, root 대신 올바른 디렉토리를 찾아 그 경로에(on the path)에 파일을 생성하는 것.
  

 

inode_create()

• 파일 또는 폴더 생성시 해당 file에 대한 inode를 생성하는 함수
  • 파일을 만들든 폴더를 만들든 그 메타데이터를 보유할 inode는 반드시 생성해야 함
• is_dir 플래그에 유의. 파일이면 0, 폴더면 1.
  • regular file: filesys_create() -> inode_create(), is_dir = 0
  • directory: dir_create() -> inode_create(), is_dir = 1
• inode를 만들 때 FAT 비트맵 공간을 확보하는 fat_create_chain()은 두 번 등장
  1. start_clst = fat_create_chain(0)
     클러스터 체인 첫 시작 지점 설정. 여기서부터 체인 이어갈 것
  2. target = fat_create_chain(target)
     현재 쓰고 있는 클러스터 넘버(target)를 넘겨 이전 체인을 계속 이어 확장하게 함

inode_create()

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

	ASSERT (length >= 0);
	ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);
	
	/* create disk_node and initialize*/
	disk_inode = calloc (1, sizeof *disk_inode);	// inode_disk 구조체에 대한 메모리 할당 (on-disk inode)
	if (disk_inode != NULL) {  						// 할당 성공시 disk_inode 구조 초기화
		size_t sectors = bytes_to_sectors (length);
		disk_inode->length = length;
		disk_inode->is_dir = is_dir;		
		disk_inode->magic = INODE_MAGIC;

		/* data cluster allocation */
		if (start_clst = fat_create_chain(0)) {		// inode에 대한 데이터 클러스터 할당
			disk_inode->start = cluster_to_sector(start_clst); 	// 중요* 새 클러스터 chian의 시작 주소를 섹터로 변환, 거기서부터 inode->data가 시작되도록 함
			/* write disk_inode on disk */
			disk_write(filesys_disk, sector, disk_inode);	// inode_disk를 디스크에 write. 지정된 sector에 inode_disk 내용을 씀.

			if (sectors > 0) {		// inode length가 0보다 크면 
				static char zeros[DISK_SECTOR_SIZE];
				cluster_t target = start_clst;
				disk_sector_t w_sector;
				size_t i;

				/* make cluster chain based length and initialize zero */
				while (sectors > 1) {
					w_sector = cluster_to_sector(target);
					disk_write(filesys_disk, w_sector, zeros);

					target = fat_create_chain(target);
					sectors--;
				}
			}
			success = true;
		}
		free (disk_inode);		// FAT 빈공간이 없으면 해제
	}
	return success;
}

 
파일 생성시 inode_create(), dir_add()가 호출되는 맥락은 다음과 같음

filesys_create()

bool filesys_create (const char *name, off_t initial_size) 
{
	disk_sector_t inode_sector = 0; 
	struct dir *dir = dir_open_root (); 
	bool success = (dir != NULL
			&& free_map_allocate (1, &inode_sector) 
			&& inode_create (inode_sector, initial_size, 0) 
			&& dir_add (dir, name, inode_sector)); 
	if (!success && inode_sector != 0)
		free_map_release (inode_sector, 1);
	dir_close (dir); 

	return success;
}

 

dir_add()

디렉토리 배열의 빈 슬롯을 찾아 해당 오프셋에 inode data를 저장하는 함수.

dir_add()

bool
dir_add (struct dir *dir, const char *name, disk_sector_t inode_sector) {
	struct dir_entry e;
	off_t ofs;
	bool success = false;

	ASSERT (dir != NULL);		// 해당 디렉토리 및 이름이 이미 존재하지 않음
	ASSERT (name != NULL);

	/* Check NAME for validity. */  
	if (*name == '\0' || strlen (name) > NAME_MAX)
		return false;

	/* Check that NAME is not in use. */
	if (lookup (dir, name, NULL, NULL))
		goto done;

	/* Set OFS to offset of free slot.*/
	for (ofs = 0; inode_read_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
			ofs += sizeof e)
		if (!e.in_use)
			break;

	/* Write slot. */
	e.in_use = true;
	strlcpy (e.name, name, sizeof e.name);
	e.inode_sector = inode_sector;
	success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e;

done:
	return success;
}