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

["dhatch at ilm dot com" <sourceware-bugzilla at sourceware dot org>]

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

             Bug #: 15310
           Summary: _dl_sort_fini is O(n^3) causing slow exit when many
                    dsos
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: critical
          Priority: P2
         Component: dynamic-link
        AssignedTo: unassigned@sourceware.org
        ReportedBy: dhatch@ilm.com
    Classification: Unclassified


The fix for Bug 13882 ("Cycle detection in dynamic loader is broken ")
fixed premature termination of the inner loop of _dl_sort_fini,
making the function (closer to) correct,
but it also changes this function's runtime from O(n^2) to O(n^3)
where n is the number of items (resident DSOs) to be sorted.
(The same is true for the corresponding init sorts in dl-open.c and dl-deps.c.)

This can be readily seen by looking at Jeff Law's example
in the description of bug 13882 (a linear chain of dependencies
that _dl_sort_fini needs to completely reverse).
In this case, each of O(n) objects gets moved O(n) times;
furthermore the analysis leading to each such move
(as well as the move itself) takes O(n) time.
That's O(n)*O(n)*O(n) = O(n^3).

Another easy way to get O(n^3) behavior
is with cycles: any node that's part of a nontrivial cycle
is guaranteed to keep getting moved repeatedly until its moved-too-many-times
counter expires, which is O(n) times (for O(n) of the items anyway).
So for example, if the dependency graph consists
of mutually dependent pairs of DSOs:
    A<->B  C<->D  E<->F ...
that will result in O(n^3) run time as well.

We observed the O(n^3) behavior in real life, in our application that had 575
DSOs
upon exit-- in RHEL5.3 (glibc 2.5), it took less than 1 second to exit;
upon upgrading to RHEL6.3 (glibc 2.12), the same app took 15 seconds to exit.
Instrumenting _dl_sort_fini (i.e. putting a counter in it
and printing it at the end) revealed that the innermost loop body
was entered more than 1.7 billion times,
roughly confirming the O(n^3) claim in practice.

This is just a topsort, which can be done simply in O(n) time
with no fancy data structures.

-- 
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.