[Patch] Fix cycle detection and initialization order in dynamic loader
Jeff Law
law@redhat.com
Wed Jun 13 16:32:00 GMT 2012
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.
-------------- next part --------------
2012-06-13 Jeff Law <law@redhat.com>
* elf/dl-deps.c (_dl_map_object_deps): Fix cycle detection. Use
uint16_t for elements in the "seen" array to avoid char overflows.
* elf/dl-fini.c (_dl_sort_fini): Likewise.
* elf/dl-open.c (dl_open_worker): Likewise.
[BZ #14050]
diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index fb1c305..4c69114 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -632,7 +632,7 @@ Filters not supported with LD_TRACE_PRELINKING"));
/* We can skip looking for the binary itself which is at the front
of the search list. */
i = 1;
- char seen[nlist];
+ uint16_t seen[nlist];
memset (seen, 0, nlist * sizeof (seen[0]));
while (1)
{
@@ -658,13 +658,13 @@ Filters not supported with LD_TRACE_PRELINKING"));
(k - i) * sizeof (l_initfini[0]));
l_initfini[k] = thisp;
- if (seen[i + 1] > 1)
+ if (seen[i + 1] > nlist - i)
{
++i;
goto next_clear;
}
- char this_seen = seen[i];
+ uint16_t this_seen = seen[i];
memmove (&seen[i], &seen[i + 1],
(k - i) * sizeof (seen[0]));
seen[k] = this_seen;
diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index 05146b3..8113b1d 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
@@ -38,7 +38,7 @@ _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns)
/* We can skip looking for the binary itself which is at the front
of the search list for the main namespace. */
unsigned int i = ns == LM_ID_BASE;
- char seen[nmaps];
+ uint16_t seen[nmaps];
memset (seen, 0, nmaps * sizeof (seen[0]));
while (1)
{
@@ -78,13 +78,13 @@ _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns)
used[k] = here_used;
}
- if (seen[i + 1] > 1)
+ if (seen[i + 1] > nmaps - i)
{
++i;
goto next_clear;
}
- char this_seen = seen[i];
+ uint16_t this_seen = seen[i];
memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
seen[k] = this_seen;
diff --git a/elf/dl-open.c b/elf/dl-open.c
index 570c5f8..781bc0f 100644
--- a/elf/dl-open.c
+++ b/elf/dl-open.c
@@ -325,7 +325,7 @@ dl_open_worker (void *a)
while (l != NULL);
if (nmaps > 1)
{
- char seen[nmaps];
+ uint16_t seen[nmaps];
memset (seen, '\0', nmaps);
size_t i = 0;
while (1)
@@ -351,13 +351,13 @@ dl_open_worker (void *a)
(k - i) * sizeof (maps[0]));
maps[k] = thisp;
- if (seen[i + 1] > 1)
+ if (seen[i + 1] > nmaps - i)
{
++i;
goto next_clear;
}
- char this_seen = seen[i];
+ uint16_t this_seen = seen[i];
memmove (&seen[i], &seen[i + 1],
(k - i) * sizeof (seen[0]));
seen[k] = this_seen;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.tar
Type: application/x-tar
Size: 10240 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20120613/da821aab/attachment.tar>
More information about the Libc-alpha
mailing list