Update from Gnulib by running admin/merge-gnulib

10 files changed, 975 insertions, 3 deletions

diff --git a/lib/malloc/dynarray-skeleton.c b/lib/malloc/dynarray-skeleton.c
new file mode 100644
index 00000000000..4995fd1c049
--- /dev/null
+++ b/lib/malloc/dynarray-skeleton.c
@@ -0,0 +1,525 @@
+/* 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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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)
+
+/* 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
+#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_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_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_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 00000000000..84e4394bf32
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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 00000000000..a4424593748
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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 00000000000..7ac4b6db403
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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 00000000000..be9441e313d
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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 00000000000..92bbddd4461
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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 00000000000..99c2cc87c31
--- /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 General Public
+   License as published by the Free Software Foundation; either
+   version 3 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
+   General Public License for more details.
+
+   You should have received a copy of the GNU 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/lib/malloc/scratch_buffer_grow.c b/lib/malloc/scratch_buffer_grow.c
index 41befe3d65f..e7606d81cd7 100644
--- a/lib/malloc/scratch_buffer_grow.c
+++ b/lib/malloc/scratch_buffer_grow.c
@@ -1,5 +1,5 @@
 /* Variable-sized buffer with on-stack default allocation.
-   Copyright (C) 2015-2020 Free Software Foundation, Inc.
+   Copyright (C) 2015-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
diff --git a/lib/malloc/scratch_buffer_grow_preserve.c b/lib/malloc/scratch_buffer_grow_preserve.c
index aef232938d5..59f8c710001 100644
--- a/lib/malloc/scratch_buffer_grow_preserve.c
+++ b/lib/malloc/scratch_buffer_grow_preserve.c
@@ -1,5 +1,5 @@
 /* Variable-sized buffer with on-stack default allocation.
-   Copyright (C) 2015-2020 Free Software Foundation, Inc.
+   Copyright (C) 2015-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
diff --git a/lib/malloc/scratch_buffer_set_array_size.c b/lib/malloc/scratch_buffer_set_array_size.c
index 5f5e4c24f5a..e2b9f31211a 100644
--- a/lib/malloc/scratch_buffer_set_array_size.c
+++ b/lib/malloc/scratch_buffer_set_array_size.c
@@ -1,5 +1,5 @@
 /* Variable-sized buffer with on-stack default allocation.
-   Copyright (C) 2015-2020 Free Software Foundation, Inc.
+   Copyright (C) 2015-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