Что общего между ядром Linux и iOS?

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

iOS является объектно-ориентированной штукой. Где-то ниже Objective-C (а скоро мы сможем говорить уже и о Swift) залегают огромные пласты не-объектного кода, и под ними — Unix (а точнее BSD) система. И на том уровне у Linux и у iOS много общего. Но я и не об этом.

Давайте сравним основные структуры ядра Linux с объектно-ориентированной частью iOS.
 

1. Основные структуры

В обеих системах присутствует некоторое количество фундаментальных структур. Например, в iOS это будут:

Строки (NSSrting);
Массивы (NSArray);
Коллекции (NSSet);
Словари (NSDictionary);
Представление числовых примитивов (NSNumber);
Скаляры (NSRange).

Я оставляю за скобками различные вариации всех этих типов (NSSet / NSMutableSet / NSCountedSet и прочее).

Все эти типы данных реализованы как классы. Легко заметить, что тут нет нескольких фундаментальных структур: связных списков (linked lists) и бинарных деревьев (binary tree). Нет их по той простой причине, что они уже инкапсулированы в другие типы данных. Так, NSArray можно использовать вместо связного списка, а NSDictionary вместо бинарного дерева, не особенно заботясь о внутренней их реализации.

Хорошо. А какие же основные типы мы можем найти в ядре Linux? Тут ситуация выглядит с точностью до наоборот. Сложно выделить какие-либо стандартные для ядра типы данных. Наибольшие претенденты на это звание:

Двойной связный список, определенный в файле include/linux/list.h;
Красно-черные деревья, определенные в файле include/linux/rbtree.h;
Радиксные деревья (radix tree), определенные в файле include/linux/radix-tree.h;
Битовые массивы (bit arrays), определенные в файле include/linux/bitmap.h;
Ну а также семафоры и спинлоки, которые не присутствуют в iOS в явном виде — то есть, их не нужно алоцировать, они скрыты в методах.

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

Итак, на первый взгляд мы имеем два ортогональных подхода к построению системы. iOS предлагает достаточно чистый объектно-ориентированный подход, и Apple старается как только может скрыть внутренности объектов от конечного программиста. Ядро Linux, напротив, определяет очень базовые примитивы, оставляя программиста разбираться с ними. Грубо говоря, iOS это блочное строительство, а ядро Linux предоставляет в ваше распоряжение иногда кирпичи, а иногда просто глину и печь для обжига. Однако и цели программирования в двух системах совершенно различные: никто не ожидает от разработчика ядра создания пользовательского интерфейса, равно как никто и не ждет от программиста в iOS написания поддержки чипа и шины данных.
 

2. Так что же общего между двумя этими системами?

Референсы. Подсчет ссылок на объекты.

До недавнего времени iOS требовала от программиста вручную уменьшать счетчик объектов. Это делалось с помощью вызова стандартного метода retain для его увеличения, release для уменьшения. В последних версиях Objective-C в этом больше нет необходимости, система делает это автоматически.

Счетчик объектов — совершенно объектно-ориентированная вещь: у тебя есть несколько процессов, совместно использующих объект. Для простоты представим, что это объект только для чтения, то есть ни один из процессов не может его изменить. Но вот вопрос: когда этот объект должен быть освобожден? И кем?

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

Извиняюсь за занудство, но вот как это происходит. Из своего кода я создаю новую строку в iOS:
 

NSString *s = [[NSString alloc] init ];

После исполнения этого кода создался объект типа NSString. Переменная s держит ссылку на объект, и этот объект имеет внутренний счетчик, равный 1.
 

NSString *s2 = s;

После исполнения этой строчки кода переменная s2 также ссылается на тот же объект. И внутренний счетчик рефересов этого объекта будет равен 2.
 

s = Nil;

Теперь переменная s больше не ссылается на объект — и внутренний счетчик референсов в объекте равен 1.
 

s2 = Nil;

Теперь и переменная s2 больше не держит ссылку на объект. Объект не доступен, его адрес утерян. Внутренний счетчик объекта равен 0. Объект будет автоматически уничтожен системой сбора мусора.

А теперь вернемся к ядру Linux. И сразу откроем файл incluce/linux/kref.h
В этом файле мы можем видеть генерную реализацию именно этого механизма — счетчик референсов. Файл не слишком большой, но необходимый.

Ядро Linux с точки зрения параллельных процессов это очень интересная штука. Если ты забыл про синхронизацию — твой код очень быстро рухнет. Вместе со всем остальным ядром, кстати. Чаще всего для этого нужны доли секунды. Иногда секунды. Если ты забыл про то, что ядро реинтерантно, и твой код может быть прерван в любой момент времени — твой код упадет. Нет никакого способа предотвратить это — даже запрет прерываний не поможет решить проблемы синхронизации. Big Lock, когда-то существовавший в ядре, и позволявший остановить все, кроме твоего процесса, был удален из ядра годы назад, так как им пользовались. Нет, серьезно, это довольно странная ситуация: у тебя есть отличный способ решить все свои проблемы с синхронизацией, но тебе говорят: не надо это использовать, это плохая карма. Но у тебя никогда нет времени, а Big Lock чудесно предотвращает падения твоего кода. Так что в какой-то момент Линус волевым усилием удалил этот механизм.

Так вот, если сделать поиск по ядру, например по функции kref_init, то вы увидите, что он используется более чем в двухстах местах. Что для ядра довольно много. Каким же образом работает kref и зачем он нужен?

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

— Если суммировать логику работы kref, то она следующая:
— Создал объект? Сразу увеличь ему kref.
— Взял ссылку на объект? Увеличь у объекта kref на единицу (используя kref_get())
— Перестал использовать ссылку на объект? Уменьши kref объекта на единицу (kref_put())
— kref объекта достиг нуля? Объект уничтожается — ссылка на функцию-деструктор передается при вызове kref_put(), и используется из kref_put() автоматически.
 

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

Никакой морали в данной статье нет.

Ни для кого не новость, что ядро Linux во многих отношениях адаптировало объектно-ориентированную парадигму. Тем не менее, модераторы ядра не позволяют разработчикам усложнять его (ядро), и поддерживают инфраструктуру на уровне простейших примитивов. Философия тут заключается в том, чтобы “keep it simple” — позволь разработчику самому сварить свой суп из сырой грудинки, не предлагай ему супный набор или куриный порошок.

iOS, в свою очередь, идет по пути сокрытия деталей реализации от разработчиков. В какой-то момент в iOS появился ARC, Automatic Reference Counting, система, которая следит за счетчиком ссылок объектов и уничтожает их автоматически. В скором будущем, похоже, объекты будут автоматически не только уничтожаться, но и создаваться, на это указывают последние тенденции — в некоторых случаях уже сегодня можно опустить вызов alloc (наример, [NSSting stringWithFormat] работает так же, как [[NSString alloc] initWithFormat:]).

Для интересующихся:
Обсасывание системы референсов в iOS
Одно из первых упоминаний kref в ядре Linux
Документ ядра Linux по kref

Хорошего всем дня. Спасибо за внимание.

http://habrahabr.ru/post/232891/