Подсчёт ссылок не так прост, как кажется: опыт языка Umka

Подсчёт ссылок обычно предлагается как самый простой способ автоматического управления памятью в языках программирования. Он избавляет программиста от необходимости вставлять в свой код free(), delete и тому подобное, следить за висячими указателями и утечками памяти. Принцип действительно звучит очень просто: каждый выделенный в куче блок памяти наделяется счётчиком ссылок на него. Каждая переменная, через которую можно добраться до этого блока, олицетворяет одну ссылку. Блок освобождается тогда, когда счётчик ссылок доходит до нуля.

В своём статически типизированном скриптовом языке Umka я решил воспользоваться именно этим способом. Его простота подкупала. Альтернативы вроде трассирующего сборщика мусора отпугнули непредсказуемыми задержками при исполнении программ. Ну а теперь пришло время рассказать про подводную часть этого невинного айсберга. Не сомневаюсь, что где-то в тысячах опубликованных статей такие айсберги описаны во всех деталях, но найти их там непросто и небыстро, особенно когда уже полным ходом идёшь на ледяную глыбу.

Итак, обсудим четыре ключевых практических проблемы, с которыми пришлось столкнуться при реализации подсчёта ссылок в языке Umka.

Проблема первая. Обход потомков

Начнём с канонического описания метода в книге Garbage Collection (судя по всему, авторы сочли метод слишком примитивным, чтобы надолго на нём задерживаться):

Функция Update(R, S) описывает действия, которые необходимо предпринять при присвоении *R = S. Предполагается, что и R, и &S указывают в кучу. Из этого псевдокода уже можно извлечь маленький урок: перед любым присвоением сначала нужно увеличивать счётчик ссылок правой части RC(S), а лишь затем уменьшать счётчик левой части, иначе при присвоении *R = *R правая часть рискует быть уничтожена ещё до присвоения.

Однако основной интерес здесь представляет функция delete(T), которая описывает уменьшение счётчика при уничтожении одной ссылки на блок памяти по указателю T, например, при вышеописанном присвоении или при выходе переменной-ссылки T из области видимости. Кроме очевидного декремента счётчика RC(T), она предписывает рекурсивно пройти по всем потомкам T, если уничтожается последняя ссылка на T. Это логично: T был одним из способов добраться до потомка, а теперь его не будет, значит, счётчик ссылок потомка нужно уменьшить. Но что такое "потомки" на практике?

Я начинал с наивного представления: потомки статического или динамического массива - это его члены, потомки структуры - её поля. Казалось, все инструкции виртуальной машины Umka, отвечающие за инкремент/декремент счётчиков ссылок, можно легко сгенерировать при компиляции в байт-код. Сама виртуальная машина при этом сохранила бы замечательное свойство, возникающее благодаря статической типизации языка: ничего не ведать об иерархии типов данных в исходной программе.

Красивая картина рассыпалась, как только я подумал про списки и деревья. В них потомками становится содержимое памяти по соответствующим указателям в каждом узле. При этом необходимо обойти всю иерархию потомков в соответствии с фактическими типами узлов и остановиться лишь там, где потомок окажется null. Предсказать этот null на этапе компиляции невозможно, поэтому весь код обхода потомков, увы, переехал из кодогенератора Umka в виртуальную машину, которой пришлось узнать и о типах данных. Элегантность статической типизации оказалась слегка подпорченной. Однако такое решение стало выглядеть неизбежным, как только в язык добавились ещё и интерфейсы в стиле Go - это вообще царство динамической типизации, ибо фактический тип содержимого интерфейса становится известен лишь при исполнении программы. В общем, в язык Umka пришёл RTTI (runtime type information) и уходить больше не собирается.

Приключения с обходом потомков на этом не закончились. Обход, основанный на рекурсии, довольно быстро съедает стек (имеется в виду системный стек, а не тот, которым оперирует виртуальная машина). Тем самым ограничивается глубина списков и деревьев, допускающих корректное освобождение. Возможно, предстоит довольно мучительное переписывание рекурсии в цикл.

Проблема вторая. Результаты функций

При возвращении из функции все локальные переменные выходят из области видимости и, если они являются указателями или содержат указатели, подлежат декременту своих счётчиков ссылок. Однако возвращаемое значение функции должно пережить смерть функции и дожить по крайней мере до присвоения результата какой-то переменной в точке вызова: y = f(x). Соответственно, выражение после return рассматривается точно так же, как правая часть присвоения, и требует инкремента счётчика ссылок. Однако кто будет держателем этой новой ссылки? Выражение f(x) - это не переменная, и на роль держателя не годится (хотя бы потому, что то же самое f(x) строчкой ниже может давать уже совершенно другое значение).

В Umka использован следующий подход: результат функции f(x) присваивается не только переменной y, но и новой неявной локальной переменной: __temp0 = f(x). Эта переменная становится держателем ссылки и умирает при выходе из того блока {...}, где вызывается f(x). Каждый новый вызов функции, даже в пределах одного блока, требует новой неявной переменной: __temp0, __temp1 и т. д. Конечно, было бы ещё лучше убивать эти переменные, как только состоялось присвоение y = f(x), но это создаёт некоторую путаницу с областями видимости.

Проблема третья. Указатели на середину структуры

Будучи во многом вдохновлён Go, язык Umka ориентирован на работу с классическими структурами (struct), которые могут вкладываться друг в друга целиком, а не в виде указателей. Это даёт замечательные преимущества при использовании Umka как встраиваемого скриптового языка в связке с C/C++. В отличие от Lua, Umka позволяет легко перекидывать структуры в программу на C/C++ и обратно, сохраняя при этом раскладку полей структуры в памяти.

Однако за такое удобство приходится платить и свою цену, о которой, кстати, не раз говорили и создатели Go. Любая структура вроде struct {x, y: int} может лежать не в стеке, а в куче, и быть доступной по указателю p. С точки зрения подсчёта ссылок, это означает следующее: где-то в куче выделено место под заголовок, в котором хранится счётчик ссылок и размер размещаемой структуры, а непосредственно за этим заголовком - место для самой структуры, на которую и указывает p. Имея p, всегда можно найти заголовок, отступив назад на размер этого заголовка. В заголовке, в свою очередь, можно найти счётчик ссылок. Однако никто не запрещает взять указатель на любое поле структуры: &p.y. Он, скорее всего, не совпадает с p. Как тогда по этому указателю отыскать заголовок?

В Umka сделано так. Память в куче выделяется страницами. Каждая страница разбита на блоки. Их размер фиксирован в пределах страницы, но отличается для разных страниц. Можно сказать, что размер блока - это основная неизменная характеристика страницы. Когда приходит время выделить место под структуру (вернее, заголовок + структуру), отыскивается страница с наиболее подходящим размером блока, в которой остался хотя бы один свободный блок. "Подходящий размер" означает: не меньше суммарного размера заголовка + структуры, но с наименьшим излишком. Если такой страницы нет, выделяется новая.

Когда размер блока фиксирован, это позволяет легко найти заголовок и счётчик ссылок по указателю на середину структуры:

• Определяется страница, на которую попадает указатель &p.y.

• Восстанавливается указатель на начало заголовка. Для этого смещение указателя &p.y от начала страницы округляется в меньшую сторону до величины, кратной размеру блока.

• Считывается заголовок блока.

• В заголовке отыскивается (а при необходимости - изменяется) счётчик ссылок.

При этом одновременно с счётчиками ссылок на блоки меняется и общий счётчик ссылок на страницу (сумма счётчиков ссылок на все её блоки). Когда счётчик ссылок страницы доходит до нуля, она удаляется.

Проблема четвёртая. Циклические ссылки

На закуску остаётся классическая проблема циклических ссылок. С ней приходится иметь дело всем, кто захотел использовать подсчёт ссылок. Насколько мне известно, эта проблема стала так раздражать разработчиков Python, что в дополнение к подсчёту ссылок они ввели трассирующую сборку мусора (был бы благодарен знатокам Python за подробности этой истории).

Возьмём код (Umka использует синтаксис Pascal для указателей):

    type (
        S = struct {t: ^T}
        T = struct {s: ^S}
    )
    p := new(S)
    q := new(T)
    p.t = q
    q.s = p

В нём счётчики ссылок на p и q никогда не обнулятся, поскольку p ссылается на q, а q ссылается на p. В результате возникает утечка памяти.

Решение в Umka столь же классическое, сколь и сама проблема: слабые (weak) указатели, то есть указатели, наличие которых не учитывается в счётчике ссылок и не препятствует удалению блока памяти. Один из указателей, составляющих цикл, делается слабым, другой остаётся сильным:

    type (
        S = struct {t: weak ^T}
        T = struct {s: ^S}
    )
    p := new(S)
    q := new(T)
    p.t = q
    q.s = p

Разумеется, по своей природе слабый указатель может оказаться висячим и указывать на уже освобождённый блок памяти, поэтому слабые указатели в Umka запрещено разыменовывать напрямую. Вместо этого его нужно сначала привести к сильному указателю. Висячий слабый указатель при таком приведении превратится в null.

Заключение

Спустя более чем год работы над Umka я по-прежнему ощущаю, что управление памятью остаётся самой сложной частью проекта, несмотря на кажущуюся простоту выбранного подхода. Баги, связанные с утечками памяти и висячими указателями, приходилось исправлять на протяжении всей работы. Начало практического применения языка и появление первых сторонних пользователей (которые подчас пишут на Umka смелее и решительнее меня) неплохо форсировало этот процесс.