spends 10+ minutes deduplicating Package lists

[Vagrant Cascadian]

[Impact] The netboot installer is unreasonably slow to deduplicate udeb Packages files retrieved from the network, scaling (at least) quadratically in the number of packages with a bad constant factor.
[Test Case] Run a netboot installer built with the new net-retriever (we'll put one in -proposed at some point after this SRU is reviewed and accepted, and post the URLs to this bug). It should work and should not take unreasonable time around the "Download installer components" stage.
[Regression Potential] Cannot affect anything other than netboot installations. I've compared the output against the old code for a sample Packages file provided by Michael and made sure it's identical; but if this goes wrong then the most likely result is a partitioning failure, or perhaps a complaint that no suitable kernel versions are available (although this can happen for other reasons, e.g. forgetting "apt-setup/proposed=true" for an image built against the kernel in -proposed).

Original report follows;

At some point after Lucid's initial release, the ubuntu alternate installer seems to stall for a very long time (10+ minutes) before the partitioning menu comes up. I don't think it was happening for the first year or so after Lucid's release, but I'm not real clear on when it started happening (it was only recently brought to my attention).

I think it is happening in /usr/lib/debian-installer/net-retriever's deduplicate function...
When it is stalled out, it keeps adding content to /tmp/net-retriever-NNNN-deduplicate/, eventually it moves on, but it takes forever. The speed of the install machine doesn't appear to matter much.
There's nothing obvious in the log as to why it's stalling at that point...

I thought it might be some issue with our preseeding, but it appears to happen on an install without preseeding as well.

Newer versions of Ubuntu (at least Xubuntu 12.04) don't seem to experience this problem, as far as I can tell.

We're using the netboot installer, apparently last updated on 2011-04-29:

2011-04-29 03:32:27-07:00 checking for updates: http://us.archive.ubuntu.com/ubuntu/dists/lucid/main/installer-i386/current/images/netboot/netboot.tar.gz
2011-04-29 03:33:13-07:00 updated: /var/lib/tftpboot/ubuntu-installer/lucid.i386.netboot.tar.gz

though as far as i can tell, that file hasn't been updated on the mirrors since 2010-04-25.

live well,
  vagrant

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[Narinder Gupta (narindergupta)]

I saw the same behavior in UBuntu 12.04 as well where net-retriever is stuck of 10+ minutes. I am attaching the installer logs on moonshot cartridges from MAAS which will give you no reason to be there. It will be great if someone can work on it and will help rectifying the issue.

[Michael Casadevall (mcasadevall)]

I've encountered this issue on armhf across multiple series. This bug seems to come and go, as it currently only happens for my on x86-based systems, and I'm not currently encountering it on ARM, but the reverse has been true for me as well.

[Jian Wen (wenjianhn)]

It took a virtual machine more than half an hour to finish it.

Ubuntu 12.04.2

Jul 5 10:27:38 192-168-64-105.master net-retriever:
Jul 5 10:27:41 192-168-64-105.master net-retriever: gpgv:
Jul 5 10:27:41 192-168-64-105.master net-retriever: Signature made Thu Jul 4 12:31:39 2013 UTC using DSA key ID 437D05B5
Jul 5 10:27:41 192-168-64-105.master net-retriever: gpgv:
Jul 5 10:27:41 192-168-64-105.master net-retriever: Good signature from "Ubuntu Archive Automatic Signing Key <email address hidden>"
Jul 5 10:27:41 192-168-64-105.master net-retriever:
Jul 5 10:28:40 192-168-64-105.master init: starting pid 278, tty '/dev/tty3': '-/bin/sh'
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext2-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext3-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext4-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (btrfs-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (crypto-dm-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext2-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext3-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (ext4-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (btrfs-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: resolver (crypto-dm-modules): package doesn't exist (ignored)
Jul 5 11:01:43 192-168-64-105.master anna[3727]: DEBUG: retrieving apt-mirror-setup 1:0.55ubuntu4
Jul 5 11:01:44 192-168-64-105.master anna[3727]: DEBUG: retrieving apt-setup-udeb 1:0.55ubuntu4
Jul 5 11:01:46 192-168-64-105.master anna[3727]: DEBUG: retrieving base-installer 1.122ubuntu7.2
Jul 5 11:01:47 192-168-64-105.master anna[3727]: DEBUG: retrieving block-modules-3.2.0-23-generic-di 3.2.0-23.36
Jul 5 11:01:48 192-168-64-105.master anna[3727]: DEBUG: retrieving bootstrap-base 1.122ubuntu7.2

[Launchpad Janitor (janitor)]

This bug was fixed in the package net-retriever - 1.33ubuntu2

---------------
net-retriever (1.33ubuntu2) saucy; urgency=low

  * Deduplicate Packages files entirely in C, massively speeding it up for
    large files (LP: #1067934).
 -- Colin Watson <email address hidden> Tue, 16 Jul 2013 13:13:15 +0100

[Adam Conrad (adconrad)]

Hello Vagrant, or anyone else affected,

Accepted net-retriever into lucid-proposed. The package will build now and be available at http://launchpad.net/ubuntu/+source/net-retriever/1.24ubuntu2.1 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, and change the tag from verification-needed to verification-done. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed. In either case, details of your testing will help us make a better decision.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

[Adam Conrad (adconrad)]

Rejected for quantal and raring, they can be resurrected from the queue if anyone desperately needs them fixed.

[Vagrant Cascadian (vagrantc)]

Works for me using http://us.archive.ubuntu.com/ubuntu/dists/precise-proposed/main/installer-i386/current/images/netboot/netboot.tar.gz. "current" appears, as best I can tell, to be a symlink to "20101020ubuntu136.10".

It deduplicates very quickly.

Using the netboot images from precise still stall on the deduplication step.

[Vagrant Cascadian (vagrantc)]

Was unable to successfully test with lucid using version 20081029ubuntu102.17 downloaded from:

http://us.archive.ubuntu.com/ubuntu/dists/lucid-proposed/main/installer-i386/current/images/netboot/netboot.tar.gz

Though that image is dated from May 20th, so perhaps is to old to contain the fix.

Not really using lucid at all anymore, but can fairly easily test it if an updated image is made available.

[Javier López (javier-lopez)]

I hitted this bug using initrd.gz & linuz files from precise-update at July 31th, 2013, the files in:

http://us.archive.ubuntu.com/ubuntu/dists/precise-proposed/main/installer-i386/current/images/netboot/netboot.tar.gz

Worked for me as well, the netinstall process never finished with the original files, I didn't waited more that 5 minutes, though.

[Colin Watson (cjwatson)]

Vagrant: I updated the lucid-proposed images you mentioned, now 20081029ubuntu102.18; I'd appreciate a test run with those.

[Vagrant Cascadian (vagrantc)]

Tested the new lucid-proposed netboot image, and it appears to work great.

So both precise and lucid proposed updates seem to fix the issue for me.

[Ryan Tandy (rtandy)]

lucid-proposed/20081029ubuntu102.18 and precise-proposed/20101020ubuntu136.10 both work well for me. Thanks for working on this Colin; it's been a long-standing annoyance.

[Launchpad Janitor (janitor)]

This bug was fixed in the package net-retriever - 1.24ubuntu2.1

---------------
net-retriever (1.24ubuntu2.1) lucid; urgency=low

  * Deduplicate Packages files entirely in C, massively speeding it up for
    large files (LP: #1067934).
 -- Colin Watson <email address hidden> Tue, 16 Jul 2013 13:27:08 +0100

[Colin Watson (cjwatson)]

The verification of this Stable Release Update has completed successfully and the package has now been released to -updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regresssions.

[Launchpad Janitor (janitor)]

This bug was fixed in the package net-retriever - 1.29ubuntu1.1

---------------
net-retriever (1.29ubuntu1.1) precise; urgency=low

  * Deduplicate Packages files entirely in C, massively speeding it up for
    large files (LP: #1067934).
 -- Colin Watson <email address hidden> Tue, 16 Jul 2013 13:27:54 +0100

[Norberto Bensa (nbensa)]

Hello,

tested on Lucid net-install. Deduplicate takes only seconds in a virtual environment.

Thanks!

[Stuart Longland (redhatter)]

Silly question, has this fix made it into the current netboot images for Ubuntu 12.04 on AMD64 and i686?

I just downloaded the latest netboot images, even tried the ones in the -proposed directory, and I'm still getting a long pause from my netboot images.

[Colin Watson (cjwatson)]

It's in the images in -updates and -proposed, yes - there's a udeb.list
file alongside the images (possibly a level or two up) that you can use
to check versions. Exactly which image (URL) are you using, and do you
have an installer log?

[Stuart Longland (redhatter)]

Hi, Apologies for the delay. I've been on other projects and only just got back to this one.

We're using the files from http://au.archive.ubuntu.com/pub/ubuntu/archive/dists/precise-proposed/main/installer-amd64/current/images/netboot/netboot.tar.gz

I'm downloading the latest copy of that now, and will give it another shot. I'll let you know if this fixes the problem.

[Stuart Longland (redhatter)]

That seems to have fixed it at long last. We've got a rather complicated boot menu system so out of those netboot tarballs, I just grab initrd.gz and linux files, and place them in a common directory tree so we can deploy various i686 and AMD64 distributions by picking them from a menu.

The broken files had the checksums:
59fcdc4f29fdc3ff08d24b96ef28151f3988a9ff initrd.gz
fba53798707c7278334a5402453586bed216de20 linux

The working ones had the checksums:
54c80dd94b0f22f4a51df70502bcfff7c29d42b4 initrd.gz
76a613634ff1c595b2e279af99bd88bff4a46404 linux

[Xizhen Du (xizhendu)]

The issue is still happening to me with 12.04.5 (amd64), with the latest netboot{.iso|tar.gz} from CC.archive.

[Colin Watson (cjwatson)]

Xizhen Du (#22): You must always state the exact URL you used. My guess is that you used one from .../precise/... rather than .../precise-updates/..., which means you're effectively using 12.04.0 rather than 12.04.5. There are up-to-date files linked from http://cdimage.ubuntu.com/netboot/precise/.