В предыдущих частях этой серии мы обсуждали внутреннее устройство коллекций ES6 и массивов в V8. На этот раз мы рассмотрим более простую тему - Math.random() функцию.

Каждый JS-разработчик время от времени использует Math.random() в своих приложениях для различных случаев использования. Общая мудрость гласит, что Math.random() годится для чего угодно, кроме безопасности. Тем не менее, эта функция не поддерживается CSPRNG (криптографически безопасный генератор псевдослучайных чисел) и не должна использоваться в задачах, связанных с безопасностью, таких как генерация UUID v4 (примечание: если вы осмеливаетесь использовать UUID для таких задач ).

Сегодня мы попытаемся понять, как именно V8 реализует Math.random() функцию, а затем попытаемся сопоставить наши выводы с общепринятой практикой.

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

Заявление об ограничении ответственности. Ниже описаны детали реализации V8 9.0 в комплекте с последней версией Node.js для разработчиков (точнее, commit 52f9aaf). Как обычно, не следует ожидать какого-либо поведения, выходящего за рамки спецификации, поскольку детали реализации могут быть изменены в любой версии V8.

Spec All the Things

Прежде чем смотреть на код, давайте посмотрим, что спецификация ECMAScript 2020 говорит о функции Math.random():

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

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

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

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

Мелкие подробности

Наше путешествие начинается с Math.random() кода, написанного на языке крутящего момента:

Мы видим, что Math.random() (здесь MathRandom) вызывает макрос RefillMathRandom, определенный в другом месте (см. extern macro). Мы увидим, что делает этот макрос чуть позже.

Затем мы видим, что значение (random число) не генерируется напрямую, а вместо этого возвращается из массива фиксированного размера (array переменная). Назовем этот массив «пулом энтропии» (или просто «пулом»), чтобы его можно было распознать по остальному тексту. Индекс (newSmiIndex целое число) уменьшается при каждом вызове, и периодически, когда он становится равным нулю, вызывается макрос RefillMathRandom, который интуитивно должен пополнять пул, но мы еще не уверены в этом.

Макрос MathRandom определен в классе CodeStubAssembler C ++ и не содержит ничего особенного. Он просто вызывает метод MathRandom::RefillCache через внешнюю ссылку. Следовательно, код, который мы ожидаем пополнить пул энтропии, написан на C ++ и выглядит примерно так:

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

Прежде всего, блок №1 из сниппета описывает инициализацию начального числа, которое будет использоваться в последующей генерации числа. Этот блок запускается только один раз и использует PRNG, доступный в текущем изолированном V8, для генерации начального числа. Затем он вычисляет хэш-коды murmur3 на основе начального числа и сохраняет его в исходном состоянии.

ГПСЧ может быть предоставлен программами для внедрения, такими как браузер Node.js или Chromium. Если PRNG не предоставляется устройством для внедрения, V8 возвращается к системно-зависимому источнику случайности, например /dev/urandom в Linux.

Затем блок № 2 использует структуру состояния для генерации и заполнения всех kCacheSize значений в пуле с помощью генератора случайных чисел xorshift128 +. Размер пула - 64, т.е. после каждых 64 Math.random() вызовов его необходимо пополнять.

Наши выводы здесь следующие. Во-первых, несмотря на то, что начальное начальное число, используемое функцией Math.random(), может быть сгенерировано с помощью криптографически безопасного ГПСЧ (примечание: это зависит от устройства для внедрения и / или ОС), последующая генерация числа не включает этот ГПСЧ. Вместо этого он использует xorshift128 +, который является быстрым алгоритмом генератора случайных чисел, но он не является криптографически безопасным. Таким образом, мы нашли доказательство общей мудрости и, действительно, реализация Math.random() в V8 не должна использоваться для обеспечения безопасности.

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

Как и ожидалось, мы использовали 42 в качестве начального значения в двух отдельных сеансах REPL Node.js, и оба раза Math.random() выдавали точно такую ​​же последовательность чисел.

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

Некоторые глупые тесты

Прежде чем мы пойдем дальше, я должен предупредить вас, что следующие микробенки - это абсолютно ненаучные и несправедливые тесты, так что относитесь к ним с недоверием. Тесты были выполнены на моей машине разработчика с процессором i5–8400H, Ubuntu 20.04 и Node.js v16.0.0-pre (фиксация 52f9aaf).

На этот раз наш микробенчмарк ужасно прост:

При запуске он вызывает Math.random() в цикле и выводит итоговую пропускную способность.

Вооружившись тестом, мы сравним kCacheSize=64 (по умолчанию) и kCacheSize=1 (без пула) сборки Node.js. Вот измеренный результат.

Тест показывает, что удаление пула делает Math.random() 22% медленнее. Разница относительно небольшая, но пул улучшает пропускную способность, удаляя накладные расходы на переключение JS-to-C ++ в каждом Math.random() вызове. Интересно, что в пакете npm uuid, а затем и в crypto.randomUUID() стандартной функции из Node.js также используется аналогичный подход с пулом энтропии (примечание: разница в том, что они используют CSPRNG, и прирост производительности гораздо более значительный).

Пришло время подвести итоги и обобщить наши выводы.

Резюме

  • Как каждый JS разработчик знает, использовать Math.random() для задач, связанных с безопасностью, - плохая идея. В браузерах вы можете использовать Web Crypto API, а пользователям Node.js следует использовать модуль crypto.
  • Начальное семя, используемое Math.random(), использует ГПСЧ, предоставленное средством внедрения (скажем, Node.js или браузером), или возвращается к зависящему от ОС источнику случайности, не обязательно безопасному.
  • Как только начальное начальное значение сгенерировано, последующие значения генерируются детерминированно с помощью алгоритма xorshift128 + и сохраняются в пуле из 64 элементов, который при необходимости пополняется. Детерминизм здесь означает, что в случае одного и того же начального начального значения сгенерированная числовая последовательность, возвращаемая из Math.random(), будет такой же.

Спасибо, что прочитали этот пост. Дайте мне знать, если у вас есть идеи для следующих постов в серии V8 Deep Dives. Отзывы о несоответствиях или неверных предположениях также более чем приветствуются.