[PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

From: Steven Rostedt (VMware) <rostedt@goodmis.org>

Reviewing Tobin's patches for getting pointers out early before
entropy has been established, I noticed that there's a lone smp_mb() in
the code. As with most lone memory barriers, this one appears to be
incorrectly used.

We currently basically have this:

	get_random_bytes(&ptr_key, sizeof(ptr_key));
	/*
	 * have_filled_random_ptr_key==true is dependent on get_random_bytes().
	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
	 * after get_random_bytes() returns.
	 */
	smp_mb();
	WRITE_ONCE(have_filled_random_ptr_key, true);

And later we have:

	if (unlikely(!have_filled_random_ptr_key))
		return string(buf, end, "(ptrval)", spec);

/* Missing memory barrier here. */

	hashval = (unsigned long)siphash_1u64((u64)ptr, &ptr_key);

As the CPU can perform speculative loads, we could have a situation
with the following:

	CPU0				CPU1
	----				----
				   load ptr_key = 0
   store ptr_key = random
   smp_mb()
   store have_filled_random_ptr_key

				   load have_filled_random_ptr_key = true

				    BAD BAD BAD!

Because nothing prevents CPU1 from loading ptr_key before loading
have_filled_random_ptr_key.

Note, I also do not see the reason to use smp_mb() instead of smp_wmb()
since we are only worried about the store of ptr_key with respect to
the store of have_filled_random_ptr_key.

Cc: stable@vger.kernel.org
Fixes: ad67b74d2469d ("printk: hash addresses printed with %p")
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..e8a0b8e54bd3 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1680,7 +1680,7 @@ static void fill_random_ptr_key(struct random_ready_callback *unused)
 	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
 	 * after get_random_bytes() returns.
 	 */
-	smp_mb();
+	smp_wmb();
 	WRITE_ONCE(have_filled_random_ptr_key, true);
 }
 
@@ -1715,6 +1715,9 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
 		return string(buf, end, "(ptrval)", spec);
 	}
 
+	/* Read ptr_key after reading have_filled_random_ptr_key */
+	smp_rmb();
+
 #ifdef CONFIG_64BIT
 	hashval = (unsigned long)siphash_1u64((u64)ptr, &ptr_key);
 	/*

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Linus Torvalds]

On Tue, May 15, 2018 at 7:06 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> -       smp_mb();
> +       smp_wmb();
>          WRITE_ONCE(have_filled_random_ptr_key, true);


> +       /* Read ptr_key after reading have_filled_random_ptr_key */
> +       smp_rmb();
> +
>   #ifdef CONFIG_64BIT
>          hashval = (unsigned long)siphash_1u64((u64)ptr, &ptr_key);

Hmm. smp_wmb/rmb are basically free on x86, but on some architectures
smp_rmb() in particular can be pretty expensive.

So when you have a "handoff" situation like this, it's _probably_ better to
use use "smp_store_release()" and "smp_load_acquire()". To some degree that
might also be better for documentation purposes, because that's exactly the
"release-acquire" pattern.

That said, I'm not convinced this really matters all that much for a
boot-time flag like this. The race is pretty theoretical.

                    Linus

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

On Tue, 15 May 2018 09:55:13 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Tue, May 15, 2018 at 7:06 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> > -       smp_mb();
> > +       smp_wmb();
> >          WRITE_ONCE(have_filled_random_ptr_key, true);  
> 
> 
> > +       /* Read ptr_key after reading have_filled_random_ptr_key */
> > +       smp_rmb();
> > +
> >   #ifdef CONFIG_64BIT
> >          hashval = (unsigned long)siphash_1u64((u64)ptr, &ptr_key);  
> 
> Hmm. smp_wmb/rmb are basically free on x86, but on some architectures
> smp_rmb() in particular can be pretty expensive.
> 
> So when you have a "handoff" situation like this, it's _probably_ better to
> use use "smp_store_release()" and "smp_load_acquire()". To some degree that
> might also be better for documentation purposes, because that's exactly the
> "release-acquire" pattern.
> 
> That said, I'm not convinced this really matters all that much for a
> boot-time flag like this. The race is pretty theoretical.
>

I was thinking the same. But since the smp_mb() is there, then it
should be correct, which it currently isn't.

We could change this to a static key, and enable it after we set up
the ptr_key. That would be a one time change at boot up, wont have
races, and have no overhead.

-- Steve

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..da4ea056a309 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1669,19 +1669,21 @@ char *pointer_string(char *buf, char *end, const void *ptr,
 	return number(buf, end, (unsigned long int)ptr, spec);
 }
 
-static bool have_filled_random_ptr_key __read_mostly;
+static DEFINE_STATIC_KEY_TRUE(not_filled_random_ptr_key);
 static siphash_key_t ptr_key __read_mostly;
 
+static void enable_ptr_key_workfn(struct work_struct *work)
+{
+	/* Needs to run from preemptable context */
+	static_branch_disable(&not_filled_random_ptr_key);
+}
+
+static DECLARE_WORK(enable_ptr_key_work, enable_ptr_key_workfn);
+
 static void fill_random_ptr_key(struct random_ready_callback *unused)
 {
 	get_random_bytes(&ptr_key, sizeof(ptr_key));
-	/*
-	 * have_filled_random_ptr_key==true is dependent on get_random_bytes().
-	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
-	 * after get_random_bytes() returns.
-	 */
-	smp_mb();
-	WRITE_ONCE(have_filled_random_ptr_key, true);
+	queue_work(system_unbound_wq, &enable_ptr_key_work);
 }
 
 static struct random_ready_callback random_ready = {
@@ -1709,7 +1711,7 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
 	unsigned long hashval;
 	const int default_width = 2 * sizeof(ptr);
 
-	if (unlikely(!have_filled_random_ptr_key)) {
+	if (static_branch_unlikely(&not_filled_random_ptr_key)) {
 		spec.field_width = default_width;
 		/* string length must be less than default_width */
 		return string(buf, end, "(ptrval)", spec);

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Linus Torvalds]

On Tue, May 15, 2018 at 11:57 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> +       queue_work(system_unbound_wq, &enable_ptr_key_work);

I think this part just makes the whole thing entirely pointless.

Now the 'not_filled_random_ptr_key' thing won't actually take effect until
possibly much later, so all the work with making this work very early
during boot (when those works are *not* done) is all for naught.

Did I miss something?

              Linus

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

On Tue, 15 May 2018 12:03:32 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Tue, May 15, 2018 at 11:57 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> > +       queue_work(system_unbound_wq, &enable_ptr_key_work);  
> 
> I think this part just makes the whole thing entirely pointless.
> 
> Now the 'not_filled_random_ptr_key' thing won't actually take effect until
> possibly much later, so all the work with making this work very early
> during boot (when those works are *not* done) is all for naught.
> 
> Did I miss something?
> 
>               Linus

The work queue looks to run immediately. When adding this:

@@ -1674,6 +1674,7 @@
 
 static void enable_ptr_key_workfn(struct work_struct *work)
 {
+       printk("enable static branch\n");
        /* Needs to run from preemptable context */
        static_branch_disable(&not_filled_random_ptr_key);
 }
@@ -1683,6 +1684,7 @@
 static void fill_random_ptr_key(struct random_ready_callback *unused)
 {
        get_random_bytes(&ptr_key, sizeof(ptr_key));
+       printk("queue enable static branch work\n");
        queue_work(system_unbound_wq, &enable_ptr_key_work);
 }
 
@@ -1694,10 +1696,11 @@
 {
        int ret = add_random_ready_callback(&random_ready);
 
+       printk("initialize random\n");
+       fill_random_ptr_key(&random_ready);
        if (!ret) {
                return 0;
        } else if (ret == -EALREADY) {
-               fill_random_ptr_key(&random_ready);
                return 0;
        }


I found this in the dmesg:

[    0.052824] initialize random
[    0.053010] random: get_random_bytes called from fill_random_ptr_key+0x15/0x40 with crng_init=0
[    0.054005] queue enable static branch work
[    0.056066] enable static branch

2 milliseconds isn't that bad. But if you don't like that, we could
always do this:

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..1b7bcc6c1032 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1669,19 +1669,24 @@ char *pointer_string(char *buf, char *end, const void *ptr,
 	return number(buf, end, (unsigned long int)ptr, spec);
 }
 
-static bool have_filled_random_ptr_key __read_mostly;
+static DEFINE_STATIC_KEY_TRUE(not_filled_random_ptr_key);
 static siphash_key_t ptr_key __read_mostly;
 
+static void enable_ptr_key_workfn(struct work_struct *work)
+{
+	/* Needs to run from preemptable context */
+	static_branch_disable(&not_filled_random_ptr_key);
+}
+
+static DECLARE_WORK(enable_ptr_key_work, enable_ptr_key_workfn);
+
 static void fill_random_ptr_key(struct random_ready_callback *unused)
 {
 	get_random_bytes(&ptr_key, sizeof(ptr_key));
-	/*
-	 * have_filled_random_ptr_key==true is dependent on get_random_bytes().
-	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
-	 * after get_random_bytes() returns.
-	 */
-	smp_mb();
-	WRITE_ONCE(have_filled_random_ptr_key, true);
+	if (irqs_disabled() || in_atomic())
+		queue_work(system_unbound_wq, &enable_ptr_key_work);
+	else
+		enable_ptr_key_workfn(&enable_ptr_key_work);
 }
 
 static struct random_ready_callback random_ready = {
@@ -1709,7 +1714,7 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
 	unsigned long hashval;
 	const int default_width = 2 * sizeof(ptr);
 
-	if (unlikely(!have_filled_random_ptr_key)) {
+	if (static_branch_unlikely(&not_filled_random_ptr_key)) {
 		spec.field_width = default_width;
 		/* string length must be less than default_width */
 		return string(buf, end, "(ptrval)", spec);

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Linus Torvalds]

On Tue, May 15, 2018 at 1:10 PM Steven Rostedt <rostedt@goodmis.org> wrote:
> The work queue looks to run immediately.

2ms is definitely not "immediately". It's just "soon".

The whole - and _only_ reason we're doing all these changes is that people
wanted reliable object hashes from very early bootup tracing, so I think it
matters.

> we could always do this:

Ugh. I think I prefer the barriers.

                Linus

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

On Tue, 15 May 2018 15:31:37 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> > we could always do this:  
> 
> Ugh. I think I prefer the barriers.

But the ugliness is only at boot up, where the early printing is
important. The benefit of this is here:

@@ -1709,7 +1717,7 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
        unsigned long hashval;
        const int default_width = 2 * sizeof(ptr);
 
-       if (unlikely(!have_filled_random_ptr_key)) {
+       if (static_branch_unlikely(&not_filled_random_ptr_key)) {
                spec.field_width = default_width;
                /* string length must be less than default_width */
                return string(buf, end, "(ptrval)", spec);

Because not only do we not add any barriers, this code basically
becomes a nop once the ptr_key is filled, and this should have a small
speed up in execution (although I have not done any benchmarks).

-- Steve

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

On Tue, 15 May 2018 18:41:17 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Tue, 15 May 2018 15:31:37 -0700
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
> 
> > > we could always do this:    
> > 
> > Ugh. I think I prefer the barriers.  
> 

If it is that if statement you don't like. We can get rid of it. On
early boot, the code is called from preemptable context, it's only
later that it is not. So we know when we can call it directly and when
we need to have a work queue.

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..69d3ed8557ce 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1669,19 +1669,21 @@ char *pointer_string(char *buf, char *end, const void *ptr,
 	return number(buf, end, (unsigned long int)ptr, spec);
 }
 
-static bool have_filled_random_ptr_key __read_mostly;
+static DEFINE_STATIC_KEY_TRUE(not_filled_random_ptr_key);
 static siphash_key_t ptr_key __read_mostly;
 
-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void enable_ptr_key_workfn(struct work_struct *work)
 {
 	get_random_bytes(&ptr_key, sizeof(ptr_key));
-	/*
-	 * have_filled_random_ptr_key==true is dependent on get_random_bytes().
-	 * ptr_to_id() needs to see have_filled_random_ptr_key==true
-	 * after get_random_bytes() returns.
-	 */
-	smp_mb();
-	WRITE_ONCE(have_filled_random_ptr_key, true);
+	/* Needs to run from preemptable context */
+	static_branch_disable(&not_filled_random_ptr_key);
+}
+
+static DECLARE_WORK(enable_ptr_key_work, enable_ptr_key_workfn);
+
+static void fill_random_ptr_key(struct random_ready_callback *unused)
+{
+	queue_work(system_unbound_wq, &enable_ptr_key_work);
 }
 
 static struct random_ready_callback random_ready = {
@@ -1695,7 +1697,7 @@ static int __init initialize_ptr_random(void)
 	if (!ret) {
 		return 0;
 	} else if (ret == -EALREADY) {
-		fill_random_ptr_key(&random_ready);
+		enable_ptr_key_workfn(&enable_ptr_key_work);
 		return 0;
 	}
 
@@ -1709,7 +1711,7 @@ static char *ptr_to_id(char *buf, char *end, void *ptr, struct printf_spec spec)
 	unsigned long hashval;
 	const int default_width = 2 * sizeof(ptr);
 
-	if (unlikely(!have_filled_random_ptr_key)) {
+	if (static_branch_unlikely(&not_filled_random_ptr_key)) {
 		spec.field_width = default_width;
 		/* string length must be less than default_width */
 		return string(buf, end, "(ptrval)", spec);

-- Steve

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Linus Torvalds]

On Tue, May 15, 2018 at 4:00 PM Steven Rostedt <rostedt@goodmis.org> wrote:

> If it is that if statement you don't like. We can get rid of it. On
> early boot, the code is called from preemptable context, it's only
> later that it is not. So we know when we can call it directly and when
> we need to have a work queue.

Oh, that looks much better to me, yes. Just doing it this way instead
removes my "ugh, that's nasty" objections.

So ack on this last version of the patch, because it doesn't scare me (or
you've worn me down ;)

               Linus

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Pavel Machek]

[-- Attachment #1: Type: text/plain, Size: 1684 bytes --]

On Tue 2018-05-15 14:57:44, Steven Rostedt wrote:
> On Tue, 15 May 2018 09:55:13 -0700
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
> 
> > On Tue, May 15, 2018 at 7:06 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> > > -       smp_mb();
> > > +       smp_wmb();
> > >          WRITE_ONCE(have_filled_random_ptr_key, true);  
> > 
> > 
> > > +       /* Read ptr_key after reading have_filled_random_ptr_key */
> > > +       smp_rmb();
> > > +
> > >   #ifdef CONFIG_64BIT
> > >          hashval = (unsigned long)siphash_1u64((u64)ptr, &ptr_key);  
> > 
> > Hmm. smp_wmb/rmb are basically free on x86, but on some architectures
> > smp_rmb() in particular can be pretty expensive.
> > 
> > So when you have a "handoff" situation like this, it's _probably_ better to
> > use use "smp_store_release()" and "smp_load_acquire()". To some degree that
> > might also be better for documentation purposes, because that's exactly the
> > "release-acquire" pattern.
> > 
> > That said, I'm not convinced this really matters all that much for a
> > boot-time flag like this. The race is pretty theoretical.
> >
> 
> I was thinking the same. But since the smp_mb() is there, then it
> should be correct, which it currently isn't.
> 
> We could change this to a static key, and enable it after we set up
> the ptr_key. That would be a one time change at boot up, wont have
> races, and have no overhead.

OTOH... fixing theoretical races is nice, but probably should not go
to stable?
								Pavel
								
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: [PATCH] vsprintf: Fix memory barriers of ptr_key to have_filed_random_ptr_key

[Steven Rostedt]

On Wed, 23 May 2018 12:40:37 +0200
Pavel Machek <pavel@ucw.cz> wrote:

> OTOH... fixing theoretical races is nice, but probably should not go
> to stable?

It also improves the performance of the hot path.

-- Steve