source: trunk/libc/src/kNIX/heap.c

/* $Id: heap.c 3863 2014-06-26 12:14:06Z bird $ */
/** @file
 *
 * kNIX - sbrk/brk heap.
 *
 * Copyright (c) 1996 by Eberhard Mattes
 * Copyright (c) 2006 knut st. osmundsen <bird-src-spam@anduin.net>
 *
 *
 * This file is part of kLIBC.
 *
 * kLIBC is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * kLIBC 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with kLIBC; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */


/*******************************************************************************
*   Header Files                                                               *
*******************************************************************************/
#include "kNIX.h"
#define __LIBC_LOG_GROUP __LIBC_LOG_GRP_HEAP
#include <klibc/logstrict.h>


/**
 * Wrapper around the OS api for freeing an object.
 */
static __inline__ void heapFreeObj(uintptr_t ObjPtr)
{
#ifdef __OS2__
    FS_VAR_SAVE_LOAD();
    int rc = DosFreeMemEx((void *)ObjPtr);
    LIBC_ASSERTM(!rc, "ObjPtr=%tx rc=%d\n", ObjPtr, rc); (void)rc;
    FS_RESTORE();

#elif defined(__NT__)
    PVOID pv = (void *)ObjPtr;
    NTSTATUS rc = NtFreeVirtualMemory(NtCurrentProcess(),   /* ProcessHandle */
                                      &pv,                  /* BaseAddress */
                                      NULL,                 /* FreeSize */
                                      MEM_RELEASE);         /* FreeType */
    LIBC_ASSERTM(NT_SUCCESS(rc), "ObjPtr=%p rc=%x\n", ObjPtr, rc); (void)rc;

#else
# error "Port me!"
#endif
}


/**
 * Allocate a memory object of SIZE bytes which is not located below
 * MIN_ADDR.
 *
 * @returns The address of the memory object.
 * @returns Return 0 on error.
 */
static uintptr_t heapAllocObjAbove(uintptr_t size, uintptr_t min_addr)
{
    void *pv = NULL;
#ifdef __OS2__
    FS_VAR_SAVE_LOAD();
    int rc = DosAllocMemEx(&pv, size, PAG_READ | PAG_WRITE | OBJ_FORK);
    FS_RESTORE();
    if (rc)
        return 0;

#elif defined(__NT__)
    ULONG cb = size;
    NTSTATUS rc = NtAllocateVirtualMemory(NtCurrentProcess(),   /* ProcessHandle */
                                          &pv,                  /* BaseAddress (In/Out) */
                                          0,                    /* ZeroBits */
                                          &cb,                  /* AllocationSize */
                                          MEM_RESERVE,          /* AllocationType */
                                          PAGE_READWRITE);      /* Protect */
    if (!NT_SUCCESS(rc))
        return 0;

#else
# error "Port me!"
#endif

    if ((uintptr_t)pv > min_addr)
        return (uintptr_t)pv;

    /*
     * The memory object is located below MIN_ADDR.  Recurse until we
     * get an appropriate object or until we run out of memory.
     */
    uintptr_t ret = heapAllocObjAbove(size, min_addr);

    /* We got a suitable object. Free the bad one. */
    heapFreeObj((uintptr_t)pv);
    return ret;
}


/**
 * Wrapper around the OS api for committing memory.
 */
static __inline__ int heapCommitObj(uintptr_t addr, uintptr_t size)
{
#ifdef __OS2__
    FS_VAR_SAVE_LOAD();
    int rc = DosSetMem((void *)addr, size, PAG_DEFAULT | PAG_COMMIT);
    FS_RESTORE();
    return !rc ? 0 : -EINVAL;

#elif defined(__NT__)
    ULONG cb = size;
    PVOID pv = (void *)addr;
    NTSTATUS rc = NtAllocateVirtualMemory(NtCurrentProcess(),   /* ProcessHandle */
                                          &pv,                  /* BaseAddress (In/Out) */
                                          0,                    /* ZeroBits */
                                          &cb,                  /* AllocationSize */
                                          MEM_COMMIT,           /* AllocationType */
                                          PAGE_READWRITE);      /* Protect */
    return NT_SUCCESS(rc) ? 0 : -EINVAL;

#else
# error "Port me!"
#endif
}


/**
 * Wrapper around the OS api for decommitting memory.
 */
static __inline__ int heapDecommitObj(uintptr_t addr, uintptr_t size)
{
#ifdef __OS2__
    FS_VAR_SAVE_LOAD();
    int rc = DosSetMem((void *)addr, size, PAG_DECOMMIT);
    FS_RESTORE();
    return !rc ? 0 : -EINVAL;

#elif defined(__NT__)
    ULONG cb = size;
    PVOID pv = (void *)addr;
    NTSTATUS rc = NtFreeVirtualMemory(NtCurrentProcess(),   /* ProcessHandle */
                                      &pv,                  /* BaseAddress */
                                      &cb,                  /* FreeSize */
                                      MEM_DECOMMIT);        /* FreeType */
    return NT_SUCCESS(rc) ? 0 : -EINVAL;

#else
# error "Port me!"
#endif
}



/**
 * Expand the top heap object by INCR bytes. INCR is a positive number.
 * Return the previous break address or 0 (error).
 */
void *__libc_back_heapExpandObjBy(uintptr_t incr)
{
    LIBCLOG_ENTER("incr=%p\n", (void *)incr);

    const uintptr_t old_brk = __libc_back_gpHeapTopObj->brk;
    const uintptr_t new_brk = old_brk + incr;
    if (    new_brk < __libc_back_gpHeapTopObj->base
        ||  new_brk > __libc_back_gpHeapTopObj->end)
        LIBCLOG_ERROR_RETURN_P(NULL);

    uintptr_t addr = old_brk;
    uintptr_t size = incr;
    if (addr & 0xfff)
    {
        uintptr_t rest = 0x1000 - (addr & 0xfff);
        if (rest >= size)
            size = 0;
        else
        {
            size -= rest;
            addr += rest;
        }
    }
    if (size != 0)
    {
        if (heapCommitObj(addr, size) != 0)
            LIBCLOG_ERROR_RETURN_P(NULL);
    }
    __libc_back_gpHeapTopObj->brk = new_brk;
    LIBCLOG_RETURN_P((void *)old_brk);
}


/**
 * Shrink the top heap object by DECR bytes. DECR is a positive number.
 * Return the previous break address or 0 (error).
 */
void *__libc_back_heapShrinkObjBy(uintptr_t decr)
{
    LIBCLOG_ENTER("decr=%p\n", (void *)decr);

    const uintptr_t old_brk = __libc_back_gpHeapTopObj->brk;
    const uintptr_t new_brk = old_brk - decr;
    if (    new_brk < __libc_back_gpHeapTopObj->base
        ||  new_brk > __libc_back_gpHeapTopObj->end)
        LIBCLOG_ERROR_RETURN_P(NULL);

    const uintptr_t addr = (new_brk + 0xfff) & ~(uintptr_t)0xfff;
    const uintptr_t high = (__libc_back_gpHeapTopObj->brk + 0xfff) & ~(uintptr_t)0xfff;
    if (high > addr)
    {
        if (heapDecommitObj(addr, high - addr) != 0)
            LIBCLOG_ERROR_RETURN_P(NULL);
    }
    __libc_back_gpHeapTopObj->brk = new_brk;
    LIBCLOG_RETURN_P((void *)old_brk);
}


/**
 * Expand the heap by INCR bytes. INCR is a positive number.
 * Return the base address of the expansion or 0 (error).
 */
void *__libc_back_heapExpandBy(uintptr_t incr, __LIBCSBRKMODEL enmSBrkModel)
{
    LIBCLOG_ENTER("incr=%tx enmSBrkModel=%d\n", incr, enmSBrkModel);
    const unsigned old_obj_count = __libc_back_gcHeapObjs;

    /*
     *Allocate the first object if not yet done.
     */
    if (__libc_back_gcHeapObjs == 0)
    {
        uintptr_t size = __libc_back_gcbHeap;
        if (incr > size)
            size = (incr + 0xffff) & ~(uintptr_t)0xffff;
        uintptr_t base = heapAllocObjAbove(size, 0);
        if (base == 0)
            LIBCLOG_ERROR_RETURN_P(NULL);
        __libc_back_gaHeapObjs[0].base = base;
        __libc_back_gaHeapObjs[0].brk = base;
        __libc_back_gaHeapObjs[0].end = base + size;
        __libc_back_gcHeapObjs = 1;
        __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[0];
    }

    /*
     * Now we have at least one heap object. Check for arithmetic
     * overflow.
     */
    if (__libc_back_gpHeapTopObj->brk + incr < __libc_back_gpHeapTopObj->base)
    {
        /*
         * Overflow. If we've just allocated the first heap object,
         * deallocate it again unless memory must be allocated contiguously.
         */
        if (    old_obj_count == 0
            &&  enmSBrkModel != __LIBC_SBRK_MODEL_CONTIGUOUS)
        {
            heapFreeObj(__libc_back_gaHeapObjs[0].base);
            __libc_back_gcHeapObjs = 0;
            __libc_back_gpHeapTopObj = NULL;
        }
        LIBCLOG_ERROR_RETURN_P(NULL);
    }

    /*
     * Check whether we need another heap object. Allocate one if we
     * need one and are allowed to allocate one. This should not happen
     * if we just allocated the first one above.
     */
    if (__libc_back_gpHeapTopObj->brk + incr > __libc_back_gpHeapTopObj->end)
    {
        /*
         * We need another heap object. Fail if we are not allowed to
         * allocate non-contiguous memory or if we already have the
         * maximum number of heap objects.
         */
        if (    enmSBrkModel == __LIBC_SBRK_MODEL_CONTIGUOUS
            ||  __libc_back_gcHeapObjs >= CFG_KNIX_MAX_HEAP_OBJS)
            LIBCLOG_ERROR_RETURN_P(NULL);

        /*
         * Allocate at least __libc_back_gcbHeap bytes. The new object must
         * be located above the currently top one.
         */
        uintptr_t size = __libc_back_gcbHeap;
        if (incr > size)
            size = (incr + 0xffff) & ~(uintptr_t)0xffff;

        uintptr_t base;
        for (;;)
        {
            if (enmSBrkModel == __LIBC_SBRK_MODEL_ARBITRARY)
                base = heapAllocObjAbove(size, 0);
            else
                base = heapAllocObjAbove(size, __libc_back_gpHeapTopObj->end);
            if (base != 0)
                break;

            /*
             * If we're out of virtual address space, halve the size and
             * try again until allocation succeeds. Of course, don't
             * attempt to allocate less than INCR bytes.
             */
            size /= 2;
            if (size < incr)
                LIBCLOG_ERROR_RETURN_P(NULL);
        }

        __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs++];
        __libc_back_gpHeapTopObj->base = base;
        __libc_back_gpHeapTopObj->brk = base;
        __libc_back_gpHeapTopObj->end = base + size;
    }

    /*
     * Now __libc_back_gpHeapTopObj points to an object which has enough
     * space. Commit memory as required.  _sys_expand_heap_obj() returns
     * the top object's break address, which is the base address of the
     * expansion as an object might have been added.
     */
    void *pRet = __libc_back_heapExpandObjBy(incr);
    if (pRet)
        LIBCLOG_RETURN_P(pRet);
    LIBCLOG_ERROR_RETURN_P(pRet);
}


/**
 * Shrink the heap to the new break address NEW_BRK.
 * Return the previous break address or 0 (error).
 */
void *__libc_back_heapShrinkTo(uintptr_t new_brk)
{
    LIBCLOG_ENTER("new_brk=%tx\n", new_brk);

    /*
     * Find the heap object containing the new break address.  Fail if
     * there is no such heap object.  Note that the new break address
     * must not be beyond the heap object current break address, that
     * is, we cannot shrink the heap (by deallocating objects) and grow
     * a heap object in one step.
     */
    unsigned iObj;
    for (iObj = 0; iObj < __libc_back_gcHeapObjs; ++iObj)
        if (    __libc_back_gaHeapObjs[iObj].base <= new_brk
            &&  __libc_back_gaHeapObjs[iObj].brk >= new_brk)
            break;
    if (iObj >= __libc_back_gcHeapObjs)
        return 0;

    /* We have at least one heap object, OBJ, so this is safe. */
    void * const pvOldBrk = (void *)__libc_back_gpHeapTopObj->brk;

    /*
     * Free objects which are between the new break address and the old
     * one. Fail if there are such objects and __LIBC_SBRK_MODEL_CONTIGUOUS is
     * selected.
     */
    if (iObj != __libc_back_gcHeapObjs - 1)
    {
        if (__libc_back_genmSBrkModel == __LIBC_SBRK_MODEL_CONTIGUOUS)
            LIBCLOG_ERROR_RETURN_P(NULL);

        while (__libc_back_gcHeapObjs - 1 > iObj)
        {
            __libc_back_gcHeapObjs -= 1;
            heapFreeObj(__libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base);
            __libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base = 0;
        }
        __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs-1];
    }

    if (new_brk == __libc_back_gpHeapTopObj->base)
    {
        /*
         * The top object is shrunk to zero bytes, deallocate it and bump NEW_BRK back
         * to the previous object. If __LIBC_SBRK_MODEL_CONTIGUOUS is selected and
         * the (only) object is shrunk to 0 bytes, it will be kept anyway to avoid
         * breaking programs which depend on the object keeping its address:
         *
         *      p = sbrk(1000);
         *      sbrk(-1000);
         *      assert(sbrk(1000) == p);
         *
         * The assertion should not fail. However, programs which select
         * __LIBC_SBRK_MODEL_MONOTONOUS or __LIBC_SBRK_MODEL_ARBITRARY should be
         * prepared for failure of the assertion. Consider the following code:
         *
         *      sbrk(1000);
         *      p = sbrk(0);
         *      sbrk(-1000);
         *      brk(p);
         *
         * Here, brk() may fail due to deallocation of the top object.
         */
        if (    iObj != 0
            ||  __libc_back_genmSBrkModel != __LIBC_SBRK_MODEL_CONTIGUOUS)
        {
            __libc_back_gcHeapObjs -= 1;
            heapFreeObj(__libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base);
            __libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base = 0;

            if (__libc_back_gcHeapObjs == 0)
                __libc_back_gpHeapTopObj = NULL;
            else
            {
                __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs-1];
                new_brk = __libc_back_gpHeapTopObj->brk;
            }
        }
    }

    /*
     * Now decommit unused pages of the top heap object, if there is one.
     */
    if (    __libc_back_gcHeapObjs > 0
        &&  __libc_back_heapShrinkObjBy(__libc_back_gpHeapTopObj->brk - new_brk) == 0)
        LIBCLOG_RETURN_P(NULL);
    LIBCLOG_RETURN_P(pvOldBrk);
}


/**
 * Shrink the heap by DECR bytes. DECR is a positive number.
 * Return the previous break address or 0 (error).
 */
void *__libc_back_heapShrinkBy(uintptr_t decr, __LIBCSBRKMODEL enmSBrkModel)
{
    LIBCLOG_ENTER("decr=%tx enmSBrkModel=%d\n", decr, enmSBrkModel);
    if (    __libc_back_gcHeapObjs != 0
        &&  __libc_back_gpHeapTopObj->brk - decr >= __libc_back_gpHeapTopObj->base)
    {
        void *pvRet = __libc_back_heapShrinkTo(__libc_back_gpHeapTopObj->brk - decr);
        LIBCLOG_RETURN_P(pvRet);
    }
    LIBCLOG_RETURN_P(NULL);
}