Владение и заимствование в D

Практически все нетривиальные программы выделяют и используют динамическую память. Делать это корректно становится все более важным, поскольку программы становятся все более сложными, а ошибки еще более дорогостоящими.

Типичными проблемами являются:

1. утечки памяти (не освобождение более не используемой памяти)
2. двойное освобождение (высвобождение памяти более одного раза)
3. использование после освобождения (использование указателя на память, ранее уже освобождённую)

Задача заключается в том, чтобы отслеживать указатели, ответственные за освобождение памяти (т.е.владеющие памятью), и отличать указатели, которые просто указывают на участок памяти, контролировать где они находятся, и которые из них активны (в области видимости).

Типовыми решениями являются следующие:

1. Сборщик мусора (Garbage Collection, GC) – GC владеет блоками памяти и периодически их сканирует на предмет наличия указателей на эти блоки. Если указатели не найдены, память высвобождается. Эта схема надежна и применяется в таких языках как Go и Java. Но GC имеет склонность к использованию гораздо большего количества памяти, чем необходимо, имеет паузы и замедляет код из-за переупаковки (orig.inserted write gates).
2. Подсчет ссылок (Reference Counting, RC) – RC объект владеет памятью и хранит счетчик указателей на себя. Когда этот счетчик уменьшается до нуля, память высвобождается. Это также надежный механизм и принят в языках типа C++ и ObjectiveC. RC эффективен по памяти, требуя дополнительно только место под счетчик. Негативными сторонами RC являются накладные расходы на поддержание счетчика, встраивание обработчика исключений для гарантированного его уменьшения, и блокировки, необходимые для разделяемых между потоками программы объектов. Для повышения производительности, программисты иногда хитрили, временно ссылаясь на RC объект в обход счетчика, порождая риск сделать это некорректно.
3. Ручное управление – Ручное управление памятью это Сишные malloc и free. Это быстро и эффективно по использованию памяти, но язык совершенно не помогает делать все корректно, полностью полагаясь на опыт и усердие программиста. Я использую malloc и free уже 35 лет, и с помощью горького и бесконечного опыта редко делаю ошибки. Но это не тот способ, на который может полагаться технология программирования, и заметьте что я сказал «редко», а не «никогда».

Решения 2 и 3 в той или иной мере полагаются на веру в программиста сделать все корректно. Системы базирующиеся на вере, плохо масштабируются, а ошибки управления памятью доказаны как очень трудно перепроверяемые (настолько плохо, что некоторыми стандартами кодирования использование динамической памяти запрещено).

Но есть еще и четвертый путь — владение и заимствование (Ownership and Borrowing, OB). Это эффективно по памяти, так же быстро как ручное управление, и подлежит автоматизированной перепроверке. Способ недавно популяризирован языком программирования Rust. У него тоже есть свои недостатки, в частности необходимость переосмысления планирования алгоритмов и структур данных.

С негативными сторонами можно бороться и остаток данной статьи является схематичным описанием как система OB работает и как мы предлагаем ее вписать в язык D. Я первоначально считал это невозможным, но затратив на размышления порядочно времени, нашел способ. Он похож на то, как мы поступили с функциональным программированием — с транзитивной иммутабельностью и «чистыми» функциями.

Владение

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

Вторым следствием является то, что указатели используют семантику перемещения а не копирования:

T* f(); void g(T*); T* p = f(); T* q = p; // значение p перемещается в q, а не копируется g(p);     // ошибка, p более недействительно

Вынесение указателя изнутри структуры данных запрещено:

struct S { T* p; } S* f(); S* s = f(); T* q = s.p; // ошибка, недопустимо создание двух указателей на s.p

Почему бы просто не пометить s.p как невалидное значение? Проблема в том, что это потребует простановку метки в рантайме, а должно быть решено на этапе компиляции, потому просто считается ошибкой компиляции.

Выход владеющего указателя за область видимости тоже является ошибкой:

void h() {   T* p = f(); } // ошибка, забыли освободить p?

Необходимо перемещать значение указателя по-другому:

void g(T*); void h() {   T* p = f();   g(p);  // переместили в g(), это теперь проблема g() }

Это прекрасно решает проблемы утечек памяти и использование после освобождения (Подсказка: чтобы было яснее, замените f() на malloc(), и g() наfree().)

Все это может быть проверено на этапе компиляции, используя технику Анализа потока данных (Data Flow Analysis (DFA), примерно как используется для Удаления общих подвыражений. DFA может раскрутить любой крысиный клубок из программных переходов, который может возникнуть.

Заимствование

Система владения, описанная выше, является надежной, но она слишком ограничивающая. Рассмотрим:

struct S { void car(); void bar(); } struct S* f(); S* s = f(); s.car();  // s перемещен в car() s.bar();  // ошибка, s недействителен

Чтобы это заработало, s.car() должна иметь способ вернуть обратно указатель при выходе.

Это то, как работает заимствование. s.car() заимствует копию s на время исполнения s.car(). s недействителен на время выполнения, и становится действительным опять когда s.car() завершится.

В языке D, функции-члены struct получают указатель this по ссылке, так что мы можем приспособить заимствование с помощью небольшого расширения: получение аргумента по ссылке заимствует его.

D также поддерживает область видимости для указателей, так что заимствование получается естественным:

void g(scope T*); T* f(); T* p = f(); g(p);      // g() заимствует p g(p);      // мы может использовать p снова по возврату из g()

(Когда функции получают аргументы по ссылке или используются указатели с областью видимости, им запрещено распространяться за границы функции или области видимости. Это соответствует семантике заимствования.)

Заимствование таким способом гарантирует единственность указателя на объект в памяти в каждый конкретный момент.

Заимствование может быть расширено далее с пониманием того, что система владения также надежна, даже если на объект указывают дополнительно несколько константных указателей (но только один мутабельный). Константный указатель не может ни изменять память ни освобождать её. Это означает, что несколько константных указателей могут заимствовать у мутабельного владельца, но он не имеет права использоваться пока живы эти константные указатели.

Например:

T* f(); void g(T*); T* p = f();  // p стал владельцем {   scope const T* q = p; // заимствованный константный указатель   scope const T* r = p; // займем еще один   g(p); // ошибка, p недействителен пока q и r в области видимости } g(p); // ok

Принципы

Вышеизложенное можно свести к следующему пониманию, что объект в памяти ведет себя так, как будто он в одном из двух состояний:

1. имеется ровно один мутабельный указатель на него
2. имеются один или несколько дополнительных константных указателей

Внимательный читатель заметит что то странное в том, что я написал: «как будто». На что я хотел обиняком намекнуть? Что за головоморочка происходит? Да, есть такое. Компьютерные языки программирования полны таких «как будто» под капотом, примерно как деньги на вашем банковском счету на самом деле находятся не там (я прошу прощения, если это был грубый шок для кого-то), и это ничем не отличается от того. Читайте дальше!

Но сначала, чуть углубимся в тему.

Интеграция техники Владения/Заимствования в D

Разве эти техники не несовместимы с тем, как люди обычно пишут на D, и не сломают ли практически все существующие программы на D? Причем не так, что легко поправить, а настолько, что придется перепроектировать с нуля все алгоритмы?

Да, действительно. Разве что D имеет (почти) секретное оружие: атрибуты функций. Оказывается, что семантика владения/заимствования (OB) может быть реализована для каждой функции в отдельности после обычного семантического анализа. Внимательный читатель мог заметить, что никакого нового синтаксиса не добавлено, только наложены ограничения на существующий код. В D уже есть история использования атрибутов функций для изменения их семантики, например атрибут pure для создания «чистых» функций. Для включения семантики OB добавляется атрибут @live.

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

Как будто

Некоторые необходимые вещи не могут быть реализованы при строгом следовании OB, такие как объекты с подсчетом ссылок. В конце концов RC объекты предназначены для того, чтобы иметь множество указателей на них. Поскольку RC объекты безопасны при работе с памятью (при корректной реализации), они могут использоваться совместно с OB без негативного влияния на надежность. Они только не могут быть созданы при технике OB. Решение в том, что в D имеются и другие атрибуты функций, например @system. @system это функции, где многие проверки надежности отключены. Естественно, OB тоже будет отключено в коде с @system. Это то место, где реализация RC-техники скрывается от контроля OB.

Но в коде с OB, RC объект выглядит так, как будто соблюдает все правила, так что но проблемо!

Потребуется некоторое число подобных библиотечных типов для успешной работы с OB.

Заключение

Эта статья является базовым обзором техники OB. Я работаю над гораздо более детализированной спецификацией. Вполне возможно, что я что то упустил и где то пробоина ниже ватерлинии, но пока все выглядит хорошо. Это очень захватывающая разработка для D и я смотрю вперед для ее реализации.

Для дальнейших дискуссий и комментариев от Уолтера, обращайтесь к темам на /r/programming subreddit и на Hacker News.