VirtualBox

Ignore:
Timestamp:
May 21, 2013 11:02:26 PM (12 years ago)
Author:
vboxsync
Message:

strcache.cpp: build fix and disable complicated allocator replacing it with a range of fixed size allocators up to 512 bytes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Runtime/common/string/strcache.cpp

    r46201 r46202  
    6666 * Using a 1KB as a reasonable limit here.
    6767 */
    68 #define RTSTRCACHE_HEAP_THRESHOLD_BIT       10
     68#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
     69# define RTSTRCACHE_HEAP_THRESHOLD_BIT      10
     70#else
     71# define RTSTRCACHE_HEAP_THRESHOLD_BIT      9
     72#endif
    6973/** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
    7074#define RTSTRCACHE_HEAP_THRESHOLD           RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
    7175
     76#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    7277/**
    7378 * The RTSTRCACHEENTRY size threshold at which we start using the merge free
    7479 * list for allocations, expressed as a power of two.
    7580 */
    76 #define RTSTRCACHE_MERGED_THRESHOLD_BIT     6
    77 
     81# define RTSTRCACHE_MERGED_THRESHOLD_BIT    6
    7882
    7983/** The number of bytes (power of two) that the merged allocation lists should
    8084 * be grown by.  Must be much greater than RTSTRCACHE_MERGED_THRESHOLD. */
    8185#define RTSTRCACHE_MERGED_GROW_SIZE         _32K
     86#endif
     87
    8288/** The number of bytes (power of two) that the fixed allocation lists should
    8389 * be grown by. */
    8490#define RTSTRCACHE_FIXED_GROW_SIZE          _32K
     91
     92/** The number of fixed sized lists. */
     93#define RTSTRCACHE_NUM_OF_FIXED_SIZES       10
     94
    8595
    8696/** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found,
    … …  
    173183typedef RTSTRCACHEFREE *PRTSTRCACHEFREE;
    174184
     185#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    175186
    176187/**
    … …  
    202213 *  header.  Must be something that's invalid UTF-8 for both little and big
    203214 *  endian system. */
    204 #define RTSTRCACHEFREEMERGE_MAIN    UINT32_C(0xfffffff1)
     215# define RTSTRCACHEFREEMERGE_MAIN   UINT32_C(0xfffffff1)
    205216/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's part of a larger
    206217 * chunk of free memory.  Must be something that's invalid UTF-8 for both little
    207218 * and big endian system. */
    208 #define RTSTRCACHEFREEMERGE_PART    UINT32_C(0xfffffff2)
    209 
     219# define RTSTRCACHEFREEMERGE_PART   UINT32_C(0xfffffff2)
     220
     221#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
    210222
    211223/**
    … …  
    242254    /** Pointer to the hash table. */
    243255    PRTSTRCACHEENTRY       *papHashTab;
    244     /** Free list for allocations of size: 64+, 16, and 32. */
    245     PRTSTRCACHEFREE         apFreeLists[2];
     256    /** Free list for allocations of the sizes defined by g_acbFixedLists. */
     257    PRTSTRCACHEFREE         apFreeLists[RTSTRCACHE_NUM_OF_FIXED_SIZES];
     258#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    246259    /** Free lists based on */
    247260    RTLISTANCHOR            aMergedFreeLists[RTSTRCACHE_HEAP_THRESHOLD_BIT - RTSTRCACHE_MERGED_THRESHOLD_BIT + 1];
     261#endif
    248262    /** List of allocated memory chunks. */
    249263    PRTSTRCACHECHUNK        pChunkList;
    … …  
    261275*   Global Variables                                                           *
    262276*******************************************************************************/
     277/** The entry sizes of the fixed lists (RTSTRCACHEINT::apFreeLists). */
     278static const uint32_t g_acbFixedLists[RTSTRCACHE_NUM_OF_FIXED_SIZES] =
     279{
     280    16, 32, 64, 128, 192, 256, 320, 384, 448, 512
     281};
     282
    263283/** Init once for the default string cache. */
    264284static RTONCE       g_rtStrCacheOnce     = RTONCE_INITIALIZER;
    … …  
    289309            {
    290310                RTListInit(&pThis->BigEntryList);
     311#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    291312                for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
    292313                    RTListInit(&pThis->aMergedFreeLists[i]);
     314#endif
    293315                pThis->cRefs    = 1;
    294316                pThis->u32Magic = RTSTRCACHE_MAGIC;
    … …  
    348370
    349371
     372
     373/**
     374 * Selects the fixed free list index for a given minimum entry size.
     375 *
     376 * @returns Free list index.
     377 * @param   cbMin               Minimum entry size.
     378 */
     379DECLINLINE(uint32_t) rtStrCacheSelectFixedList(uint32_t cbMin)
     380{
     381    Assert(cbMin <= g_acbFixedLists[RT_ELEMENTS(g_acbFixedLists) - 1]);
     382    unsigned i = 0;
     383    while (cbMin > g_acbFixedLists[i])
     384        i++;
     385    return i;
     386}
     387
     388
    350389#ifdef RT_STRICT
    351390# define RTSTRCACHE_CHECK(a_pThis)  do { rtStrCacheCheck(pThis); } while (0)
    … …  
    355394static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
    356395{
     396# ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    357397    for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
    358398    {
    … …  
    365405        }
    366406    }
     407# endif
    367408}
    368409#else
    369410# define RTSTRCACHE_CHECK(a_pThis)  do { } while (0)
    370411#endif
    371 
    372 
    373 /**
    374  * Link/Relink into the free right list.
    375  *
    376  * @param   pThis               The string cache instance.
    377  * @param   pFree               The free string entry.
    378  */
    379 static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
    380 {
    381     Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
    382     Assert(pFree->cbFree > 0);
    383     Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
    384 
    385     if (!RTListIsEmpty(&pFree->ListEntry))
    386         RTListNodeRemove(&pFree->ListEntry);
    387 
    388     uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
    389     if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
    390         iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
    391 
    392     RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
    393 }
    394412
    395413
    … …  
    464482}
    465483
    466 
    467 /**
    468  * Allocate a cache entry from the heap.
    469  *
    470  * @returns Pointer to the cache entry on success, NULL on allocation error.
     484#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
     485
     486/**
     487 * Link/Relink into the free right list.
     488 *
    471489 * @param   pThis               The string cache instance.
    472  * @param   uHash               The full hash of the string.
    473  * @param   pchString           The string.
    474  * @param   cchString           The string length.
    475  */
    476 static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
    477                                                  const char *pchString, uint32_t cchString)
    478 {
    479     /*
    480      * Allocate a heap block for storing the string. We do some size aligning
    481      * here to encourage the heap to give us optimal alignment.
    482      */
    483     size_t              cbEntry   = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
    484     PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, 64));
    485     if (!pBigEntry)
    486         return NULL;
    487 
    488     /*
    489      * Initialize the block.
    490      */
    491     RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
    492     pBigEntry->cchString        = cchString;
    493     pBigEntry->uHash            = uHash;
    494     pBigEntry->Core.cRefs       = 1;
    495     pBigEntry->Core.uHash       = (uint16_t)uHash;
    496     pBigEntry->Core.cchString   = RTSTRCACHEENTRY_BIG_LEN;
    497     memcpy(pBigEntry->Core.szString, pchString, cchString);
    498     pBigEntry->Core.szString[cchString] = '\0';
    499 
    500     return &pBigEntry->Core;
     490 * @param   pFree               The free string entry.
     491 */
     492static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
     493{
     494    Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
     495    Assert(pFree->cbFree > 0);
     496    Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
     497
     498    if (!RTListIsEmpty(&pFree->ListEntry))
     499        RTListNodeRemove(&pFree->ListEntry);
     500
     501    uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
     502    if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
     503        iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
     504
     505    RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
    501506}
    502507
    … …  
    615620}
    616621
     622#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
     623
     624/**
     625 * Allocate a cache entry from the heap.
     626 *
     627 * @returns Pointer to the cache entry on success, NULL on allocation error.
     628 * @param   pThis               The string cache instance.
     629 * @param   uHash               The full hash of the string.
     630 * @param   pchString           The string.
     631 * @param   cchString           The string length.
     632 */
     633static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
     634                                                 const char *pchString, uint32_t cchString)
     635{
     636    /*
     637     * Allocate a heap block for storing the string. We do some size aligning
     638     * here to encourage the heap to give us optimal alignment.
     639     */
     640    size_t              cbEntry   = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
     641    PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, 64));
     642    if (!pBigEntry)
     643        return NULL;
     644
     645    /*
     646     * Initialize the block.
     647     */
     648    RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
     649    pBigEntry->cchString        = cchString;
     650    pBigEntry->uHash            = uHash;
     651    pBigEntry->Core.cRefs       = 1;
     652    pBigEntry->Core.uHash       = (uint16_t)uHash;
     653    pBigEntry->Core.cchString   = RTSTRCACHEENTRY_BIG_LEN;
     654    memcpy(pBigEntry->Core.szString, pchString, cchString);
     655    pBigEntry->Core.szString[cchString] = '\0';
     656
     657    return &pBigEntry->Core;
     658}
     659
    617660
    618661/**
    … …  
    644687
    645688        PRTSTRCACHEFREE pPrev   = NULL;
    646         size_t const    cbEntry = 1 << (iFreeList + 4);
    647         uint32_t        cLeft   = PAGE_SIZE / cbEntry - 1;
     689        uint32_t const  cbEntry = g_acbFixedLists[iFreeList];
     690        uint32_t        cLeft   = RTSTRCACHE_FIXED_GROW_SIZE / cbEntry - 1;
    648691        pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
    649692
    650693        Assert(sizeof(*pChunk) <= cbEntry);
    651694        Assert(sizeof(*pFree)  <= cbEntry);
    652         Assert(cbEntry < PAGE_SIZE / 16);
     695        Assert(cbEntry < RTSTRCACHE_FIXED_GROW_SIZE / 16);
    653696
    654697        while (cLeft-- > 0)
    … …  
    762805    uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
    763806    AssertReturn(cchString < _1G, NULL);
    764 
     807    uint32_t const cchString32 = (uint32_t)cchString;
    765808
    766809    RTCritSectEnter(&pThis->CritSect);
    … …  
    768811
    769812    uint32_t iFreeHashTabEntry;
    770     PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString, pchString, &iFreeHashTabEntry);
     813    PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry);
    771814    if (pEntry)
    772815    {
    … …  
    779822         * Allocate a new entry.
    780823         */
    781         uint32_t cbEntry = cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
    782         if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
    783         {
    784             if (cbEntry <= RTSTRCACHE_HEAP_THRESHOLD)
    785                 pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString, cbEntry);
    786             else
    787                 pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString);
    788         }
     824        uint32_t cbEntry = cchString32 + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
     825        if (cbEntry >= RTSTRCACHE_HEAP_THRESHOLD)
     826            pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString32);
     827#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
     828        else if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
     829            pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString32, cbEntry);
     830#endif
    789831        else
    790             pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString, cbEntry > 16);
     832            pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString32,
     833                                               rtStrCacheSelectFixedList(cbEntry));
    791834        if (!pEntry)
    792835        {
    … …  
    941984    {
    942985        uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
    943         if (cbMin <= 32)
     986#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
     987        if (cbMin <= RTSTRCACHE_MAX_FIXED)
     988#endif
    944989        {
    945990            /*
    946991             * No merging, just add it to the list.
    947992             */
    948             uint32_t const iFreeList = cbMin > 16;
     993            uint32_t const iFreeList = rtStrCacheSelectFixedList(cbMin);
    949994            ASMCompilerBarrier();
    950995            PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
    … …  
    954999            pThis->apFreeLists[iFreeList] = pFreeStr;
    9551000        }
     1001#ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
    9561002        else
    9571003        {
    … …  
    10321078            rtStrCacheRelinkMerged(pThis, pMain);
    10331079        }
     1080#endif /* RTSTRCACHE_WITH_MERGED_ALLOCATOR */
    10341081        RTSTRCACHE_CHECK(pThis);
    10351082        RTCritSectLeave(&pThis->CritSect);
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