Сборщик мусора на C++ с подсчётом ссылок

Определение и актуальность

Сборщик мусора (Garbage Collector, GC) — это механизм автоматического управления памятью, который освобождает объекты, больше не используемые программой. В языках без встроенного GC (например, C++) разработчики вынуждены вручную управлять памятью через new/delete, что часто приводит к критическим ошибкам:

"70% высокоуровневых уязвимостей Chrome и Microsoft связаны с проблемами памяти, причём большинство — 'use-after-free' ошибки. Даже sandbox-решения не устраняют эти риски. Garbage Collection (как в MemGC для Edge) и языки с проверками на этапе компиляции (Rust) — ключевые направления борьбы с этими уязвимостями" — The Garbage Collection Handbook, Jones et al.

Данный проект реализует сборщик мусора на C++, использующий подсчёт ссылок и сканирование стека для обнаружения "мусора". Это демонстрация того, как можно добавить автоматическое управление памятью в C++, избегая части ручной работы.

Актуальность:

• Позволяет уменьшить количество утечек памяти в C++-программах.
• Демонстрирует альтернативный подход к управлению памятью без shared_ptr.

---

Общие принципы подсчёта ссылок

Подсчёт ссылок (Reference Counting, RC) — это один из базовых методов автоматического управления памятью, при котором каждый объект содержит счётчик, указывающий количество активных ссылок на него.

Основные концепции

1. Счётчик ссылок (Reference Count)
   • Каждый динамически созданный объект имеет связанный с ним счётчик.
   • При создании объекта счётчик инициализируется значением 1.
   • При копировании указателя на объект счётчик увеличивается.
   • При уничтожении ссылки счётчик уменьшается.
2. Освобождение памяти
   • Когда счётчик достигает нуля, объект считается недостижимым.
   • Память, занимаемая объектом, немедленно освобождается.
3. Распространение удаления
   • Если объект содержит указатели на другие объекты, их счётчики также уменьшаются (рекурсивно).
   • Это может привести к каскадному освобождению памяти.

Псевдокод базового алгоритма (The Garbage Collection Handbook)

New():
  ref ← allocate()
  if ref = null
    error "Out of memory"
  rc(ref) ← 0
  return ref

atomic Write(src, i, ref):
  addReference(ref)
  deleteReference(src[i])
  src[i] ← ref

addReference(ref):
  if ref ≠ null
    rc(ref) ← rc(ref) + 1

deleteReference(ref):
  if ref ≠ null
    rc(ref) ← rc(ref) − 1
    if rc(ref) = 0
      for each fld in Pointers(ref)
        deleteReference(*fld)
      free(ref)

Плюсы и минусы данного подхода

✅ Преимущества

1. Постепенное выполнение
   • Управление памятью происходит во время работы программы, без резких "stop-the-world" пауз, характерных для других GC.
2. Мгновенное освобождение памяти
   • Объекты удаляются сразу, как только становятся недостижимыми (если нет циклических ссылок).
3. Эффективность в условиях нехватки памяти
   • Может работать при почти заполненной куче, в отличие от tracing-алгоритмов, требующих свободного пространства.
4. Хорошая локализация
   • Производительность близка к исходной программе, так как операции выполняются непосредственно с указателями.
5. Простота реализации
   • Не требует сложной интеграции с runtime-системой или знания корневых объектов.
6. Широкая применимость
   • Используется во многих языках (Python, PHP, Swift) и библиотеках (C++ shared_ptr, Rust Rc).

❌ Недостатки

1. Проблемы с многопоточностью
   • Требуются атомарные операции для предотвращения состояний гонки.
2. Циклические ссылки
   • Не может автоматически освобождать циклические структуры данных (например, двусвязные списки).
3. Накладные расходы памяти
   • Каждый объект требует хранения счётчика
4. Загрязнение кэша
   • Частые обновления счётчиков снижают эффективность кэширования.
5. Потенциальные задержки
   • Удаление больших структур данных может вызывать заметные паузы из-за рекурсивного освобождения.

---

Существующие решения и аналоги

Стандартные механизмы C++

std::shared_ptr

• Принцип работы Использует атомарный подсчёт ссылок с автоматическим вызовом delete при достижении счётчиком нуля.
• Ограничения
  • Не обрабатывает циклические ссылки (требует std::weak_ptr).
  • Высокие накладные расходы из-за атомарных операций.
  • Полагается только на явное использование умных указателей

Реализация из книги Bill Blunden

В книге "Memory Management Algorithms and Implementation in C/C++" описан RefCountMemoryManager:

• Ключевые особенности:
  • Кастомный аллокатор на базе HeapAlloc с ручным управлением ссылками через inc()/dec().
  • Поддержка разделения и объединения блоков памяти.
• Недостатки:
  • Нет автоматизации: Вызовы inc()/dec() требуются вручную (автор предполагал генерацию компилятором).
  • Циклические ссылки: Не обрабатываются, как и в классическом подсчёте ссылок.

---

Как работает данный GC?

Основные механизмы

1. Подсчёт ссылок
   • Каждый объект, созданный через new, регистрируется в таблице ref_count.
   • При удалении ссылки счётчик уменьшается, при обнаружении в стеке — увеличивается.
2. Сканирование стека
   • Перед сборкой мусора все счётчики обнуляются.
   • Стек сканируется на наличие указателей на объекты из ref_count.
   • Если объект не найден в стеке, он считается мусором и удаляется.
3. Перегрузка new и delete
   • operator new регистрирует объект в GC.
   • operator delete уменьшает счётчик ссылок.

Пример работы

void foo() {
    int* a = new int(42);  // ref_count[a] = 1
    int* b = new int(100); // ref_count[b] = 1
    // Выход из foo → стек очищается
    // collect() не находит a и b в стеке → удаляет их
}

---

Преимущества

✅ Автоматическое освобождение памяти: не нужно вызывать delete вручную.

✅ Работает с циклическими структурами: в отличие от классического подсчёта ссылок, данный GC удаляет даже циклические ссылки, так как не учитывает указатели внутри объектов кучи.

✅ Простота и прозрачность: не требует сложных алгоритмов вроде Mark-and-Sweep.

✅ Минимальные накладные расходы

Недостатки

❌ Не учитывает глобальные и статические переменные: если указатель хранится в глобальной переменной, GC может ошибочно удалить его.

❌ Ложные срабатывания при сканировании стека: числа в стеке могут случайно совпасть с адресами объектов, что приведёт к некорректному учёту ссылок.

❌ Не поддерживает многопоточность: если указатель хранится в другом потоке, GC может его пропустить.

❌ Не сканирует указатели внутри объектов кучи: если объект A содержит указатель на объект B, но A недостижим из стека, B всё равно удалится (это может быть как плюсом, так и минусом).

---

🚀 Возможные улучшения

• Добавление поддержки глобальных переменных: Регистрация глобальных указателей как "корней" для GC.
• Многопоточная версия:
  • Использование мьютексов для защиты ref_count.
  • Сканирование стеков всех потоков.
• Гибридный подход (Mark-and-Sweep + подсчёт ссылок): Более точное обнаружение достижимых объектов