From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19418 invoked by alias); 20 Mar 2012 18:07:07 -0000 Received: (qmail 19398 invoked by uid 22791); 20 Mar 2012 18:07:04 -0000 X-SWARE-Spam-Status: No, hits=-2.8 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from localhost (HELO sourceware.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 20 Mar 2012 18:06:52 +0000 From: "law at redhat dot com" To: glibc-bugs@sources.redhat.com Subject: [Bug dynamic-link/13882] New: Cycle detection in dynamic loader is broken Date: Tue, 20 Mar 2012 18:34:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: glibc X-Bugzilla-Component: dynamic-link X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: law at redhat dot com X-Bugzilla-Status: NEW X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at sourceware dot org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: glibc-bugs-owner@sourceware.org X-SW-Source: 2012-03/txt/msg00264.txt.bz2 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 [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.