Bug 833538 - YUM dependency resolution algorithm bug
Summary: YUM dependency resolution algorithm bug
Keywords:
Status: CLOSED NOTABUG
Alias: None
Product: Red Hat Enterprise Linux 5
Classification: Red Hat
Component: yum
Version: 5.5
Hardware: Unspecified
OS: Linux
unspecified
unspecified
Target Milestone: rc
: ---
Assignee: James Antill
QA Contact: BaseOS QE Security Team
URL:
Whiteboard:
Depends On:
Blocks:
TreeView+ depends on / blocked
 
Reported: 2012-06-19 17:22 UTC by Sergio Freire
Modified: 2014-01-21 06:25 UTC (History)
2 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2012-06-19 18:19:23 UTC
Target Upstream Version:
Embargoed:


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

Description Sergio Freire 2012-06-19 17:22:27 UTC
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 18:19:23 UTC
> 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.