Signed-off-by: Tao Liu <[email protected]>
---
extensions/maple_tree.c | 336 ++++++++++++++++++++++++++++++++++++++++
extensions/maple_tree.h | 6 +
2 files changed, 342 insertions(+)
create mode 100644 extensions/maple_tree.c
create mode 100644 extensions/maple_tree.h
diff --git a/extensions/maple_tree.c b/extensions/maple_tree.c
new file mode 100644
index 0000000..0cc65bc
--- /dev/null
+++ b/extensions/maple_tree.c
@@ -0,0 +1,336 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include "../btf_info.h"
+#include "../kallsyms.h"
+#include "../makedumpfile.h"
+
+static unsigned char mt_slots[4] = {0};
+static unsigned char mt_pivots[4] = {0};
+static unsigned long mt_max[4] = {0};
+
+static int maple_tree_size;
+static int maple_node_size;
+static int maple_tree_ma_root;
+static int maple_tree_ma_flags;
+static int maple_node_parent;
+static int maple_node_ma64;
+static int maple_node_mr64;
+static int maple_node_slot;
+static int maple_arange_64_pivot;
+static int maple_arange_64_slot;
+static int maple_arange_64_gap;
+static int maple_arange_64_meta;
+static int maple_range_64_pivot;
+static int maple_range_64_slot;
+static int maple_metadata_end;
+static int maple_metadata_gap;
+
+#define MAPLE_BUFSIZE 512
+
+enum {
+ maple_dense_enum,
+ maple_leaf_64_enum,
+ maple_range_64_enum,
+ maple_arange_64_enum,
+};
+
+#define MAPLE_NODE_MASK 255UL
+#define MAPLE_NODE_TYPE_MASK 0x0F
+#define MAPLE_NODE_TYPE_SHIFT 0x03
+#define XA_ZERO_ENTRY xa_mk_internal(257)
+
+static unsigned long xa_mk_internal(unsigned long v)
+{
+ return (v << 2) | 2;
+}
+
+static bool xa_is_internal(unsigned long entry)
+{
+ return (entry & 3) == 2;
+}
+
+static bool xa_is_node(unsigned long entry)
+{
+ return xa_is_internal(entry) && entry > 4096;
+}
+
+static bool xa_is_value(unsigned long entry)
+{
+ return entry & 1;
+}
+
+static bool xa_is_zero(unsigned long entry)
+{
+ return entry == XA_ZERO_ENTRY;
+}
+
+static unsigned long xa_to_internal(unsigned long entry)
+{
+ return entry >> 2;
+}
+
+static unsigned long xa_to_value(unsigned long entry)
+{
+ return entry >> 1;
+}
+
+static unsigned long mte_to_node(unsigned long entry)
+{
+ return entry & ~MAPLE_NODE_MASK;
+}
+
+static unsigned long mte_node_type(unsigned long maple_enode_entry)
+{
+ return (maple_enode_entry >> MAPLE_NODE_TYPE_SHIFT) &
+ MAPLE_NODE_TYPE_MASK;
+}
+
+static unsigned long mt_slot(void **slots, unsigned char offset)
+{
+ return (unsigned long)slots[offset];
+}
+
+static bool ma_is_leaf(unsigned long type)
+{
+ return type < maple_range_64_enum;
+}
+
+static bool mte_is_leaf(unsigned long maple_enode_entry)
+{
+ return ma_is_leaf(mte_node_type(maple_enode_entry));
+}
+
+static void mt_dump_entry(unsigned long entry, unsigned long min,
+ unsigned long max, unsigned int depth,
+ unsigned long **array_out, int *array_len,
+ int *array_cap)
+{
+ unsigned long *tmp;
+ int new_cap = 0;
+
+ if (entry == 0)
+ return;
+ if (*array_out == NULL) {
+ *array_len = 0;
+ new_cap = 4;
+ } else if (*array_len >= *array_cap) {
+ new_cap = *array_cap + (*array_cap >> 1);
+ }
+
+ if (new_cap) {
+ tmp = reallocarray(*array_out, new_cap, sizeof(unsigned long));
+ if (!tmp)
+ goto no_mem;
+ *array_out = tmp;
+ *array_cap = new_cap;
+ }
+
+ (*array_out)[(*array_len)++] = entry;
+ return;
+
+no_mem:
+ printf("%s: Not enough memory!\n", __func__);
+}
+
+static void mt_dump_node(unsigned long entry, unsigned long min,
+ unsigned long max, unsigned int depth,
+ unsigned long **array_out, int *array_len,
+ int *array_cap);
+
+static void mt_dump_range64(unsigned long entry, unsigned long min,
+ unsigned long max, unsigned int depth,
+ unsigned long **array_out, int *array_len,
+ int *array_cap)
+{
+ unsigned long maple_node_m_node = mte_to_node(entry);
+ char node_buf[MAPLE_BUFSIZE];
+ bool leaf = mte_is_leaf(entry);
+ unsigned long first = min, last;
+ int i;
+ char *mr64_buf;
+
+ readmem(VADDR, maple_node_m_node, node_buf, maple_node_size);
+ mr64_buf = node_buf + maple_node_mr64;
+
+ for (i = 0; i < mt_slots[maple_range_64_enum]; i++) {
+ last = max;
+
+ if (i < (mt_slots[maple_range_64_enum] - 1))
+ last = ULONG(mr64_buf + maple_range_64_pivot +
+ sizeof(ulong) * i);
+
+ else if (!VOID_PTR(mr64_buf + maple_range_64_slot +
+ sizeof(void *) * i) &&
+ max != mt_max[mte_node_type(entry)])
+ break;
+ if (last == 0 && i > 0)
+ break;
+ if (leaf)
+ mt_dump_entry(mt_slot((void **)(mr64_buf +
+ maple_range_64_slot), i),
+ first, last, depth + 1, array_out, array_len,
array_cap);
+ else if (VOID_PTR(mr64_buf + maple_range_64_slot +
+ sizeof(void *) * i)) {
+ mt_dump_node(mt_slot((void **)(mr64_buf +
+ maple_range_64_slot), i),
+ first, last, depth + 1, array_out, array_len,
array_cap);
+ }
+
+ if (last == max)
+ break;
+ if (last > max) {
+ printf("node %p last (%lu) > max (%lu) at pivot %d!\n",
+ mr64_buf, last, max, i);
+ break;
+ }
+ first = last + 1;
+ }
+}
+
+static void mt_dump_arange64(unsigned long entry, unsigned long min,
+ unsigned long max, unsigned int depth,
+ unsigned long **array_out, int *array_len,
+ int *array_cap)
+{
+ unsigned long maple_node_m_node = mte_to_node(entry);
+ char node_buf[MAPLE_BUFSIZE];
+ unsigned long first = min, last;
+ int i;
+ char *ma64_buf;
+
+ readmem(VADDR, maple_node_m_node, node_buf, maple_node_size);
+ ma64_buf = node_buf + maple_node_ma64;
+
+ for (i = 0; i < mt_slots[maple_arange_64_enum]; i++) {
+ last = max;
+
+ if (i < (mt_slots[maple_arange_64_enum] - 1))
+ last = ULONG(ma64_buf + maple_arange_64_pivot +
+ sizeof(void *) * i);
+ else if (!VOID_PTR(ma64_buf + maple_arange_64_slot +
+ sizeof(void *) * i))
+ break;
+ if (last == 0 && i > 0)
+ break;
+
+ if (ULONG(ma64_buf + maple_arange_64_slot + sizeof(void *) * i))
+ mt_dump_node(mt_slot((void **)(ma64_buf +
+ maple_arange_64_slot), i),
+ first, last, depth + 1, array_out, array_len,
array_cap);
+
+ if (last == max)
+ break;
+ if (last > max) {
+ printf("node %p last (%lu) > max (%lu) at pivot %d!\n",
+ ma64_buf, last, max, i);
+ break;
+ }
+ first = last + 1;
+ }
+}
+
+static void mt_dump_node(unsigned long entry, unsigned long min,
+ unsigned long max, unsigned int depth,
+ unsigned long **array_out, int *array_len,
+ int *array_cap)
+{
+ unsigned long maple_node = mte_to_node(entry);
+ unsigned long type = mte_node_type(entry);
+ int i;
+ char node_buf[MAPLE_BUFSIZE];
+
+ readmem(VADDR, maple_node, node_buf, maple_node_size);
+
+ switch (type) {
+ case maple_dense_enum:
+ for (i = 0; i < mt_slots[maple_dense_enum]; i++) {
+ if (min + i > max)
+ printf("OUT OF RANGE: ");
+ mt_dump_entry(mt_slot((void **)(node_buf +
maple_node_slot), i),
+ min + i, min + i, depth, array_out, array_len,
array_cap);
+ }
+ break;
+ case maple_leaf_64_enum:
+ case maple_range_64_enum:
+ mt_dump_range64(entry, min, max, depth, array_out, array_len,
array_cap);
+ break;
+ case maple_arange_64_enum:
+ mt_dump_arange64(entry, min, max, depth, array_out, array_len,
array_cap);
+ break;
+ default:
+ printf(" UNKNOWN TYPE\n");
+ }
+}
+
+unsigned long *mt_dump(unsigned long mt, int *array_len)
+{
+ char tree_buf[MAPLE_BUFSIZE];
+ unsigned long entry;
+ unsigned long *array_out = NULL;
+ int array_cap = 0;
+ *array_len = 0;
+
+ readmem(VADDR, mt, tree_buf, maple_tree_size);
+ entry = ULONG(tree_buf + maple_tree_ma_root);
+
+ if (xa_is_node(entry))
+ mt_dump_node(entry, 0, mt_max[mte_node_type(entry)], 0,
+ &array_out, array_len, &array_cap);
+ else if (entry)
+ mt_dump_entry(entry, 0, 0, 0, &array_out, array_len,
&array_cap);
+ else
+ printf("(empty)\n");
+
+ return array_out;
+}
+
+#define MAPLE_STRUCT_SIZE(S) \
+ ({INIT_STRUCT(S); GET_STRUCT_SSIZE(S);})
+#define MAPLE_STRUCT_MEMBER_OFFSET(S, M) \
+ ({INIT_STRUCT_MEMBER(S, M); GET_STRUCT_MEMBER_MOFF(S, M) / 8;})
+
+bool maple_init(void)
+{
+ unsigned long mt_slots_ptr;
+ unsigned long mt_pivots_ptr;
+ struct struct_member_info smi;
+
+ maple_tree_size = MAPLE_STRUCT_SIZE(maple_tree);
+ maple_node_size = MAPLE_STRUCT_SIZE(maple_node);
+ maple_tree_ma_root = MAPLE_STRUCT_MEMBER_OFFSET(maple_tree, ma_root);
+ maple_tree_ma_flags = MAPLE_STRUCT_MEMBER_OFFSET(maple_tree, ma_flags);
+ maple_node_parent = MAPLE_STRUCT_MEMBER_OFFSET(maple_node, parent);
+ maple_node_ma64 = MAPLE_STRUCT_MEMBER_OFFSET(maple_node, ma64);
+ maple_node_mr64 = MAPLE_STRUCT_MEMBER_OFFSET(maple_node, mr64);
+ maple_node_slot = MAPLE_STRUCT_MEMBER_OFFSET(maple_node, slot);
+ maple_arange_64_pivot = MAPLE_STRUCT_MEMBER_OFFSET(maple_arange_64,
pivot);
+ maple_arange_64_slot = MAPLE_STRUCT_MEMBER_OFFSET(maple_arange_64,
slot);
+ maple_arange_64_gap = MAPLE_STRUCT_MEMBER_OFFSET(maple_arange_64, gap);
+ maple_arange_64_meta = MAPLE_STRUCT_MEMBER_OFFSET(maple_arange_64,
meta);
+ maple_range_64_pivot = MAPLE_STRUCT_MEMBER_OFFSET(maple_range_64,
pivot);
+ maple_range_64_slot = MAPLE_STRUCT_MEMBER_OFFSET(maple_range_64, slot);
+ maple_metadata_end = MAPLE_STRUCT_MEMBER_OFFSET(maple_metadata, end);
+ maple_metadata_gap = MAPLE_STRUCT_MEMBER_OFFSET(maple_metadata, gap);
+
+ mt_slots_ptr = get_kallsyms_value_by_name("mt_slots");
+ mt_pivots_ptr = get_kallsyms_value_by_name("mt_pivots");
+ if (mt_slots_ptr == 0 || mt_pivots_ptr == 0) {
+ printf("Invalid mt_slots/mt_pivots address\n");
+ return false;
+ }
+ if (maple_tree_size > MAPLE_BUFSIZE ||
+ maple_node_size > MAPLE_BUFSIZE) {
+ printf("MAPLE_BUFSIZE should be larger than maple_node/tree
struct\n");
+ return false;
+ }
+
+ readmem(VADDR, mt_slots_ptr, mt_slots, sizeof(mt_slots));
+ readmem(VADDR, mt_pivots_ptr, mt_pivots, sizeof(mt_pivots));
+
+ mt_max[maple_dense_enum] = mt_slots[maple_dense_enum];
+ mt_max[maple_leaf_64_enum] = ULONG_MAX;
+ mt_max[maple_range_64_enum] = ULONG_MAX;
+ mt_max[maple_arange_64_enum] = ULONG_MAX;
+
+ return true;
+}
diff --git a/extensions/maple_tree.h b/extensions/maple_tree.h
new file mode 100644
index 0000000..c96624c
--- /dev/null
+++ b/extensions/maple_tree.h
@@ -0,0 +1,6 @@
+#ifndef _MAPLE_TREE_H
+#define _MAPLE_TREE_H
+#include <stdbool.h>
+unsigned long *mt_dump(unsigned long mt, int *array_len);
+bool maple_init(void);
+#endif /* _MAPLE_TREE_H */
\ No newline at end of file
--
2.47.0
