gc

การเก็บขยะมีหน้าที่ปล่อย内存对象ที่ไม่ได้ใช้งานแล้ว เพื่อ腾出พื้นที่ให้对象อื่น คำอธิบายง่ายๆ เช่นนี้แต่การดำเนินการนั้นไม่ง่ายเลย ประวัติการพัฒนาการเก็บขยะมีมานานหลายทศวรรษ ตั้งแต่ครั้งแรกที่ภาษา Lisp ในยุค 1960 ได้นำกลไกการเก็บขยะมาใช้首次 Python, Objective-C ที่เรารู้จัก กลไก GC หลักคือการนับการอ้างอิง Java, C# ใช้การ回收แบบรุ่น

ในปัจจุบันเมื่อพูดถึงการเก็บขยะ จากอัลกอริทึมการ回收สามารถแบ่งออกเป็นหลายประเภทดังนี้:

• การนับการอ้างอิง: ให้แต่ละ对象บันทึกจำนวนครั้งที่ถูกอ้างอิง เมื่อการนับเป็น 0 จะ回收มัน
• การ标记清除:标记对象ที่ใช้งานอยู่ และ回收对象ที่ไม่ได้标记
• อัลกอริทึมการคัดลอก: คัดลอก对象ที่ใช้งานอยู่ไปยัง内存ใหม่ และ回收对象ทั้งหมดใน内存เก่า เพื่อ达到目的การ回收ขยะ
• การ标记压缩: รุ่นปรับปรุงของการ标记清除 เมื่อ回收จะย้าย对象ที่ใช้งานอยู่ไปยังส่วนหัวของ heap เพื่อความสะดวกในการจัดการ

จากมุมมองของการใช้งาน สามารถแบ่งออกเป็นหลายประเภทดังนี้:

• การ回收ทั่วโลก: 回收ขยะทั้งหมดในครั้งเดียว
• การ回收แบบรุ่น: แบ่งเป็นรุ่นต่างๆ ตามอายุการใช้งานของ对象 แล้วใช้อัลกอริทึมการ回收ที่แตกต่างกัน
• การ回收แบบเพิ่ม: แต่ละครั้งทำการ回收ขยะเฉพาะบางส่วน

TIP

ไปที่ The Journey of Go's Garbage Collector เพื่ออ่านต้นฉบับภาษาอังกฤษ และเรียนรู้เพิ่มเติมเกี่ยวกับประวัติการเก็บขยะของ Go

เมื่อ刚发布时 กลไกการเก็บขยะของ Go ค่อนข้างพื้นฐาน มีเพียงอัลกอริทึมการ标记清除แบบง่ายๆ STW (Stop The World หมายถึงการ暂停โปรแกรมทั้งหมดเนื่องจากการเก็บขยะ) ที่เกิดจากการเก็บขยะสูงถึงหลายวินาทีหรือนานกว่านั้น ทีม Go ที่ตระหนักถึงปัญหานี้จึงเริ่มปรับปรุงอัลกอริทึมการเก็บขยะ ระหว่างเวอร์ชัน go1.0 ถึง go1.8 พวกเขาได้ลองสมมติฐานมากมาย

1. การอ่าน屏障并发复制 GC: ค่าใช้จ่ายของการอ่าน屏障มีความไม่แน่นอนมาก แผนนี้ถูกยกเลิก
2. ตัว收集器面向请求 (ROC): ต้องเปิด写屏障ตลอดเวลา ชะลอความเร็วการทำงาน ลดเวลาคอมไพล์
3. การ回收แบบรุ่น: ประสิทธิภาพของการ回收แบบรุ่นใน Go ไม่สูง เพราะคอมไพเลอร์ของ Go มีแนวโน้มที่จะจัดสรร对象ใหม่บน stack 对象ที่มีอายุยาวจัดสรรบน heap ดังนั้น对象รุ่นใหม่ส่วนใหญ่จะถูก回收โดย stack โดยตรง
4. การ标记卡片无写屏障: ใช้ต้นทุนการแฮช散列แทนต้นทุน写屏障 ต้องใช้อุปกรณ์ฮาร์ดแวร์ช่วย

สุดท้ายทีม Go เลือกใช้三色并发标记+写屏障的组合 และปรับปรุงและปรับ优化อย่างต่อเนื่องในเวอร์ชันต่อๆ มา วิธีนี้ยังคงใช้มาจนถึงปัจจุบัน กราฟ一组ต่อไปนี้แสดงการเปลี่ยนแปลงความล่าช้า GC จาก go1.4 ถึง go1.9

เมื่อเขียนบทความนี้ เวอร์ชันล่าสุดของ Go เกือบจะมาถึง go1.23 แล้ว สำหรับ Go ในปัจจุบัน ประสิทธิภาพ GC ไม่ใช่ปัญหาอีกต่อไป ความล่าช้า GC ส่วนใหญ่ต่ำกว่า 100 ไมโครวินาที ตอบสนองความต้องการของสถานการณ์ธุรกิจส่วนใหญ่

โดยสรุป การเก็บขยะใน Go สามารถแบ่งออกเป็นหลายขั้นตอนดังนี้

• ขั้นตอนการสแกน: รวบรวม对象รากจาก stack และตัวแปรทั่วโลก
• ขั้นตอนการ标记:着色对象
• ขั้นตอนการ终止การ标记: จัดการงาน收尾 ปิด屏障
• ขั้นตอนการ回收: ปล่อยและ回收内存对象ขยะ

แนวคิด

ในเอกสารทางการและบทความอาจปรากฏแนวคิดต่อไปนี้ อธิบายง่ายๆ ดังนี้

• ตัว赋值 (mutator): เป็นศัพท์เทคนิค หมายถึงโปรแกรมผู้ใช้ ใน Go หมายถึงโค้ดผู้ใช้
• ตัว收集器 (collector): หมายถึงโปรแกรมที่รับผิดชอบการเก็บขยะ ใน Go ที่รับผิดชอบการเก็บขยะคือ runtime
• ตัว终结器 (finalizer): หมายถึงโค้ดที่รับผิดชอบการ回收ปล่อย清理内存对象หลังจากงาน标记扫描เสร็จสิ้น
• ตัวควบคุม: หมายถึงตัวแปรทั่วโลก runtime.gcController ประเภทของมันคือ gcControllerState หลังดำเนินการอัลกอริทึม调步 รับผิดชอบยืนยันว่าเมื่อใดควรทำการเก็บขยะและดำเนินการ工作量多少
• ตัวจำกัด: หมายถึง runtime.gcCPULimiter รับผิดชอบป้องกันการใช้ CPU สูงเกินไปขณะเก็บขยะซึ่งจะส่งผลต่อโปรแกรมผู้ใช้

การทริกเกอร์

func gcStart(trigger gcTrigger)

การเก็บขยะถูกเปิด由ฟังก์ชัน runtime.gcStart มันรับพารามิเตอร์โครงสร้าง runtime.gcTrigger เท่านั้น ซึ่งประกอบด้วยสาเหตุการทริกเกอร์ GC เวลาปัจจุบัน และนี่คือ GC รอบที่几

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

ในนั้น gcTriggerKind มีค่า可选ดังนี้

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
)

โดยสรุป เวลาทริกเกอร์การเก็บขยะมีสามแบบ

• เมื่อสร้าง对象ใหม่: เมื่อจัดสรร内存ในการเรียก runtime.mallocgc หากตรวจพบว่า heap内存ถึง阈值 (โดยทั่วไปคือสองเท่าของ GC ครั้งก่อน ค่านี้จะถูกปรับโดยอัลกอริทึม调步) จะเปิดการเก็บขยะ

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

• ทริกเกอร์บังคับ定时: Go จะเริ่ม协程แยกต่างหากขณะทำงานเพื่อรันฟังก์ชัน runtime.forcegchelper หากไม่มีการเก็บขยะเป็นเวลานาน มันจะบังคับเปิด GC เวลานี้กำหนดโดยค่าคงที่ runtime.forcegcperiod ซึ่งมีค่า 2 นาที同时在ระบบตรวจสอบ协程也会定时ตรวจสอบว่าจำเป็นต้องบังคับ GC หรือไม่

  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)
      }
    }
  }

• ทริกเกอร์ด้วยตนเอง: ผ่านฟังก์ชัน runtime.GC ผู้ใช้สามารถทริกเกอร์การเก็บขยะด้วยตนเอง

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

TIP

สนใจสามารถไปที่ Go Gc Pacer Re-Design เพื่ออ่านต้นฉบับภาษาอังกฤษ ซึ่งอธิบาย设计理念และการปรับปรุงของอัลกอริทึม调步 (pacing algorithm) ที่เกี่ยวข้องกับการทริกเกอร์ GC เนื่องจากเนื้อหาค่อนข้างซับซ้อน涉及สูตรคณิตศาสตร์มากเกินไป正文中ไม่อธิบายเพิ่มเติม

การ标记

ปัจจุบันอัลกอริทึม GC ของ Go ยังคงเป็นขั้นตอน标记ก่อนแล้วค่อย清除 แต่การดำเนินการ不再ง่ายเหมือน以前

การ标记 - การ清除

เริ่มจากอัลกอริทึมการ标记清除แบบง่ายที่สุดก่อน ใน内存 ความสัมพันธ์การอ้างอิงระหว่าง对象กับ对象จะ构成กราฟ งานเก็บขยะดำเนินการบนกราฟนี้ งานแบ่งเป็นสองขั้นตอน:

• ขั้นตอนการ标记: เริ่มจากโหนดราก (โหนดรากมักเป็นตัวแปรบน stack 对象ที่ใช้งานอยู่ทั่วโลก ฯลฯ) 遍历โหนดที่เข้าถึงได้แต่ละโหนด และ标记เป็น对象ที่ใช้งานอยู่ จนกว่าจะ遍历โหนดที่เข้าถึงได้ทั้งหมด
• ขั้นตอนการ清除: 遍历对象ทั้งหมดใน heap และ回收对象ที่ไม่ได้标记 ปล่อยพื้นที่内存หรือ复用

ในกระบวนการ回收 โครงสร้างกราฟ对象ไม่สามารถเปลี่ยนแปลงได้ ดังนั้นต้อง暂停โปรแกรมทั้งหมด นั่นคือ STW หลังจาก回收เสร็จสิ้นจึง可以继续运行 ข้อเสียของอัลกอริทึมนี้คือใช้เวลานาน ค่อนข้างส่งผลต่อประสิทธิภาพการ运行โปรแกรม นี่คืออัลกอริทึมการ标记ที่ Go เวอร์ชัน早期ใช้ ข้อเสียค่อนข้างชัดเจน

• จะเกิด碎片内存 (เนื่องจากวิธีการจัดการ内存แบบ TCMalloc ของ Go ผลกระทบของปัญหา碎片ไม่มาก)
• ในขั้นตอนการ标记จะ扫描对象ทั้งหมดใน heap
• จะทำให้ STW暂停โปรแกรมทั้งหมด และเวลาไม่สั้น

การ标记สามสี

เพื่อปรับปรุงประสิทธิภาพ Go ใช้อัลกอริทึมการ标记สามสีแบบคลาสสิก所谓สามสี หมายถึงสีดำ สีเทา สีขาว:

• สีดำ: ในกระบวนการ标记对象已访问过 และ对象ที่它直接引用也都访问过แล้ว แสดงว่า对象ที่ใช้งานอยู่
• สีเทา: ในกระบวนการ标记对象已访问过 แต่对象ที่它直接引用ยังไม่全部访问 เมื่อ访问完后จะเปลี่ยนเป็นสีดำ แสดงว่า对象ที่ใช้งานอยู่
• สีขาว: ในกระบวนการ标记ไม่เคย被访问过 หลังจาก访问后会เปลี่ยนเป็นสีเทา แสดงว่าอาจเป็น对象ขยะ

ในเริ่มงาน标记สามสี มีเพียง对象สีเทาและสีขาวเท่านั้น 对象รากทั้งหมดเป็นสีเทา 对象อื่นเป็นสีขาว ดังแสดงด้านล่าง

แต่ละรอบการ标记เริ่มจาก对象สีเทา ก่อน标记对象สีเทาเป็นสีดำ แสดงว่าเป็น对象ที่ใช้งานอยู่ แล้ว标记对象ทั้งหมดที่对象สีดำ直接引用เป็นสีเทา ที่เหลือเป็นสีขาว ขณะนี้มีสามสีดำเทาขาว

ทำซ้ำขั้นตอนข้างต้นจนกว่าจะเหลือเพียง对象สีดำและสีขาวเท่านั้น เมื่อเซต对象สีเทาว่างเปล่า แสดงว่าการ标记สิ้นสุดลง ดังรูปด้านล่าง

หลังการ标记เสร็จสิ้น ในขั้นตอนการ清除只需ปล่อย内存对象ในเซตสีขาว

ความไม่เปลี่ยนแปลง

อัลกอริทึมการ标记สามสี本身ไม่สามารถทำการ标记พร้อมกัน (หมายถึงโปรแกรม运行一边标记) หากโครงสร้างกราฟ对象เปลี่ยนแปลงในระหว่างการ标记 อาจทำให้เกิดสองสถานการณ์

• การ标记过多: หลังจาก对象被标记为สีดำแล้ว โปรแกรมผู้ใช้ลบการอ้างอิงทั้งหมดสำหรับ对象นั้น มันควรเป็น对象สีขาวที่ต้อง被清除
• การ标记漏: หลังจาก对象被标记为สีขาวแล้ว มี对象อื่นในโปรแกรมผู้อ้างอิง对象นั้น มันควรเป็น对象สีดำที่ไม่ควร被清除

สำหรับกรณีแรกสามารถยอมรับได้ เพราะ对象ที่ไม่ถูก清理可以在รอบ回收ถัดไปจัดการได้ แต่กรณีที่สองไม่สามารถยอมรับได้ 内存对象ที่กำลังใช้งานอยู่ถูกปล่อยผิดพลาด จะทำให้เกิดข้อผิดพลาดโปรแกรมร้ายแรง นี่คือปัญหาที่ต้องหลีกเลี่ยง

แนวคิดความไม่เปลี่ยนแปลงสามสีมาจากบทความวิจัย 《Barrier techniques for incremental tracing》 ที่ Pekka P. Pirinen เผยแพร่ในปี 1998 หมายถึงความไม่เปลี่ยนแปลงสองประการของสี对象ขณะ标记พร้อมกัน:

• ความไม่เปลี่ยนแปลงสามสีแบบแข็ง: 对象สีดำไม่สามารถอ้างอิง对象สีขาวโดยตรง

• ความไม่เปลี่ยนแปลงสามสีแบบอ่อน: เมื่อ对象สีดำอ้างอิง对象สีขาวโดยตรง ต้องมี对象สีเทาอื่นที่สามารถ访问对象สีขาวนั้นได้โดยตรงหรือโดยอ้อม เรียกว่าได้รับการป้องกันจาก对象สีเทา

สำหรับความไม่เปลี่ยนแปลงสามสีแบบแข็ง ทราบว่า对象สีดำ 3 เป็น对象ที่访问过แล้ว และ子对象ทั้งหมดก็访问过แล้วและ标记เป็นสีเทา หาก此时โปรแกรมผู้ใช้并发เพิ่มการอ้างอิงใหม่ของ对象สีขาว 7 ให้กับ对象สีดำ 3 ตามปกติ对象สีขาว 7 ควร被标记为สีเทา แต่เนื่องจาก对象สีดำ 3 ถูก访问过แล้ว 对象 7 จะไม่ถูก访问 ดังนั้นมันจึงเป็น对象สีขาว始终 และสุดท้ายถูก清理ผิดพลาด

สำหรับความไม่เปลี่ยนแปลงสามสีแบบอ่อน มันเหมือนกับความไม่เปลี่ยนแปลงสามสีแบบแข็ง เพราะ对象สีเทาสามารถ访问对象สีขาวนั้นได้โดยตรงหรือโดยอ้อม ในกระบวนการ标记ถัดไปมันสุดท้ายจะถูก标记เป็นสีเทา เพื่อหลีกเลี่ยงการถูก清理ผิดพลาด

ผ่านความไม่เปลี่ยนแปลง สามารถรับประกันได้ว่าในกระบวนการ标记จะไม่มี对象被清理ผิดพลาด และสามารถรับประกันความถูกต้องของงาน标记ภายใต้เงื่อนไขพร้อมกัน ซึ่งสามารถทำให้งาน标记สามสีทำงานพร้อมกันได้ เช่นนี้ประสิทธิภาพการ标记จะเพิ่มขึ้น相当มากเมื่อเทียบกับอัลกอริทึมการ标记 - การ清除 การรักษาความไม่เปลี่ยนแปลงสามสีภายใต้เงื่อนไขพร้อมกัน的关键在于เทคนิค屏障

งาน标记

ในขั้นตอนการสแกน GC มีตัวแปรทั่วโลก runtime.gcphase ใช้แสดงสถานะ GC มีค่า可选ดังนี้:

• _GCoff: งาน标记未开始
• _GCmark: งาน标记已开始
• _GCmarktermination: งาน标记将要终止

เมื่องาน标记开始 สถานะ runtime.gcphase เป็น _GCmark ฟังก์ชันที่ดำเนินการงาน标记คือ runtime.gcDrain ในนั้นพารามิเตอร์ runtime.gcWork เป็นพูลบัฟเฟอร์ มันเก็บตัวชี้对象ที่ต้องติดตาม

func gcDrain(gcw *gcWork, flags gcDrainFlags)

ขณะทำงาน มันจะลองรับตัวชี้ที่ติดตามได้จากพูลบัฟเฟอร์ หากมีจะเรียกฟังก์ชัน runtime.scanobject เพื่อดำเนินงานสแกนต่อไป หน้าที่ของมันคือ扫描对象ในบัฟเฟอร์อย่างต่อเนื่อง และ标记เป็นสีดำ

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)

เมื่อ P ถูกยึดหรือจะเกิด STW งานสแกน才会หยุด

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

runtime.gcwork เป็นคิวที่ใช้โมเดลผู้ผลิต/ผู้บริโภค คิวนี้รับผิดชอบเก็บ对象สีเทาที่ต้องติดตาม แต่ละโปรเซสเซอร์ P ท้องถิ่นมีคิวเช่นนี้ ตรงกับฟิลด์ 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)
}

ฟังก์ชัน runitme.scanobject จะ标记对象สีขาวที่เข้าถึงได้เป็นสีเทาอย่างต่อเนื่องขณะสแกน แล้วเรียก gcw.put ใส่คิวท้องถิ่น同时在ฟังก์ชัน gcDrain จะลองรับ对象สีเทาผ่าน gcw.tryget เพื่อดำเนินการสแกนต่อไป กระบวนการ标记สแกนเป็นแบบเพิ่ม ไม่จำเป็นต้องเสร็จสิ้นงาน标记ทั้งหมดในครั้งเดียว งาน标记ถูกยึดด้วยเหตุผลบางอย่างจะขัดจังหวะ เมื่อ恢复后可以继续完成งาน标记ตาม对象สีเทาที่เหลือในคิว

การ标记พื้นหลัง

งาน标记จะไม่ดำเนินการทันทีเมื่อเริ่ม GC เมื่อ刚ทริกเกอร์ GC แล้ว Go จะสร้างงาน标记จำนวนเท่ากับโปรเซสเซอร์ P ปัจจุบันทั้งหมด พวกมันจะถูกเพิ่มเข้าไปในคิวงานทั่วโลก แล้วเข้าสู่การหลับจนกว่าจะถูกปลุกในขั้นตอนการ标记 ในขณะทำงาน โดย runtime.gcBgMarkStartWorkers ดำเนินการ分配งาน งาน标记实际上หมายถึงฟังก์ชัน runtime.gcBgMarkWorker ในนั้นตัวแปรทั่วโลก gcBgMarkWorkerCount และ gomaxprocs แสดงจำนวน worker ปัจจุบันและจำนวนโปรเซสเซอร์ 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++
  }
}

หลัง worker เริ่มทำงาน มันจะสร้างโครงสร้าง runtime.gcBgMarkWorkerNode และเพิ่มเข้าไปในพูล worker ทั่วโลก runitme.gcBgMarkWorkerPool แล้วเรียกฟังก์ชัน runtime.gopark เพื่อให้协程เข้าสู่การหลับ

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)
    }
    ...
}

มีสองสถานการณ์ที่สามารถปลุก worker

• อยู่ในขั้นตอนการ标记 วัฏจักรการจัดตารางเวลาจะปลุก worker ที่หลับผ่านฟังก์ชัน runtime.runtime.gcController.findRunnableGCWorker
• อยู่ในขั้นตอนการ标记 หากโปรเซสเซอร์ P ปัจจุบันว่างเปล่า วัฏจักรการจัดตารางเวลาจะลองรับ worker ที่พร้อมใช้直接从พูล worker ทั่วโลก 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()
  }
    ...
}

โปรเซสเซอร์ P มีฟิลด์ในโครงสร้าง gcMarkWorkerMode ใช้แสดงโหมดการดำเนินการงาน标记 มีค่า可选ดังนี้:

• gcMarkWorkerNotWorker: แสดงว่าโปรเซสเซอร์ P ปัจจุบันไม่กำลังดำเนินการงาน标记

• gcMarkWorkerDedicatedMode: แสดงว่าโปรเซสเซอร์ P ปัจจุบัน专门用于ดำเนินการงาน标记 และ期间ไม่ถูกยึด

• gcMarkWorkerFractionalMode: แสดงว่าโปรเซสเซอร์ปัจจุบันดำเนินการงาน标记เพราะอัตราการใช้ GC ไม่ถึงมาตรฐาน (25% ถึงมาตรฐาน) ดำเนินการ期间可以被ยึด สมมติว่าจำนวนโปรเซสเซอร์ P ปัจจุบันเป็น 5 ตามสูตรคำนวณ此时ต้องการโปรเซสเซอร์ P หนึ่งตัว专门标记งาน อัตราการใช้ถึงเพียง 20% อัตราการใช้ 5% ที่เหลือต้องการเปิดโปรเซสเซอร์ P โหมด FractionalMode เพื่อชดเชย โค้ดการคำนวณเฉพาะแสดงด้านล่าง

  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: แสดงว่าโปรเซสเซอร์ปัจจุบันดำเนินการงาน标记เพราะว่างเปล่า ดำเนินการ期间可以被ยึด

ทีม Go ไม่希望 GC ใช้ประสิทธิภาพมากเกินไปซึ่งจะส่งผลต่อการทำงานปกติของโปรแกรมผู้ใช้ ผ่านโหมดต่างๆ เหล่านี้สำหรับงาน标记 สามารถเสร็จสิ้น GC โดยไม่เสียประสิทธิภาพและไม่ส่งผลต่อโปรแกรมผู้ใช้ ควรสังเกตว่าหน่วยการ分配งาน标记พื้นฐานคือโปรเซสเซอร์ P ดังนั้นงาน标记จึงดำเนินการพร้อมกัน งาน标记หลายงานและโปรแกรมผู้ใช้ดำเนินการพร้อมกันระหว่างกัน ไม่ส่งผลต่อกัน

การ标记เสริม

协程 G มีฟิลด์ gcAssistBytes ในขณะทำงาน เรียกที่นี่ว่าคะแนนเสริม GC เมื่ออยู่ในสถานะการ标记 GC เมื่อ协程พยายามจัดสรร内存若干ขนาด มันจะถูกหักคะแนนเท่ากับขนาด内存ที่จัดสรร หาก此时คะแนนเป็นลบ协程นั้นต้อง辅助完成งานสแกน GC จำนวน定量เพื่อชำระคะแนน เมื่อคะแนนเป็นบวก协程ก็สามารถไม่完成งาน标记เสริมได้

ฟังก์ชันหักคะแนนคือ runtime.deductAssistCredit มันจะถูกเรียกก่อนจัดสรร内存ในฟังก์ชัน runtime.mallocgc

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
}

อย่างไรก็ตามเมื่อ协程完成งานสแกนเสริม定量แล้ว จะชำระคะแนน定量ให้กับ协程ปัจจุบัน ฟังก์ชันที่รับผิดชอบการ标记เสริม实际上คือ 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))
    ...
}

เนื่องจากสแกนเป็นแบบพร้อมกัน ในงานที่บันทึกมีเพียงส่วนหนึ่งที่เป็นของ协程ปัจจุบัน งานที่เหลือจะถูกชำระให้กับ协程อื่นตามลำดับคิวเสริม หากยังมีเหลือจะถูกเพิ่มเข้าไปในคะแนนทั่วโลก 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)
}

相应地 เมื่อคะแนนที่ต้องชำระ过多时 (จัดสรร内存ใหญ่เกินไป) สามารถใช้คะแนนทั่วโลกเพื่อหักลบหนี้บางส่วนของตัวเองได้

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
    }
  }
    ...
}

การ标记เสริมเป็นวิธีการ平衡ภายใต้ภาระงานสูง ความเร็วในการจัดสรร内存ของโปรแกรมผู้ใช้สูงกว่าความเร็วในการ标记มาก จัดสรร内存多少就进行多少งาน标记

การ终止การ标记

เมื่อ对象สีเทาที่เข้าถึงได้ทั้งหมด被染黑แล้ว ขณะนี้จึงเปลี่ยนจากสถานะ _GCmark ไปเป็นสถานะ _GCmarktermination กระบวนการนี้完成由ฟังก์ชัน runtime.gcMarkDone ในตอนแรก มันจะตรวจสอบว่ายังมีงานต้องดำเนินการหรือไม่

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
  }

เมื่อไม่มีงานทั่วโลกและงานท้องถิ่นต้องดำเนินการแล้ว เรียก runtime.stopTheWorldWithSema เพื่อ STW แล้วจัดการงาน收尾 บางอย่าง

// 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)

อย่างแรกตั้งค่า runtime.BlackenEnabled เป็น 0 แสดงว่างาน标记สิ้นสุดแล้ว แจ้งตัวจำกัดว่าการ标记เสริมสิ้นสุดแล้ว ปิด屏障内存 ปลุก协程ทั้งหมดที่หลับเนื่องจากการ标记เสริม แล้วปลุก协程ผู้ใช้ทั้งหมดอีกครั้ง ยังต้องรวบรวมข้อมูลต่างๆ ของงานสแกนรอบนี้เพื่อปรับอัลกอริทึม调步เพื่อเตรียมพร้อมสำหรับรอบสแกนถัดไป หลังจากงาน收尾เสร็จสิ้น เรียกฟังก์ชัน runtime.gcSweep เพื่อ清理对象ขยะ สุดท้ายเรียก runtime.startTheWorldWithSema เพื่อให้โปรแกรม恢复运行

屏障

内存屏障的作用可以理解为 hook 了对象的赋值行为，在赋值前做一些指定的操作，这种 hook 代码通常在编译期间由编译器插入到代码中。前面提到过，三色标记在并发情况下添加和删除对象引用都会导致问题，由于这两个都是写操作（删除就是赋空值），所以拦截它们的屏障被统称为写屏障。但屏障机制并非毫无成本，拦截内存写操作会造成额外的开销，因此屏障机制只在堆上生效，考虑到实现复杂度和性能损耗，对于栈和寄存器则不起作用范围内。

TIP

想要了解更多 Go 对于屏障技术的应用细节，前往 Eliminate STW stack rescan 阅读英文原文，本文参考了许多内容。

插入写屏障

插入写屏障由 Dijkstra 提出的，它满足强三色不变式。当给黑色对象添加了一个新的白色对象引用时，插入写屏障会拦截此操作，将该白色对象标记为灰色，这样可以避免黑色对象直接引用白色对象，保证了强三色不变性，这个相当好理解。

前面提到过写屏障不会应用在栈上，如果在并发标记的过程中栈对象的引用关系发生了变化，比如栈中的黑色对象引用了堆中的白色对象，所以为了确保栈对象的正确性，只能在标记结束后再次将栈中的所有对象全部标记为灰色对象，然后重新扫描一遍，等于是一轮标记要扫描两次栈空间，并且第二次扫描时必须要 STW，假如程序中同时存在成百上千个协程栈，那么这一扫描过程的耗时将不容忽视，根据官方统计的数据，重新扫描的耗时大概在 10-100 毫秒左右。

优点：扫描时不需要 STW

缺点：需要二次扫描栈空间保证正确性，需要 STW

删除写屏障

删除写屏障由 Yuasa 提出，又称基于起始快照的屏障，该方式在开始时需要 STW 来对根对象进行快照记录，并且它会将所有根对象标黑，所有的一级子对象标灰，这样其余的白色子对象都会处于灰色对象的保护之下。Go 团队并没有直接应用删除写屏障，而是选择了将其与插入写屏障混合使用，所以为了方便后续的理解，这里还是要讲一下。删除写屏障在并发条件下保证正确性的规则是：当从灰色或白色对象删除对白色对象的引用时，都会直接将白色对象标记为灰色对象。

分两种情况来解读：

• 删除灰色对象对于白色对象的引用：由于不知道白色对象下游是否被黑色对象引用，此举可能会切断灰色对象对于白色对象的保护

• 删除白色对象对于白色对象的引用：由于不知道白色对象上游是否被灰色保护，下游是否被黑色对象引用，此举也可能会切断灰色对于白色对象的保护

不管是哪种情况，删除写屏障都会将被引用的白色对象标记为灰色，这样一来就能满足弱三色不变式。这是一种保守的做法，因为上下游情况未知，将其标记为灰色就等于不再视其为垃圾对象，就算删除引用后会导致该对象不可达也就是成为垃圾对象时，也仍然会将其标记为灰色，它会在下轮扫描中被释放掉，这总好过对象被误清理而导致的内存错误。

优点：由于栈对象全黑，所以不需要二次扫描栈空间

缺点：在扫描开始时需要 STW 来对栈空间的根对象进行快照

混合写屏障

go1.8 版本引用了新的屏障机制：混合写屏障，即插入写屏障与删除写屏障的混合，结合了它们两个的优点：

• 插入写屏障起始时不需要 STW 来进行快照
• 删除写屏障不需要 STW 来二次扫描栈空间

下面是官方给出的的伪代码：

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

简单讲解下里面的一些概念，其中 slot 是一个指针，表示对其它对象的引用，*slot 是原对象，ptr 是新对象，*slot=ptr 是一次赋值操作，等于修改对象的引用，赋空值就是删除引用，shade() 表示将一个对象标记为灰色，shade(*slot) 就是将原对象标记为灰色，shade(ptr) 就是将新对象标记为灰色，下面是一个例图，假设对象 1 原来引用着对象 2，然后用户程序修改了引用，让对象 1 引用了对象 3，混合写屏障捕捉到了这一行为，其中 *slot 代表的就是对象 2，ptr 代表的就是对象 1。

官方用一句话概括了上面伪代码的作用

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.

翻译过来就是，当混合写屏障拦截到写操作时，会将原对象标记为灰色，如果当前协程栈还未被扫描过时，就将新对象也标记为灰色。

标记工作开始时，需要扫描栈空间以收集根对象，这时会直接将其全部标记为黑色，在此期间任何新创建对象也会被标记为黑色，保证栈中的所有都是黑色对象，所以伪代码中的 current stack is grey 表示的就是当前协程栈还未被扫描过，所以协程栈只有两种状态，要么全黑要么全灰，在由全灰变为全黑的过程中是需要暂停当前协程的，所以在混合写屏障下依然会有局部的 STW。当协程栈全黑时，此时一定满足强三色不变式，因为扫描后栈中的黑色对象只会引用灰色对象，不会存在黑色对象直接引用白色对象的情况，所以此时不需要插入写屏障，对应伪代码

if current stack is grey:
        shade(ptr)

但仍然需要删除写屏障来满足弱三色不变式，也就是

shade(*slot)

在扫描完毕后，由于栈空间的对象已经是全黑的了，就不再需要去二次扫描栈空间了，可以节省掉 STW 的时间。

至此，也就是 go1.8 版本往后，Go 大体上确立了垃圾回收的基本框架，后续版本有关垃圾回收的优化也都是建立在混合写屏障的基础之上的，由于已经消除了大部分的 STW，此时垃圾回收的平均延时已经降低到了微秒级别。

着色缓存

在之前提到的屏障机制中，在拦截到写操作时都是立即标记对象颜色，在采用混合写屏障后，由于需要对原对象和新对象都行进行标记，所以工作量会翻倍，同时编译器插入的代码也会增加。为了进行优化，在 go1.10 版本中，写屏障在进行着色时不再会立即标记对象颜色，而是会将原对象和新对象存入一个缓存池中，等积攒到了一定数量后，再进行批量标记，这样做效率更高。

负责缓存的结构是 runtime.wbBuf，它实际上是一个数组，大小为 512。

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

每一个 P 本地都有这样一个缓存

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

在标记工作进行时，如果 gcw 队列中没有可用的灰色对象，就会将缓存中的对象放入本地队列中。

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)
  }
}

另外一种情况是，当标记终止时，也会检查每一个 P 本地的 wbBuf 是否有剩下的灰色对象

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

    wbBufFlush1(pp)

    pp.gcw.dispose()

  })
    ...
}

回收

在垃圾回收中，最重要的部分在于如何找出垃圾对象，也就是扫描标记工作，而在标记工作完成后，回收工作就相对没那么复杂，它只需要将未标记的对象回收释放就行。这部分代码主要在 runtime/mgcsweep.go 文件中，根据文件中注释可以得知 Go 中的回收算法分为两种。

对象回收

对象回收的工作会在标记终止阶段，由 runtime.sweepone 来完成清理工作，过程是异步的。在清理时，它会尝试在内存单元中寻找未标记的对象，然后回收掉。倘若整个内存单元都未被标记，那么这一个单元都会被回收掉。

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
}

对于对象回收算法而言，回收整个单元比较的困难，所以就有了第二个回收算法。

单元回收

单元回收的工作是在内存分配前进行的，由 runtime.mheap.reclaim 方法来完成，它会在堆中寻找所有对象都未被标记的内存单元，然后将整个单元回收。

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)
}

对于内存单元而言，有一个 sweepgen 字段用于表明其回收状态

• mspan.sweepgen == mheap.sweepgen - 2：该内存单元需要回收
• mspan.sweepgen == mheap.sweepgen - 1：该内存单元正在被回收
• mspan.sweepgen == mheap.sweepgen：该内存单元已经被回收了，可以正常使用
• mspan.sweepgen == mheap.sweepgen + 1：内存单元在缓存中，且需要回收
• mspan.sweepgen == mheap.sweepgen + 3：内存单元已经被回收了，但仍然在缓存中

mheap.sweepgen 会随着 GC 轮次而增加，并且每一次都会 +2。