From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mailout3.rbg.tum.de (mailout3.rbg.tum.de [131.159.0.8]) by sourceware.org (Postfix) with ESMTPS id CF1703856267; Wed, 10 May 2023 10:49:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CF1703856267 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=in.tum.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=in.tum.de Received: from mailrelay1.rbg.tum.de (mailrelay1.in.tum.de [131.159.254.14]) by mailout3.rbg.tum.de (Postfix) with ESMTPS id C18A51002BD; Wed, 10 May 2023 12:49:47 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=in.tum.de; s=20220209; t=1683715787; bh=xOnzMGqsutmWNtnPW6cMf++HNuCZoARPN4UyfJYyaYk=; h=Date:From:Subject:To:Cc:References:In-Reply-To:From; b=XS4jJqZXZcsIQNIawj4Xzi70FTXICHmW3jJ6Tlxt948oWikgm6DCOCJiNzK5jtvxy QMH1JNFUrZ/mLg/ts1zZ+9EzdwUiH2qst4eTFQuwYl45cePZjkSWxmnRcDGjfur1tk m3AN9VZ3JhFjw9lLymqNggQ1Eoj2QwshVpoDoYRysp5z4Z/3lNXebFDJXu9i/vd8z7 oEbbk+K0Qx1a5YHCAKT1bZRKjSqmnOS8JkJfMnpRaoBqvAbZQcchL3aibLeQxXu+BT W5Xn3i6vDnLRHXIyUDedrO5LKmxfkpshM50GKJgHUy/FQJzj7FlKfGfmUv2tn+D/sF TR2CUj9ZFYVVQ== Received: by mailrelay1.rbg.tum.de (Postfix, from userid 112) id BD2AE19E; Wed, 10 May 2023 12:49:47 +0200 (CEST) Received: from mailrelay1.rbg.tum.de (localhost [127.0.0.1]) by mailrelay1.rbg.tum.de (Postfix) with ESMTP id 76975CD; Wed, 10 May 2023 12:49:47 +0200 (CEST) Received: from mail.in.tum.de (vmrbg426.in.tum.de [131.159.0.73]) by mailrelay1.rbg.tum.de (Postfix) with ESMTPS id 72CBD24; Wed, 10 May 2023 12:49:47 +0200 (CEST) Received: by mail.in.tum.de (Postfix, from userid 112) id 6D3BD4A02FA; Wed, 10 May 2023 12:49:47 +0200 (CEST) Received: (Authenticated sender: neumann) by mail.in.tum.de (Postfix) with ESMTPSA id D90674A011B; Wed, 10 May 2023 12:49:46 +0200 (CEST) (Extended-Queue-bit xtech_yb@fff.in.tum.de) Message-ID: <830f90ea-6278-f757-4642-cca654edd736@in.tum.de> Date: Wed, 10 May 2023 12:49:46 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 From: Thomas Neumann Subject: [PATCH] fix radix sort on 32bit platforms [PR109670] To: "gcc-patches@gcc.gnu.org" Cc: Jakub Jelinek , Eric Botcazou References: <2a4776b9-9271-bb3c-a626-d5ec22dae6f3@in.tum.de> <91045a34-a534-4436-bb06-cac32d797a36@in.tum.de> <87sfibqu1s.fsf@oldenburg.str.redhat.com> Content-Language: en-US In-Reply-To: <87sfibqu1s.fsf@oldenburg.str.redhat.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,GIT_PATCH_0,RCVD_IN_DNSWL_LOW,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS,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 radix sort uses two buffers, a1 for input and a2 for output. After every digit the role of the two buffers is swapped. When terminating the sort early the code made sure the output was in a2. However, when we run out of bits, as can happen on 32bit platforms, the sorted result was in a1, was we had just swapped a1 and a2. This patch fixes the problem by unconditionally having a1 as output after every loop iteration. This bug manifested itself only on 32bit platforms and even then only in some circumstances, as it needs frames where a swap is required due to differences in the top-most byte, which is affected by ASLR. The new logic was validated by exhaustive search over 32bit input values. libgcc/ChangeLog: * unwind-dw2-fde.c: Fix radix sort buffer management. --- libgcc/unwind-dw2-fde.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/libgcc/unwind-dw2-fde.c b/libgcc/unwind-dw2-fde.c index 7b74c391ced..31a3834156b 100644 --- a/libgcc/unwind-dw2-fde.c +++ b/libgcc/unwind-dw2-fde.c @@ -624,8 +624,6 @@ fde_radixsort (struct object *ob, fde_extractor_t fde_extractor, // Stop if we are already sorted. if (!violations) { - // The sorted data is in a1 now. - a2 = a1; break; } @@ -660,9 +658,9 @@ fde_radixsort (struct object *ob, fde_extractor_t fde_extractor, #undef FANOUT #undef FANOUTBITS - // The data is in a2 now, move in place if needed. - if (a2 != v1->array) - memcpy (v1->array, a2, sizeof (const fde *) * n); + // The data is in a1 now, move in place if needed. + if (a1 != v1->array) + memcpy (v1->array, a1, sizeof (const fde *) * n); } static inline void -- 2.39.2