Re: [Patch] Fix cycle detection and initialization order in dynamic loader

[Andreas Jaeger <aj at suse dot com>]

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