This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH 06/25] Add struct scratch_buffer and its internal helper functions
- From: Florian Weimer <fweimer at redhat dot com>
- To: Paul Eggert <eggert at cs dot ucla dot edu>, libc-alpha at sourceware dot org
- Date: Mon, 23 Mar 2015 17:14:34 +0100
- Subject: Re: [PATCH 06/25] Add struct scratch_buffer and its internal helper functions
- Authentication-results: sourceware.org; auth=none
- References: <cover dot 1425285061 dot git dot fweimer at redhat dot com> <7a6fe503fb764beee3d5b89662d3bbf65242161c dot 1425285061 dot git dot fweimer at redhat dot com> <54F4BB15 dot 7070409 at cs dot ucla dot edu> <550C37F7 dot 10504 at redhat dot com> <550C4AE0 dot 60205 at cs dot ucla dot edu>
On 03/20/2015 05:29 PM, Paul Eggert wrote:
> Florian Weimer wrote:
>>>> +#define SCRATCH_BUFFER_ALIGNMENT \
>>>> + __attribute__ ((aligned (__alignof__ (union {void *p; double d;}))))
>>>
>>> This should use __attribute__ ((aligned (alignof (max_align_t)))), at
>>> least on C11 platforms.
>>
>> Hmm. Isn't intmax_t enough?
>
> I don't know about all the platforms, but in theory C11 says one should
> use max_align_t and that types other than intmax_t might have alignments
> stricter than that needed by intmax_t.
Commit 75b4202ab03337edb37536e3d9470a48a04c9341 used __alignof__
(unsigned long long). I would rather go with intmax_t because it's not
clear to me if __alignof__ (max_align_t) increases to 64 if AVX-512 is
enabled on x86_64.
>> /* Grows *BUFFER so that it can store at least NELEM elements of SIZE
>
> Grows -> grow
I think you mean âGrowâ. I fixed the other occurrences of the finite
forms as well.
>> bytes. The buffer contents is NOT preserved. Both NELEM and SIZE
>
> is NOT -> are NOT
Okay.
>> Empirically, I'm pretty certain the division does not matter
>> performance-wise.
>
> Even on platforms where integer division is a subroutine? Perhaps glibc
> isn't meant for such platforms, but still....
Even there, because you'll have at least 64K array elements, and the
division will be amortized across all that. :)
Do you think this is ready to commit now? Does anyone else want to
comment on the new internal interfaces?
* include/scratch_buffer.h: New file.
* malloc/scratch_buffer_grow.c: Likewise.
* malloc/scratch_buffer_grow_preserve.c: Likewise.
* malloc/scratch_buffer_set_array_size.c: Likewise.
* malloc/tst-scratch_buffer.c: Likewise.
* malloc/Makefile (routines): Add scratch_buffer_grow.
(tests): Add test case.
* misc/Versions (GLIBC_PRIVATE): Export
__libc_scratch_buffer_grow, __libc_scratch_buffer_grow_preserve,
__libc_scratch_buffer_set_array_size.
--
Florian Weimer / Red Hat Product Security
>From 8f4f7c662890d8ce2f28da4f7108cd2d884594be Mon Sep 17 00:00:00 2001
From: Florian Weimer <fweimer@redhat.com>
Date: Sun, 1 Mar 2015 15:28:11 +0100
Subject: [PATCH] Add struct scratch_buffer and its internal helper functions
These will be used from NSS modules, so they have to be exported.
---
include/scratch_buffer.h | 142 ++++++++++++++++++++++++++++++
malloc/Makefile | 6 +-
malloc/Versions | 5 ++
malloc/scratch_buffer_grow.c | 52 +++++++++++
malloc/scratch_buffer_grow_preserve.c | 65 ++++++++++++++
malloc/scratch_buffer_set_array_size.c | 60 +++++++++++++
malloc/tst-scratch_buffer.c | 155 +++++++++++++++++++++++++++++++++
7 files changed, 483 insertions(+), 2 deletions(-)
create mode 100644 include/scratch_buffer.h
create mode 100644 malloc/scratch_buffer_grow.c
create mode 100644 malloc/scratch_buffer_grow_preserve.c
create mode 100644 malloc/scratch_buffer_set_array_size.c
create mode 100644 malloc/tst-scratch_buffer.c
diff --git a/include/scratch_buffer.h b/include/scratch_buffer.h
new file mode 100644
index 0000000..b324232
--- /dev/null
+++ b/include/scratch_buffer.h
@@ -0,0 +1,142 @@
+/* Variable-sized buffer with on-stack default allocation.
+ Copyright (C) 2015 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef _SCRATCH_BUFFER_H
+#define _SCRATCH_BUFFER_H
+
+/* Scratch buffers with a default stack allocation and fallback to
+ heap allocation. It is expected that this function is used in this
+ way:
+
+ struct scratch_buffer tmpbuf;
+ scratch_buffer_init (&tmpbuf);
+
+ while (!function_that_uses_buffer (tmpbuf.data, tmpbuf.length))
+ if (!scratch_buffer_grow (&tmpbuf))
+ return -1;
+
+ scratch_buffer_free (&tmpbuf);
+ return 0;
+
+ The allocation functions (scratch_buffer_grow,
+ scratch_buffer_grow_preserve, scratch_buffer_set_array_size) make
+ sure that the heap allocation, if any, is freed, so that the code
+ above does not have a memory leak. The buffer still remains in a
+ state that can be deallocated using scratch_buffer_free, so a loop
+ like this is valid as well:
+
+ struct scratch_buffer tmpbuf;
+ scratch_buffer_init (&tmpbuf);
+
+ while (!function_that_uses_buffer (tmpbuf.data, tmpbuf.length))
+ if (!scratch_buffer_grow (&tmpbuf))
+ break;
+
+ scratch_buffer_free (&tmpbuf);
+
+ The non-inlined functions are implemented in such a way that it is
+ possible to change the size of the pre-allocated buffer without
+ impacting ABI.
+
+ scratch_buffer_grow and scratch_buffer_grow_preserve are guaranteed
+ to grow the buffer by at least 512 bytes. This means that when
+ using the scratch buffer as a backing store for a non-character
+ array whose element size, in bytes, is 512 or smaller, the scratch
+ buffer only has to grow once to make room for at least one more
+ element.
+*/
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+/* Scratch buffer. Must be initialized with scratch_buffer_init
+ before its use. */
+struct scratch_buffer {
+ void *data; /* Pointer to the beginning of the scratch area. */
+ size_t length; /* Allocated space at the data pointer, in bytes. */
+ char __space[1024] __attribute__ ((aligned (__alignof__ (intmax_t))));
+};
+
+/* Initializes *BUFFER so that BUFFER->data points to BUFFER->__space
+ and BUFFER->length reflects the available space. */
+static inline void
+scratch_buffer_init (struct scratch_buffer *buffer)
+ __attribute__ ((always_inline));
+static inline void
+scratch_buffer_init (struct scratch_buffer *buffer)
+{
+ buffer->data = buffer->__space;
+ buffer->length = sizeof (buffer->__space);
+}
+
+/* Deallocates *BUFFER (if it was heap-allocated). */
+static inline void
+scratch_buffer_free (struct scratch_buffer *buffer)
+{
+ if (buffer->data != buffer->__space)
+ free (buffer->data);
+}
+
+/* Grow *BUFFER by some arbitrary amount. The buffer contents is NOT
+ preserved. Return true on success, false on allocation failure (in
+ which case the old buffer is freed). On success, the new buffer is
+ larger than the previous size. On failure, *BUFFER is deallocated,
+ but remains in a free-able state, and errno is set. */
+bool __libc_scratch_buffer_grow (struct scratch_buffer *buffer);
+libc_hidden_proto (__libc_scratch_buffer_grow)
+
+/* Alias for __libc_scratch_buffer_grow. */
+static inline bool
+scratch_buffer_grow (struct scratch_buffer *buffer)
+{
+ return __glibc_likely (__libc_scratch_buffer_grow (buffer));
+}
+
+/* Like __libc_scratch_buffer_grow, but preserve the old buffer
+ contents on success, as a prefix of the new buffer. */
+bool __libc_scratch_buffer_grow_preserve (struct scratch_buffer *buffer);
+libc_hidden_proto (__libc_scratch_buffer_grow_preserve)
+
+/* Alias for __libc_scratch_buffer_grow_preserve. */
+static inline bool
+scratch_buffer_grow_preserve (struct scratch_buffer *buffer)
+{
+ return __glibc_likely (__libc_scratch_buffer_grow_preserve (buffer));
+}
+
+/* Grow *BUFFER so that it can store at least NELEM elements of SIZE
+ bytes. The buffer contents are NOT preserved. Both NELEM and SIZE
+ can be zero. Return true on success, false on allocation failure
+ (in which case the old buffer is freed, but *BUFFER remains in a
+ free-able state, and errno is set). It is unspecified whether this
+ function can reduce the array size. */
+bool __libc_scratch_buffer_set_array_size (struct scratch_buffer *buffer,
+ size_t nelem, size_t size);
+libc_hidden_proto (__libc_scratch_buffer_set_array_size)
+
+/* Alias for __libc_scratch_set_array_size. */
+static inline bool
+scratch_buffer_set_array_size (struct scratch_buffer *buffer,
+ size_t nelem, size_t size)
+{
+ return __glibc_likely (__libc_scratch_buffer_set_array_size
+ (buffer, nelem, size));
+}
+
+#endif /* _SCRATCH_BUFFER_H */
diff --git a/malloc/Makefile b/malloc/Makefile
index 5f68a79..9e7112a 100644
--- a/malloc/Makefile
+++ b/malloc/Makefile
@@ -27,10 +27,12 @@ headers := $(dist-headers) obstack.h mcheck.h
tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \
tst-mallocstate tst-mcheck tst-mallocfork tst-trim1 \
tst-malloc-usable tst-realloc tst-posix_memalign \
- tst-pvalloc tst-memalign tst-mallopt
+ tst-pvalloc tst-memalign tst-mallopt tst-scratch_buffer
test-srcs = tst-mtrace
-routines = malloc morecore mcheck mtrace obstack
+routines = malloc morecore mcheck mtrace obstack \
+ scratch_buffer_grow scratch_buffer_grow_preserve \
+ scratch_buffer_set_array_size
install-lib := libmcheck.a
non-lib.a := libmcheck.a
diff --git a/malloc/Versions b/malloc/Versions
index 7ca9bdf..f3c3d8a 100644
--- a/malloc/Versions
+++ b/malloc/Versions
@@ -67,5 +67,10 @@ libc {
# Internal destructor hook for libpthread.
__libc_thread_freeres;
+
+ # struct scratch_buffer support
+ __libc_scratch_buffer_grow;
+ __libc_scratch_buffer_grow_preserve;
+ __libc_scratch_buffer_set_array_size;
}
}
diff --git a/malloc/scratch_buffer_grow.c b/malloc/scratch_buffer_grow.c
new file mode 100644
index 0000000..6621393
--- /dev/null
+++ b/malloc/scratch_buffer_grow.c
@@ -0,0 +1,52 @@
+/* Variable-sized buffer with on-stack default allocation.
+ Copyright (C) 2015 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 <scratch_buffer.h>
+#include <errno.h>
+
+bool
+__libc_scratch_buffer_grow (struct scratch_buffer *buffer)
+{
+ size_t new_length = buffer->length * 2;
+
+ /* Discard old buffer. */
+ scratch_buffer_free (buffer);
+
+ /* Check for overflow. */
+ if (__glibc_unlikely (new_length < buffer->length))
+ {
+ /* Buffer must remain valid to free. */
+ scratch_buffer_init (buffer);
+ __set_errno (ENOMEM);
+ return false;
+ }
+
+ void *new_ptr = malloc (new_length);
+ if (new_ptr == NULL)
+ {
+ /* Buffer must remain valid to free. */
+ scratch_buffer_init (buffer);
+ return false;
+ }
+
+ /* Install new heap-based buffer. */
+ buffer->data = new_ptr;
+ buffer->length = new_length;
+ return true;
+}
+libc_hidden_def (__libc_scratch_buffer_grow);
diff --git a/malloc/scratch_buffer_grow_preserve.c b/malloc/scratch_buffer_grow_preserve.c
new file mode 100644
index 0000000..3abbd56
--- /dev/null
+++ b/malloc/scratch_buffer_grow_preserve.c
@@ -0,0 +1,65 @@
+/* Variable-sized buffer with on-stack default allocation.
+ Copyright (C) 2015 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 <scratch_buffer.h>
+#include <errno.h>
+
+bool
+__libc_scratch_buffer_grow_preserve (struct scratch_buffer *buffer)
+{
+ size_t new_length = 2 * buffer->length;
+ void *new_ptr;
+
+ if (buffer->data == buffer->__space)
+ {
+ /* Move buffer to the heap. No overflow is possible because
+ buffer->length describes a small buffer on the stack. We use
+ buffer->length instead of sizeof (buffer->__space) to avoid
+ making the size of struct scratch_buffer part of the ABI. */
+ new_ptr = malloc (new_length);
+ if (new_ptr == NULL)
+ return false;
+ memcpy (new_ptr, buffer->__space, buffer->length);
+ }
+ else
+ {
+ /* Buffer was already on the heap. Check for overflow. */
+ if (__glibc_unlikely (new_length < buffer->length))
+ {
+ /* Deallocate, but buffer must remain valid to free. */
+ free (buffer->data);
+ scratch_buffer_init (buffer);
+ __set_errno (ENOMEM);
+ return false;
+ }
+ new_ptr = realloc (buffer->data, new_length);
+ if (new_ptr == NULL)
+ {
+ /* Deallocate, but buffer must remain valid to free. */
+ free (buffer->data);
+ scratch_buffer_init (buffer);
+ return false;
+ }
+ }
+
+ /* Install new heap-based buffer. */
+ buffer->data = new_ptr;
+ buffer->length = new_length;
+ return true;
+}
+libc_hidden_def (__libc_scratch_buffer_grow_preserve);
diff --git a/malloc/scratch_buffer_set_array_size.c b/malloc/scratch_buffer_set_array_size.c
new file mode 100644
index 0000000..6e7a7e9
--- /dev/null
+++ b/malloc/scratch_buffer_set_array_size.c
@@ -0,0 +1,60 @@
+/* Variable-sized buffer with on-stack default allocation.
+ Copyright (C) 2015 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 <scratch_buffer.h>
+#include <errno.h>
+
+bool
+__libc_scratch_buffer_set_array_size (struct scratch_buffer *buffer,
+ size_t nelem, size_t size)
+{
+ /* Avoid overflow check if both values are small. */
+ if ((nelem | size) >> (sizeof (size_t) * CHAR_BIT / 2) != 0)
+ {
+ if (nelem != 0 && size > SIZE_MAX / nelem)
+ {
+ /* Overflow. Discard the old buffer, but it must remain
+ valid to free. */
+ scratch_buffer_free (buffer);
+ scratch_buffer_init (buffer);
+ __set_errno (ENOMEM);
+ return false;
+ }
+ }
+
+ size_t new_length = nelem * size;
+ if (new_length <= buffer->length)
+ return true;
+
+ /* Discard old buffer. */
+ scratch_buffer_free (buffer);
+
+ char *new_ptr = malloc (new_length);
+ if (new_ptr == NULL)
+ {
+ /* Buffer must remain valid to free. */
+ scratch_buffer_init (buffer);
+ return false;
+ }
+
+ /* Install new heap-based buffer. */
+ buffer->data = new_ptr;
+ buffer->length = new_length;
+ return true;
+}
+libc_hidden_def (__libc_scratch_buffer_set_array_size);
diff --git a/malloc/tst-scratch_buffer.c b/malloc/tst-scratch_buffer.c
new file mode 100644
index 0000000..dcae512
--- /dev/null
+++ b/malloc/tst-scratch_buffer.c
@@ -0,0 +1,155 @@
+/*
+ Copyright (C) 2015 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 <scratch_buffer.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <string.h>
+
+static bool
+unchanged_array_size (struct scratch_buffer *buf, size_t a, size_t b)
+{
+ size_t old_length = buf->length;
+ if (!scratch_buffer_set_array_size (buf, a, b))
+ {
+ printf ("scratch_buffer_set_array_size failed: %zu %zu\n",
+ a, b);
+ return false;
+ }
+ if (old_length != buf->length)
+ {
+ printf ("scratch_buffer_set_array_size did not preserve size: %zu %zu\n",
+ a, b);
+ return false;
+ }
+ return true;
+}
+
+static bool
+array_size_must_fail (size_t a, size_t b)
+{
+ for (int pass = 0; pass < 2; ++pass)
+ {
+ struct scratch_buffer buf;
+ scratch_buffer_init (&buf);
+ if (pass > 0)
+ if (!scratch_buffer_grow (&buf))
+ {
+ printf ("scratch_buffer_grow in array_size_must_fail failed\n");
+ return false;
+ }
+ if (scratch_buffer_set_array_size (&buf, a, b))
+ {
+ printf ("scratch_buffer_set_array_size passed: %d %zu %zu\n",
+ pass, a, b);
+ return false;
+ }
+ if (buf.data != buf.__space)
+ {
+ printf ("scratch_buffer_set_array_size did not free: %d %zu %zu\n",
+ pass, a, b);
+ return false;
+ }
+ }
+ return true;
+}
+
+static int
+do_test (void)
+{
+ {
+ struct scratch_buffer buf;
+ scratch_buffer_init (&buf);
+ memset (buf.data, ' ', buf.length);
+ scratch_buffer_free (&buf);
+ }
+ {
+ struct scratch_buffer buf;
+ scratch_buffer_init (&buf);
+ memset (buf.data, ' ', buf.length);
+ size_t old_length = buf.length;
+ scratch_buffer_grow (&buf);
+ if (buf.length <= old_length)
+ {
+ printf ("scratch_buffer_grow did not enlarge buffer\n");
+ return 1;
+ }
+ memset (buf.data, ' ', buf.length);
+ scratch_buffer_free (&buf);
+ }
+ {
+ struct scratch_buffer buf;
+ scratch_buffer_init (&buf);
+ memset (buf.data, '@', buf.length);
+ strcpy (buf.data, "prefix");
+ size_t old_length = buf.length;
+ scratch_buffer_grow_preserve (&buf);
+ if (buf.length <= old_length)
+ {
+ printf ("scratch_buffer_grow_preserve did not enlarge buffer\n");
+ return 1;
+ }
+ if (strcmp (buf.data, "prefix") != 0)
+ {
+ printf ("scratch_buffer_grow_preserve did not copy buffer\n");
+ return 1;
+ }
+ for (unsigned i = 7; i < old_length; ++i)
+ if (((char *)buf.data)[i] != '@')
+ {
+ printf ("scratch_buffer_grow_preserve did not copy buffer (%u)\n",
+ i);
+ return 1;
+ }
+ scratch_buffer_free (&buf);
+ }
+ {
+ struct scratch_buffer buf;
+ scratch_buffer_init (&buf);
+ for (int pass = 0; pass < 4; ++pass)
+ {
+ if (!(unchanged_array_size (&buf, 0, 0)
+ && unchanged_array_size (&buf, 1, 0)
+ && unchanged_array_size (&buf, 0, 1)
+ && unchanged_array_size (&buf, -1, 0)
+ && unchanged_array_size (&buf, 0, -1)
+ && unchanged_array_size (&buf, 1ULL << 16, 0)
+ && unchanged_array_size (&buf, 0, 1ULL << 16)
+ && unchanged_array_size (&buf, 1ULL << 32, 0)
+ && unchanged_array_size (&buf, 0, 1ULL << 32)))
+ return 1;
+ if (!scratch_buffer_grow (&buf))
+ {
+ printf ("scratch_buffer_grow_failed (pass %d)\n", pass);
+ }
+ }
+ scratch_buffer_free (&buf);
+ }
+ {
+ if (!(array_size_must_fail (-1, 1)
+ && array_size_must_fail (-1, -1)
+ && array_size_must_fail (1, -1)
+ && array_size_must_fail (((size_t)-1) / 4, 4)
+ && array_size_must_fail (4, ((size_t)-1) / 4)))
+ return 1;
+ }
+ return 0;
+}
+
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"
--
2.1.0