DBGCNtCommands.cpp@ 107044

Last change on this file since 107044 was 105580, checked in by vboxsync, 4 months ago
VBoxDbg: ntrbtree nit. bugref:10727
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.3 KB

Line
1	/* $Id: DBGCNtCommands.cpp 105580 2024-08-02 21:18:57Z 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.virtualbox.org.
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	*/
57	typedef 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	*/
74	typedef struct NT_RTL_RB_TREE64
75	{
76	uint64_t Root; /*< Address of the root node (NT_RTL_BALANCED_NODE64). /
77	/** The address of the left-most node (NT_RTL_BALANCED_NODE64).
78	* Bit 0 is used to indicate 'Encoded', meaning that Left and Right are
79	* XORed with the node address and Min is XORed with the address of this
80	* structure. */
81	uint64_t Min;
82	} NT_RTL_RB_TREE64;
83
84
85	/** Initializes a DBGC variable with a GC flat pointer. */
86	DECLINLINE(PDBGCVAR) dbgCmdNtVarFromGCFlatPtr(PDBGCVAR pVar, RTGCPTR GCFlat)
87	{
88	pVar->enmType = DBGCVAR_TYPE_GC_FLAT;
89	pVar->u.GCFlat = GCFlat;
90
91	pVar->enmRangeType = DBGCVAR_RANGE_NONE;
92	pVar->u64Range = 0;
93	pVar->pDesc = NULL;
94	pVar->pNext = NULL;
95	return pVar;
96	}
97
98
99	/** Worker for dbgcCmdNtRbTree. */
100	template<typename TreeType = NT_RTL_RB_TREE64, typename NodeType = NT_RTL_BALANCED_NODE64, typename PtrType = uint64_t>
101	int dbgCmdNtRbTreeWorker(PCDBGCCMD pCmd, PDBGCCMDHLP pCmdHlp, PCDBGCVAR pRootAddr)
102	{
103	int rcRet = VINF_SUCCESS;
104	uint32_t cErrors = 0;
105	PtrType const fAlignMask = ~(PtrType)(sizeof(PtrType) - 1);
106	PtrType const fAlignInfoMask = (PtrType)(sizeof(PtrType) - 1);
107
108	/*
109	* Read the root structure.
110	*/
111	TreeType Root;
112	int rc = DBGCCmdHlpMemRead(pCmdHlp, &Root, sizeof(Root), pRootAddr, NULL /cbRead/);
113	if (RT_FAILURE(rc))
114	return DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read tree structure");
115
116	DBGCCmdHlpPrintf(pCmdHlp,
117	sizeof(PtrType) == sizeof(uint64_t)
118	? "RB Root %DV: Root=%#016RX64 Min=%#016RX64%s\n"
119	: "RB Root %DV: Root=%#010RX32 Min=%#010RX32%s\n",
120	pRootAddr, Root.Root, Root.Min, Root.Min & 1 ? " Encoded=1" : "");
121	if ((Root.Root & fAlignMask) == 0 \|\| (Root.Min & fAlignMask) == 0)
122	{
123	if ((Root.Root & fAlignMask) == 0 && (Root.Min & fAlignMask) == 0)
124	DBGCCmdHlpPrintf(pCmdHlp, "RB Root %DV: Empty\n", pRootAddr);
125	else
126	DBGCCmdHlpPrintf(pCmdHlp, "RB Root %DV: Bogus root state!\n", pRootAddr);
127	return VINF_SUCCESS;
128	}
129	if (Root.Root & fAlignInfoMask)
130	{
131	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Root pointer: %#RX64", Root.Root);
132	cErrors++;
133	}
134	if ((Root.Min & fAlignInfoMask) > 1)
135	{
136	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Min pointer: %#RX64 (bits 1+ should be zero)", Root.Min);
137	cErrors++;
138	}
139
140	/*
141	* To properly validate and avoid unnecessary memory reads, we use a stack
142	* track tree traversal progress. The stack consists of a copy of the node
143	* and a boolean indicating whether or not the node has be processed.
144	*/
145	struct
146	{
147	NodeType Node; /*< Copy of the node. /
148	PtrType Ptr; /*< The node address. /
149	uint8_t bState; /*< 0 for going down left tree, 1 for the right, and 2 for done. /
150	uint8_t cBlacks; /*< Number of black nodes thus far, including this one. /
151	} aStack[28];
152	uint32_t cStackEntries = 0;
153
154	/*
155	* Push the root-node onto the stack.
156	*/
157	PtrType Ptr = Root.Root & fAlignMask;
158	DBGCVAR Var;
159	rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[0].Node, sizeof(aStack[0].Node), dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
160	if (RT_FAILURE(rc))
161	return DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read the root node!");
162	aStack[0].Ptr = Ptr;
163	aStack[0].bState = 0;
164	aStack[0].cBlacks = 1;
165	if (aStack[0].Node.ParentAndFlags & fAlignMask)
166	return DBGCCmdHlpFail(pCmdHlp, pCmd, "Root->Parent != NULL: %#RX64", (uint64_t)aStack[0].Node.ParentAndFlags);
167	if (aStack[0].Node.ParentAndFlags & 1)
168	return DBGCCmdHlpFail(pCmdHlp, pCmd, "Root node is RED! Parent=%#RX64", (uint64_t)aStack[0].Node.ParentAndFlags);
169	cStackEntries++;
170
171	uint8_t cReqBlacks = 0; /*< Number of black nodes required in each path. Set when we reach the left most node. /
172	uint8_t cchMaxDepth = 32;
173	uint32_t idxNode = 0;
174	while (cStackEntries > 0)
175	{
176	uint32_t const idxCurEntry = cStackEntries - 1;
177	switch (aStack[idxCurEntry].bState)
178	{
179	case 0:
180	/*
181	* Descend into the left tree, if any.
182	*/
183	if (aStack[idxCurEntry].Node.Left & fAlignInfoMask)
184	{
185	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Left pointer in node at %#RX64: %#RX64",
186	(uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry].Node.Left);
187	cErrors++;
188	}
189	Ptr = aStack[idxCurEntry].Node.Left & fAlignMask;
190	if (Ptr)
191	{
192	if (cStackEntries < RT_ELEMENTS(aStack))
193	{
194	rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[cStackEntries].Node, sizeof(aStack[cStackEntries].Node),
195	dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
196	if (RT_SUCCESS(rc))
197	{
198	if ((aStack[cStackEntries].Node.ParentAndFlags & fAlignMask) == aStack[idxCurEntry].Ptr)
199	{
200	aStack[idxCurEntry].bState = 1;
201
202	aStack[cStackEntries].Ptr = Ptr;
203	aStack[cStackEntries].cBlacks = aStack[idxCurEntry].cBlacks
204	+ !(aStack[cStackEntries].Node.ParentAndFlags & 1);
205	aStack[cStackEntries].bState = 0;
206	cStackEntries++;
207	continue;
208	}
209	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd,
210	"Left node of %#RX64 at #%RX64 has an incorrect parent value: %#RX64 (Left=%#RX64, Right=%#RX64)",
211	(uint64_t)aStack[idxCurEntry].Ptr, Ptr, aStack[cStackEntries].Node.ParentAndFlags,
212	aStack[cStackEntries].Node.Left, aStack[cStackEntries].Node.Right);
213	}
214	else
215	rcRet = DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc,
216	"Failed to read the node left of %#RX64 at address %#RX64!",
217	(uint64_t)aStack[idxCurEntry].Ptr, Ptr);
218	}
219	else
220	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Stack overflow descending to the left!");
221	cErrors++;
222	}
223	else if (idxNode != 0)
224	{
225	uint8_t const cBlacksForCur = aStack[idxCurEntry].cBlacks + 1;
226	if (cBlacksForCur != cReqBlacks)
227	{
228	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Wrong black count to the left of %#RX64: %u, expected %u",
229	aStack[idxCurEntry].Ptr, cBlacksForCur, cReqBlacks);
230	cErrors++;
231	}
232	}
233	else
234	{
235	cReqBlacks = aStack[idxCurEntry].cBlacks + 1;
236	cchMaxDepth = RT_MIN(cReqBlacks * 4, RT_ELEMENTS(aStack) * 2 + 2);
237
238	if ((Root.Min & ~(PtrType)1) != aStack[idxCurEntry].Ptr)
239	{
240	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd,
241	"Bogus Min node in tree anchor! Left most node is %#RU64, expected %#RU64",
242	aStack[idxCurEntry].Ptr, Root.Min);
243	cErrors++;
244	}
245	}
246	RT_FALL_THRU();
247
248	case 1:
249	{
250	/*
251	* Process the current node.
252	*/
253	#if 1
254	char szStack[72];
255	uint32_t cchStack = cchMaxDepth - idxCurEntry * 2;
256	//memset(szStack, ' ', cchStack);
257	for (uint32_t volatile x = 0; x < cchStack; x++)
258	szStack[x] = ' ';
259
260	if (aStack[idxCurEntry].Node.Left & fAlignMask)
261	szStack[cchStack++] = aStack[idxCurEntry].Node.Right & fAlignMask ? '>' : '`';
262	else
263	szStack[cchStack++] = aStack[idxCurEntry].Node.Right & fAlignMask ? ',' : ' ';
264	szStack[cchStack++] = aStack[idxCurEntry].Node.ParentAndFlags & 1 ? 'r' : 'B';
265
266	uint32_t volatile offLast = cchStack;
267	if (idxCurEntry > 0)
268	{
269	uint32_t idxTmp = idxCurEntry - 1;
270	uint8_t bPrev = aStack[idxTmp].bState;
271	while (idxTmp-- > 0)
272	{
273	cchStack += 2;
274	if (aStack[idxTmp].bState != bPrev)
275	{
276	bPrev = aStack[idxTmp].bState;
277	while (offLast < cchStack)
278	szStack[offLast++] = ' ';
279	//memset(&szStack[offLast], ' ', cchStack - offLast);
280	szStack[cchStack] = '\|';
281	offLast = cchStack + 1;
282	}
283	}
284	}
285	szStack[offLast] = '\0';
286
287	DBGCCmdHlpPrintf(pCmdHlp,
288	sizeof(PtrType) == sizeof(uint64_t)
289	? "#%4u/%2u at %#018RX64: Left=%#018RX64 Right=%#018RX64 Parent=%#018RX64 %s %s\n"
290	: "#%4u/%2u at %#010RX32: Left=%#010RX32 Right=%#010RX32 Parent=%#010RX32 %s %s\n",
291	idxNode, cStackEntries, aStack[idxCurEntry].Ptr, aStack[idxCurEntry].Node.Left,
292	aStack[idxCurEntry].Node.Right, aStack[idxCurEntry].Node.ParentAndFlags & ~(PtrType)1,
293	aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "Red " : "Black", szStack);
294	#else
295	DBGCCmdHlpPrintf(pCmdHlp,
296	sizeof(PtrType) == sizeof(uint64_t)
297	? "#%4u/%2u at %#018RX64: Left=%#018RX64 Right=%#018RX64 Parent=%#018RX64 %s %*s%s\n"
298	: "#%4u/%2u at %#010RX32: Left=%#010RX32 Right=%#010RX32 Parent=%#010RX32 %s %*s%s\n",
299	idxNode, cStackEntries, aStack[idxCurEntry].Ptr, aStack[idxCurEntry].Node.Left,
300	aStack[idxCurEntry].Node.Right, aStack[idxCurEntry].Node.ParentAndFlags & ~(PtrType)1,
301	aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "Red " : "Black",
302	(cMaxDepth - idxCurEntry) * 2,
303	aStack[idxCurEntry].Node.Left & fAlignMask
304	? (aStack[idxCurEntry].Node.Right & fAlignMask ? ">" : "`")
305	: aStack[idxCurEntry].Node.Right & fAlignMask ? "," : " ",
306	aStack[idxCurEntry].Node.ParentAndFlags & 1 ? "r" : "B");
307	#endif
308	idxNode++;
309
310	/* Check that there are no RED -> RED sequences. */
311	if ( (aStack[idxCurEntry].Node.ParentAndFlags & 1)
312	&& idxCurEntry > 0
313	&& (aStack[idxCurEntry - 1].Node.ParentAndFlags & 1))
314	{
315	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "RED child (%#RX64) with RED (%#RX64) parent!\n",
316	(uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry - 1].Ptr);
317	cErrors++;
318	}
319
320	/*
321	* Descend into the right tree, if present.
322	*/
323	if (aStack[idxCurEntry].Node.Right & fAlignInfoMask)
324	{
325	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Misaligned Right pointer in node at %#RX64: %#RX64",
326	(uint64_t)aStack[idxCurEntry].Ptr, (uint64_t)aStack[idxCurEntry].Node.Right);
327	cErrors++;
328	}
329	Ptr = aStack[idxCurEntry].Node.Right & fAlignMask;
330	if (Ptr)
331	{
332	if (cStackEntries < RT_ELEMENTS(aStack))
333	{
334	rc = DBGCCmdHlpMemRead(pCmdHlp, &aStack[cStackEntries].Node, sizeof(aStack[cStackEntries].Node),
335	dbgCmdNtVarFromGCFlatPtr(&Var, Ptr), NULL);
336	if (RT_SUCCESS(rc))
337	{
338	if ((aStack[cStackEntries].Node.ParentAndFlags & fAlignMask) == aStack[idxCurEntry].Ptr)
339	{
340	aStack[idxCurEntry].bState = 2;
341
342	aStack[cStackEntries].Ptr = Ptr;
343	aStack[cStackEntries].cBlacks = aStack[idxCurEntry].cBlacks
344	+ !(aStack[cStackEntries].Node.ParentAndFlags & 1);
345	aStack[cStackEntries].bState = 0;
346	cStackEntries++;
347	continue;
348	}
349	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd,
350	"Right node of #%RX64 at #%RX64 has an incorrect parent value: %#RX64 (Left=%#RX64, Right=%#RX64)",
351	(uint64_t)aStack[idxCurEntry].Ptr, Ptr, aStack[cStackEntries].Node.ParentAndFlags,
352	aStack[cStackEntries].Node.Left, aStack[cStackEntries].Node.Right);
353	}
354	else
355	rcRet = DBGCCmdHlpFailRc(pCmdHlp, pCmd, rc, "Failed to read the node right of %#RX64 at address %#RX64!",
356	(uint64_t)aStack[idxCurEntry].Ptr, Ptr);
357	}
358	else
359	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Stack overflow descending to the right!");
360	cErrors++;
361	}
362	else
363	{
364	uint8_t const cBlacksForCur = aStack[idxCurEntry].cBlacks + 1;
365	if (cBlacksForCur != cReqBlacks)
366	{
367	rcRet = DBGCCmdHlpFail(pCmdHlp, pCmd, "Wrong black count to the right of %#RX64: %u, expected %u",
368	aStack[idxCurEntry].Ptr, cBlacksForCur, cReqBlacks);
369	cErrors++;
370	}
371	}
372	RT_FALL_THRU();
373	}
374
375	case 2:
376	/* We've returned from the right tree and should pop this entry now. */
377	cStackEntries--;
378	break;
379
380	default:
381	AssertFailedReturn(DBGCCmdHlpFail(pCmdHlp, pCmd, "Internal stack state error: [%u] = %u",
382	idxCurEntry, aStack[idxCurEntry].bState));
383	}
384
385	}
386
387	if (!cErrors)
388	DBGCCmdHlpPrintf(pCmdHlp, "No obvious errors\n");
389	else
390	DBGCCmdHlpPrintf(pCmdHlp, "%u tree errors\n", cErrors);
391	return rcRet;
392	}
393
394	/**
395	* @callback_method_impl{FNDBGCCMD, The 'ntrbtree' command.}
396	*/
397	DECLCALLBACK(int) dbgcCmdNtRbTree(PCDBGCCMD pCmd, PDBGCCMDHLP pCmdHlp, PUVM pUVM, PCDBGCVAR paArgs, unsigned cArgs)
398	{
399	/* Check parsing. */
400	DBGC_CMDHLP_ASSERT_PARSER_RET(pCmdHlp, pCmd, 0, cArgs == 1);
401	DBGC_CMDHLP_ASSERT_PARSER_RET(pCmdHlp, pCmd, 0, DBGCVAR_ISGCPOINTER(paArgs[0].enmType));
402	RT_NOREF(pUVM);
403
404	/* ASSUME 64-bit for now. */
405	return dbgCmdNtRbTreeWorker<NT_RTL_RB_TREE64, NT_RTL_BALANCED_NODE64, uint64_t>(pCmd, pCmdHlp, &paArgs[0]);
406	}
407

Note: See TracBrowser for help on using the repository browser.

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

Download in other formats: