project3_file_system
위 그림과 같이 기존 xv6는 single indirect만 구현되어있다. indirect란 간접블록에 블록의 포인터만을 기록하여 파일시스템을 효과적으로 관리하는 기법이다. multi indirect 방식도 single indirect 방식에서 간접 블록의 수만 늘리면 간단히 구현할 수 있다. double indirect 방식과 triple indirect 방식을 통해 각각
블록 번호는 a * 12$8^2$ + b * 128 + c와 같이 나타낼 수 있다. 우선 블록 번호를 통해 어떤 indirect로 관리되는지 파악한 후, 위 식의 a, b, c를 각 인덱스로 하여 원하는 데이터 블록에 접근할 수 있다.
multi indirect를 지원하기 위해서는 아래 두 함수의 수정이 필요하다. bmap: xv6에서는 bmap함수를 통해 inode의 n번째 블락 주소를 반환한다. 만약 블락이 존재하지 않으면 새로 블락을 할당한다. itrunc: inode를 가리키는 디렉토리 엔트리가 없고, inode에 대한 메모리 레퍼런스가 존재하지 않으면 inode는 truncate된다. 블록을 free할 땐, inode의 addrs에서 출발하여 모든 데이터 블록까지 도달한 후 해당 블록을 free하면 된다.
하드 링크와 심볼릭 링크의 가장 큰 차이점은 inode 공유 여부이다. 하드링크는 원본 파일과 inode를 공유하지만 심볼릭 링크는 별도의 inode를 가진다. 대신 링크 파일은 원본 파일을 가리키게 된다. 기존 xv6에는 심볼릭 링크 파일 타입이 존재하지 않는다. 따라서 inode 타입에 T_SYMLINK를 추가함으로써 심볼릭 링크 파일 유무를 구분하게 할 수 있다. inode 타입을 확인한 후 심볼릭 링크 파일이라면, 해당 링크 파일이 가리키는 파일로 리다이렉션 시키는 방식으로로 심볼릭 링크를 구현할 수 있다. 단 심볼릭 링크의 메타데이터를 반환할 필요가 있는 경우가 존재할 수 있으며(ls 명령어 등), 이를 위해 O_NOFOLLOW 플래그를 추가했다.
심볼릭 링크는 다른 심볼릭 링크를 가리킬 수 있다. 이로 인해 심볼릭 링크로 인한 사이클이 발생할 수 있다. 이를 방지하기 위해 심볼릭 링크에서 원본 파일로의 리다이렉션은 최대 10번만 일어나게 했다. 이 이상은 사이클이 존재하는 것으로 간주하여 별도로처리 하였다.
마지막으로 현재 구현에서 심볼릭 링크에 대한 cd와 exec는 지원하지 않는다. 이를 지원하려면 open에서 원본 파일로 리다이렉션 시키듯이 chdir과 namei 함수등을 수정하면 된다.
기존 xv6는 write 연산이 발생할 때마다 group flush를 통해 디스크에 바로 쓴다.
bp = bread(...)
modify bp->data[]
log_write(bp)
brelse(bp)
위와 같이 버퍼로 블록을 읽어들인 후 버퍼에 변경사항을 기록한다. 이후 log_write를 통해 로그에 변경 사항을 기록한 후, end_op에서 로그에 기록된 모든 변경사항을 한번에 commit한다. 이러한 방식은 여러 프로세스가 write 연산을 수행 중일 때는 효율적일 수 있으나, 한 프로세스가 여러번 write 하는 상황에서는 disk I/O를 빈번하게 발생시켜 효율이 떨어진다. 따라서 sync 함수를 호출할 때, 혹은 버퍼에 공간이 부족할 때만 flush하도록 하면 위 문제를 해결할 수 있다.
이를 위해서 log_write가 호출되더라도 버퍼가 가득 찼을 때만 log_write_all 함수를 호출하여 모든 dirty 버퍼에 대한 로그를 기록하도록 수정했다. (로그 역시 메모리 상에 존재하는 로그 버퍼를 의미한다. 해당 버퍼는 write_log 함수를 통해 디스크로 flush 된다.) 이후 end_op에서는 기록된 로그가 있을 때만 (즉 버퍼가 가득 찼을 때만) commit을 통해 flush를 수행한다.
유의해야할 것은 실제로 disk I/O가 일어나는 시점에 NBUF만큼의 버퍼를 모두 사용 중이면 disk로의 flush를 정상적으로 수행할 수 없다. 이 작업을 위해 최소 2개의 여유 버퍼는 필요한 것으로 추정된다. 따라서 항상 최소한 SPARESIZE 만큼의 여유 버퍼를 두도록 한다. 즉 버퍼가 가득 찼을 때도 해당 사이즈 만큼의 여유를 두어 flush 작업에 사용할 수 있도록 한다.
이처럼 수정하고 나면 파일에 write를 하거나 새 파일을 생성하더라도 sync를 호출하거나 버퍼가 가득찬 상황이 아니면 재부팅했을 때 변경 사항이 저장되지 않는다. 이는 rm 명령어도 마찬가지이다. rm으로 파일을 제거했는데 재부팅시 파일이 남아있는 점은 다소 어색하게 느껴질 수 있다. 따라서 sync 시스템콜을 유저 프로그램으로 등록해두었다. 이로써 rm 명령어를 사용한 후 sync 명령어를 호출하여 재부팅 후에도 변경사항이 반영되도록 할 수 있다.
마지막으로 구현의 간결성을 위해 concurrency 상황 등은 고려하지 않았으며 오직 한 프로세스에서 I/O가 발생하는 상황만을 안정적으로 지원한다.
fs.h 헤더를 다음과 같이 변경하고 inode 구조체도 이에 맞춰 변경해주면 된다.
#define NDIRECT 10
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDINDIRECT (NINDIRECT * NINDIRECT)
#define NTINDIRECT (NINDIRECT * NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT + NTINDIRECT)
// On-disk inode structure
struct dinode {
short type; // File type
short major; // Major device number (T_DEV only)
short minor; // Minor device number (T_DEV only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+3]; // Data block addresses
};bmap함수는 앞서 설명했듯이 블락번호를 간접블록에서의 인덱스로 변환해서 사용할 수 있다.
static uint
bmap(struct inode *ip, uint bn)
{
uint addr, *a;
struct buf *bp;
if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0)
ip->addrs[bn] = addr = balloc(ip->dev);
return addr;
}
bn -= NDIRECT;
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
// addrs[NDIRECT]는 싱글레벨 인덱스 블록 주소에 해당
if((addr = ip->addrs[NDIRECT]) == 0)
ip->addrs[NDIRECT] = addr = balloc(ip->dev);
// 싱글레벨 인덱스 블록 데이터를 read
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
// 데이터 블록 주소를 블락번호로부터 찾음
if((addr = a[bn]) == 0){
a[bn] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr;
}
if (bn < NDINDIRECT)
{
// 바깥쪽 인덱스 블락 읽어들이기
if((addr = ip->addrs[NDIRECT + 1]) == 0)
ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);
// 안쪽 인덱스 블락 읽어 들이기
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn / NINDIRECT]) == 0)
{
a[bn / NINDIRECT] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
// 실제 데이터 블락 읽어 들이기
bp = bread(ip->dev, addr);
a = (uint *)bp->data;
if ((addr = a[bn % NINDIRECT]) == 0)
{
a[bn % NINDIRECT] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return (addr);
}
if (bn < NTINDIRECT)
{
// 첫번째 인덱스 블락 읽어 들이기
if ((addr = ip->addrs[NDIRECT + 2]) == 0)
ip->addrs[NDIRECT + 2] = addr = balloc(ip->dev);
// 두번째 인덱스 블락 읽어 들이기
bp = bread(ip->dev, addr);
a = (uint *)bp->data;
if ((addr = a[bn / NDINDIRECT]) == 0)
{
a[bn / NDINDIRECT] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
// 세번째 인덱스 블락 읽어 들이기
bp = bread(ip->dev, addr);
a = (uint *)bp->data;
if ((addr = a[(bn % NDINDIRECT) / NINDIRECT]) == 0)
{
a[(bn % NDINDIRECT) / NINDIRECT] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
// 데이터 블락 읽어들이기
bp = bread(ip->dev, addr);
a = (uint *)bp->data;
if ((addr = a[bn % NINDIRECT]) == 0)
{
a[bn % NINDIRECT] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return (addr);
}
panic("bmap: out of range");
}itrunc함수는 내부에서 itrunc_rec를 호출하여 재귀적으로 모든 데이터 블록을 모두 free한다.
static void
itrunc_rec(uint dev, uint addr, int depth)
{
int i;
struct buf *bp;
uint *a;
if (depth == 0)
{
bfree(dev, addr);
return ;
}
bp = bread(dev, addr);
a = (uint *)bp->data;
for (i = 0; i < NINDIRECT; i++)
{
if (a[i] == 0)
continue ;
itrunc_rec(dev, a[i], depth - 1);
}
brelse(bp);
bfree(dev, addr);
}
// Truncate inode (discard contents).
// Only called when the inode has no links
// to it (no directory entries referring to it)
// and has no in-memory reference to it (is
// not an open file or current directory).
static void
itrunc(struct inode *ip)
{
for(int i = 0; i < NDIRECT; i++){
if(ip->addrs[i]){
bfree(ip->dev, ip->addrs[i]);
ip->addrs[i] = 0;
}
}
if (ip->addrs[NDIRECT])
{
itrunc_rec(ip->dev, ip->addrs[NDIRECT], 1);
ip->addrs[NDIRECT] = 0;
}
if (ip->addrs[NDIRECT + 1])
{
itrunc_rec(ip->dev, ip->addrs[NDIRECT + 1], 2);
ip->addrs[NDIRECT + 1] = 0;
}
if (ip->addrs[NDIRECT + 2])
{
itrunc_rec(ip->dev, ip->addrs[NDIRECT + 2], 3);
ip->addrs[NDIRECT + 2] = 0;
}
ip->size = 0;
iupdate(ip);
}심볼릭 링크는 하드 링크와 달리 별개의 inode가 필요하다. 따라서 create를 호출하여 새로운 inode를 반환받는다. 이후 writei를 통해 링크 파일이 가리키는 원본 파일의 경로를 적어둔다. 해당 경로는 추후 필요할 때 readi를 통해 읽어들인다.
int
sys_symlink(void)
{
char *new, *old;
struct inode *ip;
uint bytes;
if(argstr(0, &old) < 0 || argstr(1, &new) < 0)
return -1;
begin_op();
if ((ip = create(new, T_SYMLINK, 0, 0)) == 0)
{
end_op();
return (-1);
}
// create에서 ilock을 잡기 때문에 굳이 잡지 않아도 됨...
bytes = strlen(old) + 1;
// 원본파일 경로를 inode에 기록
if (writei(ip, old, 0, bytes) != bytes)
{
iunlockput(ip);
end_op();
return (-1);
}
iunlockput(ip);
end_op();
return (0);
}open에서 현재 파일이 심볼릭 링크인지 확인하고, 심볼릭 링크라면 심볼릭링크가 가리키는 파일 경로를 읽은 후 해당 경로로 리다이렉션 시킨다.
//h 심볼릭 링크면 open할 때 심볼릭 링크가 가리키는 파일을 열게 하자
// 1. 열려는 파일이 심볼릭인지 검사 2. 심볼릭이면 심볼릭이 가리키는 경로의 파일 오픈
int
sys_open(void)
{
char *path;
char path2[128];
int fd, omode;
struct file *f;
struct inode *ip;
int n_link;
int tmp;
if(argstr(0, &path) < 0 || argint(1, &omode) < 0)
return -1;
begin_op();
//h create 모드라면 기존 파일이 있든 없든 무조건 새로 만든다. (기존코드)
if(omode & O_CREATE)
{
ip = create(path, T_FILE, 0, 0);
if(ip == 0)
{
end_op();
return -1;
}
}
else
{
if((ip = namei(path)) == 0)
{
end_op();
return -1;
}
ilock(ip);
/*** 추가한 부분 ***/
n_link = 0;
// omode가 O_NOFOLLOW가 아니고, ip가 심볼릭 링크이면 원본파일 inode까지 찾아감
while ((omode & O_NOFOLLOW) == 0 && ip->type == T_SYMLINK && n_link < 10)
{
readi(ip, path2, 0, ip->size);
iunlockput(ip);
if ((ip = namei(path2)) == 0)
{
end_op();
return (-1);
}
n_link++;
// 루프 마지막에 항상 락을 잡아서 루프에 진입할 때, 탈출할 때 모두 ilock 상태임
ilock(ip);
memset(path2, 0, sizeof(path2));
}
// link 길이가 10이 넘어가면 사이클로 간주.
if (n_link == 10)
{
iunlockput(ip);
end_op();
return (-1);
}
/*** 추가한 부분 ***/
// if(ip->type == T_DIR && omode != O_RDONLY){
tmp = omode & ~O_NOFOLLOW;
if(ip->type == T_DIR && tmp != O_RDONLY)
{
iunlockput(ip);
end_op();
return -1;
}
}
if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
if(f)
fileclose(f);
iunlockput(ip);
end_op();
return -1;
}
iunlock(ip);
end_op();
f->type = FD_INODE;
f->ip = ip;
f->off = 0;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
return fd;
}stat 함수는 파일의 메타데이터를 반환하는 것이 목적이다. 따라서 O_NOFOLLOW 플래그를 사용하여 원본 파일의 메타데이터 정보를 반환하게 한다.
int
stat(const char *n, struct stat *st)
{
int fd;
int r;
// stat에서 open시 파일의 메타데이터 정보를 얻기 위해 NOFOLLOW 옵션으로 연다.
fd = open(n, O_RDONLY | O_NOFOLLOW);
if(fd < 0)
return -1;
r = fstat(fd, st);
close(fd);
return r;
}마지막으로 기존 ln.c 파일을 수정하여 옵션을 인자로 받도록 하였다.
int
main(int argc, char *argv[])
{
if(argc != 4)
{
printf(2, "Usage: ln [-sh] old new\n");
exit();
}
if (strcmp(argv[1], "-s") == 0)
{
if (symlink(argv[2], argv[3]) < 0)
printf(2, "symlink %s %s: failed\n", argv[2], argv[3]);
}
else if (strcmp(argv[1], "-h") == 0)
{
if (link(argv[2], argv[3]) < 0)
printf(2, "link %s %s: failed\n", argv[2], argv[3]);
}
else
{
printf(2, "Invalid option -- %s\n", argv[1]);
printf(2, "Usage: ln [-sh] old new\n");
}
exit();
}앞서 설명했듯이 log_write 함수가 호출되더라도 버퍼가 가득 찼을 때만 log_write_all 함수를 통해 로그에 기록한다.
void
log_write(struct buf *b)
{
// 동시성등 복잡한 상황을 고려하지 않아도 되므로 로그에 쓰지 않더라도
// 버퍼에 블록을 읽어들이고 수정했다면 버퍼를 dirty로 바로 마킹
b->flags |= B_DIRTY;
if (buf_is_full())
log_write_all();
}int
log_write_all()
{
struct buf *b;
int n_dirty_buf;
int i;
acquire(&bcache.lock);
n_dirty_buf = 0;
for (b = bcache.head.prev; b != &bcache.head; b = b->prev)
{
if ((b->flags & B_DIRTY) != 0)
{
for (i = 0; i < log.lh.n; i++) {
if (log.lh.block[i] == b->blockno) // log absorbtion
break;
}
log.lh.block[i] = b->blockno;
if (i == log.lh.n)
log.lh.n++;
n_dirty_buf++;
}
}
release(&bcache.lock);
return (n_dirty_buf);
}기존 begin_op와 end_op는 크게 바꾸지 않았다. begin_op에서 로그 공간이 부족할 때 sleep하던 기존 코드 부분을 삭제했다. end_op에서는 버퍼가 가득차서 로그 기록을 남겨둔 상황에서만 commit하도록 수정했다.
void
begin_op(void)
{
acquire(&log.lock);
while(1){
//h 로그에 데이터를 못쓰는 상태면 sleep
if(log.committing)
sleep(&log, &log.lock);
else
{
log.outstanding += 1; //h 파일 시스템에 뭔가 쓴다고 선언
release(&log.lock);
break;
}
}
}void
end_op(void)
{
int do_commit = 0;
acquire(&log.lock);
log.outstanding -= 1;
if(log.committing) //h 다른 사람이 로그에 쓰지 않음
panic("log.committing");
// 로그가 존재하면 버퍼를 비워야 함. 로그 기록은 버퍼가 가득 찼을 때만 함
if(log.outstanding == 0 && log.lh.n > 0) {
do_commit = 1;
log.committing = 1;
} else {
// begin_op() may be waiting for log space,
// and decrementing log.outstanding has decreased
// the amount of reserved space.
wakeup(&log);
}
release(&log.lock);
if(do_commit){
// call commit w/o holding locks, since not allowed
// to sleep with locks.
//h commit을 통해 flush
commit();
acquire(&log.lock);
log.committing = 0;
wakeup(&log);
release(&log.lock);
}
}sync 함수에서는 log_write_all을 호출하여 현재 모든 dirty 버퍼를 로그에 기록한 후 commit을 통해 버퍼를 flush한다. 해당 함수를 호출해야 재부팅 시에도 변경사항이 남아있다.
int sync(void)
{
int ret;
ret = log_write_all();
commit();
return (ret);
}p3_bigfile, p3_bigfile2 테스트를 통해 큰 용량의 파일을 생성하고 읽고 쓸 수 있다. 큰 용량의 파일을 생성했다 지우는 작업을 총 여러번 반복하는 테스트도 진행할 수 있는데 이에 대해서는 후술하겠다.
hugefile이란 파일명을 가진 6mb 파일, 16mb 파일을 생성한 결과이다.
심볼릭 링크를 생성하고 ls로 확인한 결과이다.
p3_symlink2를 통해 test 파일을 수정했을 때 심볼릭 파일인 test2에도 반영된 결과이다.
원본 파일을 지웠을 때 심볼릭 링크 파일로 접근이 불가한 결과이다.
위 테스트를 하드 링크에도 적용한 것이다.
disk I/O 속도가 전보다 빨라진 것을 통해 sync가 제대로 구현된 것을 확인할 수 있다.
임시파일을 생성한 후 sync를 호출하지 않으면 재부팅시 해당 파일이 존재하지 않는 것을 확인할 수 있다.
반면 파일을 생성한 후 유저프로그램에 등록한 sync를 호출하면 재부팅 후에도 파일이 남아있는 것을 확인할 수 있다. 즉 sync를 통해서 disk로의 flush가 정상적으로 일어남을 확인할 수 있다.
💡 파일을 변경한 후 sync를 호출하지 않더라도, 버퍼캐쉬에서 해당 데이터가 남아있으면 변경 사항을 읽을 수 있다. 그러나 sync를 통해 디스크로 flush하지 않고 재부팅한다면 해당 데이터는 유실된다.큰 파일(약 16mb)을 생성했다 unlink를 통해 삭제하는 작업을 반복할 때, 특정 조건 하에서 unlink가 실패하는 문제가 발생한다. unlink에서 호출한 itrunc 함수에서 bread를 호출하는데 여기에서 bget이 실패하는 현상이 발생한다. itrunc 함수에도 log_write을 여러번 호출하는데 이 부분이 문제가 되는 걸로 추정된다.
디버깅으로 확인한 결과 현재 19개 이상의 dirty 버퍼가 존재하고 16mb 파일을 삭제할 때 문제가 발생한다. 왜냐하면 16mb 파일을 삭제할 때, 버퍼에 여유공간이 11개 필요하기 때문이다. (두가지 모두 sync의 반환값을 통해 확인할 수 있다.) 가장 간단한 해결법은 버퍼의 SPARESIZE를 기존값보다 더 키우는 것이다. 다르게 해결하고자 한다면 end_op에서 버퍼를 flush하는 게 아니라 log_write_all 직후에 버퍼를 flush하는 것이 필요해 보인다. 그래서 log_write에서 flush작업까지 하려했으나, 락킹과 관련된 이슈가 있었다. 아쉽게도 시간이 부족하여 미해결 상태로 둔다.