PhysHeap.cpp revision 3abda8f874902100d94170e6b31920b99dd4a0b9
/** @file
*
* VBoxGuestLib - A support library for VirtualBox guest additions:
* Physical memory heap
*/
/*
* Copyright (C) 2006 InnoTek Systemberatung GmbH
*
* 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 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.
*
* If you received this file as part of a commercial VirtualBox
* distribution, then only the terms of your commercial VirtualBox
* license agreement apply instead of the previous paragraph.
*/
#include <VBox/VBoxGuestLib.h>
#include "VBGLInternal.h"
#include <iprt/semaphore.h>
/* Physical memory heap consists of double linked list
* of chunks. Memory blocks are allocated inside these chunks
* and are members of Allocated and Free double linked lists.
*
* When allocating a block, we search in Free linked
* list for a suitable free block. If there is no such block,
* a new chunk is allocated and the new block is taken from
* the new chunk as the only chunk-sized free block.
* Allocated block is excluded from the Free list and goes to
* Alloc list.
*
* When freeing block, we check the pointer and then
* exclude block from Alloc list and move it to free list.
*
* For each chunk we maintain the allocated blocks counter.
* if 2 (or more) entire chunks are free they are immediately
* deallocated, so we always have at most 1 free chunk.
*
* When freeing blocks, two subsequent free blocks are always
* merged together. Current implementation merges blocks only
* when there is a block after the just freed one.
*
*/
#define VBGL_PH_ASSERT AssertRelease
#define VBGL_PH_ASSERTMsg AssertReleaseMsg
// #define DUMPHEAP
#ifdef DUMPHEAP
#define VBGL_PH_dprintf(a) AssertMsg2 a
#else
#define VBGL_PH_dprintf(a)
#endif
/* Heap block signature */
#define VBGL_PH_BLOCKSIGNATURE (0xADDBBBBB)
/* Heap chunk signarure */
#define VBGL_PH_CHUNKSIGNATURE (0xADDCCCCC)
/* Heap chunk allocation unit */
#define VBGL_PH_CHUNKSIZE (0x10000)
/* Heap block bit flags */
#define VBGL_PH_BF_ALLOCATED (0x1)
struct _VBGLPHYSHEAPBLOCK
{
/* Size of user data in the block. Does not include the block header. */
struct _VBGLPHYSHEAPBLOCK *pNext;
struct _VBGLPHYSHEAPBLOCK *pPrev;
struct _VBGLPHYSHEAPCHUNK *pChunk;
};
struct _VBGLPHYSHEAPCHUNK
{
/* Size of the the chunk. Includes the chunk header. */
/* Physical address of the chunk */
/* Number of allocated blocks in the chunk */
struct _VBGLPHYSHEAPCHUNK *pNext;
struct _VBGLPHYSHEAPCHUNK *pPrev;
};
#ifndef DUMPHEAP
#define dumpheap(a)
#else
{
VBGL_PH_dprintf(("Chunks:\n"));
while (pChunk)
{
VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, allocated = %8d, phys = %08X\n",
pChunk, pChunk->pNext, pChunk->pPrev, pChunk->u32Signature, pChunk->cbSize, pChunk->cAllocatedBlocks, pChunk->physAddr));
}
VBGL_PH_dprintf(("Allocated blocks:\n"));
while (pBlock)
{
VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
pBlock, pBlock->pNext, pBlock->pPrev, pBlock->u32Signature, pBlock->cbDataSize, pBlock->fu32Flags, pBlock->pChunk));
}
VBGL_PH_dprintf(("Free blocks:\n"));
while (pBlock)
{
VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
pBlock, pBlock->pNext, pBlock->pPrev, pBlock->u32Signature, pBlock->cbDataSize, pBlock->fu32Flags, pBlock->pChunk));
}
}
#endif
{
}
{
return pBlock;
}
DECLINLINE(int) vbglPhysHeapEnter (void)
{
("Failed to request heap mutex, rc = %Vrc\n", rc));
return rc;
}
DECLINLINE(void) vbglPhysHeapLeave (void)
{
}
static void vbglPhysHeapInitBlock (VBGLPHYSHEAPBLOCK *pBlock, VBGLPHYSHEAPCHUNK *pChunk, uint32_t cbDataSize)
{
}
{
if (pInsertAfter)
{
if (pInsertAfter->pNext)
{
}
}
else
{
/* inserting to head of list */
{
{
}
}
else
{
{
}
}
}
}
{
{
}
else
{
/* this is tail of list but we do not maintain tails of block lists.
* so do nothing.
*/
;
}
{
}
else
{
/* this is head of list but we do not maintain tails of block lists. */
{
}
else
{
}
}
}
{
/* Compute chunk size to allocate */
if (cbSize < VBGL_PH_CHUNKSIZE)
{
/* Includes case of block size 0 during initialization */
}
else
{
/* Round up to next chunk size, which must be power of 2 */
}
if (!pChunk)
{
return NULL;
}
pChunk->cAllocatedBlocks = 0;
/* Initialize the free block, which now occupies entire chunk. */
vbglPhysHeapInitBlock (pBlock, pChunk, cbSize - sizeof (VBGLPHYSHEAPCHUNK) - sizeof (VBGLPHYSHEAPBLOCK));
return pBlock;
}
{
/* first scan the chunk and exclude all blocks from lists */
char *p = (char *)pChunk + sizeof (VBGLPHYSHEAPCHUNK);
{
}
("p = %p, (char *)pChunk + pChunk->cbSize = %p, pChunk->cbSize = %08X\n",
/* Exclude chunk from the chunk list */
{
}
else
{
/* we do not maintain tail */
;
}
{
}
else
{
/* the chunk was head */
}
}
{
int rc = vbglPhysHeapEnter ();
if (VBOX_FAILURE(rc))
{
return NULL;
}
dumpheap ("pre alloc");
/* If there are free blocks in the heap, look at them. */
/* There will be not many blocks in the heap, so
* linear search would be fast enough.
*/
while (iter)
{
{
/* exact match */
break;
}
/* Looking for a free block with nearest size */
{
if (pBlock)
{
{
}
}
else
{
}
}
}
if (!pBlock)
{
/* No free blocks, allocate a new chunk,
* the only free block of the chunk will
* be returned.
*/
}
if (pBlock)
{
/* We have a free block, either found or allocated. */
{
/* Data will occupy less than a half of the block,
* the block should be split.
*/
/* Init the new 'iter' block, initialized blocks are always marked as free. */
vbglPhysHeapInitBlock (iter, pBlock->pChunk, pBlock->cbDataSize - cbSize - sizeof (VBGLPHYSHEAPBLOCK));
/* Insert the new 'iter' block after the 'pBlock' in the free list */
}
/* Exclude pBlock from free list */
/* Mark as allocated */
/* Insert to allocated list */
/* Adjust the chunk allocated blocks counter */
}
dumpheap ("post alloc");
VBGL_PH_dprintf(("VbglPhysHeapAlloc %x size %x\n", vbglPhysHeapBlock2Data (pBlock), pBlock->cbDataSize));
return vbglPhysHeapBlock2Data (pBlock);
}
{
if (pBlock)
{
}
return physAddr;
}
DECLVBGL(void) VbglPhysHeapFree (void *p)
{
int rc = vbglPhysHeapEnter ();
if (VBOX_FAILURE(rc))
{
return;
}
dumpheap ("pre free");
if (!pBlock)
{
return;
}
/* Exclude from allocated list */
dumpheap ("post exclude");
/* Mark as free */
/* Insert to free list */
dumpheap ("post insert");
/* Adjust the chunk allocated blocks counter */
/* Check if we can merge 2 free blocks. To simplify heap maintenance,
* we will look at block after the just freed one.
* This will not prevent us from detecting free memory chunks.
* Also in most cases blocks are deallocated in reverse allocation order
* and in that case the merging will work.
*/
{
/* The next block is free as well. */
/* Adjust size of current memory block */
/* Exclude the next neighbour */
}
dumpheap ("post merge");
/* now check if there are 2 or more free chunks */
{
uint32_t u32FreeChunks = 0;
while (pChunk)
{
if (pChunk->cAllocatedBlocks == 0)
{
}
}
if (u32FreeChunks > 1)
{
/* Delete current chunk, it will also exclude all free blocks
* remaining in the chunk from the free list, so the pBlock
* will also be invalid after this.
*/
}
}
dumpheap ("post free");
}
DECLVBGL(int) VbglPhysHeapInit (void)
{
int rc = VINF_SUCCESS;
/* Allocate the first chunk of the heap. */
if (!pBlock)
{
rc = VERR_NO_MEMORY;
}
return rc;
}
DECLVBGL(void) VbglPhysHeapTerminate (void)
{
while (g_vbgldata.pChunkHead)
{
}
}