Changeset 93684 in vbox for trunk/src/VBox/Runtime

Timestamp:

Feb 11, 2022 1:23:40 AM (3 years ago)

Author:

vboxsync

Message:

IPRT/hardavl: Fixed the removal bug. Extended testcase and sanity checks. bugref:10093

File:

• trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp (modified) (13 diffs)

trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp

@@ -39 +39 @@
 #include <iprt/string.h>
 #include <iprt/test.h>
+#include <iprt/time.h>
 
 
@@ -1046 +1047 @@
 
 
+static DECLCALLBACK(int) hardAvlRangeTreeGCPhysEnumCallbackCount(TESTNODE *pNode, void *pvUser)
+{
+    *(uint32_t *)pvUser += 1;
+    RT_NOREF(pNode);
+    return VINF_SUCCESS;
+}
+
+
 static uint32_t PickClearBit(uint64_t *pbm, uint32_t cItems)
 {
-    uint32_t idx = RTRandU32Ex(0, cItems - 1);
+    uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
     if (ASMBitTest(pbm, idx) == 0)
         return idx;
@@ -1076 +1085 @@
 }
 
-#if 0
+
 static uint32_t PickSetBit(uint64_t *pbm, uint32_t cItems)
 {
-    uint32_t idx = RTRandU32Ex(0, cItems - 1);
+    uint32_t idx = RTRandAdvU32Ex(g_hRand, 0, cItems - 1);
     if (ASMBitTest(pbm, idx) == 1)
         return idx;
@@ -1103 +1112 @@
 {
     uint32_t idx = PickSetBit(pbm, cItems);
-    RTTESTI_CHECK(ASMBitTestAndSet(pbm, idx) == true);
+    RTTESTI_CHECK(ASMBitTestAndClear(pbm, idx) == true);
     return idx;
 }
-#endif
-
-
-/** @return meaningless, just for return RTTestIFailed(); */
+
+
+/**
+ * @return meaningless value, just for shortening 'return RTTestIFailed();'.
+ */
 int hardAvlRangeTreeGCPhys(RTTEST hTest)
 {
@@ -1123 +1133 @@
 
     /* Initialize the allocator with a decent slab of memory. */
-    const uint32_t cItems = 16384;
+    const uint32_t cItems = 8192;
     void *pvItems;
     RTTESTI_CHECK_RC_RET(RTTestGuardedAlloc(hTest, sizeof(MYTESTNODE) * cItems,
@@ -1136 +1146 @@
      */
     /* insert */
-    for (unsigned i = 0; i < 65536; i += 4)
+    for (unsigned i = 0; i < cItems * 4; i += 4)
     {
         MYTESTNODE *pNode = Allocator.allocateNode();
@@ -1187 +1197 @@
 
     /* do gets. */
-    for (unsigned i = 0; i < 65536; i += 4)
+    for (unsigned i = 0; i < cItems * 4; i += 4)
     {
         MYTESTNODE *pNode;
@@ -1206 +1216 @@
 
     /* negative get */
-    for (unsigned i = 65536; i < 65536 * 2; i += 1)
+    for (unsigned i = cItems * 4; i < cItems * 4 * 2; i += 1)
     {
         MYTESTNODE *pNode = (MYTESTNODE *)(uintptr_t)i;
@@ -1223 +1233 @@
 
     /* remove */
-    for (unsigned i = 0, j = 0; i < 65536; i += 4, j += 3)
+    for (unsigned i = 0, j = 0; i < cItems * 4; i += 4, j += 3)
     {
         MYTESTNODE *pNode;
@@ -1250 +1260 @@
     uint64_t uSeed = RTRandU64();
     RTRandAdvSeed(g_hRand, uSeed);
-    RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed: %#RX64\n", uSeed);
+    RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #1: %#RX64\n", uSeed);
 
     RTGCPHYS const   cbStep     = RTGCPHYS_MAX / cItems + 1;
@@ -1274 +1284 @@
         if (rc != VINF_SUCCESS || pNode2 != pNode)
             return RTTestIFailed("lookup after random insert %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
-    }
-
-#if 0 /** @todo this doesn't work quit right yet */
+
+        uint32_t cCount = 0;
+        rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("enum after random insert %#x: %Rrc idx=%#x", i, rc, idx);
+        else if (cCount != i + 1)
+            RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, i + 1);
+    }
+
     /* remove all in random order. */
     for (unsigned i = 0; i < cItems; i++)
@@ -1286 +1302 @@
         if (rc != VINF_SUCCESS)
             RTTestIFailed("random remove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
-                          rc, idx, idx * cbStep, idx * cbStep + cbStep - 1);
-        else if (   pNode->Key     != idx * cbStep
+                          rc, i, idx, idx * cbStep, idx * cbStep + cbStep - 1);
+        else
+        {
+            if (   pNode->Key     != idx * cbStep
                  || pNode->KeyLast != idx * cbStep + cbStep - 1)
-            RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (i=%#x, idx=%#x)",
-                          pNode->Key, pNode->KeyLast, idx * cbStep, idx * cbStep + cbStep - 1, i, idx);
-        else
-        {
-            MYTESTNODE *pNode2 = (MYTESTNODE *)(intptr_t)i;
-            rc = Tree.lookup(&Allocator, idx * cbStep, &pNode2);
-            if (rc != VERR_NOT_FOUND)
-                RTTestIFailed("lookup after random removal %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
+                RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (i=%#x, idx=%#x)",
+                              pNode->Key, pNode->KeyLast, idx * cbStep, idx * cbStep + cbStep - 1, i, idx);
+            else
+            {
+                MYTESTNODE *pNode2 = (MYTESTNODE *)(intptr_t)i;
+                rc = Tree.lookup(&Allocator, idx * cbStep, &pNode2);
+                if (rc != VERR_NOT_FOUND)
+                    RTTestIFailed("lookup after random removal %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
+
+                uint32_t cCount = 0;
+                rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
+                if (rc != VINF_SUCCESS)
+                    RTTestIFailed("enum after random removal %#x: %Rrc idx=%#x", i, rc, idx);
+                else if (cCount != cItems - i - 1)
+                    RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cItems - i - 1);
+            }
 
             rc = Allocator.freeNode(pNode);
@@ -1303 +1329 @@
         }
     }
-#endif
-
-    /** @todo Add more random stuff here where we pick the operation to perform
-     *        using random as well and just do large number of these iterations. */
+
+    /*
+     * Randomized operation.
+     */
+    uSeed = RTRandU64();
+    RTRandAdvSeed(g_hRand, uSeed);
+    RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #2: %#RX64\n", uSeed);
+    uint32_t       cInserted    = 0;
+    uint64_t       cItemsEnumed = 0;
+    bool           fAdding      = true;
+    uint64_t const nsStart      = RTTimeNanoTS();
+    unsigned       i;
+    for (i = 0; i < _64M; i++)
+    {
+        /* The operation. */
+        bool fDelete;
+        if (cInserted == cItems)
+        {
+            fDelete = true;
+            fAdding = false;
+        }
+        else if (cInserted == 0)
+        {
+            fDelete = false;
+            fAdding = true;
+        }
+        else
+            fDelete = fAdding ? RTRandU32Ex(0, 3) == 1 : RTRandU32Ex(0, 3) != 0;
+
+        if (!fDelete)
+        {
+            uint32_t const idxInsert = PickClearBitAndSetIt(pbmPresent, cItems);
+
+            MYTESTNODE *pNode = Allocator.allocateNode();
+            if (!pNode)
+                return RTTestIFailed("out of nodes: cInserted=%#x cItems=%#x i=%#x", cInserted, cItems, i);
+            pNode->Key     = idxInsert * cbStep;
+            pNode->KeyLast = pNode->Key + cbStep - 1;
+            int rc = Tree.insert(&Allocator, pNode);
+            if (rc == VINF_SUCCESS)
+                cInserted += 1;
+            else
+            {
+                RTTestIFailed("random insert failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
+                              rc, pNode->Key, pNode->KeyLast, cInserted, cItems, i);
+                Allocator.freeNode(pNode);
+            }
+        }
+        else
+        {
+            uint32_t const idxDelete = PickSetBitAndClearIt(pbmPresent, cItems);
+
+            MYTESTNODE *pNode = (MYTESTNODE *)(intptr_t)idxDelete;
+            int rc = Tree.remove(&Allocator, idxDelete * cbStep, &pNode);
+            if (rc == VINF_SUCCESS)
+            {
+                if (   pNode->Key     != idxDelete * cbStep
+                    || pNode->KeyLast != idxDelete * cbStep + cbStep - 1)
+                    RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (cInserted=%#x cItems=%#x i=%#x)",
+                                  pNode->Key, pNode->KeyLast, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1,
+                                  cInserted, cItems, i);
+
+                cInserted -= 1;
+                rc = Allocator.freeNode(pNode);
+                if (rc != VINF_SUCCESS)
+                    RTTestIFailed("free after random removal failed: %Rrc - pNode=%p i=%#x", rc, pNode, i);
+            }
+            else
+                RTTestIFailed("random remove failed: %Rrc - %RGp ... %RGp cInserted=%#x cItems=%#x i=%#x",
+                              rc, idxDelete * cbStep, idxDelete * cbStep + cbStep - 1, cInserted, cItems, i);
+        }
+
+        /* Count the tree items.  This will make sure the tree is balanced in strict builds. */
+        uint32_t cCount = 0;
+        int rc = Tree.doWithAllFromLeft(&Allocator, hardAvlRangeTreeGCPhysEnumCallbackCount, &cCount);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("enum after random %s failed: %Rrc - i=%#x", fDelete ? "removal" : "insert", rc, i);
+        else if (cCount != cInserted)
+            RTTestIFailed("wrong count after random %s: %#x, expected %#x - i=%#x",
+                          cCount, cInserted, fDelete ? "removal" : "insert", i);
+        cItemsEnumed += cCount;
+
+        /* Check for timeout. */
+        if (   (i & 0xffff) == 0
+            && RTTimeNanoTS() - nsStart >= RT_NS_15SEC)
+            break;
+    }
+    RTTestIPrintf(RTTESTLVL_ALWAYS, "Performed %'u operations and enumerated %'RU64 nodes in %'RU64 ns\n",
+                  i, cItemsEnumed, RTTimeNanoTS() - nsStart);
 
     return 0;