From patchwork Fri Jun 30 17:26:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joe Simmons-Talbott X-Patchwork-Id: 1802072 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=b+0sds/2; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Qt2LX3Xhrz20ZL for ; Sat, 1 Jul 2023 03:27:00 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 398A1385734B for ; Fri, 30 Jun 2023 17:26:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 398A1385734B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1688146018; bh=EWSlE9M9lJ26aYjj5iFTClAbCm9GSDSKQFfUhBpFvBs=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=b+0sds/2aV3xAy0n1cm9SjaAYnzWOGPTcpPkYTRQAaZKzT7BLAtrCNwSTFcdgcM4x tkkYXDZb4y5TMeGQ+MTvHdMg4rD1qJSCuyndbGBLdseo4OwoNmCFz+UIW2W7+1aHVs YtOzOaSOywrAsE0RoJxiCW3yzMXlkBBGV2cQQYTs= 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 F17E73858C62 for ; Fri, 30 Jun 2023 17:26:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org F17E73858C62 Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-460-axJs8esOOpWEVGEpbnoe9Q-1; Fri, 30 Jun 2023 13:26:40 -0400 X-MC-Unique: axJs8esOOpWEVGEpbnoe9Q-1 Received: by mail-qk1-f198.google.com with SMTP id af79cd13be357-76735d5eb86so234764385a.3 for ; Fri, 30 Jun 2023 10:26:40 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688145999; x=1690737999; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=EWSlE9M9lJ26aYjj5iFTClAbCm9GSDSKQFfUhBpFvBs=; b=iri9RlPk4HtDN77DR++7Kk32Uc2DxyfZ0MBfLp2qzlGdf3gNi0dlogx+Ue+0sWMpWI +jQuCa6jBuYWYuoRFY0qMH+QgZNTKgfYJX6tEmHQIvmCaWHzDR2w0xg8kpB7pZWLi4B0 M3fLxrL3HY6cdKqRNH3gU4fyPxH+tFMkq6RjV3yEthAGHK7XwkNIw5EqhOVNP0vXD5Aq GwVEttC5+vBlEx/76cK+j0CMDUJu1iteCTDLSnKk4ubjNQpSYis9VP75c/xMthS8H1gp sdw4s3y0K5nyh6+v8+66leEEDX4qUMLUiFHUP+XVw0NBsAa7ohVt9tQZfg+7Cuo5FpAm ZrkQ== X-Gm-Message-State: ABy/qLaiQXdtZ+wYvDNsCU/3lSMRHzmjqQqAwQ+5xL0IK3Mf55XRzgNp +usQdh4PVPelUwA96nBrUF5zexDldXYYV5nZNDdh+/LrhR/xx4II94LCR+Fzqf09HvKoqB1XYNX taP+7/g64RDAUPtGap1lFtwbmVDkAXaQgySB4SNKhNjW/g33OZv8adTuN1nN2Z4Jq0K9uboIo3Q G6gNF/ X-Received: by 2002:a05:620a:2a02:b0:767:4246:1f83 with SMTP id o2-20020a05620a2a0200b0076742461f83mr4578766qkp.49.1688145999553; Fri, 30 Jun 2023 10:26:39 -0700 (PDT) X-Google-Smtp-Source: APBJJlElCREfADUOG+b2t0eQh9yE8eE+9Lbphvu/lAcdqFGMLkohvsEjqzCXnTnZEdO/4+EplFN49A== X-Received: by 2002:a05:620a:2a02:b0:767:4246:1f83 with SMTP id o2-20020a05620a2a0200b0076742461f83mr4578750qkp.49.1688145999261; Fri, 30 Jun 2023 10:26:39 -0700 (PDT) Received: from oak.redhat.com (c-71-206-142-238.hsd1.va.comcast.net. [71.206.142.238]) by smtp.gmail.com with ESMTPSA id x7-20020a05620a12a700b00762255dced0sm3242770qki.0.2023.06.30.10.26.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jun 2023 10:26:38 -0700 (PDT) To: libc-alpha@sourceware.org Cc: Joe Simmons-Talbott Subject: [PATCH] msort: Get rid of alloca. Date: Fri, 30 Jun 2023 13:26:36 -0400 Message-Id: <20230630172636.384922-1-josimmon@redhat.com> X-Mailer: git-send-email 2.40.1 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.5 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.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Joe Simmons-Talbott via Libc-alpha From: Joe Simmons-Talbott Reply-To: Joe Simmons-Talbott Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" Use a scratch_buffer rather than alloca/malloc to avoid potential stack overflow. --- stdlib/msort.c | 94 +++++++++++++++++++++++--------------------------- 1 file changed, 43 insertions(+), 51 deletions(-) diff --git a/stdlib/msort.c b/stdlib/msort.c index bbaa5e9f82..237dbb444f 100644 --- a/stdlib/msort.c +++ b/stdlib/msort.c @@ -24,6 +24,7 @@ #include #include #include +#include struct msort_param { @@ -164,71 +165,62 @@ void __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) { size_t size = n * s; - char *tmp = NULL; struct msort_param p; + struct scratch_buffer buf; + scratch_buffer_init (&buf); /* For large object sizes use indirect sorting. */ if (s > 32) size = 2 * n * sizeof (void *) + s; - if (size < 1024) - /* The temporary array is small, so put it on the stack. */ - p.t = __alloca (size); - else - { - /* We should avoid allocating too much memory since this might - have to be backed up by swap space. */ - static long int phys_pages; - static int pagesize; + /* We should avoid allocating too much memory since this might + have to be backed up by swap space. */ + static long int phys_pages; + static int pagesize; - if (pagesize == 0) - { - phys_pages = __sysconf (_SC_PHYS_PAGES); + if (pagesize == 0) + { + phys_pages = __sysconf (_SC_PHYS_PAGES); - if (phys_pages == -1) - /* Error while determining the memory size. So let's - assume there is enough memory. Otherwise the - implementer should provide a complete implementation of - the `sysconf' function. */ - phys_pages = (long int) (~0ul >> 1); + if (phys_pages == -1) + /* Error while determining the memory size. So let's + assume there is enough memory. Otherwise the + implementer should provide a complete implementation of + the `sysconf' function. */ + phys_pages = (long int) (~0ul >> 1); - /* The following determines that we will never use more than - a quarter of the physical memory. */ - phys_pages /= 4; + /* The following determines that we will never use more than + a quarter of the physical memory. */ + phys_pages /= 4; - /* Make sure phys_pages is written to memory. */ - atomic_write_barrier (); + /* Make sure phys_pages is written to memory. */ + atomic_write_barrier (); - pagesize = __sysconf (_SC_PAGESIZE); - } + pagesize = __sysconf (_SC_PAGESIZE); + } - /* Just a comment here. We cannot compute - phys_pages * pagesize - and compare the needed amount of memory against this value. - The problem is that some systems might have more physical - memory then can be represented with a `size_t' value (when - measured in bytes. */ + /* Just a comment here. We cannot compute + phys_pages * pagesize + and compare the needed amount of memory against this value. + The problem is that some systems might have more physical + memory then can be represented with a `size_t' value (when + measured in bytes. */ - /* 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 the memory requirements are too high don't allocate memory. */ + if (size / pagesize > (size_t) phys_pages) + { + _quicksort (b, n, s, cmp, arg); + return; + } - /* It's somewhat large, so malloc it. */ - int save = errno; - tmp = malloc (size); - __set_errno (save); - if (tmp == NULL) - { - /* Couldn't get space, so use the slower algorithm - that doesn't need a temporary array. */ - _quicksort (b, n, s, cmp, arg); - return; - } - p.t = tmp; + 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; } + p.t = buf.data; p.s = s; p.var = 4; @@ -295,7 +287,7 @@ __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) } msort_with_tmp (&p, b, n); } - free (tmp); + scratch_buffer_free (&buf); } libc_hidden_def (__qsort_r) weak_alias (__qsort_r, qsort_r)