7:38 a.m.
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>
---
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