들어가며

안녕하세요

오늘은 xv6에 FAT이라는 새로운 파일 시스템을 넣어보려고 합니다. 그전에 xv6의 기존 file system에 대해 알아보자면 다음 그림과 같습니다.

filesystem에 관한 정보를 저장하고있는 superblock과 Inode 블럭에 관한 정보를 저장하는 Inode Bitmap 블럭과 Indoe블럭들, Data 블럭에 관한 정보를 저장하는 Data Bitmap 블럭과 Data 블럭들이 있죠.

이번에 도입할 FAT filesystem이란 File Allocation Table(FAT)이라는 배열 형태의 새로운 자료구조를 활용하여 만약 어떤 파일이 44, 48, 49의 데이터 블럭을 사용한다고 하면 FAT[44] = 48, FAT[48] = 49, FAT[49] = 0 이런 형태로 해당 파일의 한 블럭의 다음 블럭을 저장해두는 시스템입니다.

또한 Bitmap블럭을 사용하지않고 freeblock list를 관리하여 이 list를 통해 새로운 블럭을 할당해줍니다. 그러기 위해서 superblock에 전체 free block 수를 나타내는 freeblks, 리스트의 시작을 가리키는 freehead 등의 정보가 담겨있고, 계속해서 업데이트 될 것 입니다.

기존 파일 시스템 분석

파일 시스템이 어떻게 동작하는지 파일을 read하는 예제를 통해 살펴보겠습니다.

read를 하게되면 sys_read() 시스템 콜이 호출되고, 여러 과정을 거쳐 최종적으로 readi()가 호출되게됩니다. readi()는 inode를 읽어오는 함수인데 아래와 같이 생겼습니다.

함수 인자로 주어진 off, n을 이용하여 해당 inode의 data block을 읽어오는 것이죠. 이 때 bmap은 해당 offset이 적혀있는 데이터 블록의 번호를 리턴해줍니다.

int readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;

  for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
    uint blkno = bmap(ip, off/BSIZE); // bmap : 해당 위치의 내용이 적혀있는 블럭 번호 리턴
    if(blkno == 0)
      break;
    bp = bread(ip->dev, blkno); // 해당 블럭 번호 내용 읽어서 리턴 & spinlock 잡기
    m = min(n - tot, BSIZE - off%BSIZE);
    if(either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
      brelse(bp); // spinlock 해제
      tot = -1;
      break;
    }
    brelse(bp);
  }
  return tot;
}

FAT file system 구현

readi를 FAT file system으로 구현하기위해서 bmap부터 다시 구현할 필요가 있습니다. 그것을 위해 저는 bmap을 다음과 같이 구현하였습니다.

static uint
bmap(struct inode *ip, uint bn)
{
  if (ip->startblk == 0)
  {
    ip->startblk = balloc(ip->dev);
  }

  uint datablockno = findnthdatablockno(ip, bn);
  
  return (datablockno);
}

uint findnthdatablockno(struct inode *ip, uint bn)
{
  uint currblkno = ip->startblk;
  uint nextblkno;
  uint fatblkno = -1;

  if (bn == 0)
    return ip->startblk; // 첫번째 블럭 리턴

  while (1)
  {
    if (bn == 0)
      return currblkno;

    fatblkno = FBLOCK(currblkno, sb) - sb.fatstart; // fat 블럭 탐색
    acquire(&fatlock[fatblkno]);
    nextblkno = fats[fatblkno][currblkno % 256]; // fat 배열에서 값 읽어오기
    release(&fatlock[fatblkno]);

    if (nextblkno == 0)
    {
      nextblkno = balloc(ip->dev);
      if (nextblkno == 0)
        return 0;

      acquire(&fatlock[fatblkno]);
      fats[fatblkno][currblkno % 256] = nextblkno;
      release(&fatlock[fatblkno]);
    }

    currblkno = nextblkno;
    bn--;
  }
}

여기서 balloc이란 block allocation으로 해당 inode에 아무런 데이터 블럭이 할당돼있지않으면 새로운 블럭을 할당해주는 것입니다. 그 후, 인자로 주어진 bn번째 데이터 블럭을 찾는 함수를 실행합니다.

findnthdatablockno()의 while문 안에서는 우선 fat 블럭 번호를 찾습니다. 앞서 말씀드린 FAT 배열은 FAT 블럭이라는 곳에 저장되어있기때문에 현재 찾고자하는 블럭과 관련된 정보가 몇번 FAT블럭에 저장되어있는지(FAT 블럭 하나당 256개의 엔트리만 저장 가능하기때문에) 찾고, 그 배열을 읽어옴으로써 다음 블럭 번호를 알아오는 것입니다.

이렇게 fat배열을 통해 한 파일에 할당돼있는 데이터 블럭들에 순차적으로 접근할 수 있습니다.

한편 balloc()과 같은 경우 아래와 같이 구현하였습니다. 전역변수인 sb에 접근하기 전에 sleeplock을 잡고, 새로운 freeblock을 할당해준 뒤, FAT 배열을 업데이트하고 마무리하는 함수입니다.

static uint
balloc(uint dev)
{
  uint fatblkno;
  uint freeblk;
  uint nextblkno;

  acquiresleep(&splock); // sleeplock
  if (sb.freeblks == 0)
  {
    printf("balloc: out of blocks\n");
    releasesleep(&splock);
    return 0;
  }

  freeblk = sb.freehead; // 새 freeblk 할당
  fatblkno = FBLOCK(freeblk, sb) - sb.fatstart;
  
  acquire(&fatlock[fatblkno]); // fat 배열 업데이트
  nextblkno = fats[fatblkno][freeblk % 256];
  fats[fatblkno][freeblk % 256] = 0;
  release(&fatlock[fatblkno]);

  sb.freehead = nextblkno; // sb값 업데이트
  sb.freeblks--;
  releasesleep(&splock);

  bzero(dev, freeblk); // 초기화
  
  return (freeblk);
}

이러한 과정들을 통해 xv6 안에 FAT 파일 시스템을 구현할 수 있었는데요 사실 이번 프로젝트를 하면서 어떻게 FAT file system을 구현하는가보다 더 큰 고민이였던 것이 파일 시스템의 최적화 문제였습니다.

최적화

usertests라는 테스트가 있습니다. 이 테스트는 여러가지 read, write, open, unlink 등 다양한 작업을 반복적으로 수행하며 시스템에 부하를 주어 수행 속도를 측정하는 테스트입니다.

제가 코드를 바꾸기 전 기존 xv6는 이 usertests를 수행하는데 7분가량 걸렸습니다. 그런데 제가 처음에 FAT file system을 구현했을 때는 11분이 걸렸습니다. 그 때는 제가 위에 보여드린 코드처럼 fats[]배열을 이용한 것이 아니라 정말로 bread()라는 블럭을 읽어오는 함수를 통해 fat 블럭을 읽어오고, 바로 수정을 했었습니다.

이게 너무 오래 걸려서 가장 최근에 읽은 블럭을 캐싱하자는 아이디어를 떠올렸고, 그걸 통해 usertests 수행 시간을 11분에서 7분 30초 가량으로 줄였었습니다. 여기서 놀랐던 것이 가장 최근 블럭 단 하나만 캐싱했는데 시간이 획기적으로 줄었다는 것이었고 이를 통해 새삼 TLB같은 것이 얼마나 효과적인지 간접적으로나마 체감할 수 있었습니다.

그렇지만 이것또한 오래걸리는 것 같아 fat배열을 메모리에 유지하고 나중에 한번에 디스크에 적자는 생각을 하게되었고, 이렇게 하자 다른 최적화없이도 usertests를 통과하는데 4분 가량이 걸려서 메모리와 디스크의 접근 사이에 시간 차이가 정말 많이난다는 것또한 알게되었습니다.

저는 이러한 최적화의 과정을 거쳤는데 여러분도 만약 파일 시스템을 건드리게 될 일이 있으시다면 이런 과정을 참고해보시면 좋을 것 같습니다.