FUGC khó tin của Fil

 (fil-c.org)
1 điểm bởi GN⁺ 2025-09-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • FUGC của ngôn ngữ Fil-C là một garbage collector tiên tiến hỗ trợ xử lý song song và đồng thời
  • Hoạt động on-the-fly (thực thi tức thời) và dùng phương pháp grey-stack Dijkstra mà không cần dừng toàn bộ chương trình
  • Triển khai thiết kế theo dõi bộ nhớ chính xác và xử lý không di chuyển đối tượng
  • Có thể quản lý bộ nhớ an toàn và hiệu quả trong môi trường đa luồng nhờ sử dụng safepoint
  • Cung cấp nhiều kiểu quản lý bộ nhớ theo phong cách C/Java/JavaScript như xử lý ngoại lệ khi truy cập đối tượng đã được giải phóng / giải phóng trùng lặp

Tổng quan về FUGC (garbage collector khó tin của Fil)

Fil-C sử dụng FUGC (Fil's Unbelievable Garbage Collector), một garbage collector song song, đồng thời, on-the-fly, grey-stack Dijkstra, chính xác, không di chuyển
Có thể xem mã nguồn FUGC tại fugc.c, nhưng nó không thể hoạt động nếu thiếu nhiều logic hỗ trợ khác từ runtime và compiler

Các đặc điểm chính của FUGC

  • Xử lý song song: thực hiện đồng thời các tác vụ marking và sweeping trên nhiều luồng; càng nhiều lõi CPU thì tốc độ thu gom càng tăng
  • Hỗ trợ đồng thời: luồng garbage collector làm việc tách biệt với mutator (tức các luồng chương trình người dùng), nên các luồng ứng dụng có thể tiếp tục chạy mà không bị dừng
  • on-the-fly (thực thi tức thời): không cần stop-the-world toàn cục; thay vào đó dùng "soft handshake (=ragged safepoint)" để từng luồng xử lý bất đồng bộ các tác vụ cụ thể như quét stack
  • Phương pháp grey-stack: quét lại stack của luồng nhiều lần cho đến khi đạt điểm cố định để lặp lại việc marking; nếu trong quá trình này phát hiện thêm đối tượng thì tiếp tục marking lại
  • Sử dụng store barrier đơn giản, không cần load barrier
  • Dijkstra barrier: nếu lưu một con trỏ vào heap hoặc biến toàn cục trong lúc marking, đối tượng đích cũng sẽ được đánh dấu đồng thời
  • Thu gom chính xác: runtime theo dõi chính xác mọi vị trí con trỏ, nên GC chỉ duyệt các đối tượng thực sự
  • Xử lý đối tượng không di chuyển: vị trí bộ nhớ của đối tượng không thay đổi, giúp việc thu gom đồng thời đa luồng và đồng bộ hóa trở nên dễ dàng hơn
  • Thiết kế advancing wavefront: mutator không thể làm tăng khối lượng công việc của collector; các đối tượng đã được đánh dấu sẽ tiếp tục được giữ lại trong chu kỳ thu gom đó
  • Thu gom gia tăng: một số đối tượng dù còn sống tại thời điểm bắt đầu thu gom vẫn có thể được giải phóng trong lúc chu kỳ đang diễn ra

Safepoint (điểm an toàn) và quản lý luồng

  • Pollcheck: compiler chèn pollcheck theo chu kỳ; ở fast path chỉ là một nhánh đơn giản, còn ở slow path sẽ gọi callback liên quan đến GC
  • Soft handshake: gửi yêu cầu thực thi callback pollcheck đến tất cả các luồng rồi chờ hoàn tất
  • Quản lý trạng thái enter/exit: với các hàm chặn dài hoặc system call nơi pollcheck bị bỏ qua, collector sẽ trực tiếp thực thi callback tương ứng
  • Bảo đảm ngăn điều kiện tranh chấp và truy cập con trỏ an toàn trong môi trường hỗ trợ đa luồng
  • Hỗ trợ các tác vụ đặc biệt như debug hoặc fork bằng chế độ stop-the-world, đồng thời việc xử lý signal cũng được triển khai ổn định

Vòng lặp collector của FUGC

  1. Chờ trigger GC
  2. Kích hoạt store barrier rồi thực hiện soft handshake với callback no-op
  3. Kích hoạt black allocation (đánh dấu trước đối tượng mới), thực hiện callback reset cache
  4. Đánh dấu các root toàn cục
  5. Soft handshake (callback quét stack và reset cache); nếu mark stack rỗng thì chuyển sang bước 7
  6. Tracing (đánh dấu các tham chiếu của từng đối tượng trong mark stack, lặp cho đến khi mark stack rỗng rồi quay lại bước 5)
  7. Tắt store barrier, chuẩn bị sweep, rồi soft handshake để reset cache lần nữa
  8. Sweep (các page chưa được sweep sẽ cấp phát theo black, còn nơi đã sweep thì cấp phát theo white)
  9. Quay lại vòng lặp

Điểm khác biệt với nghiên cứu trước đây và tối ưu hóa

  • FUGC tương tự collector DLG (Doligez-Leroy-Gonthier), nhưng nhờ Dijkstra barrier đơn giản và cách dùng grey stack, việc triển khai store barrier trực quan hơn và cho hiệu năng tốt hơn
  • Cách tiếp cận điểm cố định hội tụ nhanh và có chi phí thấp
  • Sweep cực nhanh nhờ bitvector SIMD-based sweep, chỉ chiếm dưới 5% tổng thời gian GC
  • Tối ưu hiệu năng bằng các kỹ thuật như sử dụng Verse heap config

Tính năng bổ sung (khả năng mở rộng quản lý bộ nhớ)

Giải phóng đối tượng

  • Khi gọi free trong C, đối tượng được gắn cờ là đã free ngay lập tức; nếu truy cập sau đó sẽ phát sinh trap
  • Ngăn GC hoạt động sai do dangling pointer (con trỏ treo)
  • Tham chiếu đến đối tượng đã giải phóng được chuyển hướng tới singleton free object, nhờ đó vẫn có thể phát hiện chắc chắn ngay cả sau khi bộ nhớ được cấp phát lại
  • Ngăn rò rỉ bộ nhớ do các con trỏ không còn được sử dụng nhưng vẫn kích hoạt GC

Finalizer

  • Có thể triển khai linh hoạt hàng đợi finalizer kiểu Java thông qua hàng đợi tùy chỉnh và xử lý luồng

Tham chiếu yếu

  • Hoạt động giống hệt weak reference của Java, nhưng không có reference queue riêng (không hỗ trợ phantom hoặc soft reference)

Weak map

  • Tương tự JavaScript WeakMap, nhưng có thể lặp qua toàn bộ phần tử và kiểm tra số lượng phần tử

Kết luận và ý nghĩa

Với FUGC, Fil-C cung cấp độ an toàn mạnh mẽ và xử lý ngoại lệ trực quan đối với việc lạm dụng free

  • Được thiết kế để luôn phát sinh trap khi truy cập đối tượng đã giải phóng hoặc khi double free
  • Nếu không giải phóng đối tượng, GC sẽ tự chịu trách nhiệm thu hồi đúng cách
  • Hỗ trợ nhiều mô hình quản lý bộ nhớ, mang lại môi trường quen thuộc cả với lập trình viên C/Java/JavaScript

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-09-06
Ý kiến trên Hacker News

  • Ừm, có vẻ Fil-C thực sự có thể mang ý nghĩa rất quan trọng. Có rất nhiều phần mềm chỉ tồn tại dưới dạng mã C, nên tôi nghĩ cần có một cách tiếp cận để duy trì chúng. Các trình biên dịch C hiện nay chấp nhận rủi ro bảo mật lớn để tối đa hóa hiệu năng đơn nhân, nhưng kiểu đánh đổi này đã có cảm giác lỗi thời rồi. Danh sách hỗ trợ như CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash, v.v. thực sự rất ấn tượng. Tôi không nghĩ bất kỳ phần mềm nào trong số đó có khả năng được viết lại bằng Rust. Tôi tự hỏi liệu Fil-C có thể được dùng cho đa nhiệm giữa các tiến trình không đáng tin cậy trong môi trường không có MMU hay không. Có vẻ nó đang đi đúng hướng với bảo mật dựa trên capability, đồng bộ hóa non-blocking, v.v. Tôi muốn biết có ai đã thực sự dùng thử chưa. Có báo cáo rằng ngay cả trong trường hợp xấu nhất thì tốc độ cũng chỉ giảm khoảng 4 lần, và cái tên này thực sự rất buồn cười. Filthy way! Filthy way!

    • Về câu hỏi liệu Fil-C có thể hỗ trợ đa nhiệm giữa các tiến trình không đáng tin cậy trên máy tính không có MMU hay không, về cơ bản FUGC đúng là dựa trên các tính năng phụ thuộc MMU của hệ điều hành, nhưng tôi nghĩ cũng có thể tạo ra một phiên bản loại bỏ sự phụ thuộc đó. Về hiệu năng, chậm đi 4 lần là kịch bản tệ nhất, và chính tôi là người đã báo cáo con số đó. Tôi có xu hướng luôn đo hiệu năng một cách thực tế và bám riết lấy việc cải thiện các vấn đề hiệu năng. Trên thực tế, ngay cả với các phiên bản phần mềm chạy trên Fil-C, tôi vẫn có thể dùng bình thường các chương trình mình hay sử dụng hằng ngày

    • Bạn nói danh sách phần mềm được hỗ trợ rất ấn tượng, tôi đồng ý về mặt tổng quát, nhưng lại nhìn hơi khác với các ví dụ được nêu ra. Những thứ như CPython, Perl5 vốn đã là runtime của các ngôn ngữ nổi tiếng chậm vì GC, nên chồng thêm một GC nữa lên trên không phải là một thiết kế thanh lịch, mà còn có thể làm giảm tốc độ đáng kể. Ngoài ra, đã có một số nỗ lực viết lại hoặc thay thế chúng bằng Rust hay Go, ví dụ như SQLite có Turso. Và các phần mềm này vốn là những dự án nền tảng được duy trì rất tích cực, nên biết đâu đến lúc nào đó chính chúng sẽ tự refactor hoặc port sang Rust. Tôi nghĩ nơi Fil-C phù hợp hơn là các chương trình được bảo trì ít hơn, ít nhạy cảm với hiệu năng nhưng vẫn tiếp tục được dùng, kiểu như các chương trình C từ 50 năm trước mà thỉnh thoảng ai đó vẫn lôi ra dùng

    • Điểm mạnh của việc SQLite được viết bằng C là khả năng port sang các hệ điều hành phi tiêu chuẩn. Ví dụ, tôi từng trực tiếp dùng nó trên RTOS nhúng μC/OS-II. Thiết kế hệ thống nhúng khá khác PC/server, nên để phục vụ hiệu năng và tránh phân mảnh bộ nhớ, người ta thậm chí không giải phóng bộ nhớ mà đánh dấu để tái sử dụng object/struct. Kiểu như custom heap allocation hoặc pooling. Tài liệu VFS của SQLite, giới thiệu Micro-Controller OS

    • Bạn nói sẽ không có chuyện viết lại danh sách phần mềm C nêu trên bằng Rust, nhưng tôi lại tò mò không biết còn bao lâu nữa thì các công cụ phân tích tĩnh dựa trên AI sẽ tiến bộ đến mức có thể xác định chính xác vấn đề trong mã C và đưa ra phản hồi kiểu “chỗ này sẽ lỗi, sửa thế này là được”. Nếu thực sự xuất hiện công cụ như vậy thì có lẽ cứ tiếp tục dùng C cũng ổn

    • Xin lưu ý rằng Fil-C hiện vẫn chưa hỗ trợ các hệ thống 32-bit (hoặc thấp hơn). Tài liệu về Invisicaps trong Fil-C

  • Dự án kiểu này tạo cảm giác là một trường hợp hiếm hoi theo đuổi đồng thời cả nghiên cứu lẫn tính thực dụng. Những việc như vậy thường do các công ty IT lớn lập hẳn đội ngũ và vận hành bằng doanh thu quảng cáo, nên tôi tò mò Fil-C xuất phát từ nền tảng nào. Nếu đây không chỉ là một dự án đam mê cá nhân, thì ai đã tài trợ, đã cần bao nhiêu năm nhân lực, và mục tiêu cuối cùng là gì?

    • Cá nhân tôi thấy đây giống một dự án đam mê

    • Trả lời câu hỏi về mục tiêu cuối cùng, phần bản quyền của dự án ghi là 2024-2025 Epic Games, Inc.

  • Bản thân việc Fil-C tồn tại đã là điều đáng mừng. Dù công nghệ kiểu này thực sự hiệu quả với chương trình thực tế, vẫn có rất nhiều lập trình viên tin rằng “mấy thứ đó là không thể”. Chỉ riêng việc nó có thể được hiện thực hóa cũng đủ dập tắt vô số cuộc tranh cãi ngay lập tức

    • Tôi tò mò về kết quả benchmark. Mối lo lớn nhất với cách tiếp cận này là liệu hiệu năng có tụt khủng khiếp trong những trường hợp sử dụng cụ thể mà C/C++ vẫn còn được ưa chuộng hay không. Nếu throughput, latency hay mức dùng bộ nhớ trở nên quá giống với những ngôn ngữ như Go, thì cuối cùng sẽ chẳng còn nhiều lý do để chọn nó nữa

    • Trong ngôn ngữ lập trình, câu chuyện hiệu năng luôn tồn tại từ tận thời assembly. Chỉ là đa số lập trình viên không phải những người có tầm nhìn phi thường như Ivan Suntherland, Alan Kay, Steve Jobs hay Bret Victor, mà là những người bình thường chỉ tin khi thấy thứ gì đó chạy ngay trước mắt mình. Vì vậy đến giờ vẫn đầy rẫy các bản sao của UNIX và C, và nhiều người dường như sống bằng cách lặp lại nguyên xi các tầm nhìn của quá khứ thay vì tạo ra cái mới. Tất nhiên, hai người tạo ra UNIX và C vào thập niên 1970 cũng là những nhà nhìn xa trông rộng xuất sắc

  • Tôi tò mò tại sao lại dùng chiến lược retreating wavefront thay vì advancing wavefront

  • Nếu các lời gọi free(...) trong các chương trình C hiện có đã được đặt đúng chỗ, và còn quản lý thêm thông tin phạm vi riêng cho mọi con trỏ, thì tại sao lại chọn GC toàn cục? Thay vào đó, tôi nghĩ kỹ thuật temporal checking kiểu lock-and-key (tài liệu tham khảo: liên kết bài báo) có thể tốt hơn về khả năng dự đoán mức dùng bộ nhớ, hiệu năng và scheduling. Tôi đoán có thể là vì không gian lưu key quá lớn, hoặc thời gian kiểm tra quá dài, hoặc dễ phát sinh race condition trong môi trường đa luồng

    • Cách lock and key không có những đặc điểm thông minh riêng của Fil-C. Điểm mạnh của mô hình capability trong Fil-C là hoàn toàn thread-safe và trong đa số trường hợp không cần atomics hay locking đặc biệt

    • Một điểm nữa cũng thú vị là nó cho phép phép toán trên con trỏ vượt phạm vi miễn là không dereference. Các trình biên dịch đôi khi lợi dụng UB ở những chỗ như vậy để tối ưu hóa (câu hỏi liên quan trên Stack Overflow), nên tôi tò mò liệu LLVM nội bộ của Fil-C có tắt kiểu tối ưu hóa đó hay không, hay là nó quản lý con trỏ dưới dạng tổ hợp “base + offset” để chặn hẳn khả năng này. Nếu vậy thì có bỏ lỡ một số tối ưu hóa áp dụng cho con trỏ thông thường hay không cũng là điều tôi muốn biết

  • Có vẻ là một dự án thực sự rất hay. Tôi chú ý đến việc fast path của pollcheck chỉ đơn giản là load-and-branch. Có một kỹ thuật thú vị dùng thay cho kiểu branch này, được tổng hợp khá tốt trong bài viết "kiểm tra suspend ngầm" của blog chính thức Android

    • Với poll check thì kiểu tối ưu hóa đó khá phổ biến. Thực tế là đa số JVM production hiện nay đều đã áp dụng rồi. Nhưng tôi vẫn chưa ở giai đoạn cần bận tâm đến những tối ưu hóa mức thấp như thế. Hiện tại tôi còn phải xử lý trước các tối ưu hóa mức cao cơ bản vẫn đang còn dang dở

  • Một C có GC hỗ trợ đồng thời, lại còn là non-moving GC, thực sự rất lạ. Nếu với một dự án C cỡ trung mà có thể đổi 2~3 lần hiệu năng runtime để giảm lỗi bộ nhớ, thì tôi hoàn toàn sẵn sàng chấp nhận. Tôi tò mò việc áp dụng dần dần dễ đến mức nào. Có thể làm theo từng target không, hay là phải thay toàn bộ toolchain?

  • Tôi quan tâm đến cả C, hiệu năng và bảo mật. Cấu trúc GC và capability này rất hấp dẫn. Tôi đã nhiều lần nghĩ về việc “C an toàn hơn” sẽ trông như thế nào, và cũng từng xem xét khái niệm capability vài lần, nhưng tôi không rành mã của compiler. Tôi tò mò không biết hỗ trợ Windows có khó không

    • Nói ngoài lề một chút, vì câu đầu tiên không có Oxford comma nên tôi mất khá lâu mới hiểu được ý. Hiếm khi có ví dụ nào rõ ràng đến vậy

  • Tôi tò mò GC theo dõi root object như thế nào. Có bước biên dịch nào đánh dấu trước các root để GC quét không? Nếu ai biết thì mong giải thích giúp

    • LLVM xử lý việc đó bằng cách chèn các lệnh để điền stack map

  • Dự án này thực sự đáng kinh ngạc. Nghe nói đến giờ mà tôi chưa từng biết đến nó mới là điều lạ. Tôi rất mong được tự mình thử. Có thể vì giới hạn hiệu năng mà khó dùng cho production, nhưng như một cách để trực tiếp kiểm chứng độ an toàn của một số chương trình thì nó có vẻ cực kỳ hữu ích. Nó cho cảm giác toàn diện hơn các sanitizer mà tôi vẫn dùng hằng ngày