Adding upstream version 6.0.4-dfsg.upstream/6.0.4-dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 920 insertions, 0 deletions

diff --git a/src/VBox/Runtime/common/alloc/heapsimple.cpp b/src/VBox/Runtime/common/alloc/heapsimple.cpp
new file mode 100644
index 00000000..22d5cbcb
--- /dev/null
+++ b/src/VBox/Runtime/common/alloc/heapsimple.cpp
@@ -0,0 +1,920 @@
+/* $Id: heapsimple.cpp $ */
+/** @file
+ * IPRT - A Simple Heap.
+ */
+
+/*
+ * Copyright (C) 2006-2019 Oracle Corporation
+ *
+ * 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 (GPL) 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.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
+ * VirtualBox OSE distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ */
+
+
+/*********************************************************************************************************************************
+*   Header Files                                                                                                                 *
+*********************************************************************************************************************************/
+#define LOG_GROUP RTLOGGROUP_DEFAULT
+#include <iprt/heap.h>
+#include "internal/iprt.h"
+
+#include <iprt/assert.h>
+#include <iprt/asm.h>
+#include <iprt/errcore.h>
+#include <iprt/log.h>
+#include <iprt/string.h>
+#include <iprt/param.h>
+
+#include "internal/magics.h"
+
+
+/*********************************************************************************************************************************
+*   Structures and Typedefs                                                                                                      *
+*********************************************************************************************************************************/
+/** Pointer to the heap anchor block. */
+typedef struct RTHEAPSIMPLEINTERNAL *PRTHEAPSIMPLEINTERNAL;
+/** Pointer to a heap block. */
+typedef struct RTHEAPSIMPLEBLOCK *PRTHEAPSIMPLEBLOCK;
+/** Pointer to a free heap block. */
+typedef struct RTHEAPSIMPLEFREE *PRTHEAPSIMPLEFREE;
+
+/**
+ * Structure describing a simple heap block.
+ * If this block is allocated, it is followed by the user data.
+ * If this block is free, see RTHEAPSIMPLEFREE.
+ */
+typedef struct RTHEAPSIMPLEBLOCK
+{
+    /** The next block in the global block list. */
+    PRTHEAPSIMPLEBLOCK      pNext;
+    /** The previous block in the global block list. */
+    PRTHEAPSIMPLEBLOCK      pPrev;
+    /** Pointer to the heap anchor block. */
+    PRTHEAPSIMPLEINTERNAL   pHeap;
+    /** Flags + magic. */
+    uintptr_t               fFlags;
+} RTHEAPSIMPLEBLOCK;
+AssertCompileSizeAlignment(RTHEAPSIMPLEBLOCK, 16);
+
+/** The block is free if this flag is set. When cleared it's allocated. */
+#define RTHEAPSIMPLEBLOCK_FLAGS_FREE        ((uintptr_t)RT_BIT(0))
+/** The magic value. */
+#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC       ((uintptr_t)0xabcdef00)
+/** The mask that needs to be applied to RTHEAPSIMPLEBLOCK::fFlags to obtain the magic value. */
+#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK  (~(uintptr_t)RT_BIT(0))
+
+/**
+ * Checks if the specified block is valid or not.
+ * @returns boolean answer.
+ * @param   pBlock      Pointer to a RTHEAPSIMPLEBLOCK structure.
+ */
+#define RTHEAPSIMPLEBLOCK_IS_VALID(pBlock)  \
+    ( ((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK) == RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
+
+/**
+ * Checks if the specified block is valid and in use.
+ * @returns boolean answer.
+ * @param   pBlock      Pointer to a RTHEAPSIMPLEBLOCK structure.
+ */
+#define RTHEAPSIMPLEBLOCK_IS_VALID_USED(pBlock)  \
+    ( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK | RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
+       == RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
+
+/**
+ * Checks if the specified block is valid and free.
+ * @returns boolean answer.
+ * @param   pBlock      Pointer to a RTHEAPSIMPLEBLOCK structure.
+ */
+#define RTHEAPSIMPLEBLOCK_IS_VALID_FREE(pBlock)  \
+    ( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK | RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
+       == (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE) )
+
+/**
+ * Checks if the specified block is free or not.
+ * @returns boolean answer.
+ * @param   pBlock      Pointer to a valid RTHEAPSIMPLEBLOCK structure.
+ */
+#define RTHEAPSIMPLEBLOCK_IS_FREE(pBlock)   (!!((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_FREE))
+
+/**
+ * A free heap block.
+ * This is an extended version of RTHEAPSIMPLEBLOCK that takes the unused
+ * user data to store free list pointers and a cached size value.
+ */
+typedef struct RTHEAPSIMPLEFREE
+{
+    /** Core stuff. */
+    RTHEAPSIMPLEBLOCK       Core;
+    /** Pointer to the next free block. */
+    PRTHEAPSIMPLEFREE       pNext;
+    /** Pointer to the previous free block. */
+    PRTHEAPSIMPLEFREE       pPrev;
+    /** The size of the block (excluding the RTHEAPSIMPLEBLOCK part). */
+    size_t                  cb;
+    /** An alignment filler to make it a multiple of (sizeof(void *) * 2). */
+    size_t                  Alignment;
+} RTHEAPSIMPLEFREE;
+
+
+/**
+ * The heap anchor block.
+ * 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.
+ */
+typedef struct RTHEAPSIMPLEINTERNAL
+{
+    /** The typical magic (RTHEAPSIMPLE_MAGIC). */
+    size_t                  uMagic;
+    /** The heap size. (This structure is included!) */
+    size_t                  cbHeap;
+    /** Pointer to the end of the heap. */
+    void                   *pvEnd;
+    /** The amount of free memory in the heap. */
+    size_t                  cbFree;
+    /** Free head pointer. */
+    PRTHEAPSIMPLEFREE       pFreeHead;
+    /** Free tail pointer. */
+    PRTHEAPSIMPLEFREE       pFreeTail;
+    /** Make the size of this structure is a multiple of 32. */
+    size_t                  auAlignment[2];
+} RTHEAPSIMPLEINTERNAL;
+AssertCompileSizeAlignment(RTHEAPSIMPLEINTERNAL, 32);
+
+
+/** The minimum allocation size. */
+#define RTHEAPSIMPLE_MIN_BLOCK  (sizeof(RTHEAPSIMPLEBLOCK))
+AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEBLOCK));
+AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEFREE) - sizeof(RTHEAPSIMPLEBLOCK));
+
+/** The minimum and default alignment.  */
+#define RTHEAPSIMPLE_ALIGNMENT  (sizeof(RTHEAPSIMPLEBLOCK))
+
+
+/*********************************************************************************************************************************
+*   Defined Constants And Macros                                                                                                 *
+*********************************************************************************************************************************/
+#ifdef RT_STRICT
+# define RTHEAPSIMPLE_STRICT 1
+#endif
+
+#define ASSERT_L(a, b)    AssertMsg((uintptr_t)(a) <  (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
+#define ASSERT_LE(a, b)   AssertMsg((uintptr_t)(a) <= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
+#define ASSERT_G(a, b)    AssertMsg((uintptr_t)(a) >  (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
+#define ASSERT_GE(a, b)   AssertMsg((uintptr_t)(a) >= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
+#define ASSERT_ALIGN(a)   AssertMsg(!((uintptr_t)(a) & (RTHEAPSIMPLE_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a)))
+
+#define ASSERT_PREV(pHeapInt, pBlock)  \
+    do { ASSERT_ALIGN((pBlock)->pPrev); \
+         if ((pBlock)->pPrev) \
+         { \
+             ASSERT_L((pBlock)->pPrev, (pBlock)); \
+             ASSERT_GE((pBlock)->pPrev, (pHeapInt) + 1); \
+         } \
+         else \
+             Assert((pBlock) == (PRTHEAPSIMPLEBLOCK)((pHeapInt) + 1)); \
+    } while (0)
+
+#define ASSERT_NEXT(pHeap, pBlock) \
+    do { ASSERT_ALIGN((pBlock)->pNext); \
+         if ((pBlock)->pNext) \
+         { \
+             ASSERT_L((pBlock)->pNext, (pHeapInt)->pvEnd); \
+             ASSERT_G((pBlock)->pNext, (pBlock)); \
+         } \
+    } while (0)
+
+#define ASSERT_BLOCK(pHeapInt, pBlock) \
+    do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID(pBlock), ("%#x\n", (pBlock)->fFlags)); \
+         AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
+         ASSERT_GE((pBlock), (pHeapInt) + 1); \
+         ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
+         ASSERT_NEXT(pHeapInt, pBlock); \
+         ASSERT_PREV(pHeapInt, pBlock); \
+    } while (0)
+
+#define ASSERT_BLOCK_USED(pHeapInt, pBlock) \
+    do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID_USED((pBlock)), ("%#x\n", (pBlock)->fFlags)); \
+         AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
+         ASSERT_GE((pBlock), (pHeapInt) + 1); \
+         ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
+         ASSERT_NEXT(pHeapInt, pBlock); \
+         ASSERT_PREV(pHeapInt, pBlock); \
+    } while (0)
+
+#define ASSERT_FREE_PREV(pHeapInt, pBlock) \
+    do { ASSERT_ALIGN((pBlock)->pPrev); \
+         if ((pBlock)->pPrev) \
+         { \
+             ASSERT_GE((pBlock)->pPrev, (pHeapInt)->pFreeHead); \
+             ASSERT_L((pBlock)->pPrev, (pBlock)); \
+             ASSERT_LE((pBlock)->pPrev, (pBlock)->Core.pPrev); \
+         } \
+         else \
+             Assert((pBlock) == (pHeapInt)->pFreeHead); \
+    } while (0)
+
+#define ASSERT_FREE_NEXT(pHeapInt, pBlock) \
+    do { ASSERT_ALIGN((pBlock)->pNext); \
+         if ((pBlock)->pNext) \
+         { \
+             ASSERT_LE((pBlock)->pNext, (pHeapInt)->pFreeTail); \
+             ASSERT_G((pBlock)->pNext, (pBlock)); \
+             ASSERT_GE((pBlock)->pNext, (pBlock)->Core.pNext); \
+         } \
+         else \
+             Assert((pBlock) == (pHeapInt)->pFreeTail); \
+    } while (0)
+
+#ifdef RTHEAPSIMPLE_STRICT
+# define ASSERT_FREE_CB(pHeapInt, pBlock) \
+    do { size_t cbCalc = ((pBlock)->Core.pNext ? (uintptr_t)(pBlock)->Core.pNext : (uintptr_t)(pHeapInt)->pvEnd) \
+                       - (uintptr_t)(pBlock) - sizeof(RTHEAPSIMPLEBLOCK); \
+         AssertMsg((pBlock)->cb == cbCalc, ("cb=%#zx cbCalc=%#zx\n", (pBlock)->cb, cbCalc)); \
+    } while (0)
+#else
+# define ASSERT_FREE_CB(pHeapInt, pBlock) do {} while (0)
+#endif
+
+/** Asserts that a free block is valid. */
+#define ASSERT_BLOCK_FREE(pHeapInt, pBlock) \
+    do { ASSERT_BLOCK(pHeapInt, &(pBlock)->Core); \
+         Assert(RTHEAPSIMPLEBLOCK_IS_VALID_FREE(&(pBlock)->Core)); \
+         ASSERT_GE((pBlock), (pHeapInt)->pFreeHead); \
+         ASSERT_LE((pBlock), (pHeapInt)->pFreeTail); \
+         ASSERT_FREE_NEXT(pHeapInt, pBlock); \
+         ASSERT_FREE_PREV(pHeapInt, pBlock); \
+         ASSERT_FREE_CB(pHeapInt, pBlock); \
+    } while (0)
+
+/** Asserts that the heap anchor block is ok. */
+#define ASSERT_ANCHOR(pHeapInt) \
+    do { AssertPtr(pHeapInt);\
+         Assert((pHeapInt)->uMagic == RTHEAPSIMPLE_MAGIC); \
+    } while (0)
+
+
+/*********************************************************************************************************************************
+*   Internal Functions                                                                                                           *
+*********************************************************************************************************************************/
+#ifdef RTHEAPSIMPLE_STRICT
+static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt);
+#endif
+static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment);
+static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock);
+
+
+RTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE phHeap, void *pvMemory, size_t cbMemory)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt;
+    PRTHEAPSIMPLEFREE pFree;
+    unsigned i;
+
+    /*
+     * Validate input. The imposed minimum heap size is just a convenient value.
+     */
+    AssertReturn(cbMemory >= PAGE_SIZE, VERR_INVALID_PARAMETER);
+    AssertPtrReturn(pvMemory, VERR_INVALID_POINTER);
+    AssertReturn((uintptr_t)pvMemory + (cbMemory - 1) > (uintptr_t)cbMemory, VERR_INVALID_PARAMETER);
+
+    /*
+     * Place the heap anchor block at the start of the heap memory,
+     * enforce 32 byte alignment of it. Also align the heap size correctly.
+     */
+    pHeapInt = (PRTHEAPSIMPLEINTERNAL)pvMemory;
+    if ((uintptr_t)pvMemory & 31)
+    {
+        const uintptr_t off = 32 - ((uintptr_t)pvMemory & 31);
+        cbMemory -= off;
+        pHeapInt = (PRTHEAPSIMPLEINTERNAL)((uintptr_t)pvMemory + off);
+    }
+    cbMemory &= ~(RTHEAPSIMPLE_ALIGNMENT - 1);
+
+
+    /* Init the heap anchor block. */
+    pHeapInt->uMagic = RTHEAPSIMPLE_MAGIC;
+    pHeapInt->pvEnd = (uint8_t *)pHeapInt + cbMemory;
+    pHeapInt->cbHeap = cbMemory;
+    pHeapInt->cbFree = cbMemory
+                     - sizeof(RTHEAPSIMPLEBLOCK)
+                     - sizeof(RTHEAPSIMPLEINTERNAL);
+    pHeapInt->pFreeTail = pHeapInt->pFreeHead = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
+    for (i = 0; i < RT_ELEMENTS(pHeapInt->auAlignment); i++)
+        pHeapInt->auAlignment[i] = ~(size_t)0;
+
+    /* Init the single free block. */
+    pFree = pHeapInt->pFreeHead;
+    pFree->Core.pNext = NULL;
+    pFree->Core.pPrev = NULL;
+    pFree->Core.pHeap = pHeapInt;
+    pFree->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+    pFree->pNext = NULL;
+    pFree->pPrev = NULL;
+    pFree->cb = pHeapInt->cbFree;
+
+    *phHeap = pHeapInt;
+
+#ifdef RTHEAPSIMPLE_STRICT
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+    return VINF_SUCCESS;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleInit);
+
+
+RTDECL(int) RTHeapSimpleRelocate(RTHEAPSIMPLE hHeap, uintptr_t offDelta)
+{
+    PRTHEAPSIMPLEINTERNAL   pHeapInt = hHeap;
+    PRTHEAPSIMPLEFREE       pCur;
+
+    /*
+     * Validate input.
+     */
+    AssertPtrReturn(pHeapInt, VERR_INVALID_HANDLE);
+    AssertReturn(pHeapInt->uMagic == RTHEAPSIMPLE_MAGIC, VERR_INVALID_HANDLE);
+    AssertMsgReturn((uintptr_t)pHeapInt - (uintptr_t)pHeapInt->pvEnd + pHeapInt->cbHeap == offDelta,
+                    ("offDelta=%p, expected=%p\n", offDelta, (uintptr_t)pHeapInt->pvEnd - pHeapInt->cbHeap - (uintptr_t)pHeapInt),
+                    VERR_INVALID_PARAMETER);
+
+    /*
+     * Relocate the heap anchor block.
+     */
+#define RELOCATE_IT(var, type, offDelta)    do { if (RT_UNLIKELY((var) != NULL)) { (var) = (type)((uintptr_t)(var) + offDelta); } } while (0)
+    RELOCATE_IT(pHeapInt->pvEnd,     void *,            offDelta);
+    RELOCATE_IT(pHeapInt->pFreeHead, PRTHEAPSIMPLEFREE, offDelta);
+    RELOCATE_IT(pHeapInt->pFreeTail, PRTHEAPSIMPLEFREE, offDelta);
+
+    /*
+     * Walk the heap blocks.
+     */
+    for (pCur = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
+         pCur && (uintptr_t)pCur < (uintptr_t)pHeapInt->pvEnd;
+         pCur = (PRTHEAPSIMPLEFREE)pCur->Core.pNext)
+    {
+        RELOCATE_IT(pCur->Core.pNext, PRTHEAPSIMPLEBLOCK,    offDelta);
+        RELOCATE_IT(pCur->Core.pPrev, PRTHEAPSIMPLEBLOCK,    offDelta);
+        RELOCATE_IT(pCur->Core.pHeap, PRTHEAPSIMPLEINTERNAL, offDelta);
+        if (RTHEAPSIMPLEBLOCK_IS_FREE(&pCur->Core))
+        {
+            RELOCATE_IT(pCur->pNext, PRTHEAPSIMPLEFREE, offDelta);
+            RELOCATE_IT(pCur->pPrev, PRTHEAPSIMPLEFREE, offDelta);
+        }
+    }
+#undef RELOCATE_IT
+
+#ifdef RTHEAPSIMPLE_STRICT
+    /*
+     * Give it a once over before we return.
+     */
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+    return VINF_SUCCESS;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleRelocate);
+
+
+RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE hHeap, size_t cb, size_t cbAlignment)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
+    PRTHEAPSIMPLEBLOCK pBlock;
+
+    /*
+     * Validate and adjust the input.
+     */
+    AssertPtrReturn(pHeapInt, NULL);
+    if (cb < RTHEAPSIMPLE_MIN_BLOCK)
+        cb = RTHEAPSIMPLE_MIN_BLOCK;
+    else
+        cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
+    if (!cbAlignment)
+        cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
+    else
+    {
+        Assert(!(cbAlignment & (cbAlignment - 1)));
+        Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
+        if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
+            cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
+    }
+
+    /*
+     * Do the allocation.
+     */
+    pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
+    if (RT_LIKELY(pBlock))
+    {
+        void *pv = pBlock + 1;
+        return pv;
+    }
+    return NULL;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleAlloc);
+
+
+RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE hHeap, size_t cb, size_t cbAlignment)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
+    PRTHEAPSIMPLEBLOCK pBlock;
+
+    /*
+     * Validate and adjust the input.
+     */
+    AssertPtrReturn(pHeapInt, NULL);
+    if (cb < RTHEAPSIMPLE_MIN_BLOCK)
+        cb = RTHEAPSIMPLE_MIN_BLOCK;
+    else
+        cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
+    if (!cbAlignment)
+        cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
+    else
+    {
+        Assert(!(cbAlignment & (cbAlignment - 1)));
+        Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
+        if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
+            cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
+    }
+
+    /*
+     * Do the allocation.
+     */
+    pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
+    if (RT_LIKELY(pBlock))
+    {
+        void *pv = pBlock + 1;
+        memset(pv, 0, cb);
+        return pv;
+    }
+    return NULL;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleAllocZ);
+
+
+/**
+ * Allocates a block of memory from the specified heap.
+ *
+ * No parameter validation or adjustment is performed.
+ *
+ * @returns Pointer to the allocated block.
+ * @returns NULL on failure.
+ *
+ * @param   pHeapInt    The heap.
+ * @param   cb          Size of the memory block to allocate.
+ * @param   uAlignment  The alignment specifications for the allocated block.
+ */
+static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment)
+{
+    PRTHEAPSIMPLEBLOCK  pRet = NULL;
+    PRTHEAPSIMPLEFREE   pFree;
+
+#ifdef RTHEAPSIMPLE_STRICT
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+
+    /*
+     * Search for a fitting block from the lower end of the heap.
+     */
+    for (pFree = pHeapInt->pFreeHead;
+         pFree;
+         pFree = pFree->pNext)
+    {
+        uintptr_t offAlign;
+        ASSERT_BLOCK_FREE(pHeapInt, pFree);
+
+        /*
+         * Match for size and alignment.
+         */
+        if (pFree->cb < cb)
+            continue;
+        offAlign = (uintptr_t)(&pFree->Core + 1) & (uAlignment - 1);
+        if (offAlign)
+        {
+            RTHEAPSIMPLEFREE Free;
+            PRTHEAPSIMPLEBLOCK pPrev;
+
+            offAlign = uAlignment - offAlign;
+            if (pFree->cb - offAlign < cb)
+                continue;
+
+            /*
+             * Make a stack copy of the free block header and adjust the pointer.
+             */
+            Free = *pFree;
+            pFree = (PRTHEAPSIMPLEFREE)((uintptr_t)pFree + offAlign);
+
+            /*
+             * 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
+             * for that.)
+             */
+            pPrev = Free.Core.pPrev;
+            if (pPrev)
+            {
+                AssertMsg(!RTHEAPSIMPLEBLOCK_IS_FREE(pPrev), ("Impossible!\n"));
+                pPrev->pNext = &pFree->Core;
+            }
+            else
+            {
+                pPrev = (PRTHEAPSIMPLEBLOCK)(pHeapInt + 1);
+                Assert(pPrev == &pFree->Core);
+                pPrev->pPrev = NULL;
+                pPrev->pNext = &pFree->Core;
+                pPrev->pHeap = pHeapInt;
+                pPrev->fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC;
+            }
+            pHeapInt->cbFree -= offAlign;
+
+            /*
+             * Recreate pFree in the new position and adjust the neighbors.
+             */
+            *pFree = Free;
+
+            /* the core */
+            if (pFree->Core.pNext)
+                pFree->Core.pNext->pPrev = &pFree->Core;
+            pFree->Core.pPrev = pPrev;
+
+            /* the free part */
+            pFree->cb -= offAlign;
+            if (pFree->pNext)
+                pFree->pNext->pPrev = pFree;
+            else
+                pHeapInt->pFreeTail = pFree;
+            if (pFree->pPrev)
+                pFree->pPrev->pNext = pFree;
+            else
+                pHeapInt->pFreeHead = pFree;
+            ASSERT_BLOCK_FREE(pHeapInt, pFree);
+            ASSERT_BLOCK_USED(pHeapInt, pPrev);
+        }
+
+        /*
+         * Split off a new FREE block?
+         */
+        if (pFree->cb >= cb + RT_ALIGN_Z(sizeof(RTHEAPSIMPLEFREE), RTHEAPSIMPLE_ALIGNMENT))
+        {
+            /*
+             * Move the FREE block up to make room for the new USED block.
+             */
+            PRTHEAPSIMPLEFREE   pNew = (PRTHEAPSIMPLEFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPSIMPLEBLOCK));
+
+            pNew->Core.pNext = pFree->Core.pNext;
+            if (pFree->Core.pNext)
+                pFree->Core.pNext->pPrev = &pNew->Core;
+            pNew->Core.pPrev = &pFree->Core;
+            pNew->Core.pHeap = pHeapInt;
+            pNew->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC | RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+
+            pNew->pNext = pFree->pNext;
+            if (pNew->pNext)
+                pNew->pNext->pPrev = pNew;
+            else
+                pHeapInt->pFreeTail = pNew;
+            pNew->pPrev = pFree->pPrev;
+            if (pNew->pPrev)
+                pNew->pPrev->pNext = pNew;
+            else
+                pHeapInt->pFreeHead = pNew;
+            pNew->cb    = (pNew->Core.pNext ? (uintptr_t)pNew->Core.pNext : (uintptr_t)pHeapInt->pvEnd) \
+                        - (uintptr_t)pNew - sizeof(RTHEAPSIMPLEBLOCK);
+            ASSERT_BLOCK_FREE(pHeapInt, pNew);
+
+            /*
+             * Update the old FREE node making it a USED node.
+             */
+            pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+            pFree->Core.pNext = &pNew->Core;
+            pHeapInt->cbFree -= pFree->cb;
+            pHeapInt->cbFree += pNew->cb;
+            pRet = &pFree->Core;
+            ASSERT_BLOCK_USED(pHeapInt, pRet);
+        }
+        else
+        {
+            /*
+             * Link it out of the free list.
+             */
+            if (pFree->pNext)
+                pFree->pNext->pPrev = pFree->pPrev;
+            else
+                pHeapInt->pFreeTail = pFree->pPrev;
+            if (pFree->pPrev)
+                pFree->pPrev->pNext = pFree->pNext;
+            else
+                pHeapInt->pFreeHead = pFree->pNext;
+
+            /*
+             * Convert it to a used block.
+             */
+            pHeapInt->cbFree -= pFree->cb;
+            pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+            pRet = &pFree->Core;
+            ASSERT_BLOCK_USED(pHeapInt, pRet);
+        }
+        break;
+    }
+
+#ifdef RTHEAPSIMPLE_STRICT
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+    return pRet;
+}
+
+
+RTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE hHeap, void *pv)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt;
+    PRTHEAPSIMPLEBLOCK pBlock;
+
+    /*
+     * Validate input.
+     */
+    if (!pv)
+        return;
+    AssertPtr(pv);
+    Assert(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv);
+
+    /*
+     * Get the block and heap. If in strict mode, validate these.
+     */
+    pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
+    pHeapInt = pBlock->pHeap;
+    ASSERT_BLOCK_USED(pHeapInt, pBlock);
+    ASSERT_ANCHOR(pHeapInt);
+    Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)hHeap || !hHeap); RT_NOREF_PV(hHeap);
+
+#ifdef RTHEAPSIMPLE_FREE_POISON
+    /*
+     * Poison the block.
+     */
+    const size_t cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
+                         - (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
+    memset(pBlock + 1, RTHEAPSIMPLE_FREE_POISON, cbBlock);
+#endif
+
+    /*
+     * Call worker which does the actual job.
+     */
+    rtHeapSimpleFreeBlock(pHeapInt, pBlock);
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleFree);
+
+
+/**
+ * Free a memory block.
+ *
+ * @param   pHeapInt       The heap.
+ * @param   pBlock         The memory block to free.
+ */
+static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock)
+{
+    PRTHEAPSIMPLEFREE   pFree = (PRTHEAPSIMPLEFREE)pBlock;
+    PRTHEAPSIMPLEFREE   pLeft;
+    PRTHEAPSIMPLEFREE   pRight;
+
+#ifdef RTHEAPSIMPLE_STRICT
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+
+    /*
+     * Look for the closest free list blocks by walking the blocks right
+     * of us (both lists are sorted by address).
+     */
+    pLeft = NULL;
+    pRight = NULL;
+    if (pHeapInt->pFreeTail)
+    {
+        pRight = (PRTHEAPSIMPLEFREE)pFree->Core.pNext;
+        while (pRight && !RTHEAPSIMPLEBLOCK_IS_FREE(&pRight->Core))
+        {
+            ASSERT_BLOCK(pHeapInt, &pRight->Core);
+            pRight = (PRTHEAPSIMPLEFREE)pRight->Core.pNext;
+        }
+        if (!pRight)
+            pLeft = pHeapInt->pFreeTail;
+        else
+        {
+            ASSERT_BLOCK_FREE(pHeapInt, pRight);
+            pLeft = pRight->pPrev;
+        }
+        if (pLeft)
+            ASSERT_BLOCK_FREE(pHeapInt, pLeft);
+    }
+    AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock));
+    ASSERT_L(pLeft, pFree);
+    Assert(!pRight || (uintptr_t)pRight > (uintptr_t)pFree);
+    Assert(!pLeft || pLeft->pNext == pRight);
+
+    /*
+     * Insert at the head of the free block list?
+     */
+    if (!pLeft)
+    {
+        Assert(pRight == pHeapInt->pFreeHead);
+        pFree->Core.fFlags |= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+        pFree->pPrev = NULL;
+        pFree->pNext = pRight;
+        if (pRight)
+            pRight->pPrev = pFree;
+        else
+            pHeapInt->pFreeTail = pFree;
+        pHeapInt->pFreeHead = pFree;
+    }
+    else
+    {
+        /*
+         * Can we merge with left hand free block?
+         */
+        if (pLeft->Core.pNext == &pFree->Core)
+        {
+            pLeft->Core.pNext = pFree->Core.pNext;
+            if (pFree->Core.pNext)
+                pFree->Core.pNext->pPrev = &pLeft->Core;
+            pHeapInt->cbFree -= pLeft->cb;
+            pFree = pLeft;
+        }
+        /*
+         * No, just link it into the free list then.
+         */
+        else
+        {
+            pFree->Core.fFlags |= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
+            pFree->pNext = pRight;
+            pFree->pPrev = pLeft;
+            pLeft->pNext = pFree;
+            if (pRight)
+                pRight->pPrev = pFree;
+            else
+                pHeapInt->pFreeTail = pFree;
+        }
+    }
+
+    /*
+     * Can we merge with right hand free block?
+     */
+    if (    pRight
+        &&  pRight->Core.pPrev == &pFree->Core)
+    {
+        /* core */
+        pFree->Core.pNext = pRight->Core.pNext;
+        if (pRight->Core.pNext)
+            pRight->Core.pNext->pPrev = &pFree->Core;
+
+        /* free */
+        pFree->pNext = pRight->pNext;
+        if (pRight->pNext)
+            pRight->pNext->pPrev = pFree;
+        else
+            pHeapInt->pFreeTail = pFree;
+        pHeapInt->cbFree -= pRight->cb;
+    }
+
+    /*
+     * Calculate the size and update free stats.
+     */
+    pFree->cb = (pFree->Core.pNext ? (uintptr_t)pFree->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
+              - (uintptr_t)pFree - sizeof(RTHEAPSIMPLEBLOCK);
+    pHeapInt->cbFree += pFree->cb;
+    ASSERT_BLOCK_FREE(pHeapInt, pFree);
+
+#ifdef RTHEAPSIMPLE_STRICT
+    rtHeapSimpleAssertAll(pHeapInt);
+#endif
+}
+
+
+#ifdef RTHEAPSIMPLE_STRICT
+/**
+ * Internal consistency check (relying on assertions).
+ * @param   pHeapInt
+ */
+static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt)
+{
+    PRTHEAPSIMPLEFREE pPrev = NULL;
+    PRTHEAPSIMPLEFREE pPrevFree = NULL;
+    PRTHEAPSIMPLEFREE pBlock;
+    for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
+         pBlock;
+         pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
+    {
+        if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
+        {
+            ASSERT_BLOCK_FREE(pHeapInt, pBlock);
+            Assert(pBlock->pPrev == pPrevFree);
+            Assert(pPrevFree || pHeapInt->pFreeHead == pBlock);
+            pPrevFree = pBlock;
+        }
+        else
+            ASSERT_BLOCK_USED(pHeapInt, &pBlock->Core);
+        Assert(!pPrev || pPrev == (PRTHEAPSIMPLEFREE)pBlock->Core.pPrev);
+        pPrev = pBlock;
+    }
+    Assert(pHeapInt->pFreeTail == pPrevFree);
+}
+#endif
+
+
+RTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE hHeap, void *pv)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt;
+    PRTHEAPSIMPLEBLOCK pBlock;
+    size_t cbBlock;
+
+    /*
+     * Validate input.
+     */
+    if (!pv)
+        return 0;
+    AssertPtrReturn(pv, 0);
+    AssertReturn(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv, 0);
+
+    /*
+     * Get the block and heap. If in strict mode, validate these.
+     */
+    pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
+    pHeapInt = pBlock->pHeap;
+    ASSERT_BLOCK_USED(pHeapInt, pBlock);
+    ASSERT_ANCHOR(pHeapInt);
+    Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)hHeap || !hHeap); RT_NOREF_PV(hHeap);
+
+    /*
+     * Calculate the block size.
+     */
+    cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
+            - (uintptr_t)pBlock- sizeof(RTHEAPSIMPLEBLOCK);
+    return cbBlock;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleSize);
+
+
+RTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE hHeap)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt;
+
+    if (hHeap == NIL_RTHEAPSIMPLE)
+        return 0;
+
+    pHeapInt = hHeap;
+    AssertPtrReturn(pHeapInt, 0);
+    ASSERT_ANCHOR(pHeapInt);
+    return pHeapInt->cbHeap;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleGetHeapSize);
+
+
+RTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE hHeap)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt;
+
+    if (hHeap == NIL_RTHEAPSIMPLE)
+        return 0;
+
+    pHeapInt = hHeap;
+    AssertPtrReturn(pHeapInt, 0);
+    ASSERT_ANCHOR(pHeapInt);
+    return pHeapInt->cbFree;
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleGetFreeSize);
+
+
+RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE hHeap, PFNRTHEAPSIMPLEPRINTF pfnPrintf)
+{
+    PRTHEAPSIMPLEINTERNAL pHeapInt = (PRTHEAPSIMPLEINTERNAL)hHeap;
+    PRTHEAPSIMPLEFREE pBlock;
+
+    pfnPrintf("**** Dumping Heap %p - cbHeap=%zx cbFree=%zx ****\n",
+              hHeap, pHeapInt->cbHeap, pHeapInt->cbFree);
+
+    for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
+         pBlock;
+         pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
+    {
+        size_t cb = (pBlock->pNext ? (uintptr_t)pBlock->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
+                  - (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
+        if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
+            pfnPrintf("%p  %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
+                      pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb,
+                      pBlock->cb, pBlock->pNext, pBlock->pPrev);
+        else
+            pfnPrintf("%p  %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",
+                      pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb);
+    }
+    pfnPrintf("**** Done dumping Heap %p ****\n", hHeap);
+}
+RT_EXPORT_SYMBOL(RTHeapSimpleDump);
+