kernel.h: Skip single-eval logic on literals in min()/max()

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

Quoted 5 lines · Kees Cook

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

Ok, looks good.

I just have a couple of questions about applying it.

In particular, if this will help people working on getting rid of VLA's in the short term, I can apply it directly.

But if people who are looking at it (anybody else than Kees?)

don't much care, then this
might be a 4.17 thing or at least "random -mm queue"?

#define __single_eval_max(max1, max2, x, y) ({  \
        typeof (x) max1 = (x);                  \
        typeof (y) max2 = (y);                  \
        max1 > max2 ? max1 : max2; })

actually looks more natural to me than passing the two types in as arguments to the macro.

(That form also is amenable to things like "__auto_type" etc simplifications).

Side note: do we *really* need the unique variable names? That's what makes those things _really_ illegible. I thgink it's done just for a sparse warning that we should probably ignore. It's off by default anyway exactly because it doesn't work that well due to nested macro expansions like this.

There is very real value to keeping our odd macros legible, I feel. Even when they are complicated by issues like this, it would be good to keep them as simple as possible.

Comments?

Quoted 5 lines · Kees Cook

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

Ok, looks good.

I just have a couple of questions about applying it.

In particular, if this will help people working on getting rid of VLA's in the short term, I can apply it directly. But if people who are looking at it (anybody else than Kees?) don't much care, then this might be a 4.17 thing or at least "random -mm queue"?

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

$ diff -u before.txt after.txt | grep ^-

(quoted diff) +0 -6

-drivers/input/touchscreen/cyttsp4_core.c:871:2: warning: ISO C90 forbids variable length array ‘ids’ [-Wvla]
-fs/btrfs/tree-checker.c:344:4: warning: ISO C90 forbids variable length array ‘namebuf’ [-Wvla]
-lib/vsprintf.c:747:2: warning: ISO C90 forbids variable length array ‘sym’ [-Wvla]
-net/ipv4/proc.c:403:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:198:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:218:2: warning: ISO C90 forbids variable length array ‘buff64’ [-Wvla]

Based on an earlier patch from Josh Poimboeuf.

A brief poke failed to reveal a workaround - gcc-4.4.4 doesn't appear to know that __builtin_constant_p(x) is a constant. Or something.

Sigh. Wasn't there some talk about modernizing our toolchain requirements?

Quoted 3 lines · Andrew Morton

A brief poke failed to reveal a workaround - gcc-4.4.4 doesn't appear to know that __builtin_constant_p(x) is a constant. Or something.

LOL.

I suspect it might be that it wants to evaluate __builtin_choose_expr() at an earlier stage than it evaluates __builtin_constant_p(), so it's not that it doesn't know that __builtin_constant_p() is a constant, it just might not know it *yet*.

Maybe.

Side note, if it's not that, but just the "complex" expression that has the logical 'and' etc, maybe the code could just use

__builtin_constant_p((x)+(y))

or something.

But yeah:

Quoted 2 lines

Sigh. Wasn't there some talk about modernizing our toolchain requirements?

Maybe it's just time to give up on 4.4. We wanted 4.5 for "asm goto", and once we upgrade to 4.5 I think Arnd said that no distro actually ships it, so we might as well go to 4.6.

So maybe this is just the excuse to finally make that official, if there is no clever workaround any more.

I wonder which gcc versions actually accept Kees's addition.

Quoted 2 lines · Andrew Morton

I wonder which gcc versions actually accept Kees's addition.

Note that we already do have this pattern, as seen by:

git grep -2 __builtin_choose_expr | grep -2 __builtin_constant_p

which show drivers/pinctrl/intel/pinctrl-intel.h, so the pattern already exists current kernels and _works_ - it apparently just doesn't work in slightly more complicated cases.

It's one reason why I wondered if simplifying the expression to have just that single __builtin_constant_p() might not end up working..

--
Kees Cook
Pixel Security<div class="gmail_extra"><br><div class="gmail_quote">On [...]

WTF, gmail just blasted HTML into my explicitly plain-text email?! Apologies...

Quoted 2 lines

It's one reason why I wondered if simplifying the expression to have just that single __builtin_constant_p() might not end up working..

Yeah, it seems like it doesn't bail out as "false" for complex expressions given to __builtin_constant_p().

If no magic solution, then which of these?

- go back to my original "multi-eval max only for constants" macro (meh)
- add gcc version checks around this and similarly for -Wvla in the future (eww)
- raise gcc version (yikes)

Replacing the __builtin_choose_expr() with ?: works of course.

What will be the runtime effects?

Quoted 2 lines · Andrew Morton

Replacing the __builtin_choose_expr() with ?: works of course.

Hmm. That sounds like the right thing to do. We were so myopically staring at the __builtin_choose_expr() problem that we overlooked the obvious solution.

Using __builtin_constant_p() together with a ?: is in fact our common pattern, so that should be fine. The only real reason to use __builtin_choose_expr() is if you want to get the *type* to vary depending on which side you choose, but that's not an issue for min/max.

Quoted 9 lines · Linus Torvalds

Quoted 2 lines · Andrew Morton

Replacing the __builtin_choose_expr() with ?: works of course.

Hmm. That sounds like the right thing to do. We were so myopically staring at the __builtin_choose_expr() problem that we overlooked the obvious solution.

Quoted 5 lines

Using __builtin_constant_p() together with a ?: is in fact our common pattern, so that should be fine. The only real reason to use __builtin_choose_expr() is if you want to get the *type* to vary depending on which side you choose, but that's not an issue for min/max.

This doesn't solve it for -Wvla, unfortunately. That was the point of Josh's original suggestion of __builtin_choose_expr().

Try building with KCFLAGS=-Wval and checking net/ipv6/proc.c:

net/ipv6/proc.c: In function ‘snmp6_seq_show_item’:
net/ipv6/proc.c:198:2: warning: ISO C90 forbids array ‘buff’ whose size can’t be evaluated [-Wvla]
unsigned long buff[SNMP_MIB_MAX];
^~~~~~~~

Quoted 20 lines · On Mon, 12 Mar 2018 21:28:57 -0700 Kees Cook <[email protected]> wrote:

Quoted 9 lines · Linus Torvalds

Quoted 2 lines · Andrew Morton

Replacing the __builtin_choose_expr() with ?: works of course.

Hmm. That sounds like the right thing to do. We were so myopically staring at the __builtin_choose_expr() problem that we overlooked the obvious solution.

Quoted 5 lines

Using __builtin_constant_p() together with a ?: is in fact our common pattern, so that should be fine. The only real reason to use __builtin_choose_expr() is if you want to get the *type* to vary depending on which side you choose, but that's not an issue for min/max.

This doesn't solve it for -Wvla, unfortunately. That was the point of Josh's original suggestion of __builtin_choose_expr().

Quoted 7 lines

Try building with KCFLAGS=-Wval and checking net/ipv6/proc.c:

net/ipv6/proc.c: In function ‘snmp6_seq_show_item’:
net/ipv6/proc.c:198:2: warning: ISO C90 forbids array ‘buff’ whose size can’t be evaluated [-Wvla]
unsigned long buff[SNMP_MIB_MAX];
^~~~~~~~

PITA. Didn't we once have a different way of detecting VLAs? Some post-compilation asm parser, iirc.

I suppose the world wouldn't end if we had a gcc version ifdef in kernel.h. We'll get to remove it in, oh, ten years.

Sent: 13 March 2018 22:15

I'll send a "const_max()" which will refuse to work on non-constant-values (so it doesn't get accidentally used on variables that could be exposed to double-evaluation), and will work for stack array declarations (to avoid the overly-sensitive -Wvla checks).

Quoted 14 lines · On Fri, 9 Mar 2018 12:05:36 -0800 Kees Cook <[email protected]> wrote:

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

$ diff -u before.txt after.txt | grep ^-

(quoted diff) +0 -6

-drivers/input/touchscreen/cyttsp4_core.c:871:2: warning: ISO C90 forbids variable length array ‘ids’ [-Wvla]
-fs/btrfs/tree-checker.c:344:4: warning: ISO C90 forbids variable length array ‘namebuf’ [-Wvla]
-lib/vsprintf.c:747:2: warning: ISO C90 forbids variable length array ‘sym’ [-Wvla]
-net/ipv4/proc.c:403:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:198:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:218:2: warning: ISO C90 forbids variable length array ‘buff64’ [-Wvla]

Quoted 1 line

Based on an earlier patch from Josh Poimboeuf.

v1, v2 and v3 of this patch all fail with gcc-4.4.4:

./include/linux/jiffies.h: In function 'jiffies_delta_to_clock_t':
./include/linux/jiffies.h:444: error: first argument to '__builtin_choose_expr' not a constant

gcc --version

That's with

#define __max(t1, t2, x, y)						\
	__builtin_choose_expr(__builtin_constant_p(x) &&		\
			      __builtin_constant_p(y) &&		\
			      __builtin_types_compatible_p(t1, t2),	\
			      (t1)(x) > (t2)(y) ? (t1)(x) : (t2)(y),	\
			      __single_eval_max(t1, t2,			\
						__UNIQUE_ID(max1_),	\
						__UNIQUE_ID(max2_),	\
						x, y))

/**
* max - return maximum of two values of the same or compatible types
* @x: first value
* @y: second value
*/
#define max(x, y) __max(typeof(x), typeof(y), x, y)

A brief poke failed to reveal a workaround - gcc-4.4.4 doesn't appear to know that __builtin_constant_p(x) is a constant. Or something.

Sigh. Wasn't there some talk about modernizing our toolchain requirements?

Quoted 20 lines · Andrew Morton

Quoted 14 lines · On Fri, 9 Mar 2018 12:05:36 -0800 Kees Cook <[email protected]> wrote:

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

$ diff -u before.txt after.txt | grep ^-

(quoted diff) +0 -6

-drivers/input/touchscreen/cyttsp4_core.c:871:2: warning: ISO C90 forbids variable length array ‘ids’ [-Wvla]
-fs/btrfs/tree-checker.c:344:4: warning: ISO C90 forbids variable length array ‘namebuf’ [-Wvla]
-lib/vsprintf.c:747:2: warning: ISO C90 forbids variable length array ‘sym’ [-Wvla]
-net/ipv4/proc.c:403:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:198:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:218:2: warning: ISO C90 forbids variable length array ‘buff64’ [-Wvla]

Quoted 1 line

Based on an earlier patch from Josh Poimboeuf.

v1, v2 and v3 of this patch all fail with gcc-4.4.4:

Quoted 2 lines

./include/linux/jiffies.h: In function 'jiffies_delta_to_clock_t':
./include/linux/jiffies.h:444: error: first argument to '__builtin_choose_expr' not a constant

I'm seeing that problem with

Quoted 1 line

gcc --version

gcc (SUSE Linux) 4.8.5

Quoted 25 lines · Randy Dunlap

Quoted 22 lines · Andrew Morton

Quoted 14 lines · On Fri, 9 Mar 2018 12:05:36 -0800 Kees Cook <[email protected]> wrote:

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

$ diff -u before.txt after.txt | grep ^-

(quoted diff) +0 -6

-drivers/input/touchscreen/cyttsp4_core.c:871:2: warning: ISO C90 forbids variable length array ‘ids’ [-Wvla]
-fs/btrfs/tree-checker.c:344:4: warning: ISO C90 forbids variable length array ‘namebuf’ [-Wvla]
-lib/vsprintf.c:747:2: warning: ISO C90 forbids variable length array ‘sym’ [-Wvla]
-net/ipv4/proc.c:403:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:198:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:218:2: warning: ISO C90 forbids variable length array ‘buff64’ [-Wvla]

Quoted 1 line

Based on an earlier patch from Josh Poimboeuf.

v1, v2 and v3 of this patch all fail with gcc-4.4.4:

./include/linux/jiffies.h: In function 'jiffies_delta_to_clock_t':
./include/linux/jiffies.h:444: error: first argument to '__builtin_choose_expr' not a constant

Quoted 3 lines

I'm seeing that problem with

Quoted 1 line

gcc --version

gcc (SUSE Linux) 4.8.5

Same here, 4.8.5 fails. gcc 5.4.1 seems to work. I compiled a minimal 5.1.0 and it seems to work as well.

Just compiled 4.9.0 and it seems to work -- so that would be the minimum required.

Sigh...

Some enterprise distros are either already shipping gcc >= 5 or will probably be shipping it soon (e.g. RHEL 8), so how much does it hurt to ask for a newer gcc? Are there many users/companies out there using enterprise distributions' gcc to compile and run the very latest kernels?

Quoted 25 lines · Randy Dunlap

Quoted 22 lines · Andrew Morton

Quoted 14 lines · On Fri, 9 Mar 2018 12:05:36 -0800 Kees Cook <[email protected]> wrote:

When max() is used in stack array size calculations from literal values (e.g. "char foo[max(sizeof(struct1), sizeof(struct2))]", the compiler thinks this is a dynamic calculation due to the single-eval logic, which is not needed in the literal case. This change removes several accidental stack VLAs from an x86 allmodconfig build:

$ diff -u before.txt after.txt | grep ^-

(quoted diff) +0 -6

-drivers/input/touchscreen/cyttsp4_core.c:871:2: warning: ISO C90 forbids variable length array ‘ids’ [-Wvla]
-fs/btrfs/tree-checker.c:344:4: warning: ISO C90 forbids variable length array ‘namebuf’ [-Wvla]
-lib/vsprintf.c:747:2: warning: ISO C90 forbids variable length array ‘sym’ [-Wvla]
-net/ipv4/proc.c:403:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:198:2: warning: ISO C90 forbids variable length array ‘buff’ [-Wvla]
-net/ipv6/proc.c:218:2: warning: ISO C90 forbids variable length array ‘buff64’ [-Wvla]

Quoted 1 line

Based on an earlier patch from Josh Poimboeuf.

v1, v2 and v3 of this patch all fail with gcc-4.4.4:

./include/linux/jiffies.h: In function 'jiffies_delta_to_clock_t':
./include/linux/jiffies.h:444: error: first argument to '__builtin_choose_expr' not a constant

Quoted 3 lines

I'm seeing that problem with

Quoted 1 line

gcc --version

gcc (SUSE Linux) 4.8.5

Same here, 4.8.5 fails. gcc 5.4.1 seems to work. I compiled a minimal 5.1.0 and it seems to work as well.

And sparse freaks out too:

drivers/net/ethernet/via/via-velocity.c:97:26: sparse: incorrect
type in initializer (different address spaces) @@ expected void
*addr @@ got struct mac_regs [noderef] <avoid *addr @@

Alright, I'm giving up on fixing max(). I'll go back to STACK_MAX() or some other name for the simple macro. Bleh.

Quoted 3 lines · Kees Cook

Alright, I'm giving up on fixing max(). I'll go back to STACK_MAX() or some other name for the simple macro. Bleh.

Oh, and I'm starting to see the real problem.

It's not that our current "min/max()" are broiken. It's that "-Wvla" is garbage.

Lookie here:

        int array[(1,2)];

results in gcc saying

     warning: ISO C90 forbids variable length array ‘array’ [-Wvla]
       int array[(1,2)];
       ^~~

and that error message - and the name of the flag - is obviously pure garbage.

What is *actually* going on is that ISO C90 requires an array size to be not a constant value, but a constant *expression*. Those are two different things.

A constant expression has little to do with "compile-time constant". It's a more restricted form of it, and has actual syntax requirements. A comma expression is not a constant expression, for example, which was why I tested this.

So "-Wvla" is garbage, with a misleading name, and a misleading warning string. It has nothing to do with "variable length" and whether the compiler can figure it out at build time, and everything to do with a _syntax_ rule.

So the warning is probably implemented to just trigger whenever VLAs are used but the given standard does not allow them, for all languages. The problem is why the ISO C90 frontend is not giving an error for using invalid syntax for array sizes to begin with?

So in *historical* context - when a compiler didn't do variable length arrays at all - the original semantics of C "constant expressions" actually make a ton of sense.

You can basically think of a constant expression as something that can be (historically) handled by the front-end without any real complexity, and no optimization phases - just evaluating a simple parse tree with purely compile-time constants.

So there's a good and perfectly valid reason for why C limits certain expressions to just a very particular subset. It's not just array sizes, it's case statements etc too. And those are very much part of the C standard.

So an error message like

warning: ISO C90 requires array sizes to be constant-expressions

would be technically correct and useful from a portability angle. It tells you when you're doing something non-portable, and should be automatically enabled with "-ansi -pedantic", for example.

So what's misleading is actually the name of the warning and the message, not that it happens. The warning isn't about "variable length", it's literally about the rules for what a "constant-expression" is.

And in C, the expression (2,3) has a constant _value_ (namely 3), but it isn't a constant-expression as specified by the language.

Now, the thing is that once you actually do variable length arrays, those old front-end rules make no sense any more (outside of the "give portability warnings" thing).

Because once you do variable length arrays, you obviously _parse_ everything just fine, and you're doing to evaluate much more complex expressions than some limited constant-expression rule.

And at that point it would make a whole lot more sense to add a *new* warning that basically says "I have to generate code for a variable-sized array", if you actually talk about VLA's.

But that's clearly not what gcc actually did.

So the problem really is that -Wvla doesn't actually warn about VLA's, but about something technically completely different.

And that's why those stupid syntactic issues with min/max matter. It's not whether the end result is a compile-time constant or not, it's about completely different issues, like whether there is a comma-expression in it.

Linus

So an error message like

warning: ISO C90 requires array sizes to be constant-expressions

would be technically correct and useful from a portability angle. It tells you when you're doing something non-portable, and should be automatically enabled with "-ansi -pedantic", for example.

So what's misleading is actually the name of the warning and the message, not that it happens. The warning isn't about "variable length", it's literally about the rules for what a "constant-expression" is.

And in C, the expression (2,3) has a constant _value_ (namely 3), but it isn't a constant-expression as specified by the language.

Now, the thing is that once you actually do variable length arrays, those old front-end rules make no sense any more (outside of the "give portability warnings" thing).

Because once you do variable length arrays, you obviously _parse_ everything just fine, and you're doing to evaluate much more complex expressions than some limited constant-expression rule.

BTW., while I fully agree with everything you said, it's not entirely correct to claim that if a C compiler can generate VLA code it is necessarily able to parse and evaluate constant array sizes "just fine".

Constant expressions are typically parsed very early on, at the preprocessing stage. They can be used with some preprocessor directives as well, such as '#if' (with some further limitations on their syntax).

From: "Steven Rostedt (VMware)" <[email protected]>

Instead of having a separate enum that is the index into another array, like a string array, make a single macro that combines them into a single list, and then the two can not get out of sync. This makes it easier to add and remove items.

The macro trick is:

#define DOGS \

  C( JACK,     "Jack Russell")		\
  C( ITALIAN,  "Italian Greyhound")	\
  C( GERMAN,   "German Shepherd")

#undef C
#define C(a, b) a

enum { DOGS };

#undef C
#define C(a, b) b

static char dogs[] = { DOGS };

Signed-off-by Steven Rostedt (VMware) <[email protected]>

---
 kernel/trace/trace_events_filter.c | 112 ++++++++++++++++---------------------
 1 file changed, 48 insertions(+), 64 deletions(-)

kernel/trace/trace_events_filter.c +48 -64

index c3c6eee1e4df..a2ef393b3bb2 100644
@@ -33,22 +33,26 @@
 	"# Only events with the given fields will be affected.\n"	\
 	"# If no events are modified, an error message will be displayed here"
 
-enum filter_op_ids
-{
-	OP_OR,
-	OP_AND,
-	OP_GLOB,
-	OP_NE,
-	OP_EQ,
-	OP_LT,
-	OP_LE,
-	OP_GT,
-	OP_GE,
-	OP_BAND,
-	OP_NOT,
-	OP_NONE,
-	OP_OPEN_PAREN,
-};
+#define OPS					\
+	C( OP_OR,	"||",		1 ),	\
+	C( OP_AND,	"&&",		2 ),	\
+	C( OP_GLOB,	"~",		4 ),	\
+	C( OP_NE,	"!=",		4 ),	\
+	C( OP_EQ,	"==",		4 ),	\
+	C( OP_LT,	"<",		5 ),	\
+	C( OP_LE,	"<=",		5 ),	\
+	C( OP_GT,	">",		5 ),	\
+	C( OP_GE,	">=",		5 ),	\
+	C( OP_BAND,	"&",		6 ),	\
+	C( OP_NOT,	"!",		6 ),	\
+	C( OP_NONE,	"OP_NONE",	0 ),	\
+	C( OP_OPEN_PAREN, "(",		0 ),	\
+	C( OP_MAX,	NULL,		0 )
+
+#undef C
+#define C(a, b, c)	a
+
+enum filter_op_ids { OPS };
 
 struct filter_op {
 	int id;

@@ -56,56 +60,36 @@ struct filter_op {
 	int precedence;
 };
 
-/* Order must be the same as enum filter_op_ids above */
-static struct filter_op filter_ops[] = {
-	{ OP_OR,	"||",		1 },
-	{ OP_AND,	"&&",		2 },
-	{ OP_GLOB,	"~",		4 },
-	{ OP_NE,	"!=",		4 },
-	{ OP_EQ,	"==",		4 },
-	{ OP_LT,	"<",		5 },
-	{ OP_LE,	"<=",		5 },
-	{ OP_GT,	">",		5 },
-	{ OP_GE,	">=",		5 },
-	{ OP_BAND,	"&",		6 },
-	{ OP_NOT,	"!",		6 },
-	{ OP_NONE,	"OP_NONE",	0 },
-	{ OP_OPEN_PAREN, "(",		0 },
-};
+#undef C
+#define C(a, b, c)	{ a, b, c }
 
-enum {
-	FILT_ERR_NONE,
-	FILT_ERR_INVALID_OP,
-	FILT_ERR_UNBALANCED_PAREN,
-	FILT_ERR_TOO_MANY_OPERANDS,
-	FILT_ERR_OPERAND_TOO_LONG,
-	FILT_ERR_FIELD_NOT_FOUND,
-	FILT_ERR_ILLEGAL_FIELD_OP,
-	FILT_ERR_ILLEGAL_INTVAL,
-	FILT_ERR_BAD_SUBSYS_FILTER,
-	FILT_ERR_TOO_MANY_PREDS,
-	FILT_ERR_MISSING_FIELD,
-	FILT_ERR_INVALID_FILTER,
-	FILT_ERR_IP_FIELD_ONLY,
-	FILT_ERR_ILLEGAL_NOT_OP,
-};
+static struct filter_op filter_ops[] = { OPS };
 
-static char *err_text[] = {
-	"No error",
-	"Invalid operator",
-	"Unbalanced parens",
-	"Too many operands",
-	"Operand too long",
-	"Field not found",
-	"Illegal operation for field type",
-	"Illegal integer value",
-	"Couldn't find or set field in one of a subsystem's events",
-	"Too many terms in predicate expression",
-	"Missing field name and/or value",
-	"Meaningless filter expression",
-	"Only 'ip' field is supported for function trace",
-	"Illegal use of '!'",
-};
+#define ERRORS								\
+	C( NONE,	 	"No error"),				\
+	C( INVALID_OP,		"Invalid operator"),			\
+	C( UNBALANCED_PAREN,	"Unbalanced parens"),			\
+	C( TOO_MANY_OPERANDS,	"Too many operands"),			\
+	C( OPERAND_TOO_LONG,	"Operand too long"),			\
+	C( FIELD_NOT_FOUND,	"Field not found"),			\
+	C( ILLEGAL_FIELD_OP,	"Illegal operation for field type"),	\
+	C( ILLEGAL_INTVAL,	"Illegal integer value"),		\
+	C( BAD_SUBSYS_FILTER,	"Couldn't find or set field in one of a subsystem's events"), \
+	C( TOO_MANY_PREDS,	"Too many terms in predicate expression"), \
+	C( MISSING_FIELD,	"Missing field name and/or value"),	\
+	C( INVALID_FILTER,	"Meaningless filter expression"),	\
+	C( IP_FIELD_ONLY,	"Only 'ip' field is supported for function trace"), \
+	C( ILLEGAL_NOT_OP,	"Illegal use of '!'"),
+
+#undef C
+#define C(a, b)		FILT_ERR_##a
+
+enum { ERRORS };
+
+#undef C
+#define C(a, b)		b
+
+static char *err_text[] = { ERRORS };
 
 struct opstack_op {
 	enum filter_op_ids op;

Signature · 1 line

2.15.1

From: "Steven Rostedt (VMware)" <[email protected]>

The pred_funcs_##type arrays consist of five functions that are assigned based on the ops. The array must be in the same order of the ops each function represents. The PRED_FUNC_START macro denotes the op enum that starts the op that maps to the pred_funcs_##type arrays. This is all very subtle and prone to bugs if the code is changed.

Add comments describing how PRED_FUNC_START and pred_funcs_##type array is used, and also a PRED_FUNC_MAX that is the maximum number of functions in the arrays.

Clean up select_comparison_fn() that assigns the predicates to the pred_funcs_##type array function as well as add protection in case an op is passed in that does not map correctly to the array.

Signed-off-by Steven Rostedt (VMware) <[email protected]>

---
 kernel/trace/trace_events_filter.c | 46 ++++++++++++++++++++++++++------------
 1 file changed, 32 insertions(+), 14 deletions(-)

kernel/trace/trace_events_filter.c +32 -14

index a2ef393b3bb2..9d383f4383dc 100644
@@ -65,6 +65,13 @@ struct filter_op {
 
 static struct filter_op filter_ops[] = { OPS };
 
+/*
+ * pred functions are OP_LT, OP_LE, OP_GT, OP_GE, and OP_BAND
+ * pred_funcs_##type below must match the order of them above.
+ */
+#define PRED_FUNC_START			OP_LT
+#define PRED_FUNC_MAX			(OP_BAND - PRED_FUNC_START)
+
 #define ERRORS								\
 	C( NONE,	 	"No error"),				\
 	C( INVALID_OP,		"Invalid operator"),			\

@@ -172,8 +179,6 @@ static const filter_pred_fn_t pred_funcs_##type[] = {			\
 	filter_pred_BAND_##type,					\
 };
 
-#define PRED_FUNC_START			OP_LT
-
 #define DEFINE_EQUALITY_PRED(size)					\
 static int filter_pred_##size(struct filter_pred *pred, void *event)	\
 {									\

@@ -946,39 +951,52 @@ static filter_pred_fn_t select_comparison_fn(enum filter_op_ids op,
 					    int field_size, int field_is_signed)
 {
 	filter_pred_fn_t fn = NULL;
+	int pred_func_index = -1;
+
+	switch (op) {
+	case OP_EQ:
+	case OP_NE:
+		break;
+	default:
+		if (WARN_ON_ONCE(op < PRED_FUNC_START))
+			return NULL;
+		pred_func_index = op - PRED_FUNC_START;
+		if (WARN_ON_ONCE(pred_func_index > PRED_FUNC_MAX))
+			return NULL;
+	}
 
 	switch (field_size) {
 	case 8:
-		if (op == OP_EQ || op == OP_NE)
+		if (pred_func_index < 0)
 			fn = filter_pred_64;
 		else if (field_is_signed)
-			fn = pred_funcs_s64[op - PRED_FUNC_START];
+			fn = pred_funcs_s64[pred_func_index];
 		else
-			fn = pred_funcs_u64[op - PRED_FUNC_START];
+			fn = pred_funcs_u64[pred_func_index];
 		break;
 	case 4:
-		if (op == OP_EQ || op == OP_NE)
+		if (pred_func_index < 0)
 			fn = filter_pred_32;
 		else if (field_is_signed)
-			fn = pred_funcs_s32[op - PRED_FUNC_START];
+			fn = pred_funcs_s32[pred_func_index];
 		else
-			fn = pred_funcs_u32[op - PRED_FUNC_START];
+			fn = pred_funcs_u32[pred_func_index];
 		break;
 	case 2:
-		if (op == OP_EQ || op == OP_NE)
+		if (pred_func_index < 0)
 			fn = filter_pred_16;
 		else if (field_is_signed)
-			fn = pred_funcs_s16[op - PRED_FUNC_START];
+			fn = pred_funcs_s16[pred_func_index];
 		else
-			fn = pred_funcs_u16[op - PRED_FUNC_START];
+			fn = pred_funcs_u16[pred_func_index];
 		break;
 	case 1:
-		if (op == OP_EQ || op == OP_NE)
+		if (pred_func_index < 0)
 			fn = filter_pred_8;
 		else if (field_is_signed)
-			fn = pred_funcs_s8[op - PRED_FUNC_START];
+			fn = pred_funcs_s8[pred_func_index];
 		else
-			fn = pred_funcs_u8[op - PRED_FUNC_START];
+			fn = pred_funcs_u8[pred_func_index];
 		break;
 	}
 

Signature · 1 line

2.15.1

 2 files changed, 1050 insertions(+), 1273 deletions(-)

Quoted 1 line · On Fri, 09 Mar 2018 21:34:45 -0500 Steven Rostedt <[email protected]> wrote:

 2 files changed, 1050 insertions(+), 1273 deletions(-)  

BTW, it's a bit bigger impact than 223 deletions. As I added a lot of comments to explain the logic better. Removing comments and white space from the modifications we have:

649 insertions(+), 1035 deletions(-)

That's 386 lines of code removed.

-- Steve

Sorry for the spam.

 2 files changed, 1050 insertions(+), 1273 deletions(-)  

+ * n3: r=c; r=!r; l3: if (r) goto l4;
+ * n4: r=g; r=!r; l4: if (r) goto l5;
+ * n5: r=d; l5: if (r) goto T
+ * n6: r=e; l6: if (!r) goto l7;
+ * n7: r=f; r=!r; l7: if (!r) goto F
+ * T: return TRUE
+ * F: return FALSE

On Fri, Mar 09, 2018 at 09:34:45PM -0500, Steven Rostedt wrote:

SNIP

Quoted 1 line

kernel/trace/trace_events_filter.c enum { ERRORS }; · line 168

Quoted 10 lines

kernel/trace/trace_events_filter.c +9 -1

-/* If not of not match is equal to not of not, then it is a match */
+/*
+ * Without going into a formal proof, this explains the method that is used in
+ * parsing the logical expressions.
+ *
+ * For example, if we have: "a && !(!b || (c && g)) || d || e && !f"
+ * The first pass will convert it into the following program:
+ *
+ * n1: r=a;       l1: if (!r) goto l4;
+ * n2: r=b;       l2: if (!r) goto l4;  

got stuck in here.. should that be 'goto l5' ?

jirka

Quoted 7 lines

+ * n3: r=c; r=!r; l3: if (r) goto l4;
+ * n4: r=g; r=!r; l4: if (r) goto l5;
+ * n5: r=d; l5: if (r) goto T
+ * n6: r=e; l6: if (!r) goto l7;
+ * n7: r=f; r=!r; l7: if (!r) goto F
+ * T: return TRUE
+ * F: return FALSE

jirka

From: "Steven Rostedt (VMware)" <[email protected]>

Al Viro reviewed the filter logic of ftrace trace events and found it to be very troubling. It creates a binary tree based on the logic operators and walks it during tracing. He sent myself and Tom Zanussi a long explanation (and formal proof) of how to do the string parsing better and end up with a program array that can be simply iterated to come up with the correct results.

I took his ideas and his pseudo code and rewrote the filter logic based on them. In doing so, I was able to remove a lot of code, and have a much more condensed filter logic in the process. I wrote a very long comment describing the methadology that Al proposed in my own words. For more info on how this works, read the comment above predicate_parse().

Suggested-by Al Viro <[email protected]>

Signed-off-by Steven Rostedt (VMware) <[email protected]>

got it crashed when clearing the filter via 'echo > filter'

Quoted 1 line · On Mon, 12 Mar 2018 16:10:17 +0100 Jiri Olsa <[email protected]> wrote:

got it crashed when clearing the filter via 'echo > filter'

Awesome. I'll go and test this out. Thanks!

Hmm, could you pull my tree and test my branch: ftrace/core. I may have already fixed this but haven't posted the latest (which I'll do before pushing to next).

Quoted 5 lines · Steven Rostedt

Quoted 1 line · On Mon, 12 Mar 2018 16:10:17 +0100 Jiri Olsa <[email protected]> wrote:

got it crashed when clearing the filter via 'echo > filter'

Quoted 5 lines

Awesome. I'll go and test this out. Thanks!

Hmm, could you pull my tree and test my branch: ftrace/core. I may have already fixed this but haven't posted the latest (which I'll do before pushing to next).

I couldn't apply your patches from mailbox so I used your ftrace/core already

Quoted 5 lines · Steven Rostedt

Quoted 1 line · On Mon, 12 Mar 2018 16:10:17 +0100 Jiri Olsa <[email protected]> wrote:

got it crashed when clearing the filter via 'echo > filter'

Quoted 5 lines

Awesome. I'll go and test this out. Thanks!

Hmm, could you pull my tree and test my branch: ftrace/core. I may have already fixed this but haven't posted the latest (which I'll do before pushing to next).

I couldn't apply your patches from mailbox so I used your ftrace/core already

Quoted 8 lines · On Mon, 12 Mar 2018 19:54:14 +0100 Jiri Olsa <[email protected]> wrote:

Quoted 7 lines · Steven Rostedt

Quoted 1 line · On Mon, 12 Mar 2018 16:10:17 +0100 Jiri Olsa <[email protected]> wrote:

got it crashed when clearing the filter via 'echo > filter'

Awesome. I'll go and test this out. Thanks!

Quoted 6 lines

Quoted 3 lines

Hmm, could you pull my tree and test my branch: ftrace/core. I may have already fixed this but haven't posted the latest (which I'll do before pushing to next).

I couldn't apply your patches from mailbox so I used your ftrace/core already

Jiri, If you apply the below, does it fix it for you?

-- Steve

kernel/trace/trace_events_filter.c +7 -4

index a5a131ec3c9c..4099e141188c 100644
@@ -1498,11 +1498,14 @@ static int process_preds(struct trace_event_call *call,
 		return ret;
 	}
 
-	prog = predicate_parse(filter_string, nr_parens, nr_preds,
+	if (!nr_preds) {
+		prog = NULL;
+	} else {
+		prog = predicate_parse(filter_string, nr_parens, nr_preds,
 			       parse_pred, call, pe);
-	if (IS_ERR(prog))
-		return PTR_ERR(prog);
-
+		if (IS_ERR(prog))
+			return PTR_ERR(prog);
+	}
 	rcu_assign_pointer(filter->prog, prog);
 	return 0;
 }

Quoted 1 line

Jiri, If you apply the below, does it fix it for you?

yes, the crash is gone and I can set filter ftrace/function,

but I'm still having some issues put that filter through perf

  # perf record -e ftrace:function --filter "ip == 0xffffffffa41e8490" ls

but I might be just missing something.. it's been a while ;-) I'm looking to that

Quoted 3 lines · On Tue, 13 Mar 2018 11:14:01 +0100 Jiri Olsa <[email protected]> wrote:

Quoted 1 line

Jiri, If you apply the below, does it fix it for you?

yes, the crash is gone and I can set filter ftrace/function,

Great!

Quoted 5 lines

but I'm still having some issues put that filter through perf

  # perf record -e ftrace:function --filter "ip == 0xffffffffa41e8490" ls

but I might be just missing something.. it's been a while ;-) I'm looking to that

I have to ask. Did that work with the old code? The ftrace filter was special in the old code and I tried to simulate it in the new code. I'm not sure I checked if ip can take an address, but from what the code looked like, it wouldn't. It looked like it required a name of a function. Something that gets passed into "set_ftrace_filter" which is not an address.

So instead of doing something like:

perf record -e ftrace:function --filter "ip == 0xffffffff810ccfa0" ls

You would need to do

perf record -e ftrace:function --filter "ip == schedule_tail" ls

because perf doesn't use the filter for the function, it uses the ftrace_ops->hash tables. If it would simply take the address, we could just use the trace_events_filter logic, and not make it a special case.

Special thanks goes out to Al for his patience and his time that he spent in educating us in a proper logical parser.

Two patches were added to do some initial clean up. The last patch implements Al's suggestions. I wrote up a very lengthy comment describing what Al taught us in my own words (hopefully I got it right), and the implementation is similar to what Al showed with a few changes (again, hopefully I got that right too). I tested this with lots of different filters and it looks to be holding up.

Jiri,

This affects perf as well. I ran some tests and I believe I got it woking as it does today.