Patchwork [1/8] malloc: Add specialized dynarray for C strings

login
register
mail settings
Submitter Adhemerval Zanella Netto
Date Nov. 21, 2017, 1:55 p.m.
Message ID <1511272530-10936-2-git-send-email-adhemerval.zanella@linaro.org>
Download mbox | patch
Permalink /patch/24402/
State New
Headers show

Comments

Adhemerval Zanella Netto - Nov. 21, 2017, 1:55 p.m.
This patch adds an specialized dynarray to manage C strings using the
dynarray internal implementation.  It uses some private fields from
dynarray and thus it provided specific files to access and manage
the internal string buffer.

   For instance:

   struct char_array str;

   // str == "testing"
   char_array_init_str (&str, "testing");

   // c == 's'
   char c = char_array_pos (&str, 2);

   // str = "testing2"
   char_array_set_str (&str, "testing2");

   // str = "testig2"
   char_array_erase (&str, 5);

   // str = "123testig2";
   char_array_prepend_str (&str, "123");

   // len = 10;
   size_t len = char_array_length (&str);

   // str = "123testig2456";
   char_array_append_str (&str, "456");

   // str = "123test789";
   char_array_replace_str_pos (&str, 7, "789", 3);

The provided function are not extensive and meant mainly to be use in
subsequent glob implementation cleanup.  For internal object consistency
only the function provided by char_array.c should be used, including
internal object manipulation.

To check for possible overflows in internal size manipulation a new
function, check_add_wrapv_size_t, is added on malloc-internal.  It basically
return whether the addition of two size_t overflows.

Checked on x86_64-linux-gnu.

	* malloc/Makefile (test-internal): Add tst-char_array.
	(routines): Add dynarray_overflow_failure and char_array-impl.
	* malloc/Versions [GLIBC_PRIVATE] (libc): Add
	__libc_dynarray_overflow_failure, __char_array_set_str_size,
	__char_array_erase, __char_array_prepend_str_size, and
	__char_array_replace_str_pos.
	* malloc/char_array-impl.c: New file.
	* malloc/char_array-skeleton.c: Likewise.
	* malloc/char_array.h: Likewise.
	* malloc/tst-char-array.c: Likewise.
	* malloc/dynarray_overflow_failure.c: Likewise.
	* malloc/malloc-internal.h (check_add_overflow_size_t): New function.

Signed-off-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
---
 ChangeLog                          |  15 ++
 malloc/Makefile                    |   4 +-
 malloc/Versions                    |   7 +
 malloc/char_array-impl.c           |  57 ++++++++
 malloc/char_array-skeleton.c       | 279 +++++++++++++++++++++++++++++++++++++
 malloc/char_array.h                |  53 +++++++
 malloc/dynarray.h                  |   9 ++
 malloc/dynarray_overflow_failure.c |  31 +++++
 malloc/malloc-internal.h           |  14 ++
 malloc/tst-char_array.c            | 112 +++++++++++++++
 10 files changed, 580 insertions(+), 1 deletion(-)
 create mode 100644 malloc/char_array-impl.c
 create mode 100644 malloc/char_array-skeleton.c
 create mode 100644 malloc/char_array.h
 create mode 100644 malloc/dynarray_overflow_failure.c
 create mode 100644 malloc/tst-char_array.c
Andreas Schwab - Nov. 21, 2017, 2:15 p.m.
On Nov 21 2017, Adhemerval Zanella <adhemerval.zanella@linaro.org> wrote:

> diff --git a/malloc/dynarray.h b/malloc/dynarray.h
> index 5888bcb..bb52b0f 100644
> --- a/malloc/dynarray.h
> +++ b/malloc/dynarray.h
> @@ -168,12 +168,21 @@ bool __libc_dynarray_finalize (struct dynarray_header *list, void *scratch,
>  void __libc_dynarray_at_failure (size_t size, size_t index)
>    __attribute__ ((noreturn));
>  
> +/* Internal function.  TErminate the process after an overflow in

Terminate

> diff --git a/malloc/malloc-internal.h b/malloc/malloc-internal.h
> index a9c9c6a..3957ebb 100644
> --- a/malloc/malloc-internal.h
> +++ b/malloc/malloc-internal.h
> @@ -91,4 +91,18 @@ check_mul_overflow_size_t (size_t left, size_t right, size_t *result)
>  #endif
>  }
>  
> +/* Set *R = A + B.  Return true if the answer is mathematically incorrect due
> +   to overflow; in this case, *R is the low order bits of the correct
> +   answer.  */
> +static inline bool
> +check_add_overflow_size_t (size_t a, size_t b, size_t *r)
> +{
> +#if 5 <= __GNUC__

__GNUC__ >= 5

Andreas.
Andreas Schwab - Nov. 21, 2017, 2:19 p.m.
On Nov 21 2017, Adhemerval Zanella <adhemerval.zanella@linaro.org> wrote:

>    // c == 's'
>    char c = char_array_pos (&str, 2);

I'd call it char_array_at.

Andreas.
Adhemerval Zanella Netto - Nov. 21, 2017, 4:20 p.m.
On 21/11/2017 12:15, Andreas Schwab wrote:
> On Nov 21 2017, Adhemerval Zanella <adhemerval.zanella@linaro.org> wrote:
> 
>> diff --git a/malloc/dynarray.h b/malloc/dynarray.h
>> index 5888bcb..bb52b0f 100644
>> --- a/malloc/dynarray.h
>> +++ b/malloc/dynarray.h
>> @@ -168,12 +168,21 @@ bool __libc_dynarray_finalize (struct dynarray_header *list, void *scratch,
>>  void __libc_dynarray_at_failure (size_t size, size_t index)
>>    __attribute__ ((noreturn));
>>  
>> +/* Internal function.  TErminate the process after an overflow in
> 
> Terminate
> 
>> diff --git a/malloc/malloc-internal.h b/malloc/malloc-internal.h
>> index a9c9c6a..3957ebb 100644
>> --- a/malloc/malloc-internal.h
>> +++ b/malloc/malloc-internal.h
>> @@ -91,4 +91,18 @@ check_mul_overflow_size_t (size_t left, size_t right, size_t *result)
>>  #endif
>>  }
>>  
>> +/* Set *R = A + B.  Return true if the answer is mathematically incorrect due
>> +   to overflow; in this case, *R is the low order bits of the correct
>> +   answer.  */
>> +static inline bool
>> +check_add_overflow_size_t (size_t a, size_t b, size_t *r)
>> +{
>> +#if 5 <= __GNUC__
> 
> __GNUC__ >= 5
> 
> Andreas.
> 

I fixed both locally, thanks.
Adhemerval Zanella Netto - Nov. 21, 2017, 4:32 p.m.
On 21/11/2017 12:19, Andreas Schwab wrote:
> On Nov 21 2017, Adhemerval Zanella <adhemerval.zanella@linaro.org> wrote:
> 
>>    // c == 's'
>>    char c = char_array_pos (&str, 2);
> 
> I'd call it char_array_at.
> 
> Andreas.
> 

Since char_array is based directly on dynarray the name is already implemented
by it.  In fact we do have a char_array_at, but it returns a 'char *' to the
position.

Patch

diff --git a/malloc/Makefile b/malloc/Makefile
index 17936fc..8435e7f 100644
--- a/malloc/Makefile
+++ b/malloc/Makefile
@@ -49,6 +49,7 @@  tests-internal += \
 	 tst-dynarray \
 	 tst-dynarray-fail \
 	 tst-dynarray-at-fail \
+	 tst-char_array
 
 ifneq (no,$(have-tunables))
 tests += tst-malloc-usable-tunables
@@ -61,7 +62,7 @@  test-srcs = tst-mtrace
 routines = malloc morecore mcheck mtrace obstack reallocarray \
   scratch_buffer_grow scratch_buffer_grow_preserve \
   scratch_buffer_set_array_size \
-  dynarray_at_failure \
+  dynarray_at_failure dynarray_overflow_failure \
   dynarray_emplace_enlarge \
   dynarray_finalize \
   dynarray_resize \
@@ -71,6 +72,7 @@  routines = malloc morecore mcheck mtrace obstack reallocarray \
   alloc_buffer_copy_bytes  \
   alloc_buffer_copy_string \
   alloc_buffer_create_failure \
+  char_array-impl
 
 install-lib := libmcheck.a
 non-lib.a := libmcheck.a
diff --git a/malloc/Versions b/malloc/Versions
index 2357cff..b21fe59 100644
--- a/malloc/Versions
+++ b/malloc/Versions
@@ -81,6 +81,7 @@  libc {
 
     # dynarray support
     __libc_dynarray_at_failure;
+    __libc_dynarray_overflow_failure;
     __libc_dynarray_emplace_enlarge;
     __libc_dynarray_finalize;
     __libc_dynarray_resize;
@@ -92,5 +93,11 @@  libc {
     __libc_alloc_buffer_copy_bytes;
     __libc_alloc_buffer_copy_string;
     __libc_alloc_buffer_create_failure;
+
+    # char_array support
+    __char_array_set_str_size;
+    __char_array_erase;
+    __char_array_prepend_str_size;
+    __char_array_replace_str_pos;
   }
 }
diff --git a/malloc/char_array-impl.c b/malloc/char_array-impl.c
new file mode 100644
index 0000000..5a56bbc
--- /dev/null
+++ b/malloc/char_array-impl.c
@@ -0,0 +1,57 @@ 
+/* Specialized dynarray for C strings.  Implementation file.
+   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 <malloc/char_array.h>
+
+void
+__char_array_set_str_size (struct dynarray_header *header, const char *str,
+			   size_t size)
+{
+  *((char *) mempcpy (header->array, str, size)) = '\0';
+  header->used = size + 1;
+}
+libc_hidden_def (__char_array_set_str_size)
+
+void
+__char_array_erase (struct dynarray_header *header, size_t pos)
+{
+  char *ppos = header->array + pos;
+  char *lpos = header->array + header->used;
+  ptrdiff_t size = lpos - ppos;
+  memmove (ppos, ppos + 1, size);
+  header->used--;
+}
+libc_hidden_def (__char_array_erase)
+
+void
+__char_array_prepend_str_size (struct dynarray_header *header,
+			       const char *str, size_t size, size_t used)
+{
+  memmove (header->array + size, header->array, used);
+  memcpy (header->array, str, size);
+}
+libc_hidden_def (__char_array_prepend_str_size)
+
+void
+__char_array_replace_str_pos (struct dynarray_header *header, size_t pos,
+			      const char *str, size_t len)
+{
+  char *start = header->array + pos;
+  *(char *) mempcpy (start, str, len) = '\0';
+}
+libc_hidden_def (__char_array_replace_str_pos)
diff --git a/malloc/char_array-skeleton.c b/malloc/char_array-skeleton.c
new file mode 100644
index 0000000..00d3a30
--- /dev/null
+++ b/malloc/char_array-skeleton.c
@@ -0,0 +1,279 @@ 
+/* Specialized dynarray for C strings.
+   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 file provides a dynamic C string with an initial stack allocated
+   buffer.  Since it is based on dynarray, it provides dynamic size
+   expansion and heap usage for large strings.
+
+   The following parameters are optional:
+
+   CHAR_ARRAY_INITIAL_SIZE
+      The size of the statically allocated array (default is 256).  It will
+      be used to define DYNARRAY_INITIAL_SIZE.
+
+   The following functions are provided:
+
+   bool char_array_init_empty (struct char_array *);
+   bool char_array_init_str (struct char_array *, const char *);
+   bool char_array_init_str_size (struct char_array *, const char *, size_t);
+   bool char_array_is_empty (struct char_array *);
+   const char *char_array_str (struct char_array *);
+   char char_array_pos (struct char_array *, size_t);
+   size_t char_array_length (struct char_array *);
+   bool char_array_set_str (struct char_array *, const char *);
+   bool char_array_set_str_size (struct char_array *, const char *, size_t);
+   void char_array_erase (struct char_array *, size_t);
+   bool char_array_crop (struct char_array *, size_t);
+   bool char_array_prepend_str (struct char_array *, const char *);
+   bool char_array_append_str (struct char_array *, const char *);
+   bool char_array_replace_str_pos (struct char_array *, size_t, const char *,
+				    size_t);
+
+   For instance:
+
+   struct char_array str;
+
+   // str == "testing"
+   char_array_init_str (&str, "testing");
+
+   // c == 's'
+   char c = char_array_pos (&str, 2);
+
+   // str = "testing2"
+   char_array_set_str (&str, "testing2");
+
+   // str = "testig2"
+   char_array_erase (&str, 5);
+
+   // str = "123testig2";
+   char_array_prepend_str (&str, "123");
+
+   // len = 10;
+   size_t len = char_array_length (&str);
+
+   // str = "123testig2456";
+   char_array_append_str (&str, "456");
+
+   // str = "123test789";
+   char_array_replace_str_pos (&str, 7, "789", 3);
+ */
+
+#define DYNARRAY_STRUCT            char_array
+#define DYNARRAY_ELEMENT           char
+#define DYNARRAY_PREFIX            char_array_
+#ifndef CHAR_ARRAY_INITIAL_SIZE
+# define CHAR_ARRAY_INITIAL_SIZE 256
+#endif
+#define DYNARRAY_INITIAL_SIZE  CHAR_ARRAY_INITIAL_SIZE
+#include <malloc/dynarray-skeleton.c>
+
+#include <malloc/malloc-internal.h>
+#include <malloc/char_array.h>
+
+/* Return a const char for the internal C string handled by 'array'.  */
+__attribute__ ((unused, nonnull (1)))
+static const char *
+char_array_str (struct char_array *array)
+{
+  return char_array_begin (array);
+}
+
+/* Return the character at position 'pos' from the char_array 'array'.  */
+__attribute__ ((unused, nonnull (1)))
+static char
+char_array_pos (struct char_array *array, size_t pos)
+{
+  return *char_array_at (array, pos);
+}
+
+/* Calculate the length of the string, excluding the terminating null.  */
+__attribute__ ((unused, nonnull (1)))
+static size_t
+char_array_length (struct char_array *array)
+{
+  /* Exclude the final '\0'.  */
+  return array->dynarray_header.used - 1;
+}
+
+/* Copy up 'size' bytes from string 'str' to char_array 'array'.  A final
+   '\0' is appended in the char_array.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_set_str_size (struct char_array *array, const char *str,
+			 size_t size)
+{
+  size_t newsize;
+  if (check_add_overflow_size_t (size, 1, &newsize))
+    __libc_dynarray_overflow_failure (size, 1);
+
+  if (!char_array_resize (array, newsize))
+    return false;
+
+  __char_array_set_str_size (&array->dynarray_abstract, str, size);
+  return true;
+}
+
+/* Copy the contents of string 'str' to char_array 'array', including the
+   final '\0'.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_set_str (struct char_array *array, const char *str)
+{
+  return char_array_set_str_size (array, str, strlen (str));
+}
+
+/* Initialize the char_array 'array' and sets it to an empty string ("").  */
+__attribute__ ((unused, nonnull (1)))
+static bool
+char_array_init_empty (struct char_array *array)
+{
+  char_array_init (array);
+  return char_array_set_str (array, "");
+}
+
+/* Initialize the char_array 'array' and copy the content of string 'str'.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_init_str (struct char_array *array, const char *str)
+{
+  char_array_init (array);
+  return char_array_set_str (array, str);
+}
+
+/* Initialize the char_array 'array' and copy the content of string 'str'
+   up to 'size' characteres.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_init_str_size (struct char_array *array, const char *str,
+			  size_t size)
+{
+  char_array_init (array);
+  return char_array_set_str_size (array, str, size);
+}
+
+/* Return if the char_array contain any characteres.  */
+__attribute__ ((unused, nonnull (1)))
+static bool
+char_array_is_empty (struct char_array *array)
+{
+  return *char_array_begin (array) == '\0';
+}
+
+/* Remove the byte at position 'pos' from char_array 'array'.  The contents
+   are moved internally if the position is not at the end of the internal
+   buffer.  */
+__attribute__ ((unused, nonnull (1)))
+static bool
+char_array_erase (struct char_array *array, size_t pos)
+{
+  if (pos >= array->dynarray_header.used - 1)
+    return false;
+
+  __char_array_erase (&array->dynarray_abstract, pos);
+  return true;
+}
+
+/* Resize the char_array 'array' to size 'count' maintaining the ending
+   '\0' byte.  */
+__attribute__ ((unused, nonnull (1)))
+static bool
+char_array_crop (struct char_array *array, size_t size)
+{
+  if (size >= (array->dynarray_header.used - 1)
+      || !char_array_resize (array, size + 1))
+    return false;
+
+  array->dynarray_header.array[size] = '\0';
+  return true;
+}
+
+/* Prepend the contents of string 'str' to char_array 'array', including the
+   final '\0' byte.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_prepend_str (struct char_array *array, const char *str)
+{
+  size_t size = strlen (str);
+  /* Resizing the array might change its used elements and we need below
+     to correct copy the elements.  */
+  size_t used = array->dynarray_header.used;
+
+  size_t newsize;
+  if (check_add_overflow_size_t (used, size, &newsize))
+    __libc_dynarray_overflow_failure (used, size);
+
+  /* Make room for the string and copy it.  */
+  if (!char_array_resize (array, newsize))
+    return false;
+  __char_array_prepend_str_size (&array->dynarray_abstract, str, size, used);
+  return true;
+}
+
+/* Append the contents of string 'str' to char_array 'array, including the
+   final '\0' byte.  */
+__attribute__ ((unused, nonnull (1, 2)))
+static bool
+char_array_append_str (struct char_array *array, const char *str)
+{
+  size_t size = strlen (str);
+  /* Resizing the array might change its used elements and it used it below
+     to correct copy the elements.  */
+  size_t used = array->dynarray_header.used - 1;
+
+  /* 'used' does account for final '\0', so there is no need to add
+     an extra element to calculate the final required size.  */
+  size_t newsize;
+  if (check_add_overflow_size_t (used + 1, size, &newsize))
+    __libc_dynarray_overflow_failure (used + 1, size);
+
+  if (!char_array_resize (array, newsize))
+    return false;
+
+  /* Start to append at '\0' up to string length and add a final '\0'.  */
+  *(char*) mempcpy (array->dynarray_header.array + used, str, size) = '\0';
+  return true;
+}
+
+/* Append the character 'c' on char_array 'array'.  */
+__attribute__ ((unused, nonnull (1)))
+static bool
+char_array_append_char (struct char_array *array, char c)
+{
+  return char_array_append_str (array, (const char[]) { c, '\0' });
+}
+
+/* Replace the contents starting of position 'pos' of char_array 'array'
+   with the contents of string 'str' up to 'len' bytes.  A final '\0'
+   is appended in the string.  */
+__attribute__ ((unused, nonnull (1, 3)))
+static bool
+char_array_replace_str_pos (struct char_array *array, size_t pos,
+                            const char *str, size_t len)
+{
+  if (pos > array->dynarray_header.used)
+    __libc_dynarray_at_failure (array->dynarray_header.used, pos);
+
+  size_t newsize;
+  if (check_add_overflow_size_t (pos, len, &newsize)
+      || check_add_overflow_size_t (newsize, 1, &newsize)
+      || !char_array_resize (array, newsize))
+    return false;
+
+  __char_array_replace_str_pos (&array->dynarray_abstract, pos, str, len);
+  return true;
+}
diff --git a/malloc/char_array.h b/malloc/char_array.h
new file mode 100644
index 0000000..c696673
--- /dev/null
+++ b/malloc/char_array.h
@@ -0,0 +1,53 @@ 
+/* Specialized dynarray for C strings.  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/>.  */
+
+#ifndef _CHAR_ARRAY_H
+#define _CHAR_ARRAY_H
+
+#include <malloc/dynarray.h>
+
+/* Internal funciton.  Set the dynarray to the content of the string STR up
+   to SIZE bytes.  The dynarray must be resized previously.  */
+void __char_array_set_str_size (struct dynarray_header *, const char *str,
+				size_t size);
+
+/* Internal function.  Remove the character at position POS from dynarray.
+   The position must be a valid one.  */
+void __char_array_erase (struct dynarray_header *, size_t pos);
+
+/* Internal function.  Prepend the content of string STR up to SIZE bytes to
+   dynarray by moving USED bytes forward.  The dynarray must be resized
+   previously.  */
+void __char_array_prepend_str_size (struct dynarray_header *,
+				    const char *str, size_t size,
+				    size_t used);
+
+/* Internal function.  Replace the content of dynarray starting at position
+   POS with the content of string STR up to LEN bytes.  The dynarray must
+   be resize previously and STR must contain at least LEN bytes.  */
+void __char_array_replace_str_pos (struct dynarray_header *, size_t pos,
+				   const char *str, size_t len);
+
+#ifndef _ISOMAC
+libc_hidden_proto (__char_array_set_str_size)
+libc_hidden_proto (__char_array_erase)
+libc_hidden_proto (__char_array_prepend_str_size)
+libc_hidden_proto (__char_array_replace_str_pos)
+#endif
+
+#endif
diff --git a/malloc/dynarray.h b/malloc/dynarray.h
index 5888bcb..bb52b0f 100644
--- a/malloc/dynarray.h
+++ b/malloc/dynarray.h
@@ -168,12 +168,21 @@  bool __libc_dynarray_finalize (struct dynarray_header *list, void *scratch,
 void __libc_dynarray_at_failure (size_t size, size_t index)
   __attribute__ ((noreturn));
 
+/* Internal function.  TErminate the process after an overflow in
+   new size allocation.  SIZE is the current number of elements in
+   dynamic array and INCR is the new elements to add on current
+   size.  */
+void __libc_dynarray_overflow_failure (size_t size, size_t incr)
+  __attribute__ ((noreturn));
+
 #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)
+libc_hidden_proto (__libc_dynarray_overflow_failure)
+
 #endif
 
 #endif /* _DYNARRAY_H */
diff --git a/malloc/dynarray_overflow_failure.c b/malloc/dynarray_overflow_failure.c
new file mode 100644
index 0000000..14936b0
--- /dev/null
+++ b/malloc/dynarray_overflow_failure.c
@@ -0,0 +1,31 @@ 
+/* Report an dynamic array size overflow 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_overflow_failure (size_t size, size_t incr)
+{
+  char buf[200];
+  __snprintf (buf, sizeof (buf), "Fatal glibc error: "
+              "new size overflows (old %zu and increment %zu)\n",
+              size, incr);
+ __libc_fatal (buf);
+}
+libc_hidden_def (__libc_dynarray_overflow_failure)
diff --git a/malloc/malloc-internal.h b/malloc/malloc-internal.h
index a9c9c6a..3957ebb 100644
--- a/malloc/malloc-internal.h
+++ b/malloc/malloc-internal.h
@@ -91,4 +91,18 @@  check_mul_overflow_size_t (size_t left, size_t right, size_t *result)
 #endif
 }
 
+/* Set *R = A + B.  Return true if the answer is mathematically incorrect due
+   to overflow; in this case, *R is the low order bits of the correct
+   answer.  */
+static inline bool
+check_add_overflow_size_t (size_t a, size_t b, size_t *r)
+{
+#if 5 <= __GNUC__
+  return __builtin_add_overflow (a, b, r);
+#else
+  *r = a + b;
+  return *r < a;
+#endif
+}
+
 #endif /* _MALLOC_INTERNAL_H */
diff --git a/malloc/tst-char_array.c b/malloc/tst-char_array.c
new file mode 100644
index 0000000..a3a99fb
--- /dev/null
+++ b/malloc/tst-char_array.c
@@ -0,0 +1,112 @@ 
+/* Test for char_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 <string.h>
+
+#include <malloc/char_array-skeleton.c>
+
+#include <malloc.h>
+#include <mcheck.h>
+#include <stdint.h>
+#include <support/check.h>
+#include <support/support.h>
+
+static int
+do_test (void)
+{
+  mtrace ();
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_empty (&str) == true);
+    TEST_VERIFY_EXIT (char_array_length (&str) == 0);
+    TEST_VERIFY_EXIT (char_array_is_empty (&str) == true);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "") == 0);
+    char_array_free (&str);
+  }
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_str (&str, "testing"));
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("testing"));
+    TEST_VERIFY_EXIT (char_array_pos (&str, 2) == 's');
+    TEST_VERIFY_EXIT (char_array_is_empty (&str) == false);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "testing") == 0);
+    char_array_free (&str);
+  }
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_str_size (&str, "testing", 4));
+    TEST_VERIFY_EXIT (char_array_length (&str) == 4);
+    TEST_VERIFY_EXIT (char_array_pos (&str, 2) == 's');
+    TEST_VERIFY_EXIT (char_array_is_empty (&str) == false);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "test") == 0);
+    char_array_free (&str);
+  }
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_str (&str, "testing"));
+    TEST_VERIFY_EXIT (char_array_set_str (&str, "abcdef"));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "abcdef") == 0);
+    TEST_VERIFY_EXIT (char_array_set_str_size (&str, "abcdef", 4));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "abcd") == 0);
+    char_array_free (&str);
+  }
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_str (&str, "testing"));
+    TEST_VERIFY_EXIT (char_array_erase (&str, 4) == true);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("testing") - 1);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "testng") == 0);
+    TEST_VERIFY_EXIT (char_array_erase (&str, char_array_length (&str))
+		      == false);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("testing") - 1);
+    TEST_VERIFY_EXIT (char_array_erase (&str, char_array_length (&str) - 1)
+		      == true);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("testing") - 2);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "testn") == 0);
+    char_array_free (&str);
+  }
+
+  {
+    struct char_array str;
+    TEST_VERIFY_EXIT (char_array_init_str (&str, "test"));
+    TEST_VERIFY_EXIT (char_array_prepend_str (&str, "123"));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "123test") == 0);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("123test"));
+    TEST_VERIFY_EXIT (char_array_append_str (&str, "456"));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "123test456") == 0);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("123test456"));
+    TEST_VERIFY_EXIT (char_array_replace_str_pos (&str, 7, "789", 3));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "123test789") == 0);
+    TEST_VERIFY_EXIT (char_array_length (&str) == strlen ("123test789"));
+    TEST_VERIFY_EXIT (char_array_crop (&str, 7));
+    TEST_VERIFY_EXIT (char_array_length (&str) == 7);
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "123test") == 0);
+    TEST_VERIFY_EXIT (char_array_append_char (&str, '4'));
+    TEST_VERIFY_EXIT (strcmp (char_array_str (&str), "123test4") == 0);
+    char_array_free (&str);
+  }
+
+  return 0;
+}
+
+#include <support/test-driver.c>