Changeset 80650 in vbox

Timestamp:

Sep 8, 2019 10:33:08 AM (5 years ago)

Author:

vboxsync

Message:

STAM: More by-prefix optimizations.

File:

• trunk/src/VBox/VMM/VMMR3/STAM.cpp (modified) (8 diffs)

trunk/src/VBox/VMM/VMMR3/STAM.cpp

@@ -1000 +1000 @@
 
 /**
- * Finds the first sample descriptor for a given lookup range.
+ * Finds the last sample descriptor for a given lookup range.
  *
  * This is for pattern range lookups.
@@ -1133 +1133 @@
  *
  * @returns Pointer to the first descriptor in the range.
- * @param   pRoot               The root node.
- * @param   pchPrefix           The name prefix.
- * @param   cchPrefix           The name prefix length (can be shorter than the
- *                              actual string).
+ * @param   pRoot       The root node.
+ * @param   pchPrefix   The name prefix.
+ * @param   cchPrefix   The name prefix length (can be shorter than the
+ *                      actual string).
+ * @param   ppLastDesc  Where to store the address of the last descriptor.
  * @sa      stamR3LookupFindPatternDescRange
  */
-static PSTAMDESC stamR3LookupFindFirstByPrefix(PSTAMLOOKUP pRoot, const char *pchPrefix, uint32_t cchPrefix)
-{
+static PSTAMDESC stamR3LookupFindByPrefixRange(PSTAMLOOKUP pRoot, const char *pchPrefix, uint32_t cchPrefix,
+                                               PSTAMDESC *ppLastDesc)
+
+{
+    *ppLastDesc = NULL;
     Assert(!pRoot->pParent);
-
-    /*
-     * All statistics starts with a slash.
-     */
-    while (   cchPrefix > 0
+    AssertReturn(cchPrefix > 0, NULL);
+
+    /*
+     * We start with a root slash.
+     */
+    if (!cchPrefix || *pchPrefix != '/')
+        return NULL;
+
+    /*
+     * Walk thru the prefix component by component, since that's how
+     * the lookup tree is organized.
+     */
+    while (   cchPrefix
            && *pchPrefix == '/'
            && pRoot->cDescsInTree > 0
@@ -1157 +1169 @@
         if (!pszEnd)
         {
-            /* We've narrowed it down to a sub-tree now. */
-            for (size_t i = 0; i < pRoot->cChildren; i++)
+            /*
+             * We've narrowed it down to a sub-tree now.  If we've no more prefix to work
+             * with now (e.g. '/Devices/'), the prefix matches all the children.  Otherwise,
+             * traverse the children to find the ones matching the prefix.
+             */
+            if (!cchPrefix)
             {
-                PSTAMLOOKUP pCur = pRoot->papChildren[i];
-                if (pCur->cch >= cchPrefix)
+                *ppLastDesc = stamR3LookupFindLastDescForRange(pRoot->papChildren[0], pRoot->papChildren[pRoot->cChildren - 1]);
+                return stamR3LookupFindFirstDescForRange(pRoot->papChildren[0], pRoot->papChildren[pRoot->cChildren - 1]);
+            }
+
+            size_t iEnd = pRoot->cChildren;
+            if (iEnd < 16)
+            {
+                /* Linear scan of the children: */
+                for (size_t i = 0; i < pRoot->cChildren; i++)
                 {
-                    int iDiff = memcmp(pCur->szName, pchPrefix, cchPrefix);
-                    if (iDiff == 0)
-                        return stamR3LookupFindFirstDescForRange(pCur, pRoot->papChildren[pRoot->cChildren - 1]);
-                    if (iDiff > 0)
-                        break;
+                    PSTAMLOOKUP pCur = pRoot->papChildren[i];
+                    if (pCur->cch >= cchPrefix)
+                    {
+                        int iDiff = memcmp(pCur->szName, pchPrefix, cchPrefix);
+                        if (iDiff == 0)
+                        {
+                            size_t iLast = i;
+                            while (++iLast < pRoot->cChildren)
+                            {
+                                PSTAMLOOKUP pCur2 = pRoot->papChildren[iLast];
+                                if (   pCur2->cch < cchPrefix
+                                    || memcmp(pCur2->szName, pchPrefix, cchPrefix) != 0)
+                                    break;
+                            }
+                            iLast--;
+
+                            *ppLastDesc = stamR3LookupFindLastDescForRange(pCur, pRoot->papChildren[iLast]);
+                            return stamR3LookupFindFirstDescForRange(pCur, pRoot->papChildren[iLast]);
+                        }
+                        if (iDiff > 0)
+                            break;
+                    }
                 }
             }
-            break;
-        }
-
-        uint32_t    cchElement = pszEnd - pchPrefix;
-        PSTAMLOOKUP pChild = stamR3LookupFindChild(pRoot, pchPrefix, cchElement, NULL);
+            else
+            {
+                /* Binary search to find something matching the prefix, followed
+                   by a reverse scan to locate the first child: */
+                size_t iFirst = 0;
+                size_t i      = iEnd / 2;
+                for (;;)
+                {
+                    PSTAMLOOKUP pCur = pRoot->papChildren[i];
+                    int iDiff;
+                    if (pCur->cch >= cchPrefix)
+                        iDiff = memcmp(pCur->szName, pchPrefix, cchPrefix);
+                    else
+                    {
+                        iDiff = memcmp(pCur->szName, pchPrefix, pCur->cch);
+                        if (!iDiff)
+                            iDiff = 1;
+                    }
+                    if (iDiff > 0)
+                    {
+                        if (iFirst < i)
+                            iEnd = i;
+                        else
+                            return NULL;
+                    }
+                    else if (iDiff < 0)
+                    {
+                        i += 1;
+                        if (i < iEnd)
+                            iFirst = i;
+                        else
+                            return NULL;
+                    }
+                    else
+                    {
+                        /* Match.  Reverse scan to find the first. */
+                        iFirst = i;
+                        while (   iFirst > 0
+                               && (pCur = pRoot->papChildren[iFirst - 1])->cch >= cchPrefix
+                               && memcmp(pCur->szName, pchPrefix, cchPrefix) == 0)
+                            iFirst--;
+
+                        /* Forward scan to find the last.*/
+                        size_t iLast = i;
+                        while (++iLast < pRoot->cChildren)
+                        {
+                            pCur = pRoot->papChildren[iLast];
+                            if (   pCur->cch < cchPrefix
+                                || memcmp(pCur->szName, pchPrefix, cchPrefix) != 0)
+                                break;
+                        }
+                        iLast--;
+
+                        *ppLastDesc = stamR3LookupFindLastDescForRange(pRoot->papChildren[iFirst], pRoot->papChildren[iLast]);
+                        return stamR3LookupFindFirstDescForRange(pRoot->papChildren[iFirst], pRoot->papChildren[iLast]);
+                    }
+
+                    i = iFirst + (iEnd - iFirst) / 2;
+                }
+            }
+            break;
+        }
+
+        /* Find child matching the path component:  */
+        uint32_t    cchChild = pszEnd - pchPrefix;
+        PSTAMLOOKUP pChild   = stamR3LookupFindChild(pRoot, pchPrefix, cchChild, NULL);
         if (!pChild)
             break;
 
-        /* Advance */
-        cchPrefix -= cchElement;
+        /* Advance: */
+        cchPrefix -= cchChild;
         pchPrefix  = pszEnd;
         pRoot      = pChild;
@@ -1751 +1852 @@
     STAM_LOCK_WR(pUVM);
 
-    PSTAMDESC pCur = stamR3LookupFindFirstByPrefix(pUVM->stam.s.pRoot, pszPrefix, (uint32_t)cchPrefix);
-    while (pCur)
-    {
-        PSTAMDESC const pNext   = RTListNodeGetNext(&pCur->ListEntry, STAMDESC, ListEntry);
-        size_t const    cchName = strlen(pCur->pszName);
-        if (   cchName >= cchPrefix
-            && memcmp(pCur->pszName, pszPrefix, cchPrefix) == 0)
+    PSTAMDESC pLast;
+    PSTAMDESC pCur = stamR3LookupFindByPrefixRange(pUVM->stam.s.pRoot, pszPrefix, (uint32_t)cchPrefix, &pLast);
+    if (pCur)
+        for (;;)
+        {
+            PSTAMDESC const pNext = RTListNodeGetNext(&pCur->ListEntry, STAMDESC, ListEntry);
+            Assert(strncmp(pCur->pszName, pszPrefix, cchPrefix) == 0);
+
             rc = stamR3DestroyDesc(pCur);
-        else
-            break;
-
-        /* advance. */
-        pCur = pNext;
-    }
+
+            /* advance. */
+            if (pCur == pLast)
+                break;
+            pCur = pNext;
+        }
 
     STAM_UNLOCK_WR(pUVM);
@@ -2661 +2763 @@
 
 /**
- * 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.
  *
@@ -2799 +2888 @@
         STAM_LOCK_RD(pUVM);
 #ifdef STAM_WITH_LOOKUP_TREE
-        if (!stamR3IsPattern(pszPat))
+        size_t const cchPat      = strlen(pszPat);
+        const char  *pszAsterisk = (const char *)memchr(pszPat, '*',  cchPat);
+        const char  *pszQuestion = (const char *)memchr(pszPat, '?',  cchPat);
+        if (!pszAsterisk && !pszQuestion)
         {
             pCur = stamR3LookupFindDesc(pUVM->stam.s.pRoot, pszPat);
@@ -2809 +2901 @@
             }
         }
+        /* Is this a prefix expression where we can use the lookup tree to
+           efficiently figure out the exact range? */
+        else if (   pszAsterisk == &pszPat[cchPat - 1]
+                 && pszPat[0] == '/'
+                 && !pszQuestion)
+        {
+            PSTAMDESC pLast;
+            pCur = stamR3LookupFindByPrefixRange(pUVM->stam.s.pRoot, pszPat, (uint32_t)(cchPat - 1), &pLast);
+            if (pCur)
+            {
+                for (;;)
+                {
+                    Assert(strncmp(pCur->pszName, pszPat, cchPat - 1) == 0);
+                    if (fUpdateRing0)
+                        stamR3Refresh(pUVM, pCur, &bmRefreshedGroups);
+                    rc = pfnCallback(pCur, pvArg);
+                    if (rc)
+                        break;
+                    if (pCur == pLast)
+                        break;
+                    pCur = RTListNodeGetNext(&pCur->ListEntry, STAMDESC, ListEntry);
+                }
+                Assert(pLast);
+            }
+            else
+                Assert(!pLast);
+        }
         else
         {
+            /* It's a more complicated pattern.  Find the approximate range
+               and scan it for matches. */
             PSTAMDESC pLast;
             pCur = stamR3LookupFindPatternDescRange(pUVM->stam.s.pRoot, &pUVM->stam.s.List, pszPat, &pLast);
@@ -2833 +2954 @@
             else
                 Assert(!pLast);
-
         }
 #else