From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-delivery-1.mimecast.com [207.211.31.120]) by sourceware.org (Postfix) with ESMTP id C17653857C58 for ; Sat, 25 Jul 2020 20:57:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org C17653857C58 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-79-bAOwBLN6NEqJYI3TYI69UQ-1; Sat, 25 Jul 2020 16:57:36 -0400 X-MC-Unique: bAOwBLN6NEqJYI3TYI69UQ-1 Received: by mail-qt1-f200.google.com with SMTP id h24so8562408qtk.18 for ; Sat, 25 Jul 2020 13:57:36 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:organization :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=SS+CvAGdCmwMHqJ8fhIDw2fFWiCQJd5K3OyzH6TYuv0=; b=WxeV3fUgPg3MUy/kkWW/hIyZBbsCZVCsk7DX0sw0z9PK17cdvYa9vZTEmC9U8iMvyR 2a0Nvgljt/7IyunVSCx6nM+u2SQgCDjtjJyS1LIToLCORHXBUUZZ7esuS1+6VR61a06W 6qdnJQweR4AVDRjVALV98FcNPOwOmFcehzkS1UOGuBVF40ht53O2fzX2gEhjFyKtslXF 5GHGx5IODAenqgxNGn1E832bgR8sLibAJIuyNmTVdL2Oc1FUcq+G27bwns5Fnu9VGBOF w54OMB8c/6bJpKLke+DZ11Mv2qyNyC8438FKdE9MmWkomOsTquq38rHe5z0RjtFA/mSm go3Q== X-Gm-Message-State: AOAM532HUKatDgEUSMUiFrSBEqfamULIy1hXjdtEBV6/4wwYIHhyqBUW 8LsVY0pm8+9ddII3qH7WsgMuaHqecNbcJAwweKOPqPzFt6WNNVRcfmVHRtHviYfYkv1VONKOU7g ZmL0ZdWeKFSPWyT2MK/ZL X-Received: by 2002:a05:620a:1424:: with SMTP id k4mr7791823qkj.2.1595710656319; Sat, 25 Jul 2020 13:57:36 -0700 (PDT) X-Google-Smtp-Source: ABdhPJz3lcUjIHVseNeWdmMqwb1o5qsWIW+/uwMEiohvO3HOLKNtoWXsQ5zQhKfRG0uJtgXREPjdhA== X-Received: by 2002:a05:620a:1424:: with SMTP id k4mr7791813qkj.2.1595710656045; Sat, 25 Jul 2020 13:57:36 -0700 (PDT) Received: from [192.168.1.4] (198-84-170-103.cpe.teksavvy.com. [198.84.170.103]) by smtp.gmail.com with ESMTPSA id y143sm12677426qka.22.2020.07.25.13.57.33 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 25 Jul 2020 13:57:34 -0700 (PDT) Subject: Re: [PATCH] elf: Sort only uninitialized objects in _dl_map_object_deps() To: Xiaoming Ni , libc-alpha@sourceware.org, brooks@gcc.gnu.org, ppluzhnikov@google.com, neleai@seznam.cz, marat@slonopotamus.org Cc: wangle6@huawei.com References: <20200725105205.103328-1-nixiaoming@huawei.com> From: Carlos O'Donell Organization: Red Hat Message-ID: <8a15102b-c461-23e2-21d4-f2f7b2b78682@redhat.com> Date: Sat, 25 Jul 2020 16:57:33 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0 MIME-Version: 1.0 In-Reply-To: <20200725105205.103328-1-nixiaoming@huawei.com> Content-Language: en-US X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-11.5 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_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 25 Jul 2020 20:57:43 -0000 On 7/25/20 6:52 AM, Xiaoming Ni wrote: > TIS ELF Version 1.2 > Initialization and Termination Functions: > 1. Before the initialization code for any object A is called, the > initialization code for any other objects that object A depends > on are called. > 2. The order in which the dynamic linker calls termination functions > is the exact reverse order of their corresponding initialization > functions. > 3. The dynamic linker ensures that it will not execute any > initialization or termination functions more than once. > > According to 1 and 2: _dl_sort_maps() is used for sorting when dlopen/dlclose. > According to 3: At dlopen, only the uninitialized objects need to be sorted. Thank you for posting this. It will take a while to review this, and we're currently frozen for the release on August 3rd. > Construct 200 dynamic libraries that depend on each other cyclically. Once you have a cyclic dependency the order is undefined. My opinion is that the dynamic linker should break the cycle in a deterministic fashion. What do you think? > Run the dlopen() for each dynamic library. > Before the patch is installed, it takes 214 seconds. > After patching, it takes 37 seconds. Is it still correct? Do you have a test case you can add? > Signed-off-by: Xiaoming Ni Reviewing this will have to wait until after the release, but this patch is interesting. Have you looked at Chung-Ling Tang's most recent work in this area? https://patchwork.sourceware.org/project/glibc/patch/1427b370-7400-afd0-16e8-55c1072db20e@mentor.com/ https://patchwork.sourceware.org/project/glibc/patch/5de3ab61-3dca-b400-15c6-92ff5ae80877@mentor.com/ Could you use Chung-Ling's test case constructor to write a test case? > --- > elf/dl-deps.c | 40 +++++++++++++++++++++++++++++++++++++++- > 1 file changed, 39 insertions(+), 1 deletion(-) > > diff --git a/elf/dl-deps.c b/elf/dl-deps.c > index b5a43232a7..5df1e32156 100644 > --- a/elf/dl-deps.c > +++ b/elf/dl-deps.c > @@ -152,6 +152,43 @@ preload (struct list *known, unsigned int *nlist, struct link_map *map) > map->l_reserved = 1; > } > > +/* TIS ELF Version 1.2 > + * Initialization and Termination Functions: > + * 1. Before the initialization code for any object A is called, the > + * initialization code for any other objects that object A depends on are called. > + * 2. The order in which the dynamic linker calls termination functions is the > + * exact reverse order of their corresponding initialization functions. > + * 3. The dynamic linker ensures that it will not execute any initialization > + * or termination functions more than once. > + * > + * According to 1 and 2, _dl_sort_maps() is used for sorting when dlopen/dlclose. > + * According to 3, we only need to sort the uninitialized objects. > + */ > +static void > +_dl_sort_uninit_maps (struct link_map **maps, unsigned int nmaps) > +{ > + unsigned int s = 0; > + unsigned int e = nmaps - 1; > + struct link_map *tmp; > + > + while (s < e) > + { > + while ((e > 0) && maps[e]->l_init_called) > + e--; > + while ((s < nmaps) && maps[s]->l_init_called == 0) > + s++; > + if (s >= e) > + break; > + tmp = maps[e]; > + maps[e] = maps[s]; > + maps[s] = tmp; > + s++; > + e--; > + } > + > + _dl_sort_maps (maps, s, NULL, false); > +} > + > void > _dl_map_object_deps (struct link_map *map, > struct link_map **preloads, unsigned int npreloads, > @@ -611,7 +648,8 @@ Filters not supported with LD_TRACE_PRELINKING")); > memcpy (l_initfini, map->l_searchlist.r_list, > nlist * sizeof (struct link_map *)); > > - _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false); > + if (map->l_init_called == 0) > + _dl_sort_uninit_maps (&l_initfini[1], nlist - 1); > > /* Terminate the list of dependencies. */ > l_initfini[nlist] = NULL; > -- Cheers, Carlos.