diff options
Diffstat (limited to 'src/VBox/Runtime/common/alloc/heapoffset.cpp')
| -rw-r--r-- | src/VBox/Runtime/common/alloc/heapoffset.cpp | 928 |
1 files changed, 928 insertions, 0 deletions
diff --git a/src/VBox/Runtime/common/alloc/heapoffset.cpp b/src/VBox/Runtime/common/alloc/heapoffset.cpp new file mode 100644 index 00000000..78cc4b9c --- /dev/null +++ b/src/VBox/Runtime/common/alloc/heapoffset.cpp @@ -0,0 +1,928 @@ +/* $Id: heapoffset.cpp $ */ +/** @file + * IPRT - An Offset Based 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/param.h> +#include <iprt/string.h> + +#include "internal/magics.h" + + +/********************************************************************************************************************************* +* Structures and Typedefs * +*********************************************************************************************************************************/ +/** Pointer to the heap anchor block. */ +typedef struct RTHEAPOFFSETINTERNAL *PRTHEAPOFFSETINTERNAL; +/** Pointer to a heap block. */ +typedef struct RTHEAPOFFSETBLOCK *PRTHEAPOFFSETBLOCK; +/** Pointer to a free heap block. */ +typedef struct RTHEAPOFFSETFREE *PRTHEAPOFFSETFREE; + +/** + * Structure describing a block in an offset based heap. + * + * If this block is allocated, it is followed by the user data. + * If this block is free, see RTHEAPOFFSETFREE. + */ +typedef struct RTHEAPOFFSETBLOCK +{ + /** The next block in the global block list. */ + uint32_t /*PRTHEAPOFFSETBLOCK*/ offNext; + /** The previous block in the global block list. */ + uint32_t /*PRTHEAPOFFSETBLOCK*/ offPrev; + /** Offset into the heap of this block. Used to locate the anchor block. */ + uint32_t /*PRTHEAPOFFSETINTERNAL*/ offSelf; + /** Flags + magic. */ + uint32_t fFlags; +} RTHEAPOFFSETBLOCK; +AssertCompileSize(RTHEAPOFFSETBLOCK, 16); + +/** The block is free if this flag is set. When cleared it's allocated. */ +#define RTHEAPOFFSETBLOCK_FLAGS_FREE (RT_BIT_32(0)) +/** The magic value. */ +#define RTHEAPOFFSETBLOCK_FLAGS_MAGIC (UINT32_C(0xabcdef00)) +/** The mask that needs to be applied to RTHEAPOFFSETBLOCK::fFlags to obtain the magic value. */ +#define RTHEAPOFFSETBLOCK_FLAGS_MAGIC_MASK (~RT_BIT_32(0)) + +/** + * Checks if the specified block is valid or not. + * @returns boolean answer. + * @param pBlock Pointer to a RTHEAPOFFSETBLOCK structure. + */ +#define RTHEAPOFFSETBLOCK_IS_VALID(pBlock) \ + ( ((pBlock)->fFlags & RTHEAPOFFSETBLOCK_FLAGS_MAGIC_MASK) == RTHEAPOFFSETBLOCK_FLAGS_MAGIC ) + +/** + * Checks if the specified block is valid and in use. + * @returns boolean answer. + * @param pBlock Pointer to a RTHEAPOFFSETBLOCK structure. + */ +#define RTHEAPOFFSETBLOCK_IS_VALID_USED(pBlock) \ + ( ((pBlock)->fFlags & (RTHEAPOFFSETBLOCK_FLAGS_MAGIC_MASK | RTHEAPOFFSETBLOCK_FLAGS_FREE)) \ + == RTHEAPOFFSETBLOCK_FLAGS_MAGIC ) + +/** + * Checks if the specified block is valid and free. + * @returns boolean answer. + * @param pBlock Pointer to a RTHEAPOFFSETBLOCK structure. + */ +#define RTHEAPOFFSETBLOCK_IS_VALID_FREE(pBlock) \ + ( ((pBlock)->fFlags & (RTHEAPOFFSETBLOCK_FLAGS_MAGIC_MASK | RTHEAPOFFSETBLOCK_FLAGS_FREE)) \ + == (RTHEAPOFFSETBLOCK_FLAGS_MAGIC | RTHEAPOFFSETBLOCK_FLAGS_FREE) ) + +/** + * Checks if the specified block is free or not. + * @returns boolean answer. + * @param pBlock Pointer to a valid RTHEAPOFFSETBLOCK structure. + */ +#define RTHEAPOFFSETBLOCK_IS_FREE(pBlock) (!!((pBlock)->fFlags & RTHEAPOFFSETBLOCK_FLAGS_FREE)) + +/** + * A free heap block. + * This is an extended version of RTHEAPOFFSETBLOCK that takes the unused + * user data to store free list pointers and a cached size value. + */ +typedef struct RTHEAPOFFSETFREE +{ + /** Core stuff. */ + RTHEAPOFFSETBLOCK Core; + /** Pointer to the next free block. */ + uint32_t /*PRTHEAPOFFSETFREE*/ offNext; + /** Pointer to the previous free block. */ + uint32_t /*PRTHEAPOFFSETFREE*/ offPrev; + /** The size of the block (excluding the RTHEAPOFFSETBLOCK part). */ + uint32_t cb; + /** An alignment filler to make it a multiple of 16 bytes. */ + uint32_t Alignment; +} RTHEAPOFFSETFREE; +AssertCompileSize(RTHEAPOFFSETFREE, 16+16); + + +/** + * The heap anchor block. + * This structure is placed at the head of the memory block specified to RTHeapOffsetInit(), + * which means that the first RTHEAPOFFSETBLOCK appears immediately after this structure. + */ +typedef struct RTHEAPOFFSETINTERNAL +{ + /** The typical magic (RTHEAPOFFSET_MAGIC). */ + uint32_t u32Magic; + /** The heap size. (This structure is included!) */ + uint32_t cbHeap; + /** The amount of free memory in the heap. */ + uint32_t cbFree; + /** Free head pointer. */ + uint32_t /*PRTHEAPOFFSETFREE*/ offFreeHead; + /** Free tail pointer. */ + uint32_t /*PRTHEAPOFFSETFREE*/ offFreeTail; + /** Make the size of this structure 32 bytes. */ + uint32_t au32Alignment[3]; +} RTHEAPOFFSETINTERNAL; +AssertCompileSize(RTHEAPOFFSETINTERNAL, 32); + + +/** The minimum allocation size. */ +#define RTHEAPOFFSET_MIN_BLOCK (sizeof(RTHEAPOFFSETBLOCK)) +AssertCompile(RTHEAPOFFSET_MIN_BLOCK >= sizeof(RTHEAPOFFSETBLOCK)); +AssertCompile(RTHEAPOFFSET_MIN_BLOCK >= sizeof(RTHEAPOFFSETFREE) - sizeof(RTHEAPOFFSETBLOCK)); + +/** The minimum and default alignment. */ +#define RTHEAPOFFSET_ALIGNMENT (sizeof(RTHEAPOFFSETBLOCK)) + + +/********************************************************************************************************************************* +* Defined Constants And Macros * +*********************************************************************************************************************************/ +#ifdef RT_STRICT +# define RTHEAPOFFSET_STRICT 1 +#endif + +/** + * Converts RTHEAPOFFSETBLOCK::offSelf into a heap anchor block pointer. + * + * @returns Pointer of given type. + * @param pBlock The block to find the heap anchor block for. + */ +#define RTHEAPOFF_GET_ANCHOR(pBlock) ( (PRTHEAPOFFSETINTERNAL)((uint8_t *)(pBlock) - (pBlock)->offSelf ) ) + + +/** + * Converts an offset to a pointer. + * + * All offsets are relative to the heap to make life simple. + * + * @returns Pointer of given type. + * @param pHeapInt Pointer to the heap anchor block. + * @param off The offset to convert. + * @param type The desired type. + */ +#ifdef RTHEAPOFFSET_STRICT +# define RTHEAPOFF_TO_PTR_N(pHeapInt, off, type) ( (type)rtHeapOffCheckedOffToPtr(pHeapInt, off, true /*fNull*/) ) +#else +# define RTHEAPOFF_TO_PTR_N(pHeapInt, off, type) ( (type)((off) ? (uint8_t *)(pHeapInt) + (off) : NULL) ) +#endif + +/** + * Converts an offset to a pointer. + * + * All offsets are relative to the heap to make life simple. + * + * @returns Pointer of given type. + * @param pHeapInt Pointer to the heap anchor block. + * @param off The offset to convert. + * @param type The desired type. + */ +#ifdef RTHEAPOFFSET_STRICT +# define RTHEAPOFF_TO_PTR(pHeapInt, off, type) ( (type)rtHeapOffCheckedOffToPtr(pHeapInt, off, false /*fNull*/) ) +#else +# define RTHEAPOFF_TO_PTR(pHeapInt, off, type) ( (type)((uint8_t *)(pHeapInt) + (off)) ) +#endif + +/** + * Converts a pointer to an offset. + * + * All offsets are relative to the heap to make life simple. + * + * @returns Offset into the heap. + * @param pHeapInt Pointer to the heap anchor block. + * @param ptr The pointer to convert. + */ +#ifdef RTHEAPOFFSET_STRICT +# define RTHEAPOFF_TO_OFF(pHeapInt, ptr) rtHeapOffCheckedPtrToOff(pHeapInt, ptr) +#else +# define RTHEAPOFF_TO_OFF(pHeapInt, ptr) ( (uint32_t)((ptr) ? (uintptr_t)(ptr) - (uintptr_t)(pHeapInt) : UINT32_C(0)) ) +#endif + +#define ASSERT_L(a, b) AssertMsg((a) < (b), ("a=%08x b=%08x\n", (a), (b))) +#define ASSERT_LE(a, b) AssertMsg((a) <= (b), ("a=%08x b=%08x\n", (a), (b))) +#define ASSERT_G(a, b) AssertMsg((a) > (b), ("a=%08x b=%08x\n", (a), (b))) +#define ASSERT_GE(a, b) AssertMsg((a) >= (b), ("a=%08x b=%08x\n", (a), (b))) +#define ASSERT_ALIGN(a) AssertMsg(!((uintptr_t)(a) & (RTHEAPOFFSET_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a))) + +#define ASSERT_PREV(pHeapInt, pBlock) \ + do { ASSERT_ALIGN((pBlock)->offPrev); \ + if ((pBlock)->offPrev) \ + { \ + ASSERT_L((pBlock)->offPrev, RTHEAPOFF_TO_OFF(pHeapInt, pBlock)); \ + ASSERT_GE((pBlock)->offPrev, sizeof(RTHEAPOFFSETINTERNAL)); \ + } \ + else \ + Assert((pBlock) == (PRTHEAPOFFSETBLOCK)((pHeapInt) + 1)); \ + } while (0) + +#define ASSERT_NEXT(pHeap, pBlock) \ + do { ASSERT_ALIGN((pBlock)->offNext); \ + if ((pBlock)->offNext) \ + { \ + ASSERT_L((pBlock)->offNext, (pHeapInt)->cbHeap); \ + ASSERT_G((pBlock)->offNext, RTHEAPOFF_TO_OFF(pHeapInt, pBlock)); \ + } \ + } while (0) + +#define ASSERT_BLOCK(pHeapInt, pBlock) \ + do { AssertMsg(RTHEAPOFFSETBLOCK_IS_VALID(pBlock), ("%#x\n", (pBlock)->fFlags)); \ + AssertMsg(RTHEAPOFF_GET_ANCHOR(pBlock) == (pHeapInt), ("%p != %p\n", RTHEAPOFF_GET_ANCHOR(pBlock), (pHeapInt))); \ + ASSERT_GE(RTHEAPOFF_TO_OFF(pHeapInt, pBlock), sizeof(RTHEAPOFFSETINTERNAL)); \ + ASSERT_L( RTHEAPOFF_TO_OFF(pHeapInt, pBlock), (pHeapInt)->cbHeap); \ + ASSERT_NEXT(pHeapInt, pBlock); \ + ASSERT_PREV(pHeapInt, pBlock); \ + } while (0) + +#define ASSERT_BLOCK_USED(pHeapInt, pBlock) \ + do { AssertMsg(RTHEAPOFFSETBLOCK_IS_VALID_USED((pBlock)), ("%#x\n", (pBlock)->fFlags)); \ + AssertMsg(RTHEAPOFF_GET_ANCHOR(pBlock) == (pHeapInt), ("%p != %p\n", RTHEAPOFF_GET_ANCHOR(pBlock), (pHeapInt))); \ + ASSERT_GE(RTHEAPOFF_TO_OFF(pHeapInt, pBlock), sizeof(RTHEAPOFFSETINTERNAL)); \ + ASSERT_L( RTHEAPOFF_TO_OFF(pHeapInt, pBlock), (pHeapInt)->cbHeap); \ + ASSERT_NEXT(pHeapInt, pBlock); \ + ASSERT_PREV(pHeapInt, pBlock); \ + } while (0) + +#define ASSERT_FREE_PREV(pHeapInt, pBlock) \ + do { ASSERT_ALIGN((pBlock)->offPrev); \ + if ((pBlock)->offPrev) \ + { \ + ASSERT_GE((pBlock)->offPrev, (pHeapInt)->offFreeHead); \ + ASSERT_L((pBlock)->offPrev, RTHEAPOFF_TO_OFF(pHeapInt, pBlock)); \ + ASSERT_LE((pBlock)->offPrev, (pBlock)->Core.offPrev); \ + } \ + else \ + Assert((pBlock) == RTHEAPOFF_TO_PTR(pHeapInt, (pHeapInt)->offFreeHead, PRTHEAPOFFSETFREE) ); \ + } while (0) + +#define ASSERT_FREE_NEXT(pHeapInt, pBlock) \ + do { ASSERT_ALIGN((pBlock)->offNext); \ + if ((pBlock)->offNext) \ + { \ + ASSERT_LE((pBlock)->offNext, (pHeapInt)->offFreeTail); \ + ASSERT_G((pBlock)->offNext, RTHEAPOFF_TO_OFF(pHeapInt, pBlock)); \ + ASSERT_GE((pBlock)->offNext, (pBlock)->Core.offNext); \ + } \ + else \ + Assert((pBlock) == RTHEAPOFF_TO_PTR(pHeapInt, (pHeapInt)->offFreeTail, PRTHEAPOFFSETFREE)); \ + } while (0) + +#ifdef RTHEAPOFFSET_STRICT +# define ASSERT_FREE_CB(pHeapInt, pBlock) \ + do { size_t cbCalc = ((pBlock)->Core.offNext ? (pBlock)->Core.offNext : (pHeapInt)->cbHeap) \ + - RTHEAPOFF_TO_OFF((pHeapInt), (pBlock)) - sizeof(RTHEAPOFFSETBLOCK); \ + 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(RTHEAPOFFSETBLOCK_IS_VALID_FREE(&(pBlock)->Core)); \ + ASSERT_GE(RTHEAPOFF_TO_OFF(pHeapInt, pBlock), (pHeapInt)->offFreeHead); \ + ASSERT_LE(RTHEAPOFF_TO_OFF(pHeapInt, pBlock), (pHeapInt)->offFreeTail); \ + 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)->u32Magic == RTHEAPOFFSET_MAGIC); \ + } while (0) + + +/********************************************************************************************************************************* +* Internal Functions * +*********************************************************************************************************************************/ +#ifdef RTHEAPOFFSET_STRICT +static void rtHeapOffsetAssertAll(PRTHEAPOFFSETINTERNAL pHeapInt); +#endif +static PRTHEAPOFFSETBLOCK rtHeapOffsetAllocBlock(PRTHEAPOFFSETINTERNAL pHeapInt, size_t cb, size_t uAlignment); +static void rtHeapOffsetFreeBlock(PRTHEAPOFFSETINTERNAL pHeapInt, PRTHEAPOFFSETBLOCK pBlock); + +#ifdef RTHEAPOFFSET_STRICT + +/** Checked version of RTHEAPOFF_TO_PTR and RTHEAPOFF_TO_PTR_N. */ +static void *rtHeapOffCheckedOffToPtr(PRTHEAPOFFSETINTERNAL pHeapInt, uint32_t off, bool fNull) +{ + Assert(off || fNull); + if (!off) + return NULL; + AssertMsg(off < pHeapInt->cbHeap, ("%#x %#x\n", off, pHeapInt->cbHeap)); + AssertMsg(off >= sizeof(*pHeapInt), ("%#x %#x\n", off, sizeof(*pHeapInt))); + return (uint8_t *)pHeapInt + off; +} + +/** Checked version of RTHEAPOFF_TO_OFF. */ +static uint32_t rtHeapOffCheckedPtrToOff(PRTHEAPOFFSETINTERNAL pHeapInt, void *pv) +{ + if (!pv) + return 0; + uintptr_t off = (uintptr_t)pv - (uintptr_t)pHeapInt; + AssertMsg(off < pHeapInt->cbHeap, ("%#x %#x\n", off, pHeapInt->cbHeap)); + AssertMsg(off >= sizeof(*pHeapInt), ("%#x %#x\n", off, sizeof(*pHeapInt))); + return (uint32_t)off; +} + +#endif /* RTHEAPOFFSET_STRICT */ + + + +RTDECL(int) RTHeapOffsetInit(PRTHEAPOFFSET phHeap, void *pvMemory, size_t cbMemory) +{ + PRTHEAPOFFSETINTERNAL pHeapInt; + PRTHEAPOFFSETFREE pFree; + unsigned i; + + /* + * Validate input. The imposed minimum heap size is just a convenient value. + */ + AssertReturn(cbMemory >= PAGE_SIZE, VERR_INVALID_PARAMETER); + AssertReturn(cbMemory < UINT32_MAX, 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 = (PRTHEAPOFFSETINTERNAL)pvMemory; + if ((uintptr_t)pvMemory & 31) + { + const uintptr_t off = 32 - ((uintptr_t)pvMemory & 31); + cbMemory -= off; + pHeapInt = (PRTHEAPOFFSETINTERNAL)((uintptr_t)pvMemory + off); + } + cbMemory &= ~(RTHEAPOFFSET_ALIGNMENT - 1); + + + /* Init the heap anchor block. */ + pHeapInt->u32Magic = RTHEAPOFFSET_MAGIC; + pHeapInt->cbHeap = (uint32_t)cbMemory; + pHeapInt->cbFree = (uint32_t)cbMemory + - sizeof(RTHEAPOFFSETBLOCK) + - sizeof(RTHEAPOFFSETINTERNAL); + pHeapInt->offFreeTail = pHeapInt->offFreeHead = sizeof(*pHeapInt); + for (i = 0; i < RT_ELEMENTS(pHeapInt->au32Alignment); i++) + pHeapInt->au32Alignment[i] = UINT32_MAX; + + /* Init the single free block. */ + pFree = RTHEAPOFF_TO_PTR(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE); + pFree->Core.offNext = 0; + pFree->Core.offPrev = 0; + pFree->Core.offSelf = pHeapInt->offFreeHead; + pFree->Core.fFlags = RTHEAPOFFSETBLOCK_FLAGS_MAGIC | RTHEAPOFFSETBLOCK_FLAGS_FREE; + pFree->offNext = 0; + pFree->offPrev = 0; + pFree->cb = pHeapInt->cbFree; + + *phHeap = pHeapInt; + +#ifdef RTHEAPOFFSET_STRICT + rtHeapOffsetAssertAll(pHeapInt); +#endif + return VINF_SUCCESS; +} +RT_EXPORT_SYMBOL(RTHeapOffsetInit); + + +RTDECL(void *) RTHeapOffsetAlloc(RTHEAPOFFSET hHeap, size_t cb, size_t cbAlignment) +{ + PRTHEAPOFFSETINTERNAL pHeapInt = hHeap; + PRTHEAPOFFSETBLOCK pBlock; + + /* + * Validate and adjust the input. + */ + AssertPtrReturn(pHeapInt, NULL); + if (cb < RTHEAPOFFSET_MIN_BLOCK) + cb = RTHEAPOFFSET_MIN_BLOCK; + else + cb = RT_ALIGN_Z(cb, RTHEAPOFFSET_ALIGNMENT); + if (!cbAlignment) + cbAlignment = RTHEAPOFFSET_ALIGNMENT; + else + { + Assert(!(cbAlignment & (cbAlignment - 1))); + Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment); + if (cbAlignment < RTHEAPOFFSET_ALIGNMENT) + cbAlignment = RTHEAPOFFSET_ALIGNMENT; + } + + /* + * Do the allocation. + */ + pBlock = rtHeapOffsetAllocBlock(pHeapInt, cb, cbAlignment); + if (RT_LIKELY(pBlock)) + { + void *pv = pBlock + 1; + return pv; + } + return NULL; +} +RT_EXPORT_SYMBOL(RTHeapOffsetAlloc); + + +RTDECL(void *) RTHeapOffsetAllocZ(RTHEAPOFFSET hHeap, size_t cb, size_t cbAlignment) +{ + PRTHEAPOFFSETINTERNAL pHeapInt = hHeap; + PRTHEAPOFFSETBLOCK pBlock; + + /* + * Validate and adjust the input. + */ + AssertPtrReturn(pHeapInt, NULL); + if (cb < RTHEAPOFFSET_MIN_BLOCK) + cb = RTHEAPOFFSET_MIN_BLOCK; + else + cb = RT_ALIGN_Z(cb, RTHEAPOFFSET_ALIGNMENT); + if (!cbAlignment) + cbAlignment = RTHEAPOFFSET_ALIGNMENT; + else + { + Assert(!(cbAlignment & (cbAlignment - 1))); + Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment); + if (cbAlignment < RTHEAPOFFSET_ALIGNMENT) + cbAlignment = RTHEAPOFFSET_ALIGNMENT; + } + + /* + * Do the allocation. + */ + pBlock = rtHeapOffsetAllocBlock(pHeapInt, cb, cbAlignment); + if (RT_LIKELY(pBlock)) + { + void *pv = pBlock + 1; + memset(pv, 0, cb); + return pv; + } + return NULL; +} +RT_EXPORT_SYMBOL(RTHeapOffsetAllocZ); + + +/** + * 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 PRTHEAPOFFSETBLOCK rtHeapOffsetAllocBlock(PRTHEAPOFFSETINTERNAL pHeapInt, size_t cb, size_t uAlignment) +{ + PRTHEAPOFFSETBLOCK pRet = NULL; + PRTHEAPOFFSETFREE pFree; + + AssertReturn((pHeapInt)->u32Magic == RTHEAPOFFSET_MAGIC, NULL); +#ifdef RTHEAPOFFSET_STRICT + rtHeapOffsetAssertAll(pHeapInt); +#endif + + /* + * Search for a fitting block from the lower end of the heap. + */ + for (pFree = RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE); + pFree; + pFree = RTHEAPOFF_TO_PTR_N(pHeapInt, pFree->offNext, PRTHEAPOFFSETFREE)) + { + 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) + { + PRTHEAPOFFSETFREE pPrev; + + offAlign = (uintptr_t)(&pFree[1].Core + 1) & (uAlignment - 1); + offAlign = uAlignment - offAlign; + if (pFree->cb < cb + offAlign + sizeof(RTHEAPOFFSETFREE)) + continue; + + /* + * Split up the free block into two, so that the 2nd is aligned as + * per specification. + */ + pPrev = pFree; + pFree = (PRTHEAPOFFSETFREE)((uintptr_t)(pFree + 1) + offAlign); + pFree->Core.offPrev = pPrev->Core.offSelf; + pFree->Core.offNext = pPrev->Core.offNext; + pFree->Core.offSelf = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + pFree->Core.fFlags = RTHEAPOFFSETBLOCK_FLAGS_MAGIC | RTHEAPOFFSETBLOCK_FLAGS_FREE; + pFree->offPrev = pPrev->Core.offSelf; + pFree->offNext = pPrev->offNext; + pFree->cb = (pFree->Core.offNext ? pFree->Core.offNext : pHeapInt->cbHeap) + - pFree->Core.offSelf - sizeof(RTHEAPOFFSETBLOCK); + + pPrev->Core.offNext = pFree->Core.offSelf; + pPrev->offNext = pFree->Core.offSelf; + pPrev->cb = pFree->Core.offSelf - pPrev->Core.offSelf - sizeof(RTHEAPOFFSETBLOCK); + + if (pFree->Core.offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = pFree->Core.offSelf; + if (pFree->offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETFREE)->offPrev = pFree->Core.offSelf; + else + pHeapInt->offFreeTail = pFree->Core.offSelf; + + pHeapInt->cbFree -= sizeof(RTHEAPOFFSETBLOCK); + ASSERT_BLOCK_FREE(pHeapInt, pPrev); + ASSERT_BLOCK_FREE(pHeapInt, pFree); + } + + /* + * Split off a new FREE block? + */ + if (pFree->cb >= cb + RT_ALIGN_Z(sizeof(RTHEAPOFFSETFREE), RTHEAPOFFSET_ALIGNMENT)) + { + /* + * Create a new FREE block at then end of this one. + */ + PRTHEAPOFFSETFREE pNew = (PRTHEAPOFFSETFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPOFFSETBLOCK)); + + pNew->Core.offSelf = RTHEAPOFF_TO_OFF(pHeapInt, pNew); + pNew->Core.offNext = pFree->Core.offNext; + if (pFree->Core.offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = pNew->Core.offSelf; + pNew->Core.offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + pNew->Core.fFlags = RTHEAPOFFSETBLOCK_FLAGS_MAGIC | RTHEAPOFFSETBLOCK_FLAGS_FREE; + + pNew->offNext = pFree->offNext; + if (pNew->offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pNew->offNext, PRTHEAPOFFSETFREE)->offPrev = pNew->Core.offSelf; + else + pHeapInt->offFreeTail = pNew->Core.offSelf; + pNew->offPrev = pFree->offPrev; + if (pNew->offPrev) + RTHEAPOFF_TO_PTR(pHeapInt, pNew->offPrev, PRTHEAPOFFSETFREE)->offNext = pNew->Core.offSelf; + else + pHeapInt->offFreeHead = pNew->Core.offSelf; + pNew->cb = (pNew->Core.offNext ? pNew->Core.offNext : pHeapInt->cbHeap) \ + - pNew->Core.offSelf - sizeof(RTHEAPOFFSETBLOCK); + ASSERT_BLOCK_FREE(pHeapInt, pNew); + + /* + * Adjust and convert the old FREE node into a USED node. + */ + pFree->Core.fFlags &= ~RTHEAPOFFSETBLOCK_FLAGS_FREE; + pFree->Core.offNext = pNew->Core.offSelf; + 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->offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->offNext, PRTHEAPOFFSETFREE)->offPrev = pFree->offPrev; + else + pHeapInt->offFreeTail = pFree->offPrev; + if (pFree->offPrev) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->offPrev, PRTHEAPOFFSETFREE)->offNext = pFree->offNext; + else + pHeapInt->offFreeHead = pFree->offNext; + + /* + * Convert it to a used block. + */ + pHeapInt->cbFree -= pFree->cb; + pFree->Core.fFlags &= ~RTHEAPOFFSETBLOCK_FLAGS_FREE; + pRet = &pFree->Core; + ASSERT_BLOCK_USED(pHeapInt, pRet); + } + break; + } + +#ifdef RTHEAPOFFSET_STRICT + rtHeapOffsetAssertAll(pHeapInt); +#endif + return pRet; +} + + +RTDECL(void) RTHeapOffsetFree(RTHEAPOFFSET hHeap, void *pv) +{ + PRTHEAPOFFSETINTERNAL pHeapInt; + PRTHEAPOFFSETBLOCK pBlock; + + /* + * Validate input. + */ + if (!pv) + return; + AssertPtr(pv); + Assert(RT_ALIGN_P(pv, RTHEAPOFFSET_ALIGNMENT) == pv); + + /* + * Get the block and heap. If in strict mode, validate these. + */ + pBlock = (PRTHEAPOFFSETBLOCK)pv - 1; + pHeapInt = RTHEAPOFF_GET_ANCHOR(pBlock); + ASSERT_BLOCK_USED(pHeapInt, pBlock); + ASSERT_ANCHOR(pHeapInt); + Assert(pHeapInt == (PRTHEAPOFFSETINTERNAL)hHeap || !hHeap); RT_NOREF_PV(hHeap); + +#ifdef RTHEAPOFFSET_FREE_POISON + /* + * Poison the block. + */ + const size_t cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd) + - (uintptr_t)pBlock - sizeof(RTHEAPOFFSETBLOCK); + memset(pBlock + 1, RTHEAPOFFSET_FREE_POISON, cbBlock); +#endif + + /* + * Call worker which does the actual job. + */ + rtHeapOffsetFreeBlock(pHeapInt, pBlock); +} +RT_EXPORT_SYMBOL(RTHeapOffsetFree); + + +/** + * Free a memory block. + * + * @param pHeapInt The heap. + * @param pBlock The memory block to free. + */ +static void rtHeapOffsetFreeBlock(PRTHEAPOFFSETINTERNAL pHeapInt, PRTHEAPOFFSETBLOCK pBlock) +{ + PRTHEAPOFFSETFREE pFree = (PRTHEAPOFFSETFREE)pBlock; + PRTHEAPOFFSETFREE pLeft; + PRTHEAPOFFSETFREE pRight; + +#ifdef RTHEAPOFFSET_STRICT + rtHeapOffsetAssertAll(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->offFreeTail) + { + pRight = RTHEAPOFF_TO_PTR_N(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETFREE); + while (pRight && !RTHEAPOFFSETBLOCK_IS_FREE(&pRight->Core)) + { + ASSERT_BLOCK(pHeapInt, &pRight->Core); + pRight = RTHEAPOFF_TO_PTR_N(pHeapInt, pRight->Core.offNext, PRTHEAPOFFSETFREE); + } + if (!pRight) + pLeft = RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeTail, PRTHEAPOFFSETFREE); + else + { + ASSERT_BLOCK_FREE(pHeapInt, pRight); + pLeft = RTHEAPOFF_TO_PTR_N(pHeapInt, pRight->offPrev, PRTHEAPOFFSETFREE); + } + if (pLeft) + ASSERT_BLOCK_FREE(pHeapInt, pLeft); + } + AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock)); + ASSERT_L(RTHEAPOFF_TO_OFF(pHeapInt, pLeft), RTHEAPOFF_TO_OFF(pHeapInt, pFree)); + Assert(!pRight || (uintptr_t)pRight > (uintptr_t)pFree); + Assert(!pLeft || RTHEAPOFF_TO_PTR_N(pHeapInt, pLeft->offNext, PRTHEAPOFFSETFREE) == pRight); + + /* + * Insert at the head of the free block list? + */ + if (!pLeft) + { + Assert(pRight == RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE)); + pFree->Core.fFlags |= RTHEAPOFFSETBLOCK_FLAGS_FREE; + pFree->offPrev = 0; + pFree->offNext = RTHEAPOFF_TO_OFF(pHeapInt, pRight); + if (pRight) + pRight->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + else + pHeapInt->offFreeTail = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + pHeapInt->offFreeHead = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + } + else + { + /* + * Can we merge with left hand free block? + */ + if (pLeft->Core.offNext == RTHEAPOFF_TO_OFF(pHeapInt, pFree)) + { + pLeft->Core.offNext = pFree->Core.offNext; + if (pFree->Core.offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pLeft); + pHeapInt->cbFree -= pLeft->cb; + pFree = pLeft; + } + /* + * No, just link it into the free list then. + */ + else + { + pFree->Core.fFlags |= RTHEAPOFFSETBLOCK_FLAGS_FREE; + pFree->offNext = RTHEAPOFF_TO_OFF(pHeapInt, pRight); + pFree->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pLeft); + pLeft->offNext = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + if (pRight) + pRight->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + else + pHeapInt->offFreeTail = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + } + } + + /* + * Can we merge with right hand free block? + */ + if ( pRight + && pRight->Core.offPrev == RTHEAPOFF_TO_OFF(pHeapInt, pFree)) + { + /* core */ + pFree->Core.offNext = pRight->Core.offNext; + if (pRight->Core.offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pRight->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + + /* free */ + pFree->offNext = pRight->offNext; + if (pRight->offNext) + RTHEAPOFF_TO_PTR(pHeapInt, pRight->offNext, PRTHEAPOFFSETFREE)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + else + pHeapInt->offFreeTail = RTHEAPOFF_TO_OFF(pHeapInt, pFree); + pHeapInt->cbFree -= pRight->cb; + } + + /* + * Calculate the size and update free stats. + */ + pFree->cb = (pFree->Core.offNext ? pFree->Core.offNext : pHeapInt->cbHeap) + - RTHEAPOFF_TO_OFF(pHeapInt, pFree) - sizeof(RTHEAPOFFSETBLOCK); + pHeapInt->cbFree += pFree->cb; + ASSERT_BLOCK_FREE(pHeapInt, pFree); + +#ifdef RTHEAPOFFSET_STRICT + rtHeapOffsetAssertAll(pHeapInt); +#endif +} + + +#ifdef RTHEAPOFFSET_STRICT +/** + * Internal consistency check (relying on assertions). + * @param pHeapInt + */ +static void rtHeapOffsetAssertAll(PRTHEAPOFFSETINTERNAL pHeapInt) +{ + PRTHEAPOFFSETFREE pPrev = NULL; + PRTHEAPOFFSETFREE pPrevFree = NULL; + PRTHEAPOFFSETFREE pBlock; + for (pBlock = (PRTHEAPOFFSETFREE)(pHeapInt + 1); + pBlock; + pBlock = RTHEAPOFF_TO_PTR_N(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE)) + { + if (RTHEAPOFFSETBLOCK_IS_FREE(&pBlock->Core)) + { + ASSERT_BLOCK_FREE(pHeapInt, pBlock); + Assert(pBlock->offPrev == RTHEAPOFF_TO_OFF(pHeapInt, pPrevFree)); + Assert(pPrevFree || pHeapInt->offFreeHead == RTHEAPOFF_TO_OFF(pHeapInt, pBlock)); + pPrevFree = pBlock; + } + else + ASSERT_BLOCK_USED(pHeapInt, &pBlock->Core); + Assert(!pPrev || RTHEAPOFF_TO_OFF(pHeapInt, pPrev) == pBlock->Core.offPrev); + pPrev = pBlock; + } + Assert(pHeapInt->offFreeTail == RTHEAPOFF_TO_OFF(pHeapInt, pPrevFree)); +} +#endif + + +RTDECL(size_t) RTHeapOffsetSize(RTHEAPOFFSET hHeap, void *pv) +{ + PRTHEAPOFFSETINTERNAL pHeapInt; + PRTHEAPOFFSETBLOCK pBlock; + size_t cbBlock; + + /* + * Validate input. + */ + if (!pv) + return 0; + AssertPtrReturn(pv, 0); + AssertReturn(RT_ALIGN_P(pv, RTHEAPOFFSET_ALIGNMENT) == pv, 0); + + /* + * Get the block and heap. If in strict mode, validate these. + */ + pBlock = (PRTHEAPOFFSETBLOCK)pv - 1; + pHeapInt = RTHEAPOFF_GET_ANCHOR(pBlock); + ASSERT_BLOCK_USED(pHeapInt, pBlock); + ASSERT_ANCHOR(pHeapInt); + Assert(pHeapInt == (PRTHEAPOFFSETINTERNAL)hHeap || !hHeap); RT_NOREF_PV(hHeap); + + /* + * Calculate the block size. + */ + cbBlock = (pBlock->offNext ? pBlock->offNext : pHeapInt->cbHeap) + - RTHEAPOFF_TO_OFF(pHeapInt, pBlock) - sizeof(RTHEAPOFFSETBLOCK); + return cbBlock; +} +RT_EXPORT_SYMBOL(RTHeapOffsetSize); + + +RTDECL(size_t) RTHeapOffsetGetHeapSize(RTHEAPOFFSET hHeap) +{ + PRTHEAPOFFSETINTERNAL pHeapInt; + + if (hHeap == NIL_RTHEAPOFFSET) + return 0; + + pHeapInt = hHeap; + AssertPtrReturn(pHeapInt, 0); + ASSERT_ANCHOR(pHeapInt); + return pHeapInt->cbHeap; +} +RT_EXPORT_SYMBOL(RTHeapOffsetGetHeapSize); + + +RTDECL(size_t) RTHeapOffsetGetFreeSize(RTHEAPOFFSET hHeap) +{ + PRTHEAPOFFSETINTERNAL pHeapInt; + + if (hHeap == NIL_RTHEAPOFFSET) + return 0; + + pHeapInt = hHeap; + AssertPtrReturn(pHeapInt, 0); + ASSERT_ANCHOR(pHeapInt); + return pHeapInt->cbFree; +} +RT_EXPORT_SYMBOL(RTHeapOffsetGetFreeSize); + + +RTDECL(void) RTHeapOffsetDump(RTHEAPOFFSET hHeap, PFNRTHEAPOFFSETPRINTF pfnPrintf) +{ + PRTHEAPOFFSETINTERNAL pHeapInt = (PRTHEAPOFFSETINTERNAL)hHeap; + PRTHEAPOFFSETFREE pBlock; + + pfnPrintf("**** Dumping Heap %p - cbHeap=%x cbFree=%x ****\n", + hHeap, pHeapInt->cbHeap, pHeapInt->cbFree); + + for (pBlock = (PRTHEAPOFFSETFREE)(pHeapInt + 1); + pBlock; + pBlock = RTHEAPOFF_TO_PTR_N(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE)) + { + size_t cb = (pBlock->offNext ? pBlock->Core.offNext : pHeapInt->cbHeap) + - RTHEAPOFF_TO_OFF(pHeapInt, pBlock) - sizeof(RTHEAPOFFSETBLOCK); + if (RTHEAPOFFSETBLOCK_IS_FREE(&pBlock->Core)) + pfnPrintf("%p %06x FREE offNext=%06x offPrev=%06x fFlags=%#x cb=%#06x : cb=%#06x offNext=%06x offPrev=%06x\n", + pBlock, pBlock->Core.offSelf, pBlock->Core.offNext, pBlock->Core.offPrev, pBlock->Core.fFlags, cb, + pBlock->cb, pBlock->offNext, pBlock->offPrev); + else + pfnPrintf("%p %06x USED offNext=%06x offPrev=%06x fFlags=%#x cb=%#06x\n", + pBlock, pBlock->Core.offSelf, pBlock->Core.offNext, pBlock->Core.offPrev, pBlock->Core.fFlags, cb); + } + pfnPrintf("**** Done dumping Heap %p ****\n", hHeap); +} +RT_EXPORT_SYMBOL(RTHeapOffsetDump); + |