[Bug dynamic-link/15311] _dl_sort_fini static deps can be violated by dynamic ones

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

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

--- Comment #4 from Don Hatch <dhatch at ilm dot com> 2013-03-27 22:39:57 UTC ---
(In reply to comment #3)
> If you do topologic sort it should suffice to take static dependency
> edges before dynamic ones, it assures that static when static are acyclic then
> they are always correctly ordered.

I'm working on a patch that simultaneously addresses this
and bug 15310.

My plan is to do two passes of topsort:
    first pass: sort on both static an dynamic dependencies
    second pass: sort on static dependencies only
making sure to use an implementation of topsort that is "stable",
so that the second pass only reorders things where it needs to correct
out-of-ordernesses left by the first pass.

Also, for each topsort, I'm using Tarjan's SCC algorithm
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
(rather than just a simple reverse postordering)
to guarantee that the SCCs end up contiguous,
in both passes (this is different, and arguably better,
than just breaking cycles arbitrarily by ignoring back-edges encountered
in the depth-first search... it also allows us to prove some
nice properties of the result of the two passes).

The result is well-defined (the problem wasn't really well-defined before)
and well-behaved in some desireable ways that I'll document more fully
in the code comments.

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