Compressing AMT in XZB style

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

Но во всей этой шумихе, мне больше всего понравилось, как они дерево пожали.

Бэкдор загрузился раньше других, и теперь ему нужно ждать, когда линкер подыщет всю вкусноту. Бэкдор для этого добавляет хук, который вызывается для каждого нового символа, и ему нужно понять, нужный ли это символ (например, функция загрузки RSA ключа). Проблема: условная строка RSA_public_decrypt@got.plt в бинаре появиться не должна. Это было бы банально слишком подозрительно. Решение? Построить дерево.

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

Места не так уж и много, поэтому китаец взял наш любимый array mapped trie. (Про китайца я, правда, выражаю сомнения. Легко на них всё сбросить.) Только там вместо того, чтобы хранить все узлы полностью в одном массиве, вынесли битмапы в отдельный, второй массив. Всё для того, чтобы можно было там хранить только уникальные битмапы (а узлы на них, соответственно, ссылаются). Такое дерево может спокойно похудеть на 20-30%. Правда, я не уверен, сработает ли такое на бОльших масштабах (при сохранении арности): всё-таки фокус такой LZ-style компрессии в том, что индекс на битмапу меньше размера самой битмапы.


Если интересно почитать более общий обзор, то прекрасная статья здесь. Ещё неплохой материал у herm1t с канала @ruheight конкретно про дерево и почему китаец начал хорошо, а кончил... Ну, как кончил, в общем.

Один из приколов в XZ-бэкдоре я пропустил. Бэкдором можно управлять, послав ему зашифрованную и подписанную цифровой подписью команду. И она зашита в модуль N RSA-ключа (они передаются как ASN.1 или PEM). Сперва я подумал, что ключ используется просто как контейнер, но на самом деле можно сгенерировать работающую ключевую пару с вшитым значением. Есть и статья Ленстры о том, как готовить такие ключи ("Generating RSA Moduli with a Predetermined Portion"), и работающий код от Райана Кастеллучи. Небольшой пример, как вшить константу:

from sympy import randprime, nextprime, isprime
import os, math

x = b"\x80\x00\x00\x00\x00\x00\x00\x01"
j = 0
while True:
  j += 1
  p = randprime(0, (1 << 256))
  l = int.from_bytes(x + os.urandom(56), "big")
  q = l // p # nextprime(l // p);
  if isprime(q):
    break
n = q * p;
print(str(l.bit_length()) + ":" + hex(l >> 256) + "...")
print(str(n.bit_length()) + ":" + hex(n >> 256) + "...")
print(str(p.bit_length()) + ":" + hex(p))
print(str(q.bit_length()) + ":" + hex(q))
# check key, textbook RSA
f = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, f)
m = 0xDEADBEEFCAFEBABE
c = pow(m, e, n)
t = pow(c, d, n)

#находки

https://days-since-openclaw-cve.com/

Days since last OpenClaw CVE - 0

A new CVE was published in the last 24 hours.
Because who needs security when you have vibes?

Best CVE-less streak - 12 days


Можно было на чьём-угодно OpenClaw-хосте утвердить себе права админа. Просто вписав /pair approve. Вместо админа. Это не проверялось. Ты получал полный доступ вообще ко всему.

Ебать

EML - All elementary functions from a single binary operator

В научном калькуляторе у нас много кнопок. Корни, степени там, синусы-косинусы. А теперь давайте поиграем в Сломанный калькулятор: у нас есть несколько "сломанных" кнопок, которые мы не можем использовать, и есть какое-нибудь число, которое нам нужно ввести. Проблема - в числе встречаются "сломанные" цифры. Придётся как-нибудь ухищраться. Например, с поломанными цифрами 1 и 2, чтобы ввести 21 - мы можем написать просто 7*3. Или 9*3-6. Способов много разных, в целом. Можно дополнительно запретить некоторые арифметические операторы, чтобы ещё сверху жизнь усложнить.

А сколько кнопок можно сломать, пока калькулятор не станет бесполезным?

Вот возьмём косинус. Его можно выразить, как sin(x+π/2). То есть, если у нас есть деление и π, то косинус можно исключить из набора минимально-необходимых функций. Корни - вообще частный случай степени. Если есть "вселенная", то набор "атомов", из которых её можно построить - называется функционально-полным множеством. Суть та же, что и у векторного пространства с его базисом.

В логике вот функционально-полное множество порождает пара {AND, OR} (из них выражаются все остальные операции). И таких множеств из пар на самом деле много, с десяток точно наберётся. Ну, немного ещё потому, что всё разнообразие операторов тоже через AND и OR выражается. Но вот две самых крутых операции - это NAND (NOT AND) и NOR (NOT OR). Если просто отрицать результат AND или OR, то тогда каждый по отдельности создаёт функционально-полное множество. В одно рыло! И вот таких вот однорыльных называют универсальными (бинарными операторами, но пока других универсальных ино-арных ещё не придумали; хотя по поводу тернарных задумались). NAND в логике, кстати, называется Sheffer operator/stroke/etc, много имён у него. Правда, Шеффер был вторым, кто доказал его универсальность, и третьим, кто его вообще описал. Просто все потом немного запутались, и все лавры отошли ему одному.

7 апреля 2026, Andrzej Odrzywolek из Jagiellonian University, что в Кракове (кстати, основан в 1364, старейший в Польше и один из старейших в мире) выпускает бумагу, в которой заявляет, что нечестно это как-то: в логике есть оператор Шеффера, а у нас в вещественной математике - нет. Посидел, повтыкал, и пришёл к умозаключению, что всё прекрасно выражается через eml(a,b) = e^a - ln(b) и константу 1 (чтобы можно было логарифм убрать). Собственно, exp minus log. А "всё" - это вещественные числа, весь набор тригонометрических функций, константы e, π, логарифмы, ну и так далее. Конечно, это всё ещё не NAND, которому даже константы не нужно, но и такая универсальность одной функции с константой - уже круто, учитывая, что изначально там было 36 элементов. Вольфрам у себя использует вот множество из 7 операторов. А ещё круто потому, что грамматика сводится просто к S -> 1|eml(S,S).

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

В нейросеть eml, в общем-то, можно всунуть разве что как функцию активации. Какой-нибудь ln(x) оно идеально выучивает и предсказывает. Что, конечно, просто невероятное достижение - функция активации с логарифмом смогла повторить логарифм. А вот для чего-нибудь посложнее обучить уже не получится: с ln(e−ln(e^x−ln(y))) функцию распидорасило настолько, что обучение просто сломалось. Чего и стоило ожидать от экспоненты, которую единственное, что пытается сдерживать - это какой-то там логарифм. Ещё и вычитанием. EML очень быстро "взрывается", а возле нуля ещё и фактически неопределена (дроби слишком малы). Крайне нестабильна, короче.

А вот с деревьями уже поинтереснее. С eml мы имеем обычное бинарное, то есть должно быть проще и быстрее находить оптимальное - в теории. Ну, а ещё символьная регрессия часто работает на уменьшенном наборе операторов, рискуя тем, что их не хватит для описания датасета. Зато арность поменьше. С eml, который бинарный, так ещё и де-юре универсальный, такой проблемы якобы нет. Я правда так до конца и не разобрался, какой из двух аргументов весомее - всё-таки на практике не сильно-то и меньше то дерево выходит. Требуется 19 узлов, чтобы выразить x+y. Для числа -2/3 нужны все 45 узлов. На синус там вообще сотни пойдут, почти так же, как и на π. log2(n) для 45 узлов - дерево глубиною минимум в 6 узлов, а это только базовая арифметика. Так ещё и главное преимущество символьной регрессии на деревьях - интерпретируемая формула на выходе - теряется. Чёрт ногу в том нагромождении exp и ln сломит, не слишком-то оно и сокращается. С таким же успехом можно просто обучить нейросеть, она не сильно хуже будет: практически та же чёрная коробочка, которая тоже аппроксимирует какую-нибудь функцию, только хуй знает какую. Всё-таки на матрицах не сильно погадаешь.

Ну короче классно, но очень-очень нишево. И не очень-то и революция. Хотя логический гейт EML Sheffer для аналоговых схем в бумаге уже предложен. А губа не дура!

Почему рандомный шум несжимаемый?

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

Возьмём все битстроки какой-нибудь длины n, да. Если это рандомный шум, то распределение униформное - вероятность встретить любую из строк 1/2^n. А компрессия это что?

Блять, вопрос вообще-то хороший. Если зайти интуицией, то вот можно представить, что строка несёт какую-то информацию. Допустим, строку можно удлинить (как тот url longener), и при этом не потерять в информативности. Размазать информацию, короче. Но тогда логично предположить, что можно пойти и в обратную сторону? Тогда для одной и той же информации можно представить целый бесконечный спектр всех строк, которыми она может быть представлена. Хотя скорее это даже луч, как нам на математике в 3 классе рассказывали, потому что у этого спектра явно есть начало. Если пустая строка и может быть дохуя информативной, то вот с отрицательной длиной как-то лыжи уже не едут.

Собственно, компрессия и есть - переместиться ближе к началу луча. Желательно.

Нижний предел длины, или же начало луча, можно оценить по среднему количеству информации в строке - оно же 2^n - оно же энтропия строки, как однажды сказал мой кумир Шеннон.

Возвращаясь к нашим строчечкам, как и было сказано - вероятность каждой составляет 1/2^n, это и есть наша энтропия. Значит, каждая битстрока длины n несёт в себе ровно столько информации, сколько в ней собственно бит. Если взять какую-нибудь одну рандомную из них и попытаться урезать ей один битик, тогда вдруг окажется, что эта урезанная строка является префиксом для второй битстроки. Это не очень приятно, особенно если мы захотим потом передавать эту информацию. Ну а как понять-то ёпта, ты получил полную n-1 строку, или нам всё-таки хотели следующим битом донести другую истину? Короче однозначность декодирования пропадает. Опыт ниже среднего.

Хорошо, от неоднозначности можно избавиться. Из всех битстрок можно построить одно большое бинарное дерево, которое сможет однозначно их определять. Напоминаю, у n-1 и n битстрок будет общий последний бит, поэтому чтобы в дереве не проебать n строку, нам придётся перейти на соседний узел от n-1 строки. Но он и так уже определяет третью битстроку. Но! Не стена, подвинется. Из терминального тот соседний узел магическим образом превращается в обычный и теперь ведёт к двум новым узлам: один для n строки, второй для той самой неудачливой третьей битстроки, которая там изначально сидела (жертва обстоятельств!). Эти два новых узла, выходит, лежат уже на n+1 глубине, а значит - теперь они кодируются n+1 битами.

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



Ремарка: сложность Колмогорова* здесь роли не играет - общая тенденция 2m новых бит для m убранных. ВСЕГДА. Даже если взять строку, состояющую полностью из нулей и сократить её до одного нуля, мы всё равно получим 2(n-m) бит оверхеда.

Сложность Колмогорова* - длина наименьшей программы (обычно машины Тьюринга), способной описать некую строку. В целом, она и классическая энтропия - две стороны одной монеты. Только эта более прикладная в контексте компрессоров.

А ещё лучше посмотрите 3b1b.

How-To: mutex в юзерспейсе, часть I

Кто не любит блокировать мьютексы? Поднимите руки. Я их пожму.

Начнём с истории. История - это не только интересно, но ещё и важно. Потому что я так сказал.


В Линуксе и в Винде до 2000х примитивы (и не очень) синхронизации были впаяны в ядро. Общаться с ними приходилось сисколлами, а это дороговато. Самое обидное, когда за ресурсом редко конкурентно обращаются (а это частый кейс), и ты перфомансом за воздух платишь. В какой-то момент это преодолело критический порог, таки постоянно контексты дрочить и планировщику по хуйне мозги ебать - экспириенс ниже среднего. Тогда-то к 2003-му в Линукс и завезли futex, в честь fast userspace mutex.

Была такая ОС, Solaris называлась, Sun её породили. Поскольку ребята ещё с 80х вкладывались в многоядерные и многопроцессорные машины, к концепту futex'а они пришли ещё в 1990х. Всё-таки приятнее, когда синхронизация съедает чуть меньше, чем всё. Сам концепт прост как три пизды - атомарный флаг "занято", если нет - выставляем, а сами пользуемся. К ядру с унылым еблом идём, только когда гонка проиграна и флаг оказался выставлен до нас. Собственно, это и есть наш happy-path в uncontended locks.

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

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

Только вот у Windows NT был обширный (реально сука обширный!) арсенал объектов синхронизации (такое примитивом называть - что Христа предать), который представлял из себя ядерные объекты. Ну, то есть, в Линуксе это просто int value, а в Винде прям полноценные объекты, с кучей дополнительного контента. Главный фокус - ты можешь кинуть сразу несколько объектов в WaitForMultipleObjects(), и ядро переварит их. Это буквально как select в Go, можно сразу из нескольких источников ждать. Только если Go ограничивается каналами, то в винде это могли быть пайпы, файлы, ивенты, таймеры, потоки, процессы - что угодно. Яж говорил, арсенал солидный.

Только в Windows 8 микрософты допёрли, что люд просит легковесных примитивов. Тогда-то и появился WaitOnAddress, который абсолютно тот же futex. Теперь у нас два мьютекса ебать. Один старый-добрый со всем багажом контента, а второй лёгкий на WaitOnAddress.

How-To: mutex в юзерспейсе, часть II

Как вы заметили, я люблю попиздеть. И ещё реже по делу, как то диктуют святые мужские традиции.

Futex и WaitOnAddress - это просто удобный механизм уходить в ожидание. Именно поэтому просто навесить какой-нибудь CAS на существующий мьютекс было идеей ниже среднего - удачи придумать, как нормально спать с примитивами, на то не рассчитанными.

The futex() system call provides a method for waiting until a certain condition becomes true. It is typically used as a blocking construct in the context of shared-memory synchronization. When using futexes, the majority of the synchronization operations are performed in user space. A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true. Other futex() operations can be used to wake any processes or threads waiting for a particular condition.

То есть вызываешь FUTEX_WAIT, говоришь "за этим поинтером лежит 0хА". Если там 0хА, то поток уходит в сон. Просыпается, когда кто-то другой вызывает FUTEX_WAKE. В котором, кстати, ещё можно указывать, сколько спящих будить.

Сам мьютекс делается примерно так:

/* Simplified pthread mutex */

// 0 = unlocked,
// 1 = locked,
// 2 = locked with waiters
int mutex_word = 0;

void pthread_mutex_lock(int *mutex_word)
{
    // Fast path: try to take the lock with an atomic CAS
    if (atomic_cmpxchg(mutex_word, 0, 1) == 0)
        return; // got it, no kernel call

    // Slow path: there's contention, call into the kernel
    do {
        // Mark that there are waiters
        atomic_set(mutex_word, 2);
        // Sleep until value != 2
        futex(mutex_word, FUTEX_WAIT, 2, NULL, NULL, 0);
    } while (atomic_cmpxchg(mutex_word, 0, 2) != 0);
}

void pthread_mutex_unlock(int *mutex_word)
{
    // Fast path: no waiters
    if (atomic_xchg(mutex_word, 0) == 1)
        return; // just clear, no kernel call

    // Slow path: there are waiters, wake one
    futex(mutex_word, FUTEX_WAKE, 1, NULL, NULL, 0);
}

В лучшем случае - мы просто дрочим mutex_word из 0 в 1, и наоборот. Потому что locking is only expensive when there's contention (это цитата а не выебон). Когда возвращаем, смотрим, не нужно ли оно кому, если нужно - будим его.

Кстати фанфакт: у фьютексов ещё есть режим с приоритетами. Если поток с высоким приоритетом спит, пока локом владеет поток с низким приоритетом, то последнему на время приоритет повышается. Чтобы съебал побыстрее.

Фокус в том, что вообще все мьютексы устроены буквально идентично. Даже в Go, хотя там они не удержались и всё-таки наебнули CAS дважды. В NetBSD, FreeBSD и Dragonfly тоже есть futex, в Винде эквивалентный WaitOnAddress - редкий момент унификации. Даже я переизобрёл свой мьютекс, когда нужно было по-честному мультиплексировать записи в сокет. Прям буквально 1 в 1.

Ну, а на правах инжирнера, существование одного фундаментального примитива приносит мне просто эстетическое удовольствие. The less the kernel knows, the better. А это уже выебон.

Но про Go я бы поговорил поподробнее. У них мьютекс интересный такой: есть starvation mode, когда кто-то дольше миллисекунды не может забрать себе лок, тогда владение мьютексом напрямую переходит к этому бедняжке. Правда, пока эта миллисекунда не прошла, происходит что-то очень близкое к busy loop. Просто потому, что запарковать горутину очень, очень дорого, а локи обычно долго не живут.

А ещё, сам sync.Mutex состоит из state int32 и sema uint32. Они двое разделяют семантику mutex_word из сниппета - state для атомарного счётчика, sema как уникальный идентификатор для рантайма. Ну, точнее, его адрес, в самом sema обычно лежит просто 0. В рантайме есть своя субсистема семафор, которая как раз и использует фьютексы и WaitOnAddress, когда можно (а когда нельзя, то фоллбэк к обычным семафорам по сисколлам). Этот sema и используется, как "якорь", на котором futex будет засыпать.

В общем, Go выполняет роль местного Хаскелла, только в целом хуже. Если Хаскелл - это прикладной лямбда-калькулюс, то Go - это прикладной CSP, но с минусом в виде дорогих каналов. Основополагающих блять!!

Короче, не нравится он мне.

futex2, Wine и WaitForMultipleObjects()

Я не договорила.

Я упоминал WaitForMultipleObjects() в NT. Естественно, с фьютексом, который абсолютный примитив, его семантику повторить не так просто. Что, в целом, не то, чтобы кого-то ебало в программировании под Линукс. Но ебало контрибьюторов Wine, потому что без нормального способа эмулировать поведение перф местами был в жопе.

Поэтому в Линуксе с 5.14 по 5.16 зашелестел ветер перемен. Изначально был гигантский пропозал с кучей нововведений, включая variable-sized futex word. Но решили сделать проще и адаптировать ключевые моменты под существующее ABI. А что не смогли, то в отдельные семейства сисколлов унесли. Правда, шрамы древних споведаний всё равно остались:

FUTEX2_SIZE_U8
FUTEX2_SIZE_U16
FUTEX2_SIZE_U64
These are defined, but not supported (EINVAL).

По итогу, futex2 так и остался наречием, эгидой. Но под этой эгидой добавили FUTEX_WAIT_PI2, который от обычного (не 2) отличался только лишним аргументом - теперь таймер явно указывается. До этого правда делалось то же самое, методом включения битфлага в случае, если реалтайм захотелось. Честно говоря, и сам не ведаю, на кой хуй они это сделали.

Однако!

Винишко своё таки пролоббировало, и в конце концов добавили один, но самый важный сисколл - futex_waitv. Теперь можно спать не на одном фьютексе, а сразу на куче аж до 128 штук. Воистину перемога!

Собственно, именно об этом и кричали в 2021 "ЛИНУКС ГЕЙ МИНГ ПОДНИМАЕТСЯ С КОЛЕН!!"


А, и помните ещё, я говорил, что чтобы поток заснул, нужно, чтобы val в сисколле соответствовал тому, что стоит за *uaddr? Если кому-то не похуй, то вот зачем:

If the futex value does not match val, then the call fails immediately with the error EAGAIN.

The purpose of the comparison with the expected value is to prevent lost wake-ups. If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the calling thread will observe the value change and will not start to sleep.

Поэтому вокруг фьютекса всегда надо ставить гарды от EAGAIN. В сниппете с мьютексом эту роль на себя взял do..while.

rsync in a nutshell

3 месяца назад, 30 лет тому, австралийский национальный университет дропает эту имбу. Алгоритм для модифицирования файла на удалённой машине для соответствия оригинальному. Если по-простому, то переносить диффы. Это если кто до этого про rsync не слышал.

У меня, если что, просто интернета нет. Со скуки нашёл откуда-то бумагу по нему. Вот и пишу теперь с хотспота. А вам читать.


Собственно, диффы. Можно, конечно, и их перекидывать, но есть проблема. Взяли ядро GNU/линукса версий 1.99.10 и 2.0.0, там 32к строк разницы. GNUшный diff выдал выхлопа на 2.1мб. Когда тестили rsync, в среднем там по сети перелетало 1.5мб (рекорд - 1.2мб). Так ещё и пока diff 4 минуты ебался, rsync за 2 минуты отфинишировал. Конкретно здесь - чем быстрее кончил, тем наоборот лучше.

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


Задачи выплёвывать человекочитаемые диффы не стояло, поэтому алгоритм прост как три пизды: есть компьютер А, есть компьютер Б. Компьютер А держит оригинал, Б хочет синхронизироваться. Недофайл, который лежит на Б, делится на блоки по S байт, для каждого считаем rolling checksum и MD5 хэш*. Они парами отправляются компьютеру А. Дальше А умным образом смотрит у себя, что из этого всего у него есть, и отправляет обратно Б инструкцию, что и куда записать, чтобы получить копию.

*в оригинальной бумаге используется MD4. MD5 вышел в 1991, а бумага по rsync - в 1996. Скорее всего, выбор был сделан на основе перфа - MD4 быстрее, а MD5 сильнее криптографически. Может, последний и правда уменьшает риск коллизий, ака ПОВЫШАЕТ ЭНТРОПИЮ. Тогда переход имел смысл, как только компьютеры стали шустрее калькуляторов из Техаса.

Ну так вот, умный образ. Он классный. Компьютер А проходится по всему файлу, и для каждого оффсета считает rolling checksum. Да, дороговато, мы пересчитываем чексумму для практически каждого байта в файле. Но это простенькая 32-битная чексумма, похожая на adler-32, и она определена, как взвешенная сумма байт. Поэтому, чтобы посчитать чексумму для следующего оффсета, из неё достаточно просто вычесть первый сумманд и прибавить новый. Таким образом и выходит быстро и дёшево пробежать по всему файлу и найти все блоки S байт, которые соответствуют оным в наличии у Б.

Естественно, это слабая чексумма. Я где-то оставлю документ, 3 раздел о ней. Но сила ей и не нужна, для силы есть MD5.

А дальше начинается самое интересное. Дальше начинается хэшмапа на открытой адрессации!

rsync использует трёхуровневую схему поиска совпадающих блоков. Когда А получает все пары чексумм-MD5, он считает 16-битный хэш от 32-битной чексуммы и сортирует пары, полученные от Б, по этому хешу. Получается хэшмапа на 2^16 слотов.

Вот и выходит: когда А считает чексумму, он сразу берёт от неё хэш и идёт в мапу. First-level check - проверка на то, что с таким хэшем вообще не-нулевой слот. Потом линейно ищется слот со совпадающей чексуммой - это second-level check (до тех пор, пока хэш чексуммы не перестанет совпадать с посчитанным). О мапах на открытой адрессации я подробнее здесь писал.

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

А главное - это работает хорошо для практически-идентичных файлов.

Под постом оставлю сниппет с псевдокодом на расте, как примерно устроена вся эта эпопея со скользящей чексуммой.

'I NOTATION POLISH REVERSE ❤️'

В мире аллокаторов: dlmalloc

У меня хобби такое, аллокаторы переизобретать.


Аллокаторов вагон, маленькой тележкой занимаюсь пока я. Практически у каждой программы свой уникальный паттерн мемори-менеджмента. Некоторым нужно аллоцировать очень много маленьких объектов (как вот питон), некоторые жрут килобайтами (как вот компиляторы). Ясен хуй, каждый из кейсов накладывает свои ограничения, вокруг которых можно чуть эффективнее играться. Пускай это будет некий оптимум. Даже general-purpose аллокаторы блуждают вокруг чутка разных усреднённых оптимумов - скорость, фрагментация, thread-safety. По хорошему, конечно, и их тоже под задачу выбирать надо. Как жаль что поебать.

Есть сегмент памяти, у нас там 4 объекта живёт. Скажем, два посередине освобождаются, и у нас остаётся два свободных блока - и два занятых по краям. Нам бы эту память посередине переиспользовать, но аллокатор-то не может знать, какого размера будут новые объекты. Это называется coalescing (объеденить два маленьких сегмента для одного большого объекта) и splitting (разбиение большего сегмента для объекта поменьше).

Вот сначала и был dlmalloc, отец ptmalloc и дед glibc's malloc. О нём и поговорим.

Его инвариант - не может быть двух соседствующих свободных блоков. То есть, занято-свободно-занято-... идёт в строго шахматном порядке:

chunk A | FREE | FREE | chunk B
               ↓
chunk A | LARGE  FREE | chunk B

Но устроен он интереснее. У него есть отдельные корзины (bins) для маленьких <256 байт объектов, и отдельное бинарное дерево для >256 байт (но меньше 256 килобайт). Логика такая: оверхед 8 байт для аллокации на 40 байт это дохуя. Оверхед 10 килобайт для аллокации на 400 килобайт - это норм. Сами smallbins - это просто double linked-list, при том зацикленные. Их 28 штук, на каждый (разумный) size-class. В неаллоцированных и лежат как раз указатели на предыдущий и следующий узлы, пока они не будут выделены и их не перезапишет программа своей хуйнёй. На них есть своя лукап-таблица на 32 вхождения, поэтому выделение маленьких объектов пиздец быстрое и константное.

Бинарное дерево у них называется treebin (видимо чтобы не путать). Это, ну... Просто бинарное дерево, самое обыкновенное. Правда, они тоже делятся на size classes, только тут они уже очень широкие и идут по степеням двойки (каждый следующий size class range экспоненциально больше). Подходящий блок внутри них ищется по стратегии best-fit, то есть куда аллокация лучше всего влазит. Правда, с небольшой девиацией - обычно best-fit выбирает свободный блок, который максимально близок по размеру к запрашиваемому. Но тут, если для 380кб аллокации будут претенденты 400кб и 900кб, то выбор падёт на последнего - потому что после него останется 520кб дура. Аллокатору такая идея нравится больше, так как можно будет ещё один здоровый кусок нормально туда уместить. Его стратегия вообще agressively coalesce:

We don't know the future, so use a generally robust policy: coalesce aggressively, preserve large holes by best-fit for larger allocations, and use fast size classes/locality heuristics for small allocations.

Этим-то он и отходит от теоретического best-fit.