Re: [Crash-utility] [PATCH v2 3/6] Add tree cmd support for maple tree

Maple tree is a new data structure for crash, so cmd_tree support is needed for users to dump and view the content of maple tree. This patch achieves this by porting mt_dump() and its related functions from kernel, and adapting them with tree cmd. We introduced a new -v arg specifically for dumping the complete content of maple tree: crash> tree -t maple 0xffff9034c006aec0 -v maple_tree(ffff9034c006aec0) flags 309, height 0 root 0xffff9034de70041e 0-18446744073709551615: node 0xffff9034de700400 depth 0 type 3 parent 0xffff9034c006aec1 contents:... 0-140112331583487: node 0xffff9034c01e8800 depth 1 type 1 parent 0xffff9034de700406 contents:... 0-94643156942847: (nil) 94643156942848-94643158024191: 0xffff9035131754c0 94643158024192-94643160117247: (nil) ... The old tree args can work as well: crash> tree -t maple -r mm_struct.mm_mt 0xffff9034c006aec0 -p ffff9034de70041e index: 0 position: root ffff9034c01e880c index: 1 position: root/0 0 index: 2 position: root/0/0 ffff9035131754c0 index: 3 position: root/0/1 0 index: 4 position: root/0/2 .... crash> tree -t maple 0xffff9034c006aec0 -p -x -s vm_area_struct.vm_start,vm_end ffff9034de70041e index: 0 position: root ffff9034c01e880c index: 1 position: root/0 0 index: 2 position: root/0/0 ffff9035131754c0 index: 3 position: root/0/1 vm_start = 0x5613d3c00000, vm_end = 0x5613d3d08000, 0 index: 4 position: root/0/2 ... Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; --- defs.h | 5 + maple_tree.c | 385 +++++++++++++++++++++++++++++++++++++++++++++++++++ tools.c | 20 ++- 3 files changed, 404 insertions(+), 6 deletions(-) diff --git a/defs.h b/defs.h index 2978cec..3f2453e 100644 --- a/defs.h +++ b/defs.h @@ -2191,12 +2191,15 @@ struct offset_table { /* stash of commonly-used offsets */ long maple_arange_64_parent; long maple_arange_64_pivot; long maple_arange_64_slot; + long maple_arange_64_gap; long maple_arange_64_meta; long maple_range_64_parent; long maple_range_64_pivot; long maple_range_64_slot; + long maple_range_64_pad; long maple_range_64_meta; long maple_metadata_end; + long maple_metadata_gap; }; struct size_table { /* stash of commonly-used sizes */ @@ -2705,6 +2708,7 @@ struct tree_data { #define TREE_PARSE_MEMBER (VERBOSE << 7) #define TREE_READ_MEMBER (VERBOSE << 8) #define TREE_LINEAR_ORDER (VERBOSE << 9) +#define TREE_STRUCT_VERBOSE (VERBOSE << 9)

#define ALIAS_RUNTIME (1) #define ALIAS_RCLOCAL (2) @@ -5576,6 +5580,7 @@ int same_file(char *, char *); int cleanup_memory_driver(void); void maple_init(void); +int do_mptree(struct tree_data *); /* * help.c diff --git a/maple_tree.c b/maple_tree.c index 058b769..33903cb 100644 --- a/maple_tree.c +++ b/maple_tree.c @@ -34,6 +34,7 @@ unsigned char *mt_slots = NULL; unsigned char *mt_pivots = NULL; +unsigned long mt_max[4] = {0}; #define MAPLE_BUFSIZE 512 @@ -791,6 +792,382 @@ void *mas_find(struct ma_state *mas, unsigned long max) return mas_next_entry(mas, max); } +/***************For cmd_tree********************/ + +struct do_maple_tree_info { + ulong maxcount; + ulong count; + void *data; +}; + +struct cmd_tree_info { + ulong index; + struct tree_data *td; +} cmd_tree_info; + +static const char spaces[] = " "; + +static void do_mt_range64(const struct maple_tree *, void *, + unsigned long, unsigned long, unsigned int, char *); +static void do_mt_arange64(const struct maple_tree *, void *, + unsigned long, unsigned long, unsigned int, char *); +static void do_mt_entry(void *, unsigned long, unsigned long, unsigned int, + unsigned int, char *); +static void do_mt_node(const struct maple_tree *, void *, unsigned long, + unsigned long, unsigned int, char *); +struct req_entry *fill_member_offsets(char *); +void dump_struct_members_fast(struct req_entry *, int, ulong); +void dump_struct_members_for_tree(struct tree_data *, int, ulong); + +static void mt_dump_range(unsigned long min, unsigned long max, + unsigned int depth) +{ + if (min == max) + fprintf(fp, "%.*s%lu: ", depth * 2, spaces, min); + else + fprintf(fp, "%.*s%lu-%lu: ", depth * 2, spaces, min, max); +} + +static inline bool mt_is_reserved(const void *entry) +{ + return ((unsigned long)entry < MAPLE_RESERVED_RANGE) && + xa_is_internal(entry); +} + +static inline bool mte_is_leaf(const struct maple_enode *entry) +{ + return ma_is_leaf(mte_node_type(entry)); +} + +static unsigned int mt_height(const struct maple_tree *mt) +{ + return (*(unsigned int *)(mt + OFFSET(maple_tree_ma_flags)) & + MT_FLAGS_HEIGHT_MASK) + >> MT_FLAGS_HEIGHT_OFFSET; +} + +static void dump_mt_range64(struct maple_range_64 *node) +{ + int i; + + fprintf(fp, " contents: "); + for (i = 0; i < mt_slots[maple_range_64] - 1; i++) + fprintf(fp, "%p %lu ", + *((void **)((char *)node + OFFSET(maple_range_64_slot)) + i), + *((unsigned long *)((char *)node + OFFSET(maple_range_64_pivot)) + i)); + fprintf(fp, "%p\n", *((void **)((char *)node + OFFSET(maple_range_64_slot)) + i)); +} + +static void dump_mt_arange64(struct maple_arange_64 *node) +{ + int i; + + fprintf(fp, " contents: "); + for (i = 0; i < mt_slots[maple_arange_64]; i++) + fprintf(fp, "%lu ", + *((unsigned long *)((char *)node + OFFSET(maple_arange_64_gap)) + i)); + + fprintf(fp, "| %02X %02X| ", + *((unsigned char *)node + OFFSET(maple_arange_64_meta) + OFFSET(maple_metadata_end)), + *((unsigned char *)node + OFFSET(maple_arange_64_meta) + OFFSET(maple_metadata_gap))); + + for (i = 0; i < mt_slots[maple_arange_64] - 1; i++) + fprintf(fp, "%p %lu ", + *((void **)((char *)node + OFFSET(maple_arange_64_slot)) + i), + *((unsigned long *)((char *)node + OFFSET(maple_arange_64_pivot)) + i)); + fprintf(fp, "%p\n", + *((void **)((char *)node + OFFSET(maple_arange_64_slot)) + i)); +} + +static void dump_mt_entry(void *entry, unsigned long min, unsigned long max, + unsigned int depth) +{ + mt_dump_range(min, max, depth); + + if (xa_is_value(entry)) + fprintf(fp, "value %ld (0x%lx) [%p]\n", xa_to_value(entry), + xa_to_value(entry), entry); + else if (xa_is_zero(entry)) + fprintf(fp, "zero (%ld)\n", xa_to_internal(entry)); + else if (mt_is_reserved(entry)) + fprintf(fp, "UNKNOWN ENTRY (%p)\n", entry); + else + fprintf(fp, "%p\n", entry); +} + +static void dump_mt_node(struct maple_node *node, char *node_data, + unsigned int type, unsigned long min, unsigned long max, + unsigned int depth) +{ + mt_dump_range(min, max, depth); + + fprintf(fp, "node %p depth %d type %d parent %p", node, depth, type, + node ? *(struct maple_pnode **)(node_data + OFFSET(maple_node_parent)) + : NULL); +} + +static void do_mt_range64(const struct maple_tree *mt, void *entry, + unsigned long min, unsigned long max, + unsigned int depth, char *path) +{ + struct maple_node *m_node = mte_to_node(entry); + unsigned char tmp_node[MAPLE_BUFSIZE]; + bool leaf = mte_is_leaf(entry); + unsigned long first = min, last; + int i; + int len = strlen(path); + + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + readmem((ulonglong)m_node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mt_dump_range64 read maple_node", FAULT_ON_ERROR); + + struct maple_range_64 *node = (struct maple_range_64 *) + (tmp_node + OFFSET(maple_node_mr64)); + + if (cmd_tree_info.td) { + if (cmd_tree_info.td->flags & TREE_STRUCT_VERBOSE) { + dump_mt_range64(node); + } + if (cmd_tree_info.td->flags & TREE_POSITION_DISPLAY) + fprintf(fp, "%.*s index: %ld position: %s\n", + depth * 2, spaces, cmd_tree_info.index++, path); + } + + for (i = 0; i < mt_slots[maple_range_64]; i++) { + last = max; + + if (i < (mt_slots[maple_range_64] - 1)) + last = *((unsigned long *)((char *)node + OFFSET(maple_range_64_pivot)) + i); + else if (!*((void **)((char *)node + OFFSET(maple_range_64_slot)) + i) && + max != mt_max[mte_node_type(entry)]) + break; + if (last == 0 && i > 0) + break; + if (leaf) + do_mt_entry(mt_slot(mt, (void **)((char *)node + OFFSET(maple_range_64_slot)), i), + first, last, depth + 1, i, path); + else if (*((void **)((char *)node + OFFSET(maple_range_64_slot)) + i)) { + sprintf(path + len, "/%d", i); + do_mt_node(mt, mt_slot(mt, (void **)((char *)node + OFFSET(maple_range_64_slot)), i), + first, last, depth + 1, path); + } + + if (last == max) + break; + if (last > max) { + fprintf(fp, "node %p last (%lu) > max (%lu) at pivot %d!\n", + node, last, max, i); + break; + } + first = last + 1; + } +} + +static void do_mt_arange64(const struct maple_tree *mt, void *entry, + unsigned long min, unsigned long max, unsigned int depth, + char *path) +{ + struct maple_node *m_node = mte_to_node(entry); + unsigned char tmp_node[MAPLE_BUFSIZE]; + bool leaf = mte_is_leaf(entry); + unsigned long first = min, last; + int i; + int len = strlen(path); + + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + readmem((ulonglong)m_node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mt_dump_arange64 read maple_node", FAULT_ON_ERROR); + + struct maple_arange_64 *node = (struct maple_arange_64 *) + (tmp_node + OFFSET(maple_node_ma64)); + + if (cmd_tree_info.td) { + if (cmd_tree_info.td->flags & TREE_STRUCT_VERBOSE) { + dump_mt_arange64(node); + } + if (cmd_tree_info.td->flags & TREE_POSITION_DISPLAY) + fprintf(fp, "%.*s index: %ld position: %s\n", + depth * 2, spaces, cmd_tree_info.index++, path); + } + + for (i = 0; i < mt_slots[maple_arange_64]; i++) { + last = max; + + if (i < (mt_slots[maple_arange_64] - 1)) + last = *((unsigned long *)((char *)node + OFFSET(maple_arange_64_pivot)) + i); + else if (! *((void **)((char *)node + OFFSET(maple_arange_64_slot)) + i)) + break; + if (last == 0 && i > 0) + break; + + if (leaf) + do_mt_entry(mt_slot(mt, (void **)((char *)node + OFFSET(maple_arange_64_slot)), i), + first, last, depth + 1, i, path); + else if (*((void **)((char *)node + OFFSET(maple_arange_64_slot)) + i)) { + sprintf(path + len, "/%d", i); + do_mt_node(mt, mt_slot(mt, (void **)((char *)node + OFFSET(maple_arange_64_slot)), i), + first, last, depth + 1, path); + } + + if (last == max) + break; + if (last > max) { + fprintf(fp, "node %p last (%lu) > max (%lu) at pivot %d!\n", + node, last, max, i); + break; + } + first = last + 1; + } +} + +static void do_mt_entry(void *entry, unsigned long min, unsigned long max, + unsigned int depth, unsigned int index, char *path) +{ + int print_radix = 0, i; + static struct req_entry **e = NULL; + + if (!cmd_tree_info.td) + return; + + if (!cmd_tree_info.td->count && cmd_tree_info.td->structname_args) { + /* + * Retrieve all members' info only once (count == 0) + * After last iteration all memory will be freed up + */ + e = (struct req_entry **)GETBUF(sizeof(*e) * cmd_tree_info.td->structname_args); + for (i = 0; i < cmd_tree_info.td->structname_args; i++) + e[i] = fill_member_offsets(cmd_tree_info.td->structname[i]); + } + + cmd_tree_info.td->count++; + + if (cmd_tree_info.td->flags & TREE_STRUCT_VERBOSE) { + dump_mt_entry(entry, min, max, depth); + } else if (cmd_tree_info.td->flags & VERBOSE) + fprintf(fp, "%.*s%lx\n", depth * 2, spaces, (ulong)entry); + if (cmd_tree_info.td->flags & TREE_POSITION_DISPLAY) + fprintf(fp, "%.*s index: %ld position: %s/%u\n", + depth * 2, spaces, cmd_tree_info.index++, path, index); + + if (cmd_tree_info.td->structname) { + if (cmd_tree_info.td->flags & TREE_STRUCT_RADIX_10) + print_radix = 10; + else if (cmd_tree_info.td->flags & TREE_STRUCT_RADIX_16) + print_radix = 16; + else + print_radix = 0; + + for (i = 0; i < cmd_tree_info.td->structname_args; i++) { + switch (count_chars(cmd_tree_info.td->structname[i], '.')) { + case 0: + dump_struct(cmd_tree_info.td->structname[i], + (ulong)entry, print_radix); + break; + default: + if (cmd_tree_info.td->flags & TREE_PARSE_MEMBER) + dump_struct_members_for_tree(cmd_tree_info.td, i, (ulong)entry); + else if (cmd_tree_info.td->flags & TREE_READ_MEMBER) + dump_struct_members_fast(e[i], print_radix, (ulong)entry); + break; + } + } + } +} + +static void do_mt_node(const struct maple_tree *mt, void *entry, + unsigned long min, unsigned long max, unsigned int depth, + char *path) +{ + struct maple_node *node = mte_to_node(entry); + unsigned int type = mte_node_type(entry); + unsigned int i; + char tmp_node[MAPLE_BUFSIZE]; + + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mt_dump_node read maple_node", FAULT_ON_ERROR); + + if (cmd_tree_info.td) { + if (cmd_tree_info.td->flags & TREE_STRUCT_VERBOSE) { + dump_mt_node(node, tmp_node, type, min, max, depth); + } else if (cmd_tree_info.td->flags & VERBOSE) + fprintf(fp, "%.*s%lx\n", depth * 2, spaces, (ulong)entry); + } + + switch (type) { + case maple_dense: + if (cmd_tree_info.td && + cmd_tree_info.td->flags & TREE_POSITION_DISPLAY) + fprintf(fp, "%.*s index: %ld position: %s\n", + depth * 2, spaces, cmd_tree_info.index++, path); + for (i = 0; i < mt_slots[maple_dense]; i++) { + if (min + i > max) + fprintf(fp, "OUT OF RANGE: "); + do_mt_entry(mt_slot(mt, (void **)(tmp_node + OFFSET(maple_node_slot)), i), + min + i, min + i, depth, i, path); + } + break; + case maple_leaf_64: + case maple_range_64: + do_mt_range64(mt, entry, min, max, depth, path); + break; + case maple_arange_64: + do_mt_arange64(mt, entry, min, max, depth, path); + break; + default: + fprintf(fp, " UNKNOWN TYPE\n"); + } +} + +static int do_maple_tree_traverse(ulong ptr, int is_root) +{ + char path[BUFSIZE] = {0}; + unsigned char tmp_tree[MAPLE_BUFSIZE]; + void *entry; + + assert(SIZE(maple_tree_struct) <= MAPLE_BUFSIZE); + + if (!is_root) { + strcpy(path, "direct"); + do_mt_node(NULL, (void *)ptr, 0, + mt_max[mte_node_type((struct maple_enode *)ptr)], 0, path); + } else { + readmem((ulonglong)ptr, KVADDR, tmp_tree, SIZE(maple_tree_struct), + "mt_dump read maple_tree", FAULT_ON_ERROR); + entry = *(void **)(tmp_tree + OFFSET(maple_tree_ma_root)); + + if (cmd_tree_info.td && + cmd_tree_info.td->flags & TREE_STRUCT_VERBOSE) { + fprintf(fp, "maple_tree(%lx) flags %X, height %u root %p\n\n", + ptr, *(unsigned int *)(tmp_tree + OFFSET(maple_tree_ma_flags)), + mt_height((struct maple_tree *)tmp_tree), entry); + } + + if (!xa_is_node(entry)) + do_mt_entry(entry, 0, 0, 0, 0, path); + else if (entry) { + strcpy(path, "root"); + do_mt_node((struct maple_tree *)tmp_tree, entry, 0, + mt_max[mte_node_type(entry)], 0, path); + } + } + return 0; +} + +int do_mptree(struct tree_data *td) +{ + int is_root = !(td->flags & TREE_NODE_POINTER); + + memset(&cmd_tree_info, 0, sizeof(cmd_tree_info)); + cmd_tree_info.td = td; + do_maple_tree_traverse(td->start, is_root); + + return 0; +} + /***********************************************/ void maple_init(void) { @@ -810,14 +1187,17 @@ void maple_init(void) MEMBER_OFFSET_INIT(maple_arange_64_parent, "maple_arange_64", "parent"); MEMBER_OFFSET_INIT(maple_arange_64_pivot, "maple_arange_64", "pivot"); MEMBER_OFFSET_INIT(maple_arange_64_slot, "maple_arange_64", "slot"); + MEMBER_OFFSET_INIT(maple_arange_64_gap, "maple_arange_64", "gap"); MEMBER_OFFSET_INIT(maple_arange_64_meta, "maple_arange_64", "meta"); MEMBER_OFFSET_INIT(maple_range_64_parent, "maple_range_64", "parent"); MEMBER_OFFSET_INIT(maple_range_64_pivot, "maple_range_64", "pivot"); MEMBER_OFFSET_INIT(maple_range_64_slot, "maple_range_64", "slot"); + MEMBER_OFFSET_INIT(maple_range_64_pad, "maple_range_64", "pad"); MEMBER_OFFSET_INIT(maple_range_64_meta, "maple_range_64", "meta"); MEMBER_OFFSET_INIT(maple_metadata_end, "maple_metadata", "end"); + MEMBER_OFFSET_INIT(maple_metadata_gap, "maple_metadata", "gap"); array_len = get_array_length("mt_slots", NULL, sizeof(char)); mt_slots = calloc(array_len, sizeof(char)); @@ -830,4 +1210,9 @@ void maple_init(void) readmem(symbol_value("mt_pivots"), KVADDR, mt_pivots, array_len * sizeof(char), "maple_init read mt_pivots", FAULT_ON_ERROR); + + mt_max[maple_dense] = mt_slots[maple_dense]; + mt_max[maple_leaf_64] = ULONG_MAX; + mt_max[maple_range_64] = ULONG_MAX; + mt_max[maple_arange_64] = ULONG_MAX; } \ No newline at end of file diff --git a/tools.c b/tools.c index 39306c1..3cb93c1 100644 --- a/tools.c +++ b/tools.c @@ -30,7 +30,7 @@ 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 dump_struct_members_for_tree(struct tree_data *, int, ulong); +void dump_struct_members_for_tree(struct tree_data *, int, ulong); struct req_entry { char *arg, *name, **member; @@ -40,8 +40,8 @@ struct req_entry { }; static void print_value(struct req_entry *, unsigned int, ulong, unsigned int); -static struct req_entry *fill_member_offsets(char *); -static void dump_struct_members_fast(struct req_entry *, int, ulong); +struct req_entry *fill_member_offsets(char *); +void dump_struct_members_fast(struct req_entry *, int, ulong); FILE * set_error(char *target) @@ -3666,7 +3666,7 @@ dump_struct_members_fast(struct req_entry *e, int radix, ulong p) } } -static struct req_entry * +struct req_entry * fill_member_offsets(char *arg) { int j; @@ -4307,6 +4307,7 @@ dump_struct_members(struct list_data *ld, int idx, ulong next) #define RADIXTREE_REQUEST (0x1) #define RBTREE_REQUEST (0x2) #define XARRAY_REQUEST (0x4) +#define MAPLE_REQUEST (0x8) void cmd_tree() @@ -4324,11 +4325,11 @@ cmd_tree() td = &tree_data; BZERO(td, sizeof(struct tree_data)); - while ((c = getopt(argcnt, args, "xdt:r:o:s:S:plN")) != EOF) { + while ((c = getopt(argcnt, args, "xdt:r:o:s:S:plNv")) != EOF) { switch (c) { case 't': - if (type_flag & (RADIXTREE_REQUEST|RBTREE_REQUEST|XARRAY_REQUEST)) { + if (type_flag & (RADIXTREE_REQUEST|RBTREE_REQUEST|XARRAY_REQUEST|MAPLE_REQUEST)) { error(INFO, "multiple tree types may not be entered\n"); cmd_usage(pc->curcmd, SYNOPSIS); } @@ -4342,6 +4343,8 @@ cmd_tree() type_flag = RBTREE_REQUEST; else if (STRNEQ(optarg, "x")) type_flag = XARRAY_REQUEST; + else if (STRNEQ(optarg, "m")) + type_flag = MAPLE_REQUEST; else { error(INFO, "invalid tree type: %s\n", optarg); cmd_usage(pc->curcmd, SYNOPSIS); @@ -4417,6 +4420,9 @@ cmd_tree() "-d and -x are mutually exclusive\n"); td->flags |= TREE_STRUCT_RADIX_10; break; + case 'v': + td->flags |= TREE_STRUCT_VERBOSE; + break; default: argerrs++; break; @@ -4532,6 +4538,8 @@ next_arg: do_rdtree(td); else if (type_flag & XARRAY_REQUEST) do_xatree(td); + else if (type_flag & MAPLE_REQUEST) + do_mptree(td); else do_rbtree(td); hq_close(); -- 2.33.1