/* $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 * * * 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 /** * 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); }