Сохранёнки программиста

Самый быстрый известный алгоритм печати double безымянный: он живёт в файле yy_double.c внутри JSON-библиотеки yyjson, написан её автором ibireme и почти нигде не описан. Виктор Зверович, автор {fmt}, разобрал, как он устроен и за счёт чего входит в число самых быстрых. Классический Schubfach на каждое число делает два-три 192-битных умножения. Здесь ядро работает на целых фиксированной ширины и обходится одним умножением на заранее вычисленную степень десяти. Дальше рассматриваются четыре кандидата на округление и выбирается кратчайшее корректное представление с округлением к чётному. Отдельно разобран пограничный случай, где алгоритм выбирает между 2e2 и более длинным 19e1, и на первый взгляд это похоже на баг. Автор использует тот же алгоритм в своей библиотеке Żmij. К тексту приложен интерактивный визуализатор на формате E4M3 из 256 кодировок, на котором видно, как работает каждый шаг. @prog_stuff

Как тестировать сервис, у которого 96 операций в API, больше 500 триллионов объектов и свыше 200 миллионов запросов в секунду? Инженеры Amazon описали свой подход на примере S3: рядом с настоящим сервисом живёт исполняемая эталонная модель, которая хранит состояние и сверяет с ним каждый ответ. Сценарии к модели не пишутся руками и не берутся случайно. Поведение раскладывается на признаки: например, для чтения объекта учитываются 21 параметр запроса, 36 параметров ответа и само содержимое. В одном из экспериментов из 37 признаков получилось 135 категорий поведения и 1025 качественно различных сценариев, которые и генерируются целенаправленно. Сравнение с обычным тестированием на свойствах показательно: там 28 457 запросов дали 9040 уникальных сценариев, остальные 19 417 оказались повторами. У направленной генерации трёхчасовая кампания выполняет около 432 000 запросов. В трёх запусках в конвейере сборки модель поймала 171, 92 и 109 расхождений поведения — среди них десятки настоящих проблем, которые иначе уехали бы дальше. @prog_stuff

Если хочется разобраться в криптографии руками, а не по формулам, есть Cryptopals — восемь наборов заданий, где вы последовательно ломаете реальные конструкции. Устроено так: предварительных знаний криптографии не требуется, нужен только уверенный навык программирования, а язык любой. Каждое задание решается кодом, а не угадыванием. Первый набор — разминка: hex, Base64, XOR одним байтом, XOR повторяющимся ключом, обнаружение режима ECB. Второй уже интереснее: дополнение по PKCS#7, режим CBC, оракул выбора режима, переворот битов в CBC. Дальше — потоковые шифры, генераторы случайных чисел и повторное использование одноразового значения. Затем атака посредника на обмен ключами Диффи-Хеллмана, подмена параметров группы. Ближе к концу — восстановление сообщений RSA, слабые одноразовые значения в подписях, оракулы дополнения. Почему это не устарело за тринадцать лет: ECB, оракул дополнения, повторно использованный nonce и плохая случайность — это классы ошибок, а не конкретные библиотеки. Оговорка авторов тоже важна: набор учит ломать, но не является руководством по выбору криптографии для продакшена. @prog_stuff

Обычная модель угроз для защиты от шифровальщиков предполагает, что операционная система на нашей стороне. Группа из Мичиганского университета взяла модель пожёстче: атакующий контролирует ядро, файловую систему, драйверы, гипервизор и даже привилегированного администратора. Защита вынесена ниже всего этого — на уровень блочного устройства. Физический блок нельзя перезаписать до истечения заданного интервала, состояние блоков ведётся в журнале, который можно только дополнять, а каждая операция проверяется перед записью. То есть шифровальщик может записать свои данные, но не может стереть старые. Прототип собран как блочный драйвер для ext4 на Raspberry Pi с обычными диском и твердотельным накопителем. Ядро проверяющей части занимает около 400 строк кода, а свойства «обход невозможен» и «восстановление корректно» доказаны формально в Dafny. Проверили на 18 семействах программ-вымогателей: файловую систему удалось восстановить в каждом случае. Накладные расходы — 0,4 процента по времени и 0,5 процента по пропускной способности накопителя, счётчики занимают около 2 мегабайт на терабайт данных. @prog_stuff

20 августа на crates.io вышла версия 0.3.10 крейта arrayref. Исходники макросов в ней прежние, в манифесте одно изменение — добавлена зависимость proc-macro1 версии 1.0.107. Настоящий крейт называется proc-macro2, а proc-macro1 — типосквот с подделанным полем authors под именем Дэвида Толная; его src/ копирует proc-macro2, поэтому сборка продолжала работать. Вредонос лежит в сборочном скрипте: адрес сервера собирается из base64-фрагментов, бинарник качается по TLS без проверки сертификата и запускается отдельно от сборки. Срабатывает во время компиляции — достаточно просто собрать проект. Отдельный ход: с того же аккаунта отозвали версии с 0.3.5 по 0.3.9. Cargo на отозванную версию предлагает обновиться, и единственной неотозванной оставалась 0.3.10. Rust Security Response Team сообщила, что 0.3.10 была доступна 86 минут: опубликована в 07:15 UTC, удалена в 08:41. Отозванные версии вернули, аккаунт заблокировали. Задеты ещё internment 0.8.7 и append-only-vec 0.1.9. @prog_stuff

Профилировщик показывает, что горячая функция ждёт память. Дальше начинается гадание: какое именно поле какой структуры не влезает в кэш. Группа из Университета штата Северная Каролина и Google сделала профилировщик, который отвечает на этот вопрос прямо: каждое обращение к памяти связывается с конкретным типом и полем внутри него. Работает поверх штатного perf и отладочной информации, накладных расходов во время работы программы не добавляет, потому что разбор идёт офлайн. Проверяли на ядре Linux 6.17, memcached, Redis, Git, FFmpeg и Binutils. Покрытие типов для обычной сборки Ubuntu — 92,7 процента, циклов ядра — больше 90. У FFmpeg покрытие циклов всего 40 процентов, потому что там много рукописного векторного кода без отладочной информации. Пример находки: в нагрузке MySQL на 256 серверах структура cfs_rq из планировщика занимала 7,58 процента циклов ядра и давала 49,02 процента промахов последнего уровня кэша. Перестановка полей внутри структуры этот вклад заметно снизила. @prog_stuff

Список, который стоит открывать каждый раз, когда садитесь писать что-то с датами: «Заблуждения программистов о времени» Ноа Сассмана. Тридцать четыре утверждения, каждое из которых кажется очевидно верным и каждое неверно. Во второй части их ещё семьдесят девять. Выборочно: в сутках не всегда 24 часа. Часовой пояс машины не совпадает с поясом пользователя. Часовые пояса меняются политическим решением, а переходы на летнее время не постоянны. Часы клиента и сервера не совпадают. Минута на часах не всегда равна минуте реального времени. Временные метки не обязаны быть уникальными. Время события, время записи в журнал и время получения сообщения — три разных момента. Любимый пример оттуда: виртуальная машина, приостановленная на два часа, после запуска продолжила считать, что всё ещё час дня. Вторая часть добирается до високосных секунд, разницы между настенными и монотонными часами и до того, почему sleep(1000) не значит «ровно секунда». @prog_stuff

Статический анализатор выдал 147 643 предупреждения о работе с неинициализированной памятью в ядре Linux. Подтвердились и были исправлены 52. Эта цифра — отправная точка работы группы из Калифорнийского университета в Риверсайде, представленной на OSDI в июле. Проблема известна всем, кто пробовал внедрить анализатор в большой проект: покрытие огромное, а доля настоящих находок такая, что список никто не разбирает. Идея авторов: проверять каждое предупреждение отдельно, исполняя подозрительный участок кода по-настоящему. Для этого произвольный набор функций на C и C++ собирается в самостоятельный исполняемый файл без правки исходников, а дальше по нему идёт символьное исполнение. Запускать всё ядро или готовить окружение не нужно. По цифрам: для Linux 6.16.0 удалось собрать 88,9 процента участков, для Android LTS 5.10.240 — 96,2 процента. Разбор одного предупреждения занимал в среднем 0,32 секунды против 5,14 у сравниваемого подхода, а до вердикта доводилось 95,46 процента случаев против 41,29. @prog_stuff

Телефон переставал играть музыку в Bluetooth-наушниках, как только на компьютере открывалась вкладка AliExpress. Закрыть вкладку — звук возвращается, замьютить вкладку или всю систему — не помогает. Автор блога laserphile обернул конструктор AudioContext и нашёл два скрытых аудиоконтекста в состоянии running, подключённых к destination, — при том что ни <audio>, ни <video>, ни вызовов play() на странице нет. Создают их collina.js и fireyejs.js из каталога AWSC, антифрод-обвязки Alibaba. Граф в обоих одинаковый: пилообразный осциллятор, AnalyserNode, ScriptProcessorNode, GainNode с нулевым усилением, выход в destination. Слышно ничего, но подключение к destination заставляет браузер обсчитывать граф по-настоящему, и аудиопуть остаётся занятым. Звук здесь одна из мерок отпечатка. Рядом снимаются canvas и toDataURL(), данные WebGL, размеры экрана, hardwareConcurrency, поведение WebRTC, события мыши и скролла, показания акселерометра. @prog_stuff

Идея, которую в девяностых довели до рабочего состояния, а потом почти все забыли: файловая система, которая одновременно является базой данных. Даниэль Козенца разбирает Be File System — ту, что досталась Haiku от BeOS. У файла там есть не только имя и содержимое, но и типизированные именованные атрибуты: у аудиофайла исполнитель и альбом, у письма отправитель и статус. По выбранным атрибутам строятся индексы, к тому можно писать предикаты, а живые запросы шлют приложению сообщение, когда подходящий файл появился, исчез или изменился. Почтовый клиент, который просто показывает результат запроса к файловой системе, — это оттуда. Автор при этом честно очерчивает границы. Индекс принадлежит конкретному тому: наличие его на загрузочном диске ничего не говорит про соседний. Результат запроса не вечен — файл могут переименовать или удалить. Соединений таблиц, ссылочной целостности и транзакций над несколькими записями тут нет. И главная ловушка: при переименовании атрибуты следуют за файлом, а вот при копировании наружу как повезёт — архиваторы и средства переноса ведут себя по-разному, и на файловой системе без поддержки атрибутов они просто теряются. Байты остались, смысл потерялся. @prog_stuff

Час, который стоит потратить: доклад Рича Хики «Simple Made Easy» со Strange Loop 2011. Весь доклад держится на разведении двух слов, которые в русском тоже слиплись. Простое — это то, что не переплетено с другими вещами, свойство самой конструкции. Лёгкое — это то, что близко и знакомо лично вам, свойство вашего опыта. Выбирая лёгкое, команда набирает сложность, которую потом невозможно распутать. Хики вводит слово complecting — сплетать вместе то, что могло бы жить раздельно. Изменяемая переменная сплетает значение и время. Наследование сплетает тип и реализацию. Объект сплетает данные и поведение. Всё это удобно писать и тяжело менять через полгода. Отдельный удар по привычным успокоительным: тесты, рефакторинг и система типов повышают безопасность, но не делают дизайн проще. Они ловят ошибки, а не распутывают связи. Практическое, что можно унести на завтра: при проектировании развести вопросы «что», «кто», «как», «когда», «где» и «почему» и следить, чтобы в одном месте не отвечали сразу на несколько. @prog_stuff

Микаэль Лагерквист собирал корпус из 434 201 судоку для экспериментов с программированием в ограничениях, потом захотел в них поиграть — и сделал игровые версии девяти типов головоломок, где все задачи сгенерированы решателем. Общий приём один: начать с готового решения или картинки, а потом добавлять, двигать и удалять подсказки, пока решение не станет единственным. Для судоку это выглядит так: сгенерировать полную таблицу, убирать подсказки и каждый раз проверять уникальность. Сложность судоку определяется не числом подсказок, а самым слабым набором правил распространения ограничений, которого хватает решателю без перебора вариантов. У других головоломок свои измерения, и метки сравнимы только внутри одного типа. Японские кроссворды описаны регулярным выражением вида Empty* Filled{3} Empty+ Filled{2} Empty*, которое среда сама превращает в конечный автомат. Замкнутая линия в Loopy выражается через готовое ограничение на подциклы, путь в Zip — через ограничение на гамильтонов цикл. И приятная деталь: браузер решателя не запускает вовсе, ему отдают заранее сгенерированные головоломки вместе с решениями. @prog_stuff

После одной перенастройки контроллера памяти &x != &x: два разных адреса начинают указывать в одну ячейку DRAM, притом что таблицы страниц, TLB и физические адреса, которые видит ядро, никто не трогал. Автор показывает на AMD Family 16h, что финальное преобразование адреса живёт уже за пределами всего, что защищает операционная система. Он проходит цепочку целиком: MMU, EPT и NPT, IOMMU, кэши, когерентная шина, контроллер памяти и только потом чередование по каналам, рангам и банкам. Один переключатель в конфигурации bank-swizzle схлопывает разные адреса в одну физическую координату. Само преобразование не документировано, поэтому автор восстанавливает его как линейное отображение над GF(2) и решает систему линейной алгеброй и Z3. Дальше в README идут доступ к областям PSP, SMM и SMRAM, к C6 save area и микрокоду. Оговорка у автора честная: почти всё проверено на Family 16h, для 17h и новее нужные регистры уже не документированы, а сама документация AMD неполна — порядок XOR-преобразований и стадии MMIO зависят от модели. Переносимость на другие поколения он не обещает. @prog_stuff

В BGP есть поле ORIGIN: оно говорит, как маршрут попал в протокол, и по стандарту менять его не должен никто, кроме того, кто маршрут объявил. Cloudflare проверили, как это соблюдается, и обнаружили, что примерно у 70 процентов наблюдаемых путей значение отличается от исходного. Мотив денежный. При выборе лучшего пути маршрутизатор смотрит на ORIGIN рано, ещё до сравнения других признаков, и предпочитает меньшее значение. Переписав поле в самое приоритетное, транзитный провайдер повышает шанс, что трафик — и оплата за него — пойдёт через него. Эксперимент простой: объявить шесть блоков адресов с разными значениями и посмотреть, что дойдёт до публичных коллекторов. Переписывают немногие, 64 системы из 606 разобранных, но это в основном крупные игроки: шесть из шестнадцати сетей верхнего уровня. Вывод авторов радикальный: осмысленной роли у этого поля в современном интернете не осталось. @prog_stuff

На iOS браузеры за пределами ЕС обязаны работать на WebKit, а прокси-браузеры вроде Tor-клиентов настраивают прокси через WKWebsiteDataStore.proxyConfigurations: весь трафик страницы должен уходить через прокси. Исследователи Mysk нашли три функции WebKit, которые эту настройку обходят и ходят в сеть напрямую с устройства. <link rel="dns-prefetch"> резолвит имя через системный DNS, а не через прокси: сайт вставляет уникальное имя на посетителя и смотрит, с какого резолвера прилетает запрос. WebAuthn Related Origin Requests заставляет системный сервис учётных данных скачать файл проверки напрямую, раскрывая реальный IP. WebTransport поднимает прямое HTTP/3-соединение мимо прокси. Функции появились в iOS 26.0, 18.0 и 26.4 соответственно. Всё это происходит вне обычного цикла загрузки страницы, поэтому утечки задевают и iCloud Private Relay; VPN не затронуты, они тянут трафик на уровне системы. Началось с одного бага от пользователя, у которого DNS утекал только на некоторых сайтах: без тега prefetch запроса просто не было. Авторы делают собственный браузер Psylo: в 1.3.1 prefetch блокируется, а WebTransport и WebAuthn выключены по умолчанию и включаются отдельной настройкой на сайт. PoC лежит на leaks.psylo.app. @prog_stuff

Есть характеристика процессора, которой нет ни в одной спецификации, а на скорость программы она влияет сильнее модных цифр: сколько промахов мимо кэша ядро способно держать одновременно. Поход в оперативную память стоит около 100 наносекунд — примерно 300 тактов простоя. Задержка эта за десять лет не улучшилась, а ухудшилась. Спасает то, что ядро не ждёт первый ответ, а успевает отправить следующие запросы. Даниэль Лемир измерил, сколько именно, гоняя погоню по указателям в массиве на гигабайт: сначала одну цепочку, потом всё больше независимых, пока добавление новой не перестаёт помогать. У Intel предел вырос с 10 до 30 запросов, у AMD — с 15 до 58, у Graviton — с 6 до 19. Практический смысл: структура с длинными цепочками указателей упирается не в задержку памяти, которая почти не меняется, а вот в этот предел. И он у разных процессоров различается в разы. @prog_stuff

Инженер из Тринидада и Тобаго объясняет, почему спор об элегантности набора инструкций выглядит совсем иначе, когда доставка микросхемы за доллар стоит от 60 до 200 долларов. Весь его аргумент про доступность железа. CH32V003 стоит десять центов: RV32EC, 16 регистров, без умножения и деления, 2 КБ SRAM и 16 КБ флеша, только machine mode. На другом конце того же RISC-V у него CH32H417 с двумя ядрами на 400 и 144 МГц, 896 КБ SRAM, 960 КБ флеша, USB 3.2 Gen1 и стомегабитным Ethernet, а ещё дальше VexRISC-V с MMU, на котором запускают Xous, seL4 и Linux. Одна база набора команд и один toolchain на всём этом пути, тогда как ARM разводит Cortex-M и Cortex-A по разным профилям и лицензиям. С критикой RISC-V по существу автор не спорит: фрагментацию расширений и неудобства вокруг Zcb и Zicsr он признаёт сам и решения комитета не защищает. Это личный инженерный ответ с примерами собственных проектов, а не нейтральное сравнение архитектур. @prog_stuff

Джулия Эванс рассказывает, чему научилась, гоняя небольшой сайт на SQLite. Это не «десять причин выбрать SQLite», а список мест, где она споткнулась. Полнотекстовый поиск по таблице на четыре тысячи строк вдруг выполнялся пять секунд. Помогла одна команда ANALYZE: планировщик, видимо, случайно свалился в квадратичное поведение. Автор прямо пишет, что уверенно читать план запроса пока не умеет и точную причину не знает. Массовое удаление старых строк занимало те же пять секунд с лишним, и в это время второй обработчик не мог записать данные и падал по тайм-ауту, утаскивая за собой виртуальную машину. Временное решение — удалять маленькими пачками. Именно на этом месте, пишет она, стало понятно, зачем PostgreSQL вообще разрешает нескольким писателям работать одновременно. Отдельная история с резервными копиями: VACUUM INTO с архивацией, restic в S3, который иногда падал по памяти, потом Litestream — и снова честное «не знаю, работает ли заданное хранение». @prog_stuff

GitHub разобрал аварию 17 августа. Инцидент длился 7 часов 47 минут и задел Issues, пул-реквесты, API, Actions и Copilot; на пике веб и API отдавали примерно 20% ошибок, а скачивание архивов и сырых файлов — около 50%. Большинство сервисов пришло в норму к 16:36 UTC, Actions деградировал примерно до 18:03, а выдача токенов Copilot восстановилась к 21:02. Началось с того, что sidecar Istio упёрся в предел одновременных запросов и не отмасштабировался: политика следила за лимитами сервиса, но не за лимитами самого sidecar. Отказ пошёл каскадом, четыре узла HAProxy исчерпали лимиты соединений, и сломался путь аутентификации через шлюз. Дальше вмешались повторные попытки. Часть трафика перевели из Central US в Северную Вирджинию, где задержка ответов вскрыла скрытый баг ретраев в VS Code, и нагрузка выросла примерно в десять раз. Помогло не масштабирование, а обратное: паузу на проблемных узлах HAProxy и блокировка запросов кодом 403 на балансировщиках, после чего трафик возвращали постепенно. @prog_stuff

Автор трижды в трёх компаниях строил одну и ту же систему: принять вебхуки от Stripe или провайдера авторизации и держать у себя копию их данных. Каждый раз задача на вечер разрасталась в неделю: проверка подписи, таблица дедупликации, буфер для событий, пришедших не по порядку, стартовый импорт с блокировками и ночной cron сверки. Он разобрал, почему так выходит всегда. Вебхук — это уведомление «что-то случилось» с доставкой at-least-once, без порядка, без полноты и без способа узнать, что ты что-то пропустил. Для запуска побочного эффекта это идеально, а для репликации данных нет: у автора отмена подписки клиента потерялась по дороге, и база месяцами считала его активным. Провайдер при этом держит у себя упорядоченный лог, режет его на POST-запросы и рассылает, а каждый получатель собирает лог обратно, со своими багами. Ночной cron автор называет письменным признанием: «я не доверяю копии и буду пересобирать её с нуля каждую ночь». Альтернатива в статье — перевернуть стрелку: один URL на коллекцию, курсор, полное состояние объекта в каждом событии, tombstone на удаление, Prefer: stream для живого потока и checksum состояния в конце. Дедуп, буфер и стартовый импорт исчезают. Stripe и WorkOS уже отдают похожие Events API, но каждый со своей семантикой; автор оформил идею как черновик протокола SCROLL и сам оговаривает, что это предложение, а не стандарт. @prog_stuff