Гайд Разбираем устройство скомпилированных Lua-скриптов

Предисловие
Пишу этот гайд, так как нормального описания устройства LuaJIT-Байткода(иначе, .luac файлов) не нашёл, но всё-таки разобрался в этой теме, используя исходники LuaJIT.
Просто хочу донести до вас информацию относительно простым языком, потому что далеко не каждый захочет лезть в страшные дебри Си и разбирать код
Так-же в данном гайде будет небольшая информация о устройстве Lua, что может быть полезно для общего развития.
Гайд довольно длинный, так что запасайтесь терпением, и вперёд!

---

Думаю, для начала стоит немного рассказать про внутреннее устройство Lua, и LuaJIT в частности.
При разборе LuaJIT-Байткода довольно часто будет возникать такой термин, как Прототип функции(proto).
Данный прототип из себя представляет не более чем просто структуру с данными о будущей функции, но не содержит самой функции, как бы шаблон, по которому LuaJIT в дальнейшем создаст функцию. Вникать в то, как устроены прототипы изнутри и какую информацию содержат не имеет смысла, потому что данная информация в основном нужна только LuaJIT, для правильного запуска кода.
Еще подмечу, что Global Chunk тоже является прототипом, и расположен в самом конце списка прототипов в файле.

Так-же LuaJIT довольно часто(если честно, везде, где это возможно) использует данные в формате ULEB128. Хоть данный гайд не про форматы записи данных, всё-таки стоит разобрать данный формат.

Если кратко, ULEB128 позволяет экономить место при записи 32-битных чисел.
Достигается это таким образом:

Каждый байт данных содержит 7 нижних бит полезной информации(которые правее), и 1 старший бит(самый левый), который указывает, нужно ли считывать следующий байт.
Представить ULEB128 можно примерно вот так:

MSB                    LSB ; MSB - Старшие байты(правые), LSB - Младшие(левые)
10100011 11101001 01110111 ; Байты в памяти
 0100011  1101001  1110111 ; Полезные данные
 
Попытаемся считать данные

Смотрим первый байт(10100011)
Берём полезную нагрузку(0100011)
Старший бит равен 1, значит, считываем следующий байт

Смотрим второй байт(11101001)
Берём полезную нагрузку(1101001)
Соединяем данные из второго байта с данными из первого(
    (1101001 << 7 = 11010010000000) |
    (0100011)
) = 11010010100011

И повторяем данные операции, пока не считаем все данные(пока старший бит не будет равен 0)

Надеюсь, с ULEB128 всё понятно

Задевать тему upvalue я не буду, так как они описаны в PIL

Думаю, можно уже начать разбирать сам .luac файл.
Вперёд, в дебри байтов!

---

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

Спойлер: Структура байткода

Немного описания:

{name} - "Переменная" с именем `name`, ищите определение в структуре(определение: name=...)
(type:name) - Вещественная часть байткода с типом type
[if (cond) then ...] - Если (cond) верно, то часть байткода ... будет в нём присутствовать, иначе, просто пропускается
\xHH - HEX-Значение HH

{magic}{header}{proto[]}\x00
header=(version:BYTE)(flags:ULEB128)[if !(flags & BCDUMP_F_STRIP) then (chunkname_len:ULEB128)(chunkname:BYTE[chunkname_len])]
proto={proto_head}(bytecode:INT32[sizebc])(uvdata:INT16[sizeuv]){constants}[if !(flags & BCDUMP_F_STRIP) then (debug:BYTE[sizedbg])]
proto_head=(proto_len:ULEB128)(pflags:BYTE)
   (numparams:BYTE)(framesize:BYTE)
   (sizeuv:BYTE)(sizekgc:ULEB128)(sizekn:ULEB128)(sizebc:ULEB128)
   [if !(flags & BCDUMP_F_STRIP) then (sizedbg:ULEB128)
      [if (sizedbg != 0) then (firstline:ULEB128)(numline:ULEB128)]
   ]
constants={kgc[sizekgc]}{knum[sizekn]}
kgc=(kgctype:ULEB128){kgcvalue}
knum=(low:ULEB128_33)[if (low_LOWEST_BIT) then (high:ULEB128)]
kgcvalue= ... # Depends by type(TYPE)

kgcvalue[if TYPE>=BCDUMP_KGC_STR]=(kgcbuffer:BYTE[TYPE-BCDUMP_KGC_STR])
kgcvalue[if TYPE==BCDUMP_KGC_TAB]={ktab}
kgcvalue[if TYPE==BCDUMP_KGC_COMPLEX]=(low:ULEB128)(high:ULEB128)(ilow:ULEB128)(ihigh:ULEB128)
kgcvalue[if TYPE==BCDUMP_KGC_CHILD]=NONE # idk how it works, so just ignore this
kgcvalue[else]=(low:ULEB128)(high:ULEB128)

ktab=(karray_len:ULEB128)(khash_len:ULEB128){karray[karray_len]}{khash[khash_len]}
karray={ktabk} # Value
khash={ktabk}{ktabk} # Key, Value
ktabk=(ktabktype:ULEB128){ktabkvalue}

ktabkvalue= ... # Depends by type(TYPE)
ktabkvalue[if TYPE>=BCDUMP_KTAB_STR]=(ktabkbuffer:BYTE[TYPE-BCDUMP_KTAB_STR])
ktabkvalue[if TYPE==BCDUMP_KTAB_INT]=(intv:ULEB128)
ktabkvalue[if TYPE==BCDUMP_KTAB_NUM]=(low:ULEB128)(high:ULEB128)
ktabkvalue[else]=NONE # Internal constant, check description

magic=\x1B\x4C\x4A

Что-же, перейдём к самому описанию байткода

В самом начале любого .luac файла находятся так называемые magic-байты(магические байты), которые представляют собой 3 байта: \x1B\x4C\x4A.
Они позволяют понять, имеет ли файл нужный нам формат.

Сразу за magic-байтами располагается header(заголовок) файла, который хранит основную информацию о файле.

В первом байте заголовка хранится версия байт-кода. Последняя версия на момент написания = 1.
За версией следуют флаги файла, в формате ULEB-128(на данный момент флагов всего 3, так что можно просто считывать байт)
Есть 3 доступных флага:

1. BCDUMP_F_BE(1) - Указывает, находится ли исполняемый код и upvalues в порядке Big-Endien
2. BCDUMP_F_STRIP(2) - Указывает, что в файле нету Debug-Информации(в 99% случаев он включен)
3. BCDUMP_F_FFI(4) - Указывает, загружать ли модуль FFI сразу после загрузки файла

Зачастую, включен только флаг BCDUMP_F_STRIP, поэтому разбирать как хранится debug-информация в данном гайде мы не будем, но вы можете узнать про это в моём репозитории на GitHub, который создан как-раз таки для описания данного формата(ссылка в конце гайда)

На этом, заголовок окончен, переходим к прототипам.

Сразу после заголовка следуют прототипы, которые и составляют по сути сам скомпилированный код.
В конце файла находится нулевой байт(\x00), который указывает на конец списка прототипов.

Теперь, разбираем прототип!

---

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

ТИП : НАЗВАНИЕ - ОПИСАНИЕ

Помимо уже известного вам типа ULEB128, так-же используются типы:

• BYTE - 1 байт(8 бит)
• WORD - 2 байта(16 бит)
• DWORD - 4 байта(32 бита)

Перейдём к заголовку прототипа:

ULEB128 : proto_len - Длина прототипа
BYTE : pflags - Флаги прототипа(см. ниже)
BYTE : numparams - Количество параметров прототипа(функции)
BYTE : framesize - Размер фрейма функции(используется для её вызова)
BYTE : sizeuv - Количество upvalues
ULEB128 : sizekgc - Количество констант, собираемых сборщиком мусора(все переменные)
ULEB128 : sizekn - Количество числовых констант
ULEB128 : sizebc - Размер исполняемого кода(!!! РАЗМЕР В DWORD !!!, Что-бы получить количество байт, умножайте на 4)

Что-же, вот мы и подошли к его величию, исполняемому коду!
Сразу после заголовка следует исполняемый байт-код, который и творит всю магию.
Он представляет собой массив из DWORD, длинной sizebc(значение из заголовка)

На данный момент, пожалуй пропустим его, и вернёмся к нему позже, а пока что разберёмся с upvalues и константами

За исполняемым кодом следует uvdata, это массив WORD, длинной sizeuv(значение из заголовка)
Все upvalues в нём хранятся по порядку, поэтому без угрызений совести можно просто копировать sizeuv*2 байт в свой буфер для upvalues

Далее идут константы, а именно сначала константы, собираемые сборщиком мусора(далее, gc-константы), а затем числовые константы(далее, num-константы)
На самом деле, разницы между ними особо нету, так как gc-константы спокойно могут хранить любые числа, но видимо компилятору LuaJIT виднее(если я чего-то не понимаю, прошу объяснить ;) )

Что-же, начнём разбираться с gc-константами
Сначала идёт тип константы, в формате ULEB128, потом, значение, которое, естественно, зависит от типа

Если тип >= BCDUMP_KGC_STR(5)

Значение является строкой, длина которой = Тип-BCDUMP_KGC_STR
Т.е. если тип = 10, то длина буффера будет равна 5(10-5=5)

Если тип == BCDUMP_KGC_COMPLEX(4)

Значение - 128 битное число, каждые 32 бита которого записаны в ULEB128
Т.е., что бы считать такое число, надо считывать данные примерно так:
(read_uleb128 - абстрактная функция, для считывания ULEB128)

low_low_32 = read_uleb128()
low_high_32 = read_uleb128()
high_low_32 = read_uleb128()
high_high_32 = read_uleb128()

low_64 = (low_low_32 << 32) | low_high_32
high_64 = (high_low_32 << 32) | high_high_32

!!! Языки программирования обычно не поддерживают 128-битные числа,
    и операция ниже приведёт к переполнению !!!
num_128 = (low_64 << 64) | high_64

Если тип == BCDUMP_KGC_CHILD(0)

Спойлер: Если тип == BCDUMP_KGC_CHILD(0)

Не содержит значения, однако, при получении константного значения данного типа из кода(например, опкод FNEW) - возвращается прототип, находящийся на "вершине" стека прототипов

Для понимания этого, давайте рассмотрим пример с таким кодом:

function foo()
   print("foo")
end
function main()
   foo()
end

Компилятор LuaJIT устроен таким образом, что первым делом он пытается скомпилировать Global Chunk, однако, поскольку в нём присутствуют прототипы-"дети"(т.е. прототипы, находящиеся внутри прототипа), он сначала компилирует их, по очереди, и как раз таки первый скомпилированный прототип будет на "вершине" стека прототипов. С получением каждого нового прототипа со стека прототипа, верхушка стека уходит вниз.
В общем, лучше 1 раз увидеть, чем 100 раз услышать, поэтому посмотрим на скомпилированный и дизассемблированный код выше:

Как мы видим, снизу, т.е. в конце списка прототипов, находится Global Chunk, а выше находятся прототипы-"дети"
Первая инструкция в Global Chunk получает прототип с вершины стека, и устанавливает его в глобальную среду(иначе, устанавливает глобальную переменную) с названием "foo", т.е., данный прототип является функцией foo. Посмотрев выше, видно, что foo - прототип с ID=0, т.е., первый скомпилированный, или, прототип на верхушке стека.
После получения функции foo, верхушка стека уменьшается на 1, и теперь указывает на функцию main, после чего операция повторяется, только с названием "main"

Надеюсь, на этом с типом BCDUMP_KGC_CHILD понятно

Если тип == BCDUMP_KGC_TAB(1)

Содержит таблицу, см. ниже

Иначе(тип == BCDUMP_KGC_I64(2) или BCDUMP_KGC_U64(3))

64-битное число из двух ULEB128

Если тип BCDUMP_KGC_I64, то число со знаком(т.е. как положительные значения, так и отрицательные)
Если тип BCDUMP_KGC_U64, то число без знака(только положительные значения)

---

Структура gc-константной таблицы

Первые два ULEB128 значения содержат длину "массива" и "словаря" таблицы
т.е.:

array_len = read_uleb128()
hash_len = read_uleb128()
// hash_len - иначе, dict_len, т.е. длина части с хешируемыми индексами

Кто-то: Что еще за массив и словарь такие?

Довольно просто, таблицы в Lua устроены так, что есть две её части.
Часть для числовых индексов(т.е. индексация как в массиве), т.е. массив
И часть для хешируемых индексов(зачастую, строк), т.е. словарь(термин "словарь" взят из питухона питона)

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

Схематически можно представить это вот так:

"Массив" таблицы:
{ktabk}  {ktabk}  {ktabk}...
^        ^
Значение Значение ...

"Словарь" таблицы:
{ktabk}{ktabk}   {ktabk}{ktabk} ...
^      ^         ^      ^
Ключ   Значение  Ключ   Значение ...

Разберём сам ktabk:
Структура довольно схожа с gc-константой, но всё же отличается

Сначала идёт тип в формате ULEB128

Далее, в зависимости от типа:
Если тип >= BCDUMP_KTAB_STR(5)

Значение является строкой, длина которой = Тип-BCDUMP_KGC_STR
Т.е. если тип = 10, то длина буффера будет равна 5(10-5=5)

Если тип == BCDUMP_KTAB_INT(3)

32-х битное значение в формате ULEB128

Если тип == BCDUMP_KTAB_NUM(4)

64-х битное значение из двух ULEB128

Иначе

Значение равно "внутренней константе"
Т.е. true, false или nil
Зависит от типа

BCDUMP_KTAB_NIL = 0
BCDUMP_KTAB_FALSE = 1
BCDUMP_KTAB_TRUE = 2

Думаю, при каком типе какое значение и так понятно

На этом всё, с таблице разобрались!

---

Что-же, перейдём к num-константам(напомню, что до этого мы разбирали gc-константы)

num-константы устроены немного посложнее, и записаны в формате ULEB128_33

---

Формат ULEB128_33

Формат ULEB128_33 устроен так, что самый нижний бит(самый правый) в первой байте означает какую-либо "метку"
т.е:

1 011010 1 ... Далее обычный ULEB128
^ ^^^^^^ ^
^ Данные ^
^        ^
^        "Метка"
^
Старший бит
как и в
ULEB128

---

Если "Метка" равна 0, то считанное значение и есть числом(32-х битное число)
Иначе, значение - 64-х битное число, и необходимо считать еще один ULEB128

Данный процесс можно представить как-то так

read_uleb128_33 - Абстрактная функция, считывающая ULEB128_33 и возвращающая данные, и "метку"

low, mark = read_uleb128_33()
num = 0
if mark then
    high = read_uleb128()
    num = (low << 32) | high
else
    num = low
end

num - значение num-константы

---

Что-же, теперь мы может перейти к исполняемому коду

Исполняемый код состоит из инструкций, каждая инструкция состоит из 32 бит
У каждой инструкции есть Opcode, и 3(либо 2) параметра.

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

Где Opcode - Нижние 8 бит(правые), а B или D - верхние(левые)

Описание всех опкодов и их аргументов можно найти тут

---

Если ты осилил всё выше, то поздравляю, мы прошли с тобой через эти дебри!

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

Репозиторий

Прошу вас к критике и высказыванию своего мнения

 

[imring]

Если тип == BCDUMP_KGC_CHILD(0)
Не содержит никакого значения

да, не содержит, но ты забыл дописать, для чего этот тип существует. он записывает верхний элемент стека прототипов (https://github.com/imring/disluapp/blob/master/include/dislua/lj/ljparser.hpp#L186).

 

[RedHolms]

да, не содержит, но ты забыл дописать, для чего этот тип существует. он записывает верхний элемент стека прототипов (https://github.com/imring/disluapp/blob/master/include/dislua/lj/ljparser.hpp#L186).

Понял, подправил, про стек прототипов расписал

 

[kin4stat]

Разберём сам ktabk:
Структура довольно схожа с gc-константой, но всё же отличается

Сначала идёт тип в формате ULEB128

Как тогда таблицы внутри таблицы хранятся?

 

[RedHolms]

Как тогда таблицы внутри таблицы хранятся?

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

 

[#Northn]

Как тогда таблицы внутри таблицы хранятся?

это обычные указатели на таблицы
кстати прикол, следующий код работает исправно:

test = {}
test["test"] = test
print(test.test.test.test.test.test.test.test.test)
test.test.test.test.test.test.test.test.a = 'hello'
print(test.test.test.test.a)