Контракт купи процесу

Купи процесів побудовано за класичним дизайном ERTS: один суцільний блок купи на процес плюс фрагменти переповнення, самоописові комірки, великі binary у спільних буферах поза купою та копіювальний збирач сміття, що працює лише в точках безпеки. Ця нотатка є контрактом; runtime.md підсумовує API хоста.

Розміщення слів

Терм — одне слово цільової платформи (32 або 64 біти); кодування описано в abi.md. Кожна область купи — це послідовність об'єктів, яку обхідник розбирає, починаючи з її першого слова:

• Слово заголовка (основний тег 00): біти 2–6 містять BoxedKind, біти від 7 і вище — кількість слів, що йдуть за заголовком. Упакований (boxed) терм вказує на свій заголовок. Кількість охоплює кожне слово префікса, корисного навантаження та вирівнювання, тож обхідник пропускає невідстежуване корисне навантаження, не інтерпретуючи його. Вона має 25 бітів на 32-бітних цілях (щонайбільше 33,554,431 слово) і 57 на 64-бітних (BoxHeader::MAX_COUNT): межа арності кортежу (2^24 - 1) і найбільший bignum (131,072 слова на 32-бітних) вміщуються, що перевіряється статичним твердженням, map перевіряють її під час побудови, а cons-комірки та комірки фіксованого розміру не мають великої кількості.
• Cons-комірка: два слова термів (голова, хвіст) без заголовка. Терм списку вказує на голову. Голова ніколи не є заголовком, бо жоден терм не має тегу 00.
• Заповнювач: повністю нульове слово (вид tuple, кількість 0) — це однословний заповнювач; вид filler з кількістю n охоплює ще n слів. Резервування починаються обнуленими, тож зарезервовані, але невикористані слова розбираються як заповнювач. Непорожні кортежі завжди мають ненульову кількість, а {} є безпосереднім значенням.

Жодна комірка не потребує вирівнювання, сильнішого за слово. memory/heap_walk розбирає область комірка за коміркою, а ProcessHeap::verify перевіряє всю купу. Комірки містять лише слова та байти, за винятком std::shared_ptr binary поза купою (нижче), тож комірка переміщується копіюванням її слів.

Кількість для map вказано в словах (записи = кількість / 2). Pid і порти є безпосередніми значеннями й допускаються за номерами, виданими runtime.

Binary поза купою

Binary, більший за 64 байти, — це незмінний буфер, що існує поза будь-якою купою процесу і спільно використовується з підрахунком посилань (ProcBin і Binary у BEAM).

• Його упакована комірка refc_binary містить std::shared_ptr на буфер, зсув у бітах і довжину в бітах. Зрізи великого binary (і зрізи цих зрізів) — це комірки sub_binary, що називають оригінальну комірку, як sub-binaries в ERTS: зріз не бере посилання на буфер і тримає оригінал живим. Копіювання комірки в інший процес копіює shared_ptr (копіювання між купами), ніколи не байти.
• Кожна комірка зв'язана зі списком поза купою свого процесу через своє слово зв'язку. Цей список — єдиний спосіб знайти C++-стан цих комірок.
• Переміщення комірки копіює інші її слова та створює shared_ptr у новій комірці переміщенням, тож стара копія нічим не володіє. Після збирання прохід по списку перезв'язує переміщені комірки та знищує shared_ptr мертвих; завершення процесу знищує всі. Буфер звільняється, коли помирає його остання комірка в будь-якому процесі.
• Кожен процес підраховує свої комірки для кожного буфера (HeapStorage::buffers_); буфер враховується один раз для кожного процесу, що на нього посилається (його слова поза купою, віртуальна купа binary в ERTS), доки не помре остання комірка цього процесу для нього, і один раз на загальному рахунку runtime від створення до звільнення буфера.
• std::shared_ptr — це два вказівники в кожній підтримуваній STL; static_assert фіксує розмір комірки у вісім слів після заголовка для обох ширин.

Повторне використання буферів

Звільнений буфер розміром у степінь двійки, щонайменше 256 байтів (місткості binary з дописуванням), залишається в потоку, що відкинув останнє посилання, для наступного буфера цього потоку точно такого самого розміру (як блоки купи). Кожен потік тримає щонайбільше 32 буфери й 8 MB; кеш звільняється, коли потік завершується. Байти повторно використаного буфера за межами нового binary лишаються незмінними: жодне подання їх не охоплює. Без цього цикли дописування binary брали свіжі сторінки для кожного збільшеного буфера (купа C++ повертає сторінки великих звільнених блоків). Нові буфери — це ByteBuffer (runtime/include/byte_buffer.hpp), які також ніколи не обнуляють свою пам'ять, тож відповідь драйвера порту (прочитаний цілий файл) записується один раз і переймається як є.

Посилання-дескриптори

Посилання-дескриптор (handle reference) — це посилання, яке також утримує один буфер поза купою, як магічне посилання OTP утримує ресурс; у них живуть масиви atomics (atomics і counters).

• Його комірка має вид reference і розміщення refc_binary: вісім слів після заголовка, 64-бітний номер посилання у словах зсуву та довжини в бітах (де його тримає звичайна комірка посилання), потім shared_ptr і слово зв'язку. Кожна служба посилань читає лише номер, тож воно порівнюється, хешується, друкується і кодується як звичайне посилання.
• Воно вноситься до списку, переміщується, проходиться, враховується і копіюється точно як комірка binary поза купою (layout::off_heap_cell); його буфер звільняється, коли помирає остання копія посилання в будь-якому процесі.
• Реєстр на весь процес ОС зіставляє номери живих дескрипторів з їхніми буферами (слабкі посилання), тож binary_to_term/1 закодованого дескриптора відновлює дескриптор, що спільно використовує буфер, поки той живий, а після — звичайне посилання. Записи з минулим терміном відкидаються в міру зростання реєстру.

Дерева map

Map з понад 32 записами (MAP_SMALL_MAP_LIMIT в OTP) — це 4-слівна заглушка tree_map, що називає корінь персистентного B+ дерева (terms/map_tree), чиї вузли є комірками map_node тієї самої купи, так само як OTP тримає вузли свого HAMT у купі. Менші map лишаються комірками map.

• Листки містять до 16 слів ключів і значень у точному порядку ключів; гілки містять до 16 дочірніх вузлів з їхніми першими ключами, і кожен вузол рахує записи під собою, тож пошук і доступ за позицією — O(log n). Кожен вузол, крім кореня, заповнений щонайменше наполовину.
• Оновлення копіює шлях до зміненого листка (близько 35 слів на рівень) і спільно використовує кожен інший вузол з map-джерелом, яке лишається незмінним, тож побудова map ключ за ключем коштує O(n log n) замість O(n^2). Воно спершу рахує слова шляху і виділяє їх один раз; невдале оновлення відкочує їх.
• Вузли — звичайні комірки: збирання переміщують, підвищують і звільняють їх, мертві версії нічого не коштують, і вони враховуються в heap_size, а не як слова поза купою. Копіювання map в іншу купу (повідомлення) копіює його вузли, як будь-які комірки.
• Кожна заглушка й вузол несуть слово редагування: токен оновлення, що їх створило, над бітом листка. Вузли з власним токеном оновлення змінюються на місці (оновлення кількох ключів записує кожен вузол один раз). Токени, видані до останнього збирання, не дозволяють змін на місці, оскільки збирання могло підвищити вузли, а копіювання в іншу купу очищає токен.
• Оновлення з володінням (MapOperation::update_owned), джерело якого компілятор довів як більше не прочитане, споживає заглушку-джерело (корінь [], розмір 0) і повторно використовує її токен, поки той актуальний, тож воно змінює на місці вузли, створені власним оновленням джерела, і копіює решту шляху. Невдале оновлення з володінням повертає дерево заглушці. Компілятор позначає оновлення як оновлення з володінням лише тоді, коли функція сама побудувала map-джерело (M = <map expression or comprehension> у тому самому тілі клаузи), ніде більше не читає M і ніколи не захоплює його у fun (semantic/map_ownership), а також у циклах згортки з другого кроку (акумулятори з володінням), де операція обирається під час виконання.
• Одне оновлення за ключем — малим цілим числом — визначається лише словами (MapAccess::update_small_key, без Term для кожного аргументу, пошук ключа не викликає віртуальної перевірки). За володіння воно повторно використовує й заглушку-джерело, поки її токен актуальний: заглушка тоді молодша за останнє збирання, тож запис нового кореня в неї не створює вказівника зі старого об'єкта на молодий. Згортка, що оновлює кожен запис, копіює кожен вузол щонайбільше один раз за збирання, а решту часу записує одне слово значення за крок.

Області

• Купа. Один блок [start, top, end) на процес із виділенням пам'яті зсувом вказівника (bump allocation). Він створюється першим виділенням пам'яті процесу, має розмір max(min_heap_words, request), щоб запит завжди вміщався (фрагменти починаються з мінімуму, щонайбільше 233 слова, а потім зростають, див. нижче), і належить лише цьому процесу. Згенерований код виділяє в ньому малі кортежі, списки, float і замикання безпосередньо зсувом вказівника через FrameState::heap_top/heap_limit: HeapStorage::absorb додає ці слова до вершини та used_words_ перед будь-якою операцією з купою (резервування, допуск, збирання, перевірка, запити використання), а expose знову показує вільні слова після неї. Inline-виділення ніколи не створює фрагмент і вимкнене за бюджету на процес. Щойно в блоці лишається менше 64 вільних слів, expose натомість показує найновіший власний фрагмент процесу (ніколи не перейнятий блок повідомлення), тож виділення між двома точками безпеки, як-от повернення рекурсії в тілі, лишається inline після відкриття першого фрагмента (вікна фрагментів). Без бюджету кожен новий фрагмент щонайменше такий самий великий, як фрагменти до нього.
• Області літералів (купа літералів). Складені літерали кожного модуля — рядки, константні списки, кортежі й map, числа з рухомою комою, літерали великих цілих і константні binary будь-якого розміру — компілятор кодує в один константний рядок байтів (ModuleDescriptor::literals, abi/literals.hpp), що лишається в даних виконуваного файлу лише для читання. Реєстрація декодує їх один раз на runtime у тимчасовому контексті (pid номер 0, що ніколи не видається) з атомами й фабриками термів цього runtime, а потім копіює в одну область діапазону персистентних термів, яка ніколи не вилучається; detail::LiteralAreas володіє областю протягом життя runtime і реєструє її як область літералів модуля (неблокувальний відсортований знімок), тож навіть копії, що копіюють живі персистентні терми, використовують її спільно. Binary понад 64 байти мають власний буфер. Терми кожного процесу можуть вказувати на них: допуск перевіряє HeapStorage::readable (купа, фрагменти, потім літерали), тоді як TermAccess::object читає довірені вказівники. Збирач залишає слова літералів незмінними (owned охоплює лише купу); копії між купами й у буфери повідомлень зберігають ці вказівники (корінь-літерал не потребує копії); верифікатор приймає їх. Слова літералів належать самому runtime (зокрема атоми), тож кожен runtime має власну копію; згенерований код читає слова runtime, що заволодів модулем, із literal_cache, а інших runtime — через CLAUSE_literal_v1. Оновлення map з володінням ніколи не змінює літерал на місці: підходить лише заглушка у власній купі процесу.
• Фрагменти. Коли запит не вміщується, а купа не може переміщуватися, він потрапляє до найновішого фрагмента, якщо вміщується там, інакше — до нового фрагмента відповідного розміру (щонайменше мінімального розміру купи), приєднаного до ланцюжка процесу. Наступне збирання об'єднує фрагменти в новий блок купи. Резервування живе в одній області; відкат скидає top цієї області та відкидає фрагмент (або блок купи), створений резервуванням. Виділення пам'яті ніколи не переміщує купу: переповнення залишається у фрагментах до наступної точки безпеки або збирання з боку хоста (збирання в згенерованому коді).
• Стек. Згенеровані фрейми живуть в одному плоскому стеку на процес, окремо від купи (ProcessStack, модель виконання). Типово він не має обмеження; необов'язкове обмеження на процес StackOptions::limit_words обмежує його окремо від купи.
• Список поза купою. Як описано вище.
• Стара область. Об'єкти, що пережили два збирання (покоління); малі збирання лишають її на місці, повний прохід копіює її в новий блок і звільняє.

Розміри та бюджет

• min_heap_words — це min_heap_size процесу: типово 233 слова (як в ERTS), --min-heap-size для кожного процесу (+hms в ERTS), {min_heap_size, N} у spawn_opt або process_flag(min_heap_size, N) для одного; значення округлюється вгору до розміру купи і ніколи не буває меншим за типове значення runtime, а process_flag діє з наступного збирання. Оскільки жоден блок не менший, процес не виконує збирання, доки не виділить стільки слів.
• Купа починається з min_heap_words і зростає за послідовністю розмірів ERTS: 12, 38, далі кожен розмір — сума двох попередніх плюс один до 833,026 слів, потім кроки по 20% (heap_size_at_least).
• Новий блок збирання — найменший такий розмір, за якого слова, які він може отримати, становлять менше 75% від нього: спершу всі використані слова, оскільки живі дані до копіювання невідомі. Результат, у якому живих даних менше 25%, копіюється ще раз у розмір, потрібний для його живих даних; якщо виділити цей блок не вдається, залишається більший. Жоден не менший за min_heap_words. Обидва розміри враховують слова стека процесу як живі, оскільки ERTS тримає стек усередині блоку купи.
• Якщо задано бюджет (нижче), новий блок містить щонайбільше свої живі слова плюс половину бюджету, що залишається після них і буферів поза купою (block_limit), але ніколи не менше за min_heap_words. Інша половина залишається вільною для фрагментів і нових буферів поза купою, тож сміття, виділене після збирання, досягає наступної точки безпеки як тригер, а не вичерпує бюджет. Розмір першої копії визначається з усіх використаних слів, тож блок, що перевищує межу для слів, які вижили, копіюється ще раз у розмір за політикою.
• Типово немає обмеження пам'яті ні на процес, ні на runtime: купа зростає, доки хост не відмовить у пам'яті (out_of_memory), а описане вище визначення розмірів тримає її близько до розміру живих даних. Необов'язковий бюджет на процес, HeapOptions::limit_bytes (типово UNLIMITED_HEAP_BYTES), охоплює блок купи, фрагменти та байти буферів поза купою, на які посилається цей процес; його перевищення — це limit_exceeded. Під час збирання старий і новий блоки співіснують; лише новий блок перевіряється на відповідність бюджету, обмеженому залишком бюджету після буферів поза купою. Внесок буфера повертається, коли процес відкидає свою останню комірку для нього. Стек має власне необов'язкове обмеження, StackOptions::limit_words. Програми задають обидва обмеження через --max-heap і --max-stack (параметри runtime).

Блоки купи

Блоки купи, фрагменти та старі області беруться з memory/heap_blocks. Блок, який звільняє збирання, лишається з його потоком для наступних збирань цього потоку (як носії (carriers) ERTS утримують пам'ять): новий блок бере найменший кешований блок, не менший за свій розмір і не більший за його подвоєння, інакше — свіжу пам'ять. Кожен потік тримає щонайбільше 8 блоків і 16M слів (128 MB на 64-бітних цілях); блоки менші за 4,096 слів не зберігаються, оскільки списки вільних блоків купи C++ обслуговують їх дешево. Звільнений блок, що не вміщується, спершу звільняє найстаріші збережені блоки: купа, що зростає, звільняє дедалі більші блоки, і без витіснення блоки її ранніх малих збирань заповнювали кеш, тож набір живих даних із мільйонів слів брав свіжі сторінки для кожного молодого блоку, старої області й повного проходу. Без цього цільовий простір кожного збирання брав свіжі сторінки в операційної системи й платив за помилку сторінки за кожну сторінку, якої торкався, а звільнення великого блоку повертало його сторінки. Кешовані блоки не враховуються ні жодному процесу, ні на загальному рахунку runtime; потік звільняє свій кеш, коли завершується.

Обмеження пам'яті runtime

• Необов'язкове загальне обмеження runtime, RuntimeOptions::memory_limit_bytes (типово UNLIMITED_HEAP_BYTES; програми задають його через --max-memory), обмежує пам'ять усіх процесів разом: блоки купи, фрагменти, буфери поза купою та місткість стеків. В OTP такого обмеження немає; найближчий аналог — запуск VM під обмеженням пам'яті ОС, але тут збою зазнає один процес, а не вузол.
• Один рахунок на runtime (detail::RuntimeMemory, спільний для кожного сховища купи та стека) поповнюється, коли створюється блок, фрагмент, буфер поза купою чи місткість стека, і звільняється, коли їх відкидають; буфер, спільний для кількох процесів, враховується один раз і звільняється, коли помирає останнє посилання на нього. Завершення процесу повертає всі його внески. Runtime::memory_bytes() повідомляє загальну суму.
• Для кожного процесу обмеження діє як бюджет зі сховища, яким він володіє, плюс того, що залишає обмеження (HeapStorage::budget, room), тож описане вище визначення розмірів залишає половину вільної пам'яті вільною після кожного збирання, а запит понад це — limit_exceeded (resource_limit) лише для процесу, що робить запит; інші процеси продовжують роботу. Сміття іншого процесу враховується, доки той процес не виконає збирання.
• Цільовий простір (to-space) збирання враховується навіть понад обмеження, оскільки він замінює блоки, які звільняє наприкінці того самого збирання.
• Перші 64 слова стека живуть усередині контексту процесу й враховуються під час заштовхування першого фрейму. Потім стек подвоюється, доки це дозволяє обмеження, а далі зростає лише на фрейм, що заштовхується.

Допуск

Вказівники в купу процесу створюють лише компілятор і runtime всередині цього процесу, і вони завжди вказують на початок об’єкта; внутрішніх вказівників для виявлення немає. Допуск — перевірка належності слів, повернутих процесу. Term::from_word(word, context) / TermAccess::admit спершу перевіряють, чи сховище живе (expired_context); атоми й pid/порти мають належати цьому runtime (фіксовані атоми спільні). Для складених слів:

1. Адреса вирівняна за словом усередині однієї з областей процесу, нижче її top: спершу перевіряється блок купи, потім відсортовані за адресою фрагменти, потім області літералів (області). Адреси поза цими діапазонами відхиляються без завантаження; це не виявляє старих слів за повторно використаними адресами.
2. Упаковане слово вказує на заголовок допущеного виду (не заповнювач); слово списку вказує на cons-комірку (слово, яке не є заголовком).

Після допуску TermAccess::object декодує вид, кількість і корисне навантаження через trusted_cell, без пошуку в купі; child обгортає збережене слово, а validate перевіряє лише представлення. Фабрики й далі повторно допускають вхідні дані через ProcessHeap::retain, відхиляючи чужі складені значення з wrong_owner.

Ці перевірки виконуються лише у збірках Debug (CHECKED_ADMISSION). Збірка Release довіряє кожному складеному слову, атому, pid і порту, переданому вбудованій функції, сервісу чи фабриці, як ERTS довіряє своїм Eterm: згенерований код створює лише слова власного процесу, областей літералів та атомів runtime, тому пошуки діапазону й власника лише додавали витрати для кожного аргументу. Інші безпосередні значення й далі класифікуються. Тести, що подають підроблені чи чужі слова, очікують відхилення лише за CHECKED_ADMISSION. map_find може порівнювати ключ іншого процесу лише для читання без такого відхилення. verify() залишається повною перевіркою того, що кожен слот вказує на початок об’єкта, для тестів.

Корені та точки безпеки

ProcessContext::visit_roots перелічує кожне кореневе слово для збирача. У точці безпеки ніщо інше не утримує слова купи процесу:

Жодна комірка купи не містить закріплення. Атоми є безпосередніми значеннями, а таблиця атомів ніколи не збирається. Комірки fun називають код через свій невідстежуваний FunDefinition, який живе стільки ж, скільки runtime; завантажені модулі ніколи не вивантажуються, тож ні fun, ні дескриптори трасування не потребують закріплення. Малі безпосередні значення не є коренями.

Як у C-коді ERTS, хостовий Term — рівно одне тривіально копійоване слово, чинне до наступного збирання купи або завершення процесу; воно не утримує пам’ять, не містить вказівника на купу, токена часу життя чи епохи збирання (володіння). Доступ після будь-якої з цих меж читає переміщену чи звільнену пам’ять і має невизначену поведінку, без перевірки stale_term. Зареєстровані корені переписуються; незареєстрований хостовий Term потрібно відновити з переписаного кореневого слова. Term належить своєму процесу; інші процеси можуть лише читати його, поки джерело залишається стабільним.

Купа переміщується лише в точці безпеки і ніколи, поки резервування відкрите:

• явний collect() з боку хоста, поки контекст не виконує згенерованого коду;
• collect() під час виконання згенерованого коду, що оголосив область SafePoint, обіцяючи, що утримує слова купи лише у вказаних вище коренях. Runtime відкриває її лише в точках безпеки згенерованого коду з наступного розділу.

Будь-який інший запит повертає unsafe_point і нічого не змінює, навіть канал збоїв згенерованого виклику, що виконується. Виділення пам'яті ніколи не переміщує купу: запит, що не вміщується, створює фрагмент.

Буфери повідомлень

MessageBuffer (message_buffer.hpp) зберігає терм поза всіма процесами: copy_of(value, sender) копіює граф із купи процесу відправника у власне HeapStorage. ProcessContext відправника надає параметри купи, області літералів, атоми, ідентифікатори та облік пам’яті runtime; буфер зберігає власний токен часу життя й спільно використовує позакупові binary. Використовується той самий GraphCopy, що й під час надсилання; copy_to копіює в купу одержувача. Безпосередні значення й корені-літерали не потребують сховища. Фабрики, резервування й буфери повідомлень зберігають перевірки часу життя (expired_context); Term, прочитаний із буфера, нічого не утримує й не має переживати свою пам’ять. Буфер ніколи не збирається й звільняється разом з останнім власником; його блок містить рівно слова терма незалежно від мінімуму купи відправника. Надсилання іншим процесам (буфери надходжень), повідомлення таймерів і теги моніторів використовують його, тому ніколи не перекодовуються; persistent terms живуть у власному діапазоні адрес і копіюються в буфери, а не використовуються спільно.

Один обхід повідомлення. Надсилання іншому процесу обходить граф повідомлення один раз до будь-якого блокування (OutgoingMessage, з GraphCopy із graph_copy.hpp); цей обхід визначає розмір кожної подальшої копії і, як будь-яка копія поза процесом, копіює персистентні терми.

Передавання повідомлення. Надсилання повідомлення розміром щонайменше MessageBuffer::ADOPTED_WORDS (512) слів завжди проходить через буфер, скопійований за цим обходом до будь-якого блокування, тому відправник не тримає блокування під час копіювання. Одержувач перебирає буфер замість копіювання (MessageBuffer::take, HeapStorage::adopt), коли буфер не має інших власників, а одержувач має блок купи й не має бюджету: блок приєднується до його фрагментів за тими самими адресами, позакупові списки binary й map буфера приєднуються до його власних разом з обліком, а буфер залишається порожнім. Ніхто інший не може дістатися блоку до чи після, тож жодне слово не копіюється двічі. Прийняті фрагменти запитують збирання лише після того, як receive забере їхнє повідомлення і кількість їхніх слів досягне розміру молодого блоку, як ERTS враховує фрагмент повідомлення лише після отримання (HeapStorage::received); наступне збирання вважає їх молодими даними й копіює повідомлення, що ще в черзі, як будь-який корінь. Менші повідомлення копіюються один раз, що дешевше за окремий фрагмент для кожного: прямо в купу отримувача, що не виконується, під блокуванням виконавця, або відразу за вузлом надходження для того, що виконується. Отримувач забирає таке надходження, копіюючи його слова як є і зсуваючи вказівники між ними на відстань копіювання, читаючи об'єкти в порядку адрес, як збирач сканує свої копії (переміщені надходження); повторного обходу графа немає.

Збирання в згенерованому коді

Згенерований код виконує збирання лише в кількох точках безпеки (safepoints), де кожен живий терм уже перебуває в корені. Усе інше, зокрема кожна служба, що виділяє пам'ять, є критичною секцією, яка ніколи не переміщує купу.

Тригери

Точка безпеки виконує збирання, коли цього вимагає купа (wants_collection()); інакше вона коштує одну перевірку.

Точка безпеки виконує мале збирання (minor collection), якщо не настав час повного проходу: запит garbage_collect, тиск binary поза купою, бюджет купи або стара область без місця для зрілих слів (покоління). Публічний ProcessHeap::collect завжди є повним проходом.

Розмір нового блоку визначається для живих слів плюс слів стека, що використовуються (ERTS тримає стек усередині блоку купи): глибокий стек отримує більшу купу, тож довга рекурсія виконує збирання пропорційно своєму виділенню пам'яті, а не пересканує весь стек кожні кілька сотень слів.

Точки безпеки

Кожен цикл Erlang — це або рекурсія, яка на кожному кроці проходить через вхід у функцію, або comprehension, який проходить через голову свого циклу, тож сміття між двома точками безпеки обмежене лінійним кодом і окремими результатами служб.

Не є точками безпеки (критичні секції, які продовжують виділяти пам'ять у фрагментах): кожна інша служба runtime, зокрема служби виділення пам'яті, побудови та зіставлення; CLAUSE_return_v1; поширення винятків; і доставлення повідомлень. Тому служби можуть утримувати сирі слова купи в C++ протягом усього свого виконання, а їхні вхідні масиви та результати не потребують повторного завантаження.

Процеси, що очікують і призупинені

Процес, який не виконується, ніколи не збирається: він очікує в receive, стоїть у черзі після yield чи trap або ще не запущений, і все, що він утримує, вже є коренем (його фрейми, регістри входу чи продовження, з якого він відновиться, стан trap і його повідомлення). Повідомлення, надіслані йому, копіюються у фрагменти його купи. Кожне доставлення пробуджує процес, що очікує, а його відновлення повторює вхід у його продовження (вбудовану функцію очікування, продовження trap або функцію, в якій він поступився), що є точкою безпеки входу у функцію: перше, що робить відновлений процес, — виконує збирання, якщо цього вимагає його купа. Тому процес, що очікує у вибірковому receive, який пропускає багато повідомлень, виконує збирання в міру їх надходження, так само як ERTS збирає процес під час його наступного планування. Еталон executables_mailbox_collection охоплює накопичення, очікування з тайм-аутом, глибоку рекурсію під навантаженням повідомленнями і споживача, що підтверджує 3,000 повідомлень у межах --max-heap 65536.

Виділення пам'яті не є точкою безпеки (на відміну від test_heap у BEAM): це вимагало б, щоб кожен вхід служби та кожен SSA-терм, живий під час будь-якого виділення, був у корені, повторного завантаження після кожної служби, що виділяє пам'ять, і протоколу повторних спроб у кожній службі, тоді як дві вказані вище точки безпеки вже обмежують сміття.

Правило повторного завантаження

Жодне SSA-значення (значення в нативному регістрі) не утримує слово купи через точку безпеки, і жоден нативний вказівник взагалі не перетинає її (це вже помилка в lower_frames).

• lower_frames обробляє виклик точки безпеки в голові циклу як точку відновлення виклику: розділяє блок після виклику та вивантажує кожне значення, що читається після нього, але обчислене до нього. Значення терма (завантаження зі слота терма чи регістра, значення, збережене в слот терма, або PHI таких значень) зберігається після свого визначення в наявний слот терма або в новий слот терма, врахований у roots дескриптора, і повторно завантажується перед кожним використанням. Інші слова (малі безпосередні значення, атоми, сирі цілі числа, прапорці) зберігаються в сирих слотах: збирання ніколи їх не змінює.
• Виклики вивантажують і повторно завантажують так само, терми — у слоти термів, тож точка безпеки входу бачить кожен живий терм кожного викликача.
• База фрейму залишається дійсною через точку безпеки в голові циклу, оскільки збирання переписує слова стека на місці й ніколи не переміщує стек; кожне передавання керування, як і раніше, перечитує її в пролозі тіла.
• Оптимізація виконується після lower_frames і не може замінити повторне завантаження старішим SSA-значенням: адреса фрейму завантажується з FrameState контексту, і непрозорий виклик точки безпеки може записати через неї будь-який слот (прототип).

Поведінка при збоях

• Збирання в точці безпеки ніколи не записує збій. Коли його новий блок не вдається виділити (out_of_memory), купа залишається як є, а виконання продовжується з фрагментами.
• Вичерпання пам'яті. Без обмеження пам'ять закінчується лише тоді, коли хост відмовляє у блоці купи, фрагменті, буфері поза купою чи зростанні стека: out_of_memory. Якщо задано необов'язковий бюджет або загальне обмеження runtime, запит понад нього — це limit_exceeded, що повідомляється як resource_limit. Обидва є інфраструктурними збоями: жоден обробник не виконується, фрейми розгортаються до нижнього фрейму, а програма друкує clau: runtime failure: entry call failed: <status> і завершується з кодом 70 після скидання stdout і знищення процесу (виконувані файли, відмінності). Оскільки кожне збирання залишає вільною половину бюджету, що залишається після тих, хто вижив (розміри, тригери), бюджет зазнає збою лише тоді, коли живий набір більше не вміщується або коли лінійний код між двома точками безпеки виділяє більше за цю половину; спершу збирається сміття.

Реалізація

• ProcessStack::safepoint(live) запитує ProcessHeap::wants_collection() (існує фрагмент, слова поза купою досягли binary_limit_words_ або було запитано збирання), утримує x[0..live) як корені, відкриває SafePoint і виконує збирання; невдале збирання ігнорується. enter (а отже, tail і invoke) викликає її з арністю викликаної функції перед заштовхуванням; CLAUSE_safepoint_v1 викликає її з 0.
• Пониження (lowering) comprehension генерує перевірку голови циклу в голові кожного циклу генератора (lowering_comprehensions).
• lower_frames розділяє кожне тіло після виклику точки безпеки та вивантажує значення, що її перетинають, як після виклику. Аргументи надходять у регістрах і не зберігаються під час входу: аргумент, що перетинає виклик чи точку безпеки, зберігається у власний слот аргументу після надходження. home() зберігає слот аргументу або слот терма того самого блоку, якщо там є значення; інакше значення терма (term_value: завантажене зі слота терма чи регістра, збережене в слот терма або PHI таких) отримує новий слот терма, який place_slots додає до початкових слотів термів перед сирими слотами, а будь-яке інше значення — сирий слот.
• collected_size обмежує блок значенням block_limit(live); shrink також виконується, коли блок перевищує межу для слів, що вижили; collect обмежує binary_limit_words_ тими, що вижили, плюс половиною бюджету, що залишається вільною після блоку.
• Покриття: еталони OTP executables_garbage_collection (понад 64 MiB виділено з малим живим набором: хвостові цикли, binary поза купою, фільтри comprehension, що виділяють пам'ять, глибока рекурсія в тілі, перехоплене корисне навантаження помилки; із запусками з обмеженнями під --max-heap, --max-stack і --max-memory) та executables_heap_growth (72 MB утримуваних binary); runtime_collection near_budget і shared_limit перевіряють бюджет і загальне обмеження runtime.

Прототип

tests/prototypes/safepoint містить один цикл у стилі comprehension у формі після lower_frames (loop.ll): терм Y, обчислений до циклу, зберігається в слот терма й повторно завантажується після точки безпеки в голові циклу. python tests/prototypes/safepoint/run.py компілює його для x86_64-pc-windows-msvc, aarch64-unknown-linux-gnu, i686-pc-windows-msvc і armv7-unknown-linux-gnueabihf на O0 і O2 та перевіряє, що завантаження слова фрейму Y йде після виклику точки безпеки, тож оптимізатор ніколи не використовує повторно регістр, що утримував Y.

Збирання

Копіювання Cheney (memory/heap_collect), повне або мале збирання (покоління): спершу виділити новий блок (помилка — out_of_memory, купа залишається незмінною), потім скопіювати об’єкт за кожним кореневим словом і просканувати новий блок зліва направо, копіюючи нащадків кожної копії. Слот спершу перевіряється щодо області вихідного простору попереднього слота (одна перевірка діапазону), а безпосередні значення розрізняються inline. Cons-комірки скануються без розбору, а слоти упакованої копії визначаються лише за видом її заголовка (кількість невідстежуваних слів для кожного виду, без перевірок розміру: це копії перевірених об'єктів); об'єкти до чотирьох слів копіюються слово за словом. Заголовок переміщеного boxed-об’єкта замінюється boxed-вказівником на його копію; переміщена cons-комірка отримує нульову голову й хвіст із вказівником на копію. Перенаправлення зберігає спільне використання. Корені переписуються на місці, позакуповий список очищується (копії знову з’єднуються в порядку списку, мертві комірки знищуються), а старий блок і фрагменти звільняються. Купа, яку ніколи не виділяли, не збирається. CollectionStats повідомляє слова до збирання, живі слова, новий блок купи, об’єднані фрагменти, місткість слотів стека й позакупові слова.

Покоління

Збирання за поколіннями, як це робить ERTS, без його бар'єра запису:

• Позначка верхнього рівня. Після збирання кожен об'єкт у новому блоці пережив одне збирання; вершина блоку стає позначкою верхнього рівня (high-water mark). Наступне мале збирання копіює молодий блок і фрагменти, підвищуючи (promoting) об'єкти нижче позначки до старої області, а решту — до нового молодого блоку.
• Стара область. Один блок, що ніколи не переміщується між повними проходами; мале збирання не копіює й не сканує його. Створюється першим малим збиранням, що підвищує об'єкти, розміром удвічі більше за зрілі слова. Коли вона не може прийняти зрілі слова, точка безпеки натомість виконує повний прохід, який лишає все в новому блоці нижче його позначки верхнього рівня і звільняє стару область.
• Інваріант. Незмінний об'єкт вказує лише на об'єкти, старші за себе, тож підвищення за адресою ніколи не лишає старий об'єкт, що вказує на молодий. Записи runtime на місці зберігають це: цикли binary і binary з дописуванням записують цілі числа, а оновлення map змінює на місці лише вузли, створені після останнього збирання. Налагоджувальні збірки після кожного малого збирання перевіряють, що жоден старий об'єкт не вказує в молодий блок чи фрагмент.
• Проходи. Список binary поза купою зберігає комірки старої області, перезв'язує переадресовані й звільняє мертві молоді; мертві старі комірки чекають наступного повного проходу.
• Розмір молодого блоку. Мале збирання зберігає розмір молодого блоку, як це робить ERTS, і щонайменше восьму частину старої області (ERTS). Блок малого збирання ERTS — next_heap_size(young + stack), але його стек заповнює решту повного блоку, тож це ніколи не збільшує блок; стек Clause окремий, і його врахування збільшувало блок за кожного малого збирання. Clause також збільшує блок так, щоб молоді слова вище позначки верхнього рівня (усе, що може лишитися молодим) і стек заповнювали щонайбільше 75% блоку: вимірювання показали, що менша кількість збирань вигідніша за тісніші блоки ERTS. Згенерований код виконує збирання лише в точках безпеки, тож виділення між двома з них (повернення рекурсії в тілі) може далеко переповнитися у фрагменти; коли вони містять чверть блоку або більше, наступний блок зростає на них і не зменшується. Інакше молодий блок понад 8,000 слів із менш ніж 25% живих даних зменшується до розміру втричі більшого за його живі слова (правило малого збирання ERTS).
• Зменшення на місці. Обидва зменшення (це й під час повного проходу) знижують місткість блоку на місці, як ERTS перевиділяє його: нічого не копіюється знову, а невикористаний хвіст блоку лишається виділеним, без врахування в обліку, доки наступне збирання не звільнить блок.
• Межа поза купою. Після малого збирання межа віртуальної купи binary враховує лише молоді живі слова: стара область може містити мертві слова, які не повинні відкладати повний прохід, що звільняє мертві старі binary.
• Тиск binary. Досягнення межі запускає збирання молодого покоління, як це робить віртуальна купа binary в ERTS, що звільняє binary мертвих молодих комірок. Коли таке мале збирання звільняє менше половини слів поза купою, наступне збирання через тиск binary є повним проходом, який звільняє також binary мертвих старих комірок (binary_sweep_due_).

Копіювання між купами

ProcessHeap::add(value), еквівалентно value.copy_to(heap), повертає терм цільової купи (BEAM size_object і copy_struct). Комірки джерела читаються через довірені вказівники, а cons-комірка не потребує розбору:

• Терм, який ціль може читати (власна купа чи область літералів, перевірена через storage_->readable(address)), зберігає ідентичність; інші графи копіюються. Області літералів, розпізнані реєстром цільового runtime, залишаються спільними. Обидві купи мають бути живими й належати одному runtime: це контракт викликача, без перевірки належності складених копій до одного runtime чи часу життя джерела для кожного дескриптора. Читання джерела після збирання або завершення має невизначену поведінку. Кореневі атоми, pid і порти й далі проходять допуск у цілі; завершена ціль повідомляє expired_context. Фабрики й далі відхиляють чужі складені вхідні дані (ProcessHeap::retain), тож лише явне копіювання переносить граф.
• Копії пласкі, як типовий copy_struct в ERTS (без його необов'язкового варіанта, що зберігає спільне використання): підтерм копіюється один раз на кожне досягнення, тож {T, T} копіює T двічі, а терм, спільне використання якого подвоюється на кожному рівні, зростає експоненційно, як в OTP. Один обхід з явним стеком (без рекурсії) сумує слова кожного досягнутого об'єкта; копія — це одне резервування на цю суму в блоці купи або у фрагменті, заповнене другим обходом у тому самому порядку, який знову читає кожну комірку і спрямовує кожен слот на копію дочірнього об'єкта. Обидва обходи йдуть хвостами списку на місці, тож у стеку чекають лише голови, і відрізняють спільні літерали від комірок купи однією перевіркою діапазону, що охоплює всі області літералів модулів. Перший обхід визначає розмір стека другого, тож другий нічого не виділяє, а слова буфера повідомлення не потребують обнулення. Обидва стеки й список binary зберігають перші записи inline, тож копія малого повідомлення не виділяє пам'яті в хоста. Жодна таблиця не зіставляє об'єкти джерела з копіями, і лише комірки binary та заглушки map зберігають свої зсуви.
• Копія binary поза купою — це нова комірка, що спільно використовує буфер; призначення утримує буфер (враховуючи власні слова поза купою, якщо досі не утримувало його) перед резервуванням і вносить комірку до списку лише після підтвердження резервування.
• Джерело лише читається. Збій (resource_limit для бюджету призначення чи обмеження runtime, out_of_memory для хоста) відпускає утримання буферів і відкочує резервування, тож обидві купи та кожен внесок залишаються такими, як були. Копія не володіє жодним сховищем джерела: вона переживає збирання та завершення джерела.

Вимірювання

runtime_heap_measurements (CTest у повному режимі; числа друкуються, а не перевіряються) будує список зі 100,000 кортежів {Index, Float} через TermFactory, обходить його назад через перевірені методи доступу, виконує збирання зі списком як єдиним коренем і обходить копію, а також створює 1,000 контекстів, кожен з яких утримує один малий кортеж. Він повідомляє час побудови й обходу, використані слова купи та її місткість, додаткові байти (виділення пам'яті хостом понад резерв купи), а також байти й слова купи на контекст.