GuestHost/HGSMI/HGSMIMemAlloc.cpp

c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/* $Id$ */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/** @file
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/*
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Copyright (C) 2014 Oracle Corporation
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *
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 */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/*
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Memory allocator
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * ----------------
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 *
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 *
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * 31 ... 5 | 4 | 3 ... 0
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *  offset    F   order
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *
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 *
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Implementation
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * --------------
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * The blocks collection is a sorted linear list.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync *
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 *
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.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync#include <VBox/HGSMI/HGSMIMemAlloc.h>
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync#include <VBox/HGSMI/HGSMI.h>
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync#include <iprt/err.h>
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync#include <iprt/string.h>
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncDECLINLINE(HGSMIOFFSET) hgsmiMADescriptor(HGSMIOFFSET off, bool fFree, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return (off & HGSMI_MA_DESC_OFFSET_MASK) |
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync           (fFree? HGSMI_MA_DESC_FREE_MASK: 0) |
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync           (order & HGSMI_MA_DESC_ORDER_MASK);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMABlockFree(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    pMA->env.pfnFree(pMA->env.pvEnv, pBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMABlockAlloc(HGSMIMADATA *pMA, HGSMIMABLOCK **ppBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = VINF_SUCCESS;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pBlock = (HGSMIMABLOCK *)pMA->env.pfnAlloc(pMA->env.pvEnv, sizeof(HGSMIMABLOCK));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RT_ZERO(pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        *ppBlock = pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    else
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        rc = VERR_NO_MEMORY;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return rc;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/* Divide entire area to free blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMAFormat(HGSMIMADATA *pMA)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = VINF_SUCCESS;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    /* Initial value, it will be updated in the loop below. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    pMA->cbMaxBlock = HGSMI_MA_BLOCK_SIZE_MIN;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    pMA->cBlocks = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cbBlock = HGSMI_MA_BLOCK_SIZE_MAX;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cbRemaining = pMA->area.cbArea;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET off = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    while (cbBlock >= HGSMI_MA_BLOCK_SIZE_MIN)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Build a list of free memory blocks with u32BlockSize. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        uint32_t cBlocks = cbRemaining / cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (cBlocks > 0)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            if (pMA->cbMaxBlock < cbBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                pMA->cbMaxBlock = cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIOFFSET order = HGSMIMASize2Order(cbBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            uint32_t i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            for (i = 0; i < cBlocks; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                /* A new free block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                HGSMIMABLOCK *pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                rc = hgsmiMABlockAlloc(pMA, &pBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                if (RT_FAILURE(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                    break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                pBlock->descriptor = hgsmiMADescriptor(off, true, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                ++pMA->cBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                off += cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                cbRemaining -= cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (RT_FAILURE(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        cbBlock /= 2;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return rc;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMARebuildFreeLists(HGSMIMADATA *pMA)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = VINF_SUCCESS;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pIter;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    RTListForEach(&pMA->listBlocks, pIter, HGSMIMABLOCK, nodeBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (HGSMI_MA_DESC_IS_FREE(pIter->descriptor))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIOFFSET order = HGSMI_MA_DESC_ORDER(pIter->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListAppend(&pMA->aListFreeBlocks[order], &pIter->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return rc;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic int hgsmiMARestore(HGSMIMADATA *pMA, HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = VINF_SUCCESS;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    pMA->cbMaxBlock = cbMaxBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    pMA->cBlocks = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cbRemaining = pMA->area.cbArea;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET off = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    uint32_t i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (i = 0; i < cDescriptors; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Verify the descriptor. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        HGSMISIZE cbBlock = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(paDescriptors[i]));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (   off != HGSMI_MA_DESC_OFFSET(paDescriptors[i])
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            || cbBlock > cbRemaining
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            || cbBlock > pMA->cbMaxBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            rc = VERR_INVALID_PARAMETER;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* A new free block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        HGSMIMABLOCK *pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        rc = hgsmiMABlockAlloc(pMA, &pBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (RT_FAILURE(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pBlock->descriptor = paDescriptors[i];
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        ++pMA->cBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        off += cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        cbRemaining -= cbBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return rc;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic HGSMIMABLOCK *hgsmiMAGetFreeBlock(HGSMIMADATA *pMA, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pBlock = NULL;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (i = order; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pBlock = RTListGetFirst(&pMA->aListFreeBlocks[i], HGSMIMABLOCK, nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        AssertReturn(HGSMI_MA_DESC_IS_FREE(pBlock->descriptor), NULL);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Where the block starts. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pBlock->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* 'i' is the order of the block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        while (i != order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* A larger block was found and need to be split to 2 smaller blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIMABLOCK *pBlock2;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            int rc = hgsmiMABlockAlloc(pMA, &pBlock2);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            if (RT_FAILURE(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                pBlock = NULL;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Create 2 blocks with descreased order. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            --i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Remove from the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListNodeRemove(&pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pBlock->descriptor = hgsmiMADescriptor(off, true, i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pBlock2->descriptor = hgsmiMADescriptor(off + HGSMIMAOrder2Size(i), true, i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Update list of all blocks by inserting pBlock2 after pBlock. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListNodeInsertAfter(&pBlock->nodeBlock, &pBlock2->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            ++pMA->cBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Update the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListAppend(&pMA->aListFreeBlocks[i], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListAppend(&pMA->aListFreeBlocks[i], &pBlock2->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAReformatFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET maxId,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                                      HGSMIMABLOCK *pStart, HGSMIMABLOCK *pEnd, HGSMISIZE cbBlocks)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = VINF_SUCCESS;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    /*
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     * Blocks starting from pStart until pEnd will be replaced with
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     * another set of blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     *
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     */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE u32BlockSize = HGSMIMAOrder2Size(maxId);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cbRemaining = cbBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pStart->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pBlock = pStart;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    while (u32BlockSize >= HGSMI_MA_BLOCK_SIZE_MIN && cbRemaining)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Build a list of free memory blocks with u32BlockSize. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        uint32_t cBlocks = cbRemaining / u32BlockSize;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (cBlocks > 0)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIOFFSET order = HGSMIMASize2Order(u32BlockSize);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            uint32_t i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            for (i = 0; i < cBlocks; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                if (pBlock == pEnd)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                    /* Should never happen because the new set of blocks is supposed to be smaller. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                    AssertFailed();
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                    rc = VERR_OUT_OF_RESOURCES;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                    break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                /* Remove from the free list. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                RTListNodeRemove(&pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                pBlock->descriptor = hgsmiMADescriptor(off, true, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                RTListAppend(&pMA->aListFreeBlocks[order], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                off += u32BlockSize;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                cbRemaining -= u32BlockSize;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                pBlock = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (RT_FAILURE(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        u32BlockSize /= 2;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    Assert(cbRemaining == 0);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (RT_SUCCESS(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Remove remaining free blocks from pBlock until pEnd */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        for (;;)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            bool fEnd = (pBlock == pEnd);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIMABLOCK *pNext = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListNodeRemove(&pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListNodeRemove(&pBlock->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            --pMA->cBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            hgsmiMABlockFree(pMA, pBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            if (fEnd)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pBlock = pNext;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAQueryFreeRange(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock, HGSMISIZE cbRequired,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                                  HGSMIMABLOCK **ppStart, HGSMIMABLOCK **ppEnd, HGSMISIZE *pcbBlocks)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    Assert(HGSMI_MA_DESC_IS_FREE(pBlock->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    *pcbBlocks = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(pBlock->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    *ppStart = pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    *ppEnd = pBlock;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *p;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (;;)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        p = RTListGetNext(&pMA->listBlocks, *ppEnd, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (!p || !HGSMI_MA_DESC_IS_FREE(p->descriptor))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        *ppEnd = p;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (cbRequired && *pcbBlocks >= cbRequired)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            return;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (;;)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        p = RTListGetPrev(&pMA->listBlocks, *ppStart, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (!p || !HGSMI_MA_DESC_IS_FREE(p->descriptor))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        *ppStart = p;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (cbRequired && *pcbBlocks >= cbRequired)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            return;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAMergeFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET order)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    /* Try to create a free block with the order from smaller free blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (order == 0)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* No smaller blocks. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cbRequired = HGSMIMAOrder2Size(order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    /* Scan all free lists of smaller blocks.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     *
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     *
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     * Free blocks are scanned from i to 0 orders.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync     */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET i = order - 1;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (;;)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        HGSMIMABLOCK *pIter;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RTListForEach(&pMA->aListFreeBlocks[i], pIter, HGSMIMABLOCK, nodeFree)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            Assert(HGSMI_MA_DESC_ORDER(pIter->descriptor) == i);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMISIZE cbBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIMABLOCK *pFreeStart;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            HGSMIMABLOCK *pFreeEnd;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            hgsmiMAQueryFreeRange(pMA, pIter, cbRequired, &pFreeStart, &pFreeEnd, &cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            Assert((cbBlocks / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Verify whether cbBlocks is enough for the requested block. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            if (cbBlocks >= cbRequired)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                /* Build new free blocks starting from the requested. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                hgsmiMAReformatFreeBlocks(pMA, order, pFreeStart, pFreeEnd, cbBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                i = 0; /* Leave the loop. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (i == 0)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        --i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic HGSMIOFFSET hgsmiMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (cb > pMA->cbMaxBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return HGSMIOFFSET_VOID;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (cb < HGSMI_MA_BLOCK_SIZE_MIN)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        cb = HGSMI_MA_BLOCK_SIZE_MIN;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET order = HGSMIPopCnt32(cb - 1) - HGSMI_MA_DESC_ORDER_BASE;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertReturn(HGSMIMAOrder2Size(order) >= cb, HGSMIOFFSET_VOID);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertReturn(order < RT_ELEMENTS(pMA->aListFreeBlocks), HGSMIOFFSET_VOID);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pBlock = hgsmiMAGetFreeBlock(pMA, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (RT_UNLIKELY(pBlock == NULL))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* No free block with large enough size. Merge smaller free blocks and try again. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        hgsmiMAMergeFreeBlocks(pMA, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pBlock = hgsmiMAGetFreeBlock(pMA, order);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (RT_LIKELY(pBlock != NULL))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RTListNodeRemove(&pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pBlock->descriptor &= ~HGSMI_MA_DESC_FREE_MASK;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return HGSMI_MA_DESC_OFFSET(pBlock->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return HGSMIOFFSET_VOID;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncstatic void hgsmiMAFree(HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (off == HGSMIOFFSET_VOID)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    /* Find the block corresponding to the offset. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    Assert((off / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pBlock = HGSMIMASearchOffset(pMA, off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (pBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (HGSMI_MA_DESC_OFFSET(pBlock->descriptor) == off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            /* Found the right block, mark it as free. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pBlock->descriptor |= HGSMI_MA_DESC_FREE_MASK;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListAppend(&pMA->aListFreeBlocks[HGSMI_MA_DESC_ORDER(pBlock->descriptor)], &pBlock->nodeFree);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            return;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertFailed();
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncint HGSMIMAInit(HGSMIMADATA *pMA, const HGSMIAREA *pArea,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock,
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync                const HGSMIENV *pEnv)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertReturn(pArea->cbArea < UINT32_C(0x80000000), VERR_INVALID_PARAMETER);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertReturn(pArea->cbArea >= HGSMI_MA_BLOCK_SIZE_MIN, VERR_INVALID_PARAMETER);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    RT_ZERO(*pMA);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMISIZE cb = (pArea->cbArea / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    int rc = HGSMIAreaInitialize(&pMA->area, pArea->pu8Base, cb, 0);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (RT_SUCCESS(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pMA->env = *pEnv;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        uint32_t i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        for (i = 0; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            RTListInit(&pMA->aListFreeBlocks[i]);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RTListInit(&pMA->listBlocks);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (cDescriptors)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            rc = hgsmiMARestore(pMA, paDescriptors, cDescriptors, cbMaxBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        else
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            rc = hgsmiMAFormat(pMA);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (RT_SUCCESS(rc))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            rc = hgsmiMARebuildFreeLists(pMA);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return rc;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncvoid HGSMIMAUninit(HGSMIMADATA *pMA)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pIter;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIMABLOCK *pNext;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    RTListForEachSafe(&pMA->listBlocks, pIter, pNext, HGSMIMABLOCK, nodeBlock)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        RTListNodeRemove(&pIter->nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        hgsmiMABlockFree(pMA, pIter);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    RT_ZERO(*pMA);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncHGSMIOFFSET HGSMIMAPointerToOffset(const HGSMIMADATA *pMA, const void *pv)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (HGSMIAreaContainsPointer(&pMA->area, pv))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return HGSMIPointerToOffset(&pMA->area, pv);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertFailed();
40dc632c19710a795b9a6ecb209abc4bd1c6cec4vboxsync    return HGSMIOFFSET_VOID;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncvoid *HGSMIMAOffsetToPointer(const HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (HGSMIAreaContainsOffset(&pMA->area, off))
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        return HGSMIOffsetToPointer(&pMA->area, off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    AssertFailed();
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return NULL;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncvoid *HGSMIMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET off = hgsmiMAAlloc(pMA, cb);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return HGSMIMAOffsetToPointer(pMA, off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncvoid HGSMIMAFree(HGSMIMADATA *pMA, void *pv)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    HGSMIOFFSET off = HGSMIMAPointerToOffset(pMA, pv);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (off != HGSMIOFFSET_VOID)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        hgsmiMAFree(pMA, off);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    else
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        AssertFailed();
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncHGSMIMABLOCK *HGSMIMASearchOffset(HGSMIMADATA *pMA, HGSMIOFFSET off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
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    HGSMIMABLOCK *pMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    uint32_t iStart = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    uint32_t iEnd = pMA->cBlocks;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    uint32_t iMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    for (;;)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        pMiddle = pStart;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        iMiddle = iStart + (iEnd - iStart) / 2;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (iMiddle == iStart)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            break;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        /* Find the block with the iMiddle index. Never go further than pEnd. */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        uint32_t i;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        for (i = iStart; i < iMiddle && pMiddle != pEnd; ++i)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pMiddle = RTListNodeGetNext(&pMiddle->nodeBlock, HGSMIMABLOCK, nodeBlock);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        HGSMIOFFSET offMiddle = HGSMI_MA_DESC_OFFSET(pMiddle->descriptor);
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        if (offMiddle > off)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pEnd = pMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            iEnd = iMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        else
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        {
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            pStart = pMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync            iStart = iMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync        }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return pMiddle;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync/*
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync * Helper.
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync */
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync
c107091c0fb9efb797884658dd19dd002358b0e2vboxsyncuint32_t HGSMIPopCnt32(uint32_t u32)
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync{
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    uint32_t c = 0;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (u32 > 0xFFFF) { c += 16;  u32 >>= 16; }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (u32 > 0xFF)   { c += 8;   u32 >>= 8;  }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (u32 > 0xF)    { c += 4;   u32 >>= 4;  }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (u32 > 0x3)    { c += 2;   u32 >>= 2;  }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    if (u32 > 0x1)    { c += 1;   u32 >>= 1;  }
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync    return c + u32;
c107091c0fb9efb797884658dd19dd002358b0e2vboxsync}