┌──────────────────────────────────────────┐
│       Application (User Space)           │
├──────────────────────────────────────────┤
│       Logical File System                │
│  (File name → inode translation,         │
│   protection checks)                     │
├──────────────────────────────────────────┤
│       File Organization Module           │
│  (Logical block → physical block mapping)│
├──────────────────────────────────────────┤
│       Basic File System                  │
│  (Issues block I/O requests)             │
├──────────────────────────────────────────┤
│       I/O Control                        │
│  (Device drivers, interrupt handlers)    │
├──────────────────────────────────────────┤
│       Storage Device (Disk/SSD)          │
└──────────────────────────────────────────┘

┌────────┬───────────┬──────────┬──────────┬─────────────────┐
│ Boot   │ Super     │ Free     │ inode    │ Data Blocks     │
│ Block  │ Block     │ Space    │ Table    │                 │
│        │           │ Mgmt     │          │                 │
│ Boot   │ Meta      │ Bitmap/  │ File     │ Actual file     │
│ loader │ data      │ list     │ meta     │ data            │
└────────┴───────────┴──────────┴──────────┴─────────────────┘

┌─────────────────────────────────────┐
│           inode Structure            │
├─────────────────────────────────────┤
│ File type, permissions (mode)       │
│ Owner (uid, gid)                    │
│ Size                                │
│ Timestamps (atime, mtime, ctime)    │
│ Link count                          │
│ Block count                         │
├─────────────────────────────────────┤
│ Direct block pointers [0-11] → data │
│ Single indirect pointer → ptr block │
│ Double indirect pointer → ptr^2     │
│ Triple indirect pointer → ptr^3     │
└─────────────────────────────────────┘

// 간단화된 inode 구조체 (ext2 기반)
struct inode {
    uint16_t mode;        // 파일 유형 + 권한
    uint16_t uid;         // 소유자 ID
    uint32_t size;        // 파일 크기
    uint32_t atime;       // 접근 시간
    uint32_t mtime;       // 수정 시간
    uint32_t ctime;       // 상태 변경 시간
    uint16_t gid;         // 그룹 ID
    uint16_t links_count; // 하드 링크 수
    uint32_t blocks;      // 할당된 블록 수

    uint32_t direct[12];          // 직접 블록 포인터
    uint32_t single_indirect;     // 단일 간접 포인터
    uint32_t double_indirect;     // 이중 간접 포인터
    uint32_t triple_indirect;     // 삼중 간접 포인터
};

┌───────────────────────────────────────────────┐
│              Kernel Memory                     │
│                                               │
│  ┌─────────────────┐  ┌───────────────────┐   │
│  │ Mount Table     │  │ Directory Cache   │   │
│  │ (FS list)       │  │ (recent paths)    │   │
│  └─────────────────┘  └───────────────────┘   │
│                                               │
│  ┌─────────────────┐  ┌───────────────────┐   │
│  │ System-wide     │  │ Per-process       │   │
│  │ Open File Table │  │ Open File Table   │   │
│  └─────────────────┘  └───────────────────┘   │
│                                               │
│  ┌─────────────────┐                          │
│  │ Buffer Cache    │ ← Disk block cache       │
│  └─────────────────┘                          │
└───────────────────────────────────────────────┘

           User Process
        open() read() write()
               │
    ┌──────────┴──────────┐
    │         VFS          │
    │  (Virtual File       │
    │   System)            │
    │  vnode interface     │
    └──┬──────┬──────┬─────┘
       │      │      │
    ┌──┴──┐┌──┴──┐┌──┴──┐
    │ext4 ││NFS  ││FAT  │
    │     ││     ││     │
    └──┬──┘└──┬──┘└──┬──┘
       │      │      │
    Local  Network  USB
    disk   server   drive

// VFS 추상화의 주요 객체 (Linux 기반 의사 코드)

// 1. 슈퍼블록 객체: 파일 시스템 인스턴스 정보
struct super_block {
    struct list_head s_list;       // 슈퍼블록 목록
    dev_t            s_dev;        // 장치 식별자
    unsigned long    s_blocksize;  // 블록 크기
    struct super_operations *s_op; // 연산 테이블
    // ...
};

// 2. inode 객체: 개별 파일 정보
struct inode {
    umode_t          i_mode;       // 파일 유형 + 권한
    uid_t            i_uid;        // 소유자
    loff_t           i_size;       // 파일 크기
    struct inode_operations *i_op; // inode 연산
    struct file_operations  *i_fop;// 파일 연산
    // ...
};

// 3. dentry 객체: 디렉토리 엔트리 (경로명 컴포넌트)
struct dentry {
    struct inode     *d_inode;     // 관련 inode
    struct dentry    *d_parent;    // 부모 디렉토리
    struct qstr      d_name;      // 엔트리 이름
    struct dentry_operations *d_op;
    // ...
};

// 4. file 객체: 열린 파일 인스턴스
struct file {
    struct dentry    *f_dentry;    // 관련 dentry
    loff_t           f_pos;       // 현재 오프셋
    unsigned int     f_flags;     // 열기 플래그
    struct file_operations *f_op; // 파일 연산
    // ...
};

Directory Block:
┌──────────┬────────┬──────────┬────────┬──────────┬────────┐
│ "file1"  │ inode  │ "file2"  │ inode  │ "file3"  │ inode  │
│          │  23    │          │  47    │          │  12    │
└──────────┴────────┴──────────┴────────┴──────────┴────────┘

Search: O(n) - sequential scan from beginning
Advantage: Simple implementation
Disadvantage: Slow for large directories

Hash function: hash("filename") → bucket index

Bucket 0: ["file_a", inode 23] → ["file_d", inode 89] → NULL
Bucket 1: ["file_b", inode 47] → NULL
Bucket 2: NULL
Bucket 3: ["file_c", inode 12] → ["file_e", inode 56] → NULL
...

Search: O(1) average (linked list traversal on collision)
Advantage: Fast lookup
Disadvantage: Fixed size, collision management required

Directory Entry:
┌────────┬───────────┬──────┐
│ Name   │ Start Blk │ Len  │
├────────┼───────────┼──────┤
│ file_a │    2      │  3   │
│ file_b │    7      │  2   │
│ file_c │   14      │  4   │
└────────┴───────────┴──────┘

Disk Blocks:
 0  1 [2  3  4] 5  6 [7  8] 9 10 11 12 13 [14 15 16 17]
         file_a          file_b                file_c

Directory:
┌────────┬──────┬──────┐
│ Name   │Start │ End  │
├────────┼──────┼──────┤
│ file_a │  9   │  1   │
└────────┴──────┴──────┘

Disk Blocks (each block contains next block pointer):
Block 9 → Block 16 → Block 25 → Block 1 → NULL
[data|16] [data|25] [data|1]  [data|-1]

FAT Table (cached in memory):
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │  5  │  6  │ ← Block number
├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│  3  │ EOF │  5  │  4  │ EOF │  1  │ FREE│ ← Next block
└─────┴─────┴─────┴─────┴─────┴─────┴─────┘

File A: start=0 → 0→3→4→EOF (blocks 0, 3, 4)
File B: start=2 → 2→5→1→EOF (blocks 2, 5, 1)

Directory:
┌────────┬─────────────┐
│ Name   │ Index Block │
├────────┼─────────────┤
│ file_a │     19      │
└────────┴─────────────┘

Index Block 19:          Data Blocks:
┌─────────────┐          Block 9:  [data...]
│  9          │ ────→    Block 16: [data...]
│ 16          │ ────→    Block 25: [data...]
│ 25          │ ────→    Block 1:  [data...]
│  1          │ ────→
│ -1 (end)    │
└─────────────┘

Block number: 0  1  2  3  4  5  6  7  8  9  10 11 12
Bitmap:       1  1  0  1  1  0  0  1  0  0  0  1  0

1 = in use, 0 = free

Finding free blocks: search for first 0 bit in bitmap
Advantage: Easy to find contiguous free space
Disadvantage: Bitmap grows large for big disks
      (1TB disk, 4KB blocks → 32MB bitmap)

// 비트맵에서 빈 블록 찾기
int find_free_block(uint32_t *bitmap, int total_blocks) {
    int words = total_blocks / 32;
    for (int i = 0; i < words; i++) {
        if (bitmap[i] != 0xFFFFFFFF) {  // 모두 사용 중이 아니면
            // 첫 번째 0 비트 위치 찾기
            for (int j = 0; j < 32; j++) {
                if (!(bitmap[i] & (1 << j))) {
                    return i * 32 + j;
                }
            }
        }
    }
    return -1;  // 빈 블록 없음
}

Free Space Head → Block 2 → Block 5 → Block 6 → Block 8 → NULL

Each free block points to the next free block
Advantage: Simple implementation
Disadvantage: Hard to find contiguous free space, traversal cost

Without TRIM:                    With TRIM:
1. File delete → meta only      1. File delete → meta remove
2. SSD unaware block is free    2. TRIM command notifies SSD
3. On later write:              3. SSD erases block in advance
   Read → Erase → Write needed  4. On later write: write directly
   (write perf degradation)        (write perf maintained)

Normal write (no journaling):
1. Write data blocks
2. Update inode
3. Update bitmap
→ Crash at step 2 causes inconsistency!

Journaled write:
┌──────────────────────────────────────┐
│          Journal Area (Log)          │
│                                      │
│  1. Transaction Begin (TxB)         │
│  2. Record metadata changes          │
│  3. Transaction Commit (TxE)        │
│                                      │
│  → Apply to actual location after    │
│    commit                            │
│  → Delete journal after apply        │
└──────────────────────────────────────┘

// 저널링 트랜잭션 의사 코드
void journaled_write(struct transaction *tx) {
    // 1. 저널에 트랜잭션 시작 기록
    journal_write_begin(tx);

    // 2. 변경할 메타데이터를 저널에 기록
    journal_write_metadata(tx, inode_data);
    journal_write_metadata(tx, bitmap_data);

    // 3. 저널에 트랜잭션 커밋 기록
    journal_write_commit(tx);

    // 4. 실제 파일 시스템 위치에 적용 (체크포인트)
    write_to_actual_location(inode_data);
    write_to_actual_location(bitmap_data);

    // 5. 저널에서 트랜잭션 제거
    journal_free(tx);
}

// 복구 시: 커밋된 트랜잭션은 재실행, 미커밋은 무시
void recover_from_crash() {
    for_each_transaction(journal) {
        if (transaction_committed(tx))
            replay_transaction(tx);  // 재실행
        else
            discard_transaction(tx); // 폐기
    }
}