gc

Thu gom rác là giải phóng bộ nhớ đối tượng không còn được sử dụng, giải phóng không gian cho các đối tượng khác. Chỉ một câu mô tả đơn giản như vậy nhưng việc triển khai lại vô cùng không đơn giản, lịch sử phát triển của thu gom rác đã có hàng chục năm, sớm nhất vào những năm 60 của thế kỷ trước ngôn ngữ Lisp đã lần đầu áp dụng cơ chế thu gom rác, như chúng ta đã biết Python, Objective-C, cơ chế GC chủ yếu của chúng là đếm tham chiếu, Java, C# áp dụng thu gom theo thế hệ. Ngày nay khi nói đến thu gom rác, xét từ thuật toán thu gom có thể chia thành các loại lớn sau:

• Đếm tham chiếu: khiến mỗi đối tượng ghi lại số lần được tham chiếu, khi đếm về 0 thì thu hồi
• Đánh dấu xóa: đánh dấu đối tượng hoạt động, thu hồi đối tượng không được đánh dấu
• Thuật toán sao chép: sao chép đối tượng hoạt động vào bộ nhớ mới, thu hồi tất cả đối tượng trong bộ nhớ cũ, đạt được mục đích thu gom rác
• Đánh dấu nén: phiên bản nâng cấp của đánh dấu xóa, khi thu gom di chuyển đối tượng hoạt động đến đầu heap, tiện quản lý

Xét từ cách áp dụng có thể chia thành các loại lớn sau:

• Thu gom toàn cục: một lần trực tiếp thu gom tất cả rác
• Thu gom theo thế hệ: chia thành các thế hệ khác nhau dựa trên thời gian sống của đối tượng, rồi áp dụng các thuật toán thu gom khác nhau
• Thu gom gia tăng: mỗi lần chỉ thực hiện thu gom cục bộ

TIP

Đến The Journey of Go's Garbage Collector đọc bản gốc tiếng Anh, tìm hiểu thêm về lịch sử thu gom rác của Go

Khi mới phát hành, cơ chế thu gom rác của Go vô cùng đơn giản, chỉ có thuật toán đánh dấu xóa đơn giản, STW (Stop The World, chỉ việc tạm dừng toàn bộ chương trình do thu gom rác) cao tới vài giây thậm chí lâu hơn. Nhận thức được vấn đề này, nhóm Go bắt đầu cải tiến thuật toán thu gom rác, giữa các phiên bản go1.0 đến go1.8, họ đã thử qua nhiều ý tưởng

1. GC sao chép concurrent với read barrier: chi phí read barrier có nhiều bất định, phương án này bị hủy bỏ
2. Bộ thu thập hướng yêu cầu (ROC): cần bật write barrier mọi lúc, làm chậm tốc độ chạy, kéo dài thời gian biên dịch
3. Thu gom theo thế hệ: hiệu suất thu gom theo thế hệ trong Go không cao, vì compiler của Go có xu hướng phân phối đối tượng mới vào stack, đối tượng tồn tại lâu phân phối vào heap, nên đa số đối tượng thế hệ mới sẽ được stack thu hồi trực tiếp.
4. Đánh dấu卡片 không write barrier: thay thế chi phí write barrier bằng chi phí băm hash, cần phần cứng hỗ trợ

Cuối cùng nhóm Go vẫn chọn kết hợp đánh dấu ba màu concurrent + write barrier, và không ngừng cải tiến tối ưu trong các phiên bản sau, cách làm này cũng được áp dụng đến nay, một nhóm hình dưới đây thể hiện biến động độ trễ GC từ go1.4 đến go1.9.

Khi viết bài này, phiên bản mới nhất của Go sắp đến go1.23, đối với Go ngày nay, hiệu suất GC đã không còn là vấn đề, độ trễ GC hiện nay trong hầu hết các trường hợp đều dưới 100 micro giây, đáp ứng nhu cầu của hầu hết các kịch bản nghiệp vụ.

Nhìn chung, thu gom rác trong Go có thể chia thành các giai đoạn sau

• Giai đoạn quét: thu thập đối tượng root từ stack và biến toàn cục
• Giai đoạn đánh dấu: tô màu đối tượng
• Giai đoạn kết thúc đánh dấu: xử lý công việc hậu kỳ, đóng barrier
• Giai đoạn thu hồi: giải phóng và thu hồi bộ nhớ đối tượng rác

Khái niệm

Trong tài liệu và bài viết chính thức có thể xuất hiện các khái niệm sau, dưới đây giải thích đơn giản

• Mutator (赋值器): một cách diễn đạt thuật ngữ, chỉ chương trình người dùng, trong Go chỉ code người dùng
• Collector (收集器): chỉ chương trình负责 thu gom rác, trong Go负责 thu gom rác là runtime
• Finalizer (终结器): chỉ code负责 thu hồi giải phóng清理 bộ nhớ đối tượng sau khi công việc đánh dấu quét hoàn thành
• Controller (控制器): chỉ biến toàn cục runtime.gcController, kiểu của nó là gcControllerState, cái sau triển khai thuật toán pacing,负责 xác định khi nào thực hiện thu gom rác và thực hiện bao nhiêu công việc.
• Limiter (限制器): chỉ runtime.gcCPULimiter, nó负责 ngăn CPU chiếm dụng quá cao khi thu gom rác ảnh hưởng đến chương trình người dùng

Kích hoạt

func gcStart(trigger gcTrigger)

Thu gom rác được khởi động bởi hàm runtime.gcStart, nó chỉ nhận tham số cấu trúc runtime.gcTrigger, trong đó chứa nguyên nhân kích hoạt GC, thời gian hiện tại, và đây là vòng GC thứ mấy.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: current time
    n    uint32 // gcTriggerCycle: cycle number to start
}

Trong đó gcTriggerKind có các giá trị tùy chọn sau

const (
  // gcTriggerHeap indicates that a cycle should be started when
  // the heap size reaches the trigger heap size computed by the
  // controller.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indicates that a cycle should be started when
  // it's been more than forcegcperiod nanoseconds since the
  // previous GC cycle.
  gcTriggerTime

  // gcTriggerCycle indicates that a cycle should be started if
  // we have not yet started cycle number gcTrigger.n (relative
  // to work.cycles).
  gcTriggerCycle
)

Nhìn chung thời điểm kích hoạt thu gom rác có ba loại

• Khi tạo đối tượng mới: khi gọi runtime.mallocgc phân phối bộ nhớ, nếu phát hiện bộ nhớ heap đạt ngưỡng (nói chung là gấp đôi lần GC trước, giá trị này cũng sẽ được thuật toán pacing điều chỉnh), sẽ khởi động thu gom rác

  func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
      ...
    if shouldhelpgc {
      if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
        gcStart(t)
      }
    }
      ...
  }

• Định thời cưỡng chế kích hoạt: Go sẽ khởi động một goroutine độc lập trong runtime để chạy hàm runtime.forcegchelper, nếu lâu không thu gom rác, nó sẽ cưỡng chế khởi động GC, thời gian này do hằng số runtime.forcegcperiod quyết định, giá trị là 2 phút, đồng thời trong goroutine giám sát hệ thống cũng sẽ định thời kiểm tra xem có cần cưỡng chế GC không

  func forcegchelper() {
    for {
          ...
      gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
          ...
    }
  }

  func sysmon() {
      ...
    for {
          ...
      // check if we need to force a GC
      if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && forcegc.idle.Load() {
        lock(&forcegc.lock)
        forcegc.idle.Store(false)
        var list gList
        list.push(forcegc.g)
        injectglist(&list)
        unlock(&forcegc.lock)
      }
    }
  }

• Kích hoạt thủ công: thông qua hàm runtime.GC, người dùng có thể thủ công kích hoạt thu gom rác.

  func GC() {
      ...
    n := work.cycles.Load()
    gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
      ...
  }

TIP

Nếu quan tâm có thể đến Go Gc Pacer Re-Design đọc bản gốc tiếng Anh, trong đó讲解 về设计理念 và cải tiến của thuật toán pacing kích hoạt GC, vì nội dung khá phức tạp liên quan nhiều công thức toán, phần正文 không trình bày quá nhiều.

Đánh dấu

Hiện nay thuật toán GC của Go vẫn là đánh dấu trước sau xóa, nhưng việc triển khai không còn đơn giản như trước.

Đánh dấu-xóa

Bắt đầu từ thuật toán đánh dấu xóa đơn giản nhất, trong bộ nhớ, mối quan hệ tham chiếu giữa các đối tượng sẽ cấu thành một đồ thị, công việc thu gom rác sẽ thực hiện trên đồ thị này, công việc chia làm hai giai đoạn:

• Giai đoạn đánh dấu: bắt đầu từ node root (node root thường là biến trên stack, biến toàn cục và các đối tượng hoạt động khác), lần lượt duyệt qua mỗi node có thể đến được, và đánh dấu là đối tượng hoạt động, cho đến khi duyệt xong tất cả node có thể đến được,
• Giai đoạn xóa: duyệt tất cả đối tượng trong heap, thu hồi đối tượng không được đánh dấu, giải phóng hoặc tái sử dụng không gian bộ nhớ của nó.

Trong quá trình thu gom, cấu trúc đồ thị đối tượng không được thay đổi, nên phải dừng toàn bộ chương trình,也就是 STW, sau khi thu gom xong mới có thể tiếp tục chạy, nhược điểm của thuật toán này là thời gian tiêu tốn khá dài, khá ảnh hưởng đến hiệu suất chạy chương trình, đây là thuật toán đánh dấu mà phiên bản Go sớm sử dụng, nhược điểm của nó khá rõ ràng

• Sẽ sinh ra các mảnh bộ nhớ (vì cách quản lý bộ nhớ kiểu TCMalloc của Go, ảnh hưởng của vấn đề mảnh không lớn)
• Trong giai đoạn đánh dấu sẽ quét tất cả đối tượng trong heap
• Sẽ gây ra STW, tạm dừng toàn bộ chương trình, và thời gian không ngắn

Đánh dấu ba màu

Để cải thiện hiệu suất, Go áp dụng thuật toán đánh dấu ba màu kinh điển, gọi là ba màu, chỉ ba màu đen xám trắng:

• Màu đen: trong quá trình đánh dấu đối tượng đã được truy cập, và đối tượng mà nó trực tiếp tham chiếu cũng đã được truy cập, biểu thị đối tượng hoạt động
• Màu xám: trong quá trình đánh dấu đối tượng đã được truy cập, nhưng đối tượng mà nó trực tiếp tham chiếu chưa được truy cập hết, khi truy cập hết sẽ chuyển thành màu đen, biểu thị đối tượng hoạt động
• Màu trắng: trong quá trình đánh dấu chưa bao giờ được truy cập, sau khi truy cập sẽ chuyển thành màu xám, biểu thị có thể là đối tượng rác,

Khi bắt đầu công việc đánh dấu ba màu, trên sân chỉ có đối tượng xám và trắng, tất cả đối tượng root đều là màu xám, các đối tượng khác đều là màu trắng, như hình dưới đây

Mỗi vòng đánh dấu bắt đầu, trước tiên bắt đầu từ đối tượng xám, đánh dấu đối tượng xám thành màu đen, biểu thị nó là đối tượng hoạt động, rồi đánh dấu tất cả đối tượng mà đối tượng màu đen trực tiếp tham chiếu thành màu xám, còn lại là màu trắng, lúc này trên sân đã có ba màu đen xám trắng.

Lặp lại các bước trên, cho đến khi trên sân chỉ còn đối tượng màu đen và trắng, khi tập hợp đối tượng xám rỗng, biểu thị đánh dấu kết thúc, như hình dưới

Sau khi đánh dấu kết thúc, trong giai đoạn xóa chỉ cần giải phóng bộ nhớ của đối tượng trong tập hợp màu trắng.

Tính bất biến

Bản thân thuật toán đánh dấu ba màu không thể thực hiện đánh dấu concurrent (chỉ việc chương trình vừa chạy vừa đánh dấu), nếu trong khi đánh dấu cấu trúc đồ thị đối tượng thay đổi, có thể dẫn đến hai tình huống

• Đánh dấu thừa: sau khi đối tượng được đánh dấu màu đen, chương trình người dùng xóa tất cả tham chiếu đối với đối tượng này, thì nó nên là đối tượng màu trắng cần được xóa
• Bỏ sót đánh dấu: sau khi đối tượng được đánh dấu màu trắng, có đối tượng khác trong chương trình người dùng tham chiếu đối tượng này, thì nó nên là đối tượng màu đen không nên bị xóa

Đối với tình huống đầu tiên thực ra có thể chấp nhận, vì đối tượng chưa được xóa có thể được xử lý trong vòng thu gom tiếp theo. Nhưng tình huống thứ hai thì không thể chấp nhận, bộ nhớ đối tượng đang sử dụng bị giải phóng sai, sẽ gây ra lỗi chương trình nghiêm trọng, đây là vấn đề bắt buộc phải tránh.

Khái niệm tính bất biến ba màu đến từ bài luận văn 《Barrier techniques for incremental tracing》 do Pekka P. Pirinen phát biểu năm 1998, nó chỉ hai tính bất biến của màu đối tượng khi đánh dấu concurrent:

• Tính bất biến ba màu mạnh: đối tượng màu đen không thể trực tiếp tham chiếu đối tượng màu trắng

• Tính bất biến ba màu yếu: khi đối tượng màu đen trực tiếp tham chiếu đối tượng màu trắng, phải có đối tượng màu xám khác có thể trực tiếp hoặc gián tiếp truy cập đến đối tượng màu trắng đó, gọi là được bảo vệ bởi đối tượng màu xám

Đối với tính bất biến ba màu mạnh而言, biết đối tượng màu đen 3 là đối tượng đã được truy cập, và các đối tượng con mà nó trực tiếp tham chiếu cũng đã được truy cập và đánh dấu màu xám, nếu lúc này chương trình người dùng并发 thêm tham chiếu mới của đối tượng màu trắng 7 vào đối tượng màu đen 3, bình thường đối tượng màu trắng 7 nên được đánh dấu màu xám, nhưng vì đối tượng màu đen 3 đã được truy cập rồi, đối tượng 7 sẽ không được truy cập, nên nó luôn là đối tượng màu trắng, và cuối cùng bị xóa sai.

Đối với tính bất biến ba màu yếu而言, nó thực ra cũng giống như tính bất biến ba màu mạnh, vì đối tượng màu xám có thể trực tiếp hoặc gián tiếp truy cập đến đối tượng màu trắng đó, trong quá trình đánh dấu sau nó cuối cùng sẽ được đánh dấu màu xám, từ đó tránh bị xóa nhầm.

Thông qua tính bất biến, có thể đảm bảo trong quá trình đánh dấu sẽ không có đối tượng bị xóa nhầm, cũng có thể đảm bảo tính chính xác của công việc đánh dấu trong điều kiện concurrent, từ đó có thể khiến đánh dấu ba màu hoạt động concurrent, như vậy hiệu suất đánh dấu của nó so với thuật toán đánh dấu-xóa sẽ nâng cao khá nhiều. Để đảm bảo tính bất biến ba màu trong điều kiện concurrent, then chốt nằm ở kỹ thuật barrier.

Công việc đánh dấu

Trong giai đoạn quét GC, có một biến toàn cục runtime.gcphase dùng để biểu thị trạng thái GC, có các giá trị tùy chọn sau:

• _GCoff: công việc đánh dấu chưa bắt đầu
• _GCmark: công việc đánh dấu đã bắt đầu
• _GCmarktermination: công việc đánh dấu sắp kết thúc

Khi công việc đánh dấu bắt đầu, trạng thái runtime.gcphase là _GCmark, thực thi công việc đánh dấu là hàm runtime.gcDrain, trong đó tham số runtime.gcWork là một buffer pool, nó chứa các con trỏ đối tượng cần theo dõi.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Khi làm việc, nó sẽ thử lấy con trỏ có thể theo dõi từ buffer pool, nếu có thì gọi hàm runtime.scanobject tiếp tục thực thi nhiệm vụ quét, tác dụng của nó là liên tục quét đối tượng trong buffer, tô đen chúng.

if work.full == 0 {
    gcw.balance()
}

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Flush the write barrier
        // buffer; this may create
        // more work.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // Unable to get work.
    break
}
scanobject(b, gcw)

Khi P bị chiếm quyền hoặc sẽ xảy ra STW thì công việc quét mới dừng

for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
  ...
  scanobject(b, gcw)
  ...
}

runtime.gcwork là một hàng队列 áp dụng mô hình producer/consumer, hàng队列 này负责 chứa đối tượng màu xám待 quét, mỗi processor P本地 đều có một hàng队列 như vậy, tương ứng với trường ``runtime.p.gcw`.

func scanobject(b uintptr, gcw *gcWork) {
  ...
  for {
    var addr uintptr
    if hbits, addr = hbits.nextFast(); addr == 0 {
            if hbits, addr = hbits.next(); addr == 0 {
                break
            }
        }
    scanSize = addr - b + goarch.PtrSize
    obj := *(*uintptr)(unsafe.Pointer(addr))
    if obj != 0 && obj-b >= n {
      if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
        greyobject(obj, b, addr-b, span, gcw, objIndex)
      }
    }
  }
  gcw.bytesMarked += uint64(n)
  gcw.heapScanWork += int64(scanSize)
}

Hàm runitme.scanobject khi quét sẽ liên tục đánh dấu đối tượng màu trắng có thể đến được thành màu xám, rồi thông qua gọi gcw.put放入 hàng队列 địa phương, đồng thời hàm gcDrain cũng sẽ liên tục thông qua gcw.tryget để lấy đối tượng màu xám để tiếp tục quét. Quá trình đánh dấu quét là gia tăng, không cần một hơi hoàn thành tất cả công việc đánh dấu, khi nhiệm vụ đánh dấu bị chiếm quyền vì một số nguyên nhân sẽ bị gián đoạn, đợi phục hồi sau có thể căn cứ vào đối tượng màu xám còn lại trong hàng队列 để tiếp tục hoàn thành công việc đánh dấu.

Đánh dấu nền

Công việc đánh dấu sẽ không thực thi ngay khi GC bắt đầu, khi vừa kích hoạt GC, Go sẽ tạo số lượng nhiệm vụ đánh dấu bằng với tổng số processor P hiện tại, chúng sẽ được thêm vào hàng队列 nhiệm vụ toàn cục, rồi đi vào ngủ đợi đến khi được đánh thức trong giai đoạn đánh dấu. Trong runtime, do runtime.gcBgMarkStartWorkers để phân phối nhiệm vụ, nhiệm vụ đánh dấu thực tế chỉ là hàm runtime.gcBgMarkWorker, trong đó hai biến toàn cục runtime gcBgMarkWorkerCount và gomaxprocs lần lượt biểu thị số lượng worker hiện tại và số lượng processor P.

func gcBgMarkStartWorkers() {
  // Background marking is performed by per-P G's. Ensure that each P has
  // a background GC G.
  //
  // Worker Gs don't exit if gomaxprocs is reduced. If it is raised
  // again, we can reuse the old workers; no need to create new workers.
  for gcBgMarkWorkerCount < gomaxprocs {
    go gcBgMarkWorker()

    notetsleepg(&work.bgMarkReady, -1)
    noteclear(&work.bgMarkReady)
    // The worker is now guaranteed to be added to the pool before
    // its P's next findRunnableGCWorker.

    gcBgMarkWorkerCount++
  }
}

Sau khi worker khởi động, nó sẽ tạo một cấu trúc runtime.gcBgMarkWorkerNode, thêm vào pool worker toàn cục runitme.gcBgMarkWorkerPool, rồi gọi hàm runtime.gopark để khiến goroutine rơi vào trạng thái ngủ

func gcBgMarkWorker() {
    ...
  node := new(gcBgMarkWorkerNode)
  node.gp.set(gp)
  notewakeup(&work.bgMarkReady)

  for {
    // Go to sleep until woken by
    // gcController.findRunnableGCWorker.
    gopark(func(g *g, nodep unsafe.Pointer) bool {
      node := (*gcBgMarkWorkerNode)(nodep)
      // Release this G to the pool.
      gcBgMarkWorkerPool.push(&node.node)
      // Note that at this point, the G may immediately be
      // rescheduled and may be running.
      return true
    }, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceBlockSystemGoroutine, 0)
    }
    ...
}

Có hai tình huống có thể đánh thức worker

• Khi ở giai đoạn đánh dấu, vòng điều phối sẽ đánh thức worker đang ngủ thông qua hàm runtime.runtime.gcController.findRunnableGCWorker
• Khi ở giai đoạn đánh dấu, nếu processor P hiện tại ở trạng thái rảnh, vòng điều phối sẽ thử trực tiếp lấy worker khả dụng từ pool worker toàn cục gcBgMarkWorkerPool

func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
top:
    // Try to schedule a GC worker.
  if gcBlackenEnabled != 0 {
    gp, tnow := gcController.findRunnableGCWorker(pp, now)
    if gp != nil {
      return gp, false, true
    }
    now = tnow
  }
    ...
    // We have nothing to do.
  //
  // If we're in the GC mark phase, can safely scan and blacken objects,
  // and have work to do, run idle-time marking rather than give up the P.
  if gcBlackenEnabled != 0 && gcMarkWorkAvailable(pp) && gcController.addIdleMarkWorker() {
    node := (*gcBgMarkWorkerNode)(gcBgMarkWorkerPool.pop())
    if node != nil {
      pp.gcMarkWorkerMode = gcMarkWorkerIdleMode
      gp := node.gp.ptr()

      trace := traceAcquire()
      casgstatus(gp, _Gwaiting, _Grunnable)
      if trace.ok() {
        trace.GoUnpark(gp, 0)
        traceRelease(trace)
      }
      return gp, false, false
    }
    gcController.removeIdleMarkWorker()
  }
    ...
}

Processor P có một trường trong cấu trúc gcMarkWorkerMode để biểu thị chế độ thực thi nhiệm vụ đánh dấu, nó có các giá trị tùy chọn sau:

• gcMarkWorkerNotWorker: biểu thị processor P hiện tại không đang thực thi nhiệm vụ đánh dấu

• gcMarkWorkerDedicatedMode: biểu thị processor P hiện tại chuyên dụng để thực thi nhiệm vụ đánh dấu, và trong thời gian không bị chiếm quyền.

• gcMarkWorkerFractionalMode: biểu thị processor hiện tại vì tỷ lệ sử dụng GC không đạt chuẩn (25% đạt chuẩn) mới thực thi nhiệm vụ đánh dấu, trong thời gian thực thi có thể bị chiếm quyền. Giả sử số lượng processor P hiện tại là 5, căn cứ công thức tính lúc này cần một processor P chuyên dụng đánh dấu, tỷ lệ sử dụng chỉ đạt 20%, 5% tỷ lệ sử dụng còn lại cần mở một processor P FractionalMode để bù đắp. Code tính toán cụ thể như sau

  func (c *gcControllerState) startCycle(markStartTime int64, procs int, trigger gcTrigger) {
    ...
    totalUtilizationGoal := float64(procs) * gcBackgroundUtilization
    dedicatedMarkWorkersNeeded := int64(totalUtilizationGoal + 0.5)
      if float64(dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
          // Too many dedicated workers.
          dedicatedMarkWorkersNeeded--
      }
      c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(dedicatedMarkWorkersNeeded)) / float64(procs)
      ...
  }

• gcMarkWorkerIdleMode: biểu thị processor hiện tại vì rảnh mới thực thi nhiệm vụ đánh dấu, trong thời gian thực thi có thể bị chiếm quyền.

Nhóm Go không hy vọng GC chiếm dụng quá nhiều hiệu suất ảnh hưởng đến chương trình người dùng chạy bình thường, thông qua các chế độ khác nhau này để thực hiện công việc đánh dấu, có thể hoàn thành GC trong trường hợp không lãng phí hiệu suất cũng không ảnh hưởng đến chương trình người dùng. Có thể chú ý là đơn vị phân phối cơ bản của nhiệm vụ đánh dấu là processor P, nên công việc đánh dấu là concurrent, nhiều nhiệm vụ đánh dấu và chương trình người dùng concurrent thực thi, không ảnh hưởng lẫn nhau.

Hỗ trợ đánh dấu

Goroutine G trong runtime có một trường gcAssistBytes, ở đây gọi là điểm tín dụng hỗ trợ GC. Khi ở trạng thái đánh dấu GC, khi một goroutine thử申请若干 kích thước bộ nhớ, nó sẽ bị trừ điểm tín dụng bằng với kích thước bộ nhớ申请. Nếu lúc này điểm tín dụng là số âm, thì goroutine này phải hỗ trợ hoàn thành lượng công việc quét GC định lượng để trả nợ điểm tín dụng, khi điểm tín dụng là số dương, goroutine có thể không cần hoàn thành nhiệm vụ hỗ trợ đánh dấu nữa.

Hàm trừ điểm tín dụng là runtime.deductAssistCredit, nó sẽ được gọi trước khi hàm runtime.mallocgc phân phối bộ nhớ.

func deductAssistCredit(size uintptr) *g {
    var assistG *g
    if gcBlackenEnabled != 0 {
       // Charge the current user G for this allocation.
       assistG = getg()
       if assistG.m.curg != nil {
          assistG = assistG.m.curg
       }
       // Charge the allocation against the G. We'll account
       // for internal fragmentation at the end of mallocgc.
       assistG.gcAssistBytes -= int64(size)

       if assistG.gcAssistBytes < 0 {
          // This G is in debt. Assist the GC to correct
          // this before allocating. This must happen
          // before disabling preemption.
          gcAssistAlloc(assistG)
       }
    }
    return assistG
}

Tuy nhiên khi goroutine hoàn thành công việc quét hỗ trợ định lượng, sẽ trả lại điểm tín dụng định lượng cho goroutine hiện tại, hàm thực sự负责 hỗ trợ đánh dấu là runtime.gcDrainN.

func gcAssistAlloc1(gp *g, scanWork int64) {
    ...
  gcw := &getg().m.p.ptr().gcw
    // 完成工作了
  workDone := gcDrainN(gcw, scanWork)
  ...
  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(workDone))
    ...
}

Vì quét là concurrent, trong công việc đã ghi lại chỉ có một phần là của goroutine hiện tại, phần công việc còn lại sẽ căn cứ vào thứ tự hàng队列 hỗ trợ để lần lượt trả nợ cho các goroutine khác, nếu còn dư, sẽ thêm vào điểm tín dụng toàn cục gcController.assistBytesPerWork.

func gcFlushBgCredit(scanWork int64) {
    // 如果队列为空则直接添加到全局积分中
  if work.assistQueue.q.empty() {
    gcController.bgScanCredit.Add(scanWork)
    return
  }

  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  scanBytes := int64(float64(scanWork) * assistBytesPerWork)

  lock(&work.assistQueue.lock)
  for !work.assistQueue.q.empty() && scanBytes > 0 {
    gp := work.assistQueue.q.pop()
    if scanBytes+gp.gcAssistBytes >= 0 {
      scanBytes += gp.gcAssistBytes
      gp.gcAssistBytes = 0
      ready(gp, 0, false)
    } else {
      gp.gcAssistBytes += scanBytes
      scanBytes = 0
      work.assistQueue.q.pushBack(gp)
      break
    }
  }

    // 还有剩余
  if scanBytes > 0 {
    assistWorkPerByte := gcController.assistWorkPerByte.Load()
    scanWork = int64(float64(scanBytes) * assistWorkPerByte)
    gcController.bgScanCredit.Add(scanWork)
  }
  unlock(&work.assistQueue.lock)
}

Tương ứng, khi cần trả điểm tín dụng quá nhiều (申请 bộ nhớ quá lớn), cũng có thể dùng điểm tín dụng toàn cục để khấu trừ một phần nợ của mình

func gcAssistAlloc(gp *g) {
  ...
  assistWorkPerByte := gcController.assistWorkPerByte.Load()
  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  debtBytes := -gp.gcAssistBytes
  scanWork := int64(assistWorkPerByte * float64(debtBytes))
  if scanWork < gcOverAssistWork {
    scanWork = gcOverAssistWork
    debtBytes = int64(assistBytesPerWork * float64(scanWork))
  }

    // 用全局积分抵押
  bgScanCredit := gcController.bgScanCredit.Load()
  stolen := int64(0)
  if bgScanCredit > 0 {
    if bgScanCredit < scanWork {
      stolen = bgScanCredit
      gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(stolen))
    } else {
      stolen = scanWork
      gp.gcAssistBytes += debtBytes
    }
    gcController.bgScanCredit.Add(-stolen)

    scanWork -= stolen

    if scanWork == 0 {
      return
    }
  }
    ...
}

Hỗ trợ đánh dấu là một phương tiện cân bằng trong điều kiện tải cao, tốc độ phân phối bộ nhớ của chương trình người dùng cao hơn nhiều so với tốc độ đánh dấu, phân phối bao nhiêu bộ nhớ thì thực hiện bấy nhiêu công việc đánh dấu.

Kết thúc đánh dấu

Khi tất cả đối tượng màu xám có thể đến được đều đã được tô đen, lúc này chuyển từ trạng thái _GCmark sang trạng thái _GCmarktermination, quá trình này do hàm runtime.gcMarkDone hoàn thành. Khi bắt đầu, nó sẽ kiểm tra xem còn nhiệm vụ cần thực thi không,

top:

  if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
    return
  }

  gcMarkDoneFlushed = 0
  // 将所有因写屏障拦截的标记操作全部批量的执行
  forEachP(waitReasonGCMarkTermination, func(pp *p) {
    wbBufFlush1(pp)
    pp.gcw.dispose()
    if pp.gcw.flushedWork {
      atomic.Xadd(&gcMarkDoneFlushed, 1)
      pp.gcw.flushedWork = false
    }
  })

  if gcMarkDoneFlushed != 0 {
    goto top
  }

Khi không còn nhiệm vụ toàn cục và nhiệm vụ địa phương cần thực thi, gọi runtime.stopTheWorldWithSema để STW, rồi làm một số công việc hậu kỳ

// Disable assists and background workers. We must do
// this before waking blocked assists.
atomic.Store(&gcBlackenEnabled, 0)

// Notify the CPU limiter that GC assists will now cease.
gcCPULimiter.startGCTransition(false, now)

// Wake all blocked assists. These will run when we
// start the world again.
gcWakeAllAssists()

// In STW mode, re-enable user goroutines. These will be
// queued to run after we start the world.
schedEnableUser(true)

// endCycle depends on all gcWork cache stats being flushed.
// The termination algorithm above ensured that up to
// allocations since the ragged barrier.
gcController.endCycle(now, int(gomaxprocs), work.userForced)

// Perform mark termination. This will restart the world.
gcMarkTermination(stw)

Đầu tiên đặt runtime.BlackenEnabled thành 0, biểu thị công việc đánh dấu đã kết thúc, thông báo cho limiter hỗ trợ đánh dấu đã kết thúc, đóng memory barrier, đánh thức tất cả goroutine đang ngủ vì hỗ trợ đánh dấu, rồi sau đó đánh thức lại tất cả goroutine người dùng, còn phải thu thập các loại dữ liệu khác nhau của công việc quét vòng này để điều chỉnh thuật toán pacing chuẩn bị cho vòng quét tiếp theo, sau khi hoàn thành công việc hậu kỳ, gọi hàm runtime.gcSweep để xóa đối tượng rác, cuối cùng gọi runtime.startTheWorldWithSema để chương trình phục hồi chạy.

Barrier

Tác dụng của memory barrier có thể hiểu là hook hành vi gán giá trị của đối tượng, làm một số thao tác chỉ định trước khi gán giá trị, loại code hook này thường được compiler chèn vào code trong thời gian biên dịch.前面 đã đề cập, đánh dấu ba màu trong điều kiện concurrent thêm và xóa tham chiếu đối tượng đều sẽ dẫn đến vấn đề, vì cả hai đều là thao tác ghi (xóa là gán giá trị rỗng), nên barrier chặn chúng được gọi chung là write barrier. Nhưng barrier mechanism không phải không có chi phí, chặn thao tác ghi bộ nhớ sẽ gây ra chi phí ngoài, nên barrier mechanism chỉ có hiệu lực trên heap, xét đến độ phức tạp triển khai và chi phí hiệu suất, đối với stack và register thì không phạm vi tác dụng.

TIP

Muốn tìm hiểu thêm chi tiết áp dụng barrier technology của Go, đến Eliminate STW stack rescan đọc bản gốc tiếng Anh, bài viết này tham khảo nhiều nội dung.

Insert write barrier

Insert write barrier do Dijkstra đề xuất, nó thỏa mãn tính bất biến ba màu mạnh. Khi thêm một tham chiếu đối tượng màu trắng mới vào đối tượng màu đen, insert write barrier sẽ chặn thao tác này, đánh dấu đối tượng màu trắng đó thành màu xám, như vậy có thể tránh đối tượng màu đen trực tiếp tham chiếu đối tượng màu trắng, đảm bảo tính bất biến ba màu mạnh, điều này khá dễ hiểu.

前面 đã đề cập write barrier sẽ không áp dụng trên stack, nếu trong quá trình đánh dấu concurrent mối quan hệ tham chiếu của đối tượng stack thay đổi, ví dụ đối tượng màu đen trong stack tham chiếu đối tượng màu trắng trong heap, nên để đảm bảo tính chính xác của đối tượng stack, chỉ có thể sau khi đánh dấu kết thúc lần nữa đánh dấu tất cả đối tượng trong stack thành đối tượng màu xám, rồi quét lại một lần, bằng là một vòng đánh dấu phải quét hai lần không gian stack, và lần quét thứ hai bắt buộc phải STW, giả sử trong chương trình đồng thời tồn tại hàng trăm hàng ngàn goroutine stack, thì thời gian tiêu tốn của quá trình quét này sẽ không thể xem thường, căn cứ dữ liệu thống kê chính thức, thời gian tiêu tốn quét lại khoảng 10-100 mili giây.

Ưu điểm: Quét không cần STW

Nhược điểm: Cần quét lại không gian stack để đảm bảo tính chính xác, cần STW

Delete write barrier

Delete write barrier do Yuasa đề xuất, còn gọi là barrier dựa trên snapshot bắt đầu, cách này khi bắt đầu cần STW để ghi snapshot đối tượng root, và sẽ tô đen tất cả đối tượng root, tô xám tất cả đối tượng con cấp một, như vậy các đối tượng con màu trắng còn lại đều sẽ处于 sự bảo vệ của đối tượng màu xám. Nhóm Go không trực tiếp áp dụng delete write barrier, mà chọn kết hợp nó với insert write barrier, nên để tiện hiểu phần sau, ở đây vẫn phải讲解一下。Delete write barrier trong điều kiện concurrent đảm bảo tính chính xác的规则 là: khi xóa tham chiếu đối tượng màu trắng từ đối tượng màu xám hoặc trắng, sẽ trực tiếp đánh dấu đối tượng màu trắng thành đối tượng màu xám.

Chia làm hai tình huống để giải thích:

• Xóa tham chiếu của đối tượng màu xám đối với đối tượng màu trắng: Vì không biết đối tượng màu trắng downstream có được đối tượng màu đen tham chiếu không, hành động này có thể cắt đứt sự bảo vệ của đối tượng màu xám đối với đối tượng màu trắng

• Xóa tham chiếu của đối tượng màu trắng đối với đối tượng màu trắng: Vì không biết đối tượng màu trắng upstream có được đối tượng màu xám bảo vệ không, downstream có được đối tượng màu đen tham chiếu không, hành động này cũng có thể cắt đứt sự bảo vệ của đối tượng màu xám đối với đối tượng màu trắng

Bất kể là tình huống nào, delete write barrier sẽ đánh dấu đối tượng màu trắng được tham chiếu thành màu xám, như vậy có thể thỏa mãn tính bất biến ba màu yếu. Đây là một cách làm bảo thủ, vì tình hình upstream downstream không rõ, đánh dấu nó thành màu xám bằng là không coi nó là đối tượng rác nữa, cho dù sau khi xóa tham chiếu sẽ dẫn đến đối tượng này không thể đến được也就是 trở thành đối tượng rác, cũng vẫn sẽ đánh dấu nó thành màu xám, nó sẽ được giải phóng trong vòng quét tiếp theo, tổng tốt hơn so với đối tượng bị xóa nhầm dẫn đến lỗi bộ nhớ.

Ưu điểm: Vì đối tượng stack toàn đen, nên không cần quét lại không gian stack

Nhược điểm: Khi bắt đầu quét cần STW để ghi snapshot đối tượng root của không gian stack

Hybrid write barrier

Phiên bản go1.8 引用 cơ chế barrier mới: hybrid write barrier, tức kết hợp insert write barrier và delete write barrier, kết hợp ưu điểm của chúng:

• Insert write barrier khi bắt đầu không cần STW để ghi snapshot
• Delete write barrier không cần STW để quét lại không gian stack

Dưới đây là pseudocode do chính thức đưa ra:

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

Đơn giản讲解 một số khái niệm trong đó, trong đó slot là một con trỏ, biểu thị tham chiếu đối với đối tượng khác, *slot là đối tượng gốc, ptr là đối tượng mới, *slot=ptr là một thao tác gán giá trị, bằng là sửa đổi tham chiếu của đối tượng, gán giá trị rỗng là xóa tham chiếu, shade() biểu thị đánh dấu một đối tượng thành màu xám, shade(*slot) là đánh dấu đối tượng gốc thành màu xám, shade(ptr) là đánh dấu đối tượng mới thành màu xám, dưới đây là một ví dụ hình, giả sử đối tượng 1原来 tham chiếu đối tượng 2, rồi chương trình người dùng sửa đổi tham chiếu, khiến đối tượng 1 tham chiếu đối tượng 3, hybrid write barrier bắt được hành vi này, trong đó *slot đại diện cho đối tượng 2, ptr đại diện cho đối tượng 1.

Chính thức dùng một câu để khái quát tác dụng của pseudocode trên

the write barrier shades the object whose reference is being overwritten, and, if the current goroutine's stack has not yet been scanned, also shades the reference being installed.

Dịch ra là, khi hybrid write barrier chặn được thao tác ghi, sẽ đánh dấu đối tượng gốc thành màu xám, nếu stack của goroutine hiện tại chưa được quét qua, thì đánh dấu đối tượng mới cũng thành màu xám.

Khi công việc đánh dấu bắt đầu, cần quét không gian stack để thu thập đối tượng root, lúc này sẽ trực tiếp tô đen toàn bộ chúng, trong thời gian này bất kỳ đối tượng mới tạo nào cũng sẽ được đánh dấu màu đen, đảm bảo tất cả đều là đối tượng màu đen trong stack, nên current stack is grey trong pseudocode biểu thị stack của goroutine hiện tại chưa được quét qua, nên stack của goroutine chỉ có hai trạng thái, hoặc toàn đen hoặc toàn xám, trong quá trình từ toàn xám chuyển thành toàn đen cần tạm dừng goroutine hiện tại, nên dưới hybrid write barrier vẫn sẽ có STW cục bộ. Khi stack của goroutine toàn đen, lúc này nhất định thỏa mãn tính bất biến ba màu mạnh, vì sau khi quét đối tượng màu đen trong stack chỉ tham chiếu đối tượng màu xám, không tồn tại tình huống đối tượng màu đen trực tiếp tham chiếu đối tượng màu trắng, nên lúc này không cần insert write barrier, tương ứng pseudocode

if current stack is grey:
        shade(ptr)

Nhưng vẫn cần delete write barrier để thỏa mãn tính bất biến ba màu yếu,也就是

shade(*slot)

Sau khi quét xong, vì đối tượng không gian stack đã toàn đen rồi,就不再 cần quét lại không gian stack nữa, có thể tiết kiệm thời gian STW.

Đến đây,也就是 sau phiên bản go1.8, Go về cơ bản đã xác lập khung cơ bản của thu gom rác, các tối ưu liên quan đến thu gom rác trong các phiên bản sau cũng đều建立在 nền tảng hybrid write barrier, vì đã xóa bỏ phần lớn STW, lúc này độ trễ trung bình của thu gom rác đã giảm xuống mức micro giây.

Write buffer

Trong cơ chế barrier đã đề cập trước đó, khi chặn được thao tác ghi đều lập tức đánh dấu màu đối tượng, sau khi áp dụng hybrid write barrier, vì cần đánh dấu cả đối tượng gốc và đối tượng mới, nên công việc sẽ tăng gấp đôi, đồng thời code mà compiler chèn cũng sẽ tăng thêm. Để tối ưu hóa, trong phiên bản go1.10, write barrier khi thực hiện đánh dấu不再 sẽ lập tức đánh dấu màu đối tượng, mà sẽ lưu đối tượng gốc và đối tượng mới vào một buffer pool, đợi tích lũy đến một số lượng nhất định, rồi thực hiện đánh dấu hàng loạt, làm như vậy hiệu suất cao hơn.

Cấu trúc负责 cache là runtime.wbBuf, nó thực tế là một mảng, kích thước 512.

type wbBuf struct {
  next uintptr
  end uintptr
  buf [wbBufEntries]uintptr
}

Mỗi P本地 đều có một cache như vậy

type p struct {
    ...
  wbBuf wbBuf
    ...
}

Khi công việc đánh dấu đang thực hiện, nếu trong hàng队列 gcw không có đối tượng màu xám khả dụng, sẽ đưa đối tượng trong cache vào hàng队列 địa phương.

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
  for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
    if work.full == 0 {
      gcw.balance()
    }
    b := gcw.tryGetFast()
    if b == 0 {
      b = gcw.tryGet()
      if b == 0 {
        // 刷新写屏障缓存
        wbBufFlush()
        b = gcw.tryGet()
      }
    }
    if b == 0 {
      break
    }
    scanobject(b, gcw)
  }
}

Một tình huống khác là, khi kết thúc đánh dấu, cũng sẽ kiểm tra wbBuf địa phương của mỗi P có còn đối tượng màu xám không

func gcMarkDone() {
    ...
  forEachP(waitReasonGCMarkTermination, func(pp *p) {

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

Thu hồi

Trong thu gom rác, phần quan trọng nhất nằm ở làm thế nào tìm ra đối tượng rác,也就是 công việc quét đánh dấu, mà sau khi hoàn thành công việc đánh dấu, công việc thu hồi tương đối không phức tạp lắm, nó chỉ cần thu hồi giải phóng đối tượng không được đánh dấu là được. Phần code này chủ yếu trong file runtime/mgcsweep.go, căn cứ vào chú thích trong file có thể biết thuật toán thu hồi trong Go chia làm hai loại.

Thu hồi đối tượng

Công việc thu hồi đối tượng sẽ ở giai đoạn kết thúc đánh dấu, do runtime.sweepone đến hoàn thành công việc xóa, quá trình là bất đồng bộ. Khi xóa, nó sẽ thử tìm đối tượng không được đánh dấu trong memory unit, rồi thu hồi. Nếu toàn bộ memory unit đều không được đánh dấu, thì toàn bộ unit này sẽ được thu hồi.

func sweepone() uintptr {
  sl := sweep.active.begin()
  npages := ^uintptr(0)
  var noMoreWork bool
  for {
    s := mheap_.nextSpanForSweep()
    if s == nil {
      noMoreWork = sweep.active.markDrained()
      break
    }
    if state := s.state.get(); state != mSpanInUse {
      continue
    }
        // 尝试获取回收器
    if s, ok := sl.tryAcquire(s); ok {
      npages = s.npages
            // 清理
      if s.sweep(false) {
        mheap_.reclaimCredit.Add(npages)
      } else {
        npages = 0
      }
      break
    }
  }
  sweep.active.end(sl)
  return npages
}

Đối với thuật toán thu hồi đối tượng而言, thu hồi toàn bộ unit khá khó khăn, nên có thuật toán thu hồi thứ hai.

Thu hồi unit

Công việc thu hồi unit là trước khi phân phối bộ nhớ, do phương thức runtime.mheap.reclaim đến hoàn thành, nó sẽ tìm tất cả memory unit mà đối tượng đều không được đánh dấu trong heap, rồi thu hồi toàn bộ unit.

func (h *mheap) reclaim(npage uintptr) {
  mp := acquirem()
  trace := traceAcquire()
  if trace.ok() {
    trace.GCSweepStart()
    traceRelease(trace)
  }
  arenas := h.sweepArenas
  locked := false
  for npage > 0 {
    if credit := h.reclaimCredit.Load(); credit > 0 {
      take := credit
      if take > npage {
        take = npage
      }
      if h.reclaimCredit.CompareAndSwap(credit, credit-take) {
        npage -= take
      }
      continue
    }

    idx := uintptr(h.reclaimIndex.Add(pagesPerReclaimerChunk) - pagesPerReclaimerChunk)
    if idx/pagesPerArena >= uintptr(len(arenas)) {
      h.reclaimIndex.Store(1 << 63)
      break
    }

    nfound := h.reclaimChunk(arenas, idx, pagesPerReclaimerChunk)
    if nfound <= npage {
      npage -= nfound
    } else {
      h.reclaimCredit.Add(nfound - npage)
      npage = 0
    }
  }

  trace = traceAcquire()
  if trace.ok() {
    trace.GCSweepDone()
    traceRelease(trace)
  }
  releasem(mp)
}

Đối với memory unit而言, có một trường sweepgen dùng để biểu thị trạng thái thu hồi của nó

• mspan.sweepgen == mheap.sweepgen - 2: memory unit này cần thu hồi
• mspan.sweepgen == mheap.sweepgen - 1: memory unit này đang được thu hồi
• mspan.sweepgen == mheap.sweepgen: memory unit này đã được thu hồi rồi, có thể sử dụng bình thường
• mspan.sweepgen == mheap.sweepgen + 1: memory unit ở trong cache, và cần thu hồi
• mspan.sweepgen == mheap.sweepgen + 3: memory unit đã được thu hồi rồi, nhưng vẫn ở trong cache

mheap.sweepgen sẽ tăng theo vòng GC, và mỗi lần đều +2.