[Patch] Problem with cycle detection

[Jeff Law <law at redhat dot com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


This change:


2011-08-16  Andreas Schwab  <schwab@redhat.com>

        [BZ #11724]
        * elf/dl-deps.c (_dl_map_object_deps): Only assume cycle when
        object is seen twice.
        * elf/dl-fini.c (_dl_sort_fini): Likewise.

Attempted to fix cycle detection, but got it horribly wrong.

We track how often the each object is "seen"  and once an object is
seen more than once, we assume there's a cycle.

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


Fixed thusly:

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJPGEZWAAoJEBRtltQi2kC7OK4H/iOHkciTwP4Ww5OfcUTLCmO8
KCPjQ2P3cJdNHjjTL/AhsuNL4YgatMCbjybc7MVKk6q7XxOF8RoXRBspOG81MEyi
842VtqS+DChBz6xFbPinUERMIMV6X61WMHK6nRYQaTCPNP6zjdKpwD3aP0HNZ7Qx
TngPw0ArJ7hfyhAMiqxjZk4gQ5TA9+eemZfzkvBglbKVVWfNvcl92EiyawXRe9lH
u8p++50JucUpm0+/tDT+74ePa84gsyUUfx/PC/jb+ctpBypDhhS8z35OVFm6mxO2
czwZSulSwptR3e63x+rYUxmP04qtJ++VAj20A9j0c5TT+kxJGTAjQQrj3I7l4p4=
=PakS
-----END PGP SIGNATURE-----

Attachment: test.tar
Description: Unix tar archive

Attachment: P
Description: Text document