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 | 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@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;
+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];
+}
+
+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;
+ 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@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>
+
+/*
+ * 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
--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://listman.redhat.com/mailman/listinfo/crash-utility
Contribution Guidelines: https://github.com/crash-utility/crash/wiki
