* + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch
@ 2022-05-11 19:00 Andrew Morton
0 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2022-05-11 19:00 UTC (permalink / raw)
To: mm-commits, sfr, Liam.Howlett, liam.howlett, akpm
The patch titled
Subject: maple_tree: Fix expanding null off the end of the data.
has been added to the -mm mm-unstable branch. Its filename is
maple-tree-add-new-data-structure-fix.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: Fix expanding null off the end of the data.
When expanding a write of null to another null, the metadata for the end
of the node may be off by one. Fix this issue by setting the write end
pivot (wr_mas->end_piv) in mas_wr_extend_null(). Also use the saved value
for the end pivot during node stores instead of looking up the same entry
again.
There is also unnecessary code in mas_wr_extend_null() that can be
dropped.
Link: https://lkml.kernel.org/r/20220511144304.1430851-2-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Cc: Stephen Rothwell <sfr@canb.auug.org.au>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/maple_tree.c | 8 ++------
1 file changed, 2 insertions(+), 6 deletions(-)
--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix
+++ a/lib/maple_tree.c
@@ -3981,8 +3981,7 @@ static inline bool mas_wr_node_store(str
new_end++;
} else {
- if (mas_safe_pivot(mas, wr_mas->pivots, wr_mas->offset_end,
- wr_mas->type) == mas->last)
+ if (wr_mas->end_piv == mas->last)
wr_mas->offset_end++;
new_end -= wr_mas->offset_end - offset - 1;
@@ -4146,10 +4145,7 @@ static inline void mas_wr_extend_null(st
mas->last = mas->max;
else
mas->last = wr_mas->pivots[wr_mas->offset_end];
- } else if ((mas->last > wr_mas->end_piv) &&
- !wr_mas->slots[wr_mas->offset_end]) {
- mas->last = wr_mas->end_piv;
- wr_mas->offset_end++;
+ wr_mas->end_piv = mas->last;
}
if (!wr_mas->content) {
_
Patches currently in -mm which might be from liam.howlett@oracle.com are
maple-tree-add-new-data-structure-fix.patch
^ permalink raw reply [flat|nested] 5+ messages in thread
* + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch
@ 2022-08-24 18:17 Andrew Morton
0 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2022-08-24 18:17 UTC (permalink / raw)
To: mm-commits, Liam.Howlett, liam.howlett, akpm
The patch titled
Subject: maple_tree: fix documentation warnings
has been added to the -mm mm-unstable branch. Its filename is
maple-tree-add-new-data-structure-fix.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix documentation warnings
Date: Tue, 23 Aug 2022 15:22:59 +0000
Update the argument names in the documentation to match the functions
Link: https://lkml.kernel.org/r/20220823152212.1795380-1-Liam.Howlett@oracle.com
Fixes: 96ba2a9525fb (Maple Tree: add new data structure)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
include/linux/maple_tree.h | 20 ++++++++++----------
1 file changed, 10 insertions(+), 10 deletions(-)
--- a/include/linux/maple_tree.h~maple-tree-add-new-data-structure-fix
+++ a/include/linux/maple_tree.h
@@ -220,7 +220,7 @@ struct maple_tree {
/**
* MTREE_INIT() - Initialize a maple tree
* @name: The maple tree name
- * @flags: The maple tree flags
+ * @__flags: The maple tree flags
*
*/
#define MTREE_INIT(name, __flags) { \
@@ -232,8 +232,8 @@ struct maple_tree {
/**
* MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
* @name: The tree name
- * @flags: The maple tree flags
- * @lock: The external lock
+ * @__flags: The maple tree flags
+ * @__lock: The external lock
*/
#ifdef CONFIG_LOCKDEP
#define MTREE_INIT_EXT(name, __flags, __lock) { \
@@ -509,9 +509,9 @@ static inline void mas_reset(struct ma_s
/**
* mas_for_each() - Iterate over a range of the maple tree.
- * @mas: Maple Tree operation state (maple_state)
- * @entry: Entry retrieved from the tree
- * @max: maximum index to retrieve from the tree
+ * @__mas: Maple Tree operation state (maple_state)
+ * @__entry: Entry retrieved from the tree
+ * @__max: maximum index to retrieve from the tree
*
* When returned, mas->index and mas->last will hold the entire range for the
* entry.
@@ -646,10 +646,10 @@ void *mt_next(struct maple_tree *mt, uns
/**
* mt_for_each - Iterate over each entry starting at index until max.
- * @tree: The Maple Tree
- * @entry: The current entry
- * @index: The index to update to track the location in the tree
- * @max: The maximum limit for @index
+ * @__tree: The Maple Tree
+ * @__entry: The current entry
+ * @__index: The index to update to track the location in the tree
+ * @__max: The maximum limit for @index
*
* Note: Will not return the zero entry.
*/
_
Patches currently in -mm which might be from liam.howlett@oracle.com are
binder_alloc-add-missing-mmap_lock-calls-when-using-the-vma.patch
maple-tree-add-new-data-structure-fix.patch
mm-vmscan-use-vma-iterator-instead-of-vm_next.patch
^ permalink raw reply [flat|nested] 5+ messages in thread
* + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch
@ 2022-07-25 19:19 Andrew Morton
0 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2022-07-25 19:19 UTC (permalink / raw)
To: mm-commits, yuzhao, Liam.Howlett, liam.howlett, akpm
The patch titled
Subject: maple_tree: fix mas_expected_entries() off by one
has been added to the -mm mm-unstable branch. Its filename is
maple-tree-add-new-data-structure-fix.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix mas_expected_entries() off by one
Date: Fri, 22 Jul 2022 16:06:03 +0000
When inserting nodes, a final call to split the nodes will require a new
parent. Add this as the working area for mas_expected_entries().
Add a maple state flag which will WARN_ON() if there is insufficient
nodes allocated.
Export mas_is_err() to be used in checking mas_store() returns
externally.
Link: https://lkml.kernel.org/r/20220722160546.1478722-2-Liam.Howlett@oracle.com
Fixes: 06b152b7980a (Maple Tree: add new data structure)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
include/linux/maple_tree.h | 1 +
lib/maple_tree.c | 26 +++++++++++++++++++++-----
2 files changed, 22 insertions(+), 5 deletions(-)
--- a/include/linux/maple_tree.h~maple-tree-add-new-data-structure-fix
+++ a/include/linux/maple_tree.h
@@ -457,6 +457,7 @@ void mas_store_prealloc(struct ma_state
void *mas_find(struct ma_state *mas, unsigned long max);
void *mas_find_rev(struct ma_state *mas, unsigned long min);
int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);
+bool mas_is_err(struct ma_state *mas);
bool mas_nomem(struct ma_state *mas, gfp_t gfp);
void mas_pause(struct ma_state *mas);
--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix
+++ a/lib/maple_tree.c
@@ -64,9 +64,15 @@
#define MA_ROOT_PARENT 1
-/* Maple state flags */
+/*
+ * Maple state flags
+ * * MA_STATE_BULK - Bulk insert mode
+ * * MA_STATE_REBALANCE - Indicate a rebalance during bulk insert
+ * * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation
+ */
#define MA_STATE_BULK 1
#define MA_STATE_REBALANCE 2
+#define MA_STATE_PREALLOC 4
#define ma_parent_ptr(x) ((struct maple_pnode *)(x))
#define ma_mnode_ptr(x) ((struct maple_node *)(x))
@@ -243,7 +249,7 @@ static inline bool mas_is_start(struct m
return mas->node == MAS_START;
}
-static inline bool mas_is_err(struct ma_state *mas)
+bool mas_is_err(struct ma_state *mas)
{
return xa_is_err(mas->node);
}
@@ -1215,6 +1221,12 @@ static inline void mas_alloc_nodes(struc
return;
mas_set_alloc_req(mas, 0);
+ if (mas->mas_flags & MA_STATE_PREALLOC) {
+ if (allocated)
+ return;
+ WARN_ON(!allocated);
+ }
+
if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS - 1) {
node = (struct maple_alloc *)mt_alloc_one(gfp);
if (!node)
@@ -5694,6 +5706,7 @@ int mas_preallocate(struct ma_state *mas
int ret;
mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+ mas->mas_flags |= MA_STATE_PREALLOC;
if (likely(!mas_is_err(mas)))
return 0;
@@ -5743,7 +5756,6 @@ int mas_expected_entries(struct ma_state
* insertion of entries.
*/
nr_nodes = max(nr_entries, nr_entries * 2 + 1);
-
if (!mt_is_alloc(mas->tree))
nonleaf_cap = MAPLE_RANGE64_SLOTS - 2;
@@ -5751,7 +5763,11 @@ int mas_expected_entries(struct ma_state
nr_nodes = DIV_ROUND_UP(nr_nodes, MAPLE_RANGE64_SLOTS - 1);
/* Internal nodes */
nr_nodes += DIV_ROUND_UP(nr_nodes, nonleaf_cap);
- mas_node_count(mas, nr_nodes);
+ /* Add one for working room */
+ mas_node_count(mas, nr_nodes + 1);
+
+ /* Detect if allocations run out */
+ mas->mas_flags |= MA_STATE_PREALLOC;
if (!mas_is_err(mas))
return 0;
@@ -5793,7 +5809,7 @@ void mas_destroy(struct ma_state *mas)
mas->mas_flags &= ~MA_STATE_REBALANCE;
}
- mas->mas_flags &= ~MA_STATE_BULK;
+ mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC);
while (mas->alloc && !((unsigned long)mas->alloc & 0x1)) {
node = mas->alloc;
_
Patches currently in -mm which might be from liam.howlett@oracle.com are
android-binder-fix-lockdep-check-on-clearing-vma.patch
maple-tree-add-new-data-structure-fix.patch
mm-mlock-drop-dead-code-in-count_mm_mlocked_page_nr.patch
^ permalink raw reply [flat|nested] 5+ messages in thread
* + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch
@ 2022-07-19 19:03 Andrew Morton
0 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2022-07-19 19:03 UTC (permalink / raw)
To: mm-commits, Liam.Howlett, liam.howlett, akpm
The patch titled
Subject: maple_tree: fix bitwise for logical operator in mas_validate_limits()
has been added to the -mm mm-unstable branch. Its filename is
maple-tree-add-new-data-structure-fix.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix bitwise for logical operator in mas_validate_limits()
Date: Tue, 19 Jul 2022 18:51:57 +0000
Use the correct operator.
Link: https://lkml.kernel.org/r/20220719185142.3360559-1-Liam.Howlett@oracle.com
Fixes: fb7297e8a66b (Maple Tree: add new data structure)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/maple_tree.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix
+++ a/lib/maple_tree.c
@@ -6966,7 +6966,7 @@ static void mas_validate_limits(struct m
piv = mas_safe_pivot(mas, pivots, i, type);
- if (!piv & (i != 0))
+ if (!piv && (i != 0))
break;
if (!mte_is_leaf(mas->node)) {
_
Patches currently in -mm which might be from liam.howlett@oracle.com are
android-binder-fix-lockdep-check-on-clearing-vma.patch
maple-tree-add-new-data-structure-fix.patch
mm-mlock-drop-dead-code-in-count_mm_mlocked_page_nr.patch
^ permalink raw reply [flat|nested] 5+ messages in thread
* + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch
@ 2022-06-26 20:38 Andrew Morton
0 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2022-06-26 20:38 UTC (permalink / raw)
To: mm-commits, yuzhao, Liam.Howlett, liam.howlett, akpm
The patch titled
Subject: maple_tree: fix underflow in mas_spanning_rebalance()
has been added to the -mm mm-unstable branch. Its filename is
maple-tree-add-new-data-structure-fix.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple-tree-add-new-data-structure-fix.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Liam Howlett <liam.howlett@oracle.com>
Subject: maple_tree: fix underflow in mas_spanning_rebalance()
Date: Sat, 25 Jun 2022 00:39:06 +0000
When rebalancing a spanning store that spans the entire address space,
the big node end is not expanded the extra position that
mas_spanning_rebalance() expects. Fix this by expanding on such cases.
Also change mab_mas_cp() from assuming there are at least two entries to
ensure the correct metadata is written.
Link: https://lkml.kernel.org/r/20220625003854.1230114-2-Liam.Howlett@oracle.com
Fixes: f8acc5e9581e (Maple Tree: add new data structure)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/maple_tree.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
--- a/lib/maple_tree.c~maple-tree-add-new-data-structure-fix
+++ a/lib/maple_tree.c
@@ -1977,7 +1977,6 @@ static inline void mab_mas_cp(struct map
slots[mt_pivots[mt]] = NULL;
i = mab_start;
- pivots[j++] = b_node->pivot[i++];
do {
pivots[j++] = b_node->pivot[i++];
} while (i <= mab_end && likely(b_node->pivot[i]));
@@ -2970,7 +2969,7 @@ static int mas_spanning_rebalance(struct
mast->free = &free;
mast->destroy = &destroy;
l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
- if (!mas_is_root_limits(mast->orig_l) &&
+ if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) &&
unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
mast_spanning_rebalance(mast);
@@ -4004,6 +4003,9 @@ static inline int mas_wr_spanning_store(
if (r_mas.offset <= r_wr_mas.node_end)
mas_mab_cp(&r_mas, r_mas.offset, r_wr_mas.node_end,
&b_node, b_node.b_end + 1);
+ else
+ b_node.b_end++;
+
/* Stop spanning searches by searching for just index. */
l_mas.index = l_mas.last = mas->index;
_
Patches currently in -mm which might be from liam.howlett@oracle.com are
maple-tree-add-new-data-structure-fix.patch
mm-mlock-drop-dead-code-in-count_mm_mlocked_page_nr.patch
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2022-08-24 18:17 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-11 19:00 + maple-tree-add-new-data-structure-fix.patch added to mm-unstable branch Andrew Morton
2022-06-26 20:38 Andrew Morton
2022-07-19 19:03 Andrew Morton
2022-07-25 19:19 Andrew Morton
2022-08-24 18:17 Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.