From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27690 invoked by alias); 16 Aug 2011 11:13:10 -0000 Received: (qmail 27671 invoked by uid 22791); 16 Aug 2011 11:13:09 -0000 X-SWARE-Spam-Status: No, hits=-6.1 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD,SARE_BAYES_5x8,SARE_BAYES_6x8,SPF_HELO_PASS,TW_AV,TW_LV X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 16 Aug 2011 11:12:46 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p7GBCjYo017288 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Tue, 16 Aug 2011 07:12:45 -0400 Received: from hase.home (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p7GBCihx027129 for ; Tue, 16 Aug 2011 07:12:45 -0400 From: Andreas Schwab To: libc-hacker@sourceware.org Subject: [PATCH] Correct cycle detection during dependency sorting X-Yow: Once, there was NO fun... This was before MENU planning, FASHION statements or NAUTILUS equipment... Then, in 1985.. FUN was completely encoded in this tiny MICROCHIP.. It contain 14,768 vaguely amusing SIT-COM pilots!! We had to wait FOUR BILLION years but we finally got JERRY LEWIS, MTV and a large selection of cream-filled snack cakes! Date: Tue, 16 Aug 2011 11:13:00 -0000 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Mailing-List: contact libc-hacker-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-hacker-owner@sourceware.org X-SW-Source: 2011-08/txt/msg00005.txt.bz2 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. * elf/Makefile (distribute): Add tst-initorder2.c. (tests): Add tst-initorder2. (modules-names): Add tst-initorder2a tst-initorder2b tst-initorder2c tst-initorder2d. Add rules to build them. ($(objpfx)tst-initorder2.out): New rule. * elf/tst-initorder2.c: New file. * elf/tst-initorder2.exp: New file. --- elf/Makefile | 29 ++++++++++++++++++++++++----- elf/dl-deps.c | 13 +++++++------ elf/dl-fini.c | 15 ++++++++------- elf/tst-initorder2.c | 20 ++++++++++++++++++++ elf/tst-initorder2.exp | 9 +++++++++ 5 files changed, 68 insertions(+), 18 deletions(-) create mode 100644 elf/tst-initorder2.c create mode 100644 elf/tst-initorder2.exp diff --git a/elf/Makefile b/elf/Makefile index 1897094..482d8a4 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -121,9 +121,10 @@ distribute := rtld-Rules \ ifuncmain7pie.c ifuncmain7static.c \ tst-unique1.c tst-unique1mod1.c tst-unique1mod2.c \ tst-unique2.c tst-unique2mod1.c tst-unique2mod2.c \ - tst-initordera1.c tst-initordera2.c tst-initorderb1.c \ - tst-initorderb2.c tst-initordera3.c tst-initordera4.c \ - tst-initorder.c + tst-initordera1.c tst-initordera2.c tst-initorderb1.c \ + tst-initorderb2.c tst-initordera3.c tst-initordera4.c \ + tst-initorder.c \ + tst-initorder2.c CFLAGS-dl-runtime.c = -fexceptions -fasynchronous-unwind-tables CFLAGS-dl-lookup.c = -fexceptions -fasynchronous-unwind-tables @@ -229,7 +230,7 @@ tests += loadtest restest1 preloadtest loadfail multiload origtest resolvfail \ tst-audit1 tst-audit2 \ tst-stackguard1 tst-addr1 tst-thrlock \ tst-unique1 tst-unique2 tst-unique3 tst-unique4 \ - tst-initorder + tst-initorder tst-initorder2 # reldep9 test-srcs = tst-pathopt selinux-enabled := $(shell cat /selinux/enforce 2> /dev/null) @@ -293,7 +294,8 @@ modules-names = testobj1 testobj2 testobj3 testobj4 testobj5 testobj6 \ tst-unique4lib \ tst-initordera1 tst-initorderb1 \ tst-initordera2 tst-initorderb2 \ - tst-initordera3 tst-initordera4 + tst-initordera3 tst-initordera4 \ + tst-initorder2a tst-initorder2b tst-initorder2c tst-initorder2d ifeq (yes,$(have-initfini-array)) modules-names += tst-array2dep tst-array5dep endif @@ -1168,6 +1170,23 @@ $(objpfx)tst-initorder.out: $(objpfx)tst-initorder $< > $@ cmp $@ tst-initorder.exp > /dev/null +$(objpfx)tst-initorder2: $(objpfx)tst-initorder2a.so $(objpfx)tst-initorder2d.so $(objpfx)tst-initorder2c.so +$(objpfx)tst-initorder2a.so: $(objpfx)tst-initorder2b.so +$(objpfx)tst-initorder2b.so: $(objpfx)tst-initorder2c.so +$(objpfx)tst-initorder2c.so: $(objpfx)tst-initorder2d.so +define o-iterator-doit +$(objpfx)tst-initorder2$o.os: tst-initorder2.c; \ +$$(compile-command.c) -DNAME=\"$o\" +endef +object-suffixes-left := a b c d +include $(o-iterator) + +$(objpfx)tst-initorder2.out: $(objpfx)tst-initorder2 + $(elf-objpfx)${rtld-installed-name} \ + --library-path $(rpath-link)$(patsubst %,:%,$(sysdep-library-path)) \ + $< > $@ + cmp $@ tst-initorder2.exp > /dev/null + ifeq (yes,$(config-cflags-avx)) AVX-CFLAGS=-mavx ifeq (yes,$(config-cflags-novzeroupper)) diff --git a/elf/dl-deps.c b/elf/dl-deps.c index bbb3d85..ddbf3e7 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -623,12 +623,12 @@ 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; - bool seen[nlist]; - memset (seen, false, nlist * sizeof (seen[0])); + char seen[nlist]; + memset (seen, 0, nlist * sizeof (seen[0])); while (1) { /* Keep track of which object we looked at this round. */ - seen[i] = true; + ++seen[i]; struct link_map *thisp = l_initfini[i]; /* Find the last object in the list for which the current one is @@ -649,15 +649,16 @@ Filters not supported with LD_TRACE_PRELINKING")); (k - i) * sizeof (l_initfini[0])); l_initfini[k] = thisp; - if (seen[i + 1]) + if (seen[i + 1] > 1) { ++i; goto next_clear; } + char this_seen = seen[i]; memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0])); - seen[k] = true; + seen[k] = this_seen; goto next; } @@ -668,7 +669,7 @@ Filters not supported with LD_TRACE_PRELINKING")); if (++i == nlist) break; next_clear: - memset (&seen[i], false, (nlist - i) * sizeof (seen[0])); + memset (&seen[i], 0, (nlist - i) * sizeof (seen[0])); next:; } diff --git a/elf/dl-fini.c b/elf/dl-fini.c index 0a138e9..7cb3a3d 100644 --- a/elf/dl-fini.c +++ b/elf/dl-fini.c @@ -39,12 +39,12 @@ _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; - bool seen[nmaps]; - memset (seen, false, nmaps * sizeof (seen[0])); + char seen[nmaps]; + memset (seen, 0, nmaps * sizeof (seen[0])); while (1) { /* Keep track of which object we looked at this round. */ - seen[i] = true; + ++seen[i]; struct link_map *thisp = maps[i]; /* Do not handle ld.so in secondary namespaces and object which @@ -79,14 +79,15 @@ _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns) used[k] = here_used; } - if (seen[i + 1]) + if (seen[i + 1] > 1) { ++i; goto next_clear; } + char this_seen = seen[i]; memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0])); - seen[k] = true; + seen[k] = this_seen; goto next; } @@ -96,7 +97,7 @@ _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns) unsigned int m = maps[k]->l_reldeps->act; struct link_map **relmaps = &maps[k]->l_reldeps->list[0]; - /* Look through the relocation dependencies of the object. */ + /* Look through the relocation dependencies of the object. */ while (m-- > 0) if (__builtin_expect (relmaps[m] == thisp, 0)) goto move; @@ -109,7 +110,7 @@ _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns) if (++i == nmaps) break; next_clear: - memset (&seen[i], false, (nmaps - i) * sizeof (seen[0])); + memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0])); next:; } diff --git a/elf/tst-initorder2.c b/elf/tst-initorder2.c new file mode 100644 index 0000000..050f956 --- /dev/null +++ b/elf/tst-initorder2.c @@ -0,0 +1,20 @@ +#include + +#ifndef NAME +int +main (void) +{ + puts ("main"); +} +#else +static void __attribute__ ((constructor)) +init (void) +{ + puts ("init: " NAME); +} +static void __attribute__ ((destructor)) +fini (void) +{ + puts ("fini: " NAME); +} +#endif diff --git a/elf/tst-initorder2.exp b/elf/tst-initorder2.exp new file mode 100644 index 0000000..5169489 --- /dev/null +++ b/elf/tst-initorder2.exp @@ -0,0 +1,9 @@ +init: d +init: c +init: b +init: a +main +fini: a +fini: b +fini: c +fini: d -- 1.7.6 -- Andreas Schwab, schwab@redhat.com GPG Key fingerprint = D4E8 DBE3 3813 BB5D FA84 5EC7 45C6 250E 6F00 984E "And now for something completely different."