From patchwork Tue Nov 7 16:10:23 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 1861152 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=WNCNnJ11; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SPtVV2rnzz1yQL for ; Wed, 8 Nov 2023 03:10:42 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E7BFD385C6F9 for ; Tue, 7 Nov 2023 16:10:39 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id C1A6C3858284 for ; Tue, 7 Nov 2023 16:10:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C1A6C3858284 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org C1A6C3858284 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699373432; cv=none; b=fvVfRktsguluGuA6v4PlyKguYARyhOzSxMjw0I76V3xq00JFviZNzNRmwpP2tnSVWKNlM3r0vHgeGTI/SLeVOeyeWf6OSTzaLzIE9kgPtJmdH95GBJwuSRl2GUAjP7rXilUkz/7j7L1eHa0PXRo9FKJyQYRXRr2Hnf/WNc8AiD0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699373432; c=relaxed/simple; bh=nEhtbUAFr03CaX5yrdxl1ujQmtBrW+A6HEM9jGH2SPQ=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=UzJcslQjdjokWtWmbLoUSFcu9G5kD/UHE0t/vgz2unQn8AP30BNdGMwHgeLQwGE+CMTES+k+Kne2rUzbi0l41x2CIPY1M9hZ+WqTEkMzHOtXl1t0ppvik166kX3CyV/7zx0DBGcexILuBrzOMRcYBVukL2cj33NoUHE98iUfgRA= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1699373430; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=gzV5sA5k9HoTxXgTL/K45FOZbJ4rEwpowMFDeIoSw3c=; b=WNCNnJ11usPVJjfEBnCDnmf5Qm0bHbtuaSIxxNgVe6iwH3wt2vKxai1vF7jo4otcy7UZcZ 6QbpSZZNGGfNY7xCqCaZu5iBXumcdM8DiQILpaQZ8UOzUXVyIZyymDJxUFh58G99DNr0+7 MdL+Tf0MD/m/hCdJGBbJ/BZlaRi8BiU= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-300-Xu5vW5hkP1GrO_FWisim4Q-1; Tue, 07 Nov 2023 11:10:27 -0500 X-MC-Unique: Xu5vW5hkP1GrO_FWisim4Q-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id C5B6C3821365 for ; Tue, 7 Nov 2023 16:10:25 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.2.16.22]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 460F6492BE7 for ; Tue, 7 Nov 2023 16:10:25 +0000 (UTC) From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH] stdlib: Avoid element self-comparisons in qsort Date: Tue, 07 Nov 2023 17:10:23 +0100 Message-ID: <87leb9bl3k.fsf@oldenburg.str.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.3 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-10.8 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_NONE, 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 X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org This improves compatibility with applications which assume that qsort does not invoke the comparison function with equal pointer arguments. The newly introduced branches should be predictable, as leading to a call to the comparison function. If the prediction fails, we avoid calling the function. Tested on x86_64-linux-gnu. I don't know if it papers over the LLVM problem, but the line number in the posted backtrace for the assertion failure points to the first while statement that the patch changes. Thanks, Florian Reviewed-by: Adhemerval Zanella --- stdlib/qsort.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) base-commit: 5dd3bda59c2d9da138f0d98808d087cdb95cdc17 diff --git a/stdlib/qsort.c b/stdlib/qsort.c index fd32a165e7..ad110e8a89 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -136,7 +136,7 @@ siftdown (void *base, size_t size, size_t k, size_t n, if (j < n && cmp (base + (j * size), base + ((j + 1) * size), arg) < 0) j++; - if (cmp (base + (k * size), base + (j * size), arg) >= 0) + if (j == k || cmp (base + (k * size), base + (j * size), arg) >= 0) break; do_swap (base + (size * j), base + (k * size), size, swap_type); @@ -332,10 +332,12 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, that this algorithm runs much faster than others. */ do { - while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) + while (left_ptr != mid + && (*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) left_ptr += size; - while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) + while (right_ptr != mid + && (*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) right_ptr -= size; if (left_ptr < right_ptr)