From patchwork Tue Apr 7 09:10:43 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 458608 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 D9AAA1400A0 for ; Tue, 7 Apr 2015 19:11:02 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass reason="1024-bit key; unprotected key" header.d=sourceware.org header.i=@sourceware.org header.b=WILaRWmE; dkim-adsp=none (unprotected policy); 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:message-id:date:from:mime-version:to:cc :subject:references:in-reply-to:content-type; q=dns; s=default; b= V/X+efsSH37Bmhjsg2nLjnV117XD9Pk+oYrSTHpeiAXHIsaV3Et/uJILgFj67eRt A2l3cXYE3dufZfX7kB9XFPJiZBDGefTm8kzKkIN3qYqj1/mV5RytYCjRP8uZGM/3 62eyAljJvwRQLA2hXm8ui2J6a9qg6t++4t5m6hs3P9o= 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:message-id:date:from:mime-version:to:cc :subject:references:in-reply-to:content-type; s=default; bh=Czf8 8UTTmI1vc4+8O1Ogcfe4d+Y=; b=WILaRWmEetZGzmmoOaJW79RVmejQg3UjnW+e Htw++DPquiLQYbbyay/6bWKmBSwZ7VRzfXFkjpo6z2PpbsLzD08heDZpC+nxku5Z iygFI5L5jBzCboSbgZnRprsjzvcrlg9YGvyzEXnIMV2zvet3sJAwcaUIHD+KxuTS d8J/3ME= Received: (qmail 51937 invoked by alias); 7 Apr 2015 09:10:56 -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 51917 invoked by uid 89); 7 Apr 2015 09:10:55 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.8 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Message-ID: <55239F13.5040700@redhat.com> Date: Tue, 07 Apr 2015 11:10:43 +0200 From: Florian Weimer User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 MIME-Version: 1.0 To: Paul Eggert CC: libc-alpha@sourceware.org Subject: Re: [PATCH 06/25] Add struct scratch_buffer and its internal helper functions References: <7a6fe503fb764beee3d5b89662d3bbf65242161c.1425285061.git.fweimer@redhat.com> <54F4BB15.7070409@cs.ucla.edu> <550C37F7.10504@redhat.com> <550C4AE0.60205@cs.ucla.edu> <55103BEA.7070305@redhat.com> <5510505B.8060209@cs.ucla.edu> <55105F2C.6040400@redhat.com> <55105FED.80004@redhat.com> <551C1C9B.1060807@redhat.com> <551D8AE1.5000805@redhat.com> <551DE8EA.6080200@cs.ucla.edu> <5522BC03.5090300@redhat.com> <5523007D.9080906@cs.ucla.edu> In-Reply-To: <5523007D.9080906@cs.ucla.edu> On 04/06/2015 11:54 PM, Paul Eggert wrote: > Thanks, this looks good. One performance nit that I noticed this time > around. here: > > On 04/06/2015 10:01 AM, Florian Weimer wrote: >> + /* 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; > > It's better to compute new_length first, before the overflow check, and > then replace "size > SIZE_MAX / nelem" with "size != new_length / > nelem". This will avoid the need for having SIZE_MAX in the executable, > which should shrink the code a tad. Also, hardware integer division > tends to run faster with smaller dividends, which would be the case if > this change were made. Thanks for the suggestion. I incorporated it into the version I committed after verifying it does indeed reduce code size (also attached). From cfcfd4614b8b01b2782ac4dcafb21d14d74d5184 Mon Sep 17 00:00:00 2001 From: Florian Weimer Date: Tue, 7 Apr 2015 11:03:43 +0200 Subject: [PATCH] Add struct scratch_buffer and its internal helper functions These will be used from NSS modules, so they have to be exported. --- ChangeLog | 13 +++ include/scratch_buffer.h | 137 +++++++++++++++++++++++++++++ malloc/Makefile | 6 +- malloc/Versions | 5 ++ malloc/scratch_buffer_grow.c | 52 +++++++++++ malloc/scratch_buffer_grow_preserve.c | 62 +++++++++++++ malloc/scratch_buffer_set_array_size.c | 59 +++++++++++++ malloc/tst-scratch_buffer.c | 155 +++++++++++++++++++++++++++++++++ 8 files changed, 487 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/ChangeLog b/ChangeLog index e4f86dc..4e1df07 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,16 @@ +2015-04-07 Florian Weimer + + * 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. + * malloc/Versions (GLIBC_PRIVATE): Export + __libc_scratch_buffer_grow, __libc_scratch_buffer_grow_preserve, + __libc_scratch_buffer_set_array_size. + 2015-04-06 Richard Henderson * sysdeps/unix/alpha/sysdep.h: Unconditionally include dl-sysdep.h. diff --git a/include/scratch_buffer.h b/include/scratch_buffer.h new file mode 100644 index 0000000..6f92694 --- /dev/null +++ b/include/scratch_buffer.h @@ -0,0 +1,137 @@ +/* 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 + . */ + +#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); + + 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 +#include + +#include + +/* 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__ (libc_max_align_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) +{ + 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 __always_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 __always_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 __always_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..3f27e0e --- /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 + . */ + +#include +#include + +bool +__libc_scratch_buffer_grow (struct scratch_buffer *buffer) +{ + void *new_ptr; + size_t new_length = buffer->length * 2; + + /* Discard old buffer. */ + scratch_buffer_free (buffer); + + /* Check for overflow. */ + if (__glibc_likely (new_length >= buffer->length)) + new_ptr = malloc (new_length); + else + { + __set_errno (ENOMEM); + new_ptr = NULL; + } + + if (__glibc_unlikely (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..f2edb49 --- /dev/null +++ b/malloc/scratch_buffer_grow_preserve.c @@ -0,0 +1,62 @@ +/* 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 + . */ + +#include +#include + +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. */ + 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_likely (new_length >= buffer->length)) + new_ptr = realloc (buffer->data, new_length); + else + { + __set_errno (ENOMEM); + new_ptr = NULL; + } + + if (__glibc_unlikely (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..a00b520 --- /dev/null +++ b/malloc/scratch_buffer_set_array_size.c @@ -0,0 +1,59 @@ +/* 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 + . */ + +#include +#include + +bool +__libc_scratch_buffer_set_array_size (struct scratch_buffer *buffer, + size_t nelem, size_t size) +{ + size_t new_length = nelem * size; + + /* Avoid overflow check if both values are small. */ + if ((nelem | size) >> (sizeof (size_t) * CHAR_BIT / 2) != 0 + && nelem != 0 && size != new_length / 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; + } + + 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 + . */ + +#include +#include +#include +#include + +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