Асм и автоматическое управление памятью [fasm g]

[st4s]

Здравствуйте.

Когда-то обсуждалось на WASM такое, естественно, в шутку. Потому что реальные кодеры любят делать всё сами, а сборка мусора объявлена ересью даже в Си++. Однако, однажды пришлось обдумать компилятор простейшего языка, где бы такая реализация пригодилась. Отлаживать сборщик мусора одновременно с написанием транслятора несколько накладно, потому прикрутил его к виртуальной машине, исполняющей байт-код, в который компилируется OCaml. На новом wasm.in какие-то проблемы с регистрацией и мне рекомендовали данный форум. Буду рад, если публикация поможет взглянуть на ассемблер под новым углом, в том числе и мне.

Простейший сценарий. Резервируем память в последней секции исполняемого файла, а один из регистров под указатель "кучи". В IA32/AMD64 напрашивается DI. Если надо что-то разместить в куче, используем команду STOS или MOV + увеличиваем адрес. Внимательный читатель уже задаёт вопрос: и что же случится, когда выйдем за пределы зарезервированной области? Там ведь нет подключённых страниц памяти, будет сгенерировано исключение.

Автоматический рост кучи.
Исключение нам и пригодится.
Установим обработчик:

macro    gc_init
    virtual at rsp
    .ksa    kernel_sigaction
    end virtual
    mov    rdi, rsp
    mov    rax, sigsegv_handler
    stos    qword[rdi]
    mov    eax, SA_SIGINFO or SA_RESTORER
    stos    qword[rdi]
    mov    rax, __restore_rt
    stos    qword[rdi]
    zero    eax
    mov    ecx, _NSIG / 8
    mov    r10, rcx
rep    stos    qword[rdi]
    mov    edi, SIGSEGV
    mov    rsi, rsp
    zero    edx
    sys.rt_sigaction
    j_ok    .sigseg_handler_installed
    push    rax
    puts    error_sigsegv_nohandler
    pop    rdi
    jmp    sys_exit
.sigseg_handler_installed:
end macro

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

; RDI - № сигнала (д.б. SIGSEGV)
; RSI - адрес siginfo
; RDX - контекст ucontext
proc sigsegv_handler
    virtual at rsi
    .sinf    siginfo_sigfault
    end virtual
    virtual at rdx
    .ctx    ucontext
    end virtual
    cmp    [.sinf.si_code], SEGV_MAPERR
    jnz    .err

.add_page:
    mov    rdi, [.sinf.si_addr]
    mov    esi, HEAP_INCREMENT
    mov    edx, PROT_READ or PROT_WRITE
    mov    r10d, MAP_PRIVATE or MAP_ANONYMOUS
    mov    r8, -1
    zero    r9
    sys.mmap
    ret

.err:    puts    error_sigsegv_handler
    pop    rdi
    jmp    sys_exit

; См.    glibc/sysdeps/unix/sysv/linux/x86_64/sigaction.c
; и (?)    uClibc/libc/sysdeps/linux/arc/sigaction.c
align_code 16
__restore_rt:
    sys.rt_sigreturn
end proc

Данный код рассчитан на Linux AMD64, но идея должна работать и в NT.

В Linux имеется Overcommit и можно было бы тупо выделить пару гигабайт пустых страниц, как ныне модно. Что, не надо освобождать? Оказывается, пока памяти достаточно, это может быть приемлемой стратегией, согласно новейшим исследованием каких-то известных учёных (простите, забыл фамилии).

Автоматическое освобождение ненужных блоков.
Как отличить нужный блок от ненужного? Если нам что-то нужно, зачит мы где-то сохранили адрес. Или на стеке, или в регисте. Или в той же куче? В последнем случае, адрес сохранённого адреса опять же будет либо в стеке, либо в куче, и так далее. С учётом рекурсии, достаточно проверять адреса из стека (и регистров). Их принято называть корневыми ссылками (roots).

Теперь самое интересное. В стеке может быть много всего разного. Как определить, что вот это число - адрес в куче, а не что попало? Диапазон адресов кучи известен, если не попадает - значит не то. А если попадает? Однозначное решение не известно. Кому-то может быть интересно пошевелить извилиной и произвести революцию в науке, прежде чем прочитать далее один из вариантов.

В OCaml это решили следующим образом. Локальные данные это либо целые числа, либо указатели на кучу. Поскольку на куче размещается всегда более одного байта, все указатели - чётные. А все целые - нечётные. Т.е. 0 - нечётное, 1 - нечётное, 2 - нечётное и так далее. Как? Умножены на 2 и младший бит установлен в 1. На самом деле это не так страшно, сложение выполняется одной командой: LEA RDX, [RDX + RAX - 1]. Да, диапазон возможных значений уменьшился вдвое.

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

;    Структура заголовка в данной имплементации:
;    +------+-----------------+-----+
;    |маркер| размер в словах | тэг |
;    +------+-----------------+-----+
; биты  63   40 39              8 7   0

в заголовке "живые" блоки помечаются. Эта стадия называется маркировка. Далее возможны варианты, в данной реализации используется уплотнение кучи: занятые блоки сдвигаются к её началу, а ссылки на них корректируются. Что бы не пугать читателя нагромождением деталей, оставлю их в архиве с исходниками. heap.asm это всего 740 строк, из котрых 270 комментарии - достаточно скромный показатель для асма (для сравнения, сам интерпретатор занимат более 1700, не считая реализации т.н. примитивов). Если отвязаться от OCaml-а, наверняка можно упростить. Здесь нет поколений и прочих высокоуровневых оптимизаций, поскольку это уже не относится непосредственно к ассемблеру.

Репозиторий на Github

P.S. Если вдруг кто решит исполнять на данной штуке написанные на OCaml программы (будут работать далеко не все, поскольку рантайм реализован частично), поребуется версия транслятора 4.04.2, в боле поздних изменилась сигнатура файла с байткодом, что-то меняли, с этим не разбирался.