* 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 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