Русский
Русский
English
Статистика
Реклама

V8

Перевод О реализации структуры данных Map в V8

07.09.2020 16:04:06 | Автор: admin

В стандарте ECMAScript 2015, известном как ES6, появилось много новых JavaScript-коллекций, таких, как Map, Set, WeakMap и WeakSet. Они, судя по всему, стали отличным дополнением к стандартным возможностям JavaScript. Они получили широкое применение в различных библиотеках, в приложениях, в ядре Node.js. Сегодня мы поговорим о коллекции Map, попытаемся разобраться с особенностями её реализации в V8 и сделаем некоторые практические выводы, основанные на полученных знаниях.

Стандарт ES6 не содержит чёткого указания на подход, который должен быть использован для реализации поддержки структуры данных Map. В нём лишь даны некоторые подсказки по возможным способам её реализации. Там же приведены сведения об ожидаемых от Map показателях производительности:

Объект Map должен быть реализован либо с использованием хеш-таблиц, либо с применением других механизмов, которые, в среднем, обеспечивают доступ к элементам коллекции за сублинейное время. Структуры данных, используемые в спецификации объекта Map, предназначены лишь для описания наблюдаемой семантики объектов Map. Они не задумывались как реальная модель реализации этих объектов.

Как видно, спецификация даёт тем, кто создаёт JS-движки, большую свободу. Но при этом здесь нет определённых указаний, касающихся конкретного подхода, используемого для реализации Map, его производительности, характеристик потребления памяти. Если в критически важной части вашего приложения используются структуры данных Map, и если вы записываете в такие структуры данных большие объёмы информации, то основательные знания о реализации Map, определённо, принесут вам большую пользу.

У меня есть опыт Java-разработки, я привык к коллекциям Java, когда можно выбирать между различными реализациями интерфейса Map и даже выполнять тонкую настройку выбранной реализации в том случае, если соответствующий класс это поддерживает. Более того, в Java всегда можно почитать опенсорсный код любого класса стандартной библиотеки и познакомиться с его реализацией (она, конечно, может в новых версиях меняться, но только в направлении повышения эффективности). Именно поэтому я не смог удержаться от того, чтобы изучить особенности работы объектов Map в V8.

Прежде чем мы начнём, хочу отметить, что то, о чём речь пойдёт ниже, относится к движку V8 8.4, который встроен в свежую dev-версию Node.js (если точнее, то речь идёт о коммите 238104c). Вам не нужно ожидать чего-то, выходящего за пределы спецификации.

Алгоритм, лежащий в основе реализации Map


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

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

V8 использует так называемые детерминированные хеш-таблицы, предложенные Тайлером Клоузом. Следующий псевдокод, основанный на TypeScript, демонстрирует основные структуры данных, используемые при реализации таких хеш-таблиц:

interface Entry {key: any;value: any;chain: number;}interface CloseTable {hashTable: number[];dataTable: Entry[];nextSlot: number;size: number;}

Здесь интерфейс CloseTable представляет хеш-таблицу. Он содержит массив hashTable, размер которого эквивалентен количеству хеш-контейнеров. Элемент массива с индексом N соответствует N-ному хеш-контейнеру и хранит индекс его головного элемента, находящегося в массиве dataTable. А этот массив содержит записи таблицы в порядке их вставки в неё. Записи представлены интерфейсом Entry. И наконец, у каждой записи есть свойство chain, которое указывает на следующую запись в цепочке записей хеш-контейнера (или, точнее, в односвязном списке).

Каждый раз, когда в таблицу вставляют новую запись, она сохраняется в элементе массива dataTable с индексом nextSlot. Этот процесс, кроме того, требует обновления данных в соответствующем хеш-контейнере, что приводит к тому, что вставленная запись становится новым последним элементом односвязного списка.

Когда запись удаляют из таблицы, то она удаляется из dataTable (например, путём записи в её свойства key и value значения undefined). Затем запись, предшествующая ей, и запись, следующая за ней, связываются друг с другом напрямую. Как вы могли заметить, это означает, что все удалённые записи продолжают занимать место в dataTable.

А теперь последний кусочек нашей головоломки. Когда таблица оказывается полна записей (и актуальных, и удалённых), она должна быть перехеширована (перестроена) с увеличением её размера. Размер таблицы может быть изменён и в сторону уменьшения.

Благодаря такому подходу обход структуры данных Map равносилен обходу массива dataTable. Это гарантирует сохранение порядка вставки записей в таблицу и соблюдение требования стандарта. Учитывая это, я ожидаю, что большинство JS-движков (если не все) используют детерминированные хеш-таблицы в качестве одного из механизмов, лежащих в основе реализации Map.

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


Давайте рассмотрим несколько примеров, позволяющих нам исследовать алгоритм на практике. Предположим, у нас имеется CloseTable с 2 хеш-контейнерами (hastTable.length), общая ёмкость которой составляет 4 элемента (dataTable.length). Эту таблицу заполняют следующим содержимым:

// Предположим, что мы используем хеш-функцию, возвращающую// то, что она получает на вход, то есть function hashCode(n) { return n; }table.set(0, 'a'); // => хеш-контейнер 0 (0 % 2)table.set(1, 'b'); // => хеш-контейнер 1 (1 % 2)table.set(2, 'c'); // => хеш-контейнер 0 (2 % 2)

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

const tableInternals = {hashTable: [0, -1],dataTable: [{key: 0,value: 'a',chain: 2 // индекс <2, 'c'>},{key: 1,value: 'b',chain: -1 // -1 означает последнюю запись списка},{key: 2,value: 'c',chain: -1},// пустой слот],nextSlot: 3, // указывает на пустой слотsize: 3}

Если удалить запись, воспользовавшись методом table.delete(0), то хеш таблица будет выглядеть так, как показано ниже:

const tableInternals = {hashTable: [0, 1],dataTable: [{key: undefined, // удалённая записьvalue: undefined,chain: 2},{key: 1,value: 'b',chain: -1},{key: 2,value: 'c',chain: -1},// пустой слот],nextSlot: 3,size: 2 // новый размер}

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

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

Теперь, когда мы разобрались с тем, что стоит за объектами Map в V8, мы готовы к тому, чтобы двинуться дальше.

Детали реализации


Реализация структуры данных Map в V8 написана на C++, после чего JS-коду дан доступ к соответствующим механизмам. Основная часть кода, имеющего отношение к Map, находится в классах OrderedHashTable и OrderedHashMap. Мы уже знаем о том, как работают эти классы. Если же вы хотите сами взглянуть на их код, то мы можете найти его здесь, здесь и здесь.

Так как нас особенно интересуют практические подробности о реализации Map в V8, нам, для начала, надо понять то, как задаётся ёмкость таблицы.

Ёмкость таблицы


В V8 ёмкость хеш-таблицы (структуры данных Map) всегда равна некоей степени двойки. Если говорить о коэффициенте использования хеш-контейнеров, то он всегда представлен числом 2. То есть, максимальная ёмкость таблицы это 2 * number_of_buckets 2, умноженное на количество хеш-контейнеров. При создании пустого объекта Map в его внутренней хеш-таблице имеется 2 хеш-контейнера. В результате ёмкость такого объекта равняется 4 записям.

Существует ограничение на максимальную ёмкость объектов Map. В 64-битных системах это будет около 16,7 миллиона записей. Это ограничение объясняется особенностями представления структур данных Map в куче. Мы поговорим об этом позже.

И наконец, коэффициент увеличения или уменьшения таблицы тоже всегда представлен произведением некоего числа на 2. Это значит, что после того, как в описываемую таблицу будет добавлено 4 записи, следующая операция вставки вызовет необходимость в перехешировании таблицы, в ходе которого размер таблицы увеличится в два раза. При уменьшении размеров таблицы, она, соответственно, может стать в 2 раза меньше.

Для того чтобы убедиться в том, что то, что я увидел в исходном коде, работает именно так, как я понял, я модифицировал код движка V8, встроенный в Node.js, сделав так, чтобы в объектах Map было бы доступным новое свойство buckets, содержащее сведения о количестве хеш-контейнеров. Результаты этой модификации вы можете найти здесь. В этой особой сборке Node.js можно запустить следующий скрипт:

const map = new Map();let prevBuckets = 0;for (let i = 0; i < 100; i++) {if (prevBuckets !== map.buckets) {console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);prevBuckets = map.buckets;}map.set({}, {});}

Этот скрипт просто вставляет в структуру данных Map 100 записей. Вот что выводится в консоли после его запуска:

$ ./node /home/puzpuzpuz/map-grow-capacity.jssize: 0, buckets: 2, capacity: 4size: 5, buckets: 4, capacity: 8size: 9, buckets: 8, capacity: 16size: 17, buckets: 16, capacity: 32size: 33, buckets: 32, capacity: 64size: 65, buckets: 64, capacity: 128

Как видно, когда таблица заполняется, то, при каждом изменении её размера, она увеличивается в 2 раза. Попробуем теперь добиться уменьшения таблицы, удаляя из неё элементы:

const map = new Map();for (let i = 0; i < 100; i++) {map.set(i, i);}console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);let prevBuckets = 0;for (let i = 0; i < 100; i++) {map.delete(i);if (prevBuckets !== map.buckets) {console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);prevBuckets = map.buckets;}}

Вот что выведет этот скрипт:

$ ./node /home/puzpuzpuz/map-shrink-capacity.jsinitial size: 100, buckets: 64, capacity: 128size: 99, buckets: 64, capacity: 128size: 31, buckets: 32, capacity: 64size: 15, buckets: 16, capacity: 32size: 7, buckets: 8, capacity: 16size: 3, buckets: 4, capacity: 8size: 1, buckets: 2, capacity: 4

Тут, опять же, видно, что размер таблицы уменьшается каждый раз, когда в ней оказывается меньше чем number_of_buckets / 2 элементов.

Хеш-функция


До сих пор мы не касались вопроса о том, как V8 вычисляет хеш-коды для ключей, сохраняемых в объектах Map. А это важный вопрос.

Для значений, которые можно отнести к числовым, используется та или иная хорошо известная хеш-функция с низкой вероятностью коллизии.

Для строковых значений выполняется вычисление хеш-кода, который основан на самих этих значениях. После этого данный код кешируется во внутреннем заголовке.

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

Временная сложность операций с объектами Map


Большинство операций, производимых над структурами данных Map, вроде set или delete, требуют поиска по этим структурам данных. Так же как и в случае с классическими хеш-таблицами, временная сложность поиска в нашем случае это O(1).

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

С другой стороны, в наилучшем сценарии, когда таблица заполнена, и при этом в каждом хеш-контейнере находится всего 2 записи, поиск записи потребует всего 2 действий.

Определённые операции в хеш-таблицах выполняются очень быстро, но к операции перехеширования это не относится. Временная сложность операции перехеширования это O(N). Она требует выделения в куче новой хеш-таблицы. Более того, перехеширование выполняется по необходимости, как часть операций по вставке элементов в таблицу или удаления их из неё. Поэтому, например, вызов map.set() может оказаться гораздо дороже, чем ожидается. Но, к счастью, операция перехеширования выполняется достаточно редко.

Потребление памяти


Конечно, хеш-таблица, лежащая в основе Map, должна быть как-то сохранена в куче. Она хранится в так называемом вспомогательном хранилище. И тут нас ждёт ещё один интересный факт. Вся таблица (а, значит, и всё то, что помещено в Map) хранится в единственном массиве фиксированной длины. Устройство этого массива показано на следующем рисунке.


Массив, используемый для хранения структур данных Map в памяти

Отдельные части массива имеют следующее назначение:

  • Заголовок: содержит информацию общего характера, например, сведения о количестве хеш-контейнеров или о количестве элементов, удалённых из Map.
  • Сведения о хеш-контейнерах: тут хранятся данные о контейнерах, которые соответствуют массиву hashTable из нашего примера.
  • Записи хеш-таблицы: здесь хранятся данные, соответствующие массиву dataTable. А именно, здесь находятся сведения о записях хеш-таблицы. Сведения о каждой записи занимают три ячейки массива. В одной хранится ключ, во второй значение, в третьей указатель на следующую запись в цепочке.

Если говорить о размере массива, то его можно примерно оценить как N * 3,5. Здесь N это ёмкость таблицы. Для того чтобы понять то, что это значит в плане потребления памяти, давайте представим, что у нас имеется 64-битная система, и то, что выключена возможность V8 по сжатию указателей. В таком случае для хранения каждого элемента массива понадобится 8 байт. В результате для хранения структуры данных Map, в которой содержится примерно 1 миллион записей, понадобится 29 Мб памяти в куче.

Итоги


В этом материале мы разобрали много всего, имеющего отношение к структуре данных Map в JavaScript. Подведём итоги:

  • В V8 для реализации Map используются детерминированные хеш-таблицы. Весьма вероятно то, что так же эта структура данных реализована и в других JS-движках.
  • Механизмы, поддерживающие работу Map, реализованы на C++, после чего представлены в виде API, который доступен из JavaScript.
  • Если говорить о временной сложности операций, выполняемых с объектами Map, то они, так же, как и при работе с классическими хеш-таблицами, имеют сложность O(1). При этом временная сложность операции перехеширования это O(N).
  • В 64-битных системах при отключённом сжатии указателей структура данных Map с 1 миллионом записей нуждается в 29 Мб памяти, выделяемой в куче.
  • Большинство того, что мы здесь обсудили, справедливо и для структур данных Set.

Пользуетесь ли вы объектами Map в JavaScript-разработке?

Подробнее..

Перевод Использование Atomics.wait(), Atomics.notify() и Atomics.waitAsync()

11.10.2020 18:05:36 | Автор: admin
Статические методы Atomics.wait() и Atomics.notify() представляют собой низкоуровневые примитивы синхронизации, которые можно применять для реализации мьютексов и других подобных механизмов. Но, так как метод Atomics.wait() является блокирующим, его нельзя вызывать в главном потоке (если попытаться это сделать будет выдана ошибка TypeError).

Движок V8, начиная с версии 8.7, поддерживает неблокирующий вариант Atomics.wait(), называемый Atomics.waitAsync(). Этим новым методом можно пользоваться в главном потоке.



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

Atomics.wait() и Atomics.waitAsync()


Методы Atomics.wait() и Atomics.waitAsync() принимают следующие параметры:

  • buffer: массив типа Int32Array или BigInt64Array, в основе которого лежит SharedArrayBuffer.
  • index: действительный индекс элемента в массиве.
  • expectedValue: значение, которое, как мы ожидаем, должно быть представлено в памяти, в том месте, которое описано с помощью buffer и index.
  • timeout: тайм-аут в миллисекундах (необязательный параметр, по умолчанию установлен в Infinity).

Atomics.wait() возвращает строку. Если в указанном месте памяти не оказывается ожидаемого значения Atomics.wait() немедленно завершает работу, возвращая строку not-equal. В противном случае поток блокируется. Для того чтобы блокировка была бы снята, должно произойти одно из следующих события. Первое это вызов из другого потока метода Atomics.notify() с указанием того места в памяти, которое интересует метод Atomics.wait(). Второе это истечение тайм-аута. В первом случае Atomics.wait() возвратит строку ok, во втором строковое значение timed-out.

Метод Atomics.notify() принимает следующие параметры:

  • typedArray: массив типа Int32Array или BigInt64Array, в основе которого лежит SharedArrayBuffer.
  • index: действительный индекс элемента в массиве.
  • count: количество агентов, ожидающих уведомления (необязательный параметр, по умолчанию установлен в Infinity).

Метод Atomics.notify() уведомляет указанное количество агентов, ожидающих уведомления по адресу, описываемому typedArray и index, обходя их в порядке FIFO-очереди. Если было сделано несколько вызовов Atomics.wait() или Atomics.waitAsync(), наблюдающих за одним и тем же местом в памяти, то все они оказываются в одной и той же очереди.

В отличие от метода Atomics.wait(), метод Atomics.waitAsync() сразу же возвращает значение в место вызова. Это может быть одно из следующих значений:

  • { async: false, value: 'not-equal' } если указанное место в памяти не содержит ожидаемого значения.
  • { async: false, value: 'timed-out' } только в тех случаях, когда тайм-аут установлен в 0.
  • { async: true, value: promise } в остальных случаях.

Промис, по прошествии некоторого времени, может быть успешно разрешён строковым значением ok (если был вызван метод Atomics.notify(), которому переданы сведения о том месте в памяти, которое было передано Atomics.waitAsync()). Он может быть разрешён и со значением timed-out. Этот промис никогда не отклоняется.

В следующем примере продемонстрированы основы использования Atomics.waitAsync():

const sab = new SharedArrayBuffer(16);const i32a = new Int32Array(sab);const result = Atomics.waitAsync(i32a, 0, 0, 1000);//                   | | ^ тайм-аут (необязательно)//                   | ^ ожидаемое значение//                   ^ индексif (result.value === 'not-equal') {// Значение в SharedArrayBuffer отличается от ожидаемого.} else {result.value instanceof Promise; // trueresult.value.then((value) => {if (value == 'ok') { /* агента уведомили */ }else { /* истёк тайм-аут */ }});}// В этом или в другом потоке:Atomics.notify(i32a, 0);

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

В этом примере мы не будем использовать параметр timeout при вызове Atomics.wait() и Atomics.waitAsync(). Этот параметр может быть использован для реализации условных конструкций, связанных с тайм-аутом.

Наш класс AsyncLock, представляющий мьютекс, работает с буфером SharedArrayBuffer и реализует следующие методы:

  • lock(): блокирует поток до того момента, пока у нас не появится возможность захватить мьютекс (применим только в потоке воркера).
  • unlock(): освобождает мьютекс (этот противоположность lock()).
  • executeLocked(callback): пытается захватить блокировку, не блокируя при этом поток. Этот метод может быть использован в главном потоке. Он планирует выполнение коллбэка на тот момент, когда мы сможем захватить блокировку.

Взглянем на то, как могут быть реализованы эти методы. Объявление класса включает в себя константы и конструктор, который принимает буфер SharedArrayBuffer.

class AsyncLock {static INDEX = 0;static UNLOCKED = 0;static LOCKED = 1;constructor(sab) {this.sab = sab;this.i32a = new Int32Array(sab);}lock() {/*  */}unlock() {/*  */}executeLocked(f) {/*  */}}

Здесь элемент i32a[0] содержит значение LOCKED или UNLOCKED. Он, кроме того, представляет то место в памяти, которое интересует Atomics.wait() и Atomics.waitAsync(). Класс AsyncLock обеспечивает следующие базовые возможности:

  1. Если i32a[0] == LOCKED и поток оказывается в состоянии ожидания (после вызова Atomics.wait() или Atomics.waitAsync()), наблюдая за i32a[0], он, в итоге, будет уведомлён.
  2. После того, как поток получит уведомление, он попытается захватить блокировку. Если ему это удастся, то, он, когда будет освобождать блокировку, вызовет Atomics.notify().

Синхронные захват и освобождение блокировки


Рассмотрим код метода lock(), который можно вызывать только из потока воркера.

lock() {while (true) {const oldValue = Atomics.compareExchange(this.i32a, AsyncLock.INDEX,/* Старое значение >>> */ AsyncLock.UNLOCKED,/* Новое значение >>> */ AsyncLock.LOCKED);if (oldValue == AsyncLock.UNLOCKED) {return;}Atomics.wait(this.i32a, AsyncLock.INDEX,AsyncLock.LOCKED); // <<< значение, ожидаемое в начале работы}}

Когда из потока вызывается метод lock(), сначала он пытается захватить блокировку, используя Atomics.compareExchange() для изменения состояния блокировки с UNLOCKED на LOCKED. Метод Atomics.compareExchange() пытается выполнить атомарную операцию изменения состояния блокировки, он возвращает исходное значение, находящееся в заданной области памяти. Если исходным значением было UNLOCKED, благодаря этому мы узнаем о том, что изменение состояния прошло успешно, и о том, что поток захватил блокировку. Ничего больше делать не нужно.

Если же Atomics.compareExchange() не смог изменить состояние блокировки, это значит, что блокировку удерживает другой поток. В результате поток, из которого вызван метод lock(), пытается воспользоваться методом Atomics.wait() для того чтобы дождаться момента освобождения блокировки другим потоком. Если в интересующей нас области памяти всё ещё хранится ожидаемое значение (в нашем случае AsyncLock.LOCKED), то вызов Atomics.wait() заблокирует поток. Возврат из Atomics.wait() произойдёт только тогда, когда другой поток вызовет Atomics.notify().

Метод unlock() освобождает блокировку, устанавливая её в состояние UNLOCKED, и вызывает Atomics.notify() для того чтобы уведомить агентов, ожидающих снятия этой блокировки. Предполагается, что операция изменения состояния блокировки всегда завершается успешно. Это так из-за того, что поток, выполняющий эту операцию, удерживает блокировку. Поэтому ничто другое в это время не должно вызывать метод unlock().

unlock() {const oldValue = Atomics.compareExchange(this.i32a, AsyncLock.INDEX,/* старое значение >>> */ AsyncLock.LOCKED,/* новое значение >>> */ AsyncLock.UNLOCKED);if (oldValue != AsyncLock.LOCKED) {throw new Error('Tried to unlock while not holding the mutex');}Atomics.notify(this.i32a, AsyncLock.INDEX, 1);}

В типичном случае всё происходит так: блокировка свободна и поток T1 захватывает её, меняя её состояние с помощью Atomics.compareExchange(). Поток T2 пытается захватить блокировку, вызывая Atomics.compareExchange(), но не может изменить её состояние. Затем T2 вызывает Atomics.wait(), этот вызов блокирует поток. Через некоторое время поток T1 освобождает блокировку и вызывает Atomics.notify(). Это приводит к тому, что вызов Atomics.wait() в T2 возвращает ok и поток T2 выходит из блокировки. После этого T2 пытается захватить блокировку снова. На этот раз ему это удаётся.

Тут могут возникнуть два особых случая. Их разбор призван продемонстрировать причины того, что Atomics.wait() и Atomics.waitAsync() проверяют наличие конкретного значения по заданному индексу элемента массива. Вот эти случаи:

  • T1 удерживает блокировку, а T2 пытается её захватить. Сначала T2 пытается изменить состояние блокировки, пользуясь Atomics.compareExchange(), но ему это не удаётся. Но потом T1 освобождает блокировку до того, как T2 успевает вызвать Atomics.wait(). А уже после этого T2 вызывает Atomics.wait(), откуда тут же происходит возврат значения not-equal. В подобном случае T2 переходит на следующую итерацию цикла и снова пытается захватить блокировку.
  • T1 удерживает блокировку, а T2 вызывает Atomics.wait() и ожидает её освобождения. T1 освобождает блокировку, T2 активируется (осуществляется возврат из Atomics.wait()) и пытается выполнить операцию Atomics.compareExchange() для захвата блокировки. Но другой поток, T3, оказался быстрее. Он уже успел сам захватить эту блокировку. В результате вызов Atomics.compareExchange() не позволяет T2 захватить блокировку. После этого T2 снова вызывает Atomics.wait() и оказывается заблокированным до того момента, пока T3 не освободит блокировку.

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

Асинхронный захват блокировки


Неблокирующий метод executeLocked() можно, в отличие от метода lock(), вызывать из главного потока. Он получает, в качестве единственного параметра, коллбэк, и планирует вызов коллбэка после успешного захвата блокировки.

executeLocked(f) {const self = this;async function tryGetLock() {while (true) {const oldValue = Atomics.compareExchange(self.i32a, AsyncLock.INDEX,/* старое значение >>> */ AsyncLock.UNLOCKED,/* новое значение >>> */ AsyncLock.LOCKED);if (oldValue == AsyncLock.UNLOCKED) {f();self.unlock();return;}const result = Atomics.waitAsync(self.i32a, AsyncLock.INDEX,AsyncLock.LOCKED);// ^ значение, ожидаемое в начале работыawait result.value;}}tryGetLock();}

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

Если вызов Atomics.compareExchange() захватить блокировку не позволил, нам нужно попытаться сделать это снова, в тот момент, когда блокировка, возможно, будет свободна. Но мы не можем заблокировать поток и ждать освобождения блокировки. Вместо этого мы планируем новую попытку захвата блокировки с использованием метода Atomics.waitAsync() и возвращаемого им промиса.

Если нам удалось выполнить метод Atomics.waitAsync(), то возвращённый этим методом промис разрешится тогда, когда поток, который удерживал блокировку, вызовет Atomics.notify(). После этого поток, который хотел захватить блокировку, как и прежде, снова пытается это сделать.

Тут возможны те особые случаи, что характерны для синхронной версии (блокировка освобождается между вызовами Atomics.compareExchange() и Atomics.waitAsync(); блокировку захватывает другой поток, делая это между моментами разрешения промиса и вызова Atomics.compareExchange()). Поэтому в подобном коде, применимом в реальных проектах, это необходимо учесть.

Итоги


В этом материале мы рассказали о низкоуровневых примитивах синхронизации Atomics.wait(), Atomics.waitAsync() и Atomics.notify(). Мы разобрали пример создания на их основе мьютекса, который можно применять и в главном потоке, и в потоках воркеров.

Пригодятся ли в ваших проектах Atomics.wait(), Atomics.waitAsync() и Atomics.notify()?
Подробнее..

Старший инженер-проектировщик Dyson оновых пылесосах, не взлетевших продуктах и RampD

20.07.2020 16:23:27 | Автор: admin
Крис Винсентвправом верхнем углу. Джеймс Дайсон, электромобиль, стиральная машина и робот-пылесос вправом нижнемКрис Винсентвправом верхнем углу. Джеймс Дайсон, электромобиль, стиральная машина и робот-пылесос вправом нижнем

У Dyson время от времени выходят новые модели пылесосов, но если глубоко их не изучать, кажется, что они не особо отличаются. Вот у меня есть V8, а надо ли его менять на V11 за 50штук? (Спойлер: если только вы не очень богатый разраб-технофил, вообще не обязательно!) А какая на самом деле разница? И в чем вообще фишка этих незаметных обновлений? А еще что там с электротачкой Dyson? А с роботом пылесосом? А новая стиралка будет? Обо всём этом я поговорил с Крисом Винсентом старшим инженером-проектировщиком Dyson, который работает в компании уже седьмой год. Заодно Крис рассказал о том, как устроены R&D-центры, кого выпускают из Технологического института Дайсона и в чем фишка James Dyson Awards.


Объясни для чайников, как работает циклонная технология?

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

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

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

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

А что нового с технической точки зрения в ваших последних моделях. Чем V11 круче V8?

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

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

Плюс, мы изменили химический состав батареи. Увеличилось не только время работы, но и мощность всасывания.

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

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

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

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

Работа над V11 на ранних стадиях была немного легче, потому что он похож на V10 больше, чем на предыдущие модели. Некоторые детали V10 мы смогли применить в работе над прототипами V11. Но по большей части во время разработки мы применяем 3D-печать. В любом случае речь идет о сотнях и сотнях прототипов. Но некоторые из них не полностью воспроизводят конечный продукт, а только его внешнюю часть. Внутри может находиться кусок металла для веса чтобы можно было подержать такую штуку в руках, понять, например, где центр тяжести, и поработать над удобством хвата.

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

Мы внедряем улучшения постепенно. Некоторые детали могут оставаться вообще идентичными. И это неплохо с точки зрения разработки не нужно каждый раз воссоздавать все части аппарата.

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

Как главный по дизайну расскажи, что делает продукты Dyson узнаваемыми? Не только ведь сочетание фиолетового и серого?

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

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

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

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

А сумасшедшие, не простые идеи у вас возникают?

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

Когда V11 перестает работать, он издает такой прикольный звук боу-у-у. Это специально так разработано или случайность?

на видео модель V10, но звук такой же

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

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

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

Ты знаешь о существовании комьюнити Thingiverse, где люди делятся 3D-моделями для улучшения существующих продуктов? Несколько лет назад я видел там решения, которые позволяют крепить к трубе вашего пылесоса маленькие щетки из комплекта. Прошло несколько лет, и у вас комплекте появляется похожая штука. Вы чем-то оттуда вдохновились?

Слева родной дайсоновский держатель (2019), справа модель с Thingiverse (2017). Фото: trustedreviews.comСлева родной дайсоновский держатель (2019), справа модель с Thingiverse (2017). Фото: trustedreviews.com

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

Когда мы выпускали первые модели V6 и V8, мы думали над двумя вещами: док-станцией и держателем для аксессуаров. В то время мы посчитали, что людям не понравится дополнительный вес на трубе пылесоса. Особенно это критично, когда пылесос используют на весу, для чистки чего-то наверху. Чем больше веса на конце трубы, тем сложнее держать устройство. Со временем, если мы замечаем, что люди чего-то особенно хотят, то такого рода вещи несложно реализовать. Но в основном мы стремимся сделать продукт сразу таким, каким мы его видим, и не видоизменять его в дальнейшем.


Я впервые увидел вашего робота-пылесоса 360 Eye в 2016 году на выставке в Берлине. Он был стильный и крутой, но так и не стал популярным (вероятно из-за высокой цены). Вы все еще разрабатываете этого робота или другую модель?

Мы недавно выпустили пылесос 360 Heurist в некоторых странах. Он стал своего рода обновлением оригинального 360 Eye.

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

А как насчет стиральной машины? Ждать чего-то нового?

Да, мы разрабатывали стиральную машину, и она неплохо работала. Но то количество улучшений, которое мы внедрили, клиенты не оценили. На тот момент она лучше стирала и могла делать это быстрее благодаря горизонтальному вращающемуся барабану. У большинства вертикальных стиральных машин барабан вращался по часовой стрелке. А у нас он был двойным и вращался и против часовой стрелки тоже стирка напоминала ручную с трением одежды друг о друга. Но для этого пришлось усложнить привод барабана, и поэтому машина оказалась немного дороже, чем у конкурентов.

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

И раз уж мы заговорили о несостоявшихся продуктах, расскажешь про ваш электрокар?

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

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

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


Каким должен быть инженер или дизайнер, чтобы попасть к вам на работу?

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

Но мы все равно готовы рассматривать кандидатуры и с другим бэкграундом зависит от того, как они себя представят. Я помню, когда отправил свое резюме, меня попросили составить портфолио, которого у меня, естественно, не было на тот момент. Было несколько дизайн-проектов, которые я еще не оформил. Пришлось быстро это сделать. Когда я пошел на собеседование, то взял с собой все, что у меня было на тот момент: диссертацию, дипломный проект по машиностроению, который был посвящен роботизированному захвату. А еще я взял с собой небольшую коробку с секретным замком хотел показать интервьюерам и объяснить хитрость с механизмом внутри. Им понравилось.

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

Но мы не обязательно хотим нанимать только людей с многолетним опытом. Это не обязательно должен быть опыт работы в большой инженерной компании. Противоположное часто даже предпочтительнее.

Это и побудило Дайсона основать свой технологический институт? Чем там отличается подход к обучению?

Я бы не сказал, что этот институт выпускает каких-то других специалистов. Мы очень ценим людей, которые выходят из других университетов. Но одним из главных факторов создания технологического института была нехватка инженеров. Если мы хотим делать больше [продуктов], нам, вероятно, придется готовить их самим.

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

Студенты Технологического института Дайсона получают привычную инженерную степень. Но в то же время они много времени проводят на рабочем месте, разрабатывая реальные проекты в течение года. Они погружаются в процесс разработки и видят каждую его часть. При этом студентыучаствуют в разных проектах, начиная с электроники, заканчивая автомобильным направлением. Когда они получают такой широкий спектр знаний, они могут отлично применять их. А еще все они растут на устройствах, которые мы считали в свое время футуристическими с сенсорными экранами и распознаванием голоса. Все эти вещи для них просто нормальны. Поэтому они потенциально могут лучше понять, какими должны быть устройства будущего.

Чем крут конкурс James Dyson Award?

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

Мы помогаем участникам стать самостоятельными. Мы вместе с ними определяем, в чем именно заключается их интеллектуальная собственность. У нас есть специальный отдел, который помогает им понять, что нужно сделать, чтобы защитить свои идеи. В этом у нас большой опыт. То есть интеллектуальная собственность остается за ними. А далее мы даем им призовые деньги, чтобы развить эту идею дальше. Контракта с нами нет. Нет никакой обязаловки. Это больше инвестиции в конкретного человека и университет, из которого он пришел.

У Dyson много патентов. Один из последних и актуальных описывает встроенный в наушники очиститель воздуха. Что это такое? Ждать нам такой продукт или нет?

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

А сколько у вас R&D-офисов? Сколько там сотрудников? Как выстроена работа?

У нас есть два центра в Малмсбери и Великобритании. Там у нас два корпуса: D9 и D8. В D9 у нас около 450 ученых и инженеров, а в D8 еще больше. Вероятно, 1500.

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

Исследования аккумуляторов проводятся в Великобритании и США.

Основные научно-исследовательские и опытно-конструкторские работы проходят в Великобритании и Сингапурском центре развития. Там все процессы построены вокруг доступа к инструментам производства прототипов: токарным станкам, фрезам, 3D-принтерам, лазерным резакам.

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

В работе мы используем системы, которые работают. Важнее не ПО, а то, насколько хорошо всё связано друг с другом. Мы используем PLM (Product Lifecycle Management)это софт для управления сроком службы продуктов он позволяет нам следить за каждой деталью, которую мы производим. У каждой детали есть CAD-модель, мы знаем её массу, цену, материал. И все эти детали можно объединить в один продукт. Все разработчики работают в этой системе одновременно и видят изменения, которые вносят другие.

Подробнее..

Перевод Что нового в Node.js 15?

22.01.2021 20:15:37 | Автор: admin
Делимся переводом статьи, в которой собраны подробности о новых функциях 15-й версии Node.js.

Версия Node.js 15 была выпущена 20 октября 2020 года. Среди основных изменений:

  • режим throw при необработанных отклонениях
  • особенности языка V8 8.6
  • NPM 7
  • экспериментальная поддержка QUIC
  • N-API Version 7
  • доработка API асинхронного локального хранилища (Async Local Storage)

Давайте подробнее рассмотрим, что эти нововведения из себя представляют и как их можно использовать.

Использование NVM для обзора Node


В предыдущей статье мы разобрали инструкции по использованию NVM (Node Version Manager) для управления версиями Node.js и NPM. В нашей среде были установлены Node.js 12.16.0 и NPM 6.14.8. Запустив nvm install node, мы установили Node.js 15.4.0 и NPM7.0.15.

У нас открыто два окна, в одном Node.js 12, а в другом Node.js 15.

В окне node12:

$ nvm use 12Now using node v12.16.0 (npm v6.14.8)

В окне node15:

$ nvm use 15Now using node v15.4.0 (npm v7.0.15)

Теперь мы можем исследовать эту версию.

Режим Throw при необработанном отклонении промиса (promise)


Событие unhandledRejection генерируется каждый раз, когда промис (promise) отклоняется и обработчик ошибок не прикрепляется к промису в ходе цикла обработки событий. Начиная с версии Node.js 15, режим по умолчанию для unhandledRejection был изменен с warn на throw. В режиме throw, если хук unhandledRejection не установлен, unhandledRejection генерируется как исключение, не пойманное методом catch.

Создайте программу, чтобы промис отклонялся (rejected) с сообщением об ошибке:

function myPromise() {  new Promise((_, reject) =>    setTimeout(      () =>        reject({          error: 'The call is rejected with an error',        }),      1000    )  ).then((data) => console.log(data.data));}myPromise();

Когда вы запускаете этот код в окне node12, появляется длинное сообщение с предупреждением:

$ node myPromise.js(node:79104) UnhandledPromiseRejectionWarning: #<Object>(node:79104) UnhandledPromiseRejectionWarning: Unhandled promise rejection. This error originated either by throwing inside of an async function without a catch block, or by rejecting a promise which was not handled with .catch(). To terminate the node process on unhandled promise rejection, use the CLI flag `--unhandled-rejections=strict` (see https://nodejs.org/api/cli.html#cli_unhandled_rejections_mode). (rejection id: 1)(node:79104) [DEP0018] DeprecationWarning: Unhandled promise rejections are deprecated. In the future, promise rejections that are not handled will terminate the Node.js process with a non-zero exit code.Users that have an unhandledRejection hook should see no change in behavior, and its still possible to switch modes using the --unhandled-rejections=mode process flag.

При запуске этого кода в окне node15 генерируется ошибка UnhandledPromiseRejection:

$ node myPromise.jsnode:internal/process/promises:227          triggerUncaughtException(err, true /* fromPromise */);          ^[UnhandledPromiseRejection: This error originated either by throwing inside of an async function without a catch block, or by rejecting a promise which was not handled with .catch(). The promise rejected with the reason "#<Object>".] {  code: 'ERR_UNHANDLED_REJECTION'}

Добавьте обработчик ошибок в ветвь then в приведенном ниже коде (.catch((error) => console.log(error.error)) также работает).

function myPromise() {  new Promise((_, reject) =>    setTimeout(      () =>        reject({          error: 'The call is rejected with an error',        }),      1000    )  ).then(    (data) => console.log(data.data),    (error) => console.log(error.error)  );}myPromise();

Теперь код запускается корректно в обоих окнах (node12 и node15):

$ node myPromise.jsThe call is rejected with an error

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

function myPromise() {  new Promise((_, reject) =>    setTimeout(      () =>        reject({          error: 'The call is rejected with an error',        }),      1000    )  ).then((data) => console.log(data.data));}myPromise();process.on('unhandledRejection', (reason, promise) => {  console.log('reason is', reason);  console.log('promise is', promise);  // Application specific logging, throwing an error, or other logic here});

Хук unhandledRejection работает как в Node.js 12, так и в Node.js 15. После его установки, unhandledRejection обрабатывается как нужно.

$ node myPromise.jsreason is { error: 'The call is rejected with an error' }promise is Promise { <rejected> { error: 'The call is rejected with an error' } }

V8 8.6 Новые возможности языка


V8, движок JavaScript, обновлен с 8.4 до 8.6. версии. Помимо разных хитростей для повышения производительности, новая версия V8 обладает следующими фичами:

  • Promise.any() и AggregateError (из V8 8.5)
  • await setTimeout и AbortController (экспериментальная фича)
  • String.prototype.replaceAll() (из V8 8.5)
  • Логические операторы присваивания &&=, ||= и ??= (из V8 8.5)

Promise.any() и AggregateError


Для начала давайте рассмотрим существующий метод Promise.all().

Promise.all() принимает итерируемое из промисов в качестве входных данных и возвращает один промис, который исполняется как массив результатов входных промисов.

Следующая программа вызывает Promise.all() для двух исполненных (resolved) промисов:

function myPromise(delay) {  return new Promise((resolve) =>    setTimeout(      () =>        resolve({          data: The data from ${delay} ms delay,        }),      delay    )  );}async function getData() {  try {    const data = await Promise.all([myPromise(5000), myPromise(100)]);    console.log(data);  } catch (error) {    console.log(error);  }}getData();

Promise.all() возвращает промис, который исполнится, когда все входные промисы будут исполнены (resolved), или если iterable не содержит обещаний:

$ node myPromise.js[  { data: 'The data from 5000 ms delay' },  { data: 'The data from 100 ms delay' }]

Следующая программа вызывает Promise.all() для двух отклоненных (rejected) промисов.

function myPromise(delay) {  return new Promise((_, reject) =>    setTimeout(      () =>        reject({          error: The error from ${delay} ms delay,        }),      delay    )  );}async function getData() {  try {    const data = await Promise.all([myPromise(5000), myPromise(100)]);    console.log(data);  } catch (error) {    console.log(error);  }}getData();

Promise.all() немедленно делает реджект на любое отклонение входного промиса или на любую ошибку в момент исполнения с возвратом сообщения об этой ошибке:

$ node myPromise.js{ error: 'The error from 100 ms delay' }

Promise.any() новый метод в Node.js 15. Он противоположен методу Promise.all(). Promise.any() принимает итерируемый объект, содержащий объекты обещаний Promise. И, как только одно из обещаний Promise в iterable выполнится успешно, метод возвратит единственный промис со значением выполненного обещания.

Следующая программа вызывает Promise.any() для двух исполненных (resolved) промисов:

function myPromise(delay) {  return new Promise((resolve) =>    setTimeout(      () =>        resolve({          data: The error from ${delay} ms delay,        }),      delay    )  );}async function getData() {  try {    const data = await Promise.any([myPromise(5000), myPromise(100)]);    console.log(data);  } catch (error) {    console.log(error);    console.log(error.errors);  }}getData();

Promise.any() возвращает первый исполненный (resolved) промис:

$ node myPromise.js{ data: 'The error from 100 ms delay' }

Следующая программа вызывает Promise.any() для двух отклоненных (rejected) промисов:

function myPromise(delay) {  return new Promise((_, reject) =>    setTimeout(      () =>        reject({          error: The error from ${delay} ms delay,        }),      delay    )  );}async function getData() {  try {    const data = await Promise.any([myPromise(5000), myPromise(100)]);    console.log(data);  } catch (error) {    console.log(error);    console.log(error.errors);  }}getData();

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

$ node myPromise.js[AggregateError: All promises were rejected][  { error: 'The error from 5000 ms delay' },  { error: 'The error from 100 ms delay' }]

Await setTimeout и AbortController


В предыдущих примерах мы использовали setTimeout внутри вызова промиса.

SetTimeout в WindowOrWorkerGlobalScope, использует коллбэк. Однако timers/promises предоставляют промисифицированную версию setTimeout, которую можно использовать с async/await.

const { setTimeout } = require('timers/promises');async function myPromise(delay) {  await setTimeout(delay);  return new Promise((resolve) => {    resolve({      data: The data from ${delay} ms delay,    });  });}async function getData() {  try {    const data = await Promise.any([myPromise(5000), myPromise(100)]);    console.log(data);  } catch (error) {    console.log(error);    console.log(error.errors);  }}getData();

AbortController это объект JavaScript, который позволяет прервать один или несколько веб-запросов по желанию. Мы привели примеры использования AbortController в другой статье про useAsync.

И await setTimeout, и AbortController являются экспериментальными фичами.

String.prototype.replaceAll()


Давайте рассмотрим существующий метод String.prototype.replace().

replace() возвращает новую строку с несколькими или всеми сопоставлениями с шаблоном, заменёнными на заменитель. Шаблон может быть строкой или регулярным выражением. Заменитель может быть строкой или функцией, вызываемой для каждого сопоставления.

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

'20+1+2+3'.replace('+', '-');

Использование данного оператора даст 201+2+3.

Чтобы заменить все + на -, необходимо использовать регулярное выражение.

'20+1+2+3'.replace(/\+/g, '-');

Использование указанного выше оператора даст 201-2-3.

Метод replaceAll() новинка в Node.js 15. Благодаря его использованию, нам не придется использовать регулярное выражение. Этот метод возвращает новую строку со всеми сопоставлениями с шаблоном, замененными на заменитель. Шаблон может быть строкой или регулярным выражением, а заменитель может быть строкой или функцией, вызываемой для каждого сопоставления.

Благодаря методу replaceAll(), нам можно не использовать регулярное выражение для замены всех + на -.

'20+1+2+3'.replaceAll('+', '-');

Выполнение данного оператора дает 201-2-3.

Логические операторы присваивания &&=, ||= и ??=


Логический оператор присваивания AND (x &&= y) выполняет операцию присваивания, только если x истинно.

x &&= y эквивалентно x && (x = y), но не эквивалентно x = x && y.

let x = 0;let y = 1;x &&= 0; // 0x &&= 1; // 0y &&= 1; // 1y &&= 0; // 0

Логический оператор присваивания OR (x ||= y) выполняет операцию присваивания, только если x ложно.

x || = y эквивалентно x || (x = y), но не эквивалентно x = x || у.

let x = 0;let y = 1;x ||= 0; // 0x ||= 1; // 1y ||= 1; // 1y ||= 0; // 1

Логический оператор присваивания nullish (x ?? = y) выполняет операцию присваивания, только если x имеет значение NULL (null или undefined).

x ??= y эквивалентно x ?? (x = y), и не эквивалентно x = x ?? у.

let x = undefined;let y = '';x ??= null; // nullx ??= 'a value'; // "a value"y ??= undefined; // ""y ??= null; // ""

Другие изменения


Помимо режима throw при необработанном отклонении промиса и новых языковых фич V8 8.6, в Node.js 15 есть следующие изменения:

NPM 7: Много изменений, в том числе автоматическая установка одноранговых зависимостей, усовершенствование пакетов и yarn.lock файлов, поддержка рабочего пространства и др. Все это описано в данной статье по ссылке.

QUIC: Экспериментальная поддержка протокола транспортного уровня UDP, который является основным протоколом для HTTP / 3. QUIC включает встроенную систему безопасности с TLS 1.3, управление потоком, исправление ошибок, миграцию подключений и мультиплексирование.

N-API Version 7: API для создания собственных аддонов. Не зависит от среды выполнения JavaScript, лежащей в основе, и поддерживается как часть самого Node.js.

Усовершенствование API асинхронного локального хранилища (Async Local Storage): Предоставляет возможность для более современного логирования и анализа фич для крупномасштабных приложений.

Заключение


В новой версии Node.js 15 большое количество новых функций и улучшений, в том числе и достаточно существенных.

Попробуйте новую версию и будьте готовы к обновлению проектов.

Спасибо за внимание! Надеюсь, статья была полезна для вас.
Подробнее..

JavaScript Стек вызовов и магия его размера

03.04.2021 18:14:06 | Автор: admin

Привет, Хабровчане!

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

 RangeError: Maximum call stack size exceeded. 

Но не каждый разработчик задумывался о том, а что означает "размер стэка вызовов" и каков же этот размер? А в чем его измерять?

Думаю, те, кто работают с языками, напрямую работающими с памятью, смогут легко ответить на этот вопрос, а вот типичный фронтэнд разработчик скорее всего задает себе подобные вопросы впервые. Что-ж, попробуем разобраться!

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

О чем ты вообще, автор?

Для статьи важно понимание таких понятий как Execution Stack, Execution Context. Если вы не знаете, что это такое, то советую об этом почитать. На данном ресурсе уже было достаточно хороших статей на эту тему. Пример -http://personeltest.ru/aways/habr.com/ru/company/ruvds/blog/422089/

Когда возникает эта ошибка?

Разберем на простом примере - функция, которая рекурсивно вызывает сама себя.

const func = () => {    func();}

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

А что если подглядеть, сколько же раз выполнилась функция перед тем, как возникла ошибка?

На данном этапе код запускается в Chrome DevTools последней версии на март 2021. Результат будет различаться в разных браузерах. В дальнейшем в статье я упомяну об этом.

Для эксперимента будем использовать вот такой код:

let i = 0;const func = () => {  i++;  func();};try {  func();} catch (e) {  // Словили ошибку переполнения стэка и вывели значение счетчика в консоль  console.log(i);}

Результатом вывода в консоль стало число в 13914. Делаем вывод, что перед тем, как переполнить стэк, наша функция вызвалась почти 14 тысяч раз.

Магия начинается тогда, когда мы начинаем играться с этим кодом. Допустим, изменим его вот таким образом:

let i = 0;const func = () => {  let someVariable = i + 1;  i++;  func();};try {  func();} catch (e) {  console.log(i);}

Единственное, что мы добавили, это объявление переменной someVariableв теле функции. Казалось бы, ничего не поменялось, но число стало меньше. На этот раз функция выполнилась 12523 раз. Что более чем на тысячу меньше, чем в прошлом примере. Чтобы убедиться, что это не погрешность, пробуем выполнять такой код несколько раз, но видим одни и те же результаты в консоли.

Почему же так? Что изменилось? Как понять, посмотрев на функцию, сколько раз она может выполниться рекурсивно?!

Магия раскрыта

Отличие второго примера от первого - наличие дополнительной переменной внутри тела функции. На этом все. Соответственно, можно догадаться, именно из-за этого максимальное количество рекурсивных вызовов стало меньше. Что-ж, а что, если у нас будет не одна, а четыре переменных внутри функции? По этой логике, количество рекурсивных вызовов станет еще меньше? Проверим:

let i = 0;const func = () => {  let a = i + 1;  let b = a + 1;  let c = b + 1;  let d = c + 1;  let e = d + 1;  i++;  func();};try {  func();} catch (e) {  console.log(i);}

По этой логике, значение счетчика должно стать еще меньше. Выдыхая, видим вывод - 8945. Ага, оно стало еще меньше. Значит, мы на правильном пути. Хочу привести небольшую аналогию, чтобы даже самым маленьким стало понятно.

Execution Stack (Call Stack) - это емкость с водой. Изначально она пустая. Так получилось, что эта емкость с водой стоит прямо на электрической проводке. Как только емкость переполнится, вода проливается на провода, и мы видим ошибку в консоли. При каждом новом рекурсивном вызове функции в стэк падает капелька воды. Само собой, чем капелька воды крупнее, тем быстрее наполнится стэк.

Емкости бывают разные по размеру. И размер емкости в данном примере - эторазмер коллстэка. А точнее - количество байт, которое он максимально может в себе удержать. Как гласит статья про Call Stack (Execution Stack), которую я приложил в начале, на каждый вызов функции создается Execution Context - контекст вызова функции (не путать с this). И упрощая, в нем, помимо разных "подкапотных" штук, содержатся все переменные, которые мы объявили внутри функции. Как Execution Context, так и каждая переменная внутри него имеют определенный размер, который они занимают в памяти. Сложив эти два размера мы и получим "размер" капли, которая капает в кувшин при каждом рекурсивном вызове функции.

У нас уже достаточно много данных. Может быть, поэкспериментируем еще? А давайте попробуем вычислить, какой размер коллстэка в движке, который использует Chrome?

Математика все-таки пригодилась

Как мы выяснили, у нас есть две неизвестные, которые составляют размер функции (капельки, которая падает в емкость). Это размер самого Execution Stack, а так же сумма размеров всех переменных внутри функции. Назовем первую N, а вторую K. Сам же неизвестный размер коллстэка обозначим как X.

В итоге - количество байт, которое занимает функция (в упрощенном виде) будет:

FunctionSize = N + K * SizeOfVar

SizeOfVar в данном случае - количество байт, которые занимает переменная в памяти.

Учитывая, что мы знаем количество вызовов первой функции, в теле которой не объявляются переменные, размер коллстэка можно выразить как:

X = (N + 0 * SizeOfVar)* 13914 = N * 13914

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

X = (N + 5 * SizeOfVar) * 8945

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

N * 13914 = (N + 5 * SizeOfVar) * 8945

Выглядит неплохо. У нас тут две неизвестные переменные - N и SizeOfVar. Если N мы не можем откуда-то узнать, то что насчет SizeOfVar? Заметим, что во всех функциях, которые фигурировали выше, переменные хранили значение с типом "number", а значит, нужно просто узнать, сколько же байт в памяти занимает одна такая переменная.

С помощью великого гугла получаем ответ - "Числа в JavaScript представлены 64-битными значениями с плавающей запятой. В байте 8 бит, в результате каждое число занимает 64/8 = 8 байт." Вот она - последняя неизвестная. 8 байт. Подставляем ее в наше уравнение и считаем, чем равно N.

N * 13914 = (N + 5 * 8) * 8945

Упрощаем:

N * 13914 = N * 8945 + 40 * 8945

Если выразить отсюда N, то получим ответ: N равно приблизительно 72. В данном случае 72 байтам.

Теперь, подставив N = 72 в самое первое уравнение, получим, что размер коллстэка в Chrome равен... 1002128 байтов. Это почти один мегабайт. Не так уж и много, согласитесь.

Мы получили какое-то число, но как убедиться, что наши расчеты верны и число правильное? А давайте попробуем с помощью этого числа спрогнозировать, сколько раз сможет выполниться функция, внутри которой будет объявлено 7 переменных типа 'number'.

Считаем: Ага, каждая функция будет занимать (72 + 7 * 8) байт, это 128. Разделим 1002128 на 128 и получим число... 7829! Согласно нашим расчетам, такая функция сможет рекурсивно вызваться именно 7829 раз!Идем проверять это в реальном бою...

Мы были очень даже близки. Реальное число отличается от теоретического всего на 3. Я считаю, что это успех. В наших расчетах было несколько округлений, поэтому результат мы посчитали не идеально, но, очень-очень близко. Небольшая погрешность в таком деле - нормально.

Получается, что мы посчитали все верно и можем утверждать, что размер пустого ExecutionStack в Chrome равен 72 байтам, а размер коллстэка - чуть меньше одного мегабайта.

Отличная работа!

Важное примечание

Размер стэка разнится от браузера к браузеру. Возьмем простейшую функцию из начала статьи.Выполнив ее в Сафари получим совершенно другую цифру. Целых 45606 вызовов. Функция с пятью переменными внутри выполнилась бы 39905 раз. В NodeJS числа очень близки к Chrome по понятным причинам. Любопытный читатель может проверить это самостоятельно на своем любимом движке JavaScript.

А что с непримитивами?

Если с числами все вроде бы понятно, то что насчет типа данных Object?

let i = 0;const func = () => {  const a = {    key: i + 1,  };  i++;  func();};try {  func();} catch (e) {  console.log(i);}

Простейший пример на ваших глазах. Такая функция сможет рекурсивно вызваться 12516. Это практически столько же, сколько и функция с одной переменной внутри. Тут в дело вступает механизм хранения и передачи объектов в JS'е - по ссылке. Думаю, большинство уже знают об этом.

А что с этим? А как поведет себя вот это? А что с *?

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

Итоги:

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

  • Размер стэка измеряется в байтах.

  • Чем "тяжелее" функция, тем меньше раз она может быть вызвана рекурсивно.

  • Размер стэка в разных движках различается.

Вопрос особо любознательным: А сколько переменных типа "number" должно быть объявлено в функции, чтобы она могла выполниться рекурсивно всего два раза, после чего стэк переполнится?

Подробнее..

Декомпиляция node.js в Ghidra

16.04.2021 14:07:36 | Автор: admin


Приветствую,


Вам когда-нибудь хотелось узнать, как же именно работает программа, которой вы так активно пользуетесь, игра, в которую часто играете, прошивка какого-нибудь устройства, которое что-то делает по расписанию? Если да, то для этого вам потребуется дизассемблер. А лучше декомпилятор. И если с x86-x64, Java, Python ситуация известная: этих ваших дизассемблеров и декомпиляторов полным-полно, то с другими языками всё обстоит немного сложнее: поисковые машины уверенно утверждают It's impossible.



Что ж, мы решили оспорить данное утверждение и произвести декомпиляцию NodeJS, а именно выхлоп, который выдаёт npm-пакет bytenode. Об этом подробнее мы и расскажем по ходу статьи. Заметим, что это уже вторая статья в серии о нашем плагине для Ghidra (первый материал был также опубликован в нашем блоге на Хабре). Поехали.


Часть нулевая: забегая вперёд


Да, нам действительно удалось произвести декомпиляцию NodeJS в Ghidra, преодолев путь от этого кода:



К этому:



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


  • Парсинг вывода bytenode. Кроме исполняемого кода, он также парсит пул констант, аргументы функций, области видимости, обработчики исключений, контекстные переменные и многое другое.
  • Полноценная загрузка исследуемого jsc-файла в Ghidra, с отображением пользователю необходимых для реверс-инжиниринга данных.
  • Поддержка всех опкодов, в том числе с различными вариациями их длины расширенных (wide) и экстрарасширенных (extra-wide).
  • Подтягиваются вызовы функций стандартной библиотеки (Intrinsic и Runtime-вызовы).
  • Анализируются все перекрёстные ссылки, даже в обфусцированном коде, что дает возможность исследовать любые NodeJS-приложения.

Конечно, есть и ряд ограничений. О них в конце статьи.

Составные части плагина


Сейчас модуль состоит из четырёх частей:


  1. Загрузчик: парсит файл, создаёт необходимые секции для кода и констант. Тем, кому дизассемблер ближе декомпилятора, пригодится.
  2. Анализатор: работает после загрузчика. Расставляет перекрёстные ссылки, убирает stub-код, сгенерированный компилятором (упрощает анализ), следит за контекстом исполнения.
  3. Дизассемблер и по совместительству декомпилятор. Благодаря технологиям, реализованным в Ghidra, при написании дизассемблера вы одновременно получаете и декомпилятор, что очень удобно. Для этого используется внутренний язык Гидры SLEIGH.
  4. Последняя часть модуля инжектор конструкций на PCode (языке промежуточного представления в Ghidra, аналоге микрокода в IDA). Инжектор формирует промежуточное представление для декомпилятора в тех случаях, когда через SLEIGH это реализовать сложно, или даже невозможно.

Процесс создания


Как это обычно и бывает, когда ты занимаешься реверс-инжинирингом всякой дичи, пришёл один бинарь. В нашем случае он имел расширение .jsc и запускался с помощью node.exe. Гугление по данной связке привело к bytenode пакету для Node.js, позволяющему собрать исходник на JavaScript в виде jsc-файла с байткодом, который гарантированно запустится на той же версии Ноды, если в ней установлен этот самый bytenode.


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


Но ведь в node, скажете вы, уже существует встроенный дизассемблер, и с его помощью можно смотреть на то, что происходит в запускаемом файле. Да, это так. Но он скорее рассчитан на то, что исходный файл у вас всё-таки имеется. У нас же его не было. Поэтому, сделав волевое усилие, мы приняли решение написать этот, будь он проклят, декомпилятор! Знали бы мы тогда, какие мучения нас ждут, взялись бы за проект? Конечно, взялись бы!



(Пример jsc-файла в hex-редакторе. Видны некоторые заголовки и строки)


Погружение и сборка node.js


Итак, что нам необходимо, чтобы начать разбор формата? Теория, в которой рассказывается о принципах работы Ноды? Кто вообще так делает? (Между прочим, данная теория прекрасно изложена в статье по ссылке.) Нам нужны исходники Node! Более того, они должны быть той же версии, в которой собран jsc-файл. Иначе не заработает.


Сделав клон репозитория и попытавшись его собрать, мы наткнулись на первые трудности: не собирается. Конечно, учитывая размеры репозитория и его кроссплатформенность удивляться нечему. Тем более последнюю на момент написания статьи версию Visual Studio 2019 в системе сборки Node.js стали поддерживать не так давно. Поэтому, чтобы собрать именно нужную нам v8.16, пришлось клонировать обе ветки: современную и нужную нам, а затем сравнивать систему сборки.


Система сборки состоит из набора Python-скриптов, батников и sln-проектов. Python-скрипты генерируют проекты для Visual Studio, подставляются дефайны, а затем Студия всё это дело собирает. Действительно, собирает. Но только в режиме сборки Release оно почему-то работает, а в Debug нет. А для наших целей нужна была именно дебажная сборка.


В ходе разборок со Студией, которые отняли несколько дней, выяснилось, что виной всему флаги препроцессора: они почему-то ломают работу интерпретатора именно при взаимодействии с bytenode. Ну ничего, флаги во всех 10 проектах для всех вариантов сборок были поправлены, и дебажная Нода была успешно собрана.



(Часть проекта NodeJS в Visual Studio)


Теперь с её помощью можно успешно отлаживать исходный код самой Node.js. Кроме того, появляются дополнительные флаги трассировки при исполнении, которые ещё больше помогают понять, что происходит при исполнении кода.


Парсинг формата


Было установлено огромное количество брейкпоинтов (точек останова) во всех местах, где, по идее, мог начинаться разбор jsc-файла, и наконец-то была запущена отладка.


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


И тут началось.


Уже давно никто не удивляется, что в крупных проектах на C++ используется огромное количество макросов. Да, несомненно, они помогают при написании кода сократить большие и повторяющиеся участки, но при отладке они совсем не помогают, а делают этот процесс очень сложным и долгим, особенно если нужно найти, где что объявляется или присваивается, а присваивается и объявляется оно в макросе, который состоит примерно из 20 строк.


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


Конечно, навигация по JSON (о нём расскажем чуть позже) та ещё весёлая задача, поэтому было принято не менее важное решение, очень сильно повлиявшее на наши дальнейшие запросы, перейти на Ghidra. Это решение влекло за собой следующие проблемы, которые пришлось решать:


  • перенос парсера с Python на Java и написание загрузчика jsc-формата;
  • создание нового процессорного модуля, который позволит дизассемблировать V8 (именно этот движок используется в Node.js);
  • реализация логики самих опкодов V8 с целью получения декомпилированного листинга.

Загрузчик для Ghidra 1


Первый загрузчик был простым: он разбирал JSON, который генерировался Python-версией парсера, создавал все секции, объекты, загружал байткод. Пока одна часть команды писала разборщик, другая её часть занималась реализацией опкодов на SLEIGH, параллельно создавая концепт плагина для Ghidra. Таким образом, к моменту, когда этот вариант загрузчика был готов, вся команда могла работать совместно.


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



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


Загрузчик для Ghidra 2


На этом варианте мы и остановились. Как уже было сказано, он умеет грузить jsc-формат напрямую, разбирать и создавать структуры, делать перекрёстные ссылки, анализировать всё что нужно и как это нужно Гидре. Да и вообще, этот вариант нам нравился больше, так как у него был выше потенциал уже на старте. Единственный нюанс такой загрузчик пришлось куда дольше писать. Но результат того стоит.


С вводными ознакомились, теперь пора углубиться в настоящий кошмар. И первым нас встречает загрузчик.


Внутрянка загрузчика


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


  • разобрать jsc-файл на структуры, которые будут затем использованы дизассемблером, анализатором, декомпилятором;
  • отобразить пользователю плагина все те структуры, которые потребуются при реверс-инжиниринге: код, строки, числа, контексты, обработчики исключений и многое другое;
  • переименовать все объекты, у которых есть названия, и у которых их нет (обычный код, обёрнутый в скобки);
  • идентифицировать встроенные функции Node.js, которые вызываются исключительно по индексам.

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


Загруженный в Ghidra файл обычно выглядит как-то так:



Что на картинке
  1. Слева сверху видны сегменты. В jsc их нет, но нам пришлось создать их, чтобы сгруппировать сходные типы данных, и отделить их от кода.
  2. Слева идёт список функций. В случае с файлом, изображённым на скриншоте выше, они все обфусцированные, поэтому имеют одинаковые имена. Но это никак не мешает плагину выстраивать перекрёстные ссылки.
  3. В центре скриншота виден дизассемблерный листинг. Вам в любом случае придётся с ним работать, так как декомпилятор не всесилен.
  4. Справа виден декомпилированный C-подобный листинг. Как видим, он значительно облегчает анализ jsc-приложения.

Дизассемблер


Собственно, для того чтобы весь загруженный набор байтов стал кодом, его нужно дизассемблировать. Фактически при создании плагина с помощью специального языка (SLEIGH) вы описываете порядок преобразования одних байтов в одни инструкции, а других в другие.


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


  • Байт-код V8 интерпретируемый, что усложняет процесс реализации. Тем не менее во многих моментах нам очень помогали исходные коды других процессорных модулей, например виртуальной машины Java.
  • При реализации некоторых типов регистров (например, для работы с локальными переменными могут использоваться регистры с индексом от 0 до 0x7FFFFFFF-4) пришлось пойти на компромисс в виде максимально отображаемых в дизассемблере.


(Типичный дизазм V8)


Анализатор


Наверное, второй самой объёмной частью плагина после загрузчика является анализатор. Его основной задачей является наведение порядка после работы загрузчика. Он подразумевает:


  • создание перекрёстных ссылок на код и данные (constant pool),
  • отслеживание контекста исполнения (codeflow) программы,
  • упрощение представления асинхронного кода,
  • накопление информации для декомпилятора.

Создание ссылок и работа с constant pool


Если вы занимались реверс-инжинирингом Java-классов, то наверняка знаете, что самым главным объектом в каждом классе является constant pool. Вкратце, это что-то типа словаря, в котором по индексам в качестве ключей хранятся ссылки или значения в виде абсолютно любых объектов, например:


  • строк, чисел, списков, кортежей и других примитивов;
  • функций, областей видимости и других элементов кода.


(Типичный constant pool. На скриншоте видны размеченные и аллоцированные загрузчиком элементы пула, а также ссылки на них. Можно заметить, что здесь хранятся данные практически любых типов)


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


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


  1. имеют ссылки на constant pool,
  2. имеют ссылки на контекст исполнения или изменяют его,
  3. выполняют runtime-функции (встроенные).

Код для работы с первым типом инструкций достаточно объёмный, так как в constant pool может храниться практически всё. И на это всё нужно проставить ссылки. Но рассказать мы бы хотели только об одном из сложных случаев: SwitchOnSmiNoFeedback.


SwitchOnSmiNoFeedback


По названию может показаться, что это обычные свитчи, только для V8. В действительности это специальная конструкция для работы с асинхронным кодом, то есть с тем, который помечен с помощью ключевых слов await/async. Работает оно так:


  1. В инструкции SwitchOnSmiNoFeedback указываются два индекса: первый начальный индекс в constant pool, по которому лежат ссылки на функции, и второй количество этих функций.
  2. Сами функции представляют из себя автоматически сгенерированные пролог (тело, эпилог) для кода, который требуется исполнять асинхронно (делается обёртка в виде переключения контекста, его сохранения, выгрузки). В нашем плагине этот шаблонный код заменяется на NOP-инструкции (No OPeration).

Возьмём в качестве примера следующий код:


async function handler() {    try {        const a = await 9;        const b = await 10;        const c = await 11;        let d = await 12;    } catch (e) {        return 123;    }    return 666;}console.log(handler());


(Так обычно и выглядит функция с SwitchOnSmiNoFeedback без оптимизации)



(А так с оптимизацией...)


Анализатор контекстов


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


В случае V8 для этого были введены три специальных сущности:


  1. регистр контекста,
  2. значение глубины для обращения к контексту,
  3. сохранение контекста в стек контекстов (выгрузка из него).

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


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


Runtime-функции


Основное, что здесь стоит отметить, это удаление (nop) из листинга обращений к функциям, также связанных со SwitchOnSmiNoFeedback, а именно async_function_promise_release, async_function_promise_create, promise_resolve. То есть плагин просто делает читаемость листинга декомпилятора выше.


Ссылки


GitHub: https://github.com/PositiveTechnologies/ghidra_nodejs/
Релизы: https://github.com/PositiveTechnologies/ghidra_nodejs/releases
Серьёзный разбор формата сериализации V8 движка в NodeJS: http://personeltest.ru/aways/habr.com/ru/company/pt/blog/551540/


Недостатки


Конечно, они есть. Некоторые недостатки всплывают из-за ограничений Ghidra, другие вследствие того, что проект делался под одну конкретную задачу (с которой отлично справился) и большого, полноформатного тестирования на сотнях семплов не было.


Релиз


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


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


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


Спасибо за внимание

Подробнее..

Перевод Что вошло в релиз движка V8 версии 9.0

01.05.2021 20:09:31 | Автор: admin

17 марта 2021 был опубликован релиз девятой версии движка V8. Этот пост - краткое описание того что вошло в список изменений релиза.

Оригинальный пост V8 release v9.0

JavaScript

Индексы соответствия (match indices) в RegExp

Начиная с версии 9.0, разработчики могут получать массив начальных и конечных позиций, совпадающих c группами захвата, соответствующих регулярному выражению. Этот массив доступен через свойство .indices для объектов сопоставления, если регулярное выражение имеет флаг / d.

const re = /(a)(b)/d;      // Note the /d flag.const m = re.exec('ab');console.log(m.indices[0]); // Index 0 is the whole match.//  [0, 2]console.log(m.indices[1]); // Index 1 is the 1st capture group.//  [0, 1]console.log(m.indices[2]); // Index 2 is the 2nd capture group.//  [1, 2]

Более подробное описание по ссылке

Более быстрый доступ к свойствам через функцию super

Доступ к свойствам через функцию super (например, super.x) был оптимизирован за счет использования встроенной системы кеширования V8 и оптимизированной генерации кода в TurboFan. С этими изменениями, доступ к свойствам через функцию super, теперь ближе к тому, чтобы быть наравне с обычным доступом к свойствам, как видно из графиков ниже.

Детальное описание находится по ссылке

Запрет конструкции "for ( async of "

Была обнаружена и исправленна в V8 v9.0, грамматическая неточность. Теперь конструкция for ( async of не парсится больше.

WebAssembly

Более быстрые вызовы в JS-to-Wasm

V8 использует разные представления для параметров функций WebAssembly и JavaScript. По этой причине, когда JavaScript вызывает экспортированную функцию WebAssembly, вызов проходит через так называемую оболочку JS-to-Wasm, отвечающую за адаптацию параметров из области JavaScript в область WebAssembly, а также адаптацию результатов вызова, в противоположном направлении.

К сожалению, это приводит к снижению производительности, а это означает, что вызовы из JavaScript в WebAssembly были не такими быстрыми, как вызовы из JavaScript в JavaScript. Чтобы свести к минимуму эти проблемы перфоманса, оболочка JS-to-Wasm теперь может быть встроена в сайт вызова, упрощая код и удаляя этот лишний фрейм.

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

double addNumbers(double x, double y) {  return x + y;}

и например, мы вызывем эту функцию в JavaScript, чтобы добавить несколько векторов (представленных в виде типизированных массивов):

const addNumbers = instance.exports.addNumbers;function vectorSum(len, v1, v2) {  const result = new Float64Array(len);  for (let i = 0; i < len; i++) {    result[i] = addNumbers(v1[i], v2[i]);  }  return result;}const N = 100_000_000;const v1 = new Float64Array(N);const v2 = new Float64Array(N);for (let i = 0; i < N; i++) {  v1[i] = Math.random();  v2[i] = Math.random();}// Warm up.for (let i = 0; i < 5; i++) {  vectorSum(N, v1, v2);}// Measure.console.time();const result = vectorSum(N, v1, v2);console.timeEnd();

Эта функция все еще является экспериментальной, и ее можно включить с помощью флага --turbo-inline-js-wasm-calls.

Подробнее см. дизайн документ.

Подробнее..
Категории: Javascript , Google chrome , Webassembly , V8

Перевод Sparkplug неоптимизирующий компилятор JavaScript в подробностях

09.06.2021 20:16:20 | Автор: admin

Создать компилятор JS с высокой производительностью означает сделать больше, чем разработать сильно оптимизированный компилятор, например TurboFan, особенно это касается коротких сессий, к примеру, загрузки сайта или инструментов командной строки, когда большая часть работы выполняется до того, как оптимизирующий компилятор получит хотя бы шанс на оптимизацию, не говоря уже о том, чтобы располагать временем на оптимизацию. Как решить эту проблему? К старту курса о Frontend-разработке делимся переводом статьи о Sparkplug свече зажигания под капотом Chrome 91.


Вот почему с 2016 года мы ушли от синтетических бенчмарков, таких как Octane, к измерению реальной производительности и почему старательно работали над производительностью JS вне оптимизирующих компиляторов. Для нас это означало работу над парсером, стримингом [этой поясняющей ссылки в оригинале нет], объектной моделью, конкурентностью, кешированием скомпилированного кода...

Впрочем, повернувшись лицом к улучшению производительности фактического, начального выполнения JS, мы столкнулись с ограничениями процесса оптимизации интерпретатора. Интерпретатор V8 сам по себе быстрый и сильно оптимизированный, но интерпретаторам как таковым свойственны накладные расходы, избавиться от которых мы не можем: например на декодирование байт-кода или диспетчеризацию неотъемлемые части функциональности интерпретатора.

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

Выход из положения Sparkplug: новый неоптимизирующий компилятор JavaScript, который мы выпустили вместе с V8 9.1, он работает между интерпретатором Ignition и компилятором TurboFan.

Новый процесс компиляцииНовый процесс компиляции

Быстрый компилятор

Sparkplug создан компилировать быстро. Очень быстро. Настолько, что мы всегда можем компилировать, когда захотим, повышая уровень кода SparkPlug намного агрессивнее кода TurboFan, [подробнее здесь, этой ссылки в оригинале нет].

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

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

// The Sparkplug compiler (abridged).for (; !iterator.done(); iterator.Advance()) {  VisitSingleBytecode();}

Недочёт промежуточного представления (IR) заключается в том, что компилятор ограничен возможностями оптимизации. Поскольку промежуточной архитектурно независимой стадии нет, этот факт также означает, что всю реализацию нужно переносить на каждую поддерживаемую архитектуру отдельно. Но, оказывается, ни то, ни другое не является проблемой: портировать код довольно легко, вместе с тем Sparkplug не нужно выполнять тяжёлую оптимизацию.

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

Совместимые с интерпретатором фреймы

Добавление нового компилятора в зрелую виртуальную машину JS пугающая задача. Кроме стандартного выполнения в V8 мы должны поддерживать отладчик, профилирование центрального процессора с обходом стека, а значит, трассировки стека для исключений, интеграцию в стратегию динамического повышения уровня функции, замену на стеке, чтобы оптимизировать код горячих циклов. Работы много.

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

Стековый фрейм с указателями стека и фреймаСтековый фрейм с указателями стека и фрейма

Сейчас около половины читателей закричит: "Диаграмма не имеет смысла, стек направлен в другую сторону!" Ничего страшного, я сделал кнопку: думаю, стек направлен вниз.

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

Стековые фреймы для нескольких вызововСтековые фреймы для нескольких вызовов

Строго говоря, это только соглашение, согласно которому создаётся код, но не требование. Хотя оно довольно универсально; не работает оно только в двух случаях: когда стековые фреймы полностью игнорируются или когда вместо него можно использовать таблицы со стороны отладчика.

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

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

В случае Ignition соглашение становится более явным. Ignition интерпретатор на основе регистров, это означает, что есть виртуальные регистры (не путайте их с машинными!), которые хранят текущее состояние интерпретатора. включая локальные переменные (объявления var, let, const) и временные значения. Эти регистры содержатся в стековом фрейме интерпретатора, вместе с указателем на выполняемый массив байт-кода и смещением текущего байт-кода в массиве.

Sparkplug намеренно создаёт и поддерживает соответствующий фрейму интерпретатора макет фрейма. Всякий раз, когда интерпретатор сохраняет значение регистра, SparkPlug также сохраняет его. Делает он это по нескольким причинам:

  1. Это упрощает компиляцию Sparkplug; новый компилятор может просто отражать поведение интерпретатора без необходимости сохранять какое-либо отображение из регистров интерпретатора в состояние Sparkplug.

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

  3. Это делает интеграцию с остальной частью системы почти тривиальной; отладчик, профайлер, раскручивание стека исключений, вывод трассировки все эти операции идут по стеку, чтобы узнать, каков текущий стек выполняемых функций, и все эти операции продолжают работать со Sparkplug почти без изменений, потому всё, что касается их, они получают из фрейма интерпретатора.

  4. Тривиальной становится и замена на стеке (OSR). Замена на стеке это когда выполняемая функция заменяется в процессе выполнения; сейчас это происходит, когда интерпретированная функция находится в горячем цикле (в это время она поднимается до оптимизированного кода этого цикла) и где оптимизированный код деоптимизируется (когда он опускается и продолжает выполнение функции в интерпретаторе), любая работающая в интерпретаторе логика замены на стеке будет работать и для Sparkplug. Даже лучше: мы можем взаимозаменять код интерпретатора и SparkPlug почти без накладных расходов на переход фреймов.

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

Вы можете заметить, что теперь у нас есть неиспользуемый слот фрейма, где должно быть смещение байт-кода; избавиться от него мы не можем, поскольку хотим сохранить оставшуюся часть стека неизменной. Мы перепрофилируем этот слот стека, чтобы вместо него кешировать "вектор обратной связи" для текущей выполняющейся функции; это вектор, хранящий данные о форме объекта, и он должен быть загружен для большинства операций. Всё, что нам нужно делать, соблюдать осторожность с OSR, чтобы гарантировать, что мы подставляем либо правильное смещение байт-кода, либо правильный вектор обратной связи для этого слота. В итоге стековый фрейм Sparkplug выглядит так:

Полагаемся на встроенный код

На самом деле Sparkplug генерирует очень мало собственного кода. У JS сложная семантика, так что для выполнения даже самых простых операций требуется много кода. Принудительная повторная генерация такого кода при каждой компиляции оказалась бы плохим решениям по нескольким причинам:

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

  2. Этот подход увеличил бы потребление памяти кодом Sparkplug.

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

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

Вы можете подумать: "Ну и какой тогда смысл во всём этом? Разве Sparkplug не выполняет ту же работу, что и интерпретатор?" и во многом будете правы. Во многих отношениях Sparkplug является "просто" сериализацией выполнения интерпретатора, вызывая те же встроенные двоичные сниппеты и поддерживая тот же стековый фрейм. Тем не менее оно того стоит, потому что Sparkplug удаляет (или, точнее, предварительно компилирует) те самые неустранимые накладные расходы интерпретатора, такие как декодирование операндов и диспетчеризация следующего байт-кода.

Оказалось, что интерпретация эффективнее множества оптимизаций уровня центрального процессора: статические операнды динамически читаются из памяти интерпретатором, вынуждая процессор делать предположения о том, какими могут быть значения. Диспетчеризация к следующей инструкции байт-кода для сохранения производительности требует успешного прогнозирования ветви выполнения, и, даже если предположения и прогнозы верны, по-прежнему нужно выполнять декодирование и диспетчеризацию кода, а также занимать драгоценное пространство различных буферов и кешей. ЦП сам по себе эффективный интерпретатор, хотя он применяется к машинному коду. С этой точки зрения Sparkplug транспилятор из байт-кода Ignition в байт-код центрального процессора, перемещающий выполнение в "эмуляторе" к "нативному" выполнению.

Производительность

Так как же Sparkplug работает на практике? Мы выполнили несколько бенчмарков Chrome на наших ботах для замера производительности со Sparkplug и без него. Спойлер: мы очень довольны.

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

Speedometer

Speedometer это тест, который пытается эмулировать реально работающий фреймворк, создавая веб-приложение для отслеживания списка задач с использованием нескольких популярных фреймворков и проводя стресс-тестирование производительности этого приложения добавлением и удалением задач. Мы обнаружили, что это отличное отражение поведения загрузки и взаимодействия в реальном мире, и мы неоднократно обнаруживали, что улучшения в спидометре отражаются на наших реальных показателях. Со Sparkplug оценка Speedometer улучшается на 510 %, в зависимости от бота.

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

Обзор бенчмарка

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

На этих тестах мы решили посмотреть метрику V8 Main-Thread Thread, измеряющую общее проведённое в V8 время (включая компиляцию и выполнение), в основном потоке (то есть исключая стриминговый парсинг или фоновую оптимизацию). Это лучший способ увидеть, насколько оправдан Sparkplug, без учёта других источников шума бенчмарка.

Результаты различны и сильно зависят от машины и веб-сайта, но в целом выглядят прекрасно: видно улучшение около 515 %.

Медианное улучшение времени работы V8 в основном потоке на наших бенчмарках для просмотра с 10 повторениями. Полосы на диаграмме указывают на диапазон между квартилямиМедианное улучшение времени работы V8 в основном потоке на наших бенчмарках для просмотра с 10 повторениями. Полосы на диаграмме указывают на диапазон между квартилями

Таким образом, V8 имеет новый сверхбыстрый неоптимизирующий компилятор, повышающий производительность V8 в реальных бенчмарках на 515 %. Он уже доступен в V8 v9.1 (укажите опцию --sparkplug), и мы выпустим его вместе с Chrome 91.

Вот что важно заметить: выделившись в отдельную область разработки, фронтенд не ограничивается одним только JavaScript, например есть множество тонкостей в том, каким образом браузер работает с CSS. Вместе с тем оптимизации на уровне браузера не означают, что можно больше не писать аккуратный, компактный и элегантный код. Скорее они означают, что теперь разработчики будут свободнее чувствовать себя, когда захотят написать сложную или тяжёлую функциональность. Если фронтенд вам интересен, вы можете обратить внимание на наш курс Frontend-разработчик, где получите комплексную подготовку, чтобы в дальнейшем писать и поддерживать приложения различного масштаба и уровня сложности.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы
Подробнее..

Создаем процессорный модуль под Ghidra на примере байткода v8

23.04.2021 18:05:42 | Автор: admin

В прошлом году наша команда столкнулась с необходимостью анализа байткода V8. Тогда еще не существовало готовых инструментов, позволявших восстановить такой код и обеспечить удобную навигацию по нему. Было принято решение попробовать написать процессорный модуль под фреймворк Ghidra. Благодаря особенностям используемого языка описания инструкций на выходе мы получили не только читаемый набор инструкций, но и C-подобный декомпилятор. Эта статья продолжение серии материалов (1, 2) о нашем плагине для Ghidra.

Между написанием процессорного модуля и статьи прошло несколько месяцев. За это время спецификация SLEIGH не изменилась, и описанный модуль работает на версиях 9.1.29.2.2, которые были выпущены за последние полгода.

Сейчас на ghidra.re и в приложенной к Ghidra документации есть достаточно хорошее описание возможностей языка эти материалы стоит почитать перед написанием своих модулей. Отличными примерами могут быть уже готовые процессорные модули разработчиков фреймворка, особенно если вы знаете описываемую в них архитектуру.

В документации можно прочесть, что процессорные модули для Ghidra пишутся на языке SLEIGH, который произошел от языка SLED (Specification Language for Encoding and Decoding) и разрабатывался целенаправленно под Ghidra. Он транслирует машинный код в p-code (промежуточный язык, используемый Ghidra для построения декомпилированного кода). Как у языка, предназначенного для описания инструкций процессора, у него достаточно много ограничений, которые, однако, можно купировать за счет механизма внедрения p-code в java-коде.

Исходный код созданного процессорного модуля представлен на github. В этой статье будут рассматриваться принципы и ключевые понятия, которые использовались при разработке процессорного модуля на чистом SLEIGH на примере некоторых инструкций. Работа с пулом констант, инъекции p-code, анализатор и загрузчик будут или были рассмотрены в других статьях. Также про анализаторы и загрузчики можно почитать в книге The Ghidra Book: The Definitive Guide.

С чего начать

Для работы понадобится установленная среда разработки Eclipse, в которую нужно добавить плагины, поставляемые с Ghidra: GhidraDev и GhidraSleighEditor. Далее создается Ghidra Module Project с именем v8_bytecode. Созданный проект содержит шаблоны важных для процессорного модуля файлов, которые мы будем модифицировать под свои нужды.

Чтобы получить общее представление о файлах, с которыми предстоит работать, обратимся к официальной документации либо вышедшей недавно книге Криса Игла и Кары Нанс The Ghidra Book: The Definitive Guide. Вот описание этих файлов.

  • *.сspec спецификация компилятора.

  • *.ldefs определение языка. Содержит отображаемые в интерфейсе параметры процессорного модуля. Также содержит ссылки на файлы *.sla, спецификацию процессора и спецификации компилятора.

  • *.pspec спецификация процессора.

  • *.opinion конфигурации для загрузчика; поскольку мы будем описывать только один вид файлов, файл opinion можно оставить пустым: он не пригодится.

  • *.slaspec, *.sinc файлы, описывающие регистры и инструкции процессора на языке SLEIGH.

Также после первого запуска вашего проекта появится файл с расширением .sla, он генерируется на основании slaspec-файла.

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

О регистрах V8

Jsc-файл, который нас интересовал, был собран c использованием среды выполнения JavaScript Node.Js 8.16.0 через bytenode (этот модуль либо будет в поставке Node.Js, либо нужно будет доставить его через npm). По сути, bytenode использует документированный функционал Node.js для создания скомпилированного файла. Вот исходный код функции, компилирующей jsc файлы из js:

Node.js можно скачать как в собранном виде, так и в виде исходников. При детальном изучении исходных файлов и примеров инструкций становится ясно, как кодируются регистры в байткоде (для понимания расчета индекса будут полезны файлы bytecode-register.cc, bytecode-register.h). Примеры инструкций v8 с расчетами индексов регистров в соответствии с Node.js:

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

Тут Х количество аргументов текущей функции без учета передаваемого <this>, aX регистры, содержащие аргументы функции, а rN регистры, используемые как локальные переменные. Регистры могут кодироваться 1-байтовыми значениями для обычных инструкций, 2-байтовыми для инструкций с пометкой Wide- и 4-байтовыми для инструкций с пометкой ExtraWide-. Пример кодировки Wide-инструкции с пояснениями:

Более подробно о Node.js и v8 можно почитать в статье Сергея Федонина.

Стоит заметить, что SLEIGH не совсем подходит для описания подобных интерпретируемых байткодов, поэтому у написанного процессорного модуля есть некоторые ограничения. Например, определена работа не более чем с 124регистрами rN и 125регистрами aX. Была попытка решить эту проблему через стековую модель взаимодействия с регистрами, так как она больше соответствовала концепции. Однако в этом случае дизассемблированный байткод тяжелее читался:

Также без введения дополнительных псевдоинструкций, регистров или областей памяти не представляется возможным высчитывать название регистра аргумента в соответствии с Node.js из-за отсутствия информации о количестве аргументов. В связи с этим нами было принято решение проставлять номера в названии регистров аргументов функций (X в aX) в обратном порядке. Это не мешает разбору кода, что было для нас важным критерием, однако может смущать при сравнении результатов вывода инструкций файла в разных инструментах.

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

CSPEC

Немного текстовой информации о тегах, используемых в cspec-файлах, можно найти в исходниках фреймворка на github. В описании назначения файла говорится:

Спецификация компилятора является необходимой частью модуля языка Ghidra для поддержки разборки и анализа конкретного процессора. Его цель закодировать информацию о целевом двоичном файле, специфичном для компилятора, сгенерировавшего этот двоичный файл. В Ghidra спецификация SLEIGH позволяет декодировать машинные инструкции для конкретного процессора, например Intelx86, но эти инструкции могут продуцировать более одного компилятора. Для конкретного целевого двоичного файла понимание деталей о конкретном компиляторе, используемом для его сборки, важно для процесса разбора кода. Спецификация компилятора удовлетворяет эту потребность, позволяя формально описывать такие концепции, как соглашения о передаче параметров и механизмы стека.

Также становится понятно, что теги используются для следующих целей:

  • Compiler Specific P-code Interpretation;

  • Compiler Datatype Organization (у нас использовался <data_organization>);

  • Compiler Scoping and Memory Access (у нас использовался <global>);

  • Compiler Special Purpose Registers (у нас использовался <stackpointer>);

  • Parameter Passing (у нас использовался <default_proto>).

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

Теги <data_organization> и <stackpointer> достаточно типовые; разберем тег <prototype> в <default_proto>, частично описывающий соглашение о вызове функций. Для него определим: <input>, <output>, <unaffected>.

Как говорилось выше, аргументы в функцию передаются через регистры aX. В модуле регистры должны быть определены как непрерывная последовательность байтов по смещению в некотором пространстве. Как правило, в таких случаях используется специально придуманное для этого пространство register. Однако теоретически не запрещено использовать любое другое. В случае наличия большого количества регистров, выполняющих примерно одни функции, проще всего не прописывать каждый отдельно, а просто указать смещение в пространстве регистров, по которому они будут определены. Поэтому в спецификации компилятора помечаем область памяти в пространстве регистров (space="register") в теге <input> для регистров, через которые происходит передача аргументов в функции, по смещению 0x14000 (0x14000 не несет в себе сакрального смысла, это просто смещение, по которому в *.slaspec далее будут определены регистры aX).

По умолчанию результат вызова функций сохраняется в аккумулятор (acc), что нужно прописать в теге <output>. Для альтернативных вариантов регистров, в которые происходит сохранение возвращаемых функциями значений, можно определить логику при описании инструкций. Отметим в теге <unaffected>, что вызовы функций на регистр, хранящий указатель на стек, не влияют.

Для работы с частью регистров наиболее удобным будет вариант определения их как изменяемых глобально, поэтому в теге <global> определяем диапазон регистров в пространстве register по смещению 0x2000.

LDEFS

Перейдем к определению языка это файл с расширением .ldefs. Он требует немного информации для оформления: порядок байт (у нас le), названия ключевых файлов (*.sla, *.pspec,*.cspec), id и название байткода, которое будет отображаться в списке поддерживаемых процессорных модулей при импорте файла в Ghidra. Если когда-то понадобится добавить процессорный модуль для файла, скомпилированного версией Node.js, существенно отличающейся от текущей, то имеет смысл описать его тут же через создание еще одного тега <language>, как это сделано для описания семейств процессоров в *.ldefs модулей, поставляемых в рамках Ghidra.

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

PSPEC

Сложнее в плане документации дела обстоят со спецификацией процессора (файл с расширением .pspec). В данном случае можно обратиться к готовым решениям в рамках самого фреймворка или к файлу processor_spec.rxg (вариант с полноценным разбором исходных кодов Ghidra мы не рассматривали). Чего-то более подробного на момент написания модуля не было. Вероятно, со временем разработчики опубликуют официальную документацию.

В текущем проекте на данный момент от спецификации процессора может понадобиться только программный счетчик, оставим этот тег из стандартного шаблона свежесозданного проекта (на самом деле можно оставить <processor_spec> пустым).

SLASPEC

Теперь можно приступить к непосредственному описанию инструкций на SLEIGH в файле с расширением .slaspec.

Базовые определения и макросы препроцессора

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

Адресные пространства, которые понадобятся для описания байткода (у нас создаются пространства с именами register и ram), определяются через define space, а регистры через define register. Значение offset в определении регистров не принципиально, главное, чтобы они находились по разным смещениям. Занимаемое регистрами количество байтов определяется параметром size. Стоит помнить, что определенная тут информация должна соответствовать обращениям к аналогичным абстракциям и величинам в рамках *.cspec и анализатора, если вы ссылаетесь на эти регистры.

Описание инструкций

В документации (https://ghidra.re/courses/languages/html/sleigh_constructors.html) можно прочитать, что определение инструкций происходит через таблицы, которые состоят из одного и более конструкторов и имеют имена идентификаторы символов семейства. Таблицы в SLEIGH по сути являются тем, что называется символами семейства, в статье мы не будем углубляться в определения символов, для этих целей проще прочитать Знакомство с символами. Конструкторы состоят из 5частей.

  1. Table Header (заголовок таблицы)

  2. Display Section (секция отображения)

  3. Bit Pattern Sections (секция битового шаблона)

  4. Disassembly Actions Section (секция действий при дизассемблировании инструкций)

  5. Semantics Actions Section (семантическая секция)

Пока что звучит страшно, опишем основной смысл.

  1. В Table Header либо помечается идентификатор, который можно использовать в других конструкторах, либо ничего нет (тогда это непосредственно описание инструкции).

  2. Display Section шаблон, показывающий как выводить инструкцию в листинг Ghidra.

  3. Bit Pattern Section перечень каких-либо идентификаторов, которые забирают реальные биты программы под инструкцию и выводятcя в листинг по шаблону секции отображения (иногда с использованием следующей секции).

  4. Disassembly Actions Section дополняет секцию битового шаблона какими-то вычислениями, если ее в чистом виде недостаточно.

  5. Semantics Actions Section описывает, что делает эта инструкция по смыслу, чтобы показать это в декомпиляторе.

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

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

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

  • ^ разделяет идентификаторы и/или символы в секции, между которыми не должно быть пробелов;

  • используются, чтобы вставлять жестко закодированные строки, которые не будут считаться идентификатором;

  • пробельные символы обрезаются в начале и конце секции, а их последовательности сжимаются в один пробел;

  • некоторые знаки пунктуации и спецсимволы вставляются в шаблон (неиспользуемые для каких-то определенных функций, в отличие от, например#, которые применяются для комментариев).

Токены и их поля

Для описания конструкторов инструкций необходимо определить битовые поля. Через них осуществляется привязка битов программы к определенным абстракциям языка, в который будет происходить трансляция. Такими абстракциями могут быть мнемоники, операнды и т.п. Определение полей происходит в рамках задания токенов, синтаксис их определения выглядит так:

Размер токена tokenMaxSize должен быть кратен8. Это может быть неудобно, если операнды или какие-то нюансы для инструкции кодируются меньшим количеством бит. С другой стороны, это компенсируется возможностью создавать поля разных размеров, кодирующих позиционно любые биты в пределах размеров, задаваемых токеном. Для таких полей должны соблюдаться условия: start- и endBitNumX находятся в диапазоне от 0 до tokenMaxSize-1 включительно и startBitNumX <= endBitNumX.

Для разбираемого байткода v8 не было необходимости создавать поля, отличные по размеру от токена. Но, если бы такие поля были и использовались совместно, они бы объединялись через логические операторы & или |.

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

Теперь опишем простейшую инструкцию байткода, не имеющую операндов. Определим поле, которое будет описывать опкод инструкции. Как видно выше в разделе про v8, код инструкции описывается одним байтом (есть также Wide- и ExtraWide- инструкции, но они здесь не будут рассматриваться, по сути они просто используют операнды больших размеров и дополнительные байты под опкод инструкции). Таким образом получаем:

Теперь, используя поле op для идентификации первого и единственного опкода, определяющего инструкции Illegal и Nop, пишем для них конструкторы:

Байт 0xa7 в листинге Ghidra отобразит как инструкцию Illegal, не имеющую операндов. Для этой инструкции в примере использовалось ключевое слово unimpl. Это неимплементированная команда, дальнейшая декомпиляция будет прервана, что удобно для отслеживания нереализованных семантических описаний. Для Nop оставлена пустая семантическая секция, то есть команда не повлияет на отображение в декомпиляторе, что и должна делать эта инструкция. На самом деле Nop не присутствует как инструкция в Node.js нашей версии, мы ввели ее искусственно для реализации функционала SwitchOnSmiNoFeedback, но об этом будет рассказано в статье Владимира Кононовича.

Описываем операнды и семантику

Усложним концепцию: опишем конструктор для операций LdaSmi, в рамках которой происходит загрузка целого числа в аккумулятор (acc в определении пространства регистров), и AddSmi, которая по сути представляет собой сложение значения в аккумуляторе c целым числом.

Для текущих и будущих нужд определим чуть больше полей на манер операндов в bytecodes.h Node.js, создадим их в новом токене с именем operand, поскольку у этих полей будет другое назначение. Создание нескольких полей с одинаковыми битовыми масками может быть обусловлено как удобством восприятия, так и использованием нескольких полей одного токена в рамках одной инструкции (см. пример с AddSmi).

С точки зрения листинга хочется видеть что-то наподобие LdaSmi [-0х2]. Поэтому определяем в секции отображения мнемонику, а в шаблон прописываем имена полей, которые должны подставляться из секции disassembly action или битового шаблона (квадратные скобки тут не обязательны, это просто оформление).

Для инструкции AddSmi в секции битового шаблона, помимо поля op, устанавливающего ограничение на опкод, через ; появляются поля из токена operand. Они будут подставлены в секцию отображения в качестве операндов. Маппинг на реальные биты происходит в том порядке, в котором поля указаны в секции битового шаблона. В семантической секции, используя документированные операции, реализуем логику инструкций (то, что делал бы интерпретатор, выполняя эти инструкции).

Через ; могут также, например, идти регистры, контекстные переменные (о них поговорим позже), комбинации полей одного токена или полей с контекстными переменными.

Вот так выглядит окно листинга с описанными инструкциями со включенным полем PCode в меню изменение полей листинга Ghidra. Окно декомпилятора пока что не будет показательным из-за оптимизации кода, поэтому на данном этапе стоит ориентироваться только на промежуточный p-code.

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

Инструкции возврата значения из функции реализуются с помощью ключевого слова return, и, как уже упоминалось ранее, чаще всего возвращение значения при вызове функции происходит через аккумулятор:

Выводим регистры по битовым маскам

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

В разделе Базовые определения и макросы препроцессора регистры уже были объявлены, но для того, чтобы нужные регистры выбирались в зависимости от представленных в байткоде бит, необходимо привязать их список к соответствующим битовым маскам. Поле kReg имеет размер 8бит. Через конструкцию attach variables последовательно определяем каким битовым маскам от 0b до 11111111b вышеприведенные регистры будут соответствовать в рамках последующего использования полей из заданного списка (в нашем случае только kReg) в конструкторах. Например, в этом описании видно, что операнд, закодированный как 0xfb (11111011b), интерпретируется при описании его через kReg как регистр r0.

Теперь, когда за переменной kReg закреплены регистры, ее можно использовать в конструкторах:

Усложним конструкцию для соответствия конструктора более высокоуровневым описаниям инструкций из interpreter-generator.cc исходников Node.js. Вынесем поле kReg в отдельный конструктор, идентификатор таблицы которого в Table Header назовем src. В его семантической секции появляется новое ключевое слово export. Если не вдаваться в детали построения p-code, то по смыслу export определяет значение, которое должно быть подставлено в семантическую секцию конструктора вместо src. Вывод в Ghidra не изменится.

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

Переходы по адресам с goto

В байткоде встречаются операции условного и безусловного перехода по смещению относительно текущего адреса. Для перехода по адресу или метке в SLEIGH используется ключевое слово goto. Примечательно для определения то, что в секции битового шаблона используется поле kUImm, однако оно не используется в чистом виде. В секцию отображения выводится просчитанное в disassembly action секции значение через идентификатор rel. Величина inst_start предопределена для SLEIGH и содержит адрес текущей инструкции.

Компиляция SLEIGH проходит. Правда, в таком варианте (листинг ниже), судя по выводу, не получается создать варноду (это объекты, которыми манипулирует p-code инструкция), содержащую привязку к конкретному пространству.

Воспользуемся рекомендуемым разработчиками способом и вынесем часть определения через создание дополнительного конструктора с идентификатором dest. Конструкция *[ram]:4 rel не обозначает, что мы берем 4байта по адресу rel. По факту экспортируется адрес rel в пространстве ram. Оператор * в SLEIGH обозначает разыменование, но в данном конкретном случае относится к нюансу создания варнод (подробнее в Dynamic References).

Указание пространства [ram] может быть опущено (пример в комментарии), так как при определении мы указали его пространством по умолчанию. Как видно в инструкциях p-code, смещение было помечено как принадлежащее ram.

Чуть сложнее выглядит инструкция JumpIfFalse из-за использования условной конструкции. В SLEIGH она используется вместе с ключевым словом goto. Для большего соответствия концепциям js величина False ранее была определена как регистр, и можно заметить, что в pspec диапазон пространства регистров, к которому она привязана, помечен как глобальный. Благодаря этому в псевдокоде она отображается в соответствии с именованием регистра, а не численным значением.

В рассмотренных примерах переход осуществляется по рассчитываемому относительно inst_start адресу. Рассмотрим инструкцию TestGreaterThan, в которой происходит переход с помощью goto к метке (<true> в примере ниже) и inst_next. Переход к метке в принципе должен быть интуитивно понятным: если условие истинно, то далее должны выполняться инструкции, следующие за местом ее расположения. Метка действительна в только в пределах ее семантической секции.

Конструкция goto inst_next фактически завершает обработку текущей инструкции и передает управление на следующую. Стоит обратить внимание, что для выполнения знакового сравнения используется s>, см. документацию.

Несколько регистровых операндов

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

Описание однотипных операндов через конструкторы, имеющие разные идентификаторы таблиц (см. конструкторы в примере ниже), может иметь практическое применение для использования в рамках одного конструктора корневой таблицы. Такой вариант применим не только с точки зрения соответствия описанию инструкций v8, но и для преодоления возможных ошибок. Например, 4операнда инструкции CallProperty2 являются регистрами, идентично задаваемыми с точки зрения битовой маски. Попытка определить конструктор как :CallProperty2 kReg, kReg, kReg, kReg, [kIdx] вызовет ошибку в компиляторе Sleigh при попытке открыть файл с помощью процессорного модуля. Поэтому в нашем модуле использовались конструкторы для создания чего-то наподобие алиасов:

Стоит отметить, конечно, что решить эту проблему также можно было без определения новых конструкторов. Например, определив и прописав поля callable, receiver, arg1 и arg2 в рамках какого-либо токена с последующей их привязкой через attach к списку регистров:

Каждое из этих полей работало бы аналогично kReg в предыдущих примерах. Какой именно способ использовать вопрос эстетики.

Вызовы функций

В инструкции CallProperty2 также примечательно то, что она в семантической секции использует конструкцию call [callable];, которую мы не использовали до этого. В v8 аргументы функции хранятся в регистрах aX (как мы и пометили в cspec). Однако, с точки зрения байткода, помещения туда аргументов непосредственно перед вызовом функции не происходит (случаи, когда это происходит, можно посмотреть в sinc-файле, например для x86). Интерпретатор делает это самостоятельно, ведь у него есть вся необходимая информация. Но ее нет у Ghidra, поэтому в семантической секции мы пропишем помещение аргументов в регистры вручную. Однако нам необходимо будет восстановить значения задействованных регистров после вызова, так как в вызывающей функции эти регистры тоже могут хранить какие-то значения, необходимые для потока выполнения. Можно сохранить их через локальные переменные:

Можно также применять вариант с сохранением аргументов в памяти (в данном случае на стеке: sp не используется инструкциями, потому не повлияет на отображение в декомпиляторе) при использовании макросов на примере CallUndefinedReceiver1:

При написании подобных модулей вместе с загрузчиком и анализатором стоит следить, чтобы порядок передаваемых аргументов совпадал с порядком аргументов функции, определяемых при их создании в java-коде. Также стоит отметить, что для нашей ситуации было полезно сохранять не больше аргументов функции, чем их количество в вызывающей функции, но это сложно реализовать на SLEIGH. Вариант решения проблемы можно будет прочитать в статье Вячеслава Москвина про внедрение p-code инструкций.

Определяемые пользователем операции

Чтобы не терять при декомпиляции инструкции, в которых не планируется или нет возможности описывать семантический раздел, можно использовать определяемые пользователем операции. Стоит отметить, что в ситуации с acc не требуется явно указывать размер, поскольку размер регистра определен явно, а использовать его не полностью тут не нужно. Однако при передаче в подобные пользовательские операции, например, числовых констант придется явно указывать размер передаваемого значения (как в примере с CallVariadicCallOther в разделе О диапазонах регистров далее по тексту). Пользовательские операции определяются как define pcodeop OperationName и используются в семантическом разделе конструкторов в формате, напоминающем вызов функции во многих языках программирования.

Эти операции могут использоваться для внедрения p-code-инструкций в анализаторе: вызовы добавляются через тег callotherfixup в cspec-файл и прописывается логика в анализаторе.

Без переопределения в java-коде пользовательские операции в декомпиляторе выглядят так же, как они определены в семантическом разделе:

Тестируем модуль

Уже на этом этапе можно попробовать проверить работу процессорного модуля на практике. Скомпилируем через bytenode jsc-файл из небольшого примера на js:

Попробуем запустить написанный на основании статьи проект и импортировать полученный jsc-файл в Ghidra. Если что-то описано неправильно, Ghidra выдаст ошибку, а в логах eclipse будет локализирован номер строки, вызвавшей ошибку. При исправлении кода не нужно перестраивать проект: sleigh перекомпилируется при следующей попытке открыть файл.

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

Поскольку мы описывали только инструкции, файл не будет проанализирован и разобран по функциям. Код находится по смещению 0х1с0. НажмемD для преобразования байтов в инструкции по этому смещению иF, чтобы создать функцию. Вот так она будет выглядеть:

Более понятным становится вывод при использовании других средств (помимо SLEIGH), доступных разработчикам модулей. Например, при добавлении работы с пулом констант (для обращения к нему в SLEIGH зарезервировано ключевое слово cpool) появится возможность разрезолвить числовой идентификатор в команде LdaGlobal. Вот так в последней версии нашего проекта выглядит функция (для сравнения):

Разумеется, было бы приятнее видеть большее соответствие исходному коду, написанному на JavaScript, однако этого нельзя добиться, описывая инструкции только в файлах .slaspec (и .sinc). Чуть больший простор для воображения откроет статья, в которой будет описан механизм внедрения операций p-code, позволяющий при полном доступе ко всем ресурсам приложения манипулировать инструкциями, из которых собирается дерево p-code. Как раз на основании созданного дерева p-code результат декомпиляции выстраивается и отображается в интерфейсе.

О диапазонах регистров

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

На основании описания понятно, что достаточно простым решением было бы отобразить при разборе инструкций первый регистр и их количество, то есть примерно так: ForInPrepare r9, r10!3. Чуть большим компромиссом в пользу читаемости было бы выводить первый и последний регистры диапазона, но, забегая вперед, можно сказать, что с точки зрения реализации уже это потребовало бы использования таблиц, состоящих из нескольких конструкторов.

Таблицы, содержащие несколько конструкторов

В рамках проекта для удобства восприятия было решено отображать в листинге весь список передаваемых регистров. Для секции отображения нет готового шаблона для выведения диапазонов регистров. Можно руководствоваться принципами, аналогичными использованным для процессорного модуля ARM: распечатыванием переменных через цепочку конструкторов (только сам принцип, реализация нам не подойдет из-за разности архитектур).

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

Как можно предположить, глядя на побайтовое описание инструкции CallProperty выше, для раскрытия диапазона необходимо распечатать регистры, отталкиваясь от первого вхождения, ориентируясь на известный первый регистр диапазона и количество элементов в нем. С точки зрения секции отображения, диапазон создается из двух конструкторов: rangeSrc и rangeDst. rangeSrc своего рода инициализация, где мы сохраняем входные данные, rangeDst будет распечатывать регистры на основании полученной информации. И как раз для rangeDst понадобится создавать таблицы, содержащие несколько конструкторов: как минимум для отображения диапазонов на регистрах aX и rX отдельно.

Для реализации условий необходимо учесть ряд ограничений. Проверять значения в секции битового шаблона рекомендуется только через =, а уточнять тут значение напрямую регистра нельзя, как и присваивать ему значения в секции disassembly action. Это лишает нас возможности использовать какой-то временный регистр. Стартовый регистр и длина диапазона могут быть любыми, а реализоваться, как уже упоминалось, диапазон может как на регистрах aX, так и на rX, а также быть нулевой длины. Уже на этом этапе понятно: если мы не хотим создавать гигантское количество определений на все случаи жизни, было бы неплохо иметь некие счетчики, чтобы выяснить, сколько регистров выводить и с какой позиции.

Контекстные переменные

Для решения задачи подходят контекстные переменные. Их определение похоже на определение полей токенов. Но поля в данном случае используют не реальные биты программы, а биты указанного регистра (contextreg ниже).

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

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

В документации поясняется, что контекстные переменные, как правило, используются в секции битовых шаблонов для проверки наличия какого-то контекста и изменяются в секции disassembly action. Так что в конструкторе с идентификатором таблицы rangeSrc, которую мы будем использовать для отображения диапазонов, в disassembly action секции сохраняем код первого регистра диапазона в контекстную переменную offStart, а их количество в counter. В секции отображения обозначаем начало диапазона открывающейся скобкой {.

Также стоит отметить, что в v8 не используется регистр range_size: он введен искусственно для хранения размера диапазона, чтобы было удобнее работать с этим значением в рамках семантической секции конструктора инструкции. Именно rangeSrc поставляет стартовый регистр и размер диапазона для семантической секции инструкции.

В рамках таблицы с идентификатором rangeDst описано 5конструкторов для следующих случаев.

  • Код стартового регистра диапазона соответствует a0 и счетчик counter равен 0 (пустой диапазон).

  • Код стартового регистра диапазона соответствует r0 и счетчик counter равен 0 (пустой диапазон).

  • Код регистра диапазона в offStart совпадает с a0, в disassembly action секции счетчик counter уменьшается, код регистра в offStart увеличивается, переход к конструктору rangedst1.

  • Код регистра диапазона в offStart совпадает с r0, в disassembly action секции счетчик counter и код регистра в offStart уменьшаются, переход к конструктору rangedst1.

  • Код стартового регистра диапазона пока не найден, переход к конструктору rangedst1(для этого случая в конструкторе нет никаких условий, как упоминалось выше, он будет браться, когда остальные конструкторы не подошли).

В третьем и четвертом случаях происходит вывод регистра в отображение. Последующие конструкторы rangeDstN, где N натуральное число, состоят из тех же вариантов, только для регистров aN/rN.

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

В примере ниже описаны только rangeDst, rangeDst1, rangeDst2, чтобы не загромождать статью. Для получения представления о виде подобных таблиц этого достаточно, полную версию можно посмотреть в исходниках проекта на github. По сути, при работе с rangeDst будет проходиться цепочка конструкторов по возрастанию индекса Х в rangeDstX, пока не встретится стартовый регистр, а затем цепочка конструкторов, соответствующая по длине размеру выводимого диапазона.

Конструкторы с закрывающими фигурными скобками выглядят похожими, можно попробовать их объединить. Вспоминаем про использование логических операторов & и |.

Конструктор для CallProperty в готовом проекте выглядит так:

Вот что получается в листинге:

Возможно, сейчас сбивает с толку, что в семантической секции используется пользовательская операция CallVariadicCallOther. В проекте на github она была переопределена в java-коде инструкциями p-code. Использование инъекции p-code вместо реализации через операцию call было обусловлено желанием видеть список передаваемых аргументов в декомпиляторе (согласно исходникам Node.js, первый регистр диапазона является приемником, а остальные передаваемыми аргументами). Используя только slaspec, добиться этого было бы, мягко говоря, тяжело:

Если есть желание попробовать повторить реализацию диапазонов самостоятельно, можно описать семантику как:

Затем по аналогии можно доопределить конструкторы rangeDstХ (понадобится до r7 включительно) и уже тогда попробовать посмотреть, как выглядит скомпилированный код console.log(1,2,3,4,5,6). Можно собрать его самостоятельно через bytenode или забрать готовый тут. Функция будет находиться по смещению 0x167, а сама инструкция на 0x18b.

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

Стоит отметить, что в нашем проекте мы вынесли все конструкторы rangeDst в отдельный файл, чтобы не загромождать файл с описанием инструкций (как и расширенные инструкции, работающие операндами размером 2 и 4байта):

Итог

Разработанный процессорный модуль удовлетворяет требованиям, которые мы к нему предъявляли: инструмент дает возможность просматривать инструкции байткода для заданных функций файла, который необходимо было разбирать в рамках проекта. В качестве бонуса мы получили декомпилятор, пусть не идеальный, но позволяющий быстрее ориентироваться в логике приложения. Однако, как и при работе со многими процессорными модулями, в данном случае лучше сверяться непосредственно с инструкциями, а не слепо ему верить. Можно также отметить, что при наличии времени и желания улучшить инструмент стоит реализовать хранение типов, продумать концепцию импортов и устранить проблему с обратным порядком аргументов функций. Надеемся, это руководство упростит ваше погружение в написание процессорных модулей на языке SLEIGH.

Также хочется сказать большое спасибо за исследование Node.js и разработку модуля Вячеславу Москвину, Владимиру Кононовичу, Сергею Федонину.

Автор: Наталья Тляпова

Полезные ссылки:

  1. https://ghidra.re/courses/languages/html/sleigh.html документация на SLEIGH.

  2. https://github.com/NationalSecurityAgency/ghidra/tree/master/Ghidra/Framework/SoftwareModeling/data/languages полезные файлы с описаниями *.cspec, *.pspec, *.opinion, *.ldefs.

  3. https://spinsel.dev/2020/06/17/ghidra-brainfuck-processor-1.htmlхорошая статья о реализации модуля для brainfuck в Ghidra.

  4. https://github.com/PositiveTechnologies/ghidra_nodejs репозиторий с полной версией процессорного модуля для Ghidra с загрузчиком и анализатором.

Подробнее..

Категории

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

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru