xalloc.c

#define FATALERRORS 1
/*
Copyright (C) 1995 Pascal Haible.  All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
PASCAL HAIBLE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Except as contained in this notice, the name of Pascal Haible shall
not be used in advertising or otherwise to promote the sale, use or other
dealings in this Software without prior written authorization from
Pascal Haible.
*/

/* $XFree86: xc/programs/Xserver/os/xalloc.c,v 3.35tsi Exp $ */

/* Only used if INTERNAL_MALLOC is defined
 * - otherwise xalloc() in utils.c is used
 */
#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif

#ifdef INTERNAL_MALLOC

#include <stdlib.h>	/* for malloc() etc. */

#include <X11/Xos.h>
#include "misc.h"
#include <X11/X.h>

#ifdef XALLOC_LOG
#include <stdio.h>
#endif

extern Bool Must_have_memory;

/*
 ***** New malloc approach for the X server *****
 * Pascal Haible 1995
 *
 * Some statistics about memory allocation of the X server
 * The test session included several clients of different size, including
 * xv, emacs and xpaint with a new canvas of 3000x2000, zoom 5.
 * All clients were running together.
 * A protocolling version of Xalloc recorded 318917 allocating actions
 * (191573 Xalloc, 85942 XNFalloc, 41438 Xrealloc, 279727 Xfree).
 * Results grouped by size, excluding the next lower size
 * (i.e. size=32 means 16<size<=32):
 *
 *    size   nr of alloc   max nr of blocks allocated together
 *       8	1114		287
 *      16	17341		4104
 *      32	147352		2068
 *      64	59053		2518
 *     128	46882		1230
 *     256	20544		1217
 *     512	6808		117
 *    1024	8254		171
 *    2048	4841		287
 *    4096	2429		84
 *    8192	3364		85
 *   16384	573		22
 *   32768	49		7
 *   65536	45		5
 *  131072	48		2
 *  262144	209		2
 *  524288	7		4
 * 1048576	2		1
 * 8388608	2		2
 *
 * The most used sizes:
 * count size
 * 24	136267
 * 40	37055
 * 72	17278
 * 56	13504
 * 80	9372
 * 16	8966
 * 32	8411
 * 136	8399
 * 104	7690
 * 12	7630
 * 120	5512
 * 88	4634
 * 152	3062
 * 52	2881
 * 48	2736
 * 156	1569
 * 168	1487
 * 160	1483
 * 28	1446
 * 1608	1379
 * 184	1305
 * 552	1270
 * 64	934
 * 320	891
 * 8	754
 *
 * Conclusions: more than the half of all allocations are <= 32 bytes.
 * But of these about 150,000 blocks, only a maximum of about 6,000 are
 * allocated together (including memory leaks..).
 * On the other side, only 935 of the 191573 or 0.5% were larger than 8kB
 * (362 or 0.2% larger than 16k).
 *
 * What makes the server really grow is the fragmentation of the heap,
 * and the fact that it can't shrink.
 * To cure this, we do the following:
 * - large blocks (>=11k) are mmapped on xalloc, and unmapped on xfree,
 *   so we don't need any free lists etc.
 *   As this needs 2 system calls, we only do this for the quite
 *   infrequent large (>=11k) blocks.
 * - instead of reinventing the wheel, we use system malloc for medium
 *   sized blocks (>256, <11k).
 * - for small blocks (<=256) we use an other approach:
 *   As we need many small blocks, and most ones for a short time,
 *   we don't go through the system malloc:
 *   for each fixed sizes a seperate list of free blocks is kept.
 *   to KISS (Keep it Small and Simple), we don't free them
 *   (not freeing a block of 32 bytes won't be worse than having fragmented
 *   a larger area on allocation).
 *   This way, we (almost) allways have a fitting free block right at hand,
 *   and don't have to walk any lists.
 */

/*
 * structure layout of a allocated block
 * unsigned long	size:
 *				rounded up netto size for small and medium blocks
 *				brutto size == mmap'ed area for large blocks
 * unsigned long	DEBUG ? MAGIC : unused
 * ....			data
 * ( unsigned long	MAGIC2 ) only if SIZE_TAIL defined
 *
 */
 
/* use otherwise unused long in the header to store a magic */
/* shouldn't this be removed for production release ? */
#define XALLOC_DEBUG

#ifdef XALLOC_DEBUG
/* Xfree fills the memory with a certain pattern (currently 0xF0) */
/* this should really be removed for production release! */
#define XFREE_ERASES
#endif

/* this must be a multiple of SIZE_STEPS below */
#define MAX_SMALL 264		/* quite many blocks of 264 */

#define MIN_LARGE (11*1024)
/* worst case is 25% loss with a page size of 4k */

/* SIZE_STEPS defines the granularity of size of small blocks -
 * this makes blocks align to that, too! */
#define SIZE_STEPS		(sizeof(double))
#define SIZE_HEADER		(2*sizeof(long)) /* = sizeof(double) for 32bit */
#ifdef XALLOC_DEBUG
#if defined(__sparc__)
#define SIZE_TAIL		(2*sizeof(long)) /* = sizeof(double) for 32bit */
#else
#define SIZE_TAIL		(sizeof(long))
#endif
#endif

#undef TAIL_SIZE
#ifdef SIZE_TAIL
#define TAIL_SIZE		SIZE_TAIL
#else
#define TAIL_SIZE		0
#endif

#if defined (_LP64) || \
    defined(__alpha__) || defined(__alpha) || \
    defined(__ia64__) || defined(ia64) || \
    defined(__sparc64__) || \
    defined(__s390x__) || \
    defined(__amd64__) || defined(amd64) || \
    defined(__powerpc64__) || \
    (defined(sgi) && _MIPS_SZLONG == 64))
#define MAGIC			0x1404196414071968
#define MAGIC_FREE              0x1506196615061966
#define MAGIC2			0x2515207525182079
#else
#define MAGIC			0x14071968
#define MAGIC_FREE              0x15061966
#define MAGIC2			0x25182079
#endif

/* To get some statistics about memory allocation */

#ifdef XALLOC_LOG
#define XALLOC_LOG_FILE "/tmp/Xalloc.log"	/* unsecure... */
#define LOG_BODY(_body)					\
		{ FILE *f;				\
		  f = fopen(XALLOC_LOG_FILE, "a");	\
		  if (NULL!=f) {			\
			_body;				\
			fclose(f);			\
		  }					\
		}
#if defined(linux) && defined(i386)
#define LOG_ALLOC(_fun, _size, _ret)						\
	{	unsigned long *from;						\
		__asm__("movl %%ebp,%0" : /*OUT*/ "=r" (from) : /*IN*/ );	\
		LOG_BODY(fprintf(f, "%s\t%i\t%p\t[%lu]\n", _fun, _size, _ret, *(from+1))) \
	}
#else
#define LOG_ALLOC(_fun, _size, _ret)				\
	LOG_BODY(fprintf(f, "%s\t%i\t%p\n", _fun, _size, _ret))
#endif
#define LOG_REALLOC(_fun, _ptr, _size, _ret)			\
	LOG_BODY(fprintf(f, "%s\t%p\t%i\t%p\n", _fun, _ptr, _size, _ret))
#define LOG_FREE(_fun, _ptr)					\
	LOG_BODY(fprintf(f, "%s\t%p\n", _fun, _ptr))
#else
#define LOG_ALLOC(_fun, _size, _ret)
#define LOG_REALLOC(_fun, _ptr, _size, _ret)
#define LOG_FREE(_fun, _ptr)
#endif /* XALLOC_LOG */

static unsigned long *free_lists[MAX_SMALL/SIZE_STEPS];

/*
 * systems that support it should define HAS_MMAP_ANON or MMAP_DEV_ZERO
 * and include the appropriate header files for
 * mmap(), munmap(), PROT_READ, PROT_WRITE, MAP_PRIVATE,
 * PAGE_SIZE or _SC_PAGESIZE (and MAP_ANON for HAS_MMAP_ANON).
 *
 * systems that don't support MAP_ANON fall through to the 2 fold behaviour
 */

#if defined(linux)
#define HAS_MMAP_ANON
#include <sys/types.h>
#include <sys/mman.h>
#include <asm/page.h>	/* PAGE_SIZE */
#define HAS_SC_PAGESIZE	/* _SC_PAGESIZE may be an enum for Linux */
#define HAS_GETPAGESIZE
#endif /* linux */

#if defined(__GNU__)
#define HAS_MMAP_ANON
#include <sys/types.h>
#include <sys/mman.h>
#include <mach/vm_param.h>     /* PAGE_SIZE */
#define HAS_SC_PAGESIZE
#define HAS_GETPAGESIZE
#endif /* __GNU__ */

#if defined(CSRG_BASED)
#define HAS_MMAP_ANON
#define HAS_GETPAGESIZE
#include <sys/types.h>
#include <sys/mman.h>
#endif /* CSRG_BASED */

#if defined(DGUX)
#define HAS_GETPAGESIZE
#define MMAP_DEV_ZERO
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#endif /* DGUX */

#if defined(SVR4) && !defined(DGUX)
#define MMAP_DEV_ZERO
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#endif /* SVR4 && !DGUX */

#if defined(sun) && !defined(SVR4) /* SunOS */
#define MMAP_DEV_ZERO	/* doesn't SunOS have MAP_ANON ?? */
#define HAS_GETPAGESIZE
#include <sys/types.h>
#include <sys/mman.h>
#endif /* sun && !SVR4 */

#ifdef XNO_SYSCONF
#undef _SC_PAGESIZE
#endif

#if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
static int pagesize;
#endif

#ifdef MMAP_DEV_ZERO
static int devzerofd = -1;
#include <errno.h>
#endif

/*
 * empty trap function for gdb. Breakpoint here
 * to find who tries to free a free area
 */
void XfreeTrap(void)
{
}

void *
Xalloc (unsigned long amount)
{
    register unsigned long *ptr;
    int indx;

    /* sanity checks */

    /* zero size requested */
    if (amount == 0) {
	LOG_ALLOC("Xalloc=0", amount, 0);
	return NULL;
    }
    /* negative size (or size > 2GB) - what do we do? */
    if ((long)amount < 0) {
	/* Diagnostic */
#ifdef FATALERRORS
 	FatalError("Xalloc: Xalloc(<0)\n");
#else
 	ErrorF("Xalloc warning: Xalloc(<0) ignored..\n");
#endif
 	LOG_ALLOC("Xalloc<0", amount, 0);
	return NULL;
    }

    /* alignment check */
#if defined(__alpha__) || defined(__alpha) || \
    defined(__sparc__) || \
    defined(__mips__) || \
    defined(__powerpc__) || \
    defined(__arm32__) || \
    defined(__ia64__) || defined(ia64) || \
    defined(__s390x__) || defined(__s390__)
    amount = (amount + (sizeof(long)-1)) & ~(sizeof(long)-1);
#endif

    if (amount <= MAX_SMALL) {
	/*
	 * small block
	 */
	/* pick a ready to use small chunk */
	indx = (amount-1) / SIZE_STEPS;
	ptr = free_lists[indx];
	if (NULL == ptr) {
		/* list empty - get 20 or 40 more */
		/* amount = size rounded up */
		amount = (indx+1) * SIZE_STEPS;
		ptr = (unsigned long *)calloc(1,(amount+SIZE_HEADER+TAIL_SIZE)
						* (amount<100 ? 40 : 20));
		if (NULL!=ptr) {
			int i;
			unsigned long *p1, *p2;
			p1 = 0;
			p2 = (unsigned long *)((char *)ptr + SIZE_HEADER);
			for (i=0; i<(amount<100 ? 40 : 20); i++) {
				p1 = p2;
				p1[-2] = amount;
#ifdef XALLOC_DEBUG
				p1[-1] = MAGIC_FREE;
#endif /* XALLOC_DEBUG */
#ifdef SIZE_TAIL
				*(unsigned long *)((unsigned char *)p1 + amount) = MAGIC2;
#endif /* SIZE_TAIL */
				p2 = (unsigned long *)((char *)p1 + SIZE_HEADER + amount + TAIL_SIZE);
				*(unsigned long **)p1 = p2;
			}
			/* last one has no next one */
			*(unsigned long **)p1 = NULL;
			/* put the second in the list */
			free_lists[indx] = (unsigned long *)((char *)ptr + SIZE_HEADER + amount + TAIL_SIZE + SIZE_HEADER);
			/* take the fist one */
			ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
			LOG_ALLOC("Xalloc-S", amount, ptr);
			ptr[-1] = MAGIC;
			return (void *)ptr;
		} /* else fall through to 'Out of memory' */
	} else {
		/* take that piece of mem out of the list */
		free_lists[indx] = *((unsigned long **)ptr);
		/* already has size (and evtl. magic) filled in */
#ifdef XALLOC_DEBUG
		ptr[-1] = MAGIC;
#endif /* XALLOC_DEBUG */
		LOG_ALLOC("Xalloc-S", amount, ptr);
		return (void *)ptr;
	}

#if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
    } else if (amount >= MIN_LARGE) {
	/*
	 * large block
	 */
	/* mmapped malloc */
	/* round up amount */
	amount += SIZE_HEADER + TAIL_SIZE;
	/* round up brutto amount to a multiple of the page size */
	amount = (amount + pagesize-1) & ~(pagesize-1);
#ifdef MMAP_DEV_ZERO
	ptr = (unsigned long *)mmap((caddr_t)0,
					(size_t)amount,
					PROT_READ | PROT_WRITE,
					MAP_PRIVATE,
					devzerofd,
					(off_t)0);
#else
	ptr = (unsigned long *)mmap((caddr_t)0,
					(size_t)amount,
					PROT_READ | PROT_WRITE,
					MAP_ANON | MAP_PRIVATE,
					-1,
					(off_t)0);
#endif
	if (-1!=(long)ptr) {
		ptr[0] = amount - SIZE_HEADER - TAIL_SIZE;
#ifdef XALLOC_DEBUG
		ptr[1] = MAGIC;
#endif /* XALLOC_DEBUG */
#ifdef SIZE_TAIL
		((unsigned long *)((char *)ptr + amount - TAIL_SIZE))[0] = MAGIC2;
#endif /* SIZE_TAIL */
		ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
		LOG_ALLOC("Xalloc-L", amount, ptr);
		return (void *)ptr;
	} /* else fall through to 'Out of memory' */
#endif /* HAS_MMAP_ANON || MMAP_DEV_ZERO */
    } else {
	/*
	 * medium sized block
	 */
	/* 'normal' malloc() */
	ptr=(unsigned long *)calloc(1,amount+SIZE_HEADER+TAIL_SIZE);
	if (ptr != (unsigned long *)NULL) {
		ptr[0] = amount;
#ifdef XALLOC_DEBUG
		ptr[1] = MAGIC;
#endif /* XALLOC_DEBUG */
#ifdef SIZE_TAIL
		*(unsigned long *)((char *)ptr + amount + SIZE_HEADER) = MAGIC2;
#endif /* SIZE_TAIL */
		ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
		LOG_ALLOC("Xalloc-M", amount, ptr);
		return (void *)ptr;
	}
    }
    if (Must_have_memory)
	FatalError("Out of memory");
    LOG_ALLOC("Xalloc-oom", amount, 0);
    return NULL;
}

/*****************
 * XNFalloc 
 * "no failure" realloc, alternate interface to Xalloc w/o Must_have_memory
 *****************/

pointer
XNFalloc (unsigned long amount)
{
    register pointer ptr;

    /* zero size requested */
    if (amount == 0) {
	LOG_ALLOC("XNFalloc=0", amount, 0);
	return NULL;
    }
    /* negative size (or size > 2GB) - what do we do? */
    if ((long)amount < 0) {
	/* Diagnostic */
#ifdef FATALERRORS
	FatalError("Xalloc: XNFalloc(<0)\n");
#else
	ErrorF("Xalloc warning: XNFalloc(<0) ignored..\n");
#endif
 	LOG_ALLOC("XNFalloc<0", amount, 0);
	return (unsigned long *)NULL;
    }
    ptr = Xalloc(amount);
    if (!ptr)
    {
        FatalError("Out of memory");
    }
    return ptr;
}

/*****************
 * Xcalloc
 *****************/

pointer
Xcalloc (unsigned long amount)
{
    pointer ret;

    ret = Xalloc (amount);
    if (ret != 0
#if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
	    && (amount < MIN_LARGE)	/* mmaped anonymous mem is already cleared */
#endif
       )
	bzero ((char *) ret, (int) amount);
    return ret;
}

/*****************
 * XNFcalloc
 *****************/
void *
XNFcalloc (unsigned long amount)
{
    pointer ret;

    ret = XNFalloc (amount);
    if (ret != 0
#if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
	    && (amount < MIN_LARGE)	/* mmaped anonymous mem is already cleared */
#endif
       )
	bzero ((char *) ret, (int) amount);
    return ret;
}

/*****************
 * Xrealloc
 *****************/

void *
Xrealloc (pointer ptr, unsigned long amount)
{
    register unsigned long *new_ptr;

    /* zero size requested */
    if (amount == 0) {
	if (ptr)
		Xfree(ptr);
	LOG_REALLOC("Xrealloc=0", ptr, amount, 0);
	return NULL;
    }
    /* negative size (or size > 2GB) - what do we do? */
    if ((long)amount < 0) {
	/* Diagnostic */
#ifdef FATALERRORS
	FatalError("Xalloc: Xrealloc(<0)\n");
#else
	ErrorF("Xalloc warning: Xrealloc(<0) ignored..\n");
#endif
	if (ptr)
		Xfree(ptr);	/* ?? */
	LOG_REALLOC("Xrealloc<0", ptr, amount, 0);
	return NULL;
    }

    new_ptr = Xalloc(amount);
    if ( (new_ptr) && (ptr) ) {
	unsigned long old_size;
	old_size = ((unsigned long *)ptr)[-2];
#ifdef XALLOC_DEBUG
	if (MAGIC != ((unsigned long *)ptr)[-1]) {
	    if (MAGIC_FREE == ((unsigned long *)ptr)[-1]) {
#ifdef FATALERRORS
		XfreeTrap();
		FatalError("Xalloc error: range already freed in Xrealloc() :-(\n");
#else
		ErrorF("Xalloc error: range already freed in Xrealloc() :-(\a\n");
		sleep(5);
		XfreeTrap();
#endif
		LOG_REALLOC("Xalloc error: ranged already freed in Xrealloc() :-(",
			ptr, amount, 0);
		return NULL;
	    }
#ifdef FATALERRORS
	    XfreeTrap();
		FatalError("Xalloc error: header corrupt in Xrealloc() :-(\n");
#else
		ErrorF("Xalloc error: header corrupt in Xrealloc() :-(\n");
		XfreeTrap();
#endif
		LOG_REALLOC("Xalloc error: header corrupt in Xrealloc() :-(",
			ptr, amount, 0);
		return NULL;
	}
#endif /* XALLOC_DEBUG */
	/* copy min(old size, new size) */
	memcpy((char *)new_ptr, (char *)ptr, (amount < old_size ? amount : old_size));
    }
    if (ptr)
	Xfree(ptr);
    if (new_ptr) {
	LOG_REALLOC("Xrealloc", ptr, amount, new_ptr);
	return (void *)new_ptr;
    }
    if (Must_have_memory)
	FatalError("Out of memory");
    LOG_REALLOC("Xrealloc", ptr, amount, 0);
    return NULL;
}
                    
/*****************
 * XNFrealloc 
 * "no failure" realloc, alternate interface to Xrealloc w/o Must_have_memory
 *****************/

void *
XNFrealloc (pointer ptr, unsigned long amount)
{
    if (( ptr = (pointer)Xrealloc( ptr, amount ) ) == NULL)
    {
        FatalError( "Out of memory" );
    }
    return ptr;
}

/*****************
 *  Xfree
 *    calls free 
 *****************/    

void
Xfree(pointer ptr)
{
    unsigned long size;
    unsigned long *pheader;

    /* free(NULL) IS valid :-(  - and widely used throughout the server.. */
    if (!ptr)
	return;

    pheader = (unsigned long *)((char *)ptr - SIZE_HEADER);
#ifdef XALLOC_DEBUG
    if (MAGIC != pheader[1]) {
	/* Diagnostic */
	if (MAGIC_FREE == pheader[1]) {
#ifdef FATALERRORS
	    XfreeTrap();
	    FatalError("Xalloc error: range already freed in Xrealloc() :-(\n");
#else
	    ErrorF("Xalloc error: range already freed in Xrealloc() :-(\a\n");
	    sleep(5);
	    XfreeTrap();
#endif
	    LOG_FREE("Xalloc error: ranged already freed in Xrealloc() :-(", ptr);
	    return;
	}
#ifdef FATALERRORS
	XfreeTrap();
	FatalError("Xalloc error: Header corrupt in Xfree() :-(\n");
#else
	ErrorF("Xalloc error: Header corrupt in Xfree() :-(\n");
	XfreeTrap();
#endif
	LOG_FREE("Xalloc error:  Header corrupt in Xfree() :-(", ptr);
	return;
    }
#endif /* XALLOC_DEBUG */

    size = pheader[0];
    if (size <= MAX_SMALL) {
	int indx;
	/*
	 * small block
	 */
#ifdef SIZE_TAIL
	if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
		/* Diagnostic */
#ifdef FATALERRORS
	    	XfreeTrap();
		FatalError("Xalloc error: Tail corrupt in Xfree() for small block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
#else
		ErrorF("Xalloc error: Tail corrupt in Xfree() for small block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
		XfreeTrap();
#endif
		LOG_FREE("Xalloc error: Tail corrupt in Xfree() for small block", ptr);
		return;
	}
#endif /* SIZE_TAIL */

#ifdef XFREE_ERASES
	memset(ptr,0xF0,size);
#endif /* XFREE_ERASES */
#ifdef XALLOC_DEBUG
	pheader[1] = MAGIC_FREE;
#endif
	/* put this small block at the head of the list */
	indx = (size-1) / SIZE_STEPS;
	*(unsigned long **)(ptr) = free_lists[indx];
	free_lists[indx] = (unsigned long *)ptr;
	LOG_FREE("Xfree", ptr);
	return;

#if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
    } else if (size >= MIN_LARGE) {
	/*
	 * large block
	 */
#ifdef SIZE_TAIL
	if (MAGIC2 != ((unsigned long *)((char *)ptr + size))[0]) {
		/* Diagnostic */
#ifdef FATALERRORS
	    XfreeTrap();
		FatalError("Xalloc error: Tail corrupt in Xfree() for big block (adr=0x%x, val=0x%x)\n",(char *)ptr+size,((unsigned long *)((char *)ptr + size))[0]);
#else
		ErrorF("Xalloc error: Tail corrupt in Xfree() for big block (adr=0x%x, val=0x%x)\n",(char *)ptr+size,((unsigned long *)((char *)ptr + size))[0]);
		XfreeTrap();
#endif
		LOG_FREE("Xalloc error: Tail corrupt in Xfree() for big block", ptr);
		return;
	}
	size += SIZE_TAIL;
#endif /* SIZE_TAIL */

	LOG_FREE("Xfree", ptr);
	size += SIZE_HEADER;
	munmap((caddr_t)pheader, (size_t)size);
	/* no need to clear - mem is inaccessible after munmap.. */
#endif /* HAS_MMAP_ANON */

    } else {
	/*
	 * medium sized block
	 */
#ifdef SIZE_TAIL
	if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
		/* Diagnostic */
#ifdef FATALERRORS
	    XfreeTrap();
		FatalError("Xalloc error: Tail corrupt in Xfree() for medium block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
#else
		ErrorF("Xalloc error: Tail corrupt in Xfree() for medium block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
		XfreeTrap();
#endif
		LOG_FREE("Xalloc error: Tail corrupt in Xfree() for medium block", ptr);
		return;
	}
#endif /* SIZE_TAIL */

#ifdef XFREE_ERASES
	memset(pheader,0xF0,size+SIZE_HEADER);
#endif /* XFREE_ERASES */
#ifdef XALLOC_DEBUG
	pheader[1] = MAGIC_FREE;
#endif

	LOG_FREE("Xfree", ptr);
	free((char *)pheader);
    }
}

void
OsInitAllocator (void)
{
    static Bool beenhere = FALSE;

    if (beenhere)
	return;
    beenhere = TRUE;

#if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
    pagesize = -1;
#if defined(_SC_PAGESIZE) || defined(HAS_SC_PAGESIZE)
    pagesize = sysconf(_SC_PAGESIZE);
#endif
#ifdef _SC_PAGE_SIZE
    if (pagesize == -1)
	pagesize = sysconf(_SC_PAGE_SIZE);
#endif
#ifdef HAS_GETPAGESIZE
    if (pagesize == -1)
	pagesize = getpagesize();
#endif
#ifdef PAGE_SIZE
    if (pagesize == -1)
	pagesize = PAGE_SIZE;
#endif
    if (pagesize == -1)
	FatalError("OsInitAllocator: Cannot determine page size\n");
#endif

    /* set up linked lists of free blocks */
    bzero ((char *) free_lists, MAX_SMALL/SIZE_STEPS*sizeof(unsigned long *));

#ifdef MMAP_DEV_ZERO
    /* open /dev/zero on systems that have mmap, but not MAP_ANON */
    if (devzerofd < 0) {
	if ((devzerofd = open("/dev/zero", O_RDWR, 0)) < 0)
	    FatalError("OsInitAllocator: Cannot open /dev/zero (errno=%d)\n",
			errno);
    }
#endif

#ifdef XALLOC_LOG
    /* reset the log file to zero length */
    {
	FILE *f;
	f = fopen(XALLOC_LOG_FILE, "w");
	if (NULL!=f)
		fclose(f);
    }
#endif
}

#else /* !INTERNAL_MALLOC */
/* This is to avoid an empty .o */
static int no_internal_xalloc;
#endif /* INTERNAL_MALLOC */