VirtualBox

Changeset 24621 in vbox for trunk/src


Ignore:
Timestamp:
Nov 12, 2009 7:05:01 PM (15 years ago)
Author:
vboxsync
Message:

AsyncCompletion: Implement new caching using the 2Q algorithm

Location:
trunk/src/VBox/VMM
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/VMM/PDMAsyncCompletionFileCache.cpp

    r24529 r24621  
    248248
    249249    AssertMsg(cbData > 0, ("Evicting 0 bytes not possible\n"));
     250#ifdef VBOX_WITH_2Q_CACHE
     251    AssertMsg(   !pGhostListDst
     252              || (pGhostListDst == &pCache->LruRecentlyUsedOut),
     253              ("Destination list must be NULL or the recently used but paged out list\n"));
     254#else
    250255    AssertMsg(   !pGhostListDst
    251256              || (pGhostListDst == &pCache->LruRecentlyGhost)
    252257              || (pGhostListDst == &pCache->LruFrequentlyGhost),
    253258              ("Destination list must be NULL or one of the ghost lists\n"));
     259#endif
    254260
    255261    if (fReuseBuffer)
    … …  
    297303                cbEvicted += pCurr->cbData;
    298304
     305                pCache->cbCached -= pCurr->cbData;
     306
    299307                if (pGhostListDst)
    300308                {
     309#ifdef VBOX_WITH_2Q_CACHE
     310                    /* We have to remove the last entries from the paged out list. */
     311                    while (pGhostListDst->cbCached > pCache->cbRecentlyUsedOutMax)
     312                    {
     313                        PPDMACFILECACHEENTRY pFree = pGhostListDst->pTail;
     314                        pdmacFileCacheEntryRemoveFromList(pFree);
     315                        STAM_PROFILE_ADV_START(&pCache->StatTreeRemove, Cache);
     316                        RTAvlrFileOffsetRemove(pCurr->pEndpoint->DataCache.pTree, pFree->Core.Key);
     317                        STAM_PROFILE_ADV_STOP(&pCache->StatTreeRemove, Cache);
     318                        RTMemFree(pFree);
     319                    }
     320#endif
     321
    301322                    pdmacFileCacheEntryAddToList(pGhostListDst, pCurr);
    302323                }
    … …  
    309330
    310331                    pdmacFileCacheEntryRemoveFromList(pCurr);
    311                     pCache->cbCached -= pCurr->cbData;
    312 
    313332                    RTMemFree(pCurr);
    314333                }
    … …  
    322341    return cbEvicted;
    323342}
     343
     344#ifdef VBOX_WITH_2Q_CACHE
     345static bool pdmacFileCacheReclaim(PPDMACFILECACHEGLOBAL pCache, size_t cbData, bool fReuseBuffer, uint8_t **ppbBuffer)
     346{
     347    size_t cbRemoved = 0;
     348
     349    if ((pCache->cbCached + cbData) < pCache->cbMax)
     350        return true;
     351    else if ((pCache->LruRecentlyUsedIn.cbCached + cbData) > pCache->cbRecentlyUsedInMax)
     352    {
     353        /* Try to evict as many bytes as possible from A1in */
     354        cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData, &pCache->LruRecentlyUsedIn,
     355                                                 &pCache->LruRecentlyUsedOut, fReuseBuffer, ppbBuffer);
     356
     357        /*
     358         * If it was not possible to remove enough entries
     359         * try the frequently accessed cache.
     360         */
     361        if (cbRemoved < cbData)
     362        {
     363            Assert(!fReuseBuffer || !*ppbBuffer); /* It is not possible that we got a buffer with the correct size but we didn't freed enough data. */
     364
     365            cbRemoved += pdmacFileCacheEvictPagesFrom(pCache, cbData - cbRemoved, &pCache->LruFrequentlyUsed,
     366                                                      NULL, fReuseBuffer, ppbBuffer);
     367        }
     368    }
     369    else
     370    {
     371        /* We have to remove entries from frequently access list. */
     372        cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData, &pCache->LruFrequentlyUsed,
     373                                                 NULL, fReuseBuffer, ppbBuffer);
     374    }
     375
     376    LogFlowFunc((": removed %u bytes, requested %u\n", cbRemoved, cbData));
     377    return (cbRemoved >= cbData);
     378}
     379
     380#else
    324381
    325382static size_t pdmacFileCacheReplace(PPDMACFILECACHEGLOBAL pCache, size_t cbData, PPDMACFILELRULIST pEntryList,
    … …  
    436493        AssertMsgFailed(("Invalid list type\n"));
    437494}
     495#endif
    438496
    439497/**
    … …  
    509567    PPDMACFILECACHEGLOBAL pCache = pEntry->pCache;
    510568    PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint = pEntry->pEndpoint;
     569    PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
    511570
    512571    /* Reference the entry now as we are clearing the I/O in progres flag
    … …  
    609668    PPDMACFILECACHEGLOBAL pCache = &pClassFile->Cache;
    610669
     670    rc = CFGMR3QueryU32Def(pCfgNode, "CacheSize", &pCache->cbMax, 5 * _1M);
     671    AssertLogRelRCReturn(rc, rc);
     672
     673    pCache->cbCached  = 0;
     674    LogFlowFunc((": Maximum number of bytes cached %u\n", pCache->cbMax));
     675
    611676    /* Initialize members */
     677#ifdef VBOX_WITH_2Q_CACHE
     678    pCache->LruRecentlyUsedIn.pHead    = NULL;
     679    pCache->LruRecentlyUsedIn.pTail    = NULL;
     680    pCache->LruRecentlyUsedIn.cbCached = 0;
     681
     682    pCache->LruRecentlyUsedOut.pHead    = NULL;
     683    pCache->LruRecentlyUsedOut.pTail    = NULL;
     684    pCache->LruRecentlyUsedOut.cbCached = 0;
     685
     686    pCache->LruFrequentlyUsed.pHead    = NULL;
     687    pCache->LruFrequentlyUsed.pTail    = NULL;
     688    pCache->LruFrequentlyUsed.cbCached = 0;
     689
     690    pCache->cbRecentlyUsedInMax  = (pCache->cbMax / 100) * 25; /* 25% of the buffer size */
     691    pCache->cbRecentlyUsedOutMax = (pCache->cbMax / 100) * 50; /* 50% of the buffer size */
     692    LogFlowFunc((": cbRecentlyUsedInMax=%u cbRecentlyUsedOutMax=%u\n", pCache->cbRecentlyUsedInMax, pCache->cbRecentlyUsedOutMax));
     693#else
    612694    pCache->LruRecentlyUsed.pHead  = NULL;
    613695    pCache->LruRecentlyUsed.pTail  = NULL;
    … …  
    626708    pCache->LruFrequentlyGhost.cbCached = 0;
    627709
    628     rc = CFGMR3QueryU32Def(pCfgNode, "CacheSize", &pCache->cbMax, 5 * _1M);
    629     AssertLogRelRCReturn(rc, rc);
    630 
    631     pCache->cbCached  = 0;
    632710    pCache->uAdaptVal = 0;
    633     LogFlowFunc((": Maximum number of bytes cached %u\n", pCache->cbMax));
     711#endif
    634712
    635713    STAMR3Register(pClassFile->Core.pVM, &pCache->cbMax,
    … …  
    643721                   STAMUNIT_BYTES,
    644722                   "Currently used cache");
     723#ifdef VBOX_WITH_2Q_CACHE
     724    STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsedIn.cbCached,
     725                   STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
     726                   "/PDM/AsyncCompletion/File/cbCachedMruIn",
     727                   STAMUNIT_BYTES,
     728                   "Number of bytes cached in MRU list");
     729    STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsedOut.cbCached,
     730                   STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
     731                   "/PDM/AsyncCompletion/File/cbCachedMruOut",
     732                   STAMUNIT_BYTES,
     733                   "Number of bytes cached in FRU list");
     734    STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyUsed.cbCached,
     735                   STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
     736                   "/PDM/AsyncCompletion/File/cbCachedFru",
     737                   STAMUNIT_BYTES,
     738                   "Number of bytes cached in FRU ghost list");
     739#else
    645740    STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsed.cbCached,
    646741                   STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
    … …  
    662757                   "/PDM/AsyncCompletion/File/cbCachedFruGhost",
    663758                   STAMUNIT_BYTES, "Number of bytes cached in Fru ghost list");
     759#endif
    664760
    665761#ifdef VBOX_WITH_STATISTICS
    … …  
    729825    RTCritSectEnter(&pCache->CritSect);
    730826
     827#ifdef VBOX_WITH_2Q_CACHE
     828    /* Cleanup deleting all cache entries waiting for in progress entries to finish. */
     829    pdmacFileCacheDestroyList(&pCache->LruRecentlyUsedIn);
     830    pdmacFileCacheDestroyList(&pCache->LruRecentlyUsedOut);
     831    pdmacFileCacheDestroyList(&pCache->LruFrequentlyUsed);
     832#else
    731833    /* Cleanup deleting all cache entries waiting for in progress entries to finish. */
    732834    pdmacFileCacheDestroyList(&pCache->LruRecentlyUsed);
    … …  
    734836    pdmacFileCacheDestroyList(&pCache->LruRecentlyGhost);
    735837    pdmacFileCacheDestroyList(&pCache->LruFrequentlyGhost);
     838#endif
    736839
    737840    RTCritSectLeave(&pCache->CritSect);
    … …  
    9401043 * @param   pSeg      The segment to add.
    9411044 */
    942 static void pdmacFileEpCacheEntryAddWaitingSegment(PPDMACFILECACHEENTRY pEntry, PPDMACFILETASKSEG pSeg)
     1045DECLINLINE(void) pdmacFileEpCacheEntryAddWaitingSegment(PPDMACFILECACHEENTRY pEntry, PPDMACFILETASKSEG pSeg)
    9431046{
    9441047    pSeg->pNext = NULL;
    … …  
    10821185
    10831186            /* Ghost lists contain no data. */
     1187#ifdef VBOX_WITH_2Q_CACHE
     1188            if (   (pEntry->pList == &pCache->LruRecentlyUsedIn)
     1189                || (pEntry->pList == &pCache->LruFrequentlyUsed))
     1190            {
     1191#else
    10841192            if (   (pEntry->pList == &pCache->LruRecentlyUsed)
    10851193                || (pEntry->pList == &pCache->LruFrequentlyUsed))
    10861194            {
     1195#endif
    10871196                if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
    10881197                                                                  PDMACFILECACHE_ENTRY_IS_DEPRECATED,
    … …  
    11521261
    11531262                /* Move this entry to the top position */
     1263#ifdef VBOX_WITH_2Q_CACHE
     1264                if (pEntry->pList == &pCache->LruFrequentlyUsed)
     1265                {
     1266                    RTCritSectEnter(&pCache->CritSect);
     1267                    pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
     1268                    RTCritSectLeave(&pCache->CritSect);
     1269                }
     1270#else
    11541271                RTCritSectEnter(&pCache->CritSect);
    11551272                pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
    11561273                RTCritSectLeave(&pCache->CritSect);
     1274#endif
    11571275            }
    11581276            else
    … …  
    11621280                LogFlow(("Fetching data for ghost entry %#p from file\n", pEntry));
    11631281
     1282#ifdef VBOX_WITH_2Q_CACHE
     1283                RTCritSectEnter(&pCache->CritSect);
     1284                pdmacFileCacheEntryRemoveFromList(pEntry); /* Remove it before we remove data, otherwise it may get freed when evicting data. */
     1285                pdmacFileCacheReclaim(pCache, pEntry->cbData, true, &pbBuffer);
     1286
     1287                /* Move the entry to Am and fetch it to the cache. */
     1288                pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
     1289                RTCritSectLeave(&pCache->CritSect);               
     1290#else
    11641291                RTCritSectEnter(&pCache->CritSect);
    11651292                pdmacFileCacheUpdate(pCache, pEntry);
    … …  
    11691296                pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
    11701297                RTCritSectLeave(&pCache->CritSect);
     1298#endif
    11711299
    11721300                if (pbBuffer)
    … …  
    12501378            uint8_t *pbBuffer = NULL;
    12511379
     1380#ifdef VBOX_WITH_2Q_CACHE
     1381            RTCritSectEnter(&pCache->CritSect);
     1382            bool fEnough = pdmacFileCacheReclaim(pCache, cbToReadAligned, true, &pbBuffer);
     1383            RTCritSectLeave(&pCache->CritSect);
     1384
     1385            if (fEnough)
     1386            {
     1387                LogFlow(("Evicted enough bytes (%u requested). Creating new cache entry\n", cbToReadAligned));
     1388#else
    12521389            RTCritSectEnter(&pCache->CritSect);
    12531390            size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToReadAligned, true, &pbBuffer);
    … …  
    12571394            {
    12581395                LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToReadAligned));
     1396#endif
    12591397                PPDMACFILECACHEENTRY pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToReadAligned, pbBuffer);
    12601398                AssertPtr(pEntryNew);
    12611399
    12621400                RTCritSectEnter(&pCache->CritSect);
     1401#ifdef VBOX_WITH_2Q_CACHE
     1402                pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsedIn, pEntryNew);
     1403#else
    12631404                pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
     1405#endif
    12641406                pCache->cbCached += cbToReadAligned;
    12651407                RTCritSectLeave(&pCache->CritSect);
    … …  
    12951437                 * Pass the request directly to the I/O manager.
    12961438                 */
    1297                 LogFlow(("Couldn't evict %u bytes from the cache (%u actually removed). Remaining request will be passed through\n", cbToRead, cbRemoved));
     1439                LogFlow(("Couldn't evict %u bytes from the cache. Remaining request will be passed through\n", cbToRead));
    12981440
    12991441                while (cbToRead)
    … …  
    13901532
    13911533            /* Ghost lists contain no data. */
     1534#ifdef VBOX_WITH_2Q_CACHE
     1535            if (   (pEntry->pList == &pCache->LruRecentlyUsedIn)
     1536                || (pEntry->pList == &pCache->LruFrequentlyUsed))
     1537#else
    13921538            if (   (pEntry->pList == &pCache->LruRecentlyUsed)
    13931539                || (pEntry->pList == &pCache->LruFrequentlyUsed))
     1540#endif
    13941541            {
    13951542                /* Check if the buffer is deprecated. */
    … …  
    15541701
    15551702                    /* Move this entry to the top position */
     1703#ifdef VBOX_WITH_2Q_CACHE
     1704                if (pEntry->pList == &pCache->LruFrequentlyUsed)
     1705                {
    15561706                    RTCritSectEnter(&pCache->CritSect);
    15571707                    pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
    15581708                    RTCritSectLeave(&pCache->CritSect);
    15591709                } /* Deprecated flag not set. */
     1710#else
     1711                    RTCritSectEnter(&pCache->CritSect);
     1712                    pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
     1713                    RTCritSectLeave(&pCache->CritSect);
     1714#endif
     1715                }
    15601716            }
    15611717            else /* Entry is on the ghost list */
    … …  
    15631719                uint8_t *pbBuffer = NULL;
    15641720
     1721#ifdef VBOX_WITH_2Q_CACHE
     1722                RTCritSectEnter(&pCache->CritSect);
     1723                pdmacFileCacheEntryRemoveFromList(pEntry); /* Remove it before we remove data, otherwise it may get freed when evicting data. */
     1724                pdmacFileCacheReclaim(pCache, pEntry->cbData, true, &pbBuffer);
     1725
     1726                /* Move the entry to Am and fetch it to the cache. */
     1727                pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
     1728                RTCritSectLeave(&pCache->CritSect);               
     1729#else
    15651730                RTCritSectEnter(&pCache->CritSect);
    15661731                pdmacFileCacheUpdate(pCache, pEntry);
    … …  
    15701735                pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
    15711736                RTCritSectLeave(&pCache->CritSect);
     1737#endif
    15721738
    15731739                if (pbBuffer)
    … …  
    16421808            uint8_t *pbBuffer = NULL;
    16431809
     1810#ifdef VBOX_WITH_2Q_CACHE
     1811            RTCritSectEnter(&pCache->CritSect);
     1812            bool fEnough = pdmacFileCacheReclaim(pCache, cbToWrite, true, &pbBuffer);
     1813            RTCritSectLeave(&pCache->CritSect);
     1814
     1815            if (fEnough)
     1816            {
     1817                LogFlow(("Evicted enough bytes (%u requested). Creating new cache entry\n", cbToWrite));
     1818#else
    16441819            RTCritSectEnter(&pCache->CritSect);
    16451820            size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToWrite, true, &pbBuffer);
    … …  
    16481823            if (cbRemoved >= cbToWrite)
    16491824            {
     1825                LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToWrite));
     1826
     1827#endif
    16501828                uint8_t *pbBuf;
    16511829                PPDMACFILECACHEENTRY pEntryNew;
    16521830
    1653                 LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToWrite));
    1654 
    16551831                pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToWrite, pbBuffer);
    16561832                AssertPtr(pEntryNew);
    16571833
    16581834                RTCritSectEnter(&pCache->CritSect);
     1835#ifdef VBOX_WITH_2Q_CACHE
     1836                pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsedIn, pEntryNew);
     1837#else
    16591838                pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
     1839#endif
    16601840                pCache->cbCached += cbToWrite;
    16611841                RTCritSectLeave(&pCache->CritSect);
    … …  
    16891869                 * Pass the request directly to the I/O manager.
    16901870                 */
    1691                 LogFlow(("Couldn't evict %u bytes from the cache (%u actually removed). Remaining request will be passed through\n", cbToWrite, cbRemoved));
     1871                LogFlow(("Couldn't evict %u bytes from the cache. Remaining request will be passed through\n", cbToWrite));
    16921872
    16931873                while (cbToWrite)

  • trunk/src/VBox/VMM/PDMAsyncCompletionFileInternal.h

    r24517 r24621  
    3333
    3434#include "PDMAsyncCompletionInternal.h"
     35
     36/** Enable the 2Q cache alogrithm. */
     37#define VBOX_WITH_2Q_CACHE 1
    3538
    3639/** @todo: Revise the caching of tasks. We have currently four caches:
    … …  
    275278    /** Critical section protecting the cache. */
    276279    RTCRITSECT       CritSect;
     280#ifdef VBOX_WITH_2Q_CACHE
     281    uint32_t         cbRecentlyUsedInMax;
     282    uint32_t         cbRecentlyUsedOutMax;
     283    PDMACFILELRULIST LruRecentlyUsedIn;
     284    PDMACFILELRULIST LruRecentlyUsedOut;
     285    PDMACFILELRULIST LruFrequentlyUsed;
     286#else
    277287    /** Adaption parameter (p) */
    278288    uint32_t         uAdaptVal;
    … …  
    285295    /** LRU list for evicted entries from T2 (B2) */
    286296    PDMACFILELRULIST LruFrequentlyGhost;
     297#endif
    287298#ifdef VBOX_WITH_STATISTICS
    288299    /** Hit counter. */
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette