Сборка мусора 16
Вы открыли последнюю главу книги. Если до сих пор вы ее не отбросили — примите мои восхищение и сочувствие. Вероятно, я на всю жизнь отбил у вас вкус к любым реальным проектам, кроме программ управления ядерными реакторами и полетов на Марс. Итак, если кому-нибудь из читателей потребуется организовать в С++ сборку мусора, эта глава укажет им путь. А для остальных она станет очередной интеллектуальной пробежкой по обширным полям идиом и управления памятью в С++.
Доступность
Первое, что от нас потребуется — определить, какие объекты доступны, а какие нет. Сразу же возникает вопрос: доступны откуда? В этом разделе описаны основные варианты перемещения внутрь от конкретного периметра. За ними следуют две конкретные архитектуры сборки мусора, в которых используются описанные приемы.
Периметр
Любая методика сборки мусора, не связанная с подсчетом ссылок, должна начинаться с некоторого внешнего периметра графа объектов. Прочем, даже определить этот параметр порой оказывается непросто.
Стековые переменные
Если стряхнуть с программы на С++ всю объектно-ориентированную шелуху, у вас останутся фрагменты кода. В этих фрагментах создаются локальные переменные, которые чаще всего используются для обращений к объектам.
void f()
{
Foo* foo = new Foo; |
// Объект foo доступен |
}
Стековые переменные могут непосредственно (то есть без участия другого объекта) обратиться к объекту несколькими способами:
•Указатель this является неявным указателем на объект, доступным из кода функции класса.
•Переменная может содержать указатель (*) или ссылку (&) на объект.
•Переменная может быть объектом.
•Переменная может содержать информацию, необходимую для обращения к объекту.
Кроме того, через стековую переменную к объекту можно обратиться и косвенно. Например, если this содержит переменную Bar*, то Bar будет косвенно доступен из любой функции this.
Внешние указатели
Если адрес объекта или его переменной передается системной функции, параллельному процессу или куда угодно за пределы вашего тщательно продуманного кода сборки мусора, такой объект также становится непосредственно доступным.
242
class String { private:
char* str; public:
operator char*() { return str; }
}; |
|
strcpy(aString, bString); |
// Использует оператор char* |
Для вызова strcpy(char*, char*) используется оператор преобразования. Во время выполнения strcpy обе строки непосредственно доступны из кода функции strcpy, которые вами не контролируются. И это еще относительно неплохо, поскольку strcpy можно считать атомарной операцией. Хуже, если вы передадите ссылку на функтор, скажем, функции базы данных как объектоориентированную функцию обратного вызова (callback). Вы можете заниматься своими делами, пока не зазвенит звонок, но до тех пор не смейте уничтожать функтор!
Индексированные коллекции
Весьма специфический случай. Предположим, коллекция объектов индексируется очень большим целым числом.
template <class Type> class Array {
public:
Type* operator[] (LargeInt);
};
Конечно, можно заявить, что все объекты коллекции доступны, если доступна сама коллекция, но такое решение не всегда удовлетворительно. Довольно часто требуется узнать, можно ли к объекту коллекции обратиться по индексу; то есть имеет ли какой-нибудь объект, кроме самой коллекции, индекс объекта X? Если нет — значит, адрес X имеется только у коллекции, и от него желательно избавиться. Мы не будем углубляться в эту тему и лишь мельком обратим внимание на проблему. Чаще всего она возникает при кэшировании объектов на диске и в распределенных объектых системах.
Внутри периметра
После того как будут определены все непосредственно доступные объекты, возникает следующая проблема: идентифицировать объекты, к которым возможны косвенные обращения внутри периметра. Теоретически каждый объект может обратиться к любому другому объекту. Тем не менее, объекты ссылаются друг на друга ограниченным числом способов.
Переменные классов
Один объект может быть внедрен в другой как переменная класса, или же переменная класса может представлять собой указатель или ссылку на другой объект.
Аргументы функций классов
Один объект может получить доступ к другому через аргументы своих функций. На самом деле это лишь частный случай рассмотренных выше стековых переменных.
void Foo::f(Bar* b)
{
b->member_of_Bar();
}
Базовые классы
Базовый класс в С++ интерпретируется так, словно он является внедренным объектом. Как было показано в предыдущей главе, это особенно справедливо для множественного наследования и виртуальных базовых классов. По адресу одного объекта вы можете сослаться на несколько разных
243
логических объектов внутри него — одни являются переменными класса, а другие — базовыми классами. Как правило, адреса этих объектов отличны от того объекта, которому они принадлежат.
Анализ экземпляров
Алгоритмы сборки мусора обычно начинают свою работу с периметра. Для каждого объекта периметра составляется список объектов, которые он содержит и на которые ссылается. Затем для каждого такого объекта составляется новый список и т.д. Рекурсивный перебор продолжается до тех пор, пока удается находить новые объекты. Для этого нам понадобятся некоторые средства, которые позволяют для данного объекта найти все его внедренные объекты и указатели/ссылки.
В SmallTalk и других динамических языках описание структуры экземпляра является задачей объекта класса. В С++ существует несколько вариантов. Первые два решения (см. ниже) вполне практичны, а третье — отчаянная мера, которая подходит только для профессиональных каскадеров на закрытых треках.
Виртуальные функции
Если все объекты происходят от одного общего базового класса, в этом базовом классе можно объявить виртуальную функцию для перечисления указателей и внедренных объектов. Эта функция переопределяется в каждом классе, который добавляет новые переменные или объединяет базовые классы посредством множественного наследования.
Объекты классов
Вы также можете создать свои собственные объекты классов, как было показано в предыдущих главах, и научить их перечислять внедренные объекты и указатели в экземплярах.
Осведомленные указатели
В крайнем случае можно воспользоваться умными указателями и обращаться к ним с просьбой описать объект.
class Foo { private:
Bar* bar;
};
class PFoo { // Умный указатель на Foo private:
Foo* foo; public:
FunctionThatEnumeratesPointersInFoo();
};
Почему я называю этот случай крайним? Вы рискуете тем, что указатель неверно определит тип объекта, на который он ссылается. Конечно, если PFoo — ведущий указатель, мы знаем, что foo действительно является Foo*, но что делать с bar? Как узнать, что это действительно Bar, а не что-то производное от него? Если Bar не имеет только что упоминавшейся самоописывающей виртуальной функции и не возвращает объект класса, остается одно — повсюду раскидать умные указатели и надеяться на лучшее.
class Bar { };
class Pbar { // Умный указатель на Bar };
class Foo { private:
Pbar bar;
};
244
class PFoo { // Умный указатель на Foo private:
Foo* foo; public:
FunctionThatEnumeratesPointersInFoo();
};
Теперь мы начинаем с одного умного указателя, PFoo, и рекурсивно находим другой, PBar. Каждый из этих умных указателей разбирается в особенностях строения объекта, на который он ссылается. В этом они превзошли умные указатели, поэтому я называю их осведомленными (ingenious), хотя циник, вероятно, назвал бы их нерассуждающими.
Перебор графа объектов
В дальнейшем мы воспользуемся методикой виртуальных функций из приведенного выше списка, хотя материал с таким же успехом применим и к объектам классов. Перечисление реализуется двумя основными способами: с применением рекурсивных функций и функторов, а также с применением итераторов.
Рекурсивные функции и функторы
Первая естественная реакция: организовать механизм косвенного вызова, создать функцию или функтор, вызываемые для каждого доступного объекта, и подождать, пока закончится рекурсивный перебор.
class Functor { // ‘Функция’ обратного вызова public:
virtual void Apply(MotherOfAllClasses*) = 0;
};
class MotherOfAllClasses { public:
// Применить fn к каждому доступному объекту virtual void EachObject(Functor& fn);
};
Функция EachObject() вызывает fn.Apply(this), а затем вызывает EachObject() для каждого внедренного объекта или объекта, на который указывает переменная класса. Кроме того, EachObject() вызывает Base::EachObject() для каждого базового класса, таким образом члены базового класса тоже включаются в перечисление. В зависимости от алгоритма в MotherOfAllClasses можно включить бит признака, показывающий, что объект был рассмотрен ранее. Впрочем, как мы вскоре убедимся, иногда без этого можно обойтись.
Итераторы
Более удачное решение — организовать возвращение объектом итератора для всех внедренных объектов (включая базовые классы), в том числе и тех, на которые непосредственно ссылаются его переменные.
class MOAOIterator { // “MotherOfAllObjectsIterator” public:
virtual bool More() = 0;
virtual MotherOfAllObjects* Next() = 0;
};
class MotherOfAllObjects { public:
virtual MOAOIterator* EachObject();
};