bin/116452: pkg_create uses bogosort?

[Garrett Wollman]

>Number:         116452
>Category:       bin
>Synopsis:       pkg_create uses bogosort?
>Confidential:   no
>Severity:       non-critical
>Priority:       high
>Responsible:    freebsd-bugs
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          sw-bug
>Submitter-Id:   current-users
>Arrival-Date:   Wed Sep 19 02:50:01 GMT 2007
>Closed-Date:
>Last-Modified:
>Originator:     Garrett Wollman
>Release:        FreeBSD 6.2-RELEASE-p3 i386
>Organization:
>Environment:
System: FreeBSD hergotha.csail.mit.edu 6.2-RELEASE-p3 FreeBSD 6.2-RELEASE-p3 #5: Sun Mar 18 00:59:50 EDT 2007 wollman at hergotha.csail.mit.edu:/usr/obj/usr/src/sys/HERGOTHA i386


>Description:

	pkg_create makes an insane number of pointless filesystem
	operations (quadratic? exponential?) when being run as part of
	the "Registering installation" step of a port install.
	It is definitely a function of the number of ports installed,
	as it has gotten much worse since X was fragmented into 200
	separate packages.  ktrace shows:

[root at hergotha /home/wollman]# kdump -t n | wc -l
  937814
[root at hergotha /home/wollman]# kdump -t n | sort -u | wc -l
    1023

	(This is actually only a partial ktrace, started about halfway
	through the process.)  What it is actually trying to do, I do
	not know.  A representative sample from the trace:

 97936 pkg_create CALL  lstat(0xbfbfbe20,0xbfbfb990)
 97936 pkg_create NAMI  "/var/db/pkg/glitz-0.5.6_1"
 97936 pkg_create RET   lstat 0
 97936 pkg_create CALL  access(0xbfbfbe20,0x4)
 97936 pkg_create NAMI  "/var/db/pkg/glitz-0.5.6_1"
 97936 pkg_create RET   access 0
 97936 pkg_create CALL  stat(0xbfbfba20,0xbfbfb990)
 97936 pkg_create NAMI  "/var/db/pkg/glitz-0.5.6_1/+CONTENTS"
 97936 pkg_create RET   stat 0
 97936 pkg_create CALL  access(0xbfbfba20,0x4)
 97936 pkg_create NAMI  "/var/db/pkg/glitz-0.5.6_1/+CONTENTS"
 97936 pkg_create RET   access 0

>How-To-Repeat:
	Install an already-compiled port on a machine that has lots of
	packages.  Wait a few minutes.  Wonder why it's not done yet.

>Fix:

	Either use a less-stupid algorithm or at least memoize the
	result of whatever it's trying to do with this sequence of
	calls.

>Release-Note:
>Audit-Trail:
>Unformatted: