From patchwork Sat Apr 22 15:46:33 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 753783 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3w9H6D2CLKz9s4s for ; Sun, 23 Apr 2017 01:47:00 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="ZbVXi/FH"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:to:from:subject:message-id:date:mime-version :content-type; q=dns; s=default; b=EYIqr9rMgyarFGkP4I/kS+qacgrxB oP4z8PJ4uN3ChahXA14Aa/aDJFXyWhMSucFLxtPXdWlhlmSg3WY7bY7fEt0XYwak MgOBPnDJXK31wP6xVcx1RJfdhaOdbHddwc6JQ1DFjWydUhdp4jHlH0l91o21oJ/m OqQ2yTPeURl900= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:to:from:subject:message-id:date:mime-version :content-type; s=default; bh=Gt8tAFdkQibFrndxDrPt5uoRqwE=; b=ZbV Xi/FHb475Rz3bwlTHo4XP+kddPzQUCyY4e0KpillUliCOVbkX7QD60jCLtFjTJD2 3YI2IC5t3VREq45PVBoF4kDixemJTUM9VmtPQiFxDAufUVlNzqmjuzP5ME9P9qMF A2SREGI6Uw7uTzcyUb0X3/FWShqt/Xs2gjx6qc/U= Received: (qmail 68025 invoked by alias); 22 Apr 2017 15:46:46 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 66939 invoked by uid 89); 22 Apr 2017 15:46:45 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=shrunk, owns X-HELO: mx1.redhat.com DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 31BF5711D2 Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=fweimer@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 31BF5711D2 To: GNU C Library From: Florian Weimer Subject: [PATCH] Dynamic growable arrays for internal use Message-ID: Date: Sat, 22 Apr 2017 17:46:33 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.0 MIME-Version: 1.0 The dynamic arrays implemented by the attached patch are intended as a simplified, type-safe replacement for obstacks, and can be used to replace custom array management with an on-stack initial buffer and an exponential resizing policy using realloc. Test coverage should be reasonable complete, including allocation error testing. For the __libc_fatal testing, I had to add some support machinery. The __check_mul_overflow_size_t function should go into the header once it exists (probably without the two leading underscore). Thanks, Florian 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-04-22 Florian Weimer * malloc/Makefile (routines): Add dynarray_emplace_enlarge, dynarray_finalize. (tests): 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. diff --git a/malloc/Makefile b/malloc/Makefile index e93b83b..0371d68 100644 --- a/malloc/Makefile +++ b/malloc/Makefile @@ -33,6 +33,9 @@ tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \ tst-mallocfork2 \ tst-interpose-nothread \ tst-interpose-thread \ + tst-dynarray \ + tst-dynarray-fail \ + tst-dynarray-at-fail \ tests-static := \ tst-interpose-static-nothread \ @@ -45,11 +48,16 @@ tests-static += tst-malloc-usable-static-tunables endif tests += $(tests-static) -test-srcs = tst-mtrace +test-srcs = tst-mtrace tst-dynarray tst-dynarray-fail routines = malloc morecore mcheck mtrace obstack \ scratch_buffer_grow scratch_buffer_grow_preserve \ - scratch_buffer_set_array_size + scratch_buffer_set_array_size \ + dynarray_at_failure \ + dynarray_emplace_enlarge \ + dynarray_finalize \ + dynarray_resize \ + dynarray_resize_clear \ install-lib := libmcheck.a non-lib.a := libmcheck.a @@ -135,6 +143,8 @@ ifeq ($(run-built-tests),yes) ifeq (yes,$(build-shared)) ifneq ($(PERL),no) tests-special += $(objpfx)tst-mtrace.out +tests-special += $(objpfx)tst-dynarray-mem.out +tests-special += $(objpfx)tst-dynarray-fail-mem.out endif endif endif @@ -206,3 +216,13 @@ $(objpfx)tst-interpose-thread: \ $(objpfx)tst-interpose-static-nothread: $(objpfx)tst-interpose-aux-nothread.o $(objpfx)tst-interpose-static-thread: \ $(objpfx)tst-interpose-aux-thread.o $(static-thread-library) + +tst-dynarray-ENV = MALLOC_TRACE=$(objpfx)tst-dynarray.mtrace +$(objpfx)tst-dynarray-mem.out: $(objpfx)tst-dynarray.out + $(common-objpfx)malloc/mtrace $(objpfx)tst-dynarray.mtrace > $@; \ + $(evaluate-test) + +tst-dynarray-fail-ENV = MALLOC_TRACE=$(objpfx)tst-dynarray-fail.mtrace +$(objpfx)tst-dynarray-fail-mem.out: $(objpfx)tst-dynarray-fail.out + $(common-objpfx)malloc/mtrace $(objpfx)tst-dynarray-fail.mtrace > $@; \ + $(evaluate-test) diff --git a/malloc/Versions b/malloc/Versions index 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; } } diff --git a/malloc/dynarray-skeleton.c b/malloc/dynarray-skeleton.c new file mode 100644 index 0000000..cdb4b97 --- /dev/null +++ b/malloc/dynarray-skeleton.c @@ -0,0 +1,394 @@ +/* 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 + . */ + +/* 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: 10) + 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); + 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) +*/ + +#include + +#include +#include +#include + +#ifndef DYNARRAY_STRUCT +# error "DYNARRAY_STRUCT must be defined" +#endif + +#ifndef DYNARRAY_ELEMENT +# error "DYNARRAY_ELEMENT must be defined" +#endif + +#ifndef DYNARRAY_PREFIX +# error "DYNARRAY_PREFIX must be defined" +#endif + +#ifdef DYNARRAY_INITIAL_SIZE +# if DYNARRAY_INITIAL_SIZE < 0 +# error "DYNARRAY_INITIAL_SIZE must be non-negative" +# endif +# if DYNARRAY_INITIAL_SIZE > 0 +# define DYNARRAY_HAVE_SCRATCH 1 +# else +# define DYNARRAY_HAVE_SCRATCH 0 +# endif +#else +/* Provide a reasonable default which limits the size of + DYNARRAY_STRUCT. */ +# define DYNARRAY_INITIAL_SIZE \ + (sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT)) +# define DYNARRAY_HAVE_SCRATCH 1 +#endif + +/* Public type definitions. */ + +/* All fields of this struct are private to the implementation. */ +struct DYNARRAY_STRUCT +{ + union + { + struct dynarray_header dynarray_abstract; + struct + { + /* These fields must match struct dynarray_header. */ + size_t used; + size_t allocated; + DYNARRAY_ELEMENT *array; + } dynarray_header; + }; + +#if DYNARRAY_HAVE_SCRATCH + /* Initial inline allocation. */ + DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE]; +#endif +}; + +/* Internal use only: Helper macros. */ + +/* Ensure macro-expansion of DYNARRAY_PREFIX. */ +#define DYNARRAY_CONCAT0(prefix, name) prefix##name +#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name) +#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name) + +/* Address of the scratch buffer if any. */ +#if DYNARRAY_HAVE_SCRATCH +# define DYNARRAY_SCRATCH(list) (list)->scratch +#else +# define DYNARRAY_SCRATCH(list) NULL +#endif + +/* Internal use only: Helper functions. */ + +/* Internal function. Call DYNARRAY_ELEMENT_FREE with the array + elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE + macro expansion. */ +static inline void +DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array, + size_t __dynarray_used) +{ +#ifdef DYNARRAY_ELEMENT_FREE + for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i) + DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]); +#endif /* DYNARRAY_ELEMENT_FREE */ +} + +/* Internal function. Free the non-scratch array allocation. */ +static inline void +DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list) +{ +#if DYNARRAY_HAVE_SCRATCH + if (list->dynarray_header.array != list->scratch) + free (list->dynarray_header.array); +#else + free (list->dynarray_header.array); +#endif +} + +/* Public functions. */ + +/* Initialize a dynamic array object. This must be called before any + use of the object. */ +static void +DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list) +{ + list->dynarray_header.used = 0; + list->dynarray_header.allocated = DYNARRAY_INITIAL_SIZE; + list->dynarray_header.array = DYNARRAY_SCRATCH (list); +} + +/* Deallocate the dynamic array and its elements. */ +__attribute__ ((unused)) +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. */ +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. */ +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. */ +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. */ +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; +} + +/* 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)) +static 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 (list->dynarray_header.used == list->dynarray_header.allocated) + { + if (!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract, + DYNARRAY_SCRATCH (list), + sizeof (DYNARRAY_ELEMENT))) + { + DYNARRAY_NAME (mark_failed) (list); + return NULL; + } + } + + 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; +} + +/* 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, warn_unused_result)) +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 (!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)) +static void +DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list) +{ + /* We deliberately skip error checking here. */ + 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)) +static void +DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list) +{ + /* We deliberately skip error checking here. */ + 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)) +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; + } +} +#endif + +/* 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..54a4d94 --- /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 + . */ + +/* To use the dynarray facility, you need to include + 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 + { + 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 + + To create a three-element array with elements 1, 2, 3, use this + code: + + struct dynarray_int dyn; + dynarray_int_init (&dyn); + int *place = dynarray_int_emplace (&dyn); + for (int i = 1; i <= 3; ++i) + { + int place = dynarray_int_emplace (&dyn); + assert (place != NULL); + *place = i; + } + struct int_array result = { (int *) (uintptr_t) -1, -1 }; + 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 + */ + +#ifndef _DYNARRAY_H +#define _DYNARRAY_H + +#include +#include +#include + +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..6123eae --- /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 + . */ + +#include +#include + +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..3593a8b --- /dev/null +++ b/malloc/dynarray_emplace_enlarge.c @@ -0,0 +1,67 @@ +/* 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 + . */ + +#include +#include +#include + +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 + /* Double the allocated size. */ + { + new_allocated = 2 * list->allocated; + 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..eeda423 --- /dev/null +++ b/malloc/dynarray_finalize.c @@ -0,0 +1,61 @@ +/* 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 + . */ + +#include +#include +#include + +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) { heap_array, 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 + . */ + +#include +#include +#include + +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 + . */ + +#include +#include +#include + +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..20348d1 --- /dev/null +++ b/malloc/tst-dynarray-at-fail.c @@ -0,0 +1,123 @@ +/* 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 + . */ + +#include "tst-dynarray-shared.h" + +#include +#include +#include +#include +#include + +/* 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); +} + +static void +test_empty (void *closure) +{ + size_t *pindex = closure; + struct dynarray_int dyn; + dynarray_int_init (&dyn); + dynarray_int_at (&dyn, *pindex); +} + + +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); +} + +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 diff --git a/malloc/tst-dynarray-fail.c b/malloc/tst-dynarray-fail.c new file mode 100644 index 0000000..69b84f0 --- /dev/null +++ b/malloc/tst-dynarray-fail.c @@ -0,0 +1,361 @@ +/* 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 + . */ + +/* This test is separate from tst-dynarray because it cannot run under + valgrind. */ + +#include "tst-dynarray-shared.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +/* 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; + } +} + +static void +test_int_fail (void) +{ + /* Exercise failure in emplace. */ + for (int do_finalize = 0; do_finalize < 2; ++do_finalize) + { + struct dynarray_int dyn; + dynarray_int_init (&dyn); + size_t count = 0; + while (true) + { + 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. */ + { + struct dynarray_int dyn; + dynarray_int_init (&dyn); + for (unsigned int i = 0; i < 10000; ++i) + { + 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); + } +} + +static void +test_str_fail (void) +{ + /* Exercise failure in emplace. */ + 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 = 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) + { + 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. */ + { + struct dynarray_str dyn; + dynarray_str_init (&dyn); + for (unsigned int i = 0; i < 1000; ++i) + { + char **place = dynarray_str_emplace (&dyn); + TEST_VERIFY_EXIT (place != NULL); + TEST_VERIFY_EXIT (*place == NULL); + *place = strdup ("placeholder"); + TEST_VERIFY_EXIT (place != NULL); + } + 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; +} + +#include 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 + . */ + +#include + +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 + +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 + +/* 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..7a57ec0 --- /dev/null +++ b/malloc/tst-dynarray.c @@ -0,0 +1,399 @@ +/* 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 + . */ + +#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 + +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 + +#include +#include +#include +#include +#include + +enum { max_count = 20 }; + +static void +test_int (void) +{ + { + struct dynarray_int dyn; + dynarray_int_init (&dyn); + CHECK_EMPTY (int, &dyn); + } + + { + 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); + } + + 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) + { + int *place = dynarray_int_emplace (&dyn); + TEST_VERIFY_EXIT (place != NULL); + TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn)); + *place = base + i; + 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); + } + } +} + +static void +test_str (void) +{ + { + struct dynarray_str dyn; + dynarray_str_init (&dyn); + CHECK_EMPTY (str, &dyn); + } + + { + 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); + } + + 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 **place = dynarray_str_emplace (&dyn); + TEST_VERIFY_EXIT (place != NULL); + TEST_VERIFY_EXIT (*place == NULL); + TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn)); + *place = xasprintf ("%d", base + i); + 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); + 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); + + 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); + } + + { + 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); + } +} + +static int +do_test (void) +{ + mtrace (); + test_int (); + test_str (); + test_long_init (); + return 0; +} + +#include 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 + . */ + +#ifndef SUPPORT_CAPTURE_SUBPROCESS_H +#define SUPPORT_CAPTURE_SUBPROCESS_H + +#include + +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.) */ +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 + . */ + +#include + +#include +#include +#include +#include +#include + +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); +} diff --git a/support/tst-support_capture_subprocess.c b/support/tst-support_capture_subprocess.c new file mode 100644 index 0000000..5086428 --- /dev/null +++ b/support/tst-support_capture_subprocess.c @@ -0,0 +1,174 @@ +/* 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 + . */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* 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); +} + +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; +} + +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) + { + struct test test = + { + .out = random_string (lengths[i]), + .err = random_string (lengths[j]), + .write_mode = write_mode, + .signal = signal * SIGTERM, /* 0 or SIGTERM. */ + .status = status * 3, /* 0 or 3. */ + }; + TEST_VERIFY (strlen (test.out) == lengths[i]); + TEST_VERIFY (strlen (test.err) == lengths[j]); + + 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 + 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. + 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 + . */ + +#include + +#include + +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 + . */ + +#include + +#include + +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. */