GC — стань збирачем сміття
Приберіть усі обʼєкти, до яких корені більше не дотягуються, поки купа не переповнилась. Звільните живий — segfault. Гра про досяжність.
Ви — збирач сміття. Приберіть усе, до чого корені більше не дотягуються.
Як грати
- Помаранчеві обʼєкти — корені (локальні та глобальні змінні). Вони завжди живі.
- Обʼєкт живий, якщо до нього можна дійти за посиланнями від будь-якого кореня. Усе інше — сміття.
- Клацайте сміття, поки не вийшов час. Клацнете досяжний обʼєкт — звільните живу памʼять: segfault, гру завершено.
Як це працює
На купі зʼявляються обʼєкти з посиланнями між ними. Помаранчеві — корені (локальні та глобальні змінні), і все, до чого можна дійти за посиланнями від кореня, вважається живим. Решта — сміття, і ваше завдання прибрати його, поки не вийшов час. Клацнете живий обʼєкт — ви звільнили памʼять, на яку хтось ще посилається: segfault. З третьої хвилі мертві обʼєкти посилаються одне на одного циклами — саме той випадок, який не може звільнити підрахунок посилань.
Гра про правило досяжності в основі трасувальних збирачів сміття. Справжні збирачі також працюють з поколіннями, барʼєрами запису та конкурентністю.
Часті запитання
Як гра визначає, що є сміттям?
За досяжністю, обчислюваною на льоту: обхід посилань від кожного кореня позначає все знайдене. Непозначене — сміття. Це точно фаза mark із mark-and-sweep.
Чому мертві обʼєкти посилаються одне на одного?
З третьої хвилі сміття навмисно звʼязується в цикли. Підрахунок посилань ніколи не зможе їх звільнити, бо в кожного лишається вхідне посилання; трасувальний збирач просто до них не доходить.
Чому клац по живому обʼєкту фатальний?
Бо звільнення памʼяті, на яку ще є посилання, — це use-after-free, причина великої частки реальних падінь і експлойтів. Гра до цього така сама сувора, як ваш алокатор.