QEMU.js: сега сериозно и со WASM

Еднаш одамна решив за забава докаже реверзибилноста на процесот и научете како да генерирате JavaScript (поточно, Asm.js) од машинскиот код. За експериментот беше избран QEMU, а извесно време подоцна беше напишана статија на Хабр. Во коментарите ме советуваа да го преправам проектот во WebAssembly, па дури и самиот да се откажам речиси завршена Некако не го сакав проектот... Работата се одвиваше, но многу бавно, а сега, неодамна во таа статија се појави коментар на тема „Па, како заврши сето тоа? Како одговор на мојот детален одговор, слушнав „Ова звучи како статија“. Па, ако може, ќе има статија. Можеби на некој ќе му биде корисно. Од него читателот ќе научи неколку факти за дизајнот на позадините за генерирање на код QEMU, како и како да напишете компајлер Just-in-Time за веб-апликација.

задачи

Бидејќи веќе научив како „некако“ да го префрлам QEMU на JavaScript, овој пат беше одлучено да го направам тоа мудро и да не ги повторувам старите грешки.

Грешка број еден: разгранете се од ослободување на точката

Мојата прва грешка беше што ја откинав мојата верзија од upstream верзијата 2.4.1. Тогаш ми се чинеше добра идеја: ако постои ослободување на точка, тогаш веројатно е постабилно од едноставниот 2.4, а уште повеќе гранката master. И бидејќи планирав да додадам прилично голема количина на мои грешки, воопшто не ми требаа ничии други. Веројатно така испадна. Но, тука е работата: QEMU не стои, а во одреден момент дури најавија оптимизација на генерираниот код за 10 проценти. „Да, сега ќе замрзнам“, си помислив и се расипав. Овде треба да направиме дигресија: поради природата на QEMU.js со една нишка и фактот дека оригиналниот QEMU не подразбира отсуство на повеќенишки (односно, способност за истовремено управување со неколку неповрзани патеки на кодот, и не само „користете ги сите кернели“) е критично за тоа, главните функции на нишките морав да ги „исклучам“ за да можам да повикувам однадвор. Ова создаде некои природни проблеми за време на спојувањето. Сепак, фактот дека некои од промените од гранка master, со кој се обидов да го спојам мојот код, исто така беа избрани цреши во пораката за точки (а со тоа и во мојата гранка), исто така, веројатно немаше да има дополнителна погодност.

Во принцип, решив дека сè уште има смисла да го исфрлам прототипот, да го расклопам за делови и да изградам нова верзија од нула врз основа на нешто посвежо и сега од master.

Грешка број два: методологија на TLP

Во суштина, ова не е грешка, воопшто, тоа е само карактеристика на создавање проект во услови на целосно недоразбирање и за „каде и како да се движиме?“ и воопшто „дали ќе стигнеме таму? Во овие услови несмасно програмирање беше оправдана опција, но, нормално, не сакав да ја повторувам непотребно. Овој пат сакав да го направам тоа мудро: атомски обврзувања, свесни промени на кодот (и не „спојување на случајни знаци додека не се состави (со предупредувања)“, како што еднаш рекол Линус Торвалдс за некого, според Викицитатот) итн.

Грешка број три: влегување во вода без да се знае фордот

Сè уште не се ослободив целосно од ова, но сега решив воопшто да не го следам патот на најмал отпор и да го направам тоа „како возрасен“, имено, напишете го мојот TCG заднина од нула, за да не да мора да кажам подоцна, „Да, ова е се разбира, полека, но не можам да контролирам сè - така е напишано TCI...“ Покрај тоа, ова првично изгледаше како очигледно решение, бидејќи Јас генерирам бинарен код. Како што велат, „Гент се собрау, но не тој“: кодот е, се разбира, бинарен, но контролата не може едноставно да се пренесе на него - мора експлицитно да се турка во прелистувачот за компилација, што резултира со одреден објект од светот на JS, кој сè уште треба да биди спасен некаде. Сепак, кај нормалните RISC архитектури, колку што разбирам, типична ситуација е потребата експлицитно да се ресетира кешот на инструкции за регенериран код - ако тоа не е она што ни треба, тогаш, во секој случај, тоа е блиску. Дополнително, од мојот последен обид, дознав дека контролата не се пренесува на средината на блокот за превод, така што навистина не ни треба бајтекод интерпретиран од никакво поместување и едноставно можеме да го генерираме од функцијата на TB .

Дојдоа и клоцаа

Иако почнав да го препишувам кодот уште во јули, незабележано се појави волшебен удар: обично писмата од GitHub пристигнуваат како известувања за одговорите на прашањата и барањата за повлекување, но овде, одеднаш спомни во темата Binaryen како штому заднина во контекст, „Тој направи нешто такво, можеби ќе каже нешто“. Зборувавме за користење на поврзаната библиотека на Емскриптен Бинариен да се создаде WASM JIT. Па, реков дека имаш лиценца Apache 2.0 таму, а QEMU како целина е дистрибуиран под GPLv2, и не се многу компатибилни. Одеднаш се покажа дека лиценца може да биде поправете го некако (Не знам: можеби смени, можеби двојна лиценца, можеби нешто друго...). Ова, се разбира, ме израдува, бидејќи дотогаш веќе внимателно го погледнав бинарен формат WebAssembly, а јас бев некако тажен и неразбирлив. Имаше и библиотека која ќе ги проголта основните блокови со графикот на транзиција, ќе го произведе бајтекодот, па дури и ќе го изврши во самиот толкувач, доколку е потребно.

Потоа имаше повеќе писмото на мејлинг листата на QEMU, но ова е повеќе за прашањето: „Кому му треба во секој случај?“ И тоа е одеднаш, се покажа дека е потребно. Во најмала рака, можете да ги изгребете следните можности за употреба, ако работи повеќе или помалку брзо:

• лансирање на нешто едукативно без никаква инсталација
• виртуелизација на iOS, каде што, според гласините, единствената апликација што има право да генерира код во лет е JS мотор (дали е ова вистина?)
• демонстрација на мини-оперативен систем - единечна флопи, вградена, секаков вид фирмвер, итн...

Карактеристики на траење на прелистувачот

Како што веќе реков, QEMU е поврзан со повеќенишки, но прелистувачот го нема. Па, тоа е, не... Отпрвин воопшто не постоеше, а потоа се појавија WebWorkers - колку што разбрав, ова е мулти-нишки базирано на пренесување пораки без споделени променливи. Секако, ова создава значителни проблеми при пренесување на постоечкиот код врз основа на моделот за заедничка меморија. Потоа под притисок на јавноста се спроведуваше и под името SharedArrayBuffers. Постепено се воведуваше, го прославија неговото лансирање во различни прелистувачи, потоа ја прославија Новата година, па Meltdown... По што дојдоа до заклучок дека грубо или грубо е мерењето на времето, но со помош на заедничка меморија и конец го зголемува бројачот, се е исто ќе функционира прилично прецизно. Така, го оневозможивме мултинизирањето со заедничка меморија. Се чини дека подоцна повторно го вклучија, но, како што стана јасно од првиот експеримент, постои живот без него, и ако е така, ќе се обидеме да го направиме тоа без да се потпираме на повеќенишки.

Втората карактеристика е неможноста за манипулации на ниско ниво со стекот: не можете едноставно да го земете, да го зачувате тековниот контекст и да се префрлите на нов со нов стек. Со стекот на повици управува виртуелната машина JS. Се чини, што е проблемот, бидејќи сепак решивме да управуваме со првите текови целосно рачно? Факт е дека блок I/O во QEMU се имплементира преку корутини, и тука добро би дошле манипулациите со стек на ниско ниво. За среќа, Emscipten веќе содржи механизам за асинхрони операции, дури и две: Асинфицирајте и Преведувач. Првиот работи преку значителна надуеност во генерираниот JavaScript код и повеќе не е поддржан. Вториот е тековниот „точен начин“ и работи преку генерирање бајтекод за мајчин преведувач. Работи, се разбира, бавно, но не го надувува кодот. Навистина, поддршката за корутините за овој механизам требаше да се придонесе независно (веќе имаше напишани корутини за Asyncify и имаше имплементација на приближно ист API за Emterpreter, само требаше да ги поврзете).

Во моментов, сè уште не сум успеал да го поделам кодот на компајлиран во WASM и интерпретиран со помош на Emterpreter, така што блок уредите сè уште не работат (видете во следната серија, како што велат ...). Односно, на крајот треба да добиете нешто како оваа смешна повеќеслојна работа:

• интерпретираниот блок В/И. Па, дали навистина очекувавте емулиран NVMe со природна изведба? 🙂
• статички компајлиран главен QEMU код (преведувач, други емулирани уреди итн.)
• динамички компајлиран гостин код во WASM

Карактеристики на изворите на QEMU

Како што веројатно веќе погодивте, кодот за емулација на гостински архитектури и кодот за генерирање на инструкции на машината домаќин се одделени во QEMU. Всушност, тоа е уште малку покомплицирано:

• има гостински архитектури
• постои акцелератори, имено, KVM за виртуелизација на хардвер на Linux (за гостински и домаќински системи компатибилни едни со други), TCG за генерирање JIT код насекаде. Почнувајќи со QEMU 2.9, се појави поддршка за стандардот за виртуелизација на хардверот HAXM на Windows (деталите)
• ако се користи TCG, а не хардверска виртуелизација, тогаш има посебна поддршка за генерирање код за секоја архитектура на домаќинот, како и за универзалниот преведувач
• ... и околу сето ова - емулирани периферни уреди, кориснички интерфејс, миграција, репродукција на записи итн.

Патем, дали знаевте: QEMU може да го имитира не само целиот компјутер, туку и процесорот за посебен кориснички процес во кернелот на домаќинот, кој се користи, на пример, од AFL fuzzer за бинарна инструментација. Можеби некој би сакал да го пренесе овој начин на работа на QEMU на JS? 😉

Како и повеќето долгогодишни бесплатни софтвери, QEMU е изграден преку повикот configure и make. Да речеме дека одлучивте да додадете нешто: TCG backend, имплементација на нишки, нешто друго. Не брзајте да бидете среќни/ужасни (подвлечете како што е соодветно) при можноста да комуницирате со Autoconf - всушност, configure QEMU's очигледно е самонапишан и не е генериран од ништо.

Веб-собрание

Значи, што е ова нешто што се нарекува WebAssembly (познато како WASM)? Ова е замена за Asm.js, што повеќе не се преправа дека е валиден JavaScript код. Напротив, тој е чисто бинарен и оптимизиран, па дури и едноставното пишување цел број во него не е многу едноставно: за компактност, тој се чува во формат ЛЕБ128.

Можеби сте слушнале за алгоритмот за превртување за Asm.js - ова е враќање на инструкциите за контрола на протокот на „високо ниво“ (односно, ако-тогаш-инаку, јамки, итн.), за кои се дизајнирани моторите JS, од LLVM IR на ниско ниво, поблиску до машинскиот код што го извршува процесорот. Нормално, средната застапеност на QEMU е поблиску до втората. Се чини дека тука е, бајт-код, крајот на маките... А потоа има блокови, ако-тогаш-друго и јамки!..

И ова е уште една причина зошто Binaryen е корисен: тој природно може да прифати блокови на високо ниво блиску до она што би се складирало во WASM. Но, исто така може да произведе код од графикон на основни блокови и транзиции меѓу нив. Па, веќе реков дека го крие форматот за складирање WebAssembly зад пригодниот C/C++ API.

TCG (Генератор на мали кодови)

ГТЦ беше првично backend за компајлерот C. Потоа, очигледно, не можеше да ја издржи конкуренцијата со GCC, но на крајот го најде своето место во QEMU како механизам за генерирање код за платформата домаќин. Исто така постои и TCG backend кој генерира некој апстрактен бајтекод, кој веднаш се извршува од страна на толкувачот, но решив да избегнам да го користам овој пат. Сепак, фактот што во QEMU веќе е можно да се овозможи премин кон генерирана ТБ преку функцијата tcg_qemu_tb_exec, ми се покажа многу корисно.

За да додадете нов TCG backend на QEMU, треба да креирате поддиректориум tcg/<имя архитектуры> (во овој случај, tcg/binaryen), и содржи две датотеки: tcg-target.h и tcg-target.inc.c и пропишува се работи за configure. Можете да ставите други датотеки таму, но, како што можете да претпоставите од имињата на овие две, и двете ќе бидат вклучени некаде: едната како обична датотека за заглавие (вклучена е во tcg/tcg.h, и тој веќе е во други датотеки во директориумите tcg, accel и не само), другиот - само како фрагмент од код во tcg/tcg.c, но има пристап до неговите статички функции.

Одлучувајќи дека ќе потрошам премногу време на детални испитувања за тоа како функционира, едноставно ги копирав „скелетите“ на овие две датотеки од друга имплементација на заднината, искрено означувајќи го ова во заглавието на лиценцата.

датотека tcg-target.h содржи главно поставки во формата #define-s:

• колку регистри и каква ширина има на целната архитектура (имаме колку сакаме, колку што сакаме - прашањето е повеќе за тоа што ќе се генерира во поефикасен код од прелистувачот на архитектурата „целосно целна“ ...)
• порамнување на инструкциите на домаќинот: на x86, па дури и во TCI, инструкциите воопшто не се порамнети, но ќе ставам во баферот на кодот не воопшто инструкции, туку покажувачи кон структурите на библиотеката Binaryen, па ќе кажам: 4 бајти
• какви опционални инструкции може да генерира задниот дел - ние вклучуваме сè што ќе најдеме во Binaryen, нека акцелераторот сам го раздели остатокот на поедноставни
• Која е приближната големина на кешот TLB што ја бара задниот дел. Факт е дека во QEMU сè е сериозно: иако има помошни функции кои вршат вчитување/складирање земајќи го предвид гостинот MMU (каде би биле без него сега?), тие ја зачувуваат својата кеш за превод во форма на структура, чија обработка е погодна за директно вметнување во блокови за емитување. Прашањето е што поместување во оваа структура најефикасно се обработува со мала и брза низа на команди?
• овде можете да ја измените целта на еден или два резервирани регистри, да овозможите повикување ТБ преку функција и опционално да опишете неколку мали inline-функционира како flush_icache_range (но ова не е нашиот случај)

датотека tcg-target.inc.c, се разбира, обично е многу поголем по големина и содржи неколку задолжителни функции:

• иницијализација, вклучувајќи ограничувања за тоа кои инструкции можат да работат на кои операнди. Бесплатно копиран од мене од друг бекенд
• функција која зема една инструкција за внатрешен бајтокод
• Овде можете да ставите и помошни функции, а можете да користите и статични функции од tcg/tcg.c

За себе, ја избрав следнава стратегија: во првите зборови од следниот блок за превод, запишав четири покажувачи: почетна ознака (одредена вредност во близина 0xFFFFFFFF, кој ја одреди моменталната состојба на ТБ), контекстот, генерираниот модул и магичен број за дебагирање. Отпрвин ознаката беше ставена во 0xFFFFFFFF - nкаде n - мал позитивен број, а секој пат кога се извршувал преку толкувачот се зголемувал за 1. Кога достигнал 0xFFFFFFFE, се случи компилација, модулот беше зачуван во функционалната табела, увезен во мал „фрлач“, во кој извршувањето отиде од tcg_qemu_tb_exec, и модулот беше отстранет од QEMU меморијата.

Да ги парафразираме класиците, „Птерица, колку е испреплетено во овој звук за срцето на прогерот...“. Сепак, сеќавањето протече некаде. Покрај тоа, таа беше меморија управувана од QEMU! Имав код кој, при пишувањето на следната инструкција (добро, т.е. покажувач), го избриша оној чија врска беше на ова место порано, но тоа не помогна. Всушност, во наједноставниот случај, QEMU доделува меморија при стартување и таму го запишува генерираниот код. Кога тампонот ќе истече, кодот се исфрла и следниот почнува да се запишува на негово место.

Откако го проучив кодот, сфатив дека трикот со магичниот број ми овозможи да не успеам при уништување на купот со ослободување на нешто погрешно на неиницијализиран тампон при првото поминување. Но, кој го препишува баферот за да ја заобиколи мојата функција подоцна? Како што советуваат програмерите на Emscripten, кога наидов на проблем, го префрлив добиениот код назад во матичната апликација, поставив Mozilla Record-Replay на неа... Во принцип, на крајот сфатив една едноставна работа: за секој блок, а struct TranslationBlock со неговиот опис. Погодете каде... Така е, непосредно пред блокот право во баферот. Сфаќајќи го ова, решив да престанам да користам патерици (барем некои), и едноставно го исфрлив магичниот број и ги префрлив преостанатите зборови на struct TranslationBlock, создавајќи единечно поврзан список што може брзо да се помине кога кешот за превод се ресетира и да се ослободи меморијата.

Остануваат некои патерици: на пример, означени покажувачи во баферот за кодови - некои од нив се едноставно BinaryenExpressionRef, односно ги гледаат изразите што треба линеарно да се стават во генерираниот основен блок, дел е условот за премин помеѓу BB, дел е каде да се оди. Па, веќе има подготвени блокови за Relooper кои треба да се поврзат според условите. За да ги разликувате, се користи претпоставката дека сите тие се порамнети за најмалку четири бајти, така што можете безбедно да ги користите најмалку значајните два бита за етикетата, само треба да запомните да ја отстраните доколку е потребно. Патем, таквите ознаки веќе се користат во QEMU за да се наведе причината за излегување од јамката TCG.

Користење на Binaryen

Модулите во WebAssembly содржат функции, од кои секоја содржи тело, што е израз. Изразите се унарни и бинарни операции, блокови кои се состојат од списоци на други изрази, контролен тек итн. Како што веќе реков, контролниот тек овде е организиран токму како гранки на високо ниво, циклуси, повици на функции итн. Аргументите на функциите не се пренесуваат на стекот, туку експлицитно, исто како во JS. Има и глобални променливи, но не сум ги користел, па нема да ви кажам за нив.

Функциите имаат и локални променливи, нумерирани од нула, од типот: int32 / int64 / float / double. Во овој случај, првите n локални променливи се аргументите предадени на функцијата. Имајте предвид дека иако сè овде не е целосно на ниско ниво во однос на контролниот тек, цели броеви сè уште не го носат атрибутот „потпишан/неозначен“: како се однесува бројот зависи од оперативниот код.

Општо земено, Binaryen обезбедува едноставен C-API: креирате модул, во него креирајте изрази - унарни, бинарни, блокови од други изрази, контролен тек итн. Потоа креирате функција со израз како нејзино тело. Ако вие, како мене, имате графикон за транзиција на ниско ниво, компонентата relooper ќе ви помогне. Колку што разбрав, можно е да се користи контрола на високо ниво на протокот на извршување во блок, сè додека не оди подалеку од границите на блокот - односно, можно е да се направи внатрешна брза патека / бавна разгранување на патеката во вградениот код за обработка на кешот TLB, но да не се меша со „надворешниот“ контролен тек . Кога ослободувате relooper, неговите блокови се ослободуваат; кога ослободувате модул, изразите, функциите итн. доделени на него исчезнуваат арена.

Меѓутоа, ако сакате да го интерпретирате кодот во лет без непотребно креирање и бришење на пример за толкувач, можеби ќе има смисла да ја ставите оваа логика во датотека C++ и оттаму директно да управувате со целиот C++ API на библиотеката, заобиколувајќи го готовиот изработени обвивки.

Значи, за да го генерирате кодот што ви треба

// настроить глобальные параметры (можно поменять потом)
BinaryenSetAPITracing(0);

BinaryenSetOptimizeLevel(3);
BinaryenSetShrinkLevel(2);

// создать модуль
BinaryenModuleRef MODULE = BinaryenModuleCreate();

// описать типы функций (как создаваемых, так и вызываемых)
helper_type  BinaryenAddFunctionType(MODULE, "helper-func", BinaryenTypeInt32(), int32_helper_args, ARRAY_SIZE(int32_helper_args));
// (int23_helper_args приоб^Wсоздаются отдельно)

// сконструировать супер-мега выражение
// ... ну тут уж вы как-нибудь сами :)

// потом создать функцию
BinaryenAddFunction(MODULE, "tb_fun", tb_func_type, func_locals, FUNC_LOCALS_COUNT, expr);
BinaryenAddFunctionExport(MODULE, "tb_fun", "tb_fun");
...
BinaryenSetMemory(MODULE, (1 << 15) - 1, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
BinaryenAddMemoryImport(MODULE, NULL, "env", "memory", 0);
BinaryenAddTableImport(MODULE, NULL, "env", "tb_funcs");

// запросить валидацию и оптимизацию при желании
assert (BinaryenModuleValidate(MODULE));
BinaryenModuleOptimize(MODULE);

... ако нешто заборавив, извинете, ова е само за да ја претставам вагата, а деталите се во документацијата.

И сега започнува crack-fex-pex, нешто вака:

static char buf[1 << 20];
BinaryenModuleOptimize(MODULE);
BinaryenSetMemory(MODULE, 0, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
int sz = BinaryenModuleWrite(MODULE, buf, sizeof(buf));
BinaryenModuleDispose(MODULE);
EM_ASM({
  var module = new WebAssembly.Module(new Uint8Array(wasmMemory.buffer, $0, $1));
  var fptr = $2;
  var instance = new WebAssembly.Instance(module, {
      'env': {
          'memory': wasmMemory,
          // ...
      }
  );
  // и вот уже у вас есть instance!
}, buf, sz);

Со цел некако да се поврзат световите на QEMU и JS и во исто време брзо да се пристапи до компајлираните функции, создадена е низа (табела на функции за увоз во фрлачот), а генерираните функции беа поставени таму. За брзо пресметување на индексот, првично се користеше индексот на блокот за превод на нула зборови, но потоа индексот пресметан со оваа формула почна едноставно да се вклопува во полето во struct TranslationBlock.

Патем, демо (моментално со матна лиценца) работи добро само во Firefox. Програмерите на Chrome беа некако не е подготвен до фактот дека некој би сакал да создаде повеќе од илјада примери на WebAssembly модули, па едноставно доделиле по еден гигабајт виртуелен адресен простор за секој ...

Тоа е се за сега. Можеби ќе има друга статија ако некој го интересира. Имено, останува барем само направи блок уреди да работат. Исто така, може да има смисла да се направи компилацијата на модулите WebAssembly асинхрони, како што е вообичаено во светот на JS, бидејќи сè уште постои преведувач што може да го направи сето ова додека не се подготви мајчиниот модул.

Конечно загатка: сте составиле бинарен на 32-битна архитектура, но кодот, преку мемориските операции, се искачува од Binaryen, некаде на стекот или некаде на друго место во горните 2 GB од 32-битниот адресен простор. Проблемот е што од гледна точка на Binaryen ова е пристап до премногу голема резултатска адреса. Како да се заобиколи ова?

На административен начин

Не го тестирав ова, но мојата прва мисла беше „Што ако инсталирам 32-битен Linux? Тогаш горниот дел од адресниот простор ќе биде окупиран од кернелот. Прашањето е само колку ќе биде зафатено: 1 или 2 Gb.

На начин на програмер (опција за практичари)

Ајде да дуваме балон на врвот на просторот за адреси. Јас самиот не разбирам зошто тоа функционира - таму веќе мора да има оџак. Но, „ние сме практичари: сè работи за нас, но никој не знае зошто...“

// 2gbubble.c
// Usage: LD_PRELOAD=2gbubble.so <program>

#include <sys/mman.h>
#include <assert.h>

void __attribute__((constructor)) constr(void)
{
  assert(MAP_FAILED != mmap(1u >> 31, (1u >> 31) - (1u >> 20), PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0));
}

... точно е дека не е компатибилен со Valgrind, но, за среќа, самиот Valgrind многу ефикасно ги турка сите од таму :)

Можеби некој ќе даде подобро објаснување за тоа како функционира овој мој код...

Извор: www.habr.com