Виртуальная машина

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

Запуск

При запуске программы corewar в качестве аргументов мы указываем .cor файлы чемпионов, которые примут участие в битве:

$ ./corewar batman.cor ant-man.cor iron_man.cor

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

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

Для нее три Batman'а это Player 1, Player 2 и Player 3.

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

То есть в виртуальную машину не может быть загружено больше 4 игроков за один раз.

Флаг -n

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

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

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

-n number sets the number of the next player. If non-existent, the player will have the next available number in the order of the parameters.

То есть в случае запуска данной команды ...:

$ ./corewar batman.cor -n 1 ant-man.cor iron_man.cor

... Ant-Man станет Player 1, Batman — Player 2, а Iron Man — Player 3.

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

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

Валидация

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

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

# define MEM_SIZE           (4 * 1024)
// ...
# define CHAMP_MAX_SIZE     (MEM_SIZE / 6)

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

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

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

Инициализация арены

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

Размер арены в байтах определяет константа MEM_SIZE, значение которой в примере равно 4096.

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

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

4096 / 3 = 1365

То есть код первого игрока будет располагаться начиная с нулевой ячейки памяти и далее. Код второго — с 1365-ой ячейки. А третьего — с 2730-ой.

Организация памяти

Память в виртуальной машине организована по принципу кольца или петли. То есть за последней ячейкой следует первая.

И если общий объем памяти составляет 4096 ячеек, то номер первой ячейки будет равен 0, а последней — 4095.

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

Игровые параметры

Также перед началом работы нужно установить значение следующих переменных:

• игрок, о котором в последний раз сказали, что он жив

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

• количество прошедших с начала игры циклов
• количество выполненных операций live за последний период, длинной в cycles_to_die
• cycles_to_die — длительность периода до проверки

Инициализируется значением константы CYCLES_TO_DIE, которое равно 1536.

• количество проведенных проверок

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

Инициализация кареток

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

Внутри неё содержатся следующие данные:

• уникальный номер каретки
• carry

Флаг, который могут изменять некоторые операции. Изначально его значение равно false.

• код операции, на которой стоит каретка.

До начала битвы значение этой переменной не установлено.

• цикл, в котором в последний раз была выполнена операция live
• количество циклов, оставшиеся до исполнения операции, на которой стоит каретка
• текущая позиция каретки
• количество байт, которые нужно будет «перешагнуть», чтобы оказаться на следующей операции
• регистры, количество которых задано в константе REG_NUMBER

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

Важно понимать, что каретка не работает на конкретного игрока.

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

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

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

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

Список кареток

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

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

Cursor 3 (Player 3)
        |
        V
Cursor 2 (Player 2)
        |
        V
Cursor 1 (Player 1)

На этом все подготовительные работы можно считать оконченными.

Представление игроков

Перед началом битвы полученных игроков-чемпионов необходимо объявить:

Introducing contestants...
* Player 1, weighing 22 bytes, "Batman" ("This city needs me") !
* Player 2, weighing 12 bytes, "Ant-Man" ("So small") !
* Player 3, weighing 28 bytes, "Iron Man" ("Jarvis, check all systems!") !

Битва

Правила битвы

Одной из самых важных переменных в сражении является количество циклов, прошедших после старта.

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

Битва продолжается до тех пор, пока остается хотя бы одна живая каретка.

То есть каретка может умереть или её может кто-то убить?

Да, каретка может погибнуть. Это происходит во время такого события как проверка.

Проверка

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

Во время этой проверки каретки, которые являются мертвыми, удаляются из списка.

Как определить, что каретка мертва?

Мертвой считается каретка, которая выполняла операцию live cycles_to_die циклов назад или более.

Также мертвой считается любая каретка, если cycles_to_die <= 0.

Кроме удаления кареток во время проверки происходит модификация значения cycles_to_die.

Если количество выполненных за cycles_to_die период операций live больше или равно NBR_LIVE, значение cycles_to_die уменьшается на CYCLE_DELTA.

Значение константы NBR_LIVE в предоставленном файле равно 21, а значение CYCLE_DELTA — 50.

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

Если MAX_CHECKS проверок спустя значение cycles_to_die не изменится, то оно будет принудительно уменьшено на значение CYCLE_DELTA.

Значение MAX_CHECKS в файле-примере op.h равно 10.

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

Циклы	Количество операций live	cycles_to_die	Текущее количество проверок
1536	5	1536	1
3072	193	1536 -> 1486	2
4558	537	1486 -> 1436	1
5994	1277	1436 -> 1386	1
7380	2314	1386 -> 1336	1
8716	3395	1336 -> 1286	1
...	...	...	...

Количество операций live обнуляется после каждой проверки вне зависимости от ее результатов.

«Текущее количество проверок» включает и проводящуюся в данный момент проверку.

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

Циклы	Количество операций live	cycles_to_die	Текущее количество проверок
...	...	...	...
24244	41437	136 -> 86	1
24330	25843	86 -> 36	1
24366	10846	36 -> -14	1
24367	186	-14 -> -64	1

Такие данные можно получить во время выполнения чемпиона Jinx, который находиться в архиве vm_champs.tar по пути champs/championships/2014/rabid-on/.

Внутри цикла

Теперь давайте подробнее рассмотрим, что происходит внутри цикла.

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

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

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

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

Во время самого первого цикла исполнения все каретки без исключения будут получать значения кода операции. Так как при инициализации он не устанавливается.

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

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

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

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

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

Но если считанное число не попадает в диапазон [0x01; 0x10], то есть полученный код указывает на несуществующую операцию? Как быть в такой ситуации?

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

Уменьшить количество циклов до исполнения

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

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

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

Если бы существовала операция со всего одним циклом ожидания, то она также была бы выполнена во время этого одного цикла.

Выполнить операцию

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

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

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

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

Если же код операции ошибочен, необходимо просто переместить каретку на следующий байт.

Если с самим кодом все нормально, но код типов аргументов или же номер регистра ошибочен, нужно пропустить данную операцию вместе с кодом типов аргументов и самими аргументами.

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

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

Именно поэтому в таблице операций были указаны размеры аргументов T_DIR даже для тех операций, которые такие аргументы не принимают.

Допустим код нашей операций равен 0x04:

Код операции	Имя операции	Аргумент #1	Аргумент #2	Аргумент #3
4	add	T_REG	T_REG	T_REG

Но значение байта, содержащего типы аргументов, равно 0xb6:

Аргумент #1	Аргумент #2	Аргумент #3	—
10	11	01	10
T_DIR	T_IND	T_REG	T_DIR

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

После недолгих подсчетов мы узнаем, что в данной ситуации нужно пропустить следующие 9 байт: код операции (1 байт) + байт с типами (1 байт) + Аргумент типа T_DIR (4 байта) + Аргумент типа T_IND (2 байт) + Аргумент типа T_REG (1 байт).

Флаг -dump

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

Суть его работы описывается в тексте задания следующими строками:

-dump nbr_cycles

at the end of nbr_cycles of executions, dump the memory on the standard output and quit the game. The memory must be dumped in the hexadecimal format with 32 octets per line.

Аналог данного флага присутствует и в оригинальной виртуальной машине. Только под другим именем — -d.

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

Флаг -d выводит значения 64 октетов в ряд. А флаг -dump — всего 32 октетов.