Sender: oliva AT lsd DOT ic DOT unicamp DOT br
To: Laurynas Biveinis <lauras AT softhome DOT net>
Cc: DJGPP Workers <djgpp-workers AT delorie DOT com>
Subject: Re: Using ggc-page with plain malloc
References: <orhfgef6lo DOT fsf AT garnize DOT lsd DOT ic DOT unicamp DOT br>
	<3914FA82 DOT DFFBCF52 AT softhome DOT net>
From: Alexandre Oliva <oliva AT lsd DOT ic DOT unicamp DOT br>
Date: 28 May 2000 08:53:48 -0300
In-Reply-To: Laurynas Biveinis's message of "Sun, 07 May 2000 08:09:22 +0300"
Message-ID: <or4s7iao1f.fsf@saci.lsd.ic.unicamp.br>
Lines: 22
User-Agent: Gnus/5.0805 (Gnus v5.8.5) XEmacs/21.1 (Capitol Reef)
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Reply-To: djgpp-workers AT delorie DOT com

--=-=-=

On May  7, 2000, Laurynas Biveinis <lauras AT softhome DOT net> wrote:

> Alexandre Oliva wrote:

> While looking into gc-simple performance issues, I've tried your 
> program on DJGPP (i686-pc-msdosdjgpp) and it fails:

> Assertion failed at align-malloc.c line 60: p == r
> Exiting due to signal SIGABRT

Sorry about the late reply.  I see you were not using the latest
version of my patch (I'm not even sure I posted it :-).  Would you
like to give this one a try?


--=-=-=
Content-Type: text/x-patch
Content-Disposition: inline; filename=xvalloc.patch

Index: include/ChangeLog
from  Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
	
	* libiberty.h (xvalloc, xvfree, xvalloc_overhead): Declare.
	
Index: include/libiberty.h
===================================================================
RCS file: /cvs/gcc/egcs/include/libiberty.h,v
retrieving revision 1.11
diff -u -p -r1.11 libiberty.h
--- include/libiberty.h	1999/11/30 23:56:52	1.11
+++ include/libiberty.h	2000/01/24 18:59:21
@@ -154,6 +154,22 @@ extern char *xstrdup PARAMS ((const char
 
 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: libiberty/ChangeLog
from  Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
	
	* 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.
	
Index: libiberty/configure.in
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/configure.in,v
retrieving revision 1.23
diff -u -p -r1.23 configure.in
--- libiberty/configure.in	2000/01/04 16:09:57	1.23
+++ libiberty/configure.in	2000/01/24 18:59:25
@@ -109,7 +109,7 @@ AC_SUBST_FILE(host_makefile_frag)
 # It's OK to check for header files.  Although the compiler may not be
 # able to link anything, it had better be able to at least compile
 # something.
-AC_CHECK_HEADERS(sys/file.h sys/param.h stdlib.h string.h unistd.h strings.h sys/time.h sys/resource.h sys/stat.h)
+AC_CHECK_HEADERS(sys/file.h sys/param.h stdlib.h string.h unistd.h strings.h sys/time.h sys/resource.h sys/stat.h fcntl.h sys/mman.h)
 AC_HEADER_SYS_WAIT
 
 # This is the list of functions which libiberty will provide if they
@@ -351,6 +351,89 @@ EOF
   done
   AC_CHECK_FUNCS($checkfuncs)
 fi
+
+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).
Index: libiberty/Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/libiberty/Makefile.in,v
retrieving revision 1.36
diff -u -p -r1.36 Makefile.in
--- libiberty/Makefile.in	2000/01/04 16:11:32	1.36
+++ libiberty/Makefile.in	2000/01/24 18:59:25
@@ -1,6 +1,6 @@
 #
 # Makefile
-#   Copyright (C) 1990, 91 - 99, 2000
+#   Copyright (C) 1990-2000
 #   Free Software Foundation
 #
 # This file is part of the libiberty library.
@@ -132,14 +132,15 @@ CFILES = asprintf.c alloca.c argv.c atex
 	spaces.c splay-tree.c strcasecmp.c strncasecmp.c strchr.c strdup.c \
 	strerror.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
+	waitpid.c xatexit.c xexit.c xmalloc.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 \
   fdmatch.o fnmatch.o getopt.o getopt1.o getpwd.o getruntime.o hashtab.o \
   hex.o floatformat.o objalloc.o obstack.o pexecute.o spaces.o \
   splay-tree.o strerror.o strsignal.o xatexit.o xexit.o xmalloc.o \
-  xmemdup.o xstrdup.o xstrerror.o
+  xmemdup.o xstrdup.o xstrerror.o xvalloc.o
 
 $(TARGETLIB): $(REQUIRED_OFILES) $(EXTRA_OFILES) $(LIBOBJS) $(ALLOCA)
 	rm -f $(TARGETLIB)
@@ -283,4 +284,5 @@ xmalloc.o: $(INCDIR)/libiberty.h
 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
 hashtab.o: config.h $(INCDIR)/libiberty.h $(INCDIR)/hashtab.h $(INCDIR)/ansidecl.h
Index: libiberty/xvalloc.c
===================================================================
RCS file: xvalloc.c
diff -N xvalloc.c
--- libiberty/xvalloc.c	Tue May  5 13:32:27 1998
+++ libiberty/xvalloc.c	Mon Jan 24 10:59:26 2000
@@ -0,0 +1,594 @@
+/* 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
+
+static int always_aligned;
+
+/* 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. */
+  if (! always_aligned && offset)
+    ((char**)page)[-1] = other;
+}
+
+static char *
+xvmalloc_get_pointer (page)
+     char *page;
+{
+  if (always_aligned || ! offset)
+    return page;
+  else
+    return ((char**)page)[-1];
+}
+
+static char *
+xvmalloc_align (size)
+     size_t size;
+{
+#ifndef INITIAL_MALLOC_FAILURES
+# define INITIAL_MALLOC_FAILURES 4
+#endif
+  char *page, *other, *to_free = 0, *prev_page = 0;
+  size_t misalignment, newsize;
+  /* If we don't make progress with a few attempts to get an
+	 aligned page, we'll revert to a fallback mechanism.  A
+	 failure is accounted for when we allocate a block smaller
+	 than the requested size, so as to try to get the heap
+	 aligned, but the block ends up being placed after the page we
+	 had allocated before. */
+  static size_t max_failures = INITIAL_MALLOC_FAILURES;
+  size_t failures_remaining = max_failures;
+
+  size += offset;
+
+  /* Try to allocate a whole pages, so as to try to leave the memory
+     properly aligned for the next allocation. */
+  misalignment = MISALIGNMENT (size + overhead);
+  if (misalignment)
+    size += pagesize - misalignment;
+
+  while ((page = 0, failures_remaining != 0)
+	 && ((page = xmalloc (size)),
+	     (misalignment = MISALIGNMENT (page+offset)),
+	     misalignment != 0))
+    {
+      if (always_aligned == -1 && offset != misalignment)
+	always_aligned = 0;
+      
+      /* Calculate the size the allocated block should be so that it
+	 ends just before a page boundary, i.e., the next allocation
+	 would get us a page-aligned block. */
+      newsize = pagesize - misalignment - overhead;
+      if (pagesize <= misalignment + overhead)
+	newsize += pagesize;
+
+      /* If we get the same page twice, or some page before it, keep
+	 it allocated until the end, so that it doesn't keep pestering
+	 us within this loop.  Note that the case with page ==
+	 prev_page, that is indeed a situation of no progress, is not
+	 accounted as a failure here, because the only way for it to
+	 show up is after an accounted failure.  In any other case,
+	 prev_page would have been set to NULL. */
+      if (page <= prev_page)
+	{
+	  /* If we get exactly the same page, it may be worth to try
+	     to align the block just after it, and hope it won't be
+	     properly recycled.  This is quite likely, because, having
+	     gotten here, we'd have already tried to resize the
+	     previous block and it didn't work.  So let's try to
+	     resize the next block.  This helps on IRIX 5.2. */
+	  if (page == prev_page)
+	    {
+	      other = xmalloc (newsize);
+	      free (other);
+	    }
+	  
+	  /* Prepare to add the page to to_free. */
+	  other = page;
+	  newsize = size;
+	}
+      else
+	{
+	  free (page);
+
+	  /* If we got an exact one-page offset from the previous
+	     allocation, something has gone wrong with our attempted
+	     adjustment.  Shake it a little bit.  It helps at least on
+	     Solaris. */
+	  if (to_free && page == to_free + pagesize)
+	    {
+	      other = xmalloc (size + newsize + pagesize);
+	      free (other);
+	    }
+
+	  /* Try to resize the just-allocated-and-freed unaligned page
+	     block so that the next allocation will hopefully fall in
+	     a page boundary. */
+	  other = xmalloc (newsize);
+
+	  /* If it appears before that block, it's fine to get the
+	     same block again.  Eventually, we'll have allocated all
+	     newsize blocks before page. */ 
+	  if (other <= page)
+	    {
+	      prev_page = 0;
+
+	      if (to_free && page == to_free + pagesize)
+		--failures_remaining;
+	    }
+	  else
+	    {
+	      /* If we get a block after page, it won't help, so just
+		 release it immediately, and arrange for the unaligned
+		 page to be allocated next time we get to it. */
+	      free (other);
+	      other = 0;
+	      prev_page = page;
+
+	      /* Count this as one failure.  */
+	      --failures_remaining;
+	    }
+	}
+
+      /* Add OTHER to the linked list of blocks to be freed when we
+	 get an aligned page. */
+      if (other)
+	{
+	  *(char**)other = to_free;
+	  to_free = other;
+	}
+    }
+
+  if (always_aligned == -1 && MISALIGNMENT (page))
+    always_aligned = 0;
+      
+  /* Release all blocks held during this allocation attempt. */
+  while (to_free)
+    {
+      other = *(char**)to_free;
+      free (to_free);
+      to_free = other;
+    }
+
+  /* If we got an aligned page, skip the offset, which will get us
+	 to the page-aligned address. */
+  if (failures_remaining != 0)
+    {
+      /* There are some unaligned page-sized blocks in the heap that
+	 are making it harder to find aligned pages.  Remember to try
+	 harder next time. */
+      if (failures_remaining < INITIAL_MALLOC_FAILURES)
+	max_failures += INITIAL_MALLOC_FAILURES - failures_remaining;
+	  
+      other = page;
+      page += offset;
+
+      xvmalloc_set_pointer (page, other);
+
+      return page;
+    }
+  else
+    return 0;
+}
+
+/* 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;
+  size_t minsize = pagesize / 2, misalignment;
+
+  /* We must not get here, since offset is zero. */
+  if (always_aligned)
+    abort ();
+
+  /* Binary search from pagesize/2 to pagesize.  The reasoning for the
+     test misalignment <= minsize when misalignment is non-zero is
+     a simplification of the following inequality: 
+  
+     page + (size + offset + pagesize - minsize)
+     >= (page + offset + (pagesize - misalignment)) + size
+
+     i.e., the block starting at page must be large enough for the
+     offset and padding up to a page boundary, plus the requested
+     number of bytes. */
+  for (minsize = pagesize / 2;
+       ((page = xmalloc (size + offset + pagesize - minsize)),
+	(misalignment = MISALIGNMENT (page + offset)),
+	misalignment && misalignment <= minsize);
+       minsize /= 2)
+      free (page);
+
+  /* Align the page. */
+  other = page;
+  if (misalignment)
+    page += pagesize - misalignment;
+  page += offset;
+
+  /* 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. */
+  if (! use_valloc)
+    {
+      size_t size;
+      char *to_free = 0, *p = 0, *q = 0;
+    
+      /* Find out the memory overhead of a page-sized malloc. */
+      p = xmalloc (pagesize);
+      *(char**)p = to_free;
+      q = xmalloc (pagesize);
+      *(char**)q = p;
+      to_free = q;
+      overhead = q - p - pagesize;
+
+      /* If the overhead is a whole page, odds are that malloc()ing a
+	 large block will always return a page-aligned address.  So we
+	 do just like in the case of valloc. */
+      if (overhead == pagesize)
+	for (overhead = sizeof (char*); overhead < pagesize; overhead *= 2)
+	  {
+	    p = xmalloc (pagesize - overhead);
+	    *(char**)p = to_free;
+
+	    q = xmalloc (pagesize - overhead);
+	    *(char**)q = p;
+
+	    to_free = q;
+	    if (q - p <= pagesize)
+	      break;
+	  }
+
+      while (to_free)
+	{
+	  p = to_free;
+	  to_free = *(char**)p;
+	  free (p);
+	}
+
+      /* Let's assume malloc is always page-aligned.  If it is not,
+	 xvmalloc_align will tell us so, by zeroing always_aligned. */
+      always_aligned = -1;
+      size = pagesize - overhead;
+
+      /* Try to get a page-aligned block. */
+      p = xvmalloc_align (size);
+
+      /* Got it, good.  It seems that we can control malloc reasonably
+	 well, at least to get page-aligned addresses. */
+      if (p)
+	xvfree (p, size);
+      else
+	{
+	  /* Uh oh, we couldn't get page-aligned data.  One
+	     possibility is that malloc() will always return data with
+	     some positive offset.  AIX 4.1's malloc, for example,
+	     returns addresses of the form 16n+8.  Let's try to handle
+	     this case. */
+	  offset = overhead /= 2;
+	  p = xvmalloc_align (size);
+
+	  /* Good, it worked.  We guessed right! */
+	  if (p)
+	    xvfree (p, size);
+	  else
+	    {
+	      /* Let's be conservative and revert to the original
+		 values. */
+	      offset = 0;
+	      overhead *= 2;
+	    }
+	  
+	}
+
+      /* We'll have to store a pointer to the beginning of the
+	 malloc()ed block right before the page boundary.  Reserve
+	 space for it. */
+      if (offset < sizeof (char*))
+	offset = sizeof (char*);
+      /* Assume offset has at least the same alignment requirements of
+	 the malloc overhead.  We may be wasting some bytes here, but
+	 it shouldn't hurt too much. */
+      if (offset < overhead)
+	offset = overhead;
+
+      /* Now that we have set offset and overhead, try to obtain a
+	 page-aligned address preceded by offset usable bytes. */
+      p = xvmalloc_align (size);
+      /* If it works, we seem to be able to control malloc pretty
+	 well.  Moreover, since offset is non-zero, we can assume
+	 always_aligned is not true. */
+      if (p)
+	xvfree (p, size);
+      /* Otherwise, disregard offset and set always_aligned to 1
+	 forever. */
+      else if (always_aligned)
+	{
+	  offset = 0;
+	  always_aligned = 1;
+	}
+    }
+#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)
+    {
+# if MALLOC_ACCOUNT
+      /* Account number of pages allocated with each mechanism.  */
+      static size_t aligned, fallback;
+# endif
+
+      page = xvmalloc_align (size);
+
+      if (page)
+	{
+# if MALLOC_ACCOUNT
+	  ++aligned;
+# endif
+	}
+      else
+	{
+	  page = xvmalloc_fallback (size);
+
+# if MALLOC_ACCOUNT
+	  ++fallback;
+# endif
+	}
+
+# if MALLOC_ACCOUNT
+      if ((aligned + fallback) % MALLOC_ACCOUNT == 0)
+	{
+	  printf("aligned: %lu, fallback: %lu\n",
+		 (unsigned long)aligned, (unsigned long)fallback);
+	}
+# endif
+    }
+#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
+}
Index: gcc/ChangeLog
from  Alexandre Oliva  <oliva AT lsd DOT ic DOT unicamp DOT br>
	
	* aclocal.m4 (AC_FUNC_MMAP_ANYWHERE): Moved to libiberty.
	* 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: gcc/aclocal.m4
===================================================================
RCS file: /cvs/gcc/egcs/gcc/aclocal.m4,v
retrieving revision 1.21
diff -u -p -r1.21 aclocal.m4
--- gcc/aclocal.m4	2000/01/16 18:49:31	1.21
+++ gcc/aclocal.m4	2000/01/24 18:59:42
@@ -680,85 +680,3 @@ else
 fi
 AC_SUBST($1)dnl
 ])
-
-# Check whether mmap can map an arbitrary page from /dev/zero, without
-# MAP_FIXED.
-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
-])
Index: gcc/configure.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/configure.in,v
retrieving revision 1.326
diff -u -p -r1.326 configure.in
--- gcc/configure.in	2000/01/24 04:02:40	1.326
+++ gcc/configure.in	2000/01/24 18:59:43
@@ -388,7 +388,7 @@ fi
 AC_CHECK_FUNCS(strtoul bsearch strerror 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)
 
 # Make sure wchar_t is available
 #AC_CHECK_TYPE(wchar_t, unsigned int)
@@ -405,7 +405,6 @@ case "${host}" in
   ;;
 esac
 AC_FUNC_VFORK
-AC_FUNC_MMAP_ANYWHERE
 
 GCC_NEED_DECLARATIONS(bcopy bzero bcmp \
 	index rindex getenv atol sbrk abort atof strerror getcwd getwd \
@@ -4577,13 +4576,7 @@ AC_ARG_WITH(gc,
   *)
     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/Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.369
diff -u -p -r1.369 Makefile.in
--- gcc/Makefile.in	2000/01/20 18:25:12	1.369
+++ gcc/Makefile.in	2000/01/24 18:59:45
@@ -1449,7 +1449,7 @@ ggc-simple.o: ggc-simple.c $(CONFIG_H) $
 	ggc.h varray.h
 
 ggc-page.o: ggc-page.c $(CONFIG_H) $(RTL_H) $(TREE_H) flags.h \
-	ggc.h varray.h
+	ggc.h varray.h $(srcdir)/../include/libiberty.h
 
 ggc-none.o: ggc-none.c $(CONFIG_H) $(RTL_H) ggc.h
 
Index: gcc/ggc-page.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ggc-page.c,v
retrieving revision 1.22
diff -u -p -r1.22 ggc-page.c
--- gcc/ggc-page.c	2000/01/23 20:42:53	1.22
+++ gcc/ggc-page.c	2000/01/24 18:59:45
@@ -27,18 +27,6 @@
 #include "flags.h"
 #include "ggc.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
@@ -92,6 +80,7 @@
      3: Object allocations as well.
      4: Object marks as well.   */
 #define GGC_DEBUG_LEVEL (0)
+
 
 #ifndef HOST_BITS_PER_PTR
 #define HOST_BITS_PER_PTR  HOST_BITS_PER_LONG
@@ -216,6 +205,10 @@ static struct globals
   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;
 
@@ -228,11 +221,6 @@ static struct globals
   /* 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;
 
@@ -248,7 +236,8 @@ static struct globals
 /* 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.  */
@@ -265,11 +254,14 @@ static struct globals
    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));
@@ -398,46 +390,6 @@ debug_print_page_list (order)
   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.  */
@@ -483,7 +435,10 @@ alloc_page (order)
   else
     {
       /* Actually allocate the memory.  */
-      page = alloc_anon (NULL, entry_size);
+      page = xvalloc (entry_size);
+
+      /* Remember that we allocated this memory.  */
+      G.bytes_mapped += entry_size;
     }
 
   if (entry == NULL)
@@ -533,6 +488,17 @@ free_page (entry)
 static void
 release_pages ()
 {
+  page_entry *p, *next;
+
+  for (p = G.free_pages; p ; p = next)
+    {
+      next = p->next;
+      xvfree (p->page, p->bytes);
+      G.bytes_mapped -= p->bytes;
+      free (p);
+    }
+
+#if 0 /* no longer used since xvalloc was moved to libiberty */
 #ifdef HAVE_MMAP_ANYWHERE
   page_entry *p, *next;
   char *start;
@@ -578,8 +544,22 @@ release_pages ()
       G.bytes_mapped -= p->bytes;
       free (p);
     }
+#else /* xmalloc */
+  page_entry *p, *next;
+
+  for (p = G.free_pages; p ; p = next)
+    {
+      next = p->next;
+      /* Since xmalloc won't always give us page-aligned addresses, we
+	 store a pointer to the beginning of the block just before the
+	 page boundary. */
+      free (((char**)p->page)[-1]);
+      G.bytes_mapped -= p->bytes;
+      free (p);
+    }
 #endif /* HAVE_VALLOC */
 #endif /* HAVE_MMAP_ANYWHERE */
+#endif /* 0 */
 
   G.free_pages = NULL;
 }
@@ -786,48 +766,23 @@ ggc_get_size (p)
   return 1 << pe->order;
 }
 
-/* Initialize the ggc-mmap allocator.  */
+/* Initialize the ggc-page allocator.  */
 
 void
 init_ggc ()
 {
   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);
 }
@@ -934,7 +889,7 @@ clear_marks ()
 	{
 #ifdef ENABLE_CHECKING
 	  /* The data should be page-aligned.  */
-	  if ((size_t) p->page & (G.pagesize - 1))
+	  if (MISALIGNMENT (p->page))
 	    abort ();
 #endif
 

--=-=-=
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable


--=20
Alexandre Oliva    Enjoy Guaran=E1, see http://www.ic.unicamp.br/~oliva/
Cygnus Solutions, a Red Hat company        aoliva@{redhat, cygnus}.com
Free Software Developer and Evangelist    CS PhD student at IC-Unicamp
oliva@{lsd.ic.unicamp.br, gnu.org}   Write to mailing lists, not to me

--=-=-=--