From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-2.mimecast.com [205.139.110.61]) by sourceware.org (Postfix) with ESMTP id 9A9583858D38 for ; Mon, 27 Jul 2020 00:36:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9A9583858D38 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-70-yCVwuThCO1S5IYU8b9NbPg-1; Sun, 26 Jul 2020 20:36:21 -0400 X-MC-Unique: yCVwuThCO1S5IYU8b9NbPg-1 Received: by mail-qt1-f199.google.com with SMTP id q7so10489749qtq.14 for ; Sun, 26 Jul 2020 17:36:21 -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=9voPx6vsSiq5NZ7bapLA9zkhUyYmRgKZk/wk74JBZMc=; b=e8HLpyTOqmrKKPbsc+wb92eBrAFLBdzYftJTpDLo/29W7MskySdbVqaLIYcAb8wh4d J/lacx+TjtmLVydtz9fF6ZTJo8oRaiPxjILVovePnzoDOrjIOfeZr2dmbW+XstZoWGzE EMdoGDO45mAxeOY4pKExMz3zMo5nOBHGZ6wcp3t8t2sVecTgZdi4F7BdaN4AWGSSXaSs DeBbgI/Vp9pQ18a3ZESKeNdFwngOQLLFTGIqVf1l598IFyfV1Gb3L+xdafs/AlwI+HPC rU/hp2EPTP4IDgNayJQ/hhR4qut64eb64py3lu+4zYqemqjEn6mZ/CLcy6+GPA3hM76Q Sv2g== X-Gm-Message-State: AOAM533TMsSAMUOvkWVy/crjwqI7ww1Fh8U+tmue1hyBqW/ovR8Gr8xl mOskV5dgCvJnpmLEe2D4XdVCzzXNwoBxUZPD4pImhaimCsoFQoBYd/NQ/50PbQx5gnFNp0ri0ul GK6Xe/eFBdtFmYfdGmd0j X-Received: by 2002:ad4:4992:: with SMTP id t18mr7382705qvx.193.1595810180672; Sun, 26 Jul 2020 17:36:20 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwpV6k8SP3wExH+GWZjGkufLsJi7eN9QMT1LK2sdmj2dIE9gkw7/HMZEGGquuQHsJ7IRIm5lQ== X-Received: by 2002:ad4:4992:: with SMTP id t18mr7382688qvx.193.1595810180387; Sun, 26 Jul 2020 17:36:20 -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 b8sm12011136qtg.45.2020.07.26.17.36.18 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 26 Jul 2020 17:36:19 -0700 (PDT) Subject: Re: [PATCH] elf: Sort only uninitialized objects in _dl_map_object_deps() To: cltang@codesourcery.com, 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> <8a15102b-c461-23e2-21d4-f2f7b2b78682@redhat.com> From: Carlos O'Donell Organization: Red Hat Message-ID: Date: Sun, 26 Jul 2020 20:36:17 -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: Content-Language: en-US X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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: Mon, 27 Jul 2020 00:36:28 -0000 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? >>   >>> 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. > 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/ > > 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. -- Cheers, Carlos.