По следам наших выступлений, или Brainfuck по-советски

[spamsink]

Почти три года назад я писал про систему нижнего уровня базы данных, которая работала с помощью микрокоманд. За прошедшие три года я с ней практически разобрался, и с точки зрения структуры данных она ничего особенного не представляет. Ну B+tree, ну записи с возможностью фрагментации на экстенты, ну иерархичность. В этом посте речь пойдёт про механизм работы микрокоманд, подобного которому я раньше не встречал. Дальше много технических деталей.



Представьте себе программу, записываемую в виде байт-кода, разбитого на слова по 8 байт в каждом. Для удобства пользователей код 00 - NOP.

У виртуальной машины, которая исполняет этот байт-код, есть 64 регистра, у большинства из которых назначение фиксировано (потому что практически все команды работы с данными не имеют операндов, а извлекают данные и пишут результаты в конкретные регистры - так, например, по ссылке выше коды 14 и 15 выполняют сравнение двух фиксированных регистров, содержимое которых "искомый ключ" и "найденный ключ"). Доступны для произвольного применения от силы полдюжины.

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

Для выполнения программ, состоящих из более чем 8 команд, существует команда CHAIN nn с аргументом (следующим за ней байтом), означающим номер регистра, в котором находится указатель на следующее командное слово. По этой команде происходит IW = *R[nn]++ и выполнение только что измененного командного слова начинается с первой команды в нём. Регистр 00 доступен для этой команды; если байт-код CHAIN - последний в слове, то считается, что его операнд - 00.

Таким образом, линейные программы любой разумной длины выполняются, например, с помощью IW = CHAIN; R[0] = program; start, где program - массив слов, в каждом из которых может быть вплоть до 7 полезных байт-кодов, а последний (или последний ненулевой) байт-код - CHAIN. Кроме последнего слова программы, разумеется.

Также из простых команд имеется команда LOOP - начать выполнение IW сначала, команда ASSIGN aa bb, делающая R[aa] = R[bb], команда SKIP - пропустить следующий байт-код, и команда STOP - завершить выполнение программы.

Пример использования команды STOP: последовательность кодов в микропрограмме модификации записи по ссылке выше FIND NOMATCH NOP (ALLOC INSERT STOP) UPDATE. В скобках - команды, которые выполняются если FIND не нашел запись с искомым ключом; тогда в базе резервируется место для содержимого записи и переписываются данные (ALLOC), связываются со вставляемым ключом (INSERT), и хорош. Иначе выполняется только UPDATE: новые данные переписываются в поле данных найденной записи с искомым ключом.

Команд, имеющих хоть какое-то условное действие, не так много. Упомянутые выше команды 14 (MATCH) и 15 (NOMATCH) выполняются так: если регистры KEY и CURKEY равны/неравны (MATCH/NOMATCH), то продолжить выполнение как ни в чём не бывало; если же условие не выполнено, а следующая команда - NOP, и за ней ещё есть ненулевые команды, то пропустить этот NOP и ещё 3 байт-кода; иначе диагностировать ошибку.
Так же работают и команды инкремента/декремента итератора по базе.

Ещё есть команда сравнения содержимого базы с памятью, которая при несовпадении пропускает 1 байт-код (надо думать, ради CMP CHAIN NOP ... - переход на следующее слово по совпадению, CMP SKIP CHAIN NOP ... - переход по несовпадению), и команда, которая при некотором условии пропускает 4 байт-кода.

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

Казалось бы, и что? Как из этих даже нескольких счетчиков адреса команды можно сделать что-то обобщённое, если команда LOOP работает только в пределах одного командного слова? А вот как: ещё есть команда LOADINC xx yy, которая делает ++R[yy]; R[xx] = *(R[yy]-1); и с её помощью (главное, с помощью магической самоссылающейся LOADINC xx xx), насколько я понимаю, можно организовать передачи управления произвольного вида.

Вопрос вот в чём. Кто-нибудь видел где-нибудь что-нибудь подобное?

Безотносительно к ответу на предыдущий вопрос, есть ли идеи, как преобразовывать control flow произвольного вида в набор массивов для CHAIN и LOADINC, чтобы не корпеть над ручным программированием на этих палках и верёвках?

Ах да, самое главное не сказал: регистр с номером, совпадающим с байт-кодом LOADINC, доступен для использования. Это явно неспроста.

Comments

[sab123]

Как работает LOADINC, я так и не понял. Ну, читает слово по адресу, а как переход-то? Или это имеется в виду, что LOADINC читает следующий указатель на слово из вектора указателей, на который потом идет CHAIN?

А напоминает это ранний Бейсик или Фортран. Для команд скорее всего был какой-нибудь компилятор?

Кстати, не одно ли и то же ли (++R[yy]-1) и R[yy]++ ?

[spamsink]

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

В нотации R[xx] = *R[xx]++ для команды LOADINC xx xx имеется неоднозначность, поэтому для правой части используется запись с преинкрементом, разрешающая эту неоднозначность.

[sab123]

По поводу неоднозначности, мне кажется, что в стандартном Си неоднозначность будет и так и так. Но тут у нас не Си, поэтому можно определить удобный нам порядок выполнения. В частности, в PDP-11 операция "MOV (R1)+, R1" имела порядок выполнения, в котором автоинкремент выполнялся до присваивания. И, кстати, вроде и в до-стандартном компиляторе Си - де-факто "x = *x++" тоже имело такой порядок выполнения.

[spamsink]

Твоя правда, говорит godbolt.org. Исправляю.

[spamsink]

Был ли компилятор, я не знаю. Но если можно написать компилятор для Brainfuck, то, наверное, и для этой системы можно.

[sab123]

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

[spamsink]

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

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

[spamsink]

Я всё понял! Чувак изобрёл ROP за 20+ лет до того, как security hackers его изобрели и доказали Тьюринг-полноту. Раз существуют ROP compilers, то, должно быть, написать компилятор для этой штуки не должно быть непреодолимо сложно. А вот написал ли подобный компилятор сам изобретатель, или компилировал вручную, пока тайна - издания по теме находятся только в упоминаниях литературы на гуглобуксах, но не в библиотеках.

[sab123]

Фортовский "шитый код" - тоже аналогичная конструкция.

[spamsink]

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

[sab123]

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

[spamsink]

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