HGSMIMemAlloc.cpp revision c107091c0fb9efb797884658dd19dd002358b0e2
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Copyright (C) 2014 Oracle Corporation
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * available from http://www.virtualbox.org. This file is free software;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * you can redistribute it and/or modify it under the terms of the GNU
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * General Public License (GPL) as published by the Free Software
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Memory allocator
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * ----------------
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Area [0; AreaSize) contains only the data, control structures are separate.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Block sizes are power of 2: 32B, ..., 1MB
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Area size can be anything and will be divided initially to largest possible free blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * The entire area is described by a list of 32 bit block descriptors:
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * bits 0..3 - order, which is log2 size of the block - 5: 2^(0+5) ... 2^(15+5) == 32B .. 1MB
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * bit 4 - 1 for free blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * bits 5..31 - block offset.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * 31 ... 5 | 4 | 3 ... 0
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * offset F order
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * There is a sorted collection of all block descriptors
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * (key is the block offset, bits 0...4 do not interfere with sorting).
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Also there are lists of free blocks for each size for fast allocation.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Implementation
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * --------------
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * The blocks collection is a sorted linear list.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Initially the entire area consists of one or more largest blocks followed by smaller blocks:
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * 100B area - 64B block with descriptor: 0x00000011
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * 32B block with descriptor: 0x00000030
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * 4B unused
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * 64K area - one 64K block with descriptor: 0x0000001C
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * 512K area - one 512K block with descriptor: 0x0000001F
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * When allocating a new block:
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * larger free blocks are splitted when there are no smaller free blocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * * smaller free blocks are merged if they can build a requested larger block.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncDECLINLINE(HGSMIOFFSET) hgsmiMADescriptor(HGSMIOFFSET off, bool fFree, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMABlockFree(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMABlockAlloc(HGSMIMADATA *pMA, HGSMIMABLOCK **ppBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pBlock = (HGSMIMABLOCK *)pMA->env.pfnAlloc(pMA->env.pvEnv, sizeof(HGSMIMABLOCK));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/* Divide entire area to free blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Initial value, it will be updated in the loop below. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Build a list of free memory blocks with u32BlockSize. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = 0; i < cBlocks; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* A new free block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock->descriptor = hgsmiMADescriptor(off, true, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMARebuildFreeLists(HGSMIMADATA *pMA)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListForEach(&pMA->listBlocks, pIter, HGSMIMABLOCK, nodeBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET order = HGSMI_MA_DESC_ORDER(pIter->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->aListFreeBlocks[order], &pIter->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMARestore(HGSMIMADATA *pMA, HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = 0; i < cDescriptors; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Verify the descriptor. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMISIZE cbBlock = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(paDescriptors[i]));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* A new free block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic HGSMIMABLOCK *hgsmiMAGetFreeBlock(HGSMIMADATA *pMA, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = order; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock = RTListGetFirst(&pMA->aListFreeBlocks[i], HGSMIMABLOCK, nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync AssertReturn(HGSMI_MA_DESC_IS_FREE(pBlock->descriptor), NULL);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Where the block starts. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pBlock->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* 'i' is the order of the block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync while (i != order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* A larger block was found and need to be split to 2 smaller blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Create 2 blocks with descreased order. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Remove from the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock->descriptor = hgsmiMADescriptor(off, true, i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock2->descriptor = hgsmiMADescriptor(off + HGSMIMAOrder2Size(i), true, i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Update list of all blocks by inserting pBlock2 after pBlock. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListNodeInsertAfter(&pBlock->nodeBlock, &pBlock2->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Update the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->aListFreeBlocks[i], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->aListFreeBlocks[i], &pBlock2->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAReformatFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET maxId,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pStart, HGSMIMABLOCK *pEnd, HGSMISIZE cbBlocks)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Blocks starting from pStart until pEnd will be replaced with
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * another set of blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * The new set will include the block with the required order.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Since the required order is larger than any existing block,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * it will replace at least two existing blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * The new set will also have minimal possible number of blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Therefore the new set will have at least one block less.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Blocks will be updated in place and remaining blocks will be
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * deallocated.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pStart->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync while (u32BlockSize >= HGSMI_MA_BLOCK_SIZE_MIN && cbRemaining)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Build a list of free memory blocks with u32BlockSize. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET order = HGSMIMASize2Order(u32BlockSize);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = 0; i < cBlocks; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Should never happen because the new set of blocks is supposed to be smaller. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Remove from the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock->descriptor = hgsmiMADescriptor(off, true, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->aListFreeBlocks[order], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pBlock = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Remove remaining free blocks from pBlock until pEnd */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pNext = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAQueryFreeRange(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock, HGSMISIZE cbRequired,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK **ppStart, HGSMIMABLOCK **ppEnd, HGSMISIZE *pcbBlocks)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *pcbBlocks = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(pBlock->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync p = RTListGetNext(&pMA->listBlocks, *ppEnd, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync p = RTListGetPrev(&pMA->listBlocks, *ppStart, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAMergeFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Try to create a free block with the order from smaller free blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* No smaller blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Scan all free lists of smaller blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Get the sequence of free blocks before and after each free block.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * If possible, re-split the sequence to get the required block and other free block(s).
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * If not possible, try the next free block.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Free blocks are scanned from i to 0 orders.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListForEach(&pMA->aListFreeBlocks[i], pIter, HGSMIMABLOCK, nodeFree)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync Assert(HGSMI_MA_DESC_ORDER(pIter->descriptor) == i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync hgsmiMAQueryFreeRange(pMA, pIter, cbRequired, &pFreeStart, &pFreeEnd, &cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync Assert((cbBlocks / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Verify whether cbBlocks is enough for the requested block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Build new free blocks starting from the requested. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync hgsmiMAReformatFreeBlocks(pMA, order, pFreeStart, pFreeEnd, cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync i = 0; /* Leave the loop. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync if (i == 0)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic HGSMIOFFSET hgsmiMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET order = HGSMIPopCnt32(cb - 1) - HGSMI_MA_DESC_ORDER_BASE;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync AssertReturn(HGSMIMAOrder2Size(order) >= cb, HGSMIOFFSET_VOID);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync AssertReturn(order < RT_ELEMENTS(pMA->aListFreeBlocks), HGSMIOFFSET_VOID);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pBlock = hgsmiMAGetFreeBlock(pMA, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* No free block with large enough size. Merge smaller free blocks and try again. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAFree(HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Find the block corresponding to the offset. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync Assert((off / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pBlock = HGSMIMASearchOffset(pMA, off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync if (HGSMI_MA_DESC_OFFSET(pBlock->descriptor) == off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Found the right block, mark it as free. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListAppend(&pMA->aListFreeBlocks[HGSMI_MA_DESC_ORDER(pBlock->descriptor)], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncint HGSMIMAInit(HGSMIMADATA *pMA, const HGSMIAREA *pArea,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync AssertReturn(pArea->cbArea < UINT32_C(0x80000000), VERR_INVALID_PARAMETER);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync AssertReturn(pArea->cbArea >= HGSMI_MA_BLOCK_SIZE_MIN, VERR_INVALID_PARAMETER);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMISIZE cb = (pArea->cbArea / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync int rc = HGSMIAreaInitialize(&pMA->area, pArea->pu8Base, cb, 0);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = 0; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync rc = hgsmiMARestore(pMA, paDescriptors, cDescriptors, cbMaxBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync RTListForEachSafe(&pMA->listBlocks, pIter, pNext, HGSMIMABLOCK, nodeBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncHGSMIOFFSET HGSMIMAPointerToOffset(const HGSMIMADATA *pMA, const void *pv)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncvoid *HGSMIMAOffsetToPointer(const HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncHGSMIMABLOCK *HGSMIMASearchOffset(HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Binary search in the block list for the offset. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pStart = RTListGetFirst(&pMA->listBlocks, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIMABLOCK *pEnd = RTListGetLast(&pMA->listBlocks, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync /* Find the block with the iMiddle index. Never go further than pEnd. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync for (i = iStart; i < iMiddle && pMiddle != pEnd; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync pMiddle = RTListNodeGetNext(&pMiddle->nodeBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync HGSMIOFFSET offMiddle = HGSMI_MA_DESC_OFFSET(pMiddle->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync return c + u32;