From patchwork Tue Oct 24 14:40:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ulrich Weigand X-Patchwork-Id: 23786 Received: (qmail 10574 invoked by alias); 24 Oct 2017 14:41:09 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Delivered-To: mailing list gdb-patches@sourceware.org Received: (qmail 10565 invoked by uid 89); 24 Oct 2017 14:41:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.1 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 24 Oct 2017 14:41:07 +0000 Received: from pps.filterd (m0098414.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.21/8.16.0.21) with SMTP id v9OEdPWS091971 for ; Tue, 24 Oct 2017 10:41:05 -0400 Received: from e06smtp11.uk.ibm.com (e06smtp11.uk.ibm.com [195.75.94.107]) by mx0b-001b2d01.pphosted.com with ESMTP id 2dt4shpb0g-1 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=NOT) for ; Tue, 24 Oct 2017 10:41:05 -0400 Received: from localhost by e06smtp11.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 24 Oct 2017 15:41:03 +0100 Received: from b06cxnps4076.portsmouth.uk.ibm.com (9.149.109.198) by e06smtp11.uk.ibm.com (192.168.101.141) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Tue, 24 Oct 2017 15:41:00 +0100 Received: from d06av26.portsmouth.uk.ibm.com (d06av26.portsmouth.uk.ibm.com [9.149.105.62]) by b06cxnps4076.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id v9OEexY125690144; Tue, 24 Oct 2017 14:40:59 GMT Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id E6B41AE056; Tue, 24 Oct 2017 15:34:56 +0100 (BST) Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id D6064AE051; Tue, 24 Oct 2017 15:34:56 +0100 (BST) Received: from oc3748833570.ibm.com (unknown [9.152.213.178]) by d06av26.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 24 Oct 2017 15:34:56 +0100 (BST) Received: by oc3748833570.ibm.com (Postfix, from userid 1000) id 41BA2D80756; Tue, 24 Oct 2017 16:40:59 +0200 (CEST) Subject: [pushed] Re: [RFA 1/6] Use std::vector in end_symtab_get_static_block To: tom@tromey.com (Tom Tromey) Date: Tue, 24 Oct 2017 16:40:59 +0200 (CEST) From: "Ulrich Weigand" Cc: palves@redhat.com (Pedro Alves), gdb-patches@sourceware.org, tom@tromey.com, simon.marchi@ericsson.com In-Reply-To: <87lgk03b1f.fsf@tromey.com> from "Tom Tromey" at Oct 24, 2017 07:55:40 AM MIME-Version: 1.0 X-TM-AS-GCONF: 00 x-cbid: 17102414-0040-0000-0000-000004065EAA X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17102414-0041-0000-0000-000020A8CBA5 Message-Id: <20171024144059.41BA2D80756@oc3748833570.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2017-10-24_07:, , signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1707230000 definitions=main-1710240206 Tom Tromey wrote: > >>>>> "Ulrich" == Ulrich Weigand writes: > > Ulrich> Now, the reason why we re-sort pending_blocks here is to allow > Ulrich> for object code reordering (hot/cold sections and the like). > Ulrich> But this type of reordering never actually affects inline function > Ulrich> relationships. So it may be that just using stable_sort here is > Ulrich> actually the *correct* fix ... > > I tend to think so as well, for the reasons you mentioned. > glibc doesn't claim that qsort is stable, but maybe it is in practice > sometimes? I just had a look at the glibc qsort implementation. It actually uses (in the common case) a *merge sort* into a temporary buffer, which is always stable. The GNU libstdc++ std::sort on the other hand seems to use an in-place quicksort algorithm, which is generally not stable. This would explain the difference. I've now pushed the patch in the form below. Thanks, Ulrich gdb/ChangeLog: 2017-10-24 Ulrich Weigand * buildsym.c (end_symtab_get_static_block): Use std::stable_sort. diff --git a/gdb/buildsym.c b/gdb/buildsym.c index c556ac1..07bfbd5 100644 --- a/gdb/buildsym.c +++ b/gdb/buildsym.c @@ -1249,12 +1249,14 @@ end_symtab_get_static_block (CORE_ADDR end_addr, int expandable, int required) for (pb = pending_blocks; pb != NULL; pb = pb->next) barray.push_back (pb->block); - std::sort (barray.begin (), barray.end (), - [] (const block *a, const block *b) - { - /* Sort blocks in descending order. */ - return BLOCK_START (a) > BLOCK_START (b); - }); + /* Sort blocks by start address in descending order. Blocks with the + same start address must remain in the original order to preserve + inline function caller/callee relationships. */ + std::stable_sort (barray.begin (), barray.end (), + [] (const block *a, const block *b) + { + return BLOCK_START (a) > BLOCK_START (b); + }); int i = 0; for (pb = pending_blocks; pb != NULL; pb = pb->next)