Bug 15311 - _dl_sort_fini static deps can be violated by dynamic ones
Summary: _dl_sort_fini static deps can be violated by dynamic ones
Status: NEW
Alias: None
Product: glibc
Classification: Unclassified
Component: dynamic-link (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-03-27 07:49 UTC by Don Hatch
Modified: 2019-04-14 14:46 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security-


Attachments
test case for bug Bug 15311 - patch adding new test "order3" to git master at 3a7182a14b (2.04 KB, patch)
2013-03-28 04:36 UTC, Don Hatch
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Don Hatch 2013-03-27 07:49:25 UTC
_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.
Comment 1 Carlos O'Donell 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?
Comment 2 Don Hatch 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.
Comment 3 Ondrej Bilka 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.
Comment 4 Don Hatch 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.
Comment 5 Don Hatch 2013-03-28 04:36:23 UTC
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.
Comment 6 Don Hatch 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.
Comment 7 Ondrej Bilka 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.
Comment 8 Ondrej Bilka 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.
Comment 9 Don Hatch 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.