From patchwork Thu Nov 23 09:10:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 80626 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 7BF4A38582B9 for ; Thu, 23 Nov 2023 09:11: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.129.124]) by sourceware.org (Postfix) with ESMTPS id 6AE3E3858D39 for ; Thu, 23 Nov 2023 09:11:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6AE3E3858D39 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 6AE3E3858D39 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700730670; cv=none; b=uuXQWAwCKgyxBkyGihhm0URsd2l+jf2K/UUd4WYex9BLgXM4RxCvDxZ75H0Gv8wXJ5X7SsNaya5GOYUJS+TKfQQrNErzg7L2yvP1KymRq/U3dAGdDFQ/UsEpbVdBP1AfpIZu7pm26maimagHjaIEFu8E3Y0hWp3CbUo/xFNmQsk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700730670; c=relaxed/simple; bh=6sPL01rfL+r+UWO25NOMj3Bk9GFJZWmfVdDs+7LkOGw=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=Y8uv6NIm4omu/4tRR/cxgVb5gJ5FLeaRD41m/UoEt3/BQVLaE8Tit/PMcMQ1NGai483oYtZ6OpB5l6bfDaPh7MGJJAQ/fGtR18CBp6BLfRRvuJrMI/OXj9uVM+wuV4w20livZu+J9bl/j3sDicHpnxdH3fQSzn7ZBgcAnh5hg+c= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700730666; 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=lHU0N4sAUI95SjZTyuWi2H0kFA55aGH1NrgowD3pUvU=; b=Pe5gsA4aEMnEKZMgbBLvZe0uqHWcqTErrpC00dCKGxIU66MutyyiLMpPyO9ZtIDWpLPgA+ bbr67cHbduivbiq7QBuKXkLZ8mo555cCBUMqhMl3z/S//Rck0lGAg0uKS7m/sPYZVphUNQ nniGzpTBp6cNRkkc/vNx8wikLUSuXpI= 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-93-90JjNp_cOcmLVM6sKgnEXw-1; Thu, 23 Nov 2023 04:11:02 -0500 X-MC-Unique: 90JjNp_cOcmLVM6sKgnEXw-1 Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (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 A6753101A597 for ; Thu, 23 Nov 2023 09:11:02 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.39.192.108]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 22729492BFA for ; Thu, 23 Nov 2023 09:11:01 +0000 (UTC) From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH] stdlib: Add another workaround to the insertion sort phase of qsort Date: Thu, 23 Nov 2023 10:10:59 +0100 Message-ID: <877cm8esws.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.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-10.6 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_H4, 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 If the comparison function returns negative values incorrectly, it was possible that we decrement tmp_ptr past the start of the array. Improves commit e4d8117b82065dc72e8df80097360e7c05a349b9 ("stdlib: Avoid another self-comparison in qsort"). --- stdlib/qsort.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) base-commit: 472894d2cfee5751b44c0aaa71ed87df81c8e62e diff --git a/stdlib/qsort.c b/stdlib/qsort.c index be01fb5598..6f28abbc7f 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -238,8 +238,17 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems, while ((run_ptr += size) <= end_ptr) { tmp_ptr = run_ptr - size; - while (run_ptr != tmp_ptr && cmp (run_ptr, tmp_ptr, arg) < 0) - tmp_ptr -= size; + /* The initial pointer comparison avoids a call to cmp if the + pointer arguments are identical (the call returns zero with a + correctly implemented comparison function). The final + pointer comparison cannot be reached because the element at + base_ptr is the smallest element, but it prevents the loop + from running beyond the start of the array with a broken + comparison function. */ + while (run_ptr != tmp_ptr + && cmp (run_ptr, tmp_ptr, arg) < 0 + && run_ptr != base_ptr) + tmp_ptr -= size; tmp_ptr += size; if (tmp_ptr != run_ptr)