gc

ما يفعله جمع القمامة هو تحرير ذاكرة الكائنات التي لم تعد مستخدمة، لإتاحة المساحة لكائنات أخرى. هذا الوصف البسيط لكن تنفيذه ليس بسيطًا على الإطلاق، تاريخ تطور جمع القمامة يمتد لعقود، ففي الستينيات من القرن الماضي استخدمت لغة Lisp لأول مرة آلية جمع القمامة، واللغات المعروفة مثل Python و Objective-C تعتمد بشكل رئيسي على عد المراجع، بينما Java و C# تستخدم الجمع الأجيالي. اليوم، من وجهة نظر خوارزميات الاسترداد، يمكن تقسيمها للفئات الكبرى التالية:

عد المراجع: يجعل كل كائن يسجل عدد المرات التي تمت الإشارة إليه فيها، وعندما يصل العدد للصفر، يتم استرداده
الوسم والمسح: وسم الكائنات النشطة، واسترداد الكائنات غير الموسومة
خوارزمية النسخ: نسخ الكائنات النشطة لذاكرة جديدة، واسترداد جميع الكائنات في الذاكرة القديمة
الوسم والضغط: نسخة مطورة من الوسم والمسح، عند الاسترداد تُنقل الكائنات النشطة لبداية الكومة لتسهيل الإدارة

من وجهة نظر طريقة التطبيق، يمكن تقسيمها للفئات الكبرى التالية:

الاسترداد الشامل: استرداد جميع القمامة دفعة واحدة
الاسترداد الأجيالي: تقسيم الكائنات لأجيال مختلفة بناءً على وقت بقائها، ثم استخدام خوارزميات استرداد مختلفة
الاسترداد التزايدي: في كل مرة يتم إجراء استرداد محلي للقمامة فقط

TIP

توجه لـThe Journey of Go's Garbage Collector لقراءة النص الأصلي بالإنجليزية، ومعرفة المزيد عن تاريخ جمع القمامة في Go

عند إصدارها، كانت آلية جمع القمامة في Go بدائية جدًا، مجرد خوارزمية وسم ومسح بسيطة، وSTW (Stop The World، أي إيقاف البرنامج بالكامل بسبب جمع القمامة) كان يصل لعدة ثوانٍ أو أكثر. أدرك فريق Go هذه المشكلة وبدأ في تحسين خوارزمية جمع القمامة، بين نسخ go1.0 و go1.8، جربوا العديد من الأفكار:

GC النسخي المتزامن بحاجز القراءة: تكلفة حاجز القراءة لها الكثير من عدم اليقين، أُلغيت هذه الخطة
جامع موجه للطلب (ROC): يحتاج تفعيل حاجز الكتابة دائمًا، مما يبطئ سرعة التشغيل ويزيد وقت الترجمة
الجمع الأجيالي: كفاءة الجمع الأجيالي في Go ليست عالية، لأن مترجم Go يميل لتخصيص الكائنات الجديدة على المكدس، والكائنات طويلة العمر على الكومة، لذا معظم كائنات الجيل الجديد ستُسترد مباشرة من المكدس
وسوم البطاقات بدون حاجز كتابة: استبدال تكلفة حاجز الكتابة بتكلفة التجزئة، يحتاج دعم العتاد

أخيرًا اختار فريق Go组合 خوارزمية الوسم المتزامن ثلاثي الألوان + حاجز الكتابة، وفي النسخ اللاحقة استمروا في التحسين، وهذا النهج مستخدم حتى اليوم. المجموعة التالية من الصور تُظهر تغير كمون GC من go1.4 إلى go1.9.

عند كتابة هذا المقال، أحدث نسخة من Go تقترب من go1.23، وبالنسبة لـ Go اليوم، أداء GC لم يعد مشكلة، وكمون GC الآن في معظم الحالات أقل من 100 ميكروثانية، مما يلبي احتياجات معظم سيناريوهات الأعمال.

بشكل عام، يمكن تقسيم جمع القمامة في Go للمراحل التالية:

مرحلة المسح: جمع الكائنات الجذرية من المكدس والمتغيرات العامة
مرحلة الوسم: تلوين الكائنات
مرحلة إنهاء الوسم: معالجة الأعمال الختامية، إغلاق الحواجز
مرحلة الاسترداد: تحرير واسترداد ذاكرة كائنات القمامة

المفاهيم

في الوثائق والمقالات الرسمية قد تظهر المفاهيم التالية، إليك شرح بسيط:

المُغيِّر (mutator): تعبير اصطلاحي، يشير لبرنامج المستخدم، في Go يشير لكود المستخدم
الجامع (collector): يشير للبرنامج المسؤول عن جمع القمامة، في Go المسؤول عن جمع القمامة هو بيئة التشغيل
المُنهِي (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 لتخصيص الذاكرة، إذا اكتشف أن ذاكرة الكومة وصلت للعتبة (عمومًا ضعف آخر GC، وتُعدَّل هذه القيمة بخوارزمية الضبط)، سيبدأ جمع القمامة
go
```
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 وقيمته دقيقتان،同时在 كوروتين مراقبة النظام也会 يتحقق دوريًا مما إذا كان يحتاج تفعيل 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، يمكن للمستخدم تفعيل جمع القمامة يدويًا.
go
```
func GC() {
    ...
  n := work.cycles.Load()
  gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
    ...
}
```

TIP

للمهتمين يمكن الذهاب لـGo Gc Pacer Re-Design لقراءة النص الأصلي بالإنجليزية، الذي يشرح فلسفة تصميم وتحسين خوارزمية الضبط (pacing algorithm) لتفعيل GC، وبسبب تعقيدها وإشراكها الكثير من الصيغ الرياضية، لن نشرحها بالتفصيل في المتن.

الوسم

لا تزال خوارزمية GC في Go اليوم تتبع خطوة الوسم أولًا ثم المسح، لكن تنفيذها لم يعد بسيطًا كما كان.

الوسم-المسح

لنبدأ بأبسط خوارزمية وسم ومسح، في الذاكرة، علاقات الإشارة بين الكائنات تشكل رسمًا بيانيًا، وعمل جمع القمامة يتم على هذا الرسم البياني، وينقسم العمل لمرحلتين:

مرحلة الوسم: البدء من العقد الجذرية (عادة المتغيرات على المكدس، والمتغيرات العامة وغيرها من الكائنات النشطة)، واجتياز كل عقدة يمكن الوصول إليها واحدًا تلو الآخر، ووسمها ككائن نشط، حتى الانتهاء من اجتياز جميع العقد التي يمكن الوصول إليها
مرحلة المسح: اجتياز جميع الكائنات في الكومة، واسترداد الكائنات غير الموسومة، وتحرير مساحتها الذاكرةية أو إعادة استخدامها

أثناء عملية الاسترداد، لا يمكن تغيير بنية الرسم البياني للكائنات، لذا يجب إيقاف البرنامج بالكامل، أي STW، وبعد الانتهاء من الاسترداد يمكن الاستمرار في التشغيل، عيب هذه الخوارزمية أنها تستغرق وقتًا طويلاً، مما يؤثر على كفاءة تشغيل البرنامج، وهي خوارزمية الوسم التي استخدمتها النسخ المبكرة من Go، وعيوبها واضحة:

ستُنتج شظايا ذاكرة (بسبب طريقة إدارة الذاكرة بنمط TCMalloc في Go، تأثير مشكلة الشظايا ليس كبيرًا)
في مرحلة الوسم ستتم مسح جميع الكائنات في الكومة
ستؤدي لـ STW، إيقاف البرنامج بالكامل، ولفترة ليست قصيرة

الوسم ثلاثي الألوان

لتحسين الكفاءة، اعتمد Go خوارزمية الوسم ثلاثي الألوان الكلاسيكية، فما يُسمى بثلاثي الألوان يشير للأسود والرمادي والأبيض:

الأسود: خلال عملية الوسم تمت زيارة الكائن، وجميع الكائنات التي يشير إليها مباشرة تمت زيارتها أيضًا، يمثل كائنًا نشطًا
الرمادي: خلال عملية الوسم تمت زيارة الكائن، لكن ليس جميع الكائنات التي يشير إليها مباشرة تمت زيارتها، عند زيارتها جميعًا يتحول للأسود، يمثل كائنًا نشطًا
الأبيض: خلال عملية الوسم لم تتم زيارته أبدًا، بعد الزيارة يتحول للرمادي، يمثل كائن قمامة محتمل

عند بدء عمل الوسم ثلاثي الألوان، لا يوجد على الساحة إلا كائنات رمادية وبيضاء، جميع الكائنات الجذرية رمادية، وباقي الكائنات بيضاء، كما في الصورة:

في بداية كل جولة وسح، نبدأ من الكائنات الرمادية، نوسم الكائن الرمادي بالأسود، للدلالة على أنه كائن نشط، ثم نوسم جميع الكائنات التي يشير إليها مباشرة بالرمادي، وباقي الكائنات بيضاء، والآن على الساحة ثلاثة ألوان.

نكرر الخطوات أعلاه باستمرار، حتى لا يتبقى على الساحة إلا كائنات سوداء وبيضاء، عندما تكون مجموعة الكائنات الرمادية فارغة، يعني ذلك انتهاء الوسم، كما في الصورة:

بعد انتهاء الوسم، في مرحلة المسح نحتاج فقط لتحرير ذاكرة الكائنات في المجموعة البيضاء.

الثبات

خوارزمية الوسم ثلاثي الألوان بحد ذاتها لا تستطيع إجراء وسح متزامن (أي البرنامج يعمل ويوسم في نفس الوقت)، إذا تغيرت بنية الرسم البياني للكائنات أثناء الوسم، قد يؤدي ذلك لحالتين:

وسح زائد: بعد وسم الكائن بالأسود، حذف برنامج المستخدم جميع الإشارات لهذا الكائن، إذن يجب أن يكون كائنًا أبيض يحتاج للمسح
وسح ناقص: بعد وسم الكائن بالأبيض، أشار إليه كائن آخر في برنامج المستخدم، إذن يجب أن يكون كائنًا أسود لا يجب مسحه

الحالة الأولى مقبولة، لأن الكائن غير المنظف يمكن معالجته في جولة استرداد لاحقة. لكن الحالة الثانية غير مقبولة، ذاكرة كائن قيد الاستخدام تم تحريرها بشكل خاطئ، سيؤدي لأخطاء برمجية خطيرة، وهذا يجب تجنبه.

مفهوم ثبات ثلاثي الألوان يأتي من ورقة Pekka P. Pirinen المنشورة عام 1998 《Barrier techniques for incremental tracing》، وهو يشير لثباتين في لون الكائنات أثناء الوسم المتزامن:

ثبات ثلاثي الألوان القوي: الكائن الأسود لا يمكن أن يشير مباشرة لكائن أبيض
ثبات ثلاثي الألوان الضعيف: عندما يشير كائن أسود مباشرة لكائن أبيض، يجب أن يكون هناك كائن رمادي آخر يمكنه الوصول لهذا الكائن الرمادي مباشرة أو بشكل غير مباشر، يُسمى حماية الكائن الرمادي

بالنسبة لثبات ثلاثي الألوان القوي، نعلم أن الكائن الأسود 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)
}

الدالة runtime.scanobject أثناء المسح تُوسم باستمرار الكائنات القابلة للوصول من البياض للرمادي، ثم تضعها في الطابور المحلي عبر استدعاء gcw.put، في نفس الوقت الدالة gcDrain تحاول باستمرار الحصول على الكائنات الرمادية عبر gcw.tryget لمواصلة المسح. عملية وسح المسح هي تزايديه، لا تحتاج لإكمال جميع أعمال الوسم دفعة واحدة، وعندما تُستبعد مهمة الوسم لبعض الأسباب ستتوقف، وعند الاسترداد يمكن مواصلة إكمال عمل الوسم بناءً على الكائنات الرمادية المتبقية في الطابور.

الوسم الخلفي

لا يُنفَّذ عمل الوسم فورًا عند بدء GC، عند تفعيل GC للتو، سيُنشئ Go عددًا من مهام الوسم يساوي العدد الإجمالي للمعالجات P الحالية، ستُضاف للطابور العام للمهام، ثم تدخل في السكون حتى تُستيقظ في مرحلة الوسم. في بيئة التشغيل، الدالة runtime.gcBgMarkStartWorkers مسؤولة عن توزيع المهام، ومهمة الوسم فعليًا هي الدالة runtime.gcBgMarkWorker.

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

بعد بدء العامل، سيُنشئ بنية runtime.gcBgMarkWorkerNode، يضيفها لتجمع العمال العام runtime.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)
    }
    ...
}

هناك حالتان يمكن أن تُوقظ العامل:

في مرحلة الوسم، حلقة الجدولة ستستيقظ العامل الساكن عبر الدالة runtime.gcController.findRunnableGCWorker
في مرحلة الوسم، إذا كان المعالج P حاليًا في حالة خمول، حلقة الجدولة ستحاول الحصول مباشرة على عامل متاح من تجمع العمال العام 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 لتعويضها
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)
  }
}

في حالة أخرى، عند انتهاء الوسم، سيُتحقق أيضًا مما إذا كان هناك كائنات رمادية متبقية في wbBuf المحلي لكل P:

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.

gc ​

المفاهيم ​

التفعيل ​

الوسم ​

الوسم-المسح ​

الوسم ثلاثي الألوان ​

الثبات ​

عمل الوسم ​

الوسم الخلفي ​

المساعد في الوسم ​

إنهاء الوسم ​

الحواجز ​

حاجز الكتابة للإدراج ​

حاجز الكتابة للحذف ​

حاجز الكتابة الهجين ​

تخزين التلوين المؤقت ​

الاسترداد ​

استرداد الكائنات ​

استرداد الوحدات ​

gc