![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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, доступен для использования. Это явно неспроста.
Представьте себе программу, записываемую в виде байт-кода, разбитого на слова по 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, доступен для использования. Это явно неспроста.
