[Bug dynamic-link/15310] _dl_sort_fini is O(n^3) causing slow exit when many dsos

["carlos at redhat dot com" <sourceware-bugzilla@sourceware.org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=15310

--- Comment #5 from Carlos O'Donell <carlos at redhat dot com> 2013-03-27 21:00:34 UTC ---
(In reply to comment #3)
> (In reply to comment #2)
> > Don,
> > 
> > I agree that the sorting could be made *far* faster.
> > 
> > Thanks for submitting this. We were well aware that the minimal fix for bug
> > 13882 would cause some kind of performance regression, but it was a balance
> > between a minimal fix and low risk of breakage. I reviewed the patch for 13882
> > and even build a minimal framework for testing that dynamic loader function
> > outside of the build.
> > 
> > Do you have the time to investigate this and propose a patch (requires
> > copyright assignment)?
> 
> I do. I am working on a patch that resolves both this and bug 15311,
> and I'll submit it here in a day or two.

I look forward to the patch.

> I am very interested in what you came up with in the way of a unit
> testing scheme for this function... I could certainly use it.

I aggrandized a bit here. I copied the relevant sorting code out of the loader
code, wrapped it up in a function, created some static arrays to simulate DSOs
loaded in a certain order, and then ran the sorting function against the the
simulated DSO list. The best description is that I ran a simulation. I looked
for the code I used to test bug 13882, but I've lost it (changed employers).

You can see my comments here:
http://sourceware.org/ml/libc-alpha/2012-06/msg00560.html

> I've found it frustrating that the existing tests run by "make check"
> (the ones I saw anyway)
> involve just creating/compiling/running a handful of real programs...
> to really stress test an implementation of _dl_sort_fini properly,
> I'd want to (at least) enumerate all possible graphs
> of up to 3 or 4 nodes, and call it on each of them,
> which would be millions of examples...
> and a few million randomly generated larger examples as well.
> It's *really* easy to get this stuff wrong otherwise.

I fully agree.

As a volunteer project we live and die by the companies and individuals that
choose to contribute to the project. I would be more than happy to see all
possible 3 or 4 node graphs tested. The random testing is more problematic as
you are probably well aware of; you can still auto-generate millions of test
cases just make it deterministic :-)

> Also I'd like to start by moving the init sorting code into a function.
> It looks to me like this code is duplicated in two places (dl-open.c
> and dl-deps.c), and (after the fix for bug 15309)
> it's identical in both places except that
> one of them starts at i0=0 and the other starts at i0=1.
> So this could be expressed cleanly as a new function _dl_sort_init that takes
> i0
> as a parameter.

That sounds like a great idea.

> Should I start by submitting a patch that does that,
> with no functional change, and go from there?  Or should I let you
> or someone else do this refactoring (possibly in conjunction
> with making these sorting functions unit testable)?
> Let me know how to proceed.

Always break the work into as small a piece as conceivably possible. 

Doing just the refactoring is a great first step.

Once we have that in place we can talk about next steps.

The Contribution Checklist for this project is rather long, but we are a
conservative project and it helps to have everything documented and well
specified. You can see the checklist here:
http://sourceware.org/glibc/wiki/Contribution%20checklist

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.