There are 2 ways to iterate vm_area_struct: 1) by rbtree, aka vma.vm_rb; 2) by linked list, aka vma.vm_prev/next. However for linux maple tree patch[1][2], vm_rb and vm_prev/next are removed from vm_area_struct. For memory.c:vm_area_dump of crash, it mainly uses linked list as a way of vma iteration, which will not work for this case. So maple tree iteration need to be ported to crash. For crash, currently it only iteratively read the maple tree, no more rcu safe or maple tree modification features needed. So we only port a subset of kernel maple tree features. In addition, we need to modify the ported kernel source code, making it compatible with crash. The formal crash way of vmcore struct member resolving is: readmem(node, KVADDR, buf, SIZE(buf), "", flag); return buf + OFFSET(member); which is the reimplementation of kernel way of member resolving: return node->member; The 1st one is arch independent, it uses gdb to resolve the OFFSET of members, so crash don't need to know what the inside of the struct is, even if the struct changes for new kernel version. The 2nd one is arch dependent, the struct need to be ported to crash, and the OFFSET of members may differ between crash and kernel due to padding/ alignment or optimization reasons. This patch deals with the 2 issues: 1) Poring for_each_vma() macro, and all its dependencies from kernel source[3] to crash, to enable crash maple tree vma iteration, 2) adapting the ported code with crash. [1]: https://github.com/oracle/linux-uek/commit/d19703645b80abe35dff1a88449d07... [2]: https://github.com/oracle/linux-uek/commit/91dee01f1ebb6b6587463b6ee6f7bb... [3]: https://github.com/oracle/linux-uek, maple/mainline branch Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; --- Makefile | 10 +- defs.h | 19 ++ maple_tree.c | 833 +++++++++++++++++++++++++++++++++++++++++++++++++++ maple_tree.h | 214 +++++++++++++ 4 files changed, 1073 insertions(+), 3 deletions(-) create mode 100644 maple_tree.c create mode 100644 maple_tree.h diff --git a/Makefile b/Makefile index 79aef17..6f19b77 100644 --- a/Makefile +++ b/Makefile @@ -59,6 +59,7 @@ IBM_HFILES=ibm_common.h SADUMP_HFILES=sadump.h UNWIND_HFILES=unwind.h unwind_i.h rse.h unwind_x86.h unwind_x86_64.h VMWARE_HFILES=vmware_vmss.h +MAPLE_TREE_HFILES=maple_tree.h CFILES=main.c tools.c global_data.c memory.c filesys.c help.c task.c \ kernel.c test.c gdb_interface.c configure.c net.c dev.c bpf.c \ @@ -73,12 +74,12 @@ CFILES=main.c tools.c global_data.c memory.c filesys.c help.c task.c \ xen_hyper.c xen_hyper_command.c xen_hyper_global_data.c \ xen_hyper_dump_tables.c kvmdump.c qemu.c qemu-load.c sadump.c ipcs.c \ ramdump.c vmware_vmss.c vmware_guestdump.c \ - xen_dom0.c kaslr_helper.c sbitmap.c + xen_dom0.c kaslr_helper.c sbitmap.c maple_tree.c SOURCE_FILES=${CFILES} ${GENERIC_HFILES} ${MCORE_HFILES} \ ${REDHAT_CFILES} ${REDHAT_HFILES} ${UNWIND_HFILES} \ ${LKCD_DUMP_HFILES} ${LKCD_TRACE_HFILES} ${LKCD_OBSOLETE_HFILES}\ - ${IBM_HFILES} ${SADUMP_HFILES} ${VMWARE_HFILES} + ${IBM_HFILES} ${SADUMP_HFILES} ${VMWARE_HFILES} ${MAPLE_TREE_HFILES} OBJECT_FILES=main.o tools.o global_data.o memory.o filesys.o help.o task.o \ build_data.o kernel.o test.o gdb_interface.o net.o dev.o bpf.o \ @@ -93,7 +94,7 @@ OBJECT_FILES=main.o tools.o global_data.o memory.o filesys.o help.o task.o \ xen_hyper.o xen_hyper_command.o xen_hyper_global_data.o \ xen_hyper_dump_tables.o kvmdump.o qemu.o qemu-load.o sadump.o ipcs.o \ ramdump.o vmware_vmss.o vmware_guestdump.o \ - xen_dom0.o kaslr_helper.o sbitmap.o + xen_dom0.o kaslr_helper.o sbitmap.o maple_tree.o MEMORY_DRIVER_FILES=memory_driver/Makefile memory_driver/crash.c memory_driver/README @@ -536,6 +537,9 @@ kaslr_helper.o: ${GENERIC_HFILES} kaslr_helper.c bpf.o: ${GENERIC_HFILES} bpf.c ${CC} -c ${CRASH_CFLAGS} bpf.c ${WARNING_OPTIONS} ${WARNING_ERROR} +maple_tree.o: ${GENERIC_HFILES} ${MAPLE_TREE_HFILES} maple_tree.c + ${CC} -c ${CRASH_CFLAGS} maple_tree.c ${WARNING_OPTIONS} ${WARNING_ERROR} + ${PROGRAM}: force @$(MAKE) all diff --git a/defs.h b/defs.h index afdcf6c..2978cec 100644 --- a/defs.h +++ b/defs.h @@ -2181,6 +2181,22 @@ struct offset_table { /* stash of commonly-used offsets */ long blk_mq_tags_nr_reserved_tags; long blk_mq_tags_rqs; long request_queue_hctx_table; + long mm_struct_mm_mt; + long maple_tree_ma_root; + long maple_tree_ma_flags; + long maple_node_parent; + long maple_node_ma64; + long maple_node_mr64; + long maple_node_slot; + long maple_arange_64_parent; + long maple_arange_64_pivot; + long maple_arange_64_slot; + long maple_arange_64_meta; + long maple_range_64_parent; + long maple_range_64_pivot; + long maple_range_64_slot; + long maple_range_64_meta; + long maple_metadata_end; }; struct size_table { /* stash of commonly-used sizes */ @@ -2351,6 +2367,8 @@ struct size_table { /* stash of commonly-used sizes */ long sbitmap_queue; long sbq_wait_state; long blk_mq_tags; + long maple_tree_struct; + long maple_node_struct; }; struct array_table { @@ -5557,6 +5575,7 @@ int file_dump(ulong, ulong, ulong, int, int); int same_file(char *, char *); int cleanup_memory_driver(void); +void maple_init(void); /* * help.c diff --git a/maple_tree.c b/maple_tree.c new file mode 100644 index 0000000..058b769 --- /dev/null +++ b/maple_tree.c @@ -0,0 +1,833 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * Maple Tree implementation + * Copyright (c) 2018-2022 Oracle Corporation + * Authors: Liam R. Howlett <Liam.Howlett(a)oracle.com&gt; + * Matthew Wilcox <willy(a)infradead.org&gt; + * + * The following are copied and modified from lib/maple_tree.c + */ + +#include "maple_tree.h" +#include "defs.h" + +/* Bit 1 indicates the root is a node */ +#define MAPLE_ROOT_NODE 0x02 +/* maple_type stored bit 3-6 */ +#define MAPLE_ENODE_TYPE_SHIFT 0x03 +/* Bit 2 means a NULL somewhere below */ +#define MAPLE_ENODE_NULL 0x04 + +#define MA_ROOT_PARENT 1 + +#define MAPLE_PARENT_ROOT 0x01 + +#define MAPLE_PARENT_SLOT_SHIFT 0x03 +#define MAPLE_PARENT_SLOT_MASK 0xF8 + +#define MAPLE_PARENT_16B_SLOT_SHIFT 0x02 +#define MAPLE_PARENT_16B_SLOT_MASK 0xFC + +#define MAPLE_PARENT_RANGE64 0x06 +#define MAPLE_PARENT_RANGE32 0x04 +#define MAPLE_PARENT_NOT_RANGE16 0x02 + +unsigned char *mt_slots = NULL; +unsigned char *mt_pivots = NULL; + +#define MAPLE_BUFSIZE 512 + +#define ma_parent_ptr(x) ((struct maple_pnode *)(x)) +#define ma_enode_ptr(x) ((struct maple_enode *)(x)) + +static inline bool mas_is_ptr(struct ma_state *mas) +{ + return mas->node == MAS_ROOT; +} + +static inline bool mas_is_start(struct ma_state *mas) +{ + return mas->node == MAS_START; +} + +static inline void *mte_safe_root(const struct maple_enode *node) +{ + return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE); +} + +static inline struct maple_node *mte_to_node(const struct maple_enode *entry) +{ + return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK); +} + +static inline enum maple_type mte_node_type(const struct maple_enode *entry) +{ + return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & + MAPLE_NODE_TYPE_MASK; +} + +static inline void *mas_root(struct ma_state *mas) +{ + char tree[MAPLE_BUFSIZE]; + assert(SIZE(maple_tree_struct) <= MAPLE_BUFSIZE); + + readmem((ulonglong)(mas->tree), KVADDR, tree, SIZE(maple_tree_struct), + "mas_root read maple_tree", FAULT_ON_ERROR); + return *(void **)(tree + OFFSET(maple_tree_ma_root)); +} + +static inline struct maple_enode *mas_start(struct ma_state *mas) +{ + if (mas_is_start(mas)) { + struct maple_enode *root; + + mas->node = MAS_NONE; + mas->min = 0; + mas->max = ULONG_MAX; + mas->depth = 0; + mas->offset = 0; + + root = mas_root(mas); + /* Tree with nodes */ + if (xa_is_node(root)) { + mas->node = mte_safe_root(root); + return NULL; + } + + /* empty tree */ + if (!root) { + // mas->offset = MAPLE_NODE_SLOTS; + mas->offset = mt_slots[maple_dense]; + return NULL; + } + + /* Single entry tree */ + mas->node = MAS_ROOT; + // mas->offset = MAPLE_NODE_SLOTS; + mas->offset = mt_slots[maple_dense]; + + /* Single entry tree. */ + if (mas->index > 0) + return NULL; + + return root; + } + + return NULL; +} + +static inline unsigned long *ma_pivots(struct maple_node *node, + enum maple_type type) +{ + switch (type) { + case maple_arange_64: + return (unsigned long *)((char *)node + OFFSET(maple_node_ma64) + + OFFSET(maple_arange_64_pivot)); + case maple_range_64: + case maple_leaf_64: + return (unsigned long *)((char *)node + OFFSET(maple_node_mr64) + + OFFSET(maple_range_64_pivot)); + case maple_dense: + return NULL; + } + return NULL; +} + +static inline struct maple_metadata *ma_meta(struct maple_node *mn, + enum maple_type mt) +{ + switch (mt) { + case maple_arange_64: + return (struct maple_metadata *)( + (char *)mn + OFFSET(maple_node_ma64) + + OFFSET(maple_arange_64_meta)); + default: + return (struct maple_metadata *)( + (char *)mn + OFFSET(maple_node_mr64) + + OFFSET(maple_range_64_meta)); + } +} + +static inline unsigned char ma_meta_end(struct maple_node *mn, + enum maple_type mt) +{ + struct maple_metadata *meta = ma_meta(mn, mt); + + return *((char *)meta + OFFSET(maple_metadata_end)); +} + +static inline unsigned char ma_data_end(struct maple_node *node, + enum maple_type type, + unsigned long *pivots, + unsigned long max) +{ + unsigned char offset; + + if (type == maple_arange_64) + return ma_meta_end(node, type); + + offset = mt_pivots[type] - 1; + if (!pivots[offset]) + return ma_meta_end(node, type); + + if (pivots[offset] == max) + return offset; + + return mt_pivots[type]; +} + +static inline bool ma_dead_node(const struct maple_node *node, + const struct maple_node *orig_node) +{ + struct maple_node *parent = (struct maple_node *) + (*(unsigned long *)((char *)node + + OFFSET(maple_node_parent)) + & ~MAPLE_NODE_MASK); + return (parent == orig_node); +} + +static inline void **ma_slots(struct maple_node *mn, enum maple_type mt) +{ + switch (mt) { + default: + case maple_arange_64: + return (void **)((char *)mn + OFFSET(maple_node_ma64) + + OFFSET(maple_arange_64_slot)); + case maple_range_64: + case maple_leaf_64: + return (void **)((char *)mn + OFFSET(maple_node_mr64) + + OFFSET(maple_range_64_slot)); + case maple_dense: + return (void **)((char *)mn + OFFSET(maple_node_slot)); + } +} + +static inline void *mt_slot(const struct maple_tree *mt, + void **slots, unsigned char offset) +{ + return slots[offset]; +} + +static inline bool ma_is_leaf(const enum maple_type type) +{ + return type < maple_range_64; +} + +static inline void *mtree_range_walk(struct ma_state *mas) +{ + unsigned long *pivots; + unsigned char offset; + struct maple_node *node; + struct maple_enode *next, *last; + enum maple_type type; + void **slots; + unsigned char end; + unsigned long max, min; + unsigned long prev_max, prev_min; + + char tmp_node[MAPLE_BUFSIZE]; + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + last = next = mas->node; + prev_min = min = mas->min; + max = mas->max; + do { + offset = 0; + last = next; + node = mte_to_node(next); + type = mte_node_type(next); + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mtree_range_walk read maple_node", FAULT_ON_ERROR); + pivots = ma_pivots((struct maple_node *)tmp_node, type); + end = ma_data_end((struct maple_node *)tmp_node, type, pivots, max); + if (ma_dead_node((struct maple_node *)tmp_node, node)) + goto dead_node; + + if (pivots[offset] >= mas->index) { + prev_max = max; + prev_min = min; + max = pivots[offset]; + goto next; + } + + do { + offset++; + } while ((offset < end) && (pivots[offset] < mas->index)); + + prev_min = min; + min = pivots[offset - 1] + 1; + prev_max = max; + if (offset < end && pivots[offset]) + max = pivots[offset]; + +next: + slots = ma_slots((struct maple_node *)tmp_node, type); + next = mt_slot(mas->tree, slots, offset); + if (ma_dead_node((struct maple_node *)tmp_node, node)) + goto dead_node; + } while (!ma_is_leaf(type)); + + mas->offset = offset; + mas->index = min; + mas->last = max; + mas->min = prev_min; + mas->max = prev_max; + mas->node = last; + return (void *) next; + +dead_node: + mas_reset(mas); + return NULL; +} + +static inline void *mas_state_walk(struct ma_state *mas) +{ + void *entry; + + entry = mas_start(mas); + if (mas_is_none(mas)) + return NULL; + + if (mas_is_ptr(mas)) + return entry; + + return mtree_range_walk(mas); +} + +static inline bool mas_searchable(struct ma_state *mas) +{ + if (mas_is_none(mas)) + return false; + + if (mas_is_ptr(mas)) + return false; + + return true; +} + +static inline struct maple_node *mas_mn(const struct ma_state *mas) +{ + return mte_to_node(mas->node); +} + +static inline unsigned long +mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) +{ + if (offset) + return pivots[offset - 1] + 1; + + return mas->min; +} + +static inline void *mas_slot(struct ma_state *mas, void **slots, + unsigned char offset) +{ + return mt_slot(mas->tree, slots, offset); +} + +static inline unsigned long +mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots, + unsigned char piv, enum maple_type type) +{ + if (piv >= mt_pivots[type]) + return mas->max; + + return pivots[piv]; +} + +static inline void *mas_next_nentry(struct ma_state *mas, + struct maple_node *node, unsigned long max, + enum maple_type type, struct maple_node *orig_node) +{ + unsigned char count; + unsigned long pivot; + unsigned long *pivots; + void **slots; + void *entry; + + if (mas->last == mas->max) { + mas->index = mas->max; + return NULL; + } + + pivots = ma_pivots(node, type); + slots = ma_slots(node, type); + mas->index = mas_safe_min(mas, pivots, mas->offset); + if (ma_dead_node(node, orig_node)) + return NULL; + + if (mas->index > max) + return NULL; + + count = ma_data_end(node, type, pivots, mas->max); + if (mas->offset > count) + return NULL; + + while (mas->offset < count) { + pivot = pivots[mas->offset]; + entry = mas_slot(mas, slots, mas->offset); + if (ma_dead_node(node, orig_node)) + return NULL; + + if (entry) + goto found; + + if (pivot >= max) + return NULL; + + mas->index = pivot + 1; + mas->offset++; + } + + if (mas->index > mas->max) { + mas->index = mas->last; + return NULL; + } + + pivot = mas_safe_pivot(mas, pivots, mas->offset, type); + entry = mas_slot(mas, slots, mas->offset); + if (ma_dead_node(node, orig_node)) + return NULL; + + if (!pivot) + return NULL; + + if (!entry) + return NULL; + +found: + mas->last = pivot; + return entry; +} + +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) +{ + +retry: + mas_set(mas, index); + mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; + + return; +} + +static inline bool ma_is_root(struct maple_node *node) +{ + return (*(unsigned long *)((char *)node + + OFFSET(maple_node_parent)) + & MA_ROOT_PARENT); +} + +static inline struct maple_node *mte_parent(const struct maple_node *node) +{ + return (void *)(*(unsigned long *)((char *)node + + OFFSET(maple_node_parent)) + & ~MAPLE_NODE_MASK); +} + +static inline unsigned long mte_parent_slot_mask(unsigned long parent) +{ + /* Note bit 1 == 0 means 16B */ + if (parent & MAPLE_PARENT_NOT_RANGE16) + return MAPLE_PARENT_SLOT_MASK; + + return MAPLE_PARENT_16B_SLOT_MASK; +} + +static inline bool mt_is_alloc(struct maple_tree *mt) +{ + return (*(unsigned int *)((char *)mt + + OFFSET(maple_tree_ma_flags)) + & MT_FLAGS_ALLOC_RANGE); +} + +static inline +enum maple_type mte_parent_enum(struct maple_enode *p_enode, + struct maple_tree *mt) +{ + unsigned long p_type; + char tmp_tree[MAPLE_BUFSIZE]; + assert(SIZE(maple_tree_struct) <= MAPLE_BUFSIZE); + + p_type = (unsigned long)p_enode; + if (p_type & MAPLE_PARENT_ROOT) + return 0; /* Validated in the caller. */ + + p_type &= MAPLE_NODE_MASK; + p_type = p_type & ~(MAPLE_PARENT_ROOT | mte_parent_slot_mask(p_type)); + + switch (p_type) { + case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */ + readmem((ulonglong)mt, KVADDR, tmp_tree, SIZE(maple_tree_struct), + "mte_parent_enum read maple_tree", FAULT_ON_ERROR); + if (mt_is_alloc((struct maple_tree *)tmp_tree)) + return maple_arange_64; + return maple_range_64; + } + + return 0; +} + +static inline +enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_node *node) +{ + return mte_parent_enum(ma_enode_ptr(*(struct maple_pnode **) + ((char *)node + OFFSET(maple_node_parent))), + mas->tree); +} + +static inline unsigned long mte_parent_shift(unsigned long parent) +{ + /* Note bit 1 == 0 means 16B */ + if (parent & MAPLE_PARENT_NOT_RANGE16) + return MAPLE_PARENT_SLOT_SHIFT; + + return MAPLE_PARENT_16B_SLOT_SHIFT; +} + +static inline unsigned int mte_parent_slot(const struct maple_node *node) +{ + unsigned long val = *(unsigned long *)((char *)node + + OFFSET(maple_node_parent)); + + /* Root. */ + if (val & 1) + return 0; + + /* + * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost + * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT + */ + return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val); +} + +static inline struct maple_enode *mt_mk_node(const struct maple_node *node, + enum maple_type type) +{ + return (void *)((unsigned long)node | + (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL); +} + +static inline bool mte_is_root(struct maple_node *node) +{ + return ma_is_root(node); +} + +static int mas_ascend(struct ma_state *mas) +{ + struct maple_enode *p_enode; /* parent enode. */ + struct maple_enode *a_enode; /* ancestor enode. */ + struct maple_node *a_node; /* ancestor node. */ + struct maple_node *p_node; /* parent node. */ + unsigned char a_slot; + enum maple_type a_type; + unsigned long min, max; + unsigned long *pivots; + unsigned char offset; + bool set_max = false, set_min = false; + + char tmp_node[MAPLE_BUFSIZE]; + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + a_node = mas_mn(mas); + readmem((ulonglong)a_node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_ascend read maple_node", FAULT_ON_ERROR); + if (ma_is_root((struct maple_node *)tmp_node)) { + mas->offset = 0; + return 0; + } + + readmem((ulonglong)(mte_to_node(mas->node)), KVADDR, tmp_node, + SIZE(maple_node_struct), "mas_ascend read maple_node", FAULT_ON_ERROR); + p_node = mte_parent((struct maple_node *)tmp_node); + if (a_node == p_node) + return 1; + a_type = mas_parent_enum(mas, (struct maple_node *)tmp_node); + offset = mte_parent_slot((struct maple_node *)tmp_node); + a_enode = mt_mk_node(p_node, a_type); + + /* Check to make sure all parent information is still accurate */ + if (p_node != mte_parent((struct maple_node *)tmp_node)) + return 1; + + mas->node = a_enode; + mas->offset = offset; + + readmem((ulonglong)(mte_to_node(a_enode)), KVADDR, tmp_node, + SIZE(maple_node_struct), "mas_ascend read maple_node", FAULT_ON_ERROR); + if (mte_is_root((struct maple_node *)tmp_node)) { + mas->max = ULONG_MAX; + mas->min = 0; + return 0; + } + + min = 0; + max = ULONG_MAX; + do { + p_enode = a_enode; + readmem((ulonglong)(mte_to_node(p_enode)), KVADDR, tmp_node, + SIZE(maple_node_struct), + "mas_ascend read maple_node", FAULT_ON_ERROR); + a_type = mas_parent_enum(mas, (struct maple_node *)tmp_node); + a_node = mte_parent((struct maple_node *)tmp_node); + a_slot = mte_parent_slot((struct maple_node *)tmp_node); + readmem((ulonglong)a_node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_ascend read maple_node", FAULT_ON_ERROR); + pivots = ma_pivots((struct maple_node *)tmp_node, a_type); + a_enode = mt_mk_node((struct maple_node *)tmp_node, a_type); + + if (!set_min && a_slot) { + set_min = true; + min = pivots[a_slot - 1] + 1; + } + + if (!set_max && a_slot < mt_pivots[a_type]) { + set_max = true; + max = pivots[a_slot]; + } + + if (ma_dead_node((struct maple_node *)tmp_node, a_node)) + return 1; + + if (ma_is_root((struct maple_node *)tmp_node)) + break; + + } while (!set_min || !set_max); + + mas->max = max; + mas->min = min; + return 0; +} + +static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, + unsigned long max) +{ + unsigned long min, pivot; + unsigned long *pivots; + struct maple_enode *enode; + int level = 0; + unsigned char offset; + enum maple_type mt; + void **slots; + + char tmp_node[MAPLE_BUFSIZE]; + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + if (mas->max >= max) + goto no_entry; + + level = 0; + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_next_node read maple_node", FAULT_ON_ERROR); + do { + if (ma_is_root((struct maple_node *)tmp_node)) + goto no_entry; + + min = mas->max + 1; + if (min > max) + goto no_entry; + + if (mas_ascend(mas)) + return 1; + + offset = mas->offset; + level++; + node = mas_mn(mas); + mt = mte_node_type(mas->node); + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_next_node read maple_node", FAULT_ON_ERROR); + pivots = ma_pivots((struct maple_node *)tmp_node, mt); + } while (offset == ma_data_end((struct maple_node *)tmp_node, mt, pivots, mas->max)); + + slots = ma_slots((struct maple_node *)tmp_node, mt); + pivot = mas_safe_pivot(mas, pivots, ++offset, mt); + while (level > 1) { + /* Descend, if necessary */ + enode = mas_slot(mas, slots, offset); + if (ma_dead_node((struct maple_node *)tmp_node, node)) + return 1; + + mas->node = enode; + level--; + node = mas_mn(mas); + mt = mte_node_type(mas->node); + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_next_node read maple_node", FAULT_ON_ERROR); + slots = ma_slots((struct maple_node *)tmp_node, mt); + pivots = ma_pivots((struct maple_node *)tmp_node, mt); + offset = 0; + pivot = pivots[0]; + } + + enode = mas_slot(mas, slots, offset); + if (ma_dead_node((struct maple_node *)tmp_node, node)) + return 1; + + mas->node = enode; + mas->min = min; + mas->max = pivot; + return 0; + +no_entry: + if (ma_dead_node((struct maple_node *)tmp_node, node)) + return 1; + + mas->node = MAS_NONE; + return 0; +} + +static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) +{ + void *entry = NULL; + struct maple_enode *prev_node; + struct maple_node *node; + unsigned char offset; + unsigned long last; + enum maple_type mt; + + char tmp_node[MAPLE_BUFSIZE]; + assert(SIZE(maple_node_struct) <= MAPLE_BUFSIZE); + + last = mas->last; +retry: + offset = mas->offset; + prev_node = mas->node; + node = mas_mn(mas); + mt = mte_node_type(mas->node); + mas->offset++; + if (mas->offset >= mt_slots[mt]) { + mas->offset = mt_slots[mt] - 1; + goto next_node; + } + + while (!mas_is_none(mas)) { + readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct), + "mas_next_entry read maple_node", FAULT_ON_ERROR); + entry = mas_next_nentry(mas, (struct maple_node *)tmp_node, limit, mt, node); + if (ma_dead_node((struct maple_node *)tmp_node, node)) { + mas_rewalk(mas, last); + goto retry; + } + + if (entry) + return entry; + + if ((mas->index > limit)) + break; + +next_node: + prev_node = mas->node; + offset = mas->offset; + if (mas_next_node(mas, node, limit)) { + mas_rewalk(mas, last); + goto retry; + } + mas->offset = 0; + node = mas_mn(mas); + mt = mte_node_type(mas->node); + } + + mas->index = mas->last = limit; + mas->offset = offset; + mas->node = prev_node; + return NULL; +} + +static void *mas_walk(struct ma_state *mas) +{ + void *entry; + +retry: + entry = mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; + + if (mas_is_ptr(mas)) { + if (!mas->index) { + mas->last = 0; + } else { + mas->index = 1; + mas->last = ULONG_MAX; + } + return entry; + } + + if (mas_is_none(mas)) { + mas->index = 0; + mas->last = ULONG_MAX; + } + + return entry; +} + +void *mas_find(struct ma_state *mas, unsigned long max) +{ + if (mas_is_paused(mas)) { + if (mas->last == ULONG_MAX) { + mas->node = MAS_NONE; + return NULL; + } + mas->node = MAS_START; + mas->index = ++mas->last; + } + + if (mas_is_start(mas)) { + /* First run or continue */ + void *entry; + + if (mas->index > max) + return NULL; + + entry = mas_walk(mas); + if (entry) + return entry; + } + + if (!mas_searchable(mas)) + return NULL; + + /* Retries on dead nodes handled by mas_next_entry */ + return mas_next_entry(mas, max); +} + +/***********************************************/ +void maple_init(void) +{ + int array_len; + + STRUCT_SIZE_INIT(maple_tree_struct, "maple_tree"); + STRUCT_SIZE_INIT(maple_node_struct, "maple_node"); + + MEMBER_OFFSET_INIT(maple_tree_ma_root, "maple_tree", "ma_root"); + MEMBER_OFFSET_INIT(maple_tree_ma_flags, "maple_tree", "ma_flags"); + + MEMBER_OFFSET_INIT(maple_node_parent, "maple_node", "parent"); + MEMBER_OFFSET_INIT(maple_node_ma64, "maple_node", "ma64"); + MEMBER_OFFSET_INIT(maple_node_mr64, "maple_node", "mr64"); + MEMBER_OFFSET_INIT(maple_node_slot, "maple_node", "slot"); + + 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_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_meta, "maple_range_64", "meta"); + + MEMBER_OFFSET_INIT(maple_metadata_end, "maple_metadata", "end"); + + array_len = get_array_length("mt_slots", NULL, sizeof(char)); + mt_slots = calloc(array_len, sizeof(char)); + readmem(symbol_value("mt_slots"), KVADDR, mt_slots, + array_len * sizeof(char), "maple_init read mt_slots", + FAULT_ON_ERROR); + + array_len = get_array_length("mt_pivots", NULL, sizeof(char)); + mt_pivots = calloc(array_len, sizeof(char)); + readmem(symbol_value("mt_pivots"), KVADDR, mt_pivots, + array_len * sizeof(char), "maple_init read mt_pivots", + FAULT_ON_ERROR); +} \ No newline at end of file diff --git a/maple_tree.h b/maple_tree.h new file mode 100644 index 0000000..8b36c29 --- /dev/null +++ b/maple_tree.h @@ -0,0 +1,214 @@ +/* SPDX-License-Identifier: GPL-2.0+ */ +#ifndef _MAPLE_TREE_H +#define _MAPLE_TREE_H +/* + * Maple Tree - An RCU-safe adaptive tree for storing ranges + * Copyright (c) 2018-2022 Oracle + * Authors: Liam R. Howlett <Liam.Howlett(a)Oracle.com&gt; + * Matthew Wilcox <willy(a)infradead.org&gt; + * + * eXtensible Arrays + * Copyright (c) 2017 Microsoft Corporation + * Author: Matthew Wilcox <willy(a)infradead.org&gt; + * + * See Documentation/core-api/xarray.rst for how to use the XArray. + */ +#include <stdbool.h> +#include <limits.h> + +/* + * The following are copied and modified from include/linux/maple_tree.h + * + * Keep the empty struct names for debug purpose of compiler warning. + * And can also keep the function prototypes consistent with kernel's + * corresponding functions. + */ +struct maple_tree { }; +struct maple_metadata { }; +struct maple_range_64 { }; +struct maple_arange_64 { }; +struct maple_alloc { }; +struct maple_node { }; + +struct ma_state { + struct maple_tree *tree; /* The tree we're operating in */ + unsigned long index; /* The index we're operating on - range start */ + unsigned long last; /* The last index we're operating on - range end */ + struct maple_enode *node; /* The node containing this entry */ + unsigned long min; /* The minimum index of this node - implied pivot min */ + unsigned long max; /* The maximum index of this node - implied pivot max */ + struct maple_alloc *alloc; /* Allocated nodes for this operation */ + unsigned char depth; /* depth of tree descent during write */ + unsigned char offset; + unsigned char mas_flags; +}; + +enum maple_type { + maple_dense, + maple_leaf_64, + maple_range_64, + maple_arange_64, +}; + +#define MAS_START ((struct maple_enode *)1UL) +#define MAS_ROOT ((struct maple_enode *)5UL) +#define MAS_NONE ((struct maple_enode *)9UL) +#define MAS_PAUSE ((struct maple_enode *)17UL) +#define MA_ERROR(err) \ + ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) + +#define MA_STATE(name, mt, first, end) \ + struct ma_state name = { \ + .tree = mt, \ + .index = first, \ + .last = end, \ + .node = MAS_START, \ + .min = 0, \ + .max = ULONG_MAX, \ + } + +#define MAPLE_NODE_MASK 255UL + +#define MT_FLAGS_ALLOC_RANGE 0x01 +#define MT_FLAGS_USE_RCU 0x02 +#define MT_FLAGS_HEIGHT_OFFSET 0x02 +#define MT_FLAGS_HEIGHT_MASK 0x7C +#define MT_FLAGS_LOCK_MASK 0x300 +#define MT_FLAGS_LOCK_IRQ 0x100 +#define MT_FLAGS_LOCK_BH 0x200 +#define MT_FLAGS_LOCK_EXTERN 0x300 + +#define MAPLE_HEIGHT_MAX 31 + +#define MAPLE_NODE_TYPE_MASK 0x0F +#define MAPLE_NODE_TYPE_SHIFT 0x03 + +#define MAPLE_RESERVED_RANGE 4096 + +static inline void mas_reset(struct ma_state *mas) +{ + mas->node = MAS_START; +} + +static inline +void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last) +{ + mas->index = start; + mas->last = last; + mas->node = MAS_START; +} + +static inline void mas_set(struct ma_state *mas, unsigned long index) +{ + mas_set_range(mas, index, index); +} + +static inline bool mas_is_none(struct ma_state *mas) +{ + return mas->node == MAS_NONE; +} + +static inline bool mas_is_paused(struct ma_state *mas) +{ + return mas->node == MAS_PAUSE; +} + +/* + * The following are copied and modified from include/linux/xarray.h + */ + +#define MAX_ERRNO 4095 +#define XA_ZERO_ENTRY xa_mk_internal(257) +#define XA_RETRY_ENTRY xa_mk_internal(256) + +static inline void *xa_mk_internal(unsigned long v) +{ + return (void *)((v << 2) | 2); +} + +static inline bool xa_is_internal(const void *entry) +{ + return ((unsigned long)entry & 3) == 2; +} + +static inline bool xa_is_err(const void *entry) +{ + return xa_is_internal(entry) && + entry >= xa_mk_internal(-MAX_ERRNO); +} + +static inline int xa_err(void *entry) +{ + /* xa_to_internal() would not do sign extension. */ + if (xa_is_err(entry)) + return (long)entry >> 2; + return 0; +} + +static inline bool xa_is_node(const void *entry) +{ + return xa_is_internal(entry) && (unsigned long)entry > 4096; +} + +static inline bool xa_is_value(const void *entry) +{ + return (unsigned long)entry & 1; +} + +static inline bool xa_is_zero(const void *entry) +{ + return entry == XA_ZERO_ENTRY; +} + +static inline unsigned long xa_to_internal(const void *entry) +{ + return (unsigned long)entry >> 2; +} + +static inline unsigned long xa_to_value(const void *entry) +{ + return (unsigned long)entry >> 1; +} + +static inline bool xa_is_advanced(const void *entry) +{ + return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY); +} + +/* + * The following are copied and modified from include/linux/mm.h + */ + +struct vma_iterator { + struct ma_state mas; +}; + +#define VMA_ITERATOR(name, mm_mt, addr) \ + struct vma_iterator name = { \ + .mas = { \ + .tree = mm_mt, \ + .index = addr, \ + .node = MAS_START, \ + }, \ + } + +void *mas_find(struct ma_state *, unsigned long); + +static void *vma_find(struct vma_iterator *vmi, unsigned long max) +{ + return mas_find(&vmi->mas, max); +} + + __attribute__((unused)) static void *vma_next(struct vma_iterator *vmi) +{ + /* + * Uses vma_find() to get the first VMA when the iterator starts. + * Calling mas_next() could skip the first entry. + */ + return vma_find(vmi, ULONG_MAX); +} + +#define for_each_vma(vmi, vma) \ + while ((vma = (ulong)vma_next(&(vmi))) != 0) + +#endif /* _MAPLE_TREE_H */ \ No newline at end of file -- 2.33.1

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

On 2022/10/25 21:38, Tao Liu wrote: Nice and interesting option to grasp a tree structure. But could you please align entries flatly and show only valid entries without the -v option? for example, Current: crash> tree -t maple 0xffff8bb820815500 | head ffff8bb809a3681e ffff8bb809a36f0c 0 ffff8bb807d67430 ffff8bb807d66390 ffff8bb807d67d18 ffff8bb807d66be0 ffff8bb807d667b8 ffff8bb807d67008 0 Expected: crash> tree -t maple 0xffff8bb820815500 | head ffff8bb807d67430 ffff8bb807d66390 ffff8bb807d67d18 ffff8bb807d66be0 ffff8bb807d667b8 ffff8bb807d67008 ... The tree command shows like this for the other tree types. It would be better to align with them and easier to process the output with other commands. e.g. rbtree crash> tree -t rbtree 0xffff8fa4a5b8da08 -o vm_area_struct.vm_rb | head ffff8fa5140d4cb0 ffff8fa4c763ee80 ffff8fa4fc48ecb0 ffff8fa50c5d3c18 ffff8fa3f784cd98 ffff8fa51f04d4d8 ffff8fa51f04d3f0 ffff8fa51f04dc18 ffff8fa4be58e3a0 ffff8f9b8931fde8 I think it's good to have the tree-indented output with -v option. Question: Indexes should be printed? IIUC xarray and radix tree have absolute indexes for an entry, e.g. page cache index from the beginning of a file. crash> tree -t xarray -r address_space.i_pages 0xffff8f9cbd778700 -p fffff043b6abf880 index: 738 position: root/11/34 fffff043ad7d9e80 index: 739 position: root/11/35 but I'm not sure whether the maple tree has the same concept.. Maybe index is helpful to count valid entries in a tree. If so, it seems that the maple tree doesn't have entries on internal (non-leaf) nodes, it would be better to skip them at least. I'm still reviewing this patch and the remaining, will comment next week. Thanks, Kazu > > 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();

Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; --- help.c | 45 +++++++++++++++++++++++---------------------- 1 file changed, 23 insertions(+), 22 deletions(-) diff --git a/help.c b/help.c index 99214c1..fbe8a04 100644 --- a/help.c +++ b/help.c @@ -6306,19 +6306,19 @@ NULL char *help_tree[] = { "tree", -"display radix tree, XArray or red-black tree", -"[-t [radix|xarray|rbtree]] [-r offset] [-[s|S] struct[.member[,member]]]\n -[x|d] [-o offset] [-l] [-p] [-N] start", -" This command dumps the contents of a radix tree, an XAarray, or a red-black", -" tree. The arguments are as follows:\n", +"display radix tree, XArray, red-black tree or maple tree", +"[-t [radix|xarray|rbtree|maple]] [-r offset] [-[s|S] struct[.member[,member]]]\n -[x|d] [-o offset] [-l] [-p] [-v] [-N] start", +" This command dumps the contents of a radix tree, an XAarray, a red-black", +" tree, or a maple tree. The arguments are as follows:\n", " -t type The type of tree to dump; the type string can be one of ", -" \"radix\", \"rbtree\", or \"xarray\", or alternatively, \"ra\",", -" \"rb\" or \"x\" are acceptable. If not specified, rbtree is the", -" default type.", +" \"radix\", \"rbtree\", \"xarray\", or \"maple\", or alternatively,", +" \"ra\", \"rb\", \"x\" or \"m\" are acceptable. If not specified,", +" rbtree is the default type.", " -r offset If the \"start\" argument is the address of a data structure that", -" contains an radix_tree_root, xarray or rb_root structure, then this", -" is the offset to that structure member. If the offset is non-zero,", -" then this option is required. The offset may be entered in either", -" of two manners:", +" contains an radix_tree_root, maple_tree_root, xarray or rb_root", +" structure, then this is the offset to that structure member. If the", +" offset is non-zero, then this option is required. The offset may be", +" entered in either of two manners:", " 1. In \"structure.member\" format.", " 2. A number of bytes.", " -o offset For red-black trees only, the offset of the rb_node within its ", @@ -6347,25 +6347,26 @@ char *help_tree[] = { " -p Display the node's position information, showing the relationship", " between it and the root. For red-black trees, a position that", " indicates \"root/l/r\" means that the node is the right child", -" of the left child of the root node. For radix trees and xarrays,", -" the index, the height, and the slot index values are shown with", -" respect to the root.", +" of the left child of the root node. For radix trees, xarrays and", +" maple tree, the index, the height, and the slot index values are", +" shown with respect to the root.", " -x Override default output format with hexadecimal format.", " -d Override default output format with decimal format.", +" -v For maple trees only, showing the contents of each maple tree node.", " ", " The meaning of the \"start\" argument, which can be expressed either in", " hexadecimal format or symbolically, depends upon whether the -N option", " is prepended:", " ", -" start The address of a radix_tree_root, xarray or rb_root structure, or", -" the address of a structure containing the radix_tree_root, xarray", -" or rb_root structure; if the latter, then the \"-r offset\" option", -" must be used if the member offset of the root structure is ", -" non-zero.", +" start The address of a radix_tree_root, maple_tree_root, xarray or rb_root", +" structure, or the address of a structure containing the radix_tree_root,", +" maple_tree_root, xarray or rb_root structure; if the latter, then", +" the \"-r offset\" option must be used if the member offset of the", +" root structure is non-zero.", " ", -" -N start The address of a radix_tree_node, xa_node or rb_node structure,", -" bypassing the radix_tree_root, xarray, or rb_root that points", -" to it.", +" -N start The address of a radix_tree_node, maple_tree_node, xa_node or rb_node", +" structure, bypassing the radix_tree_root, maple_tree_root, xarray,", +" or rb_root that points to it.", "", "\nEXAMPLES", " The vmap_area_root is a standalone rb_root structure. Display the ", -- 2.33.1

On Mon, Nov 7, 2022 at 3:53 PM HAGIO KAZUHITO(萩尾　一仁) <k-hagio-ab(a)nec.com&gt; wrote: Thanks, all get fixed in v3. Thanks, Tao Liu

In the previous patch, a few variables are added to offset_table and size_table, we need to print it out with help cmd. Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; --- symbols.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/symbols.c b/symbols.c index 42c4eb4..cd9bfab 100644 --- a/symbols.c +++ b/symbols.c @@ -10755,6 +10755,44 @@ dump_offset_table(char *spec, ulong makestruct) OFFSET(sbq_wait_state_wait_cnt)); fprintf(fp, " sbq_wait_state_wait: %ld\n", OFFSET(sbq_wait_state_wait)); + fprintf(fp, " mm_struct_mm_mt: %ld\n", + OFFSET(mm_struct_mm_mt)); + fprintf(fp, " maple_tree_ma_root: %ld\n", + OFFSET(maple_tree_ma_root)); + fprintf(fp, " maple_tree_ma_flags: %ld\n", + OFFSET(maple_tree_ma_flags)); + fprintf(fp, " maple_node_parent: %ld\n", + OFFSET(maple_node_parent)); + fprintf(fp, " maple_node_ma64: %ld\n", + OFFSET(maple_node_ma64)); + fprintf(fp, " maple_node_mr64: %ld\n", + OFFSET(maple_node_mr64)); + fprintf(fp, " maple_node_slot: %ld\n", + OFFSET(maple_node_slot)); + fprintf(fp, " maple_arange_64_parent: %ld\n", + OFFSET(maple_arange_64_parent)); + fprintf(fp, " maple_arange_64_pivot: %ld\n", + OFFSET(maple_arange_64_pivot)); + fprintf(fp, " maple_arange_64_slot: %ld\n", + OFFSET(maple_arange_64_slot)); + fprintf(fp, " maple_arange_64_gap: %ld\n", + OFFSET(maple_arange_64_gap)); + fprintf(fp, " maple_arange_64_meta: %ld\n", + OFFSET(maple_arange_64_meta)); + fprintf(fp, " maple_range_64_parent: %ld\n", + OFFSET(maple_range_64_parent)); + fprintf(fp, " maple_range_64_pivot: %ld\n", + OFFSET(maple_range_64_pivot)); + fprintf(fp, " maple_range_64_slot: %ld\n", + OFFSET(maple_range_64_slot)); + fprintf(fp, " maple_range_64_pad: %ld\n", + OFFSET(maple_range_64_pad)); + fprintf(fp, " maple_range_64_meta: %ld\n", + OFFSET(maple_range_64_meta)); + fprintf(fp, " maple_metadata_end: %ld\n", + OFFSET(maple_metadata_end)); + fprintf(fp, " maple_metadata_gap: %ld\n", + OFFSET(maple_metadata_gap)); fprintf(fp, "\n size_table:\n"); fprintf(fp, " page: %ld\n", SIZE(page)); @@ -11027,6 +11065,8 @@ dump_offset_table(char *spec, ulong makestruct) fprintf(fp, " sbitmap_queue: %ld\n", SIZE(sbitmap_queue)); fprintf(fp, " sbq_wait_state: %ld\n", SIZE(sbq_wait_state)); fprintf(fp, " blk_mq_tags: %ld\n", SIZE(blk_mq_tags)); + fprintf(fp, " maple_tree_struct: %ld\n", SIZE(maple_tree_struct)); + fprintf(fp, " maple_node_struct: %ld\n", SIZE(maple_node_struct)); fprintf(fp, "\n array_table:\n"); /* -- 2.33.1