// mem.c - memory management

//

// © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

//

/*

 * This file is part of zsh, the Z shell.

 *

 * Copyright (c) 1992-1997 Paul Falstad

 * All rights reserved.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and to distribute modified versions of this software for any

 * purpose, provided that the above copyright notice and the following

 * two paragraphs appear in all copies of this software.

 *

 * In no event shall Paul Falstad or the Zsh Development Group be liable

 * to any party for direct, indirect, special, incidental, or consequential

 * damages arising out of the use of this software and its documentation,

 * even if Paul Falstad and the Zsh Development Group have been advised of

 * the possibility of such damage.

 *

 * Paul Falstad and the Zsh Development Group specifically disclaim any

 * warranties, including, but not limited to, the implied warranties of

 * merchantability and fitness for a particular purpose.  The software

 * provided hereunder is on an "as is" basis, and Paul Falstad and the

 * Zsh Development Group have no obligation to provide maintenance,

 * support, updates, enhancements, or modifications.

 *

 */

#include "zsh.mdh"

#include "mem.pro"

/*

	There are two ways to allocate memory in zsh.  The first way is

	to call zalloc/zshcalloc, which call malloc/calloc directly.  It

	is legal to call realloc() or free() on memory allocated this way.

	The second way is to call zhalloc/hcalloc, which allocates memory

	from one of the memory pools on the heap stack.  Such memory pools 

	will automatically created when the heap allocation routines are

	called.  To be sure that they are freed at appropriate times

	one should call pushheap() before one starts using heaps and

	popheap() after that (when the memory allocated on the heaps since

	the last pushheap() isn't needed anymore).

	pushheap() saves the states of all currently allocated heaps and

	popheap() resets them to the last state saved and destroys the

	information about that state.  If you called pushheap() and

	allocated some memory on the heaps and then come to a place where

	you don't need the allocated memory anymore but you still want

	to allocate memory on the heap, you should call freeheap().  This

	works like popheap(), only that it doesn't free the information

	about the heap states (i.e. the heaps are like after the call to

	pushheap() and you have to call popheap some time later).

	Memory allocated in this way does not have to be freed explicitly;

	it will all be freed when the pool is destroyed.  In fact,

	attempting to free this memory may result in a core dump.

	If possible, the heaps are allocated using mmap() so that the

	(*real*) heap isn't filled up with empty zsh heaps. If mmap()

	is not available and zsh's own allocator is used, we use a simple trick

	to avoid that: we allocate a large block of memory before allocating

	a heap pool, this memory is freed again immediately after the pool

	is allocated. If there are only small blocks on the free list this

	guarantees that the memory for the pool is at the end of the memory

	which means that we can give it back to the system when the pool is

	freed.

	hrealloc(char *p, size_t old, size_t new) is an optimisation

	with a similar interface to realloc().  Typically the new size

	will be larger than the old one, since there is no gain in

	shrinking the allocation (indeed, that will confused hrealloc()

	since it will forget that the unused space once belonged to this

	pointer).  However, new == 0 is a special case; then if we

	had to allocate a special heap for this memory it is freed at

	that point.

*/

#if defined(HAVE_SYS_MMAN_H) && defined(HAVE_MMAP) && defined(HAVE_MUNMAP)

#include <sys/mman.h>

#if defined(MAP_ANONYMOUS) && defined(MAP_PRIVATE)

#define USE_MMAP 1

#define MMAP_FLAGS (MAP_ANONYMOUS | MAP_PRIVATE)

#endif

#endif

#ifdef __SYMBIAN32__

#ifdef __WINSCW__

#pragma warn_possunwant off

#endif//__WINSCW__

#endif//__SYMBIAN32__

#ifdef ZSH_MEM_WARNING

# ifndef DEBUG

#  define DEBUG 1

# endif

#endif

#if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)

static int h_m[1025], h_push, h_pop, h_free;

#endif

/* Make sure we align to the longest fundamental type. */

union mem_align {

    zlong l;

    double d;

};

#define H_ISIZE  sizeof(union mem_align)

#define HEAPSIZE (16384 - H_ISIZE)

/* Memory available for user data in default arena size */

#define HEAP_ARENA_SIZE (HEAPSIZE - sizeof(struct heap))

#define HEAPFREE (16384 - H_ISIZE)

/* Memory available for user data in heap h */

#define ARENA_SIZEOF(h) ((h)->size - sizeof(struct heap))

/* list of zsh heaps */

static Heap heaps;

/* a heap with free space, not always correct (it will be the last heap

 * if that was newly allocated but it may also be another one) */

static Heap fheap;

/* Use new heaps from now on. This returns the old heap-list. */

/**/

mod_export Heap

new_heaps(void)

{

    Heap h;

    queue_signals();

    h = heaps;

    fheap = heaps = NULL;

    unqueue_signals();

    return h;

}

/* Re-install the old heaps again, freeing the new ones. */

/**/

mod_export void

old_heaps(Heap old)

{

    Heap h, n;

    queue_signals();

    for (h = heaps; h; h = n) {

	n = h->next;

	DPUTS(h->sp, "BUG: old_heaps() with pushed heaps");

#ifdef USE_MMAP

	munmap((void *) h, sizeof(*h));

#else

	zfree(h, sizeof(*h));

#endif

    }

    heaps = old;

    fheap = NULL;

    unqueue_signals();

}

/* Temporarily switch to other heaps (or back again). */

/**/

mod_export Heap

switch_heaps(Heap new)

{

    Heap h;

    queue_signals();

    h = heaps;

    heaps = new;

    fheap = NULL;

    unqueue_signals();

    return h;

}

/* save states of zsh heaps */

/**/

mod_export void

pushheap(void)

{

    Heap h;

    Heapstack hs;

    queue_signals();

#if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)

    h_push++;

#endif

    for (h = heaps; h; h = h->next) {

	DPUTS(!h->used, "BUG: empty heap");

	hs = (Heapstack) zalloc(sizeof(*hs));

	hs->next = h->sp;

	h->sp = hs;

	hs->used = h->used;

    }

    unqueue_signals();

}

/* reset heaps to previous state */

/**/

mod_export void

freeheap(void)

{

    Heap h, hn, hl = NULL;

    queue_signals();

#if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)

    h_free++;

#endif

    fheap = NULL;

    for (h = heaps; h; h = hn) {

	hn = h->next;

	if (h->sp) {

#ifdef ZSH_MEM_DEBUG

	    memset(arena(h) + h->sp->used, 0xff, h->used - h->sp->used);

#endif

	    h->used = h->sp->used;

	    if (!fheap && h->used < ARENA_SIZEOF(h))

		fheap = h;

	    hl = h;

	} else {

#ifdef USE_MMAP

	    munmap((void *) h, h->size);

#else

	    zfree(h, HEAPSIZE);

#endif

	}

    }

    if (hl)

	hl->next = NULL;

    else

	heaps = NULL;

    unqueue_signals();

}

/* reset heap to previous state and destroy state information */

/**/

mod_export void

popheap(void)

{

    Heap h, hn, hl = NULL;

    Heapstack hs;

    queue_signals();

#if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)

    h_pop++;

#endif

    fheap = NULL;

    for (h = heaps; h; h = hn) {

	hn = h->next;

	if ((hs = h->sp)) {

	    h->sp = hs->next;

#ifdef ZSH_MEM_DEBUG

	    memset(arena(h) + hs->used, 0xff, h->used - hs->used);

#endif

	    h->used = hs->used;

	    if (!fheap && h->used < ARENA_SIZEOF(h))

		fheap = h;

	    zfree(hs, sizeof(*hs));

	    hl = h;

	} else {

#ifdef USE_MMAP

	    munmap((void *) h, h->size);

#else

	    zfree(h, HEAPSIZE);

#endif

	}

    }

    if (hl)

	hl->next = NULL;

    else

	heaps = NULL;

    unqueue_signals();

}

#ifdef USE_MMAP

/*

 * Utility function to allocate a heap area of at least *n bytes.

 * *n will be rounded up to the next page boundary.

 */

static Heap

mmap_heap_alloc(size_t *n)

{

    Heap h;

    static size_t pgsz = 0;

    if (!pgsz) {

#ifdef _SC_PAGESIZE

	pgsz = sysconf(_SC_PAGESIZE);     /* SVR4 */

#else

# ifdef _SC_PAGE_SIZE

	pgsz = sysconf(_SC_PAGE_SIZE);    /* HPUX */

# else

	pgsz = getpagesize();

# endif

#endif

	pgsz--;

    }

    *n = (*n + pgsz) & ~pgsz;

    h = (Heap) mmap(NULL, *n, PROT_READ | PROT_WRITE,

		    MMAP_FLAGS, -1, 0);

    if (h == ((Heap) -1)) {

	zerr("fatal error: out of heap memory", NULL, 0);

	exit(1);

    }

    return h;

}

#endif

/* allocate memory from the current memory pool */

/**/

mod_export void *

zhalloc(size_t size)

{

    Heap h;

    size_t n;

    size = (size + H_ISIZE - 1) & ~(H_ISIZE - 1);

    queue_signals();

#if defined(ZSH_MEM) && defined(ZSH_MEM_DEBUG)

    h_m[size < (1024 * H_ISIZE) ? (size / H_ISIZE) : 1024]++;

#endif

    /* find a heap with enough free space */

    for (h = ((fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used))

	      ? fheap : heaps);

	 h; h = h->next) {

	if (ARENA_SIZEOF(h) >= (n = size + h->used)) {

	    void *ret;

	    h->used = n;

	    ret = arena(h) + n - size;

	    unqueue_signals();

	    return ret;

	}

    }

    {

	Heap hp;

        /* not found, allocate new heap */

#if defined(ZSH_MEM) && !defined(USE_MMAP)

	static int called = 0;

	void *foo = called ? (void *)malloc(HEAPFREE) : NULL;

            /* tricky, see above */

#endif

	n = HEAP_ARENA_SIZE > size ? HEAPSIZE : size + sizeof(*h);

	for (hp = NULL, h = heaps; h; hp = h, h = h->next);

#ifdef USE_MMAP

	h = mmap_heap_alloc(&n);

#else

	h = (Heap) zalloc(n);

#endif

#if defined(ZSH_MEM) && !defined(USE_MMAP)

	if (called)

	    zfree(foo, HEAPFREE);

	called = 1;

#endif

	h->size = n;

	h->used = size;

	h->next = NULL;

	h->sp = NULL;

	if (hp)

	    hp->next = h;

	else

	    heaps = h;

	fheap = h;

	unqueue_signals();

	return arena(h);

    }

}

/**/

mod_export void *

hrealloc(char *p, size_t old, size_t new)

{

    Heap h, ph;

    old = (old + H_ISIZE - 1) & ~(H_ISIZE - 1);

    new = (new + H_ISIZE - 1) & ~(H_ISIZE - 1);

    if (old == new)

	return p;

    if (!old && !p)

	return zhalloc(new);

    /* find the heap with p */

    queue_signals();

    for (h = heaps, ph = NULL; h; ph = h, h = h->next)

	if (p >= arena(h) && p < arena(h) + ARENA_SIZEOF(h))

	    break;

    DPUTS(!h, "BUG: hrealloc() called for non-heap memory.");

    DPUTS(h->sp && arena(h) + h->sp->used > p,

	  "BUG: hrealloc() wants to realloc pushed memory");

    /*

     * If the end of the old chunk is before the used pointer,

     * more memory has been zhalloc'ed afterwards.

     * We can't tell if that's still in use, obviously, since

     * that's the whole point of heap memory.

     * We have no choice other than to grab some more memory

     * somewhere else and copy in the old stuff.

     */

    if (p + old < arena(h) + h->used) {

	if (new > old) {

	    char *ptr = (char *) zhalloc(new);

	    memcpy(ptr, p, old);

#ifdef ZSH_MEM_DEBUG

	    memset(p, 0xff, old);

#endif

	    unqueue_signals();

	    return ptr;

	} else {

	    unqueue_signals();

	    return new ? p : NULL;

	}

    }

    DPUTS(p + old != arena(h) + h->used, "BUG: hrealloc more than allocated");

    /*

     * We now know there's nothing afterwards in the heap, now see if

     * there's nothing before.  Then we can reallocate the whole thing.

     * Otherwise, we need to keep the stuff at the start of the heap,

     * then allocate a new one too; this is handled below.  (This will

     * guarantee we occupy a full heap next time round, provided we

     * don't use the heap for anything else.)

     */

    if (p == arena(h)) {

	/*

	 * Zero new seems to be a special case saying we've finished

	 * with the specially reallocated memory, see scanner() in glob.c.

	 */

	if (!new) {

	    if (ph)

		ph->next = h->next;

	    else

		heaps = h->next;

	    fheap = NULL;

#ifdef USE_MMAP

	    munmap((void *) h, h->size);

#else

	    zfree(h, HEAPSIZE);

#endif

	    unqueue_signals();

	    return NULL;

	}

	if (new > ARENA_SIZEOF(h)) {

	    /*

	     * Not enough memory in this heap.  Allocate a new

	     * one of sufficient size.

	     *

	     * To avoid this happening too often, allocate

	     * chunks in multiples of HEAPSIZE.

	     * (Historical note:  there didn't used to be any

	     * point in this since we didn't consistently record

	     * the allocated size of the heap, but now we do.)

	     */

	    size_t n = (new + sizeof(*h) + HEAPSIZE);

	    n -= n % HEAPSIZE;

	    fheap = NULL;

#ifdef USE_MMAP

	    {

		/*

		 * I don't know any easy portable way of requesting

		 * a mmap'd segment be extended, so simply allocate

		 * a new one and copy.

		 */

		Heap hnew;

		hnew = mmap_heap_alloc(&n);

		/* Copy the entire heap, header (with next pointer) included */

		memcpy(hnew, h, h->size);

		munmap((void *)h, h->size);

		h = hnew;

	    }

#else

	    h = (Heap) realloc(h, n);

#endif

	    h->size = n;

	    if (ph)

		ph->next = h;

	    else

		heaps = h;

	}