Re: [PATCH] maple_tree: Fix sparse reported issues
From: Liam Howlett
Date: Sun Jul 17 2022 - 22:28:15 EST
* Hugh Dickins <hughd@xxxxxxxxxx> [220717 16:58]:
> On Fri, 15 Jul 2022, Liam Howlett wrote:
> > * Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> [220713 13:50]:
> > > * Hugh Dickins <hughd@xxxxxxxxxx> [220713 11:56]:
> > > > On Wed, 13 Jul 2022, Liam Howlett wrote:
> > > > > * David Hildenbrand <david@xxxxxxxxxx> [220713 04:34]:
> > > > > > On 12.07.22 16:24, Liam Howlett wrote:
> > > > > > > When building with C=1, the maple tree had some rcu type mismatch &
> > > > > > > locking mismatches in the destroy functions. There were cosmetic only
> > > > > > > since this happens after the nodes are removed from the tree.
> > > > > > >
> > > > > > > Fixes: f8acc5e9581e (Maple Tree: add new data structure)
> > > > > > > Reported-by: kernel test robot <lkp@xxxxxxxxx>
> > > > > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> > > > > >
> > > > > > Sorry to say, but the fixes become hard to follow (what/where/why). :)
> > > > > >
> > > > > > I guess it's time for a new series soon. Eventually it makes sense to
> > > > > > send the fixes as reply to the individual problematic patches. (instead
> > > > > > of fixes to commit ids that are not upstream)
> > > > > >
> > > > > > [yes, I'll do more review soon :) ]
> > > > >
> > > > > I appreciate the feedback, it's much better than yelling into the void.
> > > > > I have one more fix in the works - for __vma_adjust() of all functions
> > > > > so that'll be impossible to follow anyways :) I'll work on a v11 to
> > > > > include that last one.
> > > >
> > > > Please do also post the incremental for that "one more fix" once it's
> > > > ready: I have been keeping up with what you've been posting so far,
> > > > folding them into my debugging here, and believe we have made some but
> > > > still not enough progress on the bugs I hit. Folding in one more fix
> > > > will be easy for me, advancing to v11 of a 69-part patchset will be...
> > > > dispiriting.
> > >
> > >
> > > Okay, thanks. I don't think it will fix your outstanding issues but it
> > > is necessary to fix case 6 of vma_merge() on memory allocation failure
> > > as reported by syzbot.
> >
> > Hugh,
> >
> > Please find attached the last outstanding fix for this series. It
> > covers a rare failure scenario that one of the build bots reported.
> > Ironically, it changes __vma_adjust() more than the rest of the series,
> > but leaves the locking in the existing order.
>
> Thanks, I folded that in to my testing on next-20220715, along with
> other you posted on Friday (mas_dead_leaves() walk fix);
Please drop that patch, it needs more testing.
> but have not
> even glanced at the v11 you posted Saturday, though I see from responses
> that v11 has some other changes, including __vma_adjust() again, but I
> just have not looked. (I've had my own experiments in __vma_adjust()).
>
> You'll be wanting my report, I'll give it here rather than in the v11
> thread. In short, some progress, but still frustratingly none on the
> main crashes.
>
> 1. swapops.h BUG on !PageLocked migration entry. This is *not* the
> most urgent to fix, I'm just listing it first to get it out of the way
> here. This is the BUG that terminates every tmpfs swapping load test
> on the laptop: only progress was that, just one time, the workstation
> hit it before hitting its usual problems: nice to see it there too.
> I'll worry about this bug when the rest is running stably. I've only
> ever noticed it when it's brk being unmapped, I expect that's a clue.
Thanks for pointing me towards a usable reproducer. I should be able to
narrow it down from there, especially with the brk hint.
>
> 2. Silly in do_mas_mumap():
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2513,7 +2513,7 @@ int do_mas_munmap(struct ma_state *mas, struct mm_struct *mm,
> arch_unmap(mm, start, end);
>
> /* Find the first overlapping VMA */
> - vma = mas_find(mas, end - 1);
> + vma = mas_find(mas, start);
> if (!vma)
> return 0;
>
> Fixing that does fix some bad behaviors seen - I'd been having crashes in
> unmap_vmas() and unlink_anon_vmas(), and put "if (WARN_ON(!vma)) return;"
> in unmap_region(); but that no longer seems necessary now do_mas_munmap()
> is fixed thus. I had high hopes that it would fix all the rest, but no.
This is actually correct. mas_find() is not the same as vma_find().
mas_find() uses the maple state index and searches until a limit (end
-1 in this case). I haven't seen these crashes, but I think you are
hitting the same issue you are discussing in #6 below. I also hadn't
realised the potential confusion of those APIs.
>
> 3. vma_adjust_trans_huge(). Skip this paragraph, I think there
> is actually no problem here, but for safety I have rearranged the
> vma_adjust_trans_huge()s inside the rmap locks, because when things
> aren't working right, best to rule out some possibilities. Why am
> I even mentioning it here? In case I send any code snippets and
> you're puzzled by vma_adjust_trans_huge() having moved.
Thanks, I will keep this in mind.
>
> 4. unlink_anon_vmas() in __vma_adjust(). Not urgent to fix (can only
> be an issue when GFP_KERNEL preallocation fails, which I think means
> when current is being OOM-killed), but whereas vma_expand() has careful
> anon_cloned flag, __vma_adjust() does not, and I think could be
> unlinking a pre-existing anon_vma. Aside from that, I am nervous about
> using unlink_anon_vmas() there like that (and in vma_expand()): IIUC it's
> an unnecessary "optimization" for a very unlikely case, that's in danger
> of doing more harm than good; and should be removed from them both (then
> they can both simply return -ENOMEM when mas_preallocate() fails).
I will add a flag to __vma_adjust, but I don't see how it could happen.
I guess if importer has an anon_vma already? I added these as an unwind
since I don't want to leak - even on the rare preallocation failure. If
you don't want to unroll, what would you suggest in these cases? Would
a flag be acceptable?
>
> 5. I was horrified/thrilled to notice last night that mas_store_prealloc()
> does a mas_destroy() at the end. So only the first vma_mas_store() in
> __vma_adjust() gets to use the carefully preallocated nodes. I thought
> that might be responsible for lots of nastiness, but again sadly no.
> Maybe it just falls back to GFP_ATOMIC when the preallocateds are gone
> (I didn't look) and that often works okay. Whether the carefully
> chosen prealloc count allows for __vma_adjust() use would be another
> question. (Earlier on I did try doubling its calculation, in case it
> was preallocating too few, but that made no difference either.)
mas_store_prealloc will allocate for the worst case scenario. Since I
cannot guarantee the second store isn't the worst case, and could fail,
I cannot allow for more than one allocation per preallocate. I thought
I was fine in __vma_adjust since I preallocate after the goto label for
a second removal but it turns out I wasn't since the second preallocate
could fail, so I've removed the requirement for a second store for 'case
6' by updating the tree once and removing both VMAs in a single pass.
There could, potentially be an issue if the caller to __vma_merge()
wanted to reduce one limit of the VMA (I guess just the start..) and
also remove one or more VMAs, and also be in a situation where
allocations could cause issues (fs_reclaim).. and since __vma_adjust()
is so complicated, I looked at the callers. Most use vma_merge(), and
those seem fine. fs/exec only adjusts one at a time. when splitting,
only a single insert happens. Did I miss some situation(s)?
>
> 6. The main problem, crashes on the workstation (never seen on the
> laptop). I keep hacking around with the debug info (and, please,
> %px not %p, %lx not %lu in the debug info: I've changed them all,
Okay, so I tried to remove all %px in the debug code so I'll revert
those. I use %lu for historic reasons from mt_dump(), I can change
those too, The tree uses ranges to store pointers so I print the
pointers in %lx and the ranges in %lu.
> and a couple of %lds, in my copy of lib/maple_tree.c). I forget
> how the typical crashes appeared with the MAPLE_DEBUGs turned off
> (the BUG_ON(count != mm->map_count) in exit_mmap() perhaps); I've
> turned them on, but usually comment out the mt_validate() and
> mt_dump(), which generate far too much noise for non-specialists,
> and delay the onset of crash tenfold (but re-enabled to give you
> the attached messages.xz).
>
> Every time, it's the cc1 (9.3.1) doing some munmapping (cc1 is
> mostly what's running in this load test, so that's not surprising;
> but surprising that even when I switched the laptop to using same
> gcc-9, couldn't reproduce the problem there). Typically, that
> munmapping has involved splitting a small, say three page, vma
> into two pages below and one page above (the "insert", and I've
> hacked the debug to dump that too, see "mmap: insert" - ah,
> looking at the messages now, the insert is bigger this time).
>
> And what has happened each time I've studied it (I don't know
> if this is evident from the mt dumps in the messages, I hope so)
> is that the vma and the insert have been correctly placed in the
> tree, except that the vma has *also* been placed several pages
> earlier, and a linear search of the tree finds that misplaced
> instance first, vm_start not matching mt index.
>
> The map_count in these cases has always been around 59, 60, 61:
> maybe just typical for cc1, or maybe significant for maple tree?
>
> I won't give up quite yet, but I'm hoping you'll have an idea for
> the misplaced tree entry. Something going wrong in rebalancing?
>
> For a long time I assumed the problem would be at the mm/mmap.c end,
> and I've repeatedly tried different things with the vma_mas stuff
> in __vma_adjust() (for example, using vma_mas_remove() to remove
> vmas before re-adding them, and/or doing mas_reset() in more places);
> but none of those attempts actually fixed the issue. So now I'm
> thinking the problem is really at the lib/maple_tree.c end.
>
Do you have the patch
"maple_tree-Fix-stale-data-copy-in-mas_wr_node_store.patch"? It sounds
like your issue fits this fix exactly. I was seeing the same issue with
gcc 9.3.1 20200408 and this bug doesn't happen for me now. The logs
you sent also fit the situation. I went through the same exercise
(exorcism?) of debugging the various additions and removals of the VMA
only to find the issue in the tree itself. The fix also modified the
test code to detect the issue - which was actually hit but not detected
in the existing test cases from a live capture of VMA activities. It is
difficult to spot in the tree dump as well. I am sure I sent this to
Andrew as it is included in v11 and did not show up in his diff, but I
cannot find it on lore, perhaps I forgot to CC you? I've attached it
here for you in case you missed it.
You are actually hitting the issue several iterations beyond when it
first occurred. It was introduced earlier in the tree and exposed with
your other operations by means of a node split or merge.
> 7. If you get to do cleanups later, please shrink those double blank
> lines to single blank lines. And find a better name for the strange
> vma_mas_szero() - vma_mas_erase(), or is erase something different?
> I'm not even sure that it's needed: that's a special case for exec's
> shift_arg_pages() VM_STACK_INCOMPLETE_SETUP, which uses __vma_adjust()
> in a non-standard way. And trace_vma_mas_szero() in vma_mas_remove()
> looks wrong.
Okay, I'll be sure to only have one blank line. Where do you see this?
I would have thought that checkpatch would complain? I did try to,
regretfully, address more checkpatch issues on v11. It added more noise
to the differences of v10 + patches to v11 than anything else.
Thanks again,
Liam
From e5da10161a15bb59ee22de9c78fec3881fe455b3 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@xxxxxxxxxx>
Date: Fri, 15 Jul 2022 15:10:45 -0400
Subject: [PATCH] maple_tree: Fix stale data copy in mas_wr_node_store()
When replacing or reusing a node, it is possible that stale data would
be copied into the new node when a store operation wrote to the node
maximum value but into lower slots. Fix this by skipping the copy step
if the range being written is the node maximum, and skip setting the
end pivot in this case as well.
Reported-by: syzbot+b707736a1ad47fda6500@xxxxxxxxxxxxxxxxxxxxxxxxx
Fixes: 2ee236fe53a8 ("mm: start tracking VMAs with maple tree")
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
---
lib/maple_tree.c | 56 +++++++++++++++++++++++++++++++++++++-----------
1 file changed, 43 insertions(+), 13 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index cf6d062eca09..0da2671c2810 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4120,12 +4120,18 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
if (dst_offset < max_piv)
dst_pivots[dst_offset] = mas->last;
mas->offset = dst_offset;
- rcu_assign_pointer(dst_slots[dst_offset++], wr_mas->entry);
+ rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
- /* this range wrote to the end of the node. */
- if (wr_mas->offset_end > wr_mas->node_end)
+ /*
+ * this range wrote to the end of the node or it overwrote the rest of
+ * the data
+ */
+ if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
+ new_end = dst_offset;
goto done;
+ }
+ dst_offset++;
/* Copy to the end of node if necessary. */
copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
@@ -4133,14 +4139,16 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
if (dst_offset < max_piv) {
if (copy_size > max_piv - dst_offset)
copy_size = max_piv - dst_offset;
- memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
+
+ memcpy(dst_pivots + dst_offset,
+ wr_mas->pivots + wr_mas->offset_end,
sizeof(unsigned long) * copy_size);
}
-done:
if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
dst_pivots[new_end] = mas->max;
+done:
mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end);
if (in_rcu) {
mas->node = mt_mk_node(newnode, wr_mas->type);
@@ -6945,19 +6953,20 @@ static void mas_validate_limits(struct ma_state *mas)
{
int i;
unsigned long prev_piv = 0;
- void __rcu **slots = ma_slots(mte_to_node(mas->node),
- mte_node_type(mas->node));
+ enum maple_type type = mte_node_type(mas->node);
+ 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_slot_count(mas->node); i++) {
- enum maple_type type = mte_node_type(mas->node);
- unsigned long *pivots = ma_pivots(mas_mn(mas), type);
- unsigned long piv = mas_safe_pivot(mas, pivots, type, i);
+ for (i = 0; i < mt_slots[type]; i++) {
+ unsigned long piv;
+
+ piv = mas_safe_pivot(mas, pivots, i, type);
- if (!piv)
+ if (!piv & (i != 0))
break;
if (!mte_is_leaf(mas->node)) {
@@ -6990,6 +6999,26 @@ static void mas_validate_limits(struct ma_state *mas)
if (piv == mas->max)
break;
}
+ for (i += 1; i < mt_slots[type]; i++) {
+ void *entry = mas_slot(mas, slots, i);
+
+ if (entry && (i != mt_slots[type] - 1)) {
+ pr_err("%p[%u] should not have entry %p\n", mas_mn(mas),
+ i, entry);
+ MT_BUG_ON(mas->tree, entry != NULL);
+ }
+
+ if (i < mt_pivots[type]) {
+ unsigned long piv = pivots[i];
+
+ if (!piv)
+ continue;
+
+ pr_err("%p[%u] should not have piv %lu\n",
+ mas_mn(mas), i, piv);
+ MT_BUG_ON(mas->tree, i < mt_pivots[type] - 1);
+ }
+ }
}
static void mt_validate_nulls(struct maple_tree *mt)
@@ -7022,8 +7051,9 @@ static void mt_validate_nulls(struct maple_tree *mt)
offset = 0;
slots = ma_slots(mte_to_node(mas.node),
mte_node_type(mas.node));
- } else
+ } else {
offset++;
+ }
} while (!mas_is_none(&mas));
}
--
2.35.1