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 dynamic loader
On Wednesday, June 13, 2012 10:32:10 Jeff Law wrote:
> 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.
The patch itself looks fine to me and has been tested by (at least)
Fedora and openSUSE, so I propose to add it to glibc on Wednesday if
nobody speaks up with any issues.
Is there anybody volunteering to integrate the test properly? I would
appreciate it!
Andreas
--
Andreas Jaeger aj@{suse.com,opensuse.org} Twitter/Identica: jaegerandi
SUSE LINUX Products GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany
GF: Jeff Hawn,Jennifer Guild,Felix Imendörffer,HRB16746 (AG Nürnberg)
GPG fingerprint = 93A3 365E CE47 B889 DF7F FED1 389A 563C C272 A126