[PintOS, Project 4] Indexed and Extensible Files

Indexed and Extensible Files

 The basic file system allocates files as a single extent, making it vulnerable to external fragmentation, that is, it is possible that an n-block file cannot be allocated even though n blocks are free (i.e. external fragmentation). Eliminate this problem by modifying the on-disk inode structure.

 현재의 file system은 single extent로 파일을 할당하기 때문에 (즉, 데이터가 이어진 형태의 연속 할당을 채택하고 있기 때문에) 디스크 전체에는 file size만큼의 공간이 남아있어도 할당받지 못해버리는 외부 단편화가 발생하기 쉽다. on-disk inode structure를 수정함으로서 이 문제를 해결한다.

 

 

 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.

 direct, indirect, doubly indirect block을 사용하는 index structure로 해결책을 만든다. 과거의학생들은 multi-level indexing을 활용한 UNIX FFS를 사용했지만, 학생들의 정신적 건강을 위해서 FAT을 사용하도록 해주겠다. 절대로 multi-level indexing을 사용해선 안된다. (사용하면 0점이다.)

 

 NOTE: You can assume that the file system partition will not be larger than 8 MB. You must support files as large as the partition (minus metadata). Each inode is stored in one disk sector, limiting the number of block pointers that it can contain.

 알아두기 : file system partition은 8 MB 이하다. file은 partition만큼의 크기 (빼기 metadata의 크기)로 다뤄야한다. 각 disk sector 안에 있는 각각의 inode는 가지고 있는 block의 수만큼 block pointer를 가져야한다. 

 

Indexing large files with FAT (File Allocation Table)

 Warning: this document assumes you have already understood the basic principle of general filesystem and FAT from the lecture. If not, please go back to the lecture note and understand what is filesystem and FAT.
 주의사항 : 이 문서는 당신이 FAT 과 일반적인 filesystem을 이해하고 있다는 것을 가정한다. 그렇지 않다면 깝죽거리지말고 공부부터 하고와라.

 In the basic filesystem that you have used for the previous projects, a file was stored as a contiguous single chunk over multiple disk sectors. Let's call contiguous chunk as cluster, since a cluster (chunk) can contain one or more contiguous disk sectors. In this point of view, the size of a cluster in the basic file system was equal to the size of a file that stored in the cluster.

 이전 프로젝트에서 사용한 기본 filesystem에서, 여러 개의 disk sector에 걸쳐서 이어진 형태로 공간에 저장되어 있었다. 이를 cluster라고 부르자. cluster는 한 개, 혹은 다수의 disk sector를 가질 수 있다. 이 관점에서 기존 file system의 한 cluster의 size는 cluster안에 저장되있는 file의 size와 같다고 할 수 있다.

 

 To mitigate external fragmentation, we can shrink the size of cluster (recall the page size in virtual memory). For simplicity, in our skeleton code, we fixed number of sectors in a cluster as 1. When we use smaller clusters like it, a cluster might not enough to store the entire file. In this case, we need multiple clusters for a file, so we need a data structure to index the clusters for a file in the inode. One of the easiest way is to use linked-list (a.k.a chain).

 외부 단편화를 줄이기 위해서, cluster의 크기를 줄일 수 있다 (VM에서 page size를 기억하라.). 간단하게 하기 위해서 Skeleton code에서 한 cluster의 sector 수를 1로 고정했다. 크기가 작아진 cluster를 사용할 때, 한 개의 cluster는 file 전체를 담기에는 충분하지 않을 지도 모른다. 그래서 우리는 multiple cluster가 필요하고, 따라서 file의 cluster의 위치를 추적할 data structure를 inode안에 넣어야한다. 가장 쉬운 방법 중 하나는 linked-list를 사용하는 것이다. 

 

 An inode can contain the sector number of the first block of the file, and the first block may contain the sector number of the second block. This naive approach, however, is too slow because we have to read every block of the file, even though what we really need was only the last block. To overcome this, FAT (File Allocation Table) puts the connectivity of blocks in a fixed-size File Allocation Table rather than the blocks themselves. Since FAT only contains the connectivity value rather than the actual data, its size is small enough to be cached in DRAM. As a result, we can just read corresponding entries in the table. You will implement inode indexing with the skeleton code provided in filesys/fat.c. This section briefly describes what already-implemented functions in fat.c do and what you should implement.

 inode에는 file의 첫 blcok의 sector의 갯수를 저장하고, 첫 block은 다음 block의 sector의 갯수를 저장하는 방법을 쓸 수도 있다. 하지만 이 방법을 쓴다면 마지막 block을 읽고 싶은 경우에도 전체 block을 읽어야하는 멍청한 방법이다. 이 때문에 FAT (File Allocation Table) 시스템은 고정된 크기의 FAT에 블록의 connectivity (연결 수단, 일종의 포인터?)를 놓는다. FAT는 실제 data보다는 연결 수단만을 담고있기 때문에, FAT는 DRAM에 들어갈 만큼 작아진다. 결과적으로, 우리는 table안의 entry만 읽으면 된다. filesys/fat.c에 제공된 skeleton code로 inode indexing을 수행하라. 하기는 fat.c에 만들어야 하는 함수를 간략하게 설명해놓았다.

 

 

First of all, 6 functions in fat.c (i.e. fat_init(), fat_open(), fat_close(), fat_create(), and fat_boot_create()) initialize and format disks at the boot time, so you don't have to modify them. However, you'll need to write fat_fs_init(), and briefly understanding what they do could be helpful.

 무엇보다, fat.c 안의  fat.c (i.e. fat_init(), fat_open(), fat_close(), fat_create(), fat_boot_create() 6개 함수들은 boot time 시에 disk와 format을 초기화하기 때문에 수정할 필요가 없다. 하지만 어떤 함수가 도움이 될 건지 이해할 필요가 있으며 fat_fs_init()은 작성해야한다. 

---

cluster_t fat_fs_init (void);

 Initialize FAT file system. You have to initialize fat_length and data_start field of fat_fs. fat_length stores how many clusters in the filesystem and data_start stores in which sector we can start to store files. You may want to exploit some values stored in fat_fs->bs. Also, you may want to initialize some other useful data in this function.
 FAT file system을 초기화한다. fat_length와 fat_fs의 data_start field를 초기화해야한다. fat_length에는 filesystem 안에 얼마나 많은 cluster들이 있는지의 정보가 담겨져있으며, data_start는 file을 보관할 수 있는 첫 sector의 정보(위치)가 담겨져있다. fat_fs->bs 에 있는 몇몇 정보를 활용할 수도 있다.

---

cluster_t fat_create_chain (cluster_t clst);

 Extend a chain by appending a cluster after the cluster specified in clst (cluster indexing number). If clst is equal to zero, then create a new chain. Return the cluster number of newly allocated cluster.
 인자clst (cluster를 나타내는 숫자) 에 다음 빈 cluster를 추가함으로서 chain을 늘릴 수 있다. 만약 clst가 0이라면, chain을 새로 만든다. 새로 할당한 cluster의 cluster number를 반환한다. 

---

void fat_remove_chain (cluster_t clst, cluster_t pclst);

 Starting from clst, remove clusters from a chain. pclst should be the direct previous cluster in the chain. This means, after the execution of this function, pclst should be the last element of the updated chain. If clst is the first element in the chain, pclst should be 0.
 clst부터 cluster들을 chain에서 뺀다. plcst는 반드시 clst의 직전 clst가 되어야한다. 이 말인 즉슨, 이 함수가 실행되고 나면, pclst는 새로이 갱신된 chain의 마지막 elem이 되어야한다는 것이다. 만약 clst가 chain의 첫번째 elem이라면 pclst는 0이 되어야한다.
 

---

void fat_put (cluster_t clst, cluster_t val);

 Update FAT entry pointed by cluster number clst to val. Since each entry in FAT points the next cluster in a chain (if exist; otherwise EOChain), this could be used to update connectivity.
 인자clst가 가리키는 FAT entry를 val로 갱신한다 (/* 즉, FAT[clst]가 val이 되도록 한다. */). FAT entry는 chain 안의 다음 cluster를 가리키기 때문에, 이 함수는 connectivity를 갱신하기위해 사용될 수 있다.

 

---

cluster_t fat_get (cluster_t clst);

Return in which cluster number the given cluster clst points.
 주어진 cluster clst가 가리키는 cluster number를 반환한다. 

---

disk_sector_t cluster_to_sector (cluster_t clst);

Translates a cluster number clst into the corresponding sector number and return the sector number.
 cluster number clst를 대응하는 sector number로 바꾸고, 이 sector number를 반환한다. 

---

You may wish to exploit these functions in filesys.c and inode.c to augment the basic file system.

 filesys.c와 inode.c에 있는 이 함수들을 기존 file system을 개선하는데 활용할 수 있다.

File Growth

 Implement extensible files. In the basic file system, the file size is specified when the file is created. In most modern file systems, however, a file is initially created with size 0 and is then expanded every time a write is made off the end of the file. Your file system must allow this.

 extensible files를 실행한다. 기존 file system에서 file의 크기는 file이 만들어질 때 명시되었다. 요즈음의 대부분 file system에서, file은 만들어질 때 크기가 0이 되고, EOF로 write가 끝날 때마다 갱신된다. 이것을 구현해야한다.

 

 There should be no predetermined limit on the size of a file, except that a file cannot exceed the size of the file system (minus metadata). This also applies to the root directory file, which should now be allowed to expand beyond its initial limit of 16 files.

 file system의 size를 초과하는 file 크기가 아니라면, file의 크기에 제한을 둬선 안된다. 이는 root directory file에도 적용되며, 이 directory의 file 갯수 제한 (16개) 은 해제된다. 

 

 

 User programs are allowed to seek beyond the current end-of-file (EOF). The seek itself does not extend the file. Writing at a position past EOF extends the file to the position being written, and any gap between the previous EOF and the start of the write must be filled with zeros. A read starting from a position past EOF returns no bytes.

 User Program이 현 EOF를 넘어서 검색할 수 있도록 한다. 이 검색은 file을 확장하지 않는다. 기존 EOF를 넘어가는 위치에서의 쓰기 작업은 EOF를 현 쓰기 작업이 끝난 위치로 옮긴다. 기존 EOF와 쓰기의 시작 지점 사이의 공간은 0으로 채워야한다. 이전 EOF 위치에서부터 시작된 읽기 작업은 no byte를 반환한다. 

 

 Writing far beyond EOF can cause many blocks to be entirely zero. Some file systems allocate and write real data blocks for these implicitly zeroed blocks. Other file systems do not allocate these blocks at all until they are explicitly written. The latter file systems are said to support "sparse files." You may adopt either allocation strategy in your file system.

 EOF를 넘어선 쓰기 작업은 (EOF와 쓰기 작업의 시작 위치 사이에) 0으로만 채워진 block을 만들 수 있다. 일부 file system은 이 0만 있는 block에 메모리를 할당하고 쓰기 작업을 수행하지만, 이 block에 쓰기 작업이 수행될 때 까지, 이 공간을 할당하지 않는 file system도 있다. 이러한 file system을 "sparse files"를 지원한다고 하며, 둘 중 아무거나 택해도 된다.