VirtualBox

source: vbox/trunk/src/VBox/Debugger/DBGCNtCommands.cpp@ 105538

Last change on this file since 105538 was 105538, checked in by vboxsync, 10 months ago

VBoxDbg: Added a ntrbtree command for dumping the red-black trees in Windows 8 and later. [fixes] bugref:10727
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.7 KB
Line 
1/* $Id: DBGCNtCommands.cpp 105538 2024-07-30 07:00:02Z vboxsync $ */
2/** @file
3 * DBGC - Debugger Console, Windows NT Related Commands.
4 */
5
6/*
7 * Copyright (C) 2024 Oracle and/or its affiliates.
8 *
9 * This file is part of VirtualBox base platform packages, as
10 * available from https://www.215389.xyz.
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation, in version 3 of the
15 * License.
16 *
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, see <https://www.gnu.org/licenses>.
24 *
25 * SPDX-License-Identifier: GPL-3.0-only
26 */
27
28
29/*********************************************************************************************************************************
30* Header Files *
31*********************************************************************************************************************************/
32#define LOG_GROUP LOG_GROUP_DBGC
33#include <VBox/dbg.h>
34#include <VBox/vmm/dbgf.h>
35#include <VBox/param.h>
36#include <iprt/errcore.h>
37#include <VBox/log.h>
38
39#include <iprt/assert.h>
40#include <iprt/ctype.h>
41#include <iprt/dir.h>
42#include <iprt/env.h>
43#include <iprt/ldr.h>
44#include <iprt/mem.h>
45#include <iprt/path.h>
46#include <iprt/string.h>
47
48#include "DBGCInternal.h"
49
50
51/*********************************************************************************************************************************
52* Structures and Typedefs *
53*********************************************************************************************************************************/
54/**
55 * 64-bit _RTL_BALANCED_NODE
56 */
57typedef struct NT_RTL_BALANCED_NODE64
58{
59 uint64_t Left;
60 uint64_t Right;
61
62 /**
63 * Pointer to the parent node and flags in the least significant bits.
64 *
65 * RB: 1 bit: Set if RED, clear if BLACK.
66 * AVL: 2 bits: Balance something.
67 */
68 uint64_t ParentAndFlags;
69} NT_RTL_BALANCED_NODE64;
70
71/**
72 * 64-bit _RTL_RB_TREE
73 */
74typedef struct NT_RTL_RB_TREE64
75{
76 uint64_t Root; /**< Address of the root node (NT_RTL_BALANCED_NODE64). */
77 uint64_t Min; /**< Address of the left most node (NT_RTL_BALANCED_NODE64). */
78} NT_RTL_RB_TREE64;
79
80
81/** Initializes a DBGC variable with a GC flat pointer. */
82DECLINLINE(PDBGCVAR) dbgCmdNtVarFromGCFlatPtr(PDBGCVAR pVar, RTGCPTR GCFlat)
83{
84 pVar->enmType = DBGCVAR_TYPE_GC_FLAT;
85 pVar->u.GCFlat = GCFlat;
86
87 pVar->enmRangeType = DBGCVAR_RANGE_NONE;
88 pVar->u64Range = 0;
89 pVar->pDesc = NULL;
90 pVar->pNext = NULL;
91 return pVar;
92}
93
94
95/** Worker for dbgcCmdNtRbTree. */
96template<typename TreeType = NT_RTL_RB_TREE64, typename NodeType = NT_RTL_BALANCED_NODE64, typename PtrType = uint64_t>
97int dbgCmdNtRbTreeWorker(PCDBGCCMD pCmd, PDBGCCMDHLP pCmdHlp, PCDBGCVAR pRootAddr)
98{
99 PtrType const fAlignMask = ~(PtrType)(sizeof(PtrType) - 1);
100 PtrType const fAlignInfoMask = (PtrType)(sizeof(PtrType) - 1);
101
102 /*
103 * Read the root structure.
104 */
105 TreeType Root;
106 int rc = DBGCCmdHlpMemRead(pCmdHlp, &Root, sizeof(Root), pRootAddr, NULL /*cbRead*/);
107 if (RT_FAILURE(rc))
108 return DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read tree structure");
109
110 DBGCCmdHlpPrintf(pCmdHlp,
111 sizeof(PtrType) == sizeof(uint64_t)
112 ? "RB Root %DV: Root=%#016RX64 Min=%#016RX64\n"
113 : "RB Root %DV: Root=%#010RX32 Min=%#010RX32\n",
114 pRootAddr, Root.Root, Root.Min);
115 if ((Root.Root & fAlignMask) == 0 || (Root.Min & fAlignMask) == 0)
116 {
117 if ((Root.Root & fAlignMask) == 0 && (Root.Min & fAlignMask) == 0)
118 DBGCCmdHlpPrintf(pCmdHlp, "RB Root %DV: Empty\n", pRootAddr);
119 else
120 DBGCCmdHlpPrintf(pCmdHlp, "RB Root %DV: Bogus root state!\n", pRootAddr);
121 return VINF_SUCCESS;
122 }
123
124 /*
125 * To properly validate and avoid unnecessary memory reads, we use a stack
126 * track tree traversal progress. The stack consists of a copy of the node
127 * and a boolean indicating whether or not the node has be processed.
128 */
129 struct
130 {
131 NodeType Node; /**< Copy of the node. */
132 PtrType Ptr; /**< The node address. */
133 uint8_t bState; /**< 0 for going down left tree, 1 for the right, and 2 for done. */
134 uint8_t cBlacks; /**< Number of black nodes thus far, including this one. */
135 } aStack[28];
136 uint32_t cStackEntries = 0;
137
138 /*
139 * Push the root-node onto the stack.
140 */
141 PtrType Ptr = Root.Root & fAlignMask;
142 DBGCVAR Var;
143 rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[0].Node, sizeof(aStack[0].Node), dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
144 if (RT_FAILURE(rc))
145 return DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read the root node!");
146 aStack[0].Ptr = Ptr;
147 aStack[0].bState = 0;
148 aStack[0].cBlacks = 1;
149 if (aStack[0].Node.ParentAndFlags & fAlignMask)
150 return DBGCCmdHlpFail(pCmdHlp, pCmd, "Root->Parent != NULL: %#RX64", (uint64_t)aStack[0].Node.ParentAndFlags);
151 if (aStack[0].Node.ParentAndFlags & 1)
152 return DBGCCmdHlpFail(pCmdHlp, pCmd, "Root node is RED! Parent=%#RX64", (uint64_t)aStack[0].Node.ParentAndFlags);
153 cStackEntries++;
154
155 int rcRet = VINF_SUCCESS;
156 uint8_t cReqBlacks = 0; /**< Number of black nodes required in each path. Set when we reach the left most node. */
157 uint8_t cchMaxDepth = 32;
158 uint32_t idxNode = 0;
159 uint32_t cErrors = 0;
160 while (cStackEntries > 0)
161 {
162 uint32_t const idxCurEntry = cStackEntries - 1;
163 switch (aStack[idxCurEntry].bState)
164 {
165 case 0:
166 /*
167 * Descend into the left tree, if any.
168 */
169 if (aStack[idxCurEntry].Node.Left & fAlignInfoMask)
170 {
171 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Left pointer in node at %#RX64: %#RX64",
172 (uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry].Node.Left);
173 cErrors++;
174 }
175 Ptr = aStack[idxCurEntry].Node.Left & fAlignMask;
176 if (Ptr)
177 {
178 if (cStackEntries < RT_ELEMENTS(aStack))
179 {
180 rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[cStackEntries].Node, sizeof(aStack[cStackEntries].Node),
181 dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
182 if (RT_SUCCESS(rc))
183 {
184 if ((aStack[cStackEntries].Node.ParentAndFlags & fAlignMask) == aStack[idxCurEntry].Ptr)
185 {
186 aStack[idxCurEntry].bState = 1;
187
188 aStack[cStackEntries].Ptr = Ptr;
189 aStack[cStackEntries].cBlacks = aStack[idxCurEntry].cBlacks
190 + !(aStack[cStackEntries].Node.ParentAndFlags & 1);
191 aStack[cStackEntries].bState = 0;
192 cStackEntries++;
193 continue;
194 }
195 rc = DBGCCmdHlpFail(pCmdHlp, pCmd,
196 "Left node of %#RX64 at #%RX64 has an incorrect parent value: %#RX64 (Left=%#RX64, Right=%#RX64)",
197 (uint64_t)aStack[idxCurEntry].Ptr, Ptr, aStack[cStackEntries].Node.ParentAndFlags,
198 aStack[cStackEntries].Node.Left, aStack[cStackEntries].Node.Right);
199 }
200 else
201 rcRet = DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc,
202 "Failed to read the node left of %#RX64 at address %#RX64!",
203 (uint64_t)aStack[idxCurEntry].Ptr, Ptr);
204 }
205 else
206 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Stack overflow descending to the left!");
207 cErrors++;
208 }
209 else if (idxNode != 0)
210 {
211 uint8_t const cBlacksForCur = aStack[idxCurEntry].cBlacks + 1;
212 if (cBlacksForCur != cReqBlacks)
213 {
214 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Wrong black count to the left of %#RX64: %u, expected %u",
215 aStack[idxCurEntry].Ptr, cBlacksForCur, cReqBlacks);
216 cErrors++;
217 }
218 }
219 else
220 {
221 cReqBlacks = aStack[idxCurEntry].cBlacks + 1;
222 cchMaxDepth = RT_MIN(cReqBlacks * 4, RT_ELEMENTS(aStack) * 2 + 2);
223
224 if (Root.Min != aStack[idxCurEntry].Ptr)
225 {
226 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd,
227 "Bogus Min node in tree anchor! Left most node is %#RU64, expected %#RU64",
228 aStack[idxCurEntry].Ptr, Root.Min);
229 cErrors++;
230 }
231 }
232 RT_FALL_THRU();
233
234 case 1:
235 {
236 /*
237 * Process the current node.
238 */
239#if 1
240 char szStack[72];
241 uint32_t cchStack = cchMaxDepth - idxCurEntry * 2;
242 //memset(szStack, ' ', cchStack);
243 for (uint32_t volatile x = 0; x < cchStack; x++)
244 szStack[x] = ' ';
245
246 if (aStack[idxCurEntry].Node.Left & fAlignMask)
247 szStack[cchStack++] = aStack[idxCurEntry].Node.Right & fAlignMask ? '>' : '`';
248 else
249 szStack[cchStack++] = aStack[idxCurEntry].Node.Right & fAlignMask ? ',' : ' ';
250 szStack[cchStack++] = aStack[idxCurEntry].Node.ParentAndFlags & 1 ? 'r' : 'B';
251
252 uint32_t volatile offLast = cchStack;
253 if (idxCurEntry > 0)
254 {
255 uint32_t idxTmp = idxCurEntry - 1;
256 uint8_t bPrev = aStack[idxTmp].bState;
257 while (idxTmp-- > 0)
258 {
259 cchStack += 2;
260 if (aStack[idxTmp].bState != bPrev)
261 {
262 bPrev = aStack[idxTmp].bState;
263 while (offLast < cchStack)
264 szStack[offLast++] = ' ';
265 //memset(&szStack[offLast], ' ', cchStack - offLast);
266 szStack[cchStack] = '|';
267 offLast = cchStack + 1;
268 }
269 }
270 }
271 szStack[offLast] = '\0';
272
273 DBGCCmdHlpPrintf(pCmdHlp,
274 sizeof(PtrType) == sizeof(uint64_t)
275 ? "#%4u/%2u at %#018RX64: Left=%#018RX64 Right=%#018RX64 Parent=%#018RX64 %s %s\n"
276 : "#%4u/%2u at %#010RX32: Left=%#010RX32 Right=%#010RX32 Parent=%#010RX32 %s %s\n",
277 idxNode, cStackEntries, aStack[idxCurEntry].Ptr, aStack[idxCurEntry].Node.Left,
278 aStack[idxCurEntry].Node.Right, aStack[idxCurEntry].Node.ParentAndFlags & ~(PtrType)1,
279 aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "Red " : "Black", szStack);
280#else
281 DBGCCmdHlpPrintf(pCmdHlp,
282 sizeof(PtrType) == sizeof(uint64_t)
283 ? "#%4u/%2u at %#018RX64: Left=%#018RX64 Right=%#018RX64 Parent=%#018RX64 %s %*s%s\n"
284 : "#%4u/%2u at %#010RX32: Left=%#010RX32 Right=%#010RX32 Parent=%#010RX32 %s %*s%s\n",
285 idxNode, cStackEntries, aStack[idxCurEntry].Ptr, aStack[idxCurEntry].Node.Left,
286 aStack[idxCurEntry].Node.Right, aStack[idxCurEntry].Node.ParentAndFlags & ~(PtrType)1,
287 aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "Red " : "Black",
288 (cMaxDepth - idxCurEntry) * 2,
289 aStack[idxCurEntry].Node.Left & fAlignMask
290 ? (aStack[idxCurEntry].Node.Right & fAlignMask ? ">" : "`")
291 : aStack[idxCurEntry].Node.Right & fAlignMask ? "," : " ",
292 aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "r" : "B");
293#endif
294 idxNode++;
295
296 /* Check that there are no RED -> RED sequences. */
297 if ( (aStack[idxCurEntry].Node.ParentAndFlags & 1)
298 && idxCurEntry > 0
299 && (aStack[idxCurEntry - 1].Node.ParentAndFlags & 1))
300 {
301 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "RED child (%#RX64) with RED (%#RX64) parent!\n",
302 (uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry - 1].Ptr);
303 cErrors++;
304 }
305
306 /*
307 * Descend into the right tree, if present.
308 */
309 if (aStack[idxCurEntry].Node.Right & fAlignInfoMask)
310 {
311 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Right pointer in node at %#RX64: %#RX64",
312 (uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry].Node.Right);
313 cErrors++;
314 }
315 Ptr = aStack[idxCurEntry].Node.Right & fAlignMask;
316 if (Ptr)
317 {
318 if (cStackEntries < RT_ELEMENTS(aStack))
319 {
320 rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[cStackEntries].Node, sizeof(aStack[cStackEntries].Node),
321 dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
322 if (RT_SUCCESS(rc))
323 {
324 if ((aStack[cStackEntries].Node.ParentAndFlags & fAlignMask) == aStack[idxCurEntry].Ptr)
325 {
326 aStack[idxCurEntry].bState = 2;
327
328 aStack[cStackEntries].Ptr = Ptr;
329 aStack[cStackEntries].cBlacks = aStack[idxCurEntry].cBlacks
330 + !(aStack[cStackEntries].Node.ParentAndFlags & 1);
331 aStack[cStackEntries].bState = 0;
332 cStackEntries++;
333 continue;
334 }
335 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd,
336 "Right node of #%RX64 at #%RX64 has an incorrect parent value: %#RX64 (Left=%#RX64, Right=%#RX64)",
337 (uint64_t)aStack[idxCurEntry].Ptr, Ptr, aStack[cStackEntries].Node.ParentAndFlags,
338 aStack[cStackEntries].Node.Left, aStack[cStackEntries].Node.Right);
339 }
340 else
341 rcRet = DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read the node right of %#RX64 at address %#RX64!",
342 (uint64_t)aStack[idxCurEntry].Ptr, Ptr);
343 }
344 else
345 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Stack overflow descending to the right!");
346 cErrors++;
347 }
348 else
349 {
350 uint8_t const cBlacksForCur = aStack[idxCurEntry].cBlacks + 1;
351 if (cBlacksForCur != cReqBlacks)
352 {
353 rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Wrong black count to the right of %#RX64: %u, expected %u",
354 aStack[idxCurEntry].Ptr, cBlacksForCur, cReqBlacks);
355 cErrors++;
356 }
357 }
358 RT_FALL_THRU();
359 }
360
361 case 2:
362 /* We've returned from the right tree and should pop this entry now. */
363 cStackEntries--;
364 break;
365
366 default:
367 AssertFailedReturn(DBGCCmdHlpFail(pCmdHlp, pCmd, "Internal stack state error: [%u] = %u",
368 idxCurEntry, aStack[idxCurEntry].bState));
369 }
370
371 }
372
373 if (!cErrors)
374 DBGCCmdHlpPrintf(pCmdHlp, "No obvious errors\n");
375 else
376 DBGCCmdHlpPrintf(pCmdHlp, "%u tree errors\n", cErrors);
377 return rcRet;
378}
379
380/**
381 * @callback_method_impl{FNDBGCCMD, The 'ntrbtree' command.}
382 */
383DECLCALLBACK(int) dbgcCmdNtRbTree(PCDBGCCMD pCmd, PDBGCCMDHLP pCmdHlp, PUVM pUVM, PCDBGCVAR paArgs, unsigned cArgs)
384{
385 /* Check parsing. */
386 DBGC_CMDHLP_ASSERT_PARSER_RET(pCmdHlp, pCmd, 0, cArgs == 1);
387 DBGC_CMDHLP_ASSERT_PARSER_RET(pCmdHlp, pCmd, 0, DBGCVAR_ISGCPOINTER(paArgs[0].enmType));
388 RT_NOREF(pUVM);
389
390 /* ASSUME 64-bit for now. */
391 return dbgCmdNtRbTreeWorker<NT_RTL_RB_TREE64, NT_RTL_BALANCED_NODE64, uint64_t>(pCmd, pCmdHlp, &paArgs[0]);
392}
393
Note: See TracBrowser for help on using the repository browser.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette