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

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

[dhatch at ilm dot com]

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.

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

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

[dhatch at ilm dot com]

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

Don Hatch <dhatch at ilm dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

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

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

[carlos at redhat dot com]

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

Carlos O'Donell <carlos at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |carlos at redhat dot com

--- Comment #1 from Carlos O'Donell <carlos at redhat dot com> 2013-03-27 12:59:19 UTC ---
Don,

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

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

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

[dhatch at ilm dot com]

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

--- Comment #2 from Don Hatch <dhatch at ilm dot com> 2013-03-27 20:35:40 UTC ---
(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.

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

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

[neleai at seznam dot cz]

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

--- Comment #3 from Ondrej Bilka <neleai at seznam dot cz> 2013-03-27 22:09:00 UTC ---
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.

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

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

[Ondřej Bílka]

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.

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

[dhatch at ilm dot com]

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.

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

[dhatch at ilm dot com]

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

--- Comment #5 from Don Hatch <dhatch at ilm dot com> 2013-03-28 04:36:23 UTC ---
Created attachment 6954
  --> http://sourceware.org/bugzilla/attachment.cgi?id=6954
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.

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

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

[dhatch at ilm dot com]

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.

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.

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

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

[Ondřej Bílka]

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.

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

[neleai at seznam dot cz]

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

--- Comment #7 from Ondrej Bilka <neleai at seznam dot cz> 2013-03-28 07:37:39 UTC ---
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.

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

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

[Ondřej Bílka]

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.

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

[neleai at seznam dot cz]

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

--- Comment #8 from Ondrej Bilka <neleai at seznam dot cz> 2013-03-28 08:19:12 UTC ---
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.

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

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

[dhatch at ilm dot com]

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

--- Comment #9 from Don Hatch <dhatch at ilm dot com> 2013-03-29 14:53:34 UTC ---
(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.

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

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

[fweimer at redhat dot com]

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

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

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

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
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>

-- 
You are receiving this mail because:
You are on the CC list for the bug.