Lỗi trong một trình giả lập ext2 để dạy học, và bộ test giữ chúng không quay lại

Một hệ thống file dùng để dạy học có thể trông đúng suốt nhiều năm, vì bản demo chỉ tạo vài file nhỏ. Lỗi chỉ lộ ra khi bạn bắt đầu đếm: số block trống so với bitmap, số byte ghi so với số byte đọc lại, số entry tạo ra so với số entry liệt kê được. Bài này đi qua các lỗi mình sửa trong một trình giả lập kiểu ext2 viết bằng C, và mỗi lỗi dạy gì về hệ thống file dạng block. Sau đó là ba loại test giờ giữ cho chúng không quay lại: một bước kiểm tra nhất quán theo kiểu e2fsck, fault injection ở từng thao tác đĩa, và một fuzzer so mọi kết quả với một model trong bộ nhớ.

Code là ext2-filesystem-simulator của mình, bản viết lại bằng C23 của một trình giả lập mã nguồn mở, vốn phát triển từ code ví dụ của một cuốn sách về cấu trúc bên trong nhân Linux. Nó gồm một ổ đĩa 256 MiB nằm trong bộ nhớ và một shell nhỏ (format, mkdir, fill, cat, rm...). Mình chép nó về lần đầu năm 2023 và viết lại vào tháng 10/2026, tổng cộng mười một bản sửa, mỗi bản kèm một regression test. Tác giả gốc được ghi công trong repo; code ban đầu được viết để minh hoạ cấu trúc, không phải để chịu tải nặng.

Cấu trúc đĩa trong một bảng

Đĩa có 262.145 block, mỗi block 1 KiB, chia thành 32 nhóm (group), mỗi nhóm 8.192 block. Một nhóm có 8.192 block vì một block bitmap 1 KiB theo dõi được 8 × 1.024 block. Nhóm nào cũng bắt đầu bằng cùng một phần metadata, giống cấu trúc của ext2 thật:

Hai điều từ bảng này giải thích phần lớn các lỗi bên dưới. Dung lượng trống được ghi ở ba nơi: trong bitmap, trong số đếm block trống của từng group descriptor, và trong tổng của superblock. Và số hiệu block nào cũng phải đổi ra "nhóm nào, bit nào", đúng chỗ phép tính hay sai.

Một macro thiếu ngoặc ngoài cùng đã ghi vào block dữ liệu

Xoá một file thì phải xoá bit của từng block của nó trong block bitmap của đúng nhóm. Code gốc tìm bitmap đó như sau:

#define GET_DATA_GROUP(x) ((x) - 1)/(BLOCKS_PER_GROUP)

block_read(disk, BLOCKS_PER_GROUP * GET_DATA_GROUP(b) + BLOCK_BITMAP_BASE, block);

Thân macro không có ngoặc bao ngoài, nên sau khi mở rộng, phép nhân chạy trước: BLOCKS_PER_GROUP * ((b) - 1) / BLOCKS_PER_GROUP, tức là chỉ còn b - 1. Thay vì đọc block bitmap của nhóm chứa file, rm đọc block b - 1 + 3, block dữ liệu nằm sau block đang được giải phóng hai vị trí, lật một bit trong đó rồi ghi lại. Hệ thống file không hề crash: nó làm hỏng nội dung của một file khác, và block vừa giải phóng vẫn bị đánh dấu là đang dùng, trong khi superblock lại đếm nó là trống.

Đây đúng là lý do kinh điển khiến tài liệu preprocessor của GCC khuyên đặt ngoặc cho cả tham số lẫn toàn bộ biểu thức mở rộng. Bản viết lại làm cả hai, và tính nhóm ở đúng một chỗ:

#define GET_DATA_GROUP(x) ((x) / BLOCKS_PER_GROUP)

Bộ cấp phát chỉ biết tới 2.048 block

Đĩa báo đầy khi mới dùng khoảng 1,5 MiB. Bộ cấp phát block quét bitmap bằng vòng lặp này:

for (i = 0; i < fs->sb.block_per_group && i < MAX_BLOCK_SIZE / 4; i++)

MAX_BLOCK_SIZE / 4 là 256 byte bitmap, tức 2.048 bit. Bitmap được đọc lúc nào cũng là bitmap của nhóm chứa superblock, tức nhóm 0. Trừ 517 block metadata ở đầu nhóm đó, chỉ khoảng 1.500 block dữ liệu từng được dùng tới, trên một đĩa 262.145 block. Hết số đó, hàm trả về 0, và nơi gọi coi đó là một số hiệu block hợp lệ: block 0 của đĩa.

Bản sửa tìm trong mọi nhóm, và hết chỗ thì trả về lỗi. Regression test của nó ghi 12 thư mục × 300 file × 12 KiB, khoảng 42 MiB, rồi kiểm block đầu tiên của file cuối cùng rơi vào nhóm 5.

Giải phóng bằng XOR thì làm lại hai lần sẽ ra kết quả khác

Bit được bật và tắt bằng cùng một phép toán:

b_bitmap->block_bitmap[index] ^= (0x80 >> (bit % 8));

XOR là phép đảo. Giải phóng một block vốn đã trống sẽ đánh dấu nó là đang dùng, và không có gì báo ra. Với lỗi macro ở trên, chuyện đó không chỉ là giả thuyết. Bản viết lại tách riêng set_bit và clear_bit, và từ chối giải phóng một block đã trống:

if (!test_bit(bitmap, bit))
    return EXT2_ERROR; /* already free: refuse instead of flipping it back to used */
clear_bit(bitmap, bit);

Giải phóng hai lần là triệu chứng cho thấy metadata đã không nhất quán từ trước. Báo lỗi ra có ích hơn là lặng lẽ làm nó tệ thêm.

Các bản sửa còn lại

Các lỗi còn lại nhỏ hơn, nhưng gặp trên đĩa thật thì lỗi nào cũng là một buổi debug dài:

• Thư mục vượt quá một block thì mất entry. Khi block đầu của một thư mục đầy, một block mới được cấp nhưng không bao giờ được gắn vào inode của thư mục, nên các entry từ thứ 29 trở đi biến mất khỏi ls và lookup.
• Struct superblock dài 1.020 byte nhưng được chép như 1.024 byte, đè lên trường kế tiếp. Kích thước struct giờ được kiểm lúc biên dịch: static_assert(sizeof(EXT2_SUPER_BLOCK) == MAX_BLOCK_SIZE, ...), và tương tự cho inode, descriptor và entry.
• cat bị crash, vì đường đọc truyền đối tượng hệ thống file vào chỗ cần đối tượng đĩa. Đọc và ghi giờ xử lý được mọi offset và độ dài.
• Bộ nhớ chưa khởi tạo: inode gốc được dựng từ rác trên stack, lệnh format ghi một inode bitmap vào nhóm do một biến chưa khởi tạo chọn, và tên dài hơn 8.3 làm tràn buffer.
• Shell: exit gọi _exit nên mất output còn trong buffer, và hết input thì shell lặp lại lệnh cuối mãi mãi.

Biên dịch với -Wall -Wextra -Wpedantic -Wconversion coi như lỗi, gắn [[nodiscard]] cho mọi hàm trả về trạng thái, và chạy AddressSanitizer cùng UBSan trong preset debug sẽ chặn được nguyên cả nhóm lỗi kiểu này.

Test 1: đếm lại mọi bitmap sau mỗi test

e2fsck kiểm tra hệ thống file theo từng lượt (pass); pass 5 so bitmap với các số đếm mà metadata khai báo. Mọi test của trình giả lập đều kết thúc bằng đúng phép so đó:

bitmapFreeBlocks = BLOCKS_PER_GROUP - count_bits(block, BLOCKS_PER_GROUP);
if (gd->free_blocks_count != bitmapFreeBlocks || gd->free_inodes_count != bitmapFreeInodes)
    ok = false;
/* ...then the sum over all groups must equal the superblock's totals */

Nó dài khoảng 60 dòng, và lẽ ra đã bắt được lỗi macro ngay ở test đầu tiên có xoá file, vì block được giải phóng vẫn còn bit bật trong bitmap trong khi superblock đếm nó là trống. Kiểm một bất biến sẽ bắt được những lỗi chưa ai viết test cho, nên mọi test đều gọi nó, không riêng các test về cấp phát.

Test 2: cho đĩa hỏng lần lượt ở từng thao tác

Đĩa nằm sau một interface đọc/ghi, nên test có thể thay vào một đĩa sẽ hỏng sau một "ngân sách" số thao tác sector. Một kịch bản gồm các bước bình thường (format, mount, mkdir, tạo file, ghi, đọc, xoá) được chạy một lần để đếm số thao tác, rồi chạy lại với chỗ hỏng đặt ở thao tác 0, 1, 2 và cứ thế tới hết:

for (budget = 0; budget < total; budget++) {
    g_budget = -1;                    /* format on a healthy disk */
    CHECK(ext2_format(&disk) == EXT2_SUCCESS);
    g_budget = budget;                /* then fail at this operation */
    steps = run_scenario(&disk);
    CHECK(steps < completeSteps);     /* the failure must surface as an error */
}

Bước nào cũng phải trả về lỗi thay vì crash, và sanitizer canh chừng mọi lần đọc vào vùng nhớ code không được chạm. Điều này quan trọng vì code gốc bỏ qua phần lớn kết quả của block_read và block_write; set_block_bitmap khai báo trả về int mà không có lệnh return nào.

Test 3: một fuzzer có model về những gì lẽ ra phải có

Fuzzer đọc input như một chuỗi thao tác (mkdir, rmdir, tạo file, ghi, đọc lại, rm) trên bốn tên thư mục và tám tên file. Bên cạnh hệ thống file thật, nó giữ một model: thư mục nào đang tồn tại, và với mỗi file thì kích thước cùng các byte của nó. Sau mỗi thao tác, fuzzer kiểm hai điều.

Thứ nhất, cả thành công lẫn thất bại đều phải khớp với model. Tạo file phải thành công khi và chỉ khi thư mục cha tồn tại và file chưa có:

FUZZ_ASSERT((result == EXT2_SUCCESS) == (parentExists && !file->exists), "create %u/%s", p, name);

Chỉ kiểm rằng các lần thành công cho kết quả đúng sẽ bỏ sót những lỗi mà thao tác thất bại khi lẽ ra phải thành công, hoặc thành công khi lẽ ra phải từ chối, chẳng hạn ghi quá 12 KiB mà một file chứa được.

Thứ hai, bitmap vẫn phải khớp với các số đếm, bằng đúng phép kiểm ở trên. Mỗi lần đọc lại thì so từng byte với model.

Khi chạy dưới ctest, fuzzer chạy lại một bộ corpus nhỏ gồm các input đã lưu, cộng 200 input ngẫu nhiên; với Clang nó được build thành một target của libFuzzer, và CI fuzz hai phút ở mỗi lần chạy.

Những gì các test này không bao phủ

• Tính nhất quán sau khi hỏng. Fault injection kiểm rằng lỗi được báo ra, không kiểm đĩa còn nhất quán sau đó. Không có journal, một lần ghi hỏng giữa chừng một thao tác có thể làm lệch các số đếm, y như trên ext2 thật.
• Chỉ đếm, không kiểm khả năng truy tới. Bộ kiểm tra làm việc của pass 5. Nó không duyệt cây thư mục để tìm block được đánh dấu đang dùng nhưng không thuộc inode nào, là việc của các pass trước đó trong e2fsck.
• Model chỉ biết những gì nó theo dõi. Tên, kích thước và nội dung được kiểm; timestamp và số link thì không.
• Định dạng trên đĩa không phải ext2. Entry thư mục là bản ghi cố định 32 byte với tên 8.3, và file chỉ dùng direct block, nên mỗi file chứa tối đa 12 KiB.

Tóm tắt

Nếu bạn từng test một tầng lưu trữ bằng fuzzer dựa trên model, mình rất muốn được trao đổi xem model của bạn theo dõi những gì. Email của mình ở trang chủ.