GC — стань сборщиком мусора
Уберите все объекты, до которых корни больше не дотягиваются, пока куча не переполнилась. Освободите живой объект — segfault. Игра о достижимости.
Вы — сборщик мусора. Уберите всё, до чего корни больше не дотягиваются.
Как играть
- Оранжевые объекты — корни (локальные и глобальные переменные). Они всегда живы.
- Объект жив, если до него можно дойти по ссылкам от любого корня. Всё остальное — мусор.
- Кликайте по мусору, пока не вышло время. Кликнете по достижимому объекту — освободите живую память: segfault, игра окончена.
Как это работает
На куче появляются объекты со ссылками между ними. Оранжевые объекты — корни (локальные переменные и глобальные), и всё, до чего можно дойти по ссылкам от корня, считается живым. Остальное — мусор, и ваша задача убрать его, пока не вышло время. Кликнете по живому объекту — вы освободили память, на которую кто-то ещё ссылается: segfault. С третьей волны мёртвые объекты ссылаются друг на друга циклами — ровно тот случай, который не может освободить подсчёт ссылок, а трассирующий сборщик освобождает без труда.
Игра о правиле достижимости, лежащем в основе трассирующих сборщиков мусора. Настоящие сборщики также работают с поколениями, барьерами записи и конкурентностью.
Частые вопросы
Как игра определяет, что является мусором?
По достижимости, вычисляемой на лету: обход ссылок от каждого корня помечает всё найденное. Непомеченное — мусор. Это в точности фаза mark из mark-and-sweep.
Почему мёртвые объекты ссылаются друг на друга?
С третьей волны мусор намеренно связывается в циклы. Подсчёт ссылок никогда не сможет их освободить — у каждого объекта остаётся входящая ссылка, — тогда как трассирующий сборщик просто до них не доходит.
Почему клик по живому объекту фатален?
Потому что освобождение памяти, на которую ещё есть ссылки, — это use-after-free, причина огромной доли реальных падений и эксплойтов. Игра так же строга к этому, как и ваш аллокатор.