These patches do the following:
001 - 002: Small cleanup to maple tree.
003 - 006: Improve the validation for maple tree.
007 - 008: Drop some functions that will no longer be used.
Peng Zhang (8):
maple_tree: set the node limit when creating a new root node
maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap
maple_tree: make mas_validate_gaps() to check metadata
maple_tree: fix mas_validate_child_slot() to check last missed slot
maple_tree: make mas_validate_limits() check root node and node limit
maple_tree: update mt_validate()
maple_tree: replace mas_logical_pivot() with mas_safe_pivot()
maple_tree: drop mas_first_entry()
include/linux/maple_tree.h | 2 -
lib/maple_tree.c | 246 +++++++++++--------------------------
2 files changed, 69 insertions(+), 179 deletions(-)
--
2.20.1
Set the node limit of the root node so that the last pivot of all nodes
is the node limit (if the node is not full).
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d3072858c280..f55e59bd9122 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
mas->offset = slot;
pivots[slot] = mas->last;
if (mas->last != ULONG_MAX)
- slot++;
+ pivots[++slot] = ULONG_MAX;
+
mas->depth = 1;
mas_set_height(mas);
ma_set_meta(node, maple_leaf_64, 0, slot);
--
2.20.1
Replace mas_logical_pivot() with mas_safe_pivot() and drop
mas_logical_pivot() since it won't be used anymore. We can do this since
now all nodes will have node limit pivot (if it is not full node).
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 33 +++------------------------------
1 file changed, 3 insertions(+), 30 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3aede7deaa26..8c08bfdc99cf 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -728,33 +728,6 @@ mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
return mas->min;
}
-/*
- * mas_logical_pivot() - Get the logical pivot of a given offset.
- * @mas: The maple state
- * @pivots: The pointer to the maple node pivots
- * @offset: The offset into the pivot array
- * @type: The maple node type
- *
- * When there is no value at a pivot (beyond the end of the data), then the
- * pivot is actually @mas->max.
- *
- * Return: the logical pivot of a given @offset.
- */
-static inline unsigned long
-mas_logical_pivot(struct ma_state *mas, unsigned long *pivots,
- unsigned char offset, enum maple_type type)
-{
- unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type);
-
- if (likely(lpiv))
- return lpiv;
-
- if (likely(offset))
- return mas->max;
-
- return lpiv;
-}
-
/*
* mte_set_pivot() - Set a pivot to a value in an encoded maple node.
* @mn: The encoded maple node
@@ -2202,7 +2175,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas,
goto b_end;
/* Handle new range ending before old range ends */
- piv = mas_logical_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);
+ piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);
if (piv > mas->last) {
if (piv == ULONG_MAX)
mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type);
@@ -4934,7 +4907,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
min = mas_safe_min(mas, pivots, offset);
data_end = ma_data_end(node, type, pivots, mas->max);
for (; offset <= data_end; offset++) {
- pivot = mas_logical_pivot(mas, pivots, offset, type);
+ pivot = mas_safe_pivot(mas, pivots, offset, type);
/* Not within lower bounds */
if (mas->index > pivot)
@@ -7007,7 +6980,7 @@ static void mas_validate_gaps(struct ma_state *mas)
gaps = ma_gaps(node, mt);
for (i = 0; i < mt_slot_count(mte); i++) {
- p_end = mas_logical_pivot(mas, pivots, i, mt);
+ p_end = mas_safe_pivot(mas, pivots, i, mt);
if (!gaps) {
if (!mas_get_slot(mas, i))
--
2.20.1
Do not use a special offset to indicate that there is no gap. When there
is no gap, offset can point to any valid slots because its gap is 0.
Signed-off-by: Peng Zhang <[email protected]>
---
include/linux/maple_tree.h | 2 --
lib/maple_tree.c | 13 ++-----------
2 files changed, 2 insertions(+), 13 deletions(-)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index e18ecbefc7f7..4e004d86c780 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -29,14 +29,12 @@
#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) */
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index f55e59bd9122..6a8982146338 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1610,8 +1610,6 @@ ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,
* mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
* @mas: The maple state.
*
- * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap.
- *
* Return: The gap value.
*/
static inline unsigned long mas_max_gap(struct ma_state *mas)
@@ -1628,9 +1626,6 @@ static inline unsigned long mas_max_gap(struct ma_state *mas)
node = mas_mn(mas);
MAS_BUG_ON(mas, mt != maple_arange_64);
offset = ma_meta_gap(node, mt);
- if (offset == MAPLE_ARANGE64_META_MAX)
- return 0;
-
gaps = ma_gaps(node, mt);
return gaps[offset];
}
@@ -1662,10 +1657,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
ascend:
MAS_BUG_ON(mas, pmt != maple_arange_64);
meta_offset = ma_meta_gap(pnode, pmt);
- if (meta_offset == MAPLE_ARANGE64_META_MAX)
- meta_gap = 0;
- else
- meta_gap = pgaps[meta_offset];
+ meta_gap = pgaps[meta_offset];
pgaps[offset] = new;
@@ -1678,7 +1670,6 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
ma_set_meta_gap(pnode, pmt, offset);
} else if (new < meta_gap) {
- meta_offset = 15;
new = ma_max_gap(pnode, pgaps, pmt, &meta_offset);
ma_set_meta_gap(pnode, pmt, meta_offset);
}
@@ -2076,7 +2067,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
end = j - 1;
if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {
unsigned long max_gap = 0;
- unsigned char offset = 15;
+ unsigned char offset = 0;
gaps = ma_gaps(node, mt);
do {
--
2.20.1
Update mas_validate_limits() to check root node, check node limit pivot
if there is enough room for it to exist and check data_end. Remove the
check for child existence as it is done in mas_validate_child_slot().
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 26 +++++++++++---------------
1 file changed, 11 insertions(+), 15 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 88d6373f37b0..e84a042b6d84 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7148,26 +7148,15 @@ static void mas_validate_limits(struct ma_state *mas)
void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
unsigned long *pivots = ma_pivots(mas_mn(mas), type);
- /* all limits are fine here. */
- if (mte_is_root(mas->node))
- return;
-
for (i = 0; i < mt_slots[type]; i++) {
unsigned long piv;
piv = mas_safe_pivot(mas, pivots, i, type);
- if (!piv && (i != 0))
- break;
-
- if (!mte_is_leaf(mas->node)) {
- void *entry = mas_slot(mas, slots, i);
-
- if (!entry)
- pr_err("%p[%u] cannot be null\n",
- mas_mn(mas), i);
-
- MT_BUG_ON(mas->tree, !entry);
+ if (!piv && (i != 0)) {
+ pr_err("Missing node limit pivot at %p[%u]",
+ mas_mn(mas), i);
+ MAS_WARN_ON(mas, 1);
}
if (prev_piv > piv) {
@@ -7190,6 +7179,13 @@ static void mas_validate_limits(struct ma_state *mas)
if (piv == mas->max)
break;
}
+
+ if (mas_data_end(mas) != i) {
+ pr_err("node%p: data_end %u != the last slot offset %u\n",
+ mas_mn(mas), mas_data_end(mas), i);
+ MT_BUG_ON(mas->tree, 1);
+ }
+
for (i += 1; i < mt_slots[type]; i++) {
void *entry = mas_slot(mas, slots, i);
--
2.20.1
Don't break the loop before checking the last slot. Also here check if
non-leaf nodes are missing children.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1fe8b6a787dd..88d6373f37b0 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7111,11 +7111,12 @@ static void mas_validate_child_slot(struct ma_state *mas)
for (i = 0; i < mt_slots[type]; i++) {
child = mas_slot(mas, slots, i);
- if (!pivots[i] || pivots[i] == mas->max)
- break;
- if (!child)
- break;
+ if (!child) {
+ pr_err("Non-leaf node lacks child at %p[%u]\n",
+ mas_mn(mas), i);
+ MT_BUG_ON(mas->tree, 1);
+ }
if (mte_parent_slot(child) != i) {
pr_err("Slot error at %p[%u]: child %p has pslot %u\n",
@@ -7130,6 +7131,9 @@ static void mas_validate_child_slot(struct ma_state *mas)
mte_to_node(mas->node));
MT_BUG_ON(mas->tree, 1);
}
+
+ if (i < mt_pivots[type] && pivots[i] == mas->max)
+ break;
}
}
--
2.20.1
The internal function mas_first_entry() is no longer used, so drop it.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 72 ------------------------------------------------
1 file changed, 72 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 8c08bfdc99cf..ad6810ed3231 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6662,78 +6662,6 @@ static inline struct maple_enode *mas_get_slot(struct ma_state *mas,
offset);
}
-
-/*
- * mas_first_entry() - Go the first leaf and find the first entry.
- * @mas: the maple state.
- * @limit: the maximum index to check.
- * @*r_start: Pointer to set to the range start.
- *
- * Sets mas->offset to the offset of the entry, r_start to the range minimum.
- *
- * Return: The first entry or MAS_NONE.
- */
-static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn,
- unsigned long limit, enum maple_type mt)
-
-{
- unsigned long max;
- unsigned long *pivots;
- void __rcu **slots;
- void *entry = NULL;
-
- mas->index = mas->min;
- if (mas->index > limit)
- goto none;
-
- max = mas->max;
- mas->offset = 0;
- while (likely(!ma_is_leaf(mt))) {
- MAS_WARN_ON(mas, mte_dead_node(mas->node));
- slots = ma_slots(mn, mt);
- entry = mas_slot(mas, slots, 0);
- pivots = ma_pivots(mn, mt);
- if (unlikely(ma_dead_node(mn)))
- return NULL;
- max = pivots[0];
- mas->node = entry;
- mn = mas_mn(mas);
- mt = mte_node_type(mas->node);
- }
- MAS_WARN_ON(mas, mte_dead_node(mas->node));
-
- mas->max = max;
- slots = ma_slots(mn, mt);
- entry = mas_slot(mas, slots, 0);
- if (unlikely(ma_dead_node(mn)))
- return NULL;
-
- /* Slot 0 or 1 must be set */
- if (mas->index > limit)
- goto none;
-
- if (likely(entry))
- return entry;
-
- mas->offset = 1;
- entry = mas_slot(mas, slots, 1);
- pivots = ma_pivots(mn, mt);
- if (unlikely(ma_dead_node(mn)))
- return NULL;
-
- mas->index = pivots[0] + 1;
- if (mas->index > limit)
- goto none;
-
- if (likely(entry))
- return entry;
-
-none:
- if (likely(!ma_dead_node(mn)))
- mas->node = MAS_NONE;
- return NULL;
-}
-
/* Depth first search, post-order */
static void mas_dfs_postorder(struct ma_state *mas, unsigned long max)
{
--
2.20.1
Instead of using mas_first_entry() to find the leftmost leaf, use a
simple loop instead. Remove an unneeded check for root node. To make
the error message more accurate, check pivots first and then slots,
because checking slots depend on the node limit pivot to break the loop.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 21 +++++++++++----------
1 file changed, 11 insertions(+), 10 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e84a042b6d84..3aede7deaa26 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt)
if (!mas_searchable(&mas))
goto done;
- mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
+ while (!mte_is_leaf(mas.node))
+ mas_descend(&mas);
+
while (!mas_is_none(&mas)) {
MAS_WARN_ON(&mas, mte_dead_node(mas.node));
- if (!mte_is_root(mas.node)) {
- end = mas_data_end(&mas);
- if (MAS_WARN_ON(&mas,
- (end < mt_min_slot_count(mas.node)) &&
- (mas.max != ULONG_MAX))) {
- pr_err("Invalid size %u of %p\n", end,
- mas_mn(&mas));
- }
+ end = mas_data_end(&mas);
+ if (MAS_WARN_ON(&mas,
+ (end < mt_min_slot_count(mas.node)) &&
+ (mas.max != ULONG_MAX))) {
+ pr_err("Invalid size %u of %p\n", end,
+ mas_mn(&mas));
}
+
mas_validate_parent_slot(&mas);
- mas_validate_child_slot(&mas);
mas_validate_limits(&mas);
+ mas_validate_child_slot(&mas);
if (mt_is_alloc(mt))
mas_validate_gaps(&mas);
mas_dfs_postorder(&mas, ULONG_MAX);
--
2.20.1
Make mas_validate_gaps() check whether the offset in the metadata points
to the largest gap. By the way, simplify this function.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 68 +++++++++++++++++++++++-------------------------
1 file changed, 33 insertions(+), 35 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 6a8982146338..1fe8b6a787dd 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump);
static void mas_validate_gaps(struct ma_state *mas)
{
struct maple_enode *mte = mas->node;
- struct maple_node *p_mn;
+ struct maple_node *p_mn, *node = mte_to_node(mte);
+ enum maple_type mt = mte_node_type(mas->node);
unsigned long gap = 0, max_gap = 0;
unsigned long p_end, p_start = mas->min;
- unsigned char p_slot;
+ unsigned char p_slot, offset;
unsigned long *gaps = NULL;
- unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
+ unsigned long *pivots = ma_pivots(node, mt);
int i;
- if (ma_is_dense(mte_node_type(mte))) {
+ if (ma_is_dense(mt)) {
for (i = 0; i < mt_slot_count(mte); i++) {
if (mas_get_slot(mas, i)) {
if (gap > max_gap)
@@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas)
goto counted;
}
- gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte));
+ gaps = ma_gaps(node, mt);
for (i = 0; i < mt_slot_count(mte); i++) {
- p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
+ p_end = mas_logical_pivot(mas, pivots, i, mt);
if (!gaps) {
- if (mas_get_slot(mas, i)) {
- gap = 0;
- goto not_empty;
- }
-
- gap += p_end - p_start + 1;
+ if (!mas_get_slot(mas, i))
+ gap = p_end - p_start + 1;
} else {
void *entry = mas_get_slot(mas, i);
gap = gaps[i];
- if (!entry) {
- if (gap != p_end - p_start + 1) {
- pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n",
- mas_mn(mas), i,
- mas_get_slot(mas, i), gap,
- p_end, p_start);
- mt_dump(mas->tree, mt_dump_hex);
-
- MT_BUG_ON(mas->tree,
- gap != p_end - p_start + 1);
- }
- } else {
- if (gap > p_end - p_start + 1) {
- pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
- mas_mn(mas), i, gap, p_end, p_start,
- p_end - p_start + 1);
- MT_BUG_ON(mas->tree,
- gap > p_end - p_start + 1);
- }
+ MT_BUG_ON(mas->tree, !entry);
+
+ if (gap > p_end - p_start + 1) {
+ pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
+ mas_mn(mas), i, gap, p_end, p_start,
+ p_end - p_start + 1);
+ MT_BUG_ON(mas->tree,
+ gap > p_end - p_start + 1);
}
}
if (gap > max_gap)
max_gap = gap;
-not_empty:
+
p_start = p_end + 1;
if (p_end >= mas->max)
break;
}
counted:
+ if (mt == maple_arange_64) {
+ offset = ma_meta_gap(node, mt);
+ if (offset > mt_slots[mt]) {
+ pr_err("gap offset %p[%u] is invalid\n", node, offset);
+ MT_BUG_ON(mas->tree, 1);
+ }
+
+ if (gaps[offset] != max_gap) {
+ pr_err("gap %p[%u] is not the largest gap %lu\n",
+ node, offset, max_gap);
+ MT_BUG_ON(mas->tree, 1);
+ }
+ }
+
if (mte_is_root(mte))
return;
@@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas)
if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
mt_dump(mas->tree, mt_dump_hex);
+ MT_BUG_ON(mas->tree, 1);
}
-
- MT_BUG_ON(mas->tree,
- ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap);
}
static void mas_validate_parent_slot(struct ma_state *mas)
--
2.20.1
This has been on my todo list. I will review these soon.
Thanks for resending them.
* Peng Zhang <[email protected]> [230707 06:11]:
> These patches do the following:
> 001 - 002: Small cleanup to maple tree.
> 003 - 006: Improve the validation for maple tree.
> 007 - 008: Drop some functions that will no longer be used.
>
> Peng Zhang (8):
> maple_tree: set the node limit when creating a new root node
> maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap
> maple_tree: make mas_validate_gaps() to check metadata
> maple_tree: fix mas_validate_child_slot() to check last missed slot
> maple_tree: make mas_validate_limits() check root node and node limit
> maple_tree: update mt_validate()
> maple_tree: replace mas_logical_pivot() with mas_safe_pivot()
> maple_tree: drop mas_first_entry()
>
> include/linux/maple_tree.h | 2 -
> lib/maple_tree.c | 246 +++++++++++--------------------------
> 2 files changed, 69 insertions(+), 179 deletions(-)
>
> --
> 2.20.1
>
>
* Peng Zhang <[email protected]> [230707 06:11]:
> Make mas_validate_gaps() check whether the offset in the metadata points
> to the largest gap. By the way, simplify this function.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> lib/maple_tree.c | 68 +++++++++++++++++++++++-------------------------
> 1 file changed, 33 insertions(+), 35 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 6a8982146338..1fe8b6a787dd 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump);
> static void mas_validate_gaps(struct ma_state *mas)
> {
> struct maple_enode *mte = mas->node;
> - struct maple_node *p_mn;
> + struct maple_node *p_mn, *node = mte_to_node(mte);
> + enum maple_type mt = mte_node_type(mas->node);
> unsigned long gap = 0, max_gap = 0;
> unsigned long p_end, p_start = mas->min;
> - unsigned char p_slot;
> + unsigned char p_slot, offset;
> unsigned long *gaps = NULL;
> - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
> + unsigned long *pivots = ma_pivots(node, mt);
> int i;
>
> - if (ma_is_dense(mte_node_type(mte))) {
> + if (ma_is_dense(mt)) {
> for (i = 0; i < mt_slot_count(mte); i++) {
> if (mas_get_slot(mas, i)) {
> if (gap > max_gap)
> @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas)
> goto counted;
> }
>
> - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte));
> + gaps = ma_gaps(node, mt);
> for (i = 0; i < mt_slot_count(mte); i++) {
> - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
> + p_end = mas_logical_pivot(mas, pivots, i, mt);
>
> if (!gaps) {
> - if (mas_get_slot(mas, i)) {
> - gap = 0;
> - goto not_empty;
> - }
> -
> - gap += p_end - p_start + 1;
> + if (!mas_get_slot(mas, i))
> + gap = p_end - p_start + 1;
> } else {
> void *entry = mas_get_slot(mas, i);
>
> gap = gaps[i];
> - if (!entry) {
> - if (gap != p_end - p_start + 1) {
> - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n",
> - mas_mn(mas), i,
> - mas_get_slot(mas, i), gap,
> - p_end, p_start);
> - mt_dump(mas->tree, mt_dump_hex);
> -
> - MT_BUG_ON(mas->tree,
> - gap != p_end - p_start + 1);
> - }
> - } else {
> - if (gap > p_end - p_start + 1) {
> - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
> - mas_mn(mas), i, gap, p_end, p_start,
> - p_end - p_start + 1);
> - MT_BUG_ON(mas->tree,
> - gap > p_end - p_start + 1);
> - }
> + MT_BUG_ON(mas->tree, !entry);
> +
> + if (gap > p_end - p_start + 1) {
> + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
> + mas_mn(mas), i, gap, p_end, p_start,
> + p_end - p_start + 1);
> + MT_BUG_ON(mas->tree,
> + gap > p_end - p_start + 1);
Your change above points out that we are not verifying all gaps are zero
in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap'
indicator then this may be an issue, or maybe it already is an issue?
> }
> }
>
> if (gap > max_gap)
> max_gap = gap;
> -not_empty:
> +
> p_start = p_end + 1;
> if (p_end >= mas->max)
> break;
> }
>
> counted:
> + if (mt == maple_arange_64) {
We could loop through the remainder of the gaps here pretty easily.
> + offset = ma_meta_gap(node, mt);
> + if (offset > mt_slots[mt]) {
> + pr_err("gap offset %p[%u] is invalid\n", node, offset);
> + MT_BUG_ON(mas->tree, 1);
> + }
> +
> + if (gaps[offset] != max_gap) {
> + pr_err("gap %p[%u] is not the largest gap %lu\n",
> + node, offset, max_gap);
> + MT_BUG_ON(mas->tree, 1);
> + }
> + }
> +
> if (mte_is_root(mte))
> return;
>
> @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas)
> if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
> pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
> mt_dump(mas->tree, mt_dump_hex);
> + MT_BUG_ON(mas->tree, 1);
> }
> -
> - MT_BUG_ON(mas->tree,
> - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap);
> }
>
> static void mas_validate_parent_slot(struct ma_state *mas)
> --
> 2.20.1
>
>
> --
> maple-tree mailing list
> [email protected]
> https://lists.infradead.org/mailman/listinfo/maple-tree
* Peng Zhang <[email protected]> [230707 06:11]:
> Instead of using mas_first_entry() to find the leftmost leaf, use a
> simple loop instead. Remove an unneeded check for root node. To make
> the error message more accurate, check pivots first and then slots,
> because checking slots depend on the node limit pivot to break the loop.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> lib/maple_tree.c | 21 +++++++++++----------
> 1 file changed, 11 insertions(+), 10 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index e84a042b6d84..3aede7deaa26 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt)
> if (!mas_searchable(&mas))
> goto done;
>
> - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
> + while (!mte_is_leaf(mas.node))
> + mas_descend(&mas);
> +
> while (!mas_is_none(&mas)) {
> MAS_WARN_ON(&mas, mte_dead_node(mas.node));
> - if (!mte_is_root(mas.node)) {
> - end = mas_data_end(&mas);
> - if (MAS_WARN_ON(&mas,
> - (end < mt_min_slot_count(mas.node)) &&
> - (mas.max != ULONG_MAX))) {
> - pr_err("Invalid size %u of %p\n", end,
> - mas_mn(&mas));
> - }
> + end = mas_data_end(&mas);
> + if (MAS_WARN_ON(&mas,
> + (end < mt_min_slot_count(mas.node)) &&
> + (mas.max != ULONG_MAX))) {
This line can be reformatted now that it is not as nested.
> + pr_err("Invalid size %u of %p\n", end,
> + mas_mn(&mas));
Ditto here.
> }
> +
> mas_validate_parent_slot(&mas);
> - mas_validate_child_slot(&mas);
> mas_validate_limits(&mas);
> + mas_validate_child_slot(&mas);
> if (mt_is_alloc(mt))
> mas_validate_gaps(&mas);
> mas_dfs_postorder(&mas, ULONG_MAX);
> --
> 2.20.1
>
>
* Peng Zhang <[email protected]> [230707 06:11]:
> Update mas_validate_limits() to check root node, check node limit pivot
> if there is enough room for it to exist and check data_end. Remove the
> check for child existence as it is done in mas_validate_child_slot().
>
The comments for this function say:
* Validate all pivots are within mas->min and mas->max.
This needs adjusting since we are doing a whole lot more now..
Validate limits is now checking metadata ends where the maximum ends,
checks the pivots are within the limits of the node, and ensures
there is no slots or pivots set outside of the end of the data.
Did I miss anything?
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> lib/maple_tree.c | 26 +++++++++++---------------
> 1 file changed, 11 insertions(+), 15 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 88d6373f37b0..e84a042b6d84 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -7148,26 +7148,15 @@ static void mas_validate_limits(struct ma_state *mas)
> void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
> unsigned long *pivots = ma_pivots(mas_mn(mas), type);
>
> - /* all limits are fine here. */
> - if (mte_is_root(mas->node))
> - return;
> -
> for (i = 0; i < mt_slots[type]; i++) {
> unsigned long piv;
>
> piv = mas_safe_pivot(mas, pivots, i, type);
>
> - if (!piv && (i != 0))
> - break;
> -
> - if (!mte_is_leaf(mas->node)) {
> - void *entry = mas_slot(mas, slots, i);
> -
> - if (!entry)
> - pr_err("%p[%u] cannot be null\n",
> - mas_mn(mas), i);
> -
> - MT_BUG_ON(mas->tree, !entry);
> + if (!piv && (i != 0)) {
> + pr_err("Missing node limit pivot at %p[%u]",
> + mas_mn(mas), i);
> + MAS_WARN_ON(mas, 1);
> }
>
> if (prev_piv > piv) {
> @@ -7190,6 +7179,13 @@ static void mas_validate_limits(struct ma_state *mas)
> if (piv == mas->max)
> break;
> }
> +
> + if (mas_data_end(mas) != i) {
> + pr_err("node%p: data_end %u != the last slot offset %u\n",
> + mas_mn(mas), mas_data_end(mas), i);
> + MT_BUG_ON(mas->tree, 1);
> + }
> +
> for (i += 1; i < mt_slots[type]; i++) {
> void *entry = mas_slot(mas, slots, i);
>
> --
> 2.20.1
>
>
> --
> maple-tree mailing list
> [email protected]
> https://lists.infradead.org/mailman/listinfo/maple-tree
* Peng Zhang <[email protected]> [230707 06:11]:
> Don't break the loop before checking the last slot. Also here check if
> non-leaf nodes are missing children.
>
> Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> lib/maple_tree.c | 12 ++++++++----
> 1 file changed, 8 insertions(+), 4 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 1fe8b6a787dd..88d6373f37b0 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -7111,11 +7111,12 @@ static void mas_validate_child_slot(struct ma_state *mas)
>
> for (i = 0; i < mt_slots[type]; i++) {
> child = mas_slot(mas, slots, i);
> - if (!pivots[i] || pivots[i] == mas->max)
> - break;
>
> - if (!child)
> - break;
> + if (!child) {
> + pr_err("Non-leaf node lacks child at %p[%u]\n",
> + mas_mn(mas), i);
> + MT_BUG_ON(mas->tree, 1);
> + }
>
> if (mte_parent_slot(child) != i) {
> pr_err("Slot error at %p[%u]: child %p has pslot %u\n",
> @@ -7130,6 +7131,9 @@ static void mas_validate_child_slot(struct ma_state *mas)
> mte_to_node(mas->node));
> MT_BUG_ON(mas->tree, 1);
> }
> +
> + if (i < mt_pivots[type] && pivots[i] == mas->max)
> + break;
> }
> }
>
> --
> 2.20.1
>
>
* Peng Zhang <[email protected]> [230707 06:11]:
> The internal function mas_first_entry() is no longer used, so drop it.
>
> Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> lib/maple_tree.c | 72 ------------------------------------------------
> 1 file changed, 72 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 8c08bfdc99cf..ad6810ed3231 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6662,78 +6662,6 @@ static inline struct maple_enode *mas_get_slot(struct ma_state *mas,
> offset);
> }
>
> -
> -/*
> - * mas_first_entry() - Go the first leaf and find the first entry.
> - * @mas: the maple state.
> - * @limit: the maximum index to check.
> - * @*r_start: Pointer to set to the range start.
> - *
> - * Sets mas->offset to the offset of the entry, r_start to the range minimum.
> - *
> - * Return: The first entry or MAS_NONE.
> - */
> -static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn,
> - unsigned long limit, enum maple_type mt)
> -
> -{
> - unsigned long max;
> - unsigned long *pivots;
> - void __rcu **slots;
> - void *entry = NULL;
> -
> - mas->index = mas->min;
> - if (mas->index > limit)
> - goto none;
> -
> - max = mas->max;
> - mas->offset = 0;
> - while (likely(!ma_is_leaf(mt))) {
> - MAS_WARN_ON(mas, mte_dead_node(mas->node));
> - slots = ma_slots(mn, mt);
> - entry = mas_slot(mas, slots, 0);
> - pivots = ma_pivots(mn, mt);
> - if (unlikely(ma_dead_node(mn)))
> - return NULL;
> - max = pivots[0];
> - mas->node = entry;
> - mn = mas_mn(mas);
> - mt = mte_node_type(mas->node);
> - }
> - MAS_WARN_ON(mas, mte_dead_node(mas->node));
> -
> - mas->max = max;
> - slots = ma_slots(mn, mt);
> - entry = mas_slot(mas, slots, 0);
> - if (unlikely(ma_dead_node(mn)))
> - return NULL;
> -
> - /* Slot 0 or 1 must be set */
> - if (mas->index > limit)
> - goto none;
> -
> - if (likely(entry))
> - return entry;
> -
> - mas->offset = 1;
> - entry = mas_slot(mas, slots, 1);
> - pivots = ma_pivots(mn, mt);
> - if (unlikely(ma_dead_node(mn)))
> - return NULL;
> -
> - mas->index = pivots[0] + 1;
> - if (mas->index > limit)
> - goto none;
> -
> - if (likely(entry))
> - return entry;
> -
> -none:
> - if (likely(!ma_dead_node(mn)))
> - mas->node = MAS_NONE;
> - return NULL;
> -}
> -
> /* Depth first search, post-order */
> static void mas_dfs_postorder(struct ma_state *mas, unsigned long max)
> {
> --
> 2.20.1
>
>
* Peng Zhang <[email protected]> [230707 06:11]:
> Replace mas_logical_pivot() with mas_safe_pivot() and drop
> mas_logical_pivot() since it won't be used anymore. We can do this since
> now all nodes will have node limit pivot (if it is not full node).
>
> Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> lib/maple_tree.c | 33 +++------------------------------
> 1 file changed, 3 insertions(+), 30 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3aede7deaa26..8c08bfdc99cf 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -728,33 +728,6 @@ mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
> return mas->min;
> }
>
> -/*
> - * mas_logical_pivot() - Get the logical pivot of a given offset.
> - * @mas: The maple state
> - * @pivots: The pointer to the maple node pivots
> - * @offset: The offset into the pivot array
> - * @type: The maple node type
> - *
> - * When there is no value at a pivot (beyond the end of the data), then the
> - * pivot is actually @mas->max.
> - *
> - * Return: the logical pivot of a given @offset.
> - */
> -static inline unsigned long
> -mas_logical_pivot(struct ma_state *mas, unsigned long *pivots,
> - unsigned char offset, enum maple_type type)
> -{
> - unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type);
> -
> - if (likely(lpiv))
> - return lpiv;
> -
> - if (likely(offset))
> - return mas->max;
> -
> - return lpiv;
> -}
> -
> /*
> * mte_set_pivot() - Set a pivot to a value in an encoded maple node.
> * @mn: The encoded maple node
> @@ -2202,7 +2175,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas,
> goto b_end;
>
> /* Handle new range ending before old range ends */
> - piv = mas_logical_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);
> + piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);
> if (piv > mas->last) {
> if (piv == ULONG_MAX)
> mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type);
> @@ -4934,7 +4907,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
> min = mas_safe_min(mas, pivots, offset);
> data_end = ma_data_end(node, type, pivots, mas->max);
> for (; offset <= data_end; offset++) {
> - pivot = mas_logical_pivot(mas, pivots, offset, type);
> + pivot = mas_safe_pivot(mas, pivots, offset, type);
>
> /* Not within lower bounds */
> if (mas->index > pivot)
> @@ -7007,7 +6980,7 @@ static void mas_validate_gaps(struct ma_state *mas)
>
> gaps = ma_gaps(node, mt);
> for (i = 0; i < mt_slot_count(mte); i++) {
> - p_end = mas_logical_pivot(mas, pivots, i, mt);
> + p_end = mas_safe_pivot(mas, pivots, i, mt);
>
> if (!gaps) {
> if (!mas_get_slot(mas, i))
> --
> 2.20.1
>
>
* Peng Zhang <[email protected]> [230707 06:11]:
> Do not use a special offset to indicate that there is no gap. When there
> is no gap, offset can point to any valid slots because its gap is 0.
>
> Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> include/linux/maple_tree.h | 2 --
> lib/maple_tree.c | 13 ++-----------
> 2 files changed, 2 insertions(+), 13 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index e18ecbefc7f7..4e004d86c780 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -29,14 +29,12 @@
> #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) */
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index f55e59bd9122..6a8982146338 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1610,8 +1610,6 @@ ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,
> * mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
> * @mas: The maple state.
> *
> - * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap.
> - *
> * Return: The gap value.
> */
> static inline unsigned long mas_max_gap(struct ma_state *mas)
> @@ -1628,9 +1626,6 @@ static inline unsigned long mas_max_gap(struct ma_state *mas)
> node = mas_mn(mas);
> MAS_BUG_ON(mas, mt != maple_arange_64);
> offset = ma_meta_gap(node, mt);
> - if (offset == MAPLE_ARANGE64_META_MAX)
> - return 0;
> -
> gaps = ma_gaps(node, mt);
> return gaps[offset];
> }
> @@ -1662,10 +1657,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
> ascend:
> MAS_BUG_ON(mas, pmt != maple_arange_64);
> meta_offset = ma_meta_gap(pnode, pmt);
> - if (meta_offset == MAPLE_ARANGE64_META_MAX)
> - meta_gap = 0;
> - else
> - meta_gap = pgaps[meta_offset];
> + meta_gap = pgaps[meta_offset];
>
> pgaps[offset] = new;
>
> @@ -1678,7 +1670,6 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
>
> ma_set_meta_gap(pnode, pmt, offset);
> } else if (new < meta_gap) {
> - meta_offset = 15;
> new = ma_max_gap(pnode, pgaps, pmt, &meta_offset);
> ma_set_meta_gap(pnode, pmt, meta_offset);
> }
> @@ -2076,7 +2067,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
> end = j - 1;
> if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {
> unsigned long max_gap = 0;
> - unsigned char offset = 15;
> + unsigned char offset = 0;
>
> gaps = ma_gaps(node, mt);
> do {
> --
> 2.20.1
>
* Peng Zhang <[email protected]> [230707 06:11]:
> Set the node limit of the root node so that the last pivot of all nodes
> is the node limit (if the node is not full).
>
> Signed-off-by: Peng Zhang <[email protected]>
This has been on my list of things to do for a while, thanks.
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> lib/maple_tree.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index d3072858c280..f55e59bd9122 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
> mas->offset = slot;
> pivots[slot] = mas->last;
> if (mas->last != ULONG_MAX)
> - slot++;
> + pivots[++slot] = ULONG_MAX;
> +
> mas->depth = 1;
> mas_set_height(mas);
> ma_set_meta(node, maple_leaf_64, 0, slot);
> --
> 2.20.1
>
>
在 2023/7/7 22:58, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230707 06:11]:
>> Update mas_validate_limits() to check root node, check node limit pivot
>> if there is enough room for it to exist and check data_end. Remove the
>> check for child existence as it is done in mas_validate_child_slot().
>>
>
> The comments for this function say:
> * Validate all pivots are within mas->min and mas->max.
>
> This needs adjusting since we are doing a whole lot more now..
Thanks, I will update it in v2.
>
> Validate limits is now checking metadata ends where the maximum ends,
> checks the pivots are within the limits of the node, and ensures
> there is no slots or pivots set outside of the end of the data.
>
> Did I miss anything?
You're right, that's exactly all the checks it does.
>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> lib/maple_tree.c | 26 +++++++++++---------------
>> 1 file changed, 11 insertions(+), 15 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 88d6373f37b0..e84a042b6d84 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -7148,26 +7148,15 @@ static void mas_validate_limits(struct ma_state *mas)
>> void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
>> unsigned long *pivots = ma_pivots(mas_mn(mas), type);
>>
>> - /* all limits are fine here. */
>> - if (mte_is_root(mas->node))
>> - return;
>> -
>> for (i = 0; i < mt_slots[type]; i++) {
>> unsigned long piv;
>>
>> piv = mas_safe_pivot(mas, pivots, i, type);
>>
>> - if (!piv && (i != 0))
>> - break;
>> -
>> - if (!mte_is_leaf(mas->node)) {
>> - void *entry = mas_slot(mas, slots, i);
>> -
>> - if (!entry)
>> - pr_err("%p[%u] cannot be null\n",
>> - mas_mn(mas), i);
>> -
>> - MT_BUG_ON(mas->tree, !entry);
>> + if (!piv && (i != 0)) {
>> + pr_err("Missing node limit pivot at %p[%u]",
>> + mas_mn(mas), i);
>> + MAS_WARN_ON(mas, 1);
>> }
>>
>> if (prev_piv > piv) {
>> @@ -7190,6 +7179,13 @@ static void mas_validate_limits(struct ma_state *mas)
>> if (piv == mas->max)
>> break;
>> }
>> +
>> + if (mas_data_end(mas) != i) {
>> + pr_err("node%p: data_end %u != the last slot offset %u\n",
>> + mas_mn(mas), mas_data_end(mas), i);
>> + MT_BUG_ON(mas->tree, 1);
>> + }
>> +
>> for (i += 1; i < mt_slots[type]; i++) {
>> void *entry = mas_slot(mas, slots, i);
>>
>> --
>> 2.20.1
>>
>>
>> --
>> maple-tree mailing list
>> [email protected]
>> https://lists.infradead.org/mailman/listinfo/maple-tree
在 2023/7/7 23:02, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230707 06:11]:
>> Instead of using mas_first_entry() to find the leftmost leaf, use a
>> simple loop instead. Remove an unneeded check for root node. To make
>> the error message more accurate, check pivots first and then slots,
>> because checking slots depend on the node limit pivot to break the loop.
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> lib/maple_tree.c | 21 +++++++++++----------
>> 1 file changed, 11 insertions(+), 10 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index e84a042b6d84..3aede7deaa26 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt)
>> if (!mas_searchable(&mas))
>> goto done;
>>
>> - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
>> + while (!mte_is_leaf(mas.node))
>> + mas_descend(&mas);
>> +
>> while (!mas_is_none(&mas)) {
>> MAS_WARN_ON(&mas, mte_dead_node(mas.node));
>> - if (!mte_is_root(mas.node)) {
>> - end = mas_data_end(&mas);
>> - if (MAS_WARN_ON(&mas,
>> - (end < mt_min_slot_count(mas.node)) &&
>> - (mas.max != ULONG_MAX))) {
>> - pr_err("Invalid size %u of %p\n", end,
>> - mas_mn(&mas));
>> - }
>> + end = mas_data_end(&mas);
>> + if (MAS_WARN_ON(&mas,
>> + (end < mt_min_slot_count(mas.node)) &&
>> + (mas.max != ULONG_MAX))) {
>
> This line can be reformatted now that it is not as nested.
>
>> + pr_err("Invalid size %u of %p\n", end,
>> + mas_mn(&mas));
>
> Ditto here.
Thanks, I'll reformat it.
>
>> }
>> +
>> mas_validate_parent_slot(&mas);
>> - mas_validate_child_slot(&mas);
>> mas_validate_limits(&mas);
>> + mas_validate_child_slot(&mas);
>> if (mt_is_alloc(mt))
>> mas_validate_gaps(&mas);
>> mas_dfs_postorder(&mas, ULONG_MAX);
>> --
>> 2.20.1
>>
>>
在 2023/7/7 22:45, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230707 06:11]:
>> Make mas_validate_gaps() check whether the offset in the metadata points
>> to the largest gap. By the way, simplify this function.
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> lib/maple_tree.c | 68 +++++++++++++++++++++++-------------------------
>> 1 file changed, 33 insertions(+), 35 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 6a8982146338..1fe8b6a787dd 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump);
>> static void mas_validate_gaps(struct ma_state *mas)
>> {
>> struct maple_enode *mte = mas->node;
>> - struct maple_node *p_mn;
>> + struct maple_node *p_mn, *node = mte_to_node(mte);
>> + enum maple_type mt = mte_node_type(mas->node);
>> unsigned long gap = 0, max_gap = 0;
>> unsigned long p_end, p_start = mas->min;
>> - unsigned char p_slot;
>> + unsigned char p_slot, offset;
>> unsigned long *gaps = NULL;
>> - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
>> + unsigned long *pivots = ma_pivots(node, mt);
>> int i;
>>
>> - if (ma_is_dense(mte_node_type(mte))) {
>> + if (ma_is_dense(mt)) {
>> for (i = 0; i < mt_slot_count(mte); i++) {
>> if (mas_get_slot(mas, i)) {
>> if (gap > max_gap)
>> @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas)
>> goto counted;
>> }
>>
>> - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte));
>> + gaps = ma_gaps(node, mt);
>> for (i = 0; i < mt_slot_count(mte); i++) {
>> - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
>> + p_end = mas_logical_pivot(mas, pivots, i, mt);
>>
>> if (!gaps) {
>> - if (mas_get_slot(mas, i)) {
>> - gap = 0;
>> - goto not_empty;
>> - }
>> -
>> - gap += p_end - p_start + 1;
>> + if (!mas_get_slot(mas, i))
>> + gap = p_end - p_start + 1;
>> } else {
>> void *entry = mas_get_slot(mas, i);
>>
>> gap = gaps[i];
>> - if (!entry) {
>> - if (gap != p_end - p_start + 1) {
>> - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n",
>> - mas_mn(mas), i,
>> - mas_get_slot(mas, i), gap,
>> - p_end, p_start);
>> - mt_dump(mas->tree, mt_dump_hex);
>> -
>> - MT_BUG_ON(mas->tree,
>> - gap != p_end - p_start + 1);
>> - }
>> - } else {
>> - if (gap > p_end - p_start + 1) {
>> - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
>> - mas_mn(mas), i, gap, p_end, p_start,
>> - p_end - p_start + 1);
>> - MT_BUG_ON(mas->tree,
>> - gap > p_end - p_start + 1);
>> - }
>> + MT_BUG_ON(mas->tree, !entry);
>> +
>> + if (gap > p_end - p_start + 1) {
>> + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
>> + mas_mn(mas), i, gap, p_end, p_start,
>> + p_end - p_start + 1);
>> + MT_BUG_ON(mas->tree,
>> + gap > p_end - p_start + 1);
>
> Your change above points out that we are not verifying all gaps are zero
> in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap'
> indicator then this may be an issue, or maybe it already is an issue?
If we don't have a 'no gap' indicator, why is there an issue? Are you
worried that meta_gap is wrongly pointing to the gap after the node
limit? If so we can verify that meta_gap points to a gap within the node
limit.
>
>> }
>> }
>>
>> if (gap > max_gap)
>> max_gap = gap;
>> -not_empty:
>> +
>> p_start = p_end + 1;
>> if (p_end >= mas->max)
>> break;
>> }
>>
>> counted:
>> + if (mt == maple_arange_64) {
>
> We could loop through the remainder of the gaps here pretty easily.
In this way, it can be verified that the gaps after the node limit are
0.
>
>> + offset = ma_meta_gap(node, mt);
>> + if (offset > mt_slots[mt]) {
>> + pr_err("gap offset %p[%u] is invalid\n", node, offset);
>> + MT_BUG_ON(mas->tree, 1);
>> + }
>> +
>> + if (gaps[offset] != max_gap) {
>> + pr_err("gap %p[%u] is not the largest gap %lu\n",
>> + node, offset, max_gap);
>> + MT_BUG_ON(mas->tree, 1);
>> + }
>> + }
>> +
>> if (mte_is_root(mte))
>> return;
>>
>> @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas)
>> if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
>> pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
>> mt_dump(mas->tree, mt_dump_hex);
>> + MT_BUG_ON(mas->tree, 1);
>> }
>> -
>> - MT_BUG_ON(mas->tree,
>> - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap);
>> }
>>
>> static void mas_validate_parent_slot(struct ma_state *mas)
>> --
>> 2.20.1
>>
>>
>> --
>> maple-tree mailing list
>> [email protected]
>> https://lists.infradead.org/mailman/listinfo/maple-tree
* Peng Zhang <[email protected]> [230710 05:44]:
>
>
> 在 2023/7/7 22:45, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [230707 06:11]:
> > > Make mas_validate_gaps() check whether the offset in the metadata points
> > > to the largest gap. By the way, simplify this function.
> > >
> > > Signed-off-by: Peng Zhang <[email protected]>
> > > ---
> > > lib/maple_tree.c | 68 +++++++++++++++++++++++-------------------------
> > > 1 file changed, 33 insertions(+), 35 deletions(-)
> > >
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 6a8982146338..1fe8b6a787dd 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump);
> > > static void mas_validate_gaps(struct ma_state *mas)
> > > {
> > > struct maple_enode *mte = mas->node;
> > > - struct maple_node *p_mn;
> > > + struct maple_node *p_mn, *node = mte_to_node(mte);
> > > + enum maple_type mt = mte_node_type(mas->node);
> > > unsigned long gap = 0, max_gap = 0;
> > > unsigned long p_end, p_start = mas->min;
> > > - unsigned char p_slot;
> > > + unsigned char p_slot, offset;
> > > unsigned long *gaps = NULL;
> > > - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
> > > + unsigned long *pivots = ma_pivots(node, mt);
> > > int i;
> > > - if (ma_is_dense(mte_node_type(mte))) {
> > > + if (ma_is_dense(mt)) {
> > > for (i = 0; i < mt_slot_count(mte); i++) {
> > > if (mas_get_slot(mas, i)) {
> > > if (gap > max_gap)
> > > @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas)
> > > goto counted;
> > > }
> > > - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte));
> > > + gaps = ma_gaps(node, mt);
> > > for (i = 0; i < mt_slot_count(mte); i++) {
> > > - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
> > > + p_end = mas_logical_pivot(mas, pivots, i, mt);
> > > if (!gaps) {
> > > - if (mas_get_slot(mas, i)) {
> > > - gap = 0;
> > > - goto not_empty;
> > > - }
> > > -
> > > - gap += p_end - p_start + 1;
> > > + if (!mas_get_slot(mas, i))
> > > + gap = p_end - p_start + 1;
> > > } else {
> > > void *entry = mas_get_slot(mas, i);
> > > gap = gaps[i];
> > > - if (!entry) {
> > > - if (gap != p_end - p_start + 1) {
> > > - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n",
> > > - mas_mn(mas), i,
> > > - mas_get_slot(mas, i), gap,
> > > - p_end, p_start);
> > > - mt_dump(mas->tree, mt_dump_hex);
> > > -
> > > - MT_BUG_ON(mas->tree,
> > > - gap != p_end - p_start + 1);
> > > - }
> > > - } else {
> > > - if (gap > p_end - p_start + 1) {
> > > - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
> > > - mas_mn(mas), i, gap, p_end, p_start,
> > > - p_end - p_start + 1);
> > > - MT_BUG_ON(mas->tree,
> > > - gap > p_end - p_start + 1);
> > > - }
> > > + MT_BUG_ON(mas->tree, !entry);
> > > +
> > > + if (gap > p_end - p_start + 1) {
> > > + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
> > > + mas_mn(mas), i, gap, p_end, p_start,
> > > + p_end - p_start + 1);
> > > + MT_BUG_ON(mas->tree,
> > > + gap > p_end - p_start + 1);
> >
> > Your change above points out that we are not verifying all gaps are zero
> > in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap'
> > indicator then this may be an issue, or maybe it already is an issue?
> If we don't have a 'no gap' indicator, why is there an issue? Are you
> worried that meta_gap is wrongly pointing to the gap after the node
> limit? If so we can verify that meta_gap points to a gap within the node
> limit.
I'm saying we aren't checking that gaps beyond the node limit are zero.
I wasn't concerned about the meta_gap pointing beyond the node limit,
but it would probably be a good check too.
> >
> > > }
> > > }
> > > if (gap > max_gap)
> > > max_gap = gap;
> > > -not_empty:
> > > +
> > > p_start = p_end + 1;
> > > if (p_end >= mas->max)
> > > break;
> > > }
> > > counted:
> > > + if (mt == maple_arange_64) {
> >
> > We could loop through the remainder of the gaps here pretty easily.
> In this way, it can be verified that the gaps after the node limit are
> 0.
Yes, I think that's a good idea. I don't believe we have a check for
this anywhere.
>
> >
> > > + offset = ma_meta_gap(node, mt);
> > > + if (offset > mt_slots[mt]) {
> > > + pr_err("gap offset %p[%u] is invalid\n", node, offset);
> > > + MT_BUG_ON(mas->tree, 1);
> > > + }
> > > +
> > > + if (gaps[offset] != max_gap) {
> > > + pr_err("gap %p[%u] is not the largest gap %lu\n",
> > > + node, offset, max_gap);
> > > + MT_BUG_ON(mas->tree, 1);
> > > + }
> > > + }
> > > +
> > > if (mte_is_root(mte))
> > > return;
> > > @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas)
> > > if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
> > > pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
> > > mt_dump(mas->tree, mt_dump_hex);
> > > + MT_BUG_ON(mas->tree, 1);
> > > }
> > > -
> > > - MT_BUG_ON(mas->tree,
> > > - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap);
> > > }
> > > static void mas_validate_parent_slot(struct ma_state *mas)
> > > --
> > > 2.20.1
> > >
> > >
> > > --
> > > maple-tree mailing list
> > > [email protected]
> > > https://lists.infradead.org/mailman/listinfo/maple-tree
* Liam R. Howlett <[email protected]> [230707 11:18]:
> * Peng Zhang <[email protected]> [230707 06:11]:
> > Set the node limit of the root node so that the last pivot of all nodes
> > is the node limit (if the node is not full).
This patch also fixes a bug in mas_rev_awalk(). Effectively, always
setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot().
Without this fix, it is possible that very small tasks would fail to
find the correct gap. Although this has not been observed with real
tasks, it has been reported to happen in m68k nommu running the maple
tree tests.
Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/
Cc: <[email protected]>
Cc: Geert Uytterhoeven <[email protected]>
> >
> > Signed-off-by: Peng Zhang <[email protected]>
>
> This has been on my list of things to do for a while, thanks.
>
> Reviewed-by: Liam R. Howlett <[email protected]>
>
> > ---
> > lib/maple_tree.c | 3 ++-
> > 1 file changed, 2 insertions(+), 1 deletion(-)
> >
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index d3072858c280..f55e59bd9122 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
> > mas->offset = slot;
> > pivots[slot] = mas->last;
> > if (mas->last != ULONG_MAX)
> > - slot++;
> > + pivots[++slot] = ULONG_MAX;
> > +
> > mas->depth = 1;
> > mas_set_height(mas);
> > ma_set_meta(node, maple_leaf_64, 0, slot);
> > --
> > 2.20.1
> >
> >
... actually add Geert to the cc list.
* Liam R. Howlett <[email protected]> [230710 11:06]:
> * Liam R. Howlett <[email protected]> [230707 11:18]:
> > * Peng Zhang <[email protected]> [230707 06:11]:
> > > Set the node limit of the root node so that the last pivot of all nodes
> > > is the node limit (if the node is not full).
>
> This patch also fixes a bug in mas_rev_awalk(). Effectively, always
> setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot().
> Without this fix, it is possible that very small tasks would fail to
> find the correct gap. Although this has not been observed with real
> tasks, it has been reported to happen in m68k nommu running the maple
> tree tests.
>
> Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/
> Cc: <[email protected]>
> Cc: Geert Uytterhoeven <[email protected]>
>
> > >
> > > Signed-off-by: Peng Zhang <[email protected]>
> >
> > This has been on my list of things to do for a while, thanks.
> >
> > Reviewed-by: Liam R. Howlett <[email protected]>
> >
> > > ---
> > > lib/maple_tree.c | 3 ++-
> > > 1 file changed, 2 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index d3072858c280..f55e59bd9122 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
> > > mas->offset = slot;
> > > pivots[slot] = mas->last;
> > > if (mas->last != ULONG_MAX)
> > > - slot++;
> > > + pivots[++slot] = ULONG_MAX;
> > > +
> > > mas->depth = 1;
> > > mas_set_height(mas);
> > > ma_set_meta(node, maple_leaf_64, 0, slot);
> > > --
> > > 2.20.1
> > >
> > >
>
> --
> maple-tree mailing list
> [email protected]
> https://lists.infradead.org/mailman/listinfo/maple-tree