[prev in list] [next in list] [prev in thread] [next in thread] 

List:       rpm-devel
Subject:    Integrated dep-solver in rpm5 via SAT.
From:       Jeff Johnson <n3npq () mac ! com>
Date:       2009-01-12 13:35:05
Message-ID: 0CF04DCF-5F7E-4F6F-9C2E-32FF2B13E0EF () mac ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]


On Jan 9, 2009, at 12:17 PM, Jeff Johnson wrote:

>
> On Jan 9, 2009, at 11:05 AM, devzero2000 wrote:
>
>>
>> But a rpmbuild rewrite seems to be my current RPM goal because  
>> YAMLspec!
>> is the only roadmap item @rpm5.org I'm hearing consensus about.
>>
>>
>> Off topic.
>>
>> Am i the only who  like the initial development of a dep-solver in  
>> rpm5 via sat-solver ?
>>
>
> No, having an "integrated depsolver" is still on the @rpm5.org  
> ROADMAP, and
> these days, that also means accommodating a SAT engine as an  
> assertion checker.
>
> I can send privately the description of the "integrated depsolver"  
> that
> is already in place in RPM for many years from when the RPM-5.0  
> ROADMAP
> was formulated.
>

Just in case anyone else is interested, and so that I have a public  
reference,
attached is/was the document describing the "integrated depsolver"  
within
RPM 5.0.

Merging rpmcache into rpmrepo to establish a client-side store of  
"everything"
metadata is likely the next step. Not hard, just not gotten there yet,  
other issues
keep popping up, like day job priorities and necessities.

I can write up additional RPM development details about Mancoosi CUDF  
format and the
SuSE zypp SAT solver aspects of depsolving anytime someone wishes.

Enjoy!

73 de Jeff

[Attachment #5 (multipart/mixed)]

[Attachment #7 (text/html)]

<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; \
-webkit-line-break: after-white-space; "><br><div><div>On Jan 9, 2009, at 12:17 PM, \
Jeff Johnson wrote:</div><br class="Apple-interchange-newline"><blockquote \
type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; \
-webkit-line-break: after-white-space; "><br><div><div>On Jan 9, 2009, at 11:05 AM, \
devzero2000 wrote:</div><br class="Apple-interchange-newline"><blockquote \
type="cite"><div class="gmail_quote"><blockquote class="gmail_quote" \
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; \
padding-left: 1ex;"><br> But a rpmbuild rewrite seems to be my current RPM goal \
because YAMLspec!<br> is the only roadmap item @<a href="http://rpm5.org" \
target="_blank">rpm5.org</a> I'm hearing consensus about.<br> \
</blockquote><div><br><br>Off topic. <br><br>Am i the only who&nbsp; like the initial \
development of a dep-solver in rpm5 via sat-solver \
?<br><br></div></div></blockquote><br></div><div>No, having an "integrated depsolver" \
is still on the @rpm5.org ROADMAP, and</div><div>these days, that also means \
accommodating a SAT engine as an assertion checker.</div><div><br></div><div>I can \
send privately the description of the "integrated depsolver" that</div><div>is \
already in place in RPM for many years from when the RPM-5.0 ROADMAP</div><div>was \
formulated.</div><div><br></div></div></blockquote><br></div><div>Just in case anyone \
else is interested, and so that I have a public reference,</div><div>attached is/was \
the document describing the "integrated depsolver" within</div><div>RPM \
5.0.</div><div><br></div><div>Merging rpmcache into rpmrepo to establish a \
client-side store of "everything"</div><div>metadata is likely the next step. Not \
hard, just not gotten there yet, other issues</div><div>keep popping up, like day job \
priorities and necessities.</div><div><br></div><div>I can write up additional RPM \
development details about Mancoosi CUDF format and the</div><div>SuSE zypp SAT solver \
aspects of depsolving anytime someone \
wishes.</div><div><br></div><div>Enjoy!</div><div><br></div><div>73 de \
Jeff</div><div></div></body></html>


["depsolver" (depsolver)]

Here are some thoughts, likely random, on adding a depsolver for rpm-5.0
delivery.

rpm already has most of the components for a depsolver hidden under 
the --aid CLI option. The two important heuristics for a depsolver are
    1) discovery of what package satisifes a missing dependency
    2) upgrading already installed packages based on conlicts/obsoletes hints.

The current implementation in rpmlib does 1) well and 2) not at all.

A depsolver itself is just a basic goal seeking recursion, as in
    Add packages to a transaction until all dependencies are satisfied.

There's a slew of policy heuristics that have been added over the years
to assist in choosing packages that I will skip over lightly. None
of the heuristics are very hard to implement, they are mostly arch prefernces,
or classification of subsets for special handling like
    Provides: kernel-modules
that will all be needed for rpm-5.0. All I wish to describe here is
the not very well understood depsolver implementation currently in rpm.

The depsolver mechanism within rpmlib uses a callback to a helper routine
whenever a unsatisfied dependency is encountered.

The current rpm cli helper is rpmtsSolve() in lib/rpmts.c with these arguments:

/**
 * Attempt to solve a needed dependency using the solve database.
 * @param ts            transaction set
 * @param ds            dependency set
 * @param data          opaque data associated with callback
 * @return              -1 retry, 0 ignore, 1 not found
 */
/*@-exportlocal@*/
int rpmtsSolve(rpmts ts, rpmds ds, const void * data)
        /*@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/
        /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/;
/*@=exportlocal@*/

The passed dependency set iterator is positioned at an unsatisfied dependency
and the helper routine is responsible for finding the package that will satisfy
the dependency, usually loading a header and adding the new header to the
current transaction set, and finally resuming the pursuit of the goal,
i.e. dependency closure for the current transaction.

Note the helper routine returns that determine how dependency checking
is to be resumed.

The current proof-of-concept dependency solver uses a 2nd rpmdb that
contains all possible headers and 3 macros to build a path to the
package that will be added to a transaction set:

#       The path to the dependency universe database. The default value
#       is the rpmdb-vendor location. The macro is usually defined in
#       /etc/rpm/macros.solve, installed with the rpmdb-vendor package.
%_solve_dbpath  /var/lib/solvedb

#       The path to the dependency universe packages. This should
#       be a path to the packages contained in the solve database.
%_solve_pkgsdir /var/cache/yum/development/packages/

#       The output binary package file name template used when suggesting
#       binary packages that solve a dependency. The macro is usually defined
#       in /etc/rpm/macros.solve, installed with the rpmdb-vendor package.
#
# XXX   Note: escaped %% for use in headerSprintf()
%_solve_name_fmt        %{?_solve_pkgsdir}%%{NAME}-%%{VERSION}-%%{RELEASE}.%%{ARCH}.rpm

The mechanism is quite general imho, and I believe can support other sources
for discovery of packages than an rpmdb rather easily. The major flaw
is that a package header is needed in order to be added to a transaction set
using the currently supported API:

/** \ingroup rpmts
 * Add package to be installed to transaction set.
 *
 * The transaction set is checked for duplicate package names.
 * If found, the package with the "newest" EVR will be replaced.
 *
 * @param ts            transaction set
 * @param h             header
 * @param key           package retrieval key (e.g. file name)
 * @param upgrade       is package being upgraded?
 * @param relocs        package file relocations
 * @return              0 on success, 1 on I/O error, 2 needs capabilities
 */
int rpmtsAddInstallElement(rpmts ts, Header h,
                /*@exposed@*/ /*@null@*/ const fnpyKey key, int upgrade,
                /*@null@*/ rpmRelocation relocs)
        /*@globals rpmcliPackagesTotal, rpmGlobalMacroContext, h_errno,
                fileSystem, internalState @*/
        /*@modifies ts, h, rpmcliPackagesTotal, rpmGlobalMacroContext,
                fileSystem, internalState @*/;

But there is also no reason why a transaction element can't be generated
directly without a header from, say, rpm-metadata XML. A transaction element
(aka "package") is essentially several types of dependency sets (think:
Requires: Provides: Obsoletes: Conflicts: etc) as well as a file info set
and nothing else.

Any means to populate those data structures can be used by the helper routine
before resuming the dependency closure goal. Reading package headers from a
database, parsing xml, whatever the helper wishes to do.

I believe the major architectural flaw with yum (and to some extent other
depsolvers) is that the store-and-forward download phase for distributing
the set of possible resolutions is synchronous with the depsolving.

All that means is that every yum execution should not need to go look
to see if the metadata changed, and download new metadata if available.
No computer system needs to be *THAT* up2date.

But because yum (and to some extent other depsolvers) are continuously
hitting mirrors and servers, and spending lots of time downloading,
bandwidth becomes an artificially important issue because a human
being is watching progress bars, etc etc.

And so a lot of complexity has been added (unnecessarily imho) to depsolver's
with delta rpm's, sqlite db's and xml markup when the real solution is
to maintain a representation -- be it a file tree of headers, a database, or
xml markup -- of "everything" on client machines.

The transport of the "everything" representation is easily solved
in any number of ways -- cron, rdist, incremental db updates, file tree copies,
etc -- while the depsolver mechanism I outlined above is adequate modulo the
necessity of having a helper routine that understands the representation of
"everything" and the current rpmlib API need to have a header in order to
add a new package to the current transaction.

In summary, here's what needs doing for a rpmlib depsolver in rpm 5.0:

1) Choose one or more representations of "everything".
    An rpmdb (with incremental nightly update) is one useful representation.
    Importing rpm-metadata is another useful representation.
    The sqlite db's that yum may currently use is perhaps a 3rd representation.
    The Packages.gz file used by apt may be a 4th representation.
    I can think of several other candidates. The only need is that the
    representation is "everything" and contains sufficient information
    to populate a transaction element.

2) Write a helper for each of the "everything" representations.
    The rpmdb "everything" helper is already in rpmlib.
    I have written rpm-metadata xml parsers, and yaml parsers, can/will
    write additional parsers as needed.

3) Write drivers to test the components and the rpmlib depsolver mechanism.


[Attachment #9 (text/html)]

<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; \
-webkit-line-break: after-white-space; "><div></div></body></html>


["smime.p7s" (smime.p7s)]

0	*H
 010	+0	*H
 00 rk 0
	*H
0|10	UDE10U
TC TrustCenter GmbH1%0#UTC TrustCenter Class 1 L1 CA1(0&UTC TrustCenter \
Class 1 L1 CA VI0 081202135405Z
091203135405Z0B10	UUS10UJeff Johnson10	*H
	
n3npq@mac.com0"0
	*H
0
Ҭ14B~:*;˄rx%I"^~22Wń9i,#O))~SC	` \
˨ŕ1i!~I5S)R&Ϥ(tuIAЈTOb߁>fN*5Q<1Rn&,f`iR!S~WUzsB \
SNg>Ox>ɐ{FMк00+00Q+0Eh \
ttp://www.trustcenter.de/certservices/cacerts/tc_class1_L1_CA_VI.crt02+0&http \
://ocsp.VI.tcclass1.trustcenter.de0U#0NjkJɻdK&0U00JU \
C0A0?	*,0200+$http://www.trustcenter.de/guidelines0U0UDL荺e9=7N&d?0TUM0K0I \
G EChttp://crl.VI.tcclass1.trustcenter.de/crl/v2/tc_class1_L1_CA_VI.crl03U%,0*+++
 +70U0
n3npq@mac.com0
	*H
c3#5@+Nwc<~3mJ \
2݉}dsOM3/cCåt(:ӌmxH#F?&N^?6c"*-7lu`+x|W \
ʕnbgҮV4H008 bnrd0 	*H
010	UDE10UHamburg10UHamburg1:08U
1TC TrustCenter for Security in Data Networks GmbH1"0 UTC TrustCenter Class 1 \
CA1)0'	*H 	certificate@trustcenter.de0
080718113854Z
101231225959Z0|10	UDE10U
TC TrustCenter GmbH1%0#UTC TrustCenter Class 1 L1 CA1(0&UTC TrustCenter \
Class 1 L1 CA VI00 	*H
0?N~ݤ㰾(ݙuLαlK%8H
~uH@MNCm]9Xq
K1~_݄Vfk(ѢzaW00'
@00+00L+0@http://www.trustcenter.de/certservices/ \
cacerts/tc_class_1_ca.crt0/+0#http://ocsp.tcclass1.trustcenter.de0U00JU \
C0A0?	*,0200+$http://www.trustcenter.de/guidelines0U0UNjkJɻdK&0U00 \
 ؆;http://crl.tcclass1.trustcenter.de/crl/v2/tc_class_1_ca.crlldap://www.trustc \
enter.de/CN=TC%20TrustCenter%20Class%201%20CA,O=TC%20TrustCenter%20AG,ou=rootcerts,dc=trustcenter,dc=de?certificateRevocationList?base?0
 	*H
ng,<H[<KB*8ُ˰y}e-pT-):mnzq/eJ̄tZմw"D˴W\&8kT.WƎ|W[30(0 \
0 	*H
0y10U
Root CA10Uhttp://www.cacert.org1"0 UCA Cert Signing \
Authority1!0	*H 	support@cacert.org0
070806160927Z
090805160927Z0810UCAcert WoT User10	*H
	
n3npq@mac.com0"0
	*H
0
MǼ~arqC?j(Ѝ.=
ܐ[m47囵{Hǰmgk׼=FlFَ^ \
c9hٕ/,fOcY;ik"XFS	)֟W:Z#AqW:_rIqc&ZZAKBH
 oY_x(V!zd	AHDJAdG*QXVr:tpM00U00V	`HB
 IGTo get your own certificate for FREE head over to \
http://www.CAcert.org0@U%907++ +7

+7
	`HB02+&0$0"+0http://ocsp.cacert.org0U0
n3npq@mac.com0
	*H
BmC2G$+`?kdC
o߫'iƬ'9\q459xOS@B= \
49ێ0أZ-n!Hrλy)gPmcFkrzGr1d3)g"LZ\bkR&h@[%|%@ht'?Нc]y4J


m
!ϵ[4QB}bK_gD,	?
wG:U\XC\!}i)7%7ufmW]-x|̭QćHxNF%3z3rR>~c͛y2GL<n#K/
  (_Q7nfrCejT \
q$,76ICm@C@)H4{\ZX̢T@niQjcN'.i. +(a
=F(>O1B0>00|10	UDE10U
TC TrustCenter GmbH1%0#UTC TrustCenter Class 1 L1 CA1(0&UTC TrustCenter \
Class 1 L1 CA VIrk 0	+ 0	*H 	1	*H
0	*H
	1
090112133506Z0#	*H
	1G|r߸Fu)A#0	+7100y10U
Root CA10Uhttp://www.cacert.org1"0 UCA Cert Signing \
Authority1!0	*H 	support@cacert.org0*H
	1 0y10U
Root CA10Uhttp://www.cacert.org1"0 UCA Cert Signing \
Authority1!0	*H 	support@cacert.org0
	*H
P1XmDrpG+R	C:f5PN4؏ЖmP]@mvp	DKla73A"
 _ʹ_]e"o^W|Y]
L\=CYT^L}'ܕ_īu	
>DDtƅ`Pxq^'D5Y/}̉T'%(FFDR3c:v&	)Ta):r< \
Vl;rmH


______________________________________________________________________
RPM Package Manager                                    http://rpm5.org
Developer Communication List                        rpm-devel@rpm5.org

[prev in list] [next in list] [prev in thread] [next in thread]

Configure | About | News | Add a list | Sponsored by KoreLogic