|
|
| [Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] |
At 2012-5-25 3:12, Dave Anderson wrote:
But again, the red-black tree dump should be similar to the radix tree dump, and both of them should be similar to the "list" command.\
Fixed. I misunderstood the address printed by list command. I thought I need to print the address of tree node.
Another minor nit -- you should disallow the usage of "-o offset" when a radix tree is being dumped. Although your patch apparently ignores it, it should display an error message and fail the command.
Print ""-o offset" is supported for radix tree" and then fail the command. -- -- Regards Qiao Nuohan
>From 5129a1a5fb3f3cd6c28eada13ac6e8cfe8602d28 Mon Sep 17 00:00:00 2001
From: qiaonuohan <qiaonuohan@xxxxxxxxxxxxxx>
Date: Fri, 25 May 2012 21:16:59 +0800
Subject: [PATCH] add a new command tree
---
defs.h | 18 +++
global_data.c | 1 +
help.c | 105 ++++++++++++++++
tools.c | 377 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 501 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..b2970c7 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 -o vm_area_struct.vm_rb -p 0xffff880037b3ed00 -s vm_area_struct.vm_rb",
+" ffff88004816a2d8",
+" position: root",
+" vm_rb = {",
+" rb_parent_color = 1, ",
+" rb_right = 0xffff88004816aae0, ",
+" rb_left = 0xffff88004816ff08",
+" }",
+" ffff88004816fed0",
+" position: root/l",
+" vm_rb = {",
+" rb_parent_color = 18446612133523661584, ",
+" rb_right = 0xffff88004816fd78, ",
+" rb_left = 0xffff88004816a6f8",
+" }",
+" ...",
+" ffff88004816fbb0",
+" position: root/r/l/l/r",
+" vm_rb = {",
+" rb_parent_color = 18446612133523661384, ",
+" rb_right = 0x0, ",
+" rb_left = 0x0",
+" }",
+" ffff88004816a5f8",
+" position: root/r/l/r",
+" vm_rb = {",
+" rb_parent_color = 18446612133523662185, ",
+" rb_right = 0xffff88004816a4a0, ",
+" rb_left = 0x0",
+" }",
+" ...",
+NULL
+};
char *help_ptob[] = {
"ptob",
diff --git a/tools.c b/tools.c
index 7cc580a..ee82afa 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,373 @@ 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 & (RADIXTREE_REQUEST|RBTREE_REQUEST)) {
+ 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 ((type_flag & RADIXTREE_REQUEST) && (td->flags & TREE_OFFSET_ENTERED))
+ error(FATAL, "\"-o offset\" is supported for radix tree\n");
+
+ 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", struct_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
[Home] [Fedora Legacy List] [Fedora Maintainers] [Fedora Desktop] [Red Hat 9 Bible] [Fedora Bible] [Fedora SELinux] [Big List of Linux Books] [Yosemite News] [Yosemite Photos] [KDE Users] [Fedora Tools]
|
