Using ggc-page with plain malloc

[Alexandre Oliva <oliva at lsd dot ic dot unicamp dot br>]

Hi,

I've been trying to arrange for ggc-page to work upon plain malloc.
All it needs is some way to ask for a memory area aligned at a page
boundary.  It's a bit tricky, because of wide variations among the
malloc() implementations, but I believe it can made to work well
unless someone finds some platform that breaks the following program
in a way that is too hard to fix.

I've already managed for it to work on GNU/Linux/x86, /alpha and
/sparc (all of them are running RedHat 6.1), Solaris 7/sparc and /x86,
Solaris 2.[56]/sparc, DU4.0/alpha, IRIX 5.2/mips, AIX 4.1.5/powerpc
and HP-UX 10.20/pa.  I'd appreciate if you could try the program below
on other platforms, and report successes/failures you may encounter.

There are two kinds of possible failures: assertion failures during
setup() or infinite recursion during alloc().  The former is the most
important kind of failure to detect; the second can be easily worked
around by imposing a limit on recursive calls and falling back to a
fail-safe yet wasteful alternative.

Another relevant issue: AIX 4.1.5's malloc will *never* return a
page-boundary-aligned address; it always returns addresses of the form
16k+8.  For those that have worked in the implementation of ggc-page:
would it be easier to adapt ggc-page to take this pre-overhead into
account, or would it be better to arrange for the malloc header to
occupy the end of the previous page, and waste the 8 bytes between the
malloc header (at page-boundary - 16) and the beginning of the page?

/* Copyright 2000 Alexandre Oliva <oliva@lsd.ic.unicamp.br>
 *
 * This file 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 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>
#include <assert.h>
#include <stdio.h>

/* This program tests whether malloc can be used to obtain aligned
   memory areas. */

size_t pagesize;

/* This is how much space is used up by malloc internal structures.
   It's typically 8 or 16 bytes. */
size_t overhead;

/* This is usually 0, but AIX 4.1.5's malloc, for example, always
   returns addresses p such that (p%16)==8.  This variable is supposed
   to be used as an offset from the beginning of the page, and it is
   always identical to overhead. */
size_t pre_overhead;

/* This variable indicates whether malloc won't merge consecutive free
   blocks.  The net effect is that we can't resize a block and expect
   the following malloc to return us the address just after the
   resized block. */
size_t no_resize;

/* Test some details of the implementation of malloc.  */
int setup() {
  size_t diff;
  char *p, *q, *r;
  
  pagesize = getpagesize();
  
  p = malloc (pagesize);
  q = malloc (pagesize);
  overhead = q - p - pagesize;

  free (q);
  free (p);
  diff = ((size_t)(p)) & (pagesize-1);
  r = malloc (pagesize - diff - overhead);
  assert (p == r);

  r = malloc (pagesize - overhead);
  if (r == q) {
    /* malloc doesn't merge free blocks, we'll have to waste unaligned
       allocs :-( */
    no_resize = 1;
    diff = ((size_t)(q)) & (pagesize-1);
    p = malloc (pagesize - diff - overhead);
    q = malloc (pagesize - overhead);
  } else if ((((size_t)(r + overhead / 2)) & (pagesize-1)) == 0) {
    /* AIX's overhead must be in the beginning of the page.  */
    pre_overhead = overhead /= 2;
    free (r);
    free (p);
    r = malloc (pagesize - diff - overhead);
    assert (p == r);
    q = malloc (pagesize - overhead);
  } else
    q = r;
    
  assert ((((size_t)(q - pre_overhead)) & (pagesize-1)) == 0);
  free (q);
  free (p);

  return pagesize - overhead;
}

/* Return a memory region at least as large as size, starting at a
   page boundary plus pre_overhead. */
char *alloc(size_t size) {
  char *p, *q;
  size_t diff;

  if (no_resize && ((size + overhead) & (pagesize-1)) != 0) {
    size += pagesize - ((size + overhead) & (pagesize-1));
  }
  
  p = malloc (size);
  diff = ((size_t)(p - pre_overhead)) & (pagesize-1);

  if (diff == 0) {
    return p;
  }

  if (no_resize) {
    /* We'll have to waste this page :-( */
    diff = ((size_t)(p + pagesize + overhead - pre_overhead)) & (pagesize-1);
  } else {
    free (p);
  }

  p = malloc (pagesize - diff - overhead);
  q = alloc (size);
  free (p);

  return q;
}

/* A verbose version of alloc.  */
char *myalloc(size_t size) {
  char *p = alloc (size);
  printf ("%lx @ %lx\n", size, (long)p);
  return p;
}

int main() {
  size_t size = setup();
  int i = 8;
  
  do {
    /* Allocate blocks of various sizes.  */
    if (i % 2)
      myalloc (size / 2);
    myalloc (size);
    if (i < 4)
      myalloc (i * pagesize + size);
  } while (i--);

  return 0;
}

-- 
Alexandre Oliva http://www.ic.unicamp.br/~oliva IC-Unicamp, Bra[sz]il
oliva@{lsd.ic.unicamp.br,guarana.{org,com}} aoliva@{acm,computer}.org
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
** I may forward mail about projects to mailing lists; please use them