Add internal facility for dynamic array handling

This is intended as a type-safe alternative to obstacks and
hand-written realloc constructs.  The implementation avoids
writing function pointers to the heap.

13 files changed, 2101 insertions, 2 deletions

diff --git a/malloc/Makefile b/malloc/Makefile
index b7d4c63920..af025cbb24 100644
--- a/malloc/Makefile
+++ b/malloc/Makefile
@@ -41,17 +41,28 @@ tests-static := \
 
 tests-internal := tst-mallocstate tst-scratch_buffer
 
+# The dynarray framework is only available inside glibc.
+tests-internal += \
+	 tst-dynarray \
+	 tst-dynarray-fail \
+	 tst-dynarray-at-fail \
+
 ifneq (no,$(have-tunables))
 tests += tst-malloc-usable-tunables
 tests-static += tst-malloc-usable-static-tunables
 endif
 
 tests += $(tests-static)
-test-srcs = tst-mtrace
+test-srcs = tst-mtrace tst-dynarray tst-dynarray-fail
 
 routines = malloc morecore mcheck mtrace obstack reallocarray \
   scratch_buffer_grow scratch_buffer_grow_preserve \
-  scratch_buffer_set_array_size
+  scratch_buffer_set_array_size \
+  dynarray_at_failure \
+  dynarray_emplace_enlarge \
+  dynarray_finalize \
+  dynarray_resize \
+  dynarray_resize_clear \
 
 install-lib := libmcheck.a
 non-lib.a := libmcheck.a
@@ -137,6 +148,8 @@ ifeq ($(run-built-tests),yes)
 ifeq (yes,$(build-shared))
 ifneq ($(PERL),no)
 tests-special += $(objpfx)tst-mtrace.out
+tests-special += $(objpfx)tst-dynarray-mem.out
+tests-special += $(objpfx)tst-dynarray-fail-mem.out
 endif
 endif
 endif
@@ -208,3 +221,13 @@ $(objpfx)tst-interpose-thread: \
 $(objpfx)tst-interpose-static-nothread: $(objpfx)tst-interpose-aux-nothread.o
 $(objpfx)tst-interpose-static-thread: \
   $(objpfx)tst-interpose-aux-thread.o $(static-thread-library)
+
+tst-dynarray-ENV = MALLOC_TRACE=$(objpfx)tst-dynarray.mtrace
+$(objpfx)tst-dynarray-mem.out: $(objpfx)tst-dynarray.out
+	$(common-objpfx)malloc/mtrace $(objpfx)tst-dynarray.mtrace > $@; \
+	$(evaluate-test)
+
+tst-dynarray-fail-ENV = MALLOC_TRACE=$(objpfx)tst-dynarray-fail.mtrace
+$(objpfx)tst-dynarray-fail-mem.out: $(objpfx)tst-dynarray-fail.out
+	$(common-objpfx)malloc/mtrace $(objpfx)tst-dynarray-fail.mtrace > $@; \
+	$(evaluate-test)
diff --git a/malloc/Versions b/malloc/Versions
index 23aafb5ccc..5b543069b3 100644
--- a/malloc/Versions
+++ b/malloc/Versions
@@ -76,7 +76,15 @@ libc {
     __libc_scratch_buffer_grow_preserve;
     __libc_scratch_buffer_set_array_size;
 
+
     # Internal name for reallocarray
     __libc_reallocarray;
+
+    # dynarray support
+    __libc_dynarray_at_failure;
+    __libc_dynarray_emplace_enlarge;
+    __libc_dynarray_finalize;
+    __libc_dynarray_resize;
+    __libc_dynarray_resize_clear;
   }
 }
diff --git a/malloc/dynarray-skeleton.c b/malloc/dynarray-skeleton.c
new file mode 100644
index 0000000000..7a10e083f4
--- /dev/null
+++ b/malloc/dynarray-skeleton.c
@@ -0,0 +1,499 @@
+/* Type-safe arrays which grow dynamically.
+   Copyright (C) 2017 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
+   <http://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##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;
+  };
+
+#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->dynarray_header.array != list->scratch)
+    free (list->dynarray_header.array);
+#else
+  free (list->dynarray_header.array);
+#endif
+}
+
+/* Public functions.  */
+
+/* Initialize a dynamic array object.  This must be called before any
+   use of the object.  */
+__attribute__ ((nonnull (1)))
+static void
+DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
+{
+  list->dynarray_header.used = 0;
+  list->dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
+  list->dynarray_header.array = DYNARRAY_SCRATCH (list);
+}
+
+/* Deallocate the dynamic array and its elements.  */
+__attribute__ ((unused, nonnull (1)))
+static void
+DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
+{
+  DYNARRAY_NAME (free__elements__)
+    (list->dynarray_header.array, list->dynarray_header.used);
+  DYNARRAY_NAME (free__array__) (list);
+  DYNARRAY_NAME (init) (list);
+}
+
+/* Return true if the dynamic array is in an error state.  */
+__attribute__ ((nonnull (1)))
+static inline bool
+DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
+{
+  return list->dynarray_header.allocated == __dynarray_error_marker ();
+}
+
+/* Mark the dynamic array as failed.  All elements are deallocated as
+   a side effect.  */
+__attribute__ ((nonnull (1)))
+static void
+DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
+{
+  DYNARRAY_NAME (free__elements__)
+    (list->dynarray_header.array, list->dynarray_header.used);
+  DYNARRAY_NAME (free__array__) (list);
+  list->dynarray_header.array = DYNARRAY_SCRATCH (list);
+  list->dynarray_header.used = 0;
+  list->dynarray_header.allocated = __dynarray_error_marker ();
+}
+
+/* Return the number of elements which have been added to the dynamic
+   array.  */
+__attribute__ ((nonnull (1)))
+static inline size_t
+DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
+{
+  return list->dynarray_header.used;
+}
+
+/* Return a pointer to the array element at INDEX.  Terminate the
+   process if INDEX is out of bounds.  */
+__attribute__ ((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->dynarray_header.array + index;
+}
+
+/* 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->dynarray_abstract,
+                                         DYNARRAY_SCRATCH (list),
+                                         sizeof (DYNARRAY_ELEMENT))))
+    {
+      DYNARRAY_NAME (mark_failed) (list);
+      return;
+    }
+
+  /* Copy the new element and increase the array length.  */
+  list->dynarray_header.array[list->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.  */
+__attribute__ ((unused, 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->dynarray_header.used
+                        == list->dynarray_header.allocated))
+    {
+      DYNARRAY_NAME (add__) (list, item);
+      return;
+    }
+
+  /* Copy the new element and increase the array length.  */
+  list->dynarray_header.array[list->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->dynarray_header.array[list->dynarray_header.used];
+  ++list->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->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__ ((unused, 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->dynarray_header.used
+                        == list->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__ ((unused, nonnull (1)))
+static bool
+DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
+{
+  if (size > list->dynarray_header.used)
+    {
+      bool ok;
+#if defined (DYNARRAY_ELEMENT_INIT)
+      /* The new elements have to be initialized.  */
+      size_t old_size = list->dynarray_header.used;
+      ok = __libc_dynarray_resize (&list->dynarray_abstract,
+                                   size, DYNARRAY_SCRATCH (list),
+                                   sizeof (DYNARRAY_ELEMENT));
+      if (ok)
+        for (size_t i = old_size; i < size; ++i)
+          {
+            DYNARRAY_ELEMENT_INIT (&list->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->dynarray_abstract, size,
+         DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
+#else
+      ok =  __libc_dynarray_resize (&list->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->dynarray_header.array + size,
+         list->dynarray_header.used - size);
+      list->dynarray_header.used = size;
+      return true;
+    }
+}
+
+/* Remove the last element of LIST if it is present.  */
+__attribute__ ((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->dynarray_header.used > 0)
+    {
+      size_t new_length = list->dynarray_header.used - 1;
+#ifdef DYNARRAY_ELEMENT_FREE
+      DYNARRAY_ELEMENT_FREE (&list->dynarray_header.array[new_length]);
+#endif
+      list->dynarray_header.used = new_length;
+    }
+}
+
+/* Remove all elements from the list.  The elements are freed, but the
+   list itself is not.  */
+__attribute__ ((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->dynarray_header.array, list->dynarray_header.used);
+  list->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__ ((unused, 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->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__ ((unused, 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->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/malloc/dynarray.h b/malloc/dynarray.h
new file mode 100644
index 0000000000..c73e08b6cf
--- /dev/null
+++ b/malloc/dynarray.h
@@ -0,0 +1,176 @@
+/* Type-safe arrays which grow dynamically.  Shared definitions.
+   Copyright (C) 2017 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
+   <http://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);
+libc_hidden_proto (__libc_dynarray_emplace_enlarge)
+
+/* 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);
+libc_hidden_proto (__libc_dynarray_resize)
+
+/* 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);
+libc_hidden_proto (__libc_dynarray_resize_clear)
+
+/* 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);
+libc_hidden_proto (__libc_dynarray_finalize)
+
+
+/* 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.  */
+void __libc_dynarray_at_failure (size_t size, size_t index)
+  __attribute__ ((noreturn));
+libc_hidden_proto (__libc_dynarray_at_failure)
+
+#endif /* _DYNARRAY_H */
diff --git a/malloc/dynarray_at_failure.c b/malloc/dynarray_at_failure.c
new file mode 100644
index 0000000000..fcc06f030b
--- /dev/null
+++ b/malloc/dynarray_at_failure.c
@@ -0,0 +1,31 @@
+/* Report an dynamic array index out of bounds condition.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <dynarray.h>
+#include <stdio.h>
+
+void
+__libc_dynarray_at_failure (size_t size, size_t index)
+{
+  char buf[200];
+  __snprintf (buf, sizeof (buf), "Fatal glibc error: "
+              "array index %zu not less than array length %zu\n",
+              index, size);
+ __libc_fatal (buf);
+}
+libc_hidden_def (__libc_dynarray_at_failure)
diff --git a/malloc/dynarray_emplace_enlarge.c b/malloc/dynarray_emplace_enlarge.c
new file mode 100644
index 0000000000..dfc70017ce
--- /dev/null
+++ b/malloc/dynarray_emplace_enlarge.c
@@ -0,0 +1,69 @@
+/* Increase the size of a dynamic array in preparation of an emplace operation.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <dynarray.h>
+#include <malloc-internal.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;
+      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.  */
+        return false;
+    }
+
+  size_t new_size;
+  if (check_mul_overflow_size_t (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/malloc/dynarray_finalize.c b/malloc/dynarray_finalize.c
new file mode 100644
index 0000000000..6dd8705382
--- /dev/null
+++ b/malloc/dynarray_finalize.c
@@ -0,0 +1,62 @@
+/* Copy the dynamically-allocated area to an explicitly-sized heap allocation.
+   Copyright (C) 2017 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
+   <http://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/malloc/dynarray_resize.c b/malloc/dynarray_resize.c
new file mode 100644
index 0000000000..e6dc9fbc68
--- /dev/null
+++ b/malloc/dynarray_resize.c
@@ -0,0 +1,59 @@
+/* Increase the size of a dynamic array.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <dynarray.h>
+#include <malloc-internal.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 (check_mul_overflow_size_t (size, element_size, &new_size_bytes))
+    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/malloc/dynarray_resize_clear.c b/malloc/dynarray_resize_clear.c
new file mode 100644
index 0000000000..0c4ced1d38
--- /dev/null
+++ b/malloc/dynarray_resize_clear.c
@@ -0,0 +1,35 @@
+/* Increase the size of a dynamic array and clear the new part.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <dynarray.h>
+#include <stdlib.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.  */
+  memset (list->array + (old_size * element_size), 0,
+          (size - old_size) * element_size);
+  return true;
+}
+libc_hidden_def (__libc_dynarray_resize_clear)
diff --git a/malloc/tst-dynarray-at-fail.c b/malloc/tst-dynarray-at-fail.c
new file mode 100644
index 0000000000..bc1a48c5cb
--- /dev/null
+++ b/malloc/tst-dynarray-at-fail.c
@@ -0,0 +1,125 @@
+/* Test reporting of out-of-bounds access for dynamic arrays.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include "tst-dynarray-shared.h"
+
+#include <signal.h>
+#include <stdint.h>
+#include <string.h>
+#include <support/capture_subprocess.h>
+#include <support/check.h>
+
+/* Run CALLBACK and check that the data on standard error equals
+   EXPECTED.  */
+static void
+check (const char *test, void (*callback) (void *), size_t index,
+       const char *expected)
+{
+  struct support_capture_subprocess result
+    = support_capture_subprocess (callback, &index);
+  if (strcmp (result.err.buffer, expected) != 0)
+    {
+      support_record_failure ();
+      printf ("error: test %s (%zu) unexpected standard error data\n"
+              "  expected: %s\n"
+              "  actual:   %s\n",
+              test, index, expected, result.err.buffer);
+    }
+  TEST_VERIFY (strlen (result.out.buffer) == 0);
+  TEST_VERIFY (WIFSIGNALED (result.status));
+  if (WIFSIGNALED (result.status))
+    TEST_VERIFY (WTERMSIG (result.status) == SIGABRT);
+  support_capture_subprocess_free (&result);
+}
+
+/* Try indexing an empty array.  */
+static void
+test_empty (void *closure)
+{
+  size_t *pindex = closure;
+  struct dynarray_int dyn;
+  dynarray_int_init (&dyn);
+  dynarray_int_at (&dyn, *pindex);
+}
+
+/* Try indexing a one-element array.  */
+static void
+test_one (void *closure)
+{
+  size_t *pindex = closure;
+  struct dynarray_int dyn;
+  dynarray_int_init (&dyn);
+  TEST_VERIFY (dynarray_int_resize (&dyn, 1));
+  dynarray_int_at (&dyn, *pindex);
+}
+
+/* Try indexing a longer array.  */
+static void
+test_many (void *closure)
+{
+  size_t *pindex = closure;
+  struct dynarray_int dyn;
+  dynarray_int_init (&dyn);
+  TEST_VERIFY (dynarray_int_resize (&dyn, 5371));
+  dynarray_int_at (&dyn, *pindex);
+}
+
+/* (size_t) -1 for use in string literals.  */
+#if SIZE_WIDTH == 32
+# define MINUS_1 "4294967295"
+#elif SIZE_WIDTH == 64
+# define MINUS_1 "18446744073709551615"
+#else
+# error "unknown value for SIZE_WIDTH"
+#endif
+
+static int
+do_test (void)
+{
+  TEST_VERIFY (setenv ("LIBC_FATAL_STDERR_", "1", 1) == 0);
+
+  check ("test_empty", test_empty, 0,
+         "Fatal glibc error: array index 0 not less than array length 0\n");
+  check ("test_empty", test_empty, 1,
+         "Fatal glibc error: array index 1 not less than array length 0\n");
+  check ("test_empty", test_empty, -1,
+         "Fatal glibc error: array index " MINUS_1
+         " not less than array length 0\n");
+
+  check ("test_one", test_one, 1,
+         "Fatal glibc error: array index 1 not less than array length 1\n");
+  check ("test_one", test_one, 2,
+         "Fatal glibc error: array index 2 not less than array length 1\n");
+  check ("test_one", test_one, -1,
+         "Fatal glibc error: array index " MINUS_1
+         " not less than array length 1\n");
+
+  check ("test_many", test_many, 5371,
+         "Fatal glibc error: array index 5371"
+         " not less than array length 5371\n");
+  check ("test_many", test_many, 5372,
+         "Fatal glibc error: array index 5372"
+         " not less than array length 5371\n");
+  check ("test_many", test_many, -1,
+         "Fatal glibc error: array index " MINUS_1
+         " not less than array length 5371\n");
+
+  return 0;
+}
+
+#include <support/test-driver.c>
diff --git a/malloc/tst-dynarray-fail.c b/malloc/tst-dynarray-fail.c
new file mode 100644
index 0000000000..508dbae93e
--- /dev/null
+++ b/malloc/tst-dynarray-fail.c
@@ -0,0 +1,418 @@
+/* Test allocation failures with dynamic arrays.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+/* This test is separate from tst-dynarray because it cannot run under
+   valgrind.  */
+
+#include "tst-dynarray-shared.h"
+
+#include <mcheck.h>
+#include <stdio.h>
+#include <support/check.h>
+#include <support/support.h>
+#include <support/xunistd.h>
+#include <sys/mman.h>
+#include <sys/resource.h>
+#include <unistd.h>
+
+/* Data structure to fill up the heap.  */
+struct heap_filler
+{
+  struct heap_filler *next;
+};
+
+/* Allocate objects until the heap is full.  */
+static struct heap_filler *
+fill_heap (void)
+{
+  size_t pad = 4096;
+  struct heap_filler *head = NULL;
+  while (true)
+    {
+      struct heap_filler *new_head = malloc (sizeof (*new_head) + pad);
+      if (new_head == NULL)
+        {
+          if (pad > 0)
+            {
+              /* Try again with smaller allocations.  */
+              pad = 0;
+              continue;
+            }
+          else
+            break;
+        }
+      new_head->next = head;
+      head = new_head;
+    }
+  return head;
+}
+
+/* Free the heap-filling allocations, so that we can continue testing
+   and detect memory leaks elsewhere.  */
+static void
+free_fill_heap (struct heap_filler *head)
+{
+  while (head != NULL)
+    {
+      struct heap_filler *next = head->next;
+      free (head);
+      head = next;
+    }
+}
+
+/* Check allocation failures for int arrays (without an element free
+   function).  */
+static void
+test_int_fail (void)
+{
+  /* Exercise failure in add/emplace.
+
+     do_add: Use emplace (false) or add (true) to add elements.
+     do_finalize: Perform finalization at the end (instead of free).  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      {
+        struct dynarray_int dyn;
+        dynarray_int_init (&dyn);
+        size_t count = 0;
+        while (true)
+          {
+            if (do_add)
+              {
+                dynarray_int_add (&dyn, 0);
+                if (dynarray_int_has_failed (&dyn))
+                  break;
+              }
+            else
+              {
+                int *place = dynarray_int_emplace (&dyn);
+                if (place == NULL)
+                  break;
+                TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+                *place = 0;
+              }
+            ++count;
+          }
+        printf ("info: %s: failure after %zu elements\n", __func__, count);
+        TEST_VERIFY_EXIT (dynarray_int_has_failed (&dyn));
+        if (do_finalize)
+          {
+            struct int_array result = { (int *) (uintptr_t) -1, -1 };
+            TEST_VERIFY_EXIT (!dynarray_int_finalize (&dyn, &result));
+            TEST_VERIFY_EXIT (result.array == (int *) (uintptr_t) -1);
+            TEST_VERIFY_EXIT (result.length == (size_t) -1);
+          }
+        else
+          dynarray_int_free (&dyn);
+        CHECK_INIT_STATE (int, &dyn);
+      }
+
+  /* Exercise failure in finalize.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    {
+      struct dynarray_int dyn;
+      dynarray_int_init (&dyn);
+      for (unsigned int i = 0; i < 10000; ++i)
+        {
+          if (do_add)
+            {
+              dynarray_int_add (&dyn, i);
+              TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+            }
+          else
+            {
+              int *place = dynarray_int_emplace (&dyn);
+              TEST_VERIFY_EXIT (place != NULL);
+              *place = i;
+            }
+        }
+      TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+      struct heap_filler *heap_filler = fill_heap ();
+      struct int_array result = { (int *) (uintptr_t) -1, -1 };
+      TEST_VERIFY_EXIT (!dynarray_int_finalize (&dyn, &result));
+      TEST_VERIFY_EXIT (result.array == (int *) (uintptr_t) -1);
+      TEST_VERIFY_EXIT (result.length == (size_t) -1);
+      CHECK_INIT_STATE (int, &dyn);
+      free_fill_heap (heap_filler);
+    }
+
+  /* Exercise failure in resize.  */
+  {
+    struct dynarray_int dyn;
+    dynarray_int_init (&dyn);
+    struct heap_filler *heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_int_resize (&dyn, 1000));
+    TEST_VERIFY (dynarray_int_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+
+    dynarray_int_init (&dyn);
+    TEST_VERIFY (dynarray_int_resize (&dyn, 1));
+    heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_int_resize (&dyn, 1000));
+    TEST_VERIFY (dynarray_int_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+
+    dynarray_int_init (&dyn);
+    TEST_VERIFY (dynarray_int_resize (&dyn, 1000));
+    heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_int_resize (&dyn, 2000));
+    TEST_VERIFY (dynarray_int_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+  }
+}
+
+/* Check allocation failures for char * arrays (which automatically
+   free the pointed-to strings).  */
+static void
+test_str_fail (void)
+{
+  /* Exercise failure in add/emplace.
+
+     do_add: Use emplace (false) or add (true) to add elements.
+     do_finalize: Perform finalization at the end (instead of free).  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      {
+        struct dynarray_str dyn;
+        dynarray_str_init (&dyn);
+        size_t count = 0;
+        while (true)
+          {
+            char **place;
+            if (do_add)
+              {
+                dynarray_str_add (&dyn, NULL);
+                if (dynarray_str_has_failed (&dyn))
+                  break;
+                else
+                  place = dynarray_str_at (&dyn, dynarray_str_size (&dyn) - 1);
+              }
+            else
+              {
+                place = dynarray_str_emplace (&dyn);
+                if (place == NULL)
+                  break;
+              }
+            TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+            TEST_VERIFY_EXIT (*place == NULL);
+            *place = strdup ("placeholder");
+            if (*place == NULL)
+              {
+                /* Second loop to wait for failure of
+                   dynarray_str_emplace.  */
+                while (true)
+                  {
+                    if (do_add)
+                      {
+                        dynarray_str_add (&dyn, NULL);
+                        if (dynarray_str_has_failed (&dyn))
+                          break;
+                      }
+                    else
+                      {
+                        char **place = dynarray_str_emplace (&dyn);
+                        if (place == NULL)
+                          break;
+                        TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+                        *place = NULL;
+                      }
+                    ++count;
+                  }
+                break;
+              }
+            ++count;
+          }
+        printf ("info: %s: failure after %zu elements\n", __func__, count);
+        TEST_VERIFY_EXIT (dynarray_str_has_failed (&dyn));
+        if (do_finalize)
+          {
+            struct str_array result = { (char **) (uintptr_t) -1, -1 };
+            TEST_VERIFY_EXIT (!dynarray_str_finalize (&dyn, &result));
+            TEST_VERIFY_EXIT (result.array == (char **) (uintptr_t) -1);
+            TEST_VERIFY_EXIT (result.length == (size_t) -1);
+          }
+        else
+          dynarray_str_free (&dyn);
+        TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+        TEST_VERIFY_EXIT (dyn.dynarray_header.array == dyn.scratch);
+        TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == 0);
+        TEST_VERIFY_EXIT (dyn.dynarray_header.allocated > 0);
+      }
+
+  /* Exercise failure in finalize.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    {
+      struct dynarray_str dyn;
+      dynarray_str_init (&dyn);
+      for (unsigned int i = 0; i < 1000; ++i)
+        {
+          if (do_add)
+            dynarray_str_add (&dyn, xstrdup ("placeholder"));
+          else
+            {
+              char **place = dynarray_str_emplace (&dyn);
+              TEST_VERIFY_EXIT (place != NULL);
+              TEST_VERIFY_EXIT (*place == NULL);
+              *place = xstrdup ("placeholder");
+            }
+        }
+      TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+      struct heap_filler *heap_filler = fill_heap ();
+      struct str_array result = { (char **) (uintptr_t) -1, -1 };
+      TEST_VERIFY_EXIT (!dynarray_str_finalize (&dyn, &result));
+      TEST_VERIFY_EXIT (result.array == (char **) (uintptr_t) -1);
+      TEST_VERIFY_EXIT (result.length == (size_t) -1);
+      TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+      TEST_VERIFY_EXIT (dyn.dynarray_header.array == dyn.scratch);
+      TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == 0);
+      TEST_VERIFY_EXIT (dyn.dynarray_header.allocated > 0);
+      free_fill_heap (heap_filler);
+    }
+
+  /* Exercise failure in resize.  */
+  {
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+    struct heap_filler *heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_str_resize (&dyn, 1000));
+    TEST_VERIFY (dynarray_str_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+
+    dynarray_str_init (&dyn);
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1));
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
+    heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_str_resize (&dyn, 1000));
+    TEST_VERIFY (dynarray_str_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+
+    dynarray_str_init (&dyn);
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1000));
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
+    heap_filler = fill_heap ();
+    TEST_VERIFY (!dynarray_str_resize (&dyn, 2000));
+    TEST_VERIFY (dynarray_str_has_failed (&dyn));
+    free_fill_heap (heap_filler);
+  }
+}
+
+/* Test if mmap can allocate a page.  This is necessary because
+   setrlimit does not fail even if it reduces the RLIMIT_AS limit
+   below what is currently needed by the process.  */
+static bool
+mmap_works (void)
+{
+  void *ptr =  mmap (NULL, 1, PROT_READ | PROT_WRITE,
+                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
+  if (ptr == MAP_FAILED)
+    return false;
+  xmunmap (ptr, 1);
+  return true;
+}
+
+/* Set the RLIMIT_AS limit to the value in *LIMIT.  */
+static void
+xsetrlimit_as (const struct rlimit *limit)
+{
+  if (setrlimit (RLIMIT_AS, limit) != 0)
+    FAIL_EXIT1 ("setrlimit (RLIMIT_AS, %lu): %m",
+                (unsigned long) limit->rlim_cur);
+}
+
+/* Approximately this many bytes can be allocated after
+   reduce_rlimit_as has run.  */
+enum { as_limit_reserve = 2 * 1024 * 1024 };
+
+/* Limit the size of the process, so that memory allocation in
+   allocate_thread will eventually fail, without impacting the entire
+   system.  By default, a dynamic limit which leaves room for 2 MiB is
+   activated.  The TEST_RLIMIT_AS environment variable overrides
+   it.  */
+static void
+reduce_rlimit_as (void)
+{
+  struct rlimit limit;
+  if (getrlimit (RLIMIT_AS, &limit) != 0)
+    FAIL_EXIT1 ("getrlimit (RLIMIT_AS) failed: %m");
+
+  /* Use the TEST_RLIMIT_AS setting if available.  */
+  {
+    long target = 0;
+    const char *variable = "TEST_RLIMIT_AS";
+    const char *target_str = getenv (variable);
+    if (target_str != NULL)
+      {
+        target = atoi (target_str);
+        if (target <= 0)
+          FAIL_EXIT1 ("invalid %s value: \"%s\"", variable, target_str);
+        printf ("info: setting RLIMIT_AS to %ld MiB\n", target);
+        target *= 1024 * 1024;      /* Convert to megabytes.  */
+        limit.rlim_cur = target;
+        xsetrlimit_as (&limit);
+        return;
+      }
+  }
+
+  /* Otherwise, try to find the limit with a binary search.  */
+  unsigned long low = 1 << 20;
+  limit.rlim_cur = low;
+  xsetrlimit_as (&limit);
+
+  /* Find working upper limit.  */
+  unsigned long high = 1 << 30;
+  while (true)
+    {
+      limit.rlim_cur = high;
+      xsetrlimit_as (&limit);
+      if (mmap_works ())
+        break;
+      if (2 * high < high)
+        FAIL_EXIT1 ("cannot find upper AS limit");
+      high *= 2;
+    }
+
+  /* Perform binary search.  */
+  while ((high - low) > 128 * 1024)
+    {
+      unsigned long middle = (low + high) / 2;
+      limit.rlim_cur = middle;
+      xsetrlimit_as (&limit);
+      if (mmap_works ())
+        high = middle;
+      else
+        low = middle;
+    }
+
+  unsigned long target = high + as_limit_reserve;
+  limit.rlim_cur = target;
+  xsetrlimit_as (&limit);
+  printf ("info: RLIMIT_AS limit: %lu bytes\n", target);
+}
+
+static int
+do_test (void)
+{
+  mtrace ();
+  reduce_rlimit_as ();
+  test_int_fail ();
+  test_str_fail ();
+  return 0;
+}
+
+#define TIMEOUT 90
+#include <support/test-driver.c>
diff --git a/malloc/tst-dynarray-shared.h b/malloc/tst-dynarray-shared.h
new file mode 100644
index 0000000000..faba66f580
--- /dev/null
+++ b/malloc/tst-dynarray-shared.h
@@ -0,0 +1,77 @@
+/* Shared definitions for dynarray tests.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stddef.h>
+
+struct int_array
+{
+  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>
+
+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>
+
+/* Check that *DYN is equivalent to its initial state.  */
+#define CHECK_INIT_STATE(type, dyn)                             \
+  ({                                                            \
+    TEST_VERIFY_EXIT (!dynarray_##type##_has_failed (dyn));     \
+    TEST_VERIFY_EXIT (dynarray_##type##_size (dyn) == 0);       \
+    TEST_VERIFY_EXIT ((dyn)->dynarray_header.array              \
+                      == (dyn)->scratch);                       \
+    TEST_VERIFY_EXIT ((dyn)->dynarray_header.allocated > 0);    \
+    (void) 0;                                                   \
+  })
+
+/* Check that *DYN behaves as if it is in its initial state.  */
+#define CHECK_EMPTY(type, dyn)                                       \
+  ({                                                                 \
+    CHECK_INIT_STATE (type, (dyn));                                  \
+    dynarray_##type##_free (dyn);                                    \
+    CHECK_INIT_STATE (type, (dyn));                                  \
+    dynarray_##type##_clear (dyn);                                   \
+    CHECK_INIT_STATE (type, (dyn));                                  \
+    dynarray_##type##_remove_last (dyn);                             \
+    CHECK_INIT_STATE (type, (dyn));                                  \
+    dynarray_##type##_mark_failed (dyn);                             \
+    TEST_VERIFY_EXIT (dynarray_##type##_has_failed (dyn));           \
+    dynarray_##type##_clear (dyn);                                   \
+    TEST_VERIFY_EXIT (dynarray_##type##_has_failed (dyn));           \
+    dynarray_##type##_remove_last (dyn);                             \
+    TEST_VERIFY_EXIT (dynarray_##type##_has_failed (dyn));           \
+    TEST_VERIFY_EXIT (dynarray_##type##_emplace (dyn) == NULL);      \
+    dynarray_##type##_free (dyn);                                    \
+    CHECK_INIT_STATE (type, (dyn));                                  \
+    (void) 0;                                                        \
+  })
diff --git a/malloc/tst-dynarray.c b/malloc/tst-dynarray.c
new file mode 100644
index 0000000000..7aee85aa39
--- /dev/null
+++ b/malloc/tst-dynarray.c
@@ -0,0 +1,517 @@
+/* Test for dynamic arrays.
+   Copyright (C) 2017 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
+   <http://www.gnu.org/licenses/>.  */
+
+#include "tst-dynarray-shared.h"
+
+#define DYNARRAY_STRUCT dynarray_long
+#define DYNARRAY_ELEMENT long
+#define DYNARRAY_PREFIX dynarray_long_
+#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 17)
+#include <malloc/dynarray-skeleton.c>
+
+struct long_array
+{
+  long *array;
+  size_t length;
+};
+
+#define DYNARRAY_STRUCT dynarray_long_noscratch
+#define DYNARRAY_ELEMENT long
+#define DYNARRAY_PREFIX dynarray_long_noscratch_
+#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 23)
+#define DYNARRAY_FINAL_TYPE struct long_array
+#define DYNARRAY_INITIAL_SIZE 0
+#include <malloc/dynarray-skeleton.c>
+
+#define DYNARRAY_STRUCT zstr
+#define DYNARRAY_ELEMENT char
+#define DYNARRAY_PREFIX zstr_
+#define DYNARRAY_INITIAL_SIZE 128
+#include <malloc/dynarray-skeleton.c>
+
+#include <malloc.h>
+#include <mcheck.h>
+#include <stdint.h>
+#include <support/check.h>
+#include <support/support.h>
+
+enum { max_count = 20 };
+
+/* Test dynamic arrays with int elements (no automatic deallocation
+   for elements).  */
+static void
+test_int (void)
+{
+  /* Empty array.  */
+  {
+    struct dynarray_int dyn;
+    dynarray_int_init (&dyn);
+    CHECK_EMPTY (int, &dyn);
+  }
+
+  /* Empty array with finalization.  */
+  {
+    struct dynarray_int dyn;
+    dynarray_int_init (&dyn);
+    CHECK_INIT_STATE (int, &dyn);
+    struct int_array result = { (int *) (uintptr_t) -1, -1 };
+    TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
+    CHECK_INIT_STATE (int, &dyn);
+    TEST_VERIFY_EXIT (result.array == NULL);
+    TEST_VERIFY_EXIT (result.length == 0);
+  }
+
+  /* Non-empty array tests.
+
+     do_add: Switch between emplace (false) and add (true).
+     do_finalize: Perform finalize call at the end.
+     do_clear: Perform clear call at the end.
+     do_remove_last: Perform remove_last call after adding elements.
+     count: Number of elements added to the array.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      for (int do_clear = 0; do_clear < 2; ++do_clear)
+        for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
+          for (unsigned int count = 0; count < max_count; ++count)
+            {
+              if (do_remove_last && count == 0)
+                continue;
+              unsigned int base = count * count;
+              struct dynarray_int dyn;
+              dynarray_int_init (&dyn);
+              for (unsigned int i = 0; i < count; ++i)
+                {
+                  if (do_add)
+                    dynarray_int_add (&dyn, base + i);
+                  else
+                    {
+                      int *place = dynarray_int_emplace (&dyn);
+                      TEST_VERIFY_EXIT (place != NULL);
+                      *place = base + i;
+                    }
+                  TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+                  TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == i + 1);
+                  TEST_VERIFY_EXIT (dynarray_int_size (&dyn)
+                                    <= dyn.dynarray_header.allocated);
+                }
+              TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == count);
+              TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
+              unsigned final_count;
+              bool heap_array = dyn.dynarray_header.array != dyn.scratch;
+              if (do_remove_last)
+                {
+                  dynarray_int_remove_last (&dyn);
+                  if (count == 0)
+                    final_count = 0;
+                  else
+                    final_count = count - 1;
+                }
+              else
+                final_count = count;
+              if (do_clear)
+                {
+                  dynarray_int_clear (&dyn);
+                  final_count = 0;
+                }
+              TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+              TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
+                                == heap_array);
+              TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == final_count);
+              TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
+              if (!do_clear)
+                for (unsigned int i = 0; i < final_count; ++i)
+                  TEST_VERIFY_EXIT (*dynarray_int_at (&dyn, i) == base + i);
+              if (do_finalize)
+                {
+                  struct int_array result = { (int *) (uintptr_t) -1, -1 };
+                  TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
+                  CHECK_INIT_STATE (int, &dyn);
+                  TEST_VERIFY_EXIT (result.length == final_count);
+                  if (final_count == 0)
+                    TEST_VERIFY_EXIT (result.array == NULL);
+                  else
+                    {
+                      TEST_VERIFY_EXIT (result.array != NULL);
+                      TEST_VERIFY_EXIT (result.array != (int *) (uintptr_t) -1);
+                      TEST_VERIFY_EXIT
+                        (malloc_usable_size (result.array)
+                         >= final_count * sizeof (result.array[0]));
+                      for (unsigned int i = 0; i < final_count; ++i)
+                        TEST_VERIFY_EXIT (result.array[i] == base + i);
+                      free (result.array);
+                    }
+                }
+              else /* !do_finalize */
+                {
+                  dynarray_int_free (&dyn);
+                  CHECK_INIT_STATE (int, &dyn);
+                }
+            }
+}
+
+/* Test dynamic arrays with char * elements (with automatic
+   deallocation of the pointed-to strings).  */
+static void
+test_str (void)
+{
+  /* Empty array.  */
+  {
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+    CHECK_EMPTY (str, &dyn);
+  }
+
+  /* Empty array with finalization.  */
+  {
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+    TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+    struct str_array result = { (char **) (uintptr_t) -1, -1 };
+    TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
+    CHECK_INIT_STATE (str, &dyn);
+    TEST_VERIFY_EXIT (result.array == NULL);
+    TEST_VERIFY_EXIT (result.length == 0);
+  }
+
+  /* Non-empty array tests.
+
+     do_add: Switch between emplace (false) and add (true).
+     do_finalize: Perform finalize call at the end.
+     do_clear: Perform clear call at the end.
+     do_remove_last: Perform remove_last call after adding elements.
+     count: Number of elements added to the array.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      for (int do_clear = 0; do_clear < 2; ++do_clear)
+        for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
+          for (unsigned int count = 0; count < max_count; ++count)
+            {
+              if (do_remove_last && count == 0)
+                continue;
+              unsigned int base = count * count;
+              struct dynarray_str dyn;
+              dynarray_str_init (&dyn);
+              for (unsigned int i = 0; i < count; ++i)
+                {
+                  char *item = xasprintf ("%d", base + i);
+                  if (do_add)
+                    dynarray_str_add (&dyn, item);
+                  else
+                    {
+                      char **place = dynarray_str_emplace (&dyn);
+                      TEST_VERIFY_EXIT (place != NULL);
+                      TEST_VERIFY_EXIT (*place == NULL);
+                      *place = item;
+                    }
+                  TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+                  TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == i + 1);
+                  TEST_VERIFY_EXIT (dynarray_str_size (&dyn)
+                                    <= dyn.dynarray_header.allocated);
+                }
+              TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == count);
+              TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
+              unsigned final_count;
+              bool heap_array = dyn.dynarray_header.array != dyn.scratch;
+              if (do_remove_last)
+                {
+                  dynarray_str_remove_last (&dyn);
+                  if (count == 0)
+                    final_count = 0;
+                  else
+                    final_count = count - 1;
+                }
+              else
+                final_count = count;
+              if (do_clear)
+                {
+                  dynarray_str_clear (&dyn);
+                  final_count = 0;
+                }
+              TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+              TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
+                                == heap_array);
+              TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == final_count);
+              TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
+              if (!do_clear)
+                for (unsigned int i = 0; i < count - do_remove_last; ++i)
+                  {
+                    char *expected = xasprintf ("%d", base + i);
+                    const char *actual = *dynarray_str_at (&dyn, i);
+                    TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
+                    free (expected);
+                  }
+              if (do_finalize)
+                {
+                  struct str_array result = { (char **) (uintptr_t) -1, -1 };
+                  TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
+                  CHECK_INIT_STATE (str, &dyn);
+                  TEST_VERIFY_EXIT (result.length == final_count);
+                  if (final_count == 0)
+                    TEST_VERIFY_EXIT (result.array == NULL);
+                  else
+                    {
+                      TEST_VERIFY_EXIT (result.array != NULL);
+                      TEST_VERIFY_EXIT (result.array
+                                        != (char **) (uintptr_t) -1);
+                      TEST_VERIFY_EXIT (result.length
+                                        == count - do_remove_last);
+                      TEST_VERIFY_EXIT
+                        (malloc_usable_size (result.array)
+                         >= final_count * sizeof (result.array[0]));
+                      for (unsigned int i = 0; i < count - do_remove_last; ++i)
+                        {
+                          char *expected = xasprintf ("%d", base + i);
+                          char *actual = result.array[i];
+                          TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
+                          free (expected);
+                          free (actual);
+                        }
+                      free (result.array);
+                    }
+                }
+              else /* !do_finalize */
+                {
+                  dynarray_str_free (&dyn);
+                  CHECK_INIT_STATE (str, &dyn);
+                }
+            }
+
+  /* Test resizing.  */
+  {
+    enum { count = 2131 };
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+
+    /* From length 0 to length 1.  */
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
+    dynarray_str_free (&dyn);
+
+    /* From length 0 to length 1 and 2.  */
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated0");
+    TEST_VERIFY (dynarray_str_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 2);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 1) == NULL);
+    *dynarray_str_at (&dyn, 1) = xstrdup ("allocated1");
+    TEST_VERIFY (dynarray_str_resize (&dyn, count));
+    TEST_VERIFY (dynarray_str_size (&dyn) == count);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
+    for (int i = 2; i < count; ++i)
+      TEST_VERIFY (*dynarray_str_at (&dyn, i) == NULL);
+    *dynarray_str_at (&dyn, count - 1) = xstrdup ("allocated2");
+    TEST_VERIFY (dynarray_str_resize (&dyn, 3));
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 2) == NULL);
+    dynarray_str_free (&dyn);
+  }
+}
+
+/* Verify that DYNARRAY_ELEMENT_INIT has an effect.  */
+static void
+test_long_init (void)
+{
+  enum { count = 2131 };
+  {
+    struct dynarray_long dyn;
+    dynarray_long_init (&dyn);
+    for (int i = 0; i < count; ++i)
+      {
+        long *place = dynarray_long_emplace (&dyn);
+        TEST_VERIFY_EXIT (place != NULL);
+        TEST_VERIFY (*place == 17);
+      }
+    TEST_VERIFY (dynarray_long_size (&dyn) == count);
+    for (int i = 0; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
+    dynarray_long_free (&dyn);
+
+    TEST_VERIFY (dynarray_long_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    *dynarray_long_at (&dyn, 0) = 18;
+    dynarray_long_free (&dyn);
+    TEST_VERIFY (dynarray_long_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    TEST_VERIFY (dynarray_long_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 2);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 1) == 17);
+    *dynarray_long_at (&dyn, 0) = 18;
+    TEST_VERIFY (dynarray_long_resize (&dyn, count));
+    TEST_VERIFY (dynarray_long_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 18);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
+    dynarray_long_free (&dyn);
+  }
+
+  /* Similar, but without an on-stack scratch region
+     (DYNARRAY_INITIAL_SIZE is 0).  */
+  {
+    struct dynarray_long_noscratch dyn;
+    dynarray_long_noscratch_init (&dyn);
+    struct long_array result;
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY (result.array == NULL);
+    TEST_VERIFY (result.length == 0);
+
+    /* Test with one element.  */
+    {
+      long *place = dynarray_long_noscratch_emplace (&dyn);
+      TEST_VERIFY_EXIT (place != NULL);
+      TEST_VERIFY (*place == 23);
+    }
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY_EXIT (result.array != NULL);
+    TEST_VERIFY (result.length == 1);
+    TEST_VERIFY (result.array[0] == 23);
+    free (result.array);
+
+    for (int i = 0; i < count; ++i)
+      {
+        long *place = dynarray_long_noscratch_emplace (&dyn);
+        TEST_VERIFY_EXIT (place != NULL);
+        TEST_VERIFY (*place == 23);
+        if (i == 0)
+          *place = 29;
+      }
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 29);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY_EXIT (result.array != NULL);
+    TEST_VERIFY (result.length == count);
+    TEST_VERIFY (result.array[0] == 29);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (result.array[i] == 23);
+    free (result.array);
+
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    *dynarray_long_noscratch_at (&dyn, 0) = 24;
+    dynarray_long_noscratch_free (&dyn);
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 2);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 1) == 23);
+    *dynarray_long_noscratch_at (&dyn, 0) = 24;
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, count));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 24);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
+    dynarray_long_noscratch_free (&dyn);
+  }
+}
+
+/* Test NUL-terminated string construction with the add function and
+   the simple finalize function.  */
+static void
+test_zstr (void)
+{
+  /* Totally empty string (no NUL termination).  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY (result == NULL);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY (result == NULL);
+    TEST_VERIFY (length == 0);
+    TEST_VERIFY (zstr_size (&s) == 0);
+  }
+
+  /* Empty string.  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    zstr_add (&s, '\0');
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (*result == '\0');
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+
+    zstr_add (&s, '\0');
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (*result == '\0');
+    TEST_VERIFY (length == 1);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+  }
+
+  /* A few characters.  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    zstr_add (&s, 'A');
+    zstr_add (&s, 'b');
+    zstr_add (&s, 'c');
+    zstr_add (&s, '\0');
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (strcmp (result, "Abc") == 0);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+
+    zstr_add (&s, 'X');
+    zstr_add (&s, 'y');
+    zstr_add (&s, 'z');
+    zstr_add (&s, '\0');
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (strcmp (result, "Xyz") == 0);
+    TEST_VERIFY (length == 4);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+  }
+}
+
+static int
+do_test (void)
+{
+  mtrace ();
+  test_int ();
+  test_str ();
+  test_long_init ();
+  test_zstr ();
+  return 0;
+}
+
+#include <support/test-driver.c>