Chapter 8. File system

파일 시스템은 데이터를 조직적으로 저장하고 관리하며, 재부팅 후에도 데이터를 유지(Persistence)할 수 있도록 설계되었다.

xv6 파일 시스템은 Unix와 유사한 파일, 디렉토리, 경로명을 지원하며, 데이터를 virtio 디스크에 저장하여 영속성을 제공한다.

 

파일 시스템의 주요 도전 과제

1. on-disk data structures : 

- 디렉토리와 파일의 트리를 표현

- 파일 내용이 저장된 블록을 기록

- 디스크에서 사용 가능한 블록을 추적

2. crash recovery : 전원 차단과 같은 충돌 상황에서도 파일 시스템이 일관성을 유지하고, 충돌로 인해 데이터 구조가 손상될 위험을 방지한다.

3. 동시성 : 여러 프로세스가 동시에 파일 시스템을 사용할 수 있도록 동기화한다.

4. 디스크 접근 속도 문제 : 디스크 접근은 메모리 접근보다 훨씬 느리고, 인기 있는 블록을 메모리에 캐시하여 성능을 개선한다.

 

Overview

xv6 파일 시스템은 7개의 계층으로 구성된다.

 

1. 계층 구조(아래에서 위로)

1) Disk Layer : 디스크의 블록(섹터)을 읽고 쓴다.

2) Buffer Cache Layer : 디스크 블록을 메모리에 캐시. 동시성을 관리하여 하나의 블록에 대해 여러 커널 스레드가 접근하지 못하도록 보호한다.

3) Loggin Layer : 여러 블록 업데이트를 하나의 transaction으로 묶어 원자적으로 처리한다. 충돌 발생 시 일부만 업데이트되는 상황을 방지한다.

4) Inode Layer : 각 파일을 고유한 inode와 블록으로 표현한다.

5) Directory Layer : 디렉터리를 inode의 특수한 형태로 구현하고, 항목은 파일 이름과 inode 번호(i-number)를 포함한다.

6) Pathname Layer : 계층적 경로 이름(ex: /usr/rtm/xv6/fs.c)을 지원한다. 재귀적 탐색으로 경로를 해결한다.

7) File Descriptor Layer : 파이프, 장치, 파일 등을 파일 시스템 인터페이스로 추상화한다.

 

2. 디스크 구조

structure of xv6 file system

 

xv6 파일 시스템은 디스크를 여러 영역으로 나눈다.

1) Block 0 : 부트 섹터(사용하지 않음)

2) Block 1 (Superblock) : 파일 시스템 메타 데이터 저장. 파일 시스템 크기, 데이터 블록 수, inode 수, 로그 블록 수 기록

3) Log Blocks : transaction log 저장

4) Inode Blocks : 데이터 블록의 사용 여부 추적

5) Bitmap Blocks : 데이터 블록의 사용 여부 추적

6) Data Blocks : 파일 또는 디렉터리의 실제 내용 저장

mkfs 프로그램이 파일 시스템을 초기화하고 superblock을 설정

 

Buffer Cache Layer

1. 기능

동기화 : 디스크 블록에 대한 동시 접근을 방지하고, 하나의 블록에 대해 메모리에 단일 복사본 유지

캐싱 : 자주 사용되는 블록을 캐시하여 디스크 접근 최소화

 

2. 인터페이스

 bread : 디스크 블록을 읽어와 버퍼(struct buf)로 반환

bwrite : 수정된 버퍼를 디스크에 씀

brelse : 버퍼를 해제

 

3. 캐시 관리

버퍼 캐시는 고정된 수의 블록만 보유

캐시 미스 발생 시 LRU(Least Recently Used) 정책으로 가장 오래된 버퍼를 교체

 

Code : Buffer Cache

1. 구조

1) 연결 리스트 : 버퍼 캐시는 이중 연결 리스트로 관리. binit 함수가 정적 배열(buf)을 초기화하여 연결 리스트 생성

2) 버퍼 상태 필드 

valid : 디스크 블록 데이터가 유효한지 여부

disk : 버퍼 내용이 디스크로 전송되었는지 여부

 

2. 동작 과정

1) bread : 주어진 섹터의 블록을 반환. 디스크에서 읽을 필요가 있으면 virtio_disk_rw 호출

2) bget

블록을 캐시에서 검색하거나 새로 생성

첫 번째 스캔 : 요청된 섹터를 가진 캐시된 버퍼를 찾고 발견되면 해당 버퍼 반환

두 번째 스캔 : 캐시된 버퍼가 없으면 사용 중이지 않은 버퍼를 재사용. 섹터 정보를 업데이트하고 valid를 0으로 설정

 

3. 락 및 동기화

1) bcache.lock : 블록이 캐시에 존재하는지 확인하고 캐싱 상태를 업데이트하는 동안 보호

2) b->lock(sleep-lock) : 버퍼 데이터의 읽기/쓰기를 보호, b->refcnt가 0이 아니면 재사용되지 않음

 

4. LRU 정책

brelse : 버퍼를 해제하고 리스트의 맨 앞으로 이동. 이중 연결 리스트를 정렬하여 최신 사용 버퍼가 앞에, 가장 오래된 버퍼가 뒤에 위치.

 

5. 오류 처리

모든 버퍼가 사용 중이면 bget은 panic 호출

개선점 : 여유 버퍼가 생길 때까지 대기하는 방식으로 수정 가능. 다만 이 경우 데드락 가능성 존재.

 

Loggin layer

파일 시스템 설계에서 crash recovery는 중요한 문제이다. 

파일 시스템 작업은 일반적으로 여러 디스크 쓰기를 포함하여, 충돌(ex. 전원 차단)이 준간에 발생하면 디스크 데이터 구조가 불일치 상태에 빠질 위험이 있다.

 

문제 예시 : 파일의 내용을 비우는 작엄(파일 길이를 0으로 설정하고 블록을 해제) 중 충돌이 발생할 수 있다 : 

1) Inode가 해제된 블록을 참조 : 심각한 문제로, 다른 파일에서 동일한 블록을 할당받아 데이터가 충돌할 수 있다. 다중 사용자 환경에서는 보안 문제로 이어질 수 있다.

2) 할당된 블록이 참조되지 않음 : 비교적 경미한 문제로, 디스크 공간 낭비만 발생한다.

 

xv6의 해결책 : 로깅

xv6는 로그를 활용한 원자적 파일 시스템 작업으로 충돌 문제를 해결한다.

1) 시스템 호출은 디스크 데이터 구조를 직접 수정하지 않는다.

2) 수정해야 할 디스크 쓰기 작업을 로그에 기록

3) 모든 쓰기를 로그에 기록한 후, commit 레코드를 디스크에 작성하여 로그가 완료되었음을 표시

4) 커밋 후, 로그의 내용을 디스크에 적용

5) 작업 완료 후 로그 삭제

 

충돌 복구 과정

1) 로그가 완전하지 않을 경우 : 커밋 전에 충돌이 발생하면 로그가 완전하지 않으므로 복구 시 로그 무시. 디스크는 작업 전 상태로 유지.

2) 로그가 완전할 경우 : 커밋 후 충돌이 발생하면 복구 시 로그를 사용해 모든 작업을 재적용. 중복 적용은 허용되지만 데이터 일관성 유지.

 

효과 : xv6의 로깅은 파일 시스템 작업을 충돌에 대해 atomic으로 만든다.

- 충돌 후 복구 시, 작업은 완전히 적용되었거나 전혀 적용되지 않음.

 

Log Design

로그는 디스크의 고정된 위치에 저장되며 다음과 같은 구성 요소로 이루어진다.

1) 헤더 블록 : 각 로그 블록의 섹터 번호 배열과 로그 블록의 개수를 포함.

- 로그 블록 개수(count) : 0(로그에 트랜잭션 없음), not 0(커밋된 트랜잭션이 있음)

2) 로그 블록 : 수정된 블록의 복사본 저장

 

로그 작성 흐름

1) 시스템 호출은 로그에 쓰기를 기록

2) 커밋 시점에 헤더 블록 업데이트

3) 커밋 후, 로그 블록을 디스크 데이터 구조에 적용

4) 적용 완료 후 헤더의 count를 0으로 설정하여 로그 초기화

 

group commit

xv6는 여러 시스템 호출의 쓰기를 하나의 transaction으로 묶는 group commit을 지원

- 디스크 작업 수 감소

- 디스크 회전 중 여러 쓰기를 병렬 처리

- xv6 Virtio 드라이버는 병렬 처리를 지원하지 않지만, 설계 자체는 병렬화 고려

로그 공간 제한 : 로그 공간이 고정되어 있어, 트랜잭션에서 사용할 수 있는 블록 수에 제한이 있음.

- 단일 시스템 호출은 로그 크기보다 많은 블록을 수정할 수 없음 -> 큰 쓰기를 여러 작은 트랜잭션으로 나눔

- 로그 공간이 부족하면 새로운 트랜잭션을 시작할 수 없음

 

Code : logging

시스템 호출과 로깅 흐름

begin_op(); // 트랜잭션 시작
bp = bread(...); // 블록 읽기
bp->data[...] = ...; // 블록 수정
log_write(bp); // 로그에 쓰기 등록
end_op(); // 트랜잭션 종료 및 커밋

코드 상세

1. begin_op 

- 현재 트랜잭션이 없는지 확인

- 로그 공간이 충분한지 확인

- log.outstanding 증가(활성 시스템 호출 수)

2. log_write

- 수정된 블록을 로그에 기록

- 블록이 여러 번 수정되더라도 하나의 슬롯만 사용(흡수 최적화 : 동일 블록의 중복 쓰기를 줄여 성능과 공간 효율성 개선)

3. end_op

-활성 시스템 호출 수 감소

- 활성 호출이 0이 되면 커밋 시작

1) write_log : 로그 블록을 디스크에 씀

2) write_head : 헤더 블록을 커밋 상태로 업데이트

3) install_trans : 로그 블록을 실제 디스크 데이터 구조로 복사

4) 헤더 초기화 : count를 0으로 설정

4. recover_from_log : 부팅시 호출. 커밋된 트랜잭션이 있으면 로그를 사용해 복구

 

예제 : filewrite

begin_op(); // 트랜잭션 시작
ilock(f->ip); // 파일 inode 락
r = writei(f->ip); // 파일 데이터 쓰기
iunlock(f->ip); // inode 락 해제
end_op(); // 트랜잭션 종료 및 커밋

큰 쓰기는 여러 개의 작은 트랜잭션으로 나눠 로그 크기 초과 방지

writei는 inode, 비트맵 블록, 데이트 블록 등 여러 블록을 수정

 

Code : Block allocator

파일과 디렉터리의 내용은 디스크 블록에 저장되며, 이를 block allocator를 통해 관리한다.

블록 할당기는 디스크에서 사용 가능한 블록을 추적하고, 필요에 따라 블록을 할당하거나 해제한다.

 

디스크 블록 관리

free bitmap : 디스크의 각 블록에 대해 1비트를 사용하여 상태 추적

- 0 : 블록이 비어 있음(사용 가능)

- 1 : 블록이 사용 중

mkfs는 부트 섹터, 슈퍼 블록, 로그 블록, inode 블록, 비트맵 블록에 해당하는 비트 설정

 

블록 할당기 함수

1. balloc (블록 할당)

사용 가능한 블록을 찾아 할당

작동 방식 : 

1) 블록 비트맵에서 비어 있는 비트(0)을 찾음

2) 비트를 1로 설정하여 해당 블록을 할당 상태로 변경

효율성 :

- 외부 루프 : 비트맵 블록을 읽음

- 내부 푸르 : 비트맵 블록 내의 비트를 검사

경쟁 조건 방지 :  버퍼 캐시를 사용하여 동일 비트맵 블록에 대한 동시 접근 방지

 

2. bfree (블록 해제) : 블록 미트맵에서 특정 비트를 0으로 설정하여 블록을 사용 가능 상태로 변경

- 경쟁 조건 방지 : bread와 brelse를 통해 해당 비트맵 블록을 잠그고 해제

 

트랜잭션 필요성 : balloc과 bfree는 트랜잭션 내에서 호출되어야 한다.

이는 충돌 발생 시 블록 상태를 원자적으로 유지하기 위함이다.

 

Inode layer

Inode란?

Inode는 파일 시스템에서 파일 및 디렉터리를 설명하는 meta data struc이다.

각 inode는 특정 파일에 대한 정보를 포함하여, 디스크와 메모리에서 관리된다.

 

1. Inode의 두 가지 의미

1) 디스크 상의 Inode(On-disk inode)

구조체 : struct dinode

디스크에 저장된 파일 메타데이터

포함 정보 :

- 파일 크기(size)

- 파일 타입(type) : 일반 파일, 디렉터리, 디바이스 등

- 데이터 블록 주소(addrs) : 파일 내용이 저장된 블록 번호

- 참조 수 (nlink) : 디렉터리 항목에서 이 inode를 참조하는 수

2) 메모리 상의 Inode(In-memory inode)

구조체 : struct inode

디스크 inode의 복사본과 커널에서 사용하는 추가 정보 포함

포함 정보 : ref(이 inode를 참조하는 C 포인터 개수), lock(동시 접근 제어)

 

2. Inode 관리 주소

1) Inode 테이블(itable) 

현재 활성 상태의 inode를 메모리에 저장

동일 inode가 중복 로드되지 않도록 관리

역할 : inode의 동시 접근 제어, 자주 사용되는 inode 캐싱

2) Inode 번호(i-number)

inode는 고유한 번호(i-number)로 식별

특정 inode를 빠르게 검색할 수 있음