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
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 8aba9e419e08..799afd590cf3 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6979,15 +6979,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)
@@ -7000,52 +7001,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;
@@ -7055,10 +7055,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
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 6c9b62e41605..becb4c224e57 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7256,21 +7256,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
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 d91e66ea223f..6c9b62e41605 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7144,26 +7144,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) {
@@ -7186,6 +7175,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