Skip to contentSkip to conversation

enable early printing of hashed pointers

PATCH Superseded Tobin C. Harding 2 participants 10 messages May 15, 2018

Subsystems (3)

v4 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

v4 cover enable early printing of hashed pointers

Currently if an attempt is made to print a pointer before there is enough entropy then '(____ptrval____)' is printed. This makes debugging stack traces during early boot difficult.

One partial solution to this problem is to use the hw RNG if it is available.

This version drops the final patch from the series to facilitate merge via Ted's tree.

Ted are you able to take these patches please?

Patch 1 - Whitespace fixes.
Patch 2 - Fix get_random_bytes_arch()
Patch 3 - Use hw RNG for pointer hashing if available (by default).

thanks,
Tobin.

v3 -> v4
- remove last patch of series (command line option patch)

v2 -> v3
- Add __ro_after_init (suggested by Kees).

v1 -> v2
- Use min_t() instead of min() (thanks checkpatch).
- Add __must_check to function declaration (thanks Steve).
- Use hw RNG by default if available (as originally suggested by Kees).
- Add command line option to use cryptographically insecure hashing. If debug_early_boot is enabled use hash_long() instead of siphash (as requested by Steve, and solves original problem for Anna-Maria).

Tobin C. Harding (3):
random: Fix whitespace pre random-bytes work
random: Return nbytes filled from hw RNG
vsprintf: Use hw RNG for ptr_key

 drivers/char/random.c  | 19 ++++++++++---------
 include/linux/random.h |  2 +-
 lib/vsprintf.c         | 19 ++++++++++++++++---
 3 files changed, 27 insertions(+), 13 deletions(-)
Signature · 1 line
2.7.4
#1 lore raw

PATCH v4 1/3 random: Fix whitespace pre random-bytes work

There are a couple of whitespace issues around the function get_random_bytes_arch(). In preparation for patching this function let's clean them up.

---
 drivers/char/random.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
drivers/char/random.c +1 -2
index cd888d4ee605..031d18b31e0f 100644
@@ -1737,7 +1737,7 @@ void get_random_bytes_arch(void *buf, int nbytes)
 
 		if (!arch_get_random_long(&v))
 			break;
-		
+
 		memcpy(p, &v, chunk);
 		p += chunk;
 		nbytes -= chunk;
@@ -1748,7 +1748,6 @@ void get_random_bytes_arch(void *buf, int nbytes)
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
-
 /*
  * init_std_data - initialize pool with system data
  *
Signature · 1 line
2.7.4
#2 lore raw

PATCH v4 2/3 random: Return nbytes filled from hw RNG

In reply to Tobin C. Harding

Currently the function get_random_bytes_arch() has return value 'void'. If the hw RNG fails we currently fall back to using get_random_bytes(). This defeats the purpose of requesting random material from the hw RNG in the first place.

There are currently no intree users of get_random_bytes_arch().

Only get random bytes from the hw RNG, make function return the number of bytes retrieved from the hw RNG.

---
 drivers/char/random.c  | 16 +++++++++-------
 include/linux/random.h |  2 +-
 2 files changed, 10 insertions(+), 8 deletions(-)
drivers/char/random.c +9 -7
index 031d18b31e0f..4b0ec597e783 100644
@@ -1725,26 +1725,28 @@ EXPORT_SYMBOL(del_random_ready_callback);
  * key known by the NSA).  So it's useful if we need the speed, but
  * only if we're willing to trust the hardware manufacturer not to
  * have put in a back door.
+ *
+ * Return number of bytes filled in.
  */
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;
 
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);
+	while (left) {
 		unsigned long v;
-		int chunk = min(nbytes, (int)sizeof(unsigned long));
+		int chunk = min_t(int, left, (int)sizeof(unsigned long));
 
 		if (!arch_get_random_long(&v))
 			break;
 
 		memcpy(p, &v, chunk);
 		p += chunk;
-		nbytes -= chunk;
+		left -= chunk;
 	}
 
-	if (nbytes)
-		get_random_bytes(p, nbytes);
+	return nbytes - left;
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
include/linux/random.h +1 -1
index 2ddf13b4281e..f1c9bc5cd231 100644
@@ -38,7 +38,7 @@ extern void get_random_bytes(void *buf, int nbytes);
 extern int wait_for_random_bytes(void);
 extern int add_random_ready_callback(struct random_ready_callback *rdy);
 extern void del_random_ready_callback(struct random_ready_callback *rdy);
-extern void get_random_bytes_arch(void *buf, int nbytes);
+extern int __must_check get_random_bytes_arch(void *buf, int nbytes);
 
 #ifndef MODULE
 extern const struct file_operations random_fops, urandom_fops;
Signature · 1 line
2.7.4
maintainer Reviewed-by on v4 2/3
#3 lore raw

Re: [PATCH v4 2/3] random: Return nbytes filled from hw RNG

Quoted 24 lines · On Tue, 15 May 2018 13:06:25 +1000 "Tobin C. Harding" <[email protected]> wrote:

Currently the function get_random_bytes_arch() has return value 'void'. If the hw RNG fails we currently fall back to using get_random_bytes(). This defeats the purpose of requesting random material from the hw RNG in the first place.

There are currently no intree users of get_random_bytes_arch().

Only get random bytes from the hw RNG, make function return the number of bytes retrieved from the hw RNG.

---
 drivers/char/random.c  | 16 +++++++++-------
 include/linux/random.h |  2 +-
 2 files changed, 10 insertions(+), 8 deletions(-)
drivers/char/random.c +0 -0
index 031d18b31e0f..4b0ec597e783 100644
@@ -1725,26 +1725,28 @@ EXPORT_SYMBOL(del_random_ready_callback);
  * key known by the NSA).  So it's useful if we need the speed, but

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1734

Quoted 10 lines
drivers/char/random.c +4 -1
  * only if we're willing to trust the hardware manufacturer not to
  * have put in a back door.
+ *
+ * Return number of bytes filled in.
  */
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;

Just a nit, but I know some kernel devs prefer "upside-down-xmas-tree" style of declarations. Which would make the above:

	int left = nbytes;
	char *p = buf;

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1736

Quoted 4 lines
drivers/char/random.c +1 -2
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);

Nothing to do with this patch series, but I wonder if we should move the trace event below, and record how much was done.

Quoted 25 lines
drivers/char/random.c +4 -4
+	while (left) {
 		unsigned long v;
-		int chunk = min(nbytes, (int)sizeof(unsigned long));
+		int chunk = min_t(int, left, (int)sizeof(unsigned long));
 
 		if (!arch_get_random_long(&v))
 			break;
 
 		memcpy(p, &v, chunk);
 		p += chunk;
-		nbytes -= chunk;
+		left -= chunk;
 	}
 
-	if (nbytes)
-		get_random_bytes(p, nbytes);
+	return nbytes - left;
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
include/linux/random.h +0 -0
index 2ddf13b4281e..f1c9bc5cd231 100644

include/linux/random.h extern void get_random_bytes(void *buf, int nbytes); · line 44

Quoted 8 lines
include/linux/random.h +1 -1
@@ -38,7 +38,7 @@ extern void get_random_bytes(void *buf, int nbytes);
 extern int wait_for_random_bytes(void);
 extern int add_random_ready_callback(struct random_ready_callback *rdy);
 extern void del_random_ready_callback(struct random_ready_callback *rdy);
-extern void get_random_bytes_arch(void *buf, int nbytes);
+extern int __must_check get_random_bytes_arch(void *buf, int nbytes);
 
 #ifndef MODULE
 extern const struct file_operations random_fops, urandom_fops;

Other than that...

-- Steve

#4 lore raw

Re: [PATCH v4 2/3] random: Return nbytes filled from hw RNG

Quoted 41 lines · Steven Rostedt
Quoted 24 lines · On Tue, 15 May 2018 13:06:25 +1000 "Tobin C. Harding" <[email protected]> wrote:

Currently the function get_random_bytes_arch() has return value 'void'. If the hw RNG fails we currently fall back to using get_random_bytes(). This defeats the purpose of requesting random material from the hw RNG in the first place.

There are currently no intree users of get_random_bytes_arch().

Only get random bytes from the hw RNG, make function return the number of bytes retrieved from the hw RNG.

---
 drivers/char/random.c  | 16 +++++++++-------
 include/linux/random.h |  2 +-
 2 files changed, 10 insertions(+), 8 deletions(-)
drivers/char/random.c +0 -0
index 031d18b31e0f..4b0ec597e783 100644
@@ -1725,26 +1725,28 @@ EXPORT_SYMBOL(del_random_ready_callback);
  * key known by the NSA).  So it's useful if we need the speed, but

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1734

Quoted 10 lines
drivers/char/random.c +4 -1
  * only if we're willing to trust the hardware manufacturer not to
  * have put in a back door.
+ *
+ * Return number of bytes filled in.
  */
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;

Just a nit, but I know some kernel devs prefer "upside-down-xmas-tree" style of declarations. Which would make the above:

Quoted 2 lines
	int left = nbytes;
	char *p = buf;

Super specific coding style and rigorous code cleanliness is a big part of why I love kernel dev. Thanks for pointing this one out.

While we are on these code lines, whats the typical kernel variable name for a loop counter that is going to be counted down? 'left', 'remaining', 'to_go', 'still'???

Quoted 7 lines

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1736

Quoted 4 lines
drivers/char/random.c +1 -2
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);

Nothing to do with this patch series, but I wonder if we should move the trace event below, and record how much was done.

I don't fully understand trace events, I just left this line in tact and hoped for the best :(

/me adds 'trace events' to list of things to learn more about

Quoted 31 lines
Quoted 31 lines
drivers/char/random.c +4 -4
+	while (left) {
 		unsigned long v;
-		int chunk = min(nbytes, (int)sizeof(unsigned long));
+		int chunk = min_t(int, left, (int)sizeof(unsigned long));
 
 		if (!arch_get_random_long(&v))
 			break;
 
 		memcpy(p, &v, chunk);
 		p += chunk;
-		nbytes -= chunk;
+		left -= chunk;
 	}
 
-	if (nbytes)
-		get_random_bytes(p, nbytes);
+	return nbytes - left;
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
include/linux/random.h +1 -1
index 2ddf13b4281e..f1c9bc5cd231 100644
@@ -38,7 +38,7 @@ extern void get_random_bytes(void *buf, int nbytes);
 extern int wait_for_random_bytes(void);
 extern int add_random_ready_callback(struct random_ready_callback *rdy);
 extern void del_random_ready_callback(struct random_ready_callback *rdy);
-extern void get_random_bytes_arch(void *buf, int nbytes);
+extern int __must_check get_random_bytes_arch(void *buf, int nbytes);
 
Quoted 6 lines

include/linux/random.h extern void get_random_bytes(void *buf, int nbytes); · line 44

Quoted 2 lines
include/linux/random.h +0 -0
 #ifndef MODULE
 extern const struct file_operations random_fops, urandom_fops;

Other than that...

Thanks for the review Steve, will spin again.

Tobin.

maintainer
#5 lore raw

Re: [PATCH v4 2/3] random: Return nbytes filled from hw RNG

Quoted 9 lines · On Wed, 16 May 2018 07:17:06 +1000 "Tobin C. Harding" <[email protected]> wrote:
Quoted 9 lines

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1734

Quoted 5 lines
drivers/char/random.c +2 -1
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;  

Just a nit, but I know some kernel devs prefer "upside-down-xmas-tree" style of declarations. Which would make the above:

Quoted 5 lines
Quoted 2 lines
	int left = nbytes;
	char *p = buf;  

Super specific coding style and rigorous code cleanliness is a big part of why I love kernel dev. Thanks for pointing this one out.

It's a relatively new form, but I like it. It makes the code look "less messy" ;-) Some devs don't care, others do. This file already breaks it, so it really is up to you. Like I said, it's "just a nit", not really important.

Quoted 4 lines

While we are on these code lines, whats the typical kernel variable name for a loop counter that is going to be counted down? 'left', 'remaining', 'to_go', 'still'???

"left" looks good to me.

Quoted 11 lines
Quoted 8 lines

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1736

Quoted 5 lines
drivers/char/random.c +1 -2
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);  

Nothing to do with this patch series, but I wonder if we should move the trace event below, and record how much was done.

I don't fully understand trace events, I just left this line in tact and hoped for the best :(

Your patch is fine. This could be something to add after your series.

Quoted 2 lines

/me adds 'trace events' to list of things to learn more about

Just look at /sys/kernel/debug/tracing/events

Or read Documentation/trace/ftrace.{rst,txt}.

-- Steve

#6 lore raw

Re: [PATCH v4 2/3] random: Return nbytes filled from hw RNG

Quoted 42 lines · Steven Rostedt
Quoted 9 lines · On Wed, 16 May 2018 07:17:06 +1000 "Tobin C. Harding" <[email protected]> wrote:
Quoted 9 lines

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1734

Quoted 5 lines
drivers/char/random.c +2 -1
-void get_random_bytes_arch(void *buf, int nbytes)
+int __must_check get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
+	int left = nbytes;  

Just a nit, but I know some kernel devs prefer "upside-down-xmas-tree" style of declarations. Which would make the above:

Quoted 5 lines
Quoted 2 lines
	int left = nbytes;
	char *p = buf;  

Super specific coding style and rigorous code cleanliness is a big part of why I love kernel dev. Thanks for pointing this one out.

It's a relatively new form, but I like it. It makes the code look "less messy" ;-) Some devs don't care, others do. This file already breaks it, so it really is up to you. Like I said, it's "just a nit", not really important.

Quoted 4 lines

While we are on these code lines, whats the typical kernel variable name for a loop counter that is going to be counted down? 'left', 'remaining', 'to_go', 'still'???

"left" looks good to me.

Quoted 11 lines
Quoted 8 lines

drivers/char/random.c EXPORT_SYMBOL(del_random_ready_callback); · line 1736

Quoted 5 lines
drivers/char/random.c +1 -2
-	trace_get_random_bytes_arch(nbytes, _RET_IP_);
-	while (nbytes) {
+	trace_get_random_bytes_arch(left, _RET_IP_);  

Nothing to do with this patch series, but I wonder if we should move the trace event below, and record how much was done.

I don't fully understand trace events, I just left this line in tact and hoped for the best :(

Quoted 8 lines

Your patch is fine. This could be something to add after your series.

Quoted 2 lines

/me adds 'trace events' to list of things to learn more about

Just look at /sys/kernel/debug/tracing/events

Or read Documentation/trace/ftrace.{rst,txt}.

Awesome, cheers.

#7 lore raw

PATCH v4 3/3 vsprintf: Use hw RNG for ptr_key

In reply to Tobin C. Harding

Currently we must wait for enough entropy to become available before hashed pointers can be printed. We can remove this wait by using the hw RNG if available.

Use hw RNG to get keying material.

---
 lib/vsprintf.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)
lib/vsprintf.c +16 -3
index b82f0c6c2aec..3697a19c2b25 100644
@@ -1657,9 +1657,8 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;
 
-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void ptr_key_ready(void)
 {
-	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
@@ -1669,14 +1668,28 @@ static void fill_random_ptr_key(struct random_ready_callback *unused)
 	WRITE_ONCE(have_filled_random_ptr_key, true);
 }
 
+static void fill_random_ptr_key(struct random_ready_callback *unused)
+{
+	get_random_bytes(&ptr_key, sizeof(ptr_key));
+	ptr_key_ready();
+}
+
 static struct random_ready_callback random_ready = {
 	.func = fill_random_ptr_key
 };
 
 static int __init initialize_ptr_random(void)
 {
-	int ret = add_random_ready_callback(&random_ready);
+	int ret;
+	int key_size = sizeof(ptr_key);
+
+	/* Use hw RNG if available */
+	if (get_random_bytes_arch(&ptr_key, key_size) == key_size) {
+		ptr_key_ready();
+		return 0;
+	}
 
+	ret = add_random_ready_callback(&random_ready);
 	if (!ret) {
 		return 0;
 	} else if (ret == -EALREADY) {
Signature · 1 line
2.7.4
maintainer Reviewed-by on v4 3/3
#8 lore raw

Re: [PATCH v4 3/3] vsprintf: Use hw RNG for ptr_key

Quoted 17 lines · On Tue, 15 May 2018 13:06:26 +1000 "Tobin C. Harding" <[email protected]> wrote:

Currently we must wait for enough entropy to become available before hashed pointers can be printed. We can remove this wait by using the hw RNG if available.

Use hw RNG to get keying material.

---
 lib/vsprintf.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)
lib/vsprintf.c +0 -0
index b82f0c6c2aec..3697a19c2b25 100644

lib/vsprintf.c char *device_node_string(char *buf, char *end, struct device_node *dn, · line 1664

Quoted 10 lines
lib/vsprintf.c +1 -2
@@ -1657,9 +1657,8 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;
 
-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void ptr_key_ready(void)
 {
-	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

Nothing to do with this patch, but I believe there's a missing memory barrier in the code.

Right after this we have:

	smp_mb();
	WRITE_ONCE(have_filled_random_ptr_key, true);

Where the comment says that have_filled_random_ptr_key must be set after ptr_key has been updated. But there's no memory barrier on the read side. In fact, I think this could be a smp_wmb() instead of a smp_mb(). The read side has:

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

/* Missing memory barrier smp_rmb() here. */

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

Thus we can have something like:

	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!

I'll send a patch.

Quoted 20 lines
lib/vsprintf.c +9 -1
@@ -1669,14 +1668,28 @@ static void fill_random_ptr_key(struct random_ready_callback *unused)
 	WRITE_ONCE(have_filled_random_ptr_key, true);
 }
 
+static void fill_random_ptr_key(struct random_ready_callback *unused)
+{
+	get_random_bytes(&ptr_key, sizeof(ptr_key));
+	ptr_key_ready();
+}
+
 static struct random_ready_callback random_ready = {
 	.func = fill_random_ptr_key
 };
 
 static int __init initialize_ptr_random(void)
 {
-	int ret = add_random_ready_callback(&random_ready);
+	int ret;
+	int key_size = sizeof(ptr_key);
+

lib/vsprintf.c static void fill_random_ptr_key(struct random_ready_callback *unused) · line 1695

Quoted 10 lines
lib/vsprintf.c +6 -0
+	/* Use hw RNG if available */
+	if (get_random_bytes_arch(&ptr_key, key_size) == key_size) {
+		ptr_key_ready();
+		return 0;
+	}
 
+	ret = add_random_ready_callback(&random_ready);
 	if (!ret) {
 		return 0;
 	} else if (ret == -EALREADY) {

But this patch looks good.

-- Steve

#9 lore raw

Re: [PATCH v4 3/3] vsprintf: Use hw RNG for ptr_key

Quoted 60 lines · Steven Rostedt
Quoted 17 lines · On Tue, 15 May 2018 13:06:26 +1000 "Tobin C. Harding" <[email protected]> wrote:

Currently we must wait for enough entropy to become available before hashed pointers can be printed. We can remove this wait by using the hw RNG if available.

Use hw RNG to get keying material.

---
 lib/vsprintf.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)
lib/vsprintf.c +0 -0
index b82f0c6c2aec..3697a19c2b25 100644

lib/vsprintf.c char *device_node_string(char *buf, char *end, struct device_node *dn, · line 1664

Quoted 10 lines
lib/vsprintf.c +1 -2
@@ -1657,9 +1657,8 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;
 
-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void ptr_key_ready(void)
 {
-	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

Nothing to do with this patch, but I believe there's a missing memory barrier in the code.

Right after this we have:

	smp_mb();
	WRITE_ONCE(have_filled_random_ptr_key, true);

Where the comment says that have_filled_random_ptr_key must be set after ptr_key has been updated. But there's no memory barrier on the read side. In fact, I think this could be a smp_wmb() instead of a smp_mb(). The read side has:

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

/* Missing memory barrier smp_rmb() here. */

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

Thus we can have something like:

	CPU0				CPU1
	----				----
				   load ptr_key = 0

store ptr_key = random
smp_mb()
store have_filled_random_ptr_key

Quoted 5 lines

load have_filled_random_ptr_key = true

BAD BAD BAD!

I'll send a patch.

Awesome reviewing. Thanks for catching this.

Tobin