From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 004F03851422 for ; Tue, 6 Sep 2022 07:01:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 004F03851422 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1662447713; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=Xhwuyv/8GzhJ2IncI3FAMmBoBvaZwEWNeDf/OpL2asg=; b=BlokUMQgoHrfQCejT/tdqN93kj0zLddknzczd7mzdR1UoqmH74JodmRQghz6SDIH6id8b0 hEVexGDpGXVHMMDnwZukfpYCf3Cl8F3AJK6dE8fKgBV64uEx3UGL0IvYXcS5LPHHDX/riY hMjEZcu8C0ZSa46e4ZCCBPhAvmljodU= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-103-0k_nPeltMmm_oar2Ccfybw-1; Tue, 06 Sep 2022 03:01:52 -0400 X-MC-Unique: 0k_nPeltMmm_oar2Ccfybw-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id D15B6803301 for ; Tue, 6 Sep 2022 07:01:51 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.39.192.109]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 36F6FC15BB3 for ; Tue, 6 Sep 2022 07:01:51 +0000 (UTC) From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH v2] elf: Implement force_first handling in _dl_sort_maps_dfs (bug 28937) Date: Tue, 06 Sep 2022 09:01:49 +0200 Message-ID: <87bkrtasv6.fsf@oldenburg.str.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.85 on 10.11.54.8 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_LOW,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: The implementation in _dl_close_worker requires that the first element of l_initfini is always this very map (=E2=80=9CWe are always the zeroth entry, and since we don't include ourselves in the dependency analysis start at 1.=E2=80=9D). Rather than fixing that assumption, this commit adds an implementation of the force_first argument to the new dependency sorting algorithm. This also means that the directly dlopen'ed shared object is always initialized last, which is the least surprising behavior in the presence of cycles. --- v2: Incorporate Adhemerval's review comments. Retested on i386-linux-gnu and x86_64-linux-gnu. elf/dl-sort-maps.c | 32 +++++++++++++++++++++++--------- elf/dso-sort-tests-1.def | 7 +++++++ 2 files changed, 30 insertions(+), 9 deletions(-) diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c index 5b550b1e94..3e2a6a584e 100644 --- a/elf/dl-sort-maps.c +++ b/elf/dl-sort-maps.c @@ -182,8 +182,9 @@ dfs_traversal (struct link_map ***rpo, struct link_map = *map, =20 static void _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, -=09=09 bool force_first __attribute__ ((unused)), bool for_fini) +=09=09 bool force_first, bool for_fini) { + struct link_map *first_map =3D maps[0]; for (int i =3D nmaps - 1; i >=3D 0; i--) maps[i]->l_visited =3D 0; =20 @@ -208,14 +209,6 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned in= t nmaps, Adjusting the order so that maps[0] is last traversed naturally avoid= s this problem. =20 - Further, the old "optimization" of skipping the main object at maps[0= ] - from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general - no longer valid, since traversing along object dependency-links - may "find" the main object even when it is not included in the initia= l - order (e.g. a dlopen()'ed shared object can have circular dependencie= s - linked back to itself). In such a case, traversing N-1 objects will - create a N-object result, and raise problems. - To summarize, just passing in the full list, and iterating from back to front makes things much more straightforward. */ =20 @@ -274,6 +267,27 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned in= t nmaps, } =20 memcpy (maps, rpo, sizeof (struct link_map *) * nmaps); + + /* Skipping the first object at maps[0] is not valid in general, + since traversing along object dependency-links may "find" that + first object even when it is not included in the initial order + (e.g., a dlopen'ed shared object can have circular dependencies + linked back to itself). In such a case, traversing N-1 objects + will create a N-object result, and raise problems. Instead, + force the object back into first place after sorting. This naive + approach may introduce further dependency ordering violations + compared to rotating the cycle until the first map is again in + the first position, but as there is a cycle, at least one + violation is already present. */ + if (force_first && maps[0] !=3D first_map) + { + int i; + for (i =3D 0; maps[i] !=3D first_map; ++i) +=09; + assert (i < nmaps); + memmove (&maps[1], maps, i * sizeof (maps[0])); + maps[0] =3D first_map; + } } =20 void diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def index 5f7f18ef27..4bf9052db1 100644 --- a/elf/dso-sort-tests-1.def +++ b/elf/dso-sort-tests-1.def @@ -64,3 +64,10 @@ output: b>a>{}b->c->d;d=3D>[ba];c=3D>= a;b=3D>e=3D>a;c=3D>f=3D>b;d=3D>g=3D>c output(glibc.rtld.dynamic_sort=3D1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d= [];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[c>b>a>];+e[e>];+f[f>];+g[g>];+d= [];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[a1;a->a2;a2->a;b->b1;c->a1;c=3D>a1 +output(glibc.rtld.dynamic_sort=3D1): {+a[a2>a1>a>];+b[b1>b>];-b[];%c(a1());}a1>a>];+b[b1>b>];-b[];%c(a1());}