Ext2 File System
2014년 2학기 시스템 프로그래밍 시험 공부

시스템 프로그래밍 시험 공부하면서 정리한 내용이다. 내용 갱신은 없을 예정이다.

Abstract View of VFS Objects

• In kernel memory
  • super block
  • dentry
  • inode
  • file
  • VFS, 어떤 FS를 쓰더라도 동일
  • File System 문서 참고
• On disk
  • Ext2 Filesystem
  • FS에 따라서 구조가 다르다

The Ext2 Filesystem

역사

• 최초의 리눅스는 Minix 파일시스템을 사용함
• Extended Filesystem 등장. 이전보다 개선되었지만 불만족스러운 성능
• 1994년 Second Extended Filesystem (Ext2)
• 현재 Ext3, Ext4 존재

특징

• 1024~4096 byte까지 설정 가능한 블럭 크기
• inode 의 갯수 설정가능
• 디스크 블럭을 그룹으로 나눈다. 그룹에는 데이터 블럭과 inode가 저장된다
• 일반 파일용 데이터 블럭을 파일을 사용하기전에 미리 할당
• 빠른 심볼릭 링크 지원
• 시스템 크래시의 충격을 최소화하는 파일 갱신 구현
• 부팅할때 파일시스템 상태의 무결성 자동으로 확인
• 변경 불가능한 파일(immutable), 추가만 가능한 파일 지원(append-only)

Ext2 Disk Data Structures

• 포맷
  • 파일 시스템 구조를 디스크에 적절히 기록하는 과정
  • mke2fs - create an ext2/ext3/ext4 filesystem
• Boot Block
  • Ext2 파티션의 첫번째 블럭
  • 부트 섹터용으로 항상 예약
• Block Group 0…N
  • boot block을 제외한 나머지 파티션은 block group으로 나눈다
  • 모든 블럭 그룹은 같은 크기이며 디스크에 연속적으로 저장됨
  • 커널은 하나의 파일이 하나의 블럭 그룹에 속하도록 시도해서 파일 파편화를 최소화
• Super Block
  • 크기 : 1 block
• Group Descriptors
  • 크기 : Ng blocks
• Data block Bitmap
  • 크기 : 1 block
  • 특정 데이터 블럭이 사용중인 추적
  • 데이터 블럭이 사용중이면 1, 아니면 0
• Inode Bitmap
  • 크기 : 1 block
  • 특정 inode가 사용중인지 추적
• Inode Table
  • 크기 : Ni blocks
• Data Blocks
  • 크기 : Nd blocks

‘Block Group’ Disk Data Structure

• superblock과 group descriptor는 모든 block group에 중복해서 저장한다. 하지만 커널은 **block group 0 (main block group)**만 사용한다.
  • block group 1~N 에 저장된 중복된 내용은 복구용으로 사용
• block group의 갯수는 파티션과 블럭 크기에 영향받음
  • 제약사항 : 블럭 bitmap은 단일 블럭에 저장되어야한다.
  • 예 : 8GB 파티션 + 4KB 블럭. 4KB 블럭 = 32K bit. 32K bitmap * 4KB 블럭 = 128MB 블럭 그룹. 8G / 128MB = 64개의 블럭 그룹이 필요

superblock Disk Data Structure

• superblock은 ext2_super_block 구조체에 저장된다.
• 파일시스템/파티션마다 1개
• superblock의 크기 == 1개 블럭
• include/linux/ext2_fs.h

Group Descriptor Disk Data Structure

• 각각의 블럭 그룹은 블럭 디스크립터를 가진다.
• include/linux/ext2_fs.h : ext2_group_desc
• 각각의 블럭 그룹마다 파일시스템 안에서 Ng개의 연속된 블럭을 차지하는 형태로 저장된다.

inode Table Disk Data Structure

• 연속된 블럭을 차지한다. Ni개의 블럭을 차지.
• include/linux/ext2_fs.h : ext2_inode
• 모든 inode는 동일한 크기. 128 byte
  • 4KB = 4096 byte = inode 128 byte * 32개
  • 4KB 블럭당 32개의 inode

inode File Types

• 일반 파일
  • 데이터가 시작되려면 데이터 블럭이 필요
  • file type = 1
• 장치 파일, 파이프, 소켓
  • 데이터 블럭이 필요없다.
  • inode안에 필요한 모든 정보가 저장된다.
  • CHRDEV, (character device) = file type 3
  • BLKDEV, (block device) = file type 4
  • 파이프 = file type 5
  • 소켓 = file type 6
• 심볼릭 링크
  • 60 (15 * 4) 글자까지는 데이터 블럭 포인터 배열에 저장(ext2_inode안의 i_block필드)
    • 빠른 심볼릭 링크
  • 60자 초과시 데이터 블럭 필요
  • file type = 7
• 디렉토리 파일
  • 해당 파일의 데이터 블럭에 파일이름과 대응되는 inode번호를 저장하는 특별한 종류의 파일
  • ext2_dir_entry_2
  • 각각의 디렉토리 구조체는 inode번호, 디렉토리 엔트리 크기, 이름 길이, 파일 타입, 파일 이름을 포함
  • file type = 2

Ext2 Memory Data Structures

• 효율성
  • 대부분의 디스크 자료구조에 저장된 모든 정보는 마운트 할때 램으로 복사한다.
• 얼마나 데이터 구조가 자주 바뀌는지 고려
  • 새로운 파일이 생성될때
  • 파일이 더 많은 디스크 블럭을 필요로 할때
  • 접근 시간이 갱신되어야 할 떄
• 페이지 캐시 사용
  • 일부 메모리상의 자료 구조는 디스크상의 자료 구조와 다르다. (저장 지연)

Ext2 자료구조의 VFS 이미지

Ext2 superblock Object

• include/linux/ext2_fs_sb.h : ext2_sb_info
  • ext2 파일시스템이 마운트되면 VFS 슈퍼 블럭의 s_fs_info는 ext2_sb_info를 가리킨다.
  • ext2 파일시스템만 특화 정보가 저장되어 있다.
  • 이 메모리 자료 구조는 Ext2 superblock 디스크 자료 구조에서 가져온 대부분의 정보를 포함
  • 마운트 상태, 옵션과 같은 정보 포함

Ext2 inode object

• VFS가 ext2 디스크 inode에 접근하면 inode 디스크립터인 ext2_inode_info가 생성된다
• fs/ext2/ext2.h : ext2_inode_info
  • VFS inode 객체 (struct inode)
  • VFS inode에는 없지만 디스크 inode에는 있는 대부분의 내용이 포함됨

Ext2 Operations

• VFS와 특정 파일 시스템이 연관됨
  • ext2_... + generic+... => 함수 포인터로 이루어진 구조체에 연결
• file_operations : 파일의 내용 다루는 함수
• inode_operations : file 객체용 함수
• super_operations : super block과 상호작용하는 함수
• address_space_operations : 일반화된 주소 공간용 함수
  • 파일시스템과 블럭 에이어가 여기에서 연결됨
  • 페이지 캐시

Managing Ext2 Disk Space

• 디스크 공간 관리
  • inode와 data block의 할당/해제
• 디스크 공간 관리의 목표
  1. 파일 파편화 최소화
     • 파일 파편화는 파일 연산의 평균 시간을 늘린다
     • 메모리 할당과 비슷한 문제
  2. 시간 효율
     • 파일 오프셋과 논리 블럭 번호의 변환이 커널에서 빨리 처리되어야 한다.
     • 디스크 자료 구조에 접근하는 것을 제한

inode 할당

• ext2_new_inode()
• 새로운 node를 포함하기에 적절한 block group를 선택해서 ext2 디스크 inode 생성
• 블럭 그룹 안의 일반파일과 디렉토리의 갯수를 균형 맞춤
  • 관계없는 디렉토리를 다른 그룹에 퍼뜨리기
  • 부모 디렉토리가 같은 파일은 같은 그룹에 넣기
• inode 비트맵 갱신, inode 카운터 감소, inode를 superblock의 dirty list에 넣기

inode 해제

• ext2_free_inode()
• inode 객체가 가리키는 디스크 inode 삭제
• 이런 경우에도 호출된다
  • inode가 inode 해시 테이블에서 지워진 이후
  • 마지막 하드 링크가 삭제된 이후
  • 파일이 0으로 truncated된 이후
• inode 비트맵 갱신, inode 카운터 증가, inode를 superblock의 dirty list에 추가

데이터 블럭 어드레싱

• 비어있지 않은 일반 파일은 여러개의 데이터 블럭으로 구성된다
  • 블럭은 파일에서의 상대 위치(file block number)나 디스크 파티션에서의 위치(logical block number)로 조회 가능
• 파일 안에서의 오프셋을 논리 블럭 번호로 유도하는 과정은 2단계를 거친다
  1. file block number를 오프셋에서 유도
     • file block number = (int)(offset / 블럭 크기). 간단하다
  2. file block number를 logical block number로 변환
     • ext2 파일의 데이터 블럭이 디스크에서 인접하지 않을수도 있기 때문에 쉽진 않다
     • 파일 시스템은 각각의 file block number와 대등되는 디스크상의 logical block number를 저장할수 있는 방법을 제공해야 한다.

데이터 블럭 어드세링 상세

• inode안에는 크기 15의 블럭 포인터 배열이 있다.
• 12개 항목 : 실제 데이터 블럭을 가리킨다.
  • 예 : 8KB = 4KB 블럭 * 2, 실제 블럭 가리키는 포인터 2개로 끝
• 13번째 항목 : 1-레벨 참조용으로 쓴다. 데이터 블럭 포인터가 있는 디스크 블럭(index block)을 가리킨다
  • 1024 entry(4KB 블럭 / 4byte) * 4KB 블럭 = 4MB 지원
• 14번째 항목 : 2-레벨 참조용으로 사용
  • 1024 entry(4KB 블럭 / 4byte) * 1024 * 4KB 블럭 = 4GB 지원
• 15번째 항목 : 3-레벨 참조용으로 사용
• Index based file access

데이터 블럭 할당

• fs/ext2/inode.c : ext2_get_block()
• 파편화를 최소화하려고 ext2는 파일이 마지막으로 할당한 블럭 가까이에 있는 새로운 블럭을 주려고 한다.
  • 실패시 파일의 inode가 속해있는 블럭 그룹에서 새로운 블럭을 찾는다.
  • 최후의 수단으로 다른 블럭 그룹의 비어있는 블럭을 사용
• 블럭 미리 할당 수행
• 다양한 bookkeeping 기록 갱신

데이터 블럭 해제

• fs/ext2/inode.c : ext2_truncate()
• 파일을 삭제하려면 inode가 필요
• struct ext2_inode 안의 i_block 추적해서 모든 데이터 블럭을 해제
• 다양한 bookkeeping 기록 갱신