--- /dev/null
+/* $Id: VBoxGuestR0LibPhysHeap.cpp $ */
+/** @file
+ * VBoxGuestLibR0 - Physical memory heap.
+ */
+
+/*
+ * Copyright (C) 2006-2016 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 *
+*********************************************************************************************************************************/
+#include "VBoxGuestR0LibInternal.h"
+
+#include <iprt/assert.h>
+#include <iprt/semaphore.h>
+#include <iprt/alloc.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 Assert
+#define VBGL_PH_ASSERTMsg AssertMsg
+
+// #define DUMPHEAP
+
+#ifdef DUMPHEAP
+# define VBGL_PH_dprintf(a) RTAssertMsg2Weak a
+#else
+# define VBGL_PH_dprintf(a)
+#endif
+
+/* Heap block signature */
+#define VBGL_PH_BLOCKSIGNATURE (0xADDBBBBB)
+
+
+/* Heap chunk signature */
+#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
+{
+ uint32_t u32Signature;
+
+ /* Size of user data in the block. Does not include the block header. */
+ uint32_t cbDataSize;
+
+ uint32_t fu32Flags;
+
+ struct _VBGLPHYSHEAPBLOCK *pNext;
+ struct _VBGLPHYSHEAPBLOCK *pPrev;
+
+ struct _VBGLPHYSHEAPCHUNK *pChunk;
+};
+
+struct _VBGLPHYSHEAPCHUNK
+{
+ uint32_t u32Signature;
+
+ /* Size of the chunk. Includes the chunk header. */
+ uint32_t cbSize;
+
+ /* Physical address of the chunk */
+ uint32_t physAddr;
+
+ /* Number of allocated blocks in the chunk */
+ int32_t cAllocatedBlocks;
+
+ struct _VBGLPHYSHEAPCHUNK *pNext;
+ struct _VBGLPHYSHEAPCHUNK *pPrev;
+};
+
+
+#ifndef DUMPHEAP
+#define dumpheap(a)
+#else
+void dumpheap (char *point)
+{
+ VBGL_PH_dprintf(("VBGL_PH dump at '%s'\n", point));
+
+ VBGL_PH_dprintf(("Chunks:\n"));
+
+ VBGLPHYSHEAPCHUNK *pChunk = g_vbgldata.pChunkHead;
+
+ 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));
+
+ pChunk = pChunk->pNext;
+ }
+
+ VBGL_PH_dprintf(("Allocated blocks:\n"));
+
+ VBGLPHYSHEAPBLOCK *pBlock = g_vbgldata.pAllocBlocksHead;
+
+ 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));
+
+ pBlock = pBlock->pNext;
+ }
+
+ VBGL_PH_dprintf(("Free blocks:\n"));
+
+ pBlock = g_vbgldata.pFreeBlocksHead;
+
+ 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));
+
+ pBlock = pBlock->pNext;
+ }
+
+ VBGL_PH_dprintf(("VBGL_PH dump at '%s' done\n", point));
+}
+#endif
+
+
+DECLINLINE(void *) vbglPhysHeapBlock2Data (VBGLPHYSHEAPBLOCK *pBlock)
+{
+ return (void *)(pBlock? (char *)pBlock + sizeof (VBGLPHYSHEAPBLOCK): NULL);
+}
+
+DECLINLINE(VBGLPHYSHEAPBLOCK *) vbglPhysHeapData2Block (void *p)
+{
+ VBGLPHYSHEAPBLOCK *pBlock = (VBGLPHYSHEAPBLOCK *)(p? (char *)p - sizeof (VBGLPHYSHEAPBLOCK): NULL);
+
+ VBGL_PH_ASSERTMsg(pBlock == NULL || pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE,
+ ("pBlock->u32Signature = %08X\n", pBlock->u32Signature));
+
+ return pBlock;
+}
+
+DECLINLINE(int) vbglPhysHeapEnter (void)
+{
+ int rc = RTSemFastMutexRequest(g_vbgldata.mutexHeap);
+
+ VBGL_PH_ASSERTMsg(RT_SUCCESS(rc),
+ ("Failed to request heap mutex, rc = %Rrc\n", rc));
+
+ return rc;
+}
+
+DECLINLINE(void) vbglPhysHeapLeave (void)
+{
+ RTSemFastMutexRelease(g_vbgldata.mutexHeap);
+}
+
+
+static void vbglPhysHeapInitBlock (VBGLPHYSHEAPBLOCK *pBlock, VBGLPHYSHEAPCHUNK *pChunk, uint32_t cbDataSize)
+{
+ VBGL_PH_ASSERT(pBlock != NULL);
+ VBGL_PH_ASSERT(pChunk != NULL);
+
+ pBlock->u32Signature = VBGL_PH_BLOCKSIGNATURE;
+ pBlock->cbDataSize = cbDataSize;
+ pBlock->fu32Flags = 0;
+ pBlock->pNext = NULL;
+ pBlock->pPrev = NULL;
+ pBlock->pChunk = pChunk;
+}
+
+
+static void vbglPhysHeapInsertBlock (VBGLPHYSHEAPBLOCK *pInsertAfter, VBGLPHYSHEAPBLOCK *pBlock)
+{
+ VBGL_PH_ASSERTMsg(pBlock->pNext == NULL,
+ ("pBlock->pNext = %p\n", pBlock->pNext));
+ VBGL_PH_ASSERTMsg(pBlock->pPrev == NULL,
+ ("pBlock->pPrev = %p\n", pBlock->pPrev));
+
+ if (pInsertAfter)
+ {
+ pBlock->pNext = pInsertAfter->pNext;
+ pBlock->pPrev = pInsertAfter;
+
+ if (pInsertAfter->pNext)
+ {
+ pInsertAfter->pNext->pPrev = pBlock;
+ }
+
+ pInsertAfter->pNext = pBlock;
+ }
+ else
+ {
+ /* inserting to head of list */
+ pBlock->pPrev = NULL;
+
+ if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
+ {
+ pBlock->pNext = g_vbgldata.pAllocBlocksHead;
+
+ if (g_vbgldata.pAllocBlocksHead)
+ {
+ g_vbgldata.pAllocBlocksHead->pPrev = pBlock;
+ }
+
+ g_vbgldata.pAllocBlocksHead = pBlock;
+ }
+ else
+ {
+ pBlock->pNext = g_vbgldata.pFreeBlocksHead;
+
+ if (g_vbgldata.pFreeBlocksHead)
+ {
+ g_vbgldata.pFreeBlocksHead->pPrev = pBlock;
+ }
+
+ g_vbgldata.pFreeBlocksHead = pBlock;
+ }
+ }
+}
+
+static void vbglPhysHeapExcludeBlock (VBGLPHYSHEAPBLOCK *pBlock)
+{
+ if (pBlock->pNext)
+ {
+ pBlock->pNext->pPrev = pBlock->pPrev;
+ }
+ else
+ {
+ /* this is tail of list but we do not maintain tails of block lists.
+ * so do nothing.
+ */
+ ;
+ }
+
+ if (pBlock->pPrev)
+ {
+ pBlock->pPrev->pNext = pBlock->pNext;
+ }
+ else
+ {
+ /* this is head of list but we do not maintain tails of block lists. */
+ if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
+ {
+ g_vbgldata.pAllocBlocksHead = pBlock->pNext;
+ }
+ else
+ {
+ g_vbgldata.pFreeBlocksHead = pBlock->pNext;
+ }
+ }
+
+ pBlock->pNext = NULL;
+ pBlock->pPrev = NULL;
+}
+
+static VBGLPHYSHEAPBLOCK *vbglPhysHeapChunkAlloc (uint32_t cbSize)
+{
+ RTCCPHYS physAddr;
+ VBGLPHYSHEAPCHUNK *pChunk;
+ VBGLPHYSHEAPBLOCK *pBlock;
+ VBGL_PH_dprintf(("Allocating new chunk of size %d\n", cbSize));
+
+ /* Compute chunk size to allocate */
+ if (cbSize < VBGL_PH_CHUNKSIZE)
+ {
+ /* Includes case of block size 0 during initialization */
+ cbSize = VBGL_PH_CHUNKSIZE;
+ }
+ else
+ {
+ /* Round up to next chunk size, which must be power of 2 */
+ cbSize = (cbSize + (VBGL_PH_CHUNKSIZE - 1)) & ~(VBGL_PH_CHUNKSIZE - 1);
+ }
+
+ physAddr = 0;
+ /* This function allocates physical contiguous memory (below 4GB) according to the IPRT docs.
+ * Address < 4G is required for the port IO.
+ */
+ pChunk = (VBGLPHYSHEAPCHUNK *)RTMemContAlloc (&physAddr, cbSize);
+
+ if (!pChunk)
+ {
+ LogRel(("vbglPhysHeapChunkAlloc: failed to alloc %u contiguous bytes.\n", cbSize));
+ return NULL;
+ }
+
+ AssertRelease(physAddr < _4G && physAddr + cbSize <= _4G);
+
+ pChunk->u32Signature = VBGL_PH_CHUNKSIGNATURE;
+ pChunk->cbSize = cbSize;
+ pChunk->physAddr = (uint32_t)physAddr;
+ pChunk->cAllocatedBlocks = 0;
+ pChunk->pNext = g_vbgldata.pChunkHead;
+ pChunk->pPrev = NULL;
+
+ /* Initialize the free block, which now occupies entire chunk. */
+ pBlock = (VBGLPHYSHEAPBLOCK *)((char *)pChunk + sizeof (VBGLPHYSHEAPCHUNK));
+
+ vbglPhysHeapInitBlock (pBlock, pChunk, cbSize - sizeof (VBGLPHYSHEAPCHUNK) - sizeof (VBGLPHYSHEAPBLOCK));
+
+ vbglPhysHeapInsertBlock (NULL, pBlock);
+
+ g_vbgldata.pChunkHead = pChunk;
+
+ VBGL_PH_dprintf(("Allocated chunk %p, block = %p size=%x\n", pChunk, pBlock, cbSize));
+
+ return pBlock;
+}
+
+
+void vbglPhysHeapChunkDelete (VBGLPHYSHEAPCHUNK *pChunk)
+{
+ char *p;
+ VBGL_PH_ASSERT(pChunk != NULL);
+ VBGL_PH_ASSERTMsg(pChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE,
+ ("pChunk->u32Signature = %08X\n", pChunk->u32Signature));
+
+ VBGL_PH_dprintf(("Deleting chunk %p size %x\n", pChunk, pChunk->cbSize));
+
+ /* first scan the chunk and exclude all blocks from lists */
+
+ p = (char *)pChunk + sizeof (VBGLPHYSHEAPCHUNK);
+
+ while (p < (char *)pChunk + pChunk->cbSize)
+ {
+ VBGLPHYSHEAPBLOCK *pBlock = (VBGLPHYSHEAPBLOCK *)p;
+
+ p += pBlock->cbDataSize + sizeof (VBGLPHYSHEAPBLOCK);
+
+ vbglPhysHeapExcludeBlock (pBlock);
+ }
+
+ VBGL_PH_ASSERTMsg(p == (char *)pChunk + pChunk->cbSize,
+ ("p = %p, (char *)pChunk + pChunk->cbSize = %p, pChunk->cbSize = %08X\n",
+ p, (char *)pChunk + pChunk->cbSize, pChunk->cbSize));
+
+ /* Exclude chunk from the chunk list */
+ if (pChunk->pNext)
+ {
+ pChunk->pNext->pPrev = pChunk->pPrev;
+ }
+ else
+ {
+ /* we do not maintain tail */
+ ;
+ }
+
+ if (pChunk->pPrev)
+ {
+ pChunk->pPrev->pNext = pChunk->pNext;
+ }
+ else
+ {
+ /* the chunk was head */
+ g_vbgldata.pChunkHead = pChunk->pNext;
+ }
+
+ RTMemContFree (pChunk, pChunk->cbSize);
+}
+
+
+DECLR0VBGL(void *) VbglR0PhysHeapAlloc (uint32_t cbSize)
+{
+ VBGLPHYSHEAPBLOCK *pBlock, *iter;
+ int rc = vbglPhysHeapEnter ();
+
+ if (RT_FAILURE(rc))
+ return NULL;
+
+ dumpheap ("pre alloc");
+
+ pBlock = NULL;
+
+ /* If there are free blocks in the heap, look at them. */
+ iter = g_vbgldata.pFreeBlocksHead;
+
+ /* There will be not many blocks in the heap, so
+ * linear search would be fast enough.
+ */
+
+ while (iter)
+ {
+ if (iter->cbDataSize == cbSize)
+ {
+ /* exact match */
+ pBlock = iter;
+ break;
+ }
+
+ /* Looking for a free block with nearest size */
+ if (iter->cbDataSize > cbSize)
+ {
+ if (pBlock)
+ {
+ if (iter->cbDataSize < pBlock->cbDataSize)
+ {
+ pBlock = iter;
+ }
+ }
+ else
+ {
+ pBlock = iter;
+ }
+ }
+
+ iter = iter->pNext;
+ }
+
+ if (!pBlock)
+ {
+ /* No free blocks, allocate a new chunk,
+ * the only free block of the chunk will
+ * be returned.
+ */
+ pBlock = vbglPhysHeapChunkAlloc (cbSize);
+ }
+
+ if (pBlock)
+ {
+ VBGL_PH_ASSERTMsg(pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE,
+ ("pBlock = %p, pBlock->u32Signature = %08X\n", pBlock, pBlock->u32Signature));
+ VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) == 0,
+ ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
+
+ /* We have a free block, either found or allocated. */
+
+ if (pBlock->cbDataSize > 2*(cbSize + sizeof (VBGLPHYSHEAPBLOCK)))
+ {
+ /* Data will occupy less than a half of the block,
+ * the block should be split.
+ */
+ iter = (VBGLPHYSHEAPBLOCK *)((char *)pBlock + sizeof (VBGLPHYSHEAPBLOCK) + cbSize);
+
+ /* Init the new 'iter' block, initialized blocks are always marked as free. */
+ vbglPhysHeapInitBlock (iter, pBlock->pChunk, pBlock->cbDataSize - cbSize - sizeof (VBGLPHYSHEAPBLOCK));
+
+ pBlock->cbDataSize = cbSize;
+
+ /* Insert the new 'iter' block after the 'pBlock' in the free list */
+ vbglPhysHeapInsertBlock (pBlock, iter);
+ }
+
+ /* Exclude pBlock from free list */
+ vbglPhysHeapExcludeBlock (pBlock);
+
+ /* Mark as allocated */
+ pBlock->fu32Flags |= VBGL_PH_BF_ALLOCATED;
+
+ /* Insert to allocated list */
+ vbglPhysHeapInsertBlock (NULL, pBlock);
+
+ /* Adjust the chunk allocated blocks counter */
+ pBlock->pChunk->cAllocatedBlocks++;
+ }
+
+ dumpheap ("post alloc");
+
+ vbglPhysHeapLeave ();
+ VBGL_PH_dprintf(("VbglR0PhysHeapAlloc %x size %x\n", vbglPhysHeapBlock2Data (pBlock), pBlock->cbDataSize));
+
+ return vbglPhysHeapBlock2Data (pBlock);
+}
+
+DECLR0VBGL(uint32_t) VbglR0PhysHeapGetPhysAddr (void *p)
+{
+ uint32_t physAddr = 0;
+ VBGLPHYSHEAPBLOCK *pBlock = vbglPhysHeapData2Block (p);
+
+ if (pBlock)
+ {
+ VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) != 0,
+ ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
+
+ if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
+ physAddr = pBlock->pChunk->physAddr + (uint32_t)((uintptr_t)p - (uintptr_t)pBlock->pChunk);
+ }
+
+ return physAddr;
+}
+
+DECLR0VBGL(void) VbglR0PhysHeapFree(void *p)
+{
+ VBGLPHYSHEAPBLOCK *pBlock;
+ VBGLPHYSHEAPBLOCK *pNeighbour;
+
+ int rc = vbglPhysHeapEnter ();
+ if (RT_FAILURE(rc))
+ return;
+
+ dumpheap ("pre free");
+
+ pBlock = vbglPhysHeapData2Block (p);
+
+ if (!pBlock)
+ {
+ vbglPhysHeapLeave ();
+ return;
+ }
+
+ VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) != 0,
+ ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
+
+ /* Exclude from allocated list */
+ vbglPhysHeapExcludeBlock (pBlock);
+
+ dumpheap ("post exclude");
+
+ VBGL_PH_dprintf(("VbglR0PhysHeapFree %x size %x\n", p, pBlock->cbDataSize));
+
+ /* Mark as free */
+ pBlock->fu32Flags &= ~VBGL_PH_BF_ALLOCATED;
+
+ /* Insert to free list */
+ vbglPhysHeapInsertBlock (NULL, pBlock);
+
+ dumpheap ("post insert");
+
+ /* Adjust the chunk allocated blocks counter */
+ pBlock->pChunk->cAllocatedBlocks--;
+
+ VBGL_PH_ASSERT(pBlock->pChunk->cAllocatedBlocks >= 0);
+
+ /* 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.
+ */
+
+ pNeighbour = (VBGLPHYSHEAPBLOCK *)((char *)p + pBlock->cbDataSize);
+
+ if ((char *)pNeighbour < (char *)pBlock->pChunk + pBlock->pChunk->cbSize
+ && (pNeighbour->fu32Flags & VBGL_PH_BF_ALLOCATED) == 0)
+ {
+ /* The next block is free as well. */
+
+ /* Adjust size of current memory block */
+ pBlock->cbDataSize += pNeighbour->cbDataSize + sizeof (VBGLPHYSHEAPBLOCK);
+
+ /* Exclude the next neighbour */
+ vbglPhysHeapExcludeBlock (pNeighbour);
+ }
+
+ dumpheap ("post merge");
+
+ /* now check if there are 2 or more free chunks */
+ if (pBlock->pChunk->cAllocatedBlocks == 0)
+ {
+ VBGLPHYSHEAPCHUNK *pChunk = g_vbgldata.pChunkHead;
+
+ uint32_t u32FreeChunks = 0;
+
+ while (pChunk)
+ {
+ if (pChunk->cAllocatedBlocks == 0)
+ {
+ u32FreeChunks++;
+ }
+
+ pChunk = pChunk->pNext;
+ }
+
+ 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.
+ */
+ vbglPhysHeapChunkDelete (pBlock->pChunk);
+ }
+ }
+
+ dumpheap ("post free");
+
+ vbglPhysHeapLeave ();
+}
+
+DECLR0VBGL(int) VbglR0PhysHeapInit (void)
+{
+ int rc = VINF_SUCCESS;
+
+ /* Allocate the first chunk of the heap. */
+ VBGLPHYSHEAPBLOCK *pBlock = vbglPhysHeapChunkAlloc (0);
+
+ if (!pBlock)
+ rc = VERR_NO_MEMORY;
+
+ RTSemFastMutexCreate(&g_vbgldata.mutexHeap);
+
+ return rc;
+}
+
+DECLR0VBGL(void) VbglR0PhysHeapTerminate (void)
+{
+ while (g_vbgldata.pChunkHead)
+ {
+ vbglPhysHeapChunkDelete (g_vbgldata.pChunkHead);
+ }
+
+ RTSemFastMutexDestroy(g_vbgldata.mutexHeap);
+}
+
projects / mirror_ubuntu-bionic-kernel.git / blobdiff