Changeset 46447 in vbox for trunk/src/VBox/VMM

Timestamp:

Jun 7, 2013 7:09:25 PM (12 years ago)

Author:

vboxsync

Message:

VMM: Optimize STAM enumeration. Multi pattern expressions are not optimized yet.

File:

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

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

@@ -748 +748 @@
             if (!iDiff)
             {
-                *piChild = iChild;
+                if (piChild)
+                    *piChild = iChild;
                 return pParent->papChildren[iChild];
             }
@@ -758 +759 @@
                 if (iFirst >= iEnd)
                 {
-                    *piChild = iChild;
+                    if (piChild)
+                        *piChild = iChild;
                     break;
                 }
@@ -766 +768 @@
                 if (iChild == iFirst)
                 {
-                    *piChild = iChild ? iChild - 1 : 0;
+                    if (piChild)
+                        *piChild = iChild ? iChild - 1 : 0;
                     break;
                 }
@@ -786 +789 @@
         if (iDiff <= 0)
         {
-            *piChild = iChild;
+            if (piChild)
+                *piChild = iChild;
             return !iDiff ? pParent->papChildren[iChild] : NULL;
         }
     }
-    *piChild = 0;
+    if (piChild)
+        *piChild = 0;
     return NULL;
 }
@@ -796 +801 @@
 
 /**
- * Find the next sample description node.
- *
- * This is for use with insertion in the big list.
- *
- * @returns Pointer to the next sample description. NULL if not found (i.e.
+ * Find the next sample descriptor node.
+ *
+ * This is for use with insertion in the big list and pattern range lookups.
+ *
+ * @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.
@@ -835 +840 @@
         else
         {
-            /* One level up, resuming after the current. */
+            /*
+             * One level up, resuming after the current.
+             */
             iCur = pCur->iParent + 1;
             pCur = pCur->pParent;
@@ -842 +849 @@
         }
     }
+}
+
+
+/**
+ * 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;
 }
 
@@ -2036 +2257 @@
 
 /**
+ * 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.
  *
@@ -2133 +2367 @@
 {
     int rc = VINF_SUCCESS;
-
-    /*
-     * All
+    PSTAMDESC pCur;
+
+    /*
+     * All.
      */
     if (!pszPat || !*pszPat || !strcmp(pszPat, "*"))
@@ -2143 +2378 @@
 
         STAM_LOCK_RD(pUVM);
-        PSTAMDESC pCur;
         RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
         {
@@ -2162 +2396 @@
 
         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)
         {
@@ -2175 +2437 @@
             }
         }
+#endif
         STAM_UNLOCK_RD(pUVM);
     }
@@ -2200 +2463 @@
         STAM_LOCK_RD(pUVM);
         unsigned iExpression = 0;
-        PSTAMDESC pCur;
         RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
         {