From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 5E2A33858D38 for ; Thu, 6 Jul 2023 19:18:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5E2A33858D38 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1688671084; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=qG/8A3YQGe0THJI5fZpln5T+czCWIs2HbC1t20Y0e+s=; b=ZGFP4JLWrxURy3Os9MsWVYuC7Gmja006pL/R239OwI0Bak+X4Or4JobK/3keMuSxmzy/OW pUpzo/YqEMR/iVxQXMfRgyPh1vXO+98tmY0n41+A24mW5NoNQbgLr46l7ztjPiyKWG7plo TP5gEv4vrStS65ouvpqRQZLLELU1VPc= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-81-mUcHOZn9MDCoJRtwRBBJQA-1; Thu, 06 Jul 2023 15:18:01 -0400 X-MC-Unique: mUcHOZn9MDCoJRtwRBBJQA-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 0DEB281DB6C; Thu, 6 Jul 2023 19:18:01 +0000 (UTC) Received: from oak (unknown [10.22.8.210]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 69A98207B348; Thu, 6 Jul 2023 19:18:00 +0000 (UTC) Date: Thu, 6 Jul 2023 15:17:58 -0400 From: Joe Simmons-Talbott To: Adhemerval Zanella Netto Cc: Paul Eggert , libc-alpha@sourceware.org Subject: Re: [PATCH] msort: Get rid of alloca. Message-ID: <20230706191758.GD6392@oak> References: <20230630172636.384922-1-josimmon@redhat.com> <20230703160838.GT6392@oak> MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 3.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-5.7 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_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 List-Id: On Thu, Jul 06, 2023 at 10:43:42AM -0300, Adhemerval Zanella Netto wrote: > > > On 03/07/23 13:08, Joe Simmons-Talbott via Libc-alpha wrote: > > On Fri, Jun 30, 2023 at 01:12:28PM -0700, Paul Eggert wrote: > >> On 2023-06-30 10:26, Joe Simmons-Talbott via Libc-alpha wrote: > >> > >>> + /* If the memory requirements are too high don't allocate memory. */ > >>> + if (size / pagesize > (size_t) phys_pages) > >>> + { > >>> + _quicksort (b, n, s, cmp, arg); > >>> + return; > >>> + } > >>> ... > >>> + if (!scratch_buffer_set_array_size (&buf, 1, size)) > >>> + { > >>> + /* Couldn't get space, so use the slower algorithm > >>> + that doesn't need a temporary array. */ > >>> + _quicksort (b, n, s, cmp, arg); > >>> + return; > >>> } > >> > >> Please combine the two ifs into one, since their then-parts are the same and > >> that will make the code easier to follow. > > > > I'll do this in v2. Thanks for the suggestion and the review. > > > >> > >> > >>> + scratch_buffer_free (&buf); > >> > >> Dumb question: can we arrange for scratch_buffer_free to be called even if > >> qsort's comparison function longjmps out of qsort? I realize the old code > >> leaked in that case, but it'd be nice if the new code didn't leak too. This > >> sort of longjmp sometimes happens in real code, e.g., in GNU 'ls'. > >> > > > > I'll have to defer to someone more knowledgable than me on this one. My > > understanding is that longjmp resets the stack pointer and doesn't call > > any GCC cleanup handlers thus ruling out the one option I was able to > > think of. Does anyone else have thoughts on this? > > Another option would to just remove malloc from qsort usage, by using the > quicksort implementation instead. To avoid the worse case we fallback to > a simple heapsort, as some of C++ implementation does. This has the advantage > of fixing the possible longjmp issue and making the qsort full async-safe. > >From my understanding there are three cases in __qsort_r; small where we use alloca, medium where we use malloc, and large where we use _quicksort. This would lead to always using _quicksort, if I understand correctly. _quicksort reduces the probability of the worst case by choosing the median as the pivot. Am I missing something? Thanks, Joe