Горе от ума, или как я писал виртуальную машину на C# / Habr

Предисловие

Привет.

Эта статья будет в, наверное, не совсем привычном формате — вместе с техническими деталями, я бы хотел поделиться личной историей, как я до такого ~~докатился~~ додумался, чтобы на C# пытаться делать настолько узкоспециализированную технологию. Поделюсь опытом, моментами реализации виртуальной машины, памяти и другого интересного.

История

Наверное, у каждого есть какая‑то собственная наработка, которую вы таскаете из проекта в проект? У меня тоже есть — скриптовый язык DamnScript, только ситуация немного иная... Я не таскаю его, а каждый раз реализую по‑новому. История началась несколько лет назад, когда мне впервые потребовалось нечто вроде языка из Ren'Py, на котором было бы удобно делать асинхронную логику для игровых объектов, а так же иметь возможность сохранить прогресс выполнения, с возможностью последующей загрузки.

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

Пример такого скрипта:

region Main {
  SetTextAndTitle "Text" "Title";
  GoToFrom GetActorPosition GetPointPosition "Point1";
}

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

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

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

Проблемы начали всплывать чуть позже: методы начали очень быстро плодиться. Вполне существовало 5 оберток на один и тот же метод с разными названиями, потому что если в методе указано 5 аргументов — значит, будь добр, дай 5 аргументов. Даже если тебе нужно передать только первые 2, в то время как остальныe оставить стандартными значениями.

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

Та версия была доведена до стабильности и оставлена как есть, а я сел за новую версию.

Лучше, но недостаточно

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

Синтаксис должен позволять указывать конкретное количество аргументов, чтобы избежать названия, а-ля GetItem1, GetItem2, GetItem3, в зависимости от количества аргументов, которые принимает нативный метод.
Должна быть возможность вызова не только статических методов.
Нужно что-то решить с постоянными аллокациями массивов (что такое ArraySegment я тогда даже не подозревал, но были свои мысли и идеи .-.).
Общее улучшение производительности.

Сразу откинул идею ~~кустарного~~ своего парсера и начал смотреть, какие доступные фреймворки есть, так как мне хотелось больше заниматься runtime частью, а не писать утилиты для синтаксических деревьев. Очень быстро наткнулся на ANTLR — сначала показался сложным (кому вообще легко писать regex‑like код?), но постепенно втянулся.

Был улучшен синтаксис, который приближался к нечто С-подобному:

region Main {
  GoTo(GetPoint("A12"));
  GetActor().Die();
}

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

К сожалению, тогда мне так и не удалось справиться с боксингом структур. Всё упиралось в то, что MethodInfo.Invoke требовал передавать все аргументы в виде System.Object[], и обойти это было никак нельзя. Реализовать вызов через делегаты тоже не представлялось возможным: чтобы использовать generic‑делегат, нужно было заранее знать типы аргументов метода, а значит — передавать их явно через входящий тип. Без использования generic всё превращалось в ту же проблему — аргументы снова приходилось пихать в System.Object[]. Получалось просто «шило на мыло».

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

В итоге у меня получилось:

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

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

Спасибо, C#, за стандарт, но я как-нибудь сам

Началось все с того, что мне удалось в боевых условиях пощупать delegate*<T>. Если раньше я не видел в нем никакого смысла, то сейчас что‑то в моей голове щелкнуло...

C# разрешает использовать указатели на методы, если они статические. Но статический от не статического отличается лишь тем, что первым аргументом всегда передается ссылка на this. И тут мне стало интересно, можно ли провернуть такой трюк: как‑то взять указатель на экземпляр, далее взять указатель на не статический метод...

Спойлер: да, получилось!

Разбираться с тем, как взять указатель на экземпляр долго не пришлось — я уже как‑то писал об этом статью, поэтому быстро слепился такой код:

public unsafe class Test
{
	public string name;
	
	public void Print() => Console.WriteLine(name);
	
	public static void Call()
	{
		var test = new Test { name = "test" };
		
		var thisPtr = *(void**)Unsafe.AsPointer(ref test); // Здесь мы получаем указатель на ссылку, надо разыменовать
		var methodInfo = typeof(Test).GetMethod("Print"); // Получаем MethodInfo
		var methodPtr = (delegate*<void*, void>)methodInfo!.MethodHandle.GetFunctionPointer().ToPointer(); // Получаем указатель на метод
		methodPtr(thisPtr); // Магия - передаем первым аргументом указатель на экземпляр и получаем в консоль выведенный текст "test"
	}
}

Шестеренки начали вращаться все сильнее. Больше нет привязки в конкретному типу делегата, я могу кастовать его как удобно, благо указатели позволяют такое делать. Но это не отменяет проблемы того, что все значимые типы нужно учитывать заранее, так как передаваться они будут по значению, соответственно, компилятор должен знать, сколько места выделить на стеке. Хорошая идея пришла быстро — почему бы не сделать структуру, которая будет иметь фиксированный размер и использовать в аргументах лишь ее? Так получилась структура ScriptValue:

[StructLayout(LayoutKind.Explicit)]
public unsafe struct ScriptValue
{
	[FieldOffset(0)] public bool boolValue;
	[FieldOffset(0)] public byte byteValue;
	[FieldOffset(0)] public sbyte sbyteValue;
	[FieldOffset(0)] public short shortValue;
	[FieldOffset(0)] public ushort ushortValue;
	[FieldOffset(0)] public int intValue;
	[FieldOffset(0)] public uint uintValue;
	[FieldOffset(0)] public long longValue;
	[FieldOffset(0)] public ulong ulongValue;
	[FieldOffset(0)] public float floatValue;
	[FieldOffset(0)] public double doubleValue;
	[FieldOffset(0)] public char charValue;
	[FieldOffset(0)] public void* pointerValue;
}

Имея фиксированный размер, она работает как union — внутрь можно что‑то положить, и это что‑то затем достать.

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

По максимум избавиться от боксинга структур.
Минимизировать количество managed аллокаций и, соответственно, нагрузку на GC.
Сделать компиляцию в байткод и виртуальную машину, которая будет исполнять его, а не просто интерпретировать на лету рандомные строки.
Помимо JIT сделать AOT компиляцию, которая заранее скомпилирует скрипт в байткод.
Поддержка .NET и Unity (здесь это нужно выделить как отдельную вещь, так как уже давно в Unity есть свою нюансы).
Сделать два вида API: простой официальный, но с накладными расходами, и сложный неофициальный, с минимальными накладными расходами, но высоким порогом входа.
Выпустить проект в open‑source и не сгореть со стыда:)

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

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

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

И вырисовывался такой подход:

[Виртуальная машина (которая, по сути, является хранилищем внутренних потоков)]
└──► [Поток 1]
      └──► Свой стек
└──► [Поток 2]
      └──► Свой стек
└──► [Поток 3]
      └──► Свой стек
...

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

В качестве опкодов я придумал самую простую структуру:

[4b номер опкода][4b? опциональные данные]
[________________________________________] - 8 байт с выравниванием

Любой опкод имеет фиксированную длинну 8 байт: первые 4 — это номер опкода, а 4 оставшиеся — опциональные данные (которых может и не быть, но размер при выраванивании останется 8 байт), нужные для его вызова. При желании можно отключить выравание опкодов до 8 байт и уменьшить размер номера опкода с 4 байт до 1, что может снизить затраты памяти на хранение скрипта (20%-40%), но ухудшит работу с памятью, поэтому решил оставить это опциональной фичой.

Дальше пошла фантазия на то, какие опкоды нужны. Оказалось, что буквально 12 штук, которых, спустя почти год, все еще хватает:

CALL — вызов нативного метода по имени (чуть подробнее далее).
PUSH — запушить на стек значение.
EXPCALL — сделать вызов выражения (сложение, вычетания и т. д.), а результат запушить на стек.
SAVE — сделай точку сохранения (как и в прошлых итерациях, достаточно запомнить место последнего полного вызовы и при загрузке начать выполнение с этого места).
JNE — прыгнуть на указанный абсолютный адрес, если два крайних значения на стеке не равны.
JE — прыгнуть на указанный абсолютный адрес, если два крайних значения на стеке равны.
STP — установить параметры для потока (так и не были реализованы, но есть некоторые идеи на их счет).
PUSHSTR — запушить на стек строку (о них чуть попозже).
JMP — прыгнуть на указанный абсолютный адрес.
STORE — записать значение в регистр. Кажется, я говорил, что машина стековая?.. Походу дела этого стало недостаточно, но описывать там практически нечего — для реализации циклов потребовалось хранить значение так, чтобы чтение не удаляло его. Для этой задачи было выделено 4 регистра внутри каждого потока. Работает. И как это сделать лучше — идей пока нет.
LOAD — взять значение из регистра и запушить на стек.
DPL — продублировать значение на стеке.

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

Про PUSHSTR и CALL хочу поговорить отдельно — как я уже упоминал, на аргументы для опкода выделено 4 байта, как тогда можно работать со строками? Тут на помощь пришло интернирование строк. Они не хранятся напрямую в байткоде, для этого компилятор генерирует отдельную таблицу метаданных, где лежат все строки и имена методов, опкод владеет лишь индексом в этой таблице. Таким образом, PUSHSTR нужен, чтобы запушить именно указатель на значение строки из таблицы (так как PUSH запушил бы только ее индекс), а CALL в первых 3 байтах хранит индекс метода, а последним — количество аргументов. Более того: это еще и подарило экономию памяти — если в байткоде вызов одного и того же метода повторяется много раз, то его имя не будет дублировано.

И все шло хорошо своих чередом, пока проект не начал усложняться...

Первые проблемы

С первой проблемой я столкнулся во время тестов: CLR GC умеет двигать объекты в памяти. Соответственно, если использовать указатель на ссылку в асинхронном методе, провести аллокацию, то есть не иллюзорный шанс, что указатель станет невалидным. Эта проблемы не актуальна для Unity, ибо местный GC не умеет в дефрагментацию, но так, как задачу я себе поставил сделать кроссплатформенность — надо что‑то с этим делать. Надо запретить GC двигать объект в памяти, для этого можно использовать систему пинов из GCHandle... Но эта штука не работает, если в классе есть ссылки. Соответственно, нужно как‑то делать по‑другому... И, перепробовав несколько вариантов, я пришел к одному, который, на данный момент, работает хорошо — сохранять ссылку внутри массива, возвращая ее индекс. В таком подходе мы не запрещаем двигать объект в памяти, но и оперируем им не совсем как ссылкой. Однако можно получить его временный адрес и такого «закрепления» полностью хватает, чтобы передавать managed объекты, как аргументы или возвращаемые значения.

Записать напрямую ссылку в структуру нельзя, так как она должна оставаться unmanaged! Для такого метода закрепления был сделан достаточно быстрый поиск свободного слота и переиспользование освободившихся, а так же методы защиты от повторного открепления и проверки на то, что закрепление не «протухло».

Благодаря этому, со структурой ScriptValue осталась возможность работать в виде указателя, что для меня было очень важно, а внутрь нее добавилось еще одно поле:

[FieldOffset(0)] public PinHandle safeValue;

Однако сразу после внедрения пинов встала другая проблема — теперь, помимо примитивов и указателей, ScriptValue может хранить специальную структуру, которая и не совсем примитив, и не указатель, ее надо обрабатывать отдельно, чтобы получить искомое значения. Разумеется, можно отдать это на откуп функции — пусть она сама знает, какой тип в нее должен прийти... Но это звучит совсем не круто — если надо будет в одном случае передать закрепленное значение, а в другом хватит и указателя? Надо вводить какой‑то тип для конкретного значения внутри ScriptValue. Из этого следует следующая enum запись:

public enum ValueType
{
	Invalid,
           
	Integer,
            
	Float32,
	Float64,
            
	Pointer,
	FreedPointer,
            
	NativeStringPointer,
    
	ReferenceUnsafePointer,
			
	ReferenceSafePointer,
	ReferenceUnpinnedSafePointer,
}

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

public T GetReference<T>() where T : class => type switch
		{
			ValueType.ReferenceSafePointer => GetReferencePin<T>(),
			ValueType.ReferenceUnsafePointer => GetReferenceUnsafe<T>(),
			_ => throw new NotSupportedException("For GetReference use only " +
			                                     $"{nameof(ValueType.ReferenceSafePointer)} or " +
			                                     $"{nameof(ValueType.ReferenceUnsafePointer)}!")
		};

Пару слов о строках: для них так же используется своя структура — по сути, тот же подход, что и System.String: структура, которая имеет в себе поля length и data. А так же не фиксированный размер, который определяется:

var size = 4 + length * 2; // sizeof(int) + length * sizeof(char)

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

Так же пару слов про числа: их так же получилось несколько видов. Если для того, что сохранить 32 битное число, мы легко может указать longValue = intValue;, а затем и byteValue и все другие члены union будут иметь то же значение, то с float32 и float64 такой магии не будет - они хранятся в памяти по-разному. Поэтому стало необходимо различать их все друг от друга и, если мы хотим во что бы то ни стало, получить float64 значение, то надо его безопасно конвертировать, если изначально оно было, например, int64.

Где-то здесь разработка пошла на ура. Фичи писались, безопасность улучшалась и я даже подумал, что самое сложное я уже решил и дальше только улучшения... Пока я не решил добавить авто прохождение Unit тестов после пуша в GitHub. Стоит упомянуть то, что разработку я веду на ARM64 (Mac M1), это важная деталь. Несколько Unit тестов уже были готовы, они покрывали некоторые моменты виртуальной машины, проверки на безопасность и функционал. На моем ПК они были пройдены на 100%.

День X, я запускаю проверку через GitHub Actions на Windows... И получаю NullReferenceException, думая о том, что баг не займет больше часа, я медленно спускался в кроличью нору под названием «соглашение вызовов»...

Кара за самоуправство

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

public ScriptValue Simulate(ScriptValue value1, ScriptValue value2, ScriptValue value3, ScriptValue value4, 
			ScriptValue value5, ScriptValue value6, ScriptValue value7, ScriptValue value8, ScriptValue value9)
{
	Value += value1.intValue + value2.intValue + value3.intValue + value4.intValue +
	         value5.intValue + value6.intValue + value7.intValue + value8.intValue + value9.intValue;
	return ScriptValue.FromReferenceUnsafe(this);
}

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

public void TestManagedPrint()
{
    Console.WriteLine($"Hello! I'm {name}, {age} y.o.");
    if (parent != null)
        Console.WriteLine($"My parent is {parent.name}");
}

Значит проблема в чем-то другом...

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

Если метод вызывается через delegate*.
Если метод не статический.
Если метод возвращает значение, которое > машинного слова.
Если операционная система Windows X64

Толомается указатель на this, который передается первым аргументом. Следующий вопрос был — почему ломается? И, если честно, четкого на 100% ответа я не смог сформулировать, потому как, что‑то мне подсказывает, что где‑то я мог неправильно понять. Если вы заметите ошибку — сообщите, пожалуйста, об этом мне — буду рад узнать точнее.

А теперь следите за пальцами: так как разработка велась на MacOS ARM64, где, по соглашению вызовов, если возвращаемая структура больше 8 байт, но меньше 16, то возвращаемое значение будет разделено на две части — одна из них пойдет в регистр x0, вторая в x1. Несмотря на то, что в эти же два регистра придут аргументы при вызове метода, в них же потом будет записан результат, эдакое переиспользование.

Но Windows X64...
Если возвращаемое значение более 8 байт, то первым аргументом (в регистр rcx) пойдет указатель на область стека, которую аллоцировал вызывающий метод, где будет размещен результат. А помните, как происходит __thiscall? Первым аргументом идет указатель на this, а первый аргумент какой? rcx — верно. И вот, как я понял и наэксперементировал, .NET просто не умеет обрабатывать такие случаи, из‑за чего, собственно, ломался указатель.

Это хорошо, а что теперь делать то с этим? Пришлось думать, как заменять значимый тип на указатель, чтобы результат всегда возвращался через rax. На самом деле, это было не так уж и сложно - в структуру потока добавился еще один стек, только для аргументов. Еще один, потому что я не хотел нарушать правило того, что 1 значение на стеке = 1 чтение, а для них нужно постоянное хранилище, так как в асинхронном методе их использование может быть отложено на неопределенное время. Немного трудно пришлось с возвращаемым значением, а если быть точнее, опять с асинхронными методами. Так как результат пишется в указатель, надо где-то держать И место для возвращаемого значения, И указатель для него. Не придумал ничего лучше, кроме как в структуру потока добавить ЕЩЕ одно поле, которое используется как возвращаемое значение :).

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

public ScriptValuePtr Simulate(ScriptValuePtr value1, ScriptValuePtr value2, ScriptValuePtr value3, ScriptValuePtr value4, 
			ScriptValuePtr value5, ScriptValuePtr value6, ScriptValuePtr value7, ScriptValuePtr value8, ScriptValuePtr value9)
{
	Value += value1.IntValue + value2.IntValue + value3.IntValue + value4.IntValue +
		value5.IntValue + value6.IntValue + value7.IntValue + value8.IntValue + value9.IntValue;
	return ScriptValue.FromReferenceUnsafe(this).Return();
}

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

public async Task<ScriptValuePtr> SimulateAsync(ScriptValuePtr value1, ScriptValuePtr value2, ScriptValuePtr value3, ScriptValuePtr value4, 
			ScriptValuePtr value5, ScriptValuePtr value6, ScriptValuePtr value7, ScriptValuePtr value8, ScriptValuePtr value9)
{
	var handle = ScriptEngine.CurrentThreadHandle;
	await Task.Delay(100);
	Value += value1.IntValue + value2.IntValue + value3.IntValue + value4.IntValue +
			      value5.IntValue + value6.IntValue + value7.IntValue + value8.IntValue + value9.IntValue;
	return ScriptValue.FromReferencePin(this).ReturnAsync(handle);
}

Послесловие

И это еще далеко не все нюансы, с которыми я столкнулся.

В качестве какого‑то резюме, я бы хотел сказать, что если бы мне не хотелось иметь нативную поддержку скриптов внутри Unity, я бы никогда не взял для такого дела C#, столько уж он палок в колеса вставил... Для любого, хоть сколько‑нибудь, низкоуровневого кода нужен старый добрый C/C++, и ничего больше.

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

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

Большое спасибо за внимание! Вы так же можете наблюдать за проектом на GitHub - DamnScript.