[PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Mathias Krause]

The alt_max_short() macro in asm/alternative.h does not work as
intended, leading to nasty bugs. E.g. alt_max_short("1", "3")
evaluates to 3, but alt_max_short("3", "1") evaluates to 1 -- not
exactly the maximum of 1 and 3.

In fact, I had to learn it the hard way by crashing my kernel in not
so funny ways by attempting to make use of the ALTENATIVE_2 macro
with alternatives where the first one was larger than the second
one.

According to [1] and commit dbe4058a6a44 ("x86/alternatives: Fix
ALTERNATIVE_2 padding generation properly") the right handed side
should read "-(-(a < b))" not "-(-(a - b))". Fix that, to make the
macro work as intended.

While at it, fix up the comment regarding the additional "-", too.
It's not about gas' usage of s32 but brain dead logic of having a
"true" value of -1 for the < operator ... *sigh*

Btw., the one in asm/alternative-asm.h is correct. And, apparently,
all current users of ALTERNATIVE_2() pass same sized alternatives,
avoiding to hit the bug.

[1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

Fixes: dbe4058a6a44 ("x86/alternatives: Fix ALTERNATIVE_2 padding generation properly")
Signed-off-by: Mathias Krause <minipli@googlemail.com>
Cc: Borislav Petkov <bp@suse.de>
---
 arch/x86/include/asm/alternative.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/arch/x86/include/asm/alternative.h b/arch/x86/include/asm/alternative.h
index c096624137ae..7c553f48f163 100644
--- a/arch/x86/include/asm/alternative.h
+++ b/arch/x86/include/asm/alternative.h
@@ -106,9 +106,9 @@ static inline int alternatives_text_reserved(void *start, void *end)
  * max without conditionals. Idea adapted from:
  * http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
  *
- * The additional "-" is needed because gas works with s32s.
+ * The additional "-" is needed because gas uses a "true" value of -1.
  */
-#define alt_max_short(a, b)	"((" a ") ^ (((" a ") ^ (" b ")) & -(-((" a ") - (" b ")))))"
+#define alt_max_short(a, b)	"((" a ") ^ (((" a ") ^ (" b ")) & -(-((" a ") < (" b ")))))"
 
 /*
  * Pad the second replacement alternative with additional NOPs if it is
-- 
1.7.10.4

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Borislav Petkov]

On Wed, Oct 04, 2017 at 08:08:12PM +0200, Mathias Krause wrote:
> The alt_max_short() macro in asm/alternative.h does not work as
> intended, leading to nasty bugs. E.g. alt_max_short("1", "3")
> evaluates to 3, but alt_max_short("3", "1") evaluates to 1 -- not
> exactly the maximum of 1 and 3.
> 
> In fact, I had to learn it the hard way by crashing my kernel in not
> so funny ways by attempting to make use of the ALTENATIVE_2 macro
> with alternatives where the first one was larger than the second
> one.
> 
> According to [1] and commit dbe4058a6a44 ("x86/alternatives: Fix
> ALTERNATIVE_2 padding generation properly") the right handed side
> should read "-(-(a < b))" not "-(-(a - b))". Fix that, to make the
> macro work as intended.
> 
> While at it, fix up the comment regarding the additional "-", too.
> It's not about gas' usage of s32 but brain dead logic of having a
> "true" value of -1 for the < operator ... *sigh*
> 
> Btw., the one in asm/alternative-asm.h is correct. And, apparently,
> all current users of ALTERNATIVE_2() pass same sized alternatives,
> avoiding to hit the bug.
> 
> [1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
> 
> Fixes: dbe4058a6a44 ("x86/alternatives: Fix ALTERNATIVE_2 padding generation properly")
> Signed-off-by: Mathias Krause <minipli@googlemail.com>
> Cc: Borislav Petkov <bp@suse.de>
> ---
>  arch/x86/include/asm/alternative.h |    4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/arch/x86/include/asm/alternative.h b/arch/x86/include/asm/alternative.h
> index c096624137ae..7c553f48f163 100644
> --- a/arch/x86/include/asm/alternative.h
> +++ b/arch/x86/include/asm/alternative.h
> @@ -106,9 +106,9 @@ static inline int alternatives_text_reserved(void *start, void *end)
>   * max without conditionals. Idea adapted from:
      ^^^^^^^^^^^^^^^^^^^^^^^^^

You did read this part, right?

AFAIR, gas can't stomach conditionals but I don't remember the details
anymore. Could be that -1 representation of "true". Let me add Micha to
CC.

Anyway, how can I reproduce your observation? Code snippet and compiler
pls.

Thx.

-- 
Regards/Gruss,
    Boris.

Good mailing practices for 400: avoid top-posting and trim the reply.

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Mathias Krause]

On 5 October 2017 at 09:38, Borislav Petkov <bp@alien8.de> wrote:
> On Wed, Oct 04, 2017 at 08:08:12PM +0200, Mathias Krause wrote:
>> The alt_max_short() macro in asm/alternative.h does not work as
>> intended, leading to nasty bugs. E.g. alt_max_short("1", "3")
>> evaluates to 3, but alt_max_short("3", "1") evaluates to 1 -- not
>> exactly the maximum of 1 and 3.
>>
>> In fact, I had to learn it the hard way by crashing my kernel in not
>> so funny ways by attempting to make use of the ALTENATIVE_2 macro
>> with alternatives where the first one was larger than the second
>> one.
>>
>> According to [1] and commit dbe4058a6a44 ("x86/alternatives: Fix
>> ALTERNATIVE_2 padding generation properly") the right handed side
>> should read "-(-(a < b))" not "-(-(a - b))". Fix that, to make the
>> macro work as intended.
>>
>> While at it, fix up the comment regarding the additional "-", too.
>> It's not about gas' usage of s32 but brain dead logic of having a
>> "true" value of -1 for the < operator ... *sigh*
>>
>> Btw., the one in asm/alternative-asm.h is correct. And, apparently,
>> all current users of ALTERNATIVE_2() pass same sized alternatives,
>> avoiding to hit the bug.
>>
>> [1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
>>
>> Fixes: dbe4058a6a44 ("x86/alternatives: Fix ALTERNATIVE_2 padding generation properly")
>> Signed-off-by: Mathias Krause <minipli@googlemail.com>
>> Cc: Borislav Petkov <bp@suse.de>
>> ---
>>  arch/x86/include/asm/alternative.h |    4 ++--
>>  1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/arch/x86/include/asm/alternative.h b/arch/x86/include/asm/alternative.h
>> index c096624137ae..7c553f48f163 100644
>> --- a/arch/x86/include/asm/alternative.h
>> +++ b/arch/x86/include/asm/alternative.h
>> @@ -106,9 +106,9 @@ static inline int alternatives_text_reserved(void *start, void *end)
>>   * max without conditionals. Idea adapted from:
>       ^^^^^^^^^^^^^^^^^^^^^^^^^
>
> You did read this part, right?

Yes. But it's just wrong the way it is right now. It's a crap number
generator instead of being a "max without conditionals".

> AFAIR, gas can't stomach conditionals but I don't remember the details
> anymore.

Can't be as arch/x86/include/asm/alternative.h itself makes use of
them for the implementation of ALTERNATIVE[_2], see, e.g. __OLDINSTR()
and OLDINSTR_2().

> Could be that -1 representation of "true". Let me add Micha to
> CC.
>
> Anyway, how can I reproduce your observation? Code snippet and compiler
> pls.

Here you go:

$ cat alt_max.c
#ifdef VANILLA
# define alt_max_short(a, b) \
    "((" a ") ^ (((" a ") ^ (" b ")) & -(-((" a ") - (" b ")))))"
#else
# define alt_max_short(a, b) \
    "((" a ") ^ (((" a ") ^ (" b ")) & -(-((" a ") < (" b ")))))"
#endif

#define ams(a, b) \
    "ams_" #a "_" #b " = " alt_max_short(#a, #b) "\n\t"

asm(ams(1, 3)
    ams(3, 1)
    ams(1, 6));

$ gcc -DVANILLA -c alt_max.c && nm alt_max.o
0000000000000003 a ams_1_3
0000000000000002 a ams_1_6
0000000000000001 a ams_3_1
$ gcc -c alt_max.c && nm alt_max.o
0000000000000003 a ams_1_3
0000000000000006 a ams_1_6
0000000000000003 a ams_3_1

Note not only how it gets the max(3,1) case wrong but generates even
more insane crap for max(1,6).

$ as --version | head -1
GNU assembler (GNU Binutils for Debian) 2.25

Cheers,
Mathias

>
> Thx.
>
> --
> Regards/Gruss,
>     Boris.
>
> Good mailing practices for 400: avoid top-posting and trim the reply.

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Mathias Krause]

On 5 October 2017 at 09:58, Mathias Krause <minipli@googlemail.com> wrote:
> On 5 October 2017 at 09:38, Borislav Petkov <bp@alien8.de> wrote:
>> On Wed, Oct 04, 2017 at 08:08:12PM +0200, Mathias Krause wrote:
>>> diff --git a/arch/x86/include/asm/alternative.h b/arch/x86/include/asm/alternative.h
>>> index c096624137ae..7c553f48f163 100644
>>> --- a/arch/x86/include/asm/alternative.h
>>> +++ b/arch/x86/include/asm/alternative.h
>>> @@ -106,9 +106,9 @@ static inline int alternatives_text_reserved(void *start, void *end)
>>>   * max without conditionals. Idea adapted from:
>>       ^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>> You did read this part, right?

Oh, btw., quoting its counter part from arch/x86/include/asm/alternative-asm.h:

/*
 * max without conditionals. Idea adapted from:
 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
 */
#define alt_max_short(a, b) ((a) ^ (((a) ^ (b)) & -(-((a) < (b)))))

Note the "<"! ...comment is wrong, though the implementation works!

Cheers,
Mathias

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Borislav Petkov]

On Thu, Oct 05, 2017 at 02:35:33PM +0200, Mathias Krause wrote:
> Note the "<"! ...comment is wrong, though the implementation works!

I know, I realized that when I looked at alternative-asm.h. Wanted to
double-check it with Micha first.

Testing your patch now...

-- 
Regards/Gruss,
    Boris.

Good mailing practices for 400: avoid top-posting and trim the reply.

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Michael Matz]

Hi,

On Thu, 5 Oct 2017, Borislav Petkov wrote:

> On Thu, Oct 05, 2017 at 02:35:33PM +0200, Mathias Krause wrote:
> > Note the "<"! ...comment is wrong, though the implementation works!
> 
> I know, I realized that when I looked at alternative-asm.h. Wanted to
> double-check it with Micha first.

Yeah, for bit-twiddling the result of arithmetic would need to be 
booleanized first, or alternatively the boolean operators be used in the 
first place.  So if '<' works then that's better in this context.

(In a different context, or in the same one there definitely was a problem 
with using '<', but I can't remember the details, it's too long ago we 
discussed about this; maybe it even was a problem only with some binutils 
versions.  So I'd suggest using the more obvious way until problems 
reoccur, and then document why exactly using relational ops was a problem 
;-) )


Ciao,
Michael.

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Mathias Krause]

On 5 October 2017 at 14:52, Michael Matz <matz@suse.de> wrote:
> On Thu, 5 Oct 2017, Borislav Petkov wrote:
>> On Thu, Oct 05, 2017 at 02:35:33PM +0200, Mathias Krause wrote:
>> > Note the "<"! ...comment is wrong, though the implementation works!
>>
>> I know, I realized that when I looked at alternative-asm.h. Wanted to
>> double-check it with Micha first.
>
> Yeah, for bit-twiddling the result of arithmetic would need to be
> booleanized first, or alternatively the boolean operators be used in the
> first place.  So if '<' works then that's better in this context.

Ack!

> (In a different context, or in the same one there definitely was a problem
> with using '<', but I can't remember the details, it's too long ago we
> discussed about this; maybe it even was a problem only with some binutils
> versions.  So I'd suggest using the more obvious way until problems
> reoccur, and then document why exactly using relational ops was a problem
> ;-) )

Might be because the "true" value of gas' < operator is non-obvious
with being -1. But, well, if you don't know, I don't know either ;)

Anyways, the alt_max_short() macro in alternative.h is plain wrong
while the one in alternative-asm.h works and is used in a few places,
even with varying lengths of the alternatives (e.g.
arch/x86/entry/vdso/vdso32/system_call.S,
arch/x86/lib/{clear_page_64.S,memcpy_64.S,memset_64.S}), therefore
proves to be functional.


Thanks,
Mathias

Re: [PATCH] x86/alternatives: Fix alt_max_short macro to really be a max()

[Borislav Petkov]

On Thu, Oct 05, 2017 at 02:35:33PM +0200, Mathias Krause wrote:
> Oh, btw., quoting its counter part from arch/x86/include/asm/alternative-asm.h:
> 
> /*
>  * max without conditionals. Idea adapted from:
>  * http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
>  */
> #define alt_max_short(a, b) ((a) ^ (((a) ^ (b)) & -(-((a) < (b)))))
> 
> Note the "<"! ...comment is wrong, though the implementation works!

Ok, please fix that comment in alternative-asm.h and add

Reviewed-and-tested-by: Borislav Petkov <bp@suse.de>

to v2 before sending it.

Thanks!

-- 
Regards/Gruss,
    Boris.

Good mailing practices for 400: avoid top-posting and trim the reply.