VirtualBox

Changeset 2930 in kBuild


Ignore:
Timestamp:
Sep 18, 2016 3:57:25 PM (8 years ago)
Author:
bird
Message:

kFsCache: Implemented lazy child hashing and increased the KFSCACHE_CFG_PATH_HASH_TAB_SIZE value from 16384 to 99991 to better deal with large kBuild trees (e.g. VBox).

Location:
trunk/src/lib/nt
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/lib/nt/kFsCache.c

    r2912 r2930  
    4141#include <mbstring.h>
    4242#include <wchar.h>
    43 //#include <intrin.h>
     43#ifdef _MSC_VER
     44# include <intrin.h>
     45#endif
    4446//#include <setjmp.h>
    4547//#include <ctype.h>
    … …  
    200202 * @param   cchString           The length of the substring.
    201203 */
    202 static KU32 kFsCacheStrHashN(const char *pszString, KSIZE cchString)
     204static KU32 kFsCacheStrHashN(const char *pchString, KSIZE cchString)
    203205{
    204206    KU32 uHash = 0;
    205207    while (cchString-- > 0)
    206208    {
    207         KU32 uChar = (unsigned char)*pszString++;
     209        KU32 uChar = (unsigned char)*pchString++;
    208210        uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
    209211    }
    … …  
    588590        pObj->fFlags        = pParent->Obj.fFlags & KFSOBJ_F_INHERITED_MASK;
    589591        pObj->pParent       = pParent;
     592        pObj->uNameHash     = 0;
     593        pObj->pNextNameHash = NULL;
    590594        pObj->pUserDataHead = NULL;
    591595
    … …  
    637641
    638642        /*
    639          * Type specific initilization.
     643         * Type specific initialization.
    640644         */
    641645        if (fDirish)
    … …  
    645649            pDirObj->cChildrenAllocated = 0;
    646650            pDirObj->papChildren        = NULL;
    647             pDirObj->cHashTab           = 0;
    648             pDirObj->paHashTab          = NULL;
     651            pDirObj->fHashTabMask       = 0;
     652            pDirObj->papHashTab         = NULL;
    649653            pDirObj->hDir               = INVALID_HANDLE_VALUE;
    650654            pDirObj->uDevNo             = pParent->uDevNo;
    … …  
    15161520                                  pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pOldChild->pszName));
    15171521                    kHlpAssert(pOldChild->bObjType != KFSOBJ_TYPE_DIR);
     1522                    /* Remove from hash table. */
     1523                    if (pOldChild->uNameHash != 0)
     1524                    {
     1525                        KU32    idx = pOldChild->uNameHash & pDir->fHashTabMask;
     1526                        PKFSOBJ pPrev = pDir->papHashTab[idx];
     1527                        if (pPrev == pOldChild)
     1528                            pDir->papHashTab[idx] = pOldChild->pNextNameHash;
     1529                        else
     1530                        {
     1531                            while (pPrev && pPrev->pNextNameHash != pOldChild)
     1532                                pPrev = pPrev->pNextNameHash;
     1533                            kHlpAssert(pPrev);
     1534                            if (pPrev)
     1535                                pPrev->pNextNameHash = pOldChild->pNextNameHash;
     1536                        }
     1537                        pOldChild->uNameHash = 0;
     1538                    }
    15181539                }
    15191540                kFsCacheObjRelease(pCache, pOldChild);
    … …  
    19201941 *                              failed.
    19211942 */
    1922 static PKFSOBJ kFswCacheLookupDrive(PKFSCACHE pCache, char chLetter, KU32 fFlags, KFSLOOKUPERROR *penmError)
    1923 {
    1924     KU32 const          uHash = chLetter - 'A';
     1943static PKFSOBJ kFsCacheLookupDrive(PKFSCACHE pCache, char chLetter, KU32 fFlags, KFSLOOKUPERROR *penmError)
     1944{
     1945    KU32 const          uNameHash = chLetter - 'A';
     1946    PKFSOBJ             pCur      = pCache->RootDir.papHashTab[uNameHash];
     1947
    19251948    KU32                cLeft;
    19261949    PKFSOBJ            *ppCur;
    1927 
    19281950    MY_UNICODE_STRING   NtPath;
    19291951    wchar_t             wszTmp[8];
    … …  
    19331955     * Custom drive letter hashing.
    19341956     */
    1935     if (pCache->RootDir.paHashTab)
    1936     {
    1937         /** @todo PKFSOBJHASH pHash = */
     1957    kHlpAssert((uNameHash & pCache->RootDir.fHashTabMask) == uNameHash);
     1958    while (pCur)
     1959    {
     1960        if (   pCur->uNameHash == uNameHash
     1961            && pCur->cchName == 2
     1962            && pCur->pszName[0] == chLetter
     1963            && pCur->pszName[1] == ':')
     1964        {
     1965            if (pCur->bObjType == KFSOBJ_TYPE_DIR)
     1966                return pCur;
     1967            if (   (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
     1968                || kFsCacheRefreshMissingIntermediateDir(pCache, pCur, penmError))
     1969                return pCur;
     1970            return NULL;
     1971        }
     1972        pCur = pCur->pNextNameHash;
    19381973    }
    19391974
    19401975    /*
    1941      * Special cased lookup.
     1976     * Make 100% sure it's not there.
    19421977     */
    19431978    cLeft = pCache->RootDir.cChildren;
    … …  
    19451980    while (cLeft-- > 0)
    19461981    {
    1947         PKFSOBJ pCur = *ppCur++;
     1982        pCur = *ppCur++;
    19481983        if (   pCur->cchName == 2
    19491984            && pCur->pszName[0] == chLetter
    … …  
    20592094                fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, &pDir->Obj, penmError);
    20602095                kFsCacheObjRelease(pCache, &pDir->Obj);
    2061                 return fRc ? &pDir->Obj : NULL;
     2096                if (fRc)
     2097                {
     2098                    pDir->Obj.pNextNameHash = pCache->RootDir.papHashTab[uNameHash];
     2099                    pCache->RootDir.papHashTab[uNameHash] = &pDir->Obj;
     2100                    return &pDir->Obj;
     2101                }
     2102                return NULL;
    20622103            }
    20632104
    … …  
    21102151
    21112152/**
     2153 * Slow path that allocates the child hash table and enters the given one.
     2154 *
     2155 * Allocation fialures are ignored.
     2156 *
     2157 * @param   pCache              The cache (for stats).
     2158 * @param   pDir                The directory.
     2159 * @param   uNameHash           The name hash  to enter @a pChild under.
     2160 * @param   pChild              The child to enter into the hash table.
     2161 */
     2162static void kFsCacheDirAllocHashTabAndEnterChild(PKFSCACHE pCache, PKFSDIR pDir, KU32 uNameHash, PKFSOBJ pChild)
     2163{
     2164    if (uNameHash != 0) /* paranoia ^ 4! */
     2165    {
     2166        /*
     2167         * Double the current number of children and round up to a multiple of
     2168         * two so we can avoid division.
     2169         */
     2170        KU32 cbHashTab;
     2171        KU32 cEntries;
     2172        kHlpAssert(pDir->cChildren > 0);
     2173        if (pDir->cChildren <= KU32_MAX / 4)
     2174        {
     2175#if defined(_MSC_VER) && 1
     2176            KU32 cEntriesRaw = pDir->cChildren * 2;
     2177            KU32 cEntriesShift;
     2178            kHlpAssert(sizeof(cEntries) == (unsigned long));
     2179            if (_BitScanReverse(&cEntriesShift, cEntriesRaw))
     2180            {
     2181                if (   K_BIT32(cEntriesShift) < cEntriesRaw
     2182                    && cEntriesShift < 31U)
     2183                    cEntriesShift++;
     2184                cEntries = K_BIT32(cEntriesShift);
     2185            }
     2186            else
     2187            {
     2188                kHlpAssertFailed();
     2189                cEntries = KU32_MAX / 2 + 1;
     2190            }
     2191#else
     2192            cEntries = pDir->cChildren * 2 - 1;
     2193            cEntries |= cEntries >> 1;
     2194            cEntries |= cEntries >> 2;
     2195            cEntries |= cEntries >> 4;
     2196            cEntries |= cEntries >> 8;
     2197            cEntries |= cEntries >> 16;
     2198            cEntries++;
     2199#endif
     2200        }
     2201        else
     2202            cEntries = KU32_MAX / 2 + 1;
     2203        kHlpAssert((cEntries & (cEntries -  1)) == 0);
     2204
     2205        cbHashTab = cEntries * sizeof(pDir->papHashTab[0]);
     2206        pDir->papHashTab = (PKFSOBJ *)kHlpAllocZ(cbHashTab);
     2207        if (pDir->papHashTab)
     2208        {
     2209            KU32 idx;
     2210            pDir->fHashTabMask = cEntries - 1;
     2211            pCache->cbObjects += cbHashTab;
     2212            pCache->cChildHashTabs++;
     2213            pCache->cChildHashEntriesTotal += cEntries;
     2214
     2215            /*
     2216             * Insert it.
     2217             */
     2218            pChild->uNameHash     = uNameHash;
     2219            idx = uNameHash & (pDir->fHashTabMask);
     2220            pChild->pNextNameHash = pDir->papHashTab[idx];
     2221            pDir->papHashTab[idx] = pChild;
     2222            pCache->cChildHashed++;
     2223        }
     2224    }
     2225}
     2226
     2227
     2228/**
    21122229 * Look up a child node, ANSI version.
    21132230 *
    … …  
    21202237static PKFSOBJ kFsCacheFindChildA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName)
    21212238{
    2122     /* Check for '.' first. */
     2239    /*
     2240     * Check for '.' first ('..' won't appear).
     2241     */
    21232242    if (cchName != 1 || *pchName != '.')
    21242243    {
     2244        PKFSOBJ    *ppCur;
    21252245        KU32        cLeft;
    2126         PKFSOBJ    *ppCur;
    2127 
    2128         if (pParent->paHashTab != NULL)
    2129         {
    2130             /** @todo directory hash table lookup.   */
    2131         }
    2132 
    2133         /* Linear search. */
     2246        KU32        uNameHash;
     2247
     2248        /*
     2249         * Do hash table lookup.
     2250         *
     2251         * This caches previous lookups, which should be useful when looking up
     2252         * intermediate directories at least.
     2253         */
     2254        if (pParent->papHashTab != NULL)
     2255        {
     2256            PKFSOBJ pCur;
     2257            uNameHash = kFsCacheStrHashN(pchName, cchName);
     2258            pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
     2259            while (pCur)
     2260            {
     2261                if (   pCur->uNameHash == uNameHash
     2262                    && (   (   pCur->cchName == cchName
     2263                            && _mbsnicmp(pCur->pszName, pchName, cchName) == 0)
     2264#ifdef KFSCACHE_CFG_SHORT_NAMES
     2265                        || (   pCur->cchShortName == cchName
     2266                            && pCur->pszShortName != pCur->pszName
     2267                            && _mbsnicmp(pCur->pszShortName, pchName, cchName) == 0)
     2268#endif
     2269                        )
     2270                   )
     2271                {
     2272                    pCache->cChildHashHits++;
     2273                    pCache->cChildSearches++;
     2274                    return pCur;
     2275                }
     2276                pCur = pCur->pNextNameHash;
     2277            }
     2278        }
     2279        else
     2280            uNameHash = 0;
     2281
     2282        /*
     2283         * Do linear search.
     2284         */
    21342285        cLeft = pParent->cChildren;
    21352286        ppCur = pParent->papChildren;
    … …  
    21452296#endif
    21462297               )
     2298            {
     2299                /*
     2300                 * Consider entering it into the parent hash table.
     2301                 * Note! We hash the input, not the name we found.
     2302                 */
     2303                if (   pCur->uNameHash == 0
     2304                    && pParent->cChildren >= 2)
     2305                {
     2306                    if (pParent->papHashTab)
     2307                    {
     2308                        if (uNameHash != 0)
     2309                        {
     2310                            KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
     2311                            pCur->uNameHash     = uNameHash;
     2312                            pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
     2313                            pParent->papHashTab[idxNameHash] = pCur;
     2314                            if (pCur->pNextNameHash)
     2315                                pCache->cChildHashCollisions++;
     2316                            pCache->cChildHashed++;
     2317                        }
     2318                    }
     2319                    else
     2320                        kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheStrHashN(pchName, cchName), pCur);
     2321                }
     2322
     2323                pCache->cChildSearches++;
    21472324                return pCur;
    2148         }
     2325            }
     2326        }
     2327
     2328        pCache->cChildSearches++;
    21492329        return NULL;
    21502330    }
    … …  
    21642344static PKFSOBJ kFsCacheFindChildW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName)
    21652345{
    2166     /* Check for '.' first. */
     2346    /*
     2347     * Check for '.' first ('..' won't appear).
     2348     */
    21672349    if (cwcName != 1 || *pwcName != '.')
    21682350    {
     2351        PKFSOBJ    *ppCur;
    21692352        KU32        cLeft;
    2170         PKFSOBJ    *ppCur;
    2171 
    2172         if (pParent->paHashTab != NULL)
    2173         {
    2174             /** @todo directory hash table lookup.   */
    2175         }
    2176 
    2177         /* Linear search. */
     2353        KU32        uNameHash;
     2354
     2355        /*
     2356         * Do hash table lookup.
     2357         *
     2358         * This caches previous lookups, which should be useful when looking up
     2359         * intermediate directories at least.
     2360         */
     2361        if (pParent->papHashTab != NULL)
     2362        {
     2363            PKFSOBJ pCur;
     2364            uNameHash = kFsCacheUtf16HashN(pwcName, cwcName);
     2365            pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
     2366            while (pCur)
     2367            {
     2368                if (   pCur->uNameHash == uNameHash
     2369                    && (   (   pCur->cwcName == cwcName
     2370                            && kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
     2371#ifdef KFSCACHE_CFG_SHORT_NAMES
     2372                         || (   pCur->cwcShortName == cwcName
     2373                             && pCur->pwszShortName != pCur->pwszName
     2374                             && kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
     2375#endif
     2376                       )
     2377                   )
     2378                {
     2379                    pCache->cChildHashHits++;
     2380                    pCache->cChildSearches++;
     2381                    return pCur;
     2382                }
     2383                pCur = pCur->pNextNameHash;
     2384            }
     2385        }
     2386        else
     2387            uNameHash = 0;
     2388
     2389        /*
     2390         * Do linear search.
     2391         */
    21782392        cLeft = pParent->cChildren;
    21792393        ppCur = pParent->papChildren;
    … …  
    21892403#endif
    21902404               )
     2405            {
     2406                /*
     2407                 * Consider entering it into the parent hash table.
     2408                 * Note! We hash the input, not the name we found.
     2409                 */
     2410                if (   pCur->uNameHash == 0
     2411                    && pParent->cChildren >= 4)
     2412                {
     2413                    if (pParent->papHashTab)
     2414                    {
     2415                        if (uNameHash != 0)
     2416                        {
     2417                            KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
     2418                            pCur->uNameHash     = uNameHash;
     2419                            pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
     2420                            pParent->papHashTab[idxNameHash] = pCur;
     2421                            if (pCur->pNextNameHash)
     2422                                pCache->cChildHashCollisions++;
     2423                            pCache->cChildHashed++;
     2424                        }
     2425                    }
     2426                    else
     2427                        kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheUtf16HashN(pwcName, cwcName), pCur);
     2428                }
     2429
     2430                pCache->cChildSearches++;
    21912431                return pCur;
    2192         }
     2432            }
     2433        }
     2434        pCache->cChildSearches++;
    21932435        return NULL;
    21942436    }
    … …  
    22122454 *                              failed.
    22132455 */
    2214 static PKFSOBJ kFswCacheLookupUncShareA(PKFSCACHE pCache, const char *pszPath, KU32 fFlags,
    2215                                         KU32 *poff, KFSLOOKUPERROR *penmError)
     2456static PKFSOBJ kFsCacheLookupUncShareA(PKFSCACHE pCache, const char *pszPath, KU32 fFlags,
     2457                                       KU32 *poff, KFSLOOKUPERROR *penmError)
    22162458{
    22172459#if 0 /* later */
    … …  
    22652507 *                              failed.
    22662508 */
    2267 static PKFSOBJ kFswCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
    2268                                         KU32 *poff, KFSLOOKUPERROR *penmError)
     2509static PKFSOBJ kFsCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
     2510                                       KU32 *poff, KFSLOOKUPERROR *penmError)
    22692511{
    22702512#if 0 /* later */
    … …  
    26352877        offEnd = 2;
    26362878        kHlpAssert(IS_SLASH(pszPath[2]));
    2637         pRoot = kFswCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
     2879        pRoot = kFsCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
    26382880    }
    26392881    else if (   IS_SLASH(pszPath[0])
    26402882             && IS_SLASH(pszPath[1]) )
    2641         pRoot = kFswCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
     2883        pRoot = kFsCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
    26422884    else
    26432885    {
    … …  
    27342976        offEnd = 2;
    27352977        kHlpAssert(IS_SLASH(pwszPath[2]));
    2736         pRoot = kFswCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
     2978        pRoot = kFsCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
    27372979    }
    27382980    else if (   IS_SLASH(pwszPath[0])
    27392981             && IS_SLASH(pwszPath[1]) )
    2740         pRoot = kFswCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
     2982        pRoot = kFsCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
    27412983    else
    27422984    {
    … …  
    34213663            pCache->cbObjects -= sizeof(*pDir)
    34223664                               + K_ALIGN_Z(cChildren, 16) * sizeof(pDir->papChildren)
    3423                                + pDir->cHashTab * sizeof(pDir->paHashTab);
     3665                               + (pDir->fHashTabMask + !!pDir->fHashTabMask) * sizeof(pDir->papHashTab[0]);
    34243666
    34253667            pDir->cChildren   = 0;
    … …  
    34293671            pDir->papChildren = NULL;
    34303672
    3431             kHlpFree(pDir->paHashTab);
    3432             pDir->paHashTab = NULL;
     3673            kHlpFree(pDir->papHashTab);
     3674            pDir->papHashTab = NULL;
    34333675            break;
    34343676        }
    … …  
    40834325        pCache->RootDir.papChildren         = NULL;
    40844326        pCache->RootDir.hDir                = INVALID_HANDLE_VALUE;
    4085         pCache->RootDir.cHashTab            = 251;
    4086         pCache->RootDir.paHashTab           = (PKFSOBJHASH)kHlpAllocZ(  pCache->RootDir.cHashTab
    4087                                                                       * sizeof(pCache->RootDir.paHashTab[0]));
    4088         if (pCache->RootDir.paHashTab)
     4327        pCache->RootDir.fHashTabMask        = 255; /* 256: 26 drive letters and 102 UNCs before we're half ways. */
     4328        pCache->RootDir.papHashTab          = (PKFSOBJ *)kHlpAllocZ(256 * sizeof(pCache->RootDir.papHashTab[0]));
     4329        if (pCache->RootDir.papHashTab)
    40894330        {
    40904331            /* The cache itself. */
    4091             pCache->u32Magic        = KFSCACHE_MAGIC;
    4092             pCache->fFlags          = fFlags;
     4332            pCache->u32Magic                = KFSCACHE_MAGIC;
     4333            pCache->fFlags                  = fFlags;
    40934334            pCache->auGenerations[0]        = KU32_MAX / 4;
    40944335            pCache->auGenerations[1]        = KU32_MAX / 32;
    40954336            pCache->auGenerationsMissing[0] = KU32_MAX / 256;
    40964337            pCache->auGenerationsMissing[1] = 1;
    4097             pCache->cObjects        = 1;
    4098             pCache->cbObjects       = sizeof(pCache->RootDir) + pCache->RootDir.cHashTab * sizeof(pCache->RootDir.paHashTab[0]);
    4099             pCache->cPathHashHits   = 0;
    4100             pCache->cWalkHits       = 0;
    4101             pCache->cAnsiPaths      = 0;
    4102             pCache->cAnsiPathCollisions = 0;
    4103             pCache->cbAnsiPaths     = 0;
     4338            pCache->cObjects                = 1;
     4339            pCache->cbObjects               = sizeof(pCache->RootDir)
     4340                                            + (pCache->RootDir.fHashTabMask + 1) * sizeof(pCache->RootDir.papHashTab[0]);
     4341            pCache->cPathHashHits           = 0;
     4342            pCache->cWalkHits               = 0;
     4343            pCache->cChildSearches          = 0;
     4344            pCache->cChildHashHits          = 0;
     4345            pCache->cChildHashed            = 0;
     4346            pCache->cChildHashTabs          = 1;
     4347            pCache->cChildHashEntriesTotal  = pCache->RootDir.fHashTabMask + 1;
     4348            pCache->cChildHashCollisions    = 0;
     4349            pCache->cAnsiPaths              = 0;
     4350            pCache->cAnsiPathCollisions     = 0;
     4351            pCache->cbAnsiPaths             = 0;
    41044352#ifdef KFSCACHE_CFG_UTF16
    4105             pCache->cUtf16Paths     = 0;
    4106             pCache->cUtf16PathCollisions = 0;
    4107             pCache->cbUtf16Paths    = 0;
     4353            pCache->cUtf16Paths             = 0;
     4354            pCache->cUtf16PathCollisions    = 0;
     4355            pCache->cbUtf16Paths            = 0;
    41084356#endif
    41094357            return pCache;

  • trunk/src/lib/nt/kFsCache.h

    r2912 r2930  
    4848/** @def KFSCACHE_CFG_PATH_HASH_TAB_SIZE
    4949 * Size of the path hash table. */
    50 #define KFSCACHE_CFG_PATH_HASH_TAB_SIZE     16381
     50#define KFSCACHE_CFG_PATH_HASH_TAB_SIZE     99991
    5151/** The max length paths we consider. */
    5252#define KFSCACHE_CFG_MAX_PATH               1024
    … …  
    112112
    113113
    114 /**
    115  * Directory hash table entry.
    116  *
    117  * There can be two of these per directory entry when the short name differs
    118  * from the long name.
    119  */
    120 typedef struct KFSOBJHASH
    121 {
    122     /** Pointer to the next entry with the same hash. */
    123     PKFSOBJHASH         pNext;
    124     /** Pointer to the object. */
    125     PKFSOBJ             pObj;
    126 } KFSOBJHASH;
    127 
    128114
    129115/** Pointer to a user data item. */
    … …  
    163149    KU32                fFlags;
    164150
     151    /** Hash value of the name inserted into the parent hash table.
     152     * This is 0 if not inserted.  Names are only hashed and inserted as they are
     153     * first found thru linear searching of its siblings, and which name it is
     154     * dependens on the lookup function (W or A) and whether the normal name or
     155     * short name seems to have matched.
     156     *
     157     * @note It was ruled out as too much work to hash and track all four names,
     158     *       so instead this minimalist approach was choosen in stead. */
     159    KU32                uNameHash;
     160    /** Pointer to the next child with the same name hash value. */
     161    PKFSOBJ             pNextNameHash;
    165162    /** Pointer to the parent (directory).
    166163     * This is only NULL for a root. */
    … …  
    231228    KU32                cChildrenAllocated;
    232229
    233     /** Pointer to the hash table.
    234      * @todo this isn't quite there yet, structure wise. sigh.  */
    235     PKFSOBJHASH         paHashTab;
    236     /** The size of the hash table.
    237      * @remarks The hash table is optional and only used when there are a lot of
    238      *          entries in the directory. */
    239     KU32                cHashTab;
     230    /** Pointer to the child hash table. */
     231    PKFSOBJ            *papHashTab;
     232    /** The mask shift of the hash table.
     233     * Hash table size is a power of two, this is the size minus one.
     234     *
     235     * @remarks The hash table is optional and populated by lookup hits.  The
     236     *          assumption being that a lookup is repeated and will choose a good
     237     *          name to hash on.  We've got up to 4 different hashes, so this
     238     *          was the easy way out. */
     239    KU32                fHashTabMask;
    240240
    241241    /** Handle to the directory (we generally keep it open). */
    … …  
    401401    /** Number of hits walking the file system hierarchy. */
    402402    KSIZE               cWalkHits;
     403    /** Number of child searches. */
     404    KSIZE               cChildSearches;
     405    /** Number of cChildLookups resolved thru hash table hits. */
     406    KSIZE               cChildHashHits;
     407    /** The number of child hash tables. */
     408    KSIZE               cChildHashTabs;
     409    /** The sum of all child hash table sizes. */
     410    KSIZE               cChildHashEntriesTotal;
     411    /** Number of children inserted into the hash tables. */
     412    KSIZE               cChildHashed;
     413    /** Number of collisions in the child hash tables */
     414    KSIZE               cChildHashCollisions;
    403415
    404416    /** The root directory. */
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