[PATCH v4 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.
v2 -> v3:
1) Remove for_each_vma() macro, and all its dependence functions such as
mas_find(), and use mt_dump()(aka do_maple_tree_traverse()) as a way for
maple tree iteration instead.
2) Make do_maple_tree_info and maple_tree_ops local variable instead of
global variable.
3) Show only valid maple entries by tree cmd.
4) Remove empty structures, such as maple_tree{}/maple_metadata{}, use void *
instead.
5) Other changes based on Kazu and Lianbo's comments.
v3 -> v4:
1) Rename maple_tree/node_struct to maple_tree/node.
2) Use ULONG(ptr) to replace *(unsigned long *)ptr.
3) Replace void * with ulong.
4) Add maple tree examples to help_tree EXAMPLES section.
5) Remove unused maple_tree_mt variable to simplify do_mt_entry(), do_mt_node()
and do_mt_range64() functions.
6) Removed unused radix variable of maple_tree_ops.
7) Rebase the code to the latest in upstream.
Tao Liu (6):
Port the maple tree data structures and main functions
Add tree cmd support for maple tree
Add do_maple_tree support for maple tree
Introduce maple tree vma iteration to memory.c
Update the maple tree help info for tree cmd
Dump maple tree offset variables by help -o
Makefile | 12 +-
defs.h | 26 +++
help.c | 86 +++++--
maple_tree.c | 615 +++++++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 82 +++++++
memory.c | 327 ++++++++++++++++-----------
symbols.c | 32 +++
tools.c | 67 ++++--
8 files changed, 1075 insertions(+), 172 deletions(-)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
--
2.33.1
1 year, 5 months
- 2
- 12
[PATCH 1/2] SLAB: Fix for "kmem -s|-S" options on Linux 6.1 and later
by HAGIO KAZUHITO(萩尾 一仁)
Kernel commit e36ce448a08d ("mm/slab: use kmalloc_node() for off slab
freelist_idx_t array allocation"), which is contained in Linux 6.1 and
later kernels, removed kmem_cache.freelist_cache member.
Without the patch, crash does not set SLAB_OVERLOAD_PAGE and
"kmem -s|-S" options fail with the following error:
kmem: invalid structure member offset: slab_list
FILE: memory.c LINE: 12156 FUNCTION: verify_slab_v2()
Use kmem_cache.freelist_size instead, which was instroduced together
with kmem_cache.freelist_cache by kernel commit 8456a648cf44.
Signed-off-by: Kazuhito Hagio <k-hagio-ab(a)nec.com>
---
memory.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
diff --git a/memory.c b/memory.c
index 625a94b7d7d4..71ded688206f 100644
--- a/memory.c
+++ b/memory.c
@@ -535,8 +535,11 @@ vm_init(void)
/*
* slab: overload struct slab over struct page
* https://lkml.org/lkml/2013/10/16/155
+ *
+ * commit e36ce448a08d removed kmem_cache.freelist_cache in 6.1,
+ * so use freelist_size instead.
*/
- if (MEMBER_EXISTS("kmem_cache", "freelist_cache")) {
+ if (MEMBER_EXISTS("kmem_cache", "freelist_size")) {
vt->flags |= SLAB_OVERLOAD_PAGE;
ANON_MEMBER_OFFSET_INIT(page_s_mem, "page", "s_mem");
ANON_MEMBER_OFFSET_INIT(page_freelist, "page", "freelist");
--
2.31.1
1 year, 5 months
- 2
- 3
Re: [Crash-utility] [PATCH v3 5/6] Update the maple tree help info for tree cmd
by lijiang
On Tue, Dec 6, 2022 at 4:40 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 6 Dec 2022 16:40:21 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v3 5/6] Update the maple tree help
> info for tree cmd
> Message-ID: <20221206084022.58693-6-ltao(a)redhat.com>
> Content-Type: text/plain; charset="US-ASCII"; x-default=true
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> help.c | 46 ++++++++++++++++++++++++----------------------
> 1 file changed, 24 insertions(+), 22 deletions(-)
>
> diff --git a/help.c b/help.c
> index 99214c1..f764d08 100644
> --- a/help.c
> +++ b/help.c
> @@ -6306,19 +6306,20 @@ NULL
>
> char *help_tree[] = {
> "tree",
> -"display radix tree, XArray or red-black tree",
> -"[-t [radix|xarray|rbtree]] [-r offset] [-[s|S] struct[.member[,member]]]\n -[x|d] [-o offset] [-l] [-p] [-N] start",
> -" This command dumps the contents of a radix tree, an XAarray, or a red-black",
> -" tree. The arguments are as follows:\n",
> +"display radix tree, XArray, red-black tree or maple tree",
> +"[-t [radix|xarray|rbtree|maple]] [-r offset] [-[s|S] struct[.member[,member]]]\n"
> +" -[x|d] [-o offset] [-l] [-p] [-v] [-N] start",
> +" This command dumps the contents of a radix tree, an XAarray, a red-black",
> +" tree, or a maple tree. The arguments are as follows:\n",
> " -t type The type of tree to dump; the type string can be one of ",
> -" \"radix\", \"rbtree\", or \"xarray\", or alternatively, \"ra\",",
> -" \"rb\" or \"x\" are acceptable. If not specified, rbtree is the",
> -" default type.",
> +" \"radix\", \"rbtree\", \"xarray\", or \"maple\", or alternatively,",
> +" \"ra\", \"rb\", \"x\" or \"m\" are acceptable. If not specified,",
> +" rbtree is the default type.",
> " -r offset If the \"start\" argument is the address of a data structure that",
> -" contains an radix_tree_root, xarray or rb_root structure, then this",
> -" is the offset to that structure member. If the offset is non-zero,",
> -" then this option is required. The offset may be entered in either",
> -" of two manners:",
> +" contains an radix_tree_root, maple_tree, xarray or rb_root",
> +" structure, then this is the offset to that structure member. If",
> +" the offset is non-zero, then this option is required. The offset",
> +" may be entered in either of two manners:",
> " 1. In \"structure.member\" format.",
> " 2. A number of bytes.",
> " -o offset For red-black trees only, the offset of the rb_node within its ",
> @@ -6347,25 +6348,26 @@ char *help_tree[] = {
> " -p Display the node's position information, showing the relationship",
> " between it and the root. For red-black trees, a position that",
> " indicates \"root/l/r\" means that the node is the right child",
> -" of the left child of the root node. For radix trees and xarrays,",
> -" the index, the height, and the slot index values are shown with",
> -" respect to the root.",
> +" of the left child of the root node. For radix trees, xarrays and",
> +" maple trees, the index, the height, and the slot index values are",
> +" shown with respect to the root.",
> " -x Override default output format with hexadecimal format.",
> " -d Override default output format with decimal format.",
> +" -v For maple trees only, showing the contents of each maple tree node.",
> " ",
> " The meaning of the \"start\" argument, which can be expressed either in",
> " hexadecimal format or symbolically, depends upon whether the -N option",
> " is prepended:",
> " ",
> -" start The address of a radix_tree_root, xarray or rb_root structure, or",
> -" the address of a structure containing the radix_tree_root, xarray",
> -" or rb_root structure; if the latter, then the \"-r offset\" option",
> -" must be used if the member offset of the root structure is ",
> -" non-zero.",
> +" start The address of a radix_tree_root, maple_tree, xarray or rb_root",
> +" structure, or the address of a structure containing the",
> +" radix_tree_root, maple_tree, xarray or rb_root structure; if the",
> +" latter, then the \"-r offset\" option must be used if the member",
> +" offset of the root structure is non-zero.",
> " ",
> -" -N start The address of a radix_tree_node, xa_node or rb_node structure,",
> -" bypassing the radix_tree_root, xarray, or rb_root that points",
> -" to it.",
> +" -N start The address of a radix_tree_node, maple_node, xa_node or rb_node",
> +" structure, bypassing the radix_tree_root, maple_tree, xarray, or",
> +" rb_root that points to it.",
> "",
> "\nEXAMPLES",
> " The vmap_area_root is a standalone rb_root structure. Display the ",
Could you please also add a simple example for the maple tree option
to the above EXAMPLES section? That looks more helpful.
BTW: I noticed that you had put several examples to patch[2] log.
Thanks.
Lianbo
> --
> 2.33.1
1 year, 5 months
- 2
- 1
Re: [Crash-utility] [PATCH v3 2/6] Add tree cmd support for maple tree
by lijiang
On Tue, Dec 6, 2022 at 4:40 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 6 Dec 2022 16:40:18 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v3 2/6] Add tree cmd support for maple
> tree
> Message-ID: <20221206084022.58693-3-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 2 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
> ffff9035131754c0
> index: 0 position: root/0/1
> ffff9035131751c8
> index: 1 position: root/0/3
> ffff9035131757b8
> index: 2 position: root/0/4
> ...
>
> crash> tree -t maple 0xffff9034c006aec0 -p -x -s vm_area_struct.vm_start,vm_end
> ffff9035131754c0
> index: 0 position: root/0/1
> vm_start = 0x5613d3c00000,
> vm_end = 0x5613d3d08000,
> ffff9035131751c8
> index: 1 position: root/0/3
> vm_start = 0x5613d3f07000,
> vm_end = 0x5613d3f0b000,
> ffff9035131757b8
> index: 2 position: root/0/4
> vm_start = 0x5613d3f0b000,
> vm_end = 0x5613d3f14000,
> ....
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> defs.h | 1 +
> maple_tree.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++
> tools.c | 64 ++++++++++++++++++++++++++++++++++++++--------------
> 3 files changed, 110 insertions(+), 17 deletions(-)
>
> diff --git a/defs.h b/defs.h
> index 792b007..cc40cba 100644
> --- a/defs.h
> +++ b/defs.h
> @@ -2704,6 +2704,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 << 10)
>
> #define ALIAS_RUNTIME (1)
> #define ALIAS_RCLOCAL (2)
> diff --git a/maple_tree.c b/maple_tree.c
> index e27369b..756dc0a 100644
> --- a/maple_tree.c
> +++ b/maple_tree.c
> @@ -186,6 +186,10 @@ static void do_mt_range64(void *maple_tree_mt, void *entry,
>
> maple_range_64_node = tmp_node + OFFSET(maple_node_mr64);
>
> + if (td && td->flags & TREE_STRUCT_VERBOSE) {
> + dump_mt_range64(maple_range_64_node);
> + }
> +
> for (i = 0; i < mt_slots[maple_range_64]; i++) {
> last = max;
>
> @@ -246,6 +250,10 @@ static void do_mt_arange64(void *maple_tree_mt, void *entry,
>
> maple_arange_64_node = tmp_node + OFFSET(maple_node_ma64);
>
> + if (td && td->flags & TREE_STRUCT_VERBOSE) {
> + dump_mt_arange64(maple_arange_64_node);
> + }
> +
> for (i = 0; i < mt_slots[maple_arange_64]; i++) {
> last = max;
>
> @@ -294,6 +302,50 @@ static void do_mt_entry(void *entry, unsigned long min, unsigned long max,
>
> if (!td)
> return;
> +
> + if (!td->count && 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) * td->structname_args);
> + for (i = 0; i < td->structname_args; i++)
> + e[i] = fill_member_offsets(td->structname[i]);
> + }
> +
> + td->count++;
> +
> + if (td->flags & TREE_STRUCT_VERBOSE) {
> + dump_mt_entry(entry, min, max, depth);
> + } else if (td->flags & VERBOSE && entry)
> + fprintf(fp, "%lx\n", (ulong)entry);
> + if (td->flags & TREE_POSITION_DISPLAY && entry)
> + fprintf(fp, " index: %ld position: %s/%u\n",
> + (*global_index)++, path, index);
> +
> + if (td->structname) {
> + if (td->flags & TREE_STRUCT_RADIX_10)
> + print_radix = 10;
> + else if (td->flags & TREE_STRUCT_RADIX_16)
> + print_radix = 16;
> + else
> + print_radix = 0;
> +
> + for (i = 0; i < td->structname_args; i++) {
> + switch (count_chars(td->structname[i], '.')) {
> + case 0:
> + dump_struct(td->structname[i],
> + (ulong)entry, print_radix);
> + break;
> + default:
> + if (td->flags & TREE_PARSE_MEMBER)
> + dump_struct_members_for_tree(td, i, (ulong)entry);
> + else if (td->flags & TREE_READ_MEMBER)
> + dump_struct_members_fast(e[i], print_radix, (ulong)entry);
> + break;
Seems the above "break" is redundant. The default is at the end of the
switch, it can be dropped.
Thanks.
Lianbo
> + }
> + }
> + }
> }
>
> static void do_mt_node(void *maple_tree_mt, void *entry,
> @@ -313,6 +365,10 @@ static void do_mt_node(void *maple_tree_mt, void *entry,
> readmem((ulong)maple_node, KVADDR, tmp_node, SIZE(maple_node_struct),
> "mt_dump_node read maple_node", FAULT_ON_ERROR);
>
> + if (td && td->flags & TREE_STRUCT_VERBOSE) {
> + dump_mt_node(maple_node, tmp_node, type, min, max, depth);
> + }
> +
> switch (type) {
> case maple_dense:
> for (i = 0; i < mt_slots[maple_dense]; i++) {
> @@ -359,6 +415,12 @@ static int do_maple_tree_traverse(ulong ptr, int is_root,
> "mt_dump read maple_tree", FAULT_ON_ERROR);
> entry = *(void **)(tmp_tree + OFFSET(maple_tree_ma_root));
>
> + if (td && 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(tmp_tree), entry);
> + }
> +
> if (!xa_is_node(entry))
> do_mt_entry(entry, 0, 0, 0, 0, path, &global_index, ops);
> else if (entry) {
> diff --git a/tools.c b/tools.c
> index 39306c1..4e72c60 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()
> @@ -4317,6 +4318,7 @@ cmd_tree()
> struct datatype_member struct_member, *sm;
> struct syment *sp;
> ulong value;
> + char *type_name = NULL;
>
> type_flag = 0;
> root_offset = 0;
> @@ -4324,25 +4326,33 @@ 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);
> }
>
> if (STRNEQ(optarg, "ra"))
> - if (MEMBER_EXISTS("radix_tree_root", "xa_head"))
> + if (MEMBER_EXISTS("radix_tree_root", "xa_head")) {
> type_flag = XARRAY_REQUEST;
> - else
> + type_name = "Xarrays";
> + } else {
> type_flag = RADIXTREE_REQUEST;
> - else if (STRNEQ(optarg, "rb"))
> + type_name = "radix trees";
> + }
> + else if (STRNEQ(optarg, "rb")) {
> type_flag = RBTREE_REQUEST;
> - else if (STRNEQ(optarg, "x"))
> + type_name = "rbtrees";
> + } else if (STRNEQ(optarg, "x")) {
> type_flag = XARRAY_REQUEST;
> - else {
> + type_name = "Xarrays";
> + } else if (STRNEQ(optarg, "m")) {
> + type_flag = MAPLE_REQUEST;
> + type_name = "maple trees";
> + } else {
> error(INFO, "invalid tree type: %s\n", optarg);
> cmd_usage(pc->curcmd, SYNOPSIS);
> }
> @@ -4417,6 +4427,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;
> @@ -4426,13 +4439,14 @@ cmd_tree()
> if (argerrs)
> cmd_usage(pc->curcmd, SYNOPSIS);
>
> - if ((type_flag & (XARRAY_REQUEST|RADIXTREE_REQUEST)) && (td->flags & TREE_LINEAR_ORDER))
> - error(FATAL, "-l option is not applicable to %s\n",
> - type_flag & RADIXTREE_REQUEST ? "radix trees" : "Xarrays");
> + if ((type_flag & (XARRAY_REQUEST|RADIXTREE_REQUEST|MAPLE_REQUEST)) && (td->flags & TREE_LINEAR_ORDER))
> + error(FATAL, "-l option is not applicable to %s\n", type_name);
>
> - if ((type_flag & (XARRAY_REQUEST|RADIXTREE_REQUEST)) && (td->flags & TREE_NODE_OFFSET_ENTERED))
> - error(FATAL, "-o option is not applicable to %s\n",
> - type_flag & RADIXTREE_REQUEST ? "radix trees" : "Xarrays");
> + if ((type_flag & (XARRAY_REQUEST|RADIXTREE_REQUEST|MAPLE_REQUEST)) && (td->flags & TREE_NODE_OFFSET_ENTERED))
> + error(FATAL, "-o option is not applicable to %s\n", type_name);
> +
> + if ((type_flag & (RBTREE_REQUEST|XARRAY_REQUEST|RADIXTREE_REQUEST)) && (td->flags & TREE_STRUCT_VERBOSE))
> + error(FATAL, "-v option is not applicable to %s\n", type_name);
>
> if ((td->flags & TREE_ROOT_OFFSET_ENTERED) &&
> (td->flags & TREE_NODE_POINTER))
> @@ -4506,12 +4520,26 @@ next_arg:
> if (td->flags & TREE_STRUCT_RADIX_16)
> fprintf(fp, "%sTREE_STRUCT_RADIX_16",
> others++ ? "|" : "");
> + if (td->flags & TREE_PARSE_MEMBER)
> + fprintf(fp, "%sTREE_PARSE_MEMBER",
> + others++ ? "|" : "");
> + if (td->flags & TREE_READ_MEMBER)
> + fprintf(fp, "%sTREE_READ_MEMBER",
> + others++ ? "|" : "");
> + if (td->flags & TREE_LINEAR_ORDER)
> + fprintf(fp, "%sTREE_LINEAR_ORDER",
> + others++ ? "|" : "");
> + if (td->flags & TREE_STRUCT_VERBOSE)
> + fprintf(fp, "%sTREE_STRUCT_VERBOSE",
> + others++ ? "|" : "");
> fprintf(fp, ")\n");
> fprintf(fp, " type: ");
> if (type_flag & RADIXTREE_REQUEST)
> fprintf(fp, "radix\n");
> else if (type_flag & XARRAY_REQUEST)
> fprintf(fp, "xarray\n");
> + else if (type_flag & MAPLE_REQUEST)
> + fprintf(fp, "maple\n");
> else
> fprintf(fp, "red-black%s",
> type_flag & RBTREE_REQUEST ?
> @@ -4532,6 +4560,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, 5 months
- 2
- 1
Re: [Crash-utility] [PATCH v3 1/6] Port the maple tree data structures and main functions
by lijiang
Thank you for the update, Tao.
On Tue, Dec 6, 2022 at 4:40 PM <crash-utility-request(a)redhat.com> wrote:
> Date: Tue, 6 Dec 2022 16:40:17 +0800
> From: Tao Liu <ltao(a)redhat.com>
> To: crash-utility(a)redhat.com
> Subject: [Crash-utility] [PATCH v3 1/6] Port the maple tree data
> structures and main functions
> Message-ID: <20221206084022.58693-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 mt_dump() function, and
> all its dependencies from kernel source[3] to crash, to enable crash
> maple tree 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 | 433 +++++++++++++++++++++++++++++++++++++++++++++++++++
> maple_tree.h | 81 ++++++++++
> 4 files changed, 540 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..792b007 100644
> --- a/defs.h
> +++ b/defs.h
> @@ -2181,6 +2181,21 @@ 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_pivot;
> + long maple_arange_64_slot;
> + long maple_arange_64_gap;
> + long maple_arange_64_meta;
> + long maple_range_64_pivot;
> + long maple_range_64_slot;
> + long maple_metadata_end;
> + long maple_metadata_gap;
> };
>
> struct size_table { /* stash of commonly-used sizes */
> @@ -2351,6 +2366,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 +5574,8 @@ int file_dump(ulong, ulong, ulong, int, int);
> 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
> new file mode 100644
> index 0000000..e27369b
> --- /dev/null
> +++ b/maple_tree.c
> @@ -0,0 +1,433 @@
> +// 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"
> +
> +unsigned char *mt_slots = NULL;
> +unsigned char *mt_pivots = NULL;
> +unsigned long mt_max[4] = {0};
> +
> +#define MAPLE_BUFSIZE 512
> +
> +static inline void *mte_to_node(void *maple_enode_entry)
> +{
> + return (void *)((unsigned long)maple_enode_entry & ~MAPLE_NODE_MASK);
> +}
> +
> +static inline enum maple_type mte_node_type(void *maple_enode_entry)
> +{
> + return ((unsigned long)maple_enode_entry >> MAPLE_NODE_TYPE_SHIFT) &
> + MAPLE_NODE_TYPE_MASK;
> +}
> +
> +static inline void *mt_slot(void *maple_tree_mt, void **slots,
> + unsigned char offset)
> +{
> + return slots[offset];
> +}
The argument "maple_tree_mt" is unused, can it be removed from the
above mt_slot()? That can simplify the following implementation of
functions, such as do_mt_entry(), do_mt_node() and do_mt_range64(),
etc.
The mt_slot() is implemented in the kernel with the parameter "mt"
because it is related to the lockdep engine, for crash utility, it
should be safe to drop this.
> +
> +static inline bool ma_is_leaf(const enum maple_type type)
> +{
> + return type < maple_range_64;
> +}
> +
> +/***************For cmd_tree********************/
> +
> +struct maple_tree_ops {
> + void (*entry)(ulong node, ulong slot, const char *path,
> + ulong index, void *private);
> + uint radix;
Seems the "radix" is unused?
Thanks.
Lianbo
> + void *private;
> + bool is_td;
> +};
> +
> +static const char spaces[] = " ";
> +
> +static void do_mt_range64(void *, void *, unsigned long, unsigned long,
> + unsigned int, char *, unsigned long *,
> + struct maple_tree_ops *);
> +static void do_mt_arange64(void *, void *, unsigned long, unsigned long,
> + unsigned int, char *, unsigned long *,
> + struct maple_tree_ops *);
> +static void do_mt_entry(void *, unsigned long, unsigned long, unsigned int,
> + unsigned int, char *, unsigned long *,
> + struct maple_tree_ops *);
> +static void do_mt_node(void *, void *, unsigned long, unsigned long,
> + unsigned int, char *, unsigned long *,
> + struct maple_tree_ops *);
> +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(void *maple_enode_entry)
> +{
> + return ma_is_leaf(mte_node_type(maple_enode_entry));
> +}
> +
> +static unsigned int mt_height(void *maple_tree_mt)
> +{
> + return (*(unsigned int *)(maple_tree_mt + OFFSET(maple_tree_ma_flags)) &
> + MT_FLAGS_HEIGHT_MASK)
> + >> MT_FLAGS_HEIGHT_OFFSET;
> +}
> +
> +static void dump_mt_range64(void *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 **)(maple_range_64_node +
> + OFFSET(maple_range_64_slot)) + i),
> + *((unsigned long *)(maple_range_64_node +
> + OFFSET(maple_range_64_pivot)) + i));
> + fprintf(fp, "%p\n", *((void **)(maple_range_64_node +
> + OFFSET(maple_range_64_slot)) + i));
> +}
> +
> +static void dump_mt_arange64(void *maple_arange_64_node)
> +{
> + int i;
> +
> + fprintf(fp, " contents: ");
> + for (i = 0; i < mt_slots[maple_arange_64]; i++)
> + fprintf(fp, "%lu ",
> + *((unsigned long *)(maple_arange_64_node +
> + OFFSET(maple_arange_64_gap)) + i));
> +
> + fprintf(fp, "| %02X %02X| ",
> + *((unsigned char *)maple_arange_64_node +
> + OFFSET(maple_arange_64_meta) +
> + OFFSET(maple_metadata_end)),
> + *((unsigned char *)maple_arange_64_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 **)(maple_arange_64_node +
> + OFFSET(maple_arange_64_slot)) + i),
> + *((unsigned long *)(maple_arange_64_node +
> + OFFSET(maple_arange_64_pivot)) + i));
> + fprintf(fp, "%p\n",
> + *((void **)(maple_arange_64_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(void *maple_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", maple_node, depth, type,
> + maple_node ? *(void **)(node_data + OFFSET(maple_node_parent))
> + : NULL);
> +}
> +
> +static void do_mt_range64(void *maple_tree_mt, void *entry,
> + unsigned long min, unsigned long max,
> + unsigned int depth, char *path,
> + unsigned long *global_index, struct maple_tree_ops *ops)
> +{
> + void *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);
> + struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> + void *maple_range_64_node;
> +
> + if (SIZE(maple_node_struct) > MAPLE_BUFSIZE)
> + error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node_struct");
> +
> + readmem((ulong)maple_node_m_node, KVADDR, tmp_node, SIZE(maple_node_struct),
> + "mt_dump_range64 read maple_node", FAULT_ON_ERROR);
> +
> + maple_range_64_node = tmp_node + OFFSET(maple_node_mr64);
> +
> + for (i = 0; i < mt_slots[maple_range_64]; i++) {
> + last = max;
> +
> + if (i < (mt_slots[maple_range_64] - 1))
> + last = *((unsigned long *)(maple_range_64_node +
> + OFFSET(maple_range_64_pivot)) + i);
> + else if (!*((void **)(maple_range_64_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(maple_tree_mt,
> + (void **)(maple_range_64_node +
> + OFFSET(maple_range_64_slot)), i),
> + first, last, depth + 1, i, path, global_index, ops);
> + else if (*((void **)(maple_range_64_node +
> + OFFSET(maple_range_64_slot)) + i)) {
> + sprintf(path + len, "/%d", i);
> + do_mt_node(maple_tree_mt,
> + mt_slot(maple_tree_mt,
> + (void **)(maple_range_64_node +
> + OFFSET(maple_range_64_slot)), i),
> + first, last, depth + 1, path, global_index, ops);
> + }
> +
> + if (last == max)
> + break;
> + if (last > max) {
> + fprintf(fp, "node %p last (%lu) > max (%lu) at pivot %d!\n",
> + maple_range_64_node, last, max, i);
> + break;
> + }
> + first = last + 1;
> + }
> +}
> +
> +static void do_mt_arange64(void *maple_tree_mt, void *entry,
> + unsigned long min, unsigned long max,
> + unsigned int depth, char *path,
> + unsigned long *global_index, struct maple_tree_ops *ops)
> +{
> + void *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);
> + struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> + void *maple_arange_64_node;
> +
> + if (SIZE(maple_node_struct) > MAPLE_BUFSIZE)
> + error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node_struct");
> +
> + readmem((ulong)maple_node_m_node, KVADDR, tmp_node, SIZE(maple_node_struct),
> + "mt_dump_arange64 read maple_node", FAULT_ON_ERROR);
> +
> + maple_arange_64_node = tmp_node + OFFSET(maple_node_ma64);
> +
> + for (i = 0; i < mt_slots[maple_arange_64]; i++) {
> + last = max;
> +
> + if (i < (mt_slots[maple_arange_64] - 1))
> + last = *((unsigned long *)(maple_arange_64_node +
> + OFFSET(maple_arange_64_pivot)) + i);
> + else if (! *((void **)(maple_arange_64_node +
> + OFFSET(maple_arange_64_slot)) + i))
> + break;
> + if (last == 0 && i > 0)
> + break;
> +
> + if (leaf)
> + do_mt_entry(mt_slot(maple_tree_mt,
> + (void **)(maple_arange_64_node +
> + OFFSET(maple_arange_64_slot)), i),
> + first, last, depth + 1, i, path, global_index, ops);
> + else if (*((void **)(maple_arange_64_node +
> + OFFSET(maple_arange_64_slot)) + i)) {
> + sprintf(path + len, "/%d", i);
> + do_mt_node(maple_tree_mt,
> + mt_slot(maple_tree_mt,
> + (void **)(maple_arange_64_node +
> + OFFSET(maple_arange_64_slot)), i),
> + first, last, depth + 1, path, global_index, ops);
> + }
> +
> + if (last == max)
> + break;
> + if (last > max) {
> + fprintf(fp, "node %p last (%lu) > max (%lu) at pivot %d!\n",
> + maple_arange_64_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,
> + unsigned long *global_index, struct maple_tree_ops *ops)
> +{
> + int print_radix = 0, i;
> + static struct req_entry **e = NULL;
> + struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> +
> + if (!td)
> + return;
> +}
> +
> +static void do_mt_node(void *maple_tree_mt, void *entry,
> + unsigned long min, unsigned long max,
> + unsigned int depth, char *path,
> + unsigned long *global_index, struct maple_tree_ops *ops)
> +{
> + void *maple_node = mte_to_node(entry);
> + unsigned int type = mte_node_type(entry);
> + unsigned int i;
> + char tmp_node[MAPLE_BUFSIZE];
> + struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> +
> + if (SIZE(maple_node_struct) > MAPLE_BUFSIZE)
> + error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node_struct");
> +
> + readmem((ulong)maple_node, KVADDR, tmp_node, SIZE(maple_node_struct),
> + "mt_dump_node read maple_node", FAULT_ON_ERROR);
> +
> + switch (type) {
> + case maple_dense:
> + for (i = 0; i < mt_slots[maple_dense]; i++) {
> + if (min + i > max)
> + fprintf(fp, "OUT OF RANGE: ");
> + do_mt_entry(mt_slot(maple_tree_mt,
> + (void **)(tmp_node + OFFSET(maple_node_slot)), i),
> + min + i, min + i, depth, i, path, global_index, ops);
> + }
> + break;
> + case maple_leaf_64:
> + case maple_range_64:
> + do_mt_range64(maple_tree_mt, entry, min, max,
> + depth, path, global_index, ops);
> + break;
> + case maple_arange_64:
> + do_mt_arange64(maple_tree_mt, entry, min, max,
> + depth, path, global_index, ops);
> + break;
> + default:
> + fprintf(fp, " UNKNOWN TYPE\n");
> + }
> +}
> +
> +static int do_maple_tree_traverse(ulong ptr, int is_root,
> + struct maple_tree_ops *ops)
> +{
> + char path[BUFSIZE] = {0};
> + unsigned char tmp_tree[MAPLE_BUFSIZE];
> + void *entry;
> + struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> + unsigned long global_index = 0;
> +
> + if (SIZE(maple_tree_struct) > MAPLE_BUFSIZE)
> + error(FATAL, "MAPLE_BUFSIZE should be larger than maple_tree_struct");
> +
> + if (!is_root) {
> + strcpy(path, "direct");
> + do_mt_node(NULL, (void *)ptr, 0,
> + mt_max[mte_node_type((void *)ptr)], 0,
> + path, &global_index, ops);
> + } else {
> + readmem((ulong)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 (!xa_is_node(entry))
> + do_mt_entry(entry, 0, 0, 0, 0, path, &global_index, ops);
> + else if (entry) {
> + strcpy(path, "root");
> + do_mt_node(tmp_tree, entry, 0,
> + mt_max[mte_node_type(entry)], 0,
> + path, &global_index, ops);
> + }
> + }
> + return 0;
> +}
> +
> +int do_mptree(struct tree_data *td)
> +{
> + struct maple_tree_ops ops = {
> + .entry = NULL,
> + .private = td,
> + .radix = 0,
> + .is_td = true,
> + };
> +
> + int is_root = !(td->flags & TREE_NODE_POINTER);
> +
> + do_maple_tree_traverse(td->start, is_root, &ops);
> +
> + return 0;
> +}
> +
> +/***********************************************/
> +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_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_pivot, "maple_range_64", "pivot");
> + MEMBER_OFFSET_INIT(maple_range_64_slot, "maple_range_64", "slot");
> +
> + 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));
> + readmem(symbol_value("mt_slots"), KVADDR, mt_slots,
> + array_len * sizeof(char), "maple_init read mt_slots",
> + RETURN_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",
> + RETURN_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/maple_tree.h b/maple_tree.h
> new file mode 100644
> index 0000000..c423e45
> --- /dev/null
> +++ b/maple_tree.h
> @@ -0,0 +1,81 @@
> +/* 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
> + */
> +
> +enum maple_type {
> + maple_dense,
> + maple_leaf_64,
> + maple_range_64,
> + maple_arange_64,
> +};
> +
> +#define MAPLE_NODE_MASK 255UL
> +
> +#define MT_FLAGS_HEIGHT_OFFSET 0x02
> +#define MT_FLAGS_HEIGHT_MASK 0x7C
> +
> +#define MAPLE_NODE_TYPE_MASK 0x0F
> +#define MAPLE_NODE_TYPE_SHIFT 0x03
> +
> +#define MAPLE_RESERVED_RANGE 4096
> +
> +/*
> + * The following are copied and modified from include/linux/xarray.h
> + */
> +
> +#define XA_ZERO_ENTRY xa_mk_internal(257)
> +
> +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_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;
> +}
> +
> +#endif /* _MAPLE_TREE_H */
> \ No newline at end of file
> --
> 2.33.1
>
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> --
> Crash-utility mailing list
> Crash-utility(a)redhat.com
> https://listman.redhat.com/mailman/listinfo/crash-utility
>
>
> ------------------------------
>
> End of Crash-utility Digest, Vol 207, Issue 6
> *********************************************
>
1 year, 5 months
- 2
- 1
[PATCH v3 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.
v2 -> v3:
1) Remove for_each_vma() macro, and all its dependence functions such as
mas_find(), and use mt_dump()(aka do_maple_tree_traverse()) as a way for
maple tree iteration instead.
2) Make do_maple_tree_info and maple_tree_ops local variable instead of
global variable.
3) Show only valid maple entries by tree cmd.
4) Remove empty structures, such as maple_tree{}/maple_metadata{}, use void *
instead.
5) Other changes based on Kazu and Lianbo's comments.
Tao Liu (6):
Port the maple tree data structures and main functions
Add tree cmd support for maple tree
Add do_maple_tree support for maple tree
Introduce maple tree vma iteration to memory.c
Update the maple tree help info for tree cmd
Dump maple tree offset variables by help -o
Makefile | 12 +-
defs.h | 26 +++
help.c | 46 ++--
maple_tree.c | 641 +++++++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 81 +++++++
memory.c | 327 +++++++++++++++-----------
symbols.c | 32 +++
tools.c | 64 +++--
8 files changed, 1057 insertions(+), 172 deletions(-)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
--
2.33.1
1 year, 5 months
- 2
- 10