Bug 15311

Don,

Would you mind mocking up a quick test case for this and attaching it to the issue please?

(In reply to comment #1)
> Would you mind mocking up a quick test case for this and attaching it to the
> issue please?

sure, I have one... I'll attach it as soon as I get it properly disentangled
from my git repo.

On Wed, Mar 27, 2013 at 07:49:25AM +0000, dhatch at ilm dot com wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=15311
> 
>              Bug #: 15311
>            Summary: _dl_sort_fini static deps can be violated by dynamic
>                     ones
>            Product: glibc
>            Version: unspecified
>             Status: NEW
>           Severity: normal
>           Priority: P2
>          Component: dynamic-link
>         AssignedTo: unassigned@sourceware.org
>         ReportedBy: dhatch@ilm.com
>     Classification: Unclassified
> 
> 
> _dl_sort_fini tries to honor static dependencies
> at the expense of relocation (dynamic) dependencies, when there is a conflict.
> But the code that does this is rather half-hearted--
> it only ignores a dynamic dependency
> if the dynamic dependency directly contradicts
> a single static dependency, per the following comment
> in the loop over dynamic dependencies in elf/dl-fini.c:
>     /* If a cycle exists with a link time dependency,
>        preserve the latter.  */  
> 
> In even slightly more complex situations,
> e.g. a mixed cycle of length 3 (consisting of at least one 
> static and at least one dynamic dependency),
> no preference is given to the static dep(s);
> the cycle is broken arbitrarily and so the static dep may be violated,
> even if there are no cycles at all in the static dependency graph.
> 
> If static dependencies really are more important than dynamic ones,
> it might be a good idea to give them preference in a more principled way.
> 
> If the sorting routine gets overhauled
> (as I think it needs to be, due to currently absurd asymptotic behavior,
> see bug 15310)
> it would be good to keep this in mind.
> 
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.

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

Created attachment 6954 [details]
test case for bug Bug 15311 - patch adding new test "order3" to git master at 3a7182a14b

/*
  Test case for bug 15311 "_dl_sort_fini static deps can be violated by dynamic ones".

  Static dependencies: 1->2->3->4
  Dynamic dependencies: 4->2, 4->1, 3->1, 2->21->1, 3->32->2, 4->43->3
  The static dependencies are acyclic, so they should all be honored.
  Every dynamic dependency takes part in contradicting static dependencies,
  so they should all be ignored.

  Output should be "4{2{21{1{}}}1{}43{3{1{}32{2{21{1{}}}}}}}0123456"
  (the curly brace stuff just verifies the test is set up correctly;
  the 0123456 at the end shows that _dl_sort_fini got the fini right order).
*/

The current implementation has very little chance of getting it right--
its output ends in 0134256.

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

Hi Ondrej,

I'm sorry, I just realized that in my previous reply to this comment of yours,
I outlined my strategy without actually addressing your simpler proposal at all.

I don't think what you are suggesting will work.
If I'm reading it correctly, you're saying that, when iterating through
the successors of a given node, consider static successors first
and dynamic onces after that.

Here is an example where that doesn't work:
    Static dependencies: A->B->C->D->E
    Dynamic dependencies: E->A
In this case each node has exactly one successor (static or dynamic),
so the order in which successors are considered clearly makes no difference.
If the depth-first-search happens to start at C,
it will produce the output (reverse postordering): C D E A B.
The correct answer is A B C D E.

My strategy works properly on this example (of course :-)):
first pass (topsort static+dynamic) produces arbitrary output,
since it's all one big SCC;
second pass (topsort static only) produces correct order A B C D E.

On Thu, Mar 28, 2013 at 05:00:18AM +0000, dhatch at ilm dot com wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=15311
> 
> --- Comment #6 from Don Hatch <dhatch at ilm dot com> 2013-03-28 05:00:18 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.
> 
> Hi Ondrej,
> 
> I'm sorry, I just realized that in my previous reply to this comment of yours,
> I outlined my strategy without actually addressing your simpler proposal at
> all.
> 
> I don't think what you are suggesting will work.
> If I'm reading it correctly, you're saying that, when iterating through
> the successors of a given node, consider static successors first
> and dynamic onces after that.
>
That was late at nigth and I simplified too much. 
My original alg. was 
1. topsort dynamic and static, get order o.
2. do dfs on static, get tree and repeately output and remove leaf minimal in o.

I realized it matters in which order we consider dependencies. Naturaly
dynamic deps come after static.

Why should we simply add timestamp when object is created and use it to
call destructors in reverse order.

(In reply to comment #7) 
> My original alg. was 
> 1. topsort dynamic and static, get order o.
> 2. do dfs on static, get tree and repeately output and remove leaf minimal in o.

So it's like mine except your second pass is a topsort by simple dfs
(reverse postordering)
rather than an SCC-coherent topsort like Kosaraju's or Tarjan's, for some reason.
SCC-coherent is better.
For example, say the edges are 0 <-> 1 -> 2, then dfs can produce 1 2 0...
we'd prefer either of 0 1 2 or 1 0 2 instead, since we'd like 0 to come before 2.
In general whenever (A ->* B and not B ->* A),
A should come before B in the output order.

The master branch has been updated by Adhemerval Zanella <azanella@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=e6fd79f3795d46dfb583e124be49fc063bc3d58b

commit e6fd79f3795d46dfb583e124be49fc063bc3d58b
Author: Chung-Lin Tang <cltang@codesourcery.com>
Date:   Thu Oct 21 21:41:21 2021 +0800

    elf: Testing infrastructure for ld.so DSO sorting (BZ #17645)
    
    This is the first of a 2-part patch set that fixes slow DSO sorting behavior in
    the dynamic loader, as reported in BZ #17645. In order to facilitate such a
    large modification to the dynamic loader, this first patch implements a testing
    framework for validating shared object sorting behavior, to enable comparison
    between old/new sorting algorithms, and any later enhancements.
    
    This testing infrastructure consists of a Python script
    scripts/dso-ordering-test.py' which takes in a description language, consisting
    of strings that describe a set of link dependency relations between DSOs, and
    generates testcase programs and Makefile fragments to automatically test the
    described situation, for example:
    
      a->b->c->d          # four objects linked one after another
    
      a->[bc]->d;b->c     # a depends on b and c, which both depend on d,
                          # b depends on c (b,c linked to object a in fixed order)
    
      a->b->c;{+a;%a;-a}  # a, b, c serially dependent, main program uses
                          # dlopen/dlsym/dlclose on object a
    
      a->b->c;{}!->[abc]  # a, b, c serially dependent; multiple tests generated
                          # to test all permutations of a, b, c ordering linked
                          # to main program
    
     (Above is just a short description of what the script can do, more
      documentation is in the script comments.)
    
    Two files containing several new tests, elf/dso-sort-tests-[12].def are added,
    including test scenarios for BZ #15311 and Redhat issue #1162810 [1].
    
    Due to the nature of dynamic loader tests, where the sorting behavior and test
    output occurs before/after main(), generating testcases to use
    support/test-driver.c does not suffice to control meaningful timeout for ld.so.
    Therefore a new utility program 'support/test-run-command', based on
    test-driver.c/support_test_main.c has been added. This does the same testcase
    control, but for a program specified through a command-line rather than at the
    source code level. This utility is used to run the dynamic loader testcases
    generated by dso-ordering-test.py.
    
    [1] https://bugzilla.redhat.com/show_bug.cgi?id=1162810
    
    Signed-off-by: Chung-Lin Tang  <cltang@codesourcery.com>
    Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>