Идеальная виртуальная машина SovietVM

[Алексей Гринь]

В моей ясной гениальной голове давно сформировалось некое представление об идеальной VM, надо наконец-то это изложить (по частям, ибо много графомании). Кодовое имя - SovietVM. Слава КПСС!

Часть 1. Ядро.
Во-первых, я бы чётко выделил в системе самый минимум ("ядро"), без которого виртуальная машина просто не может запуститься. Это - классы vm.Object, vm.ClassLoader, vm.Array, vm.Class, vm.Field, vm.Method, vm.Thread, vm.Lock, vm.GC (?) - они реализуются на С++ внутри ядра.

Весь прочий функционал реализуется *вне ядра*, а сами классы ядра не должны быть видны пользователю - они должны быть обёрнуты внешними обёртками, напр. system.reflection.Method есть обёртка вокруг vm.Method.

Зачем это надо? Затем, что такой модульный подход позволяет использовать виртуальную машину при эмбеддинге как захочется. Можно использовать стандартные классы VM, можно использовать другую библиотеку классов (напр., запросто эмулировать JVM); для девайсов с ограниченными ресурсами можно поstrip'ить ненужное, и т.д (т.н. профили). В C# спохватились довольно поздно (только к Silverlight'у поняли, почему это важно), в результате такой запоздалости модулярность получились у них довольно нерасторопная.

Напр., vm.Class.getName возвращает имя класса, однако... типа "строка" как такового в ядре нет. Что же возвращает эта функция? Она возвращает тип intptr. Это один из примитивных типов, который представляет opaque-указатель (32 бита/64 бита). В данном случае этот указатель инкапсулирует сырой набор байтов в формате UTF8 (специальный тип GC - blob). Задача обёртки system.reflection.Class.getName заключается в том, чтобы вызвать vm.Class.getName и конвертировать результат в целевое представление строки (system.String) -- а здесь уже выбор за архитектором. Это может быть UTF8, UTF16, и т.д.; char'ы могут быть inlined как в C# или shared как в Java -- что угодно. Такая вот свобода действий.

Грубо говоря, ядро и есть VM, а всё остальное - расширения к нему.

[Алексей Гринь]

Часть 2. О примитивные типах.

Примитивные типы: int, long, float, double, bool, intptr. Противопоставляются byref-объектам, наследующим vm.Object/system.Object

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

Я первоначально хотел оставить тип byte для IO, но теперь порешил так: куда гибче оставить эту задачу на библиотеку классов, напр. (навскидку) system.io.ByteBuffer как обёртку вокруг int[]. Напр., в Java в этом смысле классы byte[] и java.nio.ByteBuffer дублируют друг друга -- более того, до версии Java 1.4 тип byte мог вполне занимать 4 байта, как и int. Спрашивается, а зачем тогда вообще он был нужен? Более того, в Java тип byte - знаковый, что является полным маразмом и дискредитацией наличия этого типа в системе типов.

Так как в ядре нет понятия строки, то и существование понятия char на уровня ядра проблематично. 1 байт? 4 байта? 8 байтов? Поэтому на уровне метаданных должны поддерживаться typedef'ы: "typedef int char", например. Если какой-то язык не поддерживает char'ы, то он может просто игнорировать данный typedef.

bool я оставляю в ядре (в отличие от char), так как это важный тип, существенный для успешного выполнения логики кода. Без типа bool не запустится ни одна программа. Более того, реализация размерности bool в силу его семантики (всего два значения) не имеет важного значения, в отличие от того же способа кодировки строки/символов (UTF8? UTF16? у каждого своё решение).

Что касается unsigned-значений - аргуметы те же, что и в Java: не нужны. Если уж сильно приспичит, то unsigned int всегда можно выразить через long. В C# беззнаковые типы были введены заново ради общения со старым C-кодом. В обычном коде они вообще не используются. Однако эту проблему можно решить намного проще, не замусоривая корневое пространство имён кучей типов. Об этом в следующий раз.

intptr используется как opaque pointer на системный ресурс, удобно в реализации обёрток (в Java используют некрасивый хак - тип long, однако он недаёт никаких гарантий о размере указателя).

[Алексей Гринь]

Часть 3. Interop.

Общение виртуальной машины с внешним native-кодом -- вещь первостепенная в SovietVM. По моему мнению, виртуальная машина должна быть легковесной обёрткой вокруг целевой платформы, быть инструментом, а не самоцелью. Поэтому большую часть времени VM будет проводить в native-библиотеках.  Поэтому удобство пользования и производительность native call'ов имеют первостепенное значение. Однако эта светлая идея идёт в некоторое противоречие с заявленным минимализмом ядра: си-код имеет типы short, byte, unsigned int и т.д., а в ядре ничего этого нет. Что делать? Как вызывать такие функции?

На помощь приходят атрибуты. Андерс Хейлсберг зачем-то наплодил в C# кучи типов, которые используются исключительно при interop'е и которые не используются больше нигде (я про беззнаковые целые uint, ushort и т.д.), при этом бессмысленно усложняя язык и систему.

Ведь можно использовать атрибуты, которые в C#'е были с самого начала (в отличие от Java).
Например, если си-код имеет функцию типа void foo(unsigned int i), то виртуальная машина может описать этот тип следующим образом:

native static void foo(@MapAs(ExtendedType.UINT) long i);

Вот и всё -- так просто. Типа long на стороне ядра достаточно, чтобы вместить беззнаковый int. Далее ядро просто-навсего внутренне приводит long к unsigned int, проверяя на диапазон 0..2^32-1 и по возможности кидая исключение (для пущей производительности можно проверку в release-версии отключать). Оверхед не такой и большой, зато это удачный компромис между минимализмом и возможностью вызывать си-код вообще. Этот интерфейс также полезен для общения между разными VM-языками, когда один язык поддерживает "расширенные типы", а другой не поддерживает: неподдерживающий язык даже не будет знать, что это какой-то uint, для него это просто long. В C#/CLR же настрочили сотню страниц о так называемой CLS-compliance, что просто глупость по сравнению с моим гениальным подходом.

Пока я не определился насчёт более сложных ситуаций, как то передача структур туда-обратно. Вероятно, игра не стоит свеч (сборщик мусора должен поддерживать pinned-объекты и т.д.), и достаточно писать glue-обёртки, как в Java. Если же игра стоит свеч, то нужно в ядро вводить ещё один базовый класс - vm.Native. Маппинг полей такой же, как в функциях:

Код Выделить Развернуть


class POINT {
   @MapAs(ExtendedType.UINT)
   public long x, y;
}


Надо думать: удобство vs. минимализм?

[Python]

Без типа bool не запустится ни одна программа.

В сишнике как-то обходились без.

[Python]

Я первоначально хотел оставить тип byte для IO, но теперь порешил так: куда гибче оставить эту задачу на библиотеку классов, напр. (навскидку) system.io.ByteBuffer как обёртку вокруг int[].

Тяжеловато получится, мне кажется.

[Python]

Более того, в Java тип byte - знаковый, что является полным маразмом и дискредитацией наличия этого типа в системе типов.

Я бы вынес абстракцию знака за пределы базовых примитивных типов, просто добавив отдельные операции для знакового и беззнакового сравнения и некоторые другие действия. Разграничение типов по знаковости — забота не VM, а языка. Так же, как и разграничение символов и чисел.

[Алексей Гринь]

В сишнике как-то обходились без.

Потому что си слабо типизированный. В современном языке использовать всё что угодно в качестве boolean logic — моветон. Байткод и метаданные должны иметь чётко определённые логические операции и интерфейсы, для простоты и изящества. Мне так кажется. Если у вас есть серьёзные аргументы против, то всегда можно использовать typedef'ы (уже вне ядра, правда будет проблема с ExtendedTypes )

Тяжеловато получится, мне кажется.

Да не очень. В Java, например, все вызовы ByteBuffer.put/ByteBuffer.get суть intrinsic и компилируются в простые машинные инструкции чтения/записи в память. Правда, у меня такого не получится (ByteBuffer живёт вне ядра и недосягаем для таких оптимизаций), но для современных систем не беда заинлайнить подобные вызовы: ведь что такое ByteBuffer.get? Это просто нахождение нужного int и немного bit shuffling-магии.

Самый главный предполагаемый вами оверхед - это маршаллинг между VM и нативным кодом (теми самыми си-функциями fread/fwrite, что реально читают из файла, например), так тут наоборот просто идиллия: можно скармливать си-коду сразу внутренний int[] (по ссылке), и это прокатит, ведь для нативного кода нет разницы: int* или byte*. Для него это просто последовательный набор байтов.

[Алексей Гринь]

Я бы вынес абстракцию знака за пределы базовых примитивных типов, просто добавив отдельные операции для знакового и беззнакового сравнения и некоторые другие действия. Разграничение типов по знаковости — забота не VM, а языка. Так же, как и разграничение символов и чисел.

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

Да, это непроизводительно, но это проблема JIT'а (или интерпретатора), он должен быть настроен так, чтобы находить такие паттерны и замечательно их оптимизировать.

[Алексей Гринь]

Часть 4. Атрибуты.

Атрибуты эта метаинформация, embedded в определения классов, полей, методов.
Атрибуты в первую очередь служат в помощь компилятору целевого языка, они в целом игнорируются ядром. Но по сравнению с C#/Java, мы значительно расширяем их узус.

Конструкторы. С точки зрения VM, конструктор это рядовая функция инициализации, которая вызывается аккурат после выделения памяти под объект. Чтобы VM-язык мог отличить конструктор от рядовой функции, функция инициализации помечается специальным атрибутом. Этот маркер используется только компилятором, а сама виртуальная машина не делает никаких рантайм-проверок и ничего не знает ни о каких "конструкторах":

Код Выделить Развернуть


@Constructor
public void init() { }


Все подобные атрибуты выведены за пределы ядра.

Generics. VM не поддерживает generics напрямую (в отличие от C#), ибо полноценная реализация generics находилась бы в противоречии с системой типов и заявленным минимализмом. Однако целевой язык волен делать проверки типов в compile-time (как в Java). Атрибуты в данном контексте мы можем использовать, чтобы явно пометить type parameters в интерфейсе (чтобы красиво было видно в API reference).

Свойства. Свойства это всего лишь getter- и setter-методы с няшным синтаксисом. Поэтому нет смысла добавлять их поддержку напрямую в VM (как сделали в CLR) -- пусть это будет просто атрибут, compiler hint:

Код Выделить Развернуть


@PropertyGetter("x")
public int getX() { return x; }


Сюда же: события, throws clause и т.д.

Под сомнением, должны ли поддерживаться напрямую или быть атрибутами: access modifiers (public, private, etc.), final (== sealed || const) ?

By-value типы. С помощью атрибутов можно эмулировать by-value-типы в C#. Напр., реализация C# вольна помечать такие классы атрибутом @Struct. Store/load объектов всех классов, помеченных этим атрибутом, компилятор C# тогда будет осуществлять, напр., с помощью метода obj.clone(). Если VM реализует escape analysis вкупе с inlining, то оверхед будет не сильно большой.

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

[Алексей Гринь]

Часть 5. Safepoints, native access и fixed-объекты.

Сборщик мусора пока что находится в стадии прототипирования, о нём потом. Здесь я поговорю о safepoints. Safepoint это состояние потока, когда он может быть безопасно остановлен. Если реализовать SovietVM через интерпретацию, то вставка safepoints проста -- например, через каждые N инструкций поток сигнализирует о том, что он находится в safepoint.

Зачем они нужны? Чтобы сборщик мусора мог безопасно остановить все VM-потоки перед самой сборкой. Когда VM соображает, что памяти тю-тю, она устанавливает глобальное событие stopThreads. Каждый поток через каждые N инструкций проверяет сие событие и сам себя приостанавливает, если флаг события равен true. Сам же поток, вызвавший сборку мусора, сидит и ждёт, пока все VM-потоки не перейдут в режим suspended.

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

Проблема возникает с native access. Если поток в данный момент находится в native call, то вставить safepoint уже не получится. Что если native-вызов - блокирующий, например Thread.sleep? Сборщик мусора не может ждать несколько секунд. Решение такое: если поток находится в native, то мы должны проигнорировать его, с условием что по выходу из native call поток должен сразу перейти в safepoint.

Но из такого решения вылазит ещё одна проблема. Если разрешить native-потоку трогать VM-кучу, то нативный мутатор может оставить кучу в нестабильном состоянии, а сам native-код будет крашиться, потому что все указатели вдруг переместились (после сборки). Что делать? Разумное и простое решение, которое я пока вижу: ввести в VM специальное понятие fixed-объектов. Эти объекты выделяются вне куч, гарантируются быть непередвигаемыми и т.д. В C# эту проблему решили с помощью object pinning, но оно фрагментирует кучу (даже nursery!) и усложняет сборку. А в Java классы вроде direct buffers итак выделяются вне обычной кучи и не двигаются.

Но в отличие от Java, мы вводим это понятие в само ядро VM -- объект любого класса может выделен как moving или как fixed, а также конвертирован туда-обратно. В C# подобное тоже делается во время маршалинга (например, строк), однако оно почти никак не контролируется и спрятано от программиста, а также мы не можем кешировать результаты/буферы, из-за чего память для одного объекта может выделяться и конвертироватся туда-сюда по N раз, что есть плохо.

Native call'ы должны принимать в качестве аргументов только fixed-объекты; в ином случае -- автоматически конвертировать non-fixed-объект в fixed-объект.

Язык, целиком и полностью поддерживающий SovietVM, должен располагать синтаксисом вроде new fixed int[10].

Я думаю, чтобы радикально упростить сборку мусора, мы можем запретить fixed-объектам иметь какие-либо by-reference-поля. Пусть это лучше будет intptr, с ручным маршалингом через что-то вроде vm.Object vm.Native.ptrToObject(intptr, vm.Class). В таком случае сборщику мусора можно не сканировать fixed-объекты вообще.

Если же надо реализовать (в low level VM-расширениях) какие-то более заковыристые случаи, то рекомендуется использовать glue-библиотеку. API уже имеет немного функционала. Напр. само по себе GCReference даёт нам WeakReference, а GCReference + GC::registerRoot позволяет нам хранить, изменять и проч. moving-объекты даже изнутри С-кода.

[Алексей Гринь]

Часть 6. Память. Сборка мусора.

По идее, на VM не ставится никаких условий по реализации аллокатора и сборщика мусора. Тем не менее, текущий простенький stop-the-world прототип использует следующий алгоритм:

1. Первоначально, все объекты создаются в малой куче/младшем поколении, с помощью простого bump pointer allocation. Когда поколение переполняется, то происходит малая сборка: сборщик рекурсивно маркирует достижимые объекты (от корней, статических полей, GC references, intergenerational cards и данных стека) и эвакирует достижимые объекты в старшее поколение, попутно обновляя ссылки на них.

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

На данный момент используется глобальный мьютекс, что не есть хорошо В будущем надо реализовать как-нибудь lock-free TLAB'ы.

2. Итак, после того, как объект пережил две сборки в малой куче, он эвакуируется в большую кучу/старшее поколение -- до тех пор, пока сама большая куча не будет переполнена, в таком случае происходит уже большая сборка. В отличие от малой, большая куча допускает фрагментацию, так как для увеличения скорости она никогда не будет компактироваться (ну что такое менять указатели в 1 гигабайте?). Здесь пока я в раздумьях насчёт конкретной реализации, пока что не реализовал -- главное тут уметь быстро эвакуировать, чтобы сократить время малых сборок.

3. Есть также системная память VM. Здесь хранятся внутренние структуры VM и GC, классы, тела методов. Проще говоря: здесь хранятся объекты C++, выделенные с помощью new. Здесь не надо заморачиваться.

4. Память под fixed-объекты и Очень Большие Объекты (LOH). Зависит от реализации менеджера памяти. Так как в моей реализации старшее поколение не является moving, то и fixed/LOH мы можем выделять сразу прямиком в старшем поколении.

Объекты из старшего поколения могут быть корнями для объектов из младшего поколения, но при малой сборке контр-продуктивно трейсить всю большую кучу. Поэтому VM использует понятие intergenerational-ссылок. При каждом store/load поля объекта, а так же при эвакуации, VM вставляет read/write-барьеры, которые проверяют условие: стал ли текущий объект ссылаться извне своего поколения? Если условие верно, то тогда используется схема под названием card marking. Старшее поколение имеет ещё дополнительный битмап: interGenBitmap. Каждые 1024 (например) байтов  индексируются одним байтом (не битом -- для скорости). Если существует intergenerational-ссылка в данном сегменте, то байт поставлен в 1, и наоборот. При малой сборке мусора данные сегменты целиком регистрируются как корни, что гораздо уменьшает диапазон поиска по сравнению с трейсингом всей кучи.

[Алексей Гринь]

Часть 7. Deployment.

User-end виртуальная машина не должна быть system-wide-компонентом, она должна быть настолько менее intrusive, насколько это возможно. Это исключает dll hell, свистопляски с CLASS_PATH и очень переносимо; если по какой-то причине VM сломалась (некорректная версия, баг и т.д.), то перестают работать не все приложения, а только одно. Если ставить на компактность и расширяемость, в таком случае копия виртуальной машины на каждую программу -- не беда, тем более что сейчас не 1996 год и память не проблема. Разумеется, JVM и .NET весят под десятки мегабайт, где громоздкие bloated-библиотеки связаны между собой в большую нераспутываемую гирлянду -- и там такое решение не прокатит. Но если иметь изначально компактный дизайн, то такое возможно -- вспомним, например, Visual Basic -- в нём вся виртуальная машина весила под мегабайт и могла распространяться одним простым dll в папке программы. Лучше и не придумаешь.
(Разумеется, девелоперская версия должна быть system wide.)

Поэтому я бы выделил три стандартных способа deployment:

1. Локальные виртуальные машины -- как описано выше: по виртуальной машине на каждую папку/программу; байткод-библиотеки желательно пострипены от неиспользуемых классов. Но этим мы не ограничиваемся: вводится понятие контейнеров. В Java единственный простой способ запустить программу -- это использовать консоль/ярлык с вызовом программы java.exe, что не совсем красиво (неправильно отображается в списке процессов). В C# используется куда лучший механизм, но он опирается на стандарты Windows, и под Unix всё равно приходится использовать ручной вызов. Так вот, контейнер -- это исполняемый stub-файл целевой платформы (под Windows -- *.exe), который распаковывает байткод и запускает виртуальную машину -- причём и виртуальная машина, и весь байткод могут быть как запакованы внутри контейнера, так и находится вне его.

2. Полная прекомпиляция. Большинство серьёзных программ устанавливаются через installer, и в таком случае не очень понятно, зачем вообще нужен JIT (кроме generic types в C#). Write once, run everywhere легко работает и без JIT'а: во время инсталяции можно делать не только распаковку байткода, но и полную компиляцию в машинный код. Далее байткод нужен только для метаданных; startup программ всегда мгновенный. В gentoo так и делают: при установке компилируют из исходников. И никто особо не нуждается в JIT-компиляции, а один и тот же си-код работает на разных платформах. Единственно что если поменялся процессор, то программа может сломаться. (В таком случае можно проверять процессор и ежли что просить переустановить программу?)

3. API-интерфейс для эмбеддинга в качестве скриптового языка.

[Python]

Полная прекомпиляция.

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

[Алексей Гринь]

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

Я же говорю про deployment, то есть конечный продукт, подаваемый пользователю. Там не предполагается, что байткод будет изменяться. JIT по идее нужен только в динамических сценариях, когда невозможно узнать заранее, какие типы будут использоваться (в C# это generic types и System.Reflection.Emit).

[Алексей Гринь]

Часть 8. Простейший escape analysis.

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

class Vector3f { public final int x, y, z; }

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

Когда автор физического движка JBullet занимался портированием с C++, он столкнулся с проблемой (тогда Java 5 была последней версией): при расчёте физических функций миллионы создаваемых векторов и матриц запускали сборку мусора так часто, что нормальное функционирование физического движка было просто невозможно. Автор решил эту проблемом хаком на уровне перекомпиляции скомпилированного байткода.

В C# это решили введением в виртуальную машину нового подтипа: value type objects, что значительно усложнило реализацию VM.

Чтобы превратить heap allocation в stack allocation, мы должны анализировать, в какие дали утекает ссылка на созданный объект. Если ссылка на объект не утекает дальше текущего метода/потока -- то есть в конечном счёте не может быть потенциально shared между разными потоками -- то объект можно без проблем очень быстро создать в стеке, и при выходе из метода просто "забыть" его. Чтобы анализатор не думал слишком долго -- глубина анализа не должна превышать два метода (текущий и вызываемый из текущего):

1) если из текущего метода (где создан объект) объект утекает в иной метод, то следует анализировать такой иной метод -- но дальше рекурсивно не идти (глубина = 2) и ежли что консервативно помечать "утекшим"
2) если в одном из анализируемых методов на объект используются операции вроде setstaticfield, setobjectfield, throw то объект считается безвозратно "утекшим"
3) если объект утекает в virtual-метод, то объект считается безвозратно "утекшим". Дело в том, что виртуальный метод может быть overriden в подклассе, и его реализация может быть совершенно не предсказуемая -- объект может утекать, а может не утекать -- наш статический анализатор не может предсказать.
4) если ни одно из указанных выше условий не оправдалось, то объект можно выделить "в стеке".

Так вот, мой простейший подход заключается в том, что автор иммутабельных классов должен следовать определённому контракту. Во-первых, чтобы сократить время анализа, анализатор ВООБЩЕ будет игнорировать классы, в которых есть хотя бы одно нескалярное поле. Во-вторых, критичные методы иммутабельного класса должны быть помечены как final и не переопределять родительских методов (т.е. не быть virtual). Поэтому автор иммутабельных классов должен иметь эти условия в виду: если хотя бы одно условие не выполнено, объект будет создаваться не в стеке, а в куче.
Эти условия легко выполнимы для критичных объектов вроде Vector3f или Matrix4f.

Пример объекта, выделяемого в стеке:
class Vector3f {
  public final int x, y, z;
  public final Vector3f add(Vector3f o) { return new Vector3f(x + o.x, y + o.y, z + o.z); }
  /* .. */
}

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