Phân Tích Mã Nguồn Lua GC (Phần 1)

Gần đây, trong quá trình vận hành môi trường Lua với lượng dữ liệu lớn, tôi nhận thấy hoạt động thu gom rác (GC) đang chiếm dụng tới khoảng 20% tổng thời gian CPU. Điều này khiến tôi quyết tâm tối ưu hóa vấn đề này. Để làm được điều đó, trước tiên phải hiểu rõ bản chất thuật toán và cơ chế triển khai GC của Lua. Dù đã từng nghiên cứu mã nguồn Lua trước đây, nhưng do sự thay đổi giữa các phiên bản mã nguồn, tôi buộc phải thực hiện lại toàn bộ quá trình này. Lần này, tôi đã tập trung phân tích kỹ lưỡng mã nguồn phiên bản Lua 5.1.4. Từ hôm nay, tôi sẽ ghi chép chi tiết quá trình nghiên cứu này thành chuỗi bài viết. Việc đọc mã nguồn đã chiếm trọn 1 ngày làm việc của tôi, nhưng việc biên soạn thành bài viết có thể còn tốn nhiều thời gian hơn nữa. Tôi sẽ chia sẻ nội dung này thành nhiều kỳ trên blog cá nhân.

Tổng quan về hệ thống GC trong Lua

Lua sử dụng hệ thống GC đơn giản dựa trên thuật toán đánh dấu và dọn dẹp (mark-sweep). Trong môi trường Lua, có tổng cộng 9 loại kiểu dữ liệu: nil, boolean, lightuserdata, number, string, table, function, userdata và thread. Trong số này, chỉ có 4 kiểu dữ liệu string, table, function, thread là được chia sẻ dưới dạng tham chiếu trong máy ảo và cần được quản lý bởi GC. Các kiểu dữ liệu còn lại đều được lưu trữ dưới dạng giá trị trực tiếp.

Tuy nhiên, trong quá trình triển khai thực tế, Lua còn quản lý thêm 2 đối tượng khác qua GC:

1. Proto (có thể hiểu là hàm chưa gắn upvalue)
2. Upvalue (nhiều upvalue có thể trỏ đến cùng một giá trị)

Cơ chế lưu trữ giá trị trong Lua

Lua sử dụng cấu trúc union kèm tag kiểu dữ liệu để lưu trữ giá trị. Cấu trúc này được định nghĩa trong tệp lobject.h (dòng 56-75):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

/*
** Hợp (union) chứa tất cả các giá trị Lua
*/
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;

/*
** Giá trị có tag kiểu dữ liệu
*/
#define TValuefields  Value value; int tt
typedef struct lua_TValue {
  TValuefields;
} TValue;

Như bạn thấy, trường value trong TValue được định nghĩa dưới dạng union. Nếu giá trị cần được quản lý bởi GC, nó sẽ được lưu dưới dạng con trỏ GCObject*. Ngược lại, giá trị sẽ được lưu trực tiếp. Trong toàn bộ mã nguồn, các giá trị đều được biểu diễn dưới dạng TValue thay vì Value để đảm bảo có thêm trường tag kiểu dữ liệu tt. Trên hệ thống điển hình, mỗi TValue chiếm 12 byte bộ nhớ.

Chú ý: Trong tài liệu chính thức The implementation of Lua 5.0, các tác giả đã thảo luận về việc tại sao không sử dụng kỹ thuật nén tag kiểu dữ liệu vào 8 byte đầu tiên trên hệ thống 32-bit.

Cấu trúc chung của các đối tượng GC

Tất cả các đối tượng được quản lý bởi GC đều bắt đầu với một phần tiêu đề chung gọi là CommonHeader, được định nghĩa dưới dạng macro trong lobject.h (dòng 43):

1

#define CommonHeader  GCObject *next; lu_byte tt; lu_byte marked

Từ đây, ta thấy:

• Tất cả các đối tượng GC được kết nối với nhau dưới dạng danh sách liên kết đơn
• Trường tt xác định kiểu dữ liệu của đối tượng
• Trường marked dùng để đánh dấu trạng thái trong quá trình thu gom rác

Đặc điểm của chuỗi (string) trong GC

Mặc dù hầu hết các đối tượng GC đều được quản lý qua danh sách liên kết rootgc, nhưng kiểu string lại có cách xử lý đặc biệt. Tất cả các chuỗi được lưu trữ trong một bảng băm lớn để đảm bảo không có hai chuỗi trùng nhau tồn tại trong hệ thống. Do đó, các đối tượng kiểu TString (đại diện cho chuỗi) không được đưa vào danh sách chung rootgc, mà được quản lý riêng biệt thông qua cấu trúc stringtable.

Cấu trúc lua_State - Trạng thái của máy ảo Lua

lua_State là cấu trúc dữ liệu quan trọng nhất khi làm việc với giao diện C-Lua. Về cơ bản, nó đại diện cho một luồng thực thi (thread) cùng các thông tin liên quan như ngăn xếp (stack), môi trường thực thi, v.v. Cấu trúc này được định nghĩa trong lstate.h (dòng 97):

1
2
3
4
5
6
7
8

struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;         /* Ô trống đầu tiên trong ngăn xếp */
  StkId base;        /* Vị trí bắt đầu của hàm hiện tại */
  global_State *l_G; /* Trạng thái toàn cục */
  // ... các trường khác
};

值得注意的是，lua_State tự nó cũng là một đối tượng GC với kiểu thread.

Quản lý toàn cục qua global_State

Mỗi máy ảo Lua có thể chứa nhiều lua_State (nhiều luồng). Tất cả các thông tin chia sẻ giữa các luồng được lưu trữ trong cấu trúc global_State, bao gồm:

• Danh sách liên kết rootgc chứa hầu hết các đối tượng GC
• Bảng băm stringtable chứa các chuỗi
• Danh sách tmudata chứa các đối tượng userdata cần gọi hàm __gc

Hàm luaC_link - Kết nối đối tượng GC vào hệ thống

Khi tạo mới một đối tượng GC, nó sẽ được kết nối vào danh sách rootgc thông qua hàm luaC_link (định nghĩa trong lgc.c dòng 687):

1
2
3
4
5
6
7

void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  global_State *g = G(L);
  o->gch.next = g->rootgc;
  g->rootgc = o;
  o->gch.marked = luaC_white(g);
  o->gch.tt = tt;
}

Hàm này thực hiện các công việc chính:

1. Thiết lập liên kết đơn hướng đến đầu danh sách rootgc
2. Đặt trạng thái ban đầu của đối tượng là “trắng” (chưa được đánh dấu)
3. Gán kiểu dữ liệu cho đối tượng

Xử lý đặc biệt với upvalue

Upvalue là trường hợp đặc biệt vì chúng là các tham chiếu gián tiếp đến giá trị đã tồn tại. Hàm luaC_linkupval xử lý riêng trường hợp này để đảm bảo tính nhất quán khi GC hoạt động theo cơ chế phân đoạn (incremental). Khi GC đang ở giai đoạn lan truyền đánh dấu (`GCSpropagate