* [PATCH 1/3] posix: Remove alloca usage on regex set_regs
@ 2021-01-06 18:17 Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 2/3] posix: Remove alloca usage on regex build_trtable Adhemerval Zanella
` (3 more replies)
0 siblings, 4 replies; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-06 18:17 UTC (permalink / raw)
To: libc-alpha, Paul Eggert, bug-gnulib
It replaces the regmatch_t with a dynarray list.
Checked on x86_64-linux-gnu.
---
posix/regexec.c | 62 ++++++++++++++++++++++++-------------------------
1 file changed, 31 insertions(+), 31 deletions(-)
diff --git a/posix/regexec.c b/posix/regexec.c
index b083342f77..5e22f90842 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -54,9 +54,6 @@ static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
Idx *p_match_first);
static Idx check_halt_state_context (const re_match_context_t *mctx,
const re_dfastate_t *state, Idx idx);
-static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
- regmatch_t *prev_idx_match, Idx cur_node,
- Idx cur_idx, Idx nmatch);
static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
Idx str_idx, Idx dest_node, Idx nregs,
regmatch_t *regs,
@@ -1355,6 +1352,16 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
return fs->stack[num].node;
}
+
+#define DYNARRAY_STRUCT regmatch_list
+#define DYNARRAY_ELEMENT regmatch_t
+#define DYNARRAY_PREFIX regmatch_list_
+#include <malloc/dynarray-skeleton.c>
+
+static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
+ struct regmatch_list *prev_idx_match, Idx cur_node,
+ Idx cur_idx, Idx nmatch);
+
/* Set the positions where the subexpressions are starts/ends to registers
PMATCH.
Note: We assume that pmatch[0] is already set, and
@@ -1370,8 +1377,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
re_node_set eps_via_nodes;
struct re_fail_stack_t *fs;
struct re_fail_stack_t fs_body = { 0, 2, NULL };
- regmatch_t *prev_idx_match;
- bool prev_idx_match_malloced = false;
+ struct regmatch_list prev_idx_match;
+ regmatch_list_init (&prev_idx_match);
DEBUG_ASSERT (nmatch > 1);
DEBUG_ASSERT (mctx->state_log != NULL);
@@ -1388,23 +1395,18 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
cur_node = dfa->init_node;
re_node_set_init_empty (&eps_via_nodes);
- if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
- prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
- else
+ if (!regmatch_list_resize (&prev_idx_match, nmatch))
{
- prev_idx_match = re_malloc (regmatch_t, nmatch);
- if (prev_idx_match == NULL)
- {
- free_fail_stack_return (fs);
- return REG_ESPACE;
- }
- prev_idx_match_malloced = true;
+ regmatch_list_free (&prev_idx_match);
+ free_fail_stack_return (fs);
+ return REG_ESPACE;
}
- memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
+ for (size_t i = 0; i < nmatch; i++)
+ *regmatch_list_at (&prev_idx_match, i) = pmatch[i];
for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
{
- update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
+ update_regs (dfa, pmatch, &prev_idx_match, cur_node, idx, nmatch);
if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
{
@@ -1417,8 +1419,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
if (reg_idx == nmatch)
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_idx_match);
return free_fail_stack_return (fs);
}
cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
@@ -1427,8 +1428,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
else
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_idx_match);
return REG_NOERROR;
}
}
@@ -1442,8 +1442,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
if (__glibc_unlikely (cur_node == -2))
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_idx_match);
free_fail_stack_return (fs);
return REG_ESPACE;
}
@@ -1453,15 +1452,13 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
else
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_idx_match);
return REG_NOMATCH;
}
}
}
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_idx_match);
return free_fail_stack_return (fs);
}
@@ -1483,7 +1480,8 @@ free_fail_stack_return (struct re_fail_stack_t *fs)
static void
update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
- regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
+ struct regmatch_list *prev_idx_match, Idx cur_node, Idx cur_idx,
+ Idx nmatch)
{
int type = dfa->nodes[cur_node].type;
if (type == OP_OPEN_SUBEXP)
@@ -1508,18 +1506,20 @@ update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
pmatch[reg_num].rm_eo = cur_idx;
/* This is a non-empty match or we are not inside an optional
subexpression. Accept this right away. */
- memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
+ for (size_t i = 0; i < nmatch; i++)
+ *regmatch_list_at (prev_idx_match, i) = pmatch[i];
}
else
{
if (dfa->nodes[cur_node].opt_subexp
- && prev_idx_match[reg_num].rm_so != -1)
+ && regmatch_list_at (prev_idx_match, reg_num)->rm_so != -1)
/* We transited through an empty match for an optional
subexpression, like (a?)*, and this is not the subexp's
first match. Copy back the old content of the registers
so that matches of an inner subexpression are undone as
well, like in ((a?))*. */
- memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
+ memcpy (pmatch, regmatch_list_begin (prev_idx_match),
+ sizeof (regmatch_t) * nmatch);
else
/* We completed a subexpression, but it may be part of
an optional one, so do not update PREV_IDX_MATCH. */
--
2.25.1
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 2/3] posix: Remove alloca usage on regex build_trtable
2021-01-06 18:17 [PATCH 1/3] posix: Remove alloca usage on regex set_regs Adhemerval Zanella
@ 2021-01-06 18:17 ` Adhemerval Zanella
2021-01-08 22:30 ` Paul Eggert
2021-01-06 18:17 ` [PATCH 3/3] posix: Remove alloca definition from regex Adhemerval Zanella
` (2 subsequent siblings)
3 siblings, 1 reply; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-06 18:17 UTC (permalink / raw)
To: libc-alpha, Paul Eggert, bug-gnulib
__libc_use_alloca/alloca is replaced with malloc regardless.
Checked on x86_64-linux-gnu.
---
posix/regexec.c | 50 +++++++++++++++----------------------------------
1 file changed, 15 insertions(+), 35 deletions(-)
diff --git a/posix/regexec.c b/posix/regexec.c
index 5e22f90842..a8e9a9cd01 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -3259,8 +3259,6 @@ 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;
@@ -3278,15 +3276,9 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
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_alloc = re_malloc (struct dests_alloc, 1);
+ if (__glibc_unlikely (dests_alloc == NULL))
+ return false;
dests_node = dests_alloc->dests_node;
dests_ch = dests_alloc->dests_ch;
@@ -3298,8 +3290,7 @@ 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);
+ re_free (dests_alloc);
/* Return false in case of an error, true otherwise. */
if (ndests == 0)
{
@@ -3323,26 +3314,17 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
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 * sizeof (re_dfastate_t *));
+ if (__glibc_unlikely (dest_states == NULL))
{
- 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;
+ re_free (dest_states);
+ re_node_set_free (&follows);
+ for (i = 0; i < ndests; ++i)
+ re_node_set_free (dests_node + i);
+ re_free (dests_alloc);
+ return false;
}
dest_states_word = dest_states + ndests;
dest_states_nl = dest_states_word + ndests;
@@ -3470,15 +3452,13 @@ out_free:
}
}
- if (dest_states_malloced)
- re_free (dest_states);
+ 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);
+ re_free (dests_alloc);
return true;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH 3/3] posix: Remove alloca definition from regex
2021-01-06 18:17 [PATCH 1/3] posix: Remove alloca usage on regex set_regs Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 2/3] posix: Remove alloca usage on regex build_trtable Adhemerval Zanella
@ 2021-01-06 18:17 ` Adhemerval Zanella
2021-01-09 1:20 ` Paul Eggert
2021-01-08 20:14 ` [PATCH 1/3] posix: Remove alloca usage on regex set_regs Paul Eggert
2021-01-09 1:24 ` Darshit Shah
3 siblings, 1 reply; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-06 18:17 UTC (permalink / raw)
To: libc-alpha, Paul Eggert, bug-gnulib
Since it is not used anymore. No functional changes is expected.
Checked on x86_64-linux-gnu.
---
posix/regex_internal.h | 19 -------------------
1 file changed, 19 deletions(-)
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index e31ac92674..641b27e2b1 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -444,25 +444,6 @@ typedef struct re_dfa_t re_dfa_t;
#define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
#define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
-#if defined _LIBC || HAVE_ALLOCA
-# include <alloca.h>
-#endif
-
-#ifndef _LIBC
-# if HAVE_ALLOCA
-/* The OS usually guarantees only one guard page at the bottom of the stack,
- and a page size can be as small as 4096 bytes. So we cannot safely
- allocate anything larger than 4096 bytes. Also care for the possibility
- of a few compiler-allocated temporary stack slots. */
-# define __libc_use_alloca(n) ((n) < 4032)
-# else
-/* alloca is implemented with malloc, so just use malloc. */
-# define __libc_use_alloca(n) 0
-# undef alloca
-# define alloca(n) malloc (n)
-# endif
-#endif
-
#ifdef _LIBC
# define MALLOC_0_IS_NONNULL 1
#elif !defined MALLOC_0_IS_NONNULL
--
2.25.1
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] posix: Remove alloca usage on regex set_regs
2021-01-06 18:17 [PATCH 1/3] posix: Remove alloca usage on regex set_regs Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 2/3] posix: Remove alloca usage on regex build_trtable Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 3/3] posix: Remove alloca definition from regex Adhemerval Zanella
@ 2021-01-08 20:14 ` Paul Eggert
2021-01-11 12:35 ` Adhemerval Zanella
2021-01-09 1:24 ` Darshit Shah
3 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2021-01-08 20:14 UTC (permalink / raw)
To: Adhemerval Zanella; +Cc: bug-gnulib, libc-alpha
[-- Attachment #1: Type: text/plain, Size: 3276 bytes --]
On 1/6/21 10:17 AM, Adhemerval Zanella wrote:
> It replaces the regmatch_t with a dynarray list.
regexec.c is shared with Gnulib, so some work needed to be done on the
Gnulib side for this patch since Gnulib didn't have dynarray. Dynarray
is something I've been meaning to add to Gnulib for some time, so I did
that by installing the first attached patch into Gnulib. Could you
please propagate the new Gnulib dynarray sources into glibc so that they
stay in sync? As near as I can make out, the glibc dynarray files can
now be identical to the new Gnulib files; if not, please let me know.
> posix/regexec.c | 62 ++++++++++++++++++++++++-------------------------
> 1 file changed, 31 insertions(+), 31 deletions(-)
> ...
> @@ -1355,6 +1352,16 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
> return fs->stack[num].node;
> }
>
> +
> +#define DYNARRAY_STRUCT regmatch_list
> +#define DYNARRAY_ELEMENT regmatch_t
> +#define DYNARRAY_PREFIX regmatch_list_
> +#include <malloc/dynarray-skeleton.c>
> +
> +static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
> + struct regmatch_list *prev_idx_match, Idx cur_node,
> + Idx cur_idx, Idx nmatch);
> +
> /* Set the positions where the subexpressions are starts/ends to registers
> PMATCH.
> Note: We assume that pmatch[0] is already set, and
> @@ -1370,8 +1377,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> re_node_set eps_via_nodes;
> struct re_fail_stack_t *fs;
> struct re_fail_stack_t fs_body = { 0, 2, NULL };
> - regmatch_t *prev_idx_match;
> - bool prev_idx_match_malloced = false;
> + struct regmatch_list prev_idx_match;
> + regmatch_list_init (&prev_idx_match);
>
> DEBUG_ASSERT (nmatch > 1);
> DEBUG_ASSERT (mctx->state_log != NULL);
> @@ -1388,23 +1395,18 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> cur_node = dfa->init_node;
> re_node_set_init_empty (&eps_via_nodes);
>
> - if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
> - prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
> - else
> + if (!regmatch_list_resize (&prev_idx_match, nmatch))
> {
> - prev_idx_match = re_malloc (regmatch_t, nmatch);
> - if (prev_idx_match == NULL)
> - {
> - free_fail_stack_return (fs);
> - return REG_ESPACE;
> - }
> - prev_idx_match_malloced = true;
> + regmatch_list_free (&prev_idx_match);
> + free_fail_stack_return (fs);
> + return REG_ESPACE;
> }
These three hunks are good, but you can omit most of the other hunks
(and improve performance a bit) by inserting the following line after
the 3rd hunk:
+ regmatch_t *prev_idx_match = regmatch_list_begin (&prev_match);
since the dynarray doesn't grow after that and this means you don't need
to change the rest of the code to use prev_match rather than
prev_idx_match. The only other hunks you need to retain are the ones
replacing re_free with regmastch_list_free.
I've made this improvement to Gnulib by installing the second attached
patch, so you should be able to copy Gnulib regexec.c to glibc without
changing it.
[-- Attachment #2: 0001-dynarray-new-module.patch --]
[-- Type: text/x-patch, Size: 46223 bytes --]
From ae1984c524f03f8e8bb104d3a2b5c533114cf552 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 8 Jan 2021 11:44:19 -0800
Subject: [PATCH 1/2] dynarray: new module
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
* config/srclist.txt: Mention the new files.
* lib/cdefs.h (__attribute_maybe_unused__): New macro,
like Gnulib’s _GL_ATTRIBUTE_MAYBE_UNUSED but with glibc
naming conventions.
* lib/libc-config.h: Use it instead of __glibc_likely.
* lib/dynarray.h, modules/dynarray: New files.
* lib/malloc/dynarray-skeleton.c, lib/malloc/dynarray.h:
* lib/malloc/dynarray_at_failure.c:
* lib/malloc/dynarray_emplace_enlarge.c:
* lib/malloc/dynarray_finalize.c, lib/malloc/dynarray_resize.c:
* lib/malloc/dynarray_resize_clear.c, modules/dynarray:
New files, from glibc with the following changes needed for
portability to compilers that are not recent-enough GCC.
* lib/malloc/dynarray_at_failure.c: Include stdlib.h, for abort.
(__libc_dynarray_at_failure) [!_LIBC]: Simply abort.
* lib/malloc/dynarray_emplace_enlarge.c:
* lib/malloc/dynarray_resize.c:
Include intprops.h, and use INT_MULTIPLY_WRAPV instead
of __builtin_mul_overflow.
* lib/malloc/dynarray.h (__libc_dynarray_at_failure):
Use _Noreturn instead of __attribute__ ((noreturn)).
* lib/malloc/dynarray_resize_clear.c: Do not include stdlib.h;
it’s not needed.
(__libc_dynarray_resize_clear): Do not do arithmetic on void *.
* lib/malloc/dynarray-skeleton.c (struct DYNARRAY_STRUCT):
Do not use anonymous unions, as they are not in C99. All uses changed.
Use __nonnull (X) instead of __attribute__ ((nonnull X)),
and __attribute_maybe_unused__ instead of __attribute__ ((unused)).
---
ChangeLog | 32 ++
config/srclist.txt | 7 +
lib/cdefs.h | 8 +
lib/dynarray.h | 31 ++
lib/libc-config.h | 10 +-
lib/malloc/dynarray-skeleton.c | 521 ++++++++++++++++++++++++++
lib/malloc/dynarray.h | 178 +++++++++
lib/malloc/dynarray_at_failure.c | 35 ++
lib/malloc/dynarray_emplace_enlarge.c | 73 ++++
lib/malloc/dynarray_finalize.c | 62 +++
lib/malloc/dynarray_resize.c | 64 ++++
lib/malloc/dynarray_resize_clear.c | 35 ++
modules/dynarray | 37 ++
13 files changed, 1087 insertions(+), 6 deletions(-)
create mode 100644 lib/dynarray.h
create mode 100644 lib/malloc/dynarray-skeleton.c
create mode 100644 lib/malloc/dynarray.h
create mode 100644 lib/malloc/dynarray_at_failure.c
create mode 100644 lib/malloc/dynarray_emplace_enlarge.c
create mode 100644 lib/malloc/dynarray_finalize.c
create mode 100644 lib/malloc/dynarray_resize.c
create mode 100644 lib/malloc/dynarray_resize_clear.c
create mode 100644 modules/dynarray
diff --git a/ChangeLog b/ChangeLog
index df676e6ba..db37b0a24 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,35 @@
+2021-01-08 Paul Eggert <eggert@cs.ucla.edu>
+
+ dynarray: new module
+ * config/srclist.txt: Mention the new files.
+ * lib/cdefs.h (__attribute_maybe_unused__): New macro,
+ like Gnulib’s _GL_ATTRIBUTE_MAYBE_UNUSED but with glibc
+ naming conventions.
+ * lib/libc-config.h: Use it instead of __glibc_likely.
+ * lib/dynarray.h, modules/dynarray: New files.
+ * lib/malloc/dynarray-skeleton.c, lib/malloc/dynarray.h:
+ * lib/malloc/dynarray_at_failure.c:
+ * lib/malloc/dynarray_emplace_enlarge.c:
+ * lib/malloc/dynarray_finalize.c, lib/malloc/dynarray_resize.c:
+ * lib/malloc/dynarray_resize_clear.c, modules/dynarray:
+ New files, from glibc with the following changes needed for
+ portability to compilers that are not recent-enough GCC.
+ * lib/malloc/dynarray_at_failure.c: Include stdlib.h, for abort.
+ (__libc_dynarray_at_failure) [!_LIBC]: Simply abort.
+ * lib/malloc/dynarray_emplace_enlarge.c:
+ * lib/malloc/dynarray_resize.c:
+ Include intprops.h, and use INT_MULTIPLY_WRAPV instead
+ of __builtin_mul_overflow.
+ * lib/malloc/dynarray.h (__libc_dynarray_at_failure):
+ Use _Noreturn instead of __attribute__ ((noreturn)).
+ * lib/malloc/dynarray_resize_clear.c: Do not include stdlib.h;
+ it’s not needed.
+ (__libc_dynarray_resize_clear): Do not do arithmetic on void *.
+ * lib/malloc/dynarray-skeleton.c (struct DYNARRAY_STRUCT):
+ Do not use anonymous unions, as they are not in C99. All uses changed.
+ Use __nonnull (X) instead of __attribute__ ((nonnull X)),
+ and __attribute_maybe_unused__ instead of __attribute__ ((unused)).
+
2021-01-06 Simon Josefsson <simon@josefsson.org>
bootstrap: Fix parsing of package name.
diff --git a/config/srclist.txt b/config/srclist.txt
index a2b058d73..e7ceeb088 100644
--- a/config/srclist.txt
+++ b/config/srclist.txt
@@ -51,6 +51,13 @@ $GNUORG Copyright/request-disclaim.changes doc/Copyright
$LIBCSRC include/filename.h lib
$LIBCSRC include/idx.h lib
+#$LIBCSRC malloc/dynarray-skeleton.c lib/malloc
+#$LIBCSRC malloc/dynarray.h lib/malloc
+#$LIBCSRC malloc/dynarray_at_failure.c lib/malloc
+#$LIBCSRC malloc/dynarray_emplace_enlarge.c lib/malloc
+$LIBCSRC malloc/dynarray_finalize.c lib/malloc
+#$LIBCSRC malloc/dynarray_resize.c lib/malloc
+#$LIBCSRC malloc/dynarray_resize_clear.c lib/malloc
$LIBCSRC include/scratch_buffer.h lib/malloc
$LIBCSRC malloc/scratch_buffer_dupfree.c lib/malloc
$LIBCSRC malloc/scratch_buffer_grow.c lib/malloc
diff --git a/lib/cdefs.h b/lib/cdefs.h
index c4769aa70..a22ae6db2 100644
--- a/lib/cdefs.h
+++ b/lib/cdefs.h
@@ -257,6 +257,14 @@
# define __attribute_const__ /* Ignore */
#endif
+#if defined __STDC_VERSION__ && 201710L < __STDC_VERSION__
+# define __attribute_maybe_unused__ [[__maybe_unused__]]
+#elif __GNUC_PREREQ (2,7) || __glibc_has_attribute (__unused__)
+# define __attribute_maybe_unused__ __attribute__ ((__unused__))
+#else
+# define __attribute_maybe_unused__ /* Ignore */
+#endif
+
/* At some point during the gcc 3.1 development the `used' attribute
for functions was introduced. We don't want to use it unconditionally
(although this would be possible) since it generates warnings. */
diff --git a/lib/dynarray.h b/lib/dynarray.h
new file mode 100644
index 000000000..6da3e87e5
--- /dev/null
+++ b/lib/dynarray.h
@@ -0,0 +1,31 @@
+/* Type-safe arrays which grow dynamically.
+ Copyright 2021 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Paul Eggert, 2021. */
+
+#ifndef _GL_DYNARRAY_H
+#define _GL_DYNARRAY_H
+
+#include <libc-config.h>
+
+#define __libc_dynarray_at_failure gl_dynarray_at_failure
+#define __libc_dynarray_emplace_enlarge gl_dynarray_emplace_enlarge
+#define __libc_dynarray_finalize gl_dynarray_finalize
+#define __libc_dynarray_resize_clear gl_dynarray_resize_clear
+#define __libc_dynarray_resize gl_dynarray_resize
+#include <malloc/dynarray.h>
+
+#endif /* _GL_DYNARRAY_H */
diff --git a/lib/libc-config.h b/lib/libc-config.h
index 19e852f45..fcdafcb96 100644
--- a/lib/libc-config.h
+++ b/lib/libc-config.h
@@ -71,12 +71,10 @@
# endif
#endif
-#ifndef __glibc_likely
-/* <sys/cdefs.h> either does not exist, or predates glibc commit
- 2012-12-28T06:33:01Z!siddhesh@redhat.com
- (91998e449e0ce758db55aecf2abc3ee510fcbc8f)
- and so does not suffice for Gnulib. Prepare to include <cdefs.h>,
- which is Gnulib's copy of a more-recent glibc <sys/cdefs.h>. */
+#ifndef __attribute_maybe_unused__
+/* <sys/cdefs.h> either does not exist, or is too old for Gnulib.
+ Prepare to include <cdefs.h>, which is Gnulib's version of a
+ more-recent glibc <sys/cdefs.h>. */
/* Define _FEATURES_H so that <cdefs.h> does not include <features.h>. */
# ifndef _FEATURES_H
diff --git a/lib/malloc/dynarray-skeleton.c b/lib/malloc/dynarray-skeleton.c
new file mode 100644
index 000000000..fe886102c
--- /dev/null
+++ b/lib/malloc/dynarray-skeleton.c
@@ -0,0 +1,521 @@
+/* Type-safe arrays which grow dynamically.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+/* Pre-processor macros which act as parameters:
+
+ DYNARRAY_STRUCT
+ The struct tag of dynamic array to be defined.
+ DYNARRAY_ELEMENT
+ The type name of the element type. Elements are copied
+ as if by memcpy, and can change address as the dynamic
+ array grows.
+ DYNARRAY_PREFIX
+ The prefix of the functions which are defined.
+
+ The following parameters are optional:
+
+ DYNARRAY_ELEMENT_FREE
+ DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
+ contents of elements. E is of type DYNARRAY_ELEMENT *.
+ DYNARRAY_ELEMENT_INIT
+ DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new
+ element. E is of type DYNARRAY_ELEMENT *.
+ If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is
+ defined, new elements are automatically zero-initialized.
+ Otherwise, new elements have undefined contents.
+ DYNARRAY_INITIAL_SIZE
+ The size of the statically allocated array (default:
+ at least 2, more elements if they fit into 128 bytes).
+ Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0,
+ there is no statically allocated array at, and all non-empty
+ arrays are heap-allocated.
+ DYNARRAY_FINAL_TYPE
+ The name of the type which holds the final array. If not
+ defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE
+ must be a struct type, with members of type DYNARRAY_ELEMENT and
+ size_t at the start (in this order).
+
+ These macros are undefined after this header file has been
+ included.
+
+ The following types are provided (their members are private to the
+ dynarray implementation):
+
+ struct DYNARRAY_STRUCT
+
+ The following functions are provided:
+
+ void DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *);
+ void DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *);
+ bool DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *);
+ void DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *);
+ size_t DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *);
+ DYNARRAY_ELEMENT *DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *);
+ DYNARRAY_ELEMENT *DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *);
+ DYNARRAY_ELEMENT *DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *, size_t);
+ void DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *, DYNARRAY_ELEMENT);
+ DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *);
+ bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t);
+ void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *);
+ void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *);
+
+ The following functions are provided are provided if the
+ prerequisites are met:
+
+ bool DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
+ DYNARRAY_FINAL_TYPE *);
+ (if DYNARRAY_FINAL_TYPE is defined)
+ DYNARRAY_ELEMENT *DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
+ size_t *);
+ (if DYNARRAY_FINAL_TYPE is not defined)
+*/
+
+#include <malloc/dynarray.h>
+
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifndef DYNARRAY_STRUCT
+# error "DYNARRAY_STRUCT must be defined"
+#endif
+
+#ifndef DYNARRAY_ELEMENT
+# error "DYNARRAY_ELEMENT must be defined"
+#endif
+
+#ifndef DYNARRAY_PREFIX
+# error "DYNARRAY_PREFIX must be defined"
+#endif
+
+#ifdef DYNARRAY_INITIAL_SIZE
+# if DYNARRAY_INITIAL_SIZE < 0
+# error "DYNARRAY_INITIAL_SIZE must be non-negative"
+# endif
+# if DYNARRAY_INITIAL_SIZE > 0
+# define DYNARRAY_HAVE_SCRATCH 1
+# else
+# define DYNARRAY_HAVE_SCRATCH 0
+# endif
+#else
+/* Provide a reasonable default which limits the size of
+ DYNARRAY_STRUCT. */
+# define DYNARRAY_INITIAL_SIZE \
+ (sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT))
+# define DYNARRAY_HAVE_SCRATCH 1
+#endif
+
+/* Public type definitions. */
+
+/* All fields of this struct are private to the implementation. */
+struct DYNARRAY_STRUCT
+{
+ union
+ {
+ struct dynarray_header dynarray_abstract;
+ struct
+ {
+ /* These fields must match struct dynarray_header. */
+ size_t used;
+ size_t allocated;
+ DYNARRAY_ELEMENT *array;
+ } dynarray_header;
+ } u;
+
+#if DYNARRAY_HAVE_SCRATCH
+ /* Initial inline allocation. */
+ DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE];
+#endif
+};
+
+/* Internal use only: Helper macros. */
+
+/* Ensure macro-expansion of DYNARRAY_PREFIX. */
+#define DYNARRAY_CONCAT0(prefix, name) prefix##name
+#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name)
+#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name)
+
+/* Address of the scratch buffer if any. */
+#if DYNARRAY_HAVE_SCRATCH
+# define DYNARRAY_SCRATCH(list) (list)->scratch
+#else
+# define DYNARRAY_SCRATCH(list) NULL
+#endif
+
+/* Internal use only: Helper functions. */
+
+/* Internal function. Call DYNARRAY_ELEMENT_FREE with the array
+ elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE
+ macro expansion. */
+static inline void
+DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array,
+ size_t __dynarray_used)
+{
+#ifdef DYNARRAY_ELEMENT_FREE
+ for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i)
+ DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]);
+#endif /* DYNARRAY_ELEMENT_FREE */
+}
+
+/* Internal function. Free the non-scratch array allocation. */
+static inline void
+DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list)
+{
+#if DYNARRAY_HAVE_SCRATCH
+ if (list->u.dynarray_header.array != list->scratch)
+ free (list->u.dynarray_header.array);
+#else
+ free (list->u.dynarray_header.array);
+#endif
+}
+
+/* Public functions. */
+
+/* Initialize a dynamic array object. This must be called before any
+ use of the object. */
+__nonnull ((1))
+static void
+DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
+{
+ list->u.dynarray_header.used = 0;
+ list->u.dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
+ list->u.dynarray_header.array = DYNARRAY_SCRATCH (list);
+}
+
+/* Deallocate the dynamic array and its elements. */
+__attribute_maybe_unused__ __nonnull ((1))
+static void
+DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
+{
+ DYNARRAY_NAME (free__elements__)
+ (list->u.dynarray_header.array, list->u.dynarray_header.used);
+ DYNARRAY_NAME (free__array__) (list);
+ DYNARRAY_NAME (init) (list);
+}
+
+/* Return true if the dynamic array is in an error state. */
+__nonnull ((1))
+static inline bool
+DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
+{
+ return list->u.dynarray_header.allocated == __dynarray_error_marker ();
+}
+
+/* Mark the dynamic array as failed. All elements are deallocated as
+ a side effect. */
+__nonnull ((1))
+static void
+DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
+{
+ DYNARRAY_NAME (free__elements__)
+ (list->u.dynarray_header.array, list->u.dynarray_header.used);
+ DYNARRAY_NAME (free__array__) (list);
+ list->u.dynarray_header.array = DYNARRAY_SCRATCH (list);
+ list->u.dynarray_header.used = 0;
+ list->u.dynarray_header.allocated = __dynarray_error_marker ();
+}
+
+/* Return the number of elements which have been added to the dynamic
+ array. */
+__nonnull ((1))
+static inline size_t
+DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
+{
+ return list->u.dynarray_header.used;
+}
+
+/* Return a pointer to the array element at INDEX. Terminate the
+ process if INDEX is out of bounds. */
+__nonnull ((1))
+static inline DYNARRAY_ELEMENT *
+DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index)
+{
+ if (__glibc_unlikely (index >= DYNARRAY_NAME (size) (list)))
+ __libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index);
+ return list->u.dynarray_header.array + index;
+}
+
+/* Return a pointer to the first array element, if any. For a
+ zero-length array, the pointer can be NULL even though the dynamic
+ array has not entered the failure state. */
+__nonnull ((1))
+static inline DYNARRAY_ELEMENT *
+DYNARRAY_NAME (begin) (struct DYNARRAY_STRUCT *list)
+{
+ return list->u.dynarray_header.array;
+}
+
+/* Return a pointer one element past the last array element. For a
+ zero-length array, the pointer can be NULL even though the dynamic
+ array has not entered the failure state. */
+__nonnull ((1))
+static inline DYNARRAY_ELEMENT *
+DYNARRAY_NAME (end) (struct DYNARRAY_STRUCT *list)
+{
+ return list->u.dynarray_header.array + list->u.dynarray_header.used;
+}
+
+/* Internal function. Slow path for the add function below. */
+static void
+DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
+{
+ if (__glibc_unlikely
+ (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract,
+ DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT))))
+ {
+ DYNARRAY_NAME (mark_failed) (list);
+ return;
+ }
+
+ /* Copy the new element and increase the array length. */
+ list->u.dynarray_header.array[list->u.dynarray_header.used++] = item;
+}
+
+/* Add ITEM at the end of the array, enlarging it by one element.
+ Mark *LIST as failed if the dynamic array allocation size cannot be
+ increased. */
+__nonnull ((1))
+static inline void
+DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
+{
+ /* Do nothing in case of previous error. */
+ if (DYNARRAY_NAME (has_failed) (list))
+ return;
+
+ /* Enlarge the array if necessary. */
+ if (__glibc_unlikely (list->u.dynarray_header.used
+ == list->u.dynarray_header.allocated))
+ {
+ DYNARRAY_NAME (add__) (list, item);
+ return;
+ }
+
+ /* Copy the new element and increase the array length. */
+ list->u.dynarray_header.array[list->u.dynarray_header.used++] = item;
+}
+
+/* Internal function. Building block for the emplace functions below.
+ Assumes space for one more element in *LIST. */
+static inline DYNARRAY_ELEMENT *
+DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list)
+{
+ DYNARRAY_ELEMENT *result
+ = &list->u.dynarray_header.array[list->u.dynarray_header.used];
+ ++list->u.dynarray_header.used;
+#if defined (DYNARRAY_ELEMENT_INIT)
+ DYNARRAY_ELEMENT_INIT (result);
+#elif defined (DYNARRAY_ELEMENT_FREE)
+ memset (result, 0, sizeof (*result));
+#endif
+ return result;
+}
+
+/* Internal function. Slow path for the emplace function below. */
+static DYNARRAY_ELEMENT *
+DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list)
+{
+ if (__glibc_unlikely
+ (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract,
+ DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT))))
+ {
+ DYNARRAY_NAME (mark_failed) (list);
+ return NULL;
+ }
+ return DYNARRAY_NAME (emplace__tail__) (list);
+}
+
+/* Allocate a place for a new element in *LIST and return a pointer to
+ it. The pointer can be NULL if the dynamic array cannot be
+ enlarged due to a memory allocation failure. */
+__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((1))
+static
+/* Avoid inlining with the larger initialization code. */
+#if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE))
+inline
+#endif
+DYNARRAY_ELEMENT *
+DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list)
+{
+ /* Do nothing in case of previous error. */
+ if (DYNARRAY_NAME (has_failed) (list))
+ return NULL;
+
+ /* Enlarge the array if necessary. */
+ if (__glibc_unlikely (list->u.dynarray_header.used
+ == list->u.dynarray_header.allocated))
+ return (DYNARRAY_NAME (emplace__) (list));
+ return DYNARRAY_NAME (emplace__tail__) (list);
+}
+
+/* Change the size of *LIST to SIZE. If SIZE is larger than the
+ existing size, new elements are added (which can be initialized).
+ Otherwise, the list is truncated, and elements are freed. Return
+ false on memory allocation failure (and mark *LIST as failed). */
+__attribute_maybe_unused__ __nonnull ((1))
+static bool
+DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
+{
+ if (size > list->u.dynarray_header.used)
+ {
+ bool ok;
+#if defined (DYNARRAY_ELEMENT_INIT)
+ /* The new elements have to be initialized. */
+ size_t old_size = list->u.dynarray_header.used;
+ ok = __libc_dynarray_resize (&list->u.dynarray_abstract,
+ size, DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT));
+ if (ok)
+ for (size_t i = old_size; i < size; ++i)
+ {
+ DYNARRAY_ELEMENT_INIT (&list->u.dynarray_header.array[i]);
+ }
+#elif defined (DYNARRAY_ELEMENT_FREE)
+ /* Zero initialization is needed so that the elements can be
+ safely freed. */
+ ok = __libc_dynarray_resize_clear
+ (&list->u.dynarray_abstract, size,
+ DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
+#else
+ ok = __libc_dynarray_resize (&list->u.dynarray_abstract,
+ size, DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT));
+#endif
+ if (__glibc_unlikely (!ok))
+ DYNARRAY_NAME (mark_failed) (list);
+ return ok;
+ }
+ else
+ {
+ /* The list has shrunk in size. Free the removed elements. */
+ DYNARRAY_NAME (free__elements__)
+ (list->u.dynarray_header.array + size,
+ list->u.dynarray_header.used - size);
+ list->u.dynarray_header.used = size;
+ return true;
+ }
+}
+
+/* Remove the last element of LIST if it is present. */
+__attribute_maybe_unused__ __nonnull ((1))
+static void
+DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
+{
+ /* used > 0 implies that the array is the non-failed state. */
+ if (list->u.dynarray_header.used > 0)
+ {
+ size_t new_length = list->u.dynarray_header.used - 1;
+#ifdef DYNARRAY_ELEMENT_FREE
+ DYNARRAY_ELEMENT_FREE (&list->u.dynarray_header.array[new_length]);
+#endif
+ list->u.dynarray_header.used = new_length;
+ }
+}
+
+/* Remove all elements from the list. The elements are freed, but the
+ list itself is not. */
+__attribute_maybe_unused__ __nonnull ((1))
+static void
+DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
+{
+ /* free__elements__ does nothing if the list is in the failed
+ state. */
+ DYNARRAY_NAME (free__elements__)
+ (list->u.dynarray_header.array, list->u.dynarray_header.used);
+ list->u.dynarray_header.used = 0;
+}
+
+#ifdef DYNARRAY_FINAL_TYPE
+/* Transfer the dynamic array to a permanent location at *RESULT.
+ Returns true on success on false on allocation failure. In either
+ case, *LIST is re-initialized and can be reused. A NULL pointer is
+ stored in *RESULT if LIST refers to an empty list. On success, the
+ pointer in *RESULT is heap-allocated and must be deallocated using
+ free. */
+__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((1, 2))
+static bool
+DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
+ DYNARRAY_FINAL_TYPE *result)
+{
+ struct dynarray_finalize_result res;
+ if (__libc_dynarray_finalize (&list->u.dynarray_abstract,
+ DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT), &res))
+ {
+ /* On success, the result owns all the data. */
+ DYNARRAY_NAME (init) (list);
+ *result = (DYNARRAY_FINAL_TYPE) { res.array, res.length };
+ return true;
+ }
+ else
+ {
+ /* On error, we need to free all data. */
+ DYNARRAY_NAME (free) (list);
+ errno = ENOMEM;
+ return false;
+ }
+}
+#else /* !DYNARRAY_FINAL_TYPE */
+/* Transfer the dynamic array to a heap-allocated array and return a
+ pointer to it. The pointer is NULL if memory allocation fails, or
+ if the array is empty, so this function should be used only for
+ arrays which are known not be empty (usually because they always
+ have a sentinel at the end). If LENGTHP is not NULL, the array
+ length is written to *LENGTHP. *LIST is re-initialized and can be
+ reused. */
+__attribute_maybe_unused__ __attribute_warn_unused_result__ __nonnull ((1))
+static DYNARRAY_ELEMENT *
+DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
+{
+ struct dynarray_finalize_result res;
+ if (__libc_dynarray_finalize (&list->u.dynarray_abstract,
+ DYNARRAY_SCRATCH (list),
+ sizeof (DYNARRAY_ELEMENT), &res))
+ {
+ /* On success, the result owns all the data. */
+ DYNARRAY_NAME (init) (list);
+ if (lengthp != NULL)
+ *lengthp = res.length;
+ return res.array;
+ }
+ else
+ {
+ /* On error, we need to free all data. */
+ DYNARRAY_NAME (free) (list);
+ errno = ENOMEM;
+ return NULL;
+ }
+}
+#endif /* !DYNARRAY_FINAL_TYPE */
+
+/* Undo macro definitions. */
+
+#undef DYNARRAY_CONCAT0
+#undef DYNARRAY_CONCAT1
+#undef DYNARRAY_NAME
+#undef DYNARRAY_SCRATCH
+#undef DYNARRAY_HAVE_SCRATCH
+
+#undef DYNARRAY_STRUCT
+#undef DYNARRAY_ELEMENT
+#undef DYNARRAY_PREFIX
+#undef DYNARRAY_ELEMENT_FREE
+#undef DYNARRAY_ELEMENT_INIT
+#undef DYNARRAY_INITIAL_SIZE
+#undef DYNARRAY_FINAL_TYPE
diff --git a/lib/malloc/dynarray.h b/lib/malloc/dynarray.h
new file mode 100644
index 000000000..638c33f98
--- /dev/null
+++ b/lib/malloc/dynarray.h
@@ -0,0 +1,178 @@
+/* Type-safe arrays which grow dynamically. Shared definitions.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+/* To use the dynarray facility, you need to include
+ <malloc/dynarray-skeleton.c> and define the parameter macros
+ documented in that file.
+
+ A minimal example which provides a growing list of integers can be
+ defined like this:
+
+ struct int_array
+ {
+ // Pointer to result array followed by its length,
+ // as required by DYNARRAY_FINAL_TYPE.
+ int *array;
+ size_t length;
+ };
+
+ #define DYNARRAY_STRUCT dynarray_int
+ #define DYNARRAY_ELEMENT int
+ #define DYNARRAY_PREFIX dynarray_int_
+ #define DYNARRAY_FINAL_TYPE struct int_array
+ #include <malloc/dynarray-skeleton.c>
+
+ To create a three-element array with elements 1, 2, 3, use this
+ code:
+
+ struct dynarray_int dyn;
+ dynarray_int_init (&dyn);
+ for (int i = 1; i <= 3; ++i)
+ {
+ int *place = dynarray_int_emplace (&dyn);
+ assert (place != NULL);
+ *place = i;
+ }
+ struct int_array result;
+ bool ok = dynarray_int_finalize (&dyn, &result);
+ assert (ok);
+ assert (result.length == 3);
+ assert (result.array[0] == 1);
+ assert (result.array[1] == 2);
+ assert (result.array[2] == 3);
+ free (result.array);
+
+ If the elements contain resources which must be freed, define
+ DYNARRAY_ELEMENT_FREE appropriately, like this:
+
+ struct str_array
+ {
+ char **array;
+ size_t length;
+ };
+
+ #define DYNARRAY_STRUCT dynarray_str
+ #define DYNARRAY_ELEMENT char *
+ #define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr)
+ #define DYNARRAY_PREFIX dynarray_str_
+ #define DYNARRAY_FINAL_TYPE struct str_array
+ #include <malloc/dynarray-skeleton.c>
+
+ Compared to scratch buffers, dynamic arrays have the following
+ features:
+
+ - They have an element type, and are not just an untyped buffer of
+ bytes.
+
+ - When growing, previously stored elements are preserved. (It is
+ expected that scratch_buffer_grow_preserve and
+ scratch_buffer_set_array_size eventually go away because all
+ current users are moved to dynamic arrays.)
+
+ - Scratch buffers have a more aggressive growth policy because
+ growing them typically means a retry of an operation (across an
+ NSS service module boundary), which is expensive.
+
+ - For the same reason, scratch buffers have a much larger initial
+ stack allocation. */
+
+#ifndef _DYNARRAY_H
+#define _DYNARRAY_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+
+struct dynarray_header
+{
+ size_t used;
+ size_t allocated;
+ void *array;
+};
+
+/* Marker used in the allocated member to indicate that an error was
+ encountered. */
+static inline size_t
+__dynarray_error_marker (void)
+{
+ return -1;
+}
+
+/* Internal function. See the has_failed function in
+ dynarray-skeleton.c. */
+static inline bool
+__dynarray_error (struct dynarray_header *list)
+{
+ return list->allocated == __dynarray_error_marker ();
+}
+
+/* Internal function. Enlarge the dynamically allocated area of the
+ array to make room for one more element. SCRATCH is a pointer to
+ the scratch area (which is not heap-allocated and must not be
+ freed). ELEMENT_SIZE is the size, in bytes, of one element.
+ Return false on failure, true on success. */
+bool __libc_dynarray_emplace_enlarge (struct dynarray_header *,
+ void *scratch, size_t element_size);
+
+/* Internal function. Enlarge the dynamically allocated area of the
+ array to make room for at least SIZE elements (which must be larger
+ than the existing used part of the dynamic array). SCRATCH is a
+ pointer to the scratch area (which is not heap-allocated and must
+ not be freed). ELEMENT_SIZE is the size, in bytes, of one element.
+ Return false on failure, true on success. */
+bool __libc_dynarray_resize (struct dynarray_header *, size_t size,
+ void *scratch, size_t element_size);
+
+/* Internal function. Like __libc_dynarray_resize, but clear the new
+ part of the dynamic array. */
+bool __libc_dynarray_resize_clear (struct dynarray_header *, size_t size,
+ void *scratch, size_t element_size);
+
+/* Internal type. */
+struct dynarray_finalize_result
+{
+ void *array;
+ size_t length;
+};
+
+/* Internal function. Copy the dynamically-allocated area to an
+ explicitly-sized heap allocation. SCRATCH is a pointer to the
+ embedded scratch space. ELEMENT_SIZE is the size, in bytes, of the
+ element type. On success, true is returned, and pointer and length
+ are written to *RESULT. On failure, false is returned. The caller
+ has to take care of some of the memory management; this function is
+ expected to be called from dynarray-skeleton.c. */
+bool __libc_dynarray_finalize (struct dynarray_header *list, void *scratch,
+ size_t element_size,
+ struct dynarray_finalize_result *result);
+
+
+/* Internal function. Terminate the process after an index error.
+ SIZE is the number of elements of the dynamic array. INDEX is the
+ lookup index which triggered the failure. */
+_Noreturn void __libc_dynarray_at_failure (size_t size, size_t index);
+
+#ifndef _ISOMAC
+libc_hidden_proto (__libc_dynarray_emplace_enlarge)
+libc_hidden_proto (__libc_dynarray_resize)
+libc_hidden_proto (__libc_dynarray_resize_clear)
+libc_hidden_proto (__libc_dynarray_finalize)
+libc_hidden_proto (__libc_dynarray_at_failure)
+#endif
+
+#endif /* _DYNARRAY_H */
diff --git a/lib/malloc/dynarray_at_failure.c b/lib/malloc/dynarray_at_failure.c
new file mode 100644
index 000000000..0fa12c7cd
--- /dev/null
+++ b/lib/malloc/dynarray_at_failure.c
@@ -0,0 +1,35 @@
+/* Report an dynamic array index out of bounds condition.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <dynarray.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+void
+__libc_dynarray_at_failure (size_t size, size_t index)
+{
+#ifdef _LIBC
+ char buf[200];
+ __snprintf (buf, sizeof (buf), "Fatal glibc error: "
+ "array index %zu not less than array length %zu\n",
+ index, size);
+#else
+ abort ();
+#endif
+}
+libc_hidden_def (__libc_dynarray_at_failure)
diff --git a/lib/malloc/dynarray_emplace_enlarge.c b/lib/malloc/dynarray_emplace_enlarge.c
new file mode 100644
index 000000000..ddfe306fc
--- /dev/null
+++ b/lib/malloc/dynarray_emplace_enlarge.c
@@ -0,0 +1,73 @@
+/* Increase the size of a dynamic array in preparation of an emplace operation.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <dynarray.h>
+#include <errno.h>
+#include <intprops.h>
+#include <stdlib.h>
+#include <string.h>
+
+bool
+__libc_dynarray_emplace_enlarge (struct dynarray_header *list,
+ void *scratch, size_t element_size)
+{
+ size_t new_allocated;
+ if (list->allocated == 0)
+ {
+ /* No scratch buffer provided. Choose a reasonable default
+ size. */
+ if (element_size < 4)
+ new_allocated = 16;
+ else if (element_size < 8)
+ new_allocated = 8;
+ else
+ new_allocated = 4;
+ }
+ else
+ /* Increase the allocated size, using an exponential growth
+ policy. */
+ {
+ new_allocated = list->allocated + list->allocated / 2 + 1;
+ if (new_allocated <= list->allocated)
+ {
+ /* Overflow. */
+ __set_errno (ENOMEM);
+ return false;
+ }
+ }
+
+ size_t new_size;
+ if (INT_MULTIPLY_WRAPV (new_allocated, element_size, &new_size))
+ return false;
+ void *new_array;
+ if (list->array == scratch)
+ {
+ /* The previous array was not heap-allocated. */
+ new_array = malloc (new_size);
+ if (new_array != NULL && list->array != NULL)
+ memcpy (new_array, list->array, list->used * element_size);
+ }
+ else
+ new_array = realloc (list->array, new_size);
+ if (new_array == NULL)
+ return false;
+ list->array = new_array;
+ list->allocated = new_allocated;
+ return true;
+}
+libc_hidden_def (__libc_dynarray_emplace_enlarge)
diff --git a/lib/malloc/dynarray_finalize.c b/lib/malloc/dynarray_finalize.c
new file mode 100644
index 000000000..8ec6ad2bc
--- /dev/null
+++ b/lib/malloc/dynarray_finalize.c
@@ -0,0 +1,62 @@
+/* Copy the dynamically-allocated area to an explicitly-sized heap allocation.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <dynarray.h>
+#include <stdlib.h>
+#include <string.h>
+
+bool
+__libc_dynarray_finalize (struct dynarray_header *list,
+ void *scratch, size_t element_size,
+ struct dynarray_finalize_result *result)
+{
+ if (__dynarray_error (list))
+ /* The caller will reported the deferred error. */
+ return false;
+
+ size_t used = list->used;
+
+ /* Empty list. */
+ if (used == 0)
+ {
+ /* An empty list could still be backed by a heap-allocated
+ array. Free it if necessary. */
+ if (list->array != scratch)
+ free (list->array);
+ *result = (struct dynarray_finalize_result) { NULL, 0 };
+ return true;
+ }
+
+ size_t allocation_size = used * element_size;
+ void *heap_array = malloc (allocation_size);
+ if (heap_array != NULL)
+ {
+ /* The new array takes ownership of the strings. */
+ if (list->array != NULL)
+ memcpy (heap_array, list->array, allocation_size);
+ if (list->array != scratch)
+ free (list->array);
+ *result = (struct dynarray_finalize_result)
+ { .array = heap_array, .length = used };
+ return true;
+ }
+ else
+ /* The caller will perform the freeing operation. */
+ return false;
+}
+libc_hidden_def (__libc_dynarray_finalize)
diff --git a/lib/malloc/dynarray_resize.c b/lib/malloc/dynarray_resize.c
new file mode 100644
index 000000000..5c60927f3
--- /dev/null
+++ b/lib/malloc/dynarray_resize.c
@@ -0,0 +1,64 @@
+/* Increase the size of a dynamic array.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <dynarray.h>
+#include <errno.h>
+#include <intprops.h>
+#include <stdlib.h>
+#include <string.h>
+
+bool
+__libc_dynarray_resize (struct dynarray_header *list, size_t size,
+ void *scratch, size_t element_size)
+{
+ /* The existing allocation provides sufficient room. */
+ if (size <= list->allocated)
+ {
+ list->used = size;
+ return true;
+ }
+
+ /* Otherwise, use size as the new allocation size. The caller is
+ expected to provide the final size of the array, so there is no
+ over-allocation here. */
+
+ size_t new_size_bytes;
+ if (INT_MULTIPLY_WRAPV (size, element_size, &new_size_bytes))
+ {
+ /* Overflow. */
+ __set_errno (ENOMEM);
+ return false;
+ }
+ void *new_array;
+ if (list->array == scratch)
+ {
+ /* The previous array was not heap-allocated. */
+ new_array = malloc (new_size_bytes);
+ if (new_array != NULL && list->array != NULL)
+ memcpy (new_array, list->array, list->used * element_size);
+ }
+ else
+ new_array = realloc (list->array, new_size_bytes);
+ if (new_array == NULL)
+ return false;
+ list->array = new_array;
+ list->allocated = size;
+ list->used = size;
+ return true;
+}
+libc_hidden_def (__libc_dynarray_resize)
diff --git a/lib/malloc/dynarray_resize_clear.c b/lib/malloc/dynarray_resize_clear.c
new file mode 100644
index 000000000..e893d1d58
--- /dev/null
+++ b/lib/malloc/dynarray_resize_clear.c
@@ -0,0 +1,35 @@
+/* Increase the size of a dynamic array and clear the new part.
+ Copyright (C) 2017-2021 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
+ <https://www.gnu.org/licenses/>. */
+
+#include <dynarray.h>
+#include <string.h>
+
+bool
+__libc_dynarray_resize_clear (struct dynarray_header *list, size_t size,
+ void *scratch, size_t element_size)
+{
+ size_t old_size = list->used;
+ if (!__libc_dynarray_resize (list, size, scratch, element_size))
+ return false;
+ /* __libc_dynarray_resize already checked for overflow. */
+ char *array = list->array;
+ memset (array + (old_size * element_size), 0,
+ (size - old_size) * element_size);
+ return true;
+}
+libc_hidden_def (__libc_dynarray_resize_clear)
diff --git a/modules/dynarray b/modules/dynarray
new file mode 100644
index 000000000..36a08adb7
--- /dev/null
+++ b/modules/dynarray
@@ -0,0 +1,37 @@
+Description:
+Type-safe arrays which grow dynamically.
+
+Files:
+lib/dynarray.h
+lib/malloc/dynarray-skeleton.c
+lib/malloc/dynarray.h
+lib/malloc/dynarray_at_failure.c
+lib/malloc/dynarray_emplace_enlarge.c
+lib/malloc/dynarray_finalize.c
+lib/malloc/dynarray_resize.c
+lib/malloc/dynarray_resize_clear.c
+
+Depends-on:
+c99
+libc-config
+stdbool
+stddef
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += malloc/dynarray_at_failure.c \
+ malloc/dynarray_emplace_enlarge.c \
+ malloc/dynarray_finalize.c \
+ malloc/dynarray_resize.c \
+ malloc/dynarray_resize_clear.c
+
+Include:
+<dynarray.h>
+<malloc/dynarray-skeleton.c>
+
+License:
+LGPLv2+
+
+Maintainer:
+all, glibc
--
2.27.0
[-- Attachment #3: 0002-regex-remove-alloca-usage-on-regex-set_regs.patch --]
[-- Type: text/x-patch, Size: 5947 bytes --]
From c26fbc3ecdf9eb30b34be34a452d5410908d2dba Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 8 Jan 2021 12:00:09 -0800
Subject: [PATCH 2/2] regex: remove alloca usage on regex set_regs
Derived from this patch by Adhemerval Zanella:
https://sourceware.org/pipermail/libc-alpha/2021-January/121372.html
* lib/regex_internal.h: Include dynarray.h, for Gnulib.
* lib/regexec.c (DYNARRAY_STRUCT, DYNARRAY_ELEMENT)
(DYNARRAY_PREFIX): New macros.
Include malloc/dynarray-skeleton.c.
(set_regs): Use dynarray rather than alloca.
* modules/regex (Depends-on): Add dynarray.
---
ChangeLog | 10 ++++++++++
lib/regex_internal.h | 1 +
lib/regexec.c | 40 ++++++++++++++++++----------------------
modules/regex | 1 +
4 files changed, 30 insertions(+), 22 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index db37b0a24..aff3584e4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
2021-01-08 Paul Eggert <eggert@cs.ucla.edu>
+ regex: remove alloca usage on regex set_regs
+ Derived from this patch by Adhemerval Zanella:
+ https://sourceware.org/pipermail/libc-alpha/2021-January/121372.html
+ * lib/regex_internal.h: Include dynarray.h, for Gnulib.
+ * lib/regexec.c (DYNARRAY_STRUCT, DYNARRAY_ELEMENT)
+ (DYNARRAY_PREFIX): New macros.
+ Include malloc/dynarray-skeleton.c.
+ (set_regs): Use dynarray rather than alloca.
+ * modules/regex (Depends-on): Add dynarray.
+
dynarray: new module
* config/srclist.txt: Mention the new files.
* lib/cdefs.h (__attribute_maybe_unused__): New macro,
diff --git a/lib/regex_internal.h b/lib/regex_internal.h
index e31ac9267..5d4d5fe2b 100644
--- a/lib/regex_internal.h
+++ b/lib/regex_internal.h
@@ -32,6 +32,7 @@
#include <stdbool.h>
#include <stdint.h>
+#include <dynarray.h>
#include <intprops.h>
#include <verify.h>
diff --git a/lib/regexec.c b/lib/regexec.c
index b083342f7..889b10be9 100644
--- a/lib/regexec.c
+++ b/lib/regexec.c
@@ -1355,6 +1355,12 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
return fs->stack[num].node;
}
+
+#define DYNARRAY_STRUCT regmatch_list
+#define DYNARRAY_ELEMENT regmatch_t
+#define DYNARRAY_PREFIX regmatch_list_
+#include <malloc/dynarray-skeleton.c>
+
/* Set the positions where the subexpressions are starts/ends to registers
PMATCH.
Note: We assume that pmatch[0] is already set, and
@@ -1370,8 +1376,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
re_node_set eps_via_nodes;
struct re_fail_stack_t *fs;
struct re_fail_stack_t fs_body = { 0, 2, NULL };
- regmatch_t *prev_idx_match;
- bool prev_idx_match_malloced = false;
+ struct regmatch_list prev_match;
+ regmatch_list_init (&prev_match);
DEBUG_ASSERT (nmatch > 1);
DEBUG_ASSERT (mctx->state_log != NULL);
@@ -1388,18 +1394,13 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
cur_node = dfa->init_node;
re_node_set_init_empty (&eps_via_nodes);
- if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
- prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
- else
+ if (!regmatch_list_resize (&prev_match, nmatch))
{
- prev_idx_match = re_malloc (regmatch_t, nmatch);
- if (prev_idx_match == NULL)
- {
- free_fail_stack_return (fs);
- return REG_ESPACE;
- }
- prev_idx_match_malloced = true;
+ regmatch_list_free (&prev_match);
+ free_fail_stack_return (fs);
+ return REG_ESPACE;
}
+ regmatch_t *prev_idx_match = regmatch_list_begin (&prev_match);
memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
@@ -1417,8 +1418,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
if (reg_idx == nmatch)
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_match);
return free_fail_stack_return (fs);
}
cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
@@ -1427,8 +1427,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
else
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_match);
return REG_NOERROR;
}
}
@@ -1442,8 +1441,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
if (__glibc_unlikely (cur_node == -2))
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_match);
free_fail_stack_return (fs);
return REG_ESPACE;
}
@@ -1453,15 +1451,13 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
else
{
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_match);
return REG_NOMATCH;
}
}
}
re_node_set_free (&eps_via_nodes);
- if (prev_idx_match_malloced)
- re_free (prev_idx_match);
+ regmatch_list_free (&prev_match);
return free_fail_stack_return (fs);
}
diff --git a/modules/regex b/modules/regex
index 570b0bd55..39297dfe3 100644
--- a/modules/regex
+++ b/modules/regex
@@ -19,6 +19,7 @@ ssize_t
alloca-opt [test $ac_use_included_regex = yes]
btowc [test $ac_use_included_regex = yes]
builtin-expect [test $ac_use_included_regex = yes]
+dynarray [test $ac_use_included_regex = yes]
intprops [test $ac_use_included_regex = yes]
langinfo [test $ac_use_included_regex = yes]
libc-config [test $ac_use_included_regex = yes]
--
2.27.0
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] posix: Remove alloca usage on regex build_trtable
2021-01-06 18:17 ` [PATCH 2/3] posix: Remove alloca usage on regex build_trtable Adhemerval Zanella
@ 2021-01-08 22:30 ` Paul Eggert
2021-01-11 12:31 ` Adhemerval Zanella
0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2021-01-08 22:30 UTC (permalink / raw)
To: Adhemerval Zanella; +Cc: bug-gnulib, libc-alpha
[-- Attachment #1: Type: text/plain, Size: 598 bytes --]
On 1/6/21 10:17 AM, Adhemerval Zanella wrote:
> __libc_use_alloca/alloca is replaced with malloc regardless.
These allocations are so small that they should be put on the stack
instead of using malloc. I did that in Gnulib by installing the attached
patch. The idea is that the resulting regexec.c file should be copyable
unchanged into glibc.
From a Gnulib point of view this code uses a 20 KiB frame (on a 64-bit
host) which goes past the usual 4032-byte limit for stack frames, but I
think we can stretch the point here. In glibc the limit is 64 KiB so
there's no problem.
[-- Attachment #2: 0001-regexec-remove-alloca-usage-in-build_trtable.patch --]
[-- Type: text/x-patch, Size: 7203 bytes --]
From 025e89118912adaa309374201c9012f6fb46d583 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 8 Jan 2021 14:22:15 -0800
Subject: [PATCH] regexec: remove alloca usage in build_trtable
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Prompted by this different change proposed by Adhemerval Zanella:
https://sourceware.org/pipermail/libc-alpha/2021-January/121373.html
* lib/regexec.c (build_trtable): Prevent inlining,
so that it doesn’t bloat the caller’s stack.
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.
Although Gnulib traditionally has used a 4 KiB cutoff, going to 20
KiB here should not be a significant problem in practice;
Gnulib-using packages concerned about overflow of tiny stacks can
compile with something like gcc -fstack-clash-protection.
* config/srclist.txt: Comment out regexec.c for now.
---
ChangeLog | 14 +++++++++
config/srclist.txt | 2 +-
lib/regexec.c | 75 ++++++++--------------------------------------
3 files changed, 28 insertions(+), 63 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 540f15a3c..708a266b0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,19 @@
2021-01-08 Paul Eggert <eggert@cs.ucla.edu>
+ regexec: remove alloca usage in build_trtable
+ Prompted by this different change proposed by Adhemerval Zanella:
+ https://sourceware.org/pipermail/libc-alpha/2021-January/121373.html
+ * lib/regexec.c (build_trtable): Prevent inlining,
+ so that it doesn’t bloat the caller’s stack.
+ 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.
+ Although Gnulib traditionally has used a 4 KiB cutoff, going to 20
+ KiB here should not be a significant problem in practice;
+ Gnulib-using packages concerned about overflow of tiny stacks can
+ compile with something like gcc -fstack-clash-protection.
+
scratch_buffer: add scratch_buffer_dupfree macro
* lib/scratch_buffer.h (__libc_scratch_buffer_dupfree):
New macro, needed to support recent changes in this module.
diff --git a/config/srclist.txt b/config/srclist.txt
index e7ceeb088..d669fd8f0 100644
--- a/config/srclist.txt
+++ b/config/srclist.txt
@@ -69,7 +69,7 @@ $LIBCSRC posix/regex.c lib
#$LIBCSRC posix/regex.h lib
#$LIBCSRC posix/regex_internal.c lib
#$LIBCSRC posix/regex_internal.h lib
-$LIBCSRC posix/regexec.c lib
+#$LIBCSRC posix/regexec.c lib
#$LIBCSRC stdlib/canonicalize lib/canonicalize-lgpl.c
#$LIBCSRC sysdeps/generic/eloop-threshold.h lib
$LIBCSRC time/timegm.c lib
diff --git a/lib/regexec.c b/lib/regexec.c
index 889b10be9..f7b4f9cfc 100644
--- a/lib/regexec.c
+++ b/lib/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;
}
--
2.27.0
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 3/3] posix: Remove alloca definition from regex
2021-01-06 18:17 ` [PATCH 3/3] posix: Remove alloca definition from regex Adhemerval Zanella
@ 2021-01-09 1:20 ` Paul Eggert
2021-01-11 12:33 ` Adhemerval Zanella
0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2021-01-09 1:20 UTC (permalink / raw)
To: Adhemerval Zanella; +Cc: bug-gnulib, libc-alpha
[-- Attachment #1: Type: text/plain, Size: 207 bytes --]
This patch looks good for glibc, once the previous two regex patches are
done. I installed it into Gnulib by applying the attached, so that
regex_internal.h can stay in lock-step between Gnulib and glibc.
[-- Attachment #2: 0001-regex-stop-using-alloca.patch --]
[-- Type: text/x-patch, Size: 2653 bytes --]
From 87ed1f9c4bc4ae9e98e1293465a5b3a929b9c3f9 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 8 Jan 2021 17:17:32 -0800
Subject: [PATCH] regex: stop using alloca
* lib/regex_internal.h: Do not include <alloca.h> or define
__libc_use_alloca or alloca. Patch written by Adhemerval Zanella:
https://sourceware.org/pipermail/libc-alpha/2021-January/121374.html
* modules/regex (Depends-on): Remove alloca-opt.
---
ChangeLog | 6 ++++++
lib/regex_internal.h | 19 -------------------
modules/regex | 1 -
3 files changed, 6 insertions(+), 20 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 708a266b0..a2787f59a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2021-01-08 Paul Eggert <eggert@cs.ucla.edu>
+ regex: stop using alloca
+ * lib/regex_internal.h: Do not include <alloca.h> or define
+ __libc_use_alloca or alloca. Patch written by Adhemerval Zanella:
+ https://sourceware.org/pipermail/libc-alpha/2021-January/121374.html
+ * modules/regex (Depends-on): Remove alloca-opt.
+
regexec: remove alloca usage in build_trtable
Prompted by this different change proposed by Adhemerval Zanella:
https://sourceware.org/pipermail/libc-alpha/2021-January/121373.html
diff --git a/lib/regex_internal.h b/lib/regex_internal.h
index 5d4d5fe2b..b4f91d9ec 100644
--- a/lib/regex_internal.h
+++ b/lib/regex_internal.h
@@ -445,25 +445,6 @@ typedef struct re_dfa_t re_dfa_t;
#define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
#define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
-#if defined _LIBC || HAVE_ALLOCA
-# include <alloca.h>
-#endif
-
-#ifndef _LIBC
-# if HAVE_ALLOCA
-/* The OS usually guarantees only one guard page at the bottom of the stack,
- and a page size can be as small as 4096 bytes. So we cannot safely
- allocate anything larger than 4096 bytes. Also care for the possibility
- of a few compiler-allocated temporary stack slots. */
-# define __libc_use_alloca(n) ((n) < 4032)
-# else
-/* alloca is implemented with malloc, so just use malloc. */
-# define __libc_use_alloca(n) 0
-# undef alloca
-# define alloca(n) malloc (n)
-# endif
-#endif
-
#ifdef _LIBC
# define MALLOC_0_IS_NONNULL 1
#elif !defined MALLOC_0_IS_NONNULL
diff --git a/modules/regex b/modules/regex
index 39297dfe3..20cbe375a 100644
--- a/modules/regex
+++ b/modules/regex
@@ -16,7 +16,6 @@ Depends-on:
c99
extensions
ssize_t
-alloca-opt [test $ac_use_included_regex = yes]
btowc [test $ac_use_included_regex = yes]
builtin-expect [test $ac_use_included_regex = yes]
dynarray [test $ac_use_included_regex = yes]
--
2.27.0
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] posix: Remove alloca usage on regex set_regs
2021-01-06 18:17 [PATCH 1/3] posix: Remove alloca usage on regex set_regs Adhemerval Zanella
` (2 preceding siblings ...)
2021-01-08 20:14 ` [PATCH 1/3] posix: Remove alloca usage on regex set_regs Paul Eggert
@ 2021-01-09 1:24 ` Darshit Shah
2021-01-09 3:54 ` Paul Eggert
3 siblings, 1 reply; 11+ messages in thread
From: Darshit Shah @ 2021-01-09 1:24 UTC (permalink / raw)
To: Adhemerval Zanella, libc-alpha, Paul Eggert, bug-gnulib
Hi,
Since this patch has been applied, GNU Wget fails during the linking
stage due to regmatch_list_free not being available:
/usr/bin/ld: ../lib/libgnu.a(regex.o): in function `set_regs':
/home/rincewind/Programming/wget/lib/regexec.c:1444: undefined reference
to `regmatch_list_free'
/usr/bin/ld: /home/rincewind/Programming/wget/lib/regexec.c:1421:
undefined reference to `regmatch_list_free'
/usr/bin/ld: /home/rincewind/Programming/wget/lib/regexec.c:1454:
undefined reference to `regmatch_list_free'
/usr/bin/ld: /home/rincewind/Programming/wget/lib/regexec.c:1444:
undefined reference to `regmatch_list_free'
/usr/bin/ld: /home/rincewind/Programming/wget/lib/regexec.c:1430:
undefined reference to `regmatch_list_free'
/usr/bin/ld:
../lib/libgnu.a(regex.o):/home/rincewind/Programming/wget/lib/regexec.c:1460:
more undefined references to `regmatch_list_free' follow
On 06.01.21 19:17, Adhemerval Zanella wrote:
> It replaces the regmatch_t with a dynarray list.
>
> Checked on x86_64-linux-gnu.
> ---
> posix/regexec.c | 62 ++++++++++++++++++++++++-------------------------
> 1 file changed, 31 insertions(+), 31 deletions(-)
>
> diff --git a/posix/regexec.c b/posix/regexec.c
> index b083342f77..5e22f90842 100644
> --- a/posix/regexec.c
> +++ b/posix/regexec.c
> @@ -54,9 +54,6 @@ static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
> Idx *p_match_first);
> static Idx check_halt_state_context (const re_match_context_t *mctx,
> const re_dfastate_t *state, Idx idx);
> -static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
> - regmatch_t *prev_idx_match, Idx cur_node,
> - Idx cur_idx, Idx nmatch);
> static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
> Idx str_idx, Idx dest_node, Idx nregs,
> regmatch_t *regs,
> @@ -1355,6 +1352,16 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
> return fs->stack[num].node;
> }
>
> +
> +#define DYNARRAY_STRUCT regmatch_list
> +#define DYNARRAY_ELEMENT regmatch_t
> +#define DYNARRAY_PREFIX regmatch_list_
> +#include <malloc/dynarray-skeleton.c>
> +
> +static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
> + struct regmatch_list *prev_idx_match, Idx cur_node,
> + Idx cur_idx, Idx nmatch);
> +
> /* Set the positions where the subexpressions are starts/ends to registers
> PMATCH.
> Note: We assume that pmatch[0] is already set, and
> @@ -1370,8 +1377,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> re_node_set eps_via_nodes;
> struct re_fail_stack_t *fs;
> struct re_fail_stack_t fs_body = { 0, 2, NULL };
> - regmatch_t *prev_idx_match;
> - bool prev_idx_match_malloced = false;
> + struct regmatch_list prev_idx_match;
> + regmatch_list_init (&prev_idx_match);
>
> DEBUG_ASSERT (nmatch > 1);
> DEBUG_ASSERT (mctx->state_log != NULL);
> @@ -1388,23 +1395,18 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> cur_node = dfa->init_node;
> re_node_set_init_empty (&eps_via_nodes);
>
> - if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
> - prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
> - else
> + if (!regmatch_list_resize (&prev_idx_match, nmatch))
> {
> - prev_idx_match = re_malloc (regmatch_t, nmatch);
> - if (prev_idx_match == NULL)
> - {
> - free_fail_stack_return (fs);
> - return REG_ESPACE;
> - }
> - prev_idx_match_malloced = true;
> + regmatch_list_free (&prev_idx_match);
> + free_fail_stack_return (fs);
> + return REG_ESPACE;
> }
> - memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
> + for (size_t i = 0; i < nmatch; i++)
> + *regmatch_list_at (&prev_idx_match, i) = pmatch[i];
>
> for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
> {
> - update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
> + update_regs (dfa, pmatch, &prev_idx_match, cur_node, idx, nmatch);
>
> if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
> {
> @@ -1417,8 +1419,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> if (reg_idx == nmatch)
> {
> re_node_set_free (&eps_via_nodes);
> - if (prev_idx_match_malloced)
> - re_free (prev_idx_match);
> + regmatch_list_free (&prev_idx_match);
> return free_fail_stack_return (fs);
> }
> cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
> @@ -1427,8 +1428,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> else
> {
> re_node_set_free (&eps_via_nodes);
> - if (prev_idx_match_malloced)
> - re_free (prev_idx_match);
> + regmatch_list_free (&prev_idx_match);
> return REG_NOERROR;
> }
> }
> @@ -1442,8 +1442,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> if (__glibc_unlikely (cur_node == -2))
> {
> re_node_set_free (&eps_via_nodes);
> - if (prev_idx_match_malloced)
> - re_free (prev_idx_match);
> + regmatch_list_free (&prev_idx_match);
> free_fail_stack_return (fs);
> return REG_ESPACE;
> }
> @@ -1453,15 +1452,13 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
> else
> {
> re_node_set_free (&eps_via_nodes);
> - if (prev_idx_match_malloced)
> - re_free (prev_idx_match);
> + regmatch_list_free (&prev_idx_match);
> return REG_NOMATCH;
> }
> }
> }
> re_node_set_free (&eps_via_nodes);
> - if (prev_idx_match_malloced)
> - re_free (prev_idx_match);
> + regmatch_list_free (&prev_idx_match);
> return free_fail_stack_return (fs);
> }
>
> @@ -1483,7 +1480,8 @@ free_fail_stack_return (struct re_fail_stack_t *fs)
>
> static void
> update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
> - regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
> + struct regmatch_list *prev_idx_match, Idx cur_node, Idx cur_idx,
> + Idx nmatch)
> {
> int type = dfa->nodes[cur_node].type;
> if (type == OP_OPEN_SUBEXP)
> @@ -1508,18 +1506,20 @@ update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
> pmatch[reg_num].rm_eo = cur_idx;
> /* This is a non-empty match or we are not inside an optional
> subexpression. Accept this right away. */
> - memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
> + for (size_t i = 0; i < nmatch; i++)
> + *regmatch_list_at (prev_idx_match, i) = pmatch[i];
> }
> else
> {
> if (dfa->nodes[cur_node].opt_subexp
> - && prev_idx_match[reg_num].rm_so != -1)
> + && regmatch_list_at (prev_idx_match, reg_num)->rm_so != -1)
> /* We transited through an empty match for an optional
> subexpression, like (a?)*, and this is not the subexp's
> first match. Copy back the old content of the registers
> so that matches of an inner subexpression are undone as
> well, like in ((a?))*. */
> - memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
> + memcpy (pmatch, regmatch_list_begin (prev_idx_match),
> + sizeof (regmatch_t) * nmatch);
> else
> /* We completed a subexpression, but it may be part of
> an optional one, so do not update PREV_IDX_MATCH. */
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] posix: Remove alloca usage on regex set_regs
2021-01-09 1:24 ` Darshit Shah
@ 2021-01-09 3:54 ` Paul Eggert
0 siblings, 0 replies; 11+ messages in thread
From: Paul Eggert @ 2021-01-09 3:54 UTC (permalink / raw)
To: Darshit Shah; +Cc: bug-gnulib, libc-alpha, Adhemerval Zanella
[-- Attachment #1: Type: text/plain, Size: 411 bytes --]
On 1/8/21 5:24 PM, Darshit Shah wrote:
> /home/rincewind/Programming/wget/lib/regexec.c:1444: undefined reference
> to `regmatch_list_free'
Oof, it's because Gnulib's replacement of 'free' with 'rpl_free' caused
the function definition to be named 'regmatch_list_rpl_free'.
Thanks for reporting it. I installed the attached hack into Gnulib to
work around the problem. This should work with glibc as well.
[-- Attachment #2: 0001-dynarray-work-even-if-free-is-replaced.patch --]
[-- Type: text/x-patch, Size: 2990 bytes --]
From 1b50e7d4d63fee04dbe06d4a58f3061c569fede8 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 8 Jan 2021 19:50:16 -0800
Subject: [PATCH] =?UTF-8?q?dynarray:=20work=20even=20if=20=E2=80=98free?=
=?UTF-8?q?=E2=80=99=20is=20replaced?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Problem reported by Darshit Shah in:
https://lists.gnu.org/r/bug-gnulib/2021-01/msg00140.html
* lib/malloc/dynarray-skeleton.c (DYNARRAY_FREE): New macro.
Use it everywhere instead of DYNARRAY_NAME (free).
---
ChangeLog | 6 ++++++
lib/malloc/dynarray-skeleton.c | 10 +++++++---
2 files changed, 13 insertions(+), 3 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index b76330e5b..1e589aac3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2021-01-08 Paul Eggert <eggert@cs.ucla.edu>
+ dynarray: work even if ‘free’ is replaced
+ Problem reported by Darshit Shah in:
+ https://lists.gnu.org/r/bug-gnulib/2021-01/msg00140.html
+ * lib/malloc/dynarray-skeleton.c (DYNARRAY_FREE): New macro.
+ Use it everywhere instead of DYNARRAY_NAME (free).
+
tempname: don’t block for minutes
Derived from a patch proposed by Adhemerval Zanella in:
https://sourceware.org/pipermail/libc-alpha/2021-January/121302.html
diff --git a/lib/malloc/dynarray-skeleton.c b/lib/malloc/dynarray-skeleton.c
index fe886102c..5b9f37bdd 100644
--- a/lib/malloc/dynarray-skeleton.c
+++ b/lib/malloc/dynarray-skeleton.c
@@ -150,6 +150,10 @@ struct DYNARRAY_STRUCT
#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name)
#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name)
+/* Use DYNARRAY_FREE instead of DYNARRAY_NAME (free),
+ so that Gnulib does not change 'free' to 'rpl_free'. */
+#define DYNARRAY_FREE DYNARRAY_CONCAT1 (DYNARRAY_NAME (f), ree)
+
/* Address of the scratch buffer if any. */
#if DYNARRAY_HAVE_SCRATCH
# define DYNARRAY_SCRATCH(list) (list)->scratch
@@ -200,7 +204,7 @@ DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
/* Deallocate the dynamic array and its elements. */
__attribute_maybe_unused__ __nonnull ((1))
static void
-DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
+DYNARRAY_FREE (struct DYNARRAY_STRUCT *list)
{
DYNARRAY_NAME (free__elements__)
(list->u.dynarray_header.array, list->u.dynarray_header.used);
@@ -466,7 +470,7 @@ DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
else
{
/* On error, we need to free all data. */
- DYNARRAY_NAME (free) (list);
+ DYNARRAY_FREE (list);
errno = ENOMEM;
return false;
}
@@ -497,7 +501,7 @@ DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
else
{
/* On error, we need to free all data. */
- DYNARRAY_NAME (free) (list);
+ DYNARRAY_FREE (list);
errno = ENOMEM;
return NULL;
}
--
2.27.0
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH 2/3] posix: Remove alloca usage on regex build_trtable
2021-01-08 22:30 ` Paul Eggert
@ 2021-01-11 12:31 ` Adhemerval Zanella
0 siblings, 0 replies; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-11 12:31 UTC (permalink / raw)
To: Paul Eggert; +Cc: bug-gnulib, libc-alpha
On 08/01/2021 19:30, Paul Eggert wrote:
> On 1/6/21 10:17 AM, Adhemerval Zanella wrote:
>> __libc_use_alloca/alloca is replaced with malloc regardless.
>
> These allocations are so small that they should be put on the stack instead of using malloc. I did that in Gnulib by installing the attached patch. The idea is that the resulting regexec.c file should be copyable unchanged into glibc.
>
> From a Gnulib point of view this code uses a 20 KiB frame (on a 64-bit host) which goes past the usual 4032-byte limit for stack frames, but I think we can stretch the point here. In glibc the limit is 64 KiB so there's no problem.
Right, I think we can maybe use scratch_buffer for these or even a dynamic array
with a more proper initial size as an improvement.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 3/3] posix: Remove alloca definition from regex
2021-01-09 1:20 ` Paul Eggert
@ 2021-01-11 12:33 ` Adhemerval Zanella
0 siblings, 0 replies; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-11 12:33 UTC (permalink / raw)
To: Paul Eggert; +Cc: bug-gnulib, libc-alpha
On 08/01/2021 22:20, Paul Eggert wrote:
> This patch looks good for glibc, once the previous two regex patches are done. I installed it into Gnulib by applying the attached, so that regex_internal.h can stay in lock-step between Gnulib and glibc.
Right, I will sync the regex code with gnulib. Thanks for checking
on this.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 1/3] posix: Remove alloca usage on regex set_regs
2021-01-08 20:14 ` [PATCH 1/3] posix: Remove alloca usage on regex set_regs Paul Eggert
@ 2021-01-11 12:35 ` Adhemerval Zanella
0 siblings, 0 replies; 11+ messages in thread
From: Adhemerval Zanella @ 2021-01-11 12:35 UTC (permalink / raw)
To: Paul Eggert; +Cc: bug-gnulib, libc-alpha
On 08/01/2021 17:14, Paul Eggert wrote:
> On 1/6/21 10:17 AM, Adhemerval Zanella wrote:
>> It replaces the regmatch_t with a dynarray list.
>
> regexec.c is shared with Gnulib, so some work needed to be done on the Gnulib side for this patch since Gnulib didn't have dynarray. Dynarray is something I've been meaning to add to Gnulib for some time, so I did that by installing the first attached patch into Gnulib. Could you please propagate the new Gnulib dynarray sources into glibc so that they stay in sync? As near as I can make out, the glibc dynarray files can now be identical to the new Gnulib files; if not, please let me know.
I will check and sync the differences.
>
>
>> posix/regexec.c | 62 ++++++++++++++++++++++++-------------------------
>> 1 file changed, 31 insertions(+), 31 deletions(-)
>> ...
>> @@ -1355,6 +1352,16 @@ pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
>> return fs->stack[num].node;
>> }
>> +
>> +#define DYNARRAY_STRUCT regmatch_list
>> +#define DYNARRAY_ELEMENT regmatch_t
>> +#define DYNARRAY_PREFIX regmatch_list_
>> +#include <malloc/dynarray-skeleton.c>
>> +
>> +static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
>> + struct regmatch_list *prev_idx_match, Idx cur_node,
>> + Idx cur_idx, Idx nmatch);
>> +
>> /* Set the positions where the subexpressions are starts/ends to registers
>> PMATCH.
>> Note: We assume that pmatch[0] is already set, and
>> @@ -1370,8 +1377,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>> re_node_set eps_via_nodes;
>> struct re_fail_stack_t *fs;
>> struct re_fail_stack_t fs_body = { 0, 2, NULL };
>> - regmatch_t *prev_idx_match;
>> - bool prev_idx_match_malloced = false;
>> + struct regmatch_list prev_idx_match;
>> + regmatch_list_init (&prev_idx_match);
>> DEBUG_ASSERT (nmatch > 1);
>> DEBUG_ASSERT (mctx->state_log != NULL);
>> @@ -1388,23 +1395,18 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>> cur_node = dfa->init_node;
>> re_node_set_init_empty (&eps_via_nodes);
>> - if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
>> - prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
>> - else
>> + if (!regmatch_list_resize (&prev_idx_match, nmatch))
>> {
>> - prev_idx_match = re_malloc (regmatch_t, nmatch);
>> - if (prev_idx_match == NULL)
>> - {
>> - free_fail_stack_return (fs);
>> - return REG_ESPACE;
>> - }
>> - prev_idx_match_malloced = true;
>> + regmatch_list_free (&prev_idx_match);
>> + free_fail_stack_return (fs);
>> + return REG_ESPACE;
>> }
>
> These three hunks are good, but you can omit most of the other hunks (and improve performance a bit) by inserting the following line after the 3rd hunk:
>
> + regmatch_t *prev_idx_match = regmatch_list_begin (&prev_match);
>
> since the dynarray doesn't grow after that and this means you don't need to change the rest of the code to use prev_match rather than prev_idx_match. The only other hunks you need to retain are the ones replacing re_free with regmastch_list_free.
>
> I've made this improvement to Gnulib by installing the second attached patch, so you should be able to copy Gnulib regexec.c to glibc without changing it.
Ok, I will check and sync with gnulib.
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2021-01-11 12:57 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-01-06 18:17 [PATCH 1/3] posix: Remove alloca usage on regex set_regs Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 2/3] posix: Remove alloca usage on regex build_trtable Adhemerval Zanella
2021-01-08 22:30 ` Paul Eggert
2021-01-11 12:31 ` Adhemerval Zanella
2021-01-06 18:17 ` [PATCH 3/3] posix: Remove alloca definition from regex Adhemerval Zanella
2021-01-09 1:20 ` Paul Eggert
2021-01-11 12:33 ` Adhemerval Zanella
2021-01-08 20:14 ` [PATCH 1/3] posix: Remove alloca usage on regex set_regs Paul Eggert
2021-01-11 12:35 ` Adhemerval Zanella
2021-01-09 1:24 ` Darshit Shah
2021-01-09 3:54 ` Paul Eggert
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).