From patchwork Fri Nov 17 18:44:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 80169 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 CE31C385C6EF for ; Fri, 17 Nov 2023 18:44:40 +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 A790A3857C41 for ; Fri, 17 Nov 2023 18:44:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A790A3857C41 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 A790A3857C41 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=1700246667; cv=none; b=xcxusCZR7SVWPo1UyMzN51rSlewrpUwYkh62HWL6H6dhXU5gA6udVHP6mFYComRGd6GHVc7n0M7E3/m410IMjRwX+0fjk6ABWVHOKgGC+u6Wt6EpI7jLj0R1keoQ4PMDfB1tSQZPqKfUEV0opJl0zHWApflXtRU5FJ4uub2JyK0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700246667; c=relaxed/simple; bh=8R4Y1HXEWSg07M3kEhvtilNiXqPZlfBIPpSlqssVRPI=; h=DKIM-Signature:From:To:Subject:Message-ID:Date:MIME-Version; b=sg1w+EtiwyiZkkiJXDNQIQNRY62dDMazrrJeAeL44mUJh/iPQd3org3xFAqQTN0M7g6Y1+Ovo9VNInCvT8jVUGPs8BZ5kG+Tr2kEfuvA9nkoZzBGgacfBomeecLeUEJHcyuf/EOrLmlvFsfMjw9wXnpyUrR8l+QkdM+rNcOtLwc= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700246664; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=w9TiBOyoT6acXs74yA5pxgBD7uLdoROuyBKQFOu+g/Y=; b=OngV+r1q4hn952z54jfNagGkEn1mtYFhftp1KunrMOXMKLGlXQ5JlmQhdvI+WCX+FPpq4M 6Fb21NcP9b51cZLza76+UQX47g99mFKK1Ml3Vm9H7RnE+h7Z3uJl/ctUSfZuqUcwTDeI3t cgli95dcvSVDG51RV3JQ+vx9RpXn9rY= 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-441-9Fo_nssNMHGhhT5Ly1efug-1; Fri, 17 Nov 2023 13:44:21 -0500 X-MC-Unique: 9Fo_nssNMHGhhT5Ly1efug-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (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 3E31D185A781 for ; Fri, 17 Nov 2023 18:44:21 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.2.16.3]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 85F2CC09A60 for ; Fri, 17 Nov 2023 18:44:20 +0000 (UTC) From: Florian Weimer To: libc-alpha@sourceware.org Subject: [PATCH 3/3] stdlib: The qsort implementation needs to use heapsort in more cases In-Reply-To: Message-ID: References: X-From-Line: dc4a606da98f281312bad7a1018a50a71a0d7def Mon Sep 17 00:00:00 2001 Date: Fri, 17 Nov 2023 19:44:19 +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.8 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, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE, URI_DOTEDU 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 existing logic avoided internal stack overflow. To avoid a denial-of-service condition with adversarial input, it is necessary to fall over to heapsort if tail-recursing deeply, too, which does not result in a deep stack of pending partitions. The new test stdlib/tst-qsort5 is based on Douglas McIlroy's paper on this subject. Reviewed-by: Adhemerval Zanella --- stdlib/Makefile | 3 + stdlib/qsort.c | 17 +++-- stdlib/tst-qsort5.c | 171 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 187 insertions(+), 4 deletions(-) create mode 100644 stdlib/tst-qsort5.c diff --git a/stdlib/Makefile b/stdlib/Makefile index 48688f6a27..6194d1cb22 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -215,6 +215,7 @@ tests := \ tst-qsort \ tst-qsort2 \ tst-qsort3 \ + tst-qsort5 \ tst-quick_exit \ tst-rand48 \ tst-rand48-2 \ @@ -512,3 +513,5 @@ $(objpfx)tst-setcontext3.out: tst-setcontext3.sh $(objpfx)tst-setcontext3 '$(run-program-env)' '$(test-program-prefix-after-env)' \ $(common-objpfx)stdlib/; \ $(evaluate-test) + +$(objpfx)tst-qsort5: $(libm) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index a2f9e916ef..be01fb5598 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -389,14 +389,23 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, { if ((size_t) (hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ - top = pop (top, &lo, &hi, &depth); + { + top = pop (top, &lo, &hi, &depth); + --depth; + } else - /* Ignore small left partition. */ - lo = left_ptr; + { + /* Ignore small left partition. */ + lo = left_ptr; + --depth; + } } else if ((size_t) (hi - left_ptr) <= max_thresh) /* Ignore small right partition. */ - hi = right_ptr; + { + hi = right_ptr; + --depth; + } else if ((right_ptr - lo) > (hi - left_ptr)) { /* Push larger left partition indices. */ diff --git a/stdlib/tst-qsort5.c b/stdlib/tst-qsort5.c new file mode 100644 index 0000000000..d3a88c30f8 --- /dev/null +++ b/stdlib/tst-qsort5.c @@ -0,0 +1,171 @@ +/* Adversarial test for qsort_r. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +/* The approach follows Douglas McIlroy, A Killer Adversary for + Quicksort. Software—Practice and Experience 29 (1999) 341-344. + Downloaded + (2023-11-17). */ + +#include +#include +#include +#include +#include + +struct context +{ + /* Called the gas value in the paper. This value is larger than all + other values (length minus one will do), so comparison with any + decided value has a known result. */ + int undecided_value; + + /* If comparing undecided values, one of them as to be assigned a + value to ensure consistency with future comparisons. This is the + value that will be used. Starts out at zero. */ + int next_decided; + + /* Used to trick pivot selection. Deciding the value for the last + seen undcided value in a decided/undecided comparison happens + to trick the many qsort implementations. */ + int last_undecided_index; + + /* This array contains the actually asigned values. The call to + qsort_r sorts a different array that contains indices into this + array. */ + int *decided_values; +}; + +static int +compare_opponent (const void *l1, const void *r1, void *ctx1) +{ + const int *l = l1; + const int *r = r1; + struct context *ctx = ctx1; + int rvalue = ctx->decided_values[*r]; + int lvalue = ctx->decided_values[*l]; + + if (lvalue == ctx->undecided_value) + { + if (rvalue == ctx->undecided_value) + { + /* Both values are undecided. In this case, make a decision + for the last-used undecided value. This is tweak is very + specific to quicksort. */ + if (*l == ctx->last_undecided_index) + { + ctx->decided_values[*l] = ctx->next_decided; + ++ctx->next_decided; + /* The undecided value or *r is greater. */ + return -1; + } + else + { + ctx->decided_values[*r] = ctx->next_decided; + ++ctx->next_decided; + /* The undecided value for *l is greater. */ + return 1; + } + } + else + { + ctx->last_undecided_index = *l; + return 1; + } + } + else + { + /* *l is a decided value. */ + if (rvalue == ctx->undecided_value) + { + ctx->last_undecided_index = *r; + /* The undecided value for *r is greater. */ + return -1; + } + else + return lvalue - rvalue; + } +} + +/* Return a pointer to the adversarial permutation of length N. */ +static int * +create_permutation (size_t n) +{ + struct context ctx = + { + .undecided_value = n - 1, /* Larger than all other values. */ + .decided_values = xcalloc (n, sizeof (int)), + }; + for (size_t i = 0; i < n; ++i) + ctx.decided_values[i] = ctx.undecided_value; + int *scratch = xcalloc (n, sizeof (int)); + for (size_t i = 0; i < n; ++i) + scratch[i] = i; + qsort_r (scratch, n, sizeof (*scratch), compare_opponent, &ctx); + free (scratch); + return ctx.decided_values; +} + +/* Callback function for qsort which counts the number of invocations + in *CLOSURE. */ +static int +compare_counter (const void *l1, const void *r1, void *closure) +{ + const int *l = l1; + const int *r = r1; + unsigned long long int *counter = closure; + ++*counter; + return *l - *r; +} + +/* Count the comparisons required for an adversarial permutation of + length N. */ +static unsigned long long int +count_comparisons (size_t n) +{ + int *array = create_permutation (n); + unsigned long long int counter = 0; + qsort_r (array, n, sizeof (*array), compare_counter, &counter); + free (array); + return counter; +} + +/* Check the scaling factor for one adversarial permutation of length + N, and report some statistics. */ +static void +check_one_n (size_t n) +{ + unsigned long long int count = count_comparisons (n); + double factor = count / (n * log (count)); + printf ("info: length %zu: %llu comparisons ~ %f * n * log (n)\n", + n, count, factor); + /* This is an arbitrary factor which is true for the current + implementation across a wide range of sizes. */ + TEST_VERIFY (factor <= 4.5); +} + +static int +do_test (void) +{ + check_one_n (100); + check_one_n (1000); + for (int i = 1; i <= 15; ++i) + check_one_n (i * 10 * 1000); + return 0; +} + +#include