VM lectures

lecture1.md

Лекция 1. Зачем нужна VM, и как устроена память

Виртуализация -- это парадигма, подход к решению некоторого широкого набора задач при помощи определенной практики.

Слово "виртуальный" -- средневековая латынь, латинское слово virtualis было впервые использовано товарищем, которого граф оставил вместо себя управлять поместьем (потом появилась специальная должность виконт, viscount). Этот граф отправился в крестовый поход, а на его месте остался человек, который обладал теми же достоинствами и добродетелями, но графом не являлся.

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

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

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

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

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

Другая похожая система виртуализации -- это система разделения времени. Из истории компьютеров: первая система, которая была предшественницей юникса, называлась MULTICS и являлась желанием людей в университете одновременно использовать один компьютер для более чем одного человека одновременно. Были созданы time-scheduling системы -- системы, которые умели по какому-то внешнему событию (таймеру) переключать текущий контекст исполнения и начинать исполнять что-то другое. В результате (тогда компьютеры уже работали быстрее, чем люди) исполнение, пока один человек как-то взаимодействовал со своей программой, его программа ждала, а другая программа могла исполняться. Если посмотреть на то, что происходит на компьютере при таком раскладе, то программе кажется, что она исполняется непрерывно, при этом реально на процессоре происходит исполнение кусочков программы, прерываемое аппаратным прерыванием, переключением контекста и продолжением исполнения какой-то другой программы. В результате программа может не думать, что она сосуществует с другими программами на этом компьютере, они просто исполняются независимо и не думаю о существовании других программ. И дело некоторого монитора виртуальных машин (schedulerа ядра ОС) -- осуществить создание кажимости, что у каждой из этих программ есть свой процесс.

Третий показательный пример -- виртуальная память. Если мы программировали на си или иже подобных языках, то мы знаем, что, с точки зрения программы на языке си, вся память -- это один большой линейный массив, а указатель -- это индекс в этом большом линейном массиве. Весь язык си построен вокруг указателей, арифметикой над ними. Если это верно про аппаратный компьютер (у компьютера есть какое-то количество физ памяти), то из-за того, что в нем существует множество различных программ, и в разных компьютерах много чего разного (той же памяти), то иллюзия непрерывного линейного пространства (например, от 0 до 4 ГБ для 32-битного пространства, от 0 до дохрена для 64-битного) некорректна. Существует какая-то сущность (в данном случае у ОС) -- менеджер виртуальной памяти, который создает иллюзию непрерывной линейной памяти поверх сузествующей физической памяти и, соответственно, обеспечивает композицию размещения данных разных программ в этой самой наличной физической памяти.

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

Примеры из зала: нету :(

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

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

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

И внутренний, и внешний аспекты виртуализации (внутренний -- мир достаточно прост внутри виртуализированной системы, внешний -- этим миром, в котором живут виртуализируемые сущности, можно как-то управлять) одинаково важны и полезны.

Польза

Для чего виртуализация вообще людям нужна? Идея -- уйти от каких-то конкретных деталей машины.

• Упрощение разработки -- польза, например, высокоуровневых языков.

• Безопасность -- виртуальная память позволяет пользователям не знать конкретные физ. адреса, с которыми они работают.

• Стабильность

• Прозрачное управление ресурсами (если мыслить о памяти как о ресурсе, GC -- относительно прозрачный сложный менеджер ресурсов). Если посмотреть на большинство современных сборщиков мусора, это достаточно сложные программные компоненты с десятками тысяч строк кода, с достаточно сложными алгоритмами, но для обычного пользователя эта компонента является практически несуществующей -- практически нет даже операций для ызаимодействия с GC, а те, что есть, достаточно дурацкие. Явная инициализация сборщиков мусора, финализация в той джаве -- достаточно неудобные.

• Организация обратной совместимости -- во многих компьютерных системах накапливается гигантское количество legacy-кода, который часто и по финансовым, и по практическим причинам невозможно переписать, и поэтому, если legacy-код можно продолжать исполнять, то это создаст людям достаточно большую гибкость в управлении ресурсами.

  Например, VirtualBox -- это изначально был небольшой немецкий стартап под названием AnnoTek, который работал ровно над следующим: была такая ОС -- OS/2 от IBM -- достаточно хорошая ОС, которая по маркетинговым причинам не полетела, была завалена Windows. Но за время ее существования было написано большое количество софта для нее, в т.ч. для немецкий банков. И вот эти вот немецкие банки очутились в очень странной ситуации -- у них было написано много ПО, важного для их функционирования, но у них не было компьютеров, на которых они могли бы исполнять эти программы, ибо OS/2 в какое-то время перестала поддерживаться и запускаться на более современных компьютерах.

  AnnoTek, осознав такую картину мира, написали гипервизор, который был способен исполнять ту самую OS/2, и продавали его банкам. Стартап затем купил Sun, но это совсем другая история. Вот такой типичный пример, когда виртуализация сильно помогла с обратной совместимостью.

• Облачные вычисления -- классический пример виртуализующих технологий, в частности, один из важных аспектов виртуализации -- балансировка нагрузки; именно благодаря виртуализации можно покупать на Амазоне очень странные компьютеры, которые вообще в природе не существуют, либо потому что они слишком мощные, либо наоборот, но тем не менее, Амазон создает достаточно непрерывную верификацию именно за счет того, что при помощи виртуализации можно очень тонко контролировать реальное количество ресурсов, доступные компьютеру, и при этом ситуация с программами абсолютно не меняются -- программы, написанные под тот же Linux или Windows, точно так же продолжают исполняться, просто их менеджер ресурсов (в данном случае -- гипервизор, который контролирует контекст исполнения VM, отдает ему ровно столько ресурсов, за сколько уплачено).

• Создание новых сущностей. Понятно, что такая технология виртуализации может моделировать что-то существующее (например, старые компьютеры, на которых исполнялся OS/2). Так как это программная модель, то на ней можно написать модель чего угодно, например, модель несуществующего компьютера (придумать свой идельный компьютер, придумать модель для него, а затем начать писать программы для него, и потом когда-нибудь воплотить его в кремнии), так что виртуализация позволяет делать прототипы и осуществлять раннюю разработку сложных компьютерных систем.

  Если вдуматься, JVM -- тоже компьютер, просто компьютер, никогда не существовавший, компьютер с объектно-ориентированным набором инструкций.

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

Кроме того, у нее есть такой любопытный аспект, как менеджер ресурсов, который адаптируется к непредсказуемым запросам нескольких пользователей в типичных ситуациях, т.е. достаточно часто бывает так, что при разработке ОС люди понятия не имеют, какие программы будут под ней запускаться, и сколько их будет, и в каком ассортименту они будут запущены в конкретный момент.

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

Вот эти вот аспекты -- это аспекты, которые существуют примерно в любой системе управления, в любой VM.

Что дальше?

Дальше обсудим уже некоторые такие специфичные вещи (что такое ресурсы, как ими можно управлять, ...) Что такое контекст исполнения? Каким образом можно создать для программы полностью контролируемый контекст? Как этого добиваются разного рода системы исполнения? Дальше рассмотрим реальные машины (виртуальную машину джавы -- HotSpot), затем поговорим о других механизмах виртуализации -- виртуализации существующего аппаратного обеспечения на примере VirtualBox, немножко qemu. Потом немножко поговорим про верификацию программ для исполнения на рантаймах (по сути, про различные системы проверки, что программа делает что-то и не делает чего-то другого, что важно для многих рантаймов, предоставляющих гарантии), на примере верификатора байткода, верификатора в nacl-е. Про разные системы менеджмента памяти (сборщики мусора, конкретные алгоритмы), про системы виртуальной памяти в ОС, немножко про менеджер памяти в гипервизорах (он там простой, к счастью), про разные быстрые системы исполнения инструкций (интерпретатор, JIT, системы гибридного исполнения, как, например, некоторые гипервизоры -- у них часто сочетается непосредственное испонение инструкций с JIT-трансляцией тех кусков, которые нельзя непосредственно исполнить по тем или иным причинам). Про то, как можно эмулировать различное аппаратное обеспечение (на примере x86: сетевые карты, таймеры, контроллеры прерываний итд), про то, как быть менеджером реальных физических устройств, как гипервизоры разделяют доступ к физическим устр-вам. Немного обсудим безопасность VM (как работают верификаторы, как контролируется то, что может делать программа при помощи всяких аппаратных устр-в вроде MMU, привилегированных уровней процессора), ну и немного о самой сложной проблеме любого рантайма -- о производительности (как писать высокопроизводительные рантаймы, как добиваться относительно высокой производительности от существующих рантаймов).

Resource Management

Представим себе большую семью. Ужин. Есть некоторый ресурс -- кастрюля с супом. Есть десяток детишек, четверо взрослых, и необходимость разделить суп по вот этой самой разношерстной публике (детям кому-то год, кому-то 5, кому-то 15), у всех разные состояния. Как делить суп? Какие есть стратегии?

• Дать каждому поварешку, пусть набирают

• Есть гипервизор-мама, которая знает, кто сколько хочет, и раздает в той же пропорции (менеджер ресурсов, который учитывает потребность)

• Всем поровну

• Никому ничего не давать

• Упорядочить по степени нужды (давно не ел -- поешь). Планировщик задач, учитывающий предыдущую историю

• Пускать каструлю по кругу -- монопольный доступ

• Адаптивная стратегия -- пришел за добавкой -- добавили

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

Какие бывают интерфейсы получения памяти в компьютерах (например, в языке си)?

• malloc

• выделение памяти на стеке (выделяется через интеррапты -- когда мы пытаемся на стек что-то записать, чтобы ОС сама докинула туда память). Это пример неявного менеджмента ресурсов с общением с менеджером ресурсов. Не было бы ядра ОС, которая могла бы обработать попытку обратиться к невыделенной памяти

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

Как это работает? Сегмент данных BSS, сегмент стека SS. Эти данные при попытке выполнить программу ничем не инициализируются, просто создается такой layout виртуальной памяти, и stack pointer ставится между сегментами. Этот процесс потребляет (как бы) нек-рое количество вирт. памяти, но не потребляет реальную, так как доступ к любому адресу из ss ведет к ошибке -- page fault 2. Так же работает и загрузка кода -- если есть сегмент кода CS, то чаще всего, когда запускаем программу, сегмент не вычитывается с диска, а происходит просто отображение с файла на иске в память. Начало исполнения ставится на точку входа. При попытке исполнения, когда, собственно, процесср пытается вытащить первую инструкцию с памяти, происходит тот же самый page fault. Дальше исполнение переходит в обработчик в обработчик ОС, который смотрит, ага, у меня здесь вот сегмент кода отображен в файл на диске, и случился page fault. Но это не настояний PF, а это PF, который говорит мне, что файл отображен в память. Поэтому я зачитаю кусочек файла и перенесу его в оперативную память, и дальше продолжу исполнение.

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

Походая ситуация с SS: когда процессор видит, что происходит fault, но fault в районе сегмента стека, он понимает, ага, это на самом деле не программа что-то плохое сделала, а просто я должен сейчас довыделить кусочек физической памяти и подложить его под сегмент; после этого fault завершается и программа продолжается как ни в чем не бывало. То есть, с точки зрения программы произошло что-то типа sub rsp, 16 (вычли из регистра стека число 16) и mov [rsp+4], 42 (хотим записать в какое-то место на стеке в стекфрейме число 42). Вторая инструкция сначала уйдет к fault-у в ядро, потом память подмапливается и дальше, если есть следующая запись mov [rsp+8], 99, то тут уже никакого фолта нет. Благодаря такому механизму у нас есть достаточно гибкий механизм управления памятью.

• free -- операция, парная к malloc. Дай мне кусочек памяти. я скажу, сколько байтов, ты мне дай по крайней мере столько же, можно больше, и верни адрес этой полученной памяти. я могу делать с ней что хочу, и пока я не скажу free, ты мне как менеджер ресурсов гарантируешь, что никто другой ничего ни читать, ни писать, ни использовать эту память не сможет.

  Минусы: можно забыть сделать free, а можно сделать free дважды (использовали библиотечную функцию, освободили память, а потом эта функция освобождает эту же память). Неприятная, сложно отлаживаемая проблема.

Как организованы операции malloc и free? У нас есть массив под названием heap. Мы говорим: malloc 42 байта. Memory allocator бежит по той или иной структуре, описывающей свободное пространство (например, по free list-у), находит подходящее место дял нового объекта в 42 байта и возвращает указатель на начало этого места. Теперь мы говорим: free. Менеджер ресурсов убирает информацию о том, что это место занято, и это место становится свободным. И туда кто-то может что-то записать перед тем, как наш free сработает во второй раз...

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

Следующая техника более популярна для управляемых (managed) рантаймов -- это явное выделение и неявное освобождение (в джаве мы не встречаем команду free по каким-то непонятным причинам, но все понимают, как это работает). Как работает освобождение памяти в управляемых системах? За некоторым ресурсом (за ресурсом памяти) стоит некоторый менеджер ресурсов, который пытается обеспечить видимость того, что, если что-то не нужно, то оно магическим образом перестает занимать память, и поверх этой памяти можно выделить какие-то новые объекты. То есть, в принципе, всем замечательная схема.

Мы просмотрели три варианта (явное выделение и освобождение -- malloc и free; явное выделение, неявное освобождение -- java и GC; неявное выделение и освобождение -- управление стеком, где мы просто инкрементируем регистр в процессоре, а факт, что после этого доступ к памяти привел к активированию какой-то сложной логики в менеджере виртуальной памяти, абсолютно скрыт от пользователя).

Мы знаем, что стек выделяется неявно. А когда он освобождается? При смерти процесса. А может ли физическая память освободиться раньше? См. свопинг.

Что мы увидели на этих примерах? У нас есть какой-то ресурс или их набор. У нас есть нек-рое количество потребителей этого ресурса, причем потребители разные (одним нужно много памяти, другим нужно достаточно мало, но сию секунду, и они не готовы ждать), при этом то, кому что нужно, не зависит от того, что у нас сейчас есть. Людям и программам нужна память в тот момент, когда она им нужна, а не когда она освободилась в ОС. В итоге нам нужен менеджер ресурсов, который может удовлетворять (в каком-то спектре потребностей) запросам широкого набора потребителей и при этом не исчерпывать ресурс до конца. Глядя на все эти рассуждения, мы приходим к концепциям VM, если подумаем о двух вещах: обо всех ресурсах, которые вообще программе нужны для ее существования, и о том, как эти ресурсы распределяются. Получим идею контекста исполнения, в котором происходит исполнение программы.

Что нужно программе или процессу, чтобы исполниться?

• Процессорное время
• Память
• Идентификатор процесса (самому процессу он не нужен)

Что такое ресурсы, легко понять по тому, что потребитель ресурсов может сделать. Ресурсы -- это различные функциональности для исполнения. Что может делать программа на юниксе?

• ввод/вывод (файловая система, сеть, ...) Понятно, что ресурс виртуальный (никаких файлов, сокетов не существует, это абстракции поверх места на диске: файл -- способ организации пространства на диске, сетевое соединение -- абстракция для того, чтобы осуществлять взаимодействие в коммутируемой сети, и т.д.)

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

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

Во многом у VM, если говорить о ней изнутри (с точки зрения программы, которая исполняется под VM), то это не что иное, как модель контекста -- то, что описывает мир, в котором программа может жить. Можно подумать о java-машине. Как выглядит программа для языка Java, которая исполняется виртуальной машиной? Это .class-файл -- совокупность constant pool, метаданных, описания классов с сигнатурами и байткодом. Индивидуальный .class-файл описывает один отдельный класс, у которого есть какое-то количество метаинформации, связывающей его с другими классами и интерфейсами, и описание некоторой функциональности, которую данный класс реализует. Поэтому все, что нужно для исполнения программ на языке java -- это россыпь .class-файлов. И виртуальная машина должна предоставить все, что можно в этом .class-файле написать.

А что можно в нем написать? В целом, в байткоде написано: я могу делать вот такой набор операций, я могу вот так взаимодействовать с набором других классов

Аналогичным образом мы можем подумать о простой программе на языке си. Если мы напишем hello world, то для ее существования тоже нужен некоторый контекст: компилятор (или интерпретатор, никто не мешает написать интерпретатор для языка си). Например, #include <stdio.h> -- это инструкция для нек-рой программы под названием препроцессор, которая выполняет сложную операцию: по имени файла в специально обсученных местах находит файл с таким именем и осуществляет его текстовую макроподстановку во вход для компилятора. printf("Hello world") -- здесь контекст такой, что мы можем что-то выводить пользователю через какой-то канал (монитор, 3d-принтер, азбука Морзе -- здесь не очень понятно, но мы ожидаем некоторый набор side-эффектов). Поэтому даже относительно простые программы на самом деле влекут за собой некоторый весьма нетривиальный контекст.

Но тем не менее оказывается, что этот контекст почти всегда можно замкнуть. Можно понять, какой набор программ, понятий ожидает программа, и на основании этого набора понятий создать менеджер этого самого набора понятий.

Контекст в JVM

Если говорить о компонентизации в JVM, то можно выделить следующие фрагменты:

• Загрузчик классов (вход в java-машину, получение мета-информации о классе, верификация, понимание, что внутри класса написано)

• Система исполнения байткода, состоящая обычно из интерпретатора, скомбинированного с динамическим профилировщиком, и система трансляции во время исполнения, то бишь JIT

• Система управления памятью (что в народе называется garbage collector, что странно, ведь управление памятью -- это не только ее освобождение, но еще и выделение)

• Система дефрагментации памяти и так далее

Это достаточно разлапистая система, в которой сама система сборки мусора играет хотя и важную роль, но далеко не единственную.

Как мы достигаем полностью предсказуемого контектса в JVM? Почему JVM-языки (тот же Kotlin, который до появления JS и Native был полностью JVM-языком), вход которого -- это некоторый текстовый файл на каком-то языке высокого уровня, а выходом является тот самый байткод, хорошо специфированный формат описания программы в некотором таком объектно-ориентированном мире? Из чего состоит этот объектно-ориентированный мир в JVM?

Понятно, что JVM не равно Java. Java -- это высокоуровневый язык, который можно компилировать при желании в тот же машинный код, а в JVM можно компилировать другие входные языки, главное, чтобы их семантика ложилась на семантику JVM.

Чтобы понять, что такое JVM, надо понять, какие в ней есть абстракции, каким словарем оперирует JVM.

• Объектная модель -- классы, интерфейсы, объекты и методы. Одна из таких популярных парадигм программирования -- это ООП -- попытка рассуждать обо всем как об объекте.

Вообще, большинство парадигм в программировании -- это Everything is a ... . Например, парадигма юникса -- Everything is a file. ФП -- everything is a function. ООП -- everything is an object.

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

В рамках этой объектной модели (а Java придумывали как раз тогда, когда ООП было основным способом думать, ФП было сугубо академическим развлечением, поэтому в оригинальной Java функциональных конструкций особо не присутствовало, и все было объектом). Поэтому в формате байткода описывается достаточно точно некоторый набор объектно-ориентированных взаимоотношений (данного .class-файла с другими .class-файлами, вызова тех или иных методов и т.д.)

Стековая машина отличается от регистровой. Характеристика практически любого набора инструкций -- это то, что кодирует инструкция, в каком наборе понятий выражена семантика данной инструкции. Например, если посмотреть на intel x86 manual, то там можно увидеть, что инструкция add -- это сложение значения source регистра с аргументом и помещение назад в тот же регистр. Здесь параметром описания являются имена регистров. У регистровой машины есть набор регистров (предсказуемое количество, не очень большое, регистров), и над ним регистровая машина производит различные манипуляции.

Если посмотреть на чистые регистровые машины (например, про RISC-процессоры типа ARM, SPARC), то у них все операции можно производить исключительно над значениями регистра. Если что-то есть в памяти, то сначала значение надо загрузить в регистр, затем выполнить операцию над регистром, затем, если надо сохранить, то значение регистра сохраняется в памяти.

Операнды инструкций стековой машины динамически переименовываются. Грубо говоря, операндами всегда являются 2-3-4 верхних элемента стека, и причем какие конкретно элементы стека сейчас наверху, зависит исключительно от глубины стека.

Ключевой частью байткода является т.н. байткод, или набор инструкций JVM. Это набор для некоторой стековой машины: все инструкции манипулируют не непосредственными именами регистров, а, грубо говоря, двумя верхними значениями, которые сейчас лежат на вершине стека. Например, IADD берет два значения с верхушки, складывает их, и кладет на вершину стека.

Кроме этого, в JVM существуют стандартизированные типы данных (то есть, JVM не является чисто объектно-ориентированной системой, потому что изначально ориентировалась для embedded-приложений, еще в ранние годы Sun, поэтому там пришлось много вкладывать в эффективность). На самом деле, в Java не все -- объект. Есть несколько выделенных типов (мы их знаем как примитивные), которые представляют примитивными значениями, и ими можно манипулировать непосредственно. Тот же IADD не складывает объекты типа Integer, а складывает intы.

В .class-файле записано вот что. Я класс Foo. Мой суперкласс -- это класс Bar (причем ссылка на суперкласс символическая -- сугубо по имени, просто в constant pool написана строчка Foo и строчка Bar и ссылка в соответствующем элементе метаинформации на соответствующее место в constant pool). Я реализую интерфейсы I1, I2, I3, у меня есть методы m1, m2, m3, и про все поля и методы указаны их полные сигнатуры (и можно по этой метаинформации понять, как слинковаться с данным объектным файлом).

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

Поверх этих всех квантов у нас есть абстрактная исполняющая машина, которая умеет, взяв в кач-ве входа .class-файл и нек-рое описание того, что нужно запустить (entry pointer какой-нибудь), загружать требуемый файл и все его зависимости, после чего передавать исполнение на точку входа. И дальше программа исполняется на этой абстрактной стековой машине тем или иным образом до какого-то завершения. При этом в абстрактной машине описан полный lifecycle объектов, полный lifecycle классов, потоки нормального исполнения (controlflow), поток исключительного исполнения (обработка исключений тоже является частью стандарта JVM).

Что является одним из самых величайших достижений Java -- это полностью специфицированная система. Если почитать стандарт языка Си (особенно времен, когда создавалась Java), там до сих пор большая часть естественных операций описана с пометкой UB (например, знаковое переполнение в Си -- до сих пор UB, то есть, взрыв компьютера при умножении больших чисел не запрещен стандартом Си). В JVM все поведение специфицировано (причем все аспекты, в том числе исключительный -- кончилась память, переполнился стек, поделили на 0, разыменовали нулевой указатель, в общем, все классические непонятные ситуации мира Си четко специфицированы в Java и четко описано, что будет при том или ином раскладе).

Также в Java специфицированы стандартные механизмы конкурентного исполнения (может быть, не самые лучшие, но на момент придумывания JVM примитивов синхронизации лучше не было), поэтому в язык жестко гвозд]ями прибита концепция поков, мьютексов, возможности синхронизации на любом объекте и так далее.

Кроме этого, в Java существует экосистема, состоящая не только из базовых операций, но включающая и стандартную библиотеку -- набор предоставленных с самого начала операций, которые есть в любой JVM: ввод-вывод, графический интерфейс, JNI, описывающий, как из JVM передавать управление на код, написанный не на Java (обычно на C/C++).

Также важной частью экосистемы Java являются компиляторы из высокоуровневых языков (в частности, javac компилирует с Java, еще есть Jython, Groovy, ...)

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

Также есть инструменты мониторинга и профирования (JVM TI -- tooling interface, позволяющий понимать, что на текущий момент JVM исполняет, и на основании этого интерфейса с помощью тех же профиляторов выяснять, какие в программе bottleneck-и, и т.д.)

Все вместе это создает некоторую экосистему (экосистема -- это нечто большее, чем виртуальная машина, так как она описывает не только взаимоотношения компьютеров и компььютерных программ, но и взаимоотношение людей, то есть, это тот мир, в котором происходит разработка софта). Часто VM и гипервизоры связаны с экосистемами, они являются инструментами, которые позволяют эти экосистемы образовывать. Если у нас есть виртуальная машина, то она позволяет обеспечить воспроизводимость контекста, а в результате на нем можно строить экосистему. Для индустриального программирования это очень важный аспект. Грубо говоря, если мы просто пишем программы, то они скорее всего окажутся на свалке истории, а если мы создаем большие экосистемы, то как-то так выясняется, что они очень долго живут сами по себе, причем часто многие программы сейчас пережили своих автором, а есть и такие программы, которые сейчас уже никто не поймет. Экосистема -- это для людей возможность такого вот sustainable функционирования, потому что мы сейчас очень сильно зависим от программы.

Управление памятью в Java

Теперь попытаемся понять, как реализуются разные кусочки этих управляемых контекстов на примере работающей системы (на примере Java).

Разработка (и понимание) любой системы должно начинаться с понимания требований к этой системе (то есть, что система вообще делает). Почитав часть JVMSpec, то мы не увидим там особого описания желаемых алгоритмов GC или чего-то подобного. Но там есть определенный контракт, накладывающий ограничения на то, что любой memory manager для Java обязан делать.

Память всегда выделяется под какой-то объект. У любой памяти есть некоторая типизационная информация: у malloc такой интерфейс, что он не подразумевает, что ту память, которую мы выделили, у нее есть какая-то объектно-ориентированная метаинформация (какой-то тип или что-то еще), мы можем выделить кусок памяти, и это будет просто кусок памяти.

В Java память всегда выделена под некоторый типизированный объект. Это значит, что где-то должна храниться метаинформация (объект класса, который описыыает данный объект). Не может быть ad-hoc объекта. В JS любой объект -- словарь с динамическим содержимым, и привязка к какой-то метаинформации, информации о типах, достаточно условно. Даже объектно-ориентированный, managed рантайм не обязан быть типизированным.

В Java у памяти всегда есть некоторое значение по умолчанию. В том же машинном коде, если мы посмотрим на содержимое памяти, то, что там записано, мы понятия не имеем. В случае JVM память всегда инициализируется в некоторое значение по умолчанию (null для объектных ссылок, false для boolean, нулевой символ для char и т.д.) Для эффективности реализации сделано так, чтобы реальное физ представление в памяти дефолтного значения всегда было одно и то же (нулевые биты), хотя понятно, что в реальной интерпретации для float это будет 0.0, и так далее. Представление информации может быть разным для разных типов, но побитовое представление всегда нулевое.

После начальной инициализации на памяти всегда должен вызываться конструктор объекта (память нельзя просто выделить, не проинициализировав способом, который описал программист). Память может быть освобождена при недоступности объекта.

Абсолютно корректная реализация JVM -- такая, которая вообще не освобождает память. Если у компьютера бесконечная память, то можно написать JVm вообще без GC, то есть, будет простой memory manager, который при необходимости выделить выделяет, но ничего не удаляет.

Ошибкой является отождествление времени жизни объекта с жизненным циклом программы. Объект может удалиться непонятно когда. В языке Java есть метод Object.finalize(), который можно перекрыть и который должен вызываться при достижении объектом конца своей жизни. Кое-кто помещает туда освобождение независимых ресурсов (например, закрытие файловых дескрипторов). Это логическая ошибка, ведущая к тонким и неприятным моментам.

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

Запрещен алиасинг -- нельзя одну и ту же память интерпретировать несколькими способами (вот в C++ существует union).

Кроме этого, у объектов есть такое понятие, как Object identity -- операция сравнения. Операция == -- сравнение объектных ссылок. Это сложная операция, подразумевающая, что у объекта есть собственное существование, идентичность, то место, где объект хранится. Это нетривиальное свойство. На целочисленных значениях == означает совсем другое: что число, хранящееся внутри объекта, равно другому числу. То есть, в Java есть равенство по значению, а есть равенство по identity -- по тому месту, где хранится объект, и это тоже контракт memory manager'a.

Еще один контракт -- это наличие операции hashCode. Возможность реализации конкретного hashCode -- тоже нетривиальная операция. Зачем он нужен? В системах типа C++ есть неявное стабильное свойство типа address -- место в памяти. В Java такого места, которое всегда одинаково, на самом деле нет, стандарт не подразумевает наличие вот такого свойства, так как объекты могут быть перемещены GC. Поэтому пришлось придумать то, как создать и сохранить в объекте hashCode. У каждого объекта есть identityHashCode, это некоторой стабильный идентификатор, который при существовании объекта не меняется даже при перемещении между поколениями -- уникальный номер объекта.

Следующей свойство языка Java, выгодно отличающее его от плюсов -- при недостатке памяти бросается определенная ошибка OOME, и ее можно перехватить и что-то сделать. (В плюсах был бы краш и грустное сообщение). OOME может включить GC (?)

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

Жизнь объекта:

• Начинается с того, что это просто участок в некотором heap-e -- месте памяти, которое тем или иным образом выделено менеджером виртуальной машины для того, чтобы выделять в нем память. Для самого heap-а память обычно выделяется прямым запросом у ОС достаточно большого региона. Ключики типа -Xmx регулируют, сколько именно памяти нужно попросить у ОС.

• После того, как нам поступил запрос на выделение объекта, аллокатор (одна из частей memory mamager-a) выделяет требуемый кусок (обычно немножко выровненный) и заполняет его нулями -- это уже вход для следующей фазы.

• Записать в этот объект некоторый заголовок (типизационная информация -- ссылка на объект класса, именно она позволяет делать проверки типа instanceof -- выяснять у объекта, какого он собственно типа).

• Инициализация объекта вызовом конструктора

• Полноценная жизнь объекта, он участвует во всяких взаимодействиях

• Объект когда-либо может стать недостижимым. (обсудим, что это, чуть позже)

• Объект переходит в финализированное состояние

• Объект во время финализации может перейти в состояние "живое"

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

• Когда все эти танцы завершились, он снова становится просто участком в heap-е, могущий стать новым объектом следующих аллокаций.

Анализ достижимости

Анализ достижимости подразумевает достижимость откуда-то. В терминологии сборщиков мусора и систем управления памятью, элементы, объекты, достижимые из которых считаются живыми, называются root set-ом.

Что является элементами root set-а в JVM?

-- Х: стек и статическая память. И: что такое статическая память, прости Господи? Х: Там, где хранятся, например, все статические строки. И: как Вы думаете, если они статические, то какой смысл их анализировать в анализе достижимости? Х: по крайней мере, это то, что нам говорил АМ, но почему им не вести себя просто как остальным объектам? И: в любом анализе достижимости его имеет смысл проводить для чего-то (например, чтобы собрать мусор). Если у нас объекты иммутабельны и внутри нет объектных ссылок либо есть на такие же иммутабельные (например, String), то на них анализ достижимости не очень обязательно производить (ведь тут он ничего нам не даст). Х: хорошо, память статических полей, к примеру, это же не стек. И: статические поля не являются элементами root set-a, несмотря на популярную мифологию.

Далее зал молчит.

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

Там все не очень сложно, просто еще служебные структуры VM являются дополнительным источником элементов root set-a, потому что бывает, что чего-то не находится на стеке, но тем не менее это то, с чем сейчас работает VM, и нам не хотелось бы, чтобы это исчезло. Например, саллоцировали мы объект, записали туда типовую информацию, а потом кто-то в другом потоке запустил сборку мусора. Понятно, что этого объекта еще фактически нету, он только-только саллоцирован, но VM бы не очень хотела, чтобы он вдруг неожиданно исчез из-под рук.

Есть еще JNI-ные ссылки (внешние интерфейсы из Java в мир Си, эти интерфейсы, в частности, позволяют создавать держащую ссылку на Java-объект), это тоже гарантированные элементы root set-a.

Root set -- это такие точки входа в объектный граф, а дальше мы считаем транзитивное замыкание отношения "ссылается": обходим объекты, на которые ссылается объект, обходим то, на что ссылаются ссылаемые объекты, и так в результате делим весь класс мыслимых объектов на две группы: на группу достижимых объектов и на группу недостижимых. Дополнение до группы достижимых объектов можно называть мусором, в том смысле, что по построению множества, оно обладает свойством, что до него никогда нельзя добраться.

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

Слабые ссылки. В Java по мере эволюции появилось достаточно много классов ссылок (изначально существовала только одна -- обычная ссылка на объект). Существует еще три класса ссылок: java.lang.ref.SoftReference, java.lang.ref.WeakReference, java.lang.ref.PhantomReference. Отличие только в различной политике обработки коллектором.

SoftReference просит не коллектить объект, она пытается просить хоть и не держать объект, но все-таки немножко приоретизировать факт его сборки мусором. WeakReference никаким образом не влияет на то, будет объект заколлекчен или нет.

В каких структурах лучше SoftReference? В кешах. Когда мы держим какую-то структуру, которую долго перестраивать, но мы в приципе готовы ее перестроить, но лучше бы не перестраивать без лишней необходимости. WeakReference полезен, например, для ключей в HashMap. Как только ключ перестает быть нужен в системе, нам он тоже уже не нужен, так как по нему ничего не спросишь.

Мы поговорили про семантические требования (требования, накладываемые самим языком). Теперь поговорим о требованиях, связанных с внешним миром: как все-таки функционирует memory manager; что важно учитывать, когда создаем систему управления памятью, кроме требований самой системы понятий, которые мы реализуем.

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

Чему должна быть равна скорость сборки мусора? В стабильной системе она просто равна скорости аллокации. В системе, в которой нет memory leak'ов и которая достаточно долго работает, скорость сборки мусора -- это ровно скорость аллокации мусора: сколько мы новых объектов создаем, ровно столько их должно собираться. Поэтому на самом деле производительность сборщиков мусора -- это скорость тог, с какой скоростью можно выделять новый объект. Если мы не выделяем очень много объектов, то нам все рано на производительность GC.

Следующее требование -- ко времени жизни приложения. Есть программы на Java, которые выполняются месяцами или даже годами.

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

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

Ожидаемый тип аппаратного обеспечения: будет это сильно многопроцессорный сервер из 40 ядер и неоднородной архитектуры памяти, или это небольшое встроенное устройство, у которого 1-2 ядра и не очень много памяти. Тоже приходится по-разному создавать коллекторы. Именно необходимость интегрировать в себя достаточно противоречивые требования и привело к тому, что у многих виртуальных машин (не только у HotSpot) есть несколько разных memory manager'ов, которые работают по одному и тому же интерфейсу, но используют разные алгоритмы.

lecture2.md

Лекция 2. Алгоритмы сборки мусора

Два типа алгоритмов: одни считают мусором то, что точно является мусором (мусор принимают за немусор), другие -- консервативные.

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

Сама возможность приближенной оценки позволяет реализовать более простые алгоритмы сборки мусора. Например, классический Boehm GC, который иногда используется в программах на языке си, а также в некоторых рантаймах для виртуальной машины C#, там оценка того, является ли что-то мусором или нет, производится по очень глубокомысленной эвристике: весь heap находится где-то в адресном пространстве, от адреса A до адреса B, и VM так написана, что указатели в памяти выровнены на ширину указателя, поэтому можно достаточно легко проверить, есть ли на что-то ссылки, просто пробежав от A до B и ситая все указатели там. То, что мы увидели в процессе этого обхода -- это будут какие-то входящие ноды. Естественно, что это оценка, потому что вполне может быть, что у нас так получилось, что у нас есть какое-то большое целое число, которое случайно попало в этот диапазон. Но тем не менее, какую-то оценку графа достижимости мы можем получить в консервативном коллекторе.

В HotShot'е таких коллекторов нет. Все коллекторы HotSpot'а написаны так, что в нем точно производится вычисление того, какие объекты являются достижимыми, то есть, точно вычисляется и множество-дополнение.

Гипотеза поколений, копирующий коллектор

Все эти коллекторы -- это коллекторы с поколениями.

Существует такая штука, как гипотеза поколений. Люди достаточно рано начали писать ОО-системы программирования, и в частности, производилось статистическое исследование, грубо говоря, сколько объект живет. По объектам такая гистограмма выглядит как распределение Пуассона. То есть, бОльшая часть объектов умирает молодыми. Если объект родился, то с большйо вероятностью в ОО-системах он проживет недолго и умрет скоро. И наоборот, если объект прожил достаточно долго, то он с большой вероятностью проживет еще много.

Грубо говоря, эта гипотеза говорит о том, что эту гистограмму можно поделить на какое-то кол-во участков, в каждом из которых будет разная демография объектов: некоторые объекты живут совсем мало, некоторые побольше, некоторые живут долго, а некоторые вечны.

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

Если мы говорим про сборщики мусора в HotSpot, то практически все они с поколениями, но с некоторыми вариациями, кроме одного коллектора -- рантаймового. У всех остальных есть молодое поколение (young gen), есть старое поколение (old gen), есть еще перманентное поколение, куда аллоцируются служебные объекты VM, ибо у них совсем другая демография.

Зачем вообще использовать гипотезу поколений в дизайне memory managera? Плохо, когда есть объекты с разной демографией в одном и том же месте: одни объекты постоянно рождаются и умирают, а другие живут долго. Тогда понятно, что если мы хотим компактифицировать объекты, то нам придется постоянно перемещать долгоживущие объекты, и помещать их вокруг свежей освобожденной области.

Типичная стратегия для хотспотовских коллекторов -- это различные алгоритмы сборки в разных поколениях: из-за разной демографии разный мусор надо собирать по-разному. Типичная стратегия сборки в молодом поколении -- это т.н. копирующий коллектор, или коллектор с полупространствами. Это достаточно старая идея, появившаяся задолго до HotSpot'а и позволяет написать чрезвычайно простой memory manager, устроенный примерно так.

У нас есть какая-то доступная память, 100 Мб. Выделим ее на два региона по 50 Мб и назовем эти регионы полупространствами. Мы просто имеем скользящий указатель, указывающий на последний выделенный объект. Если нас попросят выделить объект какого-то размера, мы переместили этот указатель на заданное значение и вернули прежнее значение указателя тому, кому это надо.

Понятно, что когда-то место в первом полупространстве закончится, и мы не сможем обработать следующий запрос. Что мы можем сделать? Достаточно простую операцию: проведем анализ достижимости в полупространстве. Видим, что объект нам нужен -- переносим его во второе полупространство. В итоге в первом полупр-ве останется только мусор и его можно собрать, а второе полупр-во будет рабочим, продолжаем аллокации там.

Это не очень эффективно по использованию памяти, так как одна половина памяти всегда пустая и не используется по делу. Но зато это чрезвычайно простой коллектор, который хорошо работает с большим количеством мусора. Пусть мы выделили 100 объектов, из них выжило только 5 (типичная ситуация для молодого поколения). Мы перенесли только 5 объектов, а остальное объявили мусором, и сама сборка простая и легковесная.

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

Переходы между поколениями

В young gen, понятно, попадает все то, что мы аллоцировали с помощью new. Есть некоторые исключения, но в целом так. Как понять, что объект из young gen уже прожил достаточно долго? Легко: мы часто переносим такой объект между регионами. Пусть каждый перенос увеличивает внутренний счетчик (выделим под него 2-3 бита). Если счетчик достиг, например, значения 4, то этот объект признается долгоживущим, и при следующем переносе переносить его не в другое полупр-во, а в old gen.

Кроме того, есть еще один класс объектов, который сразу выделяется в old gen. Какие это объекты? Классы? Нет, они в permgen.

Чему равна стоимость переноса объектов в young gen? Его размеру. Если мы хотим не только переносить объект, а еще и реаллоцировать в нем ссылки (их тоже нужно переносить).

Поэтому есть две важные метрики: это кол-во объектных ссылок внутри объекта и физический размер объекта. Чаще всего коллекторы смотрят только на размер объекта: если его размер больше некоторого threshold'а (несколько килобайт по умолчанию), то он сразу же выделяется в old gen'е со следующими соображениями: такой объект долго переносить, и, скорее всего, если пользователь немножко подумал в своей программе (редко правда), то он не будет выделять слишком много больших маложивущих объектов (если объект большой, то, скорее всего, его lifecycle является большим).

Так что в old gen чаще всего помещаются массивы и коллекции.

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

Обычно есть нек-рая технология учета кросс-поколенческих ссылок. VM пытается работать следующим образом: на основании демографической информации (объекты живут разное кол-во времени) сборка в young gene -- достаточно частое событие (малая сборка), а сборка по всему хипу или только по old genу, или по всему хипу вместе (в разных коллекторах по-разному сделано) -- это событие достаточно редкое и достаточно тяжеловесное. Поэтому большинство реализаций коллекторов пытается тем или иным образом оптимизировать сборку в молодом поколении и по возможности оттянуть тот момент, когда придется собирать мусор в старом поколении. И это, в частности, влияет на анализ достижимости.

Еще одно свойство -- semi-space еще нередко тем или иным образом поделен на thread-локальные подобласти. Если есть несколько потоков, то каждый из них аллоцирует в каком-то своем регионе. Такая вот оптимизация, позволяющая не держать блокировку и не использовать атомики для выделения индивидуальных объектов.

Причина для этого любопытная, частично связанная с тем, что HotSpot не был разработан внутри Sun Microsystems, последние купили компанию Anamorphic, которая писала виртуальные машины для Smalltalk с полуакадемическими целями. Sun тогда был типа нынешнего Google или Facebook, она объявила тендер на создание VM, которая хорошо выполняется на их аппаратном обеспечении, а у них уже тогда были даже 128-процессорные архитектуры. Вот отсюда и заложилось понимание, что хорошо бы эффективно исполняться на сильно параллельном оборудовании.

Барьеры чтения-записи

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

Например, технология барьеров используется для минимизации обходимого графа. Как это достигается? Мы стараемся при малой сборке обходиться малым -- обходить объекты только из young genа, не заходить по возможности в old gen. Мы хотим не учитывать ссылки в старшее поколение.

Вот есть у нас объектный граф. В нем есть объекты, которые в young gen, а какие-то объекты уже попали в old gen. Вообще, все линейные куски памяти, доступной VM, поделены на две линейные части: первая для объектов из young gen, вторая для объектов из old gen.

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

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

Хотелось бы не учитывать ссылки из молодого поколения в старое, хотелось бы не заходить в старое поколение. Можно это просто так сделать? Нет, мы не может просто игнорировать ссылки из нового поколения в старое, потому что могут быть ссылки из старого поколения в новое.

В большинстве VM существует тот или мной механизм отслеживания межпоколенческих ссылок. Когда мы сохраняем ссылку из old в young, то можно, упрощенно говоря, рассмотреть объект из old gen как элемент root set'а. Это такие объекты, которые стали ссылаться на элементы нового поколения с последней сборки мусора. если мы их тем или иным образом запомним (в хотспоте это называется cardmarking), то получится оптимизировать анализ.

Например, можно создать bitmap размера, пропорционального размеру old gen, и те объекты, которые являются элементами root set, в этой битмапе пометить. И тогда, соответственно, при обходе мы просто можем посмотреть, на что объект ссылается, и тоже через него пройти. То есть, необязательно посещать все объекты из old gen, а только те, что помечены в битмапе. После сборки битмап обнуляется.

Соответственно, в хотспотовских коллекторах (почти во всех) используются барьеры записи: при сохранении межпоколенческой ссылки как-то запоминать объект, в котором хранится эта ссылка.

Когда еще нужно запоминать такого рода ссылку в системах с поколениями? Когда еще нужно добавлять элемент в эффективный root set? Ссылка из young в old может появиться двумя способами: это ссылка на уже существующий объект из old gen (рассмотрели только что), а также при промоушене объекта из young в old (все ссылки на этот объект становятся ссылками из young в old). В обоих сценариях нужно запоминать наличие ссылки между поколениями.

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

Остановка мира (Stop the World)

Это достаточно разрушительная для воспринимаемого пользователем экспериенса операция, но полезная для VM, без нее большинство реализации VM (в частности, хотспота), работать не может.

Что это такое? Сборщик мусора -- это некоторое вычисление над графом объектов. У этого графа есть любопытное свойство -- это не просто граф объектов, а еще и вечно меняющийся граф объектов (объекты постоянно создаются, удаляются, мы модифицируем поля этих объектов и т.д.) В Java очень либеральная модель того, как можно модифицировать поля объектов, граф объектов тоже может меняться совершенно непредсказуемым образом.

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

Простейший способ это сделать -- это нужно, чтобы все потоки, которые имеют какое-то отношение к JVM, остановились и ничего не делали (по крайней мере с объектным графом). При этом эта операция должна быть возобновляемое: после того, как memory manager и gc осуществили какие-то свои действия, мы хотим возобновить исполнение мира ровно с той позиции, где он замер.

Технология реализации этого действия во всем как в похожей системе в ОС: многозадачности. Есть две стратегии: примитивная и кооперативная многозадачность.

Одновременно на 2-ядерном компьютере могут исполняться два процесса. Если запустим ps, то увидим сотни процессов, у каждого из которых по сотне потоков. То есть, тех, кто хочет исполняться, гораздо больше, чем тех, кто может исполняться.

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

Кооперативная многозадачность (маки до OS X) -- наше приложение хорошо написано и само говорит, что оно не хочет выполняться, и само добровольно передает управление планировщику. Плохое приложение может выполняться сколько хочет.

Из-за того, что менеджеры рантайма обычно достаточно сложные, насильственная остановка мира, особенно для сильно оптимизированного кода, не очень хорошо работает. Допустим, мы вычисляем какое-то значение в нашем супероптимизированном джите, которое является указателем куда-то внутрь какого-то объекта. И тут нас прервали, gc решил переместить тот объект, который мы вычисляли, а у нас это где-то в каком-то регистре процессора это значение было. Мы возобновили исполнение, пытаетмся что-то прочитать по старому честно вычисленному адресу, а там ничего нет (или есть какой-то другой объект).

Поэтому в современных версиях хотспота используется кооперативная технология остановки мира, называющаяся safepoint: в определенных точках программы она готова, чтобы ее прервали. То есть, программа исполнялась, а потом осуществляет какую-то проверку, которая потенциально может привести к остановке.

Как можно вообще в программе проверять, что можно перестать исполняться? Самый простой способ: у нас есть глобальная переменная STOP, и в STOP -- call suspendMyThread. Вот самая простая логика safepointa.

Куда можно вставить safepoint?

• после каждого вызова функции
• на каждой обратной итерации цикла
• ...

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

Как этого можно добиться? Как добиться того, чтобы программа, в зависимости от состояния глобальной переменной, вела себя по-разному, но условных переходов в коде, который анализирует это состояние, не было?

В процессорах, кроме условных переходов (кроме нормального потока исполнения) есть исключительный поток исполнения (который происходит при некоторых исключительных ситуациях). Большинство оптимированных VM пользуется исключительным потоком: если у нас есть переменная STOP, то можно писать не

STOP = 1
...
if STOP:
    ...

а иначе. Какой машинный код порождается из кода выше?

mov ecx, [123] // 123 -- адрес переменной STOP
mov eax, [ecx]
...
jz DO_STOP // если значение eax = 0, то переходим на DO_STOP

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

Когда мы делаем mov eax, [ecx], то тут чтение ecx подразумевает проверку, а можно ли читать из этого адреса? Поэтому вместо того, чтобы что-то писать в адрес STOP, можно что-то писать в таблицу страниц, на которой находится эта самая переменная. Можно в таблице пометить, что данная страница недоступна на чтение, поэтому чтение ecx приведет нас к General Protection Fault (ошибка защиты страниц), она переведет нас в ядро ОС, можно установить обработчик на эту исключительную ситуацию и после этого спокойно продолжить выполняться дальше. То есть, проверка safepoint будет составлять 1-2 инструкции, а сложная логика будет в обработчике исключительных ситуаций. Это уже такой частый паттерн во многих системах, а именно, система под т.н. fast path, или common path: удешевляет обработку нормальных ситуаций засчет удорожания обработки исключительных состояний.

Представление объектных ссылок в коллекторе

В си или плюсах объектные ссылки представляются просто числом -- индексом в массиве виртуальной памяти ("по адресу 42 у меня хранится такое-то значение"). В принципе, у VM достаточно много свободы в том, как реализовывать объектные указатели.

Один из вариантов -- handlerы разного рода. HotSpot -- не первая VM для джавы, первая была написан внутри Sun, но она работала патологически медленно и не устраивала никого. В ней объектные ссылки представлялись примерно так: ссылка была индексом, но не в виртуальной памяти, а в таблице хендлов. На позиции 0 -- один указатель, на позиции 1 -- другой, ... . Даже в той VM люди понимали, что необходимо иметь возможность реализации сдвигающих коллекторов, но в такой системе с непрямой адресацией реализовывать перемещение указателей было достаточно просто. Если мы когда-то ссылались на объект №17, то все, что нам нужно сделать, когда мы переместили объект №17 -- это переписать ссылку, чтобы она указывала на другое место. Минусы: обновление таблицы (равно как и доступ) требует или блокировок, или атомарных операций.

Хотспот посчитал это решение неэффективным. Изначально хотспот использовал ordinary object pointer (oops) -- обычный указатель на объект, как в си, а при перемещении объекта в новое место сопровождалось переписываем значений во всех местах, которые ссылаются на данное место.

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

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

Возможны и другие техники адресации. Даже в Си есть режим компиляции в нек-рых компиляторах, при котором указатели представляются не просто целочисленным значением, а каким-то меньшим значением (особенно верно для 64-битных архитектур).

Если наш хип обладает свойством непрерывности (реально занимает какой-то кусок адресного пространства), то в 32-битной архитектуре хип может занимать все адресное пространство. В 64-битной архитектуре таких огромных хипов не бывает. Поэтому можно воспользоваться сжатыми указателями, воспользовавшись двумя знаниями:

• хип находится в нек-ром интервале адресного пр-ва, начиная от базы и до куда-то
• новые объекты аллоцированны выровненным образом: в большинстве ВМ и аллокаторов значения, которые возвращает ф-я malloc, делятся или на 8, или на 16. То же верно и про объектные ссылки: обычно объекты размещают так, чтобы их положение в памяти было каким-то образом выровнено, для того, в частности, чтобы операция чтения полей была более эффективной. Например, в x86 операция mov eax, [ecx] может исполняться за разное кол-во тактов в зав-ти от того, что записано в ecx: если записано выровненное значение, то тактов меньше, а если невыровненное, то больше.

Так вот, значения даже в 64-битных системах можно нередко кодировать 32-битными значениями: (ptr - A) >> align. При выравнивании 3 можно добиться адресации в 32-Гб хипе 32-битным значением.

Сериальный коллектор, mark-sweep

Самый исторически первый и простой коллектор -- сериальный коллектор, достаточно простой и надежный и рассчитанный на относительно небольшие хипы (~2 Гб).

Он делится по отношению 1:2. На young gen выделяется одна треть доступной памяти. Это поколение устроено следующий образом: есть Эдем -- место, где происходят все аллокации, и два полупр-ра (что это, обсуждали выше). Эдем -- это то, где объекты появляются на свет.

Как только Эдем заполняется, по нему происходит сборка, и, соответственно, дальше он попадает в одно из полупр-в, а оттуда по мере продолжения жизни -- в старое поколение.

Этот коллектор останавливает мир по любой оказии; любая сборка является останавливающей, один поток осуществляет сборку мусора, после чего исполнение продолжается.

В старом поколении работает не коллектор на полупр-вах, а достаточно классический алгоритм mark-sweep-compact (назван по трем фазам работы коллектора)

• mark -- обходим граф, объекты помечаем цветом. Обходим из root set.

• compact -- объекты как-то упорядочены в хипе; некоторые из них помечены (т.е. посещены), а некоторые не помечены. Не помеченные суть мусор. Про каждый объект из его заголовка можно вычислить его размер (и перейти к следующему).

  Обходим в порядке расположения в хипе (значем начало хипа, значем размер каждого объекта, ибо у каждого есть типизационная информация).

  Переносим помеченные объекты на места непомеченных, которые аллоцированы раньше в хипе. В итоге префикс хипа -- это непрерывно записанные нужные объекты, а за ними -- неаллоцированное пространство.

Некоторая форма компактификации очень популярна в коллекторах, так как не оставляет бесполезных мест: все нужные объекты хранятся строго друг за другом, без промежутков.

Теперь представим достаточно хорошо заполненный old gen, в котором второй объект на 16 байт оказался ненужным, а за ним идет 40 тысяч нужных объектов. Получается, что все 40000 объектов будут смещены на 16 байт. Это плохо.

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

Трассировка vs подсчет ссылок

Трассирофка -- обход графа (как выше).

Подсчет ссылок -- про каждый объект известно кол-во входящих ссылок.

Трассировка -- всегда глобальная операция (не считая оптимизаций типа кардмаркинга): нужно обойти более-менее весь граф, чтобы обнаружить мусор.

Подсчет ссылок -- довольно локальная операция. Плюс: видим объект с нулевым счетчиком -- это мусор, все просто. Минус: объекты образуют изолированный цикл, у каждого ненулевой счетчик, но из root set они недостижимы -- сложно обнаруживаемая проблема. Но разрешимая.

В Kotlin Native система автоматического управления памятью основана на подсчете ссылок. Можно эмулировать трассирующий коллектор на подграфе: увидев, что какая-то входящая ссылка на вершину подграфа уменьшается с X на X-1, то можно записать эту ноду в кандидаты на запуск нек-рого алгоритма, похожего на алгоритм сборки мусора.

Этот алгоритм из какого-то набора кандидатов делает на локальном графе следующую операцию: при наличии ссылки из ноды A в ноду B он а) переходит из A в B; б) уменьшает счетчик в B на 1, и обходит следующие ноды.

По достижении того факта, что мы выяснили, что обошли весь граф, произойдет следующее: те эл-ты графа, на кот. счетчик ссылок равен 0, это на самом деле те эл-ты, которые доступны только изнутри этого графа. То есть, мы получили следующий инвариант: счетчик каждой ноды графа равен количеству внешних ссылок на эту ноду.

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

Этот алгоритм запускается из потока, как только он обнаружил, что счетчик ссылок уменьшился у >= N объектов (кандидатов мы храним где-то в логическом сете). Для разделяемых м/у потоками объектов осуществляется конденсация графа, чтобы из него сделать DAG. В DAG при подсчете ссылок невозможна проблема, описанная выше, т.к. в нем нет циклов.

Цель такого алгоритма -- избавиться от блокировки всего графа, чтобы конкурентные примитивы исполнялись более-менее независимо друг от друга.

HotSpot же не использует подсчет ссылок, только трассировку.

Параллельный коллектор

Ориентирован на оборудовние, в котором повыше конкурентность (многопроцессорные железки) и на высокую произв-ть работы сборщика (на высокую скорость аллокации объектов).

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

compact параллелить сложно, поэтому он не распараллелен. Выделение -- в индивидуальных буферах. Эдем разделен по числу потоков до какого-то разумного предела.

Параллельный коллектор -- самый производительный из коллекторов HotSpot. Его написали относительно быстро и при этом он до сих пор непревзойден в производительности, но плох по другим метрикам.

Каким? Процессора он разумно жрет. Памяти жрет тоже немного. У параллельного коллектора остановки мира длинные. Их продолжительность пропорциональна количеству объектов, с которыми работает программа. Так как параллельный коллектор работает на больших хипах (10 Гб и более), то и паузы соответствующие. Даже теоретически, у современных процессоров Гб 30-40 -- операция чтения из памяти. А если нужно еще и вычисления сделать, то все еще хуже.

Любой глобальный анализ и глобальное вычисление создает воспринимаемую паузу, а это -- причина большого кол-ва бед для Java-программы.

Есть такой целый бизнес -- HFT (High Frequency Trading). Это технология, кот. позволяет, просто видя какой-то биржевой тренд, не производя глубокомысленных анализов, просто сесть на биржевой тренд, то благодаря тому, что у остальных участников торгов больше инерция, можно добиться зарабатывания большого кол-ва денег засчет большого кол-ва транзакций.

Если говорить про программную часть реализации вот этого (значительная часть торгового софта пишется на Java), то достаточно быстро становится понятно, что gc-пауза -- классический способ потерять деньги, потому что частота -- миллисекунды, и даже пауза в 100 миллисекунд расстраиввает алгоритмы HFT.

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

Конкурентный коллектор

CMS (Concurrent mark-sweep) -- сборщик, написанный, когда страдания людей по поводу использования Java в десктопных приложениях достигло непереносимой Sunом точки. Этот тот сборщик, кот. по умолчанию используется в тех десктопных программах, кот. написаны на Java: в IDEA, в Eclipse используется именно этот коллектор. Его воспринимаемые паузы ниже, чем у других алгоритмов, хотя у них производительность больше.

Работает только в старом поколении (в молодом поколении все равно та же самая картинка с Эдемом и сурвайворами). Этот коллектор не публифицирующий: самая длинная пауза -- это фаза компактификации, ибо при ней делать нельзя примерно ничего, т.к. объекты могут неожиданно перед тобой переползти; + копирование больших объемов данных -- его нельзя сделать быстрее, чем то, на что способно аппаратное обеспечение машины.

Поэтому в CMS не присутствует компактификация, но там реализован алгоритм free-listов, только для памяти. В большинстве memory manager'ов используются free-listы.

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

Free list-ы также разные для разных диапазонов размеров объектов, чтобы запросы для маленьких объектов не загрязняли free list-ы с большими объектами. Это позволяет немного уменьшить дефрагментацию.

Еще этот коллектор, в отличие от предыдущих коллекторов (сериального и параллельного), работает все время и параллельно с работой программы. Менее эффективное использование процессора, но выигрываем в длине паузы.

Коллектор с гарантиями реального времени

В Java есть JSR -- механизм расширения Java. JSR №1 -- самый первый запрос на расширение Java. Часть нереалтаймовости Java находится в ее модели управления памятью. Поэтому, для того чтобы реализовать realtime-овое расширение, понадобилось реализовывать отдельный сборщик. Но реализовать гарантии жесткого реалтайма и сравнимые характеристики производительности не получилось.

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

Этот коллектор выполняет паузу только на время маркировки стека текущего потока, он старается не выполнять глобальных блокирующих операций.

Этого коллектора нет в HotSpot и вообще сейчас он вроде как никем не поддерживается. Тем не менее, этот пример показывает, что можно написать совсем неожиданные коллекторы.

Garbage-first коллектор

У него есть много интересных свойств, в которые он агрегирует возможности того, о чем мы говорили до этого.

Это конкурентный параллельный копирующий коллектор, который еще и soft-realtime гарантии предоставляет.

Как этого достигнуть? Очень интересной техникой. У всех коллекторов, о котором мы говорили подлежащее хранилище (память, поверх которой выделяются объекты) -- это большой непрерывный участок от A до B размером, указываемым в параметре -Xmx. Этот хип поделен на две части: под old gen и под young gen.

GF сделан совершенно по-другому. Он делит хип до 2048 различных регионов предсказуемого размера: от 1 до 32 Мб. Каждый из этих кусочков имеет функцию: он служит либо для того, чтобы быть частью условно старого поколения, либо частью условно нового поколения, еще при аллокации больших объектов небольшие регионы могут быть склеены в мегарегион (если понадобилось выделить настолько большой объект).

Про каждый объект при помощи тех же самых барьеров записи примерно известны все внешние ссылки на данный регион. Мы можем знать, откуда на нас хранятся внешние ссылки для данного маленького подрегиона. Ключевая функ-ть GF состоит в том, что кроме фазы начальной маркировки стеков, с которой ничего особо не поделать, почти все остальные операции осуществляются с гранулярностью вот такого региона: мы всегда можем знать, что компактификация осуществляется только в одном регионе, или реаллокация ссылок осуществляется только в одном регионе, или в небольшом кол-ве регионов (если речь про внешние ссылки в данный регион).

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

Это достигается с использованием барьеров записи.

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

Этот коллектор очень долго делался: туда по максимуму внедряли lock-free алгоритмы и все такое.

Azul g4 (???)

lecture3.md

Лекция 3. JIT

(начало отсутствует)

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

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

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

Интерпретатор должен декодировать каждую инструкцию, т.е. нам нужно понять, что инструкция делает, прежде чем начать ее исполнять. Это содержательная операция, нужен некий branch predictor.

Мало того, нам нужно после исполнения каждой инструкции снова перейти на instruction decoder, нам нужно понять, какую инструкцию исполнять следующей. Понятно, что в конце концов внутри процессоров существует логически ровно такой же цикл интерпретации, просто он аппаратно ускорен, поэтому тут мы во многом делегируем performance hits написания интерпретатора процессору, где тысяча людей занимается оптимизацией.

Мало того, при такой организации кода, понятно, что можно пойти немножко дальше, проявить нек-рую креативност. Например, видя специфику ВМ, например стековой, мы можем понять, что верхнее значение в стеке используется значительно чаще других; то, что сейчас находится наверзу стека, скорее всего будет являться аргументом следующих инструкций. Поэтому мы можем, например, первые 2-3 значения стека закешировать в нек-рых регистрах, значит, операции будут значительно проще, так как не будут вести к каким-то модификациям в памяти, а только к модификациям значений в регистрах.

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

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

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

Чем лучше компилятор понимает программу, тем больше он способен оптимизировать.

Типичный пример хорошей оптимизации тем же gcc, это то, что для нек-рых классов вычислений компилятор может просто провести все вычисления во время компиляции, если можно доказать, что у них нет сайд-эффектов, и вместо достаточно сложного кода, который что-то делает, можно просто напрямую вернуть из функции рез-т этого вычисления, если он известен.

По мере углубления в понимание значительная часть работы программы м/б перенесена из фазы исполнения в фазу компиляции. Это в нек-ром смысле дополняющая парадигма по отношению к тому, что делают JITы в динамических рантаймах. Динамические рантаймы пытаются перенести кодогенерацию и сопутствующие вычисления максимально поздно, а сам по себе компилятор пытается сам по себе выполнить максимально много разных оптимизаций (максимлаьно много вычислений, написанных в программе).

Пример простой оптимизации:

iload 0
iload 1
iadd

абсолютно в любом случае можно схлопнуть в

iload 1

Что делают JITы для своих оптимизаций?

• Во-первых, они используют значительную часть оптимизаций из AoT-компиляторах, + оптимизации, которые лучше работают именно в джитах. Пример такой оптимизации -- инлайнер (при вызове нек-рой функции подставляет вместо вызова тело вызываемого, если оно не очень велико -- лучше локальность по кешам, отсутствие необходимости работы branch predictorа, и много других плюшек)

  Инлайнинг позволяет делать и другие оптимизации: код специализируется на call-site и можно делать оптимизации, завязанные на call-site, а не связанные с сингатурой операции.

• Важный аспект оптимизации -- оптимизация исключительных ситуаций. Плюс джавы: в ней обработка всех мыслимых ситуаций, которые могут возникнуть, полностью специфицирована (в си разыменование нулевого указателя -- это UB (ситуация, не определенная в стандарте), а в джаве -- NPE). Засчет того, что джава исполняется в рантайме, этого можно добиться на широком спектре разного рода аппаратного обеспечения (нейтивы -- исключение, на границе с внешним миром может произойти много всего непредсказуемого).

  Джит предполагает, что NPE -- нечастая ситуация, но ее надо обрабатывать корректно -- типичный потенциал для оптимизаций. Как это сделано -- чуть позднее.

• В рантайме с явно описанной моделью конкурентности (как в JVM) важной часть рантайма являются всякие блокировки, корректная оптимизация блокировок -- тоже нечто ложащееся на плечи джита.

• Общая стратегия JIT-компилятора -- это строить хорошо исполняющийся код на данных, типичных для программы. Цель профилятора -- выяснить, какие данные являются типичными, а цель джита -- построить соответствующий машинный код.

Деоптимизация и реоптимизация

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

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

Нужно уметь правильно сконструировать новое состояния конкретной реализации абстрактной машины и продолжить исполнение.

Исходя из всех этих рассуждений, получается, что джиту приходится взаимодействовать в JVM примерно со всем: с системой управления памятью (чтобы уметь восстанавливать состояние при деоптимизациях), с интерпретатором (чтобы передавать ему управление в случае необх-ти), с менеджером блокировок (чтобы их оптимизировать), нужно знать, как ловятся и обрабатываются исключения (чтобы их оптимизировать), и так далее...

В хотспоте два разных джита, которые используют стандартизированный интерфейс для разных компонентов. Выкинуть джит можно. В хотспоте три системы исполнения: только интерпретатор, интерпретатор + не сильно оптимизирующий джит, интерпретатор + сильно оптимизирующий джит.

Два динамических компилятора в хотспоте (клиентский и серверный)

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

В IBM-ном компиляторе сделано более логично: там один динамический компилятор с несколькими уровнями оптимизаций (-O0, -O1, -O2, -O3, -O4). Какой мы передали уровень оптимизации, включаются дополнительные анализирующие и оптимизирующие проходы.

Когда-то была попытка создать многоуровневый компилятор, который соединяет клиентский и серверный компилятор в одну систему, которая, в зависимости от информации от профилировщика, использует тот или иной компилятор.

Рассмотрим сначала C1 (клиентский), он попроще, а потом C2. Структурно они оба Just-in-Time, входом является байткод, выходом -- одно или несколько IR, которые затем транслируются в машинный код. IR -- тот формат, в котором компилятор хранит информацию о программе. Практически любой компилятор с высокоуровневого языка, компиляция в нем проходит через несколько этапов IR, каждый из которых позволяет смотреть на программу тем или иным образом.

Например, что у котлина:

• .kt
• (apply lexer) --> token stream
• (apply parser) --> AST
• PSI == AST (детали тяжелого наследия)
• (kotlin compiler) IR (высокоуровневое, но подходит для понижающих трансформаций и нек-рых оптимизаций)
• VMIR
• машинный код

token stream, AST, PSI -- все это тоже IR.

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

Это AoT. Если мы говорим про JIT, то у него есть уникальная интересная возможность полагаться на интерпретатор для сложных случаев: в сложном случае сказать "я не знаю" и вместо кода породить fallback в интерпретатор. Если у нас есть оригинальное представление программы в виде байткода, и какую-то инструкцию выполнить трудно (или невозможно, не завезли в JIT), то можно просто породить переход на интерпретатор со информацией, где находится стек, и что нужно выполнить инструкцию вот тут / инструкции вот отсюда.

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

Кроме этого, интерпретатор используется для начального исполнения и сбора статистики: чтобы профилятор мог работать, ему нужно откуда-то брать вход. Он берется из статистики, набранной при интерпретированном исполнении.

Плюс интерпретатор используется при деоптимизации.

Интерпретатор тоже может вызывать код, сгенерированный компилятором, или сам компилятор, в зависимости от необходимости. Интерпретатор или профилятор вдруг выяснил, что данный вход достаточно горячий, его надо оптимизировать. Типичный подход -- прееключить точку входа в метод на точку входа в компилятор, т.е. исполнение метода состоит из того, что он сначала компилируется, а потом исполняется.

C1

Какие дизайнерские цели были у клиентского компилятора? Серверный компилятор -- это достаточно сложный оптимизирующий компилятор, который долго не мог начать нормально работать. Поэтому основная цель клиентского компилятора была создать систему, кот. может предоставить нормальную работающую реализацию JVM JITа. От нее требовалось, чтобы JIT работал достаточно быстро (когда его создавали, достаточно сильно верили в джаву на десктопе, на клиенте -- отсюда и название; джит -- такой же источник потенциальных проблем с откликом, как и GC).

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

В целом, профилировочная информация достаточно простая, это сугубо... (тут пришло внешнее прерывание)

...

(продолжение исполнения)

В качестве промежуточного представления там используется CFG.

SSA -- Single Static Assignment.

Любой IR оперирует на нек-ром наборе виртуальных хранилищ.

LLVM -- это достаточно любопытный, изначально академический проект. Изначально это была попытка создать низкоуровневую абстрактную виртуальную машину (отсюда название) и заодно набор инструментов для компиляции в нее.

С виртуальной машиной как-то не задалось, а вот IR, описывающее скомпилированные программы, и компилятор с языков C/C++ получились достаточно хорошо. В компиляторной индустрии это наиболее адекватный инструмент для написания новых компиляторов (в Native тоже используется LLVM как одно из IR нижнего уровня).

В сердце LLVM (как в кач-ве языка, на котором формулируется преобразование) лежит биткод. (Если байткод выровнен по ширине восьми бит, то в LLVM из сообщражений какой-то эффективности битовые потоки, и ширина инструкции м/б не пропорциональна байту).

Что собой представляет биткод? Это достаточно простой язык, по форме напоминающий ассемблер, но с нек-рым набором очень интересных существенных отличий, как раз сделавших его очень хорошим низкоуровневым IRом.

Какие отличия? Во-первых, это типизированность. Ассемблер нетипизирован, mov rax, rcx -- непонятно, какого типа значения передаем: это целое 64-битное число, байты картинки или что-то еще; мы просто перемещаем 64 бита из одного места на кремнии в лругое.

В LLVM существуют типы i1, i8, i16, ..., i128, f32, f64 и другие. Кроме этого, существует тип адреса, указывающий на значение определенного типа.

У всех операций существует набор того, где рез-ты этих операций хранятся. Например, если мы хотим на LLVM-подобном языке скомпилировать Сишную функцию

int add(int x1, int x2) {
  return x1 + x2;
}

то машинный код будет примерно такой:

add rdi, rsi
mov rax, rdi
ret

а биткод такой:

%2 = add i32 %1, %0
ret i32 %2

Какие отличия от ассемблера? Основное отличие состоит в том, что при вычислении, если мы создаем какое-то новое значение, которого у нас раньше не было, то мы всегда создаем под него новый виртуальный регистр. Это значит, что у нас два числа, которые были аргументами, оказались в вирт. регистрах 0 и 1, а в вирт. регистр 2 мы записали значение операции add. В ассемблере же реальные регистры модифицируются. В биткоде значения не меняются. Новая операция привела бы к присвоению к новому виртуальному регистру. Это и есть SSA -- в виртуальный регистр мы присваиваем значение ровно один раз. Это позволяет переиспользовать значения и быть уверенными, что то, что сейчас видим в вирт. регистрах -- это ровно то же самое, что было там и раньше.

А как быть с ветвлениями? В зависимости от условия, глобальной переменной присваиваются разные значения. В разных ветках получаем по новому виртуальному регистру.

x = 1      // v1
if (y < 0)
  x = 2;   // v2
else
  x = 3;   // v3
... (что будет здесь, v2 или v3?)

Нужно как-то объединить результаты. SSA довольно прост, когда доминаторы однозначно определены. А если нет, то существует хитрая штука под названием фи-функция. Это функция от SSA. После ветвления пишется

x = \phi(v1, v2)

В зависимости от того, по какому ветвлению мы сюда пришли, в x попадет либо значение из v1, либо значение из v2. То же самое для циклов.

Количество аргументов фи-функции равно количеству ребер, которые входят в текущую ноду в CFG.

Типичная трансформация, используемая после SSA -- это назначение вирт. регистрам реальных регистров (т.н. регистровая аллокация). Мы можем написать сколько угодно виртуальных регистров, но их все надо как-то отобразить на реальные.

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

Это вынуждает использовать те или иные эвристики для решения задачи, например, в клиентском оптимизаторе используется субоптимальный алгоритм с линейной сложностью, называемый linear scan. Он проходится по CFG и назначает регистр, на который наименьшее (наоборот?) давление.

Local value numbering

Благодаря SSA-форме достаточно легко использовать оптимизацию local value numbering -- когда мы видим одно и то же вычисление, происходищее дважды, т.е. видим в разных участках кода что-то типа

v3 = v1 + v2
...
v101 = v1 + v2

то можно не делать последнее присваивание, а вместо v101 далее использовать v3. Оптимизация часто возникает после других оптимизаций (руками такое редко пишется).

Constant propagation

Если где-то раньше написано v1 = 2, а v2 = 3, то инструкция v3 = v1 + v2 означает, что v3 = 5.

Прелесть SSA формы в том, что она алекватно описывает граф зависимостей по данным. Мы видим поток данных: как наши данные трансформируются через SSA-значения. Поэтому можно протаскивать константы -- подставлять вместо левых частей правые.

Inliner

Он смотрит на размер байткода метода, который инлайнер пытается заинлайнить. Например, геттер может быть заинлайнен, но если кто-то добавит в него логгер, то все может сломаться.

Формы удаления null checkов

DCE (dead code elimination)

Система, позволяющая удалять недостижимый код, и не использовать его в кодогенерации. Обычно для IRов в виде CFG это некоторое не очень тривиальное вычисление.

Как по CFG вычислить, какие участки недостижимы? Очень сложно: нужно смотреть на значения в условиях, в какие ветки мы зайдем, а в какие нет, и многое другое.

Вот как важно подходящее промежуточное представление для тех или иных оптимизаций. Для CFG, который есть IR в клиентском оптимизаторе, данная оптимизация достигается тяжело, а с помощью IR серверного оптимизатора эта оптимизация получается почти автоматически.

C2

Более сложный оптимизирующий компилятор. Дизайнерская цель -- высокая производительность скомпилированного кода. В нем реализованы примерно те же оптимизации, что реализованы в оптимизированнос сишном компиляторе + JIT-специфичные оптимизации.

Стратегия кодогенерации в серверном компиляторе оч сильно базируется на понятии common path или fast path: вычислении того, какой путь является более популярным.

Мы динамически идентифицируем те куски кода, которые часто появляются в профиле. Мы можем таким образом объединить в инлайнере в единый кусок кода только часто используемые части релевантных функций; мы можем при компиляции и при кодогенерации реально компилировать и оптимизировать только fast path.

У серверного компилятора очень интересное IR. Оно называется Sea of Notes, или Море Нот. Представление связано с потоком данных. В нек-ром смысле это dead flow graph.

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

На таких идеях и основан серверный компилятор. Само IR строится относительно сайд-эффектов.

Какие сайд-эффекты есть в джаве? Это запись в хип (запись в какие-то разделяемые объекты), возвращение значений из функций, находящихся за скоупом оптимизации, ...

Все вычисления -- на графе зависимостей по данным. Мы вычисления представляем в SSA-форме, но мы больше никак не атрибутируем конкретную SSA-переменную конкретному базовому блоку.

Из-за того, что у нас прописаны все явные зависимости по данным, мы можем ноды свободно перетаскивать между разными базовыми блоками.

При этом в хотспорте в серверном компиляторе присутствует несколько IRов, Sea of Notes -- оптимизационный IR, а еще есть low-level IR -- IR, которое используется для регистрового аллокатора и выбора конкретных инструкций под целевую машину. Глядя на устр-во целевой машины, зная, что та или иная инструкция имеет тот или иной вес для кодогенератора, мы можем аккуратно выбрать наиболее адекватно описывающую требуемую семантику инструкцию (instruction selection).

Регистровый аллокатор реализует один из самых эффективных известных человеку неэкспоненциальных алгоритмов раскраски графа -- алгоритм Чайтина -- но он все равно кубичен по кол-ву вирт. переменных, в общем, не очень быстрый. Поэтому в реальных хотспотовских коспиляциях регистровая аллокация часто занимает достаточно много времени (в частности потому, что SSA-значения нелокальны для базового блока, их много).

Какие оптимизации и техники используются для того, чтобы серверный компилятор нормально работал?

Стратегия компиляции

Вызов любой ф-ии в хотспоте происходит так. Есть метод, у него есть точка входа *(entry)(). Если мы хотим вызвать метод, то просто говорим method.enter().

Как достигается механизм выбора того, как исполнять тот или иной метод? Если хотим исполнять интерпретатором, то ставим в entry точку входа интерпретатора, а если хотим, чтобы метод транслировался тем или иным джитом, то мы ставим туда точку входа в джит; а джит, когда докомпилирует метод, может поставить туда реальный указатель на уже скомпилированный код.

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

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

Global Value Numbering

Благодаря отсутствию привязки SSA-переменных к базовому блоку здесь присутствует аналог Local Value Numbering, только он глобальный. То есть, мы можем выяснять, что переменная была где-то вычислена, не только в рамках одного блока, а в рамках всей программы.

Constant folding (propagation)

Если что, константа -- это не final переменная.

Разворачивание циклов

Вот тут сильно используется знание джита о том, на каком компьютере он исполняется.

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

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

Вынос инвариантов цикла (хостинг)

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

(Почему столько внимания уделяется циклам? Потому что в основном на них и уходит бОльшая часть времени)

Алгебраические операции

Если a + b -- это то же самое, что и b + a, то ситуация v3 = v1 + v2; ...; v101 = v2 + v1 приводит к оптимизации GVN.

То же самое про сложение с нулем, умножением на 0, 1, вычитанием нуля и т.д. Хотспоту это все известно.

Удаление проверок на null

Оно базируется на рантайм-механизмах. Эти проверки реально удаляются.

Как это делается?

Если мы хотим получить поле объекта по сдвигу 40, то, если объект в rcx, то хотспот делает ровно mov rax, [rcx + 40]. Хотя объект может быть null.

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

Из этого следует тот факт, что джит должен сохранять в соответствии со скомпилированной программой, какая точка чему соответствует, чтобы делать стектрейс. Он сохраняет bci (bytecode index, индекс байткода внутри функции), а формат .class-файла имеет трансляцию bci в исходный код.

Dead code elimination

RuntimeException-ы затрудняют создание виртуальных машин. Если у нас есть функция

int foo() {
    A a = new A();
    // сложные вычисления без сайд-эффектов
    int b = a.p.x + a.p.y;
    return 42;
}

то мы не можем взять и оставить в теле только return 42, так как a.p.x (или a.p.y) может потенциально выбросить NPE.

Escape-анализ

С его помощью можно оптимизировать обращение с объектом. Если мы точно знаем, что создали объект, и обращаемся к его полю/методу, то мы не получаем NPE.

Он же помогает оптимизировать блокировки. Если можно доказать, что объект никогда не покидает области видимости нек-рого скоупа (т.е. никогда не опубликован для других потоков), то можно удалить блокировку (так как доказуемо она не имеет сайд-эффектов).

Векторизация

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

Продвинутый инлайнер

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

Удаление проверок на массиве

Если что-то обрабатывается в цикле, то часто это работа над массивом.

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

Дематериализация

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

Другое

Кодогенератор в серверном компиляторе достаточно умный, он основан на выборе тех инструкций, которые максимально подходят для описания данной семантики. Из-за того, что после кучи оптимизаций выбор инструкции происходит, грубо говоря, применением чего-то типа регулярных выражений на полученном низкоуровневом IR, и описание, какой регексп самый жадный и при этом самый дешевый -- тоже алгоритмическое усилие.

Как у любого уважающего себя компилятора, тут есть планировщик инструкций. Он занимается максимальным разнесением вычисления выражения от его использования. В программе add rcx, rdx; mov [rax], rcx инструкции зависимы по данным: вторая зависит от первой.

Дизайнеры процессоров думают о pipeline stoles -- ситуации, когда конвейеру нечего делать. Это происходит, когда мы приносим инструкцию, а выполнить ее нельзя, потому что она зависит от прерыдущей инструкции, которая еще не выполнилась.

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

Во многих компиляторах на финальной фазе происходит perfcall-оптимизация: видим IR, удаляем/соединяем те инструкции, которые не имеют смысла либо могут быть выражены более коротко. Например, когда две инструкции подряд пишут в один и тот же регистр значение, то первую инструкцию можно удалить. Такие ситуации возможны после применения других оптимизаций, там часто даже глазами можно пробежаться и увидеть плохие участки.

lecture4.md

Лекция 4. JIT (продолжение), верификация байткода

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

Еще существуют оптимизации, для которых нужно знать иерархию классов.

Например, можно не смотреть в таблицу виртуальных функций, а сразу подставлять ссылку на функцию в место, где она вызывается. Это возможно, когда класс final или не имеет наследников.

Это достаточно нередко важная операция. Например, хранение в хеш-таблице, что часто достаточно чувствительная к производительности операция, она требует вызова двух виртуальных методов: equals и hashCode. Часто используют свои кастомные реализации этих методов, а иерархия классов большая, и поиск нужного виртуального метода получается долгий. Знание того, что класс не имеет наследников, помогает увеличить производительность.

Почему в джаве вызов метода интерфейса дороже, чем метода (пусть даже абстрактного) класса?

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

С интерфейсами все иначе. Один класс может реализовывать несколько интерфейсов. Если класс A реализует интерфейсы I1, I2, I3, а у каждого интерфейса есть свой набор методов, и из класса можно вызвать любой метод этих интерфейсов. Задача рантайма -- есть список всех мыслимых методов данного класса, и нужно найти, где из всех этих методов находится, например, третий метод, реализующий интерфейс I*.

Такую задачу индексацией в массиве и косвенным переходом не решить.

В С++ нет отдельной сущности интерфейсов, но возможно множественное наследование классов. Как это там сделано? ...

Итак, джиту еще нужно знать иерархию классов.

Есть еще несколько JIT-специфичных оптимизаций.

Одна из них связана с боксингом.

Зачем нужен боксинг? В Smalltalk есть свойство: у любого объекта есть identity -- место в памяти, в котором находится данный объект.

Боксинг -- это техника затыкания оптимизационных дыр. В Java для производительности есть отдельная небольшая иерархия из примитивных типов, которые обрабатываются отдельно.

Однако в HashMap том же нельзя хранить примитивные типы, так как они не удовлетворяют объектному проткоолу, который ожидается.

Если в Java мы напишем

hashMap.put(2, "Two")

то из 2 получится объект java.lang.Integer, инстанс котрого будет передан в код обработки хемапы. Это достаточно неудобно, поэтому джит старается оптимизировать такие случаи, потому что скорее всего на той стороне при генерации оптимизированного кода где-то эта коробка будет развернута, и лучше будет это пару (?) удалить.

Оптимизация блокировок

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

Во-первых, в хотспоте просто реализован такой набор блокировок на атомарных операциях без использования платформенных примитивов.

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

Как выглядит реализация mutex_lock? Это CAS: while (cas(&lock, thread_id) != 0) { ... }

mutex_unlock: cas(&lock, 0)

На сильно синхронизированных процессорах CAS дорогостоящий (синхронизация кешей).

Поэтому в хотспоте придумали такую технику: взятие лока для определенных состояний -- это больше не атомарная операция, а вот такая: *lock = 1. Просто пишем в lock информацию о том, что он взят. А иногда мы вообще ничего не пишем.

Как это работает? Для того, чтобы это работало, нужно предпринять еще некоторые действия. Это biased лок: на одном потоке он работает так, но у остальных потоков блокировка усложняется даже в сравнении с CAS.

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

Это и использует техника biased lock. Когда другой поток хочет взять чужой предвзятый лок, он при помощи mprotect модифицирует доступ к тому месту, где этот предвзятый лок находится. В рез-те попытка взятия лока *lock = 1 не удается.

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

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

Уровни оптимизации

У классических AoT компиляторов есть переключатели, контролирующие уровень оптимизации: -O0 -- наивный кодогенератор без оптимизации, -O1 включает какие-то оптимизации, -O2 накидывает еще, и так далее.

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

Но в итоге оба джита используются по мене необходимости: для начального бутстрапа и не сильно оптимизированного кода используются интерпретатор + клиентский компилятор, а для горячих точек найденных используется серверный компилятор. Это называется tied compilation.

На этом про JIT все :(

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

Верификация байткода

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

Программы на си могут нарушать примерно все инварианты. Программы на си++ тоже могут создавать кучу проблемного кода.

В джаве постарались создать высокоуровневый язык и низкоуровневый язык (байткод), и тот и другой языки достаточно хорошо специфицированы, и хорошо специфицировано их корректное поведение.

Что это значит в части байткода? Это значит, что про любую программу на байткоде, перед ее исполнением ВМ, на ней запускается автоматически theorem prover, который проверяет нек-рый набор инвариантов, доказывает некоторые теоремы про программу.

Какие теоремы доказываются? Что можно было бы про байткод рассказать?

Один из инвариантов, который вычисляется верификатором, связан с сбалансированностью объектного стека, с тем, что со стека не читается больше, чем пишется, а максимальная глубина стека соответствует заявленной в спецификации метрике.

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

В кач-ве простого примера:

iload 0
iload 1
iadd

Пусть в начале стек был пустой. После первой операции на стеке будет 0, после второй -- 1 и 0, после третьей -- только результат сложения, 1.

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

Понятно, что это простой случай. А если случай более сложный? Допустим:

anew <String>
invoke <Integer.hashCode>

Инстанцировали нек-рый объект класса String и попытались на нем вызвать метод класса java.lang.Integer.

Понятно, что этот байткод некорректен, так как согласно сигнатуре ресивер типа Integer, а мы передали строку -- несовместимые типы.

Возможность верифицировать произвольную программу даже для несложной стековой машины Java -- это вообще-то NP-полная задача.

К счастью, практически важные программы можно верифицировать достаточно эффективным образом.

Верифицируемые программы <: корректные программы <: всевозможные программы

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

Верификатор запускается каждый раз, когда мы в какой-нибудь джаве загружаем класс. А если класс некорректно сформирован, то пользователь увидит исключение VerifierError (как-то так). В принципе, динамическая линковка классов -- достаточно сложная операция, которая, в частности, включает в себя автоматический доказатель теорем.

Какие операции этот самый класслоадер и верификатор, в частности, делает?

Classloader -- это такая абстракция джавы, описывающая механизм абстрактной линковки. Грубо говоря, входом к classloader является строка -- имя класса (например, com/foo/Bar), а выходом -- сайд-эффекты в виде изменения состояния рантайма, состоящее в том, что (в случае успешной загрузки) рантайм знает о классе com/foo/Bar, а также java.lang.Class -- объект, описывающий всю рефлективную информацию о классе.

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

Формально говоря, верификатор в виртуальной машине является одной из фаз classloader'а. Если совсем грубо говорить, то фазы такие:

• get bytes by name (согласно алгоритму получаем байтовый массив, который описывает .class-файл)
• parse classfile
• verify bytecode

classfile -- сериализованное представление, описывающее устройство Java-класса, и в нем присутствует примерно такая информация:

• нек-рое служебное описание версионной информации
• текущая версия .class-файла
• constant pool -- массив, в котором содержится информация о константах
• имя класса в символической форме
• имя суперкласса в символической форме (ссылка на суперкласс осуществлякется по символическому имени; если он загружен, то на него происходит линковка и проверка того, что класс согласован с нашим; если он не загружен, то мы просим classloader загрузить его => загрузка одного класса может приввести к загрузке многих других классов, + в каждом классе исполнится код из class initializer секции, в bc это )
• какие интерфейсы реализует
• какие у него методы
• какие имеются атрибуты

На основании всей этой информациипроисходит проверка линкуемости байткода в VM. То есть, проверяется оч большое кол-во весьма разнородных инвариантов. Например, если декларировать класс как implements I1, то проверяется, что все методы этого интерфейса реализованы этим классом. если нет, то загрузка данного класса не происходит.

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

Перед этим давайте посмотрим на то, чем является метод в байткоде. Java -- это классический ОО-язык, в нем (согласно иерархии на уровне .class-файлов) присутствует примерно вот что:

• класс
  • его суперкласс (super)
  • интерфейсы (interfaces[])
  • методы (methods[])
  • поля (fields[])
  • атрибуты (attributes[] -- например, модификаторы класса)
• метод:
  • линковочная ипостась
    • имя
    • сигнатура (сигнатура метода int getX(double d) в классе Foo выглядит как I LFoo; J -- возвращает I (int), имеет два параметра: LFoo (неявный аргумент -- инстанс класса) и J (double))
    • атрибуты
      • код -- байткод метода
      • число локалов
      • максимальная глубина стека
      • исключения

Верификация класса состоит в верификации его адекватности по иерархии наследования и в верификации индивидуальных методов (у каждого метода его байткод рассматривается статическим анализатором в верификаторе и на нем производятся некоторые вычисления)

Что такое локалы? Хотя JVM -- стековая машина, нек-рые операции на стековой машине делать не оч удобно.

Пусть у нас есть нестатический метод getX. Ему должен быть передан какой-то инстанс Foo и какой-то инстанс double. Если мы хотим ссылаться на этот самый инстанс, нам нужно его откуда-то взять.

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

Если мы хотим адресовать аргументы, то в нулевом слоте у нас хранится this, в первом слоте -- d. Туда же можно записывать, например, переменную цикла.

Поэтому JVM -- не совсем стековая машина, это смешанная с регистровой стековая машина. Аргументами стековых операций явл. несколько верхних эл-тов стека, но можно адресовать еще не-крое кол-во локальных переменных.

То, сколькотаких слотов есть для локальных переменных -- это та информация, которая хранится в атрибутах метода.

Максимальную глубину стека вычисляет компилятор. Он вычисляет, насколько глубоко мы используем стек. Если мы можем статически доказать, что байткод использует больше стека, чем указано в этом стеке, то мы можем выбросить VerifierError и сказать, что это какой-то неправильный байткод.

Таблица исключений -- структура: при выбрасывании исключений на участке байткода от A до B произошло исключение типа E, то исполнение нужно продолжить с кода C. Если такой таблицы нет, то исключения пробрасывается на фрейм выше, где происходит ровно то же самое вычисление.

Что считает верификатор

1. Корректность стековых операций. Из-за того, что стек джавы нетипизированный по своей логической модели, рядом на стеке могут лежать значения типа объектной ссылки и значение типа число.
2. Совместимость типов. Бывает совместимость типов при вызове методов, тогда на стек сначала загружаются значения аргументов, а затем следует инструкция вызова метода; задача верификатора -- при вызове метода с данной сигнатурой проверить, что типы переданных аргументов совместимы с типами, указанными в сигнатуре.
3. Инкапсуляция: невозможность доступа из полей одного класса к приватным или защищенным полям другого класса.
4. Байткод не обращается к бОльшему кол-ву локалов, чем указано. Легко проверить: смотрим, сколько локалов на самом деле используется.
5. Глубина стека не превышает ту, что указана в байткоде. В общем случае это halting problem. Если у нас есть байткод со структурой типа: l: pushl 1; jmp l, то такой код верифицирован не будет. Вот тут и полезны локалы: перед ветвлениями верификатор убеждается, что стек пустой: все значения, которые нужны верификатору, сохранены в локалах.
6. Поток исполнения по исключениям. Переход на обработчик исключения -- это такой же вызов.

finally -- синтаксический сахар, в байткоде код try { tcode; throw e; } finally { fcode } выглядит как try { tcode; fcode; throw e;}

Вычисления при совместимости типов

Если бы в Java были бы только примитивные типы, и не было бы никакой подтипизации (те же int и short несовместимы с точки зрения байткода), никакой ОО-иерархии, то верификация совместимости типов была бы тривиальной и решалась за линию: тупо бежим по байткоду и делаем абстрактную интерпретацию.

Пусть у нас есть такая иерархия: A, B:A, C:A, и метод foo(a: A).

Байткод:

anew A
astore 0
anew B
astore 0
anew C
astore 0
aload 0
invoke foo

Этот код корректный, ибо и инстанс A, и инстанс B, и инстанс C можно передать в foo.

Каков алгоритм проверки? Проверяем метод целиком. У нас есть локалы и стек. Локалы -- это значения аргументов, переданных в функцию. Стек пуст.

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

Сложности начинаются именно на нетривиальных CFG, когда нам нужно оценить тип в каком-то значении.

Типичная сложность -- O(n log T) -- длина метода, помноженная примерно на глубину классовой иерархии.

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

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

lecture5.md

Лекция 5

Какие-то общие моменты про дизайн виртуальных машин, которые не вписывались ни в одну и предыдущих тем, и гипервизоры.

Как обычно пишутся интерпретаторы виртуальных машин? Кроме большого логического свитча, завернутого в цикл, придумать что-то сложно. Большая часть интерпретаторов в основном так и делается, разница лишь оптимизационного толка.

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

В чем можно устраивать какие-то оптимизации?

while (1) {
    switch (bc[bci++]) {
        case ...:
            ...;
            break;
        ...
    }
}

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

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

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

Почему это, в частности, полезно? Написание быстрых state-машин -- достаточно полезное занятие в широком классе задач, не только в интерпретаторе.

Следующая оптимизация -- оптимизация большого свитча (в джаве порядка 200 инструкций -- порядка 200 переходов в свитче). Часть наиболее популярных инструкций выносятся в т.н. быстрый интерпретатор, а инструкции, не считающиеся самыми часто используемыми, попадают на медленный интерпретатор. Если у нас процессор с маленьким кешом, то в него может влезть быстрый интерпретатор.

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

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

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

Поможет технология абстрактной интерпретации. На входе для абстр. машины, которая интерпретирует типы, у нас состояния локалов и стеков, и по ходу абстр. интерпретации он модифицирует состояния локалов и стеков в соответствии с инструкциями. Если была инструкция anew, то на стеке на одну больше объектных ссылок, если был iadd, то на стеке на одно число меньше.

Стандартная техника выяснения -- карты сборщика мусора. Используя карты верификатора, строит такого рода структуру.

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

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

Еще немного про оптимизацию блокировок

Дизайн хотспота заточен под оптимизацию того, что часто встречается. Блокировки в джаве встречаются часто, благодаря их дизайну., и на их оптимизацию понадобилось много времени. Если говорить логически, то несколько битов в заголовке каждого Java-объекта посвящено тому, чтобы описать, каково состояние этого объекта по отношению к блокировкам (взята/не взята блокировка на объекте, ждем по данном объекту, ...)

В любом методе на Java м/б ключевое слово synchronized (блочная структура), которое реализуется в пару инструкций monitorenter и monitorexit (неблочная структура, но верификатор проверяет их корректность).

У java.lang.Object есть wait, notify и notifyAll. С каждым объектом ассоциируют мьютекс и conditional variable, на которых можно согласованным образом исполнять эти операции. Например, мы не можем сделать wait, если не заблокированы на этом объекте.

if (!takeIfNotTaken()) parkUntilNotified(). Условие можно сделать на процессорных примитивах, а park должен обращаться к ОС.

JNI

Нейтивы позволяют вызывать мир за пределами Java-машины. До этого мы говорили про мир, который полностью контролируется JVM. А теперь мы хотим выйти за пределы ее контроля.

Придумали в NetScape для нужд встраивания джавы в браузер.

class Bar {
    double b;
    native int foo() {
        // ...
    }
}

Необходимо, чтобы при попытке первого вызова метода существовала функция на языке, совместимой с Си по ABI (например, на Си) со следующей сигнатурой:

int Java_Bar_foo(JNIEnv* env, jobject thiz) // env -- интерфейс взаимодействия c VM

Интерфейс нужен для того, чтобы работать с миром джавы. Например, внутри метода foo должна происходить работа с полем b. Получить это поле можно как-то так:

jclass c = env->getClass("Foo");
jfield f = env->getField(c, "d");

Есть два механизма привязки функций к реализациям: на основе имени (в адресном пр-ве где-то должна быть функция с таким именем), и с помощью специального вызова интерфейса JNI привязать произвольную ф-ю с подходящей сигнатурой.

Что делать рантайму, когда он увидел, что кто-то написал b = new Bar(); int x = b.foo();? Мы хотим вызвать ф-ю из джава-мира и как-то использовать ее результат.

Это довольно сложная операция.

Как происходит вызов ф-ии в мире си?

mov rdi, <thiz>
call foo (= push rip+...; jmp foo)
mov rcx, rax (rax -- регистр, где хранится возвращаемое значение)

Рантайм должен уметь поддерживать разные ABI. Чтобы передать управление на сишную функцию, надо уметь создавать JNIEnv, нужно уметь переводить джава-классы в объекты так, чтобы они существовали в мире Си.

А что со сборкой мусора? Рантайм должен предполагать худший сценарий: нативные методы могут выполняться долго. Еще одна проблема: тот объект, который мы переводим в мир си (в нашем случае инстанс класса Bar), должен быть стабильным, в нем не должны реаллоцироваться ссылки.

Но мы хотим собирать мусор. Поэтому вокруг JNI-ных методов существуют т.н. JNI-барьеры -- куски кода, который исполняются на входе и на выходе.

С одной стороны, JNI-ный метод может входить назад в Java-машину. С другой, он может выполняться сколь угодно долго, и в частности, он может исполняться таким образом, что по его возвращению все остальные потоки запаркованы на сейфпоинте.

Поэтому при входе в JNI и выходе из JNI, а также при любом входе в VM через JNI-ные интерфейсы, происходит проверка, что данный поток не д/б остановлен. Это значит, что во время сборки мусора нативный код исполняется как ни в чем не бывало, и единственное, что его может остановить -- это попытка тем или иным образом повзаимодействовать с VM.

Вот что добавляется в эти входы и выходы:

if (toBeStopped(getThreadId())) {
    parkOnSafepoint();
}

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

Поэтому интероп с открытым миром -- вещь долгая и неудобная.

Взаимодействие с ОС

Что ВМ чаще всего надо от ОС?

• выделение подлежащей памяти для объектов в хипе. В JVM свой достаточно эффективный memory manager, но ему тем не менее нужна какая-то память, чтобы ею управлять. Эту самую память обычно и запрашивают у ОС на старте программы.

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

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

• взаимодействие с планировщиком ОС. Мы используем аппаратные возможности конкурентности, нам нужно как-то планировать кванты исполнения, а для этого нужно уметь запрашивать у ОС создание потока или другого примитива.

• для динамической трансляции код -- это данные. > Когда джит создает машинный код, то манипулирует с кодом как с данными, потом у него происходит передача управления. У архитектур, у кот. кеши инструкций и кеши данных -- это разные кусочки кремния (как у ARM, например), создание машинного кода требует операции синхронизации (сброса кешей -- чтобы то, что сейчас есть в кеше данных, оказалось и в кеше инструкций).

Архитектура Фон-Неймана -- однородная архитектура, в которой код и данные ничем не отличаются, зранятся в одной памяти.

Гарвардская архитектура -- логически раздельное хранилище для исполняемого кода и для данных.

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

Ядро процессоров x86 достаточно сильно гарвардское, но программная модель, которая описывается архитектурой x86 -- это фон-неймановская архитектура, там никаких особых синхронизаций кешей делать не надо.

• Место, в которое в хотспоте было вложено немало инжиниринга -- это интерфейсы доступа к времени. Интерфейсы управления временем во всех архитектурах стоят особняком, а в джаве, ибо в JDK достаточно небогатый набор доступов к времени, особенно к времени замера нек-рых вычислений (только currentTimeMillis() и nanoTime()).

  Люди использовали этот метод как таймер для профилировки, и это вело к неприятным последствиям, ибо запрос времени -- это долгая операция, требующая взаимодействия с ОС и каких-то соответствующих вычислений. Поэтому в хотспоте currentTimeMillis сделан достаточно сложным образом: там есть кеш, который периодически обновляется, а относительно этого кеша сдвиг считается инструкцией, связанной с текущим счетчиком тактов процессора. Это позволяет получать достаточно точные таймстемпы, не опрашивая постоянно ОС.

Внутренний профилятор и отладчик

Из-за того, что высокопроизводительные ВМ стараются базироваться на фидбеке о поведении программы, нужны средства для того, чтобы этот фидбек считать.

Профилятор строит гистограмму, какой метод сколько времени/ресурсов занимает. Позволяет программисту оптимизировать алгоритмы внутри функции, операции, а джиту -- напускать более высокооптимизирующие алгоритмы джита на то, про что нам известно, что оно горячее.

Две стратегии: точное профилирование и семплирующее профилирование.

• Точное -- вошли в какую-то функцию, запомнили, сколько сейчас времени, при выходе из функции запомнили, что сейчас времени столько-то, и разницу нужно добавить к весу данной функции.
• Семплирующее -- приближенное профилирование. Качество профилирования позволяет оценить ЧТОБЫВЫПОДУМАЛИ теорема Котельникова (или Найквиста).

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

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

Если у нас есть функция, в которой проводится 80% времени, то семплирующий профайлер ее быстро обнаружит. А если есть 5 функций, которые вкупе занимают 80% времени, то поймать все 5 при малой частоте семплироания достаточно затруднительно.

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

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

В большинстве ВМ значительные усилия приложены на понимание того, как обеспечить внутреннюю отлаживаемость самой ВМ.

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

Кроме того, в хотспоте реализован достаточно богатый механизм инструментирования -- возможность подключения ВМ, посмотреть ее текущее состояние memory manager'а, что джит скомпилировал, а что нет, и так далее.

Есть еще очень важный момент -- это смортом (?) анализы: большинство падений, которые видят разработчики ВМ -- это не падения, которые они могут воспроизвести, это падения, где могут предъявить какой-то core dump или какую-то другую информацию о бектрейсах. Необходимость качественного сбора такой информации критична для отдалки и sustainability.

Аппаратный ускоритель

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

В чем сложность реализации JVM в кремнии? Модель вычисления внутри JVM весьма сложная, ам присутствуют весьма высокоуровневые абстракции, объекты, различные типы данных, оч поздняя линковка -- необходимость сложных вычислений, чтобы выполнить простые методы. Чтобы выполнить invokevirtual, иногда необходимо загрузить сотню классов, выполнить кучу предварительной инициализации, и только потом выполнить метод.

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

(?) сделан аппаратный ускоритель для процессоров ARM под названием Jazell. В ARM это сделать удобно, потому что архитектура ARM в этом смысле -- оч изящное аппаратное решение, но об этом позже. В большинстве современных процессоров есть достаточно сильно разделенные механизмы декодирования инструкций и выполнения инструкций.

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

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

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

Реализовано это примерно таким образом: у нас есть набор инструкций, есть декодер, и есть ядро. Набор инструкций попадает в декодер. Но выход из декодера не должен совпадать с входом. В процессоре ARM изначально было создано расширение SAM (игра слов: ARM -- рука, или Advanced RISC Machine; SAMP -- большой палец руки, а еще это набор инструкций для того, чтобы уменьшить футпринт -- то, сколько нужно байтов, чтобы скомпилировать ту или иную программу).

Каждая инструкция шириной 2 или 4 байта, некоторый не очень большой декодер (несколько десятков тысяч транзисторов) транслировал этот набор инструкций в набор инструкций ARM, который понимался тем самым ядром, у которого ARM уже был (получается, декодер -- это что-то типа препроцессора для процессора, он транслирует один набор в другой, поэтому можно было даже смешивать ARM с SAMPом, ибо ядро все равно исполняло ARM).

Ровно таким же образом была реализована и Jazell: был добавлен дополнительный декодер, который транслировал простые JVMные операции в тот же самый набор инструкций ARM. Для сложных инструкций он выполнял (?) -- переход на предсказуемый адрес, где исполнение уже продолжала ВМ.

На этом JVM все!

Дальше будем разговаривать про всякого рода гипервизоры и аппаратную виртуализацию.

Аппаратная виртуализация

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

Поговорим об общих местах и о нек-рых частностях на примере VirtualBox.

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

Почему это м/б полезно?

• Позволяет нам создавать программы для архитектуры, которой еще нет. Первый порт линукса на mt64 появился на симуляторе, а уже потом пришла первая аппаратная реализация. Это очень удобный паттерн: если у нас есть хорошо специфицированный набор инструкций, то необязательно иметь кремний для того, чтобы писать под него программы. Аппаратной реализации конкретного компьютера у нас может и не быть, но мы можем создавать под симулятор ОС, программы и прочее.

Кроме того, ежели мы рассматриваем ВМ как менеджер ресурсов, то мы можем, рассматривая ОС и программы в ней как вход для нек-рой ВМ, гибко управлять тем, какие ресурсы доступны той или иной ОС, и позволяет существовать различным ОС с различными требованиями на ресурсы на одном физ. оборудовании.

Более того, кремний м/б недоступен и потому, что его уже нет по тем или иным причинам (например, он устарел -- вспомним пример с OS/2 и немецкими банками).

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

Это важный момент, который в большой мере влияет на дизайн гипервизоров.

Историческая справка

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

В 1964 году IBM создала архитектуру CP40, которая представляла собой 14 ВМ, исполняющихся одновременно на одном и том же мейнфрейме, причем каждая из них считала, что исполняется полностью в своем монопольном окружении, владеет всем миром, и нек-рый монитор ВМ обеспечивал мультиплексирование -- исполнение на всех этих инстансах.

Через 2 года появилась в компании IBM VM44, это было решение с паравиртуализацией (это виртуализация, при которой те, кого виртуализируют, знают, что они исполняются в виртуальном окружении). Там впервые использовалась виртуальная память, ставшая необходимым компонентом всех вычислительных систем.

1972 -- IBM VM370, в которой считал абсолютно полноценный, весьма вложенный гипервизор (т.е. гипервизор мог исполняться под гипервизором, который исполнялся под гипервизором и т.д.), с достаточно малой просадкой по произв-ти, и в целом это был такой триумф гипервизоров, но только на мейнфреймовом оборудовании: для большинства людей эта технология была недоступной и не очень релевантной.

Через 2 года были созданы критерии формальной виртуализируемости (уже после появления качественных решений) -- критерии Попека-Гольдберга, а потом было большое-большое затишье в тезнологиях виртуализации, потому что на рынке массовых вычислений она была не нужна, а на рынке нишевых вычислений она уже была сделана. Это затишье продлилось больше 20 лет.

В 1998 году была основана компания VMWare, которая создала первый коммерческий гипервизор для массовой архитектуры x86.

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

Триумфальное пришествие VMWare, которая стала оч крупной компанией, лидером на рынке ВМ, оно подвинуло Intel и AMD в 2005 на создание расширений аппаратной виртуализации. Пример с тех пор Intel и AMD производят все новые и новые расшрения того, что они делают в смысле разного рода виртуализаций, то бишь, они делают все новые технологии аппаратной виртуализации разного рода оборудования (виртуальные гостевые карты, виртуальные видеокарты, технология поддержки виртуализации произвольного оборудования VTD и т.д.)

В принципе, с тех пор виртуализация вошла на рынок community hardware абсолютно неотъемлемым образом. Сейчас уже нет компьютеров, у которых не было бы какой-то аппаратной поддержки виртуализации.

Проблемы

Если мы подумаем о виртуализации, то какие можно выделить важные проблемы создания ВМ?

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

  Исторический анекдот: когда И. работал в VirtualBox, у них появилось желание создать возможность запускать макось в виртуальном окружении. Задача казалось достаточно сложной, в частности потому, что существовал достаточно большой корпус аппаратного обеспечения, которого не было на другом оборудовании, плюс нек-рое кол-во firmware -- все это нужно было промоделировать. Они вдвоем больше полугода бились, и в рез-те они все-таки это сделали, но это была чрезвычайно трудоемкая активность из-за нереально большого объема создания модели большого кол-ва разного оборудования с разными хар-ками.

• Высокая производительность. Что сильно усугубляет сложность коррекции -- это необходимость создания высокоуровневого решения.

  Какие аспекты произв-ти существуют в реализации гипервизоров?

  • исполнение инструкций. Мы хттим исполнять какой-то набор инструкций, которые описывает программа, ОС, и хотим, чтобы это работало почти так же быстро, как на физ. процессоре.
  • часть исполнения инструкций -- это доступ к памяти. Хочется, чтобы доступ к физ. памяти был такой же быстрый, как если бы это было на реальном процессоре, но чтобы не терялся контроль (чтобы монитор ВМ мог исполнять программы в только выделенном для данной ВМ песочнице, чтобы даже гостевая ОС не могла лезть в чужую память).
  • выполнение ввода/вывода. Мы не можем пользоваться ОС, которая ничего не вводит и не выводит, потому что это была бы такая монада, которая существует сама по себе и ни с кем не контактирует. Поэтому нужно создавать технологии, предоставляющие доступ или к реальному оборудованию на машине, или к нек-рым программным моделям этого оборудования.
  • время отклика. Хотим, чтобы система в целомна пользователем чувствовалась так же хорошо, как если бы она выполнялась без монитора ВМ.
  • плюс все это должно быть безопасно и стабильно: гостевая ВМ не должна влиять на исполнение хостовой системы или других гостевых систем. Если посмотреть на Амазон, то все существование Cloud-арзитектуры амазона сугубо обеспечивается мониторми ВМ. Благодаря этому амазон может продавать именно виртуальные инстансы, т.е. ОС, выполняющуюся неизвестно где, неизвестно с кем вместе на одних и тех же компьютерах, но при этом с гарантиями кач-ва обслудивания и доступом к нек-рому кол-ву ресурсов. Иначе на каждого нового клиента Амазону пришлось бы покупать новый сервер и стоило бы это совсем других денег. При этом именно из-за того, что они могут коаллоцировать несвязные друг с другом инстансы на одном оборудовании, и один гость не ломает другого, позволяет им поддерживать разумную безопасность модели.

Паттерны решения проблем

Как эти проблемы решаются в разных гипервизорах?

Изначально люди писали программы. Потом им понадобилось писать системные программы (supervisor -- термин из бизнеса, переводится как надзиратель -- системное ПО, которое обеспечивает функционирование работы пользовательского ПО). В момент, когда появилась необходимость в виртуализации, люди поняли, что нужен какой-то надзиратель над надзирателями -- монитор ВМ, который позволяет существовать нескольким системам, так сказать, управления ресурсами пользовательского уровня. Это назвали hypervisor, или гипервизов, по-нашему. Это системное ПО, более системное, чем ядро ОС.

Так как обычно эти гипервизоры решают задачи, которые перед ними стоят?

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

Соответственно, для реализации гипервизора одна из основных стратегий -- это программная реализация всех тех кусочков, которые необходимо предоставить, но с оговорками:

• если мы будем моделировать набор инструкций, если будем все инструкции исполнять при помощи ВМ, то это будет тормозить систему. QEMU использует динамическую трансляцию. Но для исполнения серьезных больших загрузок он был недостаточен, и поэтому для таких гипервизорных сценариев в ядре Linux появилось такое расширение, как KVM (kernel VM), который позволял не эмулировать все инструкции, которые существуют в процессоре, а исполнять те инструкции, которые можно исполнять напрямую, напрямую.

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

  При нормальной реализациик компонентов производительность аппаратного обеспечения, делающего то же самое -- это потолок для гипервизоров.

  Для этого вычисления можно использовать интерпретаторы, а можно использовать и более сложные техники.

• То же верно про память. Если мы хотим описывать возможности гипервизора в отношении адресации, то надо понимать, что для системного ПО у памяти достаточно сложная модель. Для прикладного ПО у памяти весьма простая модель -- огромное линейное простр-во в зависимости от битности нашего процессора: для 32-битной архитектуры это 4Гб, для 64-битной -- побольше, с дырками и алиасами, но примерно то же.

  Если мы хотим на архитектуре A моделировать архитектуру B, то у них нередко бывают сильно разные способы взаимодействия с виртуальной памятью. Например, на архитектуре SPARC memory manager программно-аппаратный: часть операций трансляции физ. памяти делается при помощи программного кода, а часть -- при помощи оборудования.

  В x86 все вычисление аппаратное, делается при помощи технологической и логической единицы MMU (Memory Management Unit), у которой достаточно сложный программный интерфейс. Существуют нек-рые иерархические таблицы страниц с достаточно сложной структурой данных, которая описывает, как транслировать виртуальные адреса в физические.

  Гипервизоры хотят, чтобы использовать память можно было и быстро, и корректно одновременно.

• То же верно про оборудование. В типичном гипервизоре оборудование описывается нек-рым предопределенным набором достаточно стандартной конфигурации, которая часто не имеет никакого отношения к оборудованию, которое установлено на компьютере. Можно на компьютере создать ВМ с 10 сетевыми картами, такого в реальности не бывает, но это существует в виде программных моделей, которые будут представлены гостевым ОС, они будут работать с виртуальными картами так, как будто они реально существуют, а монитор ВМ может определить, что происходит, если гостевая ОС пытается читать и писать какие-то данные в ту или иную сетевую карту.

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

Критерии Попека-Гольдберга

Достаточно простые и понятные критерии того, можно или нельзя эффективно виртуализировать тот или иной набор инструкций.

Попке и Гольдберг -- два ученых из IBM, которые в 74 году сформулировали теорему, по которой можно ориентироваться, насколько хорошо виртуализируем тот или иной набор инструкций.

Эта теорема полезна не столько своим фактическим содержанием, сколько системным размышлением о том, какие задачи решает монитор ВМ и как он решает их.

Какие требования предъявлись?

• Эквивалентность: исполнение программы под монитором ВМ должно быть неотличимо от исполнения без монитора ВМ на том же оборудовании (возможно, за исключением временных характеристик)
• Контроль монитора ВМ ресурсами: гипервизор может при необходимости выдавать какие-то физ. ресурси ВМ, а может их забирать. Не должно происходить бесконтрольного захвата оборудования.
• Эффективность. Необходимо, чтобы исполнение было достаточно слабо отличимо по произв-ти от исполнения на реальном оборудовании, иначе никто гипервизиором пользоваться не будет.

Для формулировки этого прицнипа используется разбиение всех инструкций на три класса: на привилегированные, чувствительные и другие.

P -- привилегированные инструкции. Здесь подразумевается конкретная модель исполнения процессора: наличие по крайней мере двух уровней привилегии: привилегированный и непривилегированный. В зависимости от уровня привилегий, привилегированные инструкции доступны только на привилегированном уровне, на непривилегированном они осуществляют выход в монитор виртуальных машин или куда-то еще с информацией, что гостевая система пыталась выполнить какую-то привилегированную инструкцию.

S -- чувствительные инструкции -- те инструкции, либо которые ведут себя по-разному на разных уровнях привилегий, либо которые могут вести себя... типичный пример -- запрещение прерываний. Если хотим, чтобы процессор больше не обрабатывал внешние аппаратные прерывания, то мы используем инструкцию cli: она меняет состояние процессора таким образом, что исполнение теперь продолжится без возможности прерывания аппаратным образом.

O -- другие.

Есть такое достаточно условное, но важное разделение регистров на регистры общего назначения и регистры специального назначения. В регистры общего назначения (rax, rcx, ...) можно записать значение, чтобы обсуществлять какие-то вычисления. Значения регистров специального назначения влияют на функционирование всей программы (например, регистр флагов процессора, в котором хранится состояние режима прерываний, или регистр cr3, в котором хранятся правила трансляции для менеджера виртуальной памяти).

Доступ к специальным регистрам -- это типичный вариант чувствительных операций. Чувствительной операцией может также считаться сброс кешей. Еще, возможно, операции взаимодействия с периферией. В x86 есть две техники взаимодействия: одна через отображаемый в память ввод/вывод (mmio), другая -- portio (ввод/вывод через порты). Например, out 42 -- это инструкция, которая взаимодействует со специальным адресным пр-вом (АП портов) и на это АП повешена какая-то периферия. Эта инструкция и привилегирована, и чувствительна. То есть, P и S пересекаются.

Собственно, критерии Попека-Гольдберга состоят в следующем. S <= P (любая чувствительная инструкция является также привилегированной, ее можно выполнить только на привилегированном уровне операций. Обратное неверно: есть привилегированные инструкции, не являющиеся чувствительными, например, завели особый регистр, который ни на что не влияет, запись в него нечувствительна).

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

Нам необходимо, чтобы такие трапы (переходы в монитор ВМ) встречались нечасто. Суть всех критериев как раз и состоит в этом факте. Удовлетворение этим двум требованиям позволяет создавать эффективно виртуализируемые наборы инструкций.

При этом, что интересно, набор инструкций x86 не удовлетворяет этим критериям. Существует нек-рое кол-во чувствительных инструкций, которые не являются привилегировнными. Они хоть и не могут изменить привилегированное состояние, но могут его обнаружить.

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

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

Как они ее преодолели? Они осознали, что у гостя есть два контекста: часть кода исполняется на уровне пользователя, и там инструкции все непривилегированные, а есть инструкции, которые исполняются на системном контексте. Из опыта мы знаем, что больше исполняется пользовательского кода.

Поэтому для разных контекстов они выбрали разные стратегии эмуляции: для системного кода использовался джит, который брал этот системный код и исполнял его после рекомпиляции. То есть, если мы увидели, например, cli, то ранее до этого мы оттранслировали эту инструкцию в тот же код, записывающий какую-то информацию в виртуальную табличку, специфичную для гостя, что что-то с ним приключилось и он не готов принимать прерывания.

Исполнение пользовательского кода исполняется напрямую на процессоре. Мы достигли приемлемой производительности, не испортив совместимость.