Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[George Spelvin]

+#define external_array(type, name) \
+	({ \
+		extern type name[]; \
+		type *name_ptr = name; \
+		asm ("" : "+r" (name_ptr)); \
+		name_ptr; \
+	})

I've had to pull similar tricks to persuade GCC to generate
the code I wanted (in my case, it was optimization: "evaluate it
in this order, damn it!"), and I prefer to use the asm itself
with overlapping operands to do the assignment.

#define external_array(type, name) \
	({ \
		extern type name[]; \
		type *name_ptr;
		asm ("" : "=g" (name_ptr) : "0" (name)); \
		name_ptr; \
	})

You could define a wrapper if you like, something like

/*
 * Assign dst = src, but prevent the compiler from inferring anything
 * about the assigned value, so it can't do any unwanted optimization.
 */
#define blind_assign(dst,src) asm("" : "=X" (dst) : "0" (src))

In case it helps, here's a list of architecture-independent operand
constraints (that I think is exhaustive, but I'm not 100% sure):
r - general-purpose register
f - floating-point register
m - memory
o - offsettable memory (excluding pre/post inc/decrement modes)
i - immediate
g - "general", any of the above
X - "wildcard".  This matches anything at all, including special-purpose
    registers that are not included in "r".

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Linus Torvalds]

On Tue, Jun 28, 2016 at 5:23 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> You could define a wrapper if you like, something like

We already have RELOC_HIDE() and OPTIMIZER_HIDE_VAR() that basically do this.

They both use 'r'. I guess they could use X.

                    Linus

[PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Vegard Nossum]

The test in this loop:

  for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {

was getting completely compiled out by my gcc, 7.0.0 20160520. The result
was that the loop was going beyond the end of the builtin_fw array and
giving me a page fault when trying to dereference b_fw->name inside
strcmp().

I strongly suspect it's because __start_builtin_fw and __end_builtin_fw
are both declared as (separate) arrays, and so gcc conludes that b_fw can
never point to __end_builtin_fw.

By changing these variables from arrays to pointers, gcc can no longer
assume that these are separate arrays.

Cc: stable@vger.kernel.org
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
---
 drivers/base/firmware_class.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/drivers/base/firmware_class.c b/drivers/base/firmware_class.c
index 773fc30..4dddf7f 100644
--- a/drivers/base/firmware_class.c
+++ b/drivers/base/firmware_class.c
@@ -43,8 +43,8 @@ MODULE_LICENSE("GPL");
 
 #ifdef CONFIG_FW_LOADER
 
-extern struct builtin_fw __start_builtin_fw[];
-extern struct builtin_fw __end_builtin_fw[];
+extern struct builtin_fw *__start_builtin_fw;
+extern struct builtin_fw *__end_builtin_fw;
 
 static bool fw_get_builtin_firmware(struct firmware *fw, const char *name)
 {
-- 
1.9.1

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Vegard Nossum]

On 25 June 2016 at 17:04, Vegard Nossum <vegard.nossum@oracle.com> wrote:
> The test in this loop:
>
>   for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {
>
> was getting completely compiled out by my gcc, 7.0.0 20160520. The result
> was that the loop was going beyond the end of the builtin_fw array and
> giving me a page fault when trying to dereference b_fw->name inside
> strcmp().
>
> I strongly suspect it's because __start_builtin_fw and __end_builtin_fw
> are both declared as (separate) arrays, and so gcc conludes that b_fw can
> never point to __end_builtin_fw.
>
> By changing these variables from arrays to pointers, gcc can no longer
> assume that these are separate arrays.
>
> Cc: stable@vger.kernel.org
> Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>

Actually, the analysis seems right (by inspection of the assembly
code), but the patch is wrong and causes another crash as the
variables are not really pointers but true arrays (i.e. the linker
script provides the address of the variable, not its value).

I see the __start_foo[]/__end_foo[] idiom is used a lot in the kernel
so this could potentially be a problem in other places as well. The
best solution may be a compiler flag (if it exists). I'll play a bit
more with it to see if I can come up with something.


Vegard

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Vegard Nossum]

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

On 25 June 2016 at 23:06, Vegard Nossum <vegard.nossum@gmail.com> wrote:
> On 25 June 2016 at 17:04, Vegard Nossum <vegard.nossum@oracle.com> wrote:
>> The test in this loop:
>>
>>   for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {
>>
>> was getting completely compiled out by my gcc, 7.0.0 20160520. The result
>> was that the loop was going beyond the end of the builtin_fw array and
>> giving me a page fault when trying to dereference b_fw->name inside
>> strcmp().
>>
>> I strongly suspect it's because __start_builtin_fw and __end_builtin_fw
>> are both declared as (separate) arrays, and so gcc conludes that b_fw can
>> never point to __end_builtin_fw.
>>
> I see the __start_foo[]/__end_foo[] idiom is used a lot in the kernel
> so this could potentially be a problem in other places as well. The
> best solution may be a compiler flag (if it exists). I'll play a bit
> more with it to see if I can come up with something.

This is the best I could come up with: assuming gcc is not allowed to
reason about what's inside the asm(), this is the only way I could
think of to lose the array information without incurring unnecessary
overheads. It should also be relatively safe as there is no way to
accidentally use the underlying arrays without explicitly declaring
them.

I've not run-tested the final version of the patch yet (as I have to
run), but I did successfully boot an earlier version which was only
cosmetically different (I think).


Vegard

[-- Attachment #2: 0001-firmware-declare-__-start-end-_builtin_fw-as-pointer.patch --]
[-- Type: text/x-patch, Size: 2734 bytes --]

From 7efe386eea88344a0b99a587d759d8df0e937207 Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@oracle.com>
Date: Sat, 25 Jun 2016 16:30:14 +0200
Subject: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

The test in this loop:

  for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {

was getting completely compiled out by my gcc, 7.0.0 20160520. The result
was that the loop was going beyond the end of the builtin_fw array and
giving me a page fault when trying to dereference b_fw->name inside
strcmp().

I strongly suspect it's because __start_builtin_fw and __end_builtin_fw
are both declared as (separate) arrays, and so gcc conludes that b_fw can
never point to __end_builtin_fw.

We can lose the array information about a pointer by using an empty
assembly stub since gcc can't reason about the assembly code.

I've used a helper macro so that we can hide the real array definition
and not use it by accident.

Cc: stable@vger.kernel.org
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
---
 drivers/base/firmware_class.c  |  5 +++--
 include/linux/external_array.h | 18 ++++++++++++++++++
 2 files changed, 21 insertions(+), 2 deletions(-)
 create mode 100644 include/linux/external_array.h

diff --git a/drivers/base/firmware_class.c b/drivers/base/firmware_class.c
index 773fc30..595ec55 100644
--- a/drivers/base/firmware_class.c
+++ b/drivers/base/firmware_class.c
@@ -9,6 +9,7 @@
 
 #include <linux/capability.h>
 #include <linux/device.h>
+#include <linux/external_array.h>
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/timer.h>
@@ -43,8 +44,8 @@ MODULE_LICENSE("GPL");
 
 #ifdef CONFIG_FW_LOADER
 
-extern struct builtin_fw __start_builtin_fw[];
-extern struct builtin_fw __end_builtin_fw[];
+#define __start_builtin_fw external_array(struct builtin_fw, __start_builtin_fw)
+#define __end_builtin_fw external_array(struct builtin_fw, __end_builtin_fw)
 
 static bool fw_get_builtin_firmware(struct firmware *fw, const char *name)
 {
diff --git a/include/linux/external_array.h b/include/linux/external_array.h
new file mode 100644
index 0000000..dfca996
--- /dev/null
+++ b/include/linux/external_array.h
@@ -0,0 +1,18 @@
+#ifndef LINUX_EXTERNAL_ARRAY_H
+#define LINUX_EXTERNAL_ARRAY_H
+
+/*
+ * Lose any array information on the argument. Useful when we define an array
+ * in a linker script using "start" and "end" variables and gcc incorrectly
+ * assumes that these are separate arrays (and aggressively optimizes away
+ * loop termination conditions, for example).
+ */
+#define external_array(type, name) \
+	({ \
+		extern type name[]; \
+		type *name_ptr = name; \
+		asm ("" : "+r" (name_ptr)); \
+		name_ptr; \
+	})
+
+#endif
-- 
1.9.1

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Linus Torvalds]

On Sun, Jun 26, 2016 at 2:24 AM, Vegard Nossum <vegard.nossum@gmail.com> wrote:
>
> This is the best I could come up with: assuming gcc is not allowed to
> reason about what's inside the asm(), this is the only way I could
> think of to lose the array information without incurring unnecessary
> overheads. It should also be relatively safe as there is no way to
> accidentally use the underlying arrays without explicitly declaring
> them.

Ugh. I worry about the other places where we do things like this,
depending on the linker just assigning the addresses and us being able
to compare them.

If there is a compiler option to disable this optimization, I would
almost prefer that.. Because we really do have a whole slew of these
things.

                 Linus

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Jiri Slaby]

On 06/26/2016, 07:17 PM, Linus Torvalds wrote:
> On Sun, Jun 26, 2016 at 2:24 AM, Vegard Nossum <vegard.nossum@gmail.com> wrote:
>>
>> This is the best I could come up with: assuming gcc is not allowed to
>> reason about what's inside the asm(), this is the only way I could
>> think of to lose the array information without incurring unnecessary
>> overheads. It should also be relatively safe as there is no way to
>> accidentally use the underlying arrays without explicitly declaring
>> them.
> 
> Ugh. I worry about the other places where we do things like this,
> depending on the linker just assigning the addresses and us being able
> to compare them.
> 
> If there is a compiler option to disable this optimization, I would
> almost prefer that.. Because we really do have a whole slew of these
> things.

Any update on this? Couple months later and I still hit this.

Quick checking shows, that a lot code depends on comparing two arrays
(undefined behaviour):
ftrace_init
  count = __stop_mcount_loc - __start_mcount_loc;
tracer_alloc_buffers
  if (__stop___trace_bprintk_fmt != __start___trace_bprintk_fmt)


FWIW this indeed fixes the get_builtin_firmware case for me:
--- a/arch/x86/kernel/cpu/microcode/core.c
+++ b/arch/x86/kernel/cpu/microcode/core.c
@@ -97,9 +97,11 @@ extern struct builtin_fw __end_builtin_fw[];
 bool get_builtin_firmware(struct cpio_data *cd, const char *name)
 {
 #ifdef CONFIG_FW_LOADER
-       struct builtin_fw *b_fw;
+       struct builtin_fw *b_fw = __start_builtin_fw;

-       for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {
+       OPTIMIZER_HIDE_VAR(b_fw);
+
+       for (; b_fw != __end_builtin_fw; b_fw++) {
                if (!strcmp(name, b_fw->name)) {
                        cd->size = b_fw->size;
                        cd->data = b_fw->data;



What about adding:
#define for_each_vmlinux_symbol(sym, start, stop) \
  for (sym = start, OPTIMIZER_HIDE_VAR(sym); sym != stop; sym++)

and converting at least the iterators?

What to do with the array subtractions and comparisons (like tracing), I
don't know (yet).

thanks,
-- 
js
suse labs

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Vegard Nossum]

On 10/14/2016 07:52 AM, Jiri Slaby wrote:
> On 06/26/2016, 07:17 PM, Linus Torvalds wrote:
>> On Sun, Jun 26, 2016 at 2:24 AM, Vegard Nossum <vegard.nossum@gmail.com> wrote:
>>>
>>> This is the best I could come up with: assuming gcc is not allowed to
>>> reason about what's inside the asm(), this is the only way I could
>>> think of to lose the array information without incurring unnecessary
>>> overheads. It should also be relatively safe as there is no way to
>>> accidentally use the underlying arrays without explicitly declaring
>>> them.
>>
>> Ugh. I worry about the other places where we do things like this,
>> depending on the linker just assigning the addresses and us being able
>> to compare them.
>>
>> If there is a compiler option to disable this optimization, I would
>> almost prefer that.. Because we really do have a whole slew of these
>> things.
>
> Any update on this? Couple months later and I still hit this.

I didn't find any compiler flags or anything that would let us get by
with the current code.

I have a branch fixing a bunch of these (many of them in tracing code,
like you wrote) using my old approach (declaring the arrays with a
macro) but it looks so ugly I got discouraged from submitting any of it.
I also don't have a great way to actually test a lot of the fixes.

Could something like this work?

#define DECLARE_EXTERNAL_ARRAY(type, name) \
	extern type __##name##_start;
	static inline type name##_start(void) \
	{ \
		type tmp = __##name##_start; \
		OPTIMIZER_HIDE_VAR(tmp); \
		return tmp; \
	} \
	static inline type name##_end(void) \
	{ \
		type tmp = __##name##_end; \
		OPTIMIZER_HIDE_VAR(tmp); \
		return tmp; \
	} \
	static inline size_t name##_size(void) \
	{ \
		return name##_end() - name##_start(); \
	}

#define ext_for_each(var, name) \
	for (var = name##_start(); var != name##_end(); var++)

and then for the firmware case you would do

DECLARE_EXTERNAL_ARRAY(struct builtin_fw, builtin_fw);

struct builtin_fw *fw;
ext_for_each(fw, builtin_fw)
	...;

You'd also have to adjust the names in the linker script accordingly.

The points here being:

1) DECLARE_*() follows the kernel convention (you get what you expect,
more or less)

2) the real variables defined in the linker script are hidden behind
some generated names so you don't use them by accident

3) no need to sprinkle your code with OPTIMIZER_HIDE_VAR() or anything
else, but you do need to use function calls to access the variables
(e.g. firmware_start() and firmware_end()).

What do you think?


Vegard

Re: [PATCH] firmware: declare __{start,end}_builtin_fw as pointers

[Jiri Slaby]

On 10/14/2016, 08:25 AM, Vegard Nossum wrote:
> On 10/14/2016 07:52 AM, Jiri Slaby wrote:
>> On 06/26/2016, 07:17 PM, Linus Torvalds wrote:
>>> On Sun, Jun 26, 2016 at 2:24 AM, Vegard Nossum
>>> <vegard.nossum@gmail.com> wrote:
>>>>
>>>> This is the best I could come up with: assuming gcc is not allowed to
>>>> reason about what's inside the asm(), this is the only way I could
>>>> think of to lose the array information without incurring unnecessary
>>>> overheads. It should also be relatively safe as there is no way to
>>>> accidentally use the underlying arrays without explicitly declaring
>>>> them.
>>>
>>> Ugh. I worry about the other places where we do things like this,
>>> depending on the linker just assigning the addresses and us being able
>>> to compare them.
>>>
>>> If there is a compiler option to disable this optimization, I would
>>> almost prefer that.. Because we really do have a whole slew of these
>>> things.
>>
>> Any update on this? Couple months later and I still hit this.
> 
> I didn't find any compiler flags or anything that would let us get by
> with the current code.

FWIW, this changed with 73447cc5d17 in gcc. There are no flags added by
the commit, so I assume this sole optimization cannot be turned off.

> I have a branch fixing a bunch of these (many of them in tracing code,
> like you wrote) using my old approach (declaring the arrays with a
> macro) but it looks so ugly I got discouraged from submitting any of it.
> I also don't have a great way to actually test a lot of the fixes.
> 
> Could something like this work?
> 
> #define DECLARE_EXTERNAL_ARRAY(type, name) \
>     extern type __##name##_start;
>     static inline type name##_start(void) \
>     { \
>         type tmp = __##name##_start; \
>         OPTIMIZER_HIDE_VAR(tmp); \
>         return tmp; \
>     } \
>     static inline type name##_end(void) \
>     { \
>         type tmp = __##name##_end; \
>         OPTIMIZER_HIDE_VAR(tmp); \
>         return tmp; \
>     } \
>     static inline size_t name##_size(void) \
>     { \
>         return name##_end() - name##_start(); \
>     }
> 
> #define ext_for_each(var, name) \
>     for (var = name##_start(); var != name##_end(); var++)
> 
> and then for the firmware case you would do
> 
> DECLARE_EXTERNAL_ARRAY(struct builtin_fw, builtin_fw);
> 
> struct builtin_fw *fw;
> ext_for_each(fw, builtin_fw)
>     ...;
> 
> You'd also have to adjust the names in the linker script accordingly.
> 
> The points here being:
> 
> 1) DECLARE_*() follows the kernel convention (you get what you expect,
> more or less)
> 
> 2) the real variables defined in the linker script are hidden behind
> some generated names so you don't use them by accident
> 
> 3) no need to sprinkle your code with OPTIMIZER_HIDE_VAR() or anything
> else, but you do need to use function calls to access the variables
> (e.g. firmware_start() and firmware_end()).
> 
> What do you think?

FWIW LGTM

thanks,
-- 
js
suse labs