Cải tiến từ Lua 5.1

Anonymous trong Làm Việc Từ Xa và Kiến Trúc

2011-03-01 Khoảng 1000 từ 5 phút

Nội dung

Phân tích mã nguồn của Lua GC (2)

Bài phân tích mã nguồn Lua GC (Phần 2)

Lua dùng kỹ thuật GC truyền thống với cơ chế “dừng toàn bộ hệ thống” (stop-the-world) ở phiên bản đầu tiên. Khi kích hoạt quá trình thu gom rác (GC), toàn bộ hệ thống phải chờ cho đến khi quá trình này hoàn tất. Cách tiếp cận này hoàn toàn ổn định với các ứng dụng xử lý lượng dữ liệu nhỏ hoặc ít thay đổi. Tuy nhiên, với ứng dụng có yêu cầu thời gian thực cao như server game trực tuyến, việc dừng hệ thống sẽ gây ra độ trễ không thể chấp nhận được khi xử lý dữ liệu lớn.

Kể từ phiên bản Lua 5.1, hệ thống GC đã được cải tiến thành dạng phân đoạn (incremental). Dù vẫn giữ cơ chế “dừng toàn bộ hệ thống”, nhưng quá trình GC giờ đây được chia thành các bước nhỏ. Mỗi bước chỉ cần dừng hệ thống trong thời gian cực ngắn, giúp giảm độ trễ tổng thể. Cách tiếp cận này đòi hỏi logic phức tạp hơn để xử lý các thay đổi giữa các bước, đồng thời đảm bảo tính đúng đắn của quá trình thu gom rác. Mặc dù chi phí tổng thể của GC phân đoạn cao hơn chút ít so với phương pháp truyền thống, nhưng các nhà phát triển Lua đã tối ưu hóa để mức độ ảnh hưởng này là tối thiểu.

Năm giai đoạn chính của quá trình GC

Lua GC được chia thành 5 trạng thái chính, được định nghĩa trong file lgc.h:

1
2
3
4
5


#define GCSpause    0
#define GCSpropagate 1
#define GCSsweepstring 2
#define GCSsweep    3
#define GCSfinalize 4

1. Giai đoạn GCSpause

Đây là điểm khởi đầu của mọi chu kỳ GC. Tại đây, hệ thống đánh dấu các nút gốc (root nodes) - bao gồm thread chính, bảng toàn cục, bảng đăng ký và các meta table hệ thống. Hàm markroot(L) được gọi để thực hiện công việc này.

2. Giai đoạn GCSpropagate

Giai đoạn đánh dấu lan tỏa (mark propagation) này được thực hiện theo từng bước. Khi còn các đối tượng cần đánh dấu (g->gray ≠ NULL), hệ thống sẽ gọi hàm propagatemark(g). Khi không còn đối tượng nào cần xử lý, hệ thống sẽ thực hiện bước đánh dấu nguyên tử (atomic) để kết thúc giai đoạn này.

1
2
3
4
5
6
7
8


case GCSpropagate: {
    if (g->gray)
        return propagatemark(g);
    else {
        atomic(L); // Kết thúc giai đoạn đánh dấu
        return 0;
    }
}

3. Giai đoạn GCSsweepstring

Giai đoạn này chuyên xử lý việc dọn dẹp các chuỗi (string). Vì chuỗi được quản lý riêng biệt trong Lua, hệ thống sử dụng một hash table để quản lý toàn bộ chuỗi. Mỗi bước GC sẽ làm sạch một cột của bảng hash này bằng hàm sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]).

4. Giai đoạn GCSsweep

Giai đoạn dọn dẹp chính cho tất cả các đối tượng GC khác chưa được đánh dấu. Đây là giai đoạn tương tự như GCSsweepstring nhưng áp dụng cho các loại đối tượng khác.

5. Giai đoạn GCSfinalize

Trong giai đoạn cuối cùng này, các hàm meta __gc của userdata sẽ được gọi lần lượt thông qua hàm GCTM. Lưu ý rằng các userdata có hàm __gc sẽ không bị xóa ngay lập tức mà sẽ được xử lý ở chu kỳ GC tiếp theo hoặc khi gọi lua_close.

Cơ chế đánh dấu màu sắc trong GC

Hệ thống GC của Lua sử dụng cơ chế “màu sắc” để theo dõi trạng thái của các đối tượng. Mỗi đối tượng có thể ở một trong ba trạng thái:

Trắng: Đối tượng có thể bị thu gom
Xám: Đối tượng đã được đánh dấu nhưng các tham chiếu của nó chưa được xử lý
Đen: Đối tượng đã được đánh dấu hoàn tất cùng toàn bộ các tham chiếu của nó

Thông tin màu sắc được lưu trữ trong trường marked của cấu trúc CommonHeader với 8 bit, được sử dụng như sau:

1
2
3
4
5
6
7
8


#define WHITE0BIT   0
#define WHITE1BIT   1
#define BLACKBIT    2
#define FINALIZEDBIT 3
#define KEYWEAKBIT  3
#define VALUEWEAKBIT 4
#define FIXEDBIT    5
#define SFIXEDBIT   6

Cơ chế “ping-pong” giữa hai màu trắng

Việc sử dụng hai bit màu trắng (WHITE0 và WHITE1) giúp hệ thống phân biệt giữa các đối tượng được tạo ra trong chu kỳ GC hiện tại và các đối tượng tồn tại từ chu kỳ trước. Biến currentwhite trong global_State xác định bit màu trắng nào đang được sử dụng.

Bit đặc biệt FIXEDBIT

Bit này được sử dụng để bảo vệ các đối tượng quan trọng khỏi bị thu gom. Ví dụ, các chuỗi dùng để biểu diễn tên phương thức meta như __index, __newindex… trong Lua được đánh dấu bằng FIXEDBIT để đảm bảo chúng không bị xóa, giúp tăng hiệu suất khi so sánh chuỗi.

Bit SFIXEDBIT cho luồng chính

Luồng chính (mainthread) được đánh dấu bằng Sfixed để đảm bảo nó không bị xóa trong suốt vòng đời của Lua VM. Hàm lua_close sẽ xử lý việc giải phóng tài nguyên nhưng vẫn giữ nguyên luồng chính cho đến bước cuối cùng.

Tối ưu hóa quản lý bộ nhớ

Lua sử dụng hàm luaM_realloc_ trong file lmem.c để quản lý việc cấp phát và giải phóng bộ nhớ. Khi muốn theo dõi chính xác tình trạng sử dụng bộ nhớ, các nhà phát triển có thể tùy chỉnh hàm này để tính toán cả các chi phí quản lý bộ nhớ ẩn (overhead).

Ví dụ,

Cải Tiến Từ Lua 5.1