diff options
author | vboxsync <vboxsync@cfe28804-0f27-0410-a406-dd0f0b0b656f> | 2013-06-07 19:09:25 +0000 |
---|---|---|
committer | vboxsync <vboxsync@cfe28804-0f27-0410-a406-dd0f0b0b656f> | 2013-06-07 19:09:25 +0000 |
commit | 89afc4fa067446232c146e05124afdfb179c9ebf (patch) | |
tree | 3c27427759bf463dd151076a834908810f6d42f3 /src | |
parent | 56139ef882a83a04c6d895dae17bf439b823770a (diff) | |
download | VirtualBox-svn-89afc4fa067446232c146e05124afdfb179c9ebf.tar.gz |
VMM: Optimize STAM enumeration. Multi pattern expressions are not optimized yet.
git-svn-id: https://www.virtualbox.org/svn/vbox/trunk@46447 cfe28804-0f27-0410-a406-dd0f0b0b656f
Diffstat (limited to 'src')
-rw-r--r-- | src/VBox/VMM/VMMR3/STAM.cpp | 294 |
1 files changed, 278 insertions, 16 deletions
diff --git a/src/VBox/VMM/VMMR3/STAM.cpp b/src/VBox/VMM/VMMR3/STAM.cpp index 91bbc3cbdd8..4075444a1c4 100644 --- a/src/VBox/VMM/VMMR3/STAM.cpp +++ b/src/VBox/VMM/VMMR3/STAM.cpp @@ -747,7 +747,8 @@ static PSTAMLOOKUP stamR3LookupFindChild(PSTAMLOOKUP pParent, const char *pchNam int iDiff = stamR3LookupCmp(pParent->papChildren[iChild], pchName, cchName); if (!iDiff) { - *piChild = iChild; + if (piChild) + *piChild = iChild; return pParent->papChildren[iChild]; } @@ -757,7 +758,8 @@ static PSTAMLOOKUP stamR3LookupFindChild(PSTAMLOOKUP pParent, const char *pchNam iFirst = iChild + 1; if (iFirst >= iEnd) { - *piChild = iChild; + if (piChild) + *piChild = iChild; break; } } @@ -765,7 +767,8 @@ static PSTAMLOOKUP stamR3LookupFindChild(PSTAMLOOKUP pParent, const char *pchNam { if (iChild == iFirst) { - *piChild = iChild ? iChild - 1 : 0; + if (piChild) + *piChild = iChild ? iChild - 1 : 0; break; } iEnd = iChild; @@ -785,21 +788,23 @@ static PSTAMLOOKUP stamR3LookupFindChild(PSTAMLOOKUP pParent, const char *pchNam int iDiff = stamR3LookupCmp(pParent->papChildren[iChild], pchName, cchName); if (iDiff <= 0) { - *piChild = iChild; + if (piChild) + *piChild = iChild; return !iDiff ? pParent->papChildren[iChild] : NULL; } } - *piChild = 0; + if (piChild) + *piChild = 0; return NULL; } /** - * Find the next sample description node. + * Find the next sample descriptor node. * - * This is for use with insertion in the big list. + * This is for use with insertion in the big list and pattern range lookups. * - * @returns Pointer to the next sample description. NULL if not found (i.e. + * @returns Pointer to the next sample descriptor. NULL if not found (i.e. * we're at the end of the list). * @param pLookup The current node. */ @@ -834,13 +839,229 @@ static PSTAMDESC stamR3LookupFindNextWithDesc(PSTAMLOOKUP pLookup) } else { - /* One level up, resuming after the current. */ + /* + * One level up, resuming after the current. + */ + iCur = pCur->iParent + 1; + pCur = pCur->pParent; + if (!pCur) + return NULL; + } + } +} + + +/** + * Look up a sample descriptor by name. + * + * @returns Pointer to a sample descriptor. + * @param pRoot The root node. + * @param pszName The name to lookup. + */ +static PSTAMDESC stamR3LookupFindDesc(PSTAMLOOKUP pRoot, const char *pszName) +{ + Assert(!pRoot->pParent); + while (*pszName++ == '/') + { + const char *pszEnd = strchr(pszName, '/'); + uint32_t cch = pszEnd ? pszEnd - pszName : strlen(pszName); + PSTAMLOOKUP pChild = stamR3LookupFindChild(pRoot, pszName, cch, NULL); + if (!pChild) + break; + if (!pszEnd) + return pChild->pDesc; + pszName = pszEnd; + pRoot = pChild; + } + + return NULL; +} + + +/** + * Finds the first sample descriptor for a given lookup range. + * + * This is for pattern range lookups. + * + * @returns Pointer to the first descriptor. + * @param pFirst The first node in the range. + * @param pLast The last node in the range. + */ +static PSTAMDESC stamR3LookupFindFirstDescForRange(PSTAMLOOKUP pFirst, PSTAMLOOKUP pLast) +{ + if (pFirst->pDesc) + return pFirst->pDesc; + + PSTAMLOOKUP pCur = pFirst; + uint32_t iCur = 0; + for (;;) + { + uint32_t cChildren = pCur->cChildren; + if (iCur < pCur->cChildren) + { + /* + * Check all children. + */ + PSTAMLOOKUP *papChildren = pCur->papChildren; + do + { + PSTAMLOOKUP pChild = pCur->papChildren[iCur]; + if (pChild->pDesc) + return pChild->pDesc; + if (pChild->cChildren > 0) + { + /* One level down. */ + iCur = 0; + pCur = pChild; + break; + } + if (pChild == pLast) + return NULL; + } while (++iCur < cChildren); + } + else + { + /* + * One level up, checking current and its 'older' sibilings. + */ + if (pCur == pLast) + return NULL; iCur = pCur->iParent + 1; pCur = pCur->pParent; if (!pCur) + break; + } + } + + return NULL; +} + + +/** + * Finds the first sample descriptor for a given lookup range. + * + * This is for pattern range lookups. + * + * @returns Pointer to the first descriptor. + * @param pFirst The first node in the range. + * @param pLast The last node in the range. + */ +static PSTAMDESC stamR3LookupFindLastDescForRange(PSTAMLOOKUP pFirst, PSTAMLOOKUP pLast) +{ + PSTAMLOOKUP pCur = pLast; + uint32_t iCur = pCur->cChildren - 1; + for (;;) + { + if (iCur < pCur->cChildren) + { + /* + * Check children backwards, depth first. + */ + PSTAMLOOKUP *papChildren = pCur->papChildren; + do + { + PSTAMLOOKUP pChild = pCur->papChildren[iCur]; + if (pChild->cChildren > 0) + { + /* One level down. */ + iCur = pChild->cChildren - 1; + pCur = pChild; + break; + } + + if (pChild->pDesc) + return pChild->pDesc; + if (pChild == pFirst) + return NULL; + } while (iCur-- > 0); /* (underflow handled above) */ + } + else + { + /* + * One level up, checking current and its 'older' sibilings. + */ + if (pCur->pDesc) + return pCur->pDesc; + if (pCur == pFirst) return NULL; + iCur = pCur->iParent - 1; /* (underflow handled above) */ + pCur = pCur->pParent; + if (!pCur) + break; + } + } + + return NULL; +} + + +/** + * Look up the first and last descriptors for a (single) pattern expression. + * + * This is used to optimize pattern enumerations and doesn't have to return 100% + * accurate results if that costs too much. + * + * @returns Pointer to the first descriptor in the range. + * @param pRoot The root node. + * @param pList The descriptor list anchor. + * @param pszPat The name patter to lookup. + * @param ppLastDesc Where to store the address of the last + * descriptor (approximate). + */ +static PSTAMDESC stamR3LookupFindPatternDescRange(PSTAMLOOKUP pRoot, PRTLISTANCHOR pList, const char *pszPat, + PSTAMDESC *ppLastDesc) +{ + Assert(!pRoot->pParent); + + /* + * If there is an early enough wildcard, the whole list needs to be searched. + */ + if ( pszPat[0] == '*' || pszPat[0] == '?' + || pszPat[1] == '*' || pszPat[1] == '?') + { + *ppLastDesc = RTListGetLast(pList, STAMDESC, ListEntry); + return RTListGetFirst(pList, STAMDESC, ListEntry); + } + + /* + * All statistics starts with a slash. + */ + while ( *pszPat++ == '/' + && pRoot->cDescsInTree > 0 + && pRoot->cChildren > 0) + { + const char *pszEnd = strchr(pszPat, '/'); + uint32_t cch = pszEnd ? pszEnd - pszPat : strlen(pszPat); + if (!cch) + break; + + const char *pszPat1 = (const char *)memchr(pszPat, '*', cch); + const char *pszPat2 = (const char *)memchr(pszPat, '?', cch); + if (pszPat1 || pszPat2) + { + /* We've narrowed it down to a sub-tree now. */ + PSTAMLOOKUP pFirst = pRoot->papChildren[0]; + PSTAMLOOKUP pLast = pRoot->papChildren[pRoot->cChildren - 1]; + /** @todo narrow the range further if both pszPat1/2 != pszPat. */ + + *ppLastDesc = stamR3LookupFindLastDescForRange(pFirst, pLast); + return stamR3LookupFindFirstDescForRange(pFirst, pLast); } + + PSTAMLOOKUP pChild = stamR3LookupFindChild(pRoot, pszPat, cch, NULL); + if (!pChild) + break; + + /* Advance */ + if (!pszEnd) + return *ppLastDesc = pChild->pDesc; + pszPat = pszEnd; + pRoot = pChild; } + + /* No match. */ + *ppLastDesc = NULL; + return NULL; } @@ -2035,6 +2256,19 @@ static int stamR3EnumOne(PSTAMDESC pDesc, void *pvArg) /** + * Checks if the string contains a pattern expression or not. + * + * @returns true / false. + * @param pszPat The potential pattern. + */ +static bool stamR3IsPattern(const char *pszPat) +{ + return strchr(pszPat, '*') != NULL + || strchr(pszPat, '?') != NULL; +} + + +/** * Match a name against an array of patterns. * * @returns true if it matches, false if it doesn't match. @@ -2132,9 +2366,10 @@ static int stamR3EnumU(PUVM pUVM, const char *pszPat, bool fUpdateRing0, int (*pfnCallback)(PSTAMDESC pDesc, void *pvArg), void *pvArg) { int rc = VINF_SUCCESS; + PSTAMDESC pCur; /* - * All + * All. */ if (!pszPat || !*pszPat || !strcmp(pszPat, "*")) { @@ -2142,7 +2377,6 @@ static int stamR3EnumU(PUVM pUVM, const char *pszPat, bool fUpdateRing0, stamR3Ring0StatsUpdateU(pUVM, "*"); STAM_LOCK_RD(pUVM); - PSTAMDESC pCur; RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry) { rc = pfnCallback(pCur, pvArg); @@ -2161,10 +2395,38 @@ static int stamR3EnumU(PUVM pUVM, const char *pszPat, bool fUpdateRing0, stamR3Ring0StatsUpdateU(pUVM, pszPat); STAM_LOCK_RD(pUVM); - /** @todo This needs to be optimized since the GUI is using this path for the VM info dialog. - * Note that it's doing exact matching. Organizing the samples in a tree would speed up thing - * no end (at least for debug and profile builds). */ - PSTAMDESC pCur; +#ifdef STAM_WITH_LOOKUP_TREE + if (!stamR3IsPattern(pszPat)) + { + pCur = stamR3LookupFindDesc(pUVM->stam.s.pRoot, pszPat); + if (pCur) + rc = pfnCallback(pCur, pvArg); + } + else + { + PSTAMDESC pLast; + pCur = stamR3LookupFindPatternDescRange(pUVM->stam.s.pRoot, &pUVM->stam.s.List, pszPat, &pLast); + if (pCur) + { + for (;;) + { + if (RTStrSimplePatternMatch(pszPat, pCur->pszName)) + { + rc = pfnCallback(pCur, pvArg); + if (rc) + break; + } + if (pCur == pLast) + break; + pCur = RTListNodeGetNext(&pCur->ListEntry, STAMDESC, ListEntry); + } + Assert(pLast); + } + else + Assert(!pLast); + + } +#else RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry) { if (RTStrSimplePatternMatch(pszPat, pCur->pszName)) @@ -2174,6 +2436,7 @@ static int stamR3EnumU(PUVM pUVM, const char *pszPat, bool fUpdateRing0, break; } } +#endif STAM_UNLOCK_RD(pUVM); } @@ -2199,7 +2462,6 @@ static int stamR3EnumU(PUVM pUVM, const char *pszPat, bool fUpdateRing0, STAM_LOCK_RD(pUVM); unsigned iExpression = 0; - PSTAMDESC pCur; RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry) { if (stamR3MultiMatch(papszExpressions, cExpressions, &iExpression, pCur->pszName)) |