This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug dynamic-link/13882] New: Cycle detection in dynamic loader is broken
- From: "law at redhat dot com" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: Tue, 20 Mar 2012 18:06:32 +0000
- Subject: [Bug dynamic-link/13882] New: Cycle detection in dynamic loader is broken
- Auto-submitted: auto-generated
http://sourceware.org/bugzilla/show_bug.cgi?id=13882
Bug #: 13882
Summary: Cycle detection in dynamic loader is broken
Product: glibc
Version: 2.15
Status: NEW
Severity: normal
Priority: P2
Component: dynamic-link
AssignedTo: unassigned@sourceware.org
ReportedBy: law@redhat.com
Classification: Unclassified
The cycle detection and initializer ordering in the dynamic loader is badly
broken.
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.
There is a secondary problem in this code; the "seen" array is an array of
chars and thus we're assuming that we never have more than 128 DSOs that need
ordering. Several executables on my Fedora 16 box already exceed 128 DSOs.
The broken sorting code is replicated in 3 locations:
_dl_map_object_deps, _dl_sort_fini and _dl_open_worker
http://sourceware.org/ml/libc-alpha/2012-01/msg00072.html
http://sourceware.org/ml/libc-alpha/2012-01/msg00080.html
--
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.