Please attach the zypper logfile /var/log/zypper.log (or an older and compressed /var/log/zypper.log-YYYYMMDD.xz) that shows the reported behavior.

Created attachment 654254 [details]
zypper.log

> 11:30:34 [zypp] TargetImpl.commitFindFileConflicts.cc(commitFindFileConflicts):127 Checking for file conflicts in 32 new packages...
> 11:30:34 [libsolv++] PoolImpl.cc(logSat):114 searching for file conflicts
> 11:30:34 [libsolv++] PoolImpl.cc(logSat):114 packages: 8577, cutoff 32
> .
> 11:30:48 [libsolv++] PoolImpl.cc(logSat):114 filemap size: 131072, used 44568
> 11:30:48 [libsolv++] PoolImpl.cc(logSat):114 filemap memory usage: 1024 K
> 11:30:48 [libsolv++] PoolImpl.cc(logSat):114 filemap creation took 14006 ms
> 11:30:48 [libsolv++] PoolImpl.cc(logSat):114 lookat_dir size: 206004
> .
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 normap size: 262144, used 85084
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 normap memory usage: 2048 K
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 stats made: 85084
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 statmap size: 262144, used 68329
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 statmap memory usage: 2048 K
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 alias processing took 66379 ms
> 11:31:54 [libsolv++] PoolImpl.cc(logSat):114 raw candidates: 688248, pruning
> 11:31:55 [libsolv++] PoolImpl.cc(logSat):114 candidates now: 95267
> .
> 11:33:51 [libsolv++] PoolImpl.cc(logSat):114 filespace size: 15430 K
> 11:33:51 [libsolv++] PoolImpl.cc(logSat):114 candidate check took 117017 ms
> 11:33:51 [libsolv++] PoolImpl.cc(logSat):114 found 0 file conflicts
> 11:33:51 [libsolv++] PoolImpl.cc(logSat):114 file conflict detection took 197407 ms
> 11:33:51 [zypp] TargetImpl.commitFindFileConflicts.cc(commitFindFileConflicts):160 Found 0 file conflicts.

@mls: Retrieving the RPM headers seems to take some time, but the last pass seems to be very slow. Any idea how to improve it?

@Harald: if the problems persists, could you please add a solver testcase. 

>    # zypper in --debug-solver nopackage
>    ...
>    Generating solver test case...
>    Solver test case generated successfully at /var/log/zypper.solverTestCase.  
Then pack the output directory together with /var/log/zypper.log and attach it to the bugreport. 

In case the testcase exceeds the 10MB limit for bugzilla uploads, you can use 'split' to divide the file into smaller pieces: 
>  $ cd /tmp
>  $ tar cvjf zypper.solverTestCase.tar.bz2 /var/log/zypper.solverTestCase/
>  $ split -b 9M --additional-suffix=-zypper.solverTestCase.tar.bz2 \
>    zypper.solverTestCase.tar.bz2
The created pieces will be named like this:
>  xaa-zypper.solverTestCase.tar.bz2
>  xab-zypper.solverTestCase.tar.bz2
>  xac-zypper.solverTestCase.tar.bz2
>  ...

I don't know if that makes sense, as you can't reproduce file conflicts with a solver testcase.

But the output of 'rpm -qa' would be interesting, you seem to have lots of kernel versions installed or something similar.

(In reply to Michael Schröder from comment #5)
> I don't know if that makes sense, as you can't reproduce file conflicts with
> a solver testcase.

Yes, but I see where the installed packages come from, so it's easier to reproduce.

So just attach the solver-system.xml.gz file from the testcase...

For me "Checking for file conflicts" just stalled at 57% for >5 minutes without finishing, hence I needed to kill zypper.

I could resolve this situation by deleting *lots* of different installed versions of package kernel-source and package kernel-devel.
I don't know why these package versions accumulate over time (and I also deleted their files once when running out of disk space (which could also have contributed to the "checking for file conflicts" issue)).

@Stefan: Maybe you can attach your /var/log/zypp/history file. MAybe it can help us to reproduce the issue.

@Thomas: As dracut maintainer, maybe you can figure out why /sbin/purge-kernels left so many kernel-source and package kernel-devel on Stefans system (comment#8).

I had the same problem, I didn't stop the time but I gave up waiting only after quite a few minutes. Like Stefan suggested, I checked for old kernel versions and found a lot. I removed them and after that "checking for file conflicts" took less than a second.

I wrote down all the packages I removed/installed to fix the problem:

kernel-default, kernel-default-devel
in 4.8.4-1.2-x86_64
rm 4.8.4-1.1-x86_64
rm 4.8.3-1.1-x86_64
rm 4.7.6-1.1-x86_64
rm 4.7.5-1.1-x86_64
rm 4.7.4-2.1-x86_64
rm 4.7.4-1.2-x86_64
rm 4.7.3-1.1-x86_64
rm 4.7.2-2.2-x86_64
rm 4.7.2-1.2-x86_64

kernel-devel, kernel-source
in 4.8.4-1.2-noarch
rm 4.8.4-1.1-noarch
rm 4.8.3-1.1-noarch
rm 4.7.6-1.1-noarch
rm 4.7.5-1.2-noarch
rm 4.7.5-1.1-noarch
rm 4.7.4-2.1-noarch
rm 4.7.4-1.2-noarch
rm 4.7.3-1.1-noarch
rm 4.7.2-2.2-noarch
rm 4.7.2-1.3-noarch
rm 4.7.2-1.2-noarch

kernel-syms
in 4.8.4-1.2-x86_64
rm 4.8.4-1.1-x86_64
rm 4.8.3-1.1-x86_64
rm 4.7.6-1.1-x86_64
rm 4.7.5-1.2-x86_64
rm 4.7.5-1.1-x86_64
rm 4.7.4-2.1-x86_64
rm 4.7.4-1.2-x86_64
rm 4.7.3-1.1-x86_64
rm 4.7.2-2.2-x86_64
rm 4.7.2-1.3-x86_64

virtualbox, virtualbox-qt
in 5.1.6-1.18-x86_64
rm 5.1.4-3.1-x86_64

virtualbox-host-kmp-default
in 5.1.6_k4.8.4_1.18-x86_64
rm 5.1.4_k4.7.2_1-1.3-x86_64

virtualbox-guest-kmp-default
rm 5.1.4_k4.7.2_1-1.3-x86_64

For some reason I had virtualbox-guest-kmp-default installed, which I couldn't upgrade to the newest version because it had a conflict with virtualbox-host-kmp-default.
I'll also attach the part of /var/log/zypp/history with today's messages.

Created attachment 700057 [details]
/var/log/zypp/history of removing old kernels and then running "zypper up"

It seems to be sufficient to install either kernel-devel or kernel-default-devel while having another version thereof installed:

$> LANG=C zypper se -si kernel
Loading repository data...
Reading installed packages...

S | Name                 | Type    | Version      | Arch   | Repository       
--+----------------------+---------+--------------+--------+------------------
i | kernel-default       | package | 4.8.4-1.2    | x86_64 | (System Packages)
i | kernel-default       | package | 4.8.3-1.1    | x86_64 | (System Packages)
i | kernel-default       | package | 4.8.6-1.1    | x86_64 | repo-oss         
i | kernel-default-devel | package | 4.8.4-1.2    | x86_64 | (System Packages)
i | kernel-default-devel | package | 4.8.3-1.1    | x86_64 | (System Packages)
i | kernel-default-devel | package | 4.8.6-1.1    | x86_64 | repo-oss         
i | kernel-devel         | package | 4.8.4-1.2    | noarch | (System Packages)
i | kernel-devel         | package | 4.8.4-1.1    | noarch | (System Packages)
i | kernel-devel         | package | 4.8.3-1.1    | noarch | (System Packages)
i | kernel-devel         | package | 4.8.6-1.1    | noarch | repo-oss         
i | kernel-firmware      | package | 20161005-1.1 | noarch | repo-oss         
i | kernel-macros        | package | 4.8.6-1.1    | noarch | repo-oss         
i | kernel-source        | package | 4.8.4-1.2    | noarch | (System Packages)
i | kernel-source        | package | 4.8.4-1.1    | noarch | (System Packages)
i | kernel-source        | package | 4.8.3-1.1    | noarch | (System Packages)
i | kernel-source        | package | 4.8.6-1.1    | noarch | repo-oss         
i | nfs-kernel-server    | package | 1.3.4-3.1    | x86_64 | repo-oss 

for p in kernel-default kernel-default-devel ; do
  zypper in --force $p
; done

$> sudo cat /var/log/zypper.log | egrep  'Checking for file|took [0-9]{3,9}|candidates now|\.rpm from' 

2016-11-06 22:31:05 <1> pebbles.site(20719) [zypper] Summary.cc(readPool):281 package update candidates: 0
2016-11-06 22:31:05 <1> pebbles.site(20719) [zypper] Summary.cc(readPool):281 product update candidates: 0
2016-11-06 22:31:07 <1> pebbles.site(20719) [zypp++] MediaSetAccess.cc(provide):203 Going to try to provide  file ./suse/x86_64/kernel-default-4.8.6-1.1.x86_64.rpm from media number 1
2016-11-06 22:31:54 <1> pebbles.site(20719) [zypp++] MediaSetAccess.cc(releaseFile):85 Going to release file ./suse/x86_64/kernel-default-4.8.6-1.1.x86_64.rpm from media number 1
2016-11-06 22:31:54 <1> pebbles.site(20719) [zypp] TargetImpl.commitFindFileConflicts.cc(commitFindFileConflicts):127 Checking for file conflicts in 1 new packages...
2016-11-06 22:31:55 <1> pebbles.site(20719) [libsolv++] PoolImpl.cc(logSat):119 filemap creation took 175 ms
2016-11-06 22:31:55 <1> pebbles.site(20719) [libsolv++] PoolImpl.cc(logSat):119 alias processing took 147 ms
2016-11-06 22:31:55 <1> pebbles.site(20719) [libsolv++] PoolImpl.cc(logSat):119 raw candidates: 15615, pruning
2016-11-06 22:31:55 <1> pebbles.site(20719) [libsolv++] PoolImpl.cc(logSat):119 candidates now: 26
2016-11-06 22:31:55 <1> pebbles.site(20719) [libsolv++] PoolImpl.cc(logSat):119 file conflict detection took 398 ms

2016-11-06 22:33:26 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 addfileprovides took 113 ms
2016-11-06 22:33:26 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 pkg rule creation took 139 ms
2016-11-06 22:33:26 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 solver_solve took 171 ms
2016-11-06 22:33:27 <1> pebbles.site(3976) [zypper] Summary.cc(readPool):281 package update candidates: 0
2016-11-06 22:33:27 <1> pebbles.site(3976) [zypper] Summary.cc(readPool):281 product update candidates: 0
2016-11-06 22:33:30 <1> pebbles.site(3976) [zypp++] MediaSetAccess.cc(provide):203 Going to try to provide  file ./suse/x86_64/kernel-default-devel-4.8.6-1.1.x86_64.rpm from media number 1
2016-11-06 22:33:33 <1> pebbles.site(3976) [zypp++] MediaSetAccess.cc(releaseFile):85 Going to release file ./suse/x86_64/kernel-default-devel-4.8.6-1.1.x86_64.rpm from media number 1
2016-11-06 22:33:33 <1> pebbles.site(3976) [zypp] TargetImpl.commitFindFileConflicts.cc(commitFindFileConflicts):127 Checking for file conflicts in 1 new packages...
2016-11-06 22:33:34 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 filemap creation took 111 ms
2016-11-06 22:33:34 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 alias processing took 165 ms
2016-11-06 22:33:34 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 raw candidates: 51391, pruning
2016-11-06 22:33:34 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 candidates now: 12964
2016-11-06 22:33:56 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 file info fetching took 22310 ms
2016-11-06 22:33:56 <1> pebbles.site(3976) [libsolv++] PoolImpl.cc(logSat):119 file conflict detection took 22594 ms



So after the "pruning" step (whatever that is), there are a lot of candidates left, each triggering a call to rpm_iterate_filelist.

The calls to rpm_iterate_filelist are the actually expensive part. Maybe there should be an rpm_iterate_dirlist there, fetching directory names is significantly less expensive than fetching info for all files (assuming there are far less directories than files), and file conflicts can only happen if the sets of directories have a non-empty intersection.

Another point that may be relevant here, at least the kernel-default-devel packages actually *have* a conflicting file - /usr/src/linux-obj/x86_64/default is a symlink to ./default, which gets modified in the postinstall scriptlet.

Just wanted to add:

 - I'm having the same issue with Tumbleweed (just spent 4min on a 3.5GHz i7)
 - I only do have two sets of kernel source/devel installed (obviously three after an zypper up, until the next boot when the oldest is purged)
 - It just happened today with a zypper up (which indeed did install new kernel), but not for quite some updates that also installed new kernels.
 - grepping for the time for conflict check in zypper.log shows the last time it happened was last year November 17.

In case it matters: This were the packages installed during both updates:

bbswitch
bbswitch-kmp-default
bumblebee
kernel-devel
kernel-macros
kernel-source
kernel-syms
openSUSE-release
openSUSE-release-ftp
plasma5-defaults-openSUSE
plasma5-theme-openSUSE
plasma5-workspace-branding-openSUSE
sddm-theme-openSUSE
subsurface
VirtualGL
VirtualGL-32bit

Reassigning to mmarek, who owns purge-kernels.

If you encounter this problem, please attach your /etc/zypp/zypp.conf and the output of the following commands:

rpm -qa

uname -r -m

/sbin/purge-kernels

The purge-kernels command must be ran as root.

(In reply to Michal Marek from comment #15)
> If you encounter this problem, please attach your /etc/zypp/zypp.conf and
> the output of the following commands:
> 
> rpm -qa
> 
> uname -r -m
> 
> /sbin/purge-kernels
> 
> The purge-kernels command must be ran as root.

AFAICT this is not really related to the kernel itself. The bad behaviour is (at least) triggered by multiple installed versions of the kernel-default-devel package, but may happen for other packages.

This is a completely valid scenario:
$> rpm -q --provides kernel-default-devel | grep multiversion
multiversion(kernel)

*libzypp/libsolv* shows O(n^2) behaviour when detecting file conflicts. In most cases, this does not matter as the "pruning" step vastly reduces n (from comment 12):

kernel-default:
raw candidates: 15615, pruning (~9500 files)
candidates now: 26

kernel-default-devel (~16000 files):
raw candidates: 51391, pruning
candidates now: 12964

Intersection of two sets can be done in O(n) time.

Right. We are talking about two issues, one being triggered by another:

1) purge-kernels not doing its job in some cases

2) zypp file conflict check too slow if there are multiple kernels installed,
   such as when 1) happens.

So if somebody belives they are observing a bug in the purge-kernels script, please create a _new_ bugreport and attach the requested information there. Let's leave this bug open for any libzypp speedups.

*** Bug 1028014 has been marked as a duplicate of this bug. ***

Created attachment 716850 [details]
logfiles /tar.xz archive) of latest zypper dup (P.Suetterlin)

logfiles for both zypper dup and purge-kernels

Sorry, should have gone to the attachment post:

OK, I'm just running an update (zypper dup -l --no-allow-vendor-change) that again hangs in the conflicts stage. I'm attaching the requested info files.
But I doubt it's purge-kernels. I do have (before the update) two sets of kernel/source/devel installed, as requested by the zypp.conf setting...

> 2017-03-09 10:19:02 <1> woodstock.pitnet(14669) [libsolv++] PoolImpl.cc(logSat):119 pruning took 37 ms
> 2017-03-09 10:25:27 <1> woodstock.pitnet(14669) [libsolv++] PoolImpl.cc(logSat):119 header fetches: 22
> 2017-03-09 10:25:27 <1> woodstock.pitnet(14669) [libsolv++] PoolImpl.cc(logSat):119 file info fetching took 385141 ms

Taking the bug to check the 'file info fetching'.

@mls: how to speed this up?

Created attachment 738990 [details]
zypper log file

$ purge-kernels 
/sbin/purge-kernels: Nothing to do.

> 12:15:12 [zypp] TargetImpl.commitFindFileConflicts.cc(commitFindFileConflicts):127 Checking for file conflicts in 1293 new packages...
> 12:15:12 [libsolv++] PoolImpl.cc(logSat):119 searching for file conflicts
> 12:15:12 [libsolv++] PoolImpl.cc(logSat):119 packages: 5445, cutoff 1293, usefilecolors 0
> 12:15:14 [libsolv++] PoolImpl.cc(logSat):119 filemap size: 262144, used 97796
> 12:15:14 [libsolv++] PoolImpl.cc(logSat):119 filemap memory usage: 2048 K
> 12:15:14 [libsolv++] PoolImpl.cc(logSat):119 header fetches: 3427
> 12:15:14 [libsolv++] PoolImpl.cc(logSat):119 filemap creation took 1929 ms
> 12:15:14 [libsolv++] PoolImpl.cc(logSat):119 lookat_dir size: 54358
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 normap size: 65536, used 20129
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 normap memory usage: 512 K
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 header fetches: 2904
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 stats made: 20129
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 statmap size: 65536, used 18394
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 statmap memory usage: 512 K
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 alias processing took 1597 ms
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 raw candidates: 241367, pruning
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 candidates now: 119506
> 12:15:15 [libsolv++] PoolImpl.cc(logSat):119 pruning took 46 ms
> <ABORTED>
> 12:18:30 [zypp] Exception.cc(log):137 TargetImpl.commitFindFileConflicts.cc(operator()):143 THROW:    ABORT request: 

I wonder why we can not reproduce this. 
Can this be reliably reproduced on a machine we can access to investigate?

This is clearly reproducible of you have installed multiple versions of e.g. kernel-default-devel.

Please see comment 12 for some details - TLDR:

Each "candidate" calls rpm_iterate_filelist, which creates the full metadata of each currently installed file.

> $ zypper se -s kernel-default-devel
> S  | Name                 | Type    | Version     | Arch   | Repository       
> ---+----------------------+---------+-------------+--------+------------------
> v  | kernel-default-devel | package | 4.4.85-22.1 | x86_64 | update-oss (42.3)
> i+ | kernel-default-devel | package | 4.4.79-19.1 | x86_64 | update-oss (42.3)
> i+ | kernel-default-devel | package | 4.4.79-4.2  | x86_64 | update-oss (42.3)
> i+ | kernel-default-devel | package | 4.4.76-1.1  | x86_64 | repo-oss (42.3)  

> $ time zypper in kernel-default-devel-4.4.85-22.1
> real    0m13.329s
> user    0m3.534s
> sys     0m1.048s

> [zypper] main.cc(main):75 ===== '/Local/ma/zypp/BUILD/zypper/src/zypper' 'in' 'kernel-default-devel-4.4.85-22.1' =====
> [libsolv++] PoolImpl.cc(logSat):119 file conflict detection took 328 ms

Similar on my other machines (Leap/TW). I don't experience these kind of delays. Something is missing...

I experienced the same issue and since I have an nVidia card I surely did not uninstall kernel-default-devel.

I fixed my issue with removing another kernel related package: kernel-source IIRC

I can provide a new Thinkpad laptop where one can reproduce that with just a single kernel installed. Please contact me by email and I can provide credentials.

Same issue with a brand spanking new tumbleweed install on an SSD.

First ran "zypper -v dup -d", then "zypper -v dup" and the latter hangs.

"Workaround" - delete everything under /var/cache/zypp and rerun with --download-as-needed - this seems to skip the file conflict check. Kinda defeats the whole point of downloading in advance.

And not an issue on Leap 42.3 with multiple kernel-source packages.

Heavily delayed checking for file conflicts found also on my machine. If needed I could provide a zypper debug logfile for an update - updating to openSUSE-release-ftp-20171125-1.2.x86_64.

(In reply to Michael Hanscho from comment #31)
> ..I could provide a zypper debug logfile.
Yes, maybe it reveals some detail that helps us to reproduce it.

Created attachment 750248 [details]
zypper.log

zypper.log emptied - so only logging from the following zypper command
rm -rf /var/cache/zypp
export ZYPP_LIBSAT_FULLLOG=1
export ZYPP_FULLOG=1
zypper -v dup  --no-allow-vendor-change


openSUSE Tumbleweed  20171123-0 -> 20171125-0

My solution is to zypper rm all versions of kernel-devel and kernel-source and "zypper in kernel-devel kernel-source". This went like a charm.

Solution from Freek in comment #34 works for me too.
Time needed checking files was 5-10 minuten, now 1-2 seconds.

I don't have kernel-devel and kernel-source installed, and checking still takes more than a minute.

Tumbleweed upgraded from 42.3.
Additional repo: skypeforlinux

Each time I do zypper dup I get stuck at "Checking for file conflicts" for several minutes.

During the really long "Checking for file conflicts" step, System Load Viewer shows 100% CPU on one core, and the disk activity LED is OFF during most (>99%) of the waiting time. So I do think something is running more loops than necessary.


Will information from "valgrind --tool=callgrind" help if I run it next time I zypper dup?

(In reply to Michael Andres from comment #26)
> > $ zypper se -s kernel-default-devel
> > S  | Name                 | Type    | Version     | Arch   | Repository       
> > ---+----------------------+---------+-------------+--------+------------------
> > v  | kernel-default-devel | package | 4.4.85-22.1 | x86_64 | update-oss (42.3)
> > i+ | kernel-default-devel | package | 4.4.79-19.1 | x86_64 | update-oss (42.3)
> > i+ | kernel-default-devel | package | 4.4.79-4.2  | x86_64 | update-oss (42.3)
> > i+ | kernel-default-devel | package | 4.4.76-1.1  | x86_64 | repo-oss (42.3)  
> 
> > $ time zypper in kernel-default-devel-4.4.85-22.1
> > real    0m13.329s
> > user    0m3.534s
> > sys     0m1.048s
> 
> > [zypper] main.cc(main):75 ===== '/Local/ma/zypp/BUILD/zypper/src/zypper' 'in' 'kernel-default-devel-4.4.85-22.1' =====
> > [libsolv++] PoolImpl.cc(logSat):119 file conflict detection took 328 ms
> 
> Similar on my other machines (Leap/TW). I don't experience these kind of
> delays. Something is missing...

What happens if you reinstall (zypper in --force ..) one of the already installed kernel-default-devel packages?

(In reply to Qi Fan from comment #37)
> 
> Will information from "valgrind --tool=callgrind" help if I run it next time
> I zypper dup?

It spends most of the time in rpm_iterate_filelist, as already said.

rpm_iterate_filelist itself could be speed up by a factor of ~2 if it were better optimized (it does e.g. multiple mallocs per entry, where one would suffice), but this helps only a little.

The big problem still is the O(n^2) behaviour (for each candidate, check each file in each package if it conflicts).

(In reply to Stefan Brüns from comment #38)
> What happens if you reinstall (zypper in --force ..) one of the already
> installed kernel-default-devel packages?

The largest amount of time seems to be spent reading data from disk:

> 1.) real    0m41.645s
> 2.) real    0m5.820s
> sync; echo 3 > /proc/sys/vm/drop_caches
> 3.) real    0m53.244s
> 4.) real    0m6.750s

(In reply to Stefan Brüns from comment #39)
> (In reply to Qi Fan from comment #37)
> > 
> > Will information from "valgrind --tool=callgrind" help if I run it next time
> > I zypper dup?
> 
> It spends most of the time in rpm_iterate_filelist, as already said.
> 
> rpm_iterate_filelist itself could be speed up by a factor of ~2 if it were
> better optimized (it does e.g. multiple mallocs per entry, where one would
> suffice), but this helps only a little.
> 
> The big problem still is the O(n^2) behaviour (for each candidate, check
> each file in each package if it conflicts).

I think you are right. The comment like this:
https://github.com/openSUSE/libsolv/blob/bef46d75f6d2537060114eea0f3a892e958ad5e0/ext/pool_fileconflicts.c#L839
does seem to have assumed that n is pretty small. 

Some O(n) algorithm should be used instead.

No, the comment is misleading. It's just about the initial hash sizes.

The problem is that the pruned list of candidates is *way* too big. An entry in that list basically means that two files share the same disk location and so the file checksums needs to be checked.

But the end result is "no file conflicts", so all of the checksums match! The only explanation I have that it compares a package against itself, but I don't see how this can happen. The problem really is that we can't reproduce the behavior, I just installed 6 kernel versions and file conflict checking simply works.

So yes, it's easy to change that "file info fetching" step to not break in that case, but to me there's something bad going on elsewhere that causes this and we have to find and fix that first.

(In reply to Michael Schröder from comment #42)
> No, the comment is misleading. It's just about the initial hash sizes.
> 
> The problem is that the pruned list of candidates is *way* too big. An entry
> in that list basically means that two files share the same disk location and
> so the file checksums needs to be checked.
> 
> But the end result is "no file conflicts", so all of the checksums match!
> The only explanation I have that it compares a package against itself, but I
> don't see how this can happen. The problem really is that we can't reproduce
> the behavior, I just installed 6 kernel versions and file conflict checking
> simply works.
> 
> So yes, it's easy to change that "file info fetching" step to not break in
> that case, but to me there's something bad going on elsewhere that causes
> this and we have to find and fix that first.

I can still reproduce it on my new laptop with Tumbleweed. Please write me personal email and I'll send you credentials to the laptop so that you can reproduce that.

Ah, thank you for providing access. That helped a lot.

What happened is that you have both kernel version 4.15.0-1.5 and 4.15.0-1.6 installed. Note that this is just a rebuild of the same source, i.e. the packages have identical content. This is something the file conflict checker wasn't dealing with nicely. We never ran into this because it does not happen for distros with an update channel.

So there are two things to improve:

1) it shouldn't check for conflicts between those two packages at all, as both are installed. Fixed with commit 75c833caa57c41110e55aa0de86db80b9a232ef0. This is enough to make the problem go away for your laptop.
2) it shouldn't degrade so much if you want to install an identical package. I'll implement that tomorrow.

Fixed in libsolv-0.6.31 (will require update libzypp + libsolv-tools-0.6.31).

If I read https://github.com/openSUSE/libsolv/commits/master correctly, this should be
fixed in 0.6.*32*

I stand corrected - libsolv-0.6.32

*** Bug 1058242 has been marked as a duplicate of this bug. ***

SUSE-RU-2018:0690-1: An update that has 5 recommended fixes can now be installed.

Category: recommended (low)
Bug References: 1074687,1075449,1076415,1079334,953130
CVE References: 
Sources used:
SUSE Linux Enterprise Software Development Kit 12-SP3 (src):    libsolv-0.6.32-2.8.1, libzypp-16.17.10-2.25.1
SUSE Linux Enterprise Server 12-SP3 (src):    libsolv-0.6.32-2.8.1, libzypp-16.17.10-2.25.1, zypper-1.13.40-21.16.1
SUSE Linux Enterprise Desktop 12-SP3 (src):    libsolv-0.6.32-2.8.1, libzypp-16.17.10-2.25.1, zypper-1.13.40-21.16.1
SUSE CaaS Platform ALL (src):    libsolv-0.6.32-2.8.1, libzypp-16.17.10-2.25.1, zypper-1.13.40-21.16.1

SUSE-RU-2018:0691-1: An update that has 5 recommended fixes can now be installed.

Category: recommended (low)
Bug References: 1074687,1075449,1076415,1079334,953130
CVE References: 
Sources used:
SUSE Linux Enterprise Software Development Kit 12-SP2 (src):    libsolv-0.6.32-2.27.13.1, libzypp-16.17.10-27.44.1
SUSE Linux Enterprise Server for Raspberry Pi 12-SP2 (src):    libsolv-0.6.32-2.27.13.1, libzypp-16.17.10-27.44.1, zypper-1.13.40-18.28.1
SUSE Linux Enterprise Server 12-SP2 (src):    libsolv-0.6.32-2.27.13.1, libzypp-16.17.10-27.44.1, zypper-1.13.40-18.28.1
SUSE Linux Enterprise Desktop 12-SP2 (src):    libsolv-0.6.32-2.27.13.1, libzypp-16.17.10-27.44.1, zypper-1.13.40-18.28.1
OpenStack Cloud Magnum Orchestration 7 (src):    libsolv-0.6.32-2.27.13.1, libzypp-16.17.10-27.44.1, zypper-1.13.40-18.28.1

openSUSE-RU-2018:0700-1: An update that has 5 recommended fixes can now be installed.

Category: recommended (low)
Bug References: 1074687,1075449,1076415,1079334,953130
CVE References: 
Sources used:
openSUSE Leap 42.3 (src):    libsolv-0.6.32-6.1, libzypp-16.17.10-21.1, zypper-1.13.40-17.2

SUSE-RU-2018:1152-1: An update that has 8 recommended fixes can now be installed.

Category: recommended (moderate)
Bug References: 1035946,1036002,1059065,1075978,1077635,1082318,1086602,953130
CVE References: 
Sources used:
SUSE OpenStack Cloud 6 (src):    libsolv-0.6.34-2.42.1, libzypp-15.25.10-46.15.1
SUSE Linux Enterprise Server for SAP 12-SP1 (src):    libsolv-0.6.34-2.42.1, libzypp-15.25.10-46.15.1
SUSE Linux Enterprise Server 12-SP1-LTSS (src):    libsolv-0.6.34-2.42.1, libzypp-15.25.10-46.15.1

I still see this check being extremely slow on Leap 15.0 - should I reopen this or file a separate bug?

I also think its still too slow (you need to test this on a normal HD (no ssd))

Yes, I guess I'm one of the few people still with one of their root disks on spinning platters...

(In reply to H. Hansen from comment #54)
> (you need to test this on a normal HD (no
> ssd))

at least for my original issue that's not true, for me it was 100% cpu bound...

Separate bug, please.