At 2012-5-23 22:06, Dave Anderson wrote:
----- Original Message -----
At 2012-5-22 23:15, Dave Anderson wrote:
Doing it that way really confuses two different "offset" issues that are associated
with this command:
(1) the offset of an rb_root or radix_tree_node within a containing
data structure, and
(2) the offset of an rb_node within a containing data structure.
And in both cases, forget trying to implement the "the -o is not necessary" and
"the -o is only necessary..." optimizations, because it would be almost impossible
to do.
Hello Dave,
I will list all the situations I was concerning.
First red-black tree:
1. rb_node is embedded in a structure. Address is the address of the
structure, and -o shows the offset of rb_node to the structure.
2. same as 1., but the address is the address of rb_node when using -N
in command line.
rb_root was not concering. I will recall the reason. I can get the root
node from rb_root. And then the offspring of the root node. Then I still
need a offset that shows the offset of the offspring node to its related
structure to get the structure's information.
Then radix tree:
3. radix_tree_root's address is specified.
4. radix_tree_node's address is specified.
According to your reply, "-r offset" indicates rb_root and radix_tree_root,
Correct, but only if the rb_root or radix_tree_root are embedded in a
data structure, and the address argument points to the data stucture.
and "-n offset" indicates rb_node and radix_tree_node.
No -- the "-n offset" would only applicable to rb_nodes.
radix_tree_node structures data are standalone entities that are allocated
from the "radix_tree_node" slab cache, correct? When would a radix_tree_node
ever be embedded in a containing data structure?
And if I use "-r offset", then I need another option to show the offset
of rb_node. And when using "-n offset" together with an address, which
can only be one of rb_node's address and address of the structure
rb_node embedded in, I may need another option to indicate the address's
type.
The address is either that of an rb_root or radix_tree_root, or the
address of the containing data structure, in which case it would
require the "-r offset" option.
So I think "tree -t type -r offset -n offset -m addr..." is a good
choice. "-r offset" indicates the rb_root or radix_tree_root's offset,
and "-n offset" indicates the rb_node or radix_tree_node's offset.
Again, what is a "radix_tree_node offset"?
only using "-n offset" indicates the addr is related to rb_node or
radix_tree_node, but if "-r offset" is also specified, the addr is
related to rb_root or radix_tree_root. When "-m" is specified, the addr
is the address of the root(when specified "-r offset") or the node. If
"-m" is not specified, the addr is the address of the structure that
containing the root(when specified "-r offset") or the node.
Do you think it's OK?
No, that confuses the hell out me...
I really don't understand the need for the additional "-m" option?
To me it's simple -- but I may be missing something. The address argument
can be either:
(1) A pointer to an rb_root or radix_tree_root.
The "-r offset" is not required.
(2) A pointer to a data structure containing an rb_root or radix_tree_root.
The "-r offset" option is required if the member offset is non-zero.
That being the case, this should work:
red-black tree: tree -t type [-r offset] [-n offset] address
radix tree: tree -t type [-r offset] address
In the case of a red-black tree, it seems that you are also trying to
support the bypassing of the rb_root entirely, and point to an rb_node
directly? That would seem to be an odd-ball case, because the list
would be truncated if you don't point to the topmost rb_node. Is that
what you have in mind? If so, I suppose that you could also have a
additional "-N" option or something like that to signal that the address
argument is a pointer to an rb_node (and not applicable to radix trees).
I still add "-N" option to make it possible to start from node.
Dave
--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/crash-utility
--
--
Regards
Qiao Nuohan
>From 5f58fdf0397f1d3a5bbc939be4546a81be362a59 Mon Sep 17 00:00:00 2001
From: qiaonuohan <qiaonuohan@xxxxxxxxxxxxxx>
Date: Fri, 25 May 2012 02:36:23 +0800
Subject: [PATCH] add a new command tree
---
defs.h | 18 +++
global_data.c | 1 +
help.c | 105 ++++++++++++++++
tools.c | 374 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 498 insertions(+), 0 deletions(-)
diff --git a/defs.h b/defs.h
index 77a623d..e7a77d4 100755
--- a/defs.h
+++ b/defs.h
@@ -2075,6 +2075,20 @@ struct list_data { /* generic structure used by do_list() to walk */
#define RETURN_ON_DUPLICATE (VERBOSE << 5)
#define RETURN_ON_LIST_ERROR (VERBOSE << 6)
+struct tree_data {
+ ulong flags;
+ ulong start;
+ long member_offset; // indicate the offset of the memberi(tree node)
+ char **structname;
+ int structname_args;
+};
+
+#define TREE_ROOT_OFFSET_ENTERED (VERBOSE << 1)
+#define TREE_OFFSET_ENTERED (VERBOSE << 2)
+#define TREE_START_ENTERED (VERBOSE << 3)
+#define TREE_NODE_POINTER (VERBOSE << 4)
+#define TREE_POSITION_DISPLAY (VERBOSE << 5)
+
#define ALIAS_RUNTIME (1)
#define ALIAS_RCLOCAL (2)
#define ALIAS_RCHOME (3)
@@ -3654,6 +3668,7 @@ void cmd_ascii(void); /* tools.c */
void cmd_set(void); /* tools.c */
void cmd_eval(void); /* tools.c */
void cmd_list(void); /* tools.c */
+void cmd_tree(void); /* tools.c */
void cmd_template(void); /* tools.c */
void cmd_alias(void); /* cmdline.c */
void cmd_repeat(void); /* cmdline.c */
@@ -3829,6 +3844,8 @@ char *shift_string_right(char *, int);
int bracketed(char *, char *, int);
void backspace(int);
int do_list(struct list_data *);
+void do_rdtree(struct tree_data *);
+void do_rbtree(struct tree_data *);
int retrieve_list(ulong *, int);
long power(long, int);
long long ll_power(long long, long long);
@@ -4145,6 +4162,7 @@ extern char *help_help[];
extern char *help_irq[];
extern char *help_kmem[];
extern char *help__list[];
+extern char *help_tree[];
extern char *help_log[];
extern char *help_mach[];
extern char *help_mod[];
diff --git a/global_data.c b/global_data.c
index 98a5a79..e2e60de 100755
--- a/global_data.c
+++ b/global_data.c
@@ -99,6 +99,7 @@ struct command_table_entry linux_command_table[] = {
{"ptob", cmd_ptob, help_ptob, 0},
{"ptov", cmd_ptov, help_ptov, 0},
{"q", cmd_quit, help_quit, 0},
+ {"tree", cmd_tree, help_tree, 0},
{"rd", cmd_rd, help_rd, 0},
{"repeat", cmd_repeat, help_repeat, 0},
{"runq", cmd_runq, help_runq, REFRESH_TASK_TABLE},
diff --git a/help.c b/help.c
index 8ce8247..1b6568c 100755
--- a/help.c
+++ b/help.c
@@ -4445,6 +4445,111 @@ char *help__list[] = {
NULL
};
+char *help_tree[] = {
+"tree",
+"display tree",
+"-t [radix|radixtree] [-r offset] [-s struct[.member[,member]]] [-p] [-N] start\n"
+"-t [rb|rbtree] [-r offset] [-o offset] [-s struct[.member[,member]]] [-p] [-N] start",
+" This command dumps the contents of radix tree or red-black tree.",
+" ",
+" The arguments are as follows:\n",
+" -t type It indicates the type of tree which is going to be dumped. The",
+" argument \"type\" can be one of radix, radixtree, rb and rbtree(",
+" radix and radixtree means radix tree, rb and rbtree means red-black",
+" tree).",
+" -r offset The offset of radix_tree_root(radix tree) or rb_root(red-black",
+" tree), default is 0.If non-zero, the offset may be entered in",
+" either of two manners:\n",
+" 1. \"structure.member\" format",
+" 2. A number.\n",
+" -o offset The offset of rb_node(red-black tree). Its format is same as \"-r",
+" offset\"",
+" -s struct For each leaves' address of radix tree, format and print as this",
+" type of structure; use the \"struct.member\" format in order to",
+" display a particular member of the structure. To display multiple",
+" members of a structure, use a comma-separated list of members.",
+" -p Display the node's position information which indicates the",
+" relationship between it and the root. The root means the node with",
+" the biggest height offered by command's options. The information,",
+" such as \"root/l/r\" indicates the node is the right child of the",
+" left child of the root node.",
+" ",
+" The meaning of the \"start\" argument, which can be expressed either",
+" symbolically or in hexadecimal format, depends upon whether the -N option",
+" is pre-pended or not:",
+" ",
+" start The address of the structure where radix_tree_root(radix tree)",
+" or rb_node(red-black tree)",
+" -N start The address of the structure radix_tree_node(radix tree) or",
+" rb_node(red-black tree)",
+"\nEXAMPLES",
+" Display radix tree's address and position information only:\n",
+" %s> tree -t radix -r address_space.page_tree -p ffff880047875de0",
+" ffffea0000071298",
+" position: root/0/0",
+" ffffea0000065a30",
+" position: root/0/1",
+" ffffea00000664e8",
+" position: root/0/2",
+" ...",
+" ffffea0000072f40",
+" position: root/5/46",
+" ffffea0000072f78",
+" position: root/5/47",
+" ffffea0000072990",
+" position: root/5/48",
+" ...",
+" ",
+" Display radix tree, offering radix_tree_node's address:\n",
+" %s> tree -t radix -p -N 0xffff8800478734b1 -s page.flag",
+" ffffea0000071298",
+" position: root/0/0",
+" flags = 9007199254872172",
+" ffffea0000065a30",
+" position: root/0/1",
+" ...",
+" ffffea000004a4b0",
+" position: root/1/61",
+" flags = 9007199254872172",
+" ffffea000004a4e8",
+" position: root/1/62",
+" flags = 9007199254872172",
+" ...",
+" ",
+" Display red-black tree:\n",
+" %s> tree -t rb -r mm_struct.mm_rb -p 0xffff880037ea4cc0 -s rb_node",
+" ffff88004ae76670",
+" position: root",
+" struct rb_node {",
+" rb_parent_color = 1, ",
+" rb_right = 0xffff88004ae27950, ",
+" rb_left = 0xffff8800453d68c8",
+" }",
+" ffff8800453d68c8",
+" position: root/l",
+" struct rb_node {",
+" rb_parent_color = 18446612133570897521, ",
+" rb_right = 0xffff88004ae764e0, ",
+" rb_left = 0xffff88004db243d8",
+" }",
+" ...",
+" ffff88004ae76e40",
+" position: root/r/l/l/r",
+" struct rb_node {",
+" rb_parent_color = 18446612133475726697, ",
+" rb_right = 0x0, ",
+" rb_left = 0xffff8800453b3630",
+" }",
+" ffff8800453b3630",
+" position: root/r/l/l/r/l",
+" struct rb_node {",
+" rb_parent_color = 18446612133570899520, ",
+" rb_right = 0x0, ",
+" rb_left = 0x0",
+" }",
+" ...",
+NULL
+};
char *help_ptob[] = {
"ptob",
diff --git a/tools.c b/tools.c
index 7cc580a..3a6c551 100755
--- a/tools.c
+++ b/tools.c
@@ -24,6 +24,16 @@ struct hq_entry;
static void dealloc_hq_entry(struct hq_entry *);
static void show_options(void);
static void dump_struct_members(struct list_data *, int, ulong);
+static void rbtree_iteration(ulong, struct tree_data *, char *);
+static void rdtree_iteration(ulong, struct tree_data *, char *, ulong);
+static void dump_struct_members_for_tree(struct tree_data *, int, ulong);
+
+#define RADIXTREE_REQUEST (0x1)
+#define RBTREE_REQUEST (0x2)
+
+static ulong RADIX_TREE_MAP_SHIFT = UNINITIALIZED;
+static ulong RADIX_TREE_MAP_SIZE = UNINITIALIZED;
+static ulong RADIX_TREE_MAP_MASK = UNINITIALIZED;
/*
* General purpose error reporting routine. Type INFO prints the message
@@ -3507,6 +3517,370 @@ dump_struct_members(struct list_data *ld, int idx, ulong next)
FREEBUF(members);
}
+void
+cmd_tree()
+{
+ int c;
+ int type_flag;
+ long root_offset;
+ struct tree_data tree_data, *td;
+ struct datatype_member struct_member, *sm;
+ struct syment *sp;
+ ulong value;
+
+ type_flag = 0;
+ root_offset = 0;
+ sm = &struct_member;
+ td = &tree_data;
+ BZERO(td, sizeof(struct tree_data));
+
+ while ((c = getopt(argcnt, args, "t:r:o:s:pN")) != EOF) {
+ switch (c)
+ {
+ case 't':
+ if (type_flag != 0) {
+ error(INFO, "multiple type format not support\n");
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ if (STREQ(optarg, "radix") || STREQ(optarg, "radixtree"))
+ type_flag = RADIXTREE_REQUEST;
+ else if (STREQ(optarg, "rb") || STREQ(optarg, "rbtree"))
+ type_flag = RBTREE_REQUEST;
+ else {
+ error(INFO, "invalid type %s\n", optarg);
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ break;
+
+ case 'r':
+ if (td->flags & TREE_ROOT_OFFSET_ENTERED)
+ error(FATAL,
+ "root offset value %d (0x%lx) already entered\n",
+ td->member_offset, td->member_offset);
+ else if (IS_A_NUMBER(optarg))
+ root_offset = stol(optarg, FAULT_ON_ERROR, NULL);
+ else if (arg_to_datatype(optarg, sm, RETURN_ON_ERROR) > 1)
+ root_offset = sm->member_offset;
+ else
+ error(FATAL, "invalid -r argument: %s\n",
+ optarg);
+
+ td->flags |= TREE_ROOT_OFFSET_ENTERED;
+ break;
+
+ case 'o':
+ if (td->flags & TREE_OFFSET_ENTERED)
+ error(FATAL,
+ "offset value %d (0x%lx) already entered\n",
+ td->member_offset, td->member_offset);
+ else if (IS_A_NUMBER(optarg))
+ td->member_offset = stol(optarg,
+ FAULT_ON_ERROR, NULL);
+ else if (arg_to_datatype(optarg, sm, RETURN_ON_ERROR) > 1)
+ td->member_offset = sm->member_offset;
+ else
+ error(FATAL, "invalid -o argument: %s\n",
+ optarg);
+
+ td->flags |= TREE_OFFSET_ENTERED;
+ break;
+
+ case 's':
+ if (td->structname_args++ == 0)
+ hq_open();
+ hq_enter((ulong)optarg);
+ break;
+
+ case 'p':
+ td->flags |= TREE_POSITION_DISPLAY;
+ break;
+
+ case 'N':
+ td->flags |= TREE_NODE_POINTER;
+ break;
+
+ default:
+ argerrs++;
+ break;
+ }
+ }
+
+ if (argerrs)
+ cmd_usage(pc->curcmd, SYNOPSIS);
+
+ if (!args[optind]) {
+ error(INFO, "starting address required\n");
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ if ((sp = symbol_search(args[optind]))) {
+ td->start = sp->value;
+ goto next_arg;
+ }
+
+ if (!IS_A_NUMBER(args[optind])) {
+ if (can_eval(args[optind])) {
+ value = eval(args[optind], FAULT_ON_ERROR, NULL);
+ if (IS_KVADDR(value)) {
+ td->start = value;
+ goto next_arg;
+ }
+ }
+ error(FATAL, "invalid argument: %s\n", args[optind]);
+ }
+
+ if (hexadecimal_only(args[optind], 0)) {
+ value = htol(args[optind], FAULT_ON_ERROR, NULL);
+ if (IS_KVADDR(value)) {
+ td->start = value;
+ goto next_arg;
+ }
+ }
+
+ error(FATAL, "invalid argument: %s\n", args[optind]);
+
+next_arg:
+ if (args[optind+1]) {
+ error(INFO, "too many arguments\n");
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ if (td->structname_args) {
+ td->structname = (char **)GETBUF(sizeof(char *) *
+ td->structname_args);
+ retrieve_list((ulong *)td->structname, td->structname_args);
+ hq_close();
+ }
+
+ if (!(td->flags & TREE_NODE_POINTER)) {
+ td->start = td->start + root_offset;
+ }
+
+ td->flags &= ~(TREE_OFFSET_ENTERED|TREE_START_ENTERED);
+ td->flags |= VERBOSE;
+
+ if (CRASHDEBUG(1)) {
+ console(" type: %s\n",
+ type_flag & RADIXTREE_REQUEST ? "radix" : "rb");
+ console(" node pointer: %s\n",
+ td->flags & TREE_NODE_POINTER ? "yes" : "no");
+ console(" start: %lx\n", td->start);
+ console(" member_offset: %ld\n", td->member_offset);
+ console("structname_args: %d\n", td->structname_args);
+ }
+
+ hq_open();
+ if (type_flag & RADIXTREE_REQUEST)
+ do_rdtree(td);
+ else
+ do_rbtree(td);
+ hq_close();
+
+ if (td->structname_args)
+ FREEBUF(td->structname);
+}
+
+void
+do_rdtree(struct tree_data *td)
+{
+ long nlen;
+ ulong node_p;
+ uint height;
+ char pos[BUFSIZE];
+
+ if (RADIX_TREE_MAP_SHIFT == UNINITIALIZED) {
+ if (!(nlen = datatype_info("radix_tree_node", "slots",
+ MEMBER_SIZE_REQUEST)))
+ error(FATAL, "cannot determine length of "
+ "radix_tree_node.slots[] array\n");
+ nlen /= sizeof(void *);
+ RADIX_TREE_MAP_SHIFT = ffsl(nlen) - 1;
+ RADIX_TREE_MAP_SIZE = (1UL << RADIX_TREE_MAP_SHIFT);
+ RADIX_TREE_MAP_MASK = (RADIX_TREE_MAP_SIZE-1);
+ }
+
+ if (td->flags & TREE_NODE_POINTER)
+ node_p = td->start;
+ else {
+ readmem(td->start + OFFSET(radix_tree_root_height), KVADDR, &height,
+ sizeof(uint), "radix_tree_root height", FAULT_ON_ERROR);
+
+ if (height > ARRAY_LENGTH(height_to_maxindex)) {
+ fprintf(fp, "radix_tree_root at %lx\n", td->start);
+ dump_struct("radix_tree_root", (ulong)td->start, RADIX(16));
+ error(FATAL, "height %d is greater than \
+ height_to_maxindex[] index %ld\n",
+ height, ARRAY_LENGTH(height_to_maxindex));
+ }
+
+ readmem(td->start + OFFSET(radix_tree_root_rnode), KVADDR, &node_p,
+ sizeof(void *), "radix_tree_root rnode", FAULT_ON_ERROR);
+ }
+
+ if (node_p & 1)
+ node_p &= ~1;
+
+ sprintf(pos, "root");
+ rdtree_iteration(node_p, td, pos, -1);
+}
+
+void rdtree_iteration(ulong node_p, struct tree_data *td, char * ppos, ulong indexnum)
+{
+ uint height;
+ ulong slot;
+ int index;
+ int i;
+ char pos[BUFSIZE];
+
+ if (indexnum != -1)
+ sprintf(pos, "%s/%ld", ppos, indexnum);
+ else
+ sprintf(pos, "%s", ppos);
+
+ readmem(node_p + MEMBER_OFFSET("radix_tree_node", "height"), KVADDR,
+ &height, sizeof(uint), "radix_tree_node height", FAULT_ON_ERROR);
+
+ if (height > ARRAY_LENGTH(height_to_maxindex)) {
+ fprintf(fp, "radix_tree_node at %lx\n", node_p);
+ dump_struct("radix_tree_node", node_p, RADIX(16));
+ error(FATAL, "height %d is greater than height_to_maxindex[] \
+ index %ld\n", height, ARRAY_LENGTH(height_to_maxindex));
+ }
+
+ for (index = 0;index < RADIX_TREE_MAP_SIZE;index++) {
+ readmem((ulong)node_p + OFFSET(radix_tree_node_slots) +
+ sizeof(void *) * index, KVADDR, &slot, sizeof(void *),
+ "radix_tree_node.slot[index]", FAULT_ON_ERROR);
+ if (!slot)
+ continue;
+ if (height == 1) {
+ fprintf(fp, "%lx\n",slot);
+
+ if (td->flags & TREE_POSITION_DISPLAY)
+ fprintf(fp, "position: %s/%d\n", pos, index);
+
+ if (td->structname) {
+ for (i = 0; i < td->structname_args; i++) {
+ switch(count_chars(td->structname[i], '.'))
+ {
+ case 0:
+ dump_struct(td->structname[i],
+ slot, 0);
+ break;
+ case 1:
+ dump_struct_members_for_tree(td, i,
+ slot);
+ break;
+ default:
+ error(FATAL,
+ "invalid struct reference: %s\n",
+ td->structname[i]);
+ }
+ }
+ }
+ } else {
+ rdtree_iteration(slot, td, pos, index);
+ }
+ }
+}
+
+void
+do_rbtree(struct tree_data *td)
+{
+ ulong start;
+ char pos[BUFSIZE];
+ sprintf(pos, "root");
+
+ if (td->flags & TREE_NODE_POINTER)
+ start = td->start;
+ else {
+ readmem(td->start + MEMBER_OFFSET("rb_root", "rb_node"), KVADDR,
+ &start, sizeof(void *), "rb_root rb_node", FAULT_ON_ERROR);
+ }
+
+ rbtree_iteration(start, td, pos);
+}
+
+void
+rbtree_iteration(ulong node_p, struct tree_data *td, char *pos)
+{
+ int i;
+ ulong struct_p, left_p, right_p;
+ char left_pos[BUFSIZE], right_pos[BUFSIZE];
+
+ if (!node_p)
+ return;
+
+ if (node_p && !hq_enter(node_p))
+ error(FATAL, "\nduplicate tree entry: %lx\n", node_p);
+
+ struct_p = node_p - td->member_offset;
+
+
+ fprintf(fp, "%lx\n", node_p);
+
+ if (td->flags & TREE_POSITION_DISPLAY)
+ fprintf(fp, "position: %s\n", pos);
+
+ if (td->structname) {
+ for (i = 0; i < td->structname_args; i++) {
+ switch(count_chars(td->structname[i], '.'))
+ {
+ case 0:
+ dump_struct(td->structname[i], struct_p, 0);
+ break;
+ case 1:
+ dump_struct_members_for_tree(td, i, struct_p);
+ break;
+ default:
+ error(FATAL, "invalid struct reference: %s\n",
+ td->structname[i]);
+ }
+ }
+ }
+
+ readmem(node_p+MEMBER_OFFSET("rb_node", "rb_left"), KVADDR, &left_p,
+ sizeof(void *), "rb_node rb_left", FAULT_ON_ERROR);
+ readmem(node_p+MEMBER_OFFSET("rb_node", "rb_right"), KVADDR, &right_p,
+ sizeof(void *), "rb_node rb_right", FAULT_ON_ERROR);
+
+ sprintf(left_pos, "%s/l", pos);
+ sprintf(right_pos, "%s/r", pos);
+
+ rbtree_iteration(left_p, td, left_pos);
+ rbtree_iteration(right_p, td, right_pos);
+}
+
+void
+dump_struct_members_for_tree(struct tree_data *td, int idx, ulong struct_p)
+{
+ int i, argc;
+ char *p1;
+ char *structname, *members;
+ char *arglist[MAXARGS];
+
+ structname = GETBUF(strlen(td->structname[idx])+1);
+ members = GETBUF(strlen(td->structname[idx])+1);
+
+ strcpy(structname, td->structname[idx]);
+ p1 = strstr(structname, ".") + 1;
+
+ strcpy(members, p1);
+ replace_string(members, ",", ' ');
+ argc = parse_line(members, arglist);
+
+ for (i = 0; i <argc; i++) {
+ *p1 = NULLCHAR;
+ strcat(structname, arglist[i]);
+ dump_struct_member(structname, struct_p, 0);
+ }
+
+ FREEBUF(structname);
+ FREEBUF(members);
+}
+
/*
* The next set of functions are a general purpose hashing tool used to
* identify duplicate entries in a set of passed-in data, and if found,
--
1.7.1
--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/crash-utility
