Goose Memory Pools: Xây dựng đồ thị và cây không cần Heap
Cách Goose xử lý cấu trúc dữ liệu phức tạp như đồ thị, cây thư mục và bộ nhớ đệm thông qua slot_pool và slice_pool mà không cần heap allocator hay GC.
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.mdtextBạ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#
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ầnalloc_refkế 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_poolsẽ 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:
[!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:
// Định nghĩa liên kết hẹp 4-byte trỏ vào pool 'nodes'
type Link = Node&<u32 in nodes>?;
struct Node {
name: u8[..15], // Tên cố định tối đa 15 ký tự (nằm inline)
entries: Link[:], // Slice liên tục chứa các liên kết tới node con
}
// Khởi tạo hai memory pool
reusable var nodes: Node[>..] = [];
reusable[] var runs: Link[>..] = [];
// Hàm tạo node mới trong pool
fn make(name: u8[:]) -> Node& {
return nodes.alloc_ref(Node {
name: name,
entries: runs.alloc_slice(0)
});
}
// Tạo thư mục gốc root
let root .= make("/");
// Thêm liên kết con vào thư mục cha
fn link(dir: Node&, n: Node&) {
let k = dir.entries.len;
// Mở rộng slice chứa các entry con trong runs pool
dir.entries = runs.realloc_slice(dir.entries, k + 1);
dir.entries[k] .= n;
}
// Thêm thư mục hoặc file con
fn add(dir: Node&, name: u8[:]) -> Node& {
let n .= make(name);
link(dir, n);
return n;
}
// Sử dụng:
let home .= add(root, "home");
let user .= add(home, "alice");
let doc .= add(user, "project.txt");rustPhân tích kiến trúc#
- 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 poolnodes). Giá trị 0 được quy ước là null (?). - 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. - Mở rộng tại chỗ (In-Place Growth):
Hàm
realloc_slicesẽ 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. - Không có bất kỳ
mallochayfreenà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:
struct Vertex {
id: i32,
neighbors: VertexLink[:]
}
type VertexLink = Vertex&<u32 in vertices>?;
reusable var vertices: Vertex[>..] = [];
reusable[] var edges: VertexLink[>..] = [];
fn create_vertex(id: i32) -> Vertex& {
return vertices.alloc_ref(Vertex {
id: id,
neighbors: edges.alloc_slice(0)
});
}
fn add_edge(from: Vertex&, to: Vertex&) {
let k = from.neighbors.len;
from.neighbors = edges.realloc_slice(from.neighbors, k + 1);
from.neighbors[k] .= to;
}
// Tạo chu trình tam giác: A -> B -> C -> A
let vA .= create_vertex(1);
let vB .= create_vertex(2);
let vC .= create_vertex(3);
add_edge(vA, vB);
add_edge(vB, vC);
add_edge(vC, vA); // Chu trình hoàn toàn hợp lệ, không lỗi compile!rustMọ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ụng | Phức tạp, dễ rò rỉ chu trình | Rất rườm rà, dễ panic runtime | Phải tra cứu ID gián tiếp | Tự nhiên, dùng toán tử .= |
| Kích thước liên kết | 16 bytes (pointer + control block) | 16 bytes | 8 bytes (Index + Generation) | 4 bytes (Node&<u32>) |
| Chi phí cấp phát | 1 lần heap / node | 1 lần heap / node | Cấp phát mảng phụ trợ | Pointer bump () |
| Chi phí giải phóng | Giảm ref count tuần tự | Giảm ref count tuần tự | Xóa mảng | 1 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ớ:
- Không cần Garbage Collector để dọn dẹp các đồ thị phức tạp.
- 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.
- 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.