Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 515230 - Portage >=2.2.9: Dependency resolver makes incorrect choices to satisfy dependencies of virtual/pkgconfig and virtual/*udev
Summary: Portage >=2.2.9: Dependency resolver makes incorrect choices to satisfy depen...
Status: RESOLVED FIXED
Alias: None
Product: Portage Development
Classification: Unclassified
Component: Core - Dependencies (show other bugs)
Hardware: All All
: Normal normal (vote)
Assignee: Portage team
URL:
Whiteboard:
Keywords: InVCS
Depends on:
Blocks: 155723 484436
  Show dependency tree
 
Reported: 2014-06-26 20:01 UTC by Arfrever Frehtes Taifersar Arahesis
Modified: 2014-09-17 17:43 UTC (History)
7 users (show)

See Also:
Package list:
Runtime testing required: ---


Attachments
ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (emerge_1,60.64 KB, text/plain)
2014-06-26 20:05 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (emerge_1_debug.xz,342.75 KB, application/x-xz)
2014-06-26 20:07 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -ptv virtual/pkgconfig (emerge_2,1.40 KB, text/plain)
2014-06-26 20:09 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -dptv virtual/pkgconfig (emerge_2_debug.xz,241.12 KB, application/x-xz)
2014-06-26 20:10 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -ptv virtual/{libgudev,libudev,udev} (emerge_3,1.74 KB, text/plain)
2014-06-26 20:12 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -dptv virtual/{libgudev,libudev,udev} (emerge_3_debug.xz,242.23 KB, application/x-xz)
2014-06-26 20:13 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (after masking of some packages) (emerge_4,53.40 KB, text/plain)
2014-06-26 20:17 UTC, Arfrever Frehtes Taifersar Arahesis
Details
ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (after masking of some packages) (emerge_4_debug.xz,340.61 KB, application/x-xz)
2014-06-26 20:19 UTC, Arfrever Frehtes Taifersar Arahesis
Details
package_tracker.match: account for atom.unevaluated_atom (package_tracker.match-fix-bug-515230.patch,1.20 KB, patch)
2014-08-22 22:41 UTC, Zac Medico
Details | Diff
package_tracker.match: account for atom.unevaluated_atom (package_tracker.match-fix-bug-515230.patch,1.20 KB, patch)
2014-08-22 22:56 UTC, Zac Medico
Details | Diff
relevant part of the debug log (515230_debug.log.xz,252.00 KB, application/x-xz)
2014-08-24 05:56 UTC, Zac Medico
Details
_dep_check_composite_db: fix bug #515230 (dep_check_composite_db-fix-bug-515230.patch,2.97 KB, patch)
2014-08-25 21:53 UTC, Zac Medico
Details | Diff
dep_check: fix bug #515230 (dep_check-fix-bug-515230.patch,4.21 KB, patch)
2014-08-28 08:24 UTC, Zac Medico
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:01:29 UTC
I use Portage trunk (2.2.10_p39; 9089c2d755b0ecb1b340fc23dda461163f589c43).

I was preparing my system for migration from app-emulation/emul-linux-x86-* to USE="abi_x86_x32" on relevant packages and I noticed that Portage dependency resolver makes incorrect choices to satisfy dependencies of virtual/pkgconfig and virtual/*udev.

I had the following packages installed:

app-emulation/emul-linux-x86-baselibs
app-emulation/emul-linux-x86-db
app-emulation/emul-linux-x86-gtklibs
app-emulation/emul-linux-x86-medialibs
app-emulation/emul-linux-x86-opengl
app-emulation/emul-linux-x86-sdl
app-emulation/emul-linux-x86-soundlibs
app-emulation/emul-linux-x86-xlibs

These packages were direct or indirect dependencies of:

app-emulation/wine
sys-devel/gcc:4.7
sys-devel/gcc:4.8

I uninstalled all app-emulation/emul-linux-x86-* packages.

I masked all app-emulation/emul-linux-x86-* packages in /etc/portage/package.mask.

I ran `ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}`, which incorrectly suggested installation of dev-util/pkgconf and sys-apps/systemd.

virtual/pkgconfig generally depends on:
|| (
    dev-util/pkgconfig
    dev-util/pkgconf
    dev-util/pkgconfig-openbsd
)

dev-util/pkgconfig is already installed, not masked and able for being reinstalled. Portage should not suggest installation of another pkgconfig implementation.

virtual/*udev generally depends on:
|| (
    sys-fs/udev
    sys-apps/systemd
    sys-fs/eudev
)

sys-fs/udev is already installed, not masked and able for being reinstalled. Portage should not suggest installation of another udev implementation.

(I suspended migration, so that I can test potential patches for Portage.)
Comment 1 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:05:02 UTC
Created attachment 379740 [details]
ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}

Output of: ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}

This output shows problems described in initial comment.
Comment 2 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:07:03 UTC
Created attachment 379742 [details]
ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}

Output of: ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}
Comment 3 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:09:55 UTC
Created attachment 379744 [details]
ABI_X86="32 64" emerge -ptv virtual/pkgconfig

Output of: ABI_X86="32 64" emerge -ptv virtual/pkgconfig

This output shows that dev-util/pkgconfig is able to be reinstalled.
Comment 4 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:10:58 UTC
Created attachment 379746 [details]
ABI_X86="32 64" emerge -dptv virtual/pkgconfig

Output of: ABI_X86="32 64" emerge -dptv virtual/pkgconfig
Comment 5 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:12:21 UTC
Created attachment 379748 [details]
ABI_X86="32 64" emerge -ptv virtual/{libgudev,libudev,udev}

Output of: ABI_X86="32 64" emerge -ptv virtual/{libgudev,libudev,udev}

This output shows that sys-fs/udev is able to be reinstalled.
Comment 6 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:13:10 UTC
Created attachment 379750 [details]
ABI_X86="32 64" emerge -dptv virtual/{libgudev,libudev,udev}

Output of: ABI_X86="32 64" emerge -dptv virtual/{libgudev,libudev,udev}
Comment 7 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:17:29 UTC
Created attachment 379752 [details]
ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (after masking of some packages)

Output of: ABI_X86="32 64" emerge -ptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}

With the following packages masked in /etc/portage/package.mask:

dev-util/pkgconf
dev-util/pkgconfig-openbsd
sys-apps/systemd
sys-fs/eudev

Masking of these packages should not be necessary for Portage to correctly calculate dependencies.
Comment 8 Arfrever Frehtes Taifersar Arahesis 2014-06-26 20:19:17 UTC
Created attachment 379754 [details]
ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8} (after masking of some packages)

Output of: ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine sys-devel/gcc:{4.7,4.8}

With the following packages masked in /etc/portage/package.mask:

dev-util/pkgconf
dev-util/pkgconfig-openbsd
sys-apps/systemd
sys-fs/eudev
Comment 9 Michał Górny archtester Gentoo Infrastructure gentoo-dev Security 2014-06-28 12:12:21 UTC
Just for the record, does adding --deep, --upgrade or --changed-use (if possible, please try each of them separately) help?
Comment 10 Samuli Suominen gentoo-dev 2014-07-04 14:23:25 UTC
I apologize for the bugspam, but maybe sys-apps/portage should be reverted to a version where it still worked correctly?
This is causing multiple threads in the forums, such as http://forums.gentoo.org/viewtopic-t-993294.html
Comment 11 Weedy 2014-07-04 17:06:50 UTC
My laptop is not 100% idle so the margin for error is larger then I would like.
These are what looked like the average run.

Installed versions:  2.1.12.2(12:31:50 PM 04/07/14)
[blocks b      ] >=net-libs/libsoup-2.42 (">=net-libs/libsoup-2.42" is blocking net-libs/libsoup-gnome-2.40.3)
[uninstall     ]  net-libs/libsoup-gnome-2.40.3:2.4  USE="introspection -debug" 
[blocks b      ] sys-power/upower ("sys-power/upower" is blocking sys-power/upower-pm-utils-0.9.23-r2)
[uninstall     ]  sys-power/upower-pm-utils-0.9.23-r2  USE="introspection -ios" 
[blocks B      ] sys-apps/systemd ("sys-apps/systemd" is blocking sys-fs/eudev-1.8)
[blocks B      ] sys-apps/gentoo-systemd-integration ("sys-apps/gentoo-systemd-integration" is blocking sys-fs/eudev-1.8)

Total: 246 packages (192 upgrades, 2 downgrades, 42 new, 2 in new slots, 8 reinstalls, 3 uninstalls), Size of downloads: 377,367 kB
Conflict: 6 blocks (2 unsatisfied)

real	6m16.539s
user	6m6.210s
sys	0m9.871s

Installed versions:  2.2.1(12:13:43 PM 04/07/14)
<same blocks>

real	6m34.317s
user	6m24.286s
sys	0m9.559s

Installed versions:  2.2.7(12:03:49 PM 04/07/14)
<same blocks>

real	6m28.036s
user	6m18.138s
sys	0m9.295s

Installed versions:  2.2.8-r1(11:49:26 AM 04/07/14)
< couple extra packages in the blocks but still sane >

real	9m33.284s
user	9m19.807s
sys	0m12.549s

And the depgraph for 2.2.10 is insanity, I kill the timed run after 13 minutes because I gave up waiting.

RECOMMENDATION: hard mask 2.2.10, put 2.2.8+ back into testing, and then all the stable people get 2.2.7.
But I would personally mask everything past 2.2.7, I consider 2.2.7 the last version to work properly.
Comment 12 Sebastian Luther (few) 2014-07-04 18:16:41 UTC
(In reply to Weedy from comment #11)
> RECOMMENDATION: hard mask 2.2.10, put 2.2.8+ back into testing, and then all
> the stable people get 2.2.7.
> But I would personally mask everything past 2.2.7, I consider 2.2.7 the last
> version to work properly.

This version also contained resolver bugs that caused lots of duplicated bug reports.

The problem is that there are lots of bits in the resolver that interact in a non-trivial way. If you change one bit, the interaction may change and the computed result can be quite different.

What in the way of debugging this is, is that those issues are hard to reproduce. Even a debug log doesn't always help.

What we need is a minimal test case to reproduce this. A -uDN world log just contains too much noise.
Comment 13 Tom Wijsman (TomWij) (RETIRED) gentoo-dev 2014-07-06 15:06:29 UTC
(In reply to Sebastian Luther (few) from comment #12)
> What in the way of debugging this is, is that those issues are hard to
> reproduce. Even a debug log doesn't always help.

We should capture more of the state in order to reproduce it; a debug log doesn't let you reproduce it as it just gives some guesses on what could have happened, a capture state on the other hand allows one to somewhat pinpoint it in the code.
Comment 14 Weedy 2014-07-07 10:05:58 UTC
(In reply to Sebastian Luther (few) from comment #12)
> This version also contained resolver bugs that caused lots of duplicated bug
> reports.

Was 2.8 better at resolving?
Any way you look at it 2.10 is broken. Like stupidly horrendously broken.
And that's ignoring the slowness.
Comment 15 Zac Medico gentoo-dev 2014-08-22 21:45:08 UTC
(In reply to Arfrever Frehtes Taifersar Arahesis from comment #2)
> Created attachment 379742 [details]
> ABI_X86="32 64" emerge -dptv --backtrack=1000000 app-emulation/wine
> sys-devel/gcc:{4.7,4.8}
> 
> Output of: ABI_X86="32 64" emerge -dptv --backtrack=1000000
> app-emulation/wine sys-devel/gcc:{4.7,4.8}

The problem appears to be a result of the new slot conflict handling code inside the depgraph._solve_non_slot_operator_slot_conflicts method. The debug log shows it handling a conflict for virtual/pkgconfig-0-r1:

!!! Slot conflict graph:
(virtual/pkgconfig-0-r1:0/0::gentoo, installed) depends on
  (dev-util/pkgconfig-0.28-r1:0/0::gentoo, installed) (0)

Immediately after that point in the log, the depgraph starts pulling in dev-util/pkgconf instead of dev-util/pkgconfig.
Comment 16 Zac Medico gentoo-dev 2014-08-22 22:41:00 UTC
Created attachment 383434 [details, diff]
package_tracker.match: account for atom.unevaluated_atom

Please disregard comment #15.

The attached patch fixes the match cache to properly account for atom.unevaluated_atom, which is required since match_from_list output depends on atom.unevaluated_atom. Note that similar issues were also fixed in commits d603f1440c814377fbc1965729fd9b6b008cf76d and 5438bb29c996d777b6343515995176912a7c137f.
Comment 17 Zac Medico gentoo-dev 2014-08-22 22:56:20 UTC
Created attachment 383436 [details, diff]
package_tracker.match: account for atom.unevaluated_atom

This fixed misspelling of unevaluated_atom in the previous patch.

Somebody should go through other changes from the past year to see if there are any other match caches that fail to account for atom.unevaluated_atom.
Comment 18 Zac Medico gentoo-dev 2014-08-23 07:31:27 UTC
(In reply to Zac Medico from comment #17)
> Created attachment 383436 [details, diff] [details, diff]
> package_tracker.match: account for atom.unevaluated_atom
> 
> This fixed misspelling of unevaluated_atom in the previous patch.
> 
> Somebody should go through other changes from the past year to see if there
> are any other match caches that fail to account for atom.unevaluated_atom.

I spoke to Sebastian Luther on IRC, and he doesn't think there are any other match caches with this sort of problem. So, with Brian Dolbec's blessing, I've pushed this patch as commit 5c0f68017e9943f9486ee68005ea3ef7743244bd.
Comment 19 Arfrever Frehtes Taifersar Arahesis 2014-08-23 09:39:35 UTC
This bug was introduced in Portage 2.2.9.
virtual/*udev part of this bug is no longer reproducible due to changes in the tree.
virtual/pkgconfig part of this bug is still reproducible at the time of 5c0f68017e9943f9486ee68005ea3ef7743244bd.
Comment 20 Zac Medico gentoo-dev 2014-08-24 05:56:40 UTC
Created attachment 383494 [details]
relevant part of the debug log

I was able to reproduce the problem using an complete copy of Arfrever's configuration. It seems that the problem is due to the the depgraph using _select_atoms_from_graph after just having called _remove_pkg on the dev-util/pkgconfig instance because its only parent was involved in a slot conflict. The relevant _remove_pkg calls show in the log like this:

Removing package: (virtual/pkgconfig-0-r1:0/0::gentoo, installed)
Removing package: (dev-util/pkgconfig-0.28-r2:0/0::gentoo, installed)

Following that, the unbuilt virtual/pkgconfig-0-r1 ebuild gets pulled in, since it's already in the graph (it was involved in the slot conflict with the installed instance that just got removed). Here is the relevant part of the backtrace which corresponds to the state at the end of the attached log:

  pym/_emerge/depgraph.py(6269)altlist()
-> self._resolve_conflicts()
  pym/_emerge/depgraph.py(6396)_resolve_conflicts()
-> self._process_slot_conflicts()
  pym/_emerge/depgraph.py(1241)_process_slot_conflicts()
-> self._solve_non_slot_operator_slot_conflicts()
  pym/_emerge/depgraph.py(1208)_solve_non_slot_operator_slot_conflicts()
-> self._create_graph()
  pym/_emerge/depgraph.py(2037)_create_graph()
-> if not self._pop_disjunction(allow_unsatisfied):
  pym/_emerge/depgraph.py(3048)_pop_disjunction()
-> pkg, dep_root, dep_priority, dep_struct, allow_unsatisfied):
  pym/_emerge/depgraph.py(2655)_add_pkg_dep_string()
-> allow_unsatisfied)
> pym/_emerge/depgraph.py(2831)_wrapped_add_pkg_dep_string()

And with Pdb we can see the _select_atom state:

(Pdb) p self._select_atoms
<bound method depgraph._select_atoms_from_graph of <_emerge.depgraph.depgraph object at 0x9bfccec>>

So, it seems that we need to update that depgraph._select_atoms reference inside _solve_non_slot_operator_slot_conflicts, before calling _create_graph.
Comment 21 Zac Medico gentoo-dev 2014-08-25 20:43:58 UTC
The faulty dep resolution actually begins to occur when _select_atom is still set to _select_atoms_highest_available. The root problem is actually seems to be due to the _dep_check_composite_db visibility logic, as demonstrated by the following Pdb log:

(Pdb) p self._select_package('/', Atom('>=dev-util/pkgconfig-0.28-r1[abi_x86_32(-),abi_x86_64(-)]'))
(<Package ('ebuild', '/', 'dev-util/pkgconfig-0.28-r2', 'merge', 'gentoo')>, None)
(Pdb) p self._dynamic_config._filtered_trees['/']['porttree'].dbapi.match_pkgs(Atom('>=dev-util/pkgconfig-0.28-r1[abi_x86_32(-),abi_x86_64(-)]'))
[]

As you can see, _select_package appears to return the correct result, while _dep_check_composite_db.match_pkgs returns an empty result. I appears to be due to the unbuilt instance being masked by _dep_check_composite_db._visible, since the installed instance is already in the graph.
Comment 22 Zac Medico gentoo-dev 2014-08-25 21:53:20 UTC
Created attachment 383582 [details, diff]
_dep_check_composite_db: fix bug #515230

This patches fixes it for me with Arfrever's configuration. Due to the complexity of the state involved, I haven't yet written a standalone test case.
Comment 23 Arfrever Frehtes Taifersar Arahesis 2014-08-26 08:48:08 UTC
(In reply to Zac Medico from comment #22)

This patch fixes this bug, but breaks `emerge -ptv dev-java/icedtea` (unwanted downgrade of dev-java/java-config from >=2.2 to <2.2 and uninstallation of app-admin/eselect-java).
Java eclasses add these dependencies to JVM packages:
  >=dev-java/java-config-2.1.9-r1
  =dev-java/java-config-2*
  || ( app-admin/eselect-java <dev-java/java-config-2.2 )
Comment 24 Zac Medico gentoo-dev 2014-08-28 08:24:16 UTC
Created attachment 383824 [details, diff]
dep_check: fix bug #515230

This version of the patch includes a new hunk in dep_zapdeps, which fixes the java-config downgrade issue that was reported in comment #23.
Comment 25 Zac Medico gentoo-dev 2014-08-28 16:09:08 UTC
(In reply to Zac Medico from comment #24)
> Created attachment 383824 [details, diff] [details, diff]
> dep_check: fix bug #515230
> 
> This version of the patch includes a new hunk in dep_zapdeps, which fixes
> the java-config downgrade issue that was reported in comment #23.

I've pushed this as commit 617a64f77055ddda1dd86a506cf98f5adc545fae.
Comment 26 Zac Medico gentoo-dev 2014-09-17 17:43:41 UTC
This is fixed in 2.2.13.