From patchwork Fri Nov 17 18:44:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 56391 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 3724438582A6 for ; Fri, 17 Nov 2023 18:44:22 +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 B73533858D28 for ; Fri, 17 Nov 2023 18:44:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B73533858D28 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 B73533858D28 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=1700246651; cv=none; b=qAH2Ry0FmUVFkBoFI5EuHswlIwmUKveABn5a4gmoQSYY40l307RBraXO64TbD/8x4p0hkXXftT6/ygOjZM9h/s8nqzw6iwzYnFpGwwlmGnu0L3LATjMiwIKWXDSWwEgyVdi4O2E2Yuy/vwqv15tIY6Ex0r8Xk1MqM8gYUz7LA8g= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700246651; c=relaxed/simple; bh=uxaDGz/KfRk3iAWvjWoWMC7ijo2J39NPZEje/BIGJ5Y=; h=DKIM-Signature:From:To:Subject:Message-ID:Date:MIME-Version; b=pAEGS9WYt11jhC9rdpOQl8UlK/DlQKjQGjeI2eWlGrK+v/6yNcAcarlXaolHT7/sfpt3v78WymOHtHAdzzf25ZdB44WULc4jlL0qbWRWfMqkGIDAZa/zHN1TkXrJ4ds9NuOak2RfUMDMlNQfwQ3LCoUASOvPy1GFLf1xtDAXCGw= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700246649; 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=g3h+Dnr+jA0sAGxmb5LGM+iNmqYyXAKy7KIP7GYGX8Q=; b=ZUg+af1xN2OCGoekRzS/yhmOHfjl/0W2qV1wAaTUdCdoJ9OIp3WRPT4nqD2IycXIAWgrBN S+ilEWb+iS58rmjfQNBbN4qztQzXu+9DauN83EOgk7zAYLrK23QrLzJa0vG61T6LxG+WdX MfKCl/a1U5FMea58g8DlHdgfOFBAVcU= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-630-kkP5zkLYO2KOp6Ea2lhKjw-1; Fri, 17 Nov 2023 13:44:07 -0500 X-MC-Unique: kkP5zkLYO2KOp6Ea2lhKjw-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (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 B3319887182 for ; Fri, 17 Nov 2023 18:44:07 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.2.16.3]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 1776A1121306 for ; Fri, 17 Nov 2023 18:44:06 +0000 (UTC) From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH 0/3] Various qsort fixes Message-ID: X-From-Line: dc4a606da98f281312bad7a1018a50a71a0d7def Mon Sep 17 00:00:00 2001 Date: Fri, 17 Nov 2023 19:44:05 +0100 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.3 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-4.6 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_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 The first patch is basically a repost, with the condition tweaked for consistency with the other self-comparison avoidance we have. The second patch addresses Stepan's observation regarding incorrect node-index computation in the fallback heapsort heapsort implementation. The third patch activates the heapsort fallback in more cases, to avoid denial-of-service issues. Thanks, Florian Florian Weimer (3): stdlib: Avoid another self-comparison in qsort stdlib: Handle various corner cases in the fallback heapsort for qsort stdlib: The qsort implementation needs to use heapsort in more cases stdlib/Makefile | 4 ++ stdlib/qsort.c | 74 +++++++++++++------ stdlib/tst-qsort4.c | 134 ++++++++++++++++++++++++++++++++++ stdlib/tst-qsort5.c | 171 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 361 insertions(+), 22 deletions(-) create mode 100644 stdlib/tst-qsort4.c create mode 100644 stdlib/tst-qsort5.c base-commit: dae3cf4134d476a4b4ef86fd7012231d6436c15e