Re: [PATCH v4 1/6] Port the maple tree data structures and main functions

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Hi Kazu,

On Wed, Jan 4, 2023 at 3:52 PM HAGIO KAZUHITO(萩尾 一仁) <k-hagio-ab@xxxxxxx> wrote:
>
> Hi Tao Liu,
>
> Thank you for the update, getting better and better.
>
> I would like to make the code readable a little more, so there are some
> comments about variable names and macros below.
>
> On 2023/01/03 21:05, Tao Liu wrote:
> > 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/d19703645b80abe35dff1a88449d074b0b5b1bb1
> > [2]: https://github.com/oracle/linux-uek/commit/91dee01f1ebb6b6587463b6ee6f7bbc4965f91d5
> > [3]: https://github.com/oracle/linux-uek, maple/mainline branch
> >
> > Signed-off-by: Tao Liu <ltao@xxxxxxxxxx>
> > ---
> >   Makefile     |  10 +-
> >   defs.h       |  19 +++
> >   maple_tree.c | 409 +++++++++++++++++++++++++++++++++++++++++++++++++++
> >   maple_tree.h |  82 +++++++++++
> >   4 files changed, 517 insertions(+), 3 deletions(-)
> >   create mode 100644 maple_tree.c
> >   create mode 100644 maple_tree.h
> >
> > diff --git a/Makefile b/Makefile
> > index 1506dd4..102597f 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
> >
> > @@ -539,6 +540,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 08ac4dc..46bfd4a 100644
> > --- a/defs.h
> > +++ b/defs.h
> > @@ -2189,6 +2189,21 @@ struct offset_table {                    /* stash of commonly-used offsets */
> >       long request_queue_hctx_table;
> >       long percpu_counter_counters;
> >       long slab_slab_list;
> > +     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 */
> > @@ -2360,6 +2375,8 @@ struct size_table {         /* stash of commonly-used sizes */
> >       long sbq_wait_state;
> >       long blk_mq_tags;
> >       long percpu_counter;
> > +     long maple_tree;
> > +     long maple_node;
> >   };
> >
> >   struct array_table {
> > @@ -5742,6 +5759,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..0575db8
> > --- /dev/null
> > +++ b/maple_tree.c
> > @@ -0,0 +1,409 @@
> > +// SPDX-License-Identifier: GPL-2.0+
> > +/*
> > + * Maple Tree implementation
> > + * Copyright (c) 2018-2022 Oracle Corporation
> > + * Authors: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> > + *       Matthew Wilcox <willy@xxxxxxxxxxxxx>
> > + *
> > + * 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;
> > +ulong mt_max[4] = {0};
> > +
> > +#define MAPLE_BUFSIZE                        512
> > +
> > +static inline ulong mte_to_node(ulong maple_enode_entry)
> > +{
> > +     return maple_enode_entry & ~MAPLE_NODE_MASK;
> > +}
> > +
> > +static inline enum maple_type mte_node_type(ulong maple_enode_entry)
> > +{
> > +     return (maple_enode_entry >> MAPLE_NODE_TYPE_SHIFT) &
> > +             MAPLE_NODE_TYPE_MASK;
> > +}
> > +
> > +static inline ulong mt_slot(void **slots, unsigned char offset)
> > +{
> > +     return (ulong)slots[offset];
> > +}
> > +
> > +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);
> > +     void *private;
> > +     bool is_td;
> > +};
> > +
> > +static const char spaces[] = "                                ";
> > +
> > +static void do_mt_range64(ulong, ulong, ulong, uint, char *, ulong *,
> > +                       struct maple_tree_ops *);
> > +static void do_mt_arange64(ulong, ulong, ulong, uint, char *, ulong *,
> > +                        struct maple_tree_ops *);
> > +static void do_mt_entry(ulong, ulong, ulong, uint, uint, char *, ulong *,
> > +                     struct maple_tree_ops *);
> > +static void do_mt_node(ulong, ulong, ulong, uint, char *, ulong *,
> > +                    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(ulong min, ulong max, uint 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(ulong entry)
> > +{
> > +       return (entry < MAPLE_RESERVED_RANGE) && xa_is_internal(entry);
> > +}
> > +
> > +static inline bool mte_is_leaf(ulong maple_enode_entry)
> > +{
> > +       return ma_is_leaf(mte_node_type(maple_enode_entry));
> > +}
> > +
> > +static uint mt_height(void *maple_tree_mt)
> > +{
>
> I would like to clarify that the argument is a pointer to a buffer of
> struct maple_tree, so how about "char *mt_buf"?
>
> > +     return (*(uint *)(maple_tree_mt + OFFSET(maple_tree_ma_flags)) &
> > +             MT_FLAGS_HEIGHT_MASK)
> > +            >> MT_FLAGS_HEIGHT_OFFSET;
>
> Any reason for not using UINT()?  For sparc64, it seems we have to use
> the loaders defined by DEF_LOADER(xxx).
>
> > +}
> > +
> > +static void dump_mt_range64(void *maple_range_64_node)
>
> Same as above, and "maple_range_64_" is repeated in this function, so
> how about "char *mr64_buf"?  (As you know, "mr64" is used also in the
> kernel.)
>
> > +{
> > +     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),
> > +                     *((ulong *)(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));
>
> Can these be replaced with
>    VOID_PTR(mr64_buf + OFFSET(maple_range_64_slot) + sizeof(void *) * i)
> and etc.?
>
Thanks a lot for the comment, I didn't think of this way for rewriting
it in v4. It is much better! I have sent v5 to include all the
modifications as you suggested.

Thanks,
Tao Liu

> > +}
> > +
> > +static void dump_mt_arange64(void *maple_arange_64_node)
>
> Same as above, how about "char *ma64_buf"?
>
> > +{
> > +     int i;
> > +
> > +     fprintf(fp, " contents: ");
> > +     for (i = 0; i < mt_slots[maple_arange_64]; i++)
> > +             fprintf(fp, "%lu ",
> > +                     *((ulong *)(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),
> > +                     *((ulong *)(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));
>
> Same as above, ULONG(), UCHAR() and VOID_PTR() can be used?
>
> > +}
> > +
> > +static void dump_mt_entry(ulong entry, ulong min, ulong max, uint depth)
> > +{
> > +     mt_dump_range(min, max, depth);
> > +
> > +     if (xa_is_value(entry))
> > +             fprintf(fp, "value %ld (0x%lx) [0x%lx]\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 (0x%lx)\n", entry);
> > +     else
> > +             fprintf(fp, "0x%lx\n", entry);
> > +}
> > +
> > +static void dump_mt_node(ulong maple_node, char *node_data, uint type,
> > +                      ulong min, ulong max, uint depth)
> > +{
> > +     mt_dump_range(min, max, depth);
> > +
> > +     fprintf(fp, "node 0x%lx depth %d type %d parent %p", maple_node, depth, type,
> > +             maple_node ? VOID_PTR(node_data + OFFSET(maple_node_parent))
> > +                  : NULL);
> > +}
> > +
> > +static void do_mt_range64(ulong entry, ulong min, ulong max,
> > +                       uint depth, char *path, ulong *global_index,
> > +                       struct maple_tree_ops *ops)
> > +{
> > +     ulong maple_node_m_node = mte_to_node(entry);
> > +     unsigned char tmp_node[MAPLE_BUFSIZE];
>
> How about "char node_buf[MAPLE_BUFSIZE]" according to crash's custom?
> (I think usually we use "_buf" for readmem'd struct data :)
>
> > +     bool leaf = mte_is_leaf(entry);
> > +     ulong 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;
>
> char *mr64_buf;
>
> > +
> > +     if (SIZE(maple_node) > MAPLE_BUFSIZE)
> > +             error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node struct");
> > +
> > +     readmem(maple_node_m_node, KVADDR, tmp_node, SIZE(maple_node),
> > +             "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 = *((ulong *)(maple_range_64_node +
> > +                                        OFFSET(maple_range_64_pivot)) + i);
> > +             else if (!*((void **)(maple_range_64_node +
> > +                                   OFFSET(maple_range_64_slot)) + i) &&
>
> Same as above, ULONG() and VOID_PTR() can be used?
>
> > +                      max != mt_max[mte_node_type(entry)])
> > +                     break;
> > +             if (last == 0 && i > 0)
> > +                     break;
> > +             if (leaf)
> > +                     do_mt_entry(mt_slot((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)) {
>
> Ditto.
>
> > +                     sprintf(path + len, "/%d", i);
> > +                     do_mt_node(mt_slot((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(ulong entry, ulong min, ulong max,
> > +                        uint depth, char *path, ulong *global_index,
> > +                        struct maple_tree_ops *ops)
> > +{
> > +     ulong maple_node_m_node = mte_to_node(entry);
> > +     unsigned char tmp_node[MAPLE_BUFSIZE];
>
> char node_buf[MAPLE_BUFSIZE];
>
> > +     bool leaf = mte_is_leaf(entry);
> > +     ulong 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;
>
> char *ma64_buf;
>
> > +
> > +     if (SIZE(maple_node) > MAPLE_BUFSIZE)
> > +             error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node struct");
> > +
> > +     readmem(maple_node_m_node, KVADDR, tmp_node, SIZE(maple_node),
> > +             "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 = *((ulong *)(maple_arange_64_node +
> > +                                        OFFSET(maple_arange_64_pivot)) + i);
> > +             else if (! *((void **)(maple_arange_64_node +
> > +                                    OFFSET(maple_arange_64_slot)) + i))
>
> Same as do_mt_range64(), ULONG() and VOID_PTR() can be used.
>
> > +                     break;
> > +             if (last == 0 && i > 0)
> > +                     break;
> > +
> > +             if (leaf)
> > +                     do_mt_entry(mt_slot((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)) {
>
> Ditto.
>
> > +                     sprintf(path + len, "/%d", i);
> > +                     do_mt_node(mt_slot((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(ulong entry, ulong min, ulong max, uint depth,
> > +                     uint index, char *path, ulong *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(ulong entry, ulong min, ulong max,
> > +                    uint depth, char *path, ulong *global_index,
> > +                    struct maple_tree_ops *ops)
> > +{
> > +     ulong maple_node = mte_to_node(entry);
> > +     uint type = mte_node_type(entry);
> > +     uint i;
> > +     char tmp_node[MAPLE_BUFSIZE];
>
> char node_buf[MAPLE_BUFSIZE];
>
> > +     struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> > +
> > +     if (SIZE(maple_node) > MAPLE_BUFSIZE)
> > +             error(FATAL, "MAPLE_BUFSIZE should be larger than maple_node struct");
> > +
> > +     readmem(maple_node, KVADDR, tmp_node, SIZE(maple_node),
> > +             "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((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(entry, min, max, depth, path, global_index, ops);
> > +             break;
> > +     case maple_arange_64:
> > +             do_mt_arange64(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];
>
> char tree_buf[MAPLE_BUFSIZE];
>
> Thanks,
> Kazu
>
> > +     ulong entry;
> > +     struct tree_data *td = ops->is_td ? (struct tree_data *)ops->private : NULL;
> > +     ulong global_index = 0;
> > +
> > +     if (SIZE(maple_tree) > MAPLE_BUFSIZE)
> > +             error(FATAL, "MAPLE_BUFSIZE should be larger than maple_tree struct");
> > +
> > +     if (!is_root) {
> > +             strcpy(path, "direct");
> > +             do_mt_node(ptr, 0, mt_max[mte_node_type(ptr)],
> > +                        0, path, &global_index, ops);
> > +     } else {
> > +             readmem(ptr, KVADDR, tmp_tree, SIZE(maple_tree),
> > +                     "mt_dump read maple_tree", FAULT_ON_ERROR);
> > +             entry = ULONG(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(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,
> > +             .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, "maple_tree");
> > +     STRUCT_SIZE_INIT(maple_node, "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..369fa9f
> > --- /dev/null
> > +++ b/maple_tree.h
> > @@ -0,0 +1,82 @@
> > +/* 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@xxxxxxxxxx>
> > + *              Matthew Wilcox <willy@xxxxxxxxxxxxx>
> > + *
> > + * eXtensible Arrays
> > + * Copyright (c) 2017 Microsoft Corporation
> > + * Author: Matthew Wilcox <willy@xxxxxxxxxxxxx>
> > + *
> > + * See Documentation/core-api/xarray.rst for how to use the XArray.
> > + */
> > +#include <stdbool.h>
> > +#include <limits.h>
> > +#include <sys/types.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 ulong xa_mk_internal(ulong v)
> > +{
> > +     return (v << 2) | 2;
> > +}
> > +
> > +static inline bool xa_is_internal(ulong entry)
> > +{
> > +     return (entry & 3) == 2;
> > +}
> > +
> > +static inline bool xa_is_node(ulong entry)
> > +{
> > +     return xa_is_internal(entry) && entry > 4096;
> > +}
> > +
> > +static inline bool xa_is_value(ulong entry)
> > +{
> > +     return entry & 1;
> > +}
> > +
> > +static inline bool xa_is_zero(ulong entry)
> > +{
> > +     return entry == XA_ZERO_ENTRY;
> > +}
> > +
> > +static inline unsigned long xa_to_internal(ulong entry)
> > +{
> > +     return entry >> 2;
> > +}
> > +
> > +static inline unsigned long xa_to_value(ulong entry)
> > +{
> > +     return entry >> 1;
> > +}
> > +
> > +#endif /* _MAPLE_TREE_H */
> > \ No newline at end of file

--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://listman.redhat.com/mailman/listinfo/crash-utility
Contribution Guidelines: https://github.com/crash-utility/crash/wiki




[Index of Archives]     [Fedora Development]     [Fedora Desktop]     [Fedora SELinux]     [Yosemite News]     [KDE Users]     [Fedora Tools]

 

Powered by Linux