Index: /trunk/include/iprt/heap.h =================================================================== --- /trunk/include/iprt/heap.h (revision 283) +++ /trunk/include/iprt/heap.h (revision 283) @@ -0,0 +1,108 @@ +/* $Id: $ */ +/** @file + * InnoTek Portable Runtime - A Simple Heap. + */ + +/* + * Copyright (C) 2006 InnoTek Systemberatung GmbH + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. 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, + * in version 2 as it comes in the "COPYING" file of the VirtualBox OSE + * distribution. VirtualBox OSE is distributed in the hope that it will + * be useful, but WITHOUT ANY WARRANTY of any kind. + * + * If you received this file as part of a commercial VirtualBox + * distribution, then only the terms of your commercial VirtualBox + * license agreement apply instead of the previous paragraph. + */ + + +/* >>> heap.h */ +#ifndef __iprt_heap_h__ +#define __iprt_heap_h__ + +#include +#include + +/* >>> types.h */ +/** Handle to a simple heap. */ +typedef struct RTHEAPSIMPLEINTERNAL *RTHEAPSIMPLE; +/** Pointer to a handle to a simple heap. */ +typedef RTHEAPSIMPLE *PRTHEAPSIMPLE; +/* <<< types.h */ + +__BEGIN_DECLS + +/** + * Initializes the heap. + * + * @returns IPRT status code on success. + * @param pHeap Where to store the heap anchor block on success. + * @param pvMemory Pointer to the heap memory. + * @param cbMemory The size of the heap memory. + */ +RTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE pHeap, void *pvMemory, size_t cbMemory); + +/** + * Merge two simple heaps into one. + * + * The requiremet is of course that they next two each other memory wise. + * + * @returns IPRT status code on success. + * @param pHeap Where to store the handle to the merged heap on success. + * @param Heap1 Handle to the first heap. + * @param Heap2 Handle to the second heap. + */ +RTDECL(int) RTHeapSimpleMerge(PRTHEAPSIMPLE pHeap, RTHEAPSIMPLE Heap1, RTHEAPSIMPLE Heap2); + +/** + * Allocates memory from the specified simple heap. + * + * @returns Pointer to the allocated memory block on success. + * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.) + * + * @param Heap The heap to allocate the memory on. + * @param cb The requested heap block size. + * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment. + * Must be a power of 2. + */ +RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment); + +/** + * Allocates zeroed memory from the specified simple heap. + * + * @returns Pointer to the allocated memory block on success. + * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.) + * + * @param Heap The heap to allocate the memory on. + * @param cb The requested heap block size. + * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment. + * Must be a power of 2. + */ +RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment); + +/** + * Frees memory allocated from a simple heap. + * + * @param Heap The heap. This is optional and will only be used for strict assertions. + * @param pv The heap block returned by RTHeapSimple + */ +RTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE Heap, void *pv); + +#ifdef DEBUG +/** + * Dumps the hypervisor heap to the (default) log. + * + * @param Heap The heap handle. + */ +RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE Heap); +#endif + + +__END_DECLS + +#endif + Index: /trunk/src/VBox/Runtime/testcase/tstHeapSimple.cpp =================================================================== --- /trunk/src/VBox/Runtime/testcase/tstHeapSimple.cpp (revision 283) +++ /trunk/src/VBox/Runtime/testcase/tstHeapSimple.cpp (revision 283) @@ -0,0 +1,191 @@ +/* $Id $ */ +/** @file + * InnoTek Portable Runtime Testcase - Simple Heap. + */ + +/* + * Copyright (C) 2006 InnoTek Systemberatung GmbH + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. 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, + * in version 2 as it comes in the "COPYING" file of the VirtualBox OSE + * distribution. VirtualBox OSE is distributed in the hope that it will + * be useful, but WITHOUT ANY WARRANTY of any kind. + * + * If you received this file as part of a commercial VirtualBox + * distribution, then only the terms of your commercial VirtualBox + * license agreement apply instead of the previous paragraph. + */ + +/******************************************************************************* +* Header Files * +*******************************************************************************/ +#include +#include +#include +#include +#include +#include +#include + + +int main(int argc, char *argv[]) +{ + /* + * Init runtime. + */ + int rc = RTR3Init(); + if (RT_FAILURE(rc)) + { + RTPrintf("RTR3Init failed: %Vrc\n", rc); + return 1; + } + RTPrintf("tstHeapSimple: TESTING...\n"); + + /* + * Create a heap. + */ + static uint8_t s_abMem[128*1024]; + RTHEAPSIMPLE Heap; + rc = RTHeapSimpleInit(&Heap, &s_abMem[1], sizeof(s_abMem) - 1); + if (RT_FAILURE(rc)) + { + RTPrintf("RTHeapSimpleInit failed: %Vrc\n", rc); + return 1; + } + + /* + * Try allocate. + */ + static struct + { + size_t cb; + unsigned uAlignment; + void *pvAlloc; + unsigned iFreeOrder; + } aOps[] = + { + { 16, 0, NULL, 0 }, + { 16, 4, NULL, 1 }, + { 16, 8, NULL, 2 }, + { 16, 16, NULL, 5 }, + { 16, 32, NULL, 4 }, + { 32, 0, NULL, 3 }, + { 31, 0, NULL, 6 }, + { 1024, 0, NULL, 8 }, + { 1024, 32, NULL, 10 }, + { 1024, 32, NULL, 12 }, + { PAGE_SIZE, PAGE_SIZE, NULL, 13 }, + { 1024, 32, NULL, 9 }, + { PAGE_SIZE, 32, NULL, 11 }, + { PAGE_SIZE, PAGE_SIZE, NULL, 14 }, + { 16, 0, NULL, 15 }, + { 9, 0, NULL, 7 }, + { 16, 0, NULL, 7 }, + { 36, 0, NULL, 7 }, + { 16, 0, NULL, 7 }, + { 12344, 0, NULL, 7 }, + { 50, 0, NULL, 7 }, + { 16, 0, NULL, 7 }, + }; + unsigned i; +#ifdef DEBUG + RTHeapSimpleDump(Heap); +#endif +// size_t cbBefore = RTHeapSimpleGetFreeSize(Heap); + size_t cbBefore = 0; + static char szFill[] = "01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; + + /* allocate */ + for (i = 0; i < ELEMENTS(aOps); i++) + { + aOps[i].pvAlloc = RTHeapSimpleAlloc(Heap, aOps[i].cb, aOps[i].uAlignment); + if (!aOps[i].pvAlloc) + { + RTPrintf("Failure: RTHeapSimpleAlloc(%p, %#x, %#x,) -> NULL i=%d\n", (void *)Heap, aOps[i].cb, aOps[i].uAlignment, i); + return 1; + } + memset(aOps[i].pvAlloc, szFill[i], aOps[i].cb); + if (ALIGNP(aOps[i].pvAlloc, (aOps[i].uAlignment ? aOps[i].uAlignment : 8)) != aOps[i].pvAlloc) + { + RTPrintf("Failure: RTHeapSimpleAlloc(%p, %#x, %#x,) -> %p\n", (void *)Heap, aOps[i].cb, aOps[i].uAlignment, i); + return 1; + } + } + + /* free and allocate the same node again. */ + for (i = 0; i < ELEMENTS(aOps); i++) + { + if ( !aOps[i].pvAlloc + || aOps[i].uAlignment == PAGE_SIZE) + continue; + //size_t cbBeforeSub = RTHeapSimpleGetFreeSize(Heap); + RTHeapSimpleFree(Heap, aOps[i].pvAlloc); + + //RTPrintf("debug: i=%d cbBeforeSub=%d now=%d\n", i, cbBeforeSub, RTHeapSimpleGetFreeSize(Heap)); + void *pv; + pv = RTHeapSimpleAlloc(Heap, aOps[i].cb, aOps[i].uAlignment); + if (pv) + { + RTPrintf("Failure: RTHeapSimpleAlloc(%p, %#x, %#x,) -> NULL i=%d\n", (void *)Heap, aOps[i].cb, aOps[i].uAlignment, i); + return 1; + } + if (pv != aOps[i].pvAlloc) + { + RTPrintf("Failure: Free+Alloc returned different address. new=%p old=%p i=%d (doesn't work with delayed free)\n", pv, aOps[i].pvAlloc, i); + //return 1; + } + aOps[i].pvAlloc = pv; + #if 0 /* won't work :/ */ + size_t cbAfterSub = RTHeapSimpleGetFreeSize(Heap); + if (cbBeforeSub != cbAfterSub) + { + RTPrintf("Failure: cbBeforeSub=%d cbAfterSub=%d. i=%d\n", cbBeforeSub, cbAfterSub, i); + return 1; + } + #endif + } + + /* free it in a specific order. */ + int cFreed = 0; + for (i = 0; i < ELEMENTS(aOps); i++) + { + unsigned j; + for (j = 0; j < ELEMENTS(aOps); j++) + { + if ( aOps[j].iFreeOrder != i + || !aOps[j].pvAlloc) + continue; + //RTPrintf("j=%d i=%d free=%d cb=%d pv=%p\n", j, i, RTHeapSimpleGetFreeSize(Heap), aOps[j].cb, aOps[j].pvAlloc); + if (aOps[j].uAlignment == PAGE_SIZE) + cbBefore -= aOps[j].cb; + else + RTHeapSimpleFree(Heap, aOps[j].pvAlloc); + aOps[j].pvAlloc = NULL; + cFreed++; + } + } + Assert(cFreed == RT_ELEMENTS(aOps)); + //RTPrintf("i=done free=%d\n", RTHeapSimpleGetFreeSize(Heap)); + +#if 0 + /* check that we're back at the right amount of free memory. */ + //size_t cbAfter = RTHeapSimpleGetFreeSize(Heap); + if (cbBefore != cbAfter) + { + RTPrintf("Warning: Either we've split out an alignment chunk at the start, or we've got\n" + " an alloc/free accounting bug: cbBefore=%d cbAfter=%d\n", cbBefore, cbAfter); +#ifdef DEBUG + RTHeapSimpleDump(Heap); +#endif + } +#endif + + RTPrintf("tstHeapSimple: Success\n"); +#ifdef LOG_ENABLED + RTLogFlush(NULL); +#endif + return 0; +}