heapsimple.cpp revision 6cd47f43e2d859210588a870c49b1b122308b170
* Copyright (C) 2006-2007 innotek GmbH * This file is part of VirtualBox Open Source Edition (OSE), as * 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. /******************************************************************************* *******************************************************************************/ /******************************************************************************* * Structures and Typedefs * *******************************************************************************/ /** Pointer to the heap anchor block. */ /** Pointer to a heap block. */ /** Pointer to a free heap block. */ * Structure describing a simple heap block. * If this block is allocated, it is followed by the user user data. * If this block is free, see RTHEAPSIMPLEFREE. /** The next block in the global block list. */ /** The previous block in the global block list. */ /** Pointer to the heap anchor block. */ /** The block is free if this flag is set. When cleared it's allocated. */ /** The mask that needs to be applied to RTHEAPSIMPLEBLOCK::fFalgs to obtain the magic value. */ * Checks if the specified block is valid or not. * @returns boolean answer. * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure. * Checks if the specified block is valid and in use. * @returns boolean answer. * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure. * Checks if the specified block is valid and free. * @returns boolean answer. * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure. * Checks if the specified block is free or not. * @returns boolean answer. * @param pBlock Pointer to a valid RTHEAPSIMPLEBLOCK structure. * This is an extended version of RTHEAPSIMPLEBLOCK that takes the unused * user data to store free list pointers and a cached size value. /** Pointer to the next free block. */ /** Pointer to the previous free block. */ /** The size of the block (excluding the RTHEAPSIMPLEBLOCK part). */ /** An alignment filler to make it a multiple of (sizeof(void *) * 2). */ * This structure is placed at the head of the memory block specified to RTHeapSimpleInit(), * which means that the first RTHEAPSIMPLEBLOCK appears immediately after this structure. /** The typical magic (RTHEAPSIMPLE_MAGIC). */ /** The heap size. (This structure is not included!) */ /** Pointer to the end of the heap. */ /** The amount of free memory in the heap. */ /** Free head pointer. */ /** Free tail pointer. */ /** Make the size of this structure is a multiple of 32. */ /** The minimum allocation size. */ /** The minimum and default alignment. */ /******************************************************************************* * Defined Constants And Macros * *******************************************************************************/ /** Asserts that a free block is valid. */ /** Asserts that the heap anchor block is ok. */ /******************************************************************************* *******************************************************************************/ * @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. * Validate input. The imposed minimum heap size is just a convenien value. * Place the heap anchor block at the start of the heap memory, * enforce 32 byte alignment of it. Also align the heap size correctly. /* Init the heap anchor block. */ /* Init the single free block. */ * 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. * Validate and adjust the input. * 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. * Validate and adjust the input. * Allocates a block of memory from the specified heap. * No parameter validation or adjustment is preformed. * @returns Pointer to the allocated block. * @returns NULL on failure. * @param cb Size of the memory block to allocate. * @param uAlignment The alignment specifications for the allocated block. * Search for a fitting block from the lower end of the heap. * Match for size and alignment. * Make a stack copy of the free block header and adjust the pointer. * Donate offAlign bytes to the node in front of us. * If we're the head node, we'll have to create a fake node. We'll * mark it USED for simplicity. * (Should this policy of donating memory to the guy in front of us * cause big 'leaks', we could create a new free node if there is room * Recreate pFree in the new position and adjust the neighbours. * Split off a new FREE block? * Move the FREE block up to make room for the new USED block. * Update the old FREE node making it a USED node. * Link it out of the free list. * Convert it to a used block. * 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 * Get the block and heap. If in strict mode, validate these. * Call worker which does the actual job. * Free memory a memory block. * @param pHeapInt The heap. * @param pBlock The memory block to free. * Look for the closest free list blocks by walking the blocks right * of us (both list are sorted on address). * Insert at the head of the free block list? * Can we merge with left hand free block? * No, just link it into the free list then. * Can we merge with right hand free block? * Calculate the size and update free stats. * Internal consitency check (relying on assertions). * Gets the size of the specified heap block. * @returns The actual size of the heap block. * @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An invalid \a pv * can also cause traps or trigger assertions. * @param Heap The heap. This is optional and will only be used for strict assertions. * @param pv The heap block returned by RTHeapSimple * Get the block and heap. If in strict mode, validate these. * Calculate the block size. * Gets the size of the heap. * This size includes all the internal heap structures. So, even if the heap is * empty the RTHeapSimpleGetFreeSize() will never reach the heap size returned * @returns The heap size. * @returns 0 if heap was safely detected as being bad. * Returns the sum of all free heap blocks. * This is the amount of memory you can theoretically allocate * if you do allocations exactly matching the free blocks. * @returns The size of the free blocks. * @returns 0 if heap was safely detected as being bad. * Dumps the hypervisor heap. * @param Heap The heap handle. * @param pfnPrintf Printf like function that groks IPRT formatting. pfnPrintf(
"**** Dumping Heap %p - cbHeap=%zx cbFree=%zx ****\n",
pfnPrintf(
"%p %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
pfnPrintf(
"%p %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",