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.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 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=1688146001; 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: content-transfer-encoding:content-transfer-encoding; bh=EWSlE9M9lJ26aYjj5iFTClAbCm9GSDSKQFfUhBpFvBs=; b=d5b5YqjwIKB4+4Uz2DPEI2I8zAmNRTMxOVRCOiKFXiJZ+v2v68b2wwcVn5yWC2aqNB6ULG AZ4xirc6oKATWBWHJWZHPIzjACJEWBvwbYIfTGRIWlA+u1GugDlyiAqJFh53ME5qOV8sTG m1sanv3XpCrkrjRsD8MScJTeevonlAA= 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) From: Joe Simmons-Talbott 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 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true 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 List-Id: 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) -- 2.39.2