diff options
| -rw-r--r-- | ChangeLog | 17 | ||||
| -rw-r--r-- | include/alloc_buffer.h | 367 | ||||
| -rw-r--r-- | malloc/Makefile | 6 | ||||
| -rw-r--r-- | malloc/Versions | 8 | ||||
| -rw-r--r-- | malloc/alloc_buffer_alloc_array.c | 47 | ||||
| -rw-r--r-- | malloc/alloc_buffer_allocate.c | 36 | ||||
| -rw-r--r-- | malloc/alloc_buffer_copy_bytes.c | 34 | ||||
| -rw-r--r-- | malloc/alloc_buffer_copy_string.c | 30 | ||||
| -rw-r--r-- | malloc/alloc_buffer_create_failure.c | 31 | ||||
| -rw-r--r-- | malloc/tst-alloc_buffer.c | 665 |
10 files changed, 1240 insertions, 1 deletions
@@ -1,3 +1,20 @@ +2017-04-21 Florian Weimer <fweimer@redhat.com> + + * malloc/Makefile (tests-internal): Add tst-alloc_buffer. + (routines): Add alloc_buffer_alloc_array, alloc_buffer_allocate, + alloc_buffer_copy_bytes, alloc_buffer_copy_string, + alloc_buffer_create_failure. + * malloc/Versions (__libc_alloc_buffer_alloc_array) + (__libc_alloc_buffer_allocate, __libc_alloc_buffer_copy_bytes) + (__libc_alloc_buffer_copy_string) + (__libc_alloc_buffer_create_failure): Export as GLIBC_PRIVATE. + * malloc/alloc_buffer_alloc_array.c: New file. + * malloc/alloc_buffer_allocate.c: Likewise. + * malloc/alloc_buffer_copy_bytes.c: Likewise. + * malloc/alloc_buffer_copy_string.c: Likewise. + * malloc/alloc_buffer_create_failure.c: Likewise. + * malloc/tst-alloc_buffer.c: Likewise. + 2017-06-21 H.J. Lu <hongjiu.lu@intel.com> * sysdeps/x86_64/multiarch/Makefile (sysdep_routines): Add diff --git a/include/alloc_buffer.h b/include/alloc_buffer.h new file mode 100644 index 0000000000..d668a60d66 --- /dev/null +++ b/include/alloc_buffer.h @@ -0,0 +1,367 @@ +/* Allocation from a fixed-size buffer. + 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/>. */ + +/* Allocation buffers are used to carve out sub-allocations from a + larger allocation. Their primary application is in writing NSS + modules, which receive a caller-allocated buffer in which they are + expected to store variable-length results: + + void *buffer = ...; + size_t buffer_size = ...; + + struct alloc_buffer buf = alloc_buffer_create (buffer, buffer_size); + result->gr_name = alloc_buffer_copy_string (&buf, name); + + // Allocate a list of group_count groups and copy strings into it. + char **group_list = alloc_buffer_alloc_array + (&buf, char *, group_count + 1); + if (group_list == NULL) + return ...; // Request a larger buffer. + for (int i = 0; i < group_count; ++i) + group_list[i] = alloc_buffer_copy_string (&buf, group_list_src[i]); + group_list[group_count] = NULL; + ... + + if (alloc_buffer_has_failed (&buf)) + return ...; // Request a larger buffer. + result->gr_mem = group_list; + ... + + Note that it is not necessary to check the results of individual + allocation operations if the returned pointer is not dereferenced. + Allocation failure is sticky, so one check using + alloc_buffer_has_failed at the end covers all previous failures. + + A different use case involves combining multiple heap allocations + into a single, large one. In the following example, an array of + doubles and an array of ints is allocated: + + size_t double_array_size = ...; + size_t int_array_size = ...; + + void *heap_ptr; + struct alloc_buffer buf = alloc_buffer_allocate + (double_array_size * sizeof (double) + int_array_size * sizeof (int), + &heap_ptr); + _Static_assert (__alignof__ (double) >= __alignof__ (int), + "no padding after double array"); + double *double_array = alloc_buffer_alloc_array + (&buf, double, double_array_size); + int *int_array = alloc_buffer_alloc_array (&buf, int, int_array_size); + if (alloc_buffer_has_failed (&buf)) + return ...; // Report error. + ... + free (heap_ptr); + + The advantage over manual coding is that the computation of the + allocation size does not need an overflow check. In case of an + overflow, one of the subsequent allocations from the buffer will + fail. The initial size computation is checked for consistency at + run time, too. */ + +#ifndef _ALLOC_BUFFER_H +#define _ALLOC_BUFFER_H + +#include <inttypes.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdlib.h> +#include <sys/param.h> + +/* struct alloc_buffer objects refer to a region of bytes in memory of a + fixed size. The functions below can be used to allocate single + objects and arrays from this memory region, or write to its end. + On allocation failure (or if an attempt to write beyond the end of + the buffer with one of the copy functions), the buffer enters a + failed state. + + struct alloc_buffer objects can be copied. The backing buffer will + be shared, but the current write position will be independent. + + Conceptually, the memory region consists of a current write pointer + and a limit, beyond which the write pointer cannot move. */ +struct alloc_buffer +{ + /* uintptr_t is used here to simplify the alignment code, and to + avoid issues undefined subtractions if the buffer covers more + than half of the address space (which would result in differences + which could not be represented as a ptrdiff_t value). */ + uintptr_t __alloc_buffer_current; + uintptr_t __alloc_buffer_end; +}; + +enum + { + /* The value for the __alloc_buffer_current member which marks the + buffer as invalid (together with a zero-length buffer). */ + __ALLOC_BUFFER_INVALID_POINTER = 0, + }; + +/* Internal function. Terminate the process using __libc_fatal. */ +void __libc_alloc_buffer_create_failure (void *start, size_t size); + +/* Create a new allocation buffer. The byte range from START to START + + SIZE - 1 must be valid, and the allocation buffer allocates + objects from that range. If START is NULL (so that SIZE must be + 0), the buffer is marked as failed immediately. */ +static inline struct alloc_buffer +alloc_buffer_create (void *start, size_t size) +{ + uintptr_t current = (uintptr_t) start; + uintptr_t end = (uintptr_t) start + size; + if (end < current) + __libc_alloc_buffer_create_failure (start, size); + return (struct alloc_buffer) { current, end }; +} + +/* Internal function. See alloc_buffer_allocate below. */ +struct alloc_buffer __libc_alloc_buffer_allocate (size_t size, void **pptr) + __attribute__ ((nonnull (2))); + +/* Allocate a buffer of SIZE bytes using malloc. The returned buffer + is in a failed state if malloc fails. *PPTR points to the start of + the buffer and can be used to free it later, after the returned + buffer has been freed. */ +static __always_inline __attribute__ ((nonnull (2))) +struct alloc_buffer alloc_buffer_allocate (size_t size, void **pptr) +{ + return __libc_alloc_buffer_allocate (size, pptr); +} + +/* Mark the buffer as failed. */ +static inline void __attribute__ ((nonnull (1))) +alloc_buffer_mark_failed (struct alloc_buffer *buf) +{ + buf->__alloc_buffer_current = __ALLOC_BUFFER_INVALID_POINTER; + buf->__alloc_buffer_end = __ALLOC_BUFFER_INVALID_POINTER; +} + +/* Return the remaining number of bytes in the buffer. */ +static __always_inline __attribute__ ((nonnull (1))) size_t +alloc_buffer_size (const struct alloc_buffer *buf) +{ + return buf->__alloc_buffer_end - buf->__alloc_buffer_current; +} + +/* Return true if the buffer has been marked as failed. */ +static inline bool __attribute__ ((nonnull (1))) +alloc_buffer_has_failed (const struct alloc_buffer *buf) +{ + return buf->__alloc_buffer_current == __ALLOC_BUFFER_INVALID_POINTER; +} + +/* Add a single byte to the buffer (consuming the space for this + byte). Mark the buffer as failed if there is not enough room. */ +static inline void __attribute__ ((nonnull (1))) +alloc_buffer_add_byte (struct alloc_buffer *buf, unsigned char b) +{ + if (__glibc_likely (buf->__alloc_buffer_current < buf->__alloc_buffer_end)) + { + *(unsigned char *) buf->__alloc_buffer_current = b; + ++buf->__alloc_buffer_current; + } + else + alloc_buffer_mark_failed (buf); +} + +/* Obtain a pointer to LENGTH bytes in BUF, and consume these bytes. + NULL is returned if there is not enough room, and the buffer is + marked as failed, or if the buffer has already failed. + (Zero-length allocations from an empty buffer which has not yet + failed succeed.) */ +static inline __attribute__ ((nonnull (1))) void * +alloc_buffer_alloc_bytes (struct alloc_buffer *buf, size_t length) +{ + if (length <= alloc_buffer_size (buf)) + { + void *result = (void *) buf->__alloc_buffer_current; + buf->__alloc_buffer_current += length; + return result; + } + else + { + alloc_buffer_mark_failed (buf); + return NULL; + } +} + +/* Internal function. Statically assert that the type size is + constant and valid. */ +static __always_inline size_t +__alloc_buffer_assert_size (size_t size) +{ + if (!__builtin_constant_p (size)) + { + __errordecl (error, "type size is not constant"); + error (); + } + else if (size == 0) + { + __errordecl (error, "type size is zero"); + error (); + } + return size; +} + +/* Internal function. Statically assert that the type alignment is + constant and valid. */ +static __always_inline size_t +__alloc_buffer_assert_align (size_t align) +{ + if (!__builtin_constant_p (align)) + { + __errordecl (error, "type alignment is not constant"); + error (); + } + else if (align == 0) + { + __errordecl (error, "type alignment is zero"); + error (); + } + else if (!powerof2 (align)) + { + __errordecl (error, "type alignment is not a power of two"); + error (); + } + return align; +} + +/* Internal function. Obtain a pointer to an object. */ +static inline __attribute__ ((nonnull (1))) void * +__alloc_buffer_alloc (struct alloc_buffer *buf, size_t size, size_t align) +{ + if (size == 1 && align == 1) + return alloc_buffer_alloc_bytes (buf, size); + + size_t current = buf->__alloc_buffer_current; + size_t aligned = roundup (current, align); + size_t new_current = aligned + size; + if (aligned >= current /* No overflow in align step. */ + && new_current >= size /* No overflow in size computation. */ + && new_current <= buf->__alloc_buffer_end) /* Room in buffer. */ + { + buf->__alloc_buffer_current = new_current; + return (void *) aligned; + } + else + { + alloc_buffer_mark_failed (buf); + return NULL; + } +} + +/* Obtain a TYPE * pointer to an object in BUF of TYPE. Consume these + bytes from the buffer. Return NULL and mark the buffer as failed + if if there is not enough room in the buffer, or if the buffer has + failed before. */ +#define alloc_buffer_alloc(buf, type) \ + ((type *) __alloc_buffer_alloc \ + (buf, __alloc_buffer_assert_size (sizeof (type)), \ + __alloc_buffer_assert_align (__alignof__ (type)))) + +/* Internal function. Obtain a pointer to an object which is + subsequently added. */ +static inline const __attribute__ ((nonnull (1))) void * +__alloc_buffer_next (struct alloc_buffer *buf, size_t align) +{ + if (align == 1) + return (const void *) buf->__alloc_buffer_current; + + size_t current = buf->__alloc_buffer_current; + size_t aligned = roundup (current, align); + if (aligned >= current /* No overflow in align step. */ + && aligned <= buf->__alloc_buffer_end) /* Room in buffer. */ + { + buf->__alloc_buffer_current = aligned; + return (const void *) aligned; + } + else + { + alloc_buffer_mark_failed (buf); + return NULL; + } +} + +/* Like alloc_buffer_alloc, but do not advance the pointer beyond the + object (so a subseqent call to alloc_buffer_next or + alloc_buffer_alloc returns the same pointer). Note that the buffer + is still aligned according to the requirements of TYPE. The effect + of this function is similar to allocating a zero-length array from + the buffer. */ +#define alloc_buffer_next(buf, type) \ + ((const type *) __alloc_buffer_next \ + (buf, __alloc_buffer_assert_align (__alignof__ (type)))) + +/* Internal function. Allocate an array. */ +void * __libc_alloc_buffer_alloc_array (struct alloc_buffer *buf, + size_t size, size_t align, + size_t count) + __attribute__ ((nonnull (1))); + +/* Obtain a TYPE * pointer to an array of COUNT objects in BUF of + TYPE. Consume these bytes from the buffer. Return NULL and mark + the buffer as failed if if there is not enough room in the buffer, + or if the buffer has failed before. (Zero-length allocations from + an empty buffer which has not yet failed succeed.) */ +#define alloc_buffer_alloc_array(buf, type, count) \ + ((type *) __libc_alloc_buffer_alloc_array \ + (buf, __alloc_buffer_assert_size (sizeof (type)), \ + __alloc_buffer_assert_align (__alignof__ (type)), \ + count)) + +/* Internal function. See alloc_buffer_copy_bytes below. */ +struct alloc_buffer __libc_alloc_buffer_copy_bytes (struct alloc_buffer, + const void *, size_t) + __attribute__ ((nonnull (2))); + +/* Copy SIZE bytes starting at SRC into the buffer. If there is not + enough room in the buffer, the buffer is marked as failed. No + alignment of the buffer is performed. */ +static inline __attribute__ ((nonnull (1, 2))) void +alloc_buffer_copy_bytes (struct alloc_buffer *buf, const void *src, size_t size) +{ + *buf = __libc_alloc_buffer_copy_bytes (*buf, src, size); +} + +/* Internal function. See alloc_buffer_copy_string below. */ +struct alloc_buffer __libc_alloc_buffer_copy_string (struct alloc_buffer, + const char *) + __attribute__ ((nonnull (2))); + +/* Copy the string at SRC into the buffer, including its null + terminator. If there is not enough room in the buffer, the buffer + is marked as failed. Return a pointer to the string. */ +static inline __attribute__ ((nonnull (1, 2))) char * +alloc_buffer_copy_string (struct alloc_buffer *buf, const char *src) +{ + char *result = (char *) buf->__alloc_buffer_current; + *buf = __libc_alloc_buffer_copy_string (*buf, src); + if (alloc_buffer_has_failed (buf)) + result = NULL; + return result; +} + +#ifndef _ISOMAC +libc_hidden_proto (__libc_alloc_buffer_alloc_array) +libc_hidden_proto (__libc_alloc_buffer_allocate) +libc_hidden_proto (__libc_alloc_buffer_copy_bytes) +libc_hidden_proto (__libc_alloc_buffer_copy_string) +libc_hidden_proto (__libc_alloc_buffer_create_failure) +#endif + +#endif /* _ALLOC_BUFFER_H */ diff --git a/malloc/Makefile b/malloc/Makefile index 14c13f17dc..b50de7cd6c 100644 --- a/malloc/Makefile +++ b/malloc/Makefile @@ -33,6 +33,7 @@ tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \ tst-mallocfork2 \ tst-interpose-nothread \ tst-interpose-thread \ + tst-alloc_buffer \ tests-static := \ tst-interpose-static-nothread \ @@ -63,6 +64,11 @@ routines = malloc morecore mcheck mtrace obstack reallocarray \ dynarray_finalize \ dynarray_resize \ dynarray_resize_clear \ + alloc_buffer_alloc_array \ + alloc_buffer_allocate \ + alloc_buffer_copy_bytes \ + alloc_buffer_copy_string \ + alloc_buffer_create_failure \ install-lib := libmcheck.a non-lib.a := libmcheck.a diff --git a/malloc/Versions b/malloc/Versions index 5b543069b3..2357cff3da 100644 --- a/malloc/Versions +++ b/malloc/Versions @@ -76,7 +76,6 @@ libc { __libc_scratch_buffer_grow_preserve; __libc_scratch_buffer_set_array_size; - # Internal name for reallocarray __libc_reallocarray; @@ -86,5 +85,12 @@ libc { __libc_dynarray_finalize; __libc_dynarray_resize; __libc_dynarray_resize_clear; + + # struct alloc_buffer support + __libc_alloc_buffer_alloc_array; + __libc_alloc_buffer_allocate; + __libc_alloc_buffer_copy_bytes; + __libc_alloc_buffer_copy_string; + __libc_alloc_buffer_create_failure; } } diff --git a/malloc/alloc_buffer_alloc_array.c b/malloc/alloc_buffer_alloc_array.c new file mode 100644 index 0000000000..68e14da8dd --- /dev/null +++ b/malloc/alloc_buffer_alloc_array.c @@ -0,0 +1,47 @@ +/* Array allocation from a fixed-size buffer. + 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 <alloc_buffer.h> +#include <malloc-internal.h> +#include <libc-pointer-arith.h> + +void * +__libc_alloc_buffer_alloc_array (struct alloc_buffer *buf, size_t element_size, + size_t align, size_t count) +{ + size_t current = buf->__alloc_buffer_current; + /* The caller asserts that align is a power of two. */ + size_t aligned = ALIGN_UP (current, align); + size_t size; + bool overflow = check_mul_overflow_size_t (element_size, count, &size); + size_t new_current = aligned + size; + if (!overflow /* Multiplication did not overflow. */ + && aligned >= current /* No overflow in align step. */ + && new_current >= size /* No overflow in size computation. */ + && new_current <= buf->__alloc_buffer_end) /* Room in buffer. */ + { + buf->__alloc_buffer_current = new_current; + return (void *) aligned; + } + else + { + alloc_buffer_mark_failed (buf); + return NULL; + } +} +libc_hidden_def (__libc_alloc_buffer_alloc_array) diff --git a/malloc/alloc_buffer_allocate.c b/malloc/alloc_buffer_allocate.c new file mode 100644 index 0000000000..cbde72b842 --- /dev/null +++ b/malloc/alloc_buffer_allocate.c @@ -0,0 +1,36 @@ +/* Allocate a fixed-size allocation buffer using malloc. + 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 <alloc_buffer.h> + +#include <stdlib.h> + +struct alloc_buffer +__libc_alloc_buffer_allocate (size_t size, void **pptr) +{ + *pptr = malloc (size); + if (*pptr == NULL) + return (struct alloc_buffer) + { + .__alloc_buffer_current = __ALLOC_BUFFER_INVALID_POINTER, + .__alloc_buffer_end = __ALLOC_BUFFER_INVALID_POINTER + }; + else + return alloc_buffer_create (*pptr, size); +} +libc_hidden_def (__libc_alloc_buffer_allocate) diff --git a/malloc/alloc_buffer_copy_bytes.c b/malloc/alloc_buffer_copy_bytes.c new file mode 100644 index 0000000000..66196f1520 --- /dev/null +++ b/malloc/alloc_buffer_copy_bytes.c @@ -0,0 +1,34 @@ +/* Copy an array of bytes into the buffer. + 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 <alloc_buffer.h> + +#include <string.h> + +/* This function works on a copy of the buffer object, so that it can + remain non-addressable in the caller. */ +struct alloc_buffer +__libc_alloc_buffer_copy_bytes (struct alloc_buffer buf, + const void *src, size_t len) +{ + void *ptr = alloc_buffer_alloc_bytes (&buf, len); + if (ptr != NULL) + memcpy (ptr, src, len); + return buf; +} +libc_hidden_def (__libc_alloc_buffer_copy_bytes) diff --git a/malloc/alloc_buffer_copy_string.c b/malloc/alloc_buffer_copy_string.c new file mode 100644 index 0000000000..77c0023d51 --- /dev/null +++ b/malloc/alloc_buffer_copy_string.c @@ -0,0 +1,30 @@ +/* Copy a string into the allocation buffer. + 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 <alloc_buffer.h> + +#include <string.h> + +/* This function works on a copy of the buffer object, so that it can + remain non-addressable in the caller. */ +struct alloc_buffer +__libc_alloc_buffer_copy_string (struct alloc_buffer buf, const char *src) +{ + return __libc_alloc_buffer_copy_bytes (buf, src, strlen (src) + 1); +} +libc_hidden_def (__libc_alloc_buffer_copy_st |