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

Hôm nay chúng ta sẽ tìm hiểu quá trình đánh dấu (mark) được thực hiện như thế nào.

Tất cả các quy trình GC đều bắt đầu từ hàm singlestep. Đây là một máy trạng thái đơn giản, luân phiên chuyển đổi giữa các trạng thái liên tiếp nhau. Trạng thái được lưu trữ trong trường gcstate của global state. Hai trạng thái đầu tiên liên quan trực tiếp đến quá trình đánh dấu.

Trong trạng thái khởi tạo GCSpause, hàm markroot sẽ được thực thi. Hãy cùng xem đoạn mã trong file lgc.c dòng 501:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* đánh dấu tập hợp root */
static void markroot (lua_State *L) {
 global_State *g = G(L);
 g->gray = NULL;
 g->grayagain = NULL;
 g->weak = NULL;
 markobject(g, g->mainthread);
 /* đảm bảo bảng toàn cục được duyệt trước ngăn xếp chính */
 markvalue(g, gt(g->mainthread));
 markvalue(g, registry(L));
 markmt(g);
 g->gcstate = GCSpropagate;
}

Đoạn mã này chủ yếu thực hiện việc thiết lập lại trạng thái và đánh dấu các nút gốc. Lua sử dụng thuật toán đánh dấu ba màu (Tri-colour marking), trong đó duy trì một tập hợp các nút màu xám được lưu trong gray. Các nút cần đánh dấu nguyên tử được lưu trong grayagain, còn các bảng yếu (weak table) cần dọn dẹp được lưu trong weak.

Các macro markobject và markvalue được sử dụng để đánh dấu đối tượng, khác biệt ở chỗ chúng thao tác với GCObject hay TValue. Cả hai đều gọi đến hàm reallymarkobject. Hàm markmt sẽ đánh dấu các bảng siêu dữ liệu (metatable) trong global state liên quan đến các kiểu dữ liệu cơ bản. Những thành phần này kết hợp lại tạo thành tập hợp gốc (root set) của toàn bộ dữ liệu.

Hãy xem hàm cốt lõi trong lgc.c dòng 69:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

static void reallymarkobject (global_State *g, GCObject *o) {
 lua_assert(iswhite(o) && !isdead(g, o));
 white2gray(o);
 switch (o->gch.tt) {
  case LUA_TSTRING: {
   return;
  }
  case LUA_TUSERDATA: {
   Table *mt = gco2u(o)->metatable;
   gray2black(o); /* userdata không bao giờ ở trạng thái xám */
   if (mt) markobject(g, mt);
   markobject(g, gco2u(o)->env);
   return;
  }
  case LUA_TUPVAL: {
   UpVal *uv = gco2uv(o);
   markvalue(g, uv->v);
   if (uv->v == &uv->u.value) /* đã đóng chưa? */
    gray2black(o); /* upvalue mở không bao giờ ở trạng thái đen */
   return;
  }
  case LUA_TFUNCTION: {
   gco2cl(o)->c.gclist = g->gray;
   g->gray = o;
   break;
  }
  case LUA_TTABLE: {
   gco2h(o)->gclist = g->gray;
   g->gray = o;
   break;
  }
  case LUA_TTHREAD: {
   gco2th(o)->gclist = g->gray;
   g->gray = o;
   break;
  }
  case LUA_TPROTO: {
   gco2p(o)->gclist = g->gray;
   g->gray = o;
   break;
  }
  default: lua_assert(0);
 }
}

Hàm này đánh dấu đối tượng dựa trên kiểu dữ liệu thực tế của nó. Độ phức tạp thời gian của reallymarkobject là O(1), không thực hiện đệ quy đánh dấu các đối tượng liên quan. Việc đảm bảo độ phức tạp O(1) giúp quá trình đánh dấu có thể phân bổ đều qua nhiều khoảng thời gian ngắn, tránh việc dừng toàn bộ hệ thống quá lâu.

Đối với LUA_TSTRING, vì chuỗi ký tự không có đối tượng liên quan và được quản lý tập trung, nên chỉ cần chuyển sang trạng thái không trắng là đủ. Trong khi đó, LUA_TUSERDATA cần được chuyển trực tiếp sang trạng thái đen sau khi đánh dấu metatable và bảng môi trường của nó.

LUA_TUPVAL là kiểu dữ liệu đặc biệt, không nhìn thấy trực tiếp khi lập trình Lua. Nó được sử dụng để giải quyết vấn đề chia sẻ upvalue giữa nhiều closure. Khi một hàm Lua đang thực thi, các biến local ở các tầng trên đều có thể truy cập được nhờ cơ chế này. Trong quá trình biên dịch, parser sẽ xác định rõ các upvalue cần thiết. Hàm luaF_newLclosure trong file lvm.c dòng 719 sẽ xử lý việc tạo closure và ánh xạ upvalue.

Khi hàm trả về, các biến trên ngăn xếp có thể biến mất. Hàm luaF_close trong lfunc.c sẽ xử lý việc “đóng” các upvalue còn tồn tại, chuyển chúng vào cấu trúc TUPVAL an toàn.

Trong quá trình đánh dấu, các TUPVAL mở (open) cần giữ ở trạng thái xám vì chúng có thể thay đổi trong quá trình GC hoạt động. Hàm remarkupvals trong lgc.c dòng 516 sẽ đánh dấu lại tất cả các upvalue mở trước khi kết thúc quá trình mark.

Các trạng thái tiếp theo như GCSpropagate sẽ xử lý danh sách các đối tượng màu xám thông qua hàm propagatemark. Tiến độ của quá trình GC được điều khiển thông qua giá trị trả về của singlestep. Hàm luaC_step sẽ xử lý khoảng 1KB dữ liệu mỗi lần gọi, và GCthreshold sẽ tăng tương ứng.

Khi đến giai đoạn “nguyên tử” (atomic), cần thực hiện đánh dấu cuối cùng không thể gián đoạn. Hàm atomic trong lgc.c dòng 526 xử lý các bước quan trọng như đánh dấu lại upvalue, xử lý bảng yếu, và chuẩn bị cho giai đoạn dọn dẹp. Hàm iscleared xác định các phần tử có thể xóa khỏi bảng yếu dựa trên trạng thái đánh dấu.

Quá trình GC của Lua là một hệ thống tinh vi, kết hợp nhiều kỹ thuật như đánh dấu ba màu, phân bổ thời gian hợp lý, và xử lý đặc biệt cho các kiểu dữ liệu phức tạp. Việc hiểu rõ cơ chế này giúp tối ưu hiệu năng ứng dụng Lua và tránh các vấn đề rò rỉ bộ nhớ.