From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from huawei.com (szxga06-in.huawei.com [45.249.212.32]) by sourceware.org (Postfix) with ESMTPS id A1D8C3842408 for ; Wed, 29 Jul 2020 13:56:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org A1D8C3842408 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=huawei.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=nixiaoming@huawei.com Received: from DGGEMS404-HUB.china.huawei.com (unknown [172.30.72.60]) by Forcepoint Email with ESMTP id DEA75AE85BD2F338F485; Wed, 29 Jul 2020 21:56:21 +0800 (CST) Received: from [127.0.0.1] (10.67.102.197) by DGGEMS404-HUB.china.huawei.com (10.3.19.204) with Microsoft SMTP Server id 14.3.487.0; Wed, 29 Jul 2020 21:56:12 +0800 Subject: Re: [PATCH] elf: Sort only uninitialized objects in _dl_map_object_deps() To: Carlos O'Donell , , , , , , CC: References: <20200725105205.103328-1-nixiaoming@huawei.com> <8a15102b-c461-23e2-21d4-f2f7b2b78682@redhat.com> From: Xiaoming Ni Message-ID: <0e390002-1363-1c4a-fd55-cb5f12affd71@huawei.com> Date: Wed, 29 Jul 2020 21:56:07 +0800 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.0.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [10.67.102.197] X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.5 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, KAM_MANYTO, NICE_REPLY_A, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=unavailable 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: Wed, 29 Jul 2020 13:56:30 -0000 On 2020/7/27 8:36, Carlos O'Donell wrote: > On 7/26/20 6:41 AM, Chung-Lin Tang wrote: >> >> >> On 2020/7/26 4:57 AM, Carlos O'Donell via Libc-alpha wrote: >>>> 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? I do not have fully automated test cases locally. Perform the following steps to manually verify the configuration: 1. A large number of SOs are automatically generated. The init and exit functions of an SO record logs. 2. Design different dependencies (unidirectional linked list, binary tree, n-ary tree, ring, network, and random dependency). 3. Re-link the SO based on the dependency relationship. 4. Generate a random array and call dlopen in the sequence recorded in the array. 5. Manually check whether test logs and dependencies comply with the ELF standard. After manual verification, the init/exit sequence of the SO still complies with the ELF standard. >>> >>>> Signed-off-by: Xiaoming Ni >>> Reviewing this will have to wait until after the release, but this patch is >>> interesting. >> >> This patch appears to add a linear pass to somewhat reduce the input size >> of a circularly linked case, but frankly speaking, is only useful with the current >> old sorting algorithm, and just to a certain degree. > > Chung-Lin, thank you for looking over the suggested fixes. > elf/dl-deps.c _dl_map_object_deps: - _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false); + if (map->l_init_called == 0) + _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false); When an object has been loaded, all its dependent objects have been initialized. In this case, sorting is not required. >> The mentioned test case still takes 37 seconds with the proposed patch, while for >> the new DFS-based algorithm, even without any such special case input reduction, >> the sort time will probably be instantaneous. > > I expected that might be the case, but it would still be good to put > the example into a test case and verify. > >>> 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/ >> I didn't notice this before. >> If you're trying out the #17645 sorting patch, remember to add GLIBC_TUNABLES=glibc.rtld.dynamic_sort=2 >> to the environment before running the test, or it will still be the old algorithm. >> >>> Could you use Chung-Ling's test case constructor to write a test case? >>> >> >> Yeah, a new test case like this is always nice, especially to test if the description language >> is expressive enough to handle this. > > Agreed. > I'm trying to automate my test cases, but it's going to take a while. thanks