From patchwork Wed Jan 13 16:58:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 41713 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 B3B4D3939C17; Wed, 13 Jan 2021 16:58:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B3B4D3939C17 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1610557128; bh=Txq/4k7s0FkETfswoCDZHr/0l8zglhT2o4nKHY4hV4k=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=t3x385bUP6iNRJBsuUtR3eK0nr3SCrR8v0hMwXEp+C12DFhez+9f3aGsLFjOf7Rm8 m1Rk9rdpa/I8XMLKXhuzQnwSV0uI7+O4F5FQ2/8NKCAsaW3WD8ZPupoqQxnFGyso/a ARDOdz/LWBTNPUnj3+k99WJYLjMtlmELtEnBDbQA= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-qt1-x835.google.com (mail-qt1-x835.google.com [IPv6:2607:f8b0:4864:20::835]) by sourceware.org (Postfix) with ESMTPS id 3F0873939C04 for ; Wed, 13 Jan 2021 16:58:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 3F0873939C04 Received: by mail-qt1-x835.google.com with SMTP id c14so1563927qtn.0 for ; Wed, 13 Jan 2021 08:58:37 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Txq/4k7s0FkETfswoCDZHr/0l8zglhT2o4nKHY4hV4k=; b=KdJ6jtlu6Knqz6EWmUwWYvQsFjGbFyIYPi/RBytpSA/hDTTi2/NtVBax0vuDO2xjF4 /xxP4cZSOs0ew0adv/yCDn74k4hluUa2xqHlL7bPx/UakhuO2REuELa9PZ4VZzY+22Xt WVCpbiS0Lqttu/GYOvXHU6SEV/dxQPp+hcHjQTZ7l8vnDy9W9w9pZM2U87eKQUuMZsB5 uHQwBWLuGO8FqxvxbwNPSq/dVWXXLVArlQGqdo0KErChYYEpUu+Qo/nHqISNVtulHIw7 7T18iDHVtS+SMQMKYyH6S2yzX09Up0w6ioBpYxpoa1owPC1lI5A2+iIuk83oungz8wtq qjMA== X-Gm-Message-State: AOAM530DWmkeBAk+dDCinubFGzOkejZbk1HyocjZtsgsz+L29yHMsn5p lD+5snGqPcwi+4e155uW0QhMfOuPmoUqAQ== X-Google-Smtp-Source: ABdhPJwzlReAhV+aZPn7nq4NFnTBbcrEY6eSxPyIoNIO311y4vKtEUBLsjmUqNVGamVmtRaovcUrhQ== X-Received: by 2002:ac8:7b56:: with SMTP id m22mr3268864qtu.380.1610557116582; Wed, 13 Jan 2021 08:58:36 -0800 (PST) Received: from localhost.localdomain ([177.194.48.209]) by smtp.googlemail.com with ESMTPSA id y26sm1303501qth.53.2021.01.13.08.58.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Jan 2021 08:58:36 -0800 (PST) To: libc-alpha@sourceware.org Subject: [PATCH v2 4/5] regexec: remove alloca usage in build_trtable Date: Wed, 13 Jan 2021 13:58:25 -0300 Message-Id: <20210113165826.1014708-4-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210113165826.1014708-1-adhemerval.zanella@linaro.org> References: <20210113165826.1014708-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: Adhemerval Zanella via Libc-alpha From: Adhemerval Zanella Reply-To: Adhemerval Zanella Errors-To: libc-alpha-bounces@sourceware.org Sender: "Libc-alpha" It syncs with gnulib version 1731fef3d. On build_trtable prevent inlining, so that it doesn’t bloat the caller’s stack and use auto variables instead of alloca/malloc. After these changes, build_trtable’s total stack allocation is only 20 KiB on a 64-bit machine, and this is less than glibc’s 64 KiB cutoff so there’s little point to using alloca to shrink it. Checked on x86_64-linux-gnu. --- posix/regexec.c | 75 +++++++++---------------------------------------- 1 file changed, 13 insertions(+), 62 deletions(-) diff --git a/posix/regexec.c b/posix/regexec.c index 889b10be9c..f7b4f9cfc3 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -3247,7 +3247,7 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes, /* Build transition table for the state. Return true if successful. */ -static bool +static bool __attribute_noinline__ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) { reg_errcode_t err; @@ -3255,36 +3255,20 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) int ch; bool need_word_trtable = false; bitset_word_t elem, mask; - bool dests_node_malloced = false; - bool dest_states_malloced = false; Idx ndests; /* Number of the destination states from 'state'. */ re_dfastate_t **trtable; - re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl; - re_node_set follows, *dests_node; - bitset_t *dests_ch; + re_dfastate_t *dest_states[SBC_MAX]; + re_dfastate_t *dest_states_word[SBC_MAX]; + re_dfastate_t *dest_states_nl[SBC_MAX]; + re_node_set follows; bitset_t acceptable; - struct dests_alloc - { - re_node_set dests_node[SBC_MAX]; - bitset_t dests_ch[SBC_MAX]; - } *dests_alloc; - /* We build DFA states which corresponds to the destination nodes from 'state'. 'dests_node[i]' represents the nodes which i-th destination state contains, and 'dests_ch[i]' represents the characters which i-th destination state accepts. */ - if (__libc_use_alloca (sizeof (struct dests_alloc))) - dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc)); - else - { - dests_alloc = re_malloc (struct dests_alloc, 1); - if (__glibc_unlikely (dests_alloc == NULL)) - return false; - dests_node_malloced = true; - } - dests_node = dests_alloc->dests_node; - dests_ch = dests_alloc->dests_ch; + re_node_set dests_node[SBC_MAX]; + bitset_t dests_ch[SBC_MAX]; /* Initialize transition table. */ state->word_trtable = state->trtable = NULL; @@ -3294,8 +3278,6 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch); if (__glibc_unlikely (ndests <= 0)) { - if (dests_node_malloced) - re_free (dests_alloc); /* Return false in case of an error, true otherwise. */ if (ndests == 0) { @@ -3310,38 +3292,14 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) err = re_node_set_alloc (&follows, ndests + 1); if (__glibc_unlikely (err != REG_NOERROR)) - goto out_free; - - /* Avoid arithmetic overflow in size calculation. */ - size_t ndests_max - = ((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX) - / (3 * sizeof (re_dfastate_t *))); - if (__glibc_unlikely (ndests_max < ndests)) - goto out_free; - - if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX - + ndests * 3 * sizeof (re_dfastate_t *))) - dest_states = (re_dfastate_t **) - alloca (ndests * 3 * sizeof (re_dfastate_t *)); - else { - dest_states = re_malloc (re_dfastate_t *, ndests * 3); - if (__glibc_unlikely (dest_states == NULL)) - { -out_free: - if (dest_states_malloced) - re_free (dest_states); - re_node_set_free (&follows); - for (i = 0; i < ndests; ++i) - re_node_set_free (dests_node + i); - if (dests_node_malloced) - re_free (dests_alloc); - return false; - } - dest_states_malloced = true; + out_free: + re_node_set_free (&follows); + for (i = 0; i < ndests; ++i) + re_node_set_free (dests_node + i); + return false; } - dest_states_word = dest_states + ndests; - dest_states_nl = dest_states_word + ndests; + bitset_empty (acceptable); /* Then build the states for all destinations. */ @@ -3466,16 +3424,9 @@ out_free: } } - if (dest_states_malloced) - re_free (dest_states); - re_node_set_free (&follows); for (i = 0; i < ndests; ++i) re_node_set_free (dests_node + i); - - if (dests_node_malloced) - re_free (dests_alloc); - return true; }