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@xxxxxxxxxx
[1] https://lkml.kernel.org/r/1471642454-5679-1-git-send-email-mcgrof@xxxxxxxxxx
[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