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

Timestamp:

Jun 7, 2013 4:18:29 PM (12 years ago)

Author:

vboxsync

Message:

STAM: Registration optimizations.

Location:

trunk/src/VBox/VMM

Files:

• VMMR3/STAM.cpp (modified) (18 diffs)
• include/STAMInternal.h (modified) (6 diffs)

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

@@ -59 +59 @@
 #include <iprt/assert.h>
 #include <iprt/asm.h>
-#include <iprt/alloc.h>
+#include <iprt/mem.h>
 #include <iprt/stream.h>
 #include <iprt/string.h>
@@ -133 +133 @@
 *   Internal Functions                                                         *
 *******************************************************************************/
+#ifdef STAM_WITH_LOOKUP_TREE
+static void                 stamR3LookupDestroyTree(PSTAMLOOKUP pRoot);
+#endif
 static int                  stamR3RegisterU(PUVM pUVM, void *pvSample, PFNSTAMR3CALLBACKRESET pfnReset, PFNSTAMR3CALLBACKPRINT pfnPrint,
                                             STAMTYPE enmType, STAMVISIBILITY enmVisibility, const char *pszName, STAMUNIT enmUnit, const char *pszDesc);
@@ -272 +275 @@
 
     /*
-     * Initialize the read/write lock.
+     * Initialize the read/write lock and list.
      */
     int rc = RTSemRWCreate(&pUVM->stam.s.RWSem);
     AssertRCReturn(rc, rc);
+
+    RTListInit(&pUVM->stam.s.List);
+
+#ifdef STAM_WITH_LOOKUP_TREE
+    /*
+     * Initialize the root node.
+     */
+    PSTAMLOOKUP pRoot = (PSTAMLOOKUP)RTMemAlloc(sizeof(STAMLOOKUP));
+    if (!pRoot)
+    {
+        RTSemRWDestroy(pUVM->stam.s.RWSem);
+        pUVM->stam.s.RWSem = NIL_RTSEMRW;
+        return VERR_NO_MEMORY;
+    }
+    pRoot->pParent      = NULL;
+    pRoot->papChildren   = NULL;
+    pRoot->pDesc        = NULL;
+    pRoot->cDescsInTree = 0;
+    pRoot->cChildren    = 0;
+    pRoot->iParent      = UINT16_MAX;
+    pRoot->off          = 0;
+    pRoot->cch          = 0;
+    pRoot->szName[0]    = '\0';
+
+    pUVM->stam.s.pRoot = pRoot;
+#endif
+
 
     /*
@@ -309 +339 @@
      * Free used memory and the RWLock.
      */
-    PSTAMDESC pCur = pUVM->stam.s.pHead;
-    while (pCur)
-    {
-        void *pvFree = pCur;
-        pCur = pCur->pNext;
-        RTMemFree(pvFree);
-    }
-    pUVM->stam.s.pHead = NULL;
+    PSTAMDESC pCur, pNext;
+    RTListForEachSafe(&pUVM->stam.s.List, pCur, pNext, STAMDESC, ListEntry)
+    {
+#ifdef STAM_WITH_LOOKUP_TREE
+        pCur->pLookup->pDesc = NULL;
+#endif
+        RTMemFree(pCur);
+    }
+
+#ifdef STAM_WITH_LOOKUP_TREE
+    stamR3LookupDestroyTree(pUVM->stam.s.pRoot);
+    pUVM->stam.s.pRoot = NULL;
+#endif
 
     Assert(pUVM->stam.s.RWSem != NIL_RTSEMRW);
@@ -577 +612 @@
 }
 #endif /* VBOX_STRICT */
+
+
+#ifdef STAM_WITH_LOOKUP_TREE
+
+/**
+ * Compares a lookup node with a name.
+ *
+ * @returns like strcmp and memcmp.
+ * @param   pNode               The lookup node.
+ * @param   pchName             The name, not necessarily terminated.
+ * @param   cchName             The length of the name.
+ */
+DECL_FORCE_INLINE(int) stamR3LookupCmp(PSTAMLOOKUP pNode, const char *pchName, uint32_t cchName)
+{
+    uint32_t cchComp = RT_MIN(pNode->cch, cchName);
+    int iDiff = memcmp(pNode->szName, pchName, cchComp);
+    if (!iDiff && pNode->cch != cchName)
+        iDiff = pNode->cch > cchName ? 2 : -2;
+    return iDiff;
+}
+
+
+/**
+ * Creates a new lookup child node.
+ *
+ * @returns Pointer to the newly created lookup node.
+ * @param   pParent             The parent node.
+ * @param   pchName             The name (not necessarily terminated).
+ * @param   cchName             The length of the name.
+ * @param   offName             The offset of the node in a path.
+ * @param   iChild              Child index of a node that's before the one
+ *                              we're inserting (returned by
+ *                              stamR3LookupFindChild).
+ */
+static PSTAMLOOKUP stamR3LookupNewChild(PSTAMLOOKUP pParent, const char *pchName, uint32_t cchName, uint32_t offName,
+                                        uint32_t iChild)
+{
+    Assert(cchName <= UINT8_MAX);
+    Assert(offName <= UINT8_MAX);
+    Assert(iChild  <  UINT16_MAX);
+
+    /*
+     * Allocate a new entry.
+     */
+    PSTAMLOOKUP pNew = (PSTAMLOOKUP)RTMemAlloc(RT_OFFSETOF(STAMLOOKUP, szName[cchName + 1]));
+    if (!pNew)
+        return NULL;
+    pNew->pParent       = pParent;
+    pNew->papChildren    = NULL;
+    pNew->pDesc         = NULL;
+    pNew->cDescsInTree  = 0;
+    pNew->cChildren     = 0;
+    pNew->cch           = (uint16_t)cchName;
+    pNew->off           = (uint16_t)offName;
+    memcpy(pNew->szName, pchName, cchName);
+    pNew->szName[cchName] = '\0';
+
+    /*
+     * Reallocate the array?
+     */
+    if (RT_IS_POWER_OF_TWO(pParent->cChildren))
+    {
+        uint32_t cNew = pParent->cChildren ? (uint32_t)pParent->cChildren * 2 : 8;
+        AssertReturnStmt(cNew <= 0x8000, RTMemFree(pNew), NULL);
+        void *pvNew = RTMemRealloc(pParent->papChildren, cNew * sizeof(pParent->papChildren[0]));
+        if (!pvNew)
+        {
+            RTMemFree(pNew);
+            return NULL;
+        }
+        pParent->papChildren = (PSTAMLOOKUP *)pvNew;
+    }
+
+    /*
+     * Find the exact insertion point using iChild as a very good clue from
+     * the find function.
+     */
+    if (!pParent->cChildren)
+        iChild = 0;
+    else
+    {
+        if (iChild >= pParent->cChildren)
+            iChild = pParent->cChildren - 1;
+        while (   iChild < pParent->cChildren
+               && stamR3LookupCmp(pParent->papChildren[iChild], pchName, cchName) < 0)
+            iChild++;
+    }
+
+    /*
+     * Insert it.
+     */
+    if (iChild < pParent->cChildren)
+    {
+        /* Do shift. */
+        uint32_t i = pParent->cChildren;
+        while (i > iChild)
+        {
+            PSTAMLOOKUP pNode = pParent->papChildren[i - 1];
+            pParent->papChildren[i] = pNode;
+            pNode->iParent = i;
+            i--;
+        }
+    }
+
+    pNew->iParent = iChild;
+    pParent->papChildren[iChild] = pNew;
+    pParent->cChildren++;
+
+    return pNew;
+}
+
+
+/**
+ * Looks up a child.
+ *
+ * @returns Pointer to child node if found, NULL if not.
+ * @param   pParent             The parent node.
+ * @param   pchName             The name (not necessarily terminated).
+ * @param   cchName             The length of the name.
+ * @param   piChild             Where to store a child index suitable for
+ *                              passing to stamR3LookupNewChild when NULL is
+ *                              returned.
+ */
+static PSTAMLOOKUP stamR3LookupFindChild(PSTAMLOOKUP pParent, const char *pchName, uint32_t cchName, uint32_t *piChild)
+{
+    uint32_t iChild = pParent->cChildren;
+    if (iChild > 4)
+    {
+        uint32_t iFirst = 0;
+        uint32_t iEnd   = iChild;
+        iChild /= 2;
+        for (;;)
+        {
+            int iDiff = stamR3LookupCmp(pParent->papChildren[iChild], pchName, cchName);
+            if (!iDiff)
+            {
+                *piChild = iChild;
+                return pParent->papChildren[iChild];
+            }
+
+            /* Split. */
+            if (iDiff < 0)
+            {
+                iFirst = iChild + 1;
+                if (iFirst >= iEnd)
+                {
+                    *piChild = iChild;
+                    break;
+                }
+            }
+            else
+            {
+                if (iChild == iFirst)
+                {
+                    *piChild = iChild ? iChild - 1 : 0;
+                    break;
+                }
+                iEnd = iChild;
+            }
+
+            /* Calc next child. */
+            iChild = (iEnd - iFirst) / 2 + iFirst;
+        }
+        return NULL;
+    }
+
+    /*
+     * Linear search.
+     */
+    while (iChild-- > 0)
+    {
+        int iDiff = stamR3LookupCmp(pParent->papChildren[iChild], pchName, cchName);
+        if (iDiff <= 0)
+        {
+            *piChild = iChild;
+            return !iDiff ? pParent->papChildren[iChild] : NULL;
+        }
+    }
+    *piChild = 0;
+    return NULL;
+}
+
+
+/**
+ * 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.
+ *          we're at the end of the list).
+ * @param   pLookup             The current node.
+ */
+static PSTAMDESC stamR3LookupFindNextWithDesc(PSTAMLOOKUP pLookup)
+{
+    Assert(!pLookup->pDesc);
+    PSTAMLOOKUP pCur = pLookup;
+    uint32_t    iCur = 0;
+    for (;;)
+    {
+        /*
+         * Check all children.
+         */
+        uint32_t cChildren = pCur->cChildren;
+        if (iCur < cChildren)
+        {
+            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;
+                }
+            } while (++iCur < cChildren);
+        }
+        else
+        {
+            /* One level up, resuming after the current. */
+            iCur = pCur->iParent + 1;
+            pCur = pCur->pParent;
+            if (!pCur)
+                return NULL;
+        }
+    }
+}
+
+
+/**
+ * Increments the cDescInTree member of the given node an all ancestors.
+ *
+ * @param   pLookup             The lookup node.
+ */
+static void stamR3LookupIncUsage(PSTAMLOOKUP pLookup)
+{
+    Assert(pLookup->pDesc);
+
+    PSTAMLOOKUP pCur = pLookup;
+    while (pCur != NULL)
+    {
+        pCur->cDescsInTree++;
+        pCur = pCur->pParent;
+    }
+}
+
+
+/**
+ * Descrements the cDescInTree member of the given node an all ancestors.
+ *
+ * @param   pLookup             The lookup node.
+ */
+static void stamR3LookupDecUsage(PSTAMLOOKUP pLookup)
+{
+    Assert(!pLookup->pDesc);
+
+    PSTAMLOOKUP pCur = pLookup;
+    while (pCur != NULL)
+    {
+        Assert(pCur->cDescsInTree > 0);
+        pCur->cDescsInTree--;
+        pCur = pCur->pParent;
+    }
+}
+
+
+/**
+ * Frees empty lookup nodes if it's worth it.
+ *
+ * @param   pLookup             The lookup node.
+ */
+static void stamR3LookupMaybeFree(PSTAMLOOKUP pLookup)
+{
+    Assert(!pLookup->pDesc);
+
+    /*
+     * Free between two and three levels of nodes.  Freeing too much most
+     * likely wasted effort since we're either going to repopluate the tree
+     * or quit the whole thing.
+     */
+    if (pLookup->cDescsInTree > 0)
+        return;
+
+    PSTAMLOOKUP pCur = pLookup->pParent;
+    if (!pCur)
+        return;
+    if (pCur->cDescsInTree > 0)
+        return;
+    PSTAMLOOKUP pParent = pCur->pParent;
+    if (pParent)
+        return;
+
+    if (pParent->cDescsInTree == 0 && pParent->pParent)
+    {
+        pCur = pParent;
+        pParent = pCur->pParent;
+    }
+
+    /*
+     * Remove pCur from pParent.
+     */
+    PSTAMLOOKUP *papChildren = pParent->papChildren;
+    uint32_t     cChildren   = --pParent->cChildren;
+    for (uint32_t i = pCur->iParent; i < cChildren; i++)
+    {
+        PSTAMLOOKUP pChild = papChildren[i + 1];
+        pChild->iParent = i;
+        papChildren[i] = pChild;
+    }
+    pCur->pParent = NULL;
+
+    /*
+     * Destroy pCur.
+     */
+    stamR3LookupDestroyTree(pCur);
+}
+
+
+/**
+ * Destroys a lookup tree.
+ *
+ * This is used by STAMR3Term as well as stamR3LookupMaybeFree.
+ *
+ * @param   pRoot               The root of the tree (must have no parent).
+ */
+static void stamR3LookupDestroyTree(PSTAMLOOKUP pRoot)
+{
+    Assert(pRoot); Assert(!pRoot->pParent);
+    PSTAMLOOKUP pLookup = pRoot;
+    for (;;)
+    {
+        uint32_t i = pLookup->cChildren;
+        if (i > 0)
+        {
+            /*
+             * Push child (with leaf optimization).
+             */
+            PSTAMLOOKUP pChild = pLookup->papChildren[--i];
+            if (pChild->cChildren != 0)
+                pLookup = pChild;
+            else
+            {
+                /* free leaves. */
+                for (;;)
+                {
+                    if (pChild->papChildren)
+                    {
+                        RTMemFree(pChild->papChildren);
+                        pChild->papChildren = NULL;
+                    }
+                    RTMemFree(pChild);
+
+                    /* next */
+                    if (i == 0)
+                    {
+                        pLookup->papChildren = 0;
+                        break;
+                    }
+                    pChild = pLookup->papChildren[--i];
+                    if (pChild->cChildren != 0)
+                    {
+                        pLookup->cChildren = i + 1;
+                        pLookup = pChild;
+                        break;
+                    }
+                }
+            }
+        }
+        else
+        {
+            /*
+             * Pop and free current.
+             */
+            Assert(!pLookup->pDesc);
+
+            PSTAMLOOKUP pParent = pLookup->pParent;
+            RTMemFree(pLookup->papChildren);
+            pLookup->papChildren = NULL;
+            RTMemFree(pLookup);
+
+            pLookup = pParent;
+            if (!pLookup)
+                break;
+            pLookup->cChildren--;
+        }
+    }
+}
+
+#endif /* STAM_WITH_LOOKUP_TREE */
+
 
 
@@ -598 +1027 @@
                            STAMTYPE enmType, STAMVISIBILITY enmVisibility, const char *pszName, STAMUNIT enmUnit, const char *pszDesc)
 {
+    AssertReturn(pszName[0] == '/', VERR_INVALID_NAME);
+    AssertReturn(pszName[1] != '/' && pszName[1], VERR_INVALID_NAME);
+    uint32_t const cchName = (uint32_t)strlen(pszName);
+    AssertReturn(cchName < 256, VERR_OUT_OF_RANGE);
+    AssertReturn(pszName[cchName - 1] != '/', VERR_INVALID_NAME);
+    AssertReturn(memchr(pszName, '\\', cchName) == NULL, VERR_INVALID_NAME);
+
     STAM_LOCK_WR(pUVM);
 
     /*
-     * Check if exists.
-     */
-#if 0
-    PSTAMDESC   pPrev = pUVM->stam.s.pHint;
-    PSTAMDESC   pCur  = pPrev ? pPrev->pNext : NULL;
-    if (!pCur || strcmp(pCur->pszName, pszName) > 0)
-    {
-        pPrev = NULL;
-        pCur  = pUVM->stam.s.pHead;
-    }
+     * Look up the tree location, populating the lookup tree as we walk it.
+     */
+#ifdef STAM_WITH_LOOKUP_TREE
+    PSTAMLOOKUP pLookup = pUVM->stam.s.pRoot; Assert(pLookup);
+    uint32_t    offName = 1;
+    for (;;)
+    {
+        /* Get the next part of the path. */
+        const char *pszStart = &pszName[offName];
+        const char *pszEnd   = strchr(pszStart, '/');
+        uint32_t    cch      = pszEnd ? (uint32_t)(pszEnd - pszStart) : cchName - offName;
+        if (cch == 0)
+        {
+            STAM_UNLOCK_WR(pUVM);
+            AssertMsgFailed(("No double or trailing slashes are allowed: '%s'\n", pszName));
+            return VERR_INVALID_NAME;
+        }
+
+        /* Do the looking up. */
+        uint32_t    iChild = 0;
+        PSTAMLOOKUP pChild = stamR3LookupFindChild(pLookup, pszStart, cch, &iChild);
+        if (!pChild)
+        {
+            pChild = stamR3LookupNewChild(pLookup, pszStart, cch, offName, iChild);
+            if (!pChild)
+            {
+                STAM_UNLOCK_WR(pUVM);
+                return VERR_NO_MEMORY;
+            }
+        }
+
+        /* Advance. */
+        pLookup = pChild;
+        if (!pszEnd)
+            break;
+        offName += cch + 1;
+    }
+    if (pLookup->pDesc)
+    {
+        STAM_UNLOCK_WR(pUVM);
+        AssertMsgFailed(("Duplicate sample name: %s\n", pszName));
+        return VERR_ALREADY_EXISTS;
+    }
+
+    PSTAMDESC pCur = stamR3LookupFindNextWithDesc(pLookup);
+
 #else
-    PSTAMDESC   pPrev = NULL;
-    PSTAMDESC   pCur  = pUVM->stam.s.pHead;
-#endif
-    while (pCur)
+    PSTAMDESC pCur;
+    RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
     {
         int iDiff = strcmp(pCur->pszName, pszName);
@@ -628 +1098 @@
             return VERR_ALREADY_EXISTS;
         }
-
-        /* next */
-        pPrev = pCur;
-        pCur = pCur->pNext;
-    }
-    pUVM->stam.s.pHint = pPrev;
+    }
+#endif
 
     /*
@@ -640 +1106 @@
      * Problematic chars are: !"#$%&'()*+,-.
      */
+#ifdef VBOX_STRICT
     Assert(pszName[0] == '/');
-    if (pPrev)
-        Assert(stamR3SlashCompare(pPrev->pszName, pszName) < 0);
-    if (pCur)
-        Assert(stamR3SlashCompare(pCur->pszName, pszName) > 0);
-
-#ifdef VBOX_STRICT
+    PSTAMDESC pPrev = pCur
+                    ? RTListGetPrev(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
+                    : RTListGetLast(&pUVM->stam.s.List, STAMDESC, ListEntry);
+    Assert(!pPrev || strcmp(pszName, pPrev->pszName) > 0);
+    Assert(!pCur  || strcmp(pszName, pCur->pszName)  < 0);
+    Assert(!pPrev || stamR3SlashCompare(pPrev->pszName, pszName) < 0);
+    Assert(!pCur  || stamR3SlashCompare(pCur->pszName, pszName) > 0);
+
     /*
      * Check alignment requirements.
@@ -701 +1170 @@
      */
     int rc;
-    size_t cchName = strlen(pszName) + 1;
-    size_t cchDesc = pszDesc ? strlen(pszDesc) + 1 : 0;
-    PSTAMDESC pNew = (PSTAMDESC)RTMemAlloc(sizeof(*pNew) + cchName + cchDesc);
+    size_t cbDesc = pszDesc ? strlen(pszDesc) + 1 : 0;
+    PSTAMDESC pNew = (PSTAMDESC)RTMemAlloc(sizeof(*pNew) + cchName + 1 + cbDesc);
     if (pNew)
     {
-        pNew->pszName       = (char *)memcpy((char *)(pNew + 1), pszName, cchName);
+        pNew->pszName       = (char *)memcpy((char *)(pNew + 1), pszName, cchName + 1);
         pNew->enmType       = enmType;
         pNew->enmVisibility = enmVisibility;
@@ -720 +1188 @@
         pNew->pszDesc       = NULL;
         if (pszDesc)
-            pNew->pszDesc   = (char *)memcpy((char *)(pNew + 1) + cchName,  pszDesc,  cchDesc);
-
-        pNew->pNext         = pCur;
-        if (pPrev)
-            pPrev->pNext    = pNew;
+            pNew->pszDesc   = (char *)memcpy((char *)(pNew + 1) + cchName + 1, pszDesc, cbDesc);
+
+        if (pCur)
+            RTListNodeInsertBefore(&pCur->ListEntry, &pNew->ListEntry);
         else
-            pUVM->stam.s.pHead = pNew;
+            RTListAppend(&pUVM->stam.s.List, &pNew->ListEntry);
+
+#ifdef STAM_WITH_LOOKUP_TREE
+        pNew->pLookup       = pLookup;
+        pLookup->pDesc      = pNew;
+        stamR3LookupIncUsage(pLookup);
+#endif
 
         stamR3ResetOne(pNew, pUVM->pVM);
@@ -759 +1232 @@
      */
     int         rc = VERR_INVALID_HANDLE;
-    PSTAMDESC   pPrev = NULL;
-    PSTAMDESC   pCur = pUVM->stam.s.pHead;
-    while (pCur)
+    PSTAMDESC   pCur, pNext;
+    RTListForEachSafe(&pUVM->stam.s.List, pCur, pNext, STAMDESC, ListEntry)
     {
         if (pCur->u.pv == pvSample)
         {
-            void *pvFree = pCur;
-            pCur = pCur->pNext;
-            if (pPrev)
-                pPrev->pNext = pCur;
-            else
-                pUVM->stam.s.pHead = pCur;
-
-            RTMemFree(pvFree);
+            RTListNodeRemove(&pCur->ListEntry);
+#ifdef STAM_WITH_LOOKUP_TREE
+            pCur->pLookup->pDesc = NULL; /** @todo free lookup nodes once it's working. */
+            stamR3LookupDecUsage(pCur->pLookup);
+            stamR3LookupMaybeFree(pCur->pLookup);
+#endif
+            RTMemFree(pCur);
             rc = VINF_SUCCESS;
-            continue;
-        }
-
-        /* next */
-        pPrev = pCur;
-        pCur = pCur->pNext;
+        }
     }
 
@@ -1677 +2143 @@
 
         STAM_LOCK_RD(pUVM);
-        PSTAMDESC pCur = pUVM->stam.s.pHead;
-        while (pCur)
+        PSTAMDESC pCur;
+        RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
         {
             rc = pfnCallback(pCur, pvArg);
             if (rc)
                 break;
-
-            /* next */
-            pCur = pCur->pNext;
         }
         STAM_UNLOCK_RD(pUVM);
@@ -1702 +2165 @@
          * 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). */
-        for (PSTAMDESC pCur = pUVM->stam.s.pHead; pCur; pCur = pCur->pNext)
+        PSTAMDESC pCur;
+        RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
+        {
             if (RTStrSimplePatternMatch(pszPat, pCur->pszName))
             {
@@ -1709 +2174 @@
                     break;
             }
+        }
         STAM_UNLOCK_RD(pUVM);
     }
@@ -1734 +2200 @@
         STAM_LOCK_RD(pUVM);
         unsigned iExpression = 0;
-        for (PSTAMDESC pCur = pUVM->stam.s.pHead; pCur; pCur = pCur->pNext)
+        PSTAMDESC pCur;
+        RTListForEach(&pUVM->stam.s.List, pCur, STAMDESC, ListEntry)
+        {
             if (stamR3MultiMatch(papszExpressions, cExpressions, &iExpression, pCur->pszName))
             {
@@ -1741 +2209 @@
                     break;
             }
+        }
         STAM_UNLOCK_RD(pUVM);
 
@@ -1933 +2402 @@
      */
     DBGC_CMDHLP_REQ_UVM_RET(pCmdHlp, pCmd, pUVM);
-    if (!pUVM->stam.s.pHead)
+    if (RTListIsEmpty(&pUVM->stam.s.List))
         return DBGCCmdHlpFail(pCmdHlp, pCmd, "No statistics present");
 
@@ -1976 +2445 @@
      */
     DBGC_CMDHLP_REQ_UVM_RET(pCmdHlp, pCmd, pUVM);
-    if (!pUVM->stam.s.pHead)
+    if (RTListIsEmpty(&pUVM->stam.s.List))
         return DBGCCmdHlpFail(pCmdHlp, pCmd, "No statistics present");
 

trunk/src/VBox/VMM/include/STAMInternal.h

@@ -24 +24 @@
 #include <VBox/vmm/gvmm.h>
 #include <VBox/vmm/gmm.h>
+#include <iprt/list.h>
 #include <iprt/semaphore.h>
 
@@ -36 +37 @@
  */
 
+/** Enables the lookup tree.
+ * This is an optimization for speeding up registration as well as query. */
+#define STAM_WITH_LOOKUP_TREE
+
+
+/** Pointer to sample descriptor. */
+typedef struct STAMDESC    *PSTAMDESC;
+/** Pointer to a sample lookup node. */
+typedef struct STAMLOOKUP  *PSTAMLOOKUP;
+
+/**
+ * Sample lookup node.
+ */
+typedef struct STAMLOOKUP
+{
+    /** The parent lookup record. This is NULL for the root node. */
+    PSTAMLOOKUP         pParent;
+    /** Array of children (using array for binary searching). */
+    PSTAMLOOKUP        *papChildren;
+    /** Pointer to the description node, if any. */
+    PSTAMDESC           pDesc;
+    /** Number of decentants with descriptors. (Use for freeing up sub-trees.) */
+    uint32_t            cDescsInTree;
+    /** The number of children. */
+    uint16_t            cChildren;
+    /** The index in the parent paChildren array. UINT16_MAX for the root node. */
+    uint16_t            iParent;
+    /** The path offset. */
+    uint16_t            off;
+    /** The size of the path component. */
+    uint16_t            cch;
+    /** The name (variable size). */
+    char                szName[1];
+} STAMLOOKUP;
+
+
 /**
  * Sample descriptor.
@@ -41 +78 @@
 typedef struct STAMDESC
 {
-    /** Pointer to the next sample. */
-    struct STAMDESC    *pNext;
+    /** Our entry in the big linear list. */
+    RTLISTNODE          ListEntry;
+    /** Pointer to our lookup node. */
+    PSTAMLOOKUP         pLookup;
     /** Sample name. */
     const char         *pszName;
@@ -88 +127 @@
     const char         *pszDesc;
 } STAMDESC;
-/** Pointer to sample descriptor. */
-typedef STAMDESC        *PSTAMDESC;
-/** Pointer to const sample descriptor. */
-typedef const STAMDESC  *PCSTAMDESC;
 
 
@@ -99 +134 @@
 typedef struct STAMUSERPERVM
 {
-    /** Pointer to the first sample. */
-    R3PTRTYPE(PSTAMDESC)    pHead;
-    /** Lookup hint (pPrev value). */
-    R3PTRTYPE(PSTAMDESC)    pHint;
-    /** RW Lock for the list. */
+    /** List of samples. */
+    RTLISTANCHOR            List;
+    /** Root of the lookup tree. */
+    PSTAMLOOKUP             pRoot;
+
+    /** RW Lock for the list and tree. */
     RTSEMRW                 RWSem;
-    /** Alignment padding. */
-    RTR3PTR                 Alignment;
 
     /** The copy of the GVMM statistics. */
@@ -118 +152 @@
     GMMSTATS                GMMStats;
 } STAMUSERPERVM;
+#ifdef IN_RING3
 AssertCompileMemberAlignment(STAMUSERPERVM, GMMStats, 8);
+#endif
 
 /** Pointer to the STAM data kept in the UVM. */