Bug 833538 - YUM dependency resolution algorithm bug
YUM dependency resolution algorithm bug
Status: CLOSED NOTABUG
Product: Red Hat Enterprise Linux 5
Classification: Red Hat
Component: yum (Show other bugs)
5.5
Unspecified Linux
unspecified Severity unspecified
: rc
: ---
Assigned To: James Antill
BaseOS QE Security Team
:
Depends On:
Blocks:
  Show dependency treegraph
 
Reported: 2012-06-19 13:22 EDT by Sergio Freire
Modified: 2014-01-21 01:25 EST (History)
2 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2012-06-19 14:19:23 EDT
Type: Bug
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)
spec files and yum output of success and fail (2.11 KB, application/x-compressed)
2012-06-19 13:22 EDT, Sergio Freire
no flags Details

  None (edit)
Description Sergio Freire 2012-06-19 13:22:27 EDT
Created attachment 593021 [details]
spec files and yum output of success and fail

Description of problem:
yum seems not to be able to resolve dependencies correctly, even if their dependencies are in theory fully solvable.

Lets consider a yum repository we have the following packages:
 - rubygem-thor-0.14.6-1.ptin.el5.noarch
 - rubygem-thor-0.15.2-1.ptin.el5.noarch
 - pacote-a-1.0-1.ptin.el5.x86_64
 - pacote-b-1.0-1.ptin.el5.x86_64
 - pacote-c-1.0-1.ptin.el5.x86_64
 - pacote-d-1.0-1.ptin.el5.x86_64


Unsolvable Case
===============
Say we have a package named "terceiro" which depends on two other ("pacote-a" and "pacote-b").
"pacote-a" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.
"pacote-b" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.
We are unable to install "terceiro" using yum since it says the "rubygem(thor) < 0.15.0" dependency is missing.

Solvable Case
=============
Say we have a package named "quarto" (similar to "terceiro") which depends on two other ("pacote-c" and "pacote-d"). We copied the contents of pacote-a.spec to pacote-d.spec and pacote-b.spec to pacote-c.spec, respectively. We are basically changing artificially the order during yum dependency resolution, but maintaining the contents/dependencies.
So now,
"pacote-c" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.
"pacote-d" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.

Thus, we are ABLE to install "quarto", although the dependencies are exactly the same.


Version-Release number of selected component (if applicable):
yum-3.2.22-26.el5

How reproducible: always


Steps to Reproduce:
1. build the "pacote-[abcd]", "terceiro" and "quarto" RPMs using the provided spec files, and upload them to a YUM repository
2. have two RPMs rubygem-thor, as mentioned above, in a YUM repository
3. yum -d 10 install terceiro
3. yum -d 10 install quarto
  
Actual results:
only when dependencies are in the correct order, when the first dependency resolution chooses the "correct" package, the final resolution is OK.
in the first case, since rubygem-thor (0.15.2) is chosen then it does not comply with the dependency rubygem(thor) < 0.15.0 of "pacote-b".

Expected results:
packages ("terceiro" and "quarto") should always be able to install, using the rubygem-thor (0.14.6) dependency.

Additional info:
Note that we are using multiple "Requires" lines in order to limit the version of the dependency.
See yum logs attached of the two yum attempts, with debug enabled.
Comment 1 James Antill 2012-06-19 14:19:23 EDT
> Say we have a package named "terceiro" which depends on two other ("pacote-a" and "pacote-b").
> "pacote-a" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.
> "pacote-b" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.

 This kind of thing is just never going to work before RHEL-8 ... and it is very unlikely to work _well_ even then, you can test Hawkeye/DNF in rawhide now and provide feedback.

 The reason it doesn't work now is because the current depsolver just tries to solve each "prco" as it gets to it ... and it almost never looks at downgrades. It does try to sort them so that it'll look at "<" before ">=" so in the above case if it hits "foo < 15" it'll probably choose a package that satisfies all 4 requirements ... but that's mostly luck.

 The reason it can't easily work well in general is because even if you install "foo-0.14.5" when "foo-0.18" is available ... there is no good way to communicate that information into the update logic. So everytime something asks "are there updates" yum will respond "sure, foo-0.18 is available and updates foo-0.14.5" ... then it'll try to actually do it and fail.

 In short ... don't do that.

Note You need to log in before you can comment on or make changes to this bug.