linux-kernel - Re: [RFCv2] string: Use faster alternatives when constant arguments are used

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <2293c54f-40b1-1e59-665a-bd8f2cb957d2@rasmusvillemoes.dk>
Date:   Sun, 24 Mar 2019 22:17:49 +0100
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Sultan Alsawaf <sultan@...neltoast.com>, akpm@...ux-foundation.org,
        linux-kernel@...r.kernel.org
Cc:     Nathan Chancellor <natechancellor@...il.com>
Subject: Re: [RFCv2] string: Use faster alternatives when constant arguments
 are used

On 24/03/2019 03.24, Sultan Alsawaf wrote:
> I messed up the return value for strcat in the first patch. Here's a fixed
> version, ready for some scathing reviews.
> 
> From: Sultan Alsawaf <sultan@...neltoast.com>
> 
> When strcpy, strcat, and strcmp are used with a literal string, they can
> be optimized to memcpy or memcmp calls.

gcc already knows the semantics of these functions and can optimize
accordingly. E.g. for strcpy() of a literal to a buffer, gcc readily
compiles

void f(char *buf) { strcpy(buf, "1"); }
void g(char *buf) { strcpy(buf, "12"); }
void h(char *buf) { strcpy(buf, "123456"); }

into

0000000000000000 <f>:
   0:   b8 31 00 00 00          mov    $0x31,%eax
   5:   66 89 07                mov    %ax,(%rdi)
   8:   c3                      retq
   9:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)

0000000000000010 <g>:
  10:   b8 31 32 00 00          mov    $0x3231,%eax
  15:   c6 47 02 00             movb   $0x0,0x2(%rdi)
  19:   66 89 07                mov    %ax,(%rdi)
  1c:   c3                      retq
  1d:   0f 1f 00                nopl   (%rax)

0000000000000020 <h>:
  20:   b8 35 36 00 00          mov    $0x3635,%eax
  25:   c7 07 31 32 33 34       movl   $0x34333231,(%rdi)
  2b:   c6 47 06 00             movb   $0x0,0x6(%rdi)
  2f:   66 89 47 04             mov    %ax,0x4(%rdi)
  33:   c3                      retq

These alternatives are faster
> since knowing the length of a string argument beforehand allows
> traversal through the string word at a time

For strcmp(string, "someliteral"), gcc cannot (generate code that does)
read from string beyond a/the first nul byte

>  
> +/*
> + * Replace some common string helpers with faster alternatives when one of the
> + * arguments is a constant (i.e., literal string). This uses strlen instead of
> + * sizeof for calculating the string length in order to silence compiler
> + * warnings that may arise due to what the compiler thinks is incorrect sizeof
> + * usage. The strlen calls on constants are folded into scalar values at compile
> + * time, so performance is not reduced by using strlen.
> + */
> +#define strcpy(dest, src)							\
> +	__builtin_choose_expr(__builtin_constant_p(src),			\
> +		memcpy((dest), (src), strlen(src) + 1),				\
> +		(strcpy)((dest), (src)))

Does this even compile? It's a well-known (or perhaps
not-so-well-known?) pitfall that __builtin_constant_p() is not
guaranteed to be usable in __builtin_choose_expr() - the latter only
accepts bona fide integer constant expressions, while evaluation of
__builtin_constant_p can be delayed until various optimization phases.

> +#define strcat(dest, src)							\
> +	__builtin_choose_expr(__builtin_constant_p(src),			\
> +		({								\
> +			memcpy(strchr((dest), '\0'), (src), strlen(src) + 1);	\
> +			(dest);							\
> +		}),								\
> +		(strcat)((dest), (src)))
> +
> +#define strcmp(dest, src)							\
> +	__builtin_choose_expr(__builtin_constant_p(dest),			\
> +		__builtin_choose_expr(__builtin_constant_p(src),		\
> +			(strcmp)((dest), (src)),				\
> +			memcmp((dest), (src), strlen(dest) + 1)),		\

This seems to be buggy - you don't know that src is at least as long as
dest. And arguing "if it's shorter, there's a nul byte, which will
differ from dest at that point, so memcmp will/should stop" means that
the whole word-at-a-time argument would be out.

Aside from all that, you'd need multiple-evaluation guards. Also, it's a
good idea to give an example of some piece of actual kernel code that
would be compiled differently/better, by simply showing the difference
in disassembly. But even just a toy example as above would be good -
then you might have seen yourself that gcc already recognizes these
functions.

Rasmus