Message-ID: <3981452C.AB1C2C0@softhome.net>
Date: Fri, 28 Jul 2000 10:32:44 +0200
From: Laurynas Biveinis <lauras AT softhome DOT net>
X-Mailer: Mozilla 4.73 [en] (Win98; U)
X-Accept-Language: lt,en
MIME-Version: 1.0
To: Alexandre Oliva <aoliva AT redhat DOT com>
CC: law AT cygnus DOT com, gcc-patches AT gcc DOT gnu DOT org, djgpp-workers AT delorie DOT com
Subject: New patch (Was: Re: PATCH: enabling ggc-page with simple malloc())
References: <18258 DOT 964726841 AT upchuck> <39809554 DOT 400D6AEB AT softhome DOT net> <or66prussb DOT fsf AT guarana DOT lsd DOT ic DOT unicamp DOT br>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp-workers AT delorie DOT com

Alexandre Oliva wrote:
> Maybe you should post it here and let others comment on it? (assuming
> you haven't yet; I don't recall whether you'd Cc:ed the list)

OK, here we are. Note that this patch has been tested under DJGPP
only, it should be tested at least on two more platforms: with mmap() and
with valloc().

Also this patch does not include regenerated configure scripts, because
I can use only DJGPP port of Autoconf, which produces slightly different
scripts.

include/ChangeLog:
2000-06-18 Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
           Laurynas Biveinis <lauras AT softhome DOT net>
        
        * libiberty.h (xvalloc, xvfree, xvalloc_overhead): Declare.

libiberty/ChangeLog:
2000-06-18 Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
           Laurynas Biveinis <lauras AT softhome DOT net>
        
        * xvalloc.c: New file.
        * Makefile.in (CFILES): Added xvalloc.c.
        (REQUIRED_OFILES): Added xvalloc.o.
        (xvalloc.o): List dependencies.
        * configure.in: Auto-detect fcntl.h, sys/mman.h, MMAP_ANYWHERE and
        valloc.
        * configure, config.in: Rebuilt.

gcc/ChangeLog:
2000-06-18 Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
           Laurynas Biveinis <lauras AT softhome DOT net>
        
        * configure.in: No longer check for valloc.  Always use ggc-page.
        * configure, config.in: Rebuilt.
        * Makefile.in (ggc-page.o): Depend on libiberty.h
        * ggc-page.c (alloc_page): Use xvalloc from libiberty.
        (release_pages): Use xvfree.
        (struct globals): New member usable_pagesize.
        (init_ggc): Compute it with xvalloc_overhead from libiberty.
        (OBJECTS_PER_PAGE): Use it.
        (MISALIGNMENT): New macro.
        (clear_marks): Use it.
        (alloc_anon): Deleted.

Index: include/libiberty.h
===================================================================
RCS file: /cvs/gcc/egcs/include/libiberty.h,v
retrieving revision 1.12
diff -u -r1.12 libiberty.h
--- libiberty.h	2000/05/23 17:42:17	1.12
+++ libiberty.h	2000/07/28 08:10:57
@@ -161,6 +161,22 @@
 
 extern PTR xmemdup PARAMS ((const PTR, size_t, size_t)) ATTRIBUTE_MALLOC;
 
+/* Allocate a page-aligned memory block.  */
+
+extern char *xvalloc PARAMS ((size_t)) ATTRIBUTE_MALLOC;
+
+/* Release memory allocated by xvalloc.  */
+
+extern void xvfree PARAMS ((char *, size_t));
+
+/* Initialize xvalloc internal structures.  It's optional, but it's
+   best to call it before any memory allocation takes place.  It can
+   be called multiple times, returning how many bytes should be left
+   at the end of a page for memory-allocation data structures, so as
+   to avoid wasting every other page.  This value should be subtracted
+   from getpagesize() in the argument to xvalloc/xvfree. */
+extern unsigned xvalloc_overhead PARAMS ((void));
+
 /* hex character manipulation routines */
 
 #define _hex_array_size 256

Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.484
diff -u -r1.484 Makefile.in
--- Makefile.in	2000/07/24 17:43:42	1.484
+++ Makefile.in	2000/07/28 07:24:22
@@ -1211,7 +1211,7 @@
 	$(GGC_H) varray.h $(TIMEVAR_H)
 
 ggc-page.o: ggc-page.c $(CONFIG_H) $(RTL_H) $(TREE_H) flags.h toplev.h \
-	$(GGC_H) varray.h $(TIMEVAR_H)
+	$(GGC_H) varray.h $(TIMEVAR_H) $(srcdir)/../include/libiberty.h
 
 ggc-none.o: ggc-none.c $(CONFIG_H) $(RTL_H) $(GGC_H)
 
Index: gcc/config.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/config.in,v
retrieving revision 1.77
diff -u -r1.77 config.in
--- config.in	2000/07/17 09:23:16	1.77
+++ config.in	2000/07/28 07:24:24
@@ -213,9 +213,6 @@
 /* Define if you have the sysconf function.  */
 #undef HAVE_SYSCONF
 
-/* Define if you have the valloc function.  */
-#undef HAVE_VALLOC
-
 /* Define if you have the <argz.h> header file.  */
 #undef HAVE_ARGZ_H
 
Index: gcc/configure.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/configure.in,v
retrieving revision 1.398
diff -u -r1.398 configure.in
--- configure.in	2000/07/17 20:55:43	1.398
+++ configure.in	2000/07/28 07:25:17
@@ -474,7 +474,7 @@
 AC_CHECK_FUNCS(strtoul bsearch putenv popen bcopy bzero bcmp \
 	index rindex strchr strrchr kill getrlimit setrlimit atoll atoq \
 	sysconf isascii gettimeofday strsignal putc_unlocked fputc_unlocked \
-	fputs_unlocked getrusage valloc)
+	fputs_unlocked getrusage)
 
 AC_CHECK_TYPE(ssize_t, int)
 
@@ -510,7 +510,6 @@
   ;;
 esac
 AC_FUNC_VFORK
-AC_FUNC_MMAP_ANYWHERE
 AC_FUNC_MMAP_FILE
 
 # We will need to find libiberty.h and ansidecl.h
@@ -4242,7 +4241,7 @@
 		symbolic_link="cp"
 	fi
 	cc_set_by_configure="\`case '\$(CC)' in stage*) echo '\$(CC)' | sed -e 's|stage|../stage|g';; *) echo '\$(CC)';; esac\`"
-	quoted_cc_set_by_configure="\\\`case '\\\$(CC)' in stage*) echo '\\\$(CC)' | sed -e 's|stage|../stage|g';; *) echo '\\\$(CC)';; esac\\\`"
+        quoted_cc_set_by_configure="\\\`case '\$(CC)' in stage*) echo '\$(CC)' | sed -e 's|stage|../stage|g';; *) echo '\$(CC)';; esac\\\`"
 	stage_prefix_set_by_configure="\`case '\$(STAGE_PREFIX)' in stage*) echo '\$(STAGE_PREFIX)' | sed -e 's|stage|../stage|g';; *) echo '\$(STAGE_PREFIX)';; esac\`"
 fi
 rm -f symtest.tem
@@ -4765,13 +4764,7 @@
   *)
     AC_MSG_ERROR([$withval is an invalid option to --with-gc])
     ;;
-esac],
-[if test $ac_cv_func_mmap_anywhere = yes \
-    || test $ac_cv_func_valloc = yes; then
-  GGC=ggc-page
-else
-  GGC=ggc-simple
-fi])
+esac], [GGC=ggc-page])
 AC_SUBST(GGC)
 echo "Using $GGC for garbage collection."
 
Index: gcc/ggc-page.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ggc-page.c,v
retrieving revision 1.28
diff -u -r1.28 ggc-page.c
--- ggc-page.c	2000/07/23 16:25:06	1.28
+++ ggc-page.c	2000/07/28 07:25:47
@@ -29,18 +29,6 @@
 #include "ggc.h"
 #include "timevar.h"
 
-#ifdef HAVE_MMAP_ANYWHERE
-#include <sys/mman.h>
-#endif
-
-#ifndef MAP_FAILED
-#define MAP_FAILED -1
-#endif
-
-#if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
-#define MAP_ANONYMOUS MAP_ANON
-#endif
-
 /* Stategy: 
 
    This garbage-collecting allocator allocates objects on one of a set
@@ -215,6 +203,10 @@
   size_t pagesize;
   size_t lg_pagesize;
 
+  /* The system's page size minus any overheads of the page allocation
+     system.  */
+  size_t usable_pagesize;
+
   /* Bytes currently allocated.  */
   size_t allocated;
 
@@ -227,11 +219,6 @@
   /* The current depth in the context stack.  */
   unsigned short context_depth;
 
-  /* A file descriptor open to /dev/zero for reading.  */
-#if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
-  int dev_zero_fd;
-#endif
-
   /* A cache of free system pages.  */
   page_entry *free_pages;
 
@@ -247,7 +234,8 @@
 /* The number of objects per allocation page, for objects of size
    2^ORDER.  */
 #define OBJECTS_PER_PAGE(Order) \
-  ((Order) >= G.lg_pagesize ? 1 : G.pagesize / ((size_t)1 << (Order)))
+  ((Order) >= G.lg_pagesize ? 1 \
+   : ((G.usable_pagesize) / ((size_t)1 << (Order))))
 
 /* The size in bytes required to maintain a bitmap for the objects
    on a page-entry.  */
@@ -264,11 +252,14 @@
    test from triggering too often when the heap is small.  */
 #define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
 
+/* Test the misalignment of an address.  */
+#define MISALIGNMENT(Address) \
+  (((size_t)(Address)) & (G.pagesize - 1))
+
 
 static int ggc_allocated_p PARAMS ((const void *));
 static page_entry *lookup_page_table_entry PARAMS ((const void *));
 static void set_page_table_entry PARAMS ((void *, page_entry *));
-static char *alloc_anon PARAMS ((char *, size_t));
 static struct page_entry * alloc_page PARAMS ((unsigned));
 static void free_page PARAMS ((struct page_entry *));
 static void release_pages PARAMS ((void));
@@ -399,46 +390,6 @@
   fflush (stdout);
 }
 
-/* Allocate SIZE bytes of anonymous memory, preferably near PREF,
-   (if non-null).  */
-
-static inline char *
-alloc_anon (pref, size)
-     char *pref ATTRIBUTE_UNUSED;
-     size_t size;
-{
-  char *page;
-
-#ifdef HAVE_MMAP_ANYWHERE
-#ifdef MAP_ANONYMOUS
-  page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
-			MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
-#else
-  page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
-			MAP_PRIVATE, G.dev_zero_fd, 0);
-#endif
-  if (page == (char *) MAP_FAILED)
-    {
-      fputs ("Virtual memory exhausted!\n", stderr);
-      exit(1);
-    }
-#else
-#ifdef HAVE_VALLOC
-  page = (char *) valloc (size);
-  if (!page)
-    {
-      fputs ("Virtual memory exhausted!\n", stderr);
-      exit(1);
-    }
-#endif /* HAVE_VALLOC */
-#endif /* HAVE_MMAP_ANYWHERE */
-
-  /* Remember that we allocated this memory.  */
-  G.bytes_mapped += size;
-
-  return page;
-}
-
 /* Allocate a new page for allocating objects of size 2^ORDER,
    and return an entry for it.  The entry is not added to the
    appropriate page_table list.  */
@@ -484,7 +435,10 @@
   else
     {
       /* Actually allocate the memory.  */
-      page = alloc_anon (NULL, entry_size);
+      page = xvalloc (entry_size);
+
+      /* Remember that we actually allocated this memory.  */
+      G.bytes_mapped += entry_size;
     }
 
   if (entry == NULL)
@@ -534,54 +488,15 @@
 static void
 release_pages ()
 {
-#ifdef HAVE_MMAP_ANYWHERE
-  page_entry *p, *next;
-  char *start;
-  size_t len;
-
-  p = G.free_pages;
-  if (p == NULL)
-    return;
-
-  next = p->next;
-  start = p->page;
-  len = p->bytes;
-  free (p);
-  p = next;
-
-  while (p)
-    {
-      next = p->next;
-      /* Gather up adjacent pages so they are unmapped together.  */
-      if (p->page == start + len)
-	len += p->bytes;
-      else
-	{
-	  munmap (start, len);
-	  G.bytes_mapped -= len;
-	  start = p->page;
-	  len = p->bytes;
-	}
-      free (p);
-      p = next;
-    }
-
-  munmap (start, len);
-  G.bytes_mapped -= len;
-#else
-#ifdef HAVE_VALLOC
   page_entry *p, *next;
 
   for (p = G.free_pages; p ; p = next)
     {
       next = p->next;
-      free (p->page);
+      xvfree (p->page, p->bytes);
       G.bytes_mapped -= p->bytes;
       free (p);
     }
-#endif /* HAVE_VALLOC */
-#endif /* HAVE_MMAP_ANYWHERE */
-
   G.free_pages = NULL;
 }
 
@@ -783,7 +698,7 @@
   return 1 << pe->order;
 }
 
-/* Initialize the ggc-mmap allocator.  */
+/* Initialize the ggc-page allocator.  */
 
 void
 init_ggc ()
@@ -791,40 +706,16 @@
   G.pagesize = getpagesize();
   G.lg_pagesize = exact_log2 (G.pagesize);
 
-#if defined (HAVE_MMAP_ANYWHERE) && !defined(MAP_ANONYMOUS)
-  G.dev_zero_fd = open ("/dev/zero", O_RDONLY);
-  if (G.dev_zero_fd == -1)
-    abort ();
-#endif
+  G.usable_pagesize = G.pagesize - xvalloc_overhead();
 
 #if 0
-  G.debug_file = fopen ("ggc-mmap.debug", "w");
+  G.debug_file = fopen ("ggc-page.debug", "w");
 #else
   G.debug_file = stdout;
 #endif
 
   G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
 
-#ifdef HAVE_MMAP_ANYWHERE
-  /* StunOS has an amazing off-by-one error for the first mmap allocation
-     after fiddling with RLIMIT_STACK.  The result, as hard as it is to
-     believe, is an unaligned page allocation, which would cause us to
-     hork badly if we tried to use it.  */
-  {
-    char *p = alloc_anon (NULL, G.pagesize);
-    if ((size_t)p & (G.pagesize - 1))
-      {
-	/* How losing.  Discard this one and try another.  If we still
-	   can't get something useful, give up.  */
-
-	p = alloc_anon (NULL, G.pagesize);
-	if ((size_t)p & (G.pagesize - 1))
-	  abort ();
-      }
-    munmap (p, G.pagesize);
-  }
-#endif
-
   empty_string = ggc_alloc_string ("", 0);
   ggc_add_string_root (&empty_string, 1);
 }
@@ -931,7 +822,7 @@
 	{
 #ifdef ENABLE_CHECKING
 	  /* The data should be page-aligned.  */
-	  if ((size_t) p->page & (G.pagesize - 1))
+	  if (MISALIGNMENT(p->page))
 	    abort ();
 #endif
 
Index: libiberty/Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/Makefile.in,v
retrieving revision 1.52
diff -u -r1.52 Makefile.in
--- Makefile.in	2000/07/26 23:23:24	1.52
+++ Makefile.in	2000/07/28 07:27:01
@@ -135,7 +135,7 @@
 	strchr.c strdup.c strerror.c strncmp.c strrchr.c strsignal.c strstr.c \
 	strtod.c strtol.c strtoul.c tmpnam.c vasprintf.c vfork.c vfprintf.c   \
 	vprintf.c vsprintf.c waitpid.c xatexit.c xexit.c xmalloc.c	      \
-	xmemdup.c xstrdup.c xstrerror.c
+	xmemdup.c xstrdup.c xstrerror.c xvalloc.c
 
 # These are always included in the library.
 REQUIRED_OFILES = argv.o choose-temp.o concat.o cplus-dem.o cp-demangle.o \
@@ -143,7 +143,7 @@
 	getruntime.o hashtab.o hex.o floatformat.o objalloc.o obstack.o	  \
 	partition.o pexecute.o sort.o spaces.o splay-tree.o strerror.o	  \
 	strsignal.o xatexit.o xexit.o xmalloc.o xmemdup.o xstrdup.o	  \
-	xstrerror.o
+	xstrerror.o xvalloc.o
 
 $(TARGETLIB): $(REQUIRED_OFILES) $(EXTRA_OFILES) $(LIBOBJS) $(ALLOCA)
 	rm -f $(TARGETLIB)
@@ -296,5 +296,9 @@
 xmemdup.o: config.h $(INCDIR)/libiberty.h
 xstrdup.o: config.h $(INCDIR)/libiberty.h
 xstrerror.o: config.h $(INCDIR)/libiberty.h
+xvalloc.o: config.h $(INCDIR)/libiberty.h
 waitpid.o: config.h
 hashtab.o: config.h $(INCDIR)/libiberty.h $(INCDIR)/hashtab.h $(INCDIR)/ansidecl.h

Index: libiberty/configure.in
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/configure.in,v
retrieving revision 1.28
diff -u -r1.28 configure.in
--- configure.in	2000/07/23 19:18:32	1.28
+++ configure.in	2000/07/28 07:27:18
@@ -357,6 +357,89 @@
 
 libiberty_AC_FUNC_STRNCMP
 
+AC_DEFUN([AC_FUNC_MMAP_ANYWHERE],
+[AC_CHECK_HEADERS(unistd.h)
+AC_CHECK_FUNCS(getpagesize)
+AC_CACHE_CHECK(for working mmap from /dev/zero, ac_cv_func_mmap_anywhere,
+[AC_TRY_RUN([
+/* Test by Richard Henderson and Alexandre Oliva.
+   Check whether mmap from /dev/zero works. */
+#include <sys/types.h>
+#include <fcntl.h>
+#include <sys/mman.h>
+
+/* This mess was copied from the GNU getpagesize.h.  */
+#ifndef HAVE_GETPAGESIZE
+# ifdef HAVE_UNISTD_H
+#  include <unistd.h>
+# endif
+
+/* Assume that all systems that can run configure have sys/param.h.  */
+# ifndef HAVE_SYS_PARAM_H
+#  define HAVE_SYS_PARAM_H 1
+# endif
+
+# ifdef _SC_PAGESIZE
+#  define getpagesize() sysconf(_SC_PAGESIZE)
+# else /* no _SC_PAGESIZE */
+#  ifdef HAVE_SYS_PARAM_H
+#   include <sys/param.h>
+#   ifdef EXEC_PAGESIZE
+#    define getpagesize() EXEC_PAGESIZE
+#   else /* no EXEC_PAGESIZE */
+#    ifdef NBPG
+#     define getpagesize() NBPG * CLSIZE
+#     ifndef CLSIZE
+#      define CLSIZE 1
+#     endif /* no CLSIZE */
+#    else /* no NBPG */
+#     ifdef NBPC
+#      define getpagesize() NBPC
+#     else /* no NBPC */
+#      ifdef PAGESIZE
+#       define getpagesize() PAGESIZE
+#      endif /* PAGESIZE */
+#     endif /* no NBPC */
+#    endif /* no NBPG */
+#   endif /* no EXEC_PAGESIZE */
+#  else /* no HAVE_SYS_PARAM_H */
+#   define getpagesize() 8192  /* punt totally */
+#  endif /* no HAVE_SYS_PARAM_H */
+# endif /* no _SC_PAGESIZE */
+
+#endif /* no HAVE_GETPAGESIZE */
+
+int main()
+{
+  char *x;
+  int fd, pg;
+
+  fd = open("/dev/zero", O_RDWR);
+  if (fd < 0)
+    exit(1);
+
+  pg = getpagesize();
+  x = (char*)mmap(0, pg, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);
+  if (x == (char *) -1)
+    exit(2);
+
+  *(int *)x += 1;
+
+  if (munmap(x, pg) < 0)
+    exit(3);
+
+  exit(0);
+}], ac_cv_func_mmap_anywhere=yes, ac_cv_func_mmap_anywhere=no,
+ac_cv_func_mmap_anywhere=no)])
+if test $ac_cv_func_mmap_anywhere = yes; then
+  AC_DEFINE(HAVE_MMAP_ANYWHERE, 1,
+           [Define if mmap can get us zeroed pages from /dev/zero.])
+fi
+])
+
+AC_FUNC_MMAP_ANYWHERE
+AC_CHECK_FUNCS(valloc)
+
 # Install a library built with a cross compiler in $(tooldir) rather
 # than $(libdir).
 if test -z "${with_cross_host}"; then

Index: libiberty/xvalloc.c
===================================================================
RCS file: xvalloc.c
diff -N xvalloc.c
--- /dev/null	Fri Jul 28 10:22:03 2000
+++ xvalloc.c	Fri Jul 28 09:59:40 2000
@@ -0,0 +1,286 @@
+/* page-aligned memory allocation routines.
+   Copyright (C) 1999, 2000 Free Software Foundation
+
+This file is part of the libiberty library.
+Libiberty is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public
+License as published by the Free Software Foundation; either
+version 2 of the License, or (at your option) any later version.
+
+Libiberty 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
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with libiberty; see the file COPYING.LIB.  If not, write
+to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <libiberty.h>
+
+/* If defined to a positive number and malloc-based page allocation is
+   being used, counters are maintained for each successful allocation
+   using the mechanism that tries to convince malloc to return a
+   page-aligned address (aligned) and the fallback mechanism
+   (fallback).  Their values are printed every MALLOC_ACCOUNT
+   allocations. */
+#if 0
+# define MALLOC_ACCOUNT 16
+#endif
+
+#include <stdio.h>
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+
+#if HAVE_FCNTL_H
+# include <fcntl.h>
+#endif
+
+#if HAVE_SYS_MMAN_H
+# include <sys/mman.h>
+#endif
+
+#ifndef MAP_FAILED
+#define MAP_FAILED -1
+#endif
+
+#if !defined (MAP_ANONYMOUS) && defined (MAP_ANON)
+#define MAP_ANONYMOUS MAP_ANON
+#endif
+
+/* The system's page size.  */
+static size_t pagesize;
+
+#if defined (MAP_ANONYMOUS) || HAVE_MMAP_ANYWHERE
+
+# define offset 0
+# define overhead 0
+
+# ifndef MAP_ANONYMOUS
+static int dev_zero_fd;
+# endif
+
+#else
+
+#if HAVE_VALLOC
+static int use_valloc;
+#else
+# define use_valloc 0
+#endif
+
+/* This is usually 0, but AIX 4.1.5's malloc, for example, always
+   returns addresses p=16n+8.  This variable is supposed to be used as
+   an offset from the value returned by malloc to the beginning of the
+   page. */
+static size_t offset;
+
+/* This is how much space is used up by malloc internal structures.
+   It's typically 8 or 16 bytes. */
+static size_t overhead;
+#endif
+
+/* Test the misalignment of an address.  */
+#define MISALIGNMENT(Address) \
+  (((size_t)(Address)) & (pagesize - 1))
+
+#if ! defined (MAP_ANONYMOUS) && ! HAVE_MMAP_ANYWHERE
+static void
+xvmalloc_set_pointer (page, other)
+     char *page, *other;
+{
+  /* Set the pointer just before the page boundary to the beginning of
+     the block, so that it can be freed afterwards. */
+  ((char**)page)[-1] = other;
+}
+
+static char *
+xvmalloc_get_pointer (page)
+     char *page;
+{
+   return ((char**)page)[-1];
+}
+
+/* Return a page-aligned memory block with as many bytes as requested
+   in the page. */
+static char *
+xvmalloc_fallback (size)
+     size_t size;
+{
+  char *page, *other;
+
+  other = xmalloc(size + pagesize + offset - 1);
+  page = (char *)((size_t)(other + pagesize) & ~(pagesize - 1));
+
+  /* Mark its beginning. */
+  xvmalloc_set_pointer (page, other);
+
+  return page;
+}
+#endif /* ! defined (MAP_ANONYMOUS) && ! HAVE_MMAP_ANYWHERE */
+
+/* Return the number of bytes that should be subtracted from the
+   pagesize in order to avoid wasting every other page. */
+unsigned
+xvalloc_overhead ()
+{
+  if (pagesize)
+    return overhead + offset;
+
+  pagesize = getpagesize();
+
+#if ! defined (MAP_ANONYMOUS) && HAVE_MMAP_ANYWHERE
+  dev_zero_fd = open ("/dev/zero", O_RDONLY);
+  if (dev_zero_fd == -1)
+    abort ();
+#endif
+
+#if defined (MAP_ANONYMOUS) || HAVE_MMAP_ANYWHERE
+  /* StunOS has an amazing off-by-one error for the first mmap allocation
+     after fiddling with RLIMIT_STACK.  The result, as hard as it is to
+     believe, is an unaligned page allocation, which would cause us to
+     hork badly if we tried to use it.  */
+  {
+    char *p = xvalloc (pagesize);
+    if (MISALIGNMENT (p))
+      {
+       /* How losing.  Discard this one and try another.  If we still
+          can't get something useful, give up.  */
+
+       p = xvalloc (pagesize);
+       if (MISALIGNMENT (p))
+         abort ();
+      }
+    xvfree (p, pagesize);
+  }
+#else
+# if HAVE_VALLOC
+  {
+    char *to_free = 0, *p = 0, *q = 0;
+
+    /* If valloc imposes some space overhead, try to leave some bytes
+       at the end of the page, so as not to waste every other page. */
+    for (overhead = 0; overhead < pagesize;
+        overhead = overhead ? 2 * overhead : sizeof (char*))
+      {
+       p = valloc (pagesize - overhead);
+       if (! p)
+         {
+           overhead = pagesize;
+           break;
+         }
+       *(char**)p = to_free;
+
+       q = valloc (pagesize - overhead);
+       if (! q)
+         {
+           overhead = pagesize;
+           break;
+         }
+       *(char**)q = p;
+
+       to_free = q;
+       if (q - p <= pagesize)
+         break;
+      }
+
+    /* Set use_valloc so that xvfree() uses the appropriate free
+       mechanism. */
+    use_valloc = 1;
+    while (to_free)
+      {
+       p = to_free;
+       to_free = *(char**)p;
+
+       /* Note: the second argument is unused when the allocation
+          mechanism is xvalloc. */
+       xvfree (p, 0);
+      }
+
+    /* We'll only use valloc if we can arrange to not waste pages. */
+    use_valloc = (overhead < pagesize);
+  }
+# endif
+  /* If we're not using valloc, let's configure with plain malloc. */
+  overhead = offset = 0;
+#endif /* defined (MAP_ANONYMOUS) || HAVE_MMAP_ANYWHERE */
+
+  return overhead + offset;
+}
+
+/* Return a page-aligned block of memory of length size. */
+char*
+xvalloc(size)
+     size_t size;
+{
+  char *page;
+
+#if HAVE_MMAP_ANYWHERE || defined (MAP_ANONYMOUS)
+# ifdef MAP_ANONYMOUS
+  page = (char *) mmap (0, size, PROT_READ | PROT_WRITE,
+                       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+# else
+  page = (char *) mmap (0, size, PROT_READ | PROT_WRITE,
+                       MAP_PRIVATE, dev_zero_fd, 0);
+# endif
+  if (page == (char *) MAP_FAILED)
+    {
+      fputs ("Virtual memory exhausted!\n", stderr);
+      exit(1);
+    }
+#else
+
+# if HAVE_VALLOC
+  if (use_valloc)
+    {
+      page = (char *) valloc (size);
+      if (!page)
+       {
+         fputs ("Virtual memory exhausted!\n", stderr);
+         exit(1);
+       }
+    }
+# endif
+
+  if (! use_valloc)
+      page = xvmalloc_fallback (size);
+
+#endif /* defined (MAP_ANONYMOUS) || HAVE_MMAP_ANYWHERE */
+
+  return page;
+}
+
+/* Releases the memory block that has previously been returned by
+   xvalloc(size). */
+void
+xvfree(page, size)
+     char *page;
+     size_t size;
+{
+#if defined (MAP_ANONYMOUS) || HAVE_MMAP_ANYWHERE
+  munmap (page, size);
+#else
+# if HAVE_VALLOC
+  /* The docs say we shouldn't be using free() for valloc().  However,
+     no configure test that would fail for such use could be
+     implemented; it just worked.  If a failure situation is ever
+     found, a configure test that AC_DEFINEs HAVE_VALLOC to 0 should
+     be added. */
+  if (use_valloc)
+    free (page);
+# endif
+  if (! use_valloc)
+    free (xvmalloc_get_pointer (page));
+#endif
+}