This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Dynamic growable arrays for internal use
- From: Carlos O'Donell <carlos at redhat dot com>
- To: Florian Weimer <fweimer at redhat dot com>
- Cc: GNU C Library <libc-alpha at sourceware dot org>
- Date: Fri, 2 Jun 2017 03:37:09 -0400
- Subject: Re: [PATCH] Dynamic growable arrays for internal use
- Authentication-results: sourceware.org; auth=none
- References: <edae68d6-998b-58a6-a8df-82703341da23@redhat.com> <ce479249-6362-6a58-ec9b-d6227ef99db9@redhat.com> <eb0d4e4f-1294-5b32-e9e8-004edebca698@redhat.com>
On 05/30/2017 08:48 AM, Florian Weimer wrote:
> On 05/20/2017 04:01 AM, Carlos O'Donell wrote:
Thanks for the followup explanations.
This looks really good and I'd say we're done.
This is acceptable to me as an internal API which we can use.
In summary the remaining points look like this:
* Add rationale to malloc/dynarray.h as a comment explaining when and
why you would use it instead of a scratch buffer. What you write below
with some adjustments is good.
* A couple of comment typos.
OK with those changes.
>> Why would someone choose to use dynarray instead of a scratch buffer?
> Scratch buffers hard-coded to 1000-something bytes of on-stack storage.
> This can be a problem if you need several (usually small) arrays. The
> on-stack allocation is configurable for dynamic arrays.
Right, it's sufficient to say that scratch-buffers using a hard-coded and
optimized on-stack storage and that this is the problem.
> Scratch buffers are geared towards untyped byte sequences, not arrays of
> a single type.
OK.
> Scratch buffers are generally not expected to preserve their contents
> when resized.
I don't like being vague about this. Could we say something more concrete
like:
Scratch buffers do not preserve their contents when resized. The only
exception is the use of XXX which is expected to be removed and replaced
by dynarray.
> Some existing scratch buffer users probably should switch to dynarray
> once we have that functionality. scratch_buffer_set_array_size is a bit
> of a hack because I didn't want to create the full array functionality
> at that time. I expect that this function can eventually go away (and
> so should scratch_buffer_grow_preserve), so that scratch buffers are
> strictly for NSS-style buffers. At that point, we can use a more
> aggressive resizing policy (because retries are so expensive).
Perfect.
Please add these notes to malloc/dynarray.h as part of the comment header to
explain to all developers the reasons for choosing a dynarray over scratch
buffer. I think this is important rationale to anyone deciding which internal
API to use. We've never had this quality of internal objects to use in glibc
and keeping this kind of rationale present is important.
>> Can dynarray guarantee it is only heap allocated to make it easier to use
>> in certain stack-limited cases? While scratch-buffers are designed to be stack
>> allocated with heap fallback?
> By default, at least two array elements are stack-allocated, and up to
> 128 bytes of stack space are used. This can be configured through
> DYNARRAY_INITIAL_SIZE.
OK, that makes sense.
You also clarified later taht DYNARRAY_INITIAL_SIZE set to 0 makes them fully
heap allocated. Which is *perfect*, and I like that property.
>> The tests while thorough need much more comments explaining the purpose of each
>> test and the iterations being done by the tests. For example for each sequence
>> of nested for loops we need an outer comment to describe exactly what is being
>> tested and why that is important.
> I added more comments in the attached patch.
OK.
>> The initial dynarray size makes the API feel like a variant of scratch buffer.
>> Why have an initial inline size that can be allocated on the stack? I'd like to
>> avoid stack allocations for dynarray's and make them completely heap-based.
>> Does that make sense from a design perspective? It would make them an easy
>> choice when you want to avoid stack based allocations.
> Most arrays are small. A small stack-allocated array will allow us to
> create the final array with the correct size for such small arrays. We
> already need three words for the dynarray header. I could reduce the
> default stack allocation size to something in the same ballpark (say
> five words) if on-stack size is a concern.
No, what we have is OK. I appreciate the clarification. I also think that the
documentation of DYNARRAY_INITIAL_SIZE(0) as being fully heap allocated is good.
>> The dynamic array growth factor appears to be a value of 2, and that doesn't
>> match best practice nor academic literature. I would be happier with a growth
>> factor closer to 1.5.
> I used Paul's suggestion of (1.5 * N + 1).
>
> I could not find any relevant discussion of growth factors.
"Optimal memory reallocation and the golden ratio"
https://crntaylor.wordpress.com/2011/07/15/optimal-memory-reallocation-and-the-golden-ratio/
There are a lot of assumptions there, including the fact that memory
is allocated consecutively, and that you might reuse previous blocks
in a future allocation whose size is equal to the sum of previous blocks.
In reality malloc might approximate such reuse through coalescing and so
future malloc's reuse the previous two allocations (now freed) after
coalescing and so result in better malloc usage (less fragmentation).
>> Review of low level details:
>>
>> tst-dynarray-fail - Takes on average 40s on an "average" machine.
>> The timeout needs to be bumped up to 50s. I see ~93% of the
>> time in _dl_addr because the free hook uses that to
>> lookup information and that's very expensive.
> I set a timeout of 90 seconds. For me, it completes much, much faster
> for some reason.
OK.
>> malloc/dynarray_at_failure.c - Must use __snprintf to avoid PLT. Has slight
>> formatting issue.
> Fixed.
OK.
>>> +#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
>> Not OK.
>>
>> I dont like defaults for this interface. I think the user should
>> explicitly request a size or this should fail. It avoids macro API typos
>> which intend to define DYNARRAY_INITIAL_SIZE but don't, and then a default
>> applies.
>>
>> Why have a default at all though?
> Convenience. This has to be a preprocessor constant, so that we can
> make the presence of the scratch array inside the dynarray struct
> conditional on the initial size value.
>
> I do think we need some defaults here because without them, new features
> we add will eventually need patching all over the place. This would be
> very hostile to backporting in particular.
I can agree with this.
OK.
>> Can we make the choice to have dynarray always heap allocated?
> #define DYNARRAY_INITIAL_SIZE 0
>
> does that. I clarified that in the file comment.
Perfect.
>> It would make this simpler, you just never have an initial scratch.
>>
>> If you need scratch space use growable scratch buffers?
> See above why scratch buffers can be a poor fit.
Your clarification is good and I can agree with this.
>>> +/* Remove the last element of LIST if it is present. */
>>> +__attribute__ ((unused))
>>> +static void
>>> +DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
>>> +{
>>> + /* We deliberately skip error checking here. */
>> Why do you deliberatly skip error checking?
> I updated the comment.
OK.
>>> +/* Remove all elements from the list. The elements are freed, but the
>>> + list itself is not. */
>>> +__attribute__ ((unused))
>>> +static void
>>> +DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
>>> +{
>>> + /* We deliberately skip error checking here. */
>> Why?
> Likewise.
OK.
>>> +#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))
>>> +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 };
>> Can we do a named structure member assignment here just for clarity and safety?
> This would force specific names for this user-supplied structure. I did
> not want to do that.
Good point.
>>> + A minimal example which provides a growing list of integers can be
>>> + defined like this:
>>> +
>>> + struct int_array
>>> + {
>>> + int *array;
>>> + size_t length;
>>> + };
>> Please enhance this example to explain tha the layout of the final
>> type has to have ceratain members in a particular order.
> I added a comment.
OK.
>>> + /* Double the allocated size. */
>>> + {
>>> + new_allocated = 2 * list->allocated;
>> Not OK. Please review academic literature on growth factor values.
> See above.
OK.
>>> + 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) { heap_array, used };
>> Can we use named structure member assignment?
> Fixed.
OK.
>>> +static void
>>> +check_stream (const char *what, const struct xmemstream *stream,
>>> + const char *expected)
>>> +{
>>> + if (strcmp (stream->buffer, expected) != 0)
>>> + {
>>> + support_record_failure ();
>>> + printf ("error: captured %s data incorrect\n"
>>> + " expected: %s\n"
>>> + " actual: %s\n",
>>> + what, expected, stream->buffer);
>>> + }
>>> + if (stream->length != strlen (expected))
>>> + {
>>> + support_record_failure ();
>>> + printf ("error: captured %s data length incorrect\n"
>>> + " expected: %zu\n"
>>> + " actual: %zu\n",
>>> + what, strlen (expected), stream->length);
>>> + }
>>> +}
>>> +
>>> +static int
>>> +do_test (void)
>>> +{
>>> + const int lengths[] = {0, 1, 17, 512, 20000, -1};
>>> +
>>> + for (int i = 0; lengths[i] >= 0; ++i)
>>> + for (int j = 0; lengths[j] >= 0; ++j)
>>> + for (int write_mode = 0; write_mode < write_mode_last; ++write_mode)
>>> + for (int signal = 0; signal < 2; ++signal)
>>> + for (int status = 0; status < 2; ++status)
>> This needs detailed comments.
> Fixed.
OK.
> The attached patch adds a new add function for arrays, which is
> convenient to construct arrays with simple elements (such as
> NUL-terminated strings). For arrays which have sentinels when completed
> (such as NUL-terminated strings and argv lists), the existing finalize
> interface with the type definition is overkill, so I added a default
> implementation which directly returns the heap-allocated pointer.
>
> In addition, I added a few nonnull attributes and told the compiler to
> inline the fast path for emplace (and the new add function).
OK.
> Thanks,
> Florian
>
>
> dynarray.patch
>
>
> 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.
>
> 2017-05-30 Florian Weimer <fweimer@redhat.com>
>
> * malloc/Makefile (routines): Add dynarray_at_failure,
> dynarray_emplace_enlarge, dynarray_finalize.
> (tests-internal): Add tst-dynarray, tst-dynarray-fail,
> tst-dynarray-at-fail.
> (tests-srcs): Add tst-dynarray, tst-dynarray-fail.
> (tests-special): Add tst-dynarray-mem.out,
> tst-dynarray-mem-fail.out.
> (tst-dynarray-ENV, tst-dynarray-fail-ENV): Set.
> (tst-dynarray-mem.out, tst-dynarray-fail-mem.out): Generate using
> mtrace.
> * malloc/Versions (__libc_dynarray_at_failure)
> (__libc_dynarray_emplace_enlarge, __libc_dynarray_finalize)
> (__libc_dynarray_resize, __libc_dynarray_resize_clear): Export as
> GLIBC_PRIVATE.
> * malloc/dynarray.h: New file.
> * malloc/dynarray-skeleton.c: Likewise.
> * malloc/dynarray_at_failure.c: Likewise.
> * malloc/dynarray_emplace_enlarge.c: Likewise.
> * malloc/dynarray_finalize.c: Likewise.
> * malloc/dynarray_resize.c: Likewise.
> * malloc/dynarray_resize_clear.c: Likewise.
> * malloc/tst-dynarray.c: Likewise.
> * malloc/tst-dynarray-fail.c: Likewise.
> * malloc/tst-dynarray-at-fail.c: Likewise.
> * malloc/tst-dynarray-shared.h: Likewise.
> * support/Makefile (libsupport-routines): Add
> support_capture_subprocess, xdup2, xpipe.
> (tests): Add tst-support_capture_subprocess.
> * support/capture_subprocess.h: New file.
> * support/support_capture_subprocess.c: Likewise.
> * support/tst-support_capture_subprocess.c: Likewise.
> * support/xdup2.c: Likewise.
> * support/xpipe.c: Likewise.
> * support/xunistd.h (xdup2, xpipe): Declare.
>
> diff --git a/malloc/Makefile b/malloc/Makefile
> index d0f23f7..21ba755 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 \
> +
OK.
> 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
OK.
>
> routines = malloc morecore mcheck mtrace obstack \
> 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 \
OK.
>
> 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
OK.
> 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)
OK.
> diff --git a/malloc/Versions b/malloc/Versions
> index e34ab17..baf5b19 100644
> --- a/malloc/Versions
> +++ b/malloc/Versions
> @@ -74,5 +74,12 @@ libc {
> __libc_scratch_buffer_grow;
> __libc_scratch_buffer_grow_preserve;
> __libc_scratch_buffer_set_array_size;
> +
> + # dynarray support
> + __libc_dynarray_at_failure;
> + __libc_dynarray_emplace_enlarge;
> + __libc_dynarray_finalize;
> + __libc_dynarray_resize;
> + __libc_dynarray_resize_clear;
OK.
> }
> }
> diff --git a/malloc/dynarray-skeleton.c b/malloc/dynarray-skeleton.c
> new file mode 100644
> index 0000000..7a10e08
> --- /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.
OK.
> + 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
OK.
> +# endif
> +#else
> +/* Provide a reasonable default which limits the size of
> + DYNARRAY_STRUCT. */
OK.
> +# 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);
OK.
> +}
> +
> +/* 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);
> +}
OK.
> +
> +/* 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. */
OK. This is the new variant emplacement, which is fine.
> +__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 0000000..7fab4cb
> --- /dev/null
> +++ b/malloc/dynarray.h
> @@ -0,0 +1,179 @@
> +/* 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>
> + */
> +
> +#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 ();
> +}
> +
> +/* Set *RESULT to LEFT * RIGHT. Return true if the result
> + overflowed. */
> +static inline bool
> +__check_mul_overflow_size_t (size_t left, size_t right, size_t *result)
> +{
> +#if __GNUC__ >= 5
> + return __builtin_mul_overflow (left, right, result);
> +#else
> + /* size_t is unsigned so the behavior on overflow is defined. */
> + *result = left * right;
> + size_t half_size_t = ((size_t) 1) << (8 * sizeof (size_t) / 2);
> + if (__glibc_unlikely ((left | right) >= half_size_t))
> + {
> + if (__glibc_unlikely (right != 0 && *result / right != left))
> + return true;
> + }
> + return false;
> +#endif
> +}
> +
> +/* 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 0000000..fcc06f0
> --- /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 0000000..c8e7782
> --- /dev/null
> +++ b/malloc/dynarray_emplace_enlarge.c
> @@ -0,0 +1,68 @@
> +/* 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 <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;
OK.
> + 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 0000000..6dd8705
> --- /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 0000000..f7ecf80
> --- /dev/null
> +++ b/malloc/dynarray_resize.c
> @@ -0,0 +1,58 @@
> +/* 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 <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 0000000..0c4ced1
> --- /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 0000000..bc1a48c
> --- /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 0000000..508dbae
> --- /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
OK.
> +#include <support/test-driver.c>
> diff --git a/malloc/tst-dynarray-shared.h b/malloc/tst-dynarray-shared.h
> new file mode 100644
> index 0000000..faba66f
> --- /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 0000000..073cf29
> --- /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. */
OK. Thanks, that helps make the test clearer.
> + 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>
> diff --git a/support/Makefile b/support/Makefile
> index 38dbd83..3ce73a6 100644
> --- a/support/Makefile
> +++ b/support/Makefile
> @@ -36,6 +36,7 @@ libsupport-routines = \
> resolv_test \
> set_fortify_handler \
> support_become_root \
> + support_capture_subprocess \
> support_enter_network_namespace \
> support_format_address_family \
> support_format_addrinfo \
> @@ -56,6 +57,7 @@ libsupport-routines = \
> xcalloc \
> xclose \
> xconnect \
> + xdup2 \
> xfclose \
> xfopen \
> xfork \
> @@ -65,6 +67,7 @@ libsupport-routines = \
> xmemstream \
> xmmap \
> xmunmap \
> + xpipe \
> xpoll \
> xpthread_attr_destroy \
> xpthread_attr_init \
> @@ -113,6 +116,7 @@ endif
> tests = \
> README-testing \
> tst-support-namespace \
> + tst-support_capture_subprocess \
> tst-support_format_dns_packet \
> tst-support_record_failure \
>
> diff --git a/support/capture_subprocess.h b/support/capture_subprocess.h
> new file mode 100644
> index 0000000..3265d63
> --- /dev/null
> +++ b/support/capture_subprocess.h
> @@ -0,0 +1,42 @@
> +/* Capture output from a subprocess.
> + 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 SUPPORT_CAPTURE_SUBPROCESS_H
> +#define SUPPORT_CAPTURE_SUBPROCESS_H
> +
> +#include <support/xmemstream.h>
> +
> +struct support_capture_subprocess
> +{
> + struct xmemstream out;
> + struct xmemstream err;
> + int status;
> +};
> +
> +/* Invoke CALLBACK (CLOSURE) in a subprocess and capture standard
> + output, standard error, and the exit status. The out.buffer and
> + err.buffer members in the result are null-terminated strings which
> + can be examined by te caller. (out.out and err.out are NULL.) */
s/te/the/g.
Suggest:
can be examined by the caller (out.out and err.out are NULL).
> +struct support_capture_subprocess support_capture_subprocess
> + (void (*callback) (void *), void *closure);
> +
> +/* Deallocate the subprocess data captured by
> + support_capture_subprocess. */
> +void support_capture_subprocess_free (struct support_capture_subprocess *);
> +
> +#endif /* SUPPORT_CAPTURE_SUBPROCESS_H */
> diff --git a/support/support_capture_subprocess.c b/support/support_capture_subprocess.c
> new file mode 100644
> index 0000000..030f124
> --- /dev/null
> +++ b/support/support_capture_subprocess.c
> @@ -0,0 +1,108 @@
> +/* Capture output from a subprocess.
> + 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 <support/capture_subprocess.h>
> +
> +#include <errno.h>
> +#include <stdlib.h>
> +#include <support/check.h>
> +#include <support/xunistd.h>
> +#include <support/xsocket.h>
> +
> +static void
> +transfer (const char *what, struct pollfd *pfd, struct xmemstream *stream)
> +{
> + if (pfd->revents != 0)
> + {
> + char buf[1024];
> + ssize_t ret = TEMP_FAILURE_RETRY (read (pfd->fd, buf, sizeof (buf)));
> + if (ret < 0)
> + {
> + support_record_failure ();
> + printf ("error: reading from subprocess %s: %m", what);
> + pfd->events = 0;
> + pfd->revents = 0;
> + }
> + else if (ret == 0)
> + {
> + /* EOF reached. Stop listening. */
> + pfd->events = 0;
> + pfd->revents = 0;
> + }
> + else
> + /* Store the data just read. */
> + TEST_VERIFY (fwrite (buf, ret, 1, stream->out) == 1);
> + }
> +}
> +
> +struct support_capture_subprocess
> +support_capture_subprocess (void (*callback) (void *), void *closure)
> +{
> + struct support_capture_subprocess result;
> + xopen_memstream (&result.out);
> + xopen_memstream (&result.err);
> +
> + int stdout_pipe[2];
> + xpipe (stdout_pipe);
> + int stderr_pipe[2];
> + xpipe (stderr_pipe);
> +
> + TEST_VERIFY (fflush (stdout) == 0);
> + TEST_VERIFY (fflush (stderr) == 0);
> +
> + pid_t pid = xfork ();
> + if (pid == 0)
> + {
> + xclose (stdout_pipe[0]);
> + xclose (stderr_pipe[0]);
> + xdup2 (stdout_pipe[1], STDOUT_FILENO);
> + xdup2 (stderr_pipe[1], STDERR_FILENO);
> + callback (closure);
> + _exit (0);
> + }
> + xclose (stdout_pipe[1]);
> + xclose (stderr_pipe[1]);
> +
> + struct pollfd fds[2] =
> + {
> + { .fd = stdout_pipe[0], .events = POLLIN },
> + { .fd = stderr_pipe[0], .events = POLLIN },
> + };
> +
> + do
> + {
> + xpoll (fds, 2, -1);
> + transfer ("stdout", &fds[0], &result.out);
> + transfer ("stderr", &fds[1], &result.err);
> + }
> + while (fds[0].events != 0 || fds[1].events != 0);
> + xclose (stdout_pipe[0]);
> + xclose (stderr_pipe[0]);
> +
> + xfclose_memstream (&result.out);
> + xfclose_memstream (&result.err);
> + xwaitpid (pid, &result.status, 0);
> + return result;
> +}
> +
> +void
> +support_capture_subprocess_free (struct support_capture_subprocess *p)
> +{
> + free (p->out.buffer);
> + free (p->err.buffer);
> +}
OK.
> diff --git a/support/tst-support_capture_subprocess.c b/support/tst-support_capture_subprocess.c
> new file mode 100644
> index 0000000..5672fba
> --- /dev/null
> +++ b/support/tst-support_capture_subprocess.c
> @@ -0,0 +1,188 @@
> +/* Test capturing output from a subprocess.
> + 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 <stdbool.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include <support/capture_subprocess.h>
> +#include <support/check.h>
> +#include <support/support.h>
> +#include <sys/wait.h>
> +#include <unistd.h>
> +
> +/* Write one byte at *P to FD and advance *P. Do nothing if *P is
> + '\0'. */
> +static void
> +transfer (const unsigned char **p, int fd)
> +{
> + if (**p != '\0')
> + {
> + TEST_VERIFY (write (fd, *p, 1) == 1);
> + ++*p;
> + }
> +}
> +
> +/* Determine the order in which stdout and stderr are written. */
> +enum write_mode { out_first, err_first, interleave,
> + write_mode_last = interleave };
> +
> +/* Describe what to write in the subprocess. */
> +struct test
> +{
> + char *out;
> + char *err;
> + enum write_mode write_mode;
> + int signal;
> + int status;
> +};
> +
> +/* For use with support_capture_subprocess. */
> +static void
> +callback (void *closure)
> +{
> + const struct test *test = closure;
> + bool mode_ok = false;
> + switch (test->write_mode)
> + {
> + case out_first:
> + TEST_VERIFY (fputs (test->out, stdout) >= 0);
> + TEST_VERIFY (fflush (stdout) == 0);
> + TEST_VERIFY (fputs (test->err, stderr) >= 0);
> + TEST_VERIFY (fflush (stderr) == 0);
> + mode_ok = true;
> + break;
> + case err_first:
> + TEST_VERIFY (fputs (test->err, stderr) >= 0);
> + TEST_VERIFY (fflush (stderr) == 0);
> + TEST_VERIFY (fputs (test->out, stdout) >= 0);
> + TEST_VERIFY (fflush (stdout) == 0);
> + mode_ok = true;
> + break;
> + case interleave:
> + {
> + const unsigned char *pout = (const unsigned char *) test->out;
> + const unsigned char *perr = (const unsigned char *) test->err;
> + do
> + {
> + transfer (&pout, STDOUT_FILENO);
> + transfer (&perr, STDERR_FILENO);
> + }
> + while (*pout != '\0' || *perr != '\0');
> + }
> + mode_ok = true;
> + break;
> + }
> + TEST_VERIFY (mode_ok);
> +
> + if (test->signal != 0)
> + raise (test->signal);
> + exit (test->status);
> +}
> +
> +/* Create a heap-allocated random string of letters. */
> +static char *
> +random_string (size_t length)
> +{
> + char *result = xmalloc (length + 1);
> + for (size_t i = 0; i < length; ++i)
> + result[i] = 'a' + (rand () % 26);
> + result[length] = '\0';
> + return result;
> +}
> +
> +/* Check that the specific stream from the captured subprocess matches
> + expectations. */
> +static void
> +check_stream (const char *what, const struct xmemstream *stream,
> + const char *expected)
> +{
> + if (strcmp (stream->buffer, expected) != 0)
> + {
> + support_record_failure ();
> + printf ("error: captured %s data incorrect\n"
> + " expected: %s\n"
> + " actual: %s\n",
> + what, expected, stream->buffer);
> + }
> + if (stream->length != strlen (expected))
> + {
> + support_record_failure ();
> + printf ("error: captured %s data length incorrect\n"
> + " expected: %zu\n"
> + " actual: %zu\n",
> + what, strlen (expected), stream->length);
> + }
> +}
> +
> +static int
> +do_test (void)
> +{
> + const int lengths[] = {0, 1, 17, 512, 20000, -1};
> +
> + /* Test multiple combinations of support_capture_subprocess.
> +
> + length_idx_stdout: Index into the lengths array above,
> + controls how many bytes are written by the subprocess to
> + standard output.
> + length_idx_stderr: Same for standard error.
> + write_mode: How standard output and standard error writes are
> + ordered.
> + signal: Exit with no signal if zero, with SIGTERM if one.
> + status: Process exit status: 0 if zero, 3 if one. */
> + for (int length_idx_stdout = 0; lengths[length_idx_stdout] >= 0;
> + ++length_idx_stdout)
> + for (int length_idx_stderr = 0; lengths[length_idx_stderr] >= 0;
> + ++length_idx_stderr)
> + for (int write_mode = 0; write_mode < write_mode_last; ++write_mode)
> + for (int signal = 0; signal < 2; ++signal)
> + for (int status = 0; status < 2; ++status)
> + {
> + struct test test =
> + {
> + .out = random_string (lengths[length_idx_stdout]),
> + .err = random_string (lengths[length_idx_stderr]),
> + .write_mode = write_mode,
> + .signal = signal * SIGTERM, /* 0 or SIGTERM. */
> + .status = status * 3, /* 0 or 3. */
> + };
> + TEST_VERIFY (strlen (test.out) == lengths[length_idx_stdout]);
> + TEST_VERIFY (strlen (test.err) == lengths[length_idx_stderr]);
> +
> + struct support_capture_subprocess result
> + = support_capture_subprocess (callback, &test);
> + check_stream ("stdout", &result.out, test.out);
> + check_stream ("stderr", &result.err, test.err);
> + if (test.signal != 0)
> + {
> + TEST_VERIFY (WIFSIGNALED (result.status));
> + TEST_VERIFY (WTERMSIG (result.status) == test.signal);
> + }
> + else
> + {
> + TEST_VERIFY (WIFEXITED (result.status));
> + TEST_VERIFY (WEXITSTATUS (result.status) == test.status);
> + }
> + support_capture_subprocess_free (&result);
> + free (test.out);
> + free (test.err);
> + }
> + return 0;
> +}
> +
> +#include <support/test-driver.c>
> diff --git a/support/xdup2.c b/support/xdup2.c
> new file mode 100644
> index 0000000..f4a3759
> --- /dev/null
> +++ b/support/xdup2.c
> @@ -0,0 +1,28 @@
> +/* pipe with error checking.
s/pipe/dup2/g
> + 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 <support/xunistd.h>
> +
> +#include <support/check.h>
> +
> +void
> +xdup2 (int from, int to)
> +{
> + if (dup2 (from, to) < 0)
> + FAIL_EXIT1 ("dup2 (%d, %d): %m", from, to);
> +}
> diff --git a/support/xpipe.c b/support/xpipe.c
> new file mode 100644
> index 0000000..89a64a5
> --- /dev/null
> +++ b/support/xpipe.c
> @@ -0,0 +1,28 @@
> +/* pipe with error checking.
> + 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 <support/xunistd.h>
> +
> +#include <support/check.h>
> +
> +void
> +xpipe (int fds[2])
> +{
> + if (pipe (fds) < 0)
> + FAIL_EXIT1 ("pipe: %m");
> +}
> diff --git a/support/xunistd.h b/support/xunistd.h
> index 258bab5..7c14bda 100644
> --- a/support/xunistd.h
> +++ b/support/xunistd.h
> @@ -29,6 +29,8 @@ __BEGIN_DECLS
>
> pid_t xfork (void);
> pid_t xwaitpid (pid_t, int *status, int flags);
> +void xpipe (int[2]);
> +void xdup2 (int, int);
>
> /* Close the file descriptor. Ignore EINTR errors, but terminate the
> process on other errors. */
--
Cheers,
Carlos.