Extended File System

• EXTended file system의 약자
• 주로 리눅스 OS에서 많이 쓰이는 파일 시스템
• 1992년 ext를 시작으로 버전업을 진행하면서 현재도 많이 사용되고 있음

1. ext (in 1992)

• 리눅스 초기에 사용되던 파일 시스템
• From UFS(Unix File System) – Replacing MFS(Minix File System)
• 호환성 X

2. ext2 (in 1993)

• ext3가 개발되기 이전까지 가장 많이 사용된 파일 시스템
• 뛰어난 성능, 안정성
• 시스템 다운 시, 재부팅 시에 e2fsck라는 ext2 파일 시스템 검사 프로그램을 강제적으로 수행해야 했음

3. ext3 (in 2001;2.4.15)

• Journaling
• Online file system growth (Online-resizing)
• Htree (btree의 고급판)

4. ext4 (in 2006;2.6.19, 2008;2.6.28)

• 하위 파일 시스템 호환성(cf > Extent)
• Journaling Checksum
• Larger File System / File Size

	ext2	ext3	ext4
Max File Size	16GB~2TB	16GB~2TB	16GB~16TB
Max File System size	2TB~32TB	4TB~32TB	1EB

• 입출력 성능 향상
  • Extents
  • Multiblock allocation (다중블록 할당)
  • Delayed allocation (지연 할당)

EXT4 Layout

• 파일시스템을 구성하는 정보들은 각 block group에 분산 (Super block 과 group descriptor는 모든 block group에 존재)
• 파일을 저장할 때 특정 부분에 집중적으로 기록하여 하드디스크의 효율을 높이고자 함(파일 단편화를 줄임)
• 첫번째 블록(Block 0)
  • Partition boot sector를 위해 예약됨
  • Bootloader인 LILO 또는 GRUB이 들어감
• 두번째 블록(Block 1)부터 Block Group 0 시작
• 파일 시스템 전체는 여러 개의 block group으로 구성

EXT4 Data Structure

Type	Disk data	Memory data	Caching mode
Superblock	ext4_super_block	ext4_sb_info	Always cached
Group descriptor	ext4_group_desc	ext4_group_desc	Always cached
Block bitmap	Bit array in block	Bit array in buffer	Dynamic
inode bitmap	Bit array in block	Bit array in buffer	Dynamic
inode	ext4_inode	ext4_inode_info	Dynamic

SuperBlock

• SuperBlock은 블록 수, inode 수, 지원 기능, 유지 관리 정보, 저널 정보 등과 같은 포함 파일 시스템에 대한 다양한 정보를 기록함
• Super Block이 손상되면 전체 파일 시스템에 대한 정보를 잃기 때문에 Super block과 group descriptor table의 사본은 모든 block group에 저장
• 각 block group의 첫 번째 block에 위치

// total: 1024 bytes
struct ext4_super_block {

		// overall
        __le32  s_inodes_count;         /* Inodes count */
        __le32  s_blocks_count_lo;      /* Blocks count */
        __le32  s_r_blocks_count_lo;    /* Reserved blocks count */
        __le32  s_free_blocks_count_lo; /* Free blocks count */
        __le32  s_free_inodes_count;    /* Free inodes count */
        __le32  s_first_data_block;     /* First Data Block */
        __le32  s_log_block_size;       /* Block size */
        __le32  s_log_cluster_size;     /* Allocation cluster size */
        __le32  s_blocks_per_group;     /* # Blocks per group */
        __le32  s_clusters_per_group;   /* # Clusters per group */
        __le32  s_inodes_per_group;     /* # Inodes per group */
		...
        // journaling
        __u8    s_journal_uuid[16];     /* uuid of journal superblock */
        __le32  s_journal_inum;         /* inode number of journal file */
        __le32  s_journal_dev;          /* device number of journal file */
        ...
}

$ dumpe2fs –h /dev/sd[a-z]$n

Block Group Descriptor

• 파일 시스템의 각 블록 그룹에는 이와 관련된 설명자 중 하나가 있음.
• Super block 바로 다음 block에 위치
• Block Descriptor는 비트맵과 inode 테이블의 위치를 모두 기록함. (이는 고정된 위치를 가진 유일한 데이터 구조가 슈퍼블록과 그룹 설명자 테이블임을 의미)

// total 64bytes
struct ext4_group_desc { 
        __le32  bg_block_bitmap_lo;     /* Blocks bitmap block */
        __le32  bg_inode_bitmap_lo;     /* Inodes bitmap block */
        __le32  bg_inode_table_lo;      /* Inodes table block */
        __le16  bg_free_blocks_count_lo;/* Free blocks count */
        __le16  bg_free_inodes_count_lo;/* Free inodes count */
        __le16  bg_used_dirs_count_lo;  /* Directories count */
        __le16  bg_flags;               /* EXT4_BG_flags */
        …
}

$dumpe2fs /dev/sd[a-z]$n

Block bitmaps

• 이 블록에 속한 각 비트는 그룹 내에 있는 각 블록의 사용 상태를 나타냄
• Block 크기가 4KByte면 4K*8개 블록의 사용 여부 표시

Inode

• inode (index node)
  • 파일에 대한 제어 정보 및 데이터 블록 포인터 저장
  • 모든 파일들과 디렉터리들은 각각 1개의 inode를 할당
• inode bitmap
  • 이 블록에 속한 각 비트는 그룹 내에 있는 각 inode의 사용 상태를 나타냄
• inode table
  • 각각의 inode에 대한 정보를 나타내는 inode descriptor로 구성
  • inode table은 Group Descriptor Table에 저장
  • inode 번호를 알면 inode가 속한 Group을 알 수 있음
    -> Block group = (inode - 1) / INODES_PER_GROUP

Extent addressing

• Ext2/Ext3과 같은 유닉스 드라이버의 파일 시스템은 각각의 블록(파일의 데이터에 해당하여 사용되는)들의 트랙을 유지하기 위해 간접 블록 매핑 스키마를 사용 (큰 파일에 대해서 비효율적)
• 반면 Ext4는 어느 정도의 연속된 공간만 초기에 할당하며 그 양이 충분히 크지 않을 때. 추후 또 다른 연속된 공간을 익스텐트(extent)라고 부르는 단위로 할당
• 파일 블록들의 위치는 위치와 블록 수, 다음 익스텐트의 첫 블록을 가리키는 포인터로 기록됨
• Ext2/Ext3 Indirect Block vs Ext4 Extent
  

Multiblock Allocation

• 이전 파일 시스템의 단점
  • 새로운 데이터를 디스크로 쓸 필요가 생길 때, 블록 할당자(Block Allocator)는 데이터가 쓰여질 가용 공간을 결정
  • Ext2/Ext3 블록 할당자는 오직 한번에 한 개의 블록(4KB)만 할당 할 수 있음
  • 만약 시스템이 100MB의 가용공간이 필요하다면 Ext2/3 블록 할당자는 25600번 (100MB = 25600 블록)의 블록 할당 호출을 하게 됨 -> 단일 블록만을 다루기 때문

• Ext4의 다중 블록 할당
  • Ext4는 매 호출마다 싱글 블럭을 할당하는 대신에 많은 오버헤드를 피하기 위해서 한번의 호출로 많은 블록을 할당할 수 있는 다중 블록 할당자(multi block allocator)를 사용

ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
                                struct ext4_allocation_request *ar, int *errp)
{
	…
	*errp = ext4_mb_regular_allocator(ac); /* allocate space in core */
}

ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
                                ext3_fsblk_t goal, unsigned long *count, int *errp)
{	
	…
	for (bgi = 0; bgi < ngroups; bgi ++)
		grp_alloc_blk = ext3_try_to_allocate_with_rsv(sb, handle,
                                        group_no, bitmap_bh, -1, my_rsv,
                                        &num, &fatal);	
}

Delayed Allocation

• 지연할당은 자유 블록 카운트만 갱신하고 실제 할당은 뒤로 미루는 방식(단편화 방지)

• 이전 파일 시스템의 할당 정책

  • write() 연산의 경우, 파일 시스템 코드는 심지어 데이터가 디스크에 즉시 쓰여지고 있지 않더라도 이것을 일정한 시간동안 캐시에 유지한 채 즉시 데이터가 위치할 블록으로 할당
  • 이러한 접근은 단점 가짐. 가령 커지는 파일에 지속적으로 write() 연산을 할 때 데이터의 블록으로의 성공적인 write() 할당이 이루어지더라도 그 파일이 계속 커질 것이라는 것은 알지 못하기 때문

• Ex4의 지연 할당

  • 파일이 캐시에 유지되어 있는 동안에는 그 파일이 실제로 디스크에 쓰여질 때 까지 블록으로의 할당을 지연시킴

int ext4_alloc_da_blocks (struct inode *inode)
{
        trace_ext4_alloc_da_blocks(inode);

        if (!EXT4_I(inode)->i_reserved_data_blocks &&
            !EXT4_I(inode)->i_reserved_meta_blocks)
                return 0;
        return filemap_flush(inode->i_mapping);
}