Re: [PATCH] mm/sparsemem: fix race in accessing memory_section->usage

Re: [PATCH] mm/sparsemem: fix race in accessing memory_section->usage

[Marco Elver]

On Mon, Jan 15, 2024 at 09:34PM +0100, Marco Elver wrote:
> On Mon, 15 Jan 2024 at 19:44, Alexander Potapenko <glider@google.com> wrote:
> >
> > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > Cc: Marco Elver <elver@google.com>
> > Cc: Dmitry Vyukov <dvyukov@google.com>
> > Cc: kasan-dev@googlegroups.com
> > Cc: Ilya Leoshkevich <iii@linux.ibm.com>
> > Cc: Nicholas Miehlbradt <nicholas@linux.ibm.com>
> >
> > Hi folks,
> >
> > (adding KMSAN reviewers and IBM people who are currently porting KMSAN to other
> > architectures, plus Paul for his opinion on refactoring RCU)
> >
> > this patch broke x86 KMSAN in a subtle way.
> >
> > For every memory access in the code instrumented by KMSAN we call
> > kmsan_get_metadata() to obtain the metadata for the memory being accessed. For
> > virtual memory the metadata pointers are stored in the corresponding `struct
> > page`, therefore we need to call virt_to_page() to get them.
> >
> > According to the comment in arch/x86/include/asm/page.h, virt_to_page(kaddr)
> > returns a valid pointer iff virt_addr_valid(kaddr) is true, so KMSAN needs to
> > call virt_addr_valid() as well.
> >
> > To avoid recursion, kmsan_get_metadata() must not call instrumented code,
> > therefore ./arch/x86/include/asm/kmsan.h forks parts of arch/x86/mm/physaddr.c
> > to check whether a virtual address is valid or not.
> >
> > But the introduction of rcu_read_lock() to pfn_valid() added instrumented RCU
> > API calls to virt_to_page_or_null(), which is called by kmsan_get_metadata(),
> > so there is an infinite recursion now. I do not think it is correct to stop that
> > recursion by doing kmsan_enter_runtime()/kmsan_exit_runtime() in
> > kmsan_get_metadata(): that would prevent instrumented functions called from
> > within the runtime from tracking the shadow values, which might introduce false
> > positives.
> >
> > I am currently looking into inlining __rcu_read_lock()/__rcu_read_unlock(), into
> > KMSAN code to prevent it from being instrumented, but that might require factoring
> > out parts of kernel/rcu/tree_plugin.h into a non-private header. Do you think this
> > is feasible?
> 
> __rcu_read_lock/unlock() is only outlined in PREEMPT_RCU. Not sure that helps.
> 
> Otherwise, there is rcu_read_lock_sched_notrace() which does the bare
> minimum and is static inline.
> 
> Does that help?

Hrm, rcu_read_unlock_sched_notrace() can still call
__preempt_schedule_notrace(), which is again instrumented by KMSAN.

This patch gets me a working kernel:

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 4ed33b127821..2d62df462d88 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -2000,6 +2000,7 @@ static inline int pfn_valid(unsigned long pfn)
 {
 	struct mem_section *ms;
 	int ret;
+	unsigned long flags;
 
 	/*
 	 * Ensure the upper PAGE_SHIFT bits are clear in the
@@ -2013,9 +2014,9 @@ static inline int pfn_valid(unsigned long pfn)
 	if (pfn_to_section_nr(pfn) >= NR_MEM_SECTIONS)
 		return 0;
 	ms = __pfn_to_section(pfn);
-	rcu_read_lock();
+	local_irq_save(flags);
 	if (!valid_section(ms)) {
-		rcu_read_unlock();
+		local_irq_restore(flags);
 		return 0;
 	}
 	/*
@@ -2023,7 +2024,7 @@ static inline int pfn_valid(unsigned long pfn)
 	 * the entire section-sized span.
 	 */
 	ret = early_section(ms) || pfn_section_valid(ms, pfn);
-	rcu_read_unlock();
+	local_irq_restore(flags);
 
 	return ret;
 }

Disabling interrupts is a little heavy handed - it also assumes the
current RCU implementation. There is
preempt_enable_no_resched_notrace(), but that might be worse because it
breaks scheduling guarantees.

That being said, whatever we do here should be wrapped in some
rcu_read_lock/unlock_<newvariant>() helper.

Is there an existing helper we can use? If not, we need a variant that
can be used from extremely constrained contexts that can't even call
into the scheduler. And if we want pfn_valid() to switch to it, it also
should be fast.

Thanks,
-- Marco

Re: [PATCH] mm/sparsemem: fix race in accessing memory_section->usage

[Alexander Potapenko]

>
> Hrm, rcu_read_unlock_sched_notrace() can still call
> __preempt_schedule_notrace(), which is again instrumented by KMSAN.
>
> This patch gets me a working kernel:
>
> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> index 4ed33b127821..2d62df462d88 100644
> --- a/include/linux/mmzone.h
> +++ b/include/linux/mmzone.h
> @@ -2000,6 +2000,7 @@ static inline int pfn_valid(unsigned long pfn)
>  {
>         struct mem_section *ms;
>         int ret;
> +       unsigned long flags;
>
>         /*
>          * Ensure the upper PAGE_SHIFT bits are clear in the
> @@ -2013,9 +2014,9 @@ static inline int pfn_valid(unsigned long pfn)
>         if (pfn_to_section_nr(pfn) >= NR_MEM_SECTIONS)
>                 return 0;
>         ms = __pfn_to_section(pfn);
> -       rcu_read_lock();
> +       local_irq_save(flags);
>         if (!valid_section(ms)) {
> -               rcu_read_unlock();
> +               local_irq_restore(flags);
>                 return 0;
>         }
>         /*
> @@ -2023,7 +2024,7 @@ static inline int pfn_valid(unsigned long pfn)
>          * the entire section-sized span.
>          */
>         ret = early_section(ms) || pfn_section_valid(ms, pfn);
> -       rcu_read_unlock();
> +       local_irq_restore(flags);
>
>         return ret;
>  }
>
> Disabling interrupts is a little heavy handed - it also assumes the
> current RCU implementation. There is
> preempt_enable_no_resched_notrace(), but that might be worse because it
> breaks scheduling guarantees.
>
> That being said, whatever we do here should be wrapped in some
> rcu_read_lock/unlock_<newvariant>() helper.

We could as well redefine rcu_read_lock/unlock in mm/kmsan/shadow.c
(or the x86-specific KMSAN header, depending on whether people are
seeing the problem on s390 and Power) with some header magic.
But that's probably more fragile than adding a helper.

>
> Is there an existing helper we can use? If not, we need a variant that
> can be used from extremely constrained contexts that can't even call
> into the scheduler. And if we want pfn_valid() to switch to it, it also
> should be fast.

Re: [PATCH] mm/sparsemem: fix race in accessing memory_section->usage

[Marco Elver]

On Thu, Jan 18, 2024 at 10:01AM +0100, Alexander Potapenko wrote:
> >
> > Hrm, rcu_read_unlock_sched_notrace() can still call
> > __preempt_schedule_notrace(), which is again instrumented by KMSAN.
> >
> > This patch gets me a working kernel:
> >
[...]
> > Disabling interrupts is a little heavy handed - it also assumes the
> > current RCU implementation. There is
> > preempt_enable_no_resched_notrace(), but that might be worse because it
> > breaks scheduling guarantees.
> >
> > That being said, whatever we do here should be wrapped in some
> > rcu_read_lock/unlock_<newvariant>() helper.
> 
> We could as well redefine rcu_read_lock/unlock in mm/kmsan/shadow.c
> (or the x86-specific KMSAN header, depending on whether people are
> seeing the problem on s390 and Power) with some header magic.
> But that's probably more fragile than adding a helper.
> 
> >
> > Is there an existing helper we can use? If not, we need a variant that
> > can be used from extremely constrained contexts that can't even call
> > into the scheduler. And if we want pfn_valid() to switch to it, it also
> > should be fast.

The below patch also gets me a working kernel. For pfn_valid(), using
rcu_read_lock_sched() should be reasonable, given its critical section
is very small and also enables it to be called from more constrained
contexts again (like KMSAN).

Within KMSAN we also have to suppress reschedules. This is again not
ideal, but since it's limited to KMSAN should be tolerable.

WDYT?

------ >8 ------

diff --git a/arch/x86/include/asm/kmsan.h b/arch/x86/include/asm/kmsan.h
index 8fa6ac0e2d76..bbb1ba102129 100644
--- a/arch/x86/include/asm/kmsan.h
+++ b/arch/x86/include/asm/kmsan.h
@@ -64,6 +64,7 @@ static inline bool kmsan_virt_addr_valid(void *addr)
 {
 	unsigned long x = (unsigned long)addr;
 	unsigned long y = x - __START_KERNEL_map;
+	bool ret;
 
 	/* use the carry flag to determine if x was < __START_KERNEL_map */
 	if (unlikely(x > y)) {
@@ -79,7 +80,21 @@ static inline bool kmsan_virt_addr_valid(void *addr)
 			return false;
 	}
 
-	return pfn_valid(x >> PAGE_SHIFT);
+	/*
+	 * pfn_valid() relies on RCU, and may call into the scheduler on exiting
+	 * the critical section. However, this would result in recursion with
+	 * KMSAN. Therefore, disable preemption here, and re-enable preemption
+	 * below while suppressing rescheduls to avoid recursion.
+	 *
+	 * Note, this sacrifices occasionally breaking scheduling guarantees.
+	 * Although, a kernel compiled with KMSAN has already given up on any
+	 * performance guarantees due to being heavily instrumented.
+	 */
+	preempt_disable();
+	ret = pfn_valid(x >> PAGE_SHIFT);
+	preempt_enable_no_resched();
+
+	return ret;
 }
 
 #endif /* !MODULE */
diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 4ed33b127821..a497f189d988 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -2013,9 +2013,9 @@ static inline int pfn_valid(unsigned long pfn)
 	if (pfn_to_section_nr(pfn) >= NR_MEM_SECTIONS)
 		return 0;
 	ms = __pfn_to_section(pfn);
-	rcu_read_lock();
+	rcu_read_lock_sched();
 	if (!valid_section(ms)) {
-		rcu_read_unlock();
+		rcu_read_unlock_sched();
 		return 0;
 	}
 	/*
@@ -2023,7 +2023,7 @@ static inline int pfn_valid(unsigned long pfn)
 	 * the entire section-sized span.
 	 */
 	ret = early_section(ms) || pfn_section_valid(ms, pfn);
-	rcu_read_unlock();
+	rcu_read_unlock_sched();
 
 	return ret;
 }

Re: [PATCH] mm/sparsemem: fix race in accessing memory_section->usage

[Paul E. McKenney]

On Thu, Jan 18, 2024 at 10:43:06AM +0100, Marco Elver wrote:
> On Thu, Jan 18, 2024 at 10:01AM +0100, Alexander Potapenko wrote:
> > >
> > > Hrm, rcu_read_unlock_sched_notrace() can still call
> > > __preempt_schedule_notrace(), which is again instrumented by KMSAN.
> > >
> > > This patch gets me a working kernel:
> > >
> [...]
> > > Disabling interrupts is a little heavy handed - it also assumes the
> > > current RCU implementation. There is
> > > preempt_enable_no_resched_notrace(), but that might be worse because it
> > > breaks scheduling guarantees.
> > >
> > > That being said, whatever we do here should be wrapped in some
> > > rcu_read_lock/unlock_<newvariant>() helper.
> > 
> > We could as well redefine rcu_read_lock/unlock in mm/kmsan/shadow.c
> > (or the x86-specific KMSAN header, depending on whether people are
> > seeing the problem on s390 and Power) with some header magic.
> > But that's probably more fragile than adding a helper.
> > 
> > >
> > > Is there an existing helper we can use? If not, we need a variant that
> > > can be used from extremely constrained contexts that can't even call
> > > into the scheduler. And if we want pfn_valid() to switch to it, it also
> > > should be fast.
> 
> The below patch also gets me a working kernel. For pfn_valid(), using
> rcu_read_lock_sched() should be reasonable, given its critical section
> is very small and also enables it to be called from more constrained
> contexts again (like KMSAN).
> 
> Within KMSAN we also have to suppress reschedules. This is again not
> ideal, but since it's limited to KMSAN should be tolerable.
> 
> WDYT?

I like this one better from a purely selfish RCU perspective.  ;-)

							Thanx, Paul

> ------ >8 ------
> 
> diff --git a/arch/x86/include/asm/kmsan.h b/arch/x86/include/asm/kmsan.h
> index 8fa6ac0e2d76..bbb1ba102129 100644
> --- a/arch/x86/include/asm/kmsan.h
> +++ b/arch/x86/include/asm/kmsan.h
> @@ -64,6 +64,7 @@ static inline bool kmsan_virt_addr_valid(void *addr)
>  {
>  	unsigned long x = (unsigned long)addr;
>  	unsigned long y = x - __START_KERNEL_map;
> +	bool ret;
>  
>  	/* use the carry flag to determine if x was < __START_KERNEL_map */
>  	if (unlikely(x > y)) {
> @@ -79,7 +80,21 @@ static inline bool kmsan_virt_addr_valid(void *addr)
>  			return false;
>  	}
>  
> -	return pfn_valid(x >> PAGE_SHIFT);
> +	/*
> +	 * pfn_valid() relies on RCU, and may call into the scheduler on exiting
> +	 * the critical section. However, this would result in recursion with
> +	 * KMSAN. Therefore, disable preemption here, and re-enable preemption
> +	 * below while suppressing rescheduls to avoid recursion.
> +	 *
> +	 * Note, this sacrifices occasionally breaking scheduling guarantees.
> +	 * Although, a kernel compiled with KMSAN has already given up on any
> +	 * performance guarantees due to being heavily instrumented.
> +	 */
> +	preempt_disable();
> +	ret = pfn_valid(x >> PAGE_SHIFT);
> +	preempt_enable_no_resched();
> +
> +	return ret;
>  }
>  
>  #endif /* !MODULE */
> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> index 4ed33b127821..a497f189d988 100644
> --- a/include/linux/mmzone.h
> +++ b/include/linux/mmzone.h
> @@ -2013,9 +2013,9 @@ static inline int pfn_valid(unsigned long pfn)
>  	if (pfn_to_section_nr(pfn) >= NR_MEM_SECTIONS)
>  		return 0;
>  	ms = __pfn_to_section(pfn);
> -	rcu_read_lock();
> +	rcu_read_lock_sched();
>  	if (!valid_section(ms)) {
> -		rcu_read_unlock();
> +		rcu_read_unlock_sched();
>  		return 0;
>  	}
>  	/*
> @@ -2023,7 +2023,7 @@ static inline int pfn_valid(unsigned long pfn)
>  	 * the entire section-sized span.
>  	 */
>  	ret = early_section(ms) || pfn_section_valid(ms, pfn);
> -	rcu_read_unlock();
> +	rcu_read_unlock_sched();
>  
>  	return ret;
>  }