Static analyzer annotations for GC correctness in C code

Running the analysis

الإضافة المحللة التي تدفع التحليل تأتي مع جوليا. يمكن العثور على شفرة المصدر الخاصة بها في src/clangsa. يتطلب تشغيلها بناء اعتماد clang. قم بتعيين متغير BUILD_LLVM_CLANG في ملف Make.user الخاص بك من أجل بناء إصدار مناسب من clang. قد ترغب أيضًا في استخدام الثنائيات المسبقة البناء باستخدام خيارات USE_BINARYBUILDER_LLVM.

بدلاً من ذلك (أو إذا لم تكن هذه كافية)، جرب

make -C src install-analysis-deps

من دليل المستوى العلوي لجوليا.

بعد ذلك، يكون تشغيل التحليل على شجرة المصدر بسيطًا مثل تشغيل make -C src analyzegc.

General Overview

نظرًا لأن جمع القمامة في جوليا دقيق، فإنه يحتاج إلى الحفاظ على معلومات الجذر الصحيحة لأي قيمة قد يتم الإشارة إليها في أي وقت قد يحدث فيه جمع القمامة. تُعرف هذه الأماكن باسم نقاط الأمان وفي سياق الدالة المحلية، نوسع هذا التعيين ليشمل أي استدعاء دالة قد ينتهي بشكل متكرر عند نقطة أمان.

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

// The value assigned to any slot passed as an argument to these
// is rooted for the duration of this GC frame.
JL_GC_PUSH{1,...,6}(args...)
// The values assigned into the size `n` array `rts` are rooted
// for the duration of this GC frame.
JL_GC_PUSHARGS(rts, n)
// Pop a GC frame
JL_GC_POP

إذا لم يتم استخدام هذه الماكروهات حيثما ينبغي، أو تم استخدامها بشكل غير صحيح، فإن النتيجة هي فساد ذاكرة صامت. لذلك من المهم جدًا أن يتم وضعها بشكل صحيح في جميع الأكواد القابلة للتطبيق.

على هذا النحو، نستخدم التحليل الثابت (وبشكل خاص محلل clang الثابت) للمساعدة في ضمان استخدام هذه الماكرو بشكل صحيح. يقدم باقي هذا المستند نظرة عامة على هذا التحليل الثابت ويصف الدعم المطلوب في قاعدة كود جوليا لجعل الأمور تعمل.

GC Invariants

هناك اثنان من الثوابت البسيطة للصحة:

• يجب أن تتبع جميع استدعاءات GC_PUSH بـ GC_POP مناسب (في الممارسة العملية، نفرض ذلك على مستوى الدالة)
• إذا كانت القيمة غير متجذرة سابقًا في أي نقطة أمان، فقد لا يتم الإشارة إليها بعد ذلك

بالطبع الشيطان يكمن في التفاصيل هنا. بشكل خاص لتلبية الشرط الثاني من الشروط المذكورة أعلاه، نحتاج إلى معرفة:

• أي المكالمات هي نقاط أمان وأيها ليست كذلك
• أي القيم متجذرة في أي نقطة أمان معينة وأيها ليست كذلك
• عندما يتم الإشارة إلى قيمة

بالنسبة للنقطة الثانية على وجه الخصوص، نحتاج إلى معرفة أي مواقع الذاكرة ستعتبر جذرية في وقت التشغيل (أي القيم المعينة لتلك المواقع هي جذرية). يشمل ذلك المواقع التي تم تعيينها بشكل صريح على هذا النحو عن طريق تمريرها إلى أحد ماكروهات GC_PUSH، والمواقع والقيم الجذرية عالميًا، بالإضافة إلى أي موقع يمكن الوصول إليه بشكل متكرر من أي من تلك المواقع.

Static Analysis Algorithm

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

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

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

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

The analyzer annotations

توجد هذه التعليقات التوضيحية في src/support/analyzer_annotations.h. إنها نشطة فقط عند استخدام المحلل وتتمدد إما إلى لا شيء (لتعليقات التوضيح الخاصة بالنموذج) أو إلى عمليات لا تفعل شيئًا (لتعليقات التوضيح الخاصة بالوظائف).

JL_NOTSAFEPOINT

هذه ربما تكون التعليمة الأكثر شيوعًا، ويجب وضعها على أي دالة يُعرف أنها لا يمكن أن تؤدي إلى الوصول إلى نقطة أمان لجمع القمامة (GC safepoint). بشكل عام، من الآمن فقط لهذه الدالة أن تقوم بإجراء العمليات الحسابية، والوصول إلى الذاكرة، واستدعاء الدوال التي تم وضع علامة عليها بـ JL_NOTSAFEPOINT أو المعروفة بخلاف ذلك بأنها ليست نقاط أمان (على سبيل المثال، الدوال في مكتبة C القياسية، والتي تم ترميزها على هذا النحو في المحلل).

من الصحيح الاحتفاظ بالقيم غير المتجذرة عبر استدعاءات أي دالة موضوعة بهذا السمة:

مثال على الاستخدام:

void jl_get_one() JL_NOTSAFEPOINT {
  return 1;
}

jl_value_t *example() {
  jl_value_t *val = jl_alloc_whatever();
  // This is valid, even though `val` is unrooted, because
  // jl_get_one is not a safepoint
  jl_get_one();
  return val;
}

JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY

عندما يتم وضع علامة JL_MAYBE_UNROOTED كوسيط في دالة، فهذا يشير إلى أن هذا الوسيط قد يتم تمريره، حتى لو لم يكن متجذرًا. في الظروف العادية، تضمن واجهة برمجة التطبيقات (ABI) الخاصة بـ Julia أن يقوم المتصلون بتجذير القيم قبل تمريرها إلى المتلقين. ومع ذلك، فإن بعض الدوال لا تتبع هذه الواجهة وتسمح بتمرير القيم إليها حتى لو لم تكن متجذرة. ومع ذلك، يجب ملاحظة أن هذا لا يعني تلقائيًا أن هذا الوسيط سيتم الحفاظ عليه. توفر علامة ROOTS_TEMPORARILY ضمانًا أقوى، حيث لا يمكن أن تكون القيمة غير متجذرة عند تمريرها فحسب، بل سيتم أيضًا الحفاظ عليها عبر أي نقاط أمان داخلية بواسطة المتلقي.

لاحظ أن JL_NOTSAFEPOINT تعني أساسًا JL_MAYBE_UNROOTED/JL_ROOTS_TEMPORARILY، لأن كون الحجة متجذرة غير ذي صلة إذا كانت الدالة لا تحتوي على نقاط أمان.

نقطة إضافية يجب ملاحظتها هي أن هذه التعليقات تنطبق على كل من جانب المتصل وجانب المتصل به. على جانب المتصل، ترفع هذه التعليقات القيود المتعلقة بالجذرية التي تكون مطلوبة عادةً لوظائف ABI في جوليا. على جانب المتصل به، لها تأثير عكسي يتمثل في منع اعتبار هذه المعاملات جذرية ضمنيًا.

إذا تم تطبيق أي من هذه التعليقات التوضيحية على الدالة ككل، فإنها تنطبق على جميع معلمات الدالة. يجب أن يكون هذا ضروريًا عمومًا فقط لدوال varargs.

مثال على الاستخدام:

JL_DLLEXPORT void JL_NORETURN jl_throw(jl_value_t *e JL_MAYBE_UNROOTED);
jl_value_t *jl_alloc_error();

void example() {
  // The return value of the allocation is unrooted. This would normally
  // be an error, but is allowed because of the above annotation.
  jl_throw(jl_alloc_error());
}

JL_PROPAGATES_ROOT

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

مثال على الاستخدام:

jl_value_t *jl_svecref(jl_svec_t *t JL_PROPAGATES_ROOT, size_t i) JL_NOTSAFEPOINT;

size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_svecref(svec, 1)
  // This is valid, because, as annotated by the PROPAGATES_ROOT annotation,
  // jl_svecref propagates the rooted-ness from `svec` to `val`
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_ROOTING_ARGUMENT/JL_ROOTED_ARGUMENT

هذا في الأساس هو نظير المهمة لـ JL_PROPAGATES_ROOT. عند تعيين قيمة لحقل من قيمة أخرى تم جذرها بالفعل، ستورث القيمة المعينة الجذر من القيمة التي تم تعيينها فيها.

مثال على الاستخدام:

void jl_svecset(void *t JL_ROOTING_ARGUMENT, size_t i, void *x JL_ROOTED_ARGUMENT) JL_NOTSAFEPOINT


size_t example(jl_svec_t *svec) {
  jl_value_t *val = jl_box_long(10000);
  jl_svecset(svec, val);
  // This is valid, because the annotations imply that the
  // jl_svecset propagates the rooted-ness from `svec` to `val`
  jl_gc_safepoint();
  return jl_unbox_long(val);
}

JL_GC_DISABLED

تشير هذه التعليمة إلى أن هذه الدالة تُستدعى فقط عندما يكون وقت تشغيل جامع القمامة معطلاً. غالبًا ما يتم مواجهة دوال من هذا النوع أثناء بدء التشغيل وفي كود جامع القمامة نفسه. لاحظ أن هذه التعليمة يتم التحقق منها مقابل استدعاءات تمكين/تعطيل وقت التشغيل، لذا سيعرف clang إذا كنت تكذب. هذه ليست طريقة جيدة لتعطيل معالجة دالة معينة إذا لم يكن جامع القمامة معطلاً بالفعل (استخدم ifdef __clang_analyzer__ لذلك إذا كان يجب عليك).

مثال على الاستخدام:

void jl_do_magic() JL_GC_DISABLED {
  // Wildly allocate here with no regard for roots
}

void example() {
  int en = jl_gc_enable(0);
  jl_do_magic();
  jl_gc_enable(en);
}

JL_REQUIRE_ROOTED_SLOT

تتطلب هذه التعليمة من المتصل تمرير فتحة متجذرة (أي أن القيم المعينة لهذه الفتحة ستكون متجذرة).

مثال على الاستخدام:

void jl_do_processing(jl_value_t **slot JL_REQUIRE_ROOTED_SLOT) {
  *slot = jl_box_long(1);
  // Ok, only, because the slot was annotated as rooting
  jl_gc_safepoint();
}

void example() {
  jl_value_t *slot = NULL;
  JL_GC_PUSH1(&slot);
  jl_do_processing(&slot);
  JL_GC_POP();
}

JL_GLOBALLY_ROOTED

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

مثال على الاستخدام:

extern JL_DLLEXPORT jl_datatype_t *jl_any_type JL_GLOBALLY_ROOTED;
jl_ast_context_t *jl_ast_ctx(fl_context_t *fl) JL_GLOBALLY_ROOTED;

JL_ALWAYS_LEAFTYPE

هذه التعليقات تعادل أساسًا JL_GLOBALLY_ROOTED، باستثناء أنه يجب استخدامها فقط إذا كانت تلك القيم متجذرة عالميًا بفضل كونها نوع ورقة. تجذير أنواع الأوراق معقد بعض الشيء. عادةً ما تكون متجذرة من خلال حقل cache من TypeName المقابل، والذي يتجذر بدوره من الوحدة المحتوية (لذا فهي متجذرة طالما أن الوحدة المحتوية سليمة) ويمكننا عمومًا أن نفترض أن أنواع الأوراق متجذرة حيث يتم استخدامها، ولكن قد نقوم بتحسين هذه الخاصية في المستقبل، لذا فإن التعليق المنفصل يساعد في توضيح سبب كونها متجذرة عالميًا.

المحلل يكتشف أيضًا تلقائيًا الفحوصات لخاصية leaftype ولن يشتكي من عدم وجود جذور GC في هذه المسارات.

JL_DLLEXPORT jl_value_t *jl_apply_array_type(jl_value_t *type, size_t dim) JL_ALWAYS_LEAFTYPE;

JL_GC_PROMISE_ROOTED

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

void example() {
  jl_value_t *val = jl_alloc_something();
  if (some_condition) {
    // We happen to know for complicated external reasons
    // that val is rooted under these conditions
    JL_GC_PROMISE_ROOTED(val);
  }
}

Completeness of analysis

المحلل ينظر فقط إلى المعلومات المحلية. على وجه الخصوص، على سبيل المثال في حالة PROPAGATES_ROOT المذكورة أعلاه، يفترض أن هذه الذاكرة يتم تعديلها فقط بطرق يمكنه رؤيتها، وليس في أي دوال تم استدعاؤها (ما لم يقرر أن يأخذها في اعتباره في تحليله) وليس في أي خيوط تعمل بالتزامن. وبالتالي، قد يفوت بعض الحالات الإشكالية، على الرغم من أن مثل هذا التعديل المتزامن نادر جدًا في الممارسة العملية. قد يكون تحسين المحلل للتعامل مع المزيد من هذه الحالات موضوعًا مثيرًا للاهتمام للعمل في المستقبل.