Что общего между ядром 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

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

Комментарии 16

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

    Ну, если быть честным — то с введением ARC ситуация в этой сфере не поменялась вообще — внутренний счетчик был и ранее. ARC просто за программиста расставляет retain и release, не более того.

    Ну и <зануда мод> есть еще всякие слабые ссылки, не увеличивающие счетчика, да и вообще </зануда мод>

    уже сегодня можно опустить вызов alloc (наример, [NSSting stringWithFormat] работает так же, как [[NSString alloc] initWithFormat:]).

    Это тоже очень и очень старая конструкция. Ранее она отличалась от alloc] init] встроенным авторелизом. Не стал бы говорить о том, что это в том или ином роде тенденция.
      0
      Относительно конструкции NSSting stringWithFormat:
      На мой взгляд, это достаточно хороший индикатор того, куда может начать мигрировать iOS, а именно, в сторону полной автоматизации управления памятью. Как вы понимаете, эта конструкция появилась не из головы какого-то разработчика. Она была описана в архитектуре, прошло достаточно серьезные обсуждения, была одобрена и внедрена в язык. Если в ближайшие годы Apple не откажется от развития Objective C, полностью переорентировавшись на Swift, то мы увидим еще много интересных изменений.
      Сегодня объекты нужно создавать явным образом. При этом уничтожаются они автоматически. Это идет вразрез с общей идеологией изменений языка.
      Поглядим.
        0
        Не могу согласиться, что это направление для миграции, так как такого рода синтаксис был с самого начала iOS и всегда был в параллели с alloc-init. Соответственно нет никаких предпосылок, что эта ситуация будет меняться в ту или иную сторону.
        К слову — в свифте ситуация с управлением памятью практически такая же, просто не предоставлено явных инструментов для ручного управление (что не говорит, что мы не можем к ним обращаться).
          0
          Я смотрю на то, что относительно недавно появился ARC. Это шаг в направлении автоматизации — теперь объекты освобождаются автоматически. И вот в iOS наблюдается странная ассиметрия: объекты надо создавать, но не надо освобождать. Это нелогично. Более того, автоматическая алокация объекта с точки зрения управления памятью — это просто, это намного проще, чем ARC. Мне очень сложно представить себе ситуацию, в которой попытка записи в неалоцированнай объект (и как следствие invalid page fault) не является багом.
      +8
      Я не понял, а зачем вы сравниваете «коллекции» в user-space и kernel-space? Там же принципиально разные подходы к управлению ресурсами. Если уж на то пошло, то больше смысла будет в сравнении с IOKit.
        0
        Я не сравниваю коллекции в Objective C и в ядре: в ядре нет коллекций. Я просто привел список основных примитивов, доступных в обеих системах для организации данных. И именно для того, чтобы показать их разницу.
        В основном мне интересен именно тот факт, что один и тот же концепт, причем практически неизменном виде, присутствует в таких перпендикулярных системах, как iOS достаточно высокого уровня, и низкоуроневое ядро Linux.
          +1
          Про концепт — это вы про en.wikipedia.org/wiki/Reference_counting, который применяется еще в десятках других языков?
            0
            Да. Но дело в том, что в ни в стандартном C, ни в расширенном gcc нет встроенного механизма reference counting — просто потому, что это не языки, изначально построенные для ООП. Этим особенно и интересен refcounting в ядре — это относительно недавно внедренная конструкция. Когда я начинал работать с ядром, проблемы структур с общим доступом каждый решал как мог, и иногда мне попадались довольно странные идеи, явно списанные из каких-то других OS. Ядро вообще достаточно долго служило испытательным полигоном для людей из академии, которые притащили в него множество сложных и интересных для теоретиков идей и конструкций. В частности, постепенно ядро вбирало в себя все больше и больше различныех методик из ООП. Хорошо это или плохо — это уже филосовский вопрос.
              0
              Но RC несколько ортогонально ООП, вы не находите? Собственно, RC успешно применяется в С, в том коде, где нет понятий объектов или классов, а есть «общедоступные» структуры.
                –1
                Не соглашусь. RC как раз является базой ООП. Часто его не видно, но он есть там, в недрах реализации объкта. В системах с автоматической сборкой мусора сложно представить что-то другое.

                Необходимость в RC появляется в больших и недетерменированных системах, где сложно предсказать поведение — к сожалению, ООП часто приводит именно к этому. В небольшом функциональном проекте с десятком процессов просто нет необходимости в этой технике. И даже в ядре Linux RC появился только году так в 2006, а плотно использоваться стал еще позже. Да и сегодня при написании всякого рода драйверов RC используется относительно редко — драйвер создает несколько своих объектов, которые сам же при выходе и уничтожает. Гораздо чаще, на порядок чаще объекты синхронизации ядра это спинлоки и семафоры, в некоторых случаях даже просто атомарные счетчики, редко RCU.
                  +1
                  RC как раз является базой ООП
                  RC — это модель управления временем жизни данных. ООП — это парадигма программирования. RC используется в коде без ООП, ООП используется в коде без RC. Я не очень понимаю ваш аргумент. Кроме того, RC — это не примитив синхронизации, к чему тут еще и семафоры появились? RC не избавляет вас от синхронизации доступа к данным.
        0
        Тут просто дергаются указатели

        s = Nil; //В ячейку с адресом обьекта записали 0
        NSString *s2 = s; //ячейку s2 записали адрес что и s

        Я конечно понимаю что есть, АRC, но если человек не знаком с языком, нагляднее будет рассказать что есть явный вариант, и что у обьекта есть методы инкремента и декремента количества ссылок.
          +7
          Ожидал здесь увидеть сравнение linux kernel с darwin/xnu. А так это «Что общего между зубами крокодила и пухом хомячка?»
            –3
            Сравнивать Linux Kernel vs darwin/xnu как раз неинтересно. В низкоуровневых системах как очень много общих техник, там сложнее найти разницу, чем общие точки.
              0
              там сложнее найти разницу, чем общие точки

              Тем интереснее. Хотя разница между linux kernel и darwin/xnu велика, на самом деле.
                –1
                Возможно. Скажу честно, с darwin/xnu мне работать не приходилось. Один раз, году этак в 2003, мне пришлось туда залезть, уж и не помню почему. Больше никто и никогда не заказывал ничего с ним связанного. Так что моя позиция слаба.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое