xv6 파일시스템 구조

파일시스템은

• 파일, 디렉토리 및 경로이름을 제공하고 데이터를 저장한다
• 응급 복구를 지원한다
  서로 다른 프로세스가 동시에 작동할 수 있으므로 불변성 유지
• 인기있는 블록의 메모리 내 캐시 유지

구조

7계층으로 구성

• 디스크
  하드 드라이브에서 블록을 읽고 씀

• 버퍼 캐시
  디스크 블록을 캐시하고 액세스 동기화

• 로깅
  상위 레이어가 트랜잭션의 여러 블록에 대한 업데이트를 래핑,충돌 발생시 블록이 원자적으로 업데이트되도록 한다.

• inode
  고유한 i-num과 파일 데이터를 보유하는 일부 블록으로 구성된 inode 표기 파일 제공

• 디렉토리
  각각 파일 이름과 i-num을 포함하는 일련의 디렉토리 항목을 내용으로 하는 특수한 종류의 inode로 각 디렉토리를 구현
  경로 이름 제공하고 재귀 조회로 해결

• file descripter
  파일 시스템 인터페이스 사용하여 많은 unix 리소스를 추상화

섹션

블록 저장을 하기 위해 여러 섹션으로 나눈다.
fs.h에 데이터 구조 있음

• block 0
  boot sector 가짐
  사용하지 않는다

• block 1 : superblock
  metadata 가지고 있음( 블럭 안 파일 사이즈, 데이터 블럭의 수, inode의 수, log내 블럭의 수)
  초기 파일 시스템을 구성하는 mfks라는 프로그램으로 채워짐

• block 2 : log

• block 4 : inode
  한 블록에 여러개의 inode 가짐

• bitmap
  사용중인 데이터 블록 추적

• data block
  각각은 비트맵 블록에서 사용 가능으로 표시됨, 디렉토리에 대한 내용 보유

buffer cache layer

두가지 역할

1. 동기화
   블록의 복사본 하나만 메모리에 있고 한 번에 하나의 커널 스레드만 복사본을 사용하도록 디스크 블록에 대한 액세스를 동기화

2. 캐시
   느린 디스크에서 다시 읽을 필요가 없도록 캐시 ( 코드는 bio.c 존재)

버퍼 캐시에서 내보낸 인터페이스

• bread
  메모리에서 읽거나 수정할 수 있는 블록의 복사본을 포함하는 buf 얻음

• bwrite
  수정된 버퍼를 디스크의 적절한 블록에 씀
  커널 쓰레드는 brelse를 통해 반드시 버퍼 놔줘야함

버퍼 캐시는 per-buffer sleep-lock를 사용하여 동기화 보장
bread는 버퍼를 잠그고 brelse는 lock을 푼다

버퍼 캐시 코드 bio.c 분석

버퍼 캐시는 더블 링크드리스트

binit 함수가 링크드리스트를 NBUF로 만든다

버퍼에 두개의 상태비트 존재

• B_VALID
  버퍼에 블록의 사본이 포함되어 있음

• B_DIRTY
  버퍼 내용이 수정되었으며 디스크에 기록해야함

Bread는 bget을 호출해 지정된 섹터에 대한 버퍼 가져옴
디스크에서 읽어야 하는 경우에는 버퍼를 반환하기 전에 iderw를 호출하여 수행

Bget은 주어진 장치 및 섹터 번호가 있는 버퍼에 대한 버퍼목록 스캔

• 있으면 그 버퍼에 대한 sleep-lock 얻는다
  그리고 locked buffer 리턴

• 없으면 다른 섹터를 보유한 버퍼를 재사용하여 버퍼를 만들어야함
  Bget은 잠기지 않고 더럽지 않은 버퍼를 찾아 사용
  버퍼 메타데이터 편집하여 새 장치 및 섹터 번호를 기록하고 해당 절전 잠금을 획득

동기화를 위해 버퍼에 대한 잠금을 하므로 섹터당 최대 하나의 캐시된 버퍼가 있어야 함
bget은 블럭이 캐시되었는지 확인하는 첫번째 루프~ 블럭이 현재 캐시됐는지 확인하는 두번째 루프 까지bache.lock을 유지함으로써 동기화 수행

첫번째 루프

두번째 루프

bread 한 후에는 사용자가 데이터 쓰거나 읽을 수 있음
버퍼를 수정하면 bwrite를 불러서 데이터를 교체해줘야함
bwrite는 iderw가 읽을 B_DIRTY를 설정한 후에 iderw를 호출해서 디스크 하드웨어와 통신
이후 brelse 해줘야함
brelse는 sleep-lock을 해제하고 버퍼를 연결리스트 맨 앞부분으로 이동시킴
-> 버퍼를 최신순으로 정렬하게 함

찾을때는 앞부분부터 -> 지역 locality 이용
지울때는 뒷부분부터 -> 사용이 적은 버퍼 재사용

logging layer

충돌 문제 해결을 위해 로그 남겨둠
시스템 호출이 직접 파일시스템 데이터 구조를 작성하지 않는다...
먼저 디스크의 로그에 작성하려는 모든 디스크 쓰기에 대한 설명 배치
쓰기를 하면 로그에 전체 작업이 포함되어 있음을 나타내는 특수 커밋 레코드를 디스크에 기록,, 이후에 디스크상의 쓰기 이루어짐

쓰기 후 시스템 호출은 로그 지움

만약 문제가 생겼다면 충돌에서 복구가 됨
로그를 지우면 복구 코드 완료

log design

로그는 슈퍼블록에 지정된 고정위치에 상주

header block과 업데이트된 블록 복사본 (logged blocks)으로 구성

header block은 기록된 블록 각각에 대한 섹터 번호 배열과 로그 블록수 포함
header block의 count가 내부의 교환이 있었는지 알려준다
교환이 일어나면 header block을 씀. 하지만 그전은 안써져있고, 파일 시스템에 다 쓰고나면 count를 0으로 바꿔줌

-> transaction 중간에 충돌시 카운트 0
-> 커밋 후 충돌 발생 시 카운트 0이 아님

logging code

일반적인 구조

begin_op는 로깅 시스템이 현재 커밋되지 않을 때까지, 호출의 쓰기를 보관할 예약되지 않은 로그 공간이 충분할 때까지 대기
log.outstanding은 로그 공간을 예약한 시스템 호출 수 카운트

총 예약 공간은 log.outstanding * MAXOPBLOCKS

log.outstanding을 증가하면 공간이 예약되고 이 시스템 호출 중에 커밋 발생하지 않음
MAXOPBLOCKS개의 개별 블록을 작성할 수 있다고 가정

log_write
bwrite의 프록시 역할 ( 대체제)

블록 섹터번호 메모리에 기록
로그에 슬롯 예약하고 버퍼 B_DIRTY 표시하여 블록 캐시가 블록 캐시를 제거하지 못하도록 함
블록은 커밋될 때까지 캐시에 있어야 함

log absorbtion
단일 트랜잭션동안 블록이 여러번 기록될 때 해당 블록을 로그에서 동일한 슬롯에 할당해줌

end_op

우선 미해결 시스템 호출 수 줄여줌
카운트가 0이면 commit() 하여 현재 트랜잭션 커밋
commit() 과정

• write_log()
  트랜잭션에서 수정된 각 블록을 버퍼 캐시에서 디스크의 로그 슬롯으로 복사

• write_head()
  헤더 블록을 디스크에 씀
  커밋 지점..

• install_trans
  로그에서 각 블록을 읽고 파일 시스템의 적절한 위치에 씀

• end_op
  카운터가 0인 로그 헤더 기록

block allocator code

xv6의 block allocator은 free bitmap 유지, 0비트는 해당 블록이 비어있음 1비트는 사용중을 나타냄

mkfs는 boot sector, superblock, log blocks, inode blocks, bitmap blocks에 해당 비트 설정

block allocator 기능

1. balloc
   새 디스크 블록 할당
   비트맵 비트가 0인 블록 찾음
   비트맵 업데이트하고 위의 블록 반환

2. bfree
   블록 해제
   맞는 비트맵 블록 찾아 올바른 비트 지움

inode layer

inode란
파일 주소, 크기, 인덱스등 정보를 가진 블럭

• on-disk inode
  파일 크기와 데이터 블록 번호 목록을 포함하는 디스크 데이터 구조

• in-memory inode
  커널 내에 필요한 추가 정보뿐만 아니라 on-disk inode의 복사본을 포함하는 메모리 내의 inode

fs.h에 정의

온디스크 inode
struct dinode에 의해 정의

• type
  file, directory, special file 구분해준다
  0은 사용가능함을 나타냄

• nlink
  이 inode를 사용하는 on-disk 디렉토리 수를 카운트

• size
  몇바이트의 내용이 있는지 표시

struct inode는 디스크의 dinode의 in-memory 복사본

• ref
  in-memory의 몇개가 이 복사본을 포인팅하는지 카운트
  iget(), iput() 함수가 이 포인트를 얻거나 해제한다
  (ref 변수도 자동 조정해줌)
  icache.lock
  inode는 캐시에 단 하나 존재하게 도와줌
  
  
  각 in-memory inode는 sleep-lock을 포함하는 lock 영역 존재
  1보다 더 큰 ref는 inode가 cache에 남아있도록 함

• nlink
  이 파일에 속하는 디렉토리 수 카운트
  이 수가 0보다 크다면 이 inode를 절대 free하지 않는다

iget()(inode 복사본 리턴하는 함수, ref++)에 의해 반환된 struct inode 포인터는 iput()에 대한 해당 호출까지 유효함 보장
iget()는 비독점 접근 허용
많은 포인터가 같은 inode일 수 있다
!

inode code

새 inode 할당을 위해 ialloc() 호출 (balloc과 유사함)
ialloc은 루프를 돌면서 마크가 빈 곳을 찾음
찾으면 디스크에 쓰고 iget 호출로 inode 캐시의 시작점부터 끝점까지를 리턴함
ialloc의 올바른 동작은 한번에 하나의 프로세스만 bp에 대한 참조를 할수 있다는 여부에 달려있음

iget()
원하는 장치 및 inode 번호가 있는 active entry(ip->ref>0)에 대한 inode 캐시를 살펴봄
찾으면 해당 inode에 대한 새 참조 반환

ilock()

메타데이터나 content 읽기 전에 잠궈줘야함
ilock은 위의 이유로 sleep-lock 사용

iput() : inode 포인터 하나 해제
reference count를 감소시켜 inode 포인터 해제
마지막 참조인 이 inode 슬롯은 재사용가능

inode content code

디스크상의 inode 구조체인 dinode는 크기와 블록 번호 배열을 포함함
inode 데이터는 dinode의 addr 배열에 나열된 블록에서 찾을 수 있음
첫번쨰 NDIRECT block
나머지는 NINDIRECT block
마지막 주소는 indirect block의 주소를 준다

따라서 처음의 ndirect block은 inode에 나열된 블록에서 로드할 수 있는데 나머지 nindirect 부분은 간접 블록을 참조한 수 로드할 수 있다

bmap 이야기~

directory layer code

디렉토리는 파일처런 내부적으로 구현
inode는 T_DIR 타입을 가지며 이 데이터는 일련의 디렉토리 항목임

각 항목은 이름과 inode 번호를 포함하는 struct dirent임

dirlookup()
주어진 항목이 있는 디렉토리 검색
찾으면 해당하는 inode 포인터 리턴,
포인터 poff를 편집하려하는 경우 디렉토리 내 항목의 바이트 오프셋으로 설정

pathname layer code

경로 이름 조회에는 각 경로 구성요소에 대해 하나씩 dirlookup에 대한 일련의 호출이 포함

namei : 경로 평가, 해당 inode를 반환

namex : 경로 평가가 시작되는 위치를 결정,
경로가 /로 시작되면 평가는 루트에서 시작
그렇지 않으면 현재 디렉토리에서 시작

skipelem을 사용하여 각 요소를 차례로 고려
루프의 각 반복은 현재 inode ip에서 이름을 조회해야 함
반복은 ip를 잠그고 디렉토리인지 확인하는 것으로 시작
그렇지 않으면 조회 실패

file description layer

xv6는 각 프로세스에 고유한 열린파일 테이블 혹은 파일 설명자를 제공

각 열린 파일은 struct file로 제공됨
inode, pipe를 감싸는 wrapper, i/o offset, open을 호출할 때마다 새로운 구조체 파일이 생김
여러 프로세스가 같은 파일을 열면 다른 구조체 생겨남
같은 프로세스가 같은 파일을 여러 구조체로 만들고 싶을 떄는 dup을 사용하여 별칭 만들기, fork를 사용하여 자식과 공유하는 방법이 있음
이러한 참조는 특정 열린 파일에 대한 참조 수를 추적

시스템의 모든 열린 파일은 전역 파일 테이블인 ftable에 보관

파일 테이블에는 filealloc, filedup, fileclose, fileread, filewrite 기능이 있음

filealloc()
파일 테이블에서 참조되지 않은 파일f->ref==0
을 검색하고 새 참조 반환

filedup()
파일 참조 수 증가,
f 포인터 리턴

fileclose()
ref 감소 파일 참조의 수가 0이라면 유형에 따라 기본 파이프 또는 inode를 해제

inode및 stati에서만 허용

호출을 pipe 또는 inode 구현으로 전달
inode로 나타내는 경우 fileread 및 filewrite는 I/O 오프셋을 작업의 오프셋으로 사용한 다음 이를 진행

system calls code

sys_link, sys_unlink 시스템콜은 디렉토리를 편집하여 inode 참조를 만들거나 해제함

sys_link
argument 가져오는 것으로 시작(old, new)
old가 이미 존재하고 디렉토리가 아니라면 그것의 ip->nlink를 증가시킴
그다음 nameiparent를 사용해서 상위 디렉토리 와 new의 final path element 찾음, old의 inode를 가리키는 새 디렉토리 항목을 만든다

sys_link는 기존 inode의 새 이름을 만든다.

create 함수는 새 inode의 새 이름을 만듦
세가지 파일 생성 시스템 호출의 일반화(O_CREATE, mkdir, mkdev)
nameiparent을 호출하여 상위 디렉토리의 inode를 가져옴,dirlookup을 이용하여 이름이 이미 존재하는지 확인