Re: [PATCH] string: Improve the generic strlcpy() implementation

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Alexey Dobriyan]

I want to say two things:

1) strlcpy race

>  * In addition, the implementation is robust to the string changing out
>  * from underneath it, unlike the current strlcpy() implementation.

Canonical OpenBSD version does byte-by-byte copying,
this race is purely Linux invention.

2) strscpy() will copy garbage past NUL from source into destination.
It won't fault but still, who knows what lies after string.

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Alexey Dobriyan <adobriyan@gmail.com> wrote:

> I want to say two things:
> 
> 1) strlcpy race
> 
> >  * In addition, the implementation is robust to the string changing out
> >  * from underneath it, unlike the current strlcpy() implementation.
> 
> Canonical OpenBSD version does byte-by-byte copying,
> this race is purely Linux invention.
> 
> 2) strscpy() will copy garbage past NUL from source into destination.
> It won't fault but still, who knows what lies after string.

So I think your argument is nonsense on several levels:

1)

In 99% of the cases the source string access is not racy so the point is moot.

2)

In the remaining 1% of cases, where the source string might indeed be modified in 
a racy fashion, the only result is that we might get some harmless copy of the end 
of the string _that we would have copied had we been a bit faster_.

I.e. it's violently not 'garbage' - it's portion of a valid string that was valid 
literally a few cycles ago. It's not uninitialized data and it's not data of 
something we should never have gotten access to.

3)

The strscpy() based Linux variant suggested by Linus (for which I sent the patch) 
does not have that small (and harmless) race and is much faster than the OpenBSD 
implementation.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> 
> * Alexey Dobriyan <adobriyan@gmail.com> wrote:
> 
> > I want to say two things:
> > 
> > 1) strlcpy race
> > 
> > >  * In addition, the implementation is robust to the string changing out
> > >  * from underneath it, unlike the current strlcpy() implementation.
> > 
> > Canonical OpenBSD version does byte-by-byte copying,
> > this race is purely Linux invention.
> > 
> > 2) strscpy() will copy garbage past NUL from source into destination.
> > It won't fault but still, who knows what lies after string.
> 
> So I think your argument is nonsense on several levels:

Oh, you are right strscpy() - I mis-read your mail.

So the argument that is nonsensical here is mine!

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> > 2) strscpy() will copy garbage past NUL from source into destination. It won't 
> > fault but still, who knows what lies after string.
> 
> Yes, that's probably worth fixing before we get actual users..

Hm, this is the spot:

                c = *(unsigned long *)(src+res);
                *(unsigned long *)(dest+res) = c;

                if (has_zero(c, &data, &constants)) {
                        data = prep_zero_mask(c, data, &constants);
                        data = create_zero_mask(data);
                        return res + find_zero(data);
                }

We could do something like:

                c = *(unsigned long *)(src+res);
                *(unsigned long *)(dest+res) = c;

                if (has_zero(c, &data, &constants)) {
			unsigned int zero_pos;

                        data = prep_zero_mask(c, data, &constants);
                        data = create_zero_mask(data);

			zero_pos = find_zero(data);
			res += zero_pos;

			memset(dest+res, 0, sizeof(long)-zero_pos);

                        return res;
                }

I.e. the extra memset() clears out the partial word (if any) after the NUL.

Completely untested.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> We could do something like:
> 
>                 c = *(unsigned long *)(src+res);
>                 *(unsigned long *)(dest+res) = c;
> 
>                 if (has_zero(c, &data, &constants)) {
> 			unsigned int zero_pos;
> 
>                         data = prep_zero_mask(c, data, &constants);
>                         data = create_zero_mask(data);
> 
> 			zero_pos = find_zero(data);
> 			res += zero_pos;
> 
> 			memset(dest+res, 0, sizeof(long)-zero_pos);
> 
>                         return res;
>                 }
> 
> I.e. the extra memset() clears out the partial word (if any) after the NUL.

A slightly more paranoid version would be:

		c = *(unsigned long *)(src+res);
 
		if (has_zero(c, &data, &constants)) {
 			unsigned int zero_pos;
 
			data = prep_zero_mask(c, data, &constants);
			data = create_zero_mask(data);
 
 			zero_pos = find_zero(data);

			/* Clear out undefined data within the final word after the NUL: */ 
 			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);

			*(unsigned long *)(dest+res) = c;
 
			return res+zero_pos;
		}
		*(unsigned long *)(dest+res) = c;

This would solve any theoretical races in the _target_ buffer: if the target 
buffer may be copied to user-space in a racy fashion and we don't ever want it to 
have undefined data, then this variant does the tail-zeroing of the final word in 
the temporary copy, not in the target buffer.

Still untested.

Thanks,

	Ingo

[PATCH] string: Fix strscpy() uninitialized data copy bug

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> A slightly more paranoid version would be:
> 
> 		c = *(unsigned long *)(src+res);
>  
> 		if (has_zero(c, &data, &constants)) {
>  			unsigned int zero_pos;
>  
> 			data = prep_zero_mask(c, data, &constants); data = 
> 			create_zero_mask(data);
>  
>  			zero_pos = find_zero(data);
> 
> 			/* Clear out undefined data within the final word after 
> 			the NUL: */
>  			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);
> 
> 			*(unsigned long *)(dest+res) = c;
>  
> 			return res+zero_pos;
> 		}
> 		*(unsigned long *)(dest+res) = c;
> 
> This would solve any theoretical races in the _target_ buffer: if the target 
> buffer may be copied to user-space in a racy fashion and we don't ever want it 
> to have undefined data, then this variant does the tail-zeroing of the final 
> word in the temporary copy, not in the target buffer.
> 
> Still untested.

So the patch below got tested a bit more seriously, with the strscpy() based 
strlcpy() patch I sent earlier: at least a typical Fedora bootup with a few 
thousand strlcpy() uses does not crash in any obvious way.

Still needs review to make sure I have not missed anything ...

Thanks,

	Ingo

===================>
>From 946bab4d7138e5db53c5f1759e97809ebdf89551 Mon Sep 17 00:00:00 2001
From: Ingo Molnar <mingo@kernel.org>
Date: Mon, 5 Oct 2015 18:30:37 +0200
Subject: [PATCH] string: Fix strscpy() uninitialized data copy bug

Alexey Dobriyan noticed that our new strscpy() implementation will copy 
potentially out of range or uninitialized data from post the end of the
source string.

Fix this by zeroing out the tail of the final word of the copy.

Reported-by: Alexey Dobriyan <adobriyan@gmail.com>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 lib/string.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/lib/string.c b/lib/string.c
index 6b89c035df74..548f52b7a145 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -177,12 +177,24 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
 		unsigned long c, data;
 
 		c = *(unsigned long *)(src+res);
-		*(unsigned long *)(dest+res) = c;
+
 		if (has_zero(c, &data, &constants)) {
+			unsigned int zero_pos;
+
 			data = prep_zero_mask(c, data, &constants);
 			data = create_zero_mask(data);
+
+			zero_pos = find_zero(data);
+
+			/* Clear out undefined data within the final word after the NUL (if any): */
+			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);
+
+			*(unsigned long *)(dest+res) = c;
+
 			return res + find_zero(data);
 		}
+		*(unsigned long *)(dest+res) = c;
+
 		res += sizeof(unsigned long);
 		count -= sizeof(unsigned long);
 		max -= sizeof(unsigned long);

Re: [PATCH] string: Fix strscpy() uninitialized data copy bug

[Chris Metcalf]

On 10/05/2015 12:36 PM, Ingo Molnar wrote:
> So the patch below got tested a bit more seriously, with the strscpy() based
> strlcpy() patch I sent earlier: at least a typical Fedora bootup with a few
> thousand strlcpy() uses does not crash in any obvious way.
>
> Still needs review to make sure I have not missed anything ...
>
> Thanks,
>
> 	Ingo
>
> ===================>
>  From 946bab4d7138e5db53c5f1759e97809ebdf89551 Mon Sep 17 00:00:00 2001
> From: Ingo Molnar<mingo@kernel.org>
> Date: Mon, 5 Oct 2015 18:30:37 +0200
> Subject: [PATCH] string: Fix strscpy() uninitialized data copy bug
>
> Alexey Dobriyan noticed that our new strscpy() implementation will copy
> potentially out of range or uninitialized data from post the end of the
> source string.
>
> Fix this by zeroing out the tail of the final word of the copy.
>
> Reported-by: Alexey Dobriyan<adobriyan@gmail.com>
> Signed-off-by: Ingo Molnar<mingo@kernel.org>
> ---
>   lib/string.c | 14 +++++++++++++-
>   1 file changed, 13 insertions(+), 1 deletion(-)
>
> diff --git a/lib/string.c b/lib/string.c
> index 6b89c035df74..548f52b7a145 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -177,12 +177,24 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
>   		unsigned long c, data;
>   
>   		c = *(unsigned long *)(src+res);
> -		*(unsigned long *)(dest+res) = c;
> +
>   		if (has_zero(c, &data, &constants)) {
> +			unsigned int zero_pos;
> +
>   			data = prep_zero_mask(c, data, &constants);
>   			data = create_zero_mask(data);
> +
> +			zero_pos = find_zero(data);
> +
> +			/* Clear out undefined data within the final word after the NUL (if any): */
> +			memset((void *)&c + zero_pos, 0, sizeof(long)-zero_pos);

Unfortunately using memset() like that will break on big-endian
machines.  I always have to go back and play around with the
word-at-a-time.h definitions to get this right, but I think it's possible
that the "data" itself has the mask to clear the unwanted bytes,
i.e. you could do something like the following (untested).

I'm still not totally convinced it's necessary, as programmers
should generally assume anything beyond the end of a copied
string is garbage anyway, and since we're not copying it to
userspace we're not exposing any possibly secure data.

Races shouldn't be a concern either since, after all, there is
already a window where we may have overwritten the NUL
end of an earlier shorter string, and now a racy copy from the
partially-written dest buf could walk right off the end of the
buffer itself, so you'd already better not be doing that.

But, all that said, I'm not opposed to a simple fix to avoid
carrying along the uninitialized bytes from beyond the end
of the source string, since it does seem a bit cleaner, even
if I can't put my finger in a reason why it would actually matter.

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..ba64f4e0382d 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -203,12 +203,13 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
  		unsigned long c, data;
  
  		c = *(unsigned long *)(src+res);
-		*(unsigned long *)(dest+res) = c;
  		if (has_zero(c, &data, &constants)) {
  			data = prep_zero_mask(c, data, &constants);
  			data = create_zero_mask(data);
+			*(unsigned long *)(dest+res) = c & data;
  			return res + find_zero(data);
  		}
+		*(unsigned long *)(dest+res) = c;
  		res += sizeof(unsigned long);
  		count -= sizeof(unsigned long);
  		max -= sizeof(unsigned long);

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

Re: [PATCH] string: Fix strscpy() uninitialized data copy bug

[Ingo Molnar]

* Chris Metcalf <cmetcalf@ezchip.com> wrote:

> Unfortunately using memset() like that will break on big-endian machines.

doh ... and I somehow convinced myself that it was endian safe ;-)

> [...]  I always have to go back and play around with the word-at-a-time.h 
> definitions to get this right, but I think it's possible that the "data" itself 
> has the mask to clear the unwanted bytes, i.e. you could do something like the 
> following (untested).
> 
> I'm still not totally convinced it's necessary, as programmers should generally 
> assume anything beyond the end of a copied string is garbage anyway, and since 
> we're not copying it to userspace we're not exposing any possibly secure data.
> 
> Races shouldn't be a concern either since, after all, there is already a window 
> where we may have overwritten the NUL end of an earlier shorter string, and now 
> a racy copy from the partially-written dest buf could walk right off the end of 
> the buffer itself, so you'd already better not be doing that.
> 
> But, all that said, I'm not opposed to a simple fix to avoid carrying along the 
> uninitialized bytes from beyond the end of the source string, since it does seem 
> a bit cleaner, even if I can't put my finger in a reason why it would actually 
> matter.

So it would matter for more advanced sharing ABIs: for example if there's an 
mlock()-ed area registered on the kernel side as well as kernel accessible memory, 
and if we do an strscpy() to such a target area, we don't want to leak 
uninitialized data to user-space.

(This is not theoretical, the perf ring-buffer is such a construct for example.)

So IMHO this is a quality of implementation issue that we should fix.

> diff --git a/lib/string.c b/lib/string.c
> index 8dbb7b1eab50..ba64f4e0382d 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -203,12 +203,13 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
>  		unsigned long c, data;
>  		c = *(unsigned long *)(src+res);
> -		*(unsigned long *)(dest+res) = c;
>  		if (has_zero(c, &data, &constants)) {
>  			data = prep_zero_mask(c, data, &constants);
>  			data = create_zero_mask(data);
> +			*(unsigned long *)(dest+res) = c & data;
>  			return res + find_zero(data);
>  		}
> +		*(unsigned long *)(dest+res) = c;
>  		res += sizeof(unsigned long);
>  		count -= sizeof(unsigned long);
>  		max -= sizeof(unsigned long);

Looks good to me!

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Linus Torvalds]

On Mon, Oct 5, 2015 at 5:22 PM, Ingo Molnar <mingo@kernel.org> wrote:
>
> We could do something like:
>
>                 c = *(unsigned long *)(src+res);
>                 *(unsigned long *)(dest+res) = c;
>
>                 if (has_zero(c, &data, &constants)) {

No, I think we'd be better off just moving the "has_zero()" to to
before the destination write, and instead doing the destination write
for the "word has zero" case one byte at a time. Sure, you'd need to
do it differently for little- and big-endian, but big deal.

So just something like

    c = *(unsigned long *)(src+res);
    if (has_zero(c, &data, &constants))
        return strscpy_final_word(c, dst, res);
    *(unsigned long *)(dest+res) = c;
    ...

where that "strscpy_final_word()" looks something like

    static inline strscpy_final_word(unsigned long word, char *dst, long res)
    {
        for (;;res++) {
            char c;
#ifdef LITTLE_ENDIAN
            c = word; word >>= 8;
#else
            c = word >> 8*(sizeof(unsigned long)-1); word <<= 8;
#endif
            dst[res] = c;
            if (!c)
                return res;
        }
    }

which really shouldn't be too bad.

I don't think it's much better to use "memset()" than it is to have
the partially filled from the last word of the source.

For "strncpy_from_user()" we do that "partial source word write", and
it's ok there, mainly because (a) that case isn't even trying to be
some generic interface and (b) "strncpy_from_user()" is really
performance-critical. I suspect for strscpy() we're better off just
being slightly more careful. I don't think it's *nearly* as
performance-critical as something like strncpy_from_user() that is
used for every single pathname copy etc.

Alternatively, if we really do expect strscpy() to maybe be
performance-critical, we could just document the fact that it does
things word-at-a-time and that bytes after the terminating NUL
character are *not* reliable. So we *might* just choose to document
this as an implementation issue. But the "memset()" approach just
looks bad.

             Linus

[PATCH] strscpy: zero any trailing garbage bytes in the destination

[Chris Metcalf]

It's possible that the destination can be shadowed in userspace
(as, for example, the perf buffers are now).  So we should take
care not to leak data that could be inspected by userspace.

Signed-off-by: Chris Metcalf <cmetcalf@ezchip.com>
---
Ingo, can you test this change in your Fedora+strlcpy boot test?
I think it's correct but the more testing the better, particularly
if we're about to add the support for strlcpy to use it.

I did some light testing on big-endian tilegx and it appears
that zero_bytemask() is required and does the right thing.
On little-endian it's generally a no-op.  This is pretty much
the same pattern that fs/namei.c uses now too.

 lib/string.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..84775ba873b9 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -203,12 +203,13 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
 		unsigned long c, data;
 
 		c = *(unsigned long *)(src+res);
-		*(unsigned long *)(dest+res) = c;
 		if (has_zero(c, &data, &constants)) {
 			data = prep_zero_mask(c, data, &constants);
 			data = create_zero_mask(data);
+			*(unsigned long *)(dest+res) = c & zero_bytemask(data);
 			return res + find_zero(data);
 		}
+		*(unsigned long *)(dest+res) = c;
 		res += sizeof(unsigned long);
 		count -= sizeof(unsigned long);
 		max -= sizeof(unsigned long);
-- 
2.1.2

Re: [PATCH] strscpy: zero any trailing garbage bytes in the destination

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 1291 bytes --]

Hi Chris,

[auto build test ERROR on v4.3-rc4 -- if it's inappropriate base, please ignore]

config: alpha-defconfig (attached as .config)
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=alpha 

All errors (new ones prefixed by >>):

   lib/string.c: In function 'strscpy':
>> lib/string.c:209:4: error: implicit declaration of function 'zero_bytemask' [-Werror=implicit-function-declaration]
       *(unsigned long *)(dest+res) = c & zero_bytemask(data);
       ^
   cc1: some warnings being treated as errors

vim +/zero_bytemask +209 lib/string.c

   203			unsigned long c, data;
   204	
   205			c = *(unsigned long *)(src+res);
   206			if (has_zero(c, &data, &constants)) {
   207				data = prep_zero_mask(c, data, &constants);
   208				data = create_zero_mask(data);
 > 209				*(unsigned long *)(dest+res) = c & zero_bytemask(data);
   210				return res + find_zero(data);
   211			}
   212			*(unsigned long *)(dest+res) = c;

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 11535 bytes --]

Re: [PATCH] strscpy: zero any trailing garbage bytes in the destination

[Chris Metcalf]

On 10/06/2015 12:47 PM, Chris Metcalf wrote:
> It's possible that the destination can be shadowed in userspace
> (as, for example, the perf buffers are now).  So we should take
> care not to leak data that could be inspected by userspace.

Oops, we need to ensure platforms all have zero_bytemask()
before we can do this.  It's pretty trivial in general, but not all
platforms have it now.  I'll post a patch to fix this as needed,
which should be taken before this patch to avoid git bisect
failures.

I'll also see about fixing some skew in platforms that are
either newer than the patch (h8300) or added word-at-a-time.h
since the original patch (powerpc, tile).

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

Re: [PATCH] strscpy: zero any trailing garbage bytes in the destination

[Ingo Molnar]

* Chris Metcalf <cmetcalf@ezchip.com> wrote:

> It's possible that the destination can be shadowed in userspace
> (as, for example, the perf buffers are now).  So we should take
> care not to leak data that could be inspected by userspace.
> 
> Signed-off-by: Chris Metcalf <cmetcalf@ezchip.com>
> ---
> Ingo, can you test this change in your Fedora+strlcpy boot test?
> I think it's correct but the more testing the better, particularly
> if we're about to add the support for strlcpy to use it.

Yeah, booted it on a couple of systems and everything seems to be fine:

Tested-by: Ingo Molnar <mingo@kernel.org>

Thanks,

	Ingo

[GIT PULL] strscpy string copy function

[Chris Metcalf]

Linus,

Please pull the following changes for 4.3 from:

   git://git.kernel.org/pub/scm/linux/kernel/git/cmetcalf/linux-tile.git strscpy

Your comment for 4.2 was to get rid of the "make it zero-sized" default thing,
which I did in the v2 patch in July.  I did get a bit of feedback around the
language of the kerneldoc comment, which I updated, and the result is ready
to be pulled, if it seems like the right thing to you now!

Chris Metcalf (3):
       Make asm/word-at-a-time.h available on all architectures
       string: provide strscpy()
       tile: use global strscpy() rather than private copy

  arch/arc/include/asm/Kbuild          |  1 +
  arch/avr32/include/asm/Kbuild        |  1 +
  arch/blackfin/include/asm/Kbuild     |  1 +
  arch/c6x/include/asm/Kbuild          |  1 +
  arch/cris/include/asm/Kbuild         |  1 +
  arch/frv/include/asm/Kbuild          |  1 +
  arch/hexagon/include/asm/Kbuild      |  1 +
  arch/ia64/include/asm/Kbuild         |  1 +
  arch/m32r/include/asm/Kbuild         |  1 +
  arch/metag/include/asm/Kbuild        |  1 +
  arch/microblaze/include/asm/Kbuild   |  1 +
  arch/mips/include/asm/Kbuild         |  1 +
  arch/mn10300/include/asm/Kbuild      |  1 +
  arch/nios2/include/asm/Kbuild        |  1 +
  arch/powerpc/include/asm/Kbuild      |  1 +
  arch/s390/include/asm/Kbuild         |  1 +
  arch/score/include/asm/Kbuild        |  1 +
  arch/tile/gxio/mpipe.c               | 33 ++------------
  arch/tile/include/asm/Kbuild         |  1 +
  arch/um/include/asm/Kbuild           |  1 +
  arch/unicore32/include/asm/Kbuild    |  1 +
  arch/xtensa/include/asm/Kbuild       |  1 +
  include/asm-generic/word-at-a-time.h | 80 ++++++++++++++++++++++++++++----
  include/linux/string.h               |  3 ++
  lib/string.c                         | 88 ++++++++++++++++++++++++++++++++++++
  25 files changed, 188 insertions(+), 37 deletions(-)

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com

Re: [GIT PULL] strscpy string copy function

[Linus Torvalds]

On Thu, Sep 10, 2015 at 8:43 PM, Chris Metcalf <cmetcalf@ezchip.com> wrote:
>
> Please pull the following changes for 4.3 from:
>
>   git://git.kernel.org/pub/scm/linux/kernel/git/cmetcalf/linux-tile.git strscpy

So I finally pulled it. I like the patch, I like the new interface,
but despite that I wasn't really sure if I wanted to pull it in - thus
the long delay of me just seeing this in my list of pending pulls for
almost a month, but never really getting to the point where I decided
I want to commit to it.

I wrote a longish merge message about why - but it boils down to me
hating the mindless trivial conversion patches. Which were not in the
pull request, but I want to make it clear to everybody that I have
absolutely zero interest in seeing such patches. I want to encourage
judicious use of strscpy() in new code, or in code that gets modified
because it is buggy or is updated for other reasons (and thus thought
about and tested), but I am *not* going to accept patches that do mass
conversions of strlcpy or strncpy to the new interface.

So just pulling the support seemed safe since ghere are no actual
*users* of this yet. So it's purely preparatory for future patches, so
it still made sense just before I'm doing an -rc4. Of course, I hope I
won't regret that "seems safe", since I'm sure the newly exposed
word-at-a-time things may well break architectures that I am not
test-compiling (ie all of them except x86-64), but it looked fine and
any breakage should be trivial.

Side note: I'm not entirely convinced about the "__must_check". There
are real cases where you don't really care whether you get a full
string or not, and strncpy() or strlcpy() may be unacceptable due to
their respective problems. But let's see once we start getting real
users who really thought about what they want.

                Linus

[PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Thu, Sep 10, 2015 at 8:43 PM, Chris Metcalf <cmetcalf@ezchip.com> wrote:
> >
> > Please pull the following changes for 4.3 from:
> >
> >   git://git.kernel.org/pub/scm/linux/kernel/git/cmetcalf/linux-tile.git strscpy
> 
> So I finally pulled it. I like the patch, I like the new interface,
> but despite that I wasn't really sure if I wanted to pull it in - thus
> the long delay of me just seeing this in my list of pending pulls for
> almost a month, but never really getting to the point where I decided
> I want to commit to it.

Interesting. I noticed that strscpy() says this in its comments:

 * In addition, the implementation is robust to the string changing out
 * from underneath it, unlike the current strlcpy() implementation.

The strscpy() interface is very nice, but shouldn't we also fix this strlcpy() 
unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call 
sites?

The comment does not spell out what the exact race is, but I can see only a single 
race in the current generic strlcpy() implementation, which all architectures 
except s390 uses:

size_t strlcpy(char *dest, const char *src, size_t size)
{
        size_t ret = strlen(src);

        if (size) {
                size_t len = (ret >= size) ? size - 1 : ret;
                memcpy(dest, src, len);
                dest[len] = '\0';
        }
        return ret;
}

If another CPU or an interrupt changes the source string after the strlen(), but 
before the copy is complete, and shortens the source string, then we copy over the 
NUL byte of the source buffer - including fragments of earlier source string 
tails. The target buffer will still be properly NUL terminated - but it will be a 
shorter string than the returned 'ret' source buffer length. (despite there not 
being truncation.)

The s390 arch implementation has the same race AFAICS.

This may cause bugs if the return code is subsequently used to assume that it is 
equal to the destination string's length. (While in reality it's shorter.)

The race is not automatically lethal, because it's guaranteed that the returned 
length is indeed zero-delimited (due to the overlong copy we did) - so if the 
string is memcpy()-ed, then it will still result in a weirdly padded but valid 
string.

But if any subsequent use of the return code relies on the return code being equal 
to a subsequent call of strlen(dest), then that use might lead to bugs. I.e. our 
implementation of strlcpy() is indeed racy and unrobust.

But we could fix this race: by iterating over the string in a single go and 
determining the length and copying the string at once. Like the new strscpy() code 
does it, but with strlcpy() semantics.

This will also make strlcpy() faster, FWIMBW.

I also noticed another problem with our current generic strlcpy() implementation: 
AFAICS it will also happily do bad stuff if we pass it a negative size. Instead of 
that we should print a warning and return safely.

I've implemented all that, see the patch below.

(Only very lightly tested so far and no benchmarking done.)

Thanks,

	Ingo

===================================>
>From 53fc46c16ed65e67906d5b453e19d8f688093f70 Mon Sep 17 00:00:00 2001
From: Ingo Molnar <mingo@kernel.org>
Date: Mon, 5 Oct 2015 10:56:50 +0200
Subject: [PATCH] string: Improve the generic strlcpy() implementation

The current strlcpy() implementation has two implementational
weaknesses:

1)

There's a race:

size_t strlcpy(char *dest, const char *src, size_t size)
{
        size_t ret = strlen(src);

        if (size) {
                size_t len = (ret >= size) ? size - 1 : ret;
                memcpy(dest, src, len);
                dest[len] = '\0';
        }
        return ret;
}

If another CPU or an interrupt changes the source string after the strlen(), but
before the copy is complete, and shortens the source string, then we copy over the
NUL byte of the source buffer - including fragments of earlier source string
tails. The target buffer will still be properly NUL terminated - but it will be a
shorter string than the returned 'ret' source buffer length. (despite there not
being truncation.)

The s390 arch implementation has the same race AFAICS.

This may cause bugs if the return code is subsequently used to assume that it is
equal to the destination string's length. (While in reality it's shorter.)

The race is not automatically lethal, because it's guaranteed that the returned
length is indeed zero-delimited (due to the overlong copy we did) - so if the
string is memcpy()-ed, then it will still result in a weirdly padded but valid
string.

But if any subsequent use of the return code relies on the return code being equal
to a subsequent call of strlen(dest), then that use might lead to bugs. I.e. our
implementation of strlcpy() is indeed racy and unrobust.

But we can fix this race: by iterating over the string in a single go and
determining the length and copying the string at once. Like strscpy(), but with
strlcpy() semantics.

The new implementation uses word-by-word iteration over the strings if possible,
so this will also make strlcpy() faster as well.

2)

Another problem is that strlcpy() will also happily do bad stuff if we pass
it a negative size. Instead of that we will from now on print a (one time)
warning and return safely.

Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 lib/string.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 78 insertions(+), 8 deletions(-)

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..e0cfca299606 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -129,23 +129,93 @@ EXPORT_SYMBOL(strncpy);
  * strlcpy - Copy a C-string into a sized buffer
  * @dest: Where to copy the string to
  * @src: Where to copy the string from
- * @size: size of destination buffer
+ * @dest_size: size of destination buffer
  *
  * Compatible with *BSD: the result is always a valid
  * NUL-terminated string that fits in the buffer (unless,
  * of course, the buffer size is zero). It does not pad
  * out the result like strncpy() does.
  */
-size_t strlcpy(char *dest, const char *src, size_t size)
+size_t strlcpy(char *dest, const char *src, size_t dest_size)
 {
-	size_t ret = strlen(src);
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	size_t dest_left = dest_size;
+	size_t dest_aligned_left = dest_left;
+	long src_len = 0;
+
+	/* Overflow check: */
+	if (unlikely(dest_size < 0)) {
+		WARN_ONCE(1, "strlcpy(): dest_size < 0 underflow!");
+		return strlen(src);
+	}
+
+#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+	/*
+	 * If src is unaligned, don't cross a page boundary,
+	 * since we don't know if the next page is mapped.
+	 */
+	if ((long)src & (sizeof(long) - 1)) {
+		size_t limit = PAGE_SIZE - ((long)src & (PAGE_SIZE - 1));
+		if (limit < dest_aligned_left)
+			dest_aligned_left = limit;
+	}
+#else
+	/* If src or dest is unaligned, don't do word-at-a-time. */
+	if (((long) dest | (long) src) & (sizeof(long) - 1))
+		dest_aligned_left = 0;
+#endif
+
+	/* First do the word-at-a-time copy of the aligned portion (if any): */
+	while (dest_aligned_left >= sizeof(unsigned long)) {
+		unsigned long c, data;
 
-	if (size) {
-		size_t len = (ret >= size) ? size - 1 : ret;
-		memcpy(dest, src, len);
-		dest[len] = '\0';
+		c = *(unsigned long *)(src+src_len);
+		*(unsigned long *)(dest+src_len) = c;
+
+		if (has_zero(c, &data, &constants)) {
+			data = prep_zero_mask(c, data, &constants);
+			data = create_zero_mask(data);
+			/* The target string was terminated by the above word copy */
+			return src_len + find_zero(data);
+		}
+		src_len += sizeof(unsigned long);
+		dest_left -= sizeof(unsigned long);
+		dest_aligned_left -= sizeof(unsigned long);
 	}
-	return ret;
+
+	/*
+	 * We get here either for tails smaller than word size, or
+	 * unaligned strings. Copy byte by byte and return the
+	 * length of the source string if we find its end:
+	 */
+	while (dest_left) {
+		char c;
+
+		c = src[src_len];
+		dest[src_len] = c;
+		if (!c)
+			/* The target string was terminated by the above byte copy */
+			return src_len;
+		src_len++;
+		dest_left--;
+	}
+
+	/*
+	 * We get here if the source string is larger than the destination buffer.
+	 *
+	 * The strlcpy() semantics require us to return the length of the
+	 * source string - so we have to continue until we find its end.
+	 *
+	 * We first zero-terminate the (truncated, hence non yet terminated)
+	 * target string.
+	 */
+	if (dest_size)
+		dest[dest_size-1] = '\0';
+
+	while (src[src_len])
+		src_len++;
+
+	return src_len;
 }
 EXPORT_SYMBOL(strlcpy);
 #endif

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> 2)
> 
> Another problem is that strlcpy() will also happily do bad stuff if we pass
> it a negative size. Instead of that we will from now on print a (one time)
> warning and return safely.

Hm, so this check is buggy, as 'size_t' is unsigned - and for some reason GCC 
didn't warn about the never-met comparison and the resulting unreachable dead
code here:

> +	/* Overflow check: */
> +	if (unlikely(dest_size < 0)) {
> +		WARN_ONCE(1, "strlcpy(): dest_size < 0 underflow!");
> +		return strlen(src);
> +	}

which is annoying.

Would people object to something like:

> +	/* Overflow check: */
> +	if (unlikely((ssize_t)dest_size < 0)) {
> +		WARN_ONCE(1, "strlcpy(): dest_size < 0 underflow!");
> +		return strlen(src);
> +	}

?

As I doubt it's legit to have larger than 2GB strings.

Also, I'm wondering why GCC didn't warn.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> 
> * Ingo Molnar <mingo@kernel.org> wrote:
> 
> > 2)
> > 
> > Another problem is that strlcpy() will also happily do bad stuff if we pass
> > it a negative size. Instead of that we will from now on print a (one time)
> > warning and return safely.
> 
> Hm, so this check is buggy, as 'size_t' is unsigned - and for some reason GCC 
> didn't warn about the never-met comparison and the resulting unreachable dead
> code here:
> 
> > +	/* Overflow check: */
> > +	if (unlikely(dest_size < 0)) {
> > +		WARN_ONCE(1, "strlcpy(): dest_size < 0 underflow!");
> > +		return strlen(src);
> > +	}
> 
> which is annoying.
> 
> Would people object to something like:
> 
> > +	/* Overflow check: */
> > +	if (unlikely((ssize_t)dest_size < 0)) {
> > +		WARN_ONCE(1, "strlcpy(): dest_size < 0 underflow!");
> > +		return strlen(src);
> > +	}
> 
> ?
> 
> As I doubt it's legit to have larger than 2GB strings.
> 
> Also, I'm wondering why GCC didn't warn.

Hm, so GCC (v4.9.2) will only warn about this bug if -Wtype-limits is enabled 
explicitly:

 lib/string.c: In function ‘strlcpy’:
 lib/string.c:228:32: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]
   if (unlikely((size_t)dst_size < 0)) {
                                 ^

... which we don't do in the kernel.

Has anyone considered enabling -Wtype-limits? It seems to catch real bugs.

I can see there are patches that enable -Wextra (which enables -Wtype-limits and 
many other warnings), but it would be more manageable to just enable one such 
warning at a time.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Ingo Molnar <mingo@kernel.org> wrote:

> Hm, so GCC (v4.9.2) will only warn about this bug if -Wtype-limits is enabled 
> explicitly:
> 
>  lib/string.c: In function ‘strlcpy’:
>  lib/string.c:228:32: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]
>    if (unlikely((size_t)dst_size < 0)) {
>                                  ^
> 
> ... which we don't do in the kernel.
> 
> Has anyone considered enabling -Wtype-limits? It seems to catch real bugs.
> 
> I can see there are patches that enable -Wextra (which enables -Wtype-limits and 
> many other warnings), but it would be more manageable to just enable one such 
> warning at a time.

So I checked this and -Wtype-limits is super chatty at the moment, on various 
configs on x86:

 def64:    warnings:  51, delta: +51
 def32:    warnings:  50, delta: +50
 allno64:  warnings:  24, delta: +21
 allno32:  warnings:  26, delta: +24
 allyes64: warnings: 292, delta: +278
 allyes32: warnings: 318, delta: +277
 allmod64: warnings: 298, delta: +287
 allmod32: warnings: 324, delta: +286

(The delta column is the number of new warnings relative to v4.3-rc4.)

I picked 10 random warnings that triggered in files that looked interesting to me:

1) false positive warning:

./arch/x86/include/asm/apic.h:33:11: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

is caused by macro substitution:

#define apic_printk(v, s, a...) do {       \
                if ((v) <= apic_verbosity) \
                        printk(s, ##a);    \
        } while (0)

so if 'v' is 0 GCC thinks it's a bad comparison - while it isn't.

This would be easily worked around if we moved the code from CPP to C - which is 
beneficial in any case.

2) confused code (possibly harmful):

arch/x86/kernel/pci-calgary_64.c:299:25: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

this:

  static void iommu_free(struct iommu_table *tbl, dma_addr_t dma_addr, unsigned int npages)
  {

	...
        if (unlikely((dma_addr >= DMA_ERROR_CODE) && (dma_addr < badend))) {
                WARN(1, KERN_ERR "Calgary: driver tried unmapping bad DMA "
                       "address 0x%Lx\n", dma_addr);
                return;
        }

is nonsense because dma_addr is unsigned and DMA_ERROR_CODE is 0. The right way to 
check for DMA_ERROR_CODE is to check it:

  triton:~/tip> git grep DMA_ERROR_CODE | grep -E '==|!=' | wc -l
  29

not compare it:

  triton:~/tip> git grep DMA_ERROR_CODE | grep -E ' <= | >= | < | > ' | wc -l
  1

3) false positive warning:

block/cfq-iosched.c:4657:13: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

substition of '0' in the STORE_FUNCTION() macro causes this one.

4) confused code (looks harmless):

crypto/asymmetric_keys/x509_cert_parser.c:549:11: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

        unsigned year, mon, day, hour, min, sec, mon_len;
	...

            hour < 0 || hour > 23 ||

so 'hour' cannot be negative. Looks harmless.

5) false positive warning:

drivers/nvdimm/pmem.c:257:38: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

        if (nvdimm_namespace_capacity(ndns) < ND_PFN_ALIGN

so ND_PFN_ALIGN can be 0 if CONFIG_NVDIMM_PFN is disabled.

6) confused code (looks harmless):

kernel/auditsc.c:1027:23: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

        size_t len, len_left, to_send;

	...

        if (WARN_ON_ONCE(len < 0 || len > MAX_ARG_STRLEN - 1)) {

So this looks like a real bug similar to the one I made in the strlcpy() warning: 
the code wants to warn about a negative underflow - but instead it does not check 
for that condition at all.

It's harmless because the len > MAX_ARG_STRLEN-1 check would catch any underflows.

7) confused code (looks harmless):

mm/memblock.c:840:11: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]


	void __init_memblock __next_reserved_mem_region(u64 *idx,
	...

        if (*idx >= 0 && *idx < type->cnt) {

so *idx is u64 so it's always >= 0. Looks harmless.

8) confused code (looks harmless):

fs/cachefiles/bind.c:42:30: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

        /* start by checking things over */
        ASSERT(cache->fstop_percent >= 0 &&
               cache->fstop_percent < cache->fcull_percent &&
               cache->fcull_percent < cache->frun_percent &&
               cache->frun_percent  < 100);


'fstop_percent' is unsigned int, so the >= 0 test is superfluous. Looks harmless.

9) confused code (looks harmless):

fs/cachefiles/daemon.c:225:14: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

                                       size_t datalen,
	...

        if (datalen < 0 || datalen > PAGE_SIZE - 1)
                return -EOPNOTSUPP;


so 'datalen' is unsigned and this can never be negative - and the second check 
catches any underflows. Looks harmless.

10) somewhat confused code (harmless):

net/rds/iw_recv.c:203:26: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

So this comes from the comparison of RDS_PAGE_LAST_OFF:

        get_page(recv->r_frag->f_page);

        if (ic->i_frag.f_offset < RDS_PAGE_LAST_OFF) {
                ic->i_frag.f_offset += RDS_FRAG_SIZE;
        } else {
                put_page(ic->i_frag.f_page);
                ic->i_frag.f_page = NULL;
                ic->i_frag.f_offset = 0;
        }

but i_frag.f_offset is unsigned:

 net/rds/iw.h:   unsigned long           f_offset;

and:

 net/rds/iw.h:#define RDS_PAGE_LAST_OFF (((PAGE_SIZE  / RDS_FRAG_SIZE) - 1) * RDS_FRAG_SIZE)

where RDS_FRAG_SIZE == 4096, so RDS_PAGE_LAST_OFF becomes 0.

if RDS_FRAG_SIZE was smaller than 4096, say 512, then RDS_PAGE_LAST_OFF would show 
the offset within the page of the last fragment, i.e. 3584.

So the code looks correct but inefficient: it does the get_page()/put_page() 
unnecessarily in the RDS_FRAG_SIZE == PAGE_SIZE case, which is the default on most 
architectures.

I'd write this as:

        if (ic->i_frag.f_offset < RDS_PAGE_LAST_OFF) {
	        get_page(recv->r_frag->f_page);
                ic->i_frag.f_offset += RDS_FRAG_SIZE;
        } else {
                ic->i_frag.f_page = NULL;
                ic->i_frag.f_offset = 0;
        }

(but this would still generate the warning.)

============

So the summary from 10 examples is:

 1) false positive warning
 2) confused code (possibly harmful)
 3) false positive warning
 4) confused code (looks harmless)
 5) false positive warning
 6) confused code (looks harmless)
 7) confused code (looks harmless)
 8) confused code (looks harmless)
 9) confused code (looks harmless)
10) somewhat confused code (harmless)

I.e. 3 genuine false positive warnings, 6 pointing out harmless looking code 
confusion, 1 pointing out harmful looking code confusion - and one of the sites it 
pointed out highlighted an inefficiency.

That doesn't look too bad of a false positive ration from a compiler warning, 
especially considering that static checkers (and people running -Wextra builds) 
have been cleaning out these cases for quite some time it appears, which means 
these are the leftover warnings.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Oct 5, 2015 14:15, "Ingo Molnar" <mingo@kernel.org> wrote:
> >
> > Hm, so GCC (v4.9.2) will only warn about this bug if -Wtype-limits is enabled 
> > explicitly:
> 
> Some of the warnings are really nasty, and cause people to write worse code.
> 
> For example, this is inherently good code:
> 
>     if (x < 0 || x > MAXLEN)
>         return -EINVAL;
> 
> and a compiler that warns about that is pure and utter crap. Obviously. Agreed?
> 
> Now, imagine that "x" here is some random type. Maybe it's s "char" and you 
> don't even know the sign. Maybe it's "loff_t". Maybe it's "size_t", or whatever.
> 
> Note how that test is correct *regardless* of the sign of the type. A compiler 
> that warns about the "x < 0" part just because x happens to be unsigned is a bad 
> bad compiler, and makes people remove that check, even though it's good for 
> readability, and good for robustness wrt changing the type.

Yeah, that's true.

> We really do have types where sightedness depends on architecture or
> possibly configuration options. "char" is the obvious example, but the type
> limit can matter too: on some architectures you might have a type that is
> 16 bits, on another it might be 32 bits. Do you really think that
> 
>      if (x > 65535)
>           return -E2BIG;
> 
> should have some #ifdef __xyz__ around it just because the compiler warns
> if the type happens to be 16 bits wide?
> 
> So type limit warnings break not things than they fix.

Yeah, too bad.

> These things come up in macros too (think range checking etc).
> 
> In other words, that warning really isn't good if it's done mindlessly. And I've 
> never seen a compiler that did it sanely and trying to take context into 
> account.
> 
> So no. Don't enable that broken warning. We have had it on, and it caused people 
> to send in patches for warnings that made the code actively worse.

Okay. Please disregard my other mail.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Oct 5, 2015 14:15, "Ingo Molnar" <mingo@kernel.org> wrote:
> >
> > Hm, so GCC (v4.9.2) will only warn about this bug if -Wtype-limits is
> enabled
> > explicitly:
> 
> Some of the warnings are really nasty, and cause people to write worse code.
> 
> For example, this is inherently good code:
> 
>     if (x < 0 || x > MAXLEN)
>         return -EINVAL;
> 
> and a compiler that warns about that is pure and utter crap. Obviously.
> Agreed?
> 
> Now, imagine that "x" here is some random type. Maybe it's s "char" and you
> don't even know the sign. Maybe it's "loff_t". Maybe it's "size_t", or
> whatever.
> 
> Note how that test is correct *regardless* of the sign of the type. A
> compiler that warns about the "x < 0" part just because x happens to be
> unsigned is a bad bad compiler, and makes people remove that check, even
> though it's good for readability, and good for robustness wrt changing the
> type.

Hm, so there's a flip side here - if we consider 'example 6)' in my previous mail:

  kernel/auditsc.c:1027:23: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

        size_t len, len_left, to_send;

        ...

        if (WARN_ON_ONCE(len < 0 || len > MAX_ARG_STRLEN - 1)) {

Now if this code was written as:

        if (WARN_ON_ONCE(len < 0)) {

then it would be a clear bug, right?

So we could solve that by adding a generic range check:

 static inline int range_ok(unsigned long low, unsigned long val, unsigned long high)
 {               
        if (val < low)
                return 0;
        if (val >= high)
                return 0;

        return 1;
 }

and we could write this:

        if (len < 0 || len > MAX_ARG_STRLEN - 1) {

as:

        if (!range_ok(0, len, MAX_ARG_STRLEN)) {

?

That kind of construct:

 - is robust against a changed type for 'len'

 - is robust against these common typos for open coded security checks:

        if (len <= 0 || len > MAX_ARG_STRLEN - 1) {

        if (len < 0 || len >= MAX_ARG_STRLEN - 1) {

        if (len < 0 || len > MAX_ARG_STRLEN) {

   the first and second ones over-check and are harmless in this context, the 
   third one is harmful because it does not catch the MAX_ARG_STRLEN case.

 - it would also clearly document range checking performed in a function that gets
   untrusted data.

Hypothetically, if this was acceptable then we could use this in the cases where 
GCC generates a bogus warning.

But ... no strong feelings. Just found it weird that GCC let my bug slip through.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Linus Torvalds]

On Mon, Oct 5, 2015 at 3:33 PM, Ingo Molnar <mingo@kernel.org> wrote:
>
> So we could solve that by adding a generic range check:
>
>  static inline int range_ok(unsigned long low, unsigned long val, unsigned long high)

So what about the type of the thing you're checking?

Maybe negative values are ok. It's unusual, but it's not unheard of.
We do have cases like

    if ((uch_config < -1) || (uch_config > 31)) {

so we have range checks that actually have signed ranges.

So I don't think a "generic" range check helper can force types like
"unsigned long".

That said, doing a simple

    git grep '<.*||.*>'

does show that the "positive or non-zero ranges with constant range
limits" case is fairly common, and maybe we could have a macro that
does some magic compile-time checking that (a) the range really is a
compile-time constant and (b) that range is valid and (c) avoids the
comparison with zero if the expression to be tested is unsigned.

So it is possible that we could enable type limit checking if we also
introduce a good way to not then create crap patches that actually
make the code more fragile or less readable. I'm not violently against
that. But I *am* violently against introducing that braindead warning
without very clear rules that we don't then have the mindless and
wrong changes to remove proper and obvious range checking and replace
it with "the expression is unsigned so we remove the nice readable
lower bounds check as unnecessary".

            Linus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> So I don't think a "generic" range check helper can force types like
> "unsigned long".

Yeah.

> That said, doing a simple
> 
>     git grep '<.*||.*>'
> 
> does show that the "positive or non-zero ranges with constant range
> limits" case is fairly common, and maybe we could have a macro that
> does some magic compile-time checking that (a) the range really is a
> compile-time constant and (b) that range is valid and (c) avoids the
> comparison with zero if the expression to be tested is unsigned.
> 
> So it is possible that we could enable type limit checking if we also
> introduce a good way to not then create crap patches that actually
> make the code more fragile or less readable. I'm not violently against
> that. But I *am* violently against introducing that braindead warning
> without very clear rules that we don't then have the mindless and
> wrong changes to remove proper and obvious range checking and replace
> it with "the expression is unsigned so we remove the nice readable
> lower bounds check as unnecessary".

Ok, and fully agreed.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Linus Torvalds]

On Mon, Oct 5, 2015 at 12:27 PM, Ingo Molnar <mingo@kernel.org> wrote:
>
> Interesting. I noticed that strscpy() says this in its comments:
>
>  * In addition, the implementation is robust to the string changing out
>  * from underneath it, unlike the current strlcpy() implementation.
>
> The strscpy() interface is very nice, but shouldn't we also fix this strlcpy()
> unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call
> sites?

Well, I'm not sure the race really matters. I personally think
strlcpy() is a horrible interface, and the thing is, the return value
of strlcpy (which is what can race) is kind of useless because it's
not actually the size of the resulting string *anyway* (because of the
overflow issue).

So I'm not sure it's worth even fixing.

Also, if you do this, then you're better off using the (hopefully
optimized) "strlen()" for the tail part of the strlcpy destination for
the overflow case that didn't get copied.

In other words, I think your patch is overly fragile and complex.
Instead, you might choose to implement strlcpy() in terms of
"strscpy()" and "strlen()".

Something like

  int strlcpy(dst, src, len)
  {
     // do the actual copy
     int n = strscpy(dst, src, len);

     // handle the insane and broken strlcpy overflow return value
     if (n < 0)
         return len + strlen(src+len);

     return n;
   }

but I didn't actually verify that the above is correct for all the corner case.

The point being, that you really shouldn't waste your time
implementing the broken BSD strlcpy crap as an actual first-class
implementation. You're better off just using a strscpy() as the
primary engine, and then implementing the broken strlcpy interfaces on
top of it.

Does the above work? I'd take a patch that implements that if it's
tested and somebody has thought about it a lot. But I don't like your
patch that open-codes the insane interface with complex and fragile
code.

          Linus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Mon, Oct 5, 2015 at 12:27 PM, Ingo Molnar <mingo@kernel.org> wrote:
> >
> > Interesting. I noticed that strscpy() says this in its comments:
> >
> >  * In addition, the implementation is robust to the string changing out
> >  * from underneath it, unlike the current strlcpy() implementation.
> >
> > The strscpy() interface is very nice, but shouldn't we also fix this strlcpy()
> > unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call
> > sites?
> 
> Well, I'm not sure the race really matters. [...]

Yeah, so if we do the word-by-word optimization for strlcpy() then the race is 
fixed 'automatically', for free.

But you are right:

> [...] I personally think strlcpy() is a horrible interface, and the thing is, 
> the return value of strlcpy (which is what can race) is kind of useless because 
> it's not actually the size of the resulting string *anyway* (because of the 
> overflow issue).
> 
> So I'm not sure it's worth even fixing.

> Also, if you do this, then you're better off using the (hopefully optimized) 
> "strlen()" for the tail part of the strlcpy destination for the overflow case 
> that didn't get copied.

Indeed, this on top of my patch should do that:

 lib/string.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/lib/string.c b/lib/string.c
index e0cfca299606..dfd24b557e84 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -212,10 +212,7 @@ size_t strlcpy(char *dest, const char *src, size_t dest_size)
 	if (dest_size)
 		dest[dest_size-1] = '\0';
 
-	while (src[src_len])
-		src_len++;
-
-	return src_len;
+	return strlen(src) + src_len;
 }
 EXPORT_SYMBOL(strlcpy);
 #endif

(untested)

> In other words, I think your patch is overly fragile and complex.

Well, it's mostly a copy of strscpy() with obvious conversion of the return 
convention, but you are right to point out:

> Instead, you might choose to implement strlcpy() in terms of
> "strscpy()" and "strlen()".
> 
> Something like
> 
>   int strlcpy(dst, src, len)
>   {
>      // do the actual copy
>      int n = strscpy(dst, src, len);
> 
>      // handle the insane and broken strlcpy overflow return value
>      if (n < 0)
>          return len + strlen(src+len);
> 
>      return n;
>    }
> 
> but I didn't actually verify that the above is correct for all the corner case.

Hm, so I considered doing that initially, but managed to convince myself that it's 
not equivalent: but on a second thought your variant should indeed work!

> The point being, that you really shouldn't waste your time implementing the 
> broken BSD strlcpy crap as an actual first-class implementation. You're better 
> off just using a strscpy() as the primary engine, and then implementing the 
> broken strlcpy interfaces on top of it.
> 
> Does the above work? I'd take a patch that implements that if it's tested and 
> somebody has thought about it a lot. But I don't like your patch that open-codes 
> the insane interface with complex and fragile code.

So the below untested variant does that plus an overflow check - it's only FYI, 
not signed off yet.

Thanks,

	Ingo

==============>

Not-Signed-off-by: Ingo Molnar <mingo@kernel.org>

 lib/string.c | 60 ++++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 34 insertions(+), 26 deletions(-)

diff --git a/lib/string.c b/lib/string.c
index 8dbb7b1eab50..6b89c035df74 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -124,32 +124,6 @@ char *strncpy(char *dest, const char *src, size_t count)
 EXPORT_SYMBOL(strncpy);
 #endif
 
-#ifndef __HAVE_ARCH_STRLCPY
-/**
- * strlcpy - Copy a C-string into a sized buffer
- * @dest: Where to copy the string to
- * @src: Where to copy the string from
- * @size: size of destination buffer
- *
- * Compatible with *BSD: the result is always a valid
- * NUL-terminated string that fits in the buffer (unless,
- * of course, the buffer size is zero). It does not pad
- * out the result like strncpy() does.
- */
-size_t strlcpy(char *dest, const char *src, size_t size)
-{
-	size_t ret = strlen(src);
-
-	if (size) {
-		size_t len = (ret >= size) ? size - 1 : ret;
-		memcpy(dest, src, len);
-		dest[len] = '\0';
-	}
-	return ret;
-}
-EXPORT_SYMBOL(strlcpy);
-#endif
-
 #ifndef __HAVE_ARCH_STRSCPY
 /**
  * strscpy - Copy a C-string into a sized buffer
@@ -234,6 +208,40 @@ ssize_t strscpy(char *dest, const char *src, size_t count)
 EXPORT_SYMBOL(strscpy);
 #endif
 
+#ifndef __HAVE_ARCH_STRLCPY
+/**
+ * strlcpy - Copy a C-string into a sized buffer
+ * @dst: Where to copy the string to
+ * @src: Where to copy the string from
+ * @dst_size: size of destination buffer
+ *
+ * Compatible with *BSD: the result is always a valid
+ * NUL-terminated string that fits in the buffer (unless,
+ * of course, the buffer size is zero). It does not pad
+ * out the result like strncpy() does.
+ */
+size_t strlcpy(char *dst, const char *src, size_t dst_size)
+{
+	int ret;
+
+	/* Overflow check: */
+	if (unlikely((ssize_t)dst_size < 0)) {
+		WARN_ONCE(1, "strlcpy(): dst_size < 0 underflow!");
+		return strlen(src);
+	}
+
+	ret = strscpy(dst, src, dst_size);
+
+	/* Handle the insane and broken strlcpy() overflow return value: */
+	if (ret < 0)
+		return dst_size + strlen(src+dst_size);
+
+	return ret;
+}
+EXPORT_SYMBOL(strlcpy);
+#endif
+
+
 #ifndef __HAVE_ARCH_STRCAT
 /**
  * strcat - Append one %NUL-terminated string to another

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Rasmus Villemoes]

On Mon, Oct 05 2015, Ingo Molnar <mingo@kernel.org> wrote:

> * Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>> So I finally pulled it. I like the patch, I like the new interface,
>> but despite that I wasn't really sure if I wanted to pull it in - thus
>> the long delay of me just seeing this in my list of pending pulls for
>> almost a month, but never really getting to the point where I decided
>> I want to commit to it.
>
> Interesting. I noticed that strscpy() says this in its comments:
>
>  * In addition, the implementation is robust to the string changing out
>  * from underneath it, unlike the current strlcpy() implementation.
>
> The strscpy() interface is very nice, but shouldn't we also fix this strlcpy() 
> unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call 
> sites?

How about every single occurence of %s in a format string? vsnprintf
also has that "issue", but has it actually ever been a problem? The
window for something bad to happen is probably also much larger in the
printf case, and especially when when some %p extension is used and/or
the vsnprintf user is kasprintf() (where we 'replay' the formatting,
having hopefully obtained a correct-sized buffer).

In fact, writing this, it occurs to me that we should probably check the
return value of the second vsnprintf call in kasprintf and compare to
the first, issuing a warning if they don't match.

I'm not against making strlcpy more robust, but I think the theoretical
race is far more likely to manifest through a member of the printf
family.

Note that, unless one cares for performance or worries about 2G+
length strings, strlcpy could just be 'return snprintf(dst, len, "%s",
src);', which would give the "check for insanely large/negative len" for
free [though not giving strlen(src) as return value - but the caller is much
more likely to be tripped up by no copying having taken place anyway]. 

> Another problem is that strlcpy() will also happily do bad stuff if we pass
> it a negative size. Instead of that we will from now on print a (one time)
> warning and return safely.

Well, not too sure about that 'safely'. If the caller somehow managed to
compute an insanely large (remaining) capacity in the buffer and has
that in a size_t variable, then proceeds to comparing the return
value to the supposed buffer size to check for overflow, he will think
that everything is fine and proceed to using likely uninitialized
contents of his buffer.

I think a return value of 0 might be slightly better. Assuming the
caller has the capacity in a signed variable (so it only became huge by
being converted to size_t) and makes a signed comparison with the return
value, both 0 and strlen() triggers an overflow check, so we wouldn't be
worse off in that case. Clearly the same is true if the return value is
not used at all. If the return value is used mindlessly for advancing
dst and decrementing the capacity, staying put is probably better.

Rasmus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> On Mon, Oct 05 2015, Ingo Molnar <mingo@kernel.org> wrote:
> 
> > * Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >
> >> So I finally pulled it. I like the patch, I like the new interface,
> >> but despite that I wasn't really sure if I wanted to pull it in - thus
> >> the long delay of me just seeing this in my list of pending pulls for
> >> almost a month, but never really getting to the point where I decided
> >> I want to commit to it.
> >
> > Interesting. I noticed that strscpy() says this in its comments:
> >
> >  * In addition, the implementation is robust to the string changing out
> >  * from underneath it, unlike the current strlcpy() implementation.
> >
> > The strscpy() interface is very nice, but shouldn't we also fix this strlcpy() 
> > unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call 
> > sites?
> 
> How about every single occurence of %s in a format string? vsnprintf
> also has that "issue", but has it actually ever been a problem? The
> window for something bad to happen is probably also much larger in the
> printf case, and especially when when some %p extension is used and/or
> the vsnprintf user is kasprintf() (where we 'replay' the formatting,
> having hopefully obtained a correct-sized buffer).
>
> In fact, writing this, it occurs to me that we should probably check the
> return value of the second vsnprintf call in kasprintf and compare to
> the first, issuing a warning if they don't match.
> 
> I'm not against making strlcpy more robust, but I think the theoretical
> race is far more likely to manifest through a member of the printf
> family.
> 
> Note that, unless one cares for performance or worries about 2G+
> length strings, strlcpy could just be 'return snprintf(dst, len, "%s",
> src);', which would give the "check for insanely large/negative len" for
> free [though not giving strlen(src) as return value - but the caller is much
> more likely to be tripped up by no copying having taken place anyway]. 
> 
> > Another problem is that strlcpy() will also happily do bad stuff if we pass
> > it a negative size. Instead of that we will from now on print a (one time)
> > warning and return safely.
> 
> Well, not too sure about that 'safely'. If the caller somehow managed to compute 
> an insanely large (remaining) capacity in the buffer and has that in a size_t 
> variable, then proceeds to comparing the return value to the supposed buffer 
> size to check for overflow, he will think that everything is fine and proceed to 
> using likely uninitialized contents of his buffer.
> 
> I think a return value of 0 might be slightly better. Assuming the caller has 
> the capacity in a signed variable (so it only became huge by being converted to 
> size_t) and makes a signed comparison with the return value, both 0 and strlen() 
> triggers an overflow check, so we wouldn't be worse off in that case. Clearly 
> the same is true if the return value is not used at all. If the return value is 
> used mindlessly for advancing dst and decrementing the capacity, staying put is 
> probably better.

Ok, I can certainly change the return value to 0, but note that the (insane!) 
return value of strlcpy() gets used in only about 0.8% of the cases:

  triton:~/tip> git grep -w strlcpy | wc -l
  2097
  triton:~/tip> git grep -w strlcpy | grep -w if | wc -l
  11

... so this all is pretty theoretical I think, and we could as well just migrate 
all those standalone strlcpy() users that don't check the return code over to 
strscpy()!

This would probably speed up all those usecases, so it's a nice optimization.

Then we could convert the remaining ~20 call sites and mark strlcpy() as a working 
but deprecated API.

Linus, would you object to such patches, if it's done in a relatively painless 
fashion: not propagated into -next but generated automatically late in the merge 
window or right after -rc1 or so.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> On Mon, Oct 05 2015, Ingo Molnar <mingo@kernel.org> wrote:
> 
> > * Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >
> >> So I finally pulled it. I like the patch, I like the new interface, but 
> >> despite that I wasn't really sure if I wanted to pull it in - thus the long 
> >> delay of me just seeing this in my list of pending pulls for almost a month, 
> >> but never really getting to the point where I decided I want to commit to it.
> >
> > Interesting. I noticed that strscpy() says this in its comments:
> >
> >  * In addition, the implementation is robust to the string changing out
> >  * from underneath it, unlike the current strlcpy() implementation.
> >
> > The strscpy() interface is very nice, but shouldn't we also fix this strlcpy() 
> > unrobustness/race it refers to, in light of the 2000+ existing strlcpy() call 
> > sites?
> 
> How about every single occurence of %s in a format string? vsnprintf also has 
> that "issue", but has it actually ever been a problem? The window for something 
> bad to happen is probably also much larger in the printf case, and especially 
> when when some %p extension is used and/or the vsnprintf user is kasprintf() 
> (where we 'replay' the formatting, having hopefully obtained a correct-sized 
> buffer).
> 
> In fact, writing this, it occurs to me that we should probably check the return 
> value of the second vsnprintf call in kasprintf and compare to the first, 
> issuing a warning if they don't match.
> 
> I'm not against making strlcpy more robust, but I think the theoretical race is 
> far more likely to manifest through a member of the printf family.

So the printf family is generally less frequently used in ABI output than string 
copies, but yeah, since there are 15,000 s[n]printf() calls in the kernel it's 
more likely to be an issue not just by virtue of timing, but also by sheer mass of 
usage, statistically.

So I'd improve it all in the following order:

  - fix the strscpy() uninitialized use

  - base strlcpy() on strscpy() via the patch I sent. This makes all users faster 
    and eliminates the theoretical race.

  - phase out 'simple' strlcpy() uses via an automated patch. This gets rid of 
    2,000 strlcpy() call sites in a single pass.

  - phase out the remaining two dozen or so 'complex' strlcpy() uses one by one.

  - mark strlcpy() deprecated, add checkpatch warning.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Rasmus Villemoes]

On Tue, Oct 06 2015, Ingo Molnar <mingo@kernel.org> wrote:

> * Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:
>
>> 
>> I'm not against making strlcpy more robust, but I think the theoretical race is 
>> far more likely to manifest through a member of the printf family.
>
> So the printf family is generally less frequently used in ABI output than string 
> copies,

Huh? snprintf and friends are often used just to copy or concatenate
strings (essentially, any format string containing no specifiers other
than %s does exactly that) - even if a str*() function could do the same
thing. I see no reason to believe this wouldn't also be done in cases
where the final string ends up being presented to userspace.

> but yeah, since there are 15,000 s[n]printf() calls in the kernel it's 
> more likely to be an issue not just by virtue of timing, but also by sheer mass of 
> usage, statistically.

Yes.

> So I'd improve it all in the following order:
>
>   - fix the strscpy() uninitialized use
>
>   - base strlcpy() on strscpy() via the patch I sent. This makes all users faster 
>     and eliminates the theoretical race.

I'm not so sure about that part. I'd strongly suspect that the vast
majority of strings handled by strlcpy (and in the future strscpy) are
shorter than 32 bytes, so is all the word_at_a_time and pre/post
alignment yoga really worth it? strscpy is 299 bytes - that's a lot of
instruction cache lines, and it will almost always be cache cold. This
isn't an argument against basing strlcpy on strscpy (that would likely
just make the former a little smaller), but I'd like to see numbers
(cycle counts, distribution of input lengths, ...)  before I believe in
the performance argument.

>   - phase out 'simple' strlcpy() uses via an automated patch. This gets rid of 
>     2,000 strlcpy() call sites in a single pass.

That seems to be exactly the kind of mass-conversion Linus referred to
above. Also, you can't really do it if strscpy keeps it __must_check
annotation, as you'd then introduce 2000+ warnings...

Rasmus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> On Tue, Oct 06 2015, Ingo Molnar <mingo@kernel.org> wrote:
> 
> > * Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:
> >
> >> 
> >> I'm not against making strlcpy more robust, but I think the theoretical race is 
> >> far more likely to manifest through a member of the printf family.
> >
> > So the printf family is generally less frequently used in ABI output than string 
> > copies,
> 
> Huh? snprintf and friends are often used just to copy or concatenate
> strings (essentially, any format string containing no specifiers other
> than %s does exactly that) - even if a str*() function could do the same
> thing. I see no reason to believe this wouldn't also be done in cases
> where the final string ends up being presented to userspace.

But 'format string' usually means 'human output', and most of our ABI
pertains to system calls where we rarely form human output, we typically
generate programmatically actionable data structures.

We have procfs and sysfs as well, where format strings are indeed dominant, but 
are you sure this race exists in snprintf() in that form? I.e. can the return 
value of snprintf() be different from the true length of the output string, if the 
source string is modified in parallel?

> > So I'd improve it all in the following order:
> >
> >   - fix the strscpy() uninitialized use
> >
> >   - base strlcpy() on strscpy() via the patch I sent. This makes all users faster 
> >     and eliminates the theoretical race.
> 
> I'm not so sure about that part. I'd strongly suspect that the vast
> majority of strings handled by strlcpy (and in the future strscpy) are
> shorter than 32 bytes, so is all the word_at_a_time and pre/post
> alignment yoga really worth it?

That's a good question, I'll measure it.

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Rasmus Villemoes]

On Wed, Oct 07 2015, Ingo Molnar <mingo@kernel.org> wrote:

> We have procfs and sysfs as well, where format strings are indeed dominant, but 
> are you sure this race exists in snprintf() in that form? I.e. can the return 
> value of snprintf() be different from the true length of the output string, if the 
> source string is modified in parallel?

Well, if truncation has happened the return value is different
(larger). But assuming the output buffer is large enough, the 'compute
strlen, then do copying, potentially copying a nul byte which wasn't
there moments before' is pretty obvious:

lib/vsprintf.c:

static noinline_for_stack
char *string(char *buf, char *end, const char *s, struct printf_spec spec)
{
	int len, i;

	if ((unsigned long)s < PAGE_SIZE)
		s = "(null)";

	len = strnlen(s, spec.precision);

	if (!(spec.flags & LEFT)) {
		while (len < spec.field_width--) {
			if (buf < end)
				*buf = ' ';
			++buf;
		}
	}
	for (i = 0; i < len; ++i) {
		if (buf < end)
			*buf = *s;
		++buf; ++s;
	}
	while (len < spec.field_width--) {
		if (buf < end)
			*buf = ' ';
		++buf;
	}

	return buf;
}

(spec.precision is an s16 which by default is set to -1, so for the
usual case of plain %s the upper bound in strnlen is (size_t)-1,
effectively infinity). If it wasn't for the field width padding it would
probably not be that hard to fix.

But, to rephrase an earlier question: Can anyone point to an instance
where the strlcpy source or a %s argument to a printf function can
actually change under us? I'd like to see if one can intentionally
trigger the potential race, but I suspect that the vast majority cannot
have a problem - maybe someone has an idea of specific places that are
worth looking at.

>> > So I'd improve it all in the following order:
>> >
>> >   - fix the strscpy() uninitialized use
>> >
>> >   - base strlcpy() on strscpy() via the patch I sent. This makes all users faster 
>> >     and eliminates the theoretical race.
>> 
>> I'm not so sure about that part. I'd strongly suspect that the vast
>> majority of strings handled by strlcpy (and in the future strscpy) are
>> shorter than 32 bytes, so is all the word_at_a_time and pre/post
>> alignment yoga really worth it?
>
> That's a good question, I'll measure it.

Here's a few pseudo-datapoints. About half the strlcpy instances (just
from lazy grepping) has a string literal as src, and those only have
about 1/8th chance of being aligned. A quick skim through a small
vmlinux showed 34 calls of strlcpy where %rsi was easily seen to be a
literal address, of which 7 were aligned. That's 1/5, but the sample
size is rather small (also, the 1/8 is admittedly an underestimate,
since gcc seems to put long enough literals in rodata.str1.8).

Rasmus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Linus Torvalds]

On Wed, Oct 7, 2015 at 10:04 AM, Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
>
> Well, if truncation has happened the return value is different
> (larger). But assuming the output buffer is large enough, the 'compute
> strlen, then do copying, potentially copying a nul byte which wasn't
> there moments before' is pretty obvious:
[snip]

So I really refuse to worry about the snprintf() family of functions
wrt this race. I don't think it was hugely important for strlcpy()
either - more of a "quality of implementation" issue rather than
anything fundamental - but for snprintf and friends it's an almost
unavoidable issue because of how snprintf works.

Saying that 'strlcpy()' and 'snprintf("%s")' are equivalent is true
only in the loosest sense. Yes, they return the same return value.
Yes, the result string should be the same. But the two are completely
different despite that.

snprintf() has to handle all the *other* cases than just "%s",
including right-justification, string precision handling, etc etc. It
is effectively impossible to do without doing "strlen()" on the source
of the string beforehand. As a result, snprintf() is fundamentally
always going to be racy wrt the string changing during the call.

So the simple end result is that we shouldn't worry about it, and if
you are doing snprintf() on a changing string, you should just be
aware of it. We *do* actually do that, for things like "current->comm"
that really can change while being printed out. We just don't care
deeply, and have in fact been removing locks in this area, because the
end result is still guaranteed to be NUL-terminated etc.

Can we get odd truncated printouts in the (very very very unlikely)
case that the string is being changed? Yes. We just don't care.

With strlcpy(), the situation is different at least in the sense that
we *can* write a source-modification-safe version. Of course, the end
result will still be undefined, but at least the resulting string
length in the destination can be made to not disagree violently with
the return value.

Do we care? Probably not. If you do strlcpy() on strings that change
without using locking, it's either a serialization bug, or you really
don't care very deeply about the end result anyway (ie it's something
like the "current->comm" issue). But just from a quality of
implementation standpoint, I think it would be good to just do the
RightThing(tm) anyway.

That's particularly true since we should be able to do it trivially by
just implementing strlcpy() using strscpy() plus the overflow fixup.
But let's wait with that until people are happy about the state of
strscpy. There's absolutely no rush, and in fact the one thing I
absolutely wanted to avoid was to have the introduction of strscpy()
resulting in pointless churn elsewhere, so let's do the *opposite* of
rushing into this, and just say :"ok, some day we should do this, just
in case"

> Here's a few pseudo-datapoints. About half the strlcpy instances (just
> from lazy grepping) has a string literal as src, and those only have
> about 1/8th chance of being aligned.

Hmm. I think gcc actually tends to align string literals - at least on
architectures where unaligned accesses tend to be more expensive and
we do the whole SLOW_UNALIGNEd handling etc.

I don't think gcc does it on x86, but on x86 we don't much care.
Somebody on ppc or ARM might want to check.

                 Linus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> So I really refuse to worry about the snprintf() family of functions wrt this 
> race. I don't think it was hugely important for strlcpy() either - more of a 
> "quality of implementation" issue rather than anything fundamental - but for 
> snprintf and friends it's an almost unavoidable issue because of how snprintf 
> works.
> 
> Saying that 'strlcpy()' and 'snprintf("%s")' are equivalent is true only in the 
> loosest sense. Yes, they return the same return value. Yes, the result string 
> should be the same. But the two are completely different despite that.
> 
> snprintf() has to handle all the *other* cases than just "%s", including 
> right-justification, string precision handling, etc etc. It is effectively 
> impossible to do without doing "strlen()" on the source of the string 
> beforehand. As a result, snprintf() is fundamentally always going to be racy wrt 
> the string changing during the call.
> 
> So the simple end result is that we shouldn't worry about it, and if you are 
> doing snprintf() on a changing string, you should just be aware of it. We *do* 
> actually do that, for things like "current->comm" that really can change while 
> being printed out. We just don't care deeply, and have in fact been removing 
> locks in this area, because the end result is still guaranteed to be 
> NUL-terminated etc.
> 
> Can we get odd truncated printouts in the (very very very unlikely) case that 
> the string is being changed? Yes. We just don't care.

I do agree mostly, but I think we should still try to achieve the following two 
properties, if possible sanely+cheaply+cleanly:

 - the printed string should not contain spurious \0 bytes even if the %s source
   'races'. [I think this is true currently.]

 - the return code should correctly represent what snprintf did to the target
   string. [This might not be the case currently. But I'm not sure!]

Because that's a real concern I think: snprintf() return is used frequently to 
iterate over buffers, and it should correctly and reliably represent what it did, 
regardless of what the source buffer does - because snprintf obviously knows what 
it did to the output buffer, it has full, race-free control over it.

Whether left-alignment and other formatting details were calculated correctly, 
etc. is a secondary concern and cannot be guaranteed, but we should at least 
guarantee that we generated a single string, that we did nothing else, and that we 
correctly returned its length.

Agreed?

Thanks,

	Ingo

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Rasmus Villemoes]

On Thu, Oct 08 2015, Ingo Molnar <mingo@kernel.org> wrote:

> * Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>> So I really refuse to worry about the snprintf() family of functions wrt this 
>> race. I don't think it was hugely important for strlcpy() either - more of a 
>> "quality of implementation" issue rather than anything fundamental - but for 
>> snprintf and friends it's an almost unavoidable issue because of how snprintf 
>> works.
>>
[snip]
>> 
>> Can we get odd truncated printouts in the (very very very unlikely) case that 
>> the string is being changed? Yes. We just don't care.
>
> I do agree mostly, but I think we should still try to achieve the following two 
> properties, if possible sanely+cheaply+cleanly:
>
>  - the printed string should not contain spurious \0 bytes even if the %s source
>    'races'. [I think this is true currently.]

Sorry, no, that's not true currently.

>  - the return code should correctly represent what snprintf did to the target
>    string. [This might not be the case currently. But I'm not sure!]

It does, in fact, represent "the number of characters, excluding the
trailing nul byte, that would have been written if the output buffer is
big enough" - but in some cases some of those bytes may happen to be
'\0'.

[The %s race is the only way I can see spurious \0, but \0 can also
legitimately be put in the output using %c, or maybe these days also
with some %p extension.]

> Because that's a real concern I think: snprintf() return is used frequently to 
> iterate over buffers, and it should correctly and reliably represent what it did, 
> regardless of what the source buffer does - because snprintf obviously knows what 
> it did to the output buffer, it has full, race-free control over it.
>
> Whether left-alignment and other formatting details were calculated correctly, 
> etc. is a secondary concern and cannot be guaranteed, but we should at least 
> guarantee that we generated a single string, that we did nothing else, and that we 
> correctly returned its length.
>
> Agreed?

No. More precisely, I don't agree with left-alignment etc. being a
secondary concern.

It's hard not to agree with the overall "let's make it more robust if it
can be done sanely+cheaply+cleanly". I was a bit skeptical about whether
those three requirements could be met, since we'd have to do
byte-by-byte traversal of the string, maybe-copying it to the output as
we go along, but then right-alignment would require us to do a memmove,
but not before we've done some complicated bookkeeping
exercise. However, now that I read the source again, it seems that Al
Viro already did that exercise when he added dentry(). So maybe it's
doable without a net increase in LOC.

Rasmus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Rasmus Villemoes]

On Mon, Oct 05 2015, Ingo Molnar <mingo@kernel.org> wrote:

> * Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>> On Thu, Sep 10, 2015 at 8:43 PM, Chris Metcalf <cmetcalf@ezchip.com> wrote:
>> >
>> > Please pull the following changes for 4.3 from:
>> >
>> >   git://git.kernel.org/pub/scm/linux/kernel/git/cmetcalf/linux-tile.git strscpy
>> 
>> So I finally pulled it. I like the patch, I like the new interface,
>> but despite that I wasn't really sure if I wanted to pull it in - thus
>> the long delay of me just seeing this in my list of pending pulls for
>> almost a month, but never really getting to the point where I decided
>> I want to commit to it.
>
> Interesting. I noticed that strscpy() says this in its comments:
>
>  * In addition, the implementation is robust to the string changing out
>  * from underneath it, unlike the current strlcpy() implementation.

Apologies for beating a dead horse, but:

		c = *(unsigned long *)(src+res);
		if (has_zero(c, &data, &constants)) {
			data = prep_zero_mask(c, data, &constants);
			data = create_zero_mask(data);
			*(unsigned long *)(dest+res) = c & zero_bytemask(data);
			return res + find_zero(data);
		}
		*(unsigned long *)(dest+res) = c;

I wonder whether an insane compiler might actually reload c before
storing to dest+res, so that we'd have exactly the same problem of
embedded nul characters? And similarly in the byte-by-byte case:

		char c;

		c = src[res];
		dest[res] = c;
		if (!c)
			return res;

(yes, there's a store between the load and the test, and the compiler
probably can't know or prove that src and dest don't alias - but we're
storing c, so a sufficiently clever _and_ insane compiler could test
src[res]). Would READ_ONCE be justified?

Rasmus

Re: [PATCH] string: Improve the generic strlcpy() implementation

[Chris Metcalf]

On 10/19/2015 08:42 AM, Rasmus Villemoes wrote:
> On Mon, Oct 05 2015, Ingo Molnar <mingo@kernel.org> wrote:
>> Interesting. I noticed that strscpy() says this in its comments:
>>
>>   * In addition, the implementation is robust to the string changing out
>>   * from underneath it, unlike the current strlcpy() implementation.
> Apologies for beating a dead horse, but:
>
> 		c = *(unsigned long *)(src+res);
> 		if (has_zero(c, &data, &constants)) {
> 			data = prep_zero_mask(c, data, &constants);
> 			data = create_zero_mask(data);
> 			*(unsigned long *)(dest+res) = c & zero_bytemask(data);
> 			return res + find_zero(data);
> 		}
> 		*(unsigned long *)(dest+res) = c;
>
> I wonder whether an insane compiler might actually reload c before
> storing to dest+res, so that we'd have exactly the same problem of
> embedded nul characters?

Using READ_ONCE() on x86_64 with gcc 4.8 adds a bit of
overhead; for some reason the compiler converts some
mov instructions to lea+mov, unnecessarily as far as I can see.
And looking at older compilers, gcc 4.4 substantially
pessimizes the output with READ_ONCE, though perhaps we
don't care about compilers that old.

Still, your argument is certainly plausible in terms of
actually guaranteeing the semantics we are claiming rather
than leaving it to the compiler to Do The Right Thing.
Unsurprisingly, the current code is causing the compiler
to do the right thing, but of course past performance is no
guarantee of future results, as they say.

So I'm kind of on the fence, maybe leaning slightly
towards thinking the READ_ONCE semantics is worth it.
Maybe someone with a tip gcc can see if the performance
difference has been fixed there?

-- 
Chris Metcalf, EZChip Semiconductor
http://www.ezchip.com