Pintos. File systems 구현하기

🌻구현 예정 리스트🌼
1. Indexed and Extensible Files
2. Subdirectories and Soft Links

---

0. 들어가기 전

코드를 진행하기에 앞서, 스켈레톤 코드들을 최대한 뜯어보면서 어떤 코드가 있는지 살펴보자!
1. filesys/fsutil.c : 커널 커맨드 라인에서 접근할 수 있는 파일시스템을 위한 간단한 유틸리티들이 있다.

/* List files in the root directory. */
void fsutil_ls() 

/* Prints the contents of file ARGV[1] to the system console as hex and ASCII. */
void fsutil_cat() 

/* Deletes file ARGV[1]. */
void fsutil_rm()

/* Copies from the "scratch" disk, hdc or hd1:0 to file ARGV[1] in the file system. */
void fsutil_put()

/* Copies file FILE_NAME from the file system to the scratch disk. */
void fsutil_get()

2. filesys/filesys.h, filesys/filesys.c : 파일 시스템에 대한 최상위 인터페이스가 있다. 파일 시스템 사용 방법을 볼 수 있습니다.

/* The disk that contains the file system. */
struct disk *filesys_disk;

/* Initializes the file system module. */
/* If FORMAT is true, reformats the file system. */
void filesys_init();

/* Shuts down the file system module, writing any unwritten data to disk */
void filesys_done();

/* Creates a file named NAME with the given INITIAL_SIZE. */
bool filesys_create();

/* Opens the file with the given NAME */
struct file *filesys_open();

/* Deletes the file named NAME */
bool filesys_remove();

/* Formats the file system */
static void do_format();

3. filesys/directory.h, filesys/directory.c : 파일 이름을 inode로 변환한다. 디렉토리 자료구조는 파일로서 저장된다.

/* A directory */
struct dir{
	strict inode *inode;
    off_t pos;
};

/* A single directory entry */
struct dir_entry{
	disk_sector_t inode_sector;
    char name[NAME_MAX + 1];
    bool in_use;
};

/* Creates a directory with space for ENTRY_CNT entries in the given SECTOR */
bool dir_create()

/* Opens and returns the directory for the given INODE, of which it takes ownership */
struct dir *dir_open()

/* Opens the root directory and returns a directory for it */
struct dir *dir_open_root()

/* Opens and returns a new directory for the same inode as DIR */
struct dir * dir_reopen()

/* Destroys DIR and frees associated resources */
void dir_close()

/* Returns the inode encapsulated(요약된) by DIR*/
struct inode *dir_get_inode()

/* Searches DIR for a file with the given NAME 
 * If successful, returns true, sets *EP to the directory entry
 * if EP is non-null, and sets *OFSP to the byte offset of the directory entry if OFSP is non-null.
 * otherwise, returns false and ignores EP and OFSP. */
static bool lookup()

/* Searches DIR for a file with the given NAME
 * and returns true if one exists, false otherwise.
 * On success, sets *INODE to an inode for the file, otherwise to
 * a null pointer.  The caller must close *INODE. */
 bool dir_lookup()
 
 /* Adds a file named NAME to DIR, which must not already contain a file by that name.  
 * The file's inode is in sector INODE_SECTOR.
 * Returns true if successful, false on failure.
 * Fails if NAME is invalid (i.e. too long) or a disk or memory error occurs. */
 bool dir_add()
 
 /* Removes any entry for NAME in DIR. */
 bool dir_remove()
 
 /* Reads the next directory entry in DIR and stores the name in NAME. */
 bool dir_readdir()

4. filesys/fat.h, filesys/fat.c : FAT파일시스템을 관리한다.

5. filesys/file.h, filesys/file.c : 파일 read와 write를 디스크 섹터 read와 write로 변환한다.

6. include/lib/kernel/bitmap.h, lib/kernel/bitmap.c : 비트맵을 디스크 파일에다가 read, write하는 루틴이 있는 비트맵 자료구조가 있다.

👋 프로젝트4에 들어오며 생기는 제한 사항 👋
🙌 파일 시스템 지속성 테스트(Testing File System Persistence) 🙌

• 1. 지금까지 각 테스트는 Pintos를 한 번만 실행시켰다. 파일시스템의 중요한 목적은 재부팅시에도 같은 데이터에 계속 접근 가능하도록 보장하는 것이다. 즉, 파일시스템 프로젝트 테스트는 Pintos를 두 번 실행시킨다. 두 번째 실행에서 파일시스템의 모든 파일과 디렉토리를 하나의 파일로 결합하고, 해당 파일을 핀토스 파일 시스템에서 호스트의 파일 시스템으로 복사한다.
• 2. 채점 스크립트는 두 번째 실행에서 복사된 파일의 내용을 바탕으로 파일시스템의 정확도를 평가한다. 파일시스템이 웬만큼 구현돼서 tar를 지원하기 전까지는 파일시스템이 추가 테스트를 어떤 것도 통과할 수 없다는 것이다. 그 전까진 추출된(extracted) 파일시스템과 관련된 make check의 에러들은 무시해도 된다.

     tar : 복사되어서 내보내질 파일을 생성하는 Pintos 유저 프로그램

---

1. Indexed and Extensible Files

👨‍💻 기본 파일시스템은 어떻게 되어 있나요?

기본 파일 시스템은 파일들을 단일 면적에 할당하기 때문에 외부단편화에 취약하다. 즉, n개 블록이 비어있는데도 불구하고 (외부단편화가 되어 서로 떨어져 있다면) n개 길이의 블록이 할당될 수 없다는 말이다.

이 말은 실제 구현에서 직접, 간접, 이중 간접(doubly indirect) 블록들을 사용하는 인덱스 구조를 사용해야 할지도 모른다는 것을 의미한다. 즉, 스켈레톤 코드를 통해 FAT(File Allocation Table)를 구현해야 한다. (핀토스에서는 멀티레벨 인덱싱을 포함해서는 안된다)

파일 시스템 파티션이 8MB보다 크지 않을 것이라고 가정해도 좋다. 메타데이터를 제외한 파티션 크기만큼의 큰 파일들을 지원해야한다. 각 inode는 하나의 디스크 섹터에 저장된다. 그 섹터가 담을 수 있는 만큼으로 블록 포인터의 수가 제한된다.

👉 FAT를 활용하여 큰 파일을 인덱싱하기
이전까지 사용한 기본 파일시스템은 파일이 여러 디스크 섹터에 걸친 연속된 단일 덩어리로 저장되어 있었다. 연속된 덩어리를 클러스터라고 부른다. 왜냐하면 클러스터는 하나 이상의 연속된 디스크 섹터를 담을 수 있기 때문이다. 이러한 관점에서 기본 파일시스템에서 클러스터의 사이즈는 곧 클러스터에 저장된 파일의 크기를 의미한다.

외부단편화를 해소하기 위해서, 클러스터의 사이즈를 줄일 수 있다. 단순화를 위해, 스켈레톤 코드에 있는 클러스터 내의 섹터의 개수는 1로 고정해두었다. 이런 작은 클러스터를 쓰면, 전체 파일을 담기에는 클러스터의 크기가 충분하지 않을 수 있다. 이런 경우, 한 파일을 위한 여러 개의 클러스터를 필요로하기 때문에 inode에 있는 파일을 위한 클러스터를 인덱싱하기 위한 자료구조가 필요하다.

가장 쉬운 방법은 '체인'이라고 불리는 연결리스트를 사용하는 것이다. inode는 파일의 첫 번째 블록의 섹터 넘버를 포함할 수 있고, 첫 번째 블록은 두 번째 블록의 섹터 넘버를 포함할 수있다. 그러나 이런 접근은 필요한 블록이 마지막 블록 뿐일지라도 파일의 모든 블록을 읽어야 하기 때문에 너무 느리다.

이를 극복하기 위해 , 파일할당테이블(FAT)을 사용한다. 각 블록들이 자신의 구조 안에 블록 자신을 넣는 대신에 고정 크기의 FAT 안에 블록의 연결 정보를 저장한다. FAT가 실제 데이터가 아닌 연결정보 값만 담고 있기 때문에, DRAM에 캐시될 수 있을 만큼 충분히 작은 크기를 갖는다. 결과적으로 테이블에 상응하는 엔트리만 읽으면 된다.

우선, fat.c에 있는 6개의 함수들 (i.e. fat_init(), fat_open(), fat_close(), fat_create(), and fat_boot_create())은 부팅 시 디스크를 초기화하고 포맷하기 때문에, 이들을 수정할 필요가 없다. 그러나, fat_fs_init()함수를 작성하고, 이들이 하는 일이 어떤 도움이 될 지를 이해해야 한다.

1. cluster_t fat_fs_init (void)

cluster_t fat_fs_init (void);
/* FAT 파일 시스템을 초기화한다. fat_fs의 fat_length와 data_start 필드를 초기화해야 한다. 
* fat_legnth는 파일 시스템에 몇 개의 클러스터가 있는 지에 대한 정보를 저장한다. 
* data_start는 어떤 섹터에서 파일 저장을 시작할 수 있는 지에 대한 정보를 저장한다.*/

2. cluster_t fat_create_chain (cluster_t clst)

cluster_t fat_create_chain (cluster_t clst);
/* clst 인자로 특정된 클러스터 뒤에 다른 클러스터를 추가하여 체인을 연장한다.
* 만약 clst가 0이라면, 새로운 체인을 만든다
* 새롭게 할당된 클러스터의 넘버를 리턴한다 */

3. void fat_remove_chain (cluster_t clst, cluster_t pclst)

void fat_remove_chain (cluster_t clst, cluster_t pclst)
/* clst로부터 시작하여, 체인으로부터 클러스터를 제거한다.
* pclst는 체인에서의 clst 직전 클러스터여야한다.
* 이 함수가 실행되고 나면 pclst가 업데이트된 체인의 마지막 원소가 될 거라는 말이다
* 만일 clst가 체인의 첫 번째 원소라면 pclst의 값은 0이어야 한다. */

4. void fat_put (cluster_t clst, cluster_t val)

void fat_put (cluster_t clst, cluster_t val)
/* 클러스터 넘버 clst가 가리키는 FAT 엔트리를 val로 업데이트한다
* FAT에 있는 각 엔트리는 체인에서의 다음 클러스터를 가리키고 있기 때문에
* (만약 존재하지 않다면 EOChain(End Of Chain)을 의미함)
* 이 함수는 연결관계를 업데이트하기 위해 사용될 수 있다. */

5. cluster_t fat_get (cluster_t clst);

cluster_t fat_get (cluster_t clst)
/* clst가 가리키는 클러스터 넘버를 리턴한다 */

6. disk_sector_t cluster_to_sector (cluster_t clst);

disk_sector_t cluster_to_sector (cluster_t clst)
클러스터 넘버 clst를 상응하는 섹터 넘버로 변환하고, 그 섹터 넘버를 리턴한다.

---

👨‍💻 File Growth

크기를 증가시킬 수 있는 파일(Extensible File)을 구현하기.

👉기본 파일시스템에서는 파일의 생성 시에 파일 크기가 특정되었다. 하지만 대부분 현대 파일시스템에서 파일의 크기는 0으로 생성되고, 파일의 끝에서 쓰기가 이루어질 때마다 확장된다.

파일 크게 제한을 미리 정해두지 말아야한다. 물론 메타데이터를 제외한 파일시스템의 크기를 넘어서지 않는 선에 한해서다. 지금은 16개 파일로 제한되어 있는 루트 디렉토리 파일도 이제는 더 증가될 수 있어야한다.

유저 프로그램들은 현재 파일의 끝을 넘어서는 탐색을 할 수 있다. 탐색 자체로는 파일이 증가되지 않는다. EOF를 넘어선 위치에 write하면 그 위치까지 파일을 증가시키며, 이전 EOF에서부터 write의 시작위치 사이의 빈 공간은 0으로 채워져야한다. EOF를 넘어선 위치에서 read 하는 것은 어떤 바이트로 리턴하지 않는다.

EOF를 넘어서서 write 하는 것은 수많은 블록들을 완전히 0으로 만들 것이다. 어떤 파일시스템들은 이런 묵시적인 0으로 이루어진 블록들을 실제로 할당하고 write한다. 하지만 다른 어떤 파일 시스템들은 명시적으로 write 되기 전까지는 그 블록들을 할당하지 않는다. 후자의 파일시스템들은 sparse files(밀도가 희박한 파일)을 지원한다고 불린다.