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: 79338 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B75A438618A7 for ; Tue, 7 Nov 2023 16:10:43 +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+patchwork=sourceware.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)