Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [RFCv2] string: Use faster alternatives when constant arguments
 are used
To:     Sultan Alsawaf <sultan@kerneltoast.com>, akpm@linux-foundation.org,
        linux-kernel@vger.kernel.org
References: <20190324014445.28688-1-sultan@kerneltoast.com>
 <20190324022406.GA18988@sultan-box.localdomain>
From:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc:     Nathan Chancellor <natechancellor@gmail.com>
Message-ID: <2293c54f-40b1-1e59-665a-bd8f2cb957d2@rasmusvillemoes.dk>
Date:   Sun, 24 Mar 2019 22:17:49 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.5.1
MIME-Version: 1.0
In-Reply-To: <20190324022406.GA18988@sultan-box.localdomain>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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@kerneltoast.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