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