This is the mail archive of the glibc-bugs@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]