This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [Patch] Fix cycle detection and initialization order in dynamicloader
Jeff,
Many thanks for working through this issue and making sure we
didn't loose this fix in the noise.
I apologize that my review took so long.
In summary:
(a) I have reviewed that your change is correct and fixes
the sorting problems seen with shared objects and
dependencies.
(b) I have verified that the sort works in the
event of cycles.
(c) I verified that I could find no other places where
this incorrect sort algorithm was used.
(d) Pointed out some "bureaucracy" bugs.
The more detailed description:
I've gone through most of dl-deps.c (_dl_map_object_deps) with
a fine toothed comb.
I recreated the sorting loop in a harness outside of glibc
and walked through several sorting use cases and the old code
is just wrong, and your patch fixes that, and that's good.
This bug is a strong argument for unit tests against individual
functions.
It would appear that the original code tries to implement a
non-recursive depth-first topological sort with cycle detection,
but gets it wrong in several respects.
There are performance implications for the undefined case of cycles,
and I'll mention them here, but it really doesn't matter since
good performance would only be achieved by rewriting this code to
use a sensibly studied and proven algorithm (or avoid the undefined
case of libraries with circular dependencies).
In the event of a cycle, which gives undefined initializer
ordering, the number of iterations of the loop can be high
as it cycles through l_initfini until `seen[i + 1] > nlist - i`.
This wasted cycling gets longer the larger the cycle as the
offending vertex has to loop back to near the front of the
list to be seen and detected. Either way it's deterministic
and the point at which the cycle starts always has the highest
seen count and then the iteration terminates.
For example:
6----\
^ |
| |
5 |
^ |
| |
4 |
^ |
| |
3<---|
^
|
2
^
|
1
Still results in a sorting of 1, 2, 3, 4, 5, 6.
With 3, 4, 5, 6 looping until 6, 3 (seen nlist - i time), 4, 5
and a final terminated sequence of 3, 4, 5, 6.
OK with the changes below:
On 6/13/2012 12:32 PM, Jeff Law wrote:
> 2012-06-13 Jeff Law <law@redhat.com>
This is BZ#13882, add that to your ChangeLog, and please update NEWS.
> * 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
Update and merge copyright years.
> @@ -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)
Update and merge copyright years.
> /* 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
Merge copyright years as a courtesy :-)
> @@ -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;
Cheers,
Carlos.
--
Carlos O'Donell
Mentor Graphics / CodeSourcery
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026