Re: [bug-gnulib] valloc()?

[Derek Price]

Bruno Haible wrote:

> This is the best you can do in a portable way, but
>  1. the return value cannot be passed to free(),
>  2. it wastes 1/2 page of memory on average.
>
> Therefore I'd suggest a new interface:
>  void* pagealign_alloc(size_t);
>  void pagealign_free(void*);
>
> and do the implementation as follows:
>  - If mmap() is available, use mmap and some bookkeeping for pagealign_alloc,
>    and munmap() for pagealign_free,
>  - Otherwise, if posix_memalign() is available, use it and free(),
>  - Otherwise, use something similar to the valloc() above.

Okay, I've implemented this as you suggested, Bruno.  Installed in CVS,
it passes tests in all four modes (MMAP, MMAP/NO-MAP_ANON,
POSIX_MEMALIGN, OTHER).  I've attached the patch, but I still have a few
questions.  The first is the one I raised earlier about why mmap()
should be prefered to posix_memalign() when there is no bookkeeping
overhead involved when using posix_memalign().

The second is more for the CVS folks.  Is the speed increase caused by
reduced page faults worth the increased memory usage on systems that
have neither mmap() nor posix_memalign()?  This should almost double
buffer memory usage on those systems.  Of course, systems with mmap() or
posix_memalign() should see both a reduction in memory usage and a
speedup.  I have a complete patch for CVS using the new functions.  I'll
try and forward it tomorrow in case anyone has the time and facilities
for running benchmarks.

2005-03-03  Derek R. Price  <address@hidden>

   * lib/pagealign_alloc.c, lib/pagealign_alloc.h, m4/mmap.m4,
m4/pagealign_alloc.m4, modules/pagealign_alloc: New files.

Regards,

Derek

Index: lib/pagealign_alloc.c
===================================================================
RCS file: lib/pagealign_alloc.c
diff -N lib/pagealign_alloc.c
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ lib/pagealign_alloc.c       3 Mar 2005 05:56:43 -0000
@@ -0,0 +1,173 @@
+/* pagealign_alloc.c -- allocate page aligned memory.
+   (Mostly) portable public-domain implementation -- Derek R. Price
+
+   Copyright (C) 2005 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 2, 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+   USA.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <errno.h>
+#include <stdlib.h>
+
+#if HAVE_FCNTL_H
+# include <fcntl.h>
+#endif
+
+#if HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+
+#ifdef HAVE_MMAP
+# include <sys/mman.h>
+#endif
+
+#include "error.h"
+#include "getpagesize.h"
+#include "pagealign_alloc.h"
+#include "xalloc.h"
+
+
+
+#if defined (HAVE_MMAP) || !defined (HAVE_POSIX_MEMALIGN)
+/* A simple linked list is probably not the most efficient way to store these.
+ */
+typedef struct memnode_s memnode_t;
+struct memnode_s
+{
+    void *out;
+# ifdef HAVE_MMAP
+    size_t orig;
+# else /* !HAVE_MMAP */
+    void *orig;
+# endif /* HAVE_MMAP */
+    memnode_t *next;
+};
+
+
+
+static memnode_t memtable = {NULL, 0, NULL};
+
+
+
+/* Dispose of the memnode containing a map for the OUT in question and
+ * return the content of the node's ORIG field.
+ */
+#ifdef HAVE_MMAP
+static size_t
+#elif !HAVE_POSIX_MEMALIGN
+static void *
+#endif
+get_memnode (void *out)
+{
+#ifdef HAVE_MMAP
+    size_t ret;
+#elif !HAVE_POSIX_MEMALIGN
+    void *ret;
+#endif
+    memnode_t *c, *p = &memtable;
+
+    for (c = p->next; c != NULL; p = c, c = c->next)
+       if (c->out == out) break;
+    if (c)
+    {
+       /* Remove this entry from the list, save the return value, and
+        * free it.
+        */
+       p->next = c->next;
+       ret = c->orig;
+       free (c);
+    }
+    else
+       error (1, EINVAL, "pagealign_alloc: Attempt to free untracked memory.");
+
+    return ret;
+}
+
+
+
+static void
+new_memnode (void *out,
+# ifdef HAVE_MMAP
+    size_t orig
+# else /* !HAVE_MMAP */
+    void *orig
+# endif /* HAVE_MMAP */
+            )
+{
+    memnode_t *new = xmalloc (sizeof (memnode_t));
+    new->out = out;
+    new->orig = orig;
+    new->next = memtable.next;
+    memtable.next = new;
+}
+#endif /* HAVE_MMAP || !HAVE_POSIX_MEMALIGN */
+
+
+
+void *
+pagealign_alloc (size_t size)
+{
+    void *ret;
+#ifdef HAVE_MMAP
+    int flags;
+    static int fd = -1;  /* Only open /dev/zero once in order to avoid limiting
+                         * the amount of memory we may allocate based on the
+                         * number of open file descriptors.
+                         */
+# ifdef HAVE_MAP_ANONYMOUS
+    flags = MAP_ANONYMOUS | MAP_PRIVATE;
+    fd = -1;
+# else /* !HAVE_MAP_ANONYMOUS */
+    flags = MAP_FILE | MAP_PRIVATE;
+    if (fd == -1)
+       fd = open ("/dev/zero", O_RDONLY, 0666);
+    if (fd < 0) error (1, errno, "Failed to open /dev/zero for read.");
+# endif /* HAVE_MAP_ANONYMOUS */
+    ret = mmap (NULL, size, PROT_READ | PROT_WRITE, flags, fd, 0);
+    if (!ret)
+       error (1, errno, "mmap to /dev/zero failed.");
+    new_memnode (ret, size);
+#elif HAVE_POSIX_MEMALIGN
+    int status;
+    status = posix_memalign (&ret, getpagesize(), size);
+    if (status)
+       error (1, status, "posix_memalign failed.");
+#else /* !HAVE_MMAP && !HAVE_POSIX_MEMALIGN */
+    size_t pagesize = getpagesize ();
+    void *orig;
+    orig = xmalloc (size + pagesize - 1);
+   ret = (long) (orig + pagesize - 1) &~ (pagesize - 1);
+    new_memnode (ret, orig);
+#endif /* HAVE_MMAP && HAVE_POSIX_MEMALIGN */
+    return ret;
+}
+
+
+
+void
+pagealign_free (void *tofree)
+{
+#ifdef HAVE_MMAP
+    munmap (tofree, get_memnode (tofree));
+#elif HAVE_POSIX_MEMALIGN
+    free (tofree);
+#else
+    free (get_memnode (tofree));
+#endif
+}
Index: lib/pagealign_alloc.h
===================================================================
RCS file: lib/pagealign_alloc.h
diff -N lib/pagealign_alloc.h
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ lib/pagealign_alloc.h       3 Mar 2005 05:56:43 -0000
@@ -0,0 +1,26 @@
+/* Memory allocation aligned to system pages.
+
+   Copyright (C) 2005 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 2, 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+   USA.  */
+
+#ifndef _PAGEALIGN_ALLOC_H
+# define _PAGEALIGN_ALLOC_H
+
+void *pagealign_alloc (size_t);
+void pagealign_free (void *);
+
+#endif /* _PAGEALIGN_ALLOC_H */
Index: m4/mmap.m4
===================================================================
RCS file: m4/mmap.m4
diff -N m4/mmap.m4
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ m4/mmap.m4  3 Mar 2005 05:56:43 -0000
@@ -0,0 +1,56 @@
+# mmap.m4 serial 1
+dnl Copyright (C) 2005 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_FUNC_MMAP],
+[
+  dnl Work around a bug of AC_EGREP_CPP in autoconf-2.57.
+  AC_REQUIRE([AC_PROG_CPP])
+  AC_REQUIRE([AC_PROG_EGREP])
+
+  dnl Persuade glibc <sys/mman.h> to define MAP_ANONYMOUS.
+  AC_REQUIRE([AC_GNU_SOURCE])
+
+  # Check for mmap()
+  AC_FUNC_MMAP
+
+  # Try to allow MAP_ANONYMOUS.
+  gl_have_mmap_anonymous=no
+  if test $ac_cv_func_mmap_fixed_mapped = yes; then
+    AC_MSG_CHECKING([for MAP_ANONYMOUS])
+    AC_EGREP_CPP([I cant identify this map.], [
+#include <sys/mman.h>
+#ifdef MAP_ANONYMOUS
+    I cant identify this map.
+#endif
+],
+      [gl_have_mmap_anonymous=yes])
+    if test $gl_have_mmap_anonymous = no; then
+      AC_EGREP_HEADER([MAP_ANON], [
+#include <sys/mman.h>
+#ifdef MAP_ANON
+    I cant identify this map.
+#endif
+],
+        [AC_DEFINE(MAP_ANONYMOUS, MAP_ANON,
+          [Define to a substitute value for mmap()'s MAP_ANONYMOUS flag.])
+         gl_have_mmap_anonymous=yes])
+    fi
+    if test $gl_have_mmap_anonymous = yes; then
+      AC_MSG_RESULT([yes])
+      AC_DEFINE(HAVE_MAP_ANONYMOUS, 1,
+        [Define to 1 if mmap()'s MAP_ANONYMOUS flag is available after 
including
+         <config.h> and <sys/mman.h>.])
+    else
+      AC_MSG_RESULT([no])
+    fi
+
+    AH_VERBATIM([MAP_FILE],
+[/* Define MAP_FILE when it isn't otherwise.  */
+#ifndef MAP_FILE
+# define MAP_FILE 0
+#endif])
+  fi
+])
Index: m4/pagealign_alloc.m4
===================================================================
RCS file: m4/pagealign_alloc.m4
diff -N m4/pagealign_alloc.m4
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ m4/pagealign_alloc.m4       3 Mar 2005 05:56:43 -0000
@@ -0,0 +1,24 @@
+# pagealign_alloc.m4 serial 1
+dnl Copyright (C) 2005 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_PAGEALIGN_ALLOC],
+[
+  dnl Persuade glibc <sys/mman.h> to define MAP_ANONYMOUS.
+  AC_REQUIRE([AC_GNU_SOURCE])
+
+  AC_LIBSOURCE([pagealign_alloc.h])
+  AC_LIBOBJ([pagealign_alloc])
+  gl_PREREQ_PAGEALIGN_ALLOC
+])
+
+# Prerequisites of lib/pagealign_alloc.c.
+AC_DEFUN([gl_PREREQ_PAGEALIGN_ALLOC],
+[
+  AC_REQUIRE([gl_FUNC_MMAP])
+  AC_REQUIRE([gl_GETPAGESIZE])
+  AC_CHECK_FUNCS_ONCE([posix_memalign])
+  AC_CHECK_HEADERS_ONCE([fcntl.h unistd.h])
+])
Index: modules/pagealign_alloc
===================================================================
RCS file: modules/pagealign_alloc
diff -N modules/pagealign_alloc
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ modules/pagealign_alloc     3 Mar 2005 05:56:43 -0000
@@ -0,0 +1,27 @@
+Description:
+Memory allocation aligned on page boundries.
+
+Files:
+lib/pagealign_alloc.c
+lib/pagealign_alloc.h
+m4/mmap.m4
+m4/pagealign_alloc.m4
+
+Depends-on:
+error
+getpagesize
+xalloc
+
+configure.ac:
+gl_PAGEALIGN_ALLOC
+
+Makefile.am:
+
+Include:
+#include "pagealign_alloc.h"
+
+License:
+GPL
+
+Maintainer:
address@hidden

signature.asc
Description: OpenPGP digital signature