10:10 a.m.
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].
Patch 1: the pure copy-and-paste work, extracting related kernel
structures, functions, constants to crash.
Patch 2: minimal code modification for crash adaption, kernel
structures are kept for member resolving.
Patch 3: modification on crash memory.c to use the maple vma
iteration.
The idea is to make patch 1-3 a POC work.
Patch 4: Get rid of kernel structures by rewriting the structure
member resolving code into the crash way, aka change
"node->member" into "readmem(node) and OFFSET(member)"
Patch 5: print the added variables of offset/size table
Patch 6: Get rid of the compiling-time assgined arrays.
Patch 4-6 will make the POC work formal for use.
[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...
Tao Liu (6):
Port linux maple tree related files to crash
Maple tree kernel code modification for step 1
Introduce maple tree vma iteration to memory.c
Maple tree kernel code modification for step 2
Dump maple tree offset variables by help -o
Remove mt_slots and mt_pivots array assignment
Makefile | 12 +-
defs.h | 19 ++
maple_tree.c | 824 +++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 109 +++++++
maple_tree_vma.h | 34 ++
memory.c | 315 ++++++++++--------
symbols.c | 34 ++
xarray.h | 70 ++++
8 files changed, 1285 insertions(+), 132 deletions(-)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
create mode 100644 maple_tree_vma.h
create mode 100644 xarray.h
--
2.33.1
10:10 a.m.
New subject: [RFC] [PATCH 1/6] Port linux maple tree related files to crash
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.
This patch mainly ports for_each_vma() macro, and all its
dependencies from kernel source[3] to crash, to enable crash
maple tree vma iteration:
maple_tree_vma.h: The interface of maple tree vma iteration.
maple_tree.c: Maple tree main implementation.
maple_tree.h: Maple tree constants and structures.
xarray.h: Maple tree of xarray dependency.
[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>
---
maple_tree.c | 736 +++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 176 ++++++++++++
maple_tree_vma.h | 31 ++
xarray.h | 70 +++++
4 files changed, 1013 insertions(+)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
create mode 100644 maple_tree_vma.h
create mode 100644 xarray.h
diff --git a/maple_tree.c b/maple_tree.c
new file mode 100644
index 0000000..a7db8fa
--- /dev/null
+++ b/maple_tree.c
@@ -0,0 +1,736 @@
+// 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>
+ */
+
+/* Bit 1 indicates the root is a node */
+#define MAPLE_ROOT_NODE 0x02
+/* maple_type stored bit 3-6 */
+#define MAPLE_ENODE_TYPE_SHIFT 0x03
+/* Bit 2 means a NULL somewhere below */
+#define MAPLE_ENODE_NULL 0x04
+
+#define MA_ROOT_PARENT 1
+
+#define MAPLE_PARENT_ROOT 0x01
+
+#define MAPLE_PARENT_SLOT_SHIFT 0x03
+#define MAPLE_PARENT_SLOT_MASK 0xF8
+
+#define MAPLE_PARENT_16B_SLOT_SHIFT 0x02
+#define MAPLE_PARENT_16B_SLOT_MASK 0xFC
+
+#define MAPLE_PARENT_RANGE64 0x06
+#define MAPLE_PARENT_RANGE32 0x04
+#define MAPLE_PARENT_NOT_RANGE16 0x02
+
+static const unsigned char mt_slots[] = {
+ [maple_dense] = MAPLE_NODE_SLOTS,
+ [maple_leaf_64] = MAPLE_RANGE64_SLOTS,
+ [maple_range_64] = MAPLE_RANGE64_SLOTS,
+ [maple_arange_64] = MAPLE_ARANGE64_SLOTS,
+};
+#define mt_slot_count(x) mt_slots[mte_node_type(x)]
+
+static const unsigned char mt_pivots[] = {
+ [maple_dense] = 0,
+ [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1,
+ [maple_range_64] = MAPLE_RANGE64_SLOTS - 1,
+ [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1,
+};
+#define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
+
+#define ma_parent_ptr(x) ((struct maple_pnode *)(x))
+#define ma_enode_ptr(x) ((struct maple_enode *)(x))
+
+static inline bool mas_is_ptr(struct ma_state *mas)
+{
+ return mas->node == MAS_ROOT;
+}
+
+static inline bool mas_is_start(struct ma_state *mas)
+{
+ return mas->node == MAS_START;
+}
+
+static inline void *mte_safe_root(const struct maple_enode *node)
+{
+ return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE);
+}
+
+static inline struct maple_node *mte_to_node(const struct maple_enode *entry)
+{
+ return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK);
+}
+
+static inline enum maple_type mte_node_type(const struct maple_enode *entry)
+{
+ return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
+ MAPLE_NODE_TYPE_MASK;
+}
+
+static inline void *mas_root(struct ma_state *mas)
+{
+ return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree));
+}
+
+static inline struct maple_enode *mas_start(struct ma_state *mas)
+{
+ if (likely(mas_is_start(mas))) {
+ struct maple_enode *root;
+
+ mas->node = MAS_NONE;
+ mas->min = 0;
+ mas->max = ULONG_MAX;
+ mas->depth = 0;
+ mas->offset = 0;
+
+ root = mas_root(mas);
+ /* Tree with nodes */
+ if (likely(xa_is_node(root))) {
+ mas->node = mte_safe_root(root);
+ return NULL;
+ }
+
+ /* empty tree */
+ if (unlikely(!root)) {
+ mas->offset = MAPLE_NODE_SLOTS;
+ return NULL;
+ }
+
+ /* Single entry tree */
+ mas->node = MAS_ROOT;
+ mas->offset = MAPLE_NODE_SLOTS;
+
+ /* Single entry tree. */
+ if (mas->index > 0)
+ return NULL;
+
+ return root;
+ }
+
+ return NULL;
+}
+
+static inline unsigned long *ma_pivots(struct maple_node *node,
+ enum maple_type type)
+{
+ switch (type) {
+ case maple_arange_64:
+ return node->ma64.pivot;
+ case maple_range_64:
+ case maple_leaf_64:
+ return node->mr64.pivot;
+ case maple_dense:
+ return NULL;
+ }
+ return NULL;
+}
+
+static inline struct maple_metadata *ma_meta(struct maple_node *mn,
+ enum maple_type mt)
+{
+ switch (mt) {
+ case maple_arange_64:
+ return &mn->ma64.meta;
+ default:
+ return &mn->mr64.meta;
+ }
+}
+
+static inline unsigned char ma_meta_end(struct maple_node *mn,
+ enum maple_type mt)
+{
+ struct maple_metadata *meta = ma_meta(mn, mt);
+
+ return meta->end;
+}
+
+static inline unsigned char ma_data_end(struct maple_node *node,
+ enum maple_type type,
+ unsigned long *pivots,
+ unsigned long max)
+{
+ unsigned char offset;
+
+ if (type == maple_arange_64)
+ return ma_meta_end(node, type);
+
+ offset = mt_pivots[type] - 1;
+ if (likely(!pivots[offset]))
+ return ma_meta_end(node, type);
+
+ if (likely(pivots[offset] == max))
+ return offset;
+
+ return mt_pivots[type];
+}
+
+static inline bool ma_dead_node(const struct maple_node *node)
+{
+ struct maple_node *parent = (void *)((unsigned long)
+ node->parent & ~MAPLE_NODE_MASK);
+
+ return (parent == node);
+}
+
+static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)
+{
+ switch (mt) {
+ default:
+ case maple_arange_64:
+ return mn->ma64.slot;
+ case maple_range_64:
+ case maple_leaf_64:
+ return mn->mr64.slot;
+ case maple_dense:
+ return mn->slot;
+ }
+}
+
+static inline void *mt_slot(const struct maple_tree *mt,
+ void __rcu **slots, unsigned char offset)
+{
+ return rcu_dereference_check(slots[offset], mt_locked(mt));
+}
+
+static inline bool ma_is_leaf(const enum maple_type type)
+{
+ return type < maple_range_64;
+}
+
+static inline void *mtree_range_walk(struct ma_state *mas)
+{
+ unsigned long *pivots;
+ unsigned char offset;
+ struct maple_node *node;
+ struct maple_enode *next, *last;
+ enum maple_type type;
+ void __rcu **slots;
+ unsigned char end;
+ unsigned long max, min;
+ unsigned long prev_max, prev_min;
+
+ last = next = mas->node;
+ prev_min = min = mas->min;
+ max = mas->max;
+ do {
+ offset = 0;
+ last = next;
+ node = mte_to_node(next);
+ type = mte_node_type(next);
+ pivots = ma_pivots(node, type);
+ end = ma_data_end(node, type, pivots, max);
+ if (unlikely(ma_dead_node(node)))
+ goto dead_node;
+
+ if (pivots[offset] >= mas->index) {
+ prev_max = max;
+ prev_min = min;
+ max = pivots[offset];
+ goto next;
+ }
+
+ do {
+ offset++;
+ } while ((offset < end) && (pivots[offset] < mas->index));
+
+ prev_min = min;
+ min = pivots[offset - 1] + 1;
+ prev_max = max;
+ if (likely(offset < end && pivots[offset]))
+ max = pivots[offset];
+
+next:
+ slots = ma_slots(node, type);
+ next = mt_slot(mas->tree, slots, offset);
+ if (unlikely(ma_dead_node(node)))
+ goto dead_node;
+ } while (!ma_is_leaf(type));
+
+ mas->offset = offset;
+ mas->index = min;
+ mas->last = max;
+ mas->min = prev_min;
+ mas->max = prev_max;
+ mas->node = last;
+ return (void *) next;
+
+dead_node:
+ mas_reset(mas);
+ return NULL;
+}
+
+static inline void *mas_state_walk(struct ma_state *mas)
+{
+ void *entry;
+
+ entry = mas_start(mas);
+ if (mas_is_none(mas))
+ return NULL;
+
+ if (mas_is_ptr(mas))
+ return entry;
+
+ return mtree_range_walk(mas);
+}
+
+static inline bool mas_searchable(struct ma_state *mas)
+{
+ if (mas_is_none(mas))
+ return false;
+
+ if (mas_is_ptr(mas))
+ return false;
+
+ return true;
+}
+
+static inline struct maple_node *mas_mn(const struct ma_state *mas)
+{
+ return mte_to_node(mas->node);
+}
+
+static inline unsigned long
+mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
+{
+ if (likely(offset))
+ return pivots[offset - 1] + 1;
+
+ return mas->min;
+}
+
+static inline void *mas_slot(struct ma_state *mas, void __rcu **slots,
+ unsigned char offset)
+{
+ return mt_slot(mas->tree, slots, offset);
+}
+
+static inline unsigned long
+mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots,
+ unsigned char piv, enum maple_type type)
+{
+ if (piv >= mt_pivots[type])
+ return mas->max;
+
+ return pivots[piv];
+}
+
+static inline void *mas_next_nentry(struct ma_state *mas,
+ struct maple_node *node, unsigned long max, enum maple_type type)
+{
+ unsigned char count;
+ unsigned long pivot;
+ unsigned long *pivots;
+ void __rcu **slots;
+ void *entry;
+
+ if (mas->last == mas->max) {
+ mas->index = mas->max;
+ return NULL;
+ }
+
+ pivots = ma_pivots(node, type);
+ slots = ma_slots(node, type);
+ mas->index = mas_safe_min(mas, pivots, mas->offset);
+ if (ma_dead_node(node))
+ return NULL;
+
+ if (mas->index > max)
+ return NULL;
+
+ count = ma_data_end(node, type, pivots, mas->max);
+ if (mas->offset > count)
+ return NULL;
+
+ while (mas->offset < count) {
+ pivot = pivots[mas->offset];
+ entry = mas_slot(mas, slots, mas->offset);
+ if (ma_dead_node(node))
+ return NULL;
+
+ if (entry)
+ goto found;
+
+ if (pivot >= max)
+ return NULL;
+
+ mas->index = pivot + 1;
+ mas->offset++;
+ }
+
+ if (mas->index > mas->max) {
+ mas->index = mas->last;
+ return NULL;
+ }
+
+ pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
+ entry = mas_slot(mas, slots, mas->offset);
+ if (ma_dead_node(node))
+ return NULL;
+
+ if (!pivot)
+ return NULL;
+
+ if (!entry)
+ return NULL;
+
+found:
+ mas->last = pivot;
+ return entry;
+}
+
+static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
+{
+
+retry:
+ mas_set(mas, index);
+ mas_state_walk(mas);
+ if (mas_is_start(mas))
+ goto retry;
+
+ return;
+
+}
+
+static inline bool ma_is_root(struct maple_node *node)
+{
+ return ((unsigned long)node->parent & MA_ROOT_PARENT);
+}
+
+static inline struct maple_node *mte_parent(const struct maple_enode *enode)
+{
+ return (void *)((unsigned long)
+ (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);
+}
+
+static inline unsigned long mte_parent_slot_mask(unsigned long parent)
+{
+ /* Note bit 1 == 0 means 16B */
+ if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
+ return MAPLE_PARENT_SLOT_MASK;
+
+ return MAPLE_PARENT_16B_SLOT_MASK;
+}
+
+static inline bool mt_is_alloc(struct maple_tree *mt)
+{
+ return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
+}
+
+static inline
+enum maple_type mte_parent_enum(struct maple_enode *p_enode,
+ struct maple_tree *mt)
+{
+ unsigned long p_type;
+
+ p_type = (unsigned long)p_enode;
+ if (p_type & MAPLE_PARENT_ROOT)
+ return 0; /* Validated in the caller. */
+
+ p_type &= MAPLE_NODE_MASK;
+ p_type = p_type & ~(MAPLE_PARENT_ROOT | mte_parent_slot_mask(p_type));
+
+ switch (p_type) {
+ case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */
+ if (mt_is_alloc(mt))
+ return maple_arange_64;
+ return maple_range_64;
+ }
+
+ return 0;
+}
+
+static inline
+enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *enode)
+{
+ return mte_parent_enum(ma_enode_ptr(mte_to_node(enode)->parent), mas->tree);
+}
+
+static inline unsigned long mte_parent_shift(unsigned long parent)
+{
+ /* Note bit 1 == 0 means 16B */
+ if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
+ return MAPLE_PARENT_SLOT_SHIFT;
+
+ return MAPLE_PARENT_16B_SLOT_SHIFT;
+}
+
+static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
+{
+ unsigned long val = (unsigned long) mte_to_node(enode)->parent;
+
+ /* Root. */
+ if (val & 1)
+ return 0;
+
+ /*
+ * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost
+ * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT
+ */
+ return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val);
+}
+
+static inline struct maple_enode *mt_mk_node(const struct maple_node *node,
+ enum maple_type type)
+{
+ return (void *)((unsigned long)node |
+ (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL);
+}
+
+static inline bool mte_is_root(const struct maple_enode *node)
+{
+ return ma_is_root(mte_to_node(node));
+}
+
+static int mas_ascend(struct ma_state *mas)
+{
+ struct maple_enode *p_enode; /* parent enode. */
+ struct maple_enode *a_enode; /* ancestor enode. */
+ struct maple_node *a_node; /* ancestor node. */
+ struct maple_node *p_node; /* parent node. */
+ unsigned char a_slot;
+ enum maple_type a_type;
+ unsigned long min, max;
+ unsigned long *pivots;
+ unsigned char offset;
+ bool set_max = false, set_min = false;
+
+ a_node = mas_mn(mas);
+ if (ma_is_root(a_node)) {
+ mas->offset = 0;
+ return 0;
+ }
+
+ p_node = mte_parent(mas->node);
+ if (unlikely(a_node == p_node))
+ return 1;
+ a_type = mas_parent_enum(mas, mas->node);
+ offset = mte_parent_slot(mas->node);
+ a_enode = mt_mk_node(p_node, a_type);
+
+ /* Check to make sure all parent information is still accurate */
+ if (p_node != mte_parent(mas->node))
+ return 1;
+
+ mas->node = a_enode;
+ mas->offset = offset;
+
+ if (mte_is_root(a_enode)) {
+ mas->max = ULONG_MAX;
+ mas->min = 0;
+ return 0;
+ }
+
+ min = 0;
+ max = ULONG_MAX;
+ do {
+ p_enode = a_enode;
+ a_type = mas_parent_enum(mas, p_enode);
+ a_node = mte_parent(p_enode);
+ a_slot = mte_parent_slot(p_enode);
+ pivots = ma_pivots(a_node, a_type);
+ a_enode = mt_mk_node(a_node, a_type);
+
+ if (!set_min && a_slot) {
+ set_min = true;
+ min = pivots[a_slot - 1] + 1;
+ }
+
+ if (!set_max && a_slot < mt_pivots[a_type]) {
+ set_max = true;
+ max = pivots[a_slot];
+ }
+
+ if (unlikely(ma_dead_node(a_node)))
+ return 1;
+
+ if (unlikely(ma_is_root(a_node)))
+ break;
+
+ } while (!set_min || !set_max);
+
+ mas->max = max;
+ mas->min = min;
+ return 0;
+}
+
+static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
+ unsigned long max)
+{
+ unsigned long min, pivot;
+ unsigned long *pivots;
+ struct maple_enode *enode;
+ int level = 0;
+ unsigned char offset;
+ enum maple_type mt;
+ void __rcu **slots;
+
+ if (mas->max >= max)
+ goto no_entry;
+
+ level = 0;
+ do {
+ if (ma_is_root(node))
+ goto no_entry;
+
+ min = mas->max + 1;
+ if (min > max)
+ goto no_entry;
+
+ if (unlikely(mas_ascend(mas)))
+ return 1;
+
+ offset = mas->offset;
+ level++;
+ node = mas_mn(mas);
+ mt = mte_node_type(mas->node);
+ pivots = ma_pivots(node, mt);
+ } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max)));
+
+ slots = ma_slots(node, mt);
+ pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
+ while (unlikely(level > 1)) {
+ /* Descend, if necessary */
+ enode = mas_slot(mas, slots, offset);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
+ mas->node = enode;
+ level--;
+ node = mas_mn(mas);
+ mt = mte_node_type(mas->node);
+ slots = ma_slots(node, mt);
+ pivots = ma_pivots(node, mt);
+ offset = 0;
+ pivot = pivots[0];
+ }
+
+ enode = mas_slot(mas, slots, offset);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
+ mas->node = enode;
+ mas->min = min;
+ mas->max = pivot;
+ return 0;
+
+no_entry:
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
+ mas->node = MAS_NONE;
+ return 0;
+}
+
+static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
+{
+ void *entry = NULL;
+ struct maple_enode *prev_node;
+ struct maple_node *node;
+ unsigned char offset;
+ unsigned long last;
+ enum maple_type mt;
+
+ last = mas->last;
+retry:
+ offset = mas->offset;
+ prev_node = mas->node;
+ node = mas_mn(mas);
+ mt = mte_node_type(mas->node);
+ mas->offset++;
+ if (unlikely(mas->offset >= mt_slots[mt])) {
+ mas->offset = mt_slots[mt] - 1;
+ goto next_node;
+ }
+
+ while (!mas_is_none(mas)) {
+ entry = mas_next_nentry(mas, node, limit, mt);
+ if (unlikely(ma_dead_node(node))) {
+ mas_rewalk(mas, last);
+ goto retry;
+ }
+
+ if (likely(entry))
+ return entry;
+
+ if (unlikely((mas->index > limit)))
+ break;
+
+next_node:
+ prev_node = mas->node;
+ offset = mas->offset;
+ if (unlikely(mas_next_node(mas, node, limit))) {
+ mas_rewalk(mas, last);
+ goto retry;
+ }
+ mas->offset = 0;
+ node = mas_mn(mas);
+ mt = mte_node_type(mas->node);
+ }
+
+ mas->index = mas->last = limit;
+ mas->offset = offset;
+ mas->node = prev_node;
+ return NULL;
+}
+
+void *mas_walk(struct ma_state *mas)
+{
+ void *entry;
+
+retry:
+ entry = mas_state_walk(mas);
+ if (mas_is_start(mas))
+ goto retry;
+
+ if (mas_is_ptr(mas)) {
+ if (!mas->index) {
+ mas->last = 0;
+ } else {
+ mas->index = 1;
+ mas->last = ULONG_MAX;
+ }
+ return entry;
+ }
+
+ if (mas_is_none(mas)) {
+ mas->index = 0;
+ mas->last = ULONG_MAX;
+ }
+
+ return entry;
+}
+
+void *mas_find(struct ma_state *mas, unsigned long max)
+{
+ if (unlikely(mas_is_paused(mas))) {
+ if (unlikely(mas->last == ULONG_MAX)) {
+ mas->node = MAS_NONE;
+ return NULL;
+ }
+ mas->node = MAS_START;
+ mas->index = ++mas->last;
+ }
+
+ if (unlikely(mas_is_start(mas))) {
+ /* First run or continue */
+ void *entry;
+
+ if (mas->index > max)
+ return NULL;
+
+ entry = mas_walk(mas);
+ if (entry)
+ return entry;
+ }
+
+ if (unlikely(!mas_searchable(mas)))
+ return NULL;
+
+ /* Retries on dead nodes handled by mas_next_entry */
+ return mas_next_entry(mas, max);
+}
\ No newline at end of file
diff --git a/maple_tree.h b/maple_tree.h
new file mode 100644
index 0000000..c4b2828
--- /dev/null
+++ b/maple_tree.h
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+#ifndef _LINUX_MAPLE_TREE_H
+#define _LINUX_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>
+ */
+
+struct maple_tree {
+ union {
+ spinlock_t ma_lock;
+ lockdep_map_p ma_external_lock;
+ };
+ void __rcu *ma_root;
+ unsigned int ma_flags;
+};
+
+typedef struct maple_enode *maple_enode; /* encoded node */
+typedef struct maple_pnode *maple_pnode; /* parent node */
+
+struct maple_metadata {
+ unsigned char end;
+ unsigned char gap;
+};
+
+struct ma_state {
+ struct maple_tree *tree; /* The tree we're operating in */
+ unsigned long index; /* The index we're operating on - range start */
+ unsigned long last; /* The last index we're operating on - range end */
+ struct maple_enode *node; /* The node containing this entry */
+ unsigned long min; /* The minimum index of this node - implied pivot min */
+ unsigned long max; /* The maximum index of this node - implied pivot max */
+ struct maple_alloc *alloc; /* Allocated nodes for this operation */
+ unsigned char depth; /* depth of tree descent during write */
+ unsigned char offset;
+ unsigned char mas_flags;
+};
+
+enum maple_type {
+ maple_dense,
+ maple_leaf_64,
+ maple_range_64,
+ maple_arange_64,
+};
+
+#define MAS_START ((struct maple_enode *)1UL)
+#define MAS_ROOT ((struct maple_enode *)5UL)
+#define MAS_NONE ((struct maple_enode *)9UL)
+#define MAS_PAUSE ((struct maple_enode *)17UL)
+#define MA_ERROR(err) \
+ ((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
+
+#define MA_STATE(name, mt, first, end) \
+ struct ma_state name = { \
+ .tree = mt, \
+ .index = first, \
+ .last = end, \
+ .node = MAS_START, \
+ .min = 0, \
+ .max = ULONG_MAX, \
+ }
+
+#if defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64)
+/* 64bit sizes */
+#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
+#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
+#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */
+#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */
+#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
+#else
+/* 32bit sizes */
+#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
+#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
+#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
+#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */
+#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
+#endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
+
+#define MAPLE_NODE_MASK 255UL
+
+#define MT_FLAGS_ALLOC_RANGE 0x01
+#define MT_FLAGS_USE_RCU 0x02
+#define MT_FLAGS_HEIGHT_OFFSET 0x02
+#define MT_FLAGS_HEIGHT_MASK 0x7C
+#define MT_FLAGS_LOCK_MASK 0x300
+#define MT_FLAGS_LOCK_IRQ 0x100
+#define MT_FLAGS_LOCK_BH 0x200
+#define MT_FLAGS_LOCK_EXTERN 0x300
+
+#define MAPLE_HEIGHT_MAX 31
+
+#define MAPLE_NODE_TYPE_MASK 0x0F
+#define MAPLE_NODE_TYPE_SHIFT 0x03
+
+#define MAPLE_RESERVED_RANGE 4096
+
+struct maple_range_64 {
+ struct maple_pnode *parent;
+ unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
+ union {
+ void __rcu *slot[MAPLE_RANGE64_SLOTS];
+ struct {
+ void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
+ struct maple_metadata meta;
+ };
+ };
+};
+
+struct maple_arange_64 {
+ struct maple_pnode *parent;
+ unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
+ void __rcu *slot[MAPLE_ARANGE64_SLOTS];
+ unsigned long gap[MAPLE_ARANGE64_SLOTS];
+ struct maple_metadata meta;
+};
+
+struct maple_alloc {
+ unsigned long total;
+ unsigned char node_count;
+ unsigned int request_count;
+ struct maple_alloc *slot[MAPLE_ALLOC_SLOTS];
+};
+
+struct maple_node {
+ union {
+ struct {
+ struct maple_pnode *parent;
+ void __rcu *slot[MAPLE_NODE_SLOTS];
+ };
+ struct {
+ void *pad;
+ struct rcu_head rcu;
+ struct maple_enode *piv_parent;
+ unsigned char parent_slot;
+ enum maple_type type;
+ unsigned char slot_len;
+ unsigned int ma_flags;
+ };
+ struct maple_range_64 mr64;
+ struct maple_arange_64 ma64;
+ struct maple_alloc alloc;
+ };
+};
+
+static inline void mas_reset(struct ma_state *mas)
+{
+ mas->node = MAS_START;
+}
+
+static inline
+void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)
+{
+ mas->index = start;
+ mas->last = last;
+ mas->node = MAS_START;
+}
+
+static inline void mas_set(struct ma_state *mas, unsigned long index)
+{
+
+ mas_set_range(mas, index, index);
+}
+
+static inline bool mas_is_none(struct ma_state *mas)
+{
+ return mas->node == MAS_NONE;
+}
+
+static inline bool mas_is_paused(struct ma_state *mas)
+{
+ return mas->node == MAS_PAUSE;
+}
+
+#endif /*_LINUX_MAPLE_TREE_H */
\ No newline at end of file
diff --git a/maple_tree_vma.h b/maple_tree_vma.h
new file mode 100644
index 0000000..5a9fc46
--- /dev/null
+++ b/maple_tree_vma.h
@@ -0,0 +1,31 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#define for_each_vma(vmi, vma) while ((vma = vma_next(&(vmi))) != NULL)
+
+struct vma_iterator {
+ struct ma_state mas;
+};
+
+#define VMA_ITERATOR(name, mm, addr) \
+ struct vma_iterator name = { \
+ .mas = { \
+ .tree = &mm->mm_mt, \
+ .index = addr, \
+ .node = MAS_START, \
+ }, \
+ }
+
+static inline
+struct vm_area_struct *vma_find(struct vma_iterator *vmi, unsigned long max)
+{
+ return mas_find(&vmi->mas, max);
+}
+
+static inline struct vm_area_struct *vma_next(struct vma_iterator *vmi)
+{
+ /*
+ * Uses vma_find() to get the first VMA when the iterator starts.
+ * Calling mas_next() could skip the first entry.
+ */
+ return vma_find(vmi, ULONG_MAX);
+}
\ No newline at end of file
diff --git a/xarray.h b/xarray.h
new file mode 100644
index 0000000..2e14ec7
--- /dev/null
+++ b/xarray.h
@@ -0,0 +1,70 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+#ifndef _LINUX_XARRAY_H
+#define _LINUX_XARRAY_H
+/*
+ * 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.
+ */
+
+#define MAX_ERRNO 4095
+#define XA_ZERO_ENTRY xa_mk_internal(257)
+#define XA_RETRY_ENTRY xa_mk_internal(256)
+
+static inline void *xa_mk_internal(unsigned long v)
+{
+ return (void *)((v << 2) | 2);
+}
+
+static inline bool xa_is_internal(const void *entry)
+{
+ return ((unsigned long)entry & 3) == 2;
+}
+
+static inline bool xa_is_err(const void *entry)
+{
+ return unlikely(xa_is_internal(entry) &&
+ entry >= xa_mk_internal(-MAX_ERRNO));
+}
+
+static inline int xa_err(void *entry)
+{
+ /* xa_to_internal() would not do sign extension. */
+ if (xa_is_err(entry))
+ return (long)entry >> 2;
+ return 0;
+}
+
+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 unlikely(entry == XA_ZERO_ENTRY);
+}
+
+static inline unsigned long xa_to_internal(const void *entry)
+{
+ return (unsigned long)entry >> 2;
+}
+
+static inline unsigned long xa_to_value(const void *entry)
+{
+ return (unsigned long)entry >> 1;
+}
+
+static inline bool xa_is_advanced(const void *entry)
+{
+ return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY);
+}
+
+#endif /* _LINUX_XARRAY_H */
\ No newline at end of file
--
2.33.1
3:33 a.m.
New subject: [RFC] [PATCH 1/6] Port linux maple tree related files to crash
On 2022/09/20 0:10, 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.
This patch mainly ports for_each_vma() macro, and all its
dependencies from kernel source[3] to crash, to enable crash
maple tree vma iteration:
maple_tree_vma.h: The interface of maple tree vma iteration.
maple_tree.c: Maple tree main implementation.
maple_tree.h: Maple tree constants and structures.
xarray.h: Maple tree of xarray dependency.
Is it possible to put the other two header files into the maple_tree.h?
[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
This code looks a bit old, e.g. the following two lines are not found
in the current mm-stable [1], though the maple tree will come soon
mainline.
typedef struct maple_enode *maple_enode; /* encoded node */
typedef struct maple_pnode *maple_pnode; /* parent node */
[1] https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
maple_tree.c | 736 +++++++++++++++++++++++++++++++++++++++++++++++
maple_tree.h | 176 ++++++++++++
maple_tree_vma.h | 31 ++
xarray.h | 70 +++++
4 files changed, 1013 insertions(+)
create mode 100644 maple_tree.c
create mode 100644 maple_tree.h
create mode 100644 maple_tree_vma.h
create mode 100644 xarray.h
diff --git a/maple_tree.c b/maple_tree.c
new file mode 100644
index 0000000..a7db8fa
--- /dev/null
+++ b/maple_tree.c
@@ -0,0 +1,736 @@
+// 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>
For the copied parts, please add their kernel file path like
"This code comes from lib/maple_tree.c".
Thanks,
Kazu
10:10 a.m.
New subject: [RFC] [PATCH 2/6] Maple tree kernel code modification for step 1
We will modify the ported kernel source code, making it
compatible with crash.
For maple tree iteration, struct ma_state is used to record
the iteration state, which need to be stored in crash and will
be dynamically changed at runtime. Other structures such as
maple_tree/maple_node/maple_metadata... are stored in vmcore,
their members will be resolved when iterating.
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,
so crash know what the member offset is when compiling. It cannot
handle the case if the struct member changes, or the struct compiling
differs between crash and kernel due to padding/alignment or optimization
reasons.
So we divide the whole procedure into 2 steps:
1) Keep the kernel structures unchange, aka let the 2nd one work.
2) Get rid of kernel structure dependency, aka replace the 2nd with
1st one.
This patch handles step 1, mainly made the following changes:
a. Remove/Rewrite the rcu related prefix and functions.
b. Remove likely()/unlikely() macros.
c. Change the following functions' signature:
ma_dead_node() vma_find()
mas_next_nentry() vma_next()
-----
mte_parent() mas_parent_enum()
mte_parent_slot() mte_is_root()
VMA_ITERATOR()
The first 4 are changed for necessary crash compatibility.
The last 5 are changed for simplify the argument passing.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
Makefile | 10 ++-
maple_tree.c | 184 ++++++++++++++++++++++++++++-------------------
maple_tree.h | 24 ++++---
maple_tree_vma.h | 14 ++--
xarray.h | 12 ++--
5 files changed, 147 insertions(+), 97 deletions(-)
diff --git a/Makefile b/Makefile
index 79aef17..d545bc0 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 xarray.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/maple_tree.c b/maple_tree.c
index a7db8fa..21a2226 100644
--- a/maple_tree.c
+++ b/maple_tree.c
@@ -6,6 +6,10 @@
* Matthew Wilcox <willy(a)infradead.org>
*/
+#include "maple_tree.h"
+#include "defs.h"
+#include "xarray.h"
+
/* Bit 1 indicates the root is a node */
#define MAPLE_ROOT_NODE 0x02
/* maple_type stored bit 3-6 */
@@ -74,12 +78,15 @@ static inline enum maple_type mte_node_type(const struct maple_enode
*entry)
static inline void *mas_root(struct ma_state *mas)
{
- return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree));
+ struct maple_tree tree;
+ readmem(mas->tree, KVADDR, &tree, sizeof(tree),
+ "mas_root read maple_tree", FAULT_ON_ERROR);
+ return tree.ma_root;
}
static inline struct maple_enode *mas_start(struct ma_state *mas)
{
- if (likely(mas_is_start(mas))) {
+ if (mas_is_start(mas)) {
struct maple_enode *root;
mas->node = MAS_NONE;
@@ -90,13 +97,13 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
root = mas_root(mas);
/* Tree with nodes */
- if (likely(xa_is_node(root))) {
+ if (xa_is_node(root)) {
mas->node = mte_safe_root(root);
return NULL;
}
/* empty tree */
- if (unlikely(!root)) {
+ if (!root) {
mas->offset = MAPLE_NODE_SLOTS;
return NULL;
}
@@ -160,24 +167,25 @@ static inline unsigned char ma_data_end(struct maple_node *node,
return ma_meta_end(node, type);
offset = mt_pivots[type] - 1;
- if (likely(!pivots[offset]))
+ if (!pivots[offset])
return ma_meta_end(node, type);
- if (likely(pivots[offset] == max))
+ if (pivots[offset] == max)
return offset;
return mt_pivots[type];
}
-static inline bool ma_dead_node(const struct maple_node *node)
+static inline bool ma_dead_node(const struct maple_node *node,
+ const struct maple_node *orig_node)
{
struct maple_node *parent = (void *)((unsigned long)
node->parent & ~MAPLE_NODE_MASK);
- return (parent == node);
+ return (parent == orig_node);
}
-static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)
+static inline void **ma_slots(struct maple_node *mn, enum maple_type mt)
{
switch (mt) {
default:
@@ -192,9 +200,9 @@ static inline void __rcu **ma_slots(struct maple_node *mn, enum
maple_type mt)
}
static inline void *mt_slot(const struct maple_tree *mt,
- void __rcu **slots, unsigned char offset)
+ void **slots, unsigned char offset)
{
- return rcu_dereference_check(slots[offset], mt_locked(mt));
+ return slots[offset];
}
static inline bool ma_is_leaf(const enum maple_type type)
@@ -209,11 +217,13 @@ static inline void *mtree_range_walk(struct ma_state *mas)
struct maple_node *node;
struct maple_enode *next, *last;
enum maple_type type;
- void __rcu **slots;
+ void **slots;
unsigned char end;
unsigned long max, min;
unsigned long prev_max, prev_min;
+ struct maple_node tmp_node;
+
last = next = mas->node;
prev_min = min = mas->min;
max = mas->max;
@@ -222,9 +232,11 @@ static inline void *mtree_range_walk(struct ma_state *mas)
last = next;
node = mte_to_node(next);
type = mte_node_type(next);
- pivots = ma_pivots(node, type);
- end = ma_data_end(node, type, pivots, max);
- if (unlikely(ma_dead_node(node)))
+ readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mtree_range_walk read maple_node", FAULT_ON_ERROR);
+ pivots = ma_pivots(&tmp_node, type);
+ end = ma_data_end(&tmp_node, type, pivots, max);
+ if (ma_dead_node(&tmp_node, node))
goto dead_node;
if (pivots[offset] >= mas->index) {
@@ -241,13 +253,13 @@ static inline void *mtree_range_walk(struct ma_state *mas)
prev_min = min;
min = pivots[offset - 1] + 1;
prev_max = max;
- if (likely(offset < end && pivots[offset]))
+ if (offset < end && pivots[offset])
max = pivots[offset];
next:
- slots = ma_slots(node, type);
+ slots = ma_slots(&tmp_node, type);
next = mt_slot(mas->tree, slots, offset);
- if (unlikely(ma_dead_node(node)))
+ if (ma_dead_node(&tmp_node, node))
goto dead_node;
} while (!ma_is_leaf(type));
@@ -297,13 +309,13 @@ static inline struct maple_node *mas_mn(const struct ma_state *mas)
static inline unsigned long
mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
{
- if (likely(offset))
+ if (offset)
return pivots[offset - 1] + 1;
return mas->min;
}
-static inline void *mas_slot(struct ma_state *mas, void __rcu **slots,
+static inline void *mas_slot(struct ma_state *mas, void **slots,
unsigned char offset)
{
return mt_slot(mas->tree, slots, offset);
@@ -320,12 +332,13 @@ mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots,
}
static inline void *mas_next_nentry(struct ma_state *mas,
- struct maple_node *node, unsigned long max, enum maple_type type)
+ struct maple_node *node, unsigned long max,
+ enum maple_type type, struct maple_node *orig_node)
{
unsigned char count;
unsigned long pivot;
unsigned long *pivots;
- void __rcu **slots;
+ void **slots;
void *entry;
if (mas->last == mas->max) {
@@ -336,7 +349,7 @@ static inline void *mas_next_nentry(struct ma_state *mas,
pivots = ma_pivots(node, type);
slots = ma_slots(node, type);
mas->index = mas_safe_min(mas, pivots, mas->offset);
- if (ma_dead_node(node))
+ if (ma_dead_node(node, orig_node))
return NULL;
if (mas->index > max)
@@ -349,7 +362,7 @@ static inline void *mas_next_nentry(struct ma_state *mas,
while (mas->offset < count) {
pivot = pivots[mas->offset];
entry = mas_slot(mas, slots, mas->offset);
- if (ma_dead_node(node))
+ if (ma_dead_node(node, orig_node))
return NULL;
if (entry)
@@ -369,7 +382,7 @@ static inline void *mas_next_nentry(struct ma_state *mas,
pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
entry = mas_slot(mas, slots, mas->offset);
- if (ma_dead_node(node))
+ if (ma_dead_node(node, orig_node))
return NULL;
if (!pivot)
@@ -393,7 +406,6 @@ retry:
goto retry;
return;
-
}
static inline bool ma_is_root(struct maple_node *node)
@@ -401,16 +413,16 @@ static inline bool ma_is_root(struct maple_node *node)
return ((unsigned long)node->parent & MA_ROOT_PARENT);
}
-static inline struct maple_node *mte_parent(const struct maple_enode *enode)
+static inline struct maple_node *mte_parent(const struct maple_node *node)
{
return (void *)((unsigned long)
- (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);
+ (node->parent) & ~MAPLE_NODE_MASK);
}
static inline unsigned long mte_parent_slot_mask(unsigned long parent)
{
/* Note bit 1 == 0 means 16B */
- if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
+ if (parent & MAPLE_PARENT_NOT_RANGE16)
return MAPLE_PARENT_SLOT_MASK;
return MAPLE_PARENT_16B_SLOT_MASK;
@@ -426,6 +438,7 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
struct maple_tree *mt)
{
unsigned long p_type;
+ struct maple_tree tmp_tree;
p_type = (unsigned long)p_enode;
if (p_type & MAPLE_PARENT_ROOT)
@@ -436,7 +449,9 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
switch (p_type) {
case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */
- if (mt_is_alloc(mt))
+ readmem(mt, KVADDR, &tmp_tree, sizeof(tmp_tree),
+ "mte_parent_enum read maple_tree", FAULT_ON_ERROR);
+ if (mt_is_alloc(&tmp_tree))
return maple_arange_64;
return maple_range_64;
}
@@ -445,23 +460,23 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
}
static inline
-enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *enode)
+enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_node *node)
{
- return mte_parent_enum(ma_enode_ptr(mte_to_node(enode)->parent), mas->tree);
+ return mte_parent_enum(ma_enode_ptr(node->parent), mas->tree);
}
static inline unsigned long mte_parent_shift(unsigned long parent)
{
/* Note bit 1 == 0 means 16B */
- if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
+ if (parent & MAPLE_PARENT_NOT_RANGE16)
return MAPLE_PARENT_SLOT_SHIFT;
return MAPLE_PARENT_16B_SLOT_SHIFT;
}
-static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
+static inline unsigned int mte_parent_slot(const struct maple_node *node)
{
- unsigned long val = (unsigned long) mte_to_node(enode)->parent;
+ unsigned long val = (unsigned long) node->parent;
/* Root. */
if (val & 1)
@@ -481,9 +496,9 @@ static inline struct maple_enode *mt_mk_node(const struct maple_node
*node,
(type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL);
}
-static inline bool mte_is_root(const struct maple_enode *node)
+static inline bool mte_is_root(struct maple_node *node)
{
- return ma_is_root(mte_to_node(node));
+ return ma_is_root(node);
}
static int mas_ascend(struct ma_state *mas)
@@ -498,28 +513,35 @@ static int mas_ascend(struct ma_state *mas)
unsigned long *pivots;
unsigned char offset;
bool set_max = false, set_min = false;
+ struct maple_node tmp_node;
a_node = mas_mn(mas);
- if (ma_is_root(a_node)) {
+ readmem(a_node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_ascend read maple_node", FAULT_ON_ERROR);
+ if (ma_is_root(&tmp_node)) {
mas->offset = 0;
return 0;
}
- p_node = mte_parent(mas->node);
- if (unlikely(a_node == p_node))
+ readmem(mte_to_node(mas->node), KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_ascend read maple_node", FAULT_ON_ERROR);
+ p_node = mte_parent(&tmp_node);
+ if (a_node == p_node)
return 1;
- a_type = mas_parent_enum(mas, mas->node);
- offset = mte_parent_slot(mas->node);
+ a_type = mas_parent_enum(mas, &tmp_node);
+ offset = mte_parent_slot(&tmp_node);
a_enode = mt_mk_node(p_node, a_type);
/* Check to make sure all parent information is still accurate */
- if (p_node != mte_parent(mas->node))
+ if (p_node != mte_parent(&tmp_node))
return 1;
mas->node = a_enode;
mas->offset = offset;
- if (mte_is_root(a_enode)) {
+ readmem(mte_to_node(a_enode), KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_ascend read maple_node", FAULT_ON_ERROR);
+ if (mte_is_root(&tmp_node)) {
mas->max = ULONG_MAX;
mas->min = 0;
return 0;
@@ -529,11 +551,15 @@ static int mas_ascend(struct ma_state *mas)
max = ULONG_MAX;
do {
p_enode = a_enode;
- a_type = mas_parent_enum(mas, p_enode);
- a_node = mte_parent(p_enode);
- a_slot = mte_parent_slot(p_enode);
- pivots = ma_pivots(a_node, a_type);
- a_enode = mt_mk_node(a_node, a_type);
+ readmem(mte_to_node(p_enode), KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_ascend read maple_node", FAULT_ON_ERROR);
+ a_type = mas_parent_enum(mas, &tmp_node);
+ a_node = mte_parent(&tmp_node);
+ a_slot = mte_parent_slot(&tmp_node);
+ readmem(a_node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_ascend read maple_node", FAULT_ON_ERROR);
+ pivots = ma_pivots(&tmp_node, a_type);
+ a_enode = mt_mk_node(&tmp_node, a_type);
if (!set_min && a_slot) {
set_min = true;
@@ -545,10 +571,10 @@ static int mas_ascend(struct ma_state *mas)
max = pivots[a_slot];
}
- if (unlikely(ma_dead_node(a_node)))
+ if (ma_dead_node(&tmp_node, a_node))
return 1;
- if (unlikely(ma_is_root(a_node)))
+ if (ma_is_root(&tmp_node))
break;
} while (!set_min || !set_max);
@@ -567,50 +593,58 @@ static inline int mas_next_node(struct ma_state *mas, struct
maple_node *node,
int level = 0;
unsigned char offset;
enum maple_type mt;
- void __rcu **slots;
+ void **slots;
+
+ struct maple_node tmp_node;
if (mas->max >= max)
goto no_entry;
level = 0;
+ readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_next_node read maple_node", FAULT_ON_ERROR);
do {
- if (ma_is_root(node))
+ if (ma_is_root(&tmp_node))
goto no_entry;
min = mas->max + 1;
if (min > max)
goto no_entry;
- if (unlikely(mas_ascend(mas)))
+ if (mas_ascend(mas))
return 1;
offset = mas->offset;
level++;
node = mas_mn(mas);
mt = mte_node_type(mas->node);
- pivots = ma_pivots(node, mt);
- } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max)));
+ readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_next_node read maple_node", FAULT_ON_ERROR);
+ pivots = ma_pivots(&tmp_node, mt);
+ } while (offset == ma_data_end(&tmp_node, mt, pivots, mas->max));
- slots = ma_slots(node, mt);
+ slots = ma_slots(&tmp_node, mt);
pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
- while (unlikely(level > 1)) {
+ while (level > 1) {
/* Descend, if necessary */
enode = mas_slot(mas, slots, offset);
- if (unlikely(ma_dead_node(node)))
+ if (ma_dead_node(&tmp_node, node))
return 1;
mas->node = enode;
level--;
node = mas_mn(mas);
mt = mte_node_type(mas->node);
- slots = ma_slots(node, mt);
- pivots = ma_pivots(node, mt);
+ readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_next_node read maple_node", FAULT_ON_ERROR);
+ slots = ma_slots(&tmp_node, mt);
+ pivots = ma_pivots(&tmp_node, mt);
offset = 0;
pivot = pivots[0];
}
enode = mas_slot(mas, slots, offset);
- if (unlikely(ma_dead_node(node)))
+ if (ma_dead_node(&tmp_node, node))
return 1;
mas->node = enode;
@@ -619,7 +653,7 @@ static inline int mas_next_node(struct ma_state *mas, struct
maple_node *node,
return 0;
no_entry:
- if (unlikely(ma_dead_node(node)))
+ if (ma_dead_node(&tmp_node, node))
return 1;
mas->node = MAS_NONE;
@@ -635,6 +669,8 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long
limit)
unsigned long last;
enum maple_type mt;
+ struct maple_node tmp_node;
+
last = mas->last;
retry:
offset = mas->offset;
@@ -642,28 +678,30 @@ retry:
node = mas_mn(mas);
mt = mte_node_type(mas->node);
mas->offset++;
- if (unlikely(mas->offset >= mt_slots[mt])) {
+ if (mas->offset >= mt_slots[mt]) {
mas->offset = mt_slots[mt] - 1;
goto next_node;
}
while (!mas_is_none(mas)) {
- entry = mas_next_nentry(mas, node, limit, mt);
- if (unlikely(ma_dead_node(node))) {
+ readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ "mas_next_entry read maple_node", FAULT_ON_ERROR);
+ entry = mas_next_nentry(mas, &tmp_node, limit, mt, node);
+ if (ma_dead_node(&tmp_node, node)) {
mas_rewalk(mas, last);
goto retry;
}
- if (likely(entry))
+ if (entry)
return entry;
- if (unlikely((mas->index > limit)))
+ if ((mas->index > limit))
break;
next_node:
prev_node = mas->node;
offset = mas->offset;
- if (unlikely(mas_next_node(mas, node, limit))) {
+ if (mas_next_node(mas, node, limit)) {
mas_rewalk(mas, last);
goto retry;
}
@@ -707,8 +745,8 @@ retry:
void *mas_find(struct ma_state *mas, unsigned long max)
{
- if (unlikely(mas_is_paused(mas))) {
- if (unlikely(mas->last == ULONG_MAX)) {
+ if (mas_is_paused(mas)) {
+ if (mas->last == ULONG_MAX) {
mas->node = MAS_NONE;
return NULL;
}
@@ -716,7 +754,7 @@ void *mas_find(struct ma_state *mas, unsigned long max)
mas->index = ++mas->last;
}
- if (unlikely(mas_is_start(mas))) {
+ if (mas_is_start(mas)) {
/* First run or continue */
void *entry;
@@ -728,7 +766,7 @@ void *mas_find(struct ma_state *mas, unsigned long max)
return entry;
}
- if (unlikely(!mas_searchable(mas)))
+ if (!mas_searchable(mas))
return NULL;
/* Retries on dead nodes handled by mas_next_entry */
diff --git a/maple_tree.h b/maple_tree.h
index c4b2828..a5a131e 100644
--- a/maple_tree.h
+++ b/maple_tree.h
@@ -1,19 +1,24 @@
/* SPDX-License-Identifier: GPL-2.0+ */
-#ifndef _LINUX_MAPLE_TREE_H
-#define _LINUX_MAPLE_TREE_H
+#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>
*/
+#include <stdint.h>
+#include <stdbool.h>
+
+typedef uint32_t spinlock_t;
+typedef uint32_t lockdep_map_p;
struct maple_tree {
union {
spinlock_t ma_lock;
lockdep_map_p ma_external_lock;
};
- void __rcu *ma_root;
+ void *ma_root;
unsigned int ma_flags;
};
@@ -96,13 +101,15 @@ enum maple_type {
#define MAPLE_RESERVED_RANGE 4096
+typedef struct rcu_head { unsigned char x[16]; } rcu_head;
+
struct maple_range_64 {
struct maple_pnode *parent;
unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
union {
- void __rcu *slot[MAPLE_RANGE64_SLOTS];
+ void *slot[MAPLE_RANGE64_SLOTS];
struct {
- void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
+ void *pad[MAPLE_RANGE64_SLOTS - 1];
struct maple_metadata meta;
};
};
@@ -111,7 +118,7 @@ struct maple_range_64 {
struct maple_arange_64 {
struct maple_pnode *parent;
unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
- void __rcu *slot[MAPLE_ARANGE64_SLOTS];
+ void *slot[MAPLE_ARANGE64_SLOTS];
unsigned long gap[MAPLE_ARANGE64_SLOTS];
struct maple_metadata meta;
};
@@ -127,7 +134,7 @@ struct maple_node {
union {
struct {
struct maple_pnode *parent;
- void __rcu *slot[MAPLE_NODE_SLOTS];
+ void *slot[MAPLE_NODE_SLOTS];
};
struct {
void *pad;
@@ -172,5 +179,4 @@ static inline bool mas_is_paused(struct ma_state *mas)
{
return mas->node == MAS_PAUSE;
}
-
-#endif /*_LINUX_MAPLE_TREE_H */
\ No newline at end of file
+#endif /* _MAPLE_TREE_H */
\ No newline at end of file
diff --git a/maple_tree_vma.h b/maple_tree_vma.h
index 5a9fc46..0e006dc 100644
--- a/maple_tree_vma.h
+++ b/maple_tree_vma.h
@@ -1,4 +1,5 @@
/* SPDX-License-Identifier: GPL-2.0 */
+#include "maple_tree.h"
#define for_each_vma(vmi, vma) while ((vma = vma_next(&(vmi))) != NULL)
@@ -6,22 +7,23 @@ struct vma_iterator {
struct ma_state mas;
};
-#define VMA_ITERATOR(name, mm, addr) \
+#define VMA_ITERATOR(name, mm_mt, addr) \
struct vma_iterator name = { \
.mas = { \
- .tree = &mm->mm_mt, \
+ .tree = mm_mt, \
.index = addr, \
.node = MAS_START, \
}, \
}
-static inline
-struct vm_area_struct *vma_find(struct vma_iterator *vmi, unsigned long max)
+extern void *mas_find(struct ma_state *, unsigned long);
+
+void *vma_find(struct vma_iterator *vmi, unsigned long max)
{
- return mas_find(&vmi->mas, max);
+ return mas_find(&vmi->mas, max);
}
-static inline struct vm_area_struct *vma_next(struct vma_iterator *vmi)
+void *vma_next(struct vma_iterator *vmi)
{
/*
* Uses vma_find() to get the first VMA when the iterator starts.
diff --git a/xarray.h b/xarray.h
index 2e14ec7..084382d 100644
--- a/xarray.h
+++ b/xarray.h
@@ -1,6 +1,6 @@
/* SPDX-License-Identifier: GPL-2.0+ */
-#ifndef _LINUX_XARRAY_H
-#define _LINUX_XARRAY_H
+#ifndef _XARRAY_H
+#define _XARRAY_H
/*
* eXtensible Arrays
* Copyright (c) 2017 Microsoft Corporation
@@ -25,8 +25,8 @@ static inline bool xa_is_internal(const void *entry)
static inline bool xa_is_err(const void *entry)
{
- return unlikely(xa_is_internal(entry) &&
- entry >= xa_mk_internal(-MAX_ERRNO));
+ return xa_is_internal(entry) &&
+ entry >= xa_mk_internal(-MAX_ERRNO);
}
static inline int xa_err(void *entry)
@@ -49,7 +49,7 @@ static inline bool xa_is_value(const void *entry)
static inline bool xa_is_zero(const void *entry)
{
- return unlikely(entry == XA_ZERO_ENTRY);
+ return entry == XA_ZERO_ENTRY;
}
static inline unsigned long xa_to_internal(const void *entry)
@@ -67,4 +67,4 @@ static inline bool xa_is_advanced(const void *entry)
return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY);
}
-#endif /* _LINUX_XARRAY_H */
\ No newline at end of file
+#endif /* _XARRAY_H */
\ No newline at end of file
--
2.33.1
10:10 a.m.
New subject: [RFC] [PATCH 3/6] Introduce maple tree vma iteration to memory.c
Since memory.c:vm_area_dump will iterate all vma, this patch mainly
introduces maple tree vma iteration to it.
We extract the code which handles each vma into a function. If
mm_struct_mmap exist, aka the linked list of vma iteration available,
we goto the original way; if not and mm_struct_mm_mt exist, aka
maple tree is available, then we goto the maple tree vma iteration.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
Makefile | 4 +-
defs.h | 1 +
maple_tree_vma.h | 3 +-
memory.c | 311 ++++++++++++++++++++++++++++-------------------
4 files changed, 188 insertions(+), 131 deletions(-)
diff --git a/Makefile b/Makefile
index d545bc0..4d7549c 100644
--- a/Makefile
+++ b/Makefile
@@ -59,7 +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 xarray.h
+MAPLE_TREE_HFILES=maple_tree.h xarray.h maple_tree_vma.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 \
@@ -355,7 +355,7 @@ filesys.o: ${GENERIC_HFILES} filesys.c
help.o: ${GENERIC_HFILES} help.c
${CC} -c ${CRASH_CFLAGS} help.c ${WARNING_OPTIONS} ${WARNING_ERROR}
-memory.o: ${GENERIC_HFILES} memory.c
+memory.o: ${GENERIC_HFILES} ${MAPLE_TREE_HFILES} memory.c
${CC} -c ${CRASH_CFLAGS} memory.c ${WARNING_OPTIONS} ${WARNING_ERROR}
test.o: ${GENERIC_HFILES} test.c
diff --git a/defs.h b/defs.h
index afdcf6c..d4be477 100644
--- a/defs.h
+++ b/defs.h
@@ -1332,6 +1332,7 @@ struct offset_table { /* stash of commonly-used
offsets */
long percpu_struct_halt_ra;
long percpu_struct_halt_pv;
long mm_struct_mmap;
+ long mm_struct_mm_mt;
long mm_struct_pgd;
long mm_struct_rss;
long mm_struct_anon_rss;
diff --git a/maple_tree_vma.h b/maple_tree_vma.h
index 0e006dc..0b861ff 100644
--- a/maple_tree_vma.h
+++ b/maple_tree_vma.h
@@ -1,7 +1,8 @@
/* SPDX-License-Identifier: GPL-2.0 */
#include "maple_tree.h"
-#define for_each_vma(vmi, vma) while ((vma = vma_next(&(vmi))) != NULL)
+#define for_each_vma(vmi, vma) \
+ while ((vma = (ulong)vma_next(&(vmi))) != 0)
struct vma_iterator {
struct ma_state mas;
diff --git a/memory.c b/memory.c
index 7339f0c..00f7c9a 100644
--- a/memory.c
+++ b/memory.c
@@ -21,6 +21,7 @@
#include <ctype.h>
#include <netinet/in.h>
#include <byteswap.h>
+#include "maple_tree_vma.h"
struct meminfo { /* general purpose memory information structure */
ulong cache; /* used by the various memory searching/dumping */
@@ -362,6 +363,7 @@ vm_init(void)
MEMBER_OFFSET_INIT(task_struct_mm, "task_struct", "mm");
MEMBER_OFFSET_INIT(mm_struct_mmap, "mm_struct", "mmap");
+ MEMBER_OFFSET_INIT(mm_struct_mm_mt, "mm_struct", "mm_mt");
MEMBER_OFFSET_INIT(mm_struct_pgd, "mm_struct", "pgd");
MEMBER_OFFSET_INIT(mm_struct_rss, "mm_struct", "rss");
if (!VALID_MEMBER(mm_struct_rss))
@@ -3866,7 +3868,7 @@ bailout:
* for references -- and only then does a display
*/
-#define PRINT_VM_DATA() \
+#define PRINT_VM_DATA(buf4, buf5, tm) \
{ \
fprintf(fp, "%s %s ", \
mkstring(buf4, VADDR_PRLEN, CENTER|LJUST, "MM"), \
@@ -3888,7 +3890,7 @@ bailout:
mkstring(buf5, 8, CENTER|LJUST, NULL)); \
}
-#define PRINT_VMA_DATA() \
+#define PRINT_VMA_DATA(buf1, buf2, buf3, buf4, vma)
\
fprintf(fp, "%s%s%s%s%s %6llx%s%s\n", \
mkstring(buf4, VADDR_PRLEN, CENTER|LJUST|LONG_HEX, MKSTR(vma)), \
space(MINSPACE), \
@@ -3917,18 +3919,164 @@ bailout:
(DO_REF_SEARCH(X) && (string_exists(S)) &&
FILENAME_COMPONENT((S),(X)->str))
#define VM_REF_FOUND(X) ((X) && ((X)->cmdflags & VM_REF_HEADER))
-ulong
-vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
-{
- struct task_context *tc;
+struct handle_each_vm_area_args {
+ ulong task;
+ ulong flag;
+ ulong vaddr;
+ struct reference *ref;
+ char *vma_header;
+ char *buf1;
+ char *buf2;
+ char *buf3;
+ char *buf4;
+ char *buf5;
ulong vma;
+ char **vma_buf;
+ struct task_mem_usage *tm;
+ int *found;
+ int *single_vma_found;
+ unsigned int radix;
+ struct task_context *tc;
+ ulong *single_vma;
+};
+
+ulong handle_each_vm_area(struct handle_each_vm_area_args *args)
+{
+ char *dentry_buf, *file_buf;
ulong vm_start;
ulong vm_end;
ulong vm_next, vm_mm;
- char *dentry_buf, *vma_buf, *file_buf;
ulonglong vm_flags;
ulong vm_file, inode;
ulong dentry, vfsmnt;
+
+ if ((args->flag & PHYSADDR) && !DO_REF_SEARCH(args->ref))
+ fprintf(fp, "%s", args->vma_header);
+
+ inode = 0;
+ BZERO(args->buf1, BUFSIZE);
+ *(args->vma_buf) = fill_vma_cache(args->vma);
+
+ vm_mm = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_mm));
+ vm_end = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_end));
+ vm_start = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_start));
+ vm_flags = get_vm_flags(*(args->vma_buf));
+ vm_file = ULONG(*(args->vma_buf) + OFFSET(vm_area_struct_vm_file));
+
+ if (args->flag & PRINT_SINGLE_VMA) {
+ if (args->vma != *(args->single_vma))
+ return 0;
+ fprintf(fp, "%s", args->vma_header);
+ *(args->single_vma_found) = TRUE;
+ }
+
+ if (args->flag & PRINT_VMA_STRUCTS) {
+ dump_struct("vm_area_struct", args->vma, args->radix);
+ return 0;
+ }
+
+ if (vm_file && !(args->flag & VERIFY_ADDR)) {
+ file_buf = fill_file_cache(vm_file);
+ dentry = ULONG(file_buf + OFFSET(file_f_dentry));
+ dentry_buf = NULL;
+ if (dentry) {
+ dentry_buf = fill_dentry_cache(dentry);
+ if (VALID_MEMBER(file_f_vfsmnt)) {
+ vfsmnt = ULONG(file_buf +
+ OFFSET(file_f_vfsmnt));
+ get_pathname(dentry, args->buf1, BUFSIZE,
+ 1, vfsmnt);
+ } else {
+ get_pathname(dentry, args->buf1, BUFSIZE,
+ 1, 0);
+ }
+ }
+ if ((args->flag & PRINT_INODES) && dentry) {
+ inode = ULONG(dentry_buf +
+ OFFSET(dentry_d_inode));
+ }
+ }
+
+ if (!(args->flag & UVADDR) || ((args->flag & UVADDR) &&
+ ((args->vaddr >= vm_start) && (args->vaddr < vm_end)))) {
+ *(args->found) = TRUE;
+
+ if (args->flag & VERIFY_ADDR)
+ return args->vma;
+
+ if (DO_REF_SEARCH(args->ref)) {
+ if (VM_REF_CHECK_HEXVAL(args->ref, args->vma) ||
+ VM_REF_CHECK_HEXVAL(args->ref, (ulong)vm_flags) ||
+ VM_REF_CHECK_STRING(args->ref, args->buf1)) {
+ if (!(args->ref->cmdflags & VM_REF_HEADER)) {
+ print_task_header(fp, args->tc, 0);
+ PRINT_VM_DATA(args->buf4, args->buf5, args->tm);
+ args->ref->cmdflags |= VM_REF_HEADER;
+ }
+ if (!(args->ref->cmdflags & VM_REF_VMA) ||
+ (args->ref->cmdflags & VM_REF_PAGE)) {
+ fprintf(fp, "%s", args->vma_header);
+ args->ref->cmdflags |= VM_REF_VMA;
+ args->ref->cmdflags &= ~VM_REF_PAGE;
+ args->ref->ref1 = args->vma;
+ }
+ PRINT_VMA_DATA(args->buf1, args->buf2,
+ args->buf3, args->buf4, args->vma);
+ }
+
+ if (vm_area_page_dump(args->vma, args->task,
+ vm_start, vm_end, vm_mm, args->ref)) {
+ if (!(args->ref->cmdflags & VM_REF_HEADER)) {
+ print_task_header(fp, args->tc, 0);
+ PRINT_VM_DATA(args->buf4, args->buf5, args->tm);
+ args->ref->cmdflags |= VM_REF_HEADER;
+ }
+ if (!(args->ref->cmdflags & VM_REF_VMA) ||
+ (args->ref->ref1 != args->vma)) {
+ fprintf(fp, "%s", args->vma_header);
+ PRINT_VMA_DATA(args->buf1, args->buf2,
+ args->buf3, args->buf4, args->vma);
+ args->ref->cmdflags |= VM_REF_VMA;
+ args->ref->ref1 = args->vma;
+ }
+
+ args->ref->cmdflags |= VM_REF_DISPLAY;
+ vm_area_page_dump(args->vma, args->task,
+ vm_start, vm_end, vm_mm, args->ref);
+ args->ref->cmdflags &= ~VM_REF_DISPLAY;
+ }
+
+ return 0;
+ }
+
+ if (inode) {
+ fprintf(fp, "%lx%s%s%s%s%s%6llx%s%lx %s\n",
+ args->vma, space(MINSPACE),
+ mkstring(args->buf2, UVADDR_PRLEN, RJUST|LONG_HEX,
+ MKSTR(vm_start)), space(MINSPACE),
+ mkstring(args->buf3, UVADDR_PRLEN, RJUST|LONG_HEX,
+ MKSTR(vm_end)), space(MINSPACE),
+ vm_flags, space(MINSPACE), inode, args->buf1);
+ } else {
+ PRINT_VMA_DATA(args->buf1, args->buf2,
+ args->buf3, args->buf4, args->vma);
+
+ if (args->flag & (PHYSADDR|PRINT_SINGLE_VMA))
+ vm_area_page_dump(args->vma, args->task,
+ vm_start, vm_end, vm_mm, args->ref);
+ }
+
+ if (args->flag & UVADDR)
+ return args->vma;
+ }
+ return 0;
+}
+
+ulong
+vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference *ref)
+{
+ struct task_context *tc;
+ ulong vma;
ulong single_vma;
unsigned int radix;
int single_vma_found;
@@ -3940,6 +4088,7 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference
*ref)
char buf4[BUFSIZE];
char buf5[BUFSIZE];
char vma_header[BUFSIZE];
+ char *vma_buf;
tc = task_to_context(task);
tm = &task_mem_usage;
@@ -3973,14 +4122,14 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference
*ref)
if (VM_REF_CHECK_HEXVAL(ref, tm->mm_struct_addr) ||
VM_REF_CHECK_HEXVAL(ref, tm->pgd_addr)) {
print_task_header(fp, tc, 0);
- PRINT_VM_DATA();
+ PRINT_VM_DATA(buf4, buf5, tm);
fprintf(fp, "\n");
return (ulong)NULL;
}
if (!(flag & (UVADDR|PRINT_MM_STRUCT|PRINT_VMA_STRUCTS|PRINT_SINGLE_VMA))
&&
!DO_REF_SEARCH(ref))
- PRINT_VM_DATA();
+ PRINT_VM_DATA(buf4, buf5, tm);
if (!tm->mm_struct_addr) {
if (pc->curcmd_flags & MM_STRUCT_FORCE) {
@@ -4004,9 +4153,6 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct reference
*ref)
return (ulong)NULL;
}
- readmem(tm->mm_struct_addr + OFFSET(mm_struct_mmap), KVADDR,
- &vma, sizeof(void *), "mm_struct mmap", FAULT_ON_ERROR);
-
sprintf(vma_header, "%s%s%s%s%s FLAGS%sFILE\n",
mkstring(buf1, VADDR_PRLEN, CENTER|LJUST, "VMA"),
space(MINSPACE),
@@ -4019,125 +4165,34 @@ vm_area_dump(ulong task, ulong flag, ulong vaddr, struct
reference *ref)
!DO_REF_SEARCH(ref))
fprintf(fp, "%s", vma_header);
- for (found = FALSE; vma; vma = vm_next) {
-
- if ((flag & PHYSADDR) && !DO_REF_SEARCH(ref))
- fprintf(fp, "%s", vma_header);
-
- inode = 0;
- BZERO(buf1, BUFSIZE);
- vma_buf = fill_vma_cache(vma);
-
- vm_mm = ULONG(vma_buf + OFFSET(vm_area_struct_vm_mm));
- vm_end = ULONG(vma_buf + OFFSET(vm_area_struct_vm_end));
- vm_next = ULONG(vma_buf + OFFSET(vm_area_struct_vm_next));
- vm_start = ULONG(vma_buf + OFFSET(vm_area_struct_vm_start));
- vm_flags = get_vm_flags(vma_buf);
- vm_file = ULONG(vma_buf + OFFSET(vm_area_struct_vm_file));
-
- if (flag & PRINT_SINGLE_VMA) {
- if (vma != single_vma)
- continue;
- fprintf(fp, "%s", vma_header);
- single_vma_found = TRUE;
- }
-
- if (flag & PRINT_VMA_STRUCTS) {
- dump_struct("vm_area_struct", vma, radix);
- continue;
- }
-
- if (vm_file && !(flag & VERIFY_ADDR)) {
- file_buf = fill_file_cache(vm_file);
- dentry = ULONG(file_buf + OFFSET(file_f_dentry));
- dentry_buf = NULL;
- if (dentry) {
- dentry_buf = fill_dentry_cache(dentry);
- if (VALID_MEMBER(file_f_vfsmnt)) {
- vfsmnt = ULONG(file_buf +
- OFFSET(file_f_vfsmnt));
- get_pathname(dentry, buf1, BUFSIZE,
- 1, vfsmnt);
- } else {
- get_pathname(dentry, buf1, BUFSIZE,
- 1, 0);
- }
- }
- if ((flag & PRINT_INODES) && dentry) {
- inode = ULONG(dentry_buf +
- OFFSET(dentry_d_inode));
- }
- }
-
- if (!(flag & UVADDR) || ((flag & UVADDR) &&
- ((vaddr >= vm_start) && (vaddr < vm_end)))) {
- found = TRUE;
+ found = FALSE;
- if (flag & VERIFY_ADDR)
+ struct handle_each_vm_area_args args = {
+ .task = task, .flag = flag, .vaddr = vaddr,
+ .ref = ref, .vma_header = vma_header, .buf1 = buf1,
+ .buf2 = buf2, .buf3 = buf3, .buf4 = buf4,
+ .buf5 = buf5, .vma_buf = &vma_buf, .tm = tm,
+ .found = &found, .single_vma_found = &single_vma_found,
+ .radix = radix, .tc = tc, .single_vma = &single_vma,
+ };
+
+ if (INVALID_MEMBER(mm_struct_mmap) && VALID_MEMBER(mm_struct_mm_mt)) {
+ VMA_ITERATOR(vmi, (struct maple_tree *)
+ (tm->mm_struct_addr + OFFSET(mm_struct_mm_mt)), 0);
+ for_each_vma(vmi, vma) {
+ args.vma = vma;
+ if (handle_each_vm_area(&args))
return vma;
-
- if (DO_REF_SEARCH(ref)) {
- if (VM_REF_CHECK_HEXVAL(ref, vma) ||
- VM_REF_CHECK_HEXVAL(ref, (ulong)vm_flags) ||
- VM_REF_CHECK_STRING(ref, buf1)) {
- if (!(ref->cmdflags & VM_REF_HEADER)) {
- print_task_header(fp, tc, 0);
- PRINT_VM_DATA();
- ref->cmdflags |= VM_REF_HEADER;
- }
- if (!(ref->cmdflags & VM_REF_VMA) ||
- (ref->cmdflags & VM_REF_PAGE)) {
- fprintf(fp, "%s", vma_header);
- ref->cmdflags |= VM_REF_VMA;
- ref->cmdflags &= ~VM_REF_PAGE;
- ref->ref1 = vma;
- }
- PRINT_VMA_DATA();
- }
-
- if (vm_area_page_dump(vma, task,
- vm_start, vm_end, vm_mm, ref)) {
- if (!(ref->cmdflags & VM_REF_HEADER)) {
- print_task_header(fp, tc, 0);
- PRINT_VM_DATA();
- ref->cmdflags |= VM_REF_HEADER;
- }
- if (!(ref->cmdflags & VM_REF_VMA) ||
- (ref->ref1 != vma)) {
- fprintf(fp, "%s", vma_header);
- PRINT_VMA_DATA();
- ref->cmdflags |= VM_REF_VMA;
- ref->ref1 = vma;
- }
-
- ref->cmdflags |= VM_REF_DISPLAY;
- vm_area_page_dump(vma, task,
- vm_start, vm_end, vm_mm, ref);
- ref->cmdflags &= ~VM_REF_DISPLAY;
- }
-
- continue;
- }
-
- if (inode) {
- fprintf(fp, "%lx%s%s%s%s%s%6llx%s%lx %s\n",
- vma, space(MINSPACE),
- mkstring(buf2, UVADDR_PRLEN, RJUST|LONG_HEX,
- MKSTR(vm_start)), space(MINSPACE),
- mkstring(buf3, UVADDR_PRLEN, RJUST|LONG_HEX,
- MKSTR(vm_end)), space(MINSPACE),
- vm_flags, space(MINSPACE), inode, buf1);
- } else {
- PRINT_VMA_DATA();
-
- if (flag & (PHYSADDR|PRINT_SINGLE_VMA))
- vm_area_page_dump(vma, task,
- vm_start, vm_end, vm_mm, ref);
- }
-
- if (flag & UVADDR)
+ }
+ } else {
+ readmem(tm->mm_struct_addr + OFFSET(mm_struct_mmap), KVADDR,
+ &vma, sizeof(void *), "mm_struct mmap", FAULT_ON_ERROR);
+ while (vma) {
+ args.vma = vma;
+ if (handle_each_vm_area(&args))
return vma;
- }
+ vma = ULONG(vma_buf + OFFSET(vm_area_struct_vm_next));
+ }
}
if (flag & VERIFY_ADDR)
--
2.33.1
3:33 a.m.
New subject: [RFC] [PATCH 3/6] Introduce maple tree vma iteration to memory.c
On 2022/09/20 0:10, Tao Liu wrote:
Since memory.c:vm_area_dump will iterate all vma, this patch mainly
introduces maple tree vma iteration to it.
We extract the code which handles each vma into a function. If
mm_struct_mmap exist, aka the linked list of vma iteration available,
we goto the original way; if not and mm_struct_mm_mt exist, aka
maple tree is available, then we goto the maple tree vma iteration.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
Makefile | 4 +-
defs.h | 1 +
maple_tree_vma.h | 3 +-
memory.c | 311 ++++++++++++++++++++++++++++-------------------
4 files changed, 188 insertions(+), 131 deletions(-)
diff --git a/Makefile b/Makefile
index d545bc0..4d7549c 100644
--- a/Makefile
+++ b/Makefile
@@ -59,7 +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 xarray.h
+MAPLE_TREE_HFILES=maple_tree.h xarray.h maple_tree_vma.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 \
@@ -355,7 +355,7 @@ filesys.o: ${GENERIC_HFILES} filesys.c
help.o: ${GENERIC_HFILES} help.c
${CC} -c ${CRASH_CFLAGS} help.c ${WARNING_OPTIONS} ${WARNING_ERROR}
-memory.o: ${GENERIC_HFILES} memory.c
+memory.o: ${GENERIC_HFILES} ${MAPLE_TREE_HFILES} memory.c
${CC} -c ${CRASH_CFLAGS} memory.c ${WARNING_OPTIONS} ${WARNING_ERROR}
test.o: ${GENERIC_HFILES} test.c
diff --git a/defs.h b/defs.h
index afdcf6c..d4be477 100644
--- a/defs.h
+++ b/defs.h
@@ -1332,6 +1332,7 @@ struct offset_table { /* stash of commonly-used
offsets */
long percpu_struct_halt_ra;
long percpu_struct_halt_pv;
long mm_struct_mmap;
+ long mm_struct_mm_mt;
Please add this to the end of the offset_table, though this
is fixed in 4/6.
Thanks,
Kazu
10:10 a.m.
New subject: [RFC] [PATCH 4/6] Maple tree kernel code modification for step 2
This patch will remove all kernel structures, and leave them to be blank
for debug purpose. There seems to be a lot of code changes, but most are
rewriting struct member resolving into crash way.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 20 +++++-
maple_tree.c | 183 ++++++++++++++++++++++++++++++++-------------------
maple_tree.h | 92 ++++++--------------------
memory.c | 4 ++
4 files changed, 159 insertions(+), 140 deletions(-)
diff --git a/defs.h b/defs.h
index d4be477..8ea710f 100644
--- a/defs.h
+++ b/defs.h
@@ -1332,7 +1332,6 @@ struct offset_table { /* stash of commonly-used
offsets */
long percpu_struct_halt_ra;
long percpu_struct_halt_pv;
long mm_struct_mmap;
- long mm_struct_mm_mt;
long mm_struct_pgd;
long mm_struct_rss;
long mm_struct_anon_rss;
@@ -2182,6 +2181,23 @@ struct offset_table { /* stash of commonly-used
offsets */
long blk_mq_tags_nr_reserved_tags;
long blk_mq_tags_rqs;
long request_queue_hctx_table;
+
+ long mm_struct_mm_mt;
+ long maple_tree_ma_root;
+ long maple_tree_ma_flags;
+ long maple_node_parent;
+ long maple_node_ma64;
+ long maple_node_mr64;
+ long maple_node_slot;
+ long maple_arange_64_parent;
+ long maple_arange_64_pivot;
+ long maple_arange_64_slot;
+ long maple_arange_64_meta;
+ long maple_range_64_parent;
+ long maple_range_64_pivot;
+ long maple_range_64_slot;
+ long maple_range_64_meta;
+ long maple_metadata_end;
};
struct size_table { /* stash of commonly-used sizes */
@@ -2352,6 +2368,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 {
diff --git a/maple_tree.c b/maple_tree.c
index 21a2226..ff07d58 100644
--- a/maple_tree.c
+++ b/maple_tree.c
@@ -78,10 +78,11 @@ static inline enum maple_type mte_node_type(const struct maple_enode
*entry)
static inline void *mas_root(struct ma_state *mas)
{
- struct maple_tree tree;
- readmem(mas->tree, KVADDR, &tree, sizeof(tree),
+ char tree[SIZE(maple_tree_struct)];
+
+ readmem((ulonglong)(mas->tree), KVADDR, tree, SIZE(maple_tree_struct),
"mas_root read maple_tree", FAULT_ON_ERROR);
- return tree.ma_root;
+ return *(void **)(tree + OFFSET(maple_tree_ma_root));
}
static inline struct maple_enode *mas_start(struct ma_state *mas)
@@ -127,10 +128,12 @@ static inline unsigned long *ma_pivots(struct maple_node *node,
{
switch (type) {
case maple_arange_64:
- return node->ma64.pivot;
+ return (unsigned long *)((char *)node + OFFSET(maple_node_ma64)
+ + OFFSET(maple_arange_64_pivot));
case maple_range_64:
case maple_leaf_64:
- return node->mr64.pivot;
+ return (unsigned long *)((char *)node + OFFSET(maple_node_mr64)
+ + OFFSET(maple_range_64_pivot));
case maple_dense:
return NULL;
}
@@ -142,9 +145,13 @@ static inline struct maple_metadata *ma_meta(struct maple_node *mn,
{
switch (mt) {
case maple_arange_64:
- return &mn->ma64.meta;
+ return (struct maple_metadata *)(
+ (char *)mn + OFFSET(maple_node_ma64)
+ + OFFSET(maple_arange_64_meta));
default:
- return &mn->mr64.meta;
+ return (struct maple_metadata *)(
+ (char *)mn + OFFSET(maple_node_mr64)
+ + OFFSET(maple_range_64_meta));
}
}
@@ -153,7 +160,7 @@ static inline unsigned char ma_meta_end(struct maple_node *mn,
{
struct maple_metadata *meta = ma_meta(mn, mt);
- return meta->end;
+ return *((char *)meta + OFFSET(maple_metadata_end));
}
static inline unsigned char ma_data_end(struct maple_node *node,
@@ -179,9 +186,10 @@ static inline unsigned char ma_data_end(struct maple_node *node,
static inline bool ma_dead_node(const struct maple_node *node,
const struct maple_node *orig_node)
{
- struct maple_node *parent = (void *)((unsigned long)
- node->parent & ~MAPLE_NODE_MASK);
-
+ struct maple_node *parent = (struct maple_node *)
+ (*(unsigned long *)((char *)node
+ + OFFSET(maple_node_parent))
+ & ~MAPLE_NODE_MASK);
return (parent == orig_node);
}
@@ -190,12 +198,14 @@ static inline void **ma_slots(struct maple_node *mn, enum maple_type
mt)
switch (mt) {
default:
case maple_arange_64:
- return mn->ma64.slot;
+ return (void **)((char *)mn + OFFSET(maple_node_ma64)
+ + OFFSET(maple_arange_64_slot));
case maple_range_64:
case maple_leaf_64:
- return mn->mr64.slot;
+ return (void **)((char *)mn + OFFSET(maple_node_mr64)
+ + OFFSET(maple_range_64_slot));
case maple_dense:
- return mn->slot;
+ return (void **)((char *)mn + OFFSET(maple_node_slot));
}
}
@@ -222,7 +232,7 @@ static inline void *mtree_range_walk(struct ma_state *mas)
unsigned long max, min;
unsigned long prev_max, prev_min;
- struct maple_node tmp_node;
+ char tmp_node[SIZE(maple_node_struct)];
last = next = mas->node;
prev_min = min = mas->min;
@@ -232,11 +242,11 @@ static inline void *mtree_range_walk(struct ma_state *mas)
last = next;
node = mte_to_node(next);
type = mte_node_type(next);
- readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mtree_range_walk read maple_node", FAULT_ON_ERROR);
- pivots = ma_pivots(&tmp_node, type);
- end = ma_data_end(&tmp_node, type, pivots, max);
- if (ma_dead_node(&tmp_node, node))
+ pivots = ma_pivots((struct maple_node *)tmp_node, type);
+ end = ma_data_end((struct maple_node *)tmp_node, type, pivots, max);
+ if (ma_dead_node((struct maple_node *)tmp_node, node))
goto dead_node;
if (pivots[offset] >= mas->index) {
@@ -257,9 +267,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
max = pivots[offset];
next:
- slots = ma_slots(&tmp_node, type);
+ slots = ma_slots((struct maple_node *)tmp_node, type);
next = mt_slot(mas->tree, slots, offset);
- if (ma_dead_node(&tmp_node, node))
+ if (ma_dead_node((struct maple_node *)tmp_node, node))
goto dead_node;
} while (!ma_is_leaf(type));
@@ -410,13 +420,16 @@ retry:
static inline bool ma_is_root(struct maple_node *node)
{
- return ((unsigned long)node->parent & MA_ROOT_PARENT);
+ return (*(unsigned long *)((char *)node
+ + OFFSET(maple_node_parent))
+ & MA_ROOT_PARENT);
}
static inline struct maple_node *mte_parent(const struct maple_node *node)
{
- return (void *)((unsigned long)
- (node->parent) & ~MAPLE_NODE_MASK);
+ return (void *)(*(unsigned long *)((char *)node
+ + OFFSET(maple_node_parent))
+ & ~MAPLE_NODE_MASK);
}
static inline unsigned long mte_parent_slot_mask(unsigned long parent)
@@ -430,7 +443,9 @@ static inline unsigned long mte_parent_slot_mask(unsigned long
parent)
static inline bool mt_is_alloc(struct maple_tree *mt)
{
- return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
+ return (*(unsigned int *)((char *)mt
+ + OFFSET(maple_tree_ma_flags))
+ & MT_FLAGS_ALLOC_RANGE);
}
static inline
@@ -438,7 +453,7 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
struct maple_tree *mt)
{
unsigned long p_type;
- struct maple_tree tmp_tree;
+ char tmp_tree[SIZE(maple_tree_struct)];
p_type = (unsigned long)p_enode;
if (p_type & MAPLE_PARENT_ROOT)
@@ -449,9 +464,9 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
switch (p_type) {
case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */
- readmem(mt, KVADDR, &tmp_tree, sizeof(tmp_tree),
+ readmem((ulonglong)mt, KVADDR, tmp_tree, SIZE(maple_tree_struct),
"mte_parent_enum read maple_tree", FAULT_ON_ERROR);
- if (mt_is_alloc(&tmp_tree))
+ if (mt_is_alloc((struct maple_tree *)tmp_tree))
return maple_arange_64;
return maple_range_64;
}
@@ -462,7 +477,9 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode,
static inline
enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_node *node)
{
- return mte_parent_enum(ma_enode_ptr(node->parent), mas->tree);
+ return mte_parent_enum(ma_enode_ptr(*(struct maple_pnode **)
+ ((char *)node + OFFSET(maple_node_parent))),
+ mas->tree);
}
static inline unsigned long mte_parent_shift(unsigned long parent)
@@ -476,7 +493,8 @@ static inline unsigned long mte_parent_shift(unsigned long parent)
static inline unsigned int mte_parent_slot(const struct maple_node *node)
{
- unsigned long val = (unsigned long) node->parent;
+ unsigned long val = *(unsigned long *)((char *)node
+ + OFFSET(maple_node_parent));
/* Root. */
if (val & 1)
@@ -513,35 +531,36 @@ static int mas_ascend(struct ma_state *mas)
unsigned long *pivots;
unsigned char offset;
bool set_max = false, set_min = false;
- struct maple_node tmp_node;
+
+ char tmp_node[SIZE(maple_node_struct)];
a_node = mas_mn(mas);
- readmem(a_node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)a_node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_ascend read maple_node", FAULT_ON_ERROR);
- if (ma_is_root(&tmp_node)) {
+ if (ma_is_root((struct maple_node *)tmp_node)) {
mas->offset = 0;
return 0;
}
- readmem(mte_to_node(mas->node), KVADDR, &tmp_node, sizeof(tmp_node),
- "mas_ascend read maple_node", FAULT_ON_ERROR);
- p_node = mte_parent(&tmp_node);
+ readmem((ulonglong)(mte_to_node(mas->node)), KVADDR, tmp_node,
+ SIZE(maple_node_struct), "mas_ascend read maple_node", FAULT_ON_ERROR);
+ p_node = mte_parent((struct maple_node *)tmp_node);
if (a_node == p_node)
return 1;
- a_type = mas_parent_enum(mas, &tmp_node);
- offset = mte_parent_slot(&tmp_node);
+ a_type = mas_parent_enum(mas, (struct maple_node *)tmp_node);
+ offset = mte_parent_slot((struct maple_node *)tmp_node);
a_enode = mt_mk_node(p_node, a_type);
/* Check to make sure all parent information is still accurate */
- if (p_node != mte_parent(&tmp_node))
+ if (p_node != mte_parent((struct maple_node *)tmp_node))
return 1;
mas->node = a_enode;
mas->offset = offset;
- readmem(mte_to_node(a_enode), KVADDR, &tmp_node, sizeof(tmp_node),
- "mas_ascend read maple_node", FAULT_ON_ERROR);
- if (mte_is_root(&tmp_node)) {
+ readmem((ulonglong)(mte_to_node(a_enode)), KVADDR, tmp_node,
+ SIZE(maple_node_struct), "mas_ascend read maple_node", FAULT_ON_ERROR);
+ if (mte_is_root((struct maple_node *)tmp_node)) {
mas->max = ULONG_MAX;
mas->min = 0;
return 0;
@@ -551,15 +570,16 @@ static int mas_ascend(struct ma_state *mas)
max = ULONG_MAX;
do {
p_enode = a_enode;
- readmem(mte_to_node(p_enode), KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)(mte_to_node(p_enode)), KVADDR, tmp_node,
+ SIZE(maple_node_struct),
"mas_ascend read maple_node", FAULT_ON_ERROR);
- a_type = mas_parent_enum(mas, &tmp_node);
- a_node = mte_parent(&tmp_node);
- a_slot = mte_parent_slot(&tmp_node);
- readmem(a_node, KVADDR, &tmp_node, sizeof(tmp_node),
+ a_type = mas_parent_enum(mas, (struct maple_node *)tmp_node);
+ a_node = mte_parent((struct maple_node *)tmp_node);
+ a_slot = mte_parent_slot((struct maple_node *)tmp_node);
+ readmem((ulonglong)a_node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_ascend read maple_node", FAULT_ON_ERROR);
- pivots = ma_pivots(&tmp_node, a_type);
- a_enode = mt_mk_node(&tmp_node, a_type);
+ pivots = ma_pivots((struct maple_node *)tmp_node, a_type);
+ a_enode = mt_mk_node((struct maple_node *)tmp_node, a_type);
if (!set_min && a_slot) {
set_min = true;
@@ -571,10 +591,10 @@ static int mas_ascend(struct ma_state *mas)
max = pivots[a_slot];
}
- if (ma_dead_node(&tmp_node, a_node))
+ if (ma_dead_node((struct maple_node *)tmp_node, a_node))
return 1;
- if (ma_is_root(&tmp_node))
+ if (ma_is_root((struct maple_node *)tmp_node))
break;
} while (!set_min || !set_max);
@@ -595,16 +615,16 @@ static inline int mas_next_node(struct ma_state *mas, struct
maple_node *node,
enum maple_type mt;
void **slots;
- struct maple_node tmp_node;
+ char tmp_node[SIZE(maple_node_struct)];
if (mas->max >= max)
goto no_entry;
level = 0;
- readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_next_node read maple_node", FAULT_ON_ERROR);
do {
- if (ma_is_root(&tmp_node))
+ if (ma_is_root((struct maple_node *)tmp_node))
goto no_entry;
min = mas->max + 1;
@@ -618,33 +638,33 @@ static inline int mas_next_node(struct ma_state *mas, struct
maple_node *node,
level++;
node = mas_mn(mas);
mt = mte_node_type(mas->node);
- readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_next_node read maple_node", FAULT_ON_ERROR);
- pivots = ma_pivots(&tmp_node, mt);
- } while (offset == ma_data_end(&tmp_node, mt, pivots, mas->max));
+ pivots = ma_pivots((struct maple_node *)tmp_node, mt);
+ } while (offset == ma_data_end((struct maple_node *)tmp_node, mt, pivots,
mas->max));
- slots = ma_slots(&tmp_node, mt);
+ slots = ma_slots((struct maple_node *)tmp_node, mt);
pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
while (level > 1) {
/* Descend, if necessary */
enode = mas_slot(mas, slots, offset);
- if (ma_dead_node(&tmp_node, node))
+ if (ma_dead_node((struct maple_node *)tmp_node, node))
return 1;
mas->node = enode;
level--;
node = mas_mn(mas);
mt = mte_node_type(mas->node);
- readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_next_node read maple_node", FAULT_ON_ERROR);
- slots = ma_slots(&tmp_node, mt);
- pivots = ma_pivots(&tmp_node, mt);
+ slots = ma_slots((struct maple_node *)tmp_node, mt);
+ pivots = ma_pivots((struct maple_node *)tmp_node, mt);
offset = 0;
pivot = pivots[0];
}
enode = mas_slot(mas, slots, offset);
- if (ma_dead_node(&tmp_node, node))
+ if (ma_dead_node((struct maple_node *)tmp_node, node))
return 1;
mas->node = enode;
@@ -653,7 +673,7 @@ static inline int mas_next_node(struct ma_state *mas, struct
maple_node *node,
return 0;
no_entry:
- if (ma_dead_node(&tmp_node, node))
+ if (ma_dead_node((struct maple_node *)tmp_node, node))
return 1;
mas->node = MAS_NONE;
@@ -669,7 +689,7 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long
limit)
unsigned long last;
enum maple_type mt;
- struct maple_node tmp_node;
+ char tmp_node[SIZE(maple_node_struct)];
last = mas->last;
retry:
@@ -684,10 +704,10 @@ retry:
}
while (!mas_is_none(mas)) {
- readmem(node, KVADDR, &tmp_node, sizeof(tmp_node),
+ readmem((ulonglong)node, KVADDR, tmp_node, SIZE(maple_node_struct),
"mas_next_entry read maple_node", FAULT_ON_ERROR);
- entry = mas_next_nentry(mas, &tmp_node, limit, mt, node);
- if (ma_dead_node(&tmp_node, node)) {
+ entry = mas_next_nentry(mas, (struct maple_node *)tmp_node, limit, mt, node);
+ if (ma_dead_node((struct maple_node *)tmp_node, node)) {
mas_rewalk(mas, last);
goto retry;
}
@@ -771,4 +791,31 @@ void *mas_find(struct ma_state *mas, unsigned long max)
/* Retries on dead nodes handled by mas_next_entry */
return mas_next_entry(mas, max);
+}
+
+/***********************************************/
+void maple_init(void)
+{
+ STRUCT_SIZE_INIT(maple_tree_struct, "maple_tree");
+ STRUCT_SIZE_INIT(maple_node_struct, "maple_node");
+
+ MEMBER_OFFSET_INIT(maple_tree_ma_root, "maple_tree", "ma_root");
+ MEMBER_OFFSET_INIT(maple_tree_ma_flags, "maple_tree", "ma_flags");
+
+ MEMBER_OFFSET_INIT(maple_node_parent, "maple_node", "parent");
+ MEMBER_OFFSET_INIT(maple_node_ma64, "maple_node", "ma64");
+ MEMBER_OFFSET_INIT(maple_node_mr64, "maple_node", "mr64");
+ MEMBER_OFFSET_INIT(maple_node_slot, "maple_node", "slot");
+
+ MEMBER_OFFSET_INIT(maple_arange_64_parent, "maple_arange_64",
"parent");
+ MEMBER_OFFSET_INIT(maple_arange_64_pivot, "maple_arange_64",
"pivot");
+ MEMBER_OFFSET_INIT(maple_arange_64_slot, "maple_arange_64",
"slot");
+ MEMBER_OFFSET_INIT(maple_arange_64_meta, "maple_arange_64",
"meta");
+
+ MEMBER_OFFSET_INIT(maple_range_64_parent, "maple_range_64",
"parent");
+ MEMBER_OFFSET_INIT(maple_range_64_pivot, "maple_range_64",
"pivot");
+ MEMBER_OFFSET_INIT(maple_range_64_slot, "maple_range_64", "slot");
+ MEMBER_OFFSET_INIT(maple_range_64_meta, "maple_range_64", "meta");
+
+ MEMBER_OFFSET_INIT(maple_metadata_end, "maple_metadata", "end");
}
\ No newline at end of file
diff --git a/maple_tree.h b/maple_tree.h
index a5a131e..98f3c5c 100644
--- a/maple_tree.h
+++ b/maple_tree.h
@@ -7,29 +7,23 @@
* Authors: Liam R. Howlett <Liam.Howlett(a)Oracle.com>
* Matthew Wilcox <willy(a)infradead.org>
*/
-#include <stdint.h>
#include <stdbool.h>
-typedef uint32_t spinlock_t;
-typedef uint32_t lockdep_map_p;
-
-struct maple_tree {
- union {
- spinlock_t ma_lock;
- lockdep_map_p ma_external_lock;
- };
- void *ma_root;
- unsigned int ma_flags;
-};
+/*
+ * Keep the empty struct names for debug purpose of compiler warning.
+ * And can also keep the function prototypes consistent with kernel's
+ * corresponding functions.
+ */
+struct maple_tree { };
+struct maple_metadata { };
+struct maple_range_64 { };
+struct maple_arange_64 { };
+struct maple_alloc { };
+struct maple_node { };
typedef struct maple_enode *maple_enode; /* encoded node */
typedef struct maple_pnode *maple_pnode; /* parent node */
-struct maple_metadata {
- unsigned char end;
- unsigned char gap;
-};
-
struct ma_state {
struct maple_tree *tree; /* The tree we're operating in */
unsigned long index; /* The index we're operating on - range start */
@@ -67,21 +61,28 @@ enum maple_type {
.max = ULONG_MAX, \
}
-#if defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64)
+#if defined(ALPHA) || defined(IA64) || \
+ defined(S390) || defined(S390X) || \
+ defined(PPC64) || defined(X86_64) || \
+ defined(ARM64) || defined(SPARC64) || \
+ defined(MIPS64)
/* 64bit sizes */
#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */
#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */
#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
-#else
+#endif
+
+#if defined(X86) || defined(PPC) || \
+ defined(ARM) || defined(MIPS)
/* 32bit sizes */
#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */
#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
-#endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
+#endif
#define MAPLE_NODE_MASK 255UL
@@ -101,56 +102,6 @@ enum maple_type {
#define MAPLE_RESERVED_RANGE 4096
-typedef struct rcu_head { unsigned char x[16]; } rcu_head;
-
-struct maple_range_64 {
- struct maple_pnode *parent;
- unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
- union {
- void *slot[MAPLE_RANGE64_SLOTS];
- struct {
- void *pad[MAPLE_RANGE64_SLOTS - 1];
- struct maple_metadata meta;
- };
- };
-};
-
-struct maple_arange_64 {
- struct maple_pnode *parent;
- unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
- void *slot[MAPLE_ARANGE64_SLOTS];
- unsigned long gap[MAPLE_ARANGE64_SLOTS];
- struct maple_metadata meta;
-};
-
-struct maple_alloc {
- unsigned long total;
- unsigned char node_count;
- unsigned int request_count;
- struct maple_alloc *slot[MAPLE_ALLOC_SLOTS];
-};
-
-struct maple_node {
- union {
- struct {
- struct maple_pnode *parent;
- void *slot[MAPLE_NODE_SLOTS];
- };
- struct {
- void *pad;
- struct rcu_head rcu;
- struct maple_enode *piv_parent;
- unsigned char parent_slot;
- enum maple_type type;
- unsigned char slot_len;
- unsigned int ma_flags;
- };
- struct maple_range_64 mr64;
- struct maple_arange_64 ma64;
- struct maple_alloc alloc;
- };
-};
-
static inline void mas_reset(struct ma_state *mas)
{
mas->node = MAS_START;
@@ -166,7 +117,6 @@ void mas_set_range(struct ma_state *mas, unsigned long start, unsigned
long last
static inline void mas_set(struct ma_state *mas, unsigned long index)
{
-
mas_set_range(mas, index, index);
}
diff --git a/memory.c b/memory.c
index 00f7c9a..2bfd5ae 100644
--- a/memory.c
+++ b/memory.c
@@ -299,6 +299,7 @@ static void dump_page_flags(ulonglong);
static ulong kmem_cache_nodelists(ulong);
static void dump_hstates(void);
static ulong freelist_ptr(struct meminfo *, ulong, ulong);
+extern void maple_init(void);
/*
* Memory display modes specific to this file.
@@ -364,6 +365,9 @@ vm_init(void)
MEMBER_OFFSET_INIT(task_struct_mm, "task_struct", "mm");
MEMBER_OFFSET_INIT(mm_struct_mmap, "mm_struct", "mmap");
MEMBER_OFFSET_INIT(mm_struct_mm_mt, "mm_struct", "mm_mt");
+ if (VALID_MEMBER(mm_struct_mm_mt)) {
+ maple_init();
+ }
MEMBER_OFFSET_INIT(mm_struct_pgd, "mm_struct", "pgd");
MEMBER_OFFSET_INIT(mm_struct_rss, "mm_struct", "rss");
if (!VALID_MEMBER(mm_struct_rss))
--
2.33.1
3:34 a.m.
New subject: [RFC] [PATCH 4/6] Maple tree kernel code modification for step 2
On 2022/09/20 0:10, Tao Liu wrote:
This patch will remove all kernel structures, and leave them to be
blank
for debug purpose. There seems to be a lot of code changes, but most are
rewriting struct member resolving into crash way.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 20 +++++-
maple_tree.c | 183 ++++++++++++++++++++++++++++++++-------------------
maple_tree.h | 92 ++++++--------------------
memory.c | 4 ++
4 files changed, 159 insertions(+), 140 deletions(-)
diff --git a/defs.h b/defs.h
index d4be477..8ea710f 100644
--- a/defs.h
+++ b/defs.h
@@ -1332,7 +1332,6 @@ struct offset_table { /* stash of commonly-used
offsets */
long percpu_struct_halt_ra;
long percpu_struct_halt_pv;
long mm_struct_mmap;
- long mm_struct_mm_mt;
long mm_struct_pgd;
long mm_struct_rss;
long mm_struct_anon_rss;
@@ -2182,6 +2181,23 @@ struct offset_table { /* stash of commonly-used
offsets */
long blk_mq_tags_nr_reserved_tags;
long blk_mq_tags_rqs;
long request_queue_hctx_table;
+
+ long mm_struct_mm_mt;
+ long maple_tree_ma_root;
+ long maple_tree_ma_flags;
+ long maple_node_parent;
+ long maple_node_ma64;
+ long maple_node_mr64;
+ long maple_node_slot;
+ long maple_arange_64_parent;
+ long maple_arange_64_pivot;
+ long maple_arange_64_slot;
+ long maple_arange_64_meta;
+ long maple_range_64_parent;
+ long maple_range_64_pivot;
+ long maple_range_64_slot;
+ long maple_range_64_meta;
+ long maple_metadata_end;
};
struct size_table { /* stash of commonly-used sizes */
@@ -2352,6 +2368,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 {
diff --git a/maple_tree.c b/maple_tree.c
index 21a2226..ff07d58 100644
--- a/maple_tree.c
+++ b/maple_tree.c
@@ -78,10 +78,11 @@ static inline enum maple_type mte_node_type(const struct maple_enode
*entry)
static inline void *mas_root(struct ma_state *mas)
{
- struct maple_tree tree;
- readmem(mas->tree, KVADDR, &tree, sizeof(tree),
+ char tree[SIZE(maple_tree_struct)];
Please don't use variable-length array, which can be fragile.
Thanks,
Kazu
10:10 a.m.
New subject: [RFC] [PATCH 5/6] Dump maple tree offset variables by help -o
In the previous patch, a few variables are added to offset_table and
size_table, we need to print it out with help cmd.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 34 ++++++++++++++++++++++++++++++++++
1 file changed, 34 insertions(+)
diff --git a/symbols.c b/symbols.c
index 42c4eb4..44a4bf9 100644
--- a/symbols.c
+++ b/symbols.c
@@ -10755,6 +10755,38 @@ dump_offset_table(char *spec, ulong makestruct)
OFFSET(sbq_wait_state_wait_cnt));
fprintf(fp, " sbq_wait_state_wait: %ld\n",
OFFSET(sbq_wait_state_wait));
+ fprintf(fp, " mm_struct_mm_mt: %ld\n",
+ OFFSET(mm_struct_mm_mt));
+ fprintf(fp, " maple_tree_ma_root: %ld\n",
+ OFFSET(maple_tree_ma_root));
+ fprintf(fp, " maple_tree_ma_flags: %ld\n",
+ OFFSET(maple_tree_ma_flags));
+ fprintf(fp, " maple_node_parent: %ld\n",
+ OFFSET(maple_node_parent));
+ fprintf(fp, " maple_node_ma64: %ld\n",
+ OFFSET(maple_node_ma64));
+ fprintf(fp, " maple_node_mr64: %ld\n",
+ OFFSET(maple_node_mr64));
+ fprintf(fp, " maple_node_slot: %ld\n",
+ OFFSET(maple_node_slot));
+ fprintf(fp, " maple_arange_64_parent: %ld\n",
+ OFFSET(maple_arange_64_parent));
+ fprintf(fp, " maple_arange_64_pivot: %ld\n",
+ OFFSET(maple_arange_64_pivot));
+ fprintf(fp, " maple_arange_64_slot: %ld\n",
+ OFFSET(maple_arange_64_slot));
+ fprintf(fp, " maple_arange_64_meta: %ld\n",
+ OFFSET(maple_arange_64_meta));
+ fprintf(fp, " maple_range_64_parent: %ld\n",
+ OFFSET(maple_range_64_parent));
+ fprintf(fp, " maple_range_64_pivot: %ld\n",
+ OFFSET(maple_range_64_pivot));
+ fprintf(fp, " maple_range_64_slot: %ld\n",
+ OFFSET(maple_range_64_slot));
+ fprintf(fp, " maple_range_64_meta: %ld\n",
+ OFFSET(maple_range_64_meta));
+ fprintf(fp, " maple_metadata_end: %ld\n",
+ OFFSET(maple_metadata_end));
fprintf(fp, "\n size_table:\n");
fprintf(fp, " page: %ld\n", SIZE(page));
@@ -11027,6 +11059,8 @@ dump_offset_table(char *spec, ulong makestruct)
fprintf(fp, " sbitmap_queue: %ld\n", SIZE(sbitmap_queue));
fprintf(fp, " sbq_wait_state: %ld\n", SIZE(sbq_wait_state));
fprintf(fp, " blk_mq_tags: %ld\n", SIZE(blk_mq_tags));
+ fprintf(fp, " maple_tree_struct: %ld\n",
SIZE(maple_tree_struct));
+ fprintf(fp, " maple_node_struct: %ld\n",
SIZE(maple_node_struct));
fprintf(fp, "\n array_table:\n");
/*
--
2.33.1
3:34 a.m.
New subject: [RFC] [PATCH 5/6] Dump maple tree offset variables by help -o
On 2022/09/20 0:10, Tao Liu wrote:
In the previous patch, a few variables are added to offset_table
and
size_table, we need to print it out with help cmd.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 34 ++++++++++++++++++++++++++++++++++
1 file changed, 34 insertions(+)
diff --git a/symbols.c b/symbols.c
index 42c4eb4..44a4bf9 100644
--- a/symbols.c
+++ b/symbols.c
@@ -10755,6 +10755,38 @@ dump_offset_table(char *spec, ulong makestruct)
OFFSET(sbq_wait_state_wait_cnt));
fprintf(fp, " sbq_wait_state_wait: %ld\n",
OFFSET(sbq_wait_state_wait));
+ fprintf(fp, " mm_struct_mm_mt: %ld\n",
+ OFFSET(mm_struct_mm_mt));
+ fprintf(fp, " maple_tree_ma_root: %ld\n",
+ OFFSET(maple_tree_ma_root));
+ fprintf(fp, " maple_tree_ma_flags: %ld\n",
+ OFFSET(maple_tree_ma_flags));
+ fprintf(fp, " maple_node_parent: %ld\n",
+ OFFSET(maple_node_parent));
+ fprintf(fp, " maple_node_ma64: %ld\n",
+ OFFSET(maple_node_ma64));
+ fprintf(fp, " maple_node_mr64: %ld\n",
+ OFFSET(maple_node_mr64));
+ fprintf(fp, " maple_node_slot: %ld\n",
+ OFFSET(maple_node_slot));
+ fprintf(fp, " maple_arange_64_parent: %ld\n",
+ OFFSET(maple_arange_64_parent));
+ fprintf(fp, " maple_arange_64_pivot: %ld\n",
+ OFFSET(maple_arange_64_pivot));
+ fprintf(fp, " maple_arange_64_slot: %ld\n",
+ OFFSET(maple_arange_64_slot));
+ fprintf(fp, " maple_arange_64_meta: %ld\n",
+ OFFSET(maple_arange_64_meta));
+ fprintf(fp, " maple_range_64_parent: %ld\n",
+ OFFSET(maple_range_64_parent));
+ fprintf(fp, " maple_range_64_pivot: %ld\n",
+ OFFSET(maple_range_64_pivot));
+ fprintf(fp, " maple_range_64_slot: %ld\n",
+ OFFSET(maple_range_64_slot));
+ fprintf(fp, " maple_range_64_meta: %ld\n",
+ OFFSET(maple_range_64_meta));
+ fprintf(fp, " maple_metadata_end: %ld\n",
+ OFFSET(maple_metadata_end));
It's ok to not fold these lines, that would be more readable.
Thanks,
Kazu
>
> fprintf(fp, "\n size_table:\n");
> fprintf(fp, " page: %ld\n", SIZE(page));
> @@ -11027,6 +11059,8 @@ dump_offset_table(char *spec, ulong makestruct)
> fprintf(fp, " sbitmap_queue: %ld\n",
SIZE(sbitmap_queue));
> fprintf(fp, " sbq_wait_state: %ld\n",
SIZE(sbq_wait_state));
> fprintf(fp, " blk_mq_tags: %ld\n",
SIZE(blk_mq_tags));
> + fprintf(fp, " maple_tree_struct: %ld\n",
SIZE(maple_tree_struct));
> + fprintf(fp, " maple_node_struct: %ld\n",
SIZE(maple_node_struct));
>
> fprintf(fp, "\n array_table:\n");
> /*
10:10 a.m.
New subject: [RFC] [PATCH 6/6] Remove mt_slots and mt_pivots array assignment
Previous the mt_slots and mt_pivots array are assigned at compile
time, however they are arch dependent and may be inconsistent with
the vmcore. To avoid such issue, we read the array from vmcore
instead.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
maple_tree.c | 37 ++++++++++++++++++++-----------------
maple_tree.h | 23 -----------------------
2 files changed, 20 insertions(+), 40 deletions(-)
diff --git a/maple_tree.c b/maple_tree.c
index ff07d58..38a8b06 100644
--- a/maple_tree.c
+++ b/maple_tree.c
@@ -31,21 +31,8 @@
#define MAPLE_PARENT_RANGE32 0x04
#define MAPLE_PARENT_NOT_RANGE16 0x02
-static const unsigned char mt_slots[] = {
- [maple_dense] = MAPLE_NODE_SLOTS,
- [maple_leaf_64] = MAPLE_RANGE64_SLOTS,
- [maple_range_64] = MAPLE_RANGE64_SLOTS,
- [maple_arange_64] = MAPLE_ARANGE64_SLOTS,
-};
-#define mt_slot_count(x) mt_slots[mte_node_type(x)]
-
-static const unsigned char mt_pivots[] = {
- [maple_dense] = 0,
- [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1,
- [maple_range_64] = MAPLE_RANGE64_SLOTS - 1,
- [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1,
-};
-#define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
+unsigned char *mt_slots = NULL;
+unsigned char *mt_pivots = NULL;
#define ma_parent_ptr(x) ((struct maple_pnode *)(x))
#define ma_enode_ptr(x) ((struct maple_enode *)(x))
@@ -105,13 +92,15 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
/* empty tree */
if (!root) {
- mas->offset = MAPLE_NODE_SLOTS;
+ // mas->offset = MAPLE_NODE_SLOTS;
+ mas->offset = mt_slots[maple_dense];
return NULL;
}
/* Single entry tree */
mas->node = MAS_ROOT;
- mas->offset = MAPLE_NODE_SLOTS;
+ // mas->offset = MAPLE_NODE_SLOTS;
+ mas->offset = mt_slots[maple_dense];
/* Single entry tree. */
if (mas->index > 0)
@@ -796,6 +785,8 @@ void *mas_find(struct ma_state *mas, unsigned long max)
/***********************************************/
void maple_init(void)
{
+ int array_len;
+
STRUCT_SIZE_INIT(maple_tree_struct, "maple_tree");
STRUCT_SIZE_INIT(maple_node_struct, "maple_node");
@@ -818,4 +809,16 @@ void maple_init(void)
MEMBER_OFFSET_INIT(maple_range_64_meta, "maple_range_64", "meta");
MEMBER_OFFSET_INIT(maple_metadata_end, "maple_metadata", "end");
+
+ array_len = get_array_length("mt_slots", NULL, sizeof(char));
+ mt_slots = calloc(array_len, sizeof(char));
+ readmem(symbol_value("mt_slots"), KVADDR, mt_slots,
+ array_len * sizeof(char), "maple_init read mt_slots",
+ FAULT_ON_ERROR);
+
+ array_len = get_array_length("mt_pivots", NULL, sizeof(char));
+ mt_pivots = calloc(array_len, sizeof(char));
+ readmem(symbol_value("mt_pivots"), KVADDR, mt_pivots,
+ array_len * sizeof(char), "maple_init read mt_pivots",
+ FAULT_ON_ERROR);
}
\ No newline at end of file
diff --git a/maple_tree.h b/maple_tree.h
index 98f3c5c..aca1741 100644
--- a/maple_tree.h
+++ b/maple_tree.h
@@ -61,29 +61,6 @@ enum maple_type {
.max = ULONG_MAX, \
}
-#if defined(ALPHA) || defined(IA64) || \
- defined(S390) || defined(S390X) || \
- defined(PPC64) || defined(X86_64) || \
- defined(ARM64) || defined(SPARC64) || \
- defined(MIPS64)
-/* 64bit sizes */
-#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
-#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
-#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */
-#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */
-#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
-#endif
-
-#if defined(X86) || defined(PPC) || \
- defined(ARM) || defined(MIPS)
-/* 32bit sizes */
-#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
-#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
-#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
-#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */
-#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
-#endif
-
#define MAPLE_NODE_MASK 255UL
#define MT_FLAGS_ALLOC_RANGE 0x01
--
2.33.1
3:30 a.m.
On 2022/09/20 0:10, Tao Liu wrote:
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].
Patch 1: the pure copy-and-paste work, extracting related kernel
structures, functions, constants to crash.
Patch 2: minimal code modification for crash adaption, kernel
structures are kept for member resolving.
Patch 3: modification on crash memory.c to use the maple vma
iteration.
The idea is to make patch 1-3 a POC work.
Patch 4: Get rid of kernel structures by rewriting the structure
member resolving code into the crash way, aka change
"node->member" into "readmem(node) and OFFSET(member)"
Patch 5: print the added variables of offset/size table
Patch 6: Get rid of the compiling-time assgined arrays.
Patch 4-6 will make the POC work formal for use.
Thank you for working on this! and sorry for the delay.
The patchset on the whole looks good and no problem was detected
so far at my end. Some comments below and inline.
- Ideally it's better also for "tree" command to support the maple
tree like "tree -t maple", is it possible?
It's ok at all to do this later, but the maple tree looks too
complicated to me to be supported fully by the tree command..
If it looks possible, it might be better to have some preparation
at this point.
- Please fix the compilation warnings with "make clean ; make warn".
Thanks,
Kazu
>
>
> [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...
>
> Tao Liu (6):
> Port linux maple tree related files to crash
> Maple tree kernel code modification for step 1
> Introduce maple tree vma iteration to memory.c
> Maple tree kernel code modification for step 2
> Dump maple tree offset variables by help -o
> Remove mt_slots and mt_pivots array assignment
>
> Makefile | 12 +-
> defs.h | 19 ++
> maple_tree.c | 824 +++++++++++++++++++++++++++++++++++++++++++++++
> maple_tree.h | 109 +++++++
> maple_tree_vma.h | 34 ++
> memory.c | 315 ++++++++++--------
> symbols.c | 34 ++
> xarray.h | 70 ++++
> 8 files changed, 1285 insertions(+), 132 deletions(-)
> create mode 100644 maple_tree.c
> create mode 100644 maple_tree.h
> create mode 100644 maple_tree_vma.h
> create mode 100644 xarray.h
>
9:41 p.m.
Hi Kazu,
Thanks for your review and comments!
On Wed, Oct 5, 2022 at 4:30 PM HAGIO KAZUHITO(萩尾 一仁) <k-hagio-ab(a)nec.com> wrote:
On 2022/09/20 0:10, Tao Liu wrote:
> 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].
>
> Patch 1: the pure copy-and-paste work, extracting related kernel
> structures, functions, constants to crash.
> Patch 2: minimal code modification for crash adaption, kernel
> structures are kept for member resolving.
> Patch 3: modification on crash memory.c to use the maple vma
> iteration.
>
> The idea is to make patch 1-3 a POC work.
>
> Patch 4: Get rid of kernel structures by rewriting the structure
> member resolving code into the crash way, aka change
> "node->member" into "readmem(node) and
OFFSET(member)"
> Patch 5: print the added variables of offset/size table
> Patch 6: Get rid of the compiling-time assgined arrays.
>
> Patch 4-6 will make the POC work formal for use.
Thank you for working on this! and sorry for the delay.
np.
The patchset on the whole looks good and no problem was detected
so far at my end. Some comments below and inline.
- Ideally it's better also for "tree" command to support the maple
tree like "tree -t maple", is it possible?
It's ok at all to do this later, but the maple tree looks too
complicated to me to be supported fully by the tree command..
If it looks possible, it might be better to have some preparation
at this point.
Yes, I plan to support maple tree in tree cmd, I don't know if it can
be compatible with tree cmd, but it is worth trying. I will go with
another patchset for tree cmd support of maple tree.
- Please fix the compilation warnings with "make clean ; make
warn".
OK, I will get it fixed in v2, as well as the comments you inlined in
other patches.
Thanks,
Tao Liu
Thanks,
Kazu
>
>
> [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...
>
> Tao Liu (6):
> Port linux maple tree related files to crash
> Maple tree kernel code modification for step 1
> Introduce maple tree vma iteration to memory.c
> Maple tree kernel code modification for step 2
> Dump maple tree offset variables by help -o
> Remove mt_slots and mt_pivots array assignment
>
> Makefile | 12 +-
> defs.h | 19 ++
> maple_tree.c | 824 +++++++++++++++++++++++++++++++++++++++++++++++
> maple_tree.h | 109 +++++++
> maple_tree_vma.h | 34 ++
> memory.c | 315 ++++++++++--------
> symbols.c | 34 ++
> xarray.h | 70 ++++
> 8 files changed, 1285 insertions(+), 132 deletions(-)
> create mode 100644 maple_tree.c
> create mode 100644 maple_tree.h
> create mode 100644 maple_tree_vma.h
> create mode 100644 xarray.h
>
629
days inactive
649
days old
devel@lists.crash-utility.osci.io
12 comments
2 participants
participants (2)
-
HAGIO KAZUHITO(萩尾 一仁) -
Tao Liu