heapoffset.cpp revision 68464669bc262783ab39e91b5a444da86b885679
/* $Id$ */
/** @file
* IPRT - An Offset Based Heap.
*/
/*
* Copyright (C) 2006-2009 Oracle Corporation
*
* This file is part of VirtualBox Open Source Edition (OSE), as
* available from http://www.virtualbox.org. This file is free software;
* 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
/*******************************************************************************
* 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. */
/** The previous block in the global block list. */
/** Offset into the heap of this block. Used to locate the anchor block. */
/** Flags + magic. */
/** 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. */
/** 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) \
/**
* 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) \
/**
* 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) \
/**
* Checks if the specified block is free or not.
* @returns boolean answer.
* @param pBlock Pointer to a valid RTHEAPOFFSETBLOCK structure.
*/
/**
* 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. */
/** Pointer to the next free block. */
/** Pointer to the previous free block. */
/** The size of the block (excluding the RTHEAPOFFSETBLOCK part). */
/** An alignment filler to make it a multiple of 16 bytes. */
/**
* 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). */
/** The heap size. (This structure is included!) */
/** The amount of free memory in the heap. */
/** Free head pointer. */
/** Free tail pointer. */
/** Make the size of this structure 32 bytes. */
/** The minimum allocation size. */
#define RTHEAPOFFSET_MIN_BLOCK (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
#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
#else
# define RTHEAPOFF_TO_OFF(pHeapInt, ptr) ( (uint32_t)((ptr) ? (uintptr_t)(ptr) - (uintptr_t)(pHeapInt) : UINT32_C(0)) )
#endif
#define ASSERT_ALIGN(a) AssertMsg(!((uintptr_t)(a) & (RTHEAPOFFSET_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a)))
{ \
} \
else \
} while (0)
{ \
} \
} while (0)
AssertMsg(RTHEAPOFF_GET_ANCHOR(pBlock) == (pHeapInt), ("%p != %p\n", RTHEAPOFF_GET_ANCHOR(pBlock), (pHeapInt))); \
} while (0)
AssertMsg(RTHEAPOFF_GET_ANCHOR(pBlock) == (pHeapInt), ("%p != %p\n", RTHEAPOFF_GET_ANCHOR(pBlock), (pHeapInt))); \
} while (0)
{ \
} \
else \
} while (0)
{ \
} \
else \
} while (0)
#ifdef RTHEAPOFFSET_STRICT
} while (0)
#else
#endif
/** Asserts that a free block is valid. */
} while (0)
/** Asserts that the heap anchor block is ok. */
#define ASSERT_ANCHOR(pHeapInt) \
} while (0)
/*******************************************************************************
* Internal Functions *
*******************************************************************************/
#ifdef RTHEAPOFFSET_STRICT
#endif
static PRTHEAPOFFSETBLOCK rtHeapOffsetAllocBlock(PRTHEAPOFFSETINTERNAL pHeapInt, size_t cb, size_t uAlignment);
#ifdef RTHEAPOFFSET_STRICT
/** Checked version of RTHEAPOFF_TO_PTR and RTHEAPOFF_TO_PTR_N. */
DECLINLINE(void *) rtHeapOffCheckedOffToPtr(PRTHEAPOFFSETINTERNAL pHeapInt, uint32_t off, bool fNull)
{
if (!off)
return NULL;
}
/** Checked version of RTHEAPOFF_TO_OFF. */
{
if (!pv)
return 0;
}
#endif /* RTHEAPOFFSET_STRICT */
{
unsigned i;
/*
* Validate input. The imposed minimum heap size is just a convenient value.
*/
/*
* Place the heap anchor block at the start of the heap memory,
* enforce 32 byte alignment of it. Also align the heap size correctly.
*/
{
}
/* Init the heap anchor block. */
- sizeof(RTHEAPOFFSETBLOCK)
- sizeof(RTHEAPOFFSETINTERNAL);
/* Init the single free block. */
#ifdef RTHEAPOFFSET_STRICT
#endif
return VINF_SUCCESS;
}
{
/*
* Validate and adjust the input.
*/
if (cb < RTHEAPOFFSET_MIN_BLOCK)
else
if (!cbAlignment)
else
{
}
/*
* Do the allocation.
*/
{
return pv;
}
return NULL;
}
{
/*
* Validate and adjust the input.
*/
if (cb < RTHEAPOFFSET_MIN_BLOCK)
else
if (!cbAlignment)
else
{
}
/*
* Do the allocation.
*/
{
return pv;
}
return NULL;
}
/**
* 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)
{
#ifdef RTHEAPOFFSET_STRICT
#endif
/*
* Search for a fitting block from the lower end of the heap.
*/
{
/*
* Match for size and alignment.
*/
continue;
if (offAlign)
{
continue;
/*
* Split up the free block into two, so that the 2nd is aligned as
* per specification.
*/
else
}
/*
* Split off a new FREE block?
*/
{
/*
* Create a new FREE block at then end of this one.
*/
PRTHEAPOFFSETFREE pNew = (PRTHEAPOFFSETFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPOFFSETBLOCK));
else
else
/*
* Adjust and convert the old FREE node into a USED node.
*/
}
else
{
/*
* Link it out of the free list.
*/
else
else
/*
* Convert it to a used block.
*/
}
break;
}
#ifdef RTHEAPOFFSET_STRICT
#endif
return pRet;
}
{
/*
* Validate input.
*/
if (!pv)
return;
/*
* Get the block and heap. If in strict mode, validate these.
*/
#ifdef RTHEAPOFFSET_FREE_POISON
/*
* Poison the block.
*/
#endif
/*
* Call worker which does the actual job.
*/
}
/**
* Free a memory block.
*
* @param pHeapInt The heap.
* @param pBlock The memory block to free.
*/
{
#ifdef RTHEAPOFFSET_STRICT
#endif
/*
* Look for the closest free list blocks by walking the blocks right
* of us (both lists are sorted by address).
*/
if (pHeapInt->offFreeTail)
{
{
}
if (!pRight)
else
{
}
if (pLeft)
}
/*
* Insert at the head of the free block list?
*/
if (!pLeft)
{
if (pRight)
else
}
else
{
/*
* Can we merge with left hand free block?
*/
{
RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pLeft);
}
/*
* No, just link it into the free list then.
*/
else
{
if (pRight)
else
}
}
/*
* Can we merge with right hand free block?
*/
if ( pRight
{
/* core */
RTHEAPOFF_TO_PTR(pHeapInt, pRight->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree);
/* free */
RTHEAPOFF_TO_PTR(pHeapInt, pRight->offNext, PRTHEAPOFFSETFREE)->offPrev = RTHEAPOFF_TO_OFF(pHeapInt, pFree);
else
}
/*
* Calculate the size and update free stats.
*/
#ifdef RTHEAPOFFSET_STRICT
#endif
}
#ifdef RTHEAPOFFSET_STRICT
/**
* Internal consistency check (relying on assertions).
* @param pHeapInt
*/
{
{
{
}
else
}
}
#endif
{
/*
* Validate input.
*/
if (!pv)
return 0;
AssertPtrReturn(pv, 0);
/*
* Get the block and heap. If in strict mode, validate these.
*/
/*
* Calculate the block size.
*/
return cbBlock;
}
{
if (hHeap == NIL_RTHEAPOFFSET)
return 0;
AssertPtrReturn(pHeapInt, 0);
}
{
if (hHeap == NIL_RTHEAPOFFSET)
return 0;
AssertPtrReturn(pHeapInt, 0);
}
{
pfnPrintf("**** Dumping Heap %p - cbHeap=%x cbFree=%x ****\n",
{
pfnPrintf("%p %06x FREE offNext=%06x offPrev=%06x fFlags=%#x cb=%#06x : cb=%#06x offNext=%06x offPrev=%06x\n",
else
pfnPrintf("%p %06x USED offNext=%06x offPrev=%06x fFlags=%#x cb=%#06x\n",
}
}