blog.dopana

Quay lại

Trong bài viết trước, chúng ta đã tìm hiểu về triết lý đột phá của Goose: một ngôn ngữ hệ thống hoàn toàn loại bỏ vùng nhớ Heap truyền thống, không cần bộ thu gom rác (Garbage Collector), và tự động giải phóng bộ nhớ trên các Data Stacks theo phạm vi từ vựng (lexical scope).

Tuy nhiên, bất kỳ kỹ sư hệ thống nào khi nghe đến mô hình này cũng sẽ lập tức đặt ra câu hỏi then chốt:

“Nếu mọi thứ đều bị giải phóng khi kết thúc scope trên Data Stack, làm thế nào để xây dựng các cấu trúc dữ liệu có vòng đời không lồng nhau (non-nested lifetimes)? Làm sao để viết một cây thư mục mà các file có thể thêm/xóa tùy ý, một đồ thị có chu trình (cyclic graph), hệ thống thực thể game (ECS), hay một bộ nhớ đệm LRU Cache?”

Trong C và C++, lập trình viên giải quyết bài toán này bằng malloc/free, chấp nhận nguy cơ dính lỗi Use-After-Free (UAF) và phân mảnh bộ nhớ. Trong Rust, người ta phải dùng Rc<RefCell<T>>, Arc<Mutex<T>> hoặc các thư viện phụ trợ như SlotMap đi kèm chỉ số NodeId.

Goose đưa ra một câu trả lời kiến trúc thanh lịch và cực kỳ an toàn: Memory Pools (slot_pool<T> và slice_pool<T>).

1. Bản chất vấn đề: Khi vòng đời dữ liệu không tuân theo Scope#

Hãy hình dung một hệ thống cây thư mục (File Tree) trong thực tế:

/ (root)
├─bin/
│   ├─app
│   └─util
└─docs/
  └─readme.md
text

Bạn có thể tạo thư mục docs/, sau đó tạo thư mục bin/, rồi xóa docs/readme.md, rồi lại thêm bin/tools. Thời điểm sinh ra và thời điểm bị xóa của từng node hoàn toàn độc lập, không tuân theo thứ tự LIFO (vào sau ra trước) của ngăn xếp hàm.

Nếu chỉ có Data Stack thuần túy:

  • Bạn không thể xóa node ở giữa mảng đang co giãn mà không làm xáo trộn các node phía sau.
  • Bạn không thể thu hồi từng phần tử riêng lẻ khi các phần tử khác vẫn đang sống.

Đây chính là lý do Goose bổ sung hai cấu trúc nền tảng trong thư viện chuẩn: slot_pool<T> và slice_pool<T>.

2. Kiến trúc hai tầng Pool: slot_pool và slice_pool#

slot_pool: Quản lý Node cố địnhslice_pool: Quản lý Slice danh sách conslice_pool: Quản lý Slice danh sách conRelative Reference: Link u32 innodesMảng Items (Node[>..] trênData Stack)Freelist (Danh sách chỉ số Slottrống)alloc_ref: Tái sử dụng Slot hoặcPush mớifree: Trả chỉ số Slot về FreelistBuffer chứa danh sách liên kết(Link[>..])Freelist các đoạn Span (Tựđộng gộp)alloc_slice hoặc realloc_slice

1. slot_pool<T>: Quản lý các phần tử kích thước cố định#

  • Kết hợp một mảng tăng trưởng (T[>..]) nằm trên Data Stack với một danh sách các slot trống (freelist).
  • alloc_ref(value): Nếu trong freelist có slot đã từng bị xóa, nó sẽ tái sử dụng ngay slot đó. Nếu không còn slot trống, nó sẽ tịnh tiến con trỏ mảng (push) để tạo phần tử mới.
  • free(slot): Không hề trả bộ nhớ về cho hệ điều hành! Nó chỉ đơn giản đánh dấu chỉ số slot đó vào freelist để sẵn sàng tái sử dụng cho lần alloc_ref kế tiếp.

2. slice_pool<T>: Quản lý các chuỗi phần tử liên tục co giãn#

  • Dùng cho các danh sách con có độ dài biến động (ví dụ: danh sách các file con nằm trong một thư mục).
  • Hỗ trợ các hàm: alloc_slice(n), realloc_slice(s, n), và free_slice(s).
  • Khi một slice được giải phóng, slice_pool sẽ tự động gộp các đoạn trống liền kề (adjacent span merging) để chống phân mảnh bộ nhớ mà không cần can thiệp của OS.

3. Bí mật an toàn: Type-Safe Reuse (Tái sử dụng an toàn kiểu)#

Điểm nguy hiểm nhất của free() trong C/C++ là gì? Khi bạn giải phóng bộ nhớ, vùng nhớ đó có thể được OS bàn giao cho một tiến trình khác hoặc dùng để lưu một kiểu dữ liệu hoàn toàn khác. Nếu chương trình còn sót lại một con trỏ cũ (stale pointer) và đọc vào đó, hậu quả sẽ là Segfault hoặc lỗ hổng thực thi mã độc từ xa (RCE).

Goose giải quyết triệt để rủi ro này bằng triết lý Type-Safe Reuse:

Goose slot_pool: Tái sử dụng an toàn kiểuC / C++: Dangling Pointer và CrashCấp phát Node (malloc)Giải phóng Node (free)Vùng nhớ bị OS thu hồi hoặctái cấp phát cho kiểu khácĐọc con trỏ cũ: Segfault hoặcLỗ hổng bảo mật UAFCấp phát Slot (alloc_ref)Trả Slot về Freelist (free)Bộ nhớ vẫn nằm nguyên vẹntrên Data StackĐọc tham chiếu cũ: Nhận dữliệu Node hợp lệ kiểu T (Antoàn)

[!TIP] Quy tắc an toàn của Goose: Bộ nhớ của slot không bao giờ bị trả về cho hệ điều hành chừng nào pool còn tồn tại. Do đó, nếu bạn lỡ đọc vào một tham chiếu cũ trỏ tới slot đã bị free, bạn sẽ chỉ đọc thấy một giá trị khác nhưng luôn thuộc kiểu dữ liệu hợp lệ T. Đây có thể là một lỗi logic (logic bug), nhưng tuyệt đối không bao giờ là lỗi phá hủy bộ nhớ (memory corruption) hay lỗi tràn bộ đệm!

4. Thực chiến: Xây dựng Cây thư mục N-ary (26_file_tree.goose)#

Hãy xem mã nguồn kinh điển trích từ bộ sample của Goose để thấy cách hai pool phối hợp nhịp nhàng:

Phân tích kiến trúc#

  1. Liên kết siêu hẹp 4 bytes (Node&<u32 in nodes>?): Thay vì tốn con trỏ 8 bytes, liên kết giữa cha và con chỉ tốn đúng 4 bytes (offset 32-bit tính từ đầu pool nodes). Giá trị 0 được quy ước là null (?).
  2. Danh sách con duyệt liên tục: Mỗi thư mục sở hữu entries: Link[:]. Khi duyệt qua các file con của một thư mục, CPU duyệt qua một slice phẳng liền mạch trong RAM, đạt tốc độ truyền tải tối đa trên bộ nhớ đệm cache L1/L2.
  3. Mở rộng tại chỗ (In-Place Growth): Hàm realloc_slice sẽ mở rộng slice tại chỗ nếu phía sau nó còn dung lượng trống. Nếu bị cấn dữ liệu khác, nó sẽ chuyển toàn bộ run sang vị trí mới và đưa đoạn cũ vào freelist để gộp lại.
  4. Không có bất kỳ malloc hay free nào từ hệ điều hành: Toàn bộ cây thư mục hàng triệu file sống hoàn toàn trên 2 Data Stack được định nghĩa sẵn. Khi toàn bộ tác vụ xử lý cây thư mục hoàn tất, hai pool kết thúc scope, toàn bộ cây được dọn sạch trong 2 CPU cycles!

5. Xây dựng đồ thị có chu trình (Cyclic Graphs)#

Trong Rust, việc xây dựng đồ thị có chu trình (A trỏ tới B, B trỏ tới C, C trỏ ngược về A) là bài toán “ác mộng” vì vi phạm quy tắc mượn duy nhất (Borrow Checker). Trong C++, nó rất dễ gây rò rỉ bộ nhớ nếu dùng smart pointer std::shared_ptr.

Trong Goose, đồ thị có chu trình trở nên cực kỳ tự nhiên:

Mọi node đều nằm trong pool vertices, mọi liên kết đều nằm trong pool edges. Không có bộ đếm tham chiếu (reference counting), không có GC chu kỳ, và tuyệt đối không bao giờ rò rỉ bộ nhớ.

6. So sánh kỹ thuật: Quản lý đồ thị giữa các ngôn ngữ#

Tiêu chíC++ (std::shared_ptr)Rust (Rc<RefCell<T>>)Rust (SlotMap + Id)Goose (slot_pool + slice_pool)
Cú pháp sử dụngPhức tạp, dễ rò rỉ chu trìnhRất rườm rà, dễ panic runtimePhải tra cứu ID gián tiếpTự nhiên, dùng toán tử .=
Kích thước liên kết16 bytes (pointer + control block)16 bytes8 bytes (Index + Generation)4 bytes (Node&<u32>)
Chi phí cấp phát1 lần heap / node1 lần heap / nodeCấp phát mảng phụ trợPointer bump (O(1)O(1))
Chi phí giải phóngGiảm ref count tuần tựGiảm ref count tuần tựXóa mảng1 lệnh CPU Store khi hết scope
Bảo vệ rò rỉ chu trình❌ Bị rò rỉ nếu thiếu weak_ptr❌ Bị rò rỉ nếu thiếu Weak✅ Tự động dọn khi drop Map✅ Tuyệt đối không rò rỉ

7. Tổng kết#

Mô hình Memory Pools trong Goose chứng minh rằng một ngôn ngữ lập trình không nhất thiết phải đánh đổi giữa sự tự do cấu trúc và sự an toàn bộ nhớ:

  1. Không cần Garbage Collector để dọn dẹp các đồ thị phức tạp.
  2. Không cần Borrow Checker phức tạp hóa việc liên kết dữ liệu giữa các node.
  3. Không cần Heap Allocator của hệ điều hành với chi phí phân mảnh và khóa tranh chấp (lock contention).

Bằng cách kết hợp Data Stacks tĩnh, slot_pool, và liên kết tương đối 4-byte, Goose mang lại giải pháp hoàn hảo cho việc xây dựng các hệ thống đòi hỏi cấu trúc dữ liệu linh hoạt, kích thước cực kỳ nhỏ gọn và hiệu năng xử lý cache ở đẳng cấp cao nhất.

Tài Liệu Tham Khảo#