Как устроен счетчик ссылок в Swift

Мы в iOS команде Vivid Money стремимся глубже понимать инструменты, которыми пользуемся каждый день. Один из таких – это язык программирования Swift. Он состоит из нескольких частей: компилятора, стандартной библиотеки и рантайма. Компилятор преобразует код, понятный для человека, в код понятный компьютеру. Стандартная библиотека предоставляет разработчикам готовые структуры данных и алгоритмы, оптимизированные для применения в боевых проектах. А вот рантайм – это, поистине, сердце языка. В нем происходит выделение памяти, динамическое приведение типов и подсчет ссылок. И нам стало интересно, как реализован подсчет ссылок в рантайме Swift. И  вот мы вдохновились публикациями легендарного Майка Эша (Mike Ash), собрали компилятор и начали исследовать. Посмотрели на работу алгоритма подсчета ссылок и в этой статье расскажем вам о нём.

План:

1. Ссылка на объект

2. Битовое поле и операции над ним

3. Что такое счетчик ссылок?

4. Weak ссылки и side table

5. Жизненный цикл объекта

6. Флаги в счетчике ссылок

7. Заключение

Ссылка на объект

В процессе выполнения приложения в памяти создается множество объектов. И если продолжать создавать объекты и не удалять лишние, тогда память закончится. Чтобы этого избежать, нужен алгоритм освобождения памяти. Главный его принцип – это отслеживание достижимости объекта. То есть, когда на объект есть ссылки, то он считается достижимым. А пока на объект хоть кто-то ссылается – значит его нельзя удалять из памяти. И как только пропадет последняя ссылка, то объект уничтожается и освобождается занятая им память. Для отслеживания доступности объекта нужен алгоритм отслеживания активных ссылок. В Swift этот алгоритм реализован в виде механизма автоматического подсчета ссылок. Automatic Reference Counter, или сокращенно ARC – появился еще со времен Objective-C. В его основе счетчик ссылок, который есть у каждого объекта класса.

Ссылки на объект бывают трех типов – strong, weak и unowned. Объект живет в памяти пока на него есть хотя бы одна strong ссылка. И если объекты ссылаются перекрестными сильными ссылками, то они никогда не уничтожаются. Чтобы этого избежать, нужно одним из объектов сослаться weak или unowned ссылкой на другой. Если в момент обращения к weak переменной на объект уже нет strong ссылок, тогда мы получим nil. А при обращении к unowned будет выброшено исключение. Более подробно разные типы ссылок описаны в этом разделе официальной документации Swift. А мы же рассмотрим внутреннее устройство счетчика ссылок в следующем разделе.

Битовое поле и операции над ним

Счетчик ссылок – это битовое поле. Или говоря по другому – это битовый массив. Значения этого массива кодируются в один или несколько битов. А для получения и сохранения значений используются побитовые операции.

Битовые поля применяются для компактного хранения данных. В нашем примере мы будем сохранять целочисленные значения 7 и 13. В двоичной системе счисления число 7 – это 111, а 13 – это 1101. Нумерация битов начинается с нуля и идет справа налево. Мы можем сохранить 7 в первые четыре бита, а 13 в последние четыре бита. Для сохранения значения 7 в битовое поле нужно использовать побитовую операцию ИЛИ. Она обозначается как | и работает так:

0000 0000 | 0000 0111 = 0000 0111

В начале наше битовое поле размером 1 байт выглядит как 0000 0000. Побитовая операция ИЛИ принимает два битовых поля и поочередно применяет логическую операцию ИЛИ к битам с соответствующими индексами. Например, если оба бита в нулевой позиции равны нулю, тогда и в результирующем битовом поле нулевой бит тоже будет равен нулю. Если один или оба равны единице, тогда и результирующий бит тоже равен единице. Теперь давайте сохраним число 13, которое в двоичной системе счисления равно 1101:

0000 0111 | 1101 0000 = 1101 0111

В итоге мы получаем битовое поле в котором сохранено два значения. Но как теперь получить их обратно? Рассмотрим на примере числа 13, которое мы сохранили в битовое поле. Мы знаем, что число 13 лежит в последних 4-х битах. И нужно каким-то образом получить значения этих битов. В этом нам поможет побитовая операция И, обозначаемая символом &. Она, как и операция ИЛИ, выполняется над двумя битовыми полями, но к каждому биту применяет операцию логического И. Если оба бита установлены в единицу, тогда и соответствующий результирующий бит тоже будет равен единице. Посмотрим на работу операции побитового И на примере:

1101 0111 & 1111 0000 = 1101 0000

В результате получилось битовое поле, в котором последние четыре бита такие же, как и в левом битовом поле. То есть мы буквально попросили значения последних четырех битов. Теперь посмотрим на результат 1101 0000. Если перевести его в десятичную систему счисления, то получим число 208. И чтобы получить значение только последних четырех битов, нужно убрать группу нулевых битов. В этом нам поможет операция побитового сдвига вправо. Она обозначается как >> и смещает битовое поле на указанное количество битов вправо:

1101 0000 >> 4 = 0000 1101

В примере мы видим, что бит, который был в позиции 7 , теперь находится в позиции 3. И вслед за ним переместились и остальные. Их прежние места заняли нулевые биты. Проверяем, что 1101 это 13 в десятичной системе счисления. Благодаря комбинации побитового И вместе со сдвигом вправо, мы извлекли сохраненное значение. Похожим образом получим значение 7:

1101 0111 & 0000 1111 = 0111

Здесь не используется сдвиг вправо, потому что мы получаем значение из начальных битов. Второй операнд в побитовых операциях еще называют маской. Так как он “накладывается” на первый операнд. И именно от маски зависит правильность сохранения и извлечения данных из битового поля.

В iOS разработке напрямую битовые поля используются редко, но в исходниках Swift встречаются гораздо чаще. А теперь вернемся к счетчику ссылок и применим наши знания о битовых полях.

Что такое счетчик ссылок?

Это битовое поле, в котором хранится количество strong, unowned и weak ссылок. Но еще там есть вспомогательные биты, значения которых учитываются в процессе подсчета ссылок. В зависимости от разрядности процессора поле будет размером в 32 либо 64 бита. Далее будем рассматривать устройство счетчика на 64 бита. Для 32-х битных есть нюансы, но общие подходы не меняются. 

Счетчик ссылок хранится внутри структуры HeapObject. HeapObject – это внутреннее представление объекта в рантайме. То есть каждый экземпляр класса в рантайме это экземпляр структуры с типом HeapObject. Посмотрим на примере класса CommitInfo, в котором хранится хэш коммита и идентификатор пользователя:

class CommitInfo {
    let hash: Int
    let userId: Int
  
    init(hash: Int, userId: Int) {
        self.hash = hash
        self.userId = userId
    }
}

let firstCommit = CommitInfo(hash: 0xffee, userId: 1)

В рантайме переменная firstCommit является указателем на экземпляр HeapObject. В памяти он выглядит так:

Коротко пройдемся по значениям полей в HeapObject. Для удобства все значения указаны в 16-ричной системе счисления. В первом поле хранится указатель на структуру с метаданными объекта. В метаданных хранится указатель на метаданные базового класса, список свойств и методов, и еще несколько служебных полей. По сути – это описание внутренней структуры класса. Также указатель на метаданные, со времен Objective-C, называют еще и isa pointer.

Во втором поле лежит значение счетчика ссылок. А в последних двух полях сохранены значения свойств hash и userId объекта класса CommitInfo. Важно понимать, что в HeapObject только два первых поля являются обязательными. Остальные поля меняются в зависимости от структуры исходного класса. Мы обязательно рассмотрим HeapObject подробнее в одной из следующих статей.

А пока вернемся к счетчику ссылок и посмотрим на его значение – 0x3. Так как счетчик ссылок есть битовое поле, то нагляднее представить его в виде последовательности битов. И вот во что превращается 0x3:

На схеме представлено двоичное значение 11, но дополненное нулями слева до полного 64-х битного поля. На схеме мы видим группы бит, которые интерпретируются совместно. Назначение битов UseSlowRC, IsDeiniting, PureSwiftDeallocation мы рассмотрим позже. А пока обратимся к группе Unowned и Strong. В них сохраняются значения соответствующих счетчиков. То есть большой счетчик ссылок разбит на маленькие счетчики конкретного типа. 

Для получения количества unowned ссылок, нужно применить побитовую операцию ‎‎‎‎‎‎‎‎‎‎"И" с маской 0xFFFFFFFE над нашим битовым полем. А затем сдвинуть результат на один бит вправо. Зачем сдвигать вправо? Потому, что иначе мы получим значение вместе со значением флага PureSwiftDeallocation:

(0x3 & 0xFFFFFFFE) >> 1 = 1

Чтобы не перечислять каждый раз все 64 бита, мы будем использовать 16-ричное представление счетчика. И в данном случае счетчик unowned равен единице. Но ведь на объект ещё никто не ссылается по unowned ссылке? Для чего же тогда сразу сохранять единицу? Чтобы не инкрементировать в тот момент, когда появится настоящая unowned ссылка? Но ведь на объект за весь его жизненный цикл вообще может не быть unowned ссылок? И если они все таки появляются, то счетчик, ожидаемо, инкрементируется. Так зачем эта дополнительная единица? Ответ на этот вопрос мы получим позднее, когда в деталях познакомимся с жизненным циклом объекта. Пока же посмотрим на значение счетчика strong ссылок:

(0x3 & 0x7FFFFFFE00000000) >> 33 = 0

Для получения количества strong ссылок нужно применить маску 0x7FFFFFFE00000000. А после этого выполнить сдвиг вправо на 33 бита. В результате видим, что количество strong ссылок равно нулю. Постойте, но мы ведь знаем, что если у объекта нулевой счетчик strong ссылок, то он будет деаллоцирован. На самом деле у объекта есть одна сильная ссылка, но физически она представлена нулем. А почему бы явно не записать единицу, как в случае с unowned счетчиком? Ответ на этот вопрос нам не удалось получить. Просто примем начальный ноль как данность.

А что насчет счетчика weak ссылок? С ним все немного сложнее. Как видно на схеме, ему не нашлось места в счетчике ссылок. А когда появляется первая weak ссылка на объект, создается side table, в которой уже есть место для хранения weak счетчика.

Weak ссылки и side table

Side table – это внутреннее представление weak переменной. В side table сохраняется указатель на объект и количество strong, unowned и weak ссылок на него. Вдобавок в битовом поле, в котором уже лежит указатель на side table, выставляется два флага: UseSlowRC и SideTableMark:

• UseSlowRC – означает, что у объекта есть side table и все операции над счетчиками ссылок нужно проводить именно в ней. В HeapObject не осталось значений счетчиков ссылок, они переместились в side table.

• SideTableMark – смысл этого флага непонятен. Нам не удалось найти мест, где он проверяется.

После создания side table в счетчик ссылок внутри HeapObject записывается указатель на нее. А перед этим указатель сдвигается на 3 бита вправо. Если side table лежит по адресу 0x108B8E290, то в битовое поле адрес будет сохранен так:

0x108B8E290 >> 3 = 0x21171C52

Здесь также битовое поле представлено в шестнадцатеричном виде. Следом выставляется флаг UseSlowRC:

0x21171C52 | (1 << 63) = 0x8000000021171C52

И в последнюю очередь флаг SideTableMark

0x8000000021171C52 | (1 << 62) = 0xC000000021171C52

Значение 0xC000000021171C52 записывается во второе поле HeapObject, вместо старого счетчика ссылок:

Проверим, что все сохранилось корректно. Сначала получим адрес side table при помощи операции И с маской Ox3FFFFFFFFFFFFFFF и смещения на три бита влево:

(0xC000000021171C52 & Ox3FFFFFFFFFFFFFFF) << 3 = 0x108B8E290

Действительно адрес 0x108B8E290 мы и сохранили в примере выше. Похожим образом получим значение флага UseSlowRC.

(0xC000000021171C52 & 0x8000000000000000) >> 63 = 1

И значение флага SideTableMark

(0xC000000021171C52 & 0x4000000000000000) >> 62 = 1

Оба флага сохранены правильно. Если перевести 0xC000000021171C52 в двоичную систему, то получим такое битовое поле:

Теперь посмотрим, как side table выглядит в исходниках языка: 

class HeapObjectSideTableEntry {
  std::atomic<HeapObject*> object;
  SideTableRefCounts refCounts;
}

В самом первом поле хранится указатель на объект, которому принадлежит эта side table. Следом лежит его счетчик ссылок, представленный структурой типа SideTableRefCounts. Внутри нее хранится битовое поле со счетчиками ссылок и флагами. Именно то битовое поле, которое до появления side table лежало внутри объекта. Но также внутри SideTableRefCounts есть отдельное поле и для хранения счетчика weak ссылок. И теперь у нас появляется возможность отслеживать weak ссылки на объект! 

Side table работает в паре с классом WeakReference. По сути экземпляр класса WeakReference создается для каждой новой weak переменной. И взаимодействие со свойствами и методами объекта происходит через него. Класс WeakReference определен следующим образом:

class WeakReference {
  union {
    std::atomic<WeakReferenceBits> nativeValue;
#if SWIFT_OBJC_INTEROP
    id nonnativeValue;
#endif
  };
}

В nativeValue сохраняется указатель на нативный объект. Нативным называется объект, структура которого известна рантайму Swift и он может жить без рантайма Objective-C. Соответственно в nonnativeValue сохраняется объект, который наследуется от NSObject и им  управляет рантайм Objective-C. Так как это объединение, то в один момент может хранится только одно значение. Флаг SWIFT_OBJC_INTEROP  указывает на то, нужна ли интероперабельность с Objective-C – то есть можно ли из Swift кода работать с объектами Objective-C. На всех платформах от Apple этот флаг активирован. 

WeakReference хранит указатель на оригинальный объект. И для его получения вызывается функция swift_weakLoadStrong. Она принимает WeakReference единственным аргументом и возвращает указатель на HeapObject. Вызов swift_weakLoadStrong также увеличивает на единицу количество strong ссылок. Эта дополнительная единица сохраняется до конца текущей области видимости weak переменной. В конце области видимости strong счетчик уменьшается на единицу. А когда объект уже деалоцирован, то вызов swift_weakLoadStrong вернет null. Таким образом, в рантайме реализуется семантика слабых ссылок. Ведь экземпляр HeapObject физически еще присутствует в памяти. А WeakReference выступает в роли обертки и проверяет, не уничтожен ли еще объект с точки зрения рантайма. 

Жизненный цикл объекта

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

• Live – объект создан и делает какие-то полезные вещи.

• Deiniting – объект находится в процессе деинициализации, то есть у него вызван метод deinit.

• Deinited – объект полность деинициализирован.

• Freed – выделенная память под объект освобождена, но side table еще существует.

• Dead – память занятая side table освобождается.

Объект живет пока на него есть strong ссылки. И хотя счетчик strong ссылок инициализируется нулем, считается, что на объект есть одна ссылка. Он ссылается сам на себя. Ведь действительно на него еще никто не сослался, но и умирать ему рано. Для изменения значения счетчика strong ссылок используются функции swift_retain и swift_release. Функция swift_retain инкрементирует, а swift_release декрементирует значение счетчика. Компилятор генерирует вызовы этих функций в нужных местах.

Когда счетчик strong ссылок нулевой и вызван swift_release, объект переходит в состояние deiniting. Если у объекта есть метод deinit, тогда он тоже вызывается. Также в битовом поле счетчика ссылок выставляется флаг  isDeiniting. После этого объект считается деинициализированным. Но в состоянии Deiniting он будет находиться не долго. В зависимости от значений unowned и наличия side table состояние меняется на следующее:

• Если у объекта нет side table

  • Если количество unowned ссылок равно нулю, тогда объект сразу переходит в состояние dead.

  • А если unowned ссылки есть, тогда объект переходит в состояние deinited.

• Если у объекта есть side table

  • Если количество unowned ссылок равно нулю, тогда объект переходит в состояние freed.

  • А если unowned ссылки есть, тогда объект переходит в состояние deinited.

Если у объекта нет side table и в какой-то момент количество unowned ссылок на него станет равным нулю, тогда он из состояния deinited перейдет в состояние dead. В состоянии dead память под объект освобождается.  Для наглядности лучше представить жизненный цикл объекта без side table в виде схемы:

А если при нулевой strong счетчике есть side table и дополнительные unowned ссылки, то объект переходит в состояние deinited. При этом счетчик unowned ссылок уменьшается на единицу. Мы помним, что в начале он инициализирован единицей. И это начальное значение нужно уменьшить. После этого unowned счетчик станет равным количеству внешних unowned ссылок на объект. В этот момент объект уже деинициализирован. В коде приложения не доступен, но физически присутствует в памяти. И занимаемая им память освобождается только после обнуления счетчика unowned ссылок.

Вызов функции swift_unownedRetain увеличивает счетчик unowned ссылок на единицу. Соответственно вызов swift_unownedRelease уменьшает счетчик на единицу. Обе функции принимают указатель на HeapObject. Когда на объект не осталось unowned ссылок и ему вызван swift_unownedRelease, то он переходит в состояние freed. В этом состоянии память под объект уже освобождена.

Side table остается в памяти пока на объект есть weak ссылки. Ведь именно через side table происходит взаимодействие с weak переменными. А точнее через экземпляр WeakReference, в котором хранится указатель на side table. Класс WeakReference инициализируется вызовом функции swift_weakInit. Она принимает указатель на пустой WeakReference и указатель на HeapObject. .

В состоянии freed любое обращение к weak переменной вернет nil. Как только счетчик weak ссылок обнулится, объект переходит в состояние dead. В этот момент очищается и side table. Надеемся, что схема упростит понимание:

Мы познакомились с жизненным циклом и теперь вернемся к счетчику ссылок для знакомства с остальными флагами.

Флаги в счетчике ссылок

Каждый флаг занимает один бит. И первый бит в счетчике ссылок – это флаг pureSwiftDeallocation. Для всех нативных объектов он равен единице. Если он равен нулю, тогда во время деинициализации для объекта вызывается Objective-C метод objc_destructInstance. Он зачищает все associated objects и weak ссылки под управлением Objective-C рантайма. А следом вызывается функция swift_deallocObject. Именно в ней определяется, будет ли объект уничтожен сразу или же перейдет в состояние deinited.

В 32 бите расположен флаг isDeiniting. Он устанавливается в момент перехода в состояние deiniting. Причем флаг не сбрасывается при переходе в следующие состояния. Также значение флага isDeiniting проверяется в момент получения указателя на объект из WeakReference. Если он установлен, то вернется null. Значит в клиентском коде при обращение к weak переменной, на которую не осталось сильных ссылок, вернется nil.

Осталось познакомиться с флагом sideTableMark. Он находится в 62 бите и устанавливается, когда у объекта появляется side table. Нигде в коде не нашлось проверки этого флага. 

И в самом последнем 63-м бите находится флаг slowReleaseCounter. Этот флаг устанавливается для immortal и объектов с side table. Immortal объекты никогда не деаллоцируется. Еще он устанавливается, когда счетчик сильных ссылок переполняется. Что же происходит в этом случае? Если у объекта нет side table и он не immortal, тогда счетчик просто станет равен нулю. Учитывая, что счетчик strong ссылок занимает 30 бит, тогда у нас может быть максимум 2 147 483 647 сильных ссылок на объект. На схеме ниже отображены все флаги в битовом поле:

Вернемся к вопросу из начала статьи о том, почему счетчик unowned ссылок инициализируется единицей? Единица означает, что на объект еще можно создавать новые unowned ссылки. И как только счетчик станет нулевым, то при попытке инкрементировать его выполнение программы аварийно завершится.

Заключение

Рантайм Swift тесно работает с рантаймом Objective-C. И было бы здорово разобраться как считаются ссылки для объектов с базовым классом NSObject или NSProxy. Но это тема для отдельной статьи. А в этой мы начали с того, что такое битовое поле и побитовые операции. Затем посмотрели на представление объекта в рантами и увидели, что в начале у объекта есть одна unowned ссылка. И что в счетчике strong ссылок записан ноль, но интерпретируется он как единица. Узнали, что такое side table и как она связана с weak ссылками. Именно благодаря side table при обращении к деинициализированной weak переменной мы получаем nil. Посмотрели на различные флаги, которые лежат в битовом поле счетчика ссылок.

Затем познакомились с жизненным циклом объекта. Объект может быть в одном из пяти состояний: live, deiniting, deinited, freed, dead. Посмотрели на схему переходов между ними. Познакомились с некоторыми функциями в рантайме Swift. Это лишь малая часть из всего, что в нем есть. По рантайму вообще можно написать целую книгу!

Многое пришлось оставить за скобками, чтобы не усложнять повествование. Подсчет ссылок не просто реализовать. И то, что рассматривали мы – это уже вторая его реализация. Глядишь, в будущем его тоже захотят переделать. 

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

В будущем мы выпустим серию статей про другие части Swift, например, про внутреннее представление объекта и диспетчеризацию. При написании статьи мы опирались на этот файл в репозитории Swift. В нем описаны все флаги и общий алгоритм. Также на  официальном форуме языка есть интересная ветка, в которой обсуждали реализацию счетчика ссылок. Спасибо за внимание!