[Patch] Fix cycle detection and initialization order in dynamic loader

[Jeff Law <law at redhat dot com>]

On 06/12/2012 11:44 AM, Roland McGrath wrote:
> > http://sourceware.org/bugzilla/show_bug.cgi?id=13882 - contains a
> > patch.
>
> In fact it contains pointers to archives of this list, where Jeff
> posted patches.
>
> > Last time we discussed the bugs on the mailing list, Roland
> > mentioned that he wanted to review this later. Roland, could you do
> > this now, please? Or anybody else volunteering to review this bug
> > in the dynamic linker?
>
> I don't recall saying that and I don't think I have especially great
> context on this stuff.  I think Jeff should just restart the review
> by posting the minimal patch he wants to get in.

When sorting objects to ensure proper initialization order we terminate
the sort too early resulting in incorrect initialization order for DSOs.

Additionally, the sorting code is limited in the number of DSOs it can
properly handle because it using an array of chars for counts.

--

The sorting code tracks how often the each object is "seen" and once an 
object is seen more than twice, the sort terminates assuming there is a 
cycle in the dependencies.

"seen" is actually a misnomer.  It actually represents the number of
times we have looked at an object to see if there's an object later in
the list for which the current one is a dependency.

So let's assume we have 6 objects.  1 2 3 4 5 6

1 depends on 2
2 depends on 3
3 depends on 4
4 depends on 5
5 depends on 6

At the start of the code to reorder the list and detect cycles, assume
the objects arrive in the following order

1 4 6 5 3 2 (from the link line ordering)

If we trace the changes in the list we'll see the following

1 6 5 3 4 2 (Step #1, move 4 after 3, 4 has been seen once)

1 5 6 3 4 2 (Step #2, move 6 after 5, 6 has been seen once)

1 6 3 4 5 2 (Step #3, move 5 after 4, 5 has been seen once)

1 3 4 5 6 2 (Step #4, move 6 after 5 (again), 6 has been seen twice)

1 4 5 6 2 3 (Step #5, move 3 after 2, 3 has been seen once)

1 5 6 2 3 4 (Step #6, move 4 after 3 (again), 4 has been seen twice)

1 6 2 3 4 5 (Step #7, move 5 after 4 (again), 5 has been seen twice)

At this point the code (erroneously) believes it's hit a cycle as it's
already marked object 6 as being seen twice.

However, there clearly isn't a cycle if you review the dependencies.
Thus, the check for an object already being seen twice is wrong.

Given the same 6 nodes, the pathological case begins with this state

6 5 4 3 2 1

and transitions like this:

5 6 4 3 2 1
6 4 5 3 2 1
4 5 6 3 2 1
5 6 3 4 2 1
6 3 4 5 2 1
3 4 5 6 2 1
4 5 6 2 3 1
5 6 2 3 4 1
6 2 3 4 5 1
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6

Object #6 is moved 5 times.  It's fairly simple to show that for any
given number of objects the worst case scenario is N - 1 moves.

Attachment: patch
Description: Text document

Attachment: test.tar
Description: Unix tar archive