[devel] packagereq/buildreq proposal

[devel] packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1.1: Type: text/plain, Size: 4551 bytes --]

Greetings!

Дано: имеется список пакетов, полученный packagereq, БЕЗ учета текущей
оптимизации.  Список пакетов вычисляется на основе вывода strace и
получается очень большим.  Некоторая часть этого списка не содержит
полезной информации.  Задача: оптимизировать список пакетов.

Анализ текущего алгоритма оптимизации: если в списке есть пакеты с
названиями %name и %name-foo, то пакет %name удаляется из списка.
Если в списке есть пакеты с названиями lib%name и %name, то пакет
lib%name удаляется из списка.  Удаляются также все пакеты из списка
essential.

Недостатки текущего алгоритма: алгоритм не учитывает зависимости между
пакетами.  В результате 1) список пакетов остается перегруженным; 2)
алгоритм делает ошибки, если структура зависимостей не соответствует
описанным допущениям.

Примеры, которые демонстрируют недостатоки алгоритма:

$ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql perl-DBD-mysql libMySQL` &>/dev/null ||:'
packagereq: building requires list: libMySQL perl-DBD-mysql
libMySQL perl-DBD-mysql
$

Сейчас в сизифе есть два пакета с libmysqlclient.so.  perl-DBD-mysql
собран с одной из этих библиотек.  Впоследствии он может быть пересобран
с другой.  Зависимость в третьем пакете на libMySQL не нужна.

$ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql libpcre-devel libpcre` &>/dev/null ||:'
packagereq: building requires list: libpcre-devel libpcre-devel
$

Пакеты libpcre-devel и libpcre, увы, между собой не связаны.

Пример с пакетам ruby, который приводит к тому, что в минимальной
сборочной среде ruby отсутствует, я уже приводил.


Определения.

Прямая зависимость между пакетами: пакет A напрямую зависит от пакета B,
если на уровне RPM существует зависимость следующего типа:

%package -n A
Requires: B

Пример прямой зависимости:
$ rpm -q --requires libpcre-devel | grep pcre
libpcre3 = 4.4-alt1
$

Пакет pcre-devel напрямую зависит от libpcre3.


Прямая зависимость через виртуальный пакет: пакет A зависит от пакета B
через виртуальный пакет, если на уровне RPM существует зависимость
следующего типа:

%package -n A
Requires: package_B

%package -n B
Provides: package_B

Пример зависимости через виртуальный пакет:

$ rpm -q --requires perl-DBD-mysql | grep mysqlclient
libmysqlclient.so.12
$ rpm -q --whatprovides libmysqlclient.so.12
libMySQL-4.0.15-alt2
$

Пакет perl-DBD-mysql зависит от пакета libMySQL через виртуальный пакет
libmysqlclient.so.12.


Косвенная зависимость: любые зависимости с более сложной структурой не
рассматриваются.


Алгоритм оптимизации: из списка по очереди выбирается пакет-кандидат на
удаление.  Если какой-либо пакет из оставшейся части списка зависит от
кандидата напрямую или через виртуальный пакет, кандидат удаляется.
Выполнение алгоритма продолжается на оставшемся списке.


Преимущества алгоритма: алгоритм лишен недостатков текущего алгоритма.

Недостаток алгоритма: результат зависит от порядка пакетов в списке.
Пример:

BuildRequires: XFree86-libs XFree86-devel XFree86-devel-static
		^-------------'     ^----------------'
Пакеты XFree86-libs и XFree86-devel будут по очереди удалены.

BuildRequires: XFree86-devel XFree86-devel-static XFree86-libs
			`----------------------------^
		^---------------------'
Первым будет удален пакет XFree86-devel; информация о том, что он
непосредственно зависит от XFree86-libs, будет потеряна.

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

Недостаток алгоритма: алгоритм не работает с виртуальными пакетами
(которые packagereq подставляет в соответствии с правилами
/etc/buildreqs/packages/substitute.d).  Обсуждение на канале привело
меня к мысли, что семантика виртуальных пакетов, которые предоставляются
несколькими другими пакетами, определена недостаточно хорошо.  Нужно
сформулировать правила использования виртуальных пакетов.

Прототип реализации прилагается.
Примеры работы прототипа:

$ perl rpm.pl libMySQL perl-DBD-mysql
        perl-DBD-mysql requires libMySQL through libmysqlclient.so.12
                libMySQL optimized out
perl-DBD-mysql

$ perl rpm.pl libpcre3 libpcre libpcre-devel
        libpcre-devel requires libpcre3
                libpcre3 optimized out
libpcre libpcre-devel

$ perl rpm.pl XFree86-libs XFree86-devel XFree86-devel-static
        XFree86-devel requires XFree86-libs through libX11.so.6
                XFree86-libs optimized out
        XFree86-devel-static requires XFree86-devel
                XFree86-devel optimized out
XFree86-devel-static


[-- Attachment #1.2: rpm.pl --]
[-- Type: text/plain, Size: 1364 bytes --]

#!/usr/bin/perl

use RPM::Database;
use strict;

my $db = RPM::Database->new;
my %DB;

# load Requires: and Provides: from RPM database for the given packages
foreach my $pkg (@ARGV) {
	my $hdr = $$db{$pkg};
	unless ($hdr) {
		warn "package $pkg not found\n";
		next;
	}
	my $requires = $$hdr{REQUIRENAME};
	if ($requires) {
		$DB{$pkg}{req} = $requires;
	} else {
		warn "package $pkg requires nothing\n";
		$DB{$pkg}{req} = [];
	}
	my $provides = $$hdr{PROVIDES};
	if ($provides) {
		$DB{$pkg}{prov} = $provides;
	} else {
		warn "package $pkg provides nothing\n";
		$DB{$pkg}{prov} = [];
	}
}

use sort 'stable';
# try to optimize out packages with shortest names first
# alphabetical order is also in effect
my @packages = sort { length($a) <=> length($b) } sort keys %DB;

try: while (1) {
	foreach my $pkg (@packages) {
		my @rest = grep { $_ ne $pkg } @packages;
		if (my ($who, $what) = implies($pkg, @rest)) {
			warn "\t$who requires $pkg" . 
				($what eq $pkg ? "\n" : " through $what\n");
			warn "\t\t$pkg optimized out\n";
			@packages = @rest;
			next try;
		}
	}
	last;
}

@packages = sort @packages;
print "@packages\n";

sub implies {
	my ($pkg, @others) = @_;
	foreach my $prov (@{$DB{$pkg}{prov}}) {
		foreach my $who (@others) {
			foreach my $req (@{$DB{$who}{req}}) {
				return ($who, $req)
					if ($req eq $prov);
			}
		}
	}
	return;
}

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 411 bytes --]

On Sun, Nov 16, 2003 at 05:58:30PM +0300, Alexey Tourbin wrote:
> $ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql libpcre-devel libpcre` &>/dev/null ||:'
> packagereq: building requires list: libpcre-devel libpcre-devel
> $

Ошибка.  Следует читать:

$ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql libpcre-devel libpcre` &>/dev/null ||:'
packagereq: building requires list: libpcre-devel
libpcre-devel
$

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] packagereq/buildreq proposal

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 1029 bytes --]

On Sun, Nov 16, 2003 at 05:58:30PM +0300, Alexey Tourbin wrote:
[...]
> Примеры, которые демонстрируют недостатоки алгоритма:
> 
> $ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql perl-DBD-mysql libMySQL` &>/dev/null ||:'
> packagereq: building requires list: libMySQL perl-DBD-mysql
> libMySQL perl-DBD-mysql
> $
> 
> Сейчас в сизифе есть два пакета с libmysqlclient.so.  perl-DBD-mysql
> собран с одной из этих библиотек.  Впоследствии он может быть пересобран
> с другой.  Зависимость в третьем пакете на libMySQL не нужна.
> 
> $ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql libpcre-devel libpcre` &>/dev/null ||:'
> packagereq: building requires list: libpcre-devel libpcre-devel
> $
> 
> Пакеты libpcre-devel и libpcre, увы, между собой не связаны.

Я бы для начала включил в /etc/buildreqs/packages/essential
lib[^-]+ -- т.е. исключил бы все имена пакетов, удовлетворяющих шаблону
^lib[^-]+$

Обоснование: динамические библиотеки не бывают нужны сами по себе; всегда
найдется пакет, который от них зависит.


--
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 792 bytes --]

On Sun, Nov 16, 2003 at 06:54:30PM +0300, Dmitry V. Levin wrote:
> Я бы для начала включил в /etc/buildreqs/packages/essential
> lib[^-]+ -- т.е. исключил бы все имена пакетов, удовлетворяющих шаблону
> ^lib[^-]+$
> 
> Обоснование: динамические библиотеки не бывают нужны сами по себе; всегда
> найдется пакет, который от них зависит.

Это дальнейшее усугубление допущений, которые не всегда выполняются.
А результат работы правильного алгоритма как раз может показать, где они
не выполняются.  Более того, правильный алгоритм (более правильный, чем
описанный на данный момент: т.е. который будет правильно работать с
виртуальными пакетами) может сделать список essential практически не
нужным: достаточно будет "подрезать" rpm-build, а всё остальное, что
требует rpm-build, само "осыпется".

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Michael Shigorin]

[-- Attachment #1: Type: text/plain, Size: 882 bytes --]

On Sun, Nov 16, 2003 at 05:58:30PM +0300, Alexey Tourbin wrote:
> Недостаток алгоритма: результат зависит от порядка пакетов в списке.
> Пример:
> 
> BuildRequires: XFree86-libs XFree86-devel XFree86-devel-static
> 		^-------------'     ^----------------'
> Пакеты XFree86-libs и XFree86-devel будут по очереди удалены.
> 
> BuildRequires: XFree86-devel XFree86-devel-static XFree86-libs
> 			`----------------------------^
> 		^---------------------'
> Первым будет удален пакет XFree86-devel; информация о том, что он
> непосредственно зависит от XFree86-libs, будет потеряна.
> 
> Над решением этой проблемы в общем виде я не думал.  В данном частном
> случае, как и в некоторых других, достаточно отсортировать список по
> возрастанию длины названия пакета.

Отложенное удаление?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 673 bytes --]

On Mon, Nov 17, 2003 at 10:46:02AM +0200, Michael Shigorin wrote:
> > Над решением этой проблемы в общем виде я не думал.  В данном частном
> > случае, как и в некоторых других, достаточно отсортировать список по
> > возрастанию длины названия пакета.
> 
> Отложенное удаление?

Рассмотрим два пакета, которые взаимно зависят друг от друга.
Что в таком случае есть отложенное удаление?  Если отложено удалить
первый пакет, потому что от него зависит второй, а потом второй, потому
что от него зависит первый, то мы удалим два и потеряем зависимости.

Короче, для решения в общем виде нужно изучать математику в районе
деревьев и графов.  У кого-нибудь есть хорошая книжка?

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] Re: packagereq/buildreq proposal

[vserge]

Добрый день

Вы написали Alexey Tourbin <at@altlinux.ru> Mon, 17 Nov 2003 14:42:22 +0300:

> On Mon, Nov 17, 2003 at 10:46:02AM +0200, Michael Shigorin wrote:
> > > Над решением этой проблемы в общем виде я не думал.  В данном частном
> > > случае, как и в некоторых других, достаточно отсортировать список по
> > > возрастанию длины названия пакета.
> > 
> > Отложенное удаление?
> 
> Рассмотрим два пакета, которые взаимно зависят друг от друга.
> Что в таком случае есть отложенное удаление?  Если отложено удалить
> первый пакет, потому что от него зависит второй, а потом второй, потому
> что от него зависит первый, то мы удалим два и потеряем зависимости.
> 
> Короче, для решения в общем виде нужно изучать математику в районе
> деревьев и графов.  У кого-нибудь есть хорошая книжка?
> 

А что именно нужно, есть книга Кнут, Алгоритмы (не помню авторов, это
перевод кажется какого-то американского университета).

Этов москве могу предоставить,

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 355 bytes --]

On Mon, Nov 17, 2003 at 03:09:58PM +0300, vserge wrote:
> А что именно нужно, есть книга Кнут, Алгоритмы (не помню авторов, это
> перевод кажется какого-то американского университета).

Не знаю точно, что нужно.  Время нужно. :)  Что-нибудь научно-популярное
про графы с примерами программирования.  Кнут есть.

> Этов москве могу предоставить,

Спасибо.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] Re: packagereq/buildreq proposal

[Sergey Bolshakov]

>>>>> "Alexey" == Alexey Tourbin <at@altlinux.ru> writes:

 > On Mon, Nov 17, 2003 at 03:09:58PM +0300, vserge wrote:
 >> А что именно нужно, есть книга Кнут, Алгоритмы (не помню авторов, это
 >> перевод кажется какого-то американского университета).

 > Не знаю точно, что нужно.  Время нужно. :)  Что-нибудь научно-популярное
 > про графы с примерами программирования.  Кнут есть.

Взглянуть на пакет goblin при случае было бы полезно, мне кажется.

-- 

Re: [devel] Re: packagereq/buildreq proposal

[Marat Khairullin]

On Mon, 17 Nov 2003 15:12:29 +0300
Alexey Tourbin <at@altlinux.ru> wrote:

> On Mon, Nov 17, 2003 at 03:09:58PM +0300, vserge wrote:
> > А что именно нужно, есть книга Кнут, Алгоритмы (не помню авторов, это
> > перевод кажется какого-то американского университета).
> 
> Не знаю точно, что нужно.  Время нужно. :)  Что-нибудь научно-популярное
> про графы с примерами программирования.  Кнут есть.
> 
Любая книга по дискретной математике (приличного объема)
содержит раздел по графам.

PS: Был у меня когда-то опыт работы с графами, когда портировал
библиотеку TurboVision на Unix :). ar тогда не позволял создавать
большие либы - пришлось делить с учетом зависимостей на две части...

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 570 bytes --]

On Sun, Nov 16, 2003 at 05:58:30PM +0300, Alexey Tourbin wrote:
> Недостатки текущего алгоритма: алгоритм не учитывает зависимости между
> пакетами.  В результате 1) список пакетов остается перегруженным; 2)
> алгоритм делает ошибки, если структура зависимостей не соответствует
> описанным допущениям.

Увы, мое предложение было проигнорировано.

$ rpm -q --lastchange rpm-utils
* Wed Dec 10 2003 Dmitry V. Levin <ldv@> 0.7.4-alt1
- compare_packages:
  + better support for packages with devices.
- essential:
  + removed: all lib* records;
  + added: lib[^-]+ record.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Michael Shigorin]

[-- Attachment #1: Type: text/plain, Size: 249 bytes --]

On Mon, Dec 15, 2003 at 10:37:38PM +0300, Alexey Tourbin wrote:
> > Недостатки текущего алгоритма
> Увы, мое предложение было проигнорировано.

Молча?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] Re: packagereq/buildreq proposal

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 536 bytes --]

On Mon, Dec 15, 2003 at 10:37:38PM +0300, Alexey Tourbin wrote:
> On Sun, Nov 16, 2003 at 05:58:30PM +0300, Alexey Tourbin wrote:
> > Недостатки текущего алгоритма: алгоритм не учитывает зависимости между
> > пакетами.  В результате 1) список пакетов остается перегруженным; 2)
> > алгоритм делает ошибки, если структура зависимостей не соответствует
> > описанным допущениям.
> 
> Увы, мое предложение было проигнорировано.

Боюсь, что твое предложение никто кроме тебя не тестировал. :(

P.S. bugzillу никто ещё не отменял.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[devel] Re: packagereq/buildreq proposal

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 298 bytes --]

On Tue, Dec 16, 2003 at 01:09:46PM +0300, Dmitry V. Levin wrote:
> > Увы, мое предложение было проигнорировано.
> 
> Боюсь, что твое предложение никто кроме тебя не тестировал. :(

Предложение не тестируют, его обсуждают (или не обсуждают).

> P.S. bugzillу никто ещё не отменял.
> 
> 
> -- 
> ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]