@@ -46,6 +46,7 @@ tests-internal += \
tst-dynarray \
tst-dynarray-fail \
tst-dynarray-at-fail \
+ tst-char_array
ifneq (no,$(have-tunables))
tests += tst-malloc-usable-tunables
@@ -58,7 +59,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 \
@@ -82,6 +82,7 @@ libc {
# dynarray support
__libc_dynarray_at_failure;
+ __libc_dynarray_overflow_failure;
__libc_dynarray_emplace_enlarge;
__libc_dynarray_finalize;
__libc_dynarray_resize;
new file mode 100644
@@ -0,0 +1,281 @@
+/* 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 provided 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 = "testi";
+ char_array_erase (&str, 5);
+ // str = "123testi";
+ char_array_prepend_str (&str, "123");
+ // len = 8;
+ size_t len = char_array_length (&str);
+ // str = "123testi456";
+ char_array_append_str (&str, "456");
+ // str = "123testi789";
+ 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>
+
+/* Return a const char for the internal C string handled by 'array'. */
+__attribute__ ((nonnull (1)))
+static const char *
+char_array_str (struct char_array *array)
+{
+ return char_array_at (array, 0);
+}
+
+/* Return the character at position 'pos' from the char_array 'array'. */
+__attribute__ ((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 the contents of string 'str' to char_array 'array', including the
+ final '\0'. */
+__attribute__ ((nonnull (1, 2)))
+static bool
+char_array_set_str (struct char_array *array, const char *str)
+{
+ size_t size = strlen (str) + 1;
+ if (!char_array_resize (array, size))
+ return false;
+ memcpy (array->dynarray_header.array, str, size);
+ array->dynarray_header.used = size;
+ return true;
+}
+
+/* Copy up 'size' bytes from string 'str' to char_array 'array'. A final
+ '\0' is appended in the char_array. */
+__attribute__ ((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_wrapv_size_t (size, 1, &newsize))
+ __libc_dynarray_overflow_failure (size, 1);
+
+ if (!char_array_resize (array, newsize))
+ return false;
+
+ *((char *) mempcpy (array->dynarray_header.array, str, size)) = '\0';
+ array->dynarray_header.used = newsize;
+ return true;
+}
+
+/* Initialize the char_array 'array' and sets it to an empty string (""). */
+__attribute__ ((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__ ((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__ ((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__ ((nonnull (1)))
+static bool
+char_array_is_empty (struct char_array *array)
+{
+ return *char_array_at (array, 0) == '\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__ ((nonnull (1)))
+static bool
+char_array_erase (struct char_array *array, size_t pos)
+{
+ if (pos >= array->dynarray_header.used - 1)
+ return false;
+
+ char *ppos = char_array_at (array, pos);
+ char *lpos = array->dynarray_header.array + array->dynarray_header.used;
+ ptrdiff_t size = lpos - ppos;
+ memmove (ppos, ppos + 1, size);
+ array->dynarray_header.used--;
+ return true;
+}
+
+/* Resize the char_array 'array' to size 'count' maintaining the ending
+ '\0' byte. */
+__attribute__ ((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__ ((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_wrapv_size_t (used, size, &newsize))
+ __libc_dynarray_overflow_failure (used, size);
+
+ if (!char_array_resize (array, newsize))
+ return false;
+
+ /* Make room for the string and copy it. */
+ memmove (array->dynarray_header.array + size, array->dynarray_header.array,
+ used);
+ memcpy (array->dynarray_header.array, str, size);
+ array->dynarray_header.used = newsize;
+ return true;
+}
+
+/* Append the contents of string 'str' to char_array 'array, including the
+ final '\0' byte. */
+__attribute__ ((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_wrapv_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';
+ array->dynarray_header.used = newsize;
+ return true;
+}
+
+/* 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__ ((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)
+ return false;
+
+ size_t newsize;
+ if (check_add_wrapv_size_t (pos, len, &newsize))
+ __libc_dynarray_overflow_failure (pos, len);
+ if (check_add_wrapv_size_t (newsize, 1, &newsize))
+ __libc_dynarray_overflow_failure (newsize, 1);
+
+ if (!char_array_resize (array, newsize))
+ return false;
+
+ char *start = char_array_at (array, pos);
+ *(char *) mempcpy (start, str, len) = '\0';
+ array->dynarray_header.used = newsize;
+ return true;
+}
@@ -173,4 +173,12 @@ void __libc_dynarray_at_failure (size_t size, size_t index)
__attribute__ ((noreturn));
libc_hidden_proto (__libc_dynarray_at_failure)
+/* 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));
+libc_hidden_proto (__libc_dynarray_overflow_failure)
+
#endif /* _DYNARRAY_H */
new file mode 100644
@@ -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)
@@ -101,4 +101,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_wrapv_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 */
new file mode 100644
@@ -0,0 +1,110 @@
+/* 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.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);
+ char_array_free (&str);
+ }
+
+ return 0;
+}
+
+#include <support/test-driver.c>