Phân Tích Mã Nguồn Lua GC (6) Kết Thúc

Phần phức tạp nhất trong GC là đánh dấu (mark) đã được trình bày xong. Những phần còn lại khá đơn giản. Hôm nay sẽ hoàn thành toàn bộ nội dung.

Quy trình dọn dẹp (sweep) gồm hai giai đoạn: giai đoạn đầu xử lý các chuỗi ký tự, giai đoạn sau xử lý các đối tượng khác. Xem đoạn mã tại lgc.c dòng 573:

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

  case GCSsweepstring: {
   lu_mem old = g->totalbytes;
   sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
   if (g->sweepstrgc >= g->strt.size) /* không còn gì để dọn nữa? */
    g->gcstate = GCSsweep; /* kết thúc giai đoạn quét chuỗi */
   lua_assert(old >= g->totalbytes);
   g->estimate -= old - g->totalbytes;
   return GCSWEEPCOST;
  }
  case GCSsweep: {
   lu_mem old = g->totalbytes;
   g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
   if (*g->sweepgc == NULL) { /* không còn gì để quét nữa? */
    checkSizes(L);
    g->gcstate = GCSfinalize; /* kết thúc giai đoạn quét */
   }
   lua_assert(old >= g->totalbytes);
   g->estimate -= old - g->totalbytes;
   return GCSWEEPMAX*GCSWEEPCOST;
  }

Trong trạng thái GCSsweepstring, mỗi bước gọi sweepwholelist sẽ xử lý một cột trong bảng băm của strt. Trong điều kiện lý tưởng, mọi chuỗi đều được phân bố đều trong bảng băm không có va chạm, mỗi cột sẽ chứa đúng một chuỗi. Chúng ta có thể tham khảo đoạn mã tại lstring.c dòng 68:

1
2

 if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
  luaS_resize(L, tb->size*2); /* quá tải */

Khi số lượng chuỗi (nuse) trong bảng băm vượt quá số cột (size), Lua sẽ nhân đôi kích thước bảng băm. Đây là cơ chế ước lượng dựa trên nguyên tắc mỗi cột chứa một phần tử.

Đáng chú ý là với GC phân đoạn, trong giai đoạn này có thể không dọn dẹp triệt để các đối tượng chuỗi. Khi xảy ra sự kiện mở rộng bảng băm trong quá trình GCSsweepstring, bảng băm sẽ được tổ chức lại (rehash). Những chuỗi chưa kịp dọn dẹp có thể bị phân bố lại vào các cột đã được quét qua ở giai đoạn GCSsweepstring. Khi đó, một số đối tượng chuỗi sẽ không có cơ hội được đặt lại màu trắng trong chu kỳ GC hiện tại. Trong một số trường hợp cực đoan, ngay cả khi gọi fullgc cũng không thể dọn dẹp hoàn toàn rác.

Cần lưu ý thêm về đối tượng chuỗi: Lua tái sử dụng các đối tượng TString có cùng giá trị, đảm bảo không tồn tại hai bản sao của cùng một chuỗi. Tuy nhiên, cơ chế GC phân đoạn có thể khiến một số đối tượng TString chờ dọn dẹp “hồi sinh”. Do đó, khi tạo đối tượng TString mới, Lua thực hiện kiểm tra, xem lstring.c dòng 86:

1
2
3
4
5

  if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
   /* chuỗi có thể đã chết */
   if (isdead(G(L), o)) changewhite(o);
   return ts;
  }

Vấn đề tương tự cũng tồn tại với upvalue, và cũng có cơ chế kiểm tra tương ứng.

Giá trị GCSWEEPCOST là một hằng số kinh nghiệm. Như đã biết ở phần trước, giá trị này xác định thời gian thực hiện của phương thức luaC_step. Điều này giúp đảm bảo thời gian thực hiện mỗi lần gọi API gần như không đổi. Trong giai đoạn đánh dấu, giá trị này được xác định dựa trên số byte quét được. Trong khi đó, thời gian giải phóng một chuỗi gần như không đổi (không phụ thuộc độ dài chuỗi), nên GCSWEEPCOST đại diện cho chi phí giải phóng một đối tượng.

GCSsweep xử lý toàn bộ danh sách liên kết GCObject. Vì danh sách này rất dài nên cũng được xử lý theo từng đoạn. Con trỏ sweepgc theo dõi vị trí hiện tại, mỗi lần xử lý GCSWEEPMAX đối tượng. Dù có thực hiện dọn dẹp hay không, chi phí cho mỗi lần duyệt đều gần như nhau. Đối với các đối tượng còn sống, cần đặt lại bit màu; đối tượng chết cần giải phóng bộ nhớ. Chi phí mỗi lần GCSsweep chắc chắn lớn hơn GCSsweepstring. Thời gian ước tính là GCSWEEPMAX*GCSWEEPCOST.

Hàm sweeplist tại lgc.c dòng 408 thực hiện công việc dọn dẹp thực sự:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
 GCObject *curr;
 global_State *g = G(L);
 int deadmask = otherwhite(g);
 while ((curr = *p) != NULL && count-- > 0) {
  if (curr->gch.tt == LUA_TTHREAD) /* quét upvalue mở của từng thread */
   sweepwholelist(L, &gco2th(curr)->openupval);
  if ((curr->gch.marked ^ WHITEBITS) & deadmask) { /* chưa chết? */
   lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
   makewhite(g, curr); /* đặt màu trắng (cho chu kỳ sau) */
   p = &curr->gch.next;
  }
  else { /* cần xóa `curr' */
   lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
   *p = curr->gch.next;
   if (curr == g->rootgc) /* có phải phần tử đầu danh sách? */
    g->rootgc = curr->gch.next; /* điều chỉnh phần tử đầu */
   freeobj(L, curr);
  }
 }
 return p;
}

Nửa đoạn mã sau dễ hiểu: khi đối tượng còn sống gọi makewhite; khi chết gọi freeobj. sweeplist bắt đầu từ sweepgc chứ không phải rootgc (dù hai giá trị này có thể trùng nhau), nên cần xử lý đặc biệt với