[devel] удволетворение зависимостей - pkglist-unmets v0.1 (+rpmdsCompare sucks)

[Alexey Tourbin <alexey.tourbin@gmail.com>]

Уважаемые мужчины, жители Энрофа!

Я написал новую программу обнаружения неудволетворенных зависимостей.
https://github.com/svpv/pkglist-unmets/blob/master/unmets.c
Старую программу /usr/bin/unmets написал тоже я, а было это, ох, еще 12
лет назад.  Поскольку deepsolver, ваш отечественный менеджер пакетов,
не взлетел, а разработчик его перешел на apt, то вот и у меня зачесалось
перетряхнуть некоторые вещи, связанные с аптом.  Итак, старая программа
просто создавала отдельное от системного состояние апта (с помощью
/usr/bin/mkaptbox), запускала на нем "apt-cache unmet" и немного
переформатировала вывод (чтобы выводилось по одной зависимости на
строчку).  Новая программа написана на Си, никак не связана с аптом,
и делает всё сама.

$ cat /var/lib/apt/lists/*pkglist.* |/usr/bin/time ./pkglist-unmets
2.41user 0.11system 0:02.54elapsed 99%CPU (0avgtext+0avgdata 55344maxresident)k

Программа получает на вход поток rpm-хедеров, строит внутри какие-то
таблицы, и ничего не выводит (потому что неудволетворенных зависимостей
нет).  Требует это около 2.5 секунд и 55 Мб памяти.

При этом подключен полный комплект репозиториев:

$ du -hsc /var/lib/apt/lists/*pkglist.*  
48M     ..._Sisyphus_noarch_base_pkglist.classic
53M     ..._Sisyphus_x86%5f64-i586_base_pkglist.classic
91M     ..._Sisyphus_x86%5f64_base_pkglist.classic
44M     ..._Sisyphus_x86%5f64_base_pkglist.debuginfo
234M    total

Для сравнения, повторный запуск "apt-cache unmet" (на максимально
"горячем" состоянии) занимает около 2 секунд и 124 Мб памяти:

$ apt-cache unmet >/dev/null && /usr/bin/time apt-cache unmet >/dev/null
1.93user 0.03system 0:01.97elapsed 99%CPU (0avgtext+0avgdata 124764maxresident)k

Если же создавать отдельное состояние, то получается 12 секунд user time
и минимум 187 Мб памяти (максимум среди всех процессов), а общее время
не имеет значения, поскольку здесь у меня идет скачивание по сети:

$ /usr/bin/time unmets -s /etc/apt/sources.list.d/alt.list
11.66user 1.23system 0:28.40elapsed 45%CPU (0avgtext+0avgdata 187372maxresident)k

На самом деле потребление памяти в смысле нагрузки на подсистему
виртуальной памяти ядра здесь намного больше, поскольку apt
распаковывает pkglist.classic.xz и хранит их в разжатом виде.
Так что можно смело добавлять "234M total".  Интересно также оценить,
сколько из этих 12 секунд уходит на распаковку xz.

$ time xz -dc Sisyphus/{x86_64-i586,noarch}/base/pkglist.classic.xz Sisyphus/x86_64/base/pkglist.{classic,debuginfo}.xz >/dev/null      
3.38s user

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

$ xz -dc Sisyphus/{x86_64-i586,noarch}/base/pkglist.classic.xz Sisyphus/x86_64/base/pkglist.{classic,debuginfo}.xz |time md5sum
0.54s user

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

$ time xz -dc Sisyphus/{x86_64,noarch}/base/pkglist.classic.xz |./pkglist-unmets
xz  2.02s user
./pkglist-unmets  1.65s user

Поэтому есть еще идея параллельно с pkglist.classic.xz генерировать
pkglist.classic.zst.  Это будет полезно и в ряде других случаев;
напишу об этом в следующий раз.

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

Из каждого rpm-хедера программа берет Requires и Provides.  Далее надо
отсортировать их по имени, однако зависимости представлены в виде трех
связанных массивов: names[], versions[] и flags[].  Как отсортировать
три связанных массива?  Ну, можно соединить их в один массив записей
struct { name, version, flags } и отсортировать. :-)  С другой стороны,
абстрактному алгоритму сортировки какая разница что сортировать?  Ему
можно дать сортировать просто индексы 0..N-1, а весь доступ к реальным
данным могут взять на себя примитивы LESS (или CMP) и SWAP.  В общем, на
третий день Зоркий Глаз понял, что тут всё сходится, и реализовал макрос
QSORT(N, LESS, SWAP).

Далее задача состоит в том, чтобы избежать глобальной сортировки массива
Requires и Provides, а понемножку сливать их алгоритмом слияния.  При
этом слияние должно быть сбалансированным, чтобы обеспечить оптимальную
асимптотику.  То есть нужно сливать зависимости 1+1, далее 2+2 пакетов
и т.п.  (Конечно при слиянии 1+1 у одного из пакетов зависимостей может
оказаться намного больше, но на следующих уровнях усреднение происходит
очень быстро.)  Чтобы реализовать такое слияние, проще всего
устроить стек, класть на стек очередной пакет и пытаться провернуть
сверху вниз серию слияний.  В какой-то момент на стеке окажутся пакеты
в таком количестве:

	top -> 1 2 4 8 ... n

После того, как на стек положат очередной пакет, запустится каскад
слияний 1+1=>2, 2+2=>4, 4+4=>8, ..., n+n=2n, после чего стек окажется
в состоянии

	top -> 2n

Когда все rpm-хедеры загружены, стек досливается принудительно,
уже не в оптимальной пропорции n+n, а как получится - x+n, x<n.
В общем, такой алгоритм слияния очень похож на то, что на человеческом
языке называется bottom-up mergesort.  Из этого следует, что он
обладает оптимальной асимптотической сложностью, и в некотором смысле
более оптимален даже по сравнению с глобальным qsort, т.к. Quicksort
выполняет в 1.2-1.3 раза больше сравнений, чем merge sort.  А сравнение
здесь как раз стоит несколько дороже обычного, что плавно подводит нас
к следующему пункту.

Основным источником избыточности в отсортированном списке строк являются
повторяющиеся общие префиксы.  И имеется очень эффективный алгоритм
сжатия, который называется front encoding и используется, например,
в locatedb(5).  В последовательности строк /usr/aa и /usr/ab из второй
строки достаточно закодировать только "b" и длину общего с первой строкой
префикса - length("/usr/a") = 6.  (Вместо префикса часто кодируется
дельта, т.е. разница между этим префиксом и предыдущим префиксом.
Это дает то, что дельты по абсолютному значению получаются намного
меньше префиксов.  Иногда это важно, иногда - не очень.)

В общем, весь смысл тут в том, что два сжатых списка можно сливать
вместе в третий список без полной их распаковки, то есть используя
в несколько раз меньше памяти, чем если бы алгоритм работал на
распакованных строках.  Более того, у меня есть подозрение, что
он может работать даже и быстрее, если не отбрасывать информацию
об имеющихся префиксах, а пытаться использовать ее при кодирования
третьего списка.  У меня пока слияние реализовано достаточно
прямолинейно (функция mergeSeq) - на каждой итерации имя
восстанавливается полностью и сохраняется/копируется для следующий
итерации.  Очевидно, что там могут быть сделаны некоторые оптимизации.
Но как сделать *исчерпывающую* оптимизацию этого алгоритма слияния -
это вопрос довольно каверзный, и я его пока как следует не обдумывал.
Применительно к именам зависимостей этот вопрос не имеет столь важного
значения, а вот для ELF-символов он будет гораздо важнее.
(Действительно, по количеству и по длине символов там доминируют
C++-символы вида namespace::class::method, причем и в декорированном
виде общим префиксом методов является namespace::class.)

В конце получается два отсортированных списка Requires и Provides,
и уже ясно, как найти неудволетворенные зависимости.  Если зависимости
из Requires с именем R.name нету в списке Provides, то получается
неудволетворенная зависимость по одному только имени.  Такие
неудволетворенные зависимости выводятся без версии, даже если в
зависимости есть версия.  (Мне кажется, в сборочной системе в таком виде
они будут понятнее.  Сейчас, когда сборочная система обнаруживает
неудволетворенную зависимость libfoo.so.0 >= set:bMxyz, то не понятно,
сменился ли soname, или же, напротив, не хватает символов.)

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

/** \ingroup rpmds
 * Compare two versioned dependency ranges, looking for overlap.
 * @param A		1st dependency
 * @param B		2nd dependency
 * @return		1 if dependencies overlap, 0 otherwise
 */
int rpmdsCompare(const rpmds A, const rpmds B);

Вину за интерфейс rpmdsCompare() оба апстрима делят пополам.  Джефф
неправильно назвал функцию: compare подразумевает "больше, меньше или
равно", а здесь функция возвращает 0 или 1 (1 - если зависимость
удовлетворена).  Но неверная аналогия со сравнением прилипает/пристает
и дальше направляет неверный ход мыслей: кажется, что сравнение должно
быть симметричным (т.е. давать такой же результат при перестановке
местами A и B).  И действительно, реализация функции rpmdsCompare
является симметричной относительно перестановки A и B, что приводит к
ошибке: Requires с версией удовлетворяется Provides без версии (я писал
об этом в прошлом письме).  Однако же rpmdsCompare вызывает функцию
rpmdsCompareEVR(); несмотря на свой симметричный прототип, эта функция
уже не является симметричной (что делает и функцию rpmdsCompare
несимметричной).  Вообще, и сама аналогия "перекрытия диапазонов"
(overlap) является неверной.  Перекрытие симметрично, а разрешение
Requires относительно Provides несимметрично!  Почему?  Потому что
версии структурированы более сложно, они могут иметь или не иметь
релиза; релиз привносит понятие специфичности, которое разрушает
симметрию.  Казалось бы, почему бы не экспортировать какой-нибудь
интерфейс в терминах предметной области, а не ложных аналогий?
Например:

// Try to satisfy R with P.
bool rpmSatisfy(const char *R, int flagsR, const char *P, int flagsP);

Но нет, людям очень нравятся математические аналогии.  Так оно как-то
ближе к идеальным платоновским сущностям.  С таким же успехом солнце
можно объявить додекаэдром, и обсуждать применительно к солнцу группы
вращения додекаэдра!  А почему бы солнце могло быть додекаэдром?  Ну,
читайте Тимея, может поймете.  Это отсекает большую часть оппонентов,
хотя абсурдность утверждения от этого никак не меняется.

Вторая часть вины лежит на Пану М., на большом специалисте по структурам
данных, который не знает, какого цвета учебник.  Он изобрел rpmstrPool -
структуру данных, которая вроде пытается экономить память за счет
плотной упаковки строк, но в реальности она делает глупости (вроде
хеширования строк one-at-a-time, по одному байту на итерацию),
что приводит к неимоверному пожиранию процессора.  Может, это и работает
ничего на коротких версиях типа "1.0-alt1", но на set-версиях
прожорливость сразу набегает секундами.  В общем, основное правило для
тех, кто хочет использовать эти интерфейсы: стараться по максимуму
вообще не трогать rpmds и rpmstrPool.  Кстати, я видел, что в апте Глеб
с Легионом сделали один глобальный пул, чтобы не создавать пул при
каждой проверке зависимостей.  Секунд так набегает меньше, но в
результате в пуле хранятся все сравниваемые строки.  Т.е. "apt-cache
unmet" впустую жрет примерно на 20 Мб больше памяти, чем мог бы.

Интересно, что в реализации pkglist-unmet мне удалось проторить, как это
говорится, to tread the middle path: по максимуму избегать rpmds и
rpmstrPool, а иначе создавать пулы не слишком часто, и в то же время
накапливать в них строк не слишком много.

В общем, когда я пишу, что rpm является наслоением глупостей, причем
новый rpm - в большей степени, чем старый, то это не является
преувеличением: всё это вживую вас мучает при написании и профилировании
кода.  Отпрофилировав код первые несколько раз, я вспомнил бессмертную
цитату из Бивиса и Баттхеда: "This sucks more than anything that has
ever sucked before."  Таковы апстримы rpm.

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