/* $Id: VBoxGuestR0LibPhysHeap.cpp $ */ /** @file * VBoxGuestLibR0 - Physical memory heap. */ /* * Copyright (C) 2006-2023 Oracle and/or its affiliates. * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation * files (the "Software"), to deal in the Software without * restriction, including without limitation the rights to use, * copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following * conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR * OTHER DEALINGS IN THE SOFTWARE. */ /** @page pg_vbglr0_phys_heap VBoxGuestLibR0 - Physical memory heap. * * Traditional heap implementation keeping all blocks in a ordered list and * keeping free blocks on additional list via pointers in the user area. This * is similar to @ref grp_rt_heap_simple "RTHeapSimple" and * @ref grp_rt_heap_offset "RTHeapOffset" in IPRT, except that this code handles * mutiple chunks and has a physical address associated with each chunk and * block. The alignment is fixed (VBGL_PH_ALLOC_ALIGN). * * When allocating memory, a free block is found that satisfies the request, * extending the heap with another chunk if needed. The block is split if it's * too large, and the tail end is put on the free list. * * When freeing memory, the block being freed is put back on the free list and * we use the block list to check whether it can be merged with adjacent blocks. * * @note The original code managed the blocks in two separate lists for free and * allocated blocks, which had the disadvantage only allowing merging with * the block after the block being freed. On the plus side, it had the * potential for slightly better locality when examining the free list, * since the next pointer and block size members were closer to one * another. */ /********************************************************************************************************************************* * Header Files * *********************************************************************************************************************************/ #include "VBoxGuestR0LibInternal.h" #include #include #include #include #include /********************************************************************************************************************************* * Defined Constants And Macros * *********************************************************************************************************************************/ /** Enables heap dumping. */ #if defined(DOXYGEN_RUNNING) || 0 # define VBGL_PH_DUMPHEAP #endif #ifdef VBGL_PH_DUMPHEAP # define VBGL_PH_DPRINTF(a) RTAssertMsg2Weak a #else # define VBGL_PH_DPRINTF(a) do { } while (0) #endif /** Heap chunk signature */ #define VBGL_PH_CHUNKSIGNATURE UINT32_C(0xADDCCCCC) /** Heap chunk allocation unit */ #define VBGL_PH_CHUNKSIZE (0x10000) /** Heap block signature */ #define VBGL_PH_BLOCKSIGNATURE UINT32_C(0xADDBBBBB) /** The allocation block alignment. * * This cannot be larger than VBGLPHYSHEAPBLOCK. */ #define VBGL_PH_ALLOC_ALIGN (sizeof(void *)) /** Max number of free nodes to search before just using the best fit. * * This is used to limit the free list walking during allocation and just get * on with the job. A low number should reduce the cache trashing at the * possible cost of heap fragmentation. * * Picked 16 after comparing the tstVbglR0PhysHeap-1 results w/ uRandSeed=42 for * different max values. */ #define VBGL_PH_MAX_FREE_SEARCH 16 /** Threshold to stop the block search if a free block is at least this much too big. * * May cause more fragmation (depending on usage pattern), but should speed up * allocation and hopefully reduce cache trashing. * * Since we merge adjacent free blocks when we can, free blocks should typically * be a lot larger that what's requested. So, it is probably a good idea to * just chop up a large block rather than keep searching for a perfect-ish * match. * * Undefine this to disable this trick. */ #if defined(DOXYGEN_RUNNING) || 1 # define VBGL_PH_STOP_SEARCH_AT_EXCESS _4K #endif /** Threshold at which to split out a tail free block when allocating. * * The value gives the amount of user space, i.e. excluding the header. * * Using 32 bytes based on VMMDev.h request sizes. The smallest requests are 24 * bytes, i.e. only the header, at least 4 of these. There are at least 10 with * size 28 bytes and at least 11 with size 32 bytes. So, 32 bytes would fit * some 25 requests out of about 60, which is reasonable. */ #define VBGL_PH_MIN_SPLIT_FREE_BLOCK 32 /** The smallest amount of user data that can be allocated. * * This is to ensure that the block can be converted into a * VBGLPHYSHEAPFREEBLOCK structure when freed. This must be smaller or equal * to VBGL_PH_MIN_SPLIT_FREE_BLOCK. */ #define VBGL_PH_SMALLEST_ALLOC_SIZE 16 /** The maximum allocation request size. */ #define VBGL_PH_LARGEST_ALLOC_SIZE RT_ALIGN_32( _128M \ - sizeof(VBGLPHYSHEAPBLOCK) \ - sizeof(VBGLPHYSHEAPCHUNK) \ - VBGL_PH_ALLOC_ALIGN, \ VBGL_PH_ALLOC_ALIGN) /** * Whether to use the RTR0MemObjAllocCont API or RTMemContAlloc for * allocating chunks. * * This can be enabled on hosts where RTMemContAlloc is more complicated than * RTR0MemObjAllocCont. This can also be done if we wish to save code space, as * the latter is typically always dragged into the link on guests where the * linker cannot eliminiate functions within objects. Only drawback is that * RTR0MemObjAllocCont requires another heap allocation for the handle. */ #if defined(DOXYGEN_RUNNING) || (!defined(IN_TESTCASE) && 0) # define VBGL_PH_USE_MEMOBJ #endif /********************************************************************************************************************************* * Structures and Typedefs * *********************************************************************************************************************************/ /** * A heap block (within a chunk). * * This is used to track a part of a heap chunk that's either free or * allocated. The VBGLPHYSHEAPBLOCK::fAllocated member indicates which it is. */ struct VBGLPHYSHEAPBLOCK { /** Magic value (VBGL_PH_BLOCKSIGNATURE). */ uint32_t u32Signature; /** Size of user data in the block. Does not include this block header. */ uint32_t cbUser : 31; /** The top bit indicates whether it's allocated or free. */ uint32_t fAllocated : 1; /** Pointer to the next block on the list. */ VBGLPHYSHEAPBLOCK *pNext; /** Pointer to the previous block on the list. */ VBGLPHYSHEAPBLOCK *pPrev; /** Pointer back to the chunk. */ VBGLPHYSHEAPCHUNK *pChunk; }; /** * A free block. */ struct VBGLPHYSHEAPFREEBLOCK { /** Core block data. */ VBGLPHYSHEAPBLOCK Core; /** Pointer to the next free list entry. */ VBGLPHYSHEAPFREEBLOCK *pNextFree; /** Pointer to the previous free list entry. */ VBGLPHYSHEAPFREEBLOCK *pPrevFree; }; AssertCompile(VBGL_PH_SMALLEST_ALLOC_SIZE >= sizeof(VBGLPHYSHEAPFREEBLOCK) - sizeof(VBGLPHYSHEAPBLOCK)); AssertCompile(VBGL_PH_MIN_SPLIT_FREE_BLOCK >= sizeof(VBGLPHYSHEAPFREEBLOCK) - sizeof(VBGLPHYSHEAPBLOCK)); AssertCompile(VBGL_PH_MIN_SPLIT_FREE_BLOCK >= VBGL_PH_SMALLEST_ALLOC_SIZE); /** * A chunk of memory used by the heap for sub-allocations. * * There is a list of these. */ struct VBGLPHYSHEAPCHUNK { /** Magic value (VBGL_PH_CHUNKSIGNATURE). */ uint32_t u32Signature; /** Size of the chunk. Includes the chunk header. */ uint32_t cbChunk; /** Physical address of the chunk (contiguous). */ uint32_t physAddr; #if !defined(VBGL_PH_USE_MEMOBJ) || ARCH_BITS != 32 uint32_t uPadding1; #endif /** Number of block of any kind. */ int32_t cBlocks; /** Number of free blocks. */ int32_t cFreeBlocks; /** Pointer to the next chunk. */ VBGLPHYSHEAPCHUNK *pNext; /** Pointer to the previous chunk. */ VBGLPHYSHEAPCHUNK *pPrev; #if defined(VBGL_PH_USE_MEMOBJ) /** The allocation handle. */ RTR0MEMOBJ hMemObj; #endif #if ARCH_BITS == 64 /** Pad the size up to 64 bytes. */ # ifdef VBGL_PH_USE_MEMOBJ uintptr_t auPadding2[2]; # else uintptr_t auPadding2[3]; # endif #endif }; #if ARCH_BITS == 64 AssertCompileSize(VBGLPHYSHEAPCHUNK, 64); #endif /** * Debug function that dumps the heap. */ #ifndef VBGL_PH_DUMPHEAP # define dumpheap(pszWhere) do { } while (0) #else static void dumpheap(const char *pszWhere) { VBGL_PH_DPRINTF(("VBGL_PH dump at '%s'\n", pszWhere)); VBGL_PH_DPRINTF(("Chunks:\n")); for (VBGLPHYSHEAPCHUNK *pChunk = g_vbgldata.pChunkHead; pChunk; pChunk = pChunk->pNext) VBGL_PH_DPRINTF(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, cBlocks = %8d, cFreeBlocks=%8d, phys = %08X\n", pChunk, pChunk->pNext, pChunk->pPrev, pChunk->u32Signature, pChunk->cbChunk, pChunk->cBlocks, pChunk->cFreeBlocks, pChunk->physAddr)); VBGL_PH_DPRINTF(("Allocated blocks:\n")); for (VBGLPHYSHEAPBLOCK *pBlock = g_vbgldata.pBlockHead; pBlock; pBlock = pBlock->pNext) VBGL_PH_DPRINTF(("%p: pNext = %p, pPrev = %p, size = %05x, sign = %08X, %s, pChunk = %p\n", pBlock, pBlock->pNext, pBlock->pPrev, pBlock->cbUser, pBlock->u32Signature, pBlock->fAllocated ? "allocated" : " free", pBlock->pChunk)); VBGL_PH_DPRINTF(("Free blocks:\n")); for (VBGLPHYSHEAPFREEBLOCK *pBlock = g_vbgldata.pFreeHead; pBlock; pBlock = pBlock->pNextFree) VBGL_PH_DPRINTF(("%p: pNextFree = %p, pPrevFree = %p, size = %05x, sign = %08X, pChunk = %p%s\n", pBlock, pBlock->pNextFree, pBlock->pPrevFree, pBlock->Core.cbUser, pBlock->Core.u32Signature, pBlock->Core.pChunk, !pBlock->Core.fAllocated ? "" : " !!allocated-block-on-freelist!!")); VBGL_PH_DPRINTF(("VBGL_PH dump at '%s' done\n", pszWhere)); } #endif /** * Initialize a free block */ static void vbglPhysHeapInitFreeBlock(VBGLPHYSHEAPFREEBLOCK *pBlock, VBGLPHYSHEAPCHUNK *pChunk, uint32_t cbUser) { Assert(pBlock != NULL); Assert(pChunk != NULL); pBlock->Core.u32Signature = VBGL_PH_BLOCKSIGNATURE; pBlock->Core.cbUser = cbUser; pBlock->Core.fAllocated = false; pBlock->Core.pNext = NULL; pBlock->Core.pPrev = NULL; pBlock->Core.pChunk = pChunk; pBlock->pNextFree = NULL; pBlock->pPrevFree = NULL; } /** * Updates block statistics when a block is added. */ DECLINLINE(void) vbglPhysHeapStatsBlockAdded(VBGLPHYSHEAPBLOCK *pBlock) { g_vbgldata.cBlocks += 1; pBlock->pChunk->cBlocks += 1; AssertMsg((uint32_t)pBlock->pChunk->cBlocks <= pBlock->pChunk->cbChunk / sizeof(VBGLPHYSHEAPFREEBLOCK), ("pChunk=%p: cbChunk=%#x cBlocks=%d\n", pBlock->pChunk, pBlock->pChunk->cbChunk, pBlock->pChunk->cBlocks)); } /** * Links @a pBlock onto the head of block list. * * This also update the per-chunk block counts. */ static void vbglPhysHeapInsertBlock(VBGLPHYSHEAPBLOCK *pBlock) { AssertMsg(pBlock->pNext == NULL, ("pBlock->pNext = %p\n", pBlock->pNext)); AssertMsg(pBlock->pPrev == NULL, ("pBlock->pPrev = %p\n", pBlock->pPrev)); /* inserting to head of list */ VBGLPHYSHEAPBLOCK *pOldHead = g_vbgldata.pBlockHead; pBlock->pNext = pOldHead; pBlock->pPrev = NULL; if (pOldHead) pOldHead->pPrev = pBlock; g_vbgldata.pBlockHead = pBlock; /* Update the stats: */ vbglPhysHeapStatsBlockAdded(pBlock); } /** * Links @a pBlock onto the block list after @a pInsertAfter. * * This also update the per-chunk block counts. */ static void vbglPhysHeapInsertBlockAfter(VBGLPHYSHEAPBLOCK *pBlock, VBGLPHYSHEAPBLOCK *pInsertAfter) { AssertMsg(pBlock->pNext == NULL, ("pBlock->pNext = %p\n", pBlock->pNext)); AssertMsg(pBlock->pPrev == NULL, ("pBlock->pPrev = %p\n", pBlock->pPrev)); pBlock->pNext = pInsertAfter->pNext; pBlock->pPrev = pInsertAfter; if (pInsertAfter->pNext) pInsertAfter->pNext->pPrev = pBlock; pInsertAfter->pNext = pBlock; /* Update the stats: */ vbglPhysHeapStatsBlockAdded(pBlock); } /** * Unlinks @a pBlock from the block list. * * This also update the per-chunk block counts. */ static void vbglPhysHeapUnlinkBlock(VBGLPHYSHEAPBLOCK *pBlock) { VBGLPHYSHEAPBLOCK *pOtherBlock = pBlock->pNext; if (pOtherBlock) pOtherBlock->pPrev = pBlock->pPrev; /* else: this is tail of list but we do not maintain tails of block lists. so nothing to do. */ pOtherBlock = pBlock->pPrev; if (pOtherBlock) pOtherBlock->pNext = pBlock->pNext; else { Assert(g_vbgldata.pBlockHead == pBlock); g_vbgldata.pBlockHead = pBlock->pNext; } pBlock->pNext = NULL; pBlock->pPrev = NULL; /* Update the stats: */ g_vbgldata.cBlocks -= 1; pBlock->pChunk->cBlocks -= 1; AssertMsg(pBlock->pChunk->cBlocks >= 0, ("pChunk=%p: cbChunk=%#x cBlocks=%d\n", pBlock->pChunk, pBlock->pChunk->cbChunk, pBlock->pChunk->cBlocks)); Assert(g_vbgldata.cBlocks >= 0); } /** * Updates statistics after adding a free block. */ DECLINLINE(void) vbglPhysHeapStatsFreeBlockAdded(VBGLPHYSHEAPFREEBLOCK *pBlock) { g_vbgldata.cFreeBlocks += 1; pBlock->Core.pChunk->cFreeBlocks += 1; } /** * Links @a pBlock onto head of the free chain. * * This is used during block freeing and when adding a new chunk. * * This also update the per-chunk block counts. */ static void vbglPhysHeapInsertFreeBlock(VBGLPHYSHEAPFREEBLOCK *pBlock) { Assert(!pBlock->Core.fAllocated); AssertMsg(pBlock->pNextFree == NULL, ("pBlock->pNextFree = %p\n", pBlock->pNextFree)); AssertMsg(pBlock->pPrevFree == NULL, ("pBlock->pPrevFree = %p\n", pBlock->pPrevFree)); /* inserting to head of list */ VBGLPHYSHEAPFREEBLOCK *pOldHead = g_vbgldata.pFreeHead; pBlock->pNextFree = pOldHead; pBlock->pPrevFree = NULL; if (pOldHead) pOldHead->pPrevFree = pBlock; g_vbgldata.pFreeHead = pBlock; /* Update the stats: */ vbglPhysHeapStatsFreeBlockAdded(pBlock); } /** * Links @a pBlock after @a pInsertAfter. * * This is used when splitting a free block during allocation to preserve the * place in the free list. * * This also update the per-chunk block counts. */ static void vbglPhysHeapInsertFreeBlockAfter(VBGLPHYSHEAPFREEBLOCK *pBlock, VBGLPHYSHEAPFREEBLOCK *pInsertAfter) { Assert(!pBlock->Core.fAllocated); AssertMsg(pBlock->pNextFree == NULL, ("pBlock->pNextFree = %p\n", pBlock->pNextFree)); AssertMsg(pBlock->pPrevFree == NULL, ("pBlock->pPrevFree = %p\n", pBlock->pPrevFree)); /* inserting after the tiven node */ pBlock->pNextFree = pInsertAfter->pNextFree; pBlock->pPrevFree = pInsertAfter; if (pInsertAfter->pNextFree) pInsertAfter->pNextFree->pPrevFree = pBlock; pInsertAfter->pNextFree = pBlock; /* Update the stats: */ vbglPhysHeapStatsFreeBlockAdded(pBlock); } /** * Unlinks @a pBlock from the free list. * * This also update the per-chunk block counts. */ static void vbglPhysHeapUnlinkFreeBlock(VBGLPHYSHEAPFREEBLOCK *pBlock) { Assert(!pBlock->Core.fAllocated); VBGLPHYSHEAPFREEBLOCK *pOtherBlock = pBlock->pNextFree; if (pOtherBlock) pOtherBlock->pPrevFree = pBlock->pPrevFree; /* else: this is tail of list but we do not maintain tails of block lists. so nothing to do. */ pOtherBlock = pBlock->pPrevFree; if (pOtherBlock) pOtherBlock->pNextFree = pBlock->pNextFree; else { Assert(g_vbgldata.pFreeHead == pBlock); g_vbgldata.pFreeHead = pBlock->pNextFree; } pBlock->pNextFree = NULL; pBlock->pPrevFree = NULL; /* Update the stats: */ g_vbgldata.cFreeBlocks -= 1; pBlock->Core.pChunk->cFreeBlocks -= 1; AssertMsg(pBlock->Core.pChunk->cFreeBlocks >= 0, ("pChunk=%p: cbChunk=%#x cFreeBlocks=%d\n", pBlock->Core.pChunk, pBlock->Core.pChunk->cbChunk, pBlock->Core.pChunk->cFreeBlocks)); Assert(g_vbgldata.cFreeBlocks >= 0); } /** * Allocate another chunk and add it to the heap. * * @returns Pointer to the free block in the new chunk on success, NULL on * allocation failure. * @param cbMinBlock The size of the user block we need this chunk for. */ static VBGLPHYSHEAPFREEBLOCK *vbglPhysHeapChunkAlloc(uint32_t cbMinBlock) { RTCCPHYS PhysAddr = NIL_RTHCPHYS; VBGLPHYSHEAPCHUNK *pChunk; uint32_t cbChunk; #ifdef VBGL_PH_USE_MEMOBJ RTR0MEMOBJ hMemObj = NIL_RTR0MEMOBJ; int rc; #endif VBGL_PH_DPRINTF(("Allocating new chunk for %#x byte allocation\n", cbMinBlock)); AssertReturn(cbMinBlock <= VBGL_PH_LARGEST_ALLOC_SIZE, NULL); /* paranoia */ /* * Compute the size of the new chunk, rounding up to next chunk size, * which must be power of 2. * * Note! Using VBGLPHYSHEAPFREEBLOCK here means the minimum block size is * 8 or 16 bytes too high, but safer this way since cbMinBlock is * zero during the init code call. */ Assert(RT_IS_POWER_OF_TWO(VBGL_PH_CHUNKSIZE)); cbChunk = cbMinBlock + sizeof(VBGLPHYSHEAPCHUNK) + sizeof(VBGLPHYSHEAPFREEBLOCK); cbChunk = RT_ALIGN_32(cbChunk, VBGL_PH_CHUNKSIZE); /* * This function allocates physical contiguous memory below 4 GB. This 4GB * limitation stems from using a 32-bit OUT instruction to pass a block * physical address to the host. */ #ifdef VBGL_PH_USE_MEMOBJ rc = RTR0MemObjAllocCont(&hMemObj, cbChunk, false /*fExecutable*/); pChunk = (VBGLPHYSHEAPCHUNK *)(RT_SUCCESS(rc) ? RTR0MemObjAddress(hMemObj) : NULL); #else pChunk = (VBGLPHYSHEAPCHUNK *)RTMemContAlloc(&PhysAddr, cbChunk); #endif if (!pChunk) { /* If the allocation fail, halv the size till and try again. */ uint32_t cbMinChunk = RT_MAX(cbMinBlock, PAGE_SIZE / 2) + sizeof(VBGLPHYSHEAPCHUNK) + sizeof(VBGLPHYSHEAPFREEBLOCK); cbMinChunk = RT_ALIGN_32(cbMinChunk, PAGE_SIZE); if (cbChunk > cbMinChunk) do { cbChunk >>= 2; cbChunk = RT_ALIGN_32(cbChunk, PAGE_SIZE); #ifdef VBGL_PH_USE_MEMOBJ rc = RTR0MemObjAllocCont(&hMemObj, cbChunk, false /*fExecutable*/); pChunk = (VBGLPHYSHEAPCHUNK *)(RT_SUCCESS(rc) ? RTR0MemObjAddress(hMemObj) : NULL); #else pChunk = (VBGLPHYSHEAPCHUNK *)RTMemContAlloc(&PhysAddr, cbChunk); #endif } while (!pChunk && cbChunk > cbMinChunk); } if (pChunk) { VBGLPHYSHEAPCHUNK *pOldHeadChunk; VBGLPHYSHEAPFREEBLOCK *pBlock; AssertRelease(PhysAddr < _4G && PhysAddr + cbChunk <= _4G); /* * Init the new chunk. */ pChunk->u32Signature = VBGL_PH_CHUNKSIGNATURE; pChunk->cbChunk = cbChunk; pChunk->physAddr = (uint32_t)PhysAddr; pChunk->cBlocks = 0; pChunk->cFreeBlocks = 0; pChunk->pNext = NULL; pChunk->pPrev = NULL; #ifdef VBGL_PH_USE_MEMOBJ pChunk->hMemObj = hMemObj; #endif /* Initialize the padding too: */ #if !defined(VBGL_PH_USE_MEMOBJ) || ARCH_BITS != 32 pChunk->uPadding1 = UINT32_C(0xADDCAAA1); #endif #if ARCH_BITS == 64 pChunk->auPadding2[0] = UINT64_C(0xADDCAAA3ADDCAAA2); pChunk->auPadding2[1] = UINT64_C(0xADDCAAA5ADDCAAA4); # ifndef VBGL_PH_USE_MEMOBJ pChunk->auPadding2[2] = UINT64_C(0xADDCAAA7ADDCAAA6); # endif #endif /* * Initialize the free block, which now occupies entire chunk. */ pBlock = (VBGLPHYSHEAPFREEBLOCK *)(pChunk + 1); vbglPhysHeapInitFreeBlock(pBlock, pChunk, cbChunk - sizeof(VBGLPHYSHEAPCHUNK) - sizeof(VBGLPHYSHEAPBLOCK)); vbglPhysHeapInsertBlock(&pBlock->Core); vbglPhysHeapInsertFreeBlock(pBlock); /* * Add the chunk to the list. */ pOldHeadChunk = g_vbgldata.pChunkHead; pChunk->pNext = pOldHeadChunk; if (pOldHeadChunk) pOldHeadChunk->pPrev = pChunk; g_vbgldata.pChunkHead = pChunk; VBGL_PH_DPRINTF(("Allocated chunk %p LB %#x, block %p LB %#x\n", pChunk, cbChunk, pBlock, pBlock->Core.cbUser)); return pBlock; } LogRel(("vbglPhysHeapChunkAlloc: failed to alloc %u (%#x) contiguous bytes.\n", cbChunk, cbChunk)); return NULL; } /** * Deletes a chunk: Unlinking all its blocks and freeing its memory. */ static void vbglPhysHeapChunkDelete(VBGLPHYSHEAPCHUNK *pChunk) { uintptr_t uEnd, uCur; Assert(pChunk != NULL); AssertMsg(pChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE, ("pChunk->u32Signature = %08X\n", pChunk->u32Signature)); VBGL_PH_DPRINTF(("Deleting chunk %p size %x\n", pChunk, pChunk->cbChunk)); /* * First scan the chunk and unlink all blocks from the lists. * * Note! We could do this by finding the first and last block list entries * and just drop the whole chain relating to this chunk, rather than * doing it one by one. But doing it one by one is simpler and will * continue to work if the block list ends in an unsorted state. */ uEnd = (uintptr_t)pChunk + pChunk->cbChunk; uCur = (uintptr_t)(pChunk + 1); while (uCur < uEnd) { VBGLPHYSHEAPBLOCK *pBlock = (VBGLPHYSHEAPBLOCK *)uCur; Assert(pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE); Assert(pBlock->pChunk == pChunk); uCur += pBlock->cbUser + sizeof(VBGLPHYSHEAPBLOCK); Assert(uCur == (uintptr_t)pBlock->pNext || uCur >= uEnd); if (!pBlock->fAllocated) vbglPhysHeapUnlinkFreeBlock((VBGLPHYSHEAPFREEBLOCK *)pBlock); vbglPhysHeapUnlinkBlock(pBlock); } AssertMsg(uCur == uEnd, ("uCur = %p, uEnd = %p, pChunk->cbChunk = %08X\n", uCur, uEnd, pChunk->cbChunk)); /* * Unlink the chunk from the chunk list. */ if (pChunk->pNext) pChunk->pNext->pPrev = pChunk->pPrev; /* else: we do not maintain tail pointer. */ if (pChunk->pPrev) pChunk->pPrev->pNext = pChunk->pNext; else { Assert(g_vbgldata.pChunkHead == pChunk); g_vbgldata.pChunkHead = pChunk->pNext; } /* * Finally, free the chunk memory. */ #ifdef VBGL_PH_USE_MEMOBJ RTR0MemObjFree(pChunk->hMemObj, true /*fFreeMappings*/); #else RTMemContFree(pChunk, pChunk->cbChunk); #endif } DECLR0VBGL(void *) VbglR0PhysHeapAlloc(uint32_t cb) { VBGLPHYSHEAPFREEBLOCK *pBlock; VBGLPHYSHEAPFREEBLOCK *pIter; int32_t cLeft; #ifdef VBGL_PH_STOP_SEARCH_AT_EXCESS uint32_t cbAlwaysSplit; #endif int rc; /* * Make sure we don't allocate anything too small to turn into a free node * and align the size to prevent pointer misalignment and whatnot. */ cb = RT_MAX(cb, VBGL_PH_SMALLEST_ALLOC_SIZE); cb = RT_ALIGN_32(cb, VBGL_PH_ALLOC_ALIGN); AssertCompile(VBGL_PH_ALLOC_ALIGN <= sizeof(pBlock->Core)); rc = RTSemFastMutexRequest(g_vbgldata.hMtxHeap); AssertRCReturn(rc, NULL); dumpheap("pre alloc"); /* * Search the free list. We do this in linear fashion as we don't expect * there to be many blocks in the heap. */ #ifdef VBGL_PH_STOP_SEARCH_AT_EXCESS cbAlwaysSplit = cb + VBGL_PH_STOP_SEARCH_AT_EXCESS; #endif cLeft = VBGL_PH_MAX_FREE_SEARCH; pBlock = NULL; if (cb <= PAGE_SIZE / 4 * 3) { /* Smaller than 3/4 page: Prefer a free block that can keep the request within a single page, so HGCM processing in VMMDev can use page locks instead of several reads and writes. */ VBGLPHYSHEAPFREEBLOCK *pFallback = NULL; for (pIter = g_vbgldata.pFreeHead; pIter != NULL; pIter = pIter->pNextFree, cLeft--) { AssertBreak(pIter->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE); if (pIter->Core.cbUser >= cb) { if (pIter->Core.cbUser == cb) { if (PAGE_SIZE - ((uintptr_t)(pIter + 1) & PAGE_OFFSET_MASK) >= cb) { pBlock = pIter; break; } pFallback = pIter; } else { if (!pFallback || pIter->Core.cbUser < pFallback->Core.cbUser) pFallback = pIter; if (PAGE_SIZE - ((uintptr_t)(pIter + 1) & PAGE_OFFSET_MASK) >= cb) { if (!pBlock || pIter->Core.cbUser < pBlock->Core.cbUser) pBlock = pIter; #ifdef VBGL_PH_STOP_SEARCH_AT_EXCESS else if (pIter->Core.cbUser >= cbAlwaysSplit) { pBlock = pIter; break; } #endif } } if (cLeft > 0) { /* likely */ } else break; } } if (!pBlock) pBlock = pFallback; } else { /* Large than 3/4 page: Find closest free list match. */ for (pIter = g_vbgldata.pFreeHead; pIter != NULL; pIter = pIter->pNextFree, cLeft--) { AssertBreak(pIter->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE); if (pIter->Core.cbUser >= cb) { if (pIter->Core.cbUser == cb) { /* Exact match - we're done! */ pBlock = pIter; break; } #ifdef VBGL_PH_STOP_SEARCH_AT_EXCESS if (pIter->Core.cbUser >= cbAlwaysSplit) { /* Really big block - no point continue searching! */ pBlock = pIter; break; } #endif /* Looking for a free block with nearest size. */ if (!pBlock || pIter->Core.cbUser < pBlock->Core.cbUser) pBlock = pIter; if (cLeft > 0) { /* likely */ } else break; } } } if (!pBlock) { /* No free blocks, allocate a new chunk, the only free block of the chunk will be returned. */ pBlock = vbglPhysHeapChunkAlloc(cb); } if (pBlock) { /* We have a free block, either found or allocated. */ AssertMsg(pBlock->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE, ("pBlock = %p, pBlock->u32Signature = %08X\n", pBlock, pBlock->Core.u32Signature)); AssertMsg(!pBlock->Core.fAllocated, ("pBlock = %p\n", pBlock)); /* * If the block is too large, split off a free block with the unused space. * * We do this before unlinking the block so we can preserve the location * in the free list. * * Note! We cannot split off and return the tail end here, because that may * violate the same page requirements for requests smaller than 3/4 page. */ AssertCompile(VBGL_PH_MIN_SPLIT_FREE_BLOCK >= sizeof(*pBlock) - sizeof(pBlock->Core)); if (pBlock->Core.cbUser >= sizeof(VBGLPHYSHEAPBLOCK) * 2 + VBGL_PH_MIN_SPLIT_FREE_BLOCK + cb) { pIter = (VBGLPHYSHEAPFREEBLOCK *)((uintptr_t)(&pBlock->Core + 1) + cb); vbglPhysHeapInitFreeBlock(pIter, pBlock->Core.pChunk, pBlock->Core.cbUser - cb - sizeof(VBGLPHYSHEAPBLOCK)); pBlock->Core.cbUser = cb; /* Insert the new 'pIter' block after the 'pBlock' in the block list and in the free list. */ vbglPhysHeapInsertBlockAfter(&pIter->Core, &pBlock->Core); vbglPhysHeapInsertFreeBlockAfter(pIter, pBlock); } /* * Unlink the block from the free list and mark it as allocated. */ vbglPhysHeapUnlinkFreeBlock(pBlock); pBlock->Core.fAllocated = true; dumpheap("post alloc"); /* * Return success. */ rc = RTSemFastMutexRelease(g_vbgldata.hMtxHeap); VBGL_PH_DPRINTF(("VbglR0PhysHeapAlloc: returns %p size %x\n", pBlock + 1, pBlock->Core.cbUser)); return &pBlock->Core + 1; } /* * Return failure. */ rc = RTSemFastMutexRelease(g_vbgldata.hMtxHeap); AssertRC(rc); VBGL_PH_DPRINTF(("VbglR0PhysHeapAlloc: returns NULL (requested %#x bytes)\n", cb)); return NULL; } DECLR0VBGL(uint32_t) VbglR0PhysHeapGetPhysAddr(void *pv) { /* * Validate the incoming pointer. */ if (pv != NULL) { VBGLPHYSHEAPBLOCK *pBlock = (VBGLPHYSHEAPBLOCK *)pv - 1; if ( pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE && pBlock->fAllocated) { /* * Calculate and return its physical address. */ VBGLPHYSHEAPCHUNK *pChunk = pBlock->pChunk; return pChunk->physAddr + (uint32_t)((uintptr_t)pv - (uintptr_t)pChunk); } AssertMsgFailed(("Use after free or corrupt pointer variable: pv=%p pBlock=%p: u32Signature=%#x cb=%#x fAllocated=%d\n", pv, pBlock, pBlock->u32Signature, pBlock->cbUser, pBlock->fAllocated)); } else AssertMsgFailed(("Unexpected NULL pointer\n")); return 0; } DECLR0VBGL(void) VbglR0PhysHeapFree(void *pv) { if (pv != NULL) { VBGLPHYSHEAPFREEBLOCK *pBlock; int rc = RTSemFastMutexRequest(g_vbgldata.hMtxHeap); AssertRCReturnVoid(rc); dumpheap("pre free"); /* * Validate the block header. */ pBlock = (VBGLPHYSHEAPFREEBLOCK *)((VBGLPHYSHEAPBLOCK *)pv - 1); if ( pBlock->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE && pBlock->Core.fAllocated && pBlock->Core.cbUser >= VBGL_PH_SMALLEST_ALLOC_SIZE) { VBGLPHYSHEAPCHUNK *pChunk; VBGLPHYSHEAPBLOCK *pNeighbour; /* * Change the block status to freeed. */ VBGL_PH_DPRINTF(("VbglR0PhysHeapFree: %p size %#x\n", pv, pBlock->Core.cbUser)); pBlock->Core.fAllocated = false; pBlock->pNextFree = pBlock->pPrevFree = NULL; vbglPhysHeapInsertFreeBlock(pBlock); dumpheap("post insert"); /* * Check if the block after this one is also free and we can merge it into this one. */ pChunk = pBlock->Core.pChunk; pNeighbour = pBlock->Core.pNext; if ( pNeighbour && !pNeighbour->fAllocated && pNeighbour->pChunk == pChunk) { Assert((uintptr_t)pBlock + sizeof(pBlock->Core) + pBlock->Core.cbUser == (uintptr_t)pNeighbour); /* Adjust size of current memory block */ pBlock->Core.cbUser += pNeighbour->cbUser + sizeof(VBGLPHYSHEAPBLOCK); /* Unlink the following node and invalid it. */ vbglPhysHeapUnlinkFreeBlock((VBGLPHYSHEAPFREEBLOCK *)pNeighbour); vbglPhysHeapUnlinkBlock(pNeighbour); pNeighbour->u32Signature = ~VBGL_PH_BLOCKSIGNATURE; pNeighbour->cbUser = UINT32_MAX / 4; dumpheap("post merge after"); } /* * Same check for the block before us. This invalidates pBlock. */ pNeighbour = pBlock->Core.pPrev; if ( pNeighbour && !pNeighbour->fAllocated && pNeighbour->pChunk == pChunk) { Assert((uintptr_t)pNeighbour + sizeof(*pNeighbour) + pNeighbour->cbUser == (uintptr_t)pBlock); /* Adjust size of the block before us */ pNeighbour->cbUser += pBlock->Core.cbUser + sizeof(VBGLPHYSHEAPBLOCK); /* Unlink this node and invalid it. */ vbglPhysHeapUnlinkFreeBlock(pBlock); vbglPhysHeapUnlinkBlock(&pBlock->Core); pBlock->Core.u32Signature = ~VBGL_PH_BLOCKSIGNATURE; pBlock->Core.cbUser = UINT32_MAX / 8; pBlock = NULL; /* invalid */ dumpheap("post merge before"); } /* * If this chunk is now completely unused, delete it if there are * more completely free ones. */ if ( pChunk->cFreeBlocks == pChunk->cBlocks && (pChunk->pPrev || pChunk->pNext)) { VBGLPHYSHEAPCHUNK *pCurChunk; uint32_t cUnusedChunks = 0; for (pCurChunk = g_vbgldata.pChunkHead; pCurChunk; pCurChunk = pCurChunk->pNext) { AssertBreak(pCurChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE); if (pCurChunk->cFreeBlocks == pCurChunk->cBlocks) { cUnusedChunks++; if (cUnusedChunks > 1) { /* Delete current chunk, it will also unlink all free blocks * remaining in the chunk from the free list, so the pBlock * will also be invalid after this. */ vbglPhysHeapChunkDelete(pChunk); pBlock = NULL; /* invalid */ pChunk = NULL; pNeighbour = NULL; break; } } } } dumpheap("post free"); } else AssertMsgFailed(("pBlock: %p: u32Signature=%#x cb=%#x fAllocated=%d - double free?\n", pBlock, pBlock->Core.u32Signature, pBlock->Core.cbUser, pBlock->Core.fAllocated)); rc = RTSemFastMutexRelease(g_vbgldata.hMtxHeap); AssertRC(rc); } } #ifdef IN_TESTCASE /* For the testcase only */ /** * Returns the sum of all free heap blocks. * * This is the amount of memory you can theoretically allocate if you do * allocations exactly matching the free blocks. * * @returns The size of the free blocks. * @returns 0 if heap was safely detected as being bad. */ DECLVBGL(size_t) VbglR0PhysHeapGetFreeSize(void) { int rc = RTSemFastMutexRequest(g_vbgldata.hMtxHeap); AssertRCReturn(rc, 0); size_t cbTotal = 0; for (VBGLPHYSHEAPFREEBLOCK *pCurBlock = g_vbgldata.pFreeHead; pCurBlock; pCurBlock = pCurBlock->pNextFree) { Assert(pCurBlock->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE); Assert(!pCurBlock->Core.fAllocated); cbTotal += pCurBlock->Core.cbUser; } RTSemFastMutexRelease(g_vbgldata.hMtxHeap); return cbTotal; } /** * Checks the heap, caller responsible for locking. * * @returns VINF_SUCCESS if okay, error status if not. * @param pErrInfo Where to return more error details, optional. */ static int vbglR0PhysHeapCheckLocked(PRTERRINFO pErrInfo) { /* * Scan the blocks in each chunk, walking the block list in parallel. */ const VBGLPHYSHEAPBLOCK *pPrevBlockListEntry = NULL; const VBGLPHYSHEAPBLOCK *pCurBlockListEntry = g_vbgldata.pBlockHead; unsigned acTotalBlocks[2] = { 0, 0 }; for (VBGLPHYSHEAPCHUNK *pCurChunk = g_vbgldata.pChunkHead, *pPrevChunk = NULL; pCurChunk; pCurChunk = pCurChunk->pNext) { AssertReturn(pCurChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE, RTErrInfoSetF(pErrInfo, VERR_INVALID_MAGIC, "pCurChunk=%p: magic=%#x", pCurChunk, pCurChunk->u32Signature)); AssertReturn(pCurChunk->pPrev == pPrevChunk, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_2, "pCurChunk=%p: pPrev=%p, expected %p", pCurChunk, pCurChunk->pPrev, pPrevChunk)); const VBGLPHYSHEAPBLOCK *pCurBlock = (const VBGLPHYSHEAPBLOCK *)(pCurChunk + 1); uintptr_t const uEnd = (uintptr_t)pCurChunk + pCurChunk->cbChunk; unsigned acBlocks[2] = { 0, 0 }; while ((uintptr_t)pCurBlock < uEnd) { AssertReturn(pCurBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE, RTErrInfoSetF(pErrInfo, VERR_INVALID_MAGIC, "pCurBlock=%p: magic=%#x", pCurBlock, pCurBlock->u32Signature)); AssertReturn(pCurBlock->pChunk == pCurChunk, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_2, "pCurBlock=%p: pChunk=%p, expected %p", pCurBlock, pCurBlock->pChunk, pCurChunk)); AssertReturn( pCurBlock->cbUser >= VBGL_PH_SMALLEST_ALLOC_SIZE && pCurBlock->cbUser <= VBGL_PH_LARGEST_ALLOC_SIZE && RT_ALIGN_32(pCurBlock->cbUser, VBGL_PH_ALLOC_ALIGN) == pCurBlock->cbUser, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_3, "pCurBlock=%p: cbUser=%#x", pCurBlock, pCurBlock->cbUser)); AssertReturn(pCurBlock == pCurBlockListEntry, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_4, "pCurChunk=%p: pCurBlock=%p, pCurBlockListEntry=%p\n", pCurChunk, pCurBlock, pCurBlockListEntry)); AssertReturn(pCurBlock->pPrev == pPrevBlockListEntry, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_5, "pCurChunk=%p: pCurBlock->pPrev=%p, pPrevBlockListEntry=%p\n", pCurChunk, pCurBlock->pPrev, pPrevBlockListEntry)); acBlocks[pCurBlock->fAllocated] += 1; /* advance */ pPrevBlockListEntry = pCurBlock; pCurBlockListEntry = pCurBlock->pNext; pCurBlock = (const VBGLPHYSHEAPBLOCK *)((uintptr_t)(pCurBlock + 1) + pCurBlock->cbUser); } AssertReturn((uintptr_t)pCurBlock == uEnd, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_4, "pCurBlock=%p uEnd=%p", pCurBlock, uEnd)); acTotalBlocks[1] += acBlocks[1]; AssertReturn(acBlocks[0] + acBlocks[1] == (uint32_t)pCurChunk->cBlocks, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_4, "pCurChunk=%p: cBlocks=%u, expected %u", pCurChunk, pCurChunk->cBlocks, acBlocks[0] + acBlocks[1])); acTotalBlocks[0] += acBlocks[0]; AssertReturn(acBlocks[0] == (uint32_t)pCurChunk->cFreeBlocks, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_5, "pCurChunk=%p: cFreeBlocks=%u, expected %u", pCurChunk, pCurChunk->cFreeBlocks, acBlocks[0])); pPrevChunk = pCurChunk; } AssertReturn(acTotalBlocks[0] == (uint32_t)g_vbgldata.cFreeBlocks, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR, "g_vbgldata.cFreeBlocks=%u, expected %u", g_vbgldata.cFreeBlocks, acTotalBlocks[0])); AssertReturn(acTotalBlocks[0] + acTotalBlocks[1] == (uint32_t)g_vbgldata.cBlocks, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR, "g_vbgldata.cBlocks=%u, expected %u", g_vbgldata.cBlocks, acTotalBlocks[0] + acTotalBlocks[1])); /* * Check that the free list contains the same number of blocks as we * encountered during the above scan. */ { unsigned cFreeListBlocks = 0; for (const VBGLPHYSHEAPFREEBLOCK *pCurBlock = g_vbgldata.pFreeHead, *pPrevBlock = NULL; pCurBlock; pCurBlock = pCurBlock->pNextFree) { AssertReturn(pCurBlock->Core.u32Signature == VBGL_PH_BLOCKSIGNATURE, RTErrInfoSetF(pErrInfo, VERR_INVALID_MAGIC, "pCurBlock=%p/free: magic=%#x", pCurBlock, pCurBlock->Core.u32Signature)); AssertReturn(pCurBlock->pPrevFree == pPrevBlock, RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_2, "pCurBlock=%p/free: pPrev=%p, expected %p", pCurBlock, pCurBlock->pPrevFree, pPrevBlock)); AssertReturn(pCurBlock->Core.pChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE, RTErrInfoSetF(pErrInfo, VERR_INVALID_MAGIC, "pCurBlock=%p/free: chunk (%p) magic=%#x", pCurBlock, pCurBlock->Core.pChunk, pCurBlock->Core.pChunk->u32Signature)); cFreeListBlocks++; pPrevBlock = pCurBlock; } AssertReturn(cFreeListBlocks == acTotalBlocks[0], RTErrInfoSetF(pErrInfo, VERR_INTERNAL_ERROR_3, "Found %u in free list, expected %u", cFreeListBlocks, acTotalBlocks[0])); } return VINF_SUCCESS; } /** * Performs a heap check. * * @returns Problem description on failure, NULL on success. * @param pErrInfo Where to return more error details, optional. */ DECLVBGL(int) VbglR0PhysHeapCheck(PRTERRINFO pErrInfo) { int rc = RTSemFastMutexRequest(g_vbgldata.hMtxHeap); AssertRCReturn(rc, 0); rc = vbglR0PhysHeapCheckLocked(pErrInfo); RTSemFastMutexRelease(g_vbgldata.hMtxHeap); return rc; } #endif /* IN_TESTCASE */ DECLR0VBGL(int) VbglR0PhysHeapInit(void) { g_vbgldata.hMtxHeap = NIL_RTSEMFASTMUTEX; /* Allocate the first chunk of the heap. */ VBGLPHYSHEAPFREEBLOCK *pBlock = vbglPhysHeapChunkAlloc(0); if (pBlock) return RTSemFastMutexCreate(&g_vbgldata.hMtxHeap); return VERR_NO_CONT_MEMORY; } DECLR0VBGL(void) VbglR0PhysHeapTerminate(void) { while (g_vbgldata.pChunkHead) vbglPhysHeapChunkDelete(g_vbgldata.pChunkHead); RTSemFastMutexDestroy(g_vbgldata.hMtxHeap); g_vbgldata.hMtxHeap = NIL_RTSEMFASTMUTEX; }