Project

Profile

Help

Task #3528

Investigate which library to use for dep solving

Added by ttereshc over 2 years ago. Updated 6 months ago.

Status:
CLOSED - COMPLETE
Priority:
Normal
Assignee:
Sprint/Milestone:
-
Start date:
Due date:
% Done:

0%

Estimated time:
Platform Release:
Groomed:
Yes
Sprint Candidate:
Yes
Tags:
Pulp 2
Sprint:
Sprint 38
Quarter:

Description

Current implementation of a dep solving supports only strong (Requires:) simple (package_name) dependencies.
In order to support strong (Requires:) rich (aka boolean) dependencies an external library should be used.
The suggestion is to drop the current implementation of dep solving and for any kind of a dep solving start using:
- either libdnf via its Python interface (python2-dnf)
- or libsolv via its Python bindings (python2-solv)

libdnf uses libsolv and exposes a higher level API to a user.

Both libdnf and libsolv requires repodata to perform dep solving.
Some temporary working directory should be provided to a solver to store its cache there.

Functionality of a solver we are looking for:

  • list dependencies for a given rpm package (can be a part of a synchronous task)
  • list fulfilled dependencies (from a given list of available packages) for a given rpm package
  • validate that all the dependencies (from a given list of available packages) for a given rpm package are fulfilled.
  • perform dep solving against multiple repositories

The actions mentioned above will be a part of an asynchronous task (see a copy example below).

An example of the dep solving use case in Pulp is a recursive flag during a copy: https://docs.pulpproject.org/plugins/pulp_rpm/user-guide/recipes.html?highlight=recursive#copy-errata-from-one-repository-to-another
Dep solving related functionality to support: https://pulp.plan.io/issues/2478

Example usage of the libsolv Python bindings: https://github.com/fedora-modularity/depchase
Ping ttereshc for more details about examples for libdnf case.

Figure out which library supports all required functionality. Keep in mind that performance is important as well. There could be repositories with 100K+ packages against which dep solving can be requested.


Related issues

Related to RPM Support - Issue #4152: Regression Pulp 2.17.1: recursive copy of RPMs does not copy partially resolvable dependenciesCLOSED - CURRENTRELEASE<a title="Actions" class="icon-only icon-actions js-contextmenu" href="#">Actions</a>

History

#1 Updated by ttereshc over 2 years ago

  • Description updated (diff)

#2 Updated by ttereshc over 2 years ago

  • Description updated (diff)

#3 Updated by dkliban@redhat.com over 2 years ago

  • Groomed changed from No to Yes
  • Sprint Candidate changed from No to Yes

#4 Updated by milan over 2 years ago

  • Status changed from NEW to ASSIGNED
  • Assignee set to milan

#5 Updated by daviddavis over 2 years ago

  • Sprint set to Sprint 35

#6 Updated by rchan over 2 years ago

  • Sprint changed from Sprint 35 to Sprint 36

#7 Updated by milan over 2 years ago

I'd like to propose using libsolv directly rather than thru libdnf, with the following reasoning

  • libdnf is exposing just the hawkey API which in turn supports loading repository data only thru reading the repo metadata
  • Pulp would have to dump the MongoDB records into XML metadata, consumable by libdnf, to update its pool.repo data while at the same time, updating pool.repo data with libsolv can be done directly and iteratively
  • a selective, recursive copy of a unit needs checking what unit.requires are missing from the target repository (being built)
  • this implies building the solver target data pool.repo on the fly, updating the pool record of each unit of the target repository
  • the solver might need to perform couple of iterations to support copying of mutually-conflicting packages into the same target repository
  • therefore a low-level interaction with the solver seems a better fit
  • libdnf is an RPM-specific implementation that would limit reuse e.g in the Debian plugin
  • libdnf might bring in more features than necessary, Pulp has a narrowed-down set of usecases for which it needs fine-grain control (see Comment 10)
  • libdnf is a work-in-progress

Pulp depending on libdnf would also mean having to synchronize another project's release cycle

On the other hand, there's the open question of supporting depsolving for Modularity, which doesn't seem to be the case in either of the libraries but libdnf seems to have some minimal support PR posted

#8 Updated by milan over 2 years ago

Problem statement

Given source and target repositories, solve what dependencies copying a unit from the source to the target repo induces:

+------------------------------------------+
| MONGO                                    |
|                foo-1.1                   |
|                 - bar                    |
|  +--------+     - baz        +--------+  |
|  | Source |                  | Target |  |
|  |  repo  |  +------------>  |  repo  |  |
|  |        |                  |        |  |
|  +---+----+                  +----+---+  |
|      |                            |      |
+------------------------------------------+
       |                            |
       |                            |
       ^                            ^
+------+------+              +------+------+
| Solv Pool   |              | Solv Pool   |
|             |              |             |
| +---------+ |              | +---------+ |
| |repo:    | |              | |repo:    | |
| | foo,1.1 | |              | | bar,1.0 | |
| | bar,0.9 | |              | +---------+ |
| | baz,1.0 | |              |             |
| +---------+ |              +-------------+
|             |
+-------------+

Note please, the target repo already contains bar, newer than the source does.
In the context of https://pulp.plan.io/issues/2478 one would expect, if dependencies of foo allow it, the bar to be kept at the target version:

+------------------------------------------+
| MONGO                                    |
|                                          |
|                                          |
|  +--------+                  +--------+  |
|  | Source |                  | Target |  |
|  |  repo  |                  |  repo  |  |
|  |        |                  |        |  |
|  +---+----+                  +----+---+  |
|      |                            |      |
+------------------------------------------+
       |                            |
       |                            |
       ^                            ^
+------+------+              +------+------+
| Solv Pool   |              | Solv Pool   |
|             |              |             |
| +---------+ |              | +---------+ |
| |repo:    | |              | |repo:    | |
| | foo,1.1 | |              | | bar,1.0 | |
| | bar,0.9 | |              | | foo,1.1 | |
| | baz,1.0 | |              | | baz,1.0 | |
| +---------+ |              | +---------+ |
|             |              |             |
+-------------+              +-------------+

Proposed solution

The libsolv sat solver can be used to infer steps required to copy a unit; one can request libsolv to "install" foo.
Putting the target libsolv repo into the source libsolv pool allows one to solve an optimal repo transaction log, considering latest available units:

+------------------------------------------+
| MONGO                                    |
|                foo-1.1                   |
|  +--------+     - baz,1.0    +--------+  |
|  | Source |                  | Target |  |
|  |  repo  |  +------------>  |  repo  |  |
|  |        |                  |        |  |
|  +---+----+                  +----+---+  |
|      |                            |      |
+------------------------------------------+
       |                            |
       |                            |
       ^                            ^
+------+------+              +------+------+
| Solv Pool   |              | Solv Pool   |
|             |              |             |
| +---------+ |              | +---------+ |
| |repo:    | |              | |repo:    | |
| | foo,1.1 | |              | | bar,1.0 | |
| | bar,0.9 | |              | +----+----+ |
| | baz,1.0 | |              |      |      |
| +---------+ |              +-------------+
|             |                     |
| +---------+ |                     |
| |@System: | |                     |
| | bar,1.0 <-----------------------+
| +---------+ |
+-------------+

There might be cases when multiple packages with mutually-conflicting dependencies are being requested to be "installed" by the solver.
To address this, the solver can be configured with allow_uninstall flag to give a successful transaction in such a case; the uninstall transaction steps would be ignored.
Pulling-in weak dependencies can be configured similarly and setting repository priorities will allow more fine-grained control over the solving process.
It might make sense to expose all these configuration options to the user thru the REST API.

Implementation considerations

The pool.repo objects don't support sharing between pool objects; one actually has to copy the units between repos one by one.
This might take significant amount of time and might require some fine-grained state keeping around the pool objects, should the implementation decide to cache those on the disk.

For the same reason, the https://pulp.plan.io/issues/2478 behavior might be optional (exposed as another copy option thru the REST API) to save resources.

Furthermore the "smaller" repo would ideally be picked to be "copied" into a pool; since nothing is ever actually installed, the pool is just a context. Repository priorities would most likely have to be reversed in that case.

In unit dependency conflict cases, the solver might require multiple iterations to resolve the "install" jobs. The implementation should consider this possibility and evaluate the jobs in a stabilization fashion; any outstanding job requests would imply unit dependency bugs and some users might be interested in being able to see those.

Both the source and target repos will most likely have to be locked during the copy task run. Out of sync solver pools&repos might happen in case cached pools are being used and the copy task has been interrupted: there might be inconsistencies between Mongo and the solver pools.

#9 Updated by rchan over 2 years ago

  • Sprint changed from Sprint 36 to Sprint 37

#10 Updated by milan over 2 years ago

Thinking out loud about the requirements from the description section.... I think overall a sat solver isn't a good fit for what the requirements are; the main theme of a sat solver being to give a yes (no) answer with a (counter-)proof i.e steps how (not) to install a package, all the requirements here imply some adjusting of the solver for a task it wasn't really meant to be used for.

Functionality of a solver we are looking for:

list dependencies for a given rpm package (can be a part of a synchronous task)

A solver works in a context of all available packages --- a content pool. Considering the transitive nature of content unit dependencies, to give an answer, the solver has to work in the context of all available packages from all relevant repos. The solver then returns a list of jobs to fulfill to successfully install a content unit, which may in turn contain removals of obsoleted, outdated or conflicting units.
In an empty pool, the list of dependencies of a package equals to the top-level Requires field of the package but it most certainly misses dependencies of the dependencies. Unless the Requires field dependencies are all leafs in the dependency tree of the package.
Thus the answer is context-dependent and blurred by various content conflicts but maybe the question itself is the same.

list fulfilled dependencies (from a given list of available packages) for a given rpm package

In the context of a (multi-)source--target repository copy task, to give an answer, the sat solver has to be tricked to consider the target repository content to be already installed. This can be achieved by copying the target repo into the source repo Pool and marking all the units installed. An answer to an install request will then give a list of units to install. When compared to the list of requirements (from the previous bullet), one can obtain list of fulfilled dependencies. However the conflicts might blur the picture again.

validate that all the dependencies (from a given list of available packages) for a given rpm package are fulfilled.

Similar to the previous bullet; asserting the list of packages to install to be empty. Mind the conflicts though.

perform dep solving against multiple repositories

This is naturally supported by both the solvers; a pool can have multiple repos.

Note please that all the answers can be fine-tuned (and changed) by setting various solver options and/or the priorities of the pool repos.
Maybe stating the justification of the requirements could give more context to understand why those are needed and figure out how (better) to address them.

#11 Updated by milan over 2 years ago

  • File pulpsolv.py added

Attaching a POC Pulp-fed depsolving thru direct libsolv calls.
Unfortunately it segfaults at the solving :-/

[vagrant@pulp2 tmp]$ python pulpsolv.py -h
usage: pulpsolv.py [-h] [--repo-name REPO_NAME] [--unit-name UNIT_NAME]

optional arguments:
  -h, --help            show this help message and exit
  --repo-name REPO_NAME
  --unit-name UNIT_NAME
[vagrant@pulp2 tmp]$  python pulpsolv.py --repo-name zoo --unit-name lion
skipping erratum
skipping erratum
skipping erratum
skipping erratum
skipping package_category
skipping package_group
skipping package_group
loaded rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute name value lion
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute epoch value 0
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute version value 0.4
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute release value 1
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute arch value noarch
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute vendor value None
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute requires value [{u'release': None, u'epoch': None, u'version': None, u'flags': None, u'name': u'wolf'}]
processing {u'release': None, u'epoch': None, u'version': None, u'flags': None, u'name': u'wolf'} (dict) attribute name value wolf
processing {u'release': None, u'epoch': None, u'version': None, u'flags': None, u'name': u'wolf'} (dict) attribute epoch value None
processing {u'release': None, u'epoch': None, u'version': None, u'flags': None, u'name': u'wolf'} (dict) attribute version value None
processing {u'release': None, u'epoch': None, u'version': None, u'flags': None, u'name': u'wolf'} (dict) attribute release value None
processing unit rpm: lion-0-0.4-1-noarch-sha256-2c5df6b51df167eb01246dce3049668cbe688033b9abff24464b0e05cdeb20ac attribute provides value [{u'release': u'1', u'epoch': u'0', u'version': u'0.4', u'flags': u'EQ', u'name': u'lion'}]
# --------->%-------------------------------
chimpanzee-0 0.21 1.<NULL>
Found unit lion: 0bebcf20-b999-4707-9809-656f0e38e5cd, solv: 2
Segmentation fault
[vagrant@pulp2 tmp]$
Core was generated by `python pulpsolv.py --repo-name zoo'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x00007f29da3ed893 in solver_addpkgrulesforsolvable (
    solv=solv@entry=0x560d60f65b90, s=0x560d60f45d00, m=m@entry=0x7ffc5f931fa0)
    at /usr/src/debug/libsolv-0.6.30/src/rules.c:1034
1034          if (m && pool->implicitobsoleteusescolors && (s->arch > pool->lastarch || pool->id2arch[s->arch] != 1))
[Current thread is 1 (Thread 0x7f29dcfa2440 (LWP 19137))]
Missing separate debuginfos, use: dnf debuginfo-install python2-2.7.14-4.fc26.x86_64
(gdb) where
#0  0x00007f29da3ed893 in solver_addpkgrulesforsolvable (
    solv=solv@entry=0x560d60f65b90, s=0x560d60f45d00, m=m@entry=0x7ffc5f931fa0)
    at /usr/src/debug/libsolv-0.6.30/src/rules.c:1034
#1  0x00007f29da3b538e in solver_solve (solv=solv@entry=0x560d60f65b90,
    job=0x560d60f65b98, job@entry=0x7ffc5f932080)
    at /usr/src/debug/libsolv-0.6.30/src/solver.c:3652
#2  0x00007f29da88451f in Solver_solve_helper (jobs=..., self=0x560d60f65b90)
    at /usr/src/debug/libsolv-0.6.30/build/bindings/python/solv_python.c:5066
#3  _wrap_Solver_solve_helper (self=<optimized out>, args=<optimized out>)
    at /usr/src/debug/libsolv-0.6.30/build/bindings/python/solv_python.c:14932
#4  0x00007f29dcaaf53e in PyEval_EvalFrameEx () from /lib64/libpython2.7.so.1.0
#5  0x00007f29dcaadb19 in PyEval_EvalFrameEx () from /lib64/libpython2.7.so.1.0
#6  0x00007f29dcaadb19 in PyEval_EvalFrameEx () from /lib64/libpython2.7.so.1.0
#7  0x00007f29dcab0198 in PyEval_EvalCodeEx () from /lib64/libpython2.7.so.1.0
#8  0x00007f29dcab03a9 in PyEval_EvalCode () from /lib64/libpython2.7.so.1.0
#9  0x00007f29dcab639f in run_mod () from /lib64/libpython2.7.so.1.0
#10 0x00007f29dcab634a in PyRun_FileExFlags () from /lib64/libpython2.7.so.1.0
#11 0x00007f29dcab623e in PyRun_SimpleFileExFlags ()
   from /lib64/libpython2.7.so.1.0
#12 0x00007f29dcabc519 in Py_Main () from /lib64/libpython2.7.so.1.0
#13 0x00007f29dbc5488a in __libc_start_main () from /lib64/libc.so.6
#14 0x0000560d5f98377a in _start ()
(gdb)

#12 Updated by milan over 2 years ago

  • File pulpsolv.py added

Attaching a working POC; it still needs some polishing tho

#14 Updated by milan over 2 years ago

  • File deleted (pulpsolv.py)
  • File deleted (pulpsolv.py)

Removing the outdated attachments and replacing with my Github POC repo.

#15 Updated by milan over 2 years ago

Random POC Notes

  • not calling pool.setarch() causes a segfault (see also the note 11 above). libsolv requires setting an architecture which might be an issue as our repos can contain units with different architectures. libdnf being build on top of libsolv most likely exposes the same behavior.
  • pool.parsermprichdep is needed to parse rich dependencies. Fedora26 however didn't ship with libsolv >=0.6.33 so I had to workaround on my dev box; for demo purposes, one can use e.g ignatenkobrain's copr repo
  • The files attribute of an rpm unit isn't processed yet but should be trivial to add.
  • Just the rpm unit type supported; drpm, srpm units should be trivial to add
  • me not knowing what the errata type depsolving should look like I feel it might be a challenge to implement; we might consider evaluating this
  • to support recursive copying of particular module dependencies while maintaining the user-expected module vs system upgrade workflow semantics we'd need to expose the pool->considered C-API function to Python. This function operates over a custom-sized bitmap vector of enabled--disabled content units that we'd have to implement an adapter for, between the Python and C runtimes. This would be a focused patch against the upstream libsolv repo
  • libsolv exposes a decent unit/solvable lookup interface, that supports e.g the globing syntax

#16 Updated by milan over 2 years ago

TODO

Yum content types not covered yet:

  • Erratum (easy) POC
  • srpm (easy) POC
  • drpm (tricky) might not be needed
  • package category (trivial), a set of groups
  • package group (trivial), a set of (RPM) packages

Yum features not covered yet:

  • weak dependencies (done in POC)
  • file-provides (tricky)

Modularity/App-streams support:

  • expose pool->considered to Python bindings (tricky)
  • module as a solvable (dunno, probably tricky)

#17 Updated by rchan over 2 years ago

  • Sprint changed from Sprint 37 to Sprint 38

#19 Updated by milan over 2 years ago

  • Status changed from ASSIGNED to CLOSED - COMPLETE

Marking as done since all the POC items have been implemented and the investigation was concluded, favoring the libsolv library.
See the issues #3715 #3740 and #3741 for the Pulp2 follow-up stories.

#20 Updated by milan about 2 years ago

  • Related to Issue #4152: Regression Pulp 2.17.1: recursive copy of RPMs does not copy partially resolvable dependencies added

#21 Updated by bmbouter over 1 year ago

  • Tags Pulp 2 added

Please register to edit this issue

Also available in: Atom PDF