Hello Dave,
The attachment is the code that adds two command, rbtree and rdtree. The
commands work well, but, onsidering some code is a copy of command list,
I think the code still need a big change.
>From 753d0e07f476c34e1ba2d509985a5fe7562fd13b Mon Sep 17 00:00:00 2001
From: qiaonuohan <qiaonuohan@xxxxxxxxxxxxxx>
Date: Mon, 14 May 2012 22:04:50 +0800
Subject: [PATCH] add command rdtree & rbtree
---
defs.h | 21 +++
global_data.c | 2 +
help.c | 179 ++++++++++++++++++++++++
tools.c | 432 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 634 insertions(+), 0 deletions(-)
diff --git a/defs.h b/defs.h
index 77a623d..657bc12 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_OFFSET_ENTERED (VERBOSE << 1)
+#define TREE_START_ENTERED (VERBOSE << 2)
+#define TREE_ROOT_POINTER (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,8 @@ 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_rdtree(void); /* tools.c */
+void cmd_rbtree(void); /* tools.c */
void cmd_template(void); /* tools.c */
void cmd_alias(void); /* cmdline.c */
void cmd_repeat(void); /* cmdline.c */
@@ -3829,6 +3845,9 @@ char *shift_string_right(char *, int);
int bracketed(char *, char *, int);
void backspace(int);
int do_list(struct list_data *);
+void cmd_tree(ulong);
+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 +4164,8 @@ extern char *help_help[];
extern char *help_irq[];
extern char *help_kmem[];
extern char *help__list[];
+extern char *help_rdtree[];
+extern char *help_rbtree[];
extern char *help_log[];
extern char *help_mach[];
extern char *help_mod[];
diff --git a/global_data.c b/global_data.c
index 98a5a79..9d6feb2 100755
--- a/global_data.c
+++ b/global_data.c
@@ -99,6 +99,8 @@ 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},
+ {"rdtree", cmd_rdtree, help_rdtree, 0},
+ {"rbtree", cmd_rbtree, help_rbtree, 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..2feb76c 100755
--- a/help.c
+++ b/help.c
@@ -4445,6 +4445,185 @@ char *help__list[] = {
NULL
};
+char *help_rdtree[] = {
+"rdtree",
+"radix tree",
+"[-s struct[.member[,member]]] [-p] [-H] start",
+" This command dumps the contents of a radix tree.",
+" ",
+" The arguments are as follows:\n",
+" -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 position information for each leaves.",
+" ",
+" The meaning of the \"start\" argument, which can be expressed either",
+" symbolically or in hexadecimal format, depends upon whether the -H option",
+" is pre-pended or not:",
+" ",
+" start The address of the structure radix_tree_node",
+" -H start The address of the structure radix_tree_root",
+"\nEXAMPLES",
+" Display address and position information only:\n",
+" %s> rdtree 0xffff88004e7cb911 -p",
+" ffffea000004a6a8",
+" position: root/0",
+" ffffea0000055880",
+" position: root/1",
+" ffffea0000c3cd08",
+" position: root/2",
+" ffffea0000071570",
+" position: root/3",
+" ffffea000004a2b8",
+" position: root/4",
+" ...",
+" ",
+" Display structure's information as well:\n",
+" %s> rdtree 0xffff88004e7cb911 -s page",
+" ffffea000004a6a8",
+" position: root/0",
+" struct page {",
+" flags = 9007199254872172, ",
+" _count = {",
+" counter = 19",
+" }, ",
+" {",
+" _mapcount = {",
+" counter = 17",
+" }, ",
+" {",
+" inuse = 17, ",
+" objects = 0",
+" }",
+" }, ",
+" {",
+" {",
+" private = 0, ",
+" mapping = 0xffff880047c261e0",
+" }, ",
+" ptl = {",
+" raw_lock = {",
+" slock = 0",
+" }",
+" }, ",
+" slab = 0x0, ",
+" first_page = 0x0",
+" }, ",
+" {",
+" index = 0, ",
+" freelist = 0x0",
+" }, ",
+" lru = {",
+" next = 0xffffea0000fb08c0, ",
+" prev = 0xffffea000004aaf8",
+" }",
+" }",
+" ffffea0000055880",
+" position: root/1",
+" struct page {",
+" flags = 9007199254872172, ",
+" _count = {",
+" counter = 17",
+" }, ",
+" {",
+" _mapcount = {",
+" counter = 15",
+" }, ",
+" {",
+" inuse = 15, ",
+" objects = 0",
+" }",
+" }, ",
+" {",
+" {",
+" private = 0, ",
+" mapping = 0xffff880047c261e0",
+" }, ",
+" ptl = {",
+" raw_lock = {",
+" slock = 0",
+" }",
+" }, ",
+" slab = 0x0, ",
+" first_page = 0x0",
+" }, ",
+" {",
+" index = 1, ",
+" freelist = 0x1",
+" }, ",
+" lru = {",
+" next = 0xffffea0000077f40, ",
+" prev = 0xffffea0000c3cd30",
+" }",
+" }",
+" ...",
+NULL
+};
+
+char *help_rbtree[] = {
+"rbtree",
+"red-black tree",
+"[[-o] offset] [-s struct[.member[,member]]] [-p] [-H] start",
+" This command dumps the contents of a red-black tree.",
+" ",
+" The arguments are as follows:\n",
+" [-o] offset The offset within the structure to the rb_node(default is 0).If",
+" non-zero, the offset may be entered in either of two manners:\n",
+" 1. In \"structure.member\" format; the \"-o\" is not necessary.",
+" 2. A number of bytes; the \"-o\" is only necessary on processors",
+" where the offset value could be misconstrued as a kernel",
+" virtual address.\n",
+" -s struct For each nodes' address of red-black 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 position information for each node.",
+" ",
+" The meaning of the \"start\" argument, which can be expressed either",
+" symbolically or in hexadecimal format, depends upon whether the -H option",
+" is pre-pended or not:",
+" ",
+" start The address of the structure radix_tree_node",
+" -H start The address of the structure radix_tree_root",
+"\nEXAMPLES",
+" Display address and position information only:\n",
+" %s> rbtree -o tts.rb ffffffffa0472380 -p",
+" ffffffffa0472388",
+" position: root",
+" ffffffffa04723a8",
+" position: root/l",
+" ffffffffa04723c8",
+" position: root/l/l",
+" ffffffffa04723e8",
+" position: root/l/l/l",
+" ffffffffa0472408",
+" position: root/l/r",
+" ffffffffa0472428",
+" position: root/r",
+" ",
+" Display structure's information as well:\n",
+" %s> rbtree -o tts.rb ffffffffa0472380 -p -s tts.a",
+" ffffffffa0472388",
+" position: root",
+" a = 0",
+" ffffffffa04723a8",
+" position: root/l",
+" a = 1",
+" ffffffffa04723c8",
+" position: root/l/l",
+" a = 2",
+" ffffffffa04723e8",
+" position: root/l/l/l",
+" a = 3",
+" ffffffffa0472408",
+" position: root/l/r",
+" a = 4",
+" ffffffffa0472428",
+" position: root/r",
+" a = 5",
+NULL
+};
char *help_ptob[] = {
"ptob",
diff --git a/tools.c b/tools.c
index 7cc580a..e7c176a 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,428 @@ dump_struct_members(struct list_data *ld, int idx, ulong next)
FREEBUF(members);
}
+void
+cmd_rdtree(void)
+{
+ cmd_tree(RADIXTREE_REQUEST);
+}
+
+void
+cmd_rbtree(void)
+{
+ cmd_tree(RBTREE_REQUEST);
+}
+
+void
+cmd_tree(ulong flags)
+{
+ int c;
+ struct tree_data tree_data, *td;
+ struct datatype_member struct_member, *sm;
+ struct syment *sp;
+ ulong value;
+
+ sm = &struct_member;
+ td = &tree_data;
+ BZERO(td, sizeof(struct tree_data));
+
+ while ((c = getopt(argcnt, args, "Hs:o:p")) != EOF) {
+ switch (c)
+ {
+ case 'H':
+ if (flags & RADIXTREE_REQUEST)
+ td->flags |= TREE_ROOT_POINTER;
+ if (flags & RBTREE_REQUEST)
+ td->flags |= TREE_NODE_POINTER;
+ break;
+
+ case 's':
+ if (td->structname_args++ == 0)
+ hq_open();
+ hq_enter((ulong)optarg);
+ 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 'p':
+ td->flags |= TREE_POSITION_DISPLAY;
+ break;
+
+ default:
+ argerrs++;
+ break;
+ }
+ }
+
+ if (argerrs)
+ cmd_usage(pc->curcmd, SYNOPSIS);
+
+ if (args[optind] && args[optind+1] && args[optind+2]) {
+ 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();
+ }
+
+ while (args[optind]) {
+ if (strstr(args[optind], ".") &&
+ arg_to_datatype(args[optind], sm, RETURN_ON_ERROR) > 1) {
+ if (td->flags & TREE_OFFSET_ENTERED)
+ error(FATAL,
+ "offset value %ld (0x%lx) already entered\n",
+ td->member_offset, td->member_offset);
+ td->member_offset = sm->member_offset;
+ td->flags |= TREE_OFFSET_ENTERED;
+ } else {
+ /*
+ * Do an inordinate amount of work to avoid -o...
+ *
+ * OK, if it's a symbol, then it has to be a start.
+ */
+ if ((sp = symbol_search(args[optind]))) {
+ if (td->flags & TREE_START_ENTERED)
+ error(FATAL,
+ "tree start already entered\n");
+ td->start = sp->value;
+ td->flags |= TREE_START_ENTERED;
+ goto next_arg;
+ }
+
+ /*
+ * If it's not a symbol nor a number, bail out if it
+ * cannot be evaluated as a start address.
+ */
+ if (!IS_A_NUMBER(args[optind])) {
+ if (can_eval(args[optind])) {
+ value = eval(args[optind], FAULT_ON_ERROR, NULL);
+ if (IS_KVADDR(value)) {
+ if (td->flags & TREE_START_ENTERED)
+ error(FATAL,
+ "tree start already entered\n");
+ td->start = value;
+ td->flags |= TREE_START_ENTERED;
+ goto next_arg;
+ }
+ }
+
+ error(FATAL, "invalid argument: %s\n",
+ args[optind]);
+ }
+
+ /*
+ * If the start is known, it's got to be an offset.
+ */
+ if (td->flags & TREE_START_ENTERED) {
+ value = stol(args[optind], FAULT_ON_ERROR,
+ NULL);
+ td->member_offset = value;
+ td->flags |= TREE_OFFSET_ENTERED;
+ break;
+ }
+
+ /*
+ * If the offset is known, or there's no subsequent
+ * argument, then it's got to be a start.
+ */
+ if ((td->flags & TREE_OFFSET_ENTERED) ||
+ !args[optind+1]) {
+ value = htol(args[optind], FAULT_ON_ERROR,
+ NULL);
+ if (!IS_KVADDR(value))
+ error(FATAL,
+ "invalid kernel virtual address: %s\n",
+ args[optind]);
+ td->start = value;
+ td->flags |= TREE_START_ENTERED;
+ break;
+ }
+
+ /*
+ * Neither start nor offset has been entered, and
+ * it's a number. Look ahead to the next argument.
+ * If it's a symbol, then this must be an offset.
+ */
+ if ((sp = symbol_search(args[optind+1]))) {
+ value = stol(args[optind], FAULT_ON_ERROR,
+ NULL);
+ td->member_offset = value;
+ td->flags |= TREE_OFFSET_ENTERED;
+ goto next_arg;
+ } else if ((!IS_A_NUMBER(args[optind+1]) &&
+ !can_eval(args[optind+1])) &&
+ !strstr(args[optind+1], "."))
+ error(FATAL, "symbol not found: %s\n",
+ args[optind+1]);
+ /*
+ * Crunch time. We've got two numbers. If they're
+ * both ambigous we must have zero-based kernel
+ * virtual address space.
+ */
+ if (COMMON_VADDR_SPACE() &&
+ AMBIGUOUS_NUMBER(args[optind]) &&
+ AMBIGUOUS_NUMBER(args[optind+1])) {
+ error(INFO,
+ "ambiguous arguments: \"%s\" and \"%s\": -o is required\n",
+ args[optind], args[optind+1]);
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ if (hexadecimal_only(args[optind], 0)) {
+ value = htol(args[optind], FAULT_ON_ERROR,
+ NULL);
+ if (IS_KVADDR(value)) {
+ td->start = value;
+ td->flags |= TREE_START_ENTERED;
+ goto next_arg;
+ }
+ }
+ value = stol(args[optind], FAULT_ON_ERROR, NULL);
+ td->member_offset = value;
+ td->flags |= TREE_OFFSET_ENTERED;
+ }
+next_arg:
+ optind++;
+ }
+
+ if (!(td->flags & TREE_START_ENTERED)) {
+ error(INFO, "starting address required\n");
+ cmd_usage(pc->curcmd, SYNOPSIS);
+ }
+
+ if (!(td->flags & TREE_NODE_POINTER)) {
+ td->start = td->start + td->member_offset;
+ }
+
+ if ((flags & RADIXTREE_REQUEST) && (td->flags & TREE_OFFSET_ENTERED))
+ error(INFO, "offset infomation is useless.\n");
+
+ td->flags &= ~(TREE_OFFSET_ENTERED|TREE_START_ENTERED);
+ td->flags |= VERBOSE;
+
+ hq_open();
+ if (flags & 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_ROOT_POINTER) {
+ 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);
+ }
+ else
+ node_p = td->start;
+
+ 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 *slots;
+ 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));
+ }
+
+ slots = (ulong *)GETBUF(sizeof(void *) * RADIX_TREE_MAP_SIZE);
+ readmem((ulong)node_p+OFFSET(radix_tree_node_slots), KVADDR, &slots[0],
+ sizeof(void *) * RADIX_TREE_MAP_SIZE, "radix_tree_node.slots",
+ FAULT_ON_ERROR);
+
+ for (index = 0;index < RADIX_TREE_MAP_SIZE;index++) {
+ if (!slots[index])
+ continue;
+ if (height == 1) {
+ fprintf(fp, "%lx\n",slots[index]);
+
+ 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],
+ slots[index], 0);
+ break;
+ case 1:
+ dump_struct_members_for_tree(td, i,
+ slots[index]);
+ break;
+ default:
+ error(FATAL,
+ "invalid struct reference: %s\n",
+ td->structname[i]);
+ }
+ }
+ }
+ } else {
+ rdtree_iteration(slots[index], td, pos, index);
+ }
+ }
+}
+
+void
+do_rbtree(struct tree_data *td)
+{
+ char pos[BUFSIZE];
+ sprintf(pos, "root");
+
+ rbtree_iteration(td->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
