[PATCH v2 0/6] Add maple tree vma iteration support for crash
by Tao Liu
Patchset [1] introduces maple tree data structure for linux, and the
modification on mm subsystem.
The main impact on crash utility, is the modification on vm_area_struct.
Patch [2][3] removed the rbtree and linked list iteration of
vm_area_struct, making it impossible for crash to iterate vma
in the traditional way. For example, we can observe the failing
of crash cmd vm/fuser on kernel which has integrated with patchset [1].
This patchset deals with the issue by porting and adapting
kernel's maple tree vma iteration code to crash utility. It has been
tested on linux-next-next-20220914 [4].
[1]: https://lore.kernel.org/all/20220906194824.2110408-1-Liam.Howlett@oracle....
[2]: https://github.com/oracle/linux-uek/commit/d19703645b80abe35dff1a88449d07...
[3]: https://github.com/oracle/linux-uek/commit/91dee01f1ebb6b6587463b6ee6f7bb...
[4]: https://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git/snaps...
v1 -> v2:
1) Move xarray.h and maple_tree_vma.h into maple.h.
2) Remove variable-length array for maple_tree.c.
3) Add tree cmd and do_maple_tree() support for maple tree.
4) Other small modifications.
Tao Liu (6):
Port the maple tree data structures and main functions
Introduce maple tree vma iteration to memory.c
Add tree cmd support for maple tree
Update the maple tree help info for tree cmd
Add do_maple_tree support for maple tree
Dump maple tree offset variables by help -o
Makefile | 12 +-
defs.h | 30 ++
help.c | 45 +-
maple_tree.c | 1367 ++++++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 214 ++++++++
memory.c | 319 +++++++-----
symbols.c | 40 ++
tools.c | 20 +-
8 files changed, 1885 insertions(+), 162 deletions(-)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
--
2.33.1
1 year, 11 months
- 2
- 15
Re: [Crash-utility] [PATCH v2 3/6] Add tree cmd support for maple tree
by lijiang
On Tue, Oct 25, 2022 at 8:39 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 25 Oct 2022 20:38:22 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v2 3/6] Add tree cmd support for maple
> tree
> Message-ID: <20221025123825.36421-4-ltao(a)redhat.com>
> Content-Type: text/plain; charset="US-ASCII"; x-default=true
>
> 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;
> };
They have to be appended to the end of this table.
>
> 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;
> +
Here, I would recommend checking if the related structures or members
are valid, just like this:
if (!VALID_STRUCT(maple_tree_struct) ||
!VALID_STRUCT(maple_node_struct) ||
!VALID_MEMBER(maple_tree_ma_root) ...)
error(FATAL,
"maple tree does not exist or has changed its
format\n");
...
Thanks.
Lianbo
> + 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
1 year, 11 months
- 2
- 1
Re: [Crash-utility] [PATCH v2 5/6] Add do_maple_tree support for maple tree
by lijiang
On Tue, Oct 25, 2022 at 8:39 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 25 Oct 2022 20:38:24 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v2 5/6] Add do_maple_tree support for
> maple tree
> Message-ID: <20221025123825.36421-6-ltao(a)redhat.com>
> Content-Type: text/plain; charset="US-ASCII"; x-default=true
>
> do_maple_tree() is similar to do_radix_tree() and do_xarray(), which
> takes the same do_maple_tree_traverse entry as tree cmd. Currently
> do_maple_tree() is not called by any other functions, we reserve it
> for future use.
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> defs.h | 6 +++
> maple_tree.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 155 insertions(+)
>
> diff --git a/defs.h b/defs.h
> index 3f2453e..827e561 100644
> --- a/defs.h
> +++ b/defs.h
> @@ -5581,6 +5581,12 @@ int cleanup_memory_driver(void);
>
> void maple_init(void);
> int do_mptree(struct tree_data *);
> +ulong do_maple_tree(ulong, int, struct list_pair *);
> +#define MAPLE_TREE_COUNT (1)
> +#define MAPLE_TREE_SEARCH (2)
> +#define MAPLE_TREE_DUMP (3)
> +#define MAPLE_TREE_GATHER (4)
> +#define MAPLE_TREE_DUMP_CB (5)
>
> /*
> * help.c
> diff --git a/maple_tree.c b/maple_tree.c
> index 33903cb..e8a287a 100644
> --- a/maple_tree.c
> +++ b/maple_tree.c
> @@ -805,6 +805,13 @@ struct cmd_tree_info {
> struct tree_data *td;
> } cmd_tree_info;
>
> +struct maple_tree_ops {
> + void (*entry)(ulong node, ulong slot, const char *path,
> + ulong index, void *private);
> + uint radix;
> + void *private;
> +} maple_tree_ops;
> +
> static const char spaces[] = " ";
>
> static void do_mt_range64(const struct maple_tree *, void *,
> @@ -1028,6 +1035,10 @@ static void do_mt_entry(void *entry, unsigned long min, unsigned long max,
> int print_radix = 0, i;
> static struct req_entry **e = NULL;
>
> + if (maple_tree_ops.entry)
> + maple_tree_ops.entry((ulong)entry, (ulong)entry, path, max,
> + maple_tree_ops.private);
> +
> if (!cmd_tree_info.td)
> return;
>
> @@ -1162,12 +1173,150 @@ int do_mptree(struct tree_data *td)
> int is_root = !(td->flags & TREE_NODE_POINTER);
>
> memset(&cmd_tree_info, 0, sizeof(cmd_tree_info));
> + memset(&maple_tree_ops, 0, sizeof(maple_tree_ops));
See comments below.
> cmd_tree_info.td = td;
> do_maple_tree_traverse(td->start, is_root);
>
> return 0;
> }
>
> +/*************For do_maple_tree*****************/
> +static void do_maple_tree_count(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct do_maple_tree_info *info = private;
> + info->count++;
> +}
> +
> +static void do_maple_tree_search(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct do_maple_tree_info *info = private;
> + struct list_pair *rtp = info->data;
> +
> + if (rtp->index == index) {
> + rtp->value = (void *)slot;
> + info->count = 1;
> + }
> +}
> +
> +static void do_maple_tree_dump(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct do_maple_tree_info *info = private;
> + fprintf(fp, "[%lu] %lx\n", index, slot);
> + info->count++;
> +}
> +
> +static void do_maple_tree_gather(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct do_maple_tree_info *info = private;
> + struct list_pair *rtp = info->data;
> +
> + if (info->maxcount) {
> + rtp[info->count].index = index;
> + rtp[info->count].value = (void *)slot;
> +
> + info->count++;
> + info->maxcount--;
> + }
> +}
> +
> +static void do_maple_tree_dump_cb(ulong node, ulong slot, const char *path,
> + ulong index, void *private)
> +{
> + struct do_maple_tree_info *info = private;
> + struct list_pair *rtp = info->data;
> + int (*cb)(ulong) = rtp->value;
> +
> + /* Caller defined operation */
> + if (!cb(slot)) {
> + error(FATAL, "do_maple_tree: callback "
> + "operation failed: entry: %ld item: %lx\n",
> + info->count, slot);
> + }
> + info->count++;
> +}
> +
> +/*
> + * do_maple_tree argument usage:
> + *
> + * root: Address of a maple_tree_root structure
> + *
> + * flag: MAPLE_TREE_COUNT - Return the number of entries in the tree.
> + * MAPLE_TREE_SEARCH - Search for an entry at rtp->index; if found,
> + * store the entry in rtp->value and return a count of 1; otherwise
> + * return a count of 0.
> + * MAPLE_TREE_DUMP - Dump all existing index/value pairs.
> + * MAPLE_TREE_GATHER - Store all existing index/value pairs in the
> + * passed-in array of list_pair structs starting at rtp,
> + * returning the count of entries stored; the caller can/should
> + * limit the number of returned entries by putting the array size
> + * (max count) in the rtp->index field of the first structure
> + * in the passed-in array.
> + * MAPLE_TREE_DUMP_CB - Similar with MAPLE_TREE_DUMP, but for each
> + * maple tree entry, a user defined callback at rtp->value will
> + * be invoked.
> + *
> + * rtp: Unused by MAPLE_TREE_COUNT and MAPLE_TREE_DUMP.
^^^
> + * A pointer to a list_pair structure for MAPLE_TREE_SEARCH.
> + * A pointer to an array of list_pair structures for
> + * MAPLE_TREE_GATHER; the dimension (max count) of the array may
> + * be stored in the index field of the first structure to avoid
> + * any chance of an overrun.
> + * For MAPLE_TREE_DUMP_CB, the rtp->value must be initialized as a
> + * callback function. The callback prototype must be: int (*)(ulong);
> + */
> +ulong
> +do_maple_tree(ulong root, int flag, struct list_pair *rtp)
The parameter name "rtp" looks a bit weird, could you please replace
the "rtp" with the "lp" and update the above comment?
> +{
> + struct do_maple_tree_info info = {
> + .count = 0,
> + .data = rtp,
Ditto.
> + };
> +
> + memset(&maple_tree_ops, 0, sizeof(maple_tree_ops));
> + memset(&cmd_tree_info, 0, sizeof(cmd_tree_info));
> + maple_tree_ops.private = &info;
Think about it again. It could be good to use a local variable and
eventually pass the ops parameter to do_maple_tree_traverse(). Just
like:
//filesys.c
struct do_radix_tree_info info = {
.count = 0,
.data = rtp,
};
struct radix_tree_ops ops = {
.radix = 16,
.private = &info,
};
> +
> + switch (flag)
> + {
> + case MAPLE_TREE_COUNT:
> + maple_tree_ops.entry = do_maple_tree_count;
> + break;
> +
> + case MAPLE_TREE_SEARCH:
> + maple_tree_ops.entry = do_maple_tree_search;
> + break;
> +
> + case MAPLE_TREE_DUMP:
> + maple_tree_ops.entry = do_maple_tree_dump;
> + break;
> +
> + case MAPLE_TREE_GATHER:
> + if (!(info.maxcount = rtp->index))
> + info.maxcount = (ulong)(-1); /* caller beware */
> +
> + maple_tree_ops.entry = do_maple_tree_gather;
> + break;
> +
> + case MAPLE_TREE_DUMP_CB:
> + if (rtp->value == NULL) {
> + error(FATAL, "do_maple_tree: need set callback function");
> + return -EINVAL;
The above "return" seems to be redundant.
Thanks.
Lianbo
> + }
> + maple_tree_ops.entry = do_maple_tree_dump_cb;
> + break;
> +
> + default:
> + error(FATAL, "do_maple_tree: invalid flag: %lx\n", flag);
> + }
> +
> + do_maple_tree_traverse(root, true);
> + return info.count;
> +}
> +
> /***********************************************/
> void maple_init(void)
> {
> --
> 2.33.1
1 year, 11 months
- 2
- 1
Re: [Crash-utility] [PATCH v2 3/6] Add tree cmd support for maple tree
by lijiang
> Date: Fri, 28 Oct 2022 11:28:10 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: Re: [Crash-utility] [PATCH v2 3/6] Add tree cmd support for
> maple tree
> Message-ID:
> <CAO7dBbVL_er-hA8LtXs3Cz8GMcZAQDjVMGNHRVAc8LyekDKtrQ(a)mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> On Tue, Oct 25, 2022 at 8:38 PM Tao Liu <ltao(a)redhat.com> wrote:
> >
> > 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)
>
> Sorry, the (VERBOSE << 9) should be (VERBOSE << 10)
>
In addition, can you also replace the assert() with "if() error(FATAL, ...)" ?
Thanks.
Lianbo
> >
> > #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
1 year, 11 months
- 2
- 1
Re: [Crash-utility] [PATCH v2 2/6] Introduce maple tree vma iteration to memory.c
by lijiang
On Tue, Oct 25, 2022 at 8:39 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 25 Oct 2022 20:38:21 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v2 2/6] Introduce maple tree vma
> iteration to memory.c
> Message-ID: <20221025123825.36421-3-ltao(a)redhat.com>
> Content-Type: text/plain; charset="US-ASCII"; x-default=true
>
> Since memory.c:vm_area_dump will iterate all vma, this patch mainly
> introduces maple tree vma iteration to it.
>
> We extract the code which handles each vma into a function. If
> mm_struct_mmap exist, aka the linked list of vma iteration available,
> we goto the original way; if not and mm_struct_mm_mt exist, aka
> maple tree is available, then we goto the maple tree vma iteration.
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> Makefile | 2 +-
> memory.c | 319 ++++++++++++++++++++++++++++++++-----------------------
> 2 files changed, 190 insertions(+), 131 deletions(-)
>
> diff --git a/Makefile b/Makefile
> index 6f19b77..ad8e9c4 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -355,7 +355,7 @@ filesys.o: ${GENERIC_HFILES} filesys.c
> help.o: ${GENERIC_HFILES} help.c
> ${CC} -c ${CRASH_CFLAGS} help.c ${WARNING_OPTIONS} ${WARNING_ERROR}
>
> -memory.o: ${GENERIC_HFILES} memory.c
> +memory.o: ${GENERIC_HFILES} ${MAPLE_TREE_HFILES} memory.c
> ${CC} -c ${CRASH_CFLAGS} memory.c ${WARNING_OPTIONS} ${WARNING_ERROR}
>
> test.o: ${GENERIC_HFILES} test.c
> diff --git a/memory.c b/memory.c
> index c80ef61..8e043d0 100644
> --- a/memory.c
> +++ b/memory.c
> @@ -21,6 +21,7 @@
> #include <ctype.h>
> #include <netinet/in.h>
> #include <byteswap.h>
> +#include "maple_tree.h"
>
> struct meminfo { /* general purpose memory information structure */
> ulong cache; /* used by the various memory searching/dumping */
> @@ -136,6 +137,27 @@ struct searchinfo {
> char buf[BUFSIZE];
> };
>
> +struct handle_each_vm_area_args {
> + ulong task;
> + ulong flag;
> + ulong vaddr;
> + struct reference *ref;
> + char *vma_header;
> + char *buf1;
> + char *buf2;
> + char *buf3;
> + char *buf4;
> + char *buf5;
> + ulong vma;
> + char **vma_buf;
> + struct task_mem_usage *tm;
> + int *found;
> + int *single_vma_found;
> + unsigned int radix;
> + struct task_context *tc;
> + ulong *single_vma;
> +};
> +
> static char *memtype_string(int, int);
> static char *error_handle_string(ulong);
> static void collect_page_member_data(char *, struct meminfo *);
> @@ -298,6 +320,7 @@ static void dump_page_flags(ulonglong);
> static ulong kmem_cache_nodelists(ulong);
> static void dump_hstates(void);
> static ulong freelist_ptr(struct meminfo *, ulong, ulong);
> +static ulong handle_each_vm_area(struct handle_each_vm_area_args *);
>
> /*
> * Memory display modes specific to this file.
> @@ -362,6 +385,10 @@ vm_init(void)
>
> MEMBER_OFFSET_INIT(task_struct_mm, "task_struct", "mm");
> MEMBER_OFFSET_INIT(mm_struct_mmap, "mm_struct", "mmap");
> + MEMBER_OFFSET_INIT(mm_struct_mm_mt, "mm_struct", "mm_mt");
> + if (VALID_MEMBER(mm_struct_mm_mt)) {
> + maple_init();
> + }
> MEMBER_OFFSET_INIT(mm_struct_pgd, "mm_struct", "pgd");
> MEMBER_OFFSET_INIT(mm_struct_rss, "mm_struct", "rss");
> if (!VALID_MEMBER(mm_struct_rss))
> @@ -3866,7 +3893,7 @@ bailout:
> * for references -- and only then does a display
> */
>
> -#define PRINT_VM_DATA() \
> +#define PRINT_VM_DATA(buf4, buf5, tm) \
> { \
> fprintf(fp, "%s %s ", \
> mkstring(buf4, VADDR_PRLEN, CENTER|LJUST, "MM"), \
> @@ -3888,9 +3915,9 @@ bailout:
> mkstring(buf5, 8, CENTER|LJUST, NULL)); \
> }
>
> -#define PRINT_VMA_DATA() \
> +#define PRINT_VMA_DATA(buf1, buf2, buf3, buf4, vma) \
> fprintf(fp, "%s%s%s%s%s %6llx%s%s\n", \
> - mkstring(buf4, VADDR_PRLEN, CENTER|LJUST|LONG_HEX, MKSTR(vma)), \
> + mkstring(buf4, VADDR_PRLEN, CENTER|LJUST|LONG_HEX, MKSTR(vma)),\
> space(MINSPACE), \
> mkstring(buf2, UVADDR_PRLEN, RJUST|LONG_HEX, MKSTR(vm_start)), \
> space(MINSPACE), \
> @@ -3917,18 +3944,143 @@ bailout:
> (DO_REF_SEARCH(X) && (string_exists(S)) && FILENAME_COMPONENT((S),(X)->str))
> #define VM_REF_FOUND(X) ((X) && ((X)->cmdflags & VM_REF_HEADER))
>
> -ulong
> -vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> +static ulong handle_each_vm_area(struct handle_each_vm_area_args *args)
> {
> - struct task_context *tc;
> - ulong vma;
> + char *dentry_buf, *file_buf;
> ulong vm_start;
> ulong vm_end;
> - ulong vm_next, vm_mm;
> - char *dentry_buf, *vma_buf, *file_buf;
> + ulong vm_mm;
> ulonglong vm_flags;
> ulong vm_file, inode;
> ulong dentry, vfsmnt;
> +
> + if ((args->flag & PHYSADDR) && !DO_REF_SEARCH(args->ref))
> + fprintf(fp, "%s", args->vma_header);
> +
> + inode = 0;
> + BZERO(args->buf1, BUFSIZE);
> + *(args->vma_buf) = fill_vma_cache(args->vma);
> +
> + vm_mm = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_mm));
> + vm_end = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_end));
> + vm_start = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_start));
> + vm_flags = get_vm_flags(*(args->vma_buf));
> + vm_file = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_file));
> +
> + if (args->flag & PRINT_SINGLE_VMA) {
> + if (args->vma != *(args->single_vma))
> + return 0;
> + fprintf(fp, "%s", args->vma_header);
> + *(args->single_vma_found) = TRUE;
> + }
> +
> + if (args->flag & PRINT_VMA_STRUCTS) {
> + dump_struct("vm_area_struct", args->vma, args->radix);
> + return 0;
> + }
> +
> + if (vm_file && !(args->flag & VERIFY_ADDR)) {
> + file_buf = fill_file_cache(vm_file);
> + dentry = ULONG(file_buf + OFFSET(file_f_dentry));
> + dentry_buf = NULL;
> + if (dentry) {
> + dentry_buf = fill_dentry_cache(dentry);
> + if (VALID_MEMBER(file_f_vfsmnt)) {
> + vfsmnt = ULONG(file_buf +
> + OFFSET(file_f_vfsmnt));
> + get_pathname(dentry, args->buf1, BUFSIZE,
> + 1, vfsmnt);
> + } else {
> + get_pathname(dentry, args->buf1, BUFSIZE,
> + 1, 0);
> + }
> + }
> + if ((args->flag & PRINT_INODES) && dentry) {
> + inode = ULONG(dentry_buf +
> + OFFSET(dentry_d_inode));
> + }
> + }
> +
> + if (!(args->flag & UVADDR) || ((args->flag & UVADDR) &&
> + ((args->vaddr >= vm_start) && (args->vaddr < vm_end)))) {
> + *(args->found) = TRUE;
> +
> + if (args->flag & VERIFY_ADDR)
> + return args->vma;
> +
> + if (DO_REF_SEARCH(args->ref)) {
> + if (VM_REF_CHECK_HEXVAL(args->ref, args->vma) ||
> + VM_REF_CHECK_HEXVAL(args->ref, (ulong)vm_flags) ||
> + VM_REF_CHECK_STRING(args->ref, args->buf1)) {
> + if (!(args->ref->cmdflags & VM_REF_HEADER)) {
> + print_task_header(fp, args->tc, 0);
> + PRINT_VM_DATA(args->buf4, args->buf5, args->tm);
> + args->ref->cmdflags |= VM_REF_HEADER;
> + }
> + if (!(args->ref->cmdflags & VM_REF_VMA) ||
> + (args->ref->cmdflags & VM_REF_PAGE)) {
> + fprintf(fp, "%s", args->vma_header);
> + args->ref->cmdflags |= VM_REF_VMA;
> + args->ref->cmdflags &= ~VM_REF_PAGE;
> + args->ref->ref1 = args->vma;
> + }
> + PRINT_VMA_DATA(args->buf1, args->buf2,
> + args->buf3, args->buf4, args->vma);
> + }
> +
> + if (vm_area_page_dump(args->vma, args->task,
> + vm_start, vm_end, vm_mm, args->ref)) {
> + if (!(args->ref->cmdflags & VM_REF_HEADER)) {
> + print_task_header(fp, args->tc, 0);
> + PRINT_VM_DATA(args->buf4, args->buf5, args->tm);
> + args->ref->cmdflags |= VM_REF_HEADER;
> + }
> + if (!(args->ref->cmdflags & VM_REF_VMA) ||
> + (args->ref->ref1 != args->vma)) {
> + fprintf(fp, "%s", args->vma_header);
> + PRINT_VMA_DATA(args->buf1, args->buf2,
> + args->buf3, args->buf4, args->vma);
> + args->ref->cmdflags |= VM_REF_VMA;
> + args->ref->ref1 = args->vma;
> + }
> +
> + args->ref->cmdflags |= VM_REF_DISPLAY;
> + vm_area_page_dump(args->vma, args->task,
> + vm_start, vm_end, vm_mm, args->ref);
> + args->ref->cmdflags &= ~VM_REF_DISPLAY;
> + }
> +
> + return 0;
> + }
> +
> + if (inode) {
> + fprintf(fp, "%lx%s%s%s%s%s%6llx%s%lx %s\n",
> + args->vma, space(MINSPACE),
> + mkstring(args->buf2, UVADDR_PRLEN, RJUST|LONG_HEX,
> + MKSTR(vm_start)), space(MINSPACE),
> + mkstring(args->buf3, UVADDR_PRLEN, RJUST|LONG_HEX,
> + MKSTR(vm_end)), space(MINSPACE),
> + vm_flags, space(MINSPACE), inode, args->buf1);
> + } else {
> + PRINT_VMA_DATA(args->buf1, args->buf2,
> + args->buf3, args->buf4, args->vma);
> +
> + if (args->flag & (PHYSADDR|PRINT_SINGLE_VMA))
> + vm_area_page_dump(args->vma, args->task,
> + vm_start, vm_end, vm_mm, args->ref);
> + }
> +
> + if (args->flag & UVADDR)
> + return args->vma;
> + }
> + return 0;
> +}
> +
> +ulong
> +vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> +{
> + struct task_context *tc;
> + ulong vma;
> ulong single_vma;
> unsigned int radix;
> int single_vma_found;
> @@ -3940,6 +4092,7 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> char buf4[BUFSIZE];
> char buf5[BUFSIZE];
> char vma_header[BUFSIZE];
> + char *vma_buf;
>
> tc = task_to_context(task);
> tm = &task_mem_usage;
> @@ -3973,14 +4126,14 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> if (VM_REF_CHECK_HEXVAL(ref, tm->mm_struct_addr) ||
> VM_REF_CHECK_HEXVAL(ref, tm->pgd_addr)) {
> print_task_header(fp, tc, 0);
> - PRINT_VM_DATA();
> + PRINT_VM_DATA(buf4, buf5, tm);
> fprintf(fp, "\n");
> return (ulong)NULL;
> }
>
> if (!(flag & (UVADDR|PRINT_MM_STRUCT|PRINT_VMA_STRUCTS|PRINT_SINGLE_VMA)) &&
> !DO_REF_SEARCH(ref))
> - PRINT_VM_DATA();
> + PRINT_VM_DATA(buf4, buf5, tm);
>
> if (!tm->mm_struct_addr) {
> if (pc->curcmd_flags & MM_STRUCT_FORCE) {
> @@ -4004,9 +4157,6 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> return (ulong)NULL;
> }
>
> - readmem(tm->mm_struct_addr + OFFSET(mm_struct_mmap), KVADDR,
> - &vma, sizeof(void *), "mm_struct mmap", FAULT_ON_ERROR);
> -
> sprintf(vma_header, "%s%s%s%s%s FLAGS%sFILE\n",
> mkstring(buf1, VADDR_PRLEN, CENTER|LJUST, "VMA"),
> space(MINSPACE),
> @@ -4019,125 +4169,34 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
> !DO_REF_SEARCH(ref))
> fprintf(fp, "%s", vma_header);
>
> - for (found = FALSE; vma; vma = vm_next) {
> -
> - if ((flag & PHYSADDR) && !DO_REF_SEARCH(ref))
> - fprintf(fp, "%s", vma_header);
> -
> - inode = 0;
> - BZERO(buf1, BUFSIZE);
> - vma_buf = fill_vma_cache(vma);
> -
> - vm_mm = ULONG(vma_buf + OFFSET(vm_area_struct_vm_mm));
> - vm_end = ULONG(vma_buf + OFFSET(vm_area_struct_vm_end));
> - vm_next = ULONG(vma_buf + OFFSET(vm_area_struct_vm_next));
> - vm_start = ULONG(vma_buf + OFFSET(vm_area_struct_vm_start));
> - vm_flags = get_vm_flags(vma_buf);
> - vm_file = ULONG(vma_buf + OFFSET(vm_area_struct_vm_file));
> -
> - if (flag & PRINT_SINGLE_VMA) {
> - if (vma != single_vma)
> - continue;
> - fprintf(fp, "%s", vma_header);
> - single_vma_found = TRUE;
> - }
> -
> - if (flag & PRINT_VMA_STRUCTS) {
> - dump_struct("vm_area_struct", vma, radix);
> - continue;
> - }
> -
> - if (vm_file && !(flag & VERIFY_ADDR)) {
> - file_buf = fill_file_cache(vm_file);
> - dentry = ULONG(file_buf + OFFSET(file_f_dentry));
> - dentry_buf = NULL;
> - if (dentry) {
> - dentry_buf = fill_dentry_cache(dentry);
> - if (VALID_MEMBER(file_f_vfsmnt)) {
> - vfsmnt = ULONG(file_buf +
> - OFFSET(file_f_vfsmnt));
> - get_pathname(dentry, buf1, BUFSIZE,
> - 1, vfsmnt);
> - } else {
> - get_pathname(dentry, buf1, BUFSIZE,
> - 1, 0);
> - }
> - }
> - if ((flag & PRINT_INODES) && dentry) {
> - inode = ULONG(dentry_buf +
> - OFFSET(dentry_d_inode));
> - }
> - }
> -
> - if (!(flag & UVADDR) || ((flag & UVADDR) &&
> - ((vaddr >= vm_start) && (vaddr < vm_end)))) {
> - found = TRUE;
> + found = FALSE;
>
> - if (flag & VERIFY_ADDR)
> + struct handle_each_vm_area_args args = {
> + .task = task, .flag = flag, .vaddr = vaddr,
> + .ref = ref, .vma_header = vma_header, .buf1 = buf1,
> + .buf2 = buf2, .buf3 = buf3, .buf4 = buf4,
> + .buf5 = buf5, .vma_buf = &vma_buf, .tm = tm,
> + .found = &found, .single_vma_found = &single_vma_found,
> + .radix = radix, .tc = tc, .single_vma = &single_vma,
> + };
The refactored code looks good, but the above structure seems to lack
a little readability. Is it possible to rearrange/split them according
to some rules? Such as parameter dependencies or input/output
parameters, etc... Just an idea.
Thanks.
Lianbo
> +
> + if (INVALID_MEMBER(mm_struct_mmap) && VALID_MEMBER(mm_struct_mm_mt)) {
> + VMA_ITERATOR(vmi, (struct maple_tree *)
> + (tm->mm_struct_addr + OFFSET(mm_struct_mm_mt)), 0);
> + for_each_vma(vmi, vma) {
> + args.vma = vma;
> + if (handle_each_vm_area(&args))
> return vma;
> -
> - if (DO_REF_SEARCH(ref)) {
> - if (VM_REF_CHECK_HEXVAL(ref, vma) ||
> - VM_REF_CHECK_HEXVAL(ref, (ulong)vm_flags) ||
> - VM_REF_CHECK_STRING(ref, buf1)) {
> - if (!(ref->cmdflags & VM_REF_HEADER)) {
> - print_task_header(fp, tc, 0);
> - PRINT_VM_DATA();
> - ref->cmdflags |= VM_REF_HEADER;
> - }
> - if (!(ref->cmdflags & VM_REF_VMA) ||
> - (ref->cmdflags & VM_REF_PAGE)) {
> - fprintf(fp, "%s", vma_header);
> - ref->cmdflags |= VM_REF_VMA;
> - ref->cmdflags &= ~VM_REF_PAGE;
> - ref->ref1 = vma;
> - }
> - PRINT_VMA_DATA();
> - }
> -
> - if (vm_area_page_dump(vma, task,
> - vm_start, vm_end, vm_mm, ref)) {
> - if (!(ref->cmdflags & VM_REF_HEADER)) {
> - print_task_header(fp, tc, 0);
> - PRINT_VM_DATA();
> - ref->cmdflags |= VM_REF_HEADER;
> - }
> - if (!(ref->cmdflags & VM_REF_VMA) ||
> - (ref->ref1 != vma)) {
> - fprintf(fp, "%s", vma_header);
> - PRINT_VMA_DATA();
> - ref->cmdflags |= VM_REF_VMA;
> - ref->ref1 = vma;
> - }
> -
> - ref->cmdflags |= VM_REF_DISPLAY;
> - vm_area_page_dump(vma, task,
> - vm_start, vm_end, vm_mm, ref);
> - ref->cmdflags &= ~VM_REF_DISPLAY;
> - }
> -
> - continue;
> - }
> -
> - if (inode) {
> - fprintf(fp, "%lx%s%s%s%s%s%6llx%s%lx %s\n",
> - vma, space(MINSPACE),
> - mkstring(buf2, UVADDR_PRLEN, RJUST|LONG_HEX,
> - MKSTR(vm_start)), space(MINSPACE),
> - mkstring(buf3, UVADDR_PRLEN, RJUST|LONG_HEX,
> - MKSTR(vm_end)), space(MINSPACE),
> - vm_flags, space(MINSPACE), inode, buf1);
> - } else {
> - PRINT_VMA_DATA();
> -
> - if (flag & (PHYSADDR|PRINT_SINGLE_VMA))
> - vm_area_page_dump(vma, task,
> - vm_start, vm_end, vm_mm, ref);
> - }
> -
> - if (flag & UVADDR)
> + }
> + } else {
> + readmem(tm->mm_struct_addr + OFFSET(mm_struct_mmap), KVADDR,
> + &vma, sizeof(void *), "mm_struct mmap", FAULT_ON_ERROR);
> + while (vma) {
> + args.vma = vma;
> + if (handle_each_vm_area(&args))
> return vma;
> - }
> + vma = ULONG(vma_buf + OFFSET(vm_area_struct_vm_next));
> + }
> }
>
> if (flag & VERIFY_ADDR)
> --
> 2.33.1
1 year, 11 months
- 2
- 1
Re: [Crash-utility] [PATCH v2 1/6] Port the maple tree data structures and main functions
by lijiang
On Tue, Oct 25, 2022 at 8:39 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 25 Oct 2022 20:38:20 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v2 1/6] Port the maple tree data
> structures and main functions
> Message-ID: <20221025123825.36421-2-ltao(a)redhat.com>
> Content-Type: text/plain; charset="US-ASCII"; x-default=true
>
> 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>
> ---
> 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>
> + * Matthew Wilcox <willy(a)infradead.org>
> + *
> + * 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))
Unused.
> +#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);
The assert() may cause the crash coredump, could you please replace
the assert() with the similar code block as below?
if (SIZE(maple_tree_struct) <= MAPLE_BUFSIZE)
error(FATAL, "");
> +
> + 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);
Ditto.
> +
> + 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;
The "return" is redundant?
> +}
> +
> +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);
Ditto.
> +
> + p_type = (unsigned long)p_enode;
> + if (p_type & MAPLE_PARENT_ROOT)
> + return 0; /* Validated in the caller. */
Does this indicate that it is the enum maple_type: maple_dense?
> +
> + 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);
Ditto.
> +
> + 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);
Ditto.
> +
> + 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);
Ditto.
> +
> + 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>
> + * Matthew Wilcox <willy(a)infradead.org>
> + *
> + * eXtensible Arrays
> + * Copyright (c) 2017 Microsoft Corporation
> + * Author: Matthew Wilcox <willy(a)infradead.org>
> + *
> + * 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 { };
> +
Is it possible to define them with the "void *" ? For example:
struct ma_state {
void *tree;
unsigned long index;
...
void *node;
...
};
Kernel may change them or move them out of the structure in the
future, in this situation crash won't have to change accordingly.
> +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, \
> + }
The above two macros are unused.
> +
> +#define MAPLE_NODE_MASK 255UL
> +
> +#define MT_FLAGS_ALLOC_RANGE 0x01
> +#define MT_FLAGS_USE_RCU 0x02
Unused.
> +#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
The above four macros are unused.
> +
> +#define MAPLE_HEIGHT_MAX 31
Unused.
> +
> +#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
The macro MAX_ERRNO is unused because the xa_is_err() is not called.
> +#define XA_ZERO_ENTRY xa_mk_internal(257)
> +#define XA_RETRY_ENTRY xa_mk_internal(256)
The macro XA_RETRY_ENTRY is unused because the xa_is_advanced() is not
called by other functions.
> +
> +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);
> +}
The xa_is_err() is unused.
> +
> +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;
> +}
Ditto.
> +
> +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);
> +}
Ditto.
Thanks.
Lianbo
> +
> +/*
> + * 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
1 year, 11 months
- 2
- 1
[PATCH] task: ps: Provide an option to display no header line
by Aaron Tomlin
One might often find it useful to redirect/or filter the output
generated by the 'ps' command. This simple patch provides an option
(i.e. '-H') to display no header line so it does not need to be
considered e.g.
crash> ps -u -H | head -5
1 0 1 ffff956e8028d280 IN 0.0 174276 9272 systemd
1067 1 2 ffff956e81380000 IN 0.1 59480 15788 systemd-journal
1080 1 0 ffff956e8d152940 IN 0.0 36196 3548 systemd-udevd
1278 1 6 ffff956e8aa60000 IN 0.0 17664 3072 systemd-oomd
1366 1 7 ffff956e88548000 IN 0.0 10868 2328 dbus-broker-lau
Signed-off-by: Aaron Tomlin <atomlin(a)atomlin.com>
---
help.c | 3 ++-
task.c | 6 +++++-
2 files changed, 7 insertions(+), 2 deletions(-)
diff --git a/help.c b/help.c
index 99214c15..14981cd0 100644
--- a/help.c
+++ b/help.c
@@ -1379,7 +1379,7 @@ NULL
char *help_ps[] = {
"ps",
"display process status information",
-"[-k|-u|-G|-y policy] [-s] [-p|-c|-t|-[l|m][-C cpu]|-a|-g|-r|-S|-A]\n [pid | task | command] ...",
+"[-k|-u|-G|-y policy] [-s] [-p|-c|-t|-[l|m][-C cpu]|-a|-g|-r|-S|-A|-H]\n [pid | task | command] ...",
" This command displays process status for selected, or all, processes" ,
" in the system. If no arguments are entered, the process data is",
" is displayed for all processes. Specific processes may be selected",
@@ -1458,6 +1458,7 @@ char *help_ps[] = {
" -r display resource limits (rlimits) of selected, or all, tasks.",
" -S display a summary consisting of the number of tasks in a task state.",
" -A display only the active task on each cpu.",
+" -H display no header line.",
"\nEXAMPLES",
" Show the process status of all current tasks:\n",
" %s> ps",
diff --git a/task.c b/task.c
index db2abc81..88941c7b 100644
--- a/task.c
+++ b/task.c
@@ -3504,7 +3504,7 @@ cmd_ps(void)
cpuspec = NULL;
flag = 0;
- while ((c = getopt(argcnt, args, "ASgstcpkuGlmarC:y:")) != EOF) {
+ while ((c = getopt(argcnt, args, "HASgstcpkuGlmarC:y:")) != EOF) {
switch(c)
{
case 'k':
@@ -3615,6 +3615,10 @@ cmd_ps(void)
flag |= PS_ACTIVE;
break;
+ case 'H':
+ flag |= PS_NO_HEADER;
+ break;
+
default:
argerrs++;
break;
--
2.37.3
1 year, 12 months
- 2
- 2
[ANNOUNCE] crash-8.0.2 is available
by HAGIO KAZUHITO(萩尾 一仁)
Download from: https://crash-utility.github.io/
or
https://github.com/crash-utility/crash/releases
The GitHub master branch serves as a development branch that will contain
all patches that are queued for the next release:
$ git clone https://github.com/crash-utility/crash.git
Changelog:
f1cd581 crash-8.0.1 -> crash-8.0.2
a158590 Fix for "ps/vm" commands to display correct %MEM and RSS values
21139d9 Fix segmentation fault in page_flags_init_from_pageflag_names()
4875514 ppc64: still allow to move on if the emergency stacks info fails to initialize
3b5e3e1 Let "kmem" print task context with physical address
60cb865 Fix page offset issue when converting physical to virtual address
ad1397a Fix "kmem" failing to print task context when address is vmalloced stack
4ea3a80 Fix for the invalid linux_banner pointer issue
bdbf588 Fix gcc-11 compiler warnings on gdb-10.2/gdb/symtab.c
51acac7 Fix gcc-12 compiler warnings on lkcd_*.c
5b9d3e9 Add debian/ubuntu vmlinux location to default search dirs
3ed9ec5 x86_64: Correct the identifier when locating the call instruction
2145b2b Let gdb get kernel module symbols info from crash
9cbfea6 Fix "task -R" by adding end identifier for union in task_struct
f02c8e8 arm64: use TCR_EL1_T1SZ to get the correct info if vabits_actual is missing
4c85e98 gdb: fix for assigning NULL to std::string
c2743ad Makefile: Fix unnecessary re-patching with coreutils-9.0
763e221 x86_64: Fix for AMD SME issue
f37df7d Fix gcc-11 compiler warning on kvmdump.c
7591e3c Fix gcc-11 compiler warning on makedumpfile.c
b9c0ed1 Fix gcc-11 compiler warning on symbols.c
f374aca Fix gcc-11 compiler warnings on filesys.c
6722ea1 arm64: Fix for st->_stext_vmlinux not initialized when set VA_BITS_ACTUAL
93b8802 ppc64: use a variable for machdep->machspec
4dc2f1c ppc64: print emergency stacks info with 'mach' command
cdd57e8 ppc64: handle backtrace when CPU is in an emergency stack
4d1b968 ppc64: rename ppc64_paca_init to ppc64_paca_percpu_offset_init
3ee5956 ppc64: dynamically allocate h/w interrupt stack
c67ce5b ppc64: fix bt for '-S' case
d8869b0 Extend field length of task attributes
85f3906 Fix for "dev" command on Linux 5.11 and later
b8f2ae6 sbitmapq: Limit kernels without sbitmap again
6bc3b74 sbitmapq: Fix for kernels without struct wait_queue_head
c070682 Make "dev -d|-D" options parse sbitmap on Linux 4.18 and later
12fe6c7 sbitmapq: Fix for sbitmap_queue without min_shallow_depth member
0d3e86f sbitmapq: Fix for sbitmap_word without cleared member
9ce31a1 sbitmapq: Fix for sbitmap_queue without ws_active member
c672d7a Doc: update man page for the "bpf" and "sbitmapq" commands
68ce0b9 Fix for "dev -d|-D" options to support blk-mq change on Linux v5.18-rc1
7095c8f Enhance "dev -d|-D" options to support blk-mq sbitmap
dda5b2d gdb: print details of unnamed struct and union
0f162fe bt: arm64: add support for 'bt -n idle'
6833262 bt: x86_64: filter out idle task stack
9705669 Makefile: add missing crash_target.o to be cleaned
3750803 sbitmapq: fix invalid offset for "sbitmap_word_depth" on Linux v5.18-rc1
530fe6a sbitmapq: fix invalid offset for "sbitmap_queue_round_robin" on Linux v5.13-rc1
a295cb4 sbitmapq: fix invalid offset for "sbitmap_queue_alloc_hint" on Linux v5.13-rc1
364b2e4 sbitmapq: remove struct and member validation in sbitmapq_init()
ae52398 ppc64: update the NR_CPUS to 8192
0ca55e4 Mark start of 8.0.2 development phase with version 8.0.1++
Full changelog: https://crash-utility.github.io/changelog/ChangeLog-8.0.2.txt
2 years
- 1
- 0
[PATCH] Fix for "ps/vm" commands to display correct %MEM and RSS values
by Lianbo Jiang
The ps/vm commands may print the bogus value of the %MEM and RSS, the
reason is that the counter of rss stat is updated in asynchronous manner
and may become negative, when the SPLIT_RSS_COUNTING is enabled in kernel.
As a result, crash will read it from memory and convert from negative to
unsigned long integer, eventually it overflows and gets a big integer. For
example:
crash> ps 1393
PID PPID CPU TASK ST %MEM VSZ RSS COMM
1393 1 24 ffff9584bb542100 RU 541298032135.9 4132 18014398509481908 enlinuxpc64
^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^
This is unexpected, crash needs to correct its value for this case.
Signed-off-by: Lianbo Jiang <lijiang(a)redhat.com>
---
memory.c | 23 ++++++++++++++++++-----
1 file changed, 18 insertions(+), 5 deletions(-)
diff --git a/memory.c b/memory.c
index 8724c4aa3d8a..9c15c1b745ef 100644
--- a/memory.c
+++ b/memory.c
@@ -4714,18 +4714,29 @@ get_task_mem_usage(ulong task, struct task_mem_usage *tm)
* Latest kernels have mm_struct.mm_rss_stat[].
*/
if (VALID_MEMBER(mm_struct_rss_stat)) {
- long anonpages, filepages;
+ long anonpages, filepages, count;
anonpages = tt->anonpages;
filepages = tt->filepages;
- rss += LONG(tt->mm_struct +
+ count = LONG(tt->mm_struct +
OFFSET(mm_struct_rss_stat) +
OFFSET(mm_rss_stat_count) +
(filepages * sizeof(long)));
- rss += LONG(tt->mm_struct +
+
+ /*
+ * The counter is updated in asynchronous manner
+ * and may become negative, see:
+ * include/linux/mm.h: get_mm_counter()
+ */
+ if (count > 0)
+ rss += count;
+
+ count = LONG(tt->mm_struct +
OFFSET(mm_struct_rss_stat) +
OFFSET(mm_rss_stat_count) +
(anonpages * sizeof(long)));
+ if (count > 0)
+ rss += count;
}
/* Check whether SPLIT_RSS_COUNTING is enabled */
@@ -4769,7 +4780,8 @@ get_task_mem_usage(ulong task, struct task_mem_usage *tm)
RETURN_ON_ERROR))
continue;
- rss_cache += sync_rss;
+ if (sync_rss > 0)
+ rss_cache += sync_rss;
/* count 1 -> anonpages */
if (!readmem(first->task +
@@ -4782,7 +4794,8 @@ get_task_mem_usage(ulong task, struct task_mem_usage *tm)
RETURN_ON_ERROR))
continue;
- rss_cache += sync_rss;
+ if (sync_rss > 0)
+ rss_cache += sync_rss;
if (first == last)
break;
--
2.37.1
2 years
- 2
- 1