Tự Tay Xây Dựng Một Bộ Thu Gom Rác Cho Ngôn Ngữ C

Dịp Tết Đoan Ngọ vừa qua, giải đấu Euro Cup cũng chính thức khởi tranh. Để giữ tỉnh táo xuyên đêm theo dõi bóng đá, tôi đã chọn cách “giết thời gian” bằng việc viết một chương trình thử nghiệm. Thành quả ba ngày qua chính là một bộ thu gom rác (garbage collector - GC) dành riêng cho ngôn ngữ C. Cảm giác khá thú vị khi hoàn thành!

Thực ra ý tưởng về GC cho C/C++ không phải mới mẻ. Ví dụ như dự án tham khảo này đã từng thực hiện. Tuy nhiên phương pháp dự đoán con trỏ dựa trên heuristic khiến nhiều người lo ngại về độ tin cậy và hiệu suất thu gom. Tôi muốn xây dựng một giải pháp thuần túy hơn - một module GC với giao diện đơn giản nhưng hiệu quả cao.

Sau ba ngày phát triển, phiên bản đầu đã hoàn thành. Hiện tôi đang cân nhắc việc open-source trên SourceForge. Trước mắt cần hoàn thiện thêm kiểm thử (có thể bổ sung hỗ trợ đa luồng) rồi mới quyết định.

Mục tiêu thiết kế và định hướng triển khai

1. Chiến lược thu gom: Sử dụng thuật toán đánh dấu và xóa (mark-sweep) - phương pháp được cộng đồng công nhận hiệu quả nhất hiện nay, vượt trội so với kỹ thuật đếm tham chiếu như boost::smart_ptr.
2. Giao diện đơn giản: Người dùng chỉ cần quan tâm đến mối liên kết giữa các đối tượng, không cần xử lý các chi tiết phức tạp.
3. Hiệu suất tối ưu: Ngoại trừ quá trình thu gom, mọi API đều yêu cầu độ phức tạp gần O(1).

Phân tích điểm yếu của GC truyền thống

Hầu hết các GC hiện tại đều yêu cầu gắn metadata (dữ liệu quản lý) vào vùng nhớ cấp phát - bao gồm các cờ hiệu và thông tin liên kết. Khi lượng bộ nhớ lớn hơn RAM vật lý, quy trình đánh dấu sẽ gây ra hiện tượng thrashing (hoán đổi bộ nhớ ảo dữ liệu liên tục). Mỗi khối nhớ đều phải được truy cập và cập nhật cờ, dù có cần thiết hay không.

Tôi đã cải tiến bằng cách tách biệt hoàn toàn dữ liệu quản lý khỏi vùng nhớ người dùng. Quá trình thu gom chỉ thao tác trên metadata tập trung, chỉ giải phóng vùng nhớ vật lý khi thực sự cần thiết.

Giải pháp quản lý bộ nhớ ngăn xếp

Điểm mấu chốt của GC là theo dõi các biến cục bộ trên ngăn xếp. Khi thu gom, các vùng nhớ tạm thời không được giải phóng. Vì C không hỗ trợ duyệt ngăn xếp tự động, tôi thiết kế cơ chế “bảo vệ” (guard) tại các điểm vào/ra hàm để thiết lập mối liên kết.

Cụ thể:

• Mỗi cấp độ gọi hàm sẽ có điểm neo riêng. Khi hàm trả về, các vùng nhớ tạm thời sẽ tự động ngắt liên kết với gốc.
• Nếu vùng nhớ được trả về như kết quả hàm, nó sẽ được giữ lại thông qua tham số của gc_leave.

Giao diện API chính

Thư viện cung cấp 5 hàm thiết yếu:

1
2
3
4
5

void *gc_malloc(size_t sz, void (*free)(const void *));
void gc_link(const void *parent, const void *prev, const void *child);
void gc_enter();
void gc_leave(const void *value, ... );
void gc_collect();

Ví dụ minh họa:

1
2
3
4
5
6
7
8
9

struct tree *foo() {
  struct tree *t;
  gc_enter();  // Bắt đầu khối bảo vệ
  t = new_node();
  EVAL(t, left, new_node());  // Tự động liên kết
  EVAL(t, right, new_node());
  gc_leave(t, 0);  // Giữ lại giá trị trả về
  return t;
}

Tối ưu hóa hiệu suất

1. Caching liên kết:

   • Sử dụng hash map ánh xạ con trỏ sang ID nội bộ
   • Lưu trữ tạm thời các thay đổi trên đồ thị liên kết, gộp các thao tác trùng lặp trước khi cập nhật chính thức
   • Sắp xếp theo thứ tự để tối ưu xóa/bổ sung hàng loạt

2. Tối ưu ngăn xếp:

   • Lưu trữ trực tiếp con trỏ trong cache, tránh tra cứu hash map
   • Xử lý theo mô hình cây phân cấp thay vì đồ thị phức tạp
   • Tính toán đồng loạt khi gọi gc_collect

Hành trình phát triển

Dù chỉ hơn 600 dòng mã, việc thiết kế các cấu trúc dữ liệu tinh gọn đòi hỏi nhiều công sức. Phiên bản này sẽ thay thế module GC “thô sơ” tôi viết năm ngoái - vốn phụ thuộc vào cấu trúc cây đơn gốc phức tạp.

Kế hoạch tương lai

Nếu open-source, cần:

• Chuẩn hóa mã nguồn
• Bổ sung test case chi tiết
• Hỗ trợ kiến trúc 64-bit

Cập nhật 10/6: Dự án đã được công bố trên Google Code theo giấy phép BSD. Phiên bản đầu tiên vẫn còn nhiều lỗi, bạn có thể checkout qua SVN tại:

P/s: Tiếng Anh của tôi không tốt lắm, các chú thích và tài liệu hướng dẫn có thể chưa chuẩn xác.