[PATCH 01/13] walloc: new module

[Paul Eggert]

* lib/walloc.c, lib/walloc.h, modules/walloc:
* modules/walloc-tests, tests/test-walloc.c: New files.
---
 ChangeLog            |   4 ++
 lib/walloc.c         | 105 ++++++++++++++++++++++++++++++++
 lib/walloc.h         | 169 +++++++++++++++++++++++++++++++++++++++++++++++++++
 modules/walloc       |  29 +++++++++
 modules/walloc-tests |   9 +++
 tests/test-walloc.c  |  57 +++++++++++++++++
 6 files changed, 373 insertions(+)
 create mode 100644 lib/walloc.c
 create mode 100644 lib/walloc.h
 create mode 100644 modules/walloc
 create mode 100644 modules/walloc-tests
 create mode 100644 tests/test-walloc.c

diff --git a/ChangeLog b/ChangeLog
index 4294d51..7818861 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2017-06-04  Paul Eggert  <address@hidden>
 
+       walloc: new module
+       * lib/walloc.c, lib/walloc.h, modules/walloc:
+       * modules/walloc-tests, tests/test-walloc.c: New files.
+
        same-inode: port better to VMS 8.2 and later
        Problem reported by John E. Malmberg in:
        http://lists.gnu.org/archive/html/bug-gnulib/2017-06/msg00005.html
diff --git a/lib/walloc.c b/lib/walloc.c
new file mode 100644
index 0000000..d95d7bd
--- /dev/null
+++ b/lib/walloc.c
@@ -0,0 +1,105 @@
+/* Wary memory allocation with signed integer counts
+
+   Copyright 2017 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+   Written by Paul Eggert.  */
+
+#include <config.h>
+
+#define WALLOC_INLINE _GL_EXTERN_INLINE
+
+#include "walloc.h"
+
+#include "allocator.h"
+#include "intprops.h"
+#include "minmax.h"
+#include "verify.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+void *
+wreallocarray (void *a, ptrdiff_t n, ptrdiff_t s)
+{
+  ptrdiff_t n0 = 0;
+  return wallocmore (a, &n0, n, n, s, &stdlib_allocator);
+}
+
+void *
+wgrowalloc (void *a, ptrdiff_t *pn, ptrdiff_t incr, ptrdiff_t nmax,
+            ptrdiff_t itemsize)
+{
+  return wallocmore (a, pn, incr, nmax, itemsize, &stdlib_allocator);
+}
+
+void *
+wallocmore (void *a, ptrdiff_t *pn, ptrdiff_t incr, ptrdiff_t nmax,
+            ptrdiff_t itemsize, struct allocator const *alloc)
+{
+  ptrdiff_t n0 = *pn;
+  assume (0 <= n0 && 0 < itemsize && 0 <= incr && -1 <= nmax);
+
+  /* The approximate size to use for initial small allocation
+     requests.  This is the largest "small" request for the GNU C
+     library malloc.  */
+  enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 };
+
+  /* In the following implementation, positive sizes are increased by a
+     factor of approximately 1.5 so that repeated reallocations have
+     O(N) overall cost rather than O(N**2) cost, but the
+     specification for this function does not guarantee that rate.
+
+     Grow the array size by about 50%, adjusted to be at least S or
+     DEFAULT_MXFAST - DEFAULT_MXFAST % S bytes, whichever is greater.
+     Adjust the growth according to three constraints: INCR, NMAX,
+     and what the C language can represent safely.  */
+
+  ptrdiff_t n;
+  if (INT_ADD_WRAPV (n0, (n0 >> 1) + 1, &n))
+    n = PTRDIFF_MAX;
+  ptrdiff_t nbytes_max = MIN (PTRDIFF_MAX, SIZE_MAX - 1);
+  ptrdiff_t nmax_max = nbytes_max / itemsize;
+  if (! (0 <= nmax && nmax <= nmax_max))
+    nmax = nmax_max;
+  if ((n - n0 < incr && INT_ADD_WRAPV (n0, incr, &n)) || nmax < n)
+    n = nmax;
+
+  size_t nbytes;
+
+  if (n - n0 < incr)
+    nbytes = SIZE_MAX;
+  else
+    {
+      nbytes = n * itemsize;
+      if (nbytes < DEFAULT_MXFAST)
+        {
+          n = DEFAULT_MXFAST / itemsize;
+          nbytes = DEFAULT_MXFAST - DEFAULT_MXFAST % itemsize;
+        }
+      char *newa = alloc->reallocate (a, nbytes);
+      if (newa)
+        {
+          *pn = n;
+          return newa;
+        }
+    }
+
+  if (alloc->die)
+    alloc->die (nbytes);
+  return NULL;
+}
diff --git a/lib/walloc.h b/lib/walloc.h
new file mode 100644
index 0000000..c3a83f2
--- /dev/null
+++ b/lib/walloc.h
@@ -0,0 +1,169 @@
+/* Wary memory allocation with signed integer counts
+
+   Copyright 2017 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+   Written by Paul Eggert.  */
+
+
+/* Support memory allocation warily.  Use ptrdiff_t instead of size_t
+   For byte and object counts, as this works better on platforms where
+   reliability is important.  These platforms can use options like
+   GCC's -fsanitize=undefined to catch integer overflow errors that
+   might otherwise cause serious bugs, and this kind of checking does
+   not work with unsigned types like size_t where arithmetic wraps
+   around on overflow.
+
+   Using ptrdiff_t does not unduly impose a size limit on allocations
+   because memory allocations should never create objects with more
+   than PTRDIFF_MAX bytes anyway: such objects can have undefined
+   behavior later when pointers are subtracted.
+
+   It is a good idea to also use intprops.h when computing sizes by
+   adding or multiplying large numbers.  For example, intprops.h's
+   INT_ADD_WRAPV and INT_MULTIPLY_WRAPV can catch ptrdiff_t overflow.  */
+
+
+#ifndef WALLOC_H_
+#define WALLOC_H_
+
+#include <stddef.h>
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef WALLOC_INLINE
+# define WALLOC_INLINE _GL_INLINE
+#endif
+
+#if 3 <= __GNUC__
+# define _GL_ATTRIBUTE_MALLOC __attribute__ ((__malloc__))
+#else
+# define _GL_ATTRIBUTE_MALLOC
+#endif
+
+#if 4 < __GNUC__ + (3 <= __GNUC_MINOR__) && !defined __clang__
+# define _GL_ATTRIBUTE_ALLOC_SIZE(args) __attribute__ ((__alloc_size__ args))
+#else
+# define _GL_ATTRIBUTE_ALLOC_SIZE(args)
+#endif
+
+#if 4 < __GNUC__ + (9 <= __GNUC_MINOR__)
+# define _GL_ATTRIBUTE_RETURNS_NONNULL __attribute__ ((__returns_nonnull__))
+#else
+# define _GL_ATTRIBUTE_RETURNS_NONNULL
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Reallocate A to contain N * S bytes.  This is like BSD reallocarray
+   except with ptrdiff_t and positive S.  Return null on failure.  */
+
+extern void *wreallocarray (void *, ptrdiff_t, ptrdiff_t)
+  _GL_ATTRIBUTE_ALLOC_SIZE ((2, 3));
+
+/* Both growing allocator functions do the following:
+
+     Warily reallocate an array A with *PN allocated items, updating *PN
+     to the new allocation count.  If A is null, allocate a new array.
+
+     The reallocated array must have at least *PN + INCR items, and must
+     have at most NMAX items if NMAX is nonnegative; if this is not
+     possible the allocation fails.  Each array item has ITEMSIZE bytes.
+     ITEMSIZE must be positive, INCR must be nonnegative, and NMAX must
+     be at least -1.  For best amortized performance, grow the array by
+     a certain factor each time, if the other constraints permit it.
+
+     To grow an array A without saving its old contents, free (A) and
+     then pass NULL instead of A.
+
+   Here is how the two functions differ:
+
+     wallocmore (A, *PN, INCR, NMAX, ITEMSIZE, ALLOCATOR) uses
+     ALLOCATOR to allocate memory.  On failure to allocate a block of
+     NBYTES bytes it calls ALLOCATOR->die (NBYTES) if ALLOCATOR is
+     nonnull, and returns a null pointer if ALLOCATOR->die is null or
+     if it returns.  Here, NBYTES is 0 if it is unknown, e.g., because
+     of integer size overflow.
+
+     wgrowalloc (A, *PN, INCR, NMAX, ITEMSIZE) uses standard
+     allocators and returns null on failure.  It is equivalent to
+     wallocmore with ALLOCATOR == &stdlib_allocator.
+
+   Here is an example:
+
+     float *a;
+     ptrdiff_t used;
+     ptrdiff_t allocated;
+
+     bool
+     append_val (float value)
+     {
+       if (used == allocated)
+         {
+           float *a1 = wgrowalloc (a, &allocated, 1, -1, sizeof *a);
+           if (!a1)
+             return false;
+           a = a1;
+         }
+       a[used++] = value;
+       return true;
+     }
+
+   This causes wallocmore to allocate a block of some positive size
+   the first time it is called, and to grow the block when full.
+   It returns NULL on failure.
+
+   See xwalloc.h for an allocator that always succeeds.  */
+
+struct allocator;
+extern void *wgrowalloc (void *, ptrdiff_t *, ptrdiff_t, ptrdiff_t, ptrdiff_t);
+extern void *wallocmore (void *, ptrdiff_t *, ptrdiff_t, ptrdiff_t, ptrdiff_t,
+                         struct allocator const *);
+
+#ifdef __cplusplus
+}
+
+/* C++ does not allow conversions from void * to other pointer types
+   without a cast.  Use templates to work around the problem when
+   possible.  */
+
+template <typename T> inline T *
+wallocmore (T *a, ptrdiff_t *pn, ptrdiff_t incr, ptrdiff_t nmax,
+            ptrdiff_t itemsize, struct allocator const *allocator)
+{
+  return (T *) wallocmore ((void *) a, pn, incr, nmax, itemsize,
+                           allocator);
+}
+template <typename T> inline T *
+wgrowalloc (T *a, ptdiff_t *pn, ptrdiff_t incr, ptrdiff_t nmax,
+            ptrdiff_t itemsize)
+{
+  return (T *) wgrowalloc (a, pn, incr, nmax, itemsize);
+}
+template <typename T> inline T *
+wreallocarray (T *a, ptdiff_t n, ptrdiff_t s)
+{
+  return (T *) wreallocarray ((void *) a, n, s);
+}
+
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* !WALLOC_H_ */
diff --git a/modules/walloc b/modules/walloc
new file mode 100644
index 0000000..a40c151
--- /dev/null
+++ b/modules/walloc
@@ -0,0 +1,29 @@
+Description:
+Wary memory allocation with signed integer counts
+
+Files:
+lib/allocator.h
+lib/walloc.h
+lib/walloc.c
+
+Depends-on:
+extern-inline
+intprops
+minmax
+stdbool
+stdint
+verify
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += walloc.c
+
+Include:
+"walloc.h"
+
+License:
+LGPLv2+
+
+Maintainer:
+all
diff --git a/modules/walloc-tests b/modules/walloc-tests
new file mode 100644
index 0000000..9b7b792
--- /dev/null
+++ b/modules/walloc-tests
@@ -0,0 +1,9 @@
+Files:
+tests/test-walloc.c
+
+Depends-on:
+allocator
+
+Makefile.am:
+TESTS += test-walloc
+check_PROGRAMS += test-walloc
diff --git a/tests/test-walloc.c b/tests/test-walloc.c
new file mode 100644
index 0000000..61315e7
--- /dev/null
+++ b/tests/test-walloc.c
@@ -0,0 +1,57 @@
+/* Test walloc module
+   Copyright 2017 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include <walloc.h>
+
+#include <allocator.h>
+#include <stdlib.h>
+
+static ptrdiff_t
+test (ptrdiff_t *p, ptrdiff_t oldn, ptrdiff_t n)
+{
+  if (!p)
+    return 0;
+  for (ptrdiff_t i = 0; i < oldn; i++)
+    if (p[i] != ~i)
+      abort ();
+  for (ptrdiff_t i = oldn; i < n; i++)
+    p[i] = ~i;
+  return n;
+}
+
+int
+main (void)
+{
+  ptrdiff_t oldn = 0;
+  ptrdiff_t n = 1;
+  ptrdiff_t *p = wreallocarray (0, n, sizeof *p);
+  for (int i = 0; i < 10; i++)
+    {
+      oldn = test (p, oldn, n);
+      p = wgrowalloc (p, &n, 1, n + 2, sizeof *p);
+      oldn = test (p, oldn, n);
+      p = wallocmore (p, &n, 1, n + 2, sizeof *p, &stdlib_allocator);
+      oldn = test (p, oldn, n);
+      if (wgrowalloc (p, &n, 1, n, sizeof *p))
+        abort ();
+      if (wallocmore (p, &n, 1, n, sizeof *p, &stdlib_allocator))
+        abort ();
+    }
+  free (p);
+  return 0;
+}
-- 
2.9.4