[PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[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.

This is 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.

Apparently similar optimizations were observed on NetBSD for GCC 5.4:
http://mail-index.netbsd.org/netbsd-bugs/2016/06/22/msg047136.html

We can lose the array information about a pointer using
OPTIMIZER_HIDE_VAR().

Additional points on the design of this interface:

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. ext_start(builtin_fw) and ext_end(builtin_fw)).

Reported-by: Jiri Slaby <jslaby@suse.cz>
Cc: stable@vger.kernel.org
Cc: Ming Lei <ming.lei@canonical.com>
Cc: Steven Rostedt <srostedt@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
---
 include/linux/extarray.h | 65 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)
 create mode 100644 include/linux/extarray.h

diff --git a/include/linux/extarray.h b/include/linux/extarray.h
new file mode 100644
index 0000000..1185abc
--- /dev/null
+++ b/include/linux/extarray.h
@@ -0,0 +1,65 @@
+#ifndef LINUX_EXTARRAY_H
+#define LINUX_EXTARRAY_H
+
+#include <linux/compiler.h>
+
+/*
+ * A common pattern in the kernel is to put certain objects in a specific
+ * named section and then create variables in the linker script pointing
+ * to the start and the end of this section. These variables are declared
+ * as extern arrays to allow C code to iterate over the list of objects.
+ *
+ * In C, comparing pointers to objects in two different arrays is undefined.
+ * GCC version 7.0 and newer (commit 73447cc5d17) will aggressively optimize
+ * out such comparisons if it can prove that the two pointers point to
+ * different arrays (which is the case when the arrays are declared as two
+ * separate variables). This breaks the typical code used to iterate over
+ * such arrays.
+ *
+ * One way to get around this limitation is to force GCC to lose any array
+ * information about the pointers before we compare them. We can use e.g.
+ * OPTIMIZER_HIDE_VAR() for this.
+ *
+ * This file defines a few helpers to deal with declaring and accessing
+ * such linker-script-defined arrays.
+ */
+
+
+#define DECLARE_EXTARRAY(type, name)					\
+	extern type __start_##name[];					\
+	extern type __stop_##name[];					\
+
+#define _ext_start(name, tmp) \
+	({								\
+		typeof(*__start_##name) *tmp = __start_##name;		\
+		OPTIMIZER_HIDE_VAR(tmp);				\
+		tmp;							\
+	})
+
+#define ext_start(name) _ext_start(name, __UNIQUE_ID(ext_start_))
+
+#define _ext_end(name, tmp)						\
+	({								\
+		typeof(*__stop_##name) *tmp = __stop_##name;		\
+		OPTIMIZER_HIDE_VAR(tmp);				\
+		tmp;							\
+	})
+
+#define ext_end(name) _ext_end(name, __UNIQUE_ID(ext_end_))
+
+#define _ext_size(name, tmp1, tmp2)					\
+	({								\
+		typeof(*__start_##name) *tmp1 = __start_##name;		\
+		typeof(*__stop_##name) *tmp2 = __stop_##name;		\
+		OPTIMIZER_HIDE_VAR(tmp1);				\
+		OPTIMIZER_HIDE_VAR(tmp2);				\
+		tmp2 - tmp1;						\
+	})
+
+#define ext_size(name) \
+	_ext_size(name, __UNIQUE_ID(ext_size1_), __UNIQUE_ID(ext_size2_))
+
+#define ext_for_each(var, name) \
+	for (var = ext_start(name); var != ext_end(name); var++)
+
+#endif
-- 
2.10.0.479.g221bd91

[PATCH 02/12] firmware: declare {__start,__end}_builtin_fw as external array

[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().

By using the new external array helper macros we get the expected
behaviour.

Reported-by: Jiri Slaby <jslaby@suse.cz>
Cc: Dmitry Torokhov <dmitry.torokhov@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: stable@vger.kernel.org
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
---
 arch/x86/kernel/cpu/microcode/core.c | 5 ++---
 drivers/base/firmware_class.c        | 9 +++++----
 include/asm-generic/vmlinux.lds.h    | 2 +-
 3 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/arch/x86/kernel/cpu/microcode/core.c b/arch/x86/kernel/cpu/microcode/core.c
index 5ce5155..6669746 100644
--- a/arch/x86/kernel/cpu/microcode/core.c
+++ b/arch/x86/kernel/cpu/microcode/core.c
@@ -91,15 +91,14 @@ static bool __init check_loader_disabled_bsp(void)
 	return *res;
 }
 
-extern struct builtin_fw __start_builtin_fw[];
-extern struct builtin_fw __end_builtin_fw[];
+DECLARE_EXTARRAY(struct builtin_fw, builtin_fw);
 
 bool get_builtin_firmware(struct cpio_data *cd, const char *name)
 {
 #ifdef CONFIG_FW_LOADER
 	struct builtin_fw *b_fw;
 
-	for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {
+	ext_for_each(b_fw, builtin_fw) {
 		if (!strcmp(name, b_fw->name)) {
 			cd->size = b_fw->size;
 			cd->data = b_fw->data;
diff --git a/drivers/base/firmware_class.c b/drivers/base/firmware_class.c
index 22d1760..b85d943e6 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/extarray.h>
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/timer.h>
@@ -43,15 +44,14 @@ MODULE_LICENSE("GPL");
 
 #ifdef CONFIG_FW_LOADER
 
-extern struct builtin_fw __start_builtin_fw[];
-extern struct builtin_fw __end_builtin_fw[];
+DECLARE_EXTARRAY(struct builtin_fw, builtin_fw)
 
 static bool fw_get_builtin_firmware(struct firmware *fw, const char *name,
 				    void *buf, size_t size)
 {
 	struct builtin_fw *b_fw;
 
-	for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++) {
+	ext_for_each(b_fw, builtin_fw) {
 		if (strcmp(name, b_fw->name) == 0) {
 			fw->size = b_fw->size;
 			fw->data = b_fw->data;
@@ -69,9 +69,10 @@ static bool fw_is_builtin_firmware(const struct firmware *fw)
 {
 	struct builtin_fw *b_fw;
 
-	for (b_fw = __start_builtin_fw; b_fw != __end_builtin_fw; b_fw++)
+	ext_for_each(b_fw, builtin_fw) {
 		if (fw->data == b_fw->data)
 			return true;
+	}
 
 	return false;
 }
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index 3074796..d6121ac 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -317,7 +317,7 @@
 	.builtin_fw        : AT(ADDR(.builtin_fw) - LOAD_OFFSET) {	\
 		VMLINUX_SYMBOL(__start_builtin_fw) = .;			\
 		*(.builtin_fw)						\
-		VMLINUX_SYMBOL(__end_builtin_fw) = .;			\
+		VMLINUX_SYMBOL(__stop_builtin_fw) = .;			\
 	}								\
 									\
 	TRACEDATA							\
-- 
2.10.0.479.g221bd91

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Greg Kroah-Hartman]

On Sun, Oct 16, 2016 at 05:16:05PM +0200, Vegard Nossum 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.
> 
> This is 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.
> 
> Apparently similar optimizations were observed on NetBSD for GCC 5.4:
> http://mail-index.netbsd.org/netbsd-bugs/2016/06/22/msg047136.html
> 
> We can lose the array information about a pointer using
> OPTIMIZER_HIDE_VAR().
> 
> Additional points on the design of this interface:
> 
> 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. ext_start(builtin_fw) and ext_end(builtin_fw)).
> 
> Reported-by: Jiri Slaby <jslaby@suse.cz>
> Cc: stable@vger.kernel.org
> Cc: Ming Lei <ming.lei@canonical.com>
> Cc: Steven Rostedt <srostedt@redhat.com>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
> ---
>  include/linux/extarray.h | 65 ++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 65 insertions(+)
>  create mode 100644 include/linux/extarray.h
> 
> diff --git a/include/linux/extarray.h b/include/linux/extarray.h
> new file mode 100644
> index 0000000..1185abc
> --- /dev/null
> +++ b/include/linux/extarray.h
> @@ -0,0 +1,65 @@
> +#ifndef LINUX_EXTARRAY_H
> +#define LINUX_EXTARRAY_H
> +
> +#include <linux/compiler.h>
> +
> +/*
> + * A common pattern in the kernel is to put certain objects in a specific
> + * named section and then create variables in the linker script pointing
> + * to the start and the end of this section. These variables are declared
> + * as extern arrays to allow C code to iterate over the list of objects.
> + *
> + * In C, comparing pointers to objects in two different arrays is undefined.
> + * GCC version 7.0 and newer (commit 73447cc5d17) will aggressively optimize
> + * out such comparisons if it can prove that the two pointers point to
> + * different arrays (which is the case when the arrays are declared as two
> + * separate variables). This breaks the typical code used to iterate over
> + * such arrays.
> + *
> + * One way to get around this limitation is to force GCC to lose any array
> + * information about the pointers before we compare them. We can use e.g.
> + * OPTIMIZER_HIDE_VAR() for this.
> + *
> + * This file defines a few helpers to deal with declaring and accessing
> + * such linker-script-defined arrays.
> + */
> +
> +
> +#define DECLARE_EXTARRAY(type, name)					\
> +	extern type __start_##name[];					\
> +	extern type __stop_##name[];					\

"EXTARRAY" kind of gives a good hint as to what is going on, but why not
just spell the thing out, "DECLARE_EXTERNAL_ARRAY()"?

> +#define _ext_start(name, tmp) \
> +	({								\
> +		typeof(*__start_##name) *tmp = __start_##name;		\
> +		OPTIMIZER_HIDE_VAR(tmp);				\
> +		tmp;							\
> +	})
> +
> +#define ext_start(name) _ext_start(name, __UNIQUE_ID(ext_start_))
> +
> +#define _ext_end(name, tmp)						\
> +	({								\
> +		typeof(*__stop_##name) *tmp = __stop_##name;		\
> +		OPTIMIZER_HIDE_VAR(tmp);				\
> +		tmp;							\
> +	})
> +
> +#define ext_end(name) _ext_end(name, __UNIQUE_ID(ext_end_))
> +
> +#define _ext_size(name, tmp1, tmp2)					\
> +	({								\
> +		typeof(*__start_##name) *tmp1 = __start_##name;		\
> +		typeof(*__stop_##name) *tmp2 = __stop_##name;		\
> +		OPTIMIZER_HIDE_VAR(tmp1);				\
> +		OPTIMIZER_HIDE_VAR(tmp2);				\
> +		tmp2 - tmp1;						\
> +	})
> +
> +#define ext_size(name) \
> +	_ext_size(name, __UNIQUE_ID(ext_size1_), __UNIQUE_ID(ext_size2_))
> +
> +#define ext_for_each(var, name) \
> +	for (var = ext_start(name); var != ext_end(name); var++)

"ext_" is also vague, and hard to know what this is at first glance when
reading code.  Again, we have lots of characters, let's use them.
"external_array_for_each()"?

thanks,

greg k-h

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Sun, Oct 16, 2016 at 05:16:05PM +0200, Vegard Nossum 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.
> 
> This is 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.
> 

Urgh, isn't that the kind of 'optimizations' we should shoot in the head
for the kernel? Just like the -fno-strict-aliassing crap?

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Jiri Slaby]

On 10/17/2016, 10:33 AM, Peter Zijlstra wrote:
> On Sun, Oct 16, 2016 at 05:16:05PM +0200, Vegard Nossum 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.
>>
>> This is 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.
>>
> 
> Urgh, isn't that the kind of 'optimizations' we should shoot in the head
> for the kernel? Just like the -fno-strict-aliassing crap?

Unfortunately, there is no such switch for this optimization.

On the top of that, it's incorrect C according to the standard. So it is
as correct as expecting 0 printed here: 'int zero; printf("%d\n",
zero);'. It never worked, not even with gcc 4 and maybe older. We were
just lucky.

thanks,
-- 
js
suse labs

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
> On 10/17/2016, 10:33 AM, Peter Zijlstra wrote:
> > On Sun, Oct 16, 2016 at 05:16:05PM +0200, Vegard Nossum 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.
> >>
> >> This is 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.
> >>
> > 
> > Urgh, isn't that the kind of 'optimizations' we should shoot in the head
> > for the kernel? Just like the -fno-strict-aliassing crap?
> 
> Unfortunately, there is no such switch for this optimization.

Should we get one?

> On the top of that, it's incorrect C according to the standard. 

According to the standard non of the kernel has any chance in hell of
working, so don't pretend you care about that :-)

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Vegard Nossum]

On 10/17/2016 11:09 AM, Peter Zijlstra wrote:
> On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
>> On the top of that, it's incorrect C according to the standard.
>
> According to the standard non of the kernel has any chance in hell of
> working, so don't pretend you care about that :-)

I think that's a bit of a false dilemma. It's obviously true that kernel
code does not conform to the standards, but that doesn't mean it's not
something we should strive towards or care about in general. It helps
static analysis tools, compiler diversity, etc.


Vegard

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Mon, Oct 17, 2016 at 01:27:08PM +0200, Vegard Nossum wrote:
> On 10/17/2016 11:09 AM, Peter Zijlstra wrote:
> >On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
> >>On the top of that, it's incorrect C according to the standard.
> >
> >According to the standard non of the kernel has any chance in hell of
> >working, so don't pretend you care about that :-)
> 
> I think that's a bit of a false dilemma. It's obviously true that kernel
> code does not conform to the standards, but that doesn't mean it's not
> something we should strive towards or care about in general. It helps
> static analysis tools, compiler diversity, etc.

Sure, but this, two separately allocated objects their address should
not be compared and therefore... stuff is explicitly relied upon by the
kernel in many places.

We have workarounds in various places, and this patch adds yet another
instance of it.

The workaround is simply confusing the compiler enough to have it not do
the 'optimization'. But we very much still rely on this 'undefined'
behaviour.

I think it makes more sense to explicitly allow it than to obfuscate our
code and run the risk a future compiler will see through our tricks.

I don't see how its different than explicitly disabling the
strict-aliasing muck, explicitly allowing (and 'defining') signed and
pointer overflow, doing all the concurrency stuff on our own (gnu89
emphatically does _not_ have a memory model) etc..

And given GCC7 is still in development, this might be a good time to get
a knob added for our benefit.

Are we 'modifying' the C language, sure, but that ship has sailed long
ago.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Vegard Nossum]

On 10/17/2016 01:45 PM, Peter Zijlstra wrote:
> On Mon, Oct 17, 2016 at 01:27:08PM +0200, Vegard Nossum wrote:
>> On 10/17/2016 11:09 AM, Peter Zijlstra wrote:
>>> On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
>>>> On the top of that, it's incorrect C according to the standard.
>>>
>>> According to the standard non of the kernel has any chance in hell of
>>> working, so don't pretend you care about that :-)
>>
>> I think that's a bit of a false dilemma. It's obviously true that kernel
>> code does not conform to the standards, but that doesn't mean it's not
>> something we should strive towards or care about in general. It helps
>> static analysis tools, compiler diversity, etc.
>
> Sure, but this, two separately allocated objects their address should
> not be compared and therefore... stuff is explicitly relied upon by the
> kernel in many places.
>
> We have workarounds in various places, and this patch adds yet another
> instance of it.
>
> The workaround is simply confusing the compiler enough to have it not do
> the 'optimization'. But we very much still rely on this 'undefined'
> behaviour.
>
> I think it makes more sense to explicitly allow it than to obfuscate our
> code and run the risk a future compiler will see through our tricks.

Actually, I think we're all a bit wrong.

It's not comparing the pointers that's undefined behavior, that was my
bad trying to oversimplify the issue.

Of course, comparing arbitrary (valid) pointers with each other is not
undefined behavior. The undefined behavior is technically doing iter++
past the end of the array, that is "creating" a pointer that points
outside an array.

What gcc does wrong is that it sees us iterating over one array and the
optimizer concludes that the iterator can never point to the second
array. I'd argue there's no real undefined behaviour happening here.
Thus, the code _is_ correct and valid C as it stands, it just doesn't do
what you would expect intuitively.

However, from the linker script's point of view there is no difference
between one big array and two consecutive arrays of the same type, and
the fact that the compiler doesn't know the memory layout -- although
we do.

When we call OPTIMIZER_HIDE_VAR() we're not really "confusing" the
compiler, it's more like calling a function defined in a different file
(therefore the compiler can't see into it) that returns a pointer which
we _know_ is valid because it still points to (the end of) the array.

If we obtain a pointer somehow (be it from a hardware register or from
the stack of a userspace process), the compiler must assume that it's a
valid pointer, right? The only reason it didn't do that for the arrays
was because we had declared the two arrays as separate variables so it
"knew" it was the case that the iterator initialised to point to one
array could never point to the second array.

Anyway, IANALL.


Vegard

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Luis R. Rodriguez]

On Tue, Oct 18, 2016 at 10:08:44AM +0200, Vegard Nossum wrote:
>

Vegard, thanks for bringing this to attention!

Including this hunk for those that were originally not CC'd
on the original patch.

> diff --git a/include/linux/extarray.h b/include/linux/extarray.h
> new file mode 100644
> index 0000000..1185abc 
> --- /dev/null
> +++ b/include/linux/extarray.h
> @@ -0,0 +1,65 @@
> +#ifndef LINUX_EXTARRAY_H
> +#define LINUX_EXTARRAY_H
> +
> +#include <linux/compiler.h>
> +
> +/*
> + * A common pattern in the kernel

This is quite an understatement, as you noted on the cover letter, I've been
reviewing these uses, in particular where such uses are used also for the
linker script for quite some time now. I've devised a generic API for these
uses then to help with making it easier to add new entries, making easier
to avoid typos, and giving us some new features from this effort. This the
linker table and section range APIs [0] [1]. Given my review of all this code in
the kernel I'd say this use is not just common, its a well established practice
by now, across *all* architectures.

In fact I would not be surprised if this usage and practice has extended far
beyond the kernel by now, and custom firmwares / linker scripts also use this
to mimic the practice on the kernel to take advantage of this old hack to stuff
special code / data structures into special ELF sections. As such, I would not
think this is just an issue for Linux.

Upon a quick cursory review I can confirm such use is prevalent in Xen as well,
for instance the Xen Security Module framework uses it since eons ago [2]. Its
used elsewhere on the Xen linker script too though... so XSM is one small
example at a *quick* glance.

[0] https://lkml.kernel.org/r/1471642875-5957-1-git-send-email-mcgrof@kernel.org
[1] https://lkml.kernel.org/r/1471642454-5679-1-git-send-email-mcgrof@kernel.org
[2] https://xenbits.xen.org/gitweb/?p=xen.git;a=commitdiff;h=d046f361dc937d8fc179cc2da168f571726cb5a0

> +   is to put certain objects in a specific
> + * named section and then create variables in the linker script pointing
> + * to the start and the end of this section. These variables are declared
> + * as extern arrays to allow C code to iterate over the list of objects

Right, sometimes its just a char pointer to represent code, other times it
custom data structure.

> + *
> + * In C, comparing pointers to objects in two different arrays is undefined
> + * GCC version 7.0 and newer (commit 73447cc5d17) will aggressively optimize
> + * out such comparisons if it can prove that the two pointers point to
> + * different arrays (which is the case when the arrays are declared as two
> + * separate variables). This breaks the typical code used to iterate over
> + * such arrays.

Eek, thanks, I checked commit 73447cc5d17 on gcc [2] however its commit log
is pretty vague to me and does not seem to justify why exactly this optimization
is done, nor what effort was put in to vet for it, as such I cannot agree or
disagree with it. Logically though, to me these are just pointers, as such,
its not clear to me why gcc can take such optimization to make such assumptions.

Since I cannot infer any more from this commit, and given how prevalent I
expect this use to be (clearly even outside of Linux) I am inclined to consider
this a gcc bug, which requires at least an opt-in optimization rather than this
being a default. Had anyone reported this ??

Richard ?

[2] https://github.com/gcc-mirror/gcc/commit/73447cc5d17

> + *
> + * One way to get around this limitation is to force GCC to lose any array
> + * information about the pointers before we compare them. We can use e.g.
> + * OPTIMIZER_HIDE_VAR() for this.

As far as Linux is concerned though your patch set addresses covering a few
cases, it does not cover all, so while it might help boot x86 on some type of
system, by no means would I expect it suffice to boot all Linux systems.
Additionally,  while  it may  *fix*  boot on x86, are we certain the use of
OPTIMIZER_HIDE_VAR() may not *break* on certain platforms ? I would ask such
type of intrusive changes which affect the linker script to go well beyond
just 0-day for testing -- Guenter Roeck was kind enough to let me test my
series for linker table / section ranges on his infrastructure which covers
much architectures and toolchains not addressed by 0-day. I'd expect such type
of testing for these types of changes, which can affect many architectures.

Additionally you asked for this to series to be considered a stable
patch, if this just fixes x86 boot, but breaks other architecture it would
be a considerable regression. I'd prefer we first determine if we want this
change reverted on gcc, or if it at least can be disabled by default.
I really do expect shit to hit the fan elsewhere, so this work around
doesn't same like the next best step at this point.

> + *
> + * This file defines a few helpers to deal with declaring and accessing
> + * such linker-script-defined arrays.
> + */
> +
> +
> +#define DECLARE_EXTARRAY(type, name)                                   \
> +       extern type __start_##name[];                                   \
> +       extern type __stop_##name[];                                    \
> +
> +#define _ext_start(name, tmp) \
> +       ({                                                              \
> +               typeof(*__start_##name) *tmp = __start_##name;          \
> +               OPTIMIZER_HIDE_VAR(tmp);                                \
> +               tmp;                                                    \
> +       })
> +
> +#define ext_start(name) _ext_start(name, __UNIQUE_ID(ext_start_))
> +
> +#define _ext_end(name, tmp)                                            \
> +       ({                                                              \
> +               typeof(*__stop_##name) *tmp = __stop_##name;            \
> +               OPTIMIZER_HIDE_VAR(tmp);                                \
> +               tmp;                                                    \
> +       })
> +
> +#define ext_end(name) _ext_end(name, __UNIQUE_ID(ext_end_))
> +
> +#define _ext_size(name, tmp1, tmp2)                                    \
> +       ({                                                              \
> +               typeof(*__start_##name) *tmp1 = __start_##name;         \
> +               typeof(*__stop_##name) *tmp2 = __stop_##name;           \
> +               OPTIMIZER_HIDE_VAR(tmp1);                               \
> +               OPTIMIZER_HIDE_VAR(tmp2);                               \
> +               tmp2 - tmp1;                                            \
> +       })
> +
> +#define ext_size(name) \
> +       _ext_size(name, __UNIQUE_ID(ext_size1_), __UNIQUE_ID(ext_size2_))
> +
> +#define ext_for_each(var, name) \
> +       for (var = ext_start(name); var != ext_end(name); var++)
> +
> +#endif

FWIW, with linker able we'd do this type of "fix" in one place later,
if we wanted it, provided all uses are ported, of course.

> On 10/17/2016 01:45 PM, Peter Zijlstra wrote:
> > On Mon, Oct 17, 2016 at 01:27:08PM +0200, Vegard Nossum wrote:
> > > On 10/17/2016 11:09 AM, Peter Zijlstra wrote:
> > > > On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
> > > > > On the top of that, it's incorrect C according to the standard.
> > > > 
> > > > According to the standard non of the kernel has any chance in hell of
> > > > working, so don't pretend you care about that :-)
> > > 
> > > I think that's a bit of a false dilemma. It's obviously true that kernel
> > > code does not conform to the standards, but that doesn't mean it's not
> > > something we should strive towards or care about in general. It helps
> > > static analysis tools, compiler diversity, etc.
> > 
> > Sure, but this, two separately allocated objects their address should
> > not be compared and therefore... stuff is explicitly relied upon by the
> > kernel in many places.
> > 
> > We have workarounds in various places, and this patch adds yet another
> > instance of it.
> > 
> > The workaround is simply confusing the compiler enough to have it not do
> > the 'optimization'. But we very much still rely on this 'undefined'
> > behaviour.
> > 
> > I think it makes more sense to explicitly allow it than to obfuscate our
> > code and run the risk a future compiler will see through our tricks.
> 
> Actually, I think we're all a bit wrong.
> 
> It's not comparing the pointers that's undefined behavior, that was my
> bad trying to oversimplify the issue.
> 
> Of course, comparing arbitrary (valid) pointers with each other is not
> undefined behavior. The undefined behavior is technically doing iter++
> past the end of the array,

What defines the end of the array?

> that is "creating" a pointer that points outside an array.

I mean, its just a pointer.

This is the sort of information that would be useful for the commit log.

> What gcc does wrong is that it sees us iterating over one array and the
> optimizer concludes that the iterator can never point to the second
> array.

Which second array? Why does it make this huge assumption ?

> I'd argue there's no real undefined behaviour happening here.
> Thus, the code _is_ correct and valid C as it stands, it just doesn't do
> what you would expect intuitively.

People have relied on its functionality for years, if this is going
to change it would be I think a good idea to at least have a strong
justification rather than having us trying to interpret the original
goal of the gcc patch.

> However, from the linker script's point of view there is no difference
> between one big array and two consecutive arrays of the same type, and
> the fact that the compiler doesn't know the memory layout -- although
> we do.

In Linux we don't mix/match pointer types, we typically use two char *
pointers for start/end of code, or a data structure pointers for start/
end of list, that's it. Its not clear to me why gcc believes it is correct
to assume start != end.

> When we call OPTIMIZER_HIDE_VAR() we're not really "confusing" the
> compiler, it's more like calling a function defined in a different file
> (therefore the compiler can't see into it) that returns a pointer which
> we _know_ is valid because it still points to (the end of) the array.

Its a hack to work around the optimization, if we are to do this I think
its important we all first understand *why* the original commit was done,
without this - it would seem the current optimization will just go breaking
quite a bit of projects. Your changeset would also require much more work
(or we port things to the linker table / section ranges API, and just do the
fix with those wrappers, as it would mean 1 collateral evolution rather than 2
-- one for this fix and then one for the linker table API).

> If we obtain a pointer somehow (be it from a hardware register or from
> the stack of a userspace process), the compiler must assume that it's a
> valid pointer, right? The only reason it didn't do that for the arrays
> was because we had declared the two arrays as separate variables so it
> "knew" it was the case that the iterator initialised to point to one
> array could never point to the second array.

But why is this invalid C all of a sudden with optimizations ?

foo.h:

extern char *start_foo;
extern char *end_foo;

foo.c:

#include "foo.h"

char *str = "hello";                                                            

char *start_foo;
char *end_foo;

int main(void)
{
	start_foo = str;                                                        
	end_foo = str;                                                          

	return !(start_foo == end_foo);
}

> Anyway, IANALL.

IGINYA - I guess I'm not young anymore, what's IANALL mean? :)

  Luis

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Jiri Slaby]

On 10/17/2016, 01:45 PM, Peter Zijlstra wrote:
> And given GCC7 is still in development, this might be a good time to get
> a knob added for our benefit.

I tried and failed, see below. Citing from:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77964

(In reply to Jiri Slaby from comment #16)
> (In reply to Jakub Jelinek from comment #15)
> > lots of them that rely on pointer arithmetics being defined only
within the
> > same object.
>
> Sure, but the two pointers (taken implicitly of the arrays) are within the
> same object. So I do not see, why it wouldn't work? I.e. where exactly
this
> breaks the C specs?

No.  In C
extern struct builtin_fw __start_builtin_fw[];
extern struct builtin_fw __end_builtin_fw[];
declares two external arrays, thus they are two independent objects.  It
is like if you have:
int a[10];
int b[10];
in your program, although they might be allocated adjacent, such that
int *p = &a[10]; int *q = &b[0]; memcmp (&p, &q, sizeof (p)) == 0;
&b[0] - &a[0] is still UB.
What you do with __start_*/__end_* symbols is nothing you can define in
C, you need linker support or asm for that, and to use it without UB you
also need to use an optimization barrier that has been suggested.

==============================

> And given gcc 7 is to be released yet, can we have a switch to disable
this
> optimization?

This is nothing new in GCC 7, you've most likely just been extremely
lucky in the past that it happened to work as you expected.  Other
projects had to change similar UB code years ago.  It isn't just a
single optimization, but lots of them that rely on pointer arithmetics
being defined only within the same object.


-- 
js
suse labs

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Richard Biener]

On Tue, 18 Oct 2016, Luis R. Rodriguez wrote:

> On Tue, Oct 18, 2016 at 10:08:44AM +0200, Vegard Nossum wrote:
> >
> 
> Vegard, thanks for bringing this to attention!
> 
> Including this hunk for those that were originally not CC'd
> on the original patch.
> 
> > diff --git a/include/linux/extarray.h b/include/linux/extarray.h
> > new file mode 100644
> > index 0000000..1185abc 
> > --- /dev/null
> > +++ b/include/linux/extarray.h
> > @@ -0,0 +1,65 @@
> > +#ifndef LINUX_EXTARRAY_H
> > +#define LINUX_EXTARRAY_H
> > +
> > +#include <linux/compiler.h>
> > +
> > +/*
> > + * A common pattern in the kernel
> 
> This is quite an understatement, as you noted on the cover letter, I've been
> reviewing these uses, in particular where such uses are used also for the
> linker script for quite some time now. I've devised a generic API for these
> uses then to help with making it easier to add new entries, making easier
> to avoid typos, and giving us some new features from this effort. This the
> linker table and section range APIs [0] [1]. Given my review of all this code in
> the kernel I'd say this use is not just common, its a well established practice
> by now, across *all* architectures.
> 
> In fact I would not be surprised if this usage and practice has extended far
> beyond the kernel by now, and custom firmwares / linker scripts also use this
> to mimic the practice on the kernel to take advantage of this old hack to stuff
> special code / data structures into special ELF sections. As such, I would not
> think this is just an issue for Linux.
> 
> Upon a quick cursory review I can confirm such use is prevalent in Xen as well,
> for instance the Xen Security Module framework uses it since eons ago [2]. Its
> used elsewhere on the Xen linker script too though... so XSM is one small
> example at a *quick* glance.
> 
> [0] https://lkml.kernel.org/r/1471642875-5957-1-git-send-email-mcgrof@kernel.org
> [1] https://lkml.kernel.org/r/1471642454-5679-1-git-send-email-mcgrof@kernel.org
> [2] https://xenbits.xen.org/gitweb/?p=xen.git;a=commitdiff;h=d046f361dc937d8fc179cc2da168f571726cb5a0
> 
> > +   is to put certain objects in a specific
> > + * named section and then create variables in the linker script pointing
> > + * to the start and the end of this section. These variables are declared
> > + * as extern arrays to allow C code to iterate over the list of objects
> 
> Right, sometimes its just a char pointer to represent code, other times it
> custom data structure.
> 
> > + *
> > + * In C, comparing pointers to objects in two different arrays is undefined
> > + * GCC version 7.0 and newer (commit 73447cc5d17) will aggressively optimize
> > + * out such comparisons if it can prove that the two pointers point to
> > + * different arrays (which is the case when the arrays are declared as two
> > + * separate variables). This breaks the typical code used to iterate over
> > + * such arrays.
> 
> Eek, thanks, I checked commit 73447cc5d17 on gcc [2] however its commit log
> is pretty vague to me and does not seem to justify why exactly this optimization
> is done, nor what effort was put in to vet for it, as such I cannot agree or
> disagree with it. Logically though, to me these are just pointers, as such,
> its not clear to me why gcc can take such optimization to make such assumptions.
> 
> Since I cannot infer any more from this commit, and given how prevalent I
> expect this use to be (clearly even outside of Linux) I am inclined to consider
> this a gcc bug, which requires at least an opt-in optimization rather than this
> being a default. Had anyone reported this ??
> 
> Richard ?

The commit implements a long-standing failure to optimize trivial pointer
comparisons that arise for example from libstdc++.  PR65686 contains
a simple C example:

mytype f(struct S *e)
{
  mytype x;
  if(&x != e->pu)
    __builtin_memcpy(&x, e->pu, sizeof(unsigned));
  return x;
}

where GCC before the commit could not optimize the &x != e->pu test
as trivial false.

The commit uses points-to analysis results to simplify pointer equality
tests (which is in itself a very good way to expose bugs in points-to
analysis -- I've fixed a bunch of them thanks to this ;)).

> [2] https://github.com/gcc-mirror/gcc/commit/73447cc5d17
> 
> > + *
> > + * One way to get around this limitation is to force GCC to lose any array
> > + * information about the pointers before we compare them. We can use e.g.
> > + * OPTIMIZER_HIDE_VAR() for this.
> 
> As far as Linux is concerned though your patch set addresses covering a few
> cases, it does not cover all, so while it might help boot x86 on some type of
> system, by no means would I expect it suffice to boot all Linux systems.
> Additionally,  while  it may  *fix*  boot on x86, are we certain the use of
> OPTIMIZER_HIDE_VAR() may not *break* on certain platforms ? I would ask such
> type of intrusive changes which affect the linker script to go well beyond
> just 0-day for testing -- Guenter Roeck was kind enough to let me test my
> series for linker table / section ranges on his infrastructure which covers
> much architectures and toolchains not addressed by 0-day. I'd expect such type
> of testing for these types of changes, which can affect many architectures.
> 
> Additionally you asked for this to series to be considered a stable
> patch, if this just fixes x86 boot, but breaks other architecture it would
> be a considerable regression. I'd prefer we first determine if we want this
> change reverted on gcc, or if it at least can be disabled by default.
> I really do expect shit to hit the fan elsewhere, so this work around
> doesn't same like the next best step at this point.
> 
> > + *
> > + * This file defines a few helpers to deal with declaring and accessing
> > + * such linker-script-defined arrays.
> > + */
> > +
> > +
> > +#define DECLARE_EXTARRAY(type, name)                                   \
> > +       extern type __start_##name[];                                   \
> > +       extern type __stop_##name[];                                    \
> > +
> > +#define _ext_start(name, tmp) \
> > +       ({                                                              \
> > +               typeof(*__start_##name) *tmp = __start_##name;          \
> > +               OPTIMIZER_HIDE_VAR(tmp);                                \
> > +               tmp;                                                    \
> > +       })
> > +
> > +#define ext_start(name) _ext_start(name, __UNIQUE_ID(ext_start_))
> > +
> > +#define _ext_end(name, tmp)                                            \
> > +       ({                                                              \
> > +               typeof(*__stop_##name) *tmp = __stop_##name;            \
> > +               OPTIMIZER_HIDE_VAR(tmp);                                \
> > +               tmp;                                                    \
> > +       })
> > +
> > +#define ext_end(name) _ext_end(name, __UNIQUE_ID(ext_end_))
> > +
> > +#define _ext_size(name, tmp1, tmp2)                                    \
> > +       ({                                                              \
> > +               typeof(*__start_##name) *tmp1 = __start_##name;         \
> > +               typeof(*__stop_##name) *tmp2 = __stop_##name;           \
> > +               OPTIMIZER_HIDE_VAR(tmp1);                               \
> > +               OPTIMIZER_HIDE_VAR(tmp2);                               \
> > +               tmp2 - tmp1;                                            \
> > +       })
> > +
> > +#define ext_size(name) \
> > +       _ext_size(name, __UNIQUE_ID(ext_size1_), __UNIQUE_ID(ext_size2_))
> > +
> > +#define ext_for_each(var, name) \
> > +       for (var = ext_start(name); var != ext_end(name); var++)
> > +
> > +#endif
> 
> FWIW, with linker able we'd do this type of "fix" in one place later,
> if we wanted it, provided all uses are ported, of course.
> 
> > On 10/17/2016 01:45 PM, Peter Zijlstra wrote:
> > > On Mon, Oct 17, 2016 at 01:27:08PM +0200, Vegard Nossum wrote:
> > > > On 10/17/2016 11:09 AM, Peter Zijlstra wrote:
> > > > > On Mon, Oct 17, 2016 at 11:01:13AM +0200, Jiri Slaby wrote:
> > > > > > On the top of that, it's incorrect C according to the standard.
> > > > > 
> > > > > According to the standard non of the kernel has any chance in hell of
> > > > > working, so don't pretend you care about that :-)
> > > > 
> > > > I think that's a bit of a false dilemma. It's obviously true that kernel
> > > > code does not conform to the standards, but that doesn't mean it's not
> > > > something we should strive towards or care about in general. It helps
> > > > static analysis tools, compiler diversity, etc.
> > > 
> > > Sure, but this, two separately allocated objects their address should
> > > not be compared and therefore... stuff is explicitly relied upon by the
> > > kernel in many places.
> > > 
> > > We have workarounds in various places, and this patch adds yet another
> > > instance of it.
> > > 
> > > The workaround is simply confusing the compiler enough to have it not do
> > > the 'optimization'. But we very much still rely on this 'undefined'
> > > behaviour.
> > > 
> > > I think it makes more sense to explicitly allow it than to obfuscate our
> > > code and run the risk a future compiler will see through our tricks.
> > 
> > Actually, I think we're all a bit wrong.
> > 
> > It's not comparing the pointers that's undefined behavior, that was my
> > bad trying to oversimplify the issue.
> > 
> > Of course, comparing arbitrary (valid) pointers with each other is not
> > undefined behavior. The undefined behavior is technically doing iter++
> > past the end of the array,
> 
> What defines the end of the array?
> 
> > that is "creating" a pointer that points outside an array.
> 
> I mean, its just a pointer.
> 
> This is the sort of information that would be useful for the commit log.
> 
> > What gcc does wrong is that it sees us iterating over one array and the
> > optimizer concludes that the iterator can never point to the second
> > array.
> 
> Which second array? Why does it make this huge assumption ?
> 
> > I'd argue there's no real undefined behaviour happening here.
> > Thus, the code _is_ correct and valid C as it stands, it just doesn't do
> > what you would expect intuitively.
> 
> People have relied on its functionality for years, if this is going
> to change it would be I think a good idea to at least have a strong
> justification rather than having us trying to interpret the original
> goal of the gcc patch.

The original goal of the gcc patch wasn't to break the kernel.  The
goal was to implement an optimization other compilers do since a long
time.

> > However, from the linker script's point of view there is no difference
> > between one big array and two consecutive arrays of the same type, and
> > the fact that the compiler doesn't know the memory layout -- although
> > we do.
> 
> In Linux we don't mix/match pointer types, we typically use two char *
> pointers for start/end of code, or a data structure pointers for start/
> end of list, that's it. Its not clear to me why gcc believes it is correct
> to assume start != end.
> 
> > When we call OPTIMIZER_HIDE_VAR() we're not really "confusing" the
> > compiler, it's more like calling a function defined in a different file
> > (therefore the compiler can't see into it) that returns a pointer which
> > we _know_ is valid because it still points to (the end of) the array.
> 
> Its a hack to work around the optimization, if we are to do this I think
> its important we all first understand *why* the original commit was done,
> without this - it would seem the current optimization will just go breaking
> quite a bit of projects. Your changeset would also require much more work
> (or we port things to the linker table / section ranges API, and just do the
> fix with those wrappers, as it would mean 1 collateral evolution rather than 2
> -- one for this fix and then one for the linker table API).
> 
> > If we obtain a pointer somehow (be it from a hardware register or from
> > the stack of a userspace process), the compiler must assume that it's a
> > valid pointer, right? The only reason it didn't do that for the arrays
> > was because we had declared the two arrays as separate variables so it
> > "knew" it was the case that the iterator initialised to point to one
> > array could never point to the second array.
> 
> But why is this invalid C all of a sudden with optimizations ?
> 
> foo.h:
> 
> extern char *start_foo;
> extern char *end_foo;
> 
> foo.c:
> 
> #include "foo.h"
> 
> char *str = "hello";                                                            
> 
> char *start_foo;
> char *end_foo;
> 
> int main(void)
> {
> 	start_foo = str;                                                        
> 	end_foo = str;                                                          
> 
> 	return !(start_foo == end_foo);
> }

Why should this be invalid?

Let's look at what is special about the kernel usage.  Looking
at GCC bug 77964 it is declaring

extern struct builtin_fw __start_builtin_fw[];
extern struct builtin_fw __end_builtin_fw[];

which are extern zero-sized arrays.  I suppose they are nowhere
actually defined but these symbols are created by the linker script only.

I can think of adding workarounds to GCC to try catching this
special case which would be treating a pointer to a extern
object of size zero (so you can't do this in C++ ...) as a
pointer to possibly any other global variable (given actual
data layout may make the pointer value equal to it).

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c  (revision 241327)
+++ gcc/tree-ssa-structalias.c  (working copy)
@@ -2944,6 +2944,17 @@ get_constraint_for_ssa_var (tree t, vec<
          DECL_PT_UID (t) = DECL_UID (node->decl);
          t = node->decl;
        }
+
+      /* If this is an external zero-sized object consider it to
+        point to NONLOCAL as well.  */
+      if (DECL_EXTERNAL (t)
+         && (! DECL_SIZE (t) || integer_zerop (DECL_SIZE (t))))
+       {
+         cexpr.var = nonlocal_id;
+         cexpr.type = SCALAR;
+         cexpr.offset = 0;
+         results->safe_push (cexpr);
+       }
     }
 
   vi = get_vi_for_tree (t);

Note that any issues exposed by the pointer equality simplification
are possible issues in previous GCC with regard to alias analysis.

I notice we try to honor symbol interposition when directly comparing
__start_builtin_fw != __end_builtin_fw for example.  But we certainly
do not "honor" interposition for alias analysis for, say

extern int a[1];
extern int b[1];

where a store to a[0] is not considered aliasing b[0].

Richard.

> > Anyway, IANALL.
> 
> IGINYA - I guess I'm not young anymore, what's IANALL mean? :)
> 
>   Luis
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Wed, Oct 19, 2016 at 10:18:43AM +0200, Richard Biener wrote:

> The commit implements a long-standing failure to optimize trivial pointer
> comparisons that arise for example from libstdc++.  PR65686 contains
> a simple C example:
> 
> mytype f(struct S *e)
> {
>   mytype x;
>   if(&x != e->pu)
>     __builtin_memcpy(&x, e->pu, sizeof(unsigned));
>   return x;
> }
> 
> where GCC before the commit could not optimize the &x != e->pu test
> as trivial false.

Which is fine; x is stack based and could not possibly have been handed
as the argument to this same function.

This is also an entirely different class of optimizations than the whole
pointer arithmetic is only valid inside an object thing.

The kernel very much relies on unbounded pointer arithmetic, including
overflow. Sure, C language says its UB, but we know our memory layout,
and it would be very helpful if we could define it.

Can't we get a knob extending -fno-strict-aliasing to define pointer
arithmetic outside of objects and overflow? I mean, we already use that,
we also use -fno-strict-overflow and a whole bunch of others.

At the very least, it would be nice to get a -W flag for when this alias
analysis stuff kills something so we can at least know when GCC goes and
defeats us.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Richard Biener]

On Wed, 19 Oct 2016, Peter Zijlstra wrote:

> On Wed, Oct 19, 2016 at 10:18:43AM +0200, Richard Biener wrote:
> 
> > The commit implements a long-standing failure to optimize trivial pointer
> > comparisons that arise for example from libstdc++.  PR65686 contains
> > a simple C example:
> > 
> > mytype f(struct S *e)
> > {
> >   mytype x;
> >   if(&x != e->pu)
> >     __builtin_memcpy(&x, e->pu, sizeof(unsigned));
> >   return x;
> > }
> > 
> > where GCC before the commit could not optimize the &x != e->pu test
> > as trivial false.
> 
> Which is fine; x is stack based and could not possibly have been handed
> as the argument to this same function.

Sure, it was just one example.

> This is also an entirely different class of optimizations than the whole
> pointer arithmetic is only valid inside an object thing.

Yes, it is not related to that.  I've opened 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78035 to track an
inconsistency in that new optimization.

> The kernel very much relies on unbounded pointer arithmetic, including
> overflow. Sure, C language says its UB, but we know our memory layout,
> and it would be very helpful if we could define it.

It's well-defined and correctly handled if you do the arithmetic
in uintptr_t.  No need for knobs.

> Can't we get a knob extending -fno-strict-aliasing to define pointer
> arithmetic outside of objects and overflow? I mean, we already use that,
> we also use -fno-strict-overflow and a whole bunch of others.
> 
> At the very least, it would be nice to get a -W flag for when this alias
> analysis stuff kills something so we can at least know when GCC goes and
> defeats us.

What kind of warning do you envision?

"warning: optimized address comparison to always true/false"

?  That would trigger all over the place.

Richard.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Wed, Oct 19, 2016 at 11:33:41AM +0200, Richard Biener wrote:
> On Wed, 19 Oct 2016, Peter Zijlstra wrote:

> > This is also an entirely different class of optimizations than the whole
> > pointer arithmetic is only valid inside an object thing.
> 
> Yes, it is not related to that.  I've opened 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78035 to track an
> inconsistency in that new optimization.
> 
> > The kernel very much relies on unbounded pointer arithmetic, including
> > overflow. Sure, C language says its UB, but we know our memory layout,
> > and it would be very helpful if we could define it.
> 
> It's well-defined and correctly handled if you do the arithmetic
> in uintptr_t.  No need for knobs.

So why not extend that to the pointers themselves and be done with it?

In any case, so you're saying our:

#define RELOC_HIDE(ptr, off)						\
({									\
	unsigned long __ptr;						\
	__asm__ ("" : "=r"(__ptr) : "0"(ptr));				\
	(typeof(ptr)) (__ptr + (off));					\
})

could be written like:

#define RELOC_HIDE(ptr, off)			\
({						\
	uintptr_t __ptr = (ptr);		\
	(typeof(ptr)) (__ptr + (off));		\
})

Without laundering it through inline asm?

Is there any advantage to doing so?

But this still means we need to be aware of this and use these macros to
launder our pointers.

Which gets us back to the issue that started this whole thread. We have
code that now gets miscompiled, silently.

That is a bad situation. So we need to either avoid the miscompilation,
or make it verbose.

> > Can't we get a knob extending -fno-strict-aliasing to define pointer
> > arithmetic outside of objects and overflow? I mean, we already use that,
> > we also use -fno-strict-overflow and a whole bunch of others.
> > 
> > At the very least, it would be nice to get a -W flag for when this alias
> > analysis stuff kills something so we can at least know when GCC goes and
> > defeats us.
> 
> What kind of warning do you envision?
> 
> "warning: optimized address comparison to always true/false"
> 
> ?  That would trigger all over the place.

That is indeed what I was thinking of. And I have no idea how often that
would trigger on the kernel.

I'm thinking that if this WARN isn't subject to false
positives we could live with that. Its the false positives that render
other warnings useless (too much noise on perfectly fine code etc..).

/me ponders..

So there might be a problem if this triggers in generic code due to
conditions at its use site. There we would not want to, nor could, fix
the generic code because in generic the thing would not be optimized. So
maybe we'd need an annotation still.

Hurm.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Richard Biener]

On Wed, 19 Oct 2016, Peter Zijlstra wrote:

> On Wed, Oct 19, 2016 at 11:33:41AM +0200, Richard Biener wrote:
> > On Wed, 19 Oct 2016, Peter Zijlstra wrote:
> 
> > > This is also an entirely different class of optimizations than the whole
> > > pointer arithmetic is only valid inside an object thing.
> > 
> > Yes, it is not related to that.  I've opened 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78035 to track an
> > inconsistency in that new optimization.
> > 
> > > The kernel very much relies on unbounded pointer arithmetic, including
> > > overflow. Sure, C language says its UB, but we know our memory layout,
> > > and it would be very helpful if we could define it.
> > 
> > It's well-defined and correctly handled if you do the arithmetic
> > in uintptr_t.  No need for knobs.
> 
> So why not extend that to the pointers themselves and be done with it?
> 
> In any case, so you're saying our:
> 
> #define RELOC_HIDE(ptr, off)						\
> ({									\
> 	unsigned long __ptr;						\
> 	__asm__ ("" : "=r"(__ptr) : "0"(ptr));				\
> 	(typeof(ptr)) (__ptr + (off));					\
> })
> 
> could be written like:
> 
> #define RELOC_HIDE(ptr, off)			\
> ({						\
> 	uintptr_t __ptr = (ptr);		\
> 	(typeof(ptr)) (__ptr + (off));		\
> })
> 
> Without laundering it through inline asm?

I think so.

> Is there any advantage to doing so?

asms always introduce issues with optimization passes that do not
bother to handle it (and give up).  And then there is register
allocation - not sure how it is affected by the asm.

Generally I'd say if you can do it w/o asm then better..

Note that old GCC may have had bugs that made the uintptr_t variant
w/o the asm not work.

> But this still means we need to be aware of this and use these macros to
> launder our pointers.

Yes, if you base 'ptr' on the address of a declaration at least.
 
> Which gets us back to the issue that started this whole thread. We have
> code that now gets miscompiled, silently.
> 
> That is a bad situation. So we need to either avoid the miscompilation,
> or make it verbose.

GCC 7 is still not released and I think we should try not to break
things without a good reason.

> > > Can't we get a knob extending -fno-strict-aliasing to define pointer
> > > arithmetic outside of objects and overflow? I mean, we already use that,
> > > we also use -fno-strict-overflow and a whole bunch of others.
> > > 
> > > At the very least, it would be nice to get a -W flag for when this alias
> > > analysis stuff kills something so we can at least know when GCC goes and
> > > defeats us.
> > 
> > What kind of warning do you envision?
> > 
> > "warning: optimized address comparison to always true/false"
> > 
> > ?  That would trigger all over the place.
> 
> That is indeed what I was thinking of. And I have no idea how often that
> would trigger on the kernel.
> 
> I'm thinking that if this WARN isn't subject to false
> positives we could live with that. Its the false positives that render
> other warnings useless (too much noise on perfectly fine code etc..).
> 
> /me ponders..
> 
> So there might be a problem if this triggers in generic code due to
> conditions at its use site. There we would not want to, nor could, fix
> the generic code because in generic the thing would not be optimized. So
> maybe we'd need an annotation still.

For C++ these kind of warnings trigger whenever abstraction penalty
is removed.  Like the typical

 template <int i> foo () { if (i) { <code> } }

triggering for a hypothetical -Wdead-code for i == 0.  The kernel
is known for its "C" abstraction stuff and I can believe that
such -W flag would trigger for cases where abstraction is removed.

Richard.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Peter Zijlstra]

On Wed, Oct 19, 2016 at 01:11:31PM +0200, Richard Biener wrote:
> For C++ these kind of warnings trigger whenever abstraction penalty
> is removed.  Like the typical
> 
>  template <int i> foo () { if (i) { <code> } }
> 
> triggering for a hypothetical -Wdead-code for i == 0.  The kernel
> is known for its "C" abstraction stuff and I can believe that
> such -W flag would trigger for cases where abstraction is removed.

Sure, we very much rely on dead code elimination and constant
propagation all over the place. I was mostly thinking about the specific
case where it was triggered by alias analysis. I'm not sure how often
we'd trigger that.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Markus Trippelsdorf]

On 2016.10.19 at 12:25 +0200, Peter Zijlstra wrote:
> On Wed, Oct 19, 2016 at 11:33:41AM +0200, Richard Biener wrote:
> > On Wed, 19 Oct 2016, Peter Zijlstra wrote:
> 
> > > This is also an entirely different class of optimizations than the whole
> > > pointer arithmetic is only valid inside an object thing.
> > 
> > Yes, it is not related to that.  I've opened 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78035 to track an
> > inconsistency in that new optimization.
> > 
> > > The kernel very much relies on unbounded pointer arithmetic, including
> > > overflow. Sure, C language says its UB, but we know our memory layout,
> > > and it would be very helpful if we could define it.
> > 
> > It's well-defined and correctly handled if you do the arithmetic
> > in uintptr_t.  No need for knobs.
> 
> So why not extend that to the pointers themselves and be done with it?
> 
> In any case, so you're saying our:
> 
> #define RELOC_HIDE(ptr, off)						\
> ({									\
> 	unsigned long __ptr;						\
> 	__asm__ ("" : "=r"(__ptr) : "0"(ptr));				\
> 	(typeof(ptr)) (__ptr + (off));					\
> })
> 
> could be written like:
> 
> #define RELOC_HIDE(ptr, off)			\
> ({						\
> 	uintptr_t __ptr = (ptr);		\
> 	(typeof(ptr)) (__ptr + (off));		\
> })
> 
> Without laundering it through inline asm?
> 
> Is there any advantage to doing so?
> 
> But this still means we need to be aware of this and use these macros to
> launder our pointers.
> 
> Which gets us back to the issue that started this whole thread. We have
> code that now gets miscompiled, silently.
> 
> That is a bad situation. So we need to either avoid the miscompilation,
> or make it verbose.

FYI this issue was fixed on gcc trunk by:
https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=76bc343a2f1aa540e3f5c60e542586bb1ca0e032

-- 
Markus

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Richard Biener]

On Wed, 2 Nov 2016, Markus Trippelsdorf wrote:

> On 2016.10.19 at 12:25 +0200, Peter Zijlstra wrote:
> > On Wed, Oct 19, 2016 at 11:33:41AM +0200, Richard Biener wrote:
> > > On Wed, 19 Oct 2016, Peter Zijlstra wrote:
> > 
> > > > This is also an entirely different class of optimizations than the whole
> > > > pointer arithmetic is only valid inside an object thing.
> > > 
> > > Yes, it is not related to that.  I've opened 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78035 to track an
> > > inconsistency in that new optimization.
> > > 
> > > > The kernel very much relies on unbounded pointer arithmetic, including
> > > > overflow. Sure, C language says its UB, but we know our memory layout,
> > > > and it would be very helpful if we could define it.
> > > 
> > > It's well-defined and correctly handled if you do the arithmetic
> > > in uintptr_t.  No need for knobs.
> > 
> > So why not extend that to the pointers themselves and be done with it?
> > 
> > In any case, so you're saying our:
> > 
> > #define RELOC_HIDE(ptr, off)						\
> > ({									\
> > 	unsigned long __ptr;						\
> > 	__asm__ ("" : "=r"(__ptr) : "0"(ptr));				\
> > 	(typeof(ptr)) (__ptr + (off));					\
> > })
> > 
> > could be written like:
> > 
> > #define RELOC_HIDE(ptr, off)			\
> > ({						\
> > 	uintptr_t __ptr = (ptr);		\
> > 	(typeof(ptr)) (__ptr + (off));		\
> > })
> > 
> > Without laundering it through inline asm?
> > 
> > Is there any advantage to doing so?
> > 
> > But this still means we need to be aware of this and use these macros to
> > launder our pointers.
> > 
> > Which gets us back to the issue that started this whole thread. We have
> > code that now gets miscompiled, silently.
> > 
> > That is a bad situation. So we need to either avoid the miscompilation,
> > or make it verbose.
> 
> FYI this issue was fixed on gcc trunk by:
> https://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=76bc343a2f1aa540e3f5c60e542586bb1ca0e032

Note while this change restored the old behavior this change was _not_
intended to fix this particular fallout (it was to fix an inconsistency
with respect to comparing addresses of symbols that can be interposed).
It just happens that your externs can be interposed with ELF.

Richard.

Re: [PATCH 01/12] extarray: define helpers for arrays defined in linker scripts

[Linus Torvalds]

On Wed, Nov 2, 2016 at 6:14 AM, Richard Biener <rguenther@suse.de> wrote:
>
> Note while this change restored the old behavior this change was _not_
> intended to fix this particular fallout (it was to fix an inconsistency
> with respect to comparing addresses of symbols that can be interposed).
> It just happens that your externs can be interposed with ELF.

I think it should in general work for the kernel too, since as far as
I can tell, it fundamentally fixes the issue that linker scripts will
set symbol addresses to possibly alias other symbols.

So from a compiler standpoint, I think our "begin/end" linker script
symbols can be seen as interposing a larger array and give bounds for
it. No>

                  Linus