[Crash-utility] [PATCH 2/2] tree: add an option to dump the tree sorted

--- defs.h | 1 + help.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ tools.c | 16 +++++++++++-- 3 files changed, 95 insertions(+), 2 deletions(-) diff --git a/defs.h b/defs.h index adddb9f2748d..ec298cbd70be 100644 --- a/defs.h +++ b/defs.h @@ -2480,6 +2480,7 @@ struct tree_data { #define TREE_STRUCT_RADIX_16 (VERBOSE << 6) #define TREE_PARSE_MEMBER (VERBOSE << 7) #define TREE_READ_MEMBER (VERBOSE << 8) +#define TREE_LINEAR_ORDER (VERBOSE << 9) #define ALIAS_RUNTIME (1) #define ALIAS_RCLOCAL (2) diff --git a/help.c b/help.c index c5cec5365962..e7df50fa2ef4 100644 --- a/help.c +++ b/help.c @@ -5698,6 +5698,8 @@ char *help_tree[] = { " indicates \"root/l/r\" means that the node is the right child", " of the left child of the root node. For radix trees, the height", " and slot index values are shown with respect to the root.", +" -l Dump the tree sorted in linear order starting with the leftmost", +" node and progressing to the right.", " ", " The meaning of the \"start\" argument, which can be expressed either in", " hexadecimal format or symbolically, depends upon whether the -N option", @@ -5823,6 +5825,84 @@ char *help_tree[] = { " ffffea000407de58", " position: root/3/28", "", +" List the tree in linear order from the leftmost node progressing", +" to the right using the -l option:\n", +" %s> tree -lps vm_area_struct.vm_start,vm_end -o vm_area_struct.vm_rb -r mm_struct.mm_rb 0xffff8805dee5e400 | sed 's/^ //' | paste - - - - | column -ts' '", +" ffff8805e108f008 position: root/l/l/l/l/l/l/l/l/l vm_start = 0x7f6f9ca5f000 vm_end = 0x7f6f9d44c000", +" ffff880540d35d88 position: root/l/l/l/l/l/l/l/l vm_start = 0x7f6f9d44c000 vm_end = 0x7f6f9d454000", +" ffff8805def64d80 position: root/l/l/l/l/l/l/l vm_start = 0x7f6f9d454000 vm_end = 0x7f6f9d653000", +" ffff8805e0b46510 position: root/l/l/l/l/l/l/l/r/l vm_start = 0x7f6f9d653000 vm_end = 0x7f6f9d654000", +" ffff8805e108e288 position: root/l/l/l/l/l/l/l/r vm_start = 0x7f6f9d654000 vm_end = 0x7f6f9d655000", +" ffff8805def65bd8 position: root/l/l/l/l/l/l/l/r/r vm_start = 0x7f6f9d655000 vm_end = 0x7f6f9d661000", +" ffff8805def64ca8 position: root/l/l/l/l/l/l vm_start = 0x7f6f9d661000 vm_end = 0x7f6f9d860000", +" ffff8805def641b0 position: root/l/l/l/l/l/l/r/l vm_start = 0x7f6f9d860000 vm_end = 0x7f6f9d861000", +" ffff8805def64438 position: root/l/l/l/l/l/l/r/l/r vm_start = 0x7f6f9d861000 vm_end = 0x7f6f9d862000", +" ffff8805def65368 position: root/l/l/l/l/l/l/r vm_start = 0x7f6f9d862000 vm_end = 0x7f6f9d868000", +" ffff880540ec2e58 position: root/l/l/l/l/l/l/r/r vm_start = 0x7f6f9d868000 vm_end = 0x7f6f9d88c000", +" ...", +" ffff8805dfc08e58 position: root/l/r/r/l/r/l vm_start = 0x7f6fa020f000 vm_end = 0x7f6fa0216000", +" ffff880540ec35f0 position: root/l/r/r/l/r vm_start = 0x7f6fa0216000 vm_end = 0x7f6fa0217000", +" ffff8805dfc09cb0 position: root/l/r/r/l/r/r vm_start = 0x7f6fa0217000 vm_end = 0x7f6fa0338000", +" ffff8805dfc08360 position: root/l/r/r vm_start = 0x7f6fa0338000 vm_end = 0x7f6fa0538000", +" ffff8805dfc08bd0 position: root vm_start = 0x7f6fa07af000 vm_end = 0x7f6fa09ae000", +" ffff8805dfc08288 position: root/r/l/l/l/l/l vm_start = 0x7f6fa09ae000 vm_end = 0x7f6fa09b2000", +" ffff880540ec31b8 position: root/r/l/l/l/l/l/r vm_start = 0x7f6fa09b2000 vm_end = 0x7f6fa09b3000", +" ffff8805dfc08ca8 position: root/r/l/l/l/l vm_start = 0x7f6fa09b3000 vm_end = 0x7f6fa09b4000", +" ffff8800f78c15f0 position: root/r/l/l/l/l/r vm_start = 0x7f6fa09b4000 vm_end = 0x7f6fa0b6c000", +" ...", +" ffff8805def651b8 position: root/r/r/r/r/l/l vm_start = 0x7f6fa2f42000 vm_end = 0x7f6fa2f43000", +" ffff880540d35e60 position: root/r/r/r/r/l vm_start = 0x7f6fa2f43000 vm_end = 0x7f6fa2f44000", +" ffff880540d35518 position: root/r/r/r/r/l/r vm_start = 0x7f6fa2f44000 vm_end = 0x7f6fa2f85000", +" ffff880540d356c8 position: root/r/r/r/r vm_start = 0x7f6fa3185000 vm_end = 0x7f6fa3187000", +" ffff8805def64000 position: root/r/r/r/r/r/l/l vm_start = 0x7f6fa3187000 vm_end = 0x7f6fa3188000", +" ffff880540d35cb0 position: root/r/r/r/r/r/l vm_start = 0x7f6fa3188000 vm_end = 0x7f6fa3189000", +" ffff8805def64798 position: root/r/r/r/r/r/l/r vm_start = 0x7f6fa4bf9000 vm_end = 0x7f6fa4c1a000", +" ffff880540d340d8 position: root/r/r/r/r/r vm_start = 0x7ffc2b386000 vm_end = 0x7ffc2b3a8000", +" ffff880540d35950 position: root/r/r/r/r/r/r vm_start = 0x7ffc2b3c2000 vm_end = 0x7ffc2b3c4000", +"", +" Compared to the top/down order:\n", +" %s> tree -ps vm_area_struct.vm_start,vm_end -o vm_area_struct.vm_rb -r mm_struct.mm_rb 0xffff8805dee5e400 | sed 's/^ //' | paste - - - - | column -ts' '", +" ffff8805dfc08bd0 position: root vm_start = 0x7f6fa07af000 vm_end = 0x7f6fa09ae000", +" ffff8805e0b79b00 position: root/l vm_start = 0x7f6f9f585000 vm_end = 0x7f6f9f785000", +" ffff8805e0b79e60 position: root/l/l vm_start = 0x7f6f9ec2b000 vm_end = 0x7f6f9ee2b000", +" ffff8805e0b78bd0 position: root/l/l/l vm_start = 0x7f6f9e2c1000 vm_end = 0x7f6f9e4c0000", +" ffff8805e07f0bd0 position: root/l/l/l/l vm_start = 0x7f6f9da92000 vm_end = 0x7f6f9dc91000", +" ffff880540ec20d8 position: root/l/l/l/l/l vm_start = 0x7f6f9d88c000 vm_end = 0x7f6f9da8b000", +" ffff8805def64ca8 position: root/l/l/l/l/l/l vm_start = 0x7f6f9d661000 vm_end = 0x7f6f9d860000", +" ffff8805def64d80 position: root/l/l/l/l/l/l/l vm_start = 0x7f6f9d454000 vm_end = 0x7f6f9d653000", +" ffff880540d35d88 position: root/l/l/l/l/l/l/l/l vm_start = 0x7f6f9d44c000 vm_end = 0x7f6f9d454000", +" ffff8805e108f008 position: root/l/l/l/l/l/l/l/l/l vm_start = 0x7f6f9ca5f000 vm_end = 0x7f6f9d44c000", +" ffff8805e108e288 position: root/l/l/l/l/l/l/l/r vm_start = 0x7f6f9d654000 vm_end = 0x7f6f9d655000", +" ffff8805e0b46510 position: root/l/l/l/l/l/l/l/r/l vm_start = 0x7f6f9d653000 vm_end = 0x7f6f9d654000", +" ffff8805def65bd8 position: root/l/l/l/l/l/l/l/r/r vm_start = 0x7f6f9d655000 vm_end = 0x7f6f9d661000", +" ...", +" ffff8805dfc08360 position: root/l/r/r vm_start = 0x7f6fa0338000 vm_end = 0x7f6fa0538000", +" ffff8805dfc096c8 position: root/l/r/r/l vm_start = 0x7f6fa0010000 vm_end = 0x7f6fa020f000", +" ffff880540ec2870 position: root/l/r/r/l/l vm_start = 0x7f6f9ffe9000 vm_end = 0x7f6f9ffea000", +" ffff8805dfc09440 position: root/l/r/r/l/l/l vm_start = 0x7f6f9ffe8000 vm_end = 0x7f6f9ffe9000", +" ffff8805dfc09290 position: root/l/r/r/l/l/r vm_start = 0x7f6f9ffea000 vm_end = 0x7f6fa0010000", +" ffff880540ec35f0 position: root/l/r/r/l/r vm_start = 0x7f6fa0216000 vm_end = 0x7f6fa0217000", +" ffff8805dfc08e58 position: root/l/r/r/l/r/l vm_start = 0x7f6fa020f000 vm_end = 0x7f6fa0216000", +" ffff8805dfc09cb0 position: root/l/r/r/l/r/r vm_start = 0x7f6fa0217000 vm_end = 0x7f6fa0338000", +" ffff880540d346c0 position: root/r vm_start = 0x7f6fa1f5a000 vm_end = 0x7f6fa2159000", +" ffff8800f78c10e0 position: root/r/l vm_start = 0x7f6fa135f000 vm_end = 0x7f6fa155f000", +" ffff8800f78c1440 position: root/r/l/l vm_start = 0x7f6fa0d8d000 vm_end = 0x7f6fa0f8d000", +" ffff8800f78c1950 position: root/r/l/l/l vm_start = 0x7f6fa0b6c000 vm_end = 0x7f6fa0d6c000", +" ffff8805dfc08ca8 position: root/r/l/l/l/l vm_start = 0x7f6fa09b3000 vm_end = 0x7f6fa09b4000", +" ffff8805dfc08288 position: root/r/l/l/l/l/l vm_start = 0x7f6fa09ae000 vm_end = 0x7f6fa09b2000", +" ffff880540ec31b8 position: root/r/l/l/l/l/l/r vm_start = 0x7f6fa09b2000 vm_end = 0x7f6fa09b3000", +" ffff8800f78c15f0 position: root/r/l/l/l/l/r vm_start = 0x7f6fa09b4000 vm_end = 0x7f6fa0b6c000", +" ...", +" ffff880540d356c8 position: root/r/r/r/r vm_start = 0x7f6fa3185000 vm_end = 0x7f6fa3187000", +" ffff880540d35e60 position: root/r/r/r/r/l vm_start = 0x7f6fa2f43000 vm_end = 0x7f6fa2f44000", +" ffff8805def651b8 position: root/r/r/r/r/l/l vm_start = 0x7f6fa2f42000 vm_end = 0x7f6fa2f43000", +" ffff880540d35518 position: root/r/r/r/r/l/r vm_start = 0x7f6fa2f44000 vm_end = 0x7f6fa2f85000", +" ffff880540d340d8 position: root/r/r/r/r/r vm_start = 0x7ffc2b386000 vm_end = 0x7ffc2b3a8000", +" ffff880540d35cb0 position: root/r/r/r/r/r/l vm_start = 0x7f6fa3188000 vm_end = 0x7f6fa3189000", +" ffff8805def64000 position: root/r/r/r/r/r/l/l vm_start = 0x7f6fa3187000 vm_end = 0x7f6fa3188000", +" ffff8805def64798 position: root/r/r/r/r/r/l/r vm_start = 0x7f6fa4bf9000 vm_end = 0x7f6fa4c1a000", +" ffff880540d35950 position: root/r/r/r/r/r/r vm_start = 0x7ffc2b3c2000 vm_end = 0x7ffc2b3c4000", +"", " Alternatively, take the address of the radix_tree_node from the", " radix_tree_root structure in the address_space structure above,", " and display the tree with the -N option:\n", diff --git a/tools.c b/tools.c index 992f4776281a..1970e8bb136b 100644 --- a/tools.c +++ b/tools.c @@ -3926,7 +3926,7 @@ cmd_tree() td = &tree_data; BZERO(td, sizeof(struct tree_data)); - while ((c = getopt(argcnt, args, "xdt:r:o:s:S:pN")) != EOF) { + while ((c = getopt(argcnt, args, "xdt:r:o:s:S:plN")) != EOF) { switch (c) { case 't': @@ -3993,6 +3993,10 @@ cmd_tree() td->flags |= TREE_POSITION_DISPLAY; break; + case 'l': + td->flags |= TREE_LINEAR_ORDER; + break; + case 'N': td->flags |= TREE_NODE_POINTER; break; @@ -4399,6 +4403,13 @@ rbtree_iteration(ulong node_p, struct tree_data *td, char *pos) struct_p = node_p - td->node_member_offset; + if (td->flags & TREE_LINEAR_ORDER && + readmem(node_p+OFFSET(rb_node_rb_left), KVADDR, &new_p, + sizeof(void *), "rb_node rb_left", RETURN_ON_ERROR)) { + sprintf(new_pos, "%s/l", pos); + rbtree_iteration(new_p, td, new_pos); + } + if (td->flags & VERBOSE) fprintf(fp, "%lx\n", struct_p); @@ -4430,7 +4441,8 @@ rbtree_iteration(ulong node_p, struct tree_data *td, char *pos) } } - if ( readmem(node_p+OFFSET(rb_node_rb_left), KVADDR, &new_p, + if (!(td->flags & TREE_LINEAR_ORDER) && + readmem(node_p+OFFSET(rb_node_rb_left), KVADDR, &new_p, sizeof(void *), "rb_node rb_left", RETURN_ON_ERROR)) { sprintf(new_pos, "%s/l", pos); rbtree_iteration(new_p, td, new_pos); -- 2.16.2