heapsimple.cpp revision 9d80662bfa36cc718a22f982d48148415ca95fb8
de4157257515400c2c25373591135f110227b68cvboxsync * innotek Portable Runtime - A Simple Heap.
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync * Copyright (C) 2006-2007 innotek GmbH
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * available from http://www.virtualbox.org. This file is free software;
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * you can redistribute it and/or modify it under the terms of the GNU
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * General Public License (GPL) as published by the Free Software
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
b263fac6f6e7fa933c7bfb2a45d598fe8e458c09vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
de4157257515400c2c25373591135f110227b68cvboxsync * The contents of this file may alternatively be used under the terms
de4157257515400c2c25373591135f110227b68cvboxsync * of the Common Development and Distribution License Version 1.0
de4157257515400c2c25373591135f110227b68cvboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
de4157257515400c2c25373591135f110227b68cvboxsync * VirtualBox OSE distribution, in which case the provisions of the
de4157257515400c2c25373591135f110227b68cvboxsync * CDDL are applicable instead of those of the GPL.
de4157257515400c2c25373591135f110227b68cvboxsync * You may elect to license modified versions of this file under the
de4157257515400c2c25373591135f110227b68cvboxsync * terms and conditions of either the GPL or the CDDL or both.
de4157257515400c2c25373591135f110227b68cvboxsync/*******************************************************************************
de4157257515400c2c25373591135f110227b68cvboxsync* Header Files *
de4157257515400c2c25373591135f110227b68cvboxsync*******************************************************************************/
de4157257515400c2c25373591135f110227b68cvboxsync/*******************************************************************************
de4157257515400c2c25373591135f110227b68cvboxsync* Structures and Typedefs *
de4157257515400c2c25373591135f110227b68cvboxsync*******************************************************************************/
01a4740f743b850f8337988627cd58dd2abbb81bvboxsync/** Pointer to the heap anchor block. */
de4157257515400c2c25373591135f110227b68cvboxsynctypedef struct RTHEAPSIMPLEINTERNAL *PRTHEAPSIMPLEINTERNAL;
296a2ed12c9cf6041bb8006c2223605d2f56c6c9vboxsync/** Pointer to a heap block. */
296a2ed12c9cf6041bb8006c2223605d2f56c6c9vboxsynctypedef struct RTHEAPSIMPLEBLOCK *PRTHEAPSIMPLEBLOCK;
de4157257515400c2c25373591135f110227b68cvboxsync/** Pointer to a free heap block. */
de4157257515400c2c25373591135f110227b68cvboxsync * Structure describing a simple heap block.
de4157257515400c2c25373591135f110227b68cvboxsync * If this block is allocated, it is followed by the user user data.
de4157257515400c2c25373591135f110227b68cvboxsync * If this block is free, see RTHEAPSIMPLEFREE.
590bfe12ce22cd3716448fbb9f4dc51664bfe5e2vboxsync /** The next block in the global block list. */
de4157257515400c2c25373591135f110227b68cvboxsync /** The previous block in the global block list. */
de4157257515400c2c25373591135f110227b68cvboxsync /** Pointer to the heap anchor block. */
de4157257515400c2c25373591135f110227b68cvboxsync /** Flags + magic. */
de4157257515400c2c25373591135f110227b68cvboxsync/** The block is free if this flag is set. When cleared it's allocated. */
de4157257515400c2c25373591135f110227b68cvboxsync#define RTHEAPSIMPLEBLOCK_FLAGS_FREE ((uintptr_t)RT_BIT(0))
de4157257515400c2c25373591135f110227b68cvboxsync/** The magic value. */
de4157257515400c2c25373591135f110227b68cvboxsync#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC ((uintptr_t)0xabcdef00)
de4157257515400c2c25373591135f110227b68cvboxsync/** The mask that needs to be applied to RTHEAPSIMPLEBLOCK::fFalgs to obtain the magic value. */
de4157257515400c2c25373591135f110227b68cvboxsync#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK (~(uintptr_t)RT_BIT(0))
de4157257515400c2c25373591135f110227b68cvboxsync * Checks if the specified block is valid or not.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns boolean answer.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
de4157257515400c2c25373591135f110227b68cvboxsync ( ((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK) == RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
de4157257515400c2c25373591135f110227b68cvboxsync * Checks if the specified block is valid and in use.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns boolean answer.
590bfe12ce22cd3716448fbb9f4dc51664bfe5e2vboxsync * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
de4157257515400c2c25373591135f110227b68cvboxsync ( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK | RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
de4157257515400c2c25373591135f110227b68cvboxsync * Checks if the specified block is valid and free.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns boolean answer.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
ad27e1d5e48ca41245120c331cc88b50464813cevboxsync ( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK | RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
de4157257515400c2c25373591135f110227b68cvboxsync == (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE) )
de4157257515400c2c25373591135f110227b68cvboxsync * Checks if the specified block is free or not.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns boolean answer.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pBlock Pointer to a valid RTHEAPSIMPLEBLOCK structure.
de4157257515400c2c25373591135f110227b68cvboxsync#define RTHEAPSIMPLEBLOCK_IS_FREE(pBlock) (!!((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_FREE))
de4157257515400c2c25373591135f110227b68cvboxsync * A free heap block.
de4157257515400c2c25373591135f110227b68cvboxsync * This is an extended version of RTHEAPSIMPLEBLOCK that takes the unused
de4157257515400c2c25373591135f110227b68cvboxsync * user data to store free list pointers and a cached size value.
de4157257515400c2c25373591135f110227b68cvboxsync /** Core stuff. */
590bfe12ce22cd3716448fbb9f4dc51664bfe5e2vboxsync /** Pointer to the next free block. */
de4157257515400c2c25373591135f110227b68cvboxsync /** Pointer to the previous free block. */
de4157257515400c2c25373591135f110227b68cvboxsync /** The size of the block (excluding the RTHEAPSIMPLEBLOCK part). */
de4157257515400c2c25373591135f110227b68cvboxsync /** An alignment filler to make it a multiple of (sizeof(void *) * 2). */
de4157257515400c2c25373591135f110227b68cvboxsync * The heap anchor block.
de4157257515400c2c25373591135f110227b68cvboxsync * This structure is placed at the head of the memory block specified to RTHeapSimpleInit(),
de4157257515400c2c25373591135f110227b68cvboxsync * which means that the first RTHEAPSIMPLEBLOCK appears immediately after this structure.
de4157257515400c2c25373591135f110227b68cvboxsync /** The typical magic (RTHEAPSIMPLE_MAGIC). */
de4157257515400c2c25373591135f110227b68cvboxsync /** The heap size. (This structure is not included!) */
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync /** Pointer to the end of the heap. */
de4157257515400c2c25373591135f110227b68cvboxsync /** The amount of free memory in the heap. */
de4157257515400c2c25373591135f110227b68cvboxsync /** Free head pointer. */
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync /** Free tail pointer. */
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync /** Make the size of this structure is a multiple of 32. */
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsyncAssertCompileSizeAlignment(RTHEAPSIMPLEINTERNAL, 32);
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync/** The minimum allocation size. */
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync#define RTHEAPSIMPLE_MIN_BLOCK (sizeof(RTHEAPSIMPLEBLOCK))
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsyncAssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEBLOCK));
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsyncAssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEFREE) - sizeof(RTHEAPSIMPLEBLOCK));
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync/** The minimum and default alignment. */
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync#define RTHEAPSIMPLE_ALIGNMENT (sizeof(RTHEAPSIMPLEBLOCK))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync/*******************************************************************************
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync* Defined Constants And Macros *
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync*******************************************************************************/
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync#define ASSERT_L(a, b) AssertMsg((uintptr_t)(a) < (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync#define ASSERT_LE(a, b) AssertMsg((uintptr_t)(a) <= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync#define ASSERT_G(a, b) AssertMsg((uintptr_t)(a) > (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync#define ASSERT_GE(a, b) AssertMsg((uintptr_t)(a) >= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync#define ASSERT_ALIGN(a) AssertMsg(!((uintptr_t)(a) & (RTHEAPSIMPLE_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a)))
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync Assert((pBlock) == (PRTHEAPSIMPLEBLOCK)((pHeapInt) + 1)); \
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync } while (0)
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync } while (0)
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID(pBlock), ("%#x\n", (pBlock)->fFlags)); \
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync } while (0)
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID_USED((pBlock)), ("%#x\n", (pBlock)->fFlags)); \
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
3d3defbbc6d46d5bbb80fca96508b609ef983948vboxsync } while (0)
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync ASSERT_GE((pBlock)->pPrev, (pHeapInt)->pFreeHead); \
b341bcbb341f01cceb1767c9e45fb6ecf161a46evboxsync ASSERT_LE((pBlock)->pPrev, (pBlock)->Core.pPrev); \
de4157257515400c2c25373591135f110227b68cvboxsync } while (0)
de4157257515400c2c25373591135f110227b68cvboxsync ASSERT_LE((pBlock)->pNext, (pHeapInt)->pFreeTail); \
de4157257515400c2c25373591135f110227b68cvboxsync ASSERT_GE((pBlock)->pNext, (pBlock)->Core.pNext); \
de4157257515400c2c25373591135f110227b68cvboxsync } while (0)
de4157257515400c2c25373591135f110227b68cvboxsync do { size_t cbCalc = ((pBlock)->Core.pNext ? (uintptr_t)(pBlock)->Core.pNext : (uintptr_t)(pHeapInt)->pvEnd) \
de4157257515400c2c25373591135f110227b68cvboxsync - (uintptr_t)(pBlock) - sizeof(RTHEAPSIMPLEBLOCK); \
de4157257515400c2c25373591135f110227b68cvboxsync AssertMsg((pBlock)->cb == cbCalc, ("cb=%#zx cbCalc=%#zx\n", (pBlock)->cb, cbCalc)); \
de4157257515400c2c25373591135f110227b68cvboxsync } while (0)
de4157257515400c2c25373591135f110227b68cvboxsync# define ASSERT_FREE_CB(pHeapInt, pBlock) do {} while (0)
2a047f0d7ee5964456dbc4dec9925031482588abvboxsync/** Asserts that a free block is valid. */
de4157257515400c2c25373591135f110227b68cvboxsync Assert(RTHEAPSIMPLEBLOCK_IS_VALID_FREE(&(pBlock)->Core)); \
de4157257515400c2c25373591135f110227b68cvboxsync } while (0)
de4157257515400c2c25373591135f110227b68cvboxsync/** Asserts that the heap anchor block is ok. */
de4157257515400c2c25373591135f110227b68cvboxsync Assert((pHeapInt)->uMagic == RTHEAPSIMPLE_MAGIC); \
de4157257515400c2c25373591135f110227b68cvboxsync } while (0)
de4157257515400c2c25373591135f110227b68cvboxsync/*******************************************************************************
de4157257515400c2c25373591135f110227b68cvboxsync* Internal Functions *
de4157257515400c2c25373591135f110227b68cvboxsync*******************************************************************************/
de4157257515400c2c25373591135f110227b68cvboxsyncstatic void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt);
de4157257515400c2c25373591135f110227b68cvboxsyncstatic PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment);
de4157257515400c2c25373591135f110227b68cvboxsyncstatic void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock);
de4157257515400c2c25373591135f110227b68cvboxsync * Initializes the heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns IPRT status code on success.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pHeap Where to store the heap anchor block on success.
2a047f0d7ee5964456dbc4dec9925031482588abvboxsync * @param pvMemory Pointer to the heap memory.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cbMemory The size of the heap memory.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE pHeap, void *pvMemory, size_t cbMemory)
de4157257515400c2c25373591135f110227b68cvboxsync unsigned i;
de4157257515400c2c25373591135f110227b68cvboxsync * Validate input. The imposed minimum heap size is just a convenien value.
de4157257515400c2c25373591135f110227b68cvboxsync AssertReturn(cbMemory >= PAGE_SIZE, VERR_INVALID_PARAMETER);
de4157257515400c2c25373591135f110227b68cvboxsync AssertReturn((uintptr_t)pvMemory + (cbMemory - 1) > (uintptr_t)cbMemory, VERR_INVALID_PARAMETER);
de4157257515400c2c25373591135f110227b68cvboxsync * Place the heap anchor block at the start of the heap memory,
de4157257515400c2c25373591135f110227b68cvboxsync * enforce 32 byte alignment of it. Also align the heap size correctly.
de4157257515400c2c25373591135f110227b68cvboxsync const unsigned off = 32 - ((uintptr_t)pvMemory & 31);
de4157257515400c2c25373591135f110227b68cvboxsync pHeapInt = (PRTHEAPSIMPLEINTERNAL)((uintptr_t)pvMemory + off);
de4157257515400c2c25373591135f110227b68cvboxsync /* Init the heap anchor block. */
de4157257515400c2c25373591135f110227b68cvboxsync pHeapInt->pFreeTail = pHeapInt->pFreeHead = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
c0b6af690ad705bddfa87c643b89770a7a0aaf5avboxsync for (i = 0; i < ELEMENTS(pHeapInt->auAlignment); i++)
de4157257515400c2c25373591135f110227b68cvboxsync /* Init the single free block. */
de4157257515400c2c25373591135f110227b68cvboxsync pFree->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync * Allocates memory from the specified simple heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns Pointer to the allocated memory block on success.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap to allocate the memory on.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cb The requested heap block size.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
de4157257515400c2c25373591135f110227b68cvboxsync * Must be a power of 2.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
de4157257515400c2c25373591135f110227b68cvboxsync * Validate and adjust the input.
de4157257515400c2c25373591135f110227b68cvboxsync Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
de4157257515400c2c25373591135f110227b68cvboxsync * Do the allocation.
de4157257515400c2c25373591135f110227b68cvboxsync pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
de4157257515400c2c25373591135f110227b68cvboxsync * Allocates zeroed memory from the specified simple heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns Pointer to the allocated memory block on success.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap to allocate the memory on.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cb The requested heap block size.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
de4157257515400c2c25373591135f110227b68cvboxsync * Must be a power of 2.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
de4157257515400c2c25373591135f110227b68cvboxsync * Validate and adjust the input.
de4157257515400c2c25373591135f110227b68cvboxsync Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
de4157257515400c2c25373591135f110227b68cvboxsync * Do the allocation.
de4157257515400c2c25373591135f110227b68cvboxsync pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
de4157257515400c2c25373591135f110227b68cvboxsync * Allocates a block of memory from the specified heap.
de4157257515400c2c25373591135f110227b68cvboxsync * No parameter validation or adjustment is preformed.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns Pointer to the allocated block.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns NULL on failure.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pHeapInt The heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @param cb Size of the memory block to allocate.
de4157257515400c2c25373591135f110227b68cvboxsync * @param uAlignment The alignment specifications for the allocated block.
de4157257515400c2c25373591135f110227b68cvboxsyncstatic PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment)
9127c416edfd6f9266e387f7abd7aa9904eecbc9vboxsync * Search for a fitting block from the lower end of the heap.
de4157257515400c2c25373591135f110227b68cvboxsync * Match for size and alignment.
108e1eed4a717344ddcec74bcae3ea793fda4724vboxsync offAlign = (uintptr_t)(&pFree->Core + 1) & (uAlignment - 1);
de4157257515400c2c25373591135f110227b68cvboxsync * Make a stack copy of the free block header and adjust the pointer.
de4157257515400c2c25373591135f110227b68cvboxsync pFree = (PRTHEAPSIMPLEFREE)((uintptr_t)pFree + offAlign);
de4157257515400c2c25373591135f110227b68cvboxsync * Donate offAlign bytes to the node in front of us.
de4157257515400c2c25373591135f110227b68cvboxsync * If we're the head node, we'll have to create a fake node. We'll
de4157257515400c2c25373591135f110227b68cvboxsync * mark it USED for simplicity.
de4157257515400c2c25373591135f110227b68cvboxsync * (Should this policy of donating memory to the guy in front of us
de4157257515400c2c25373591135f110227b68cvboxsync * cause big 'leaks', we could create a new free node if there is room
de4157257515400c2c25373591135f110227b68cvboxsync * for that.)
de4157257515400c2c25373591135f110227b68cvboxsync AssertMsg(!RTHEAPSIMPLEBLOCK_IS_FREE(pPrev), ("Impossible!\n"));
de4157257515400c2c25373591135f110227b68cvboxsync * Recreate pFree in the new position and adjust the neighbours.
de4157257515400c2c25373591135f110227b68cvboxsync /* the core */
de4157257515400c2c25373591135f110227b68cvboxsync /* the free part */
de4157257515400c2c25373591135f110227b68cvboxsync * Split off a new FREE block?
de4157257515400c2c25373591135f110227b68cvboxsync if (pFree->cb >= cb + RT_ALIGN_Z(sizeof(RTHEAPSIMPLEFREE), RTHEAPSIMPLE_ALIGNMENT))
de4157257515400c2c25373591135f110227b68cvboxsync * Move the FREE block up to make room for the new USED block.
de4157257515400c2c25373591135f110227b68cvboxsync PRTHEAPSIMPLEFREE pNew = (PRTHEAPSIMPLEFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPSIMPLEBLOCK));
de4157257515400c2c25373591135f110227b68cvboxsync pNew->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync pNew->cb = (pNew->Core.pNext ? (uintptr_t)pNew->Core.pNext : (uintptr_t)pHeapInt->pvEnd) \
de4157257515400c2c25373591135f110227b68cvboxsync * Update the old FREE node making it a USED node.
de4157257515400c2c25373591135f110227b68cvboxsync pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync * Link it out of the free list.
de4157257515400c2c25373591135f110227b68cvboxsync * Convert it to a used block.
de4157257515400c2c25373591135f110227b68cvboxsync pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync * Frees memory allocated from a simple heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap. This is optional and will only be used for strict assertions.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pv The heap block returned by RTHeapSimple
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE Heap, void *pv)
de4157257515400c2c25373591135f110227b68cvboxsync * Validate input.
de4157257515400c2c25373591135f110227b68cvboxsync Assert(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv);
de4157257515400c2c25373591135f110227b68cvboxsync * Get the block and heap. If in strict mode, validate these.
de4157257515400c2c25373591135f110227b68cvboxsync Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)Heap || !Heap);
de4157257515400c2c25373591135f110227b68cvboxsync * Poison the block.
de4157257515400c2c25373591135f110227b68cvboxsync const size_t cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
de4157257515400c2c25373591135f110227b68cvboxsync memset(pBlock + 1, RTHEAPSIMPLE_FREE_POISON, cbBlock);
de4157257515400c2c25373591135f110227b68cvboxsync * Call worker which does the actual job.
de4157257515400c2c25373591135f110227b68cvboxsync * Free memory a memory block.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pHeapInt The heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pBlock The memory block to free.
de4157257515400c2c25373591135f110227b68cvboxsyncstatic void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock)
de4157257515400c2c25373591135f110227b68cvboxsync PRTHEAPSIMPLEFREE pFree = (PRTHEAPSIMPLEFREE)pBlock;
de4157257515400c2c25373591135f110227b68cvboxsync * Look for the closest free list blocks by walking the blocks right
de4157257515400c2c25373591135f110227b68cvboxsync * of us (both list are sorted on address).
de4157257515400c2c25373591135f110227b68cvboxsync while (pRight && !RTHEAPSIMPLEBLOCK_IS_FREE(&pRight->Core))
5f809eed9fe4d8f7f317e8102657eb877fd5fbdavboxsync AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock));
5f809eed9fe4d8f7f317e8102657eb877fd5fbdavboxsync Assert(!pRight || (uintptr_t)pRight > (uintptr_t)pFree);
5f809eed9fe4d8f7f317e8102657eb877fd5fbdavboxsync * Insert at the head of the free block list?
5f809eed9fe4d8f7f317e8102657eb877fd5fbdavboxsync pFree->Core.fFlags |= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync * Can we merge with left hand free block?
de4157257515400c2c25373591135f110227b68cvboxsync * No, just link it into the free list then.
de4157257515400c2c25373591135f110227b68cvboxsync pFree->Core.fFlags |= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
de4157257515400c2c25373591135f110227b68cvboxsync * Can we merge with right hand free block?
de4157257515400c2c25373591135f110227b68cvboxsync * Calculate the size and update free stats.
de4157257515400c2c25373591135f110227b68cvboxsync pFree->cb = (pFree->Core.pNext ? (uintptr_t)pFree->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
de4157257515400c2c25373591135f110227b68cvboxsync * Internal consitency check (relying on assertions).
de4157257515400c2c25373591135f110227b68cvboxsync * @param pHeapInt
de4157257515400c2c25373591135f110227b68cvboxsyncstatic void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt)
de4157257515400c2c25373591135f110227b68cvboxsync Assert(pPrevFree || pHeapInt->pFreeHead == pBlock);
de4157257515400c2c25373591135f110227b68cvboxsync Assert(!pPrev || pPrev == (PRTHEAPSIMPLEFREE)pBlock->Core.pPrev);
de4157257515400c2c25373591135f110227b68cvboxsync * Gets the size of the specified heap block.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns The actual size of the heap block.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An invalid \a pv
de4157257515400c2c25373591135f110227b68cvboxsync * can also cause traps or trigger assertions.
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap. This is optional and will only be used for strict assertions.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pv The heap block returned by RTHeapSimple
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE Heap, void *pv)
de4157257515400c2c25373591135f110227b68cvboxsync * Validate input.
de4157257515400c2c25373591135f110227b68cvboxsync AssertReturn(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv, 0);
de4157257515400c2c25373591135f110227b68cvboxsync * Get the block and heap. If in strict mode, validate these.
de4157257515400c2c25373591135f110227b68cvboxsync Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)Heap || !Heap);
de4157257515400c2c25373591135f110227b68cvboxsync * Calculate the block size.
de4157257515400c2c25373591135f110227b68cvboxsync cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
de4157257515400c2c25373591135f110227b68cvboxsync * Gets the size of the heap.
de4157257515400c2c25373591135f110227b68cvboxsync * This size includes all the internal heap structures. So, even if the heap is
de4157257515400c2c25373591135f110227b68cvboxsync * empty the RTHeapSimpleGetFreeSize() will never reach the heap size returned
de4157257515400c2c25373591135f110227b68cvboxsync * by this function.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns The heap size.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns 0 if heap was safely detected as being bad.
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE Heap)
de4157257515400c2c25373591135f110227b68cvboxsync * Returns the sum of all free heap blocks.
de4157257515400c2c25373591135f110227b68cvboxsync * This is the amount of memory you can theoretically allocate
de4157257515400c2c25373591135f110227b68cvboxsync * if you do allocations exactly matching the free blocks.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns The size of the free blocks.
de4157257515400c2c25373591135f110227b68cvboxsync * @returns 0 if heap was safely detected as being bad.
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE Heap)
de4157257515400c2c25373591135f110227b68cvboxsync * Dumps the hypervisor heap.
de4157257515400c2c25373591135f110227b68cvboxsync * @param Heap The heap handle.
de4157257515400c2c25373591135f110227b68cvboxsync * @param pfnPrintf Printf like function that groks IPRT formatting.
de4157257515400c2c25373591135f110227b68cvboxsyncRTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE Heap, PFNRTHEAPSIMPLEPRINTF pfnPrintf)
de4157257515400c2c25373591135f110227b68cvboxsync PRTHEAPSIMPLEINTERNAL pHeapInt = (PRTHEAPSIMPLEINTERNAL)Heap;
de4157257515400c2c25373591135f110227b68cvboxsync pfnPrintf("**** Dumping Heap %p - cbHeap=%zx cbFree=%zx ****\n",
22f8a6ac3bcf3e3c8aa1f275097d6f7ce392195bvboxsync size_t cb = (pBlock->pNext ? (uintptr_t)pBlock->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
1fa6e123716bad466cddb3c25227616b1c87ab83vboxsync pfnPrintf("%p %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
22f8a6ac3bcf3e3c8aa1f275097d6f7ce392195bvboxsync pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb,
22f8a6ac3bcf3e3c8aa1f275097d6f7ce392195bvboxsync pfnPrintf("%p %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",
22f8a6ac3bcf3e3c8aa1f275097d6f7ce392195bvboxsync pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb);
22f8a6ac3bcf3e3c8aa1f275097d6f7ce392195bvboxsync pfnPrintf("**** Done dumping Heap %p ****\n", Heap);