2016-10-16 15:21:06

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 00/12] external array access helpers

Hi,

The first two patches in the series fix the concrete bug (a boot crash
when using gcc 7.0+) by defining new wrappers for arrays defined in
linker scripts. These two patches should probably go into the kernel +
stable as soon as people are happy with the new interface. Not sure who
would pick this up, Greg maybe?

The rest of the patches are more to try out other users of the API to
get a feel for what the patches will look like. Eventually all the users
in the whole kernel should probably be converted to avoid similar latent
bugs, but I don't have the means to test many of the changes myself.
These patches do not fix not any known crashes as far as I'm aware and
can probably trickle in through specific maintainers.

Looks like Luis R. Rodriguez has some related work on linker tables.
AFAICT that should be orthogonal to this, although there may be source
level conflicts.


Vegard


2016-10-16 15:17:16

by Vegard Nossum

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

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 <[email protected]>
Cc: Dmitry Torokhov <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: [email protected]
Signed-off-by: Vegard Nossum <[email protected]>
---
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

2016-10-16 15:17:24

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 04/12] tracing: declare __{start,stop}_{annotated_,}branch_profile as external array

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/trace_branch.c | 15 +++++++--------
1 file changed, 7 insertions(+), 8 deletions(-)

diff --git a/kernel/trace/trace_branch.c b/kernel/trace/trace_branch.c
index 3a2a737..47d78fd 100644
--- a/kernel/trace/trace_branch.c
+++ b/kernel/trace/trace_branch.c
@@ -3,6 +3,7 @@
*
* Copyright (C) 2008 Steven Rostedt <[email protected]>
*/
+#include <linux/extarray.h>
#include <linux/kallsyms.h>
#include <linux/seq_file.h>
#include <linux/spinlock.h>
@@ -218,8 +219,7 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect)
}
EXPORT_SYMBOL(ftrace_likely_update);

-extern unsigned long __start_annotated_branch_profile[];
-extern unsigned long __stop_annotated_branch_profile[];
+DECLARE_EXTARRAY(unsigned long, annotated_branch_profile);

static int annotated_branch_stat_headers(struct seq_file *m)
{
@@ -273,7 +273,7 @@ static int branch_stat_show(struct seq_file *m, void *v)

static void *annotated_branch_stat_start(struct tracer_stat *trace)
{
- return __start_annotated_branch_profile;
+ return ext_start(annotated_branch_profile);
}

static void *
@@ -283,7 +283,7 @@ annotated_branch_stat_next(void *v, int idx)

++p;

- if ((void *)p >= (void *)__stop_annotated_branch_profile)
+ if ((void *)p >= (void *)ext_end(annotated_branch_profile))
return NULL;

return p;
@@ -347,8 +347,7 @@ fs_initcall(init_annotated_branch_stats);

#ifdef CONFIG_PROFILE_ALL_BRANCHES

-extern unsigned long __start_branch_profile[];
-extern unsigned long __stop_branch_profile[];
+DECLARE_EXTARRAY(unsigned long, branch_profile);

static int all_branch_stat_headers(struct seq_file *m)
{
@@ -363,7 +362,7 @@ static int all_branch_stat_headers(struct seq_file *m)

static void *all_branch_stat_start(struct tracer_stat *trace)
{
- return __start_branch_profile;
+ return ext_start(branch_profile);
}

static void *
@@ -373,7 +372,7 @@ all_branch_stat_next(void *v, int idx)

++p;

- if ((void *)p >= (void *)__stop_branch_profile)
+ if ((void *)p >= (void *)ext_end(branch_profile))
return NULL;

return p;
--
2.10.0.479.g221bd91

2016-10-16 15:17:38

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 03/12] ftrace: declare __{start,stop}_mcount_loc as external array

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/ftrace.c | 11 ++++++-----
1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 2050a765..3c37036 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -13,6 +13,7 @@
* Copyright (C) 2004 Nadia Yvette Chambers
*/

+#include <linux/extarray.h>
#include <linux/stop_machine.h>
#include <linux/clocksource.h>
#include <linux/kallsyms.h>
@@ -5075,10 +5076,10 @@ void ftrace_module_init(struct module *mod)
}
#endif /* CONFIG_MODULES */

+DECLARE_EXTARRAY(unsigned long, mcount_loc);
+
void __init ftrace_init(void)
{
- extern unsigned long __start_mcount_loc[];
- extern unsigned long __stop_mcount_loc[];
unsigned long count, flags;
int ret;

@@ -5088,7 +5089,7 @@ void __init ftrace_init(void)
if (ret)
goto failed;

- count = __stop_mcount_loc - __start_mcount_loc;
+ count = ext_size(mcount_loc);
if (!count) {
pr_info("ftrace: No functions to be traced?\n");
goto failed;
@@ -5100,8 +5101,8 @@ void __init ftrace_init(void)
last_ftrace_enabled = ftrace_enabled = 1;

ret = ftrace_process_locs(NULL,
- __start_mcount_loc,
- __stop_mcount_loc);
+ ext_start(mcount_loc),
+ ext_end(mcount_loc));

set_ftrace_early_filters();

--
2.10.0.479.g221bd91

2016-10-16 15:18:58

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 05/12] kprobes: declare __{start,stop}_kprobe_blacklist as external array

Cc: Ananth N Mavinakayanahalli <[email protected]>
Cc: Anil S Keshavamurthy <[email protected]>
Cc: "David S. Miller" <[email protected]>
Cc: Masami Hiramatsu <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/kprobes.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index d630954..f163f74 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -31,6 +31,7 @@
* <[email protected]> and Prasanna S Panchamukhi
* <[email protected]> added function-return probes.
*/
+#include <linux/extarray.h>
#include <linux/kprobes.h>
#include <linux/hash.h>
#include <linux/init.h>
@@ -2126,8 +2127,7 @@ static struct notifier_block kprobe_module_nb = {
};

/* Markers of _kprobe_blacklist section */
-extern unsigned long __start_kprobe_blacklist[];
-extern unsigned long __stop_kprobe_blacklist[];
+DECLARE_EXTARRAY(unsigned long, kprobe_blacklist);

static int __init init_kprobes(void)
{
@@ -2141,8 +2141,8 @@ static int __init init_kprobes(void)
raw_spin_lock_init(&(kretprobe_table_locks[i].lock));
}

- err = populate_kprobe_blacklist(__start_kprobe_blacklist,
- __stop_kprobe_blacklist);
+ err = populate_kprobe_blacklist(ext_start(kprobe_blacklist),
+ ext_end(kprobe_blacklist));
if (err) {
pr_err("kprobes: failed to populate blacklist: %d\n", err);
pr_err("Please take care of using kprobes.\n");
--
2.10.0.479.g221bd91

2016-10-16 15:19:09

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 06/12] tracing: declare __{start,stop}_ftrace_events as external array

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/trace_events.c | 7 +++----
1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/kernel/trace/trace_events.c b/kernel/trace/trace_events.c
index 03c0a48..400162f 100644
--- a/kernel/trace/trace_events.c
+++ b/kernel/trace/trace_events.c
@@ -10,6 +10,7 @@

#define pr_fmt(fmt) fmt

+#include <linux/extarray.h>
#include <linux/workqueue.h>
#include <linux/spinlock.h>
#include <linux/kthread.h>
@@ -2808,8 +2809,7 @@ static void __add_event_to_tracers(struct trace_event_call *call)
__trace_add_new_event(call, tr);
}

-extern struct trace_event_call *__start_ftrace_events[];
-extern struct trace_event_call *__stop_ftrace_events[];
+DECLARE_EXTARRAY(struct trace_event_call *, ftrace_events)

static char bootup_event_buf[COMMAND_LINE_SIZE] __initdata;

@@ -2992,8 +2992,7 @@ static __init int event_trace_enable(void)
if (!tr)
return -ENODEV;

- for_each_event(iter, __start_ftrace_events, __stop_ftrace_events) {
-
+ ext_for_each(iter, ftrace_events) {
call = *iter;
ret = event_init(call);
if (!ret)
--
2.10.0.479.g221bd91

2016-10-16 15:19:38

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 11/12] jump_label: declare jump table as external array

Cc: Jason Baron <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
include/linux/jump_label.h | 4 ++--
kernel/jump_label.c | 10 +++++-----
2 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
index a0547c5..7ba9918 100644
--- a/include/linux/jump_label.h
+++ b/include/linux/jump_label.h
@@ -76,6 +76,7 @@

#ifndef __ASSEMBLY__

+#include <linux/extarray.h>
#include <linux/types.h>
#include <linux/compiler.h>

@@ -132,8 +133,7 @@ static __always_inline bool static_key_true(struct static_key *key)
return !arch_static_branch(key, true);
}

-extern struct jump_entry __start___jump_table[];
-extern struct jump_entry __stop___jump_table[];
+DECLARE_EXTARRAY(struct jump_entry, __jump_table);

extern void jump_label_init(void);
extern void jump_label_lock(void);
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 93ad6c1..bf14906 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -274,8 +274,8 @@ static void __jump_label_update(struct static_key *key,

void __init jump_label_init(void)
{
- struct jump_entry *iter_start = __start___jump_table;
- struct jump_entry *iter_stop = __stop___jump_table;
+ struct jump_entry *iter_start = ext_start(__jump_table);
+ struct jump_entry *iter_stop = ext_end(__jump_table);
struct static_key *key = NULL;
struct jump_entry *iter;

@@ -539,8 +539,8 @@ early_initcall(jump_label_init_module);
*/
int jump_label_text_reserved(void *start, void *end)
{
- int ret = __jump_label_text_reserved(__start___jump_table,
- __stop___jump_table, start, end);
+ int ret = __jump_label_text_reserved(ext_start(__jump_table),
+ ext_end(__jump_table), start, end);

if (ret)
return ret;
@@ -553,7 +553,7 @@ int jump_label_text_reserved(void *start, void *end)

static void jump_label_update(struct static_key *key)
{
- struct jump_entry *stop = __stop___jump_table;
+ struct jump_entry *stop = ext_end(__jump_table);
struct jump_entry *entry = static_key_entries(key);
#ifdef CONFIG_MODULES
struct module *mod;
--
2.10.0.479.g221bd91

2016-10-16 15:20:34

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 12/12] dynamic debug: declare table as external array

Cc: Greg Banks <[email protected]>
Cc: Jason Baron <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
lib/dynamic_debug.c | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c
index da796e2..101a420 100644
--- a/lib/dynamic_debug.c
+++ b/lib/dynamic_debug.c
@@ -13,6 +13,7 @@

#define pr_fmt(fmt) KBUILD_MODNAME ":%s: " fmt, __func__

+#include <linux/extarray.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/moduleparam.h>
@@ -37,8 +38,7 @@
#include <linux/device.h>
#include <linux/netdevice.h>

-extern struct _ddebug __start___verbose[];
-extern struct _ddebug __stop___verbose[];
+DECLARE_EXTARRAY(struct _ddebug, __verbose);

struct ddebug_table {
struct list_head link;
@@ -978,14 +978,14 @@ static int __init dynamic_debug_init(void)
int n = 0, entries = 0, modct = 0;
int verbose_bytes = 0;

- if (__start___verbose == __stop___verbose) {
+ if (!ext_size(__verbose)) {
pr_warn("_ddebug table is empty in a CONFIG_DYNAMIC_DEBUG build\n");
return 1;
}
- iter = __start___verbose;
+ iter = ext_start(__verbose);
modname = iter->modname;
iter_start = iter;
- for (; iter < __stop___verbose; iter++) {
+ for (; iter < ext_end(__verbose); iter++) {
entries++;
verbose_bytes += strlen(iter->modname) + strlen(iter->function)
+ strlen(iter->filename) + strlen(iter->format);
@@ -1008,7 +1008,7 @@ static int __init dynamic_debug_init(void)
ddebug_init_success = 1;
vpr_info("%d modules, %d entries and %d bytes in ddebug tables, %d bytes in (readonly) verbose section\n",
modct, entries, (int)(modct * sizeof(struct ddebug_table)),
- verbose_bytes + (int)(__stop___verbose - __start___verbose));
+ verbose_bytes + (int)(ext_size(__verbose) * sizeof(struct _ddebug)));

/* apply ddebug_query boot param, dont unload tables on err */
if (ddebug_setup_string[0] != '\0') {
--
2.10.0.479.g221bd91

2016-10-16 15:20:43

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 07/12] tracing: declare __{start,stop}_ftrace_enum_maps as external array

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/trace.c | 10 ++++------
1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/kernel/trace/trace.c b/kernel/trace/trace.c
index 8696ce6..d1bee81 100644
--- a/kernel/trace/trace.c
+++ b/kernel/trace/trace.c
@@ -11,6 +11,7 @@
* Copyright (C) 2004-2006 Ingo Molnar
* Copyright (C) 2004 Nadia Yvette Chambers
*/
+#include <linux/extarray.h>
#include <linux/ring_buffer.h>
#include <generated/utsrelease.h>
#include <linux/stacktrace.h>
@@ -7299,15 +7300,12 @@ struct dentry *tracing_init_dentry(void)
return NULL;
}

-extern struct trace_enum_map *__start_ftrace_enum_maps[];
-extern struct trace_enum_map *__stop_ftrace_enum_maps[];
+DECLARE_EXTARRAY(struct trace_enum_map *, ftrace_enum_maps);

static void __init trace_enum_init(void)
{
- int len;
-
- len = __stop_ftrace_enum_maps - __start_ftrace_enum_maps;
- trace_insert_enum_map(NULL, __start_ftrace_enum_maps, len);
+ trace_insert_enum_map(NULL, ext_start(ftrace_enum_maps),
+ ext_size(ftrace_enum_maps));
}

#ifdef CONFIG_MODULES
--
2.10.0.479.g221bd91

2016-10-16 15:20:55

by Vegard Nossum

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

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 <[email protected]>
Cc: [email protected]
Cc: Ming Lei <[email protected]>
Cc: Steven Rostedt <[email protected]>
Cc: Linus Torvalds <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
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

2016-10-16 15:58:07

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 10/12] serial_core: declare __earlycon_table{,_end} as external array

Cc: Peter Hurley <[email protected]>
Cc: Greg Kroah-Hartman <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
drivers/of/fdt.c | 2 +-
drivers/tty/serial/earlycon.c | 2 +-
include/asm-generic/vmlinux.lds.h | 8 ++++----
include/linux/serial_core.h | 4 ++--
4 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index c89d5d2..eb41e3d 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -956,7 +956,7 @@ int __init early_init_dt_scan_chosen_stdout(void)
return 0;
}

- for (match = __earlycon_table; match < __earlycon_table_end; match++) {
+ ext_for_each(match, earlycon_table) {
if (!match->compatible[0])
continue;

diff --git a/drivers/tty/serial/earlycon.c b/drivers/tty/serial/earlycon.c
index c365154..f49cfed 100644
--- a/drivers/tty/serial/earlycon.c
+++ b/drivers/tty/serial/earlycon.c
@@ -180,7 +180,7 @@ int __init setup_earlycon(char *buf)
if (early_con.flags & CON_ENABLED)
return -EALREADY;

- for (match = __earlycon_table; match < __earlycon_table_end; match++) {
+ ext_for_each(match, earlycon_table) {
size_t len = strlen(match->name);

if (strncmp(buf, match->name, len))
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index d6121ac..342c2dd 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -154,10 +154,10 @@
#endif

#ifdef CONFIG_SERIAL_EARLYCON
-#define EARLYCON_TABLE() STRUCT_ALIGN(); \
- VMLINUX_SYMBOL(__earlycon_table) = .; \
- *(__earlycon_table) \
- VMLINUX_SYMBOL(__earlycon_table_end) = .;
+#define EARLYCON_TABLE() STRUCT_ALIGN(); \
+ VMLINUX_SYMBOL(__start_earlycon_table) = .; \
+ *(__earlycon_table) \
+ VMLINUX_SYMBOL(__stop_earlycon_table) = .;
#else
#define EARLYCON_TABLE()
#endif
diff --git a/include/linux/serial_core.h b/include/linux/serial_core.h
index 3442014..2d35e87 100644
--- a/include/linux/serial_core.h
+++ b/include/linux/serial_core.h
@@ -22,6 +22,7 @@


#include <linux/compiler.h>
+#include <linux/extarray.h>
#include <linux/interrupt.h>
#include <linux/circ_buf.h>
#include <linux/spinlock.h>
@@ -349,8 +350,7 @@ struct earlycon_id {
int (*setup)(struct earlycon_device *, const char *options);
} __aligned(32);

-extern const struct earlycon_id __earlycon_table[];
-extern const struct earlycon_id __earlycon_table_end[];
+DECLARE_EXTARRAY(const struct earlycon_id, earlycon_table);

#if defined(CONFIG_SERIAL_EARLYCON) && !defined(MODULE)
#define EARLYCON_USED_OR_UNUSED __used
--
2.10.0.479.g221bd91

2016-10-16 15:58:01

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 08/12] tracing: declare __trace_bprintk_fmt/__tracepoint_str as external arrays

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/trace.c | 2 +-
kernel/trace/trace.h | 7 +++----
kernel/trace/trace_printk.c | 8 ++++----
3 files changed, 8 insertions(+), 9 deletions(-)

diff --git a/kernel/trace/trace.c b/kernel/trace/trace.c
index d1bee81..50af466 100644
--- a/kernel/trace/trace.c
+++ b/kernel/trace/trace.c
@@ -7642,7 +7642,7 @@ __init static int tracer_alloc_buffers(void)
goto out_free_buffer_mask;

/* Only allocate trace_printk buffers if a trace_printk exists */
- if (__stop___trace_bprintk_fmt != __start___trace_bprintk_fmt)
+ if (ext_size(__trace_bprintk_fmt))
/* Must be called before global_trace.buffer is allocated */
trace_printk_init_buffers();

diff --git a/kernel/trace/trace.h b/kernel/trace/trace.h
index fd24b1f..75d2750 100644
--- a/kernel/trace/trace.h
+++ b/kernel/trace/trace.h
@@ -2,6 +2,7 @@
#ifndef _LINUX_KERNEL_TRACE_H
#define _LINUX_KERNEL_TRACE_H

+#include <linux/extarray.h>
#include <linux/fs.h>
#include <linux/atomic.h>
#include <linux/sched.h>
@@ -1605,11 +1606,9 @@ extern int trace_event_enable_disable(struct trace_event_file *file,
int enable, int soft_disable);
extern int tracing_alloc_snapshot(void);

-extern const char *__start___trace_bprintk_fmt[];
-extern const char *__stop___trace_bprintk_fmt[];
+DECLARE_EXTARRAY(const char *, __trace_bprintk_fmt);

-extern const char *__start___tracepoint_str[];
-extern const char *__stop___tracepoint_str[];
+DECLARE_EXTARRAY(const char *, __tracepoint_str);

void trace_printk_control(bool enabled);
void trace_printk_init_buffers(void);
diff --git a/kernel/trace/trace_printk.c b/kernel/trace/trace_printk.c
index ad1d6164..0d66509 100644
--- a/kernel/trace/trace_printk.c
+++ b/kernel/trace/trace_printk.c
@@ -255,10 +255,10 @@ static const char **find_next(void *v, loff_t *pos)
int start_index;
int last_index;

- start_index = __stop___trace_bprintk_fmt - __start___trace_bprintk_fmt;
+ start_index = ext_size(__trace_bprintk_fmt);

if (*pos < start_index)
- return __start___trace_bprintk_fmt + *pos;
+ return ext_start(__trace_bprintk_fmt) + *pos;

/*
* The __tracepoint_str section is treated the same as the
@@ -273,10 +273,10 @@ static const char **find_next(void *v, loff_t *pos)
* the ASCII text for userspace.
*/
last_index = start_index;
- start_index = __stop___tracepoint_str - __start___tracepoint_str;
+ start_index = ext_size(__tracepoint_str);

if (*pos < last_index + start_index)
- return __start___tracepoint_str + (*pos - last_index);
+ return ext_start(__tracepoint_str) + (*pos - last_index);

start_index += last_index;
return find_next_mod_format(start_index, v, fmt, pos);
--
2.10.0.479.g221bd91

2016-10-16 16:13:36

by Vegard Nossum

[permalink] [raw]
Subject: [PATCH 09/12] tracing: declare __{start,stop}_syscalls_metadata as external array

Cc: Steven Rostedt <[email protected]>
Signed-off-by: Vegard Nossum <[email protected]>
---
kernel/trace/trace_syscalls.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/kernel/trace/trace_syscalls.c b/kernel/trace/trace_syscalls.c
index 5e10395..2b1c1c3 100644
--- a/kernel/trace/trace_syscalls.c
+++ b/kernel/trace/trace_syscalls.c
@@ -1,5 +1,6 @@
#include <trace/syscall.h>
#include <trace/events/syscalls.h>
+#include <linux/extarray.h>
#include <linux/syscalls.h>
#include <linux/slab.h>
#include <linux/kernel.h>
@@ -26,8 +27,7 @@ syscall_get_enter_fields(struct trace_event_call *call)
return &entry->enter_fields;
}

-extern struct syscall_metadata *__start_syscalls_metadata[];
-extern struct syscall_metadata *__stop_syscalls_metadata[];
+DECLARE_EXTARRAY(struct syscall_metadata *, syscalls_metadata);

static struct syscall_metadata **syscalls_metadata;

@@ -84,8 +84,8 @@ find_syscall_meta(unsigned long syscall)
char str[KSYM_SYMBOL_LEN];


- start = __start_syscalls_metadata;
- stop = __stop_syscalls_metadata;
+ start = ext_start(syscalls_metadata);
+ stop = ext_end(syscalls_metadata);
kallsyms_lookup(syscall, NULL, NULL, NULL, str);

if (arch_syscall_match_sym_name(str, "sys_ni_syscall"))
--
2.10.0.479.g221bd91

2016-10-16 16:14:04

by Greg Kroah-Hartman

[permalink] [raw]
Subject: Re: [PATCH 00/12] external array access helpers

On Sun, Oct 16, 2016 at 05:16:04PM +0200, Vegard Nossum wrote:
> Hi,
>
> The first two patches in the series fix the concrete bug (a boot crash
> when using gcc 7.0+) by defining new wrappers for arrays defined in
> linker scripts. These two patches should probably go into the kernel +
> stable as soon as people are happy with the new interface. Not sure who
> would pick this up, Greg maybe?

Ugh, that's messy, but nice fixup. I can take these in my tree. I'd
like to get others to review them first, but I can queue them up in a
week or so if there is no objections.

Is gcc 7.0 "stable" enough that people will start to be using it soon?

thanks,

greg k-h

2016-10-16 16:26:01

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [PATCH 11/12] jump_label: declare jump table as external array

On Sun, Oct 16, 2016 at 05:16:15PM +0200, Vegard Nossum wrote:
> Cc: Jason Baron <[email protected]>
> Cc: Peter Zijlstra <[email protected]>
> Cc: Steven Rostedt <[email protected]>
> Signed-off-by: Vegard Nossum <[email protected]>

NAK, -ENOCHANGELOG.

2016-10-16 16:52:15

by Vegard Nossum

[permalink] [raw]
Subject: Re: [PATCH 11/12] jump_label: declare jump table as external array

On 10/16/2016 06:25 PM, Peter Zijlstra wrote:
> On Sun, Oct 16, 2016 at 05:16:15PM +0200, Vegard Nossum wrote:
>> Cc: Jason Baron <[email protected]>
>> Cc: Peter Zijlstra <[email protected]>
>> Cc: Steven Rostedt <[email protected]>
>> Signed-off-by: Vegard Nossum <[email protected]>
>
> NAK, -ENOCHANGELOG.
>

Hi Peter,

It's true I didn't put an RFC tag on this (mostly because git-send-email
doesn't seem to have an option for it?), but the whole point of doing
these other patches (03-12) was to demonstrate what the patches would
look like for some other kernel code and ask for feedback on the overall
interface/approach. I don't know if you read the introduction and first
patch in the series, but I'd expect that to be more than enough to
understand the problem.

If we really have to repeat the rationale for every patch, can we reuse
this?

"Comparisons between pointers to different arrays is technically
undefined behaviour and recent GCCs may incorrectly optimise away loop
termination conditions. Use the external array accessor macros to
prevent this from happening."


Vegard

2016-10-16 17:28:35

by Vegard Nossum

[permalink] [raw]
Subject: Re: [PATCH 00/12] external array access helpers

On 10/16/2016 06:14 PM, Greg Kroah-Hartman wrote:
> On Sun, Oct 16, 2016 at 05:16:04PM +0200, Vegard Nossum wrote:
>> Hi,
>>
>> The first two patches in the series fix the concrete bug (a boot crash
>> when using gcc 7.0+) by defining new wrappers for arrays defined in
>> linker scripts. These two patches should probably go into the kernel +
>> stable as soon as people are happy with the new interface. Not sure who
>> would pick this up, Greg maybe?
>
> Ugh, that's messy, but nice fixup. I can take these in my tree. I'd
> like to get others to review them first, but I can queue them up in a
> week or so if there is no objections.

Thanks!

> Is gcc 7.0 "stable" enough that people will start to be using it soon?

Well, it seems like Jiri and I both ran into the firmware thing
independently.

gcc 7 is not actually released yet, so I guess my message above is
slightly misleading.

gcc 6 seems to have released about a year after development started
and gcc 7 development started in April, so I guess there's still quite a
lot of time before it's officially out.

Although the NetBSD people seemed to have run into the same issue using
GCC 5.4, I'm not sure what to make of that.


Vegard

2016-10-16 17:44:46

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [PATCH 11/12] jump_label: declare jump table as external array

On Sun, Oct 16, 2016 at 06:50:55PM +0200, Vegard Nossum wrote:
> On 10/16/2016 06:25 PM, Peter Zijlstra wrote:
> >On Sun, Oct 16, 2016 at 05:16:15PM +0200, Vegard Nossum wrote:
> >>Cc: Jason Baron <[email protected]>
> >>Cc: Peter Zijlstra <[email protected]>
> >>Cc: Steven Rostedt <[email protected]>
> >>Signed-off-by: Vegard Nossum <[email protected]>
> >
> >NAK, -ENOCHANGELOG.
> >
>
> Hi Peter,
>
> It's true I didn't put an RFC tag on this (mostly because git-send-email
> doesn't seem to have an option for it?), but the whole point of doing
> these other patches (03-12) was to demonstrate what the patches would
> look like for some other kernel code and ask for feedback on the overall
> interface/approach. I don't know if you read the introduction and first
> patch in the series, but I'd expect that to be more than enough to
> understand the problem.

Well, seeing how I was not Cc'ed on any of the other patches, including
the first patch, I really couldn't say.

2016-10-17 06:26:37

by Jiri Slaby

[permalink] [raw]
Subject: Re: [PATCH 00/12] external array access helpers

On 10/16/2016, 06:14 PM, Greg Kroah-Hartman wrote:
> Is gcc 7.0 "stable" enough that people will start to be using it soon?

Standard suse kernel builds and boots with gcc 7 just fine. But only
with 02/12 from this series. So perhaps it's not stable enough for
production use, but at least I was about to test use-after-scope gcc 7
UBSAN thingie via syzkaller soon.

thanks,
--
js
suse labs

2016-10-17 06:44:12

by Masami Hiramatsu

[permalink] [raw]
Subject: Re: [PATCH 05/12] kprobes: declare __{start,stop}_kprobe_blacklist as external array

Could you please add the patch description for the patch?
And send me the whole series of the patches.

Thanks,

On Sun, 16 Oct 2016 17:16:09 +0200
Vegard Nossum <[email protected]> wrote:

> Cc: Ananth N Mavinakayanahalli <[email protected]>
> Cc: Anil S Keshavamurthy <[email protected]>
> Cc: "David S. Miller" <[email protected]>
> Cc: Masami Hiramatsu <[email protected]>
> Signed-off-by: Vegard Nossum <[email protected]>
> ---
> kernel/kprobes.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/kprobes.c b/kernel/kprobes.c
> index d630954..f163f74 100644
> --- a/kernel/kprobes.c
> +++ b/kernel/kprobes.c
> @@ -31,6 +31,7 @@
> * <[email protected]> and Prasanna S Panchamukhi
> * <[email protected]> added function-return probes.
> */
> +#include <linux/extarray.h>
> #include <linux/kprobes.h>
> #include <linux/hash.h>
> #include <linux/init.h>
> @@ -2126,8 +2127,7 @@ static struct notifier_block kprobe_module_nb = {
> };
>
> /* Markers of _kprobe_blacklist section */
> -extern unsigned long __start_kprobe_blacklist[];
> -extern unsigned long __stop_kprobe_blacklist[];
> +DECLARE_EXTARRAY(unsigned long, kprobe_blacklist);
>
> static int __init init_kprobes(void)
> {
> @@ -2141,8 +2141,8 @@ static int __init init_kprobes(void)
> raw_spin_lock_init(&(kretprobe_table_locks[i].lock));
> }
>
> - err = populate_kprobe_blacklist(__start_kprobe_blacklist,
> - __stop_kprobe_blacklist);
> + err = populate_kprobe_blacklist(ext_start(kprobe_blacklist),
> + ext_end(kprobe_blacklist));
> if (err) {
> pr_err("kprobes: failed to populate blacklist: %d\n", err);
> pr_err("Please take care of using kprobes.\n");
> --
> 2.10.0.479.g221bd91
>


--
Masami Hiramatsu

2016-10-17 07:02:57

by Greg Kroah-Hartman

[permalink] [raw]
Subject: Re: [PATCH 00/12] external array access helpers

On Sun, Oct 16, 2016 at 07:05:22PM +0200, Vegard Nossum wrote:
> On 10/16/2016 06:14 PM, Greg Kroah-Hartman wrote:
> > On Sun, Oct 16, 2016 at 05:16:04PM +0200, Vegard Nossum wrote:
> > > Hi,
> > >
> > > The first two patches in the series fix the concrete bug (a boot crash
> > > when using gcc 7.0+) by defining new wrappers for arrays defined in
> > > linker scripts. These two patches should probably go into the kernel +
> > > stable as soon as people are happy with the new interface. Not sure who
> > > would pick this up, Greg maybe?
> >
> > Ugh, that's messy, but nice fixup. I can take these in my tree. I'd
> > like to get others to review them first, but I can queue them up in a
> > week or so if there is no objections.
>
> Thanks!

Ok, I didn't read the later patches, and as others pointed out, I can't
take patches without any changelog information, so those need to be
redone.

I'm also a bit worried about the naming of this, I'll respond to the
first patch about those issues.

thanks,

greg k-h

2016-10-17 07:04:36

by Greg Kroah-Hartman

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

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 <[email protected]>
> Cc: [email protected]
> Cc: Ming Lei <[email protected]>
> Cc: Steven Rostedt <[email protected]>
> Cc: Linus Torvalds <[email protected]>
> Signed-off-by: Vegard Nossum <[email protected]>
> ---
> 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

2016-10-17 08:33:36

by Peter Zijlstra

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

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?


2016-10-17 09:01:25

by Jiri Slaby

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

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

2016-10-17 09:09:48

by Peter Zijlstra

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

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 :-)

2016-10-17 11:28:04

by Vegard Nossum

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

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

2016-10-17 11:45:31

by Peter Zijlstra

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

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.

2016-10-17 21:33:24

by Steven Rostedt

[permalink] [raw]
Subject: Re: [PATCH 11/12] jump_label: declare jump table as external array

On Sun, 16 Oct 2016 18:50:55 +0200
Vegard Nossum <[email protected]> wrote:
> >
> > NAK, -ENOCHANGELOG.

Agreed.

> >
>
> Hi Peter,
>
> It's true I didn't put an RFC tag on this (mostly because git-send-email
> doesn't seem to have an option for it?), but the whole point of doing

I would think it does, although I never use it (I always use quilt
mail).


> these other patches (03-12) was to demonstrate what the patches would
> look like for some other kernel code and ask for feedback on the overall
> interface/approach. I don't know if you read the introduction and first
> patch in the series, but I'd expect that to be more than enough to
> understand the problem.

But we were not Cc'd on those. If we are not on the Cc to the
introduction nor the other patches, we will most likely not be reading
them.

>
> If we really have to repeat the rationale for every patch, can we reuse
> this?
>
> "Comparisons between pointers to different arrays is technically
> undefined behaviour and recent GCCs may incorrectly optimise away loop
> termination conditions. Use the external array accessor macros to
> prevent this from happening."
>

So basically gcc will break on these array address calculations? Which
version of gcc started this, and has this actually been an issue?


-- Steve

2016-10-18 08:09:32

by Vegard Nossum

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

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

2016-10-18 21:18:23

by Luis Chamberlain

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

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/[email protected]
[1] https://lkml.kernel.org/r/[email protected]
[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

2016-10-19 14:23:56

by Richard Biener

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

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.

2016-10-19 14:36:34

by Peter Zijlstra

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

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.

2016-10-19 14:40:03

by Jiri Slaby

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

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

2016-10-19 15:03:57

by Richard Biener

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

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/[email protected]
> [1] https://lkml.kernel.org/r/[email protected]
> [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 <[email protected]>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

2016-10-19 15:50:09

by Richard Biener

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

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.

2016-10-19 15:59:29

by Peter Zijlstra

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

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.

2016-10-19 16:11:20

by Peter Zijlstra

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

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.

2016-11-02 12:12:05

by Markus Trippelsdorf

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

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

2016-11-02 12:14:15

by Richard Biener

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

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.

2016-11-02 15:02:10

by Linus Torvalds

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

On Wed, Nov 2, 2016 at 6:14 AM, Richard Biener <[email protected]> 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