Немного про HTTP/2

Я самое интересное забыл! Но сначала всё-таки введение в окна.
TL;DR - если разгерметизировались, то лучше поменять, теплопроводимости пизда.


В HTTP/2 есть connection/stream windows. Connection window я буду называть глобальным, не с вашего позволения.

Семантически это то же самое, что и окна в TCP подключениях - ты перестаёшь слать данные, когда этосамое окно переполняется. Удалённый пир сам тебе говорит, сколько байт он обработал. Это для того, чтобы избежать заторов - congestion - когда ты продолжаешь насыпать, пока пир ахуевает и не может ничего принять.

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

В HTTP/2, из-за мультиплексирования внутри одного подключения, пришлось переизобретать окна по второму кругу. Теперь у каждого стрима есть своё собственное окно, и одно глобальное на целое подключение. Нахуя глобальное нужно - вообще без понятия, но скорее всего, чтобы им можно было отключать per-stream окна. Последние были изобретены ради DATA фреймов (ими тело перекидывают).

Потому что! HTTP/1 болело Head-of-Line блокировкой. Это значит, что пока текущий запрос не завершится, другой ты хуй начнёшь обрабатывать. Ради этого браузеры даже по нескольку подключений открывали (по-умолчанию до 6 на домен, domain sharding звётся, писал тут). Хром сходу два открывает.

Ровно для этого и породили стримы. Потому что несколько подключений нахуй не надо (а ещё их количество часто и щедро режет файрволл). Ну и в дополнение можно сильно лучше сжатие заголовков HPACK производить. Но вот представим: мы шлём сразу два POST-запроса одновременно. Обработчик может начать втыкать перед тем, как непосредственно начать обрабатывать это тело. Это значит, что всё подключение блокируется, пока этот далбаеб не начнёт работать. Connection stalling - очень такая себе штука, особенно если в этот момент прилетает PING (им обычно RTT замеряют или в подключение палкой тыкают, а-ля кипалайв).

Решение - DATA-фреймы нужно куда-то откладывать, чтобы пайплайн не вставал. Собственно, для этого и есть окна. Per-stream окна, видимо, добавили с расчётом на то, что кто-то додумается каждому обработчику индивидуальную складскую коробочку выделять.

Естественно, per-stream окна можно вполне спокойно отключать. Нужно просто сделать его равным глобальному окну. А для глобального окна можно просто гигабайт въебать. Так, например, делает фейсбук (только у них почему-то гигабайт без одного байта. Мелочные люди.)

И немного про bump-аллокаторы

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

Спустя добрых пол года размышлений, я пришёл к старому-доброму bump-аллокатору. Это я просто аллоцирую одним махом буфер на добрый мегабайт и больше его не дрочу. Сим я эксплуатирую demand-pages - виртуальные страницы маппятся в физическую память только тогда, когда мы туда что-то пишем. Вот поэтому какой-нибудь хром и может выжирать сотни гигабайт виртуальной памяти, умещаясь при этом в 6-8 физических.

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

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

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

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


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

https://pubs.acs.org/ancac3/article-abstract/14/1/21/602927/Will-Any-Crap-We-Put-into-Graphene-Increase-Its

„We added shit to graphene“

В мире меча и компляторов!

https://github.com/xoreaxeaxeax/schrodingers-toctou



TL;DR Когда мы скомпилируем что-то эдакое:

unsigned int g(unsigned short *p) {
  short t = *p; //copy *p into a local for safekeeping
  return (unsigned short)t - t;
}

мы в ассемблере (arm gcc 14.2.0, -O2) можем вполне себе увидеть:

g:
        ldrh    r2, [r0]     # load *p, once
        ldrsh   r0, [r0]     # load *p, twice
        subs    r0, r2, r0
        bx      lr

одно чтение стало два!

Собственно, размножение почкованием доступно потому, что абстрактная машина С считает, что память между двумя чтениями не изменится. Invented load называется.

Да вот незадача.

if (sh->len <= 20)  // CHECK reads shared->len
    // ** attacker modifies shared->len **
    memcpy(out, sh->data, sh->len);  // USE reads it again: buffer overflow

Неатомарненько выходит. Там аж PoC в репозитории есть.

При том подвержена куча компиляторов на куче таргетов. Как на -О2, так и на -О3.

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

Можно изъёбываться с барьерами и volatile, но это всё не убивает проблему на корню. Volatile, например, относится к lvalue, тот же memcpy квалификатор не сохраняет. Тогда оверфлова просто закапывается чуть ниже. А барьеры нередко стоят не там, где надо.

Даже деды хуесосят комитет С, по этому и не только по этому поводу. В половине случаев, правда, дед вполне себе конкретный - начинается на Л, кончается на инус Торвальдс.

Ёжик плакал и кололся, но на С писать не переставал.

Я на матфак вступил

GZIP наносит ответный удар

Вот мы хотим классифицировать текст. Классическая задача для ML. Поэтому в основном здесь рулят deep neural networks (отныне DNN).

Да, но:
- посчитай миллионы параметров
- поднеси тонну текста
- поднеси железо
- ой иди нахуй меня на таком не учили

А теперь помните кросс-энтропию? 3b1b видос выпускал. Это когда мы оцениваем, насколько хорошо одно распределение ложится на другое. А-ля в HPACK у HTTP2 вхардкоженная в стандарт таблица Хаффмана, строили по типичным для протокола сэмплам. А теперь представьте таким какой-нибудь бинарный код или кириллицу сжимать. Не-алфавитные символы в той таблице по 30 бит занимают, если что.

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

Он просто брал тексты на одном языке, прилеплял к ним тексты на другом, и смотрел, как хорошо gzip это сожмёт.

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

В 2023 выходит интересная бумага. Даже не потому, что в ней буквально 5.5 авторов, из которых трое с очень китайскими фамилиями, и не менее американскими именами. А потому, что они gzip'ом тексты классифицируют.

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

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

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

Есть класс grammar-based компрессоров, например. Они пытаются построить грамматику текста, которая и выступает программой. Тогда всё становится возможным.

Вот и мы возьмём C(x) как аппроксимацию. Пусть она возвращает длину сжатой строки x.

Собственно, теперь нам остаётся взять информационное расстояние между двумя текстами. Китаймериканцы представили Normalized Compression Distance, определённую как

NCD(x,y) = (C(xy) - min(C(x), C(y))) / max(C(x), C(y))

(простите, у меня пока нет према, чтобы в латех писать)

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

Собственно, вот и всё. Берём референсы (классы), и смотрим, к какому из них текст ближе всего.

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

Зато способ с попарным сравнением текста с каждым сэмплом датасета охуенно профитирует.

Для тестов взяли выпуски новостей. 7 in-distribution и 5 out-of-distribution датасетов - разница в том, что DNN в сравнениях обучали на первых семи, а остальные пять в выборки не входили. Это всякие филиппинские и хуй-выговоришь новости. И в результате...

...NCD был на уровне нейронок в in-distribution новостях. А out-of-distribution рвал, потому что компрессор в целом data-type-agnostic. Даже когда нейронки слегка пре-тренили. Ему поебать, если вы ещё не поняли. Он хоть самобытный диалект с 40 носителями пожмёт и сделает это с гордостью.

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

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

И это всё ещё классификация без обучения. Для вообще любого языка.

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

гемини

я хрюкнул